bounding box when scanning using homogenous coordinates

[nirradi]

I am trying to determine a bounding box for a triangle using homogenous coordinates only (x,y,z,w), i want to avoid divide by w at all cost. Does anyone have a suggestion on how to that?

 

[RoOoBo]

I am trying to determine a bounding box for a triangle using homogenous coordinates only (x,y,z,w), i want to avoid divide by w at all cost. Does anyone have a suggestion on how to that?

Sure, use the whole viewport (or scissor box) as 'bounding' box .

I didn't find any way that would work (but don't give up, creating mathematic theorems from scratch is not my strong point). At the end I decided that a division by w wasn't really that costly nowadays and what you really want to avoid is dividing by 0. So the solution I used was to divide by w only when it was possible and then use those vertex positions to create the bounding box. When it wasn't possible I would use the whole viewport, or some of the viewport borders, complemented with any of the vertices that had a non zero w, as the bounding box, then a slow recursive descend to hell. Source code in the usual place.

In normal geometry a a w of 0 shouldn't be that frequent (I have never tried to mesure it in any case but given that performance should be quite horrible and would be easy noticeable it musn't be).

And please give me a call if you discover a method.

Actually it seems at some point I discovered something from the Great Master of Graphics (Blinn) but I still see divisions there. The other method I mentioned before is now only used for the scan tiled rasterizer (it makes even more sense as you don't need to waste time descending and you only need a start point for the scan operation, it can be a vertex or a viewport corner), not the recursive rasterizer.

This is the code of the GPUMath::boundingBox() function in the latest version of the simulator. I remember that another member of the group fixed a bug in one of the bounding box related functions but I don't remember if it was actually in GPUMath::boundingBox().

/*  Calculate bounding box from triangle homogeneous coordinates.

    Source: Blinn - Calculating Screen Coverage).

    XL = - 1, XR = 1
    YB = - 1, YT = 1
    ZN = - 1, ZF = 1

 */

void GPUMath::boundingBox(QuadFloat v1, QuadFloat v2, QuadFloat v3,
    s32bit x0, s32bit y0, u32bit width, u32bit height, s32bit &xMin, s32bit &xMax,
    s32bit &yMin, s32bit &yMax, s32bit &zMin, s32bit &zMax)
{
    u32bit outcodes[3];
    bool anyVis[3];
    u32bit accept;
    u32bit reject;
    f32bit minX, maxX, minY, maxY, minZ, maxZ;

#define BOUNDCODES(c, w, a, b, co0, co1)    \
    (((((c) - (a) * (w)) < 0.0f)?(co0):0x00) | (((-(c) + (b) * (w)) < 0.0f)?(co1):0x00))

    /*  Calculate the horizontal outcodes for the three vertices.  */
    outcodes[0] = BOUNDCODES(v1[0], v1[3], -1.0f, 1.0f, 0x01, 0x02);
    outcodes[1] = BOUNDCODES(v2[0], v2[3], -1.0f, 1.0f, 0x01, 0x02);
    outcodes[2] = BOUNDCODES(v3[0], v3[3], -1.0f, 1.0f, 0x01, 0x02);

    /*  Calculate the vertical outcodes for the three vertices.  */
    outcodes[0] |= BOUNDCODES(v1[1], v1[3], -1.0f, 1.0f, 0x04, 0x08);
    outcodes[1] |= BOUNDCODES(v2[1], v2[3], -1.0f, 1.0f, 0x04, 0x08);
    outcodes[2] |= BOUNDCODES(v3[1], v3[3], -1.0f, 1.0f, 0x04, 0x08);

    /*  Calculate the depth outcodes for the three vertices.  */
    outcodes[0] |= BOUNDCODES(v1[2], v1[3], -1.0f, 1.0f, 0x10, 0x20);
    outcodes[1] |= BOUNDCODES(v2[2], v2[3], -1.0f, 1.0f, 0x10, 0x20);
    outcodes[2] |= BOUNDCODES(v3[2], v3[3], -1.0f, 1.0f, 0x10, 0x20);

#undef BOUNDCODES

    /*  Calculate trivial acception.  */
    accept = outcodes[0] | outcodes[1] | outcodes[2];

    /*  Calculate trivial rejection.  */
    reject = outcodes[0] & outcodes[1] & outcodes[2];

//printf("outcodes[0] = %04x outcodes[1] = %04x outcodes[2] = %04x\n",
//outcodes[0], outcodes[1], outcodes[2]);

    /*  Check trivial rejection.  */
    GPU_ASSERT(
        if (reject != 0)
            panic("GPUMath", "boundingBox", "Triangle is trivially rejected (shouldn't happen here!).");
    )

    /*  Set initial bounding box limits.  */
    minX = minY = minZ = 1.0f;
    maxX = maxY = maxZ = -1.0f;

    /*  Set visibility flags.  */
    anyVis[0] = anyVis[1] = anyVis[2] = FALSE;

#define BOUNDRANGE(outcode, mask, c, w, min, max, vis)\
    if (((outcode) & (mask)) == 0)                  \
    {                                               \
        vis = TRUE;                                 \
                                                    \
        if (((c) - (min) * (w)) < 0.0f)             \
            (min) = (c) / (w);                      \
        if (((c) - (max) * (w)) > 0.0f)             \
            (max) = (c) / (w);                      \
    }

    /*  Calculate horizontal range.  */
    BOUNDRANGE(outcodes[0], 0x03, v1[0], v1[3], minX, maxX, anyVis[0])
    BOUNDRANGE(outcodes[1], 0x03, v2[0], v2[3], minX, maxX, anyVis[0])
    BOUNDRANGE(outcodes[2], 0x03, v3[0], v3[3], minX, maxX, anyVis[0])

    /*  Calculate vertical range.  */
    BOUNDRANGE(outcodes[0], 0x0c, v1[1], v1[3], minY, maxY, anyVis[1])
    BOUNDRANGE(outcodes[1], 0x0c, v2[1], v2[3], minY, maxY, anyVis[1])
    BOUNDRANGE(outcodes[2], 0x0c, v3[1], v3[3], minY, maxY, anyVis[1])

    /*  Calculate depth range.  */
    BOUNDRANGE(outcodes[0], 0x30, v1[2], v1[3], minZ, maxZ, anyVis[2])
    BOUNDRANGE(outcodes[1], 0x30, v2[2], v2[3], minZ, maxZ, anyVis[2])
    BOUNDRANGE(outcodes[2], 0x30, v3[2], v3[3], minZ, maxZ, anyVis[2])

#undef BOUNDRANGE

//printf("First pass >> %f %f %f %f\n", minX, maxX, minY, maxY);

#define BOUNDRANGE2(outcode, mask0, mask1, c, w, min, max, a, b)        \
    if ((((outcode) & (mask0)) != 0) && (((c) - (min) * (w)) < 0.0f))   \
        (min) = (a);                                                    \
    if ((((outcode) & (mask1)) != 0) && (((c) - (max) * (w)) > 0.0f))   \
        (max) = (b);

    /*  Check if all the vertices are visible (trivial accept).  */
    if (accept != 0)
    {
        /*  No trivial accept, second pass required.  */

        /*  Reset boundaries if none of the triangle points are visible.  */
        if (!anyVis[0])
        {
            minX = -1.0f;
            maxX = 1.0f;
        }
        else
        {
            /*  Second pass.  */
            BOUNDRANGE2(outcodes[0], 0x01, 0x02, v1[0], v1[3], minX, maxX, -1.0f, 1.0f);
            BOUNDRANGE2(outcodes[1], 0x01, 0x02, v2[0], v2[3], minX, maxX, -1.0f, 1.0f);
            BOUNDRANGE2(outcodes[2], 0x01, 0x02, v3[0], v3[3], minX, maxX, -1.0f, 1.0f);
        }

        if (!anyVis[1])
        {
            minY = -1.0f;
            maxY = 1.0f;
        }
        else
        {
            /*  Second pass.  */
            BOUNDRANGE2(outcodes[0], 0x04, 0x08, v1[1], v1[3], minY, maxY, -1.0f, 1.0f);
            BOUNDRANGE2(outcodes[1], 0x04, 0x08, v2[1], v2[3], minY, maxY, -1.0f, 1.0f);
            BOUNDRANGE2(outcodes[2], 0x04, 0x08, v3[1], v3[3], minY, maxY, -1.0f, 1.0f);
        }

        if (!anyVis[2])
        {
            minZ = -1.0f;
            maxZ = 1.0f;
        }
        else
        {
            /*  Second pass.  */
            BOUNDRANGE2(outcodes[0], 0x10, 0x20, v1[2], v1[3], minZ, maxZ, -1.0f, 1.0f);
            BOUNDRANGE2(outcodes[1], 0x10, 0x20, v2[2], v2[3], minZ, maxZ, -1.0f, 1.0f);
            BOUNDRANGE2(outcodes[2], 0x10, 0x20, v3[2], v3[3], minZ, maxZ, -1.0f, 1.0f);
        }
    }

#undef BOUNDRANGE2

//printf("Second pass >> %f %f %f %f\n", minX, maxX, minY, maxY);

    /*  Convert to viewport coordinates.  */
    xMin = GPU_MAX(s32bit(GPU_FLOOR(minX * (f32bit(width) * 0.5f) + f32bit(x0) + (f32bit(width) * 0.5f))) - 1, s32bit(x0));
    xMax = GPU_MIN(s32bit(GPU_FLOOR(maxX * (f32bit(width) * 0.5f) + f32bit(x0) + (f32bit(width) * 0.5f))) + 1, s32bit(x0 + width));
    yMin = GPU_MAX(s32bit(GPU_FLOOR(minY * (f32bit(height) * 0.5f) + f32bit(y0) + (f32bit(height) * 0.5f))) - 1, s32bit(y0));
    yMax = GPU_MIN(s32bit(GPU_FLOOR(maxY * (f32bit(height) * 0.5f) + f32bit(y0) + (f32bit(height) * 0.5f))) + 1, s32bit(y0 + height));
//printf("Viewport coords: %d %d %d %d\n", xMin, xMax, yMin, yMax);
}

 

[frogblast]

After trying to figure out this very problem, and failing, I divided my index lists up into blocks of ~200 indices, and usually there were no offending vertices (near or far clipping required) in the entire block. I only went down the more expensive path if a index block ended up contaminated. In practice, I performed the W divide during vertex processing, and then accumulated a bit to track if any of the vertices required near or far clipping. At the end of the block, I checked the bit once, and only then do I dive into the more expensive clipping (with the assumption that some outputs of vertex processing were undefined).

In practice, few enough blocks were offending, that it really didn't matter, especially compared to rasterization and fragment processing. It was worthwhile to assume the non-clipped case, and just catch anything else after the fact and clean up.

 

[nirradi]

In my case I only need a start point for the scan operation (and wanted the bounding box to give such a point) , i didnt understand from you answer if divide by w can be avoided in this case.

 

[RoOoBo]

As far as I know for scan rasterization you have to divide. I don't see how you could start scan on a random position and manage to hit the triangle. But there are solutions (that don't require complete projection and clipping the triangle against the frustum) in case you can't divide.

For recursive rasterization you don't need to divide. But you pay having to traverse the whole viewport recursively: up to log2(max(viewport width, viewportheight)) cycles until first fragment is generated.

For the scan tiled algorithm ATTILA only avoids the division by w when the w is 0 for the three vertices. In that case it uses one of the corners of the viewport or a point in the middle of the viewport area as the start point. For normal cases at least one of the vertex positions is divided by its w. Or at least that was the first implementation I wrote.

Right now it seems to be using the values from the Blinn based bounding box function to find the start point. See GPUMath::startPosition() for the new and old code (at the end of the function, non-reachable code). The bounding box function has the divisions but copes with problematic w values.