Skip to main content
GameDev.net gamedev.net
🔒 Locked

Frustrum Culling using cones and spheres?

Started by M16hty M0u53 Aug 1, 2002 at 12:13 PM 3 replies 1.3k views
Original Post
M16hty M0u53
M16hty M0u53
Whenever I read about frustrum culling, its always done using bounding boxes. I'm wondering if it could be done more efficiently using bounding spheres for objects to be tested and a bounding cone for the view frustrum. I know about using a sphere encompassing the view frustum to eliminate objects. I'm wondering if this approach might be faster than using the sphere and then the bounding box, or if it could be used in conjunction with either/both of those methods. Using a cone would not be 100% accurate, since monitors aren't circles; some objects along the edges would be kept when they hould be discarded (particularly around the midpoints of each side). Maybe using a second cone bounding the inside of the view frustrum (intersecting the midpoints of the sides, rather than the corners of the actual bounding box) could be used to identify objects around the border that could be tested using a bounding box. Testing the objects against 2 2D triangles (one for the horizontal and one for the vertical) might work better, though this would mean more comparisons. I'm just trying to think of new ways to do frustrum culling that might be faster. Testing each point of one bounding box against 6 planes seems like a lot of comparisons. I wish I could draw out all of the geometry, it would help explain this a lot better. Here is what I've worked out so far to test if a sphere is within a cone. This doesn't take the radius of the sphere into account, but it should be easy enough to add that. Variables - deltaX, deltaY, and deltaZ are the coordinates of the object in relation to the viewer viewerXZ is the horizontal rotation of the viewer viewerYZ is the vertical rotation of the viewer objectXZ is the horizontal rotation of the object in relation to the viewer objectYZ is the vertical rotation of the object in relation to the viewer minDepth and maxDepth are the limits of the view frustrum viewAngle is the angle of the cone Steps - 1. evaluate deltaX, deltaY, and deltaZ deltaX = objectX - viewerX (same for Y and Z) 2. check against minDepth and maxDepth deltaX^2 + deltaY^2 + deltaZ^2 < maxDepth^2 (same for minDepth) 3. evaluate objectXZ and objectYZ objectXZ = InverseTan(deltaX / deltaZ) - viewerXZ (same for YZ) 4. check if the object is in the cone (think of a circle given by the equation x + y = viewAngle^2, where x represents the XZ angle and y represents the YZ angle. test to see if the XZ and YZ angles for the object are within this circle) objectXZ^2 + objectYZ^2 < viewAngle^2 Using a lookup table for the InverseTan function would lose accuracy but increase speed tremendously. As it stands now, this method would only require three comparisons for each object (2 depth tests and 1 for the cone). Please post any thoughts/comments. [edited by - M16hty M0u53 on August 1, 2002 3:43:39 PM]
Yann L
Yann L
quote:

I''m just trying to think of new ways to do frustrum culling that might be faster. Testing each point of one bounding box against 6 planes seems like a lot of comparisons.


There is an ultra-efficient algorithm to check if a bounding box is inside/outside the frustum, it only takes 6 compares (and a few multiplications) per bounding box, and checks against the full frustum. You don''t need to check each of the 8 points individually, one single is enough (the trick is to know the right one).

If anyone is interested, I''ll try to dig it out.

/ Yann
SporadicFire
SporadicFire
im interested...if you can please find it.
M16hty M0u53
M16hty M0u53
I'd definitely like to see that.

Is there much overhead looking for the right point to compare with?

[edited by - M16hty M0u53 on August 2, 2002 1:53:24 PM]
Yann L
Yann L
Well, I can't find the reference paper anymore, so I really don't know who to credit for it.

There is a very small per frame overhead in determining the right point (6 matrix multiplies and 3 compares per frame and a little math for getting D). There is no special per bounding box overhead.

Here is a short (pseudo-code) overview, how it is done:


        
// A view frustum plane

typedef struct {
   vector3   Object_N;
   vector3   Eye_N;
   char      nidx, nidy, nidz;
   // ...other stuff...

} D_ViewFrustumPlane;

// The frustum has 6 planes

D_ViewFrustumPlane ViewFrustumPlanes[6];

// At the beginning of your engine:

void Init(void)
{
   // initialize ViewFrustumPlanes[0..5].Object_N with the object space normal of each frustum plane

}

// Then, do that every frame:

void PrepareFrustumClipping(void)
{
   // For each frustum plane

   for( p=0, current=ViewFrustumPlanes; p<6; p++, current++ ) {

      // You have to rotate the object space normal of the current plane into the eye-space of the current frame camera. 

      // Store the result in current->Eye_N

      current->Eye_N = TransformToEyeSpace( current->Object_N );

      // Compute the plane's D value for the new eye space normal

      current->D = ComputeD( ... )

      // Now set the indices for the largest x, y and z values of the rotated normal

      current->nidx = ( current->Eye_N.x > 0 ) ? 3 : 0;
      current->nidy = ( current->Eye_N.y > 0 ) ? 4 : 1;
      current->nidz = ( current->Eye_N.z > 0 ) ? 5 : 2;
}

// And finally, the bounding box against frustum clipping code. Call it every time you want to clip a bounding box. 

// It returns 1, if the box is inside (or partially inside) the frustum, 0 otherwise.


// the min & max values of the bounding box need to be stored in a array from 0 to 6, where:

// box[0]=xmin, box[1]=ymin, box[2]=zmin

// box[3]=xmax, box[4]=ymax, box[5]=zmax

// You could use unnamed unions to make access easier.


typedef struct {
   float   box[6];
   // ... other stuff here

} D_Object;

int IsBoundingBoxInFrustum( float *box )
{   
   for( p=0, current=ViewFrustrumPlanes; p<6; p++, current++ ) {
      if( (current->Eye_N.x*box[current->nidx] + current->Eye_N.y*box[current->nidy] + current->Eye_N.z*box[current->nidz] + current->D) < 0 ) return( 0 );
   }
   return( 1 );
}


I just cut that out from our game engine. There might be some errors here and there, since I needed to modify some stuff on the fly...

/ Yann

[edited by - Yann L on August 2, 2002 4:03:35 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.