The frustumCulling example

frustumCulling

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>
#include <QGLViewer/manipulatedCameraFrame.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()));


	viewer.setWindowTitle("frustumCulling");
	observer.setWindowTitle("scene observer");

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

	return application.exec();
}

Back to the examples main page.