Frustum culling problem

it would be useful if you post your source code

If all the points of the box are behind any ONE of the planes, then it can be rejected.

Death of one is a tragedy, death of a million is just a statistic.

quote:

---

Original post by TheGecko
Hey people,

Take a look at this image:



In my code,if the frustrum intersects the bounding box like this, then the bounding box gets rejected and nothing is drawn.Is there any efficient(read: non cpu intensive) way to fix this?

Incase you are wondering,yes,the bounding box should be drawn since it intersects with the frustum

Thanx for any help.



[edited by - TheGecko on April 13, 2002 6:05:40 PM]

---

I guess that you are checking if any of the corners of the box is in the viewing frustrum. Am i right? In distant boxes the error rate is low, but in closer boxes things like that can happen.

Im guessing that since it was my first attempt at checking frustum visibility ... and i still haven''t solved it since it was sthing that could be left for later

Kenny Hoff has done some good work here:
http://www.cs.unc.edu/~hoff/research/vfculler/boxvfc/boxvfc.html

---

Helpful links:
How To Ask Questions The Smart Way | Google can help with your question | Search MSDN for help with standard C or Windows functions

Thanx guys...I got it working with this method described below and it works perfectly!

-----------------------
Above, we can see that although the four corner points of the bounding box are outside the view frustum, the bounding box would be partially visible, as one of its edges intersects the frustum. To get around this problem, we have to test each plane, one at a time, against just a single point on the bounding box. This point will be one of the corners of our bounding box, but which corner point we use is completely dependant on the orientation of the current frustum plane being tested. If we imagine that the AABB is completely outside the frustum and just about to intersect the current plane being tested, the point we wish to find would be the first point (corner) on the box that would intersect it. This point is called the ''negative'' or ''near'' point and is the corner of the bounding box that would be first to intersect the current plane if the box was in front of it. What we will do is look at each component of the plane normal, and find which corner point of the AABB we have to use. We do this for each plane we test because each plane will have a different orientation. Therefore, the corner of the AABB that we use ''the near point'' for will be different for each plane. The basic principle is this:

1) For each frustum plane we test the plane normal.

2) If the ''x'' component of the plane normal is negative, then we use the bounding box''s x maximum point as our test point''s x component. Otherwise, we use the bounding box''s x minimum component.

3) If the ''y'' component of the plane normal is negative, then we use the bounding box''s y maximum point as our test point''s y component. Otherwise, we use the bounding box''s y minimum component.

4) If the ''z'' component of the plane normal is negative, then we use the bounding box''s z maximum point as our test point''s z component. Otherwise, we use the bounding box''s z minimum component.

At this point, we have now constructed a point (vector) to test against the clip plane. If this point is in front of the current plane (remember frustum planes point outwards), then we can bail out of the function immediately and do not have to check the other planes, because if this ''near'' point is outside (in front) of the planes then the entire AABB must be outside the frustum.

If, however, the ''near'' point is behind the plane, then we must test the other planes. For every plane that we test, we have to build a new ''near'' point to test, depending on the orientation of the plane normal. If at any point the current ‘near’ point is in front of the current plane being tested, then we can bail because the AABB is completely outside the frustum. If, however, we test all six planes and do not find a ''near'' point that is in front of one of the planes, this means that the AABB is at least partially inside the frustum and the function should return ‘true.’
-----------------------------

Hope that helps you folks

Here's a code snippet:

bool frustum_cull(const short* mins, const short* maxs)
{
    for (int i = 0; i < 5; i++)
    {
        const short* min = mins, *max = maxs;
        const float* n = frustum_planes[ i ].normal;
        float d = -frustum_planes[ i ].dist;

        d += (*n>0 ? (*n*(float)*min) : (*n*(float)*max)); min++, max++; n++;
        d += (*n>0 ? (*n*(float)*min) : (*n*(float)*max)); min++, max++; n++;
        d += (*n>0 ? (*n*(float)*min) : (*n*(float)*max)); min++, max++; n++;

        if (d > 0)
            return true;
    }

    return false;
}
   

mins and maxs are the minimum and maximum points of the rectangle (i.e top-left-back and bottom-right-front points). The source variable passed is an array of 3 shorts with the XYZ coordinates. This planes are stored using a zero-based normal, and a distance representing the magnitude of the plane along the normal from the origin.

I'm still figuring this one out. It works, but I'm decoding the math

[edited by - Zipster on April 22, 2002 2:00:49 AM]

I use this method. Catches all of those funny cases where the polygon overlaps or completely engulfs the frustum, and is pretty quick.

1. Assign bitcodes to each half-plane of the frustum, a la cohen sutherland clipping.

                      00001

                 _/__________|_
         10000   /           |
                /            |
               /             |
             \/              |   00010
             /\     00000    | 
               \             |
       01000    \            |
                 \           |
                 _\__________|_
                   \         |

                      00100 
 

2. Calculate the bitcode for all points within the bounding box.

3. AND the bitcodes for all points together. If it is nonzero, the triangle definitely does not intersect the frustum. You can check this after each iteration - if it is zero at any stage then you can draw the polygon.