Home Documentation Download Examples Developer

# The frustumCulling example

Frustum culling using `getFrustumPlanesCoefficients`.

A hierarchical octree structure is clipped against a camera's frustum clipping planes, obtained using `getFrustumPlanesCoefficients`. A second viewer displays an external view of the scene that exhibits the clipping (using `drawCamera()` to display the frustum).

This frustum culling implementation is quite naive. Many optimisation techniques are available in the litterature.

## frustumCulling.h

    #include <QGLViewer/qglviewer.h>

    class CullingCamera;

    class Viewer : public QGLViewer
    {
    public:
      void setCullingCamera(const CullingCamera* const cc) { cullingCamera = cc; }

    protected:
      virtual void draw();
      virtual void init();
      virtual QString helpString() const;

    private:
      const CullingCamera* cullingCamera;
    };

## frustumCulling.cpp

    #include "frustumCulling.h"
    #include "cullingCamera.h"
    #include "box.h"

    using namespace qglviewer;

    void Viewer::draw()
    {
      Box::Root->drawIfAllChildrenAreVisible(cullingCamera);

      if (cullingCamera == camera())
        // Main viewer computes its plane equation
        cullingCamera->computeFrustumPlanesEquations();
      else
        {
          // Observer viewer draws cullingCamera
          glLineWidth(4.0);
          glColor4f(1.0, 1.0, 1.0, 0.5);
          cullingCamera->draw();
        }
    }

    void Viewer::init()
    {
      // Restore previous viewer state.
      restoreStateFromFile();

      if (cullingCamera != camera())
        {
          // Observer viewer configuration
          glEnable(GL_BLEND);
          glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
          help();
        }

      glDisable(GL_LIGHTING);
    }

    QString Viewer::helpString() const
    {
      QString text("<h2>F r u s t u m C u l l i n g</h2>");

      text += "A hierarchical octree structure is clipped against the camera's frustum clipping planes, obtained ";
      text += "using <code>getFrustumPlanesCoefficients</code>. A second viewer uses <code>drawCamera()</code> to ";
      text += "display an external view of the first viewer's camera.<br><br>";

      text += "This frustum culling implementation is quite naive. Many optimisation techniques are available in ";
      text += "the litterature.";

      return text;
    }

## box.h

    #include <QGLViewer/camera.h>

    class CullingCamera;

    // An Axis Aligned Bounding Box octree hierarchy element.
    class Box
    {
    public:
      Box(const qglviewer::Vec& P1, const qglviewer::Vec& P2) : p1(P1), p2(P2) {};

      void draw() const;
      void drawIfAllChildrenAreVisible(const CullingCamera* camera) const;
      void buildBoxHierarchy(int l);

      // Lazy static member, so that it is shared by viewers
      static Box* Root;

    private:
      qglviewer::Vec p1, p2;
      Box* child[8];
      int level;
    };

## cullingCamera.h

    #include <QGLViewer/camera.h>

    class CullingCamera : public qglviewer::Camera
    {
    public:

      void computeFrustumPlanesEquations() const { getFrustumPlanesCoefficients(planeCoefficients); }

      float distanceToFrustumPlane(int index, const qglviewer::Vec& pos) const;
      bool sphereIsVisible(const qglviewer::Vec& center, float radius) const;
      bool aaBoxIsVisible(const qglviewer::Vec& p1, const qglviewer::Vec& p2, bool* entirely=NULL) const;

    private:
      // F r u s t u m   p l a n e s
      mutable GLdouble planeCoefficients[6][4];
    };

## box.cpp

    #include "box.h"
    #include "cullingCamera.h"

    using namespace std;
    using namespace qglviewer;

    // Static member initialization
    Box* Box::Root;

    void Box::draw() const
    {
      glColor3f(0.3*level, 0.2f, 1.0-0.3*level);
      glLineWidth(level+1);

      glBegin(GL_LINE_STRIP);
      glVertex3fv(Vec(p1.x, p1.y, p1.z));
      glVertex3fv(Vec(p1.x, p2.y, p1.z));
      glVertex3fv(Vec(p2.x, p2.y, p1.z));
      glVertex3fv(Vec(p2.x, p1.y, p1.z));
      glVertex3fv(Vec(p1.x, p1.y, p1.z));
      glVertex3fv(Vec(p1.x, p1.y, p2.z));
      glVertex3fv(Vec(p1.x, p2.y, p2.z));
      glVertex3fv(Vec(p2.x, p2.y, p2.z));
      glVertex3fv(Vec(p2.x, p1.y, p2.z));
      glVertex3fv(Vec(p1.x, p1.y, p2.z));
      glEnd();

      glBegin(GL_LINES);
      glVertex3fv(Vec(p1.x, p2.y, p1.z));
      glVertex3fv(Vec(p1.x, p2.y, p2.z));
      glVertex3fv(Vec(p2.x, p2.y, p1.z));
      glVertex3fv(Vec(p2.x, p2.y, p2.z));
      glVertex3fv(Vec(p2.x, p1.y, p1.z));
      glVertex3fv(Vec(p2.x, p1.y, p2.z));
      glEnd();
    }

    void Box::buildBoxHierarchy(int l)
    {
      level = l;
      const Vec middle = (p1+p2) / 2.0;
      for (unsigned int i=0; i<8; ++i)
        {
          // point in one of the 8 box corners
          const Vec point((i&4)?p1.x:p2.x, (i&2)?p1.y:p2.y, (i&1)?p1.z:p2.z);
          if (level > 0)
    	{
    	  child[i] = new Box(point, middle);
    	  child[i]->buildBoxHierarchy(level-1);
    	}
          else
    	child[i] = NULL;
        }
    }

    void Box::drawIfAllChildrenAreVisible(const CullingCamera* camera) const
    {
      static bool* entirely = new bool;

      if (camera->aaBoxIsVisible(p1, p2, entirely)) {
        if (*entirely)
          draw();
        else
          if (child[0])
    	for (int i=0; i<8; ++i)
    	  child[i]->drawIfAllChildrenAreVisible(camera);
          else
    	draw();
      }
    }

## cullingCamera.cpp

    #include "cullingCamera.h"

    using namespace qglviewer;

    float CullingCamera::distanceToFrustumPlane(int index, const Vec& pos) const
    {
      return pos * Vec(planeCoefficients[index]) - planeCoefficients[index][3];
    }

    bool CullingCamera::sphereIsVisible(const Vec& center, float radius) const
    {
      for (int i=0; i<6; ++i)
        if (distanceToFrustumPlane(i, center) > radius)
          return false;
      return true;
    }

    bool CullingCamera::aaBoxIsVisible(const Vec& p1, const Vec& p2, bool* entirely) const
    {
      bool allInForAllPlanes = true;
      for (int i=0; i<6; ++i)
        {
          bool allOut = true;
          for (unsigned int c=0; c<8; ++c)
    	{
    	  const Vec pos((c&4)?p1.x:p2.x, (c&2)?p1.y:p2.y, (c&1)?p1.z:p2.z);
    	  if (distanceToFrustumPlane(i, pos) > 0.0)
    	    allInForAllPlanes = false;
    	  else
    	    allOut = false;
    	}

          // The eight points are on the outside side of this plane
          if (allOut)
    	return false;
        }

      if (entirely)
        // Entirely visible : the eight points are on the inside side of the 6 planes
        *entirely = allInForAllPlanes;

      // Too conservative, but tangent cases are too expensive to detect
      return true;
    }

## main.cpp

    #include "frustumCulling.h"
    #include "cullingCamera.h"
    #include "box.h"
    #include <qapplication.h>

    using namespace qglviewer;

    int main(int argc, char** argv)
    {
      QApplication application(argc,argv);

      // Create octree AABBox hierarchy
      const qglviewer::Vec p(1.0, 0.7f, 1.3f);
      Box::Root = new Box(-p, p);
      Box::Root->buildBoxHierarchy(4);

      // Instantiate the two viewers.
      Viewer viewer, observer;

      // Give v a cullingCamera;
      Camera* c = viewer.camera();
      CullingCamera* cc = new CullingCamera();
      viewer.setCamera(cc);
      delete c;

      // Both viewers share the culling camera
      viewer.setCullingCamera(cc);
      observer.setCullingCamera(cc);

      // Place observer
      observer.setSceneRadius(10.0);
      observer.camera()->setViewDirection(qglviewer::Vec(0.0, -1.0, 0.0));
      observer.showEntireScene();

      // Make sure every culling Camera movement updates the outer viewer
      QObject::connect(viewer.camera()->frame(), SIGNAL(manipulated()), &observer, SLOT(updateGL()));
      QObject::connect(viewer.camera()->frame(), SIGNAL(spun()), &observer, SLOT(updateGL()));

    #if QT_VERSION < 0x040000
      // Set the viewer as the application main widget.
      application.setMainWidget(&viewer);
    #else
      viewer.setWindowTitle("frustumCulling");
      observer.setWindowTitle("scene observer");
    #endif

      // Show the viewers' windows.
      viewer.show();
      observer.show();

      return application.exec();
    }

Back to the examples main page.

Last modified on Sunday, February 28, 2010.