Tutorial no.6 - Frustum Culling
Introduction
If you're planning to write an 3D-Engine by yourself, you'll come across the problem that every thing get's slower, the bigger your maps or environments get.Although many of your sectors or objects may be outside of your view, they drag the rendering speed down.
Modern graphicscards have the z-buffer and other techniques to determine if a pixel will get overdrawn or not.But before they can determine this, you'll have to send them your object informations.Then the gfxcard does it's depht and visibility testings.
If your object lies behind another, or is outside of your view, your gfxcard will likley be smart enough to detect this, but even if your object isn't drawn, it'll cost you speed as you have to send the geometry data to your card across the AGP-bus.
Frustum Culling is an easy method of determing if an object lies within your view or not and is done before you send the objects data to your graphicscard.This will save a lot of bandwith and means much less work for your gfxcard.

So in this tutorial, I'll show you how to use the frustum culling.It's really not much work nor much maths but it's a very efficient way of boosting your rendering speed.

The TFrustum class
We're goint to implement frustum culling via a class called TFrustum, to make things easier.Here's the class :


TFrustum = object
   Frustum : array[0..5,0..3] of Single;
   function IsPointWithin(const pX, pY, pZ : Single) : Boolean;
   function IsBoxWithin(const pX, pY, pZ, pB, pH, pT : Single) : Boolean;
   procedure Calculate;
  end;
Calculating the frustum (procedure Calculate)
Now to the most important part of our TFrustum class.Before we can say if something is within the frustum or not, we need to calculate the six planes that define our frustum.


[01]  procedure TFrustum.Calculate;
[02]  var
[03]   ProjM, ModM, Clip : array[0..15] of Single;
[04]  begin
[05]  glGetFloatv(GL_PROJECTION_MATRIX, @ProjM);
[06]  glGetFloatv(GL_MODELVIEW_MATRIX, @ModM);
[07]  Clip[ 0] := ModM[ 0]*ProjM[ 0] + ModM[ 1]*ProjM[ 4] +
                  ModM[ 2]*ProjM[ 8] + ModM[ 3]*ProjM[12];
[08]  Clip[ 1] := ModM[ 0]*ProjM[ 1] + ModM[ 1]*ProjM[ 5] +
                  ModM[ 2]*ProjM[ 9] + ModM[ 3]*ProjM[13];
[09]  Clip[ 2] := ModM[ 0]*ProjM[ 2] + ModM[ 1]*ProjM[ 6] +
                  ModM[ 2]*ProjM[10] + ModM[ 3]*ProjM[14];
[10]  Clip[ 3] := ModM[ 0]*ProjM[ 3] + ModM[ 1]*ProjM[ 7] +
                  ModM[ 2]*ProjM[11] + ModM[ 3]*ProjM[15];
[11]  Clip[ 4] := ModM[ 4]*ProjM[ 0] + ModM[ 5]*ProjM[ 4] +
                  ModM[ 6]*ProjM[ 8] + ModM[ 7]*ProjM[12];
[12]  Clip[ 5] := ModM[ 4]*ProjM[ 1] + ModM[ 5]*ProjM[ 5] +
                  ModM[ 6]*ProjM[ 9] + ModM[ 7]*ProjM[13];
[13]  Clip[ 6] := ModM[ 4]*ProjM[ 2] + ModM[ 5]*ProjM[ 6] +
                  ModM[ 6]*ProjM[10] + ModM[ 7]*ProjM[14];
[14]  Clip[ 7] := ModM[ 4]*ProjM[ 3] + ModM[ 5]*ProjM[ 7] +
                  ModM[ 6]*ProjM[11] + ModM[ 7]*ProjM[15];
[15]  Clip[ 8] := ModM[ 8]*ProjM[ 0] + ModM[ 9]*ProjM[ 4] +
                  ModM[10]*ProjM[ 8] + ModM[11]*ProjM[12];
[16]  Clip[ 9] := ModM[ 8]*ProjM[ 1] + ModM[ 9]*ProjM[ 5] +
                  ModM[10]*ProjM[ 9] + ModM[11]*ProjM[13];
[17]  Clip[10] := ModM[ 8]*ProjM[ 2] + ModM[ 9]*ProjM[ 6] +
                  ModM[10]*ProjM[10] + ModM[11]*ProjM[14];
[18]  Clip[11] := ModM[ 8]*ProjM[ 3] + ModM[ 9]*ProjM[ 7] +
                  ModM[10]*ProjM[11] + ModM[11]*ProjM[15];
[19]  Clip[12] := ModM[12]*ProjM[ 0] + ModM[13]*ProjM[ 4] +
                  ModM[14]*ProjM[ 8] + ModM[15]*ProjM[12];
[20]  Clip[13] := ModM[12]*ProjM[ 1] + ModM[13]*ProjM[ 5] +
                  ModM[14]*ProjM[ 9] + ModM[15]*ProjM[13];
[21]  Clip[14] := ModM[12]*ProjM[ 2] + ModM[13]*ProjM[ 6] +
                  ModM[14]*ProjM[10] + ModM[15]*ProjM[14];
[22]  Clip[15] := ModM[12]*ProjM[ 3] + ModM[13]*ProjM[ 7] +
                  ModM[14]*ProjM[11] + ModM[15]*ProjM[15];
.
.
.
In Line [05], we extract our current Projectionmatrix and store it into an array of 16 singles.Line [06] does the same but with the current modelviewmatrix.
These two matrices are then combined throughout lines [07] to [22] and are saved as the clipping matrix.

The following lines now calculate the six planes of the frustum.The planes name values (Right, Left, Top, etc.) are defined in the const section of this unit.
.
.
.
[23]  Frustum[Right][A] := clip[ 3] - clip[ 0];
[24]  Frustum[Right][B] := clip[ 7] - clip[ 4];
[25]  Frustum[Right][C] := clip[11] - clip[ 8];
[26]  Frustum[Right][D] := clip[15] - clip[12];
[27]  NormalizePlane(self, Right);

[28]  Frustum[Left][A] := clip[ 3] + clip[ 0];
[29]  Frustum[Left][B] := clip[ 7] + clip[ 4];
[30]  Frustum[Left][C] := clip[11] + clip[ 8];
[31]  Frustum[Left][D] := clip[15] + clip[12];
[32]  NormalizePlane(self, Left);

[33]  Frustum[Bottom][A] := clip[ 3] + clip[ 1];
[34]  Frustum[Bottom][B] := clip[ 7] + clip[ 5];
[35]  Frustum[Bottom][C] := clip[11] + clip[ 9];
[36]  Frustum[Bottom][D] := clip[15] + clip[13];
[37]  NormalizePlane(self, Bottom);

[38]  Frustum[Top][A] := clip[ 3] - clip[ 1];
[39]  Frustum[Top][B] := clip[ 7] - clip[ 5];
[40]  Frustum[Top][C] := clip[11] - clip[ 9];
[41]  Frustum[Top][D] := clip[15] - clip[13];
[42]  NormalizePlane(self, Top);

[43]  Frustum[Back][A] := clip[ 3] - clip[ 2];
[44]  Frustum[Back][B] := clip[ 7] - clip[ 6];
[45]  Frustum[Back][C] := clip[11] - clip[10];
[46]  Frustum[Back][D] := clip[15] - clip[14];
[47]  NormalizePlane(self, Back);

[48]  Frustum[Front][A] := clip[ 3] + clip[ 2];
[49]  Frustum[Front][B] := clip[ 7] + clip[ 6];
[50]  Frustum[Front][C] := clip[11] + clip[10];
[51]  Frustum[Front][D] := clip[15] + clip[14];
[52]  NormalizePlane(self, Front);
[53]  end;
Those calculations store the results in the Frustum array of our TFrustum class.This calculations need to be executed after every viewchange.So if you're lazy, just call this procedure every frame after setting up your view, but before drawing anything.

Point in Frustum?
The easiest visibility test is to determine if a single point lies within our Frustum.This is the case, if the distance to all of the six frustum planes is positive (this means, that the point lies in front of the plane.If the value is negative, the point lies behind the plane).

To calculate this, we use this simple formula : Distance := (A*x) + (B*y) + (C*z) + D

So the function TFrustum.IsPointWithin(const pX, pY, pZ : Single) : Boolean simply loops through all the six planes and calculates the point's distance to this plane.If the distance is negative (i.e. the point lies behind), the function returns false.

[01]  function TFrustum.IsPointWithin(const pX, pY, pZ : Single) : Boolean;
[02]  var
[03]   i : Integer;
[04]  begin
[05]  Result := true;
[06]  for i := 0 to 5 do
[07]   if (Frustum[i][A]*pX + Frustum[i][B]*pY +
           Frustum[i][C]*pZ + Frustum[i][D]) <= 0 then
[08]    begin
[09]    Result := False;
[10]    exit;
[11]    end;
[12]  end;
Sphere in Frustum?
After determing if a point is in the frustum, doing the same with a sphere is the easiest task to do now.As you know, every sphere can be described by it's radius, so it's nothing more than a point (the center of the sphere) and it's radius.So this function just replaces the test against the zero value (to see if the point is behind the plane) with the test against the negative radius of the sphere.Very easy, isn't it?

[01]  function TFrustum.IsSphereWithin(const pX, pY, pZ,
                        pRadius : Single) : Boolean;
[02]  var
[03]   i : Integer;
[04]  begin
[05]  Result := true;
[06]  for i := 0 to 5 do
[07]   if (Frustum[i][A]*pX + Frustum[i][B]*pY +
           Frustum[i][C]*pZ + Frustum[i][D]) <= -pRadius then
[08]    begin
[09]    Result := False;
[10]    exit;
[11]    end;
[12]  end;
This is the visibilty test you'll mostly use for determing an objects visibility.This has three causes :
First, the Sphere test is the fastes, as only six calculations have to be done.Second, most objects' bounding volume can be described by a surrounding sphere.Third is that storing data for a sphere only needs four floating point values (three for the center point and one for the radius).
So use this test, instead of the box test if your object can be described by a surrounding sphere.

Box in Frustum?
Determing if a box is within the frustum isn't much harder than the sphere test.As you know a box has eight corners.So we loop through all six frustum planes again and test if one of these corners is in front of that plane.If that's the case, we can skip the other edges and advance to the next plane test.

[01]  function TFrustum.IsBoxWithin
        (const pX, pY, pZ, pB, pH, pT : Single) : Boolean;
[02]  var
[03]   i : Integer;
[04]  begin
[05]  Result := true;
[06]  for i := 0 to 5 do
[07]   begin
[08]   if (Frustum[i][A]*(pX-pB) + Frustum[i][B]*(pY-pH) +
           Frustum[i][C]*(pZ-pT) + Frustum[i][D]>0) then
[09]        continue;
[10]   if (Frustum[i][A]*(px+pB) + Frustum[i][B]*(py-pH) +
           Frustum[i][C]*(pz-pT) + Frustum[i][D]>0) then
[11]        continue;
[12]   if (Frustum[i][A]*(px-pB) + Frustum[i][B]*(py+pH) +
           Frustum[i][C]*(pz-pT) + Frustum[i][D]>0) then
[13]        continue;
[14]   if (Frustum[i][A]*(px+pB) + Frustum[i][B]*(py+pH) +
           Frustum[i][C]*(pz-pT) + Frustum[i][D]>0) then
[15]        continue;
[16]   if (Frustum[i][A]*(px-pB) + Frustum[i][B]*(py-pH) +
           Frustum[i][C]*(pz+pT) + Frustum[i][D]>0) then
[17]        continue;
[18]   if (Frustum[i][A]*(px+pB) + Frustum[i][B]*(py-pH) +
           Frustum[i][C]*(pz+pT) + Frustum[i][D]>0) then
[19]        continue;
[20]   if (Frustum[i][A]*(px-pB) + Frustum[i][B]*(py+pH) +
           Frustum[i][C]*(pz+pT) + Frustum[i][D]>0) then
[21]        continue;
[22]   if (Frustum[i][A]*(px+pB) + Frustum[i][B]*(py+pH) +
           Frustum[i][C]*(pz+pT) + Frustum[i][D]>0) then
[23]        continue;
[24]   Result := False;
[25]   end;
[26]  end;
As said before, this test needs much more calculations (up to 48) than the sphere test.So if you can use a bounding sphere for an object instead of a box do it, as it'll save you many calculations.

The sample application
This sample application renders plenty spheres and tests their visibility against the frustum.Use the buttons to test what difference it makes when you turn frustum culling off.



Download

Download the frustum culling demo including the sourcecode