View Frustum Culling

Descriptions

Frustum: a frustum is a geometrical shape, it is a pyramid in where the pointed bit has been cut by a plane parallel to the base.(Weisstein, Eric W, 1999-2015).

View frustum: It is the space of the world that appears on the screen. The field of view of the camera. The shape of the view frustum is usually the frustum of a rectangular pyramid. (Microsoft, 2015).

View frustum culling: It is a technique used to remove objects that are not inside the view frustum from the rendering process (ARF, 2015). It improves efficiency because objects that are outside of the view frustum are not visible and drawing them would be a waste of resources.

Simulation

The simulation consists of a car that the user can control (from now on "the player") using the directional keys and other static cars.

All the cars have an AABB (Jeff Lander, 2000) around them, this is the box that we are going to test against the 6 planes of the frustum to check if the cars should be drawn or not.

In the demonstration, you can drive the car around. On the top right corner, the HUD will display how many cars are being drawn at that moment depending on whether they are inside the view frustum or not.

- 3 cars inside the view frustum (including the player).

- Screenshot taken on the same position with a different camera perspective,

now there are only 2 cars in the view frustum

The view frustum consists of 6 planes (far, near, right, left, top, bottom). Planes have a front and a back face depending where the normal is facing. In the view frustum all planes face inwards.

For an object to be inside the frustum, any of its vertices must be in front of all 6 planes. We can use the formula to find the distance between a point and a plane to know if the vertex is in front or behind the plane (Miguel Casillas, 2010).

• q is a point.
• N is the normal to the plane.
• D is the distance from the origin to the plane.

If the distance is negative, the point is behind the plane.

If the distance is positive, the point is in front of the plane.

If the distance is 0, the point belongs to the plane.

Implementation of the algorithm

First we need to position the camera using gluPerspective() and gluLookAt(), then get the model view and projection matrices that hold the transformations of these. To get the clip coordinates we multiply them together. Now we apply the perspective divison (divide all components x, y and z by w) to get the frustum in clip coordinates.

It is easier to test points and boxes in clip space because the view frustum is transformed into a cube with coordinates (-1, -1, -1) (1, 1, 1). We compare the vertices to see if they are behind or in front of this cube. Only objects that are inside the cube are drawn.

- View frustum after clipping transformations are applied.

AABB intersection test

We need to check all 8 vertices of the box against the 6 planes of view frustum.

There is a easy way of doing this test. Because we are in clip space, the planes are:

We can define these planes using an outcode. The outcode is a number that will represent the plane, as we have six planes, we need a 6 bits number for each plane (Dunn & Parberry, 2002), for example:

We are going to set the bits to 0 if the vertex is in front of that plane, 1 if it is behind.

For each vertex, we will get an outcode, for example the outcode 100001 for a given vertex means that it is behind the near and right planes, and in front of the rest.

To create this outcode we use the bitwise operator OR. We start with all the bits set to 0, if we find a plane in which the vertex is behind, we set that plane to 1 using OR, for example:

000000 OR 000010 = 000010, and so on with all the planes.

We are testing a box, so we will have 8 outcodes. We can use the bitwise operator AND to compare them and see if there is a plane in where all the vertices are behind it.

Example:

The bitwise AND between all the outcodes will result in 100000, meaning that all vertices of the box are behind that plane, therefore the box is outside the view frustum.

Using the AND operator is an easy way of comparing the bits and checking if there is any plane which is behind for all vertices.

We can see how using simple logical operators like OR and AND is very handy and a fast way of approaching this algorithm.

With these two possible outcode outputs (zero or non zero) we can determine if the box should be drawn or not.

Note: there is a third possible outcome which is not relevant in my simulation but can be useful in other cases, when the box is partially in and partially out of the view frustum. This condition will happen when one or more outcodes of the 8 vertices are zero and the rest are non zero.

In the function where we are drawing our objects we will check for collision between the view frustum and the AABBs using the algorithm explained. Only when the boxes are inside the frustum we will tell OpenGL to draw them.

The results can be seen in the demo with the feature in the top right corner, which displays the number of cars being drawn. Basically all the cars within the visual range of the camera are drawn, anything else outside of it will not be passed to the OpenGL draw functions.

- Code snippet of the function that calculates the outcode (click to enlarge):

- Code snippet of the function that calculates if a Box is inside the frustum (click to enlarge):