Hi there,

These past two weeks I've been working on implementing a Frustum Culling algorithm for the engine. Here is a video of beta v0.0.6 of the engine with Frustum Culling.

In the previous beta version of the game engine, I had 20 soccer players on the screen. And I noticed that the game was a bit choppy. I recall the Frames-Per-Second (fps) being below 30. The engine was rendering all 20 players, the two goals, and soccer field at every frame without analyzing if the camera was able to see these models or not. You can agree that this is a problem.

The logic behind a Frustum Culling algorithm is essentially this:

"If the camera does not see the 3D model, then the engine should not render it".

Implementing this logic, allows you to have 100 models in a game, but only 10 or so many models being rendered at any time. Thus, improving the game experience.

For example, the minimum acceptable fps in a game is 30 fps. With Frustum Culling, the engine was able to render the entities at 60 fps and the lowest it got was 49 fps.

If you are entirely new to Frustum Culling, keep reading. I'm going to give you a brief tutorial on how Frustum Culling works.

What is a Frustum

A game engine requires a camera. During initialization of a game, the engine computes a Frustum. A frustum is a chopped pyramid. And 3D models within the frustum are visible by the camera and by YOU.

Notice how the frustum is composed of six planes.

What is Frustum Culling

A Frustum Culling Algorithm tests which 3D models lie within the frustum. If the 3D model lies outside the frustum, then it is ignored by the rendering engine. If the 3D model lies within the frustum, then it is rendered.

Frustum Culling Test

Testing if a 3D model lies within a frustum is quite simple. First, the 3D model is wrapped within a box, in this case, with an AABB (Axis-Aligned Boundary Box).

Then, the eight vertices of the AABB are tested against a plane. In a Frustum Culling algorithm, the AABB's vertices are tested against all six frustum's planes.

If all vertices lie on the negative side of the plane, then the model is considered being outside the frustum. Otherwise, it lies within the frustum.

And that is it. You repeat the process for all game entities in your game.

Improving the Frustum Culling Algorithm

Frustum Culling improves the efficiency of a game engine, but it is not enough. If your game only has ten 3D models, the engine can quickly do a Frustum Culling on all these entities. However, if your game has 200 or 1000 objects, then Frustum Culling by itself may not improve the efficiency of the engine.

What you need is an algorithm that can analyze the spatial area seen by the camera. For example, if the camera does not see the upper-left quadrant, then the engine should not perform Frustum Culling on the entities that lie on this quadrant. There are many algorithms that you can use. In the engine, I implemented a Boundary Volume Hierarchy (BVH) tree.

The image below shows the idea. I recursively wrapped the game entities in an AABB, until there is only one model per AABB. Then, starting from the root node, the engine test if the camera sees the AABB node or not. If the camera does not see the AABB node, then all the children node, containing the 3D models, are not rendered.

If the camera does see the AABB node, then it keeps performing Frustum Culling on the next AABB child node, until it reaches the leaf node.

In the example shown above, the algorithm rejects the red AABB box and does not need to test if the red and gray car is seen by the camera.

The camera does see the blue AABB box. Thus it tests the children nodes of the blue AABB box. It does this on and on until it reaches the leaf nodes. In this case, it sees the blue and orange car, but not the yellow car.

And that is Frustum Culling. I hope you learned something.

Thanks for reading.