Home

Culling makes close-ups with few objects so much faster.

(this text may be helpful to some; note that Racer these days uses a speedier approach than explained here, using bits to very quickly decide the intersection state of spheres, boxes and points)

To get faster drawing, I cull away objects speedily by checking whether the objects that make up your scene are inside the view frustum (the topped-off pyramid that defines the volume you can see onscreen). If they're outside, you need not render them, and if only a few visible remain, you can expect a very good speed-up.
Below is (most of the) code that makes up my base culler class. The only difficult thing is grabbing the plane equations from the projection and modelview matrix, which I did with the help of www.markmorley.com (see the references page; this page has disappeared, but I've kept a copy here). Note that I use the OpenGL axis system (Y+ up, X+ right, Z+ out of the screen), and also the OpenGL matrix scheme (my float m[16] match those expected by OpenGL).

Note the SphereInFrustum() is just a variant; the plane equations are useful also in deciding how far away an object is (the Z-distance), which might come in handy for Z-sorting blended polygons/objects. For my first frustum culling algorithm, I used a simple class that extends DCuller, and has an array (not a tree) of the objects' bounding sphere. Upon painting the track, I call DCullerSphereList::Paint(), which does roughly 'for all objects; if SphereInFrustum(object.boundingSphereCenter,object.boundingSphereRadius) then Paint(object)'. Although a tree is nicer, this was way faster to program, and with 500 objects or so, it is incredibly fast already on today's CPUs (with energy better spent on other parts for now).

   /*
    * DCuller - (view frustum) culling base class
    * 04-01-2001: Created! (19:29:18)
    * NOTES:
    * (C) MarketGraph/RvG
    */
   
   #include <d3/d3.h>
   #pragma hdrstop
   #include <d3/culler.h>
   #include <qlib/debug.h>
   DEBUG_ENABLE
   
   DCuller::DCuller()
   {
   }
   DCuller::~DCuller()
   {
   }
   
   /*********************************
   * Calculating the frustum planes *
   *********************************/
   void DCuller::CalcFrustumEquations()
   // From the current OpenGL modelview and projection matrices,
   // calculate the frustum plane equations (Ax+By+Cz+D=0, n=(A,B,C))
   // The equations can then be used to see on which side points are.
   {
     dfloat *m,t;
     DPlane3 *p;
     int i;
   
     // This piece of code taken from:
     // http://www.markmorley.com/opengl/frustumculling.html
     // Modified quite a bit to suit the D3 classes.
   
     // Retrieve matrices from OpenGL
     glGetFloatv(GL_MODELVIEW_MATRIX,matModelView.GetM());
     glGetFloatv(GL_PROJECTION_MATRIX,matProjection.GetM());
   
     // Combine into 1 matrix
     glGetFloatv(GL_PROJECTION_MATRIX,matFrustum.GetM());
     matFrustum.Multiply(&matModelView);
   
     // Get plane parameters
     m=matFrustum.GetM();
   
     p=&frustumPlane[RIGHT];
     p->n.x=m[3]-m[0];
     p->n.y=m[7]-m[4];
     p->n.z=m[11]-m[8];
     p->d=m[15]-m[12];
   
     p=&frustumPlane[LEFT];
     p->n.x=m[3]+m[0];
     p->n.y=m[7]+m[4];
     p->n.z=m[11]+m[8];
     p->d=m[15]+m[12];
   
     p=&frustumPlane[BOTTOM];
     p->n.x=m[3]+m[1];
     p->n.y=m[7]+m[5];
     p->n.z=m[11]+m[9];
     p->d=m[15]+m[13];
   
     p=&frustumPlane[TOP];
     p->n.x=m[3]-m[1];
     p->n.y=m[7]-m[5];
     p->n.z=m[11]-m[9];
     p->d=m[15]-m[13];
   
     p=&frustumPlane[PFAR];
     p->n.x=m[3]-m[2];
     p->n.y=m[7]-m[6];
     p->n.z=m[11]-m[10];
     p->d=m[15]-m[14];
   
     p=&frustumPlane[PNEAR];
     p->n.x=m[3]+m[2];
     p->n.y=m[7]+m[6];
     p->n.z=m[11]+m[10];
     p->d=m[15]+m[14];
   
     // Normalize all plane normals
     for(i=0;i<6;i++)
       frustumPlane[i].Normalize();
   }

   /**************
   * Classifying *
   **************/
   int DCuller::SphereInFrustum(const DVector3 *center,dfloat radius) const
   // Returns classification (INSIDE/INTERSECTING/OUTSIDE)
   {
     int i;
     const DPlane3 *p;
   
     for(i=0;i<6;i++)
     {
       p=&frustumPlane[i];
       if(p->n.x*center->x+p->n.y*center->y+p->n.z*center->z+p->d <= -radius)
         return OUTSIDE;
     }
     // Decide: Inside or intersecting
     return INTERSECTING;
   }

This code is my base class for culling, whatever kind. Below is for example DCullerSphereList(), which uses a list of bounding spheres to implement culling. Not the fastest structure, but very easy to implement and not bad at all performancewise. Realise that optimization must go into the part of the program where most time is spent. Calculating SphereInFrustum() for about 500 objects
(a small to medium track) isn't that costly, it seems. Ofcourse, better culling classes can always supersede the simple list.

   /*
   * DCullerSphereList - culling a list based on sphere bounding volumes
   * 04-01-2001: Created! (22:28:00)
   * NOTES:
   * - Meant more as a test of the DCuller equations.
   * (C) MarketGraph/RvG
   */

   #include <d3/d3.h>
   #pragma hdrstop
   #include <d3/culler.h>
   #include <qlib/debug.h>
   DEBUG_ENABLE

   DCullerSphereList::DCullerSphereList()
   {
     nodes=0;
     node=(DCSLNode*)qcalloc(MAX_NODE*sizeof(DCSLNode));
   }
   DCullerSphereList::~DCullerSphereList()
   {
     if(node)qfree(node);
   }

   /**********
   * Destroy *
   **********/
   void DCullerSphereList::Destroy()
   // Destroy culler
   {
     nodes=0;
   }

   /***********
   * Building *
   ***********/
   bool DCullerSphereList::AddGeode(DGeode *g)
   {
     DCSLNode *n;
     DBox box;
     if(nodes==MAX_NODE)return FALSE;
     n=&node[nodes];
     n->geode=g;
     g->GetBoundingBox(&box);
     box.GetCenter(&n->center);
     n->radius=box.GetRadius();
   
     nodes++;
   
     return TRUE;
   }

   /***********
   * Painting *
   ***********/
   void DCullerSphereList::Paint()
   {
     int i,count;
     DCSLNode *n;
   
     for(i=0;i<nodes;i++)
     {
       n=&node[i];
       if(SphereInFrustum(&n->center,n->radius)!=OUTSIDE)
       { count++;
         n->geode->Paint();
       }
     }
   }

That concludes the remarks about culling in Racer for now. It may have improved by the way, without me updating this page, but it
seems this is a nice introduction that makes you understand what is going on.

(last updated November 13, 2012 )