Adding Frustum Culling to My Engine

Even though not every object in a 3D scene appears on the screen, their data is still sent to the GPU for processing, only to be discarded later in the rendering pipeline. Those draw calls are pure waste: the CPU pays to issue them and the GPU pays to transform and clip geometry that was never going to be seen. However, we could just pick the objects that lie inside the viewing volume of the camera and send only the data associated with this subset of entities to the GPU. This is what Frustum Culling does, and it can dramatically improve the performance in many applications.

The name is somewhat of a misnomer as this technique can be applied to orthographic cameras as well.

Frustum culling operates by iterating over a list of objects (entities) in the active scene and checking if any part of them lies in the viewing volume. The method or metric that is used to determine if an object is considered inside the frustum may be different between implementations. A view frustum is defined by its planes, and an object can be represented by a bounding box since the original shape may be too complex for efficiently performing the tests. Let’s see first what a bounding box is and how to obtain one for a given mesh.

Bounding Box

A bounding box is a 3D volume that contains all the vertices of a mesh. Ideally, it should tightly contain the mesh so it could be accurately determined if the object intersects the frustum. An axis aligned bounding box (AABB), where each face is parallel to one of the xz, xy or yz planes, is good enough in many cases. Though, there could be cases such as a model of the Leaning Tower of Pisa that might require special handling. In my AABB implementation, I use two points that are the corners with the minimum and maximum coordinate values. These points are given in model space and are valid for the original scale.

In the following code, the definitions should either be marked inline or put in a separate (source) file to prevent multiple definition errors.

struct BoundingBox {
  glm::vec3 min{};
  glm::vec3 max{};
  BoundingBox();
  BoundingBox(glm::vec3, glm::vec3);
  BoundingBox GetWorldBounds(const glm::mat4&) const;
};

BoundingBox::BoundingBox()
  : min(glm::vec3(std::numeric_limits<float>::max())), max(glm::vec3(std::numeric_limits<float>::lowest())) {}

BoundingBox::BoundingBox(glm::vec3 min, glm::vec3 max) {
  if (glm::any(glm::lessThan(max, min)))
    throw std::invalid_argument("Max bounds must be greater than or equal to min bounds.");
  this->min = min;
  this->max = max;
}

For a given set of vertices that defines a mesh, an AABB can be calculated by iterating over each vertex and updating the min and max points through comparisons.

glm::min and glm::max operate on each component independently.

void AssetLoader::CalculateBounds(Mesh& mesh, const std::vector<Vertex>& vertices) {
  mesh.bounds.min = glm::vec3(std::numeric_limits<float>::max());
  mesh.bounds.max = glm::vec3(std::numeric_limits<float>::lowest());
  for (const auto& vertex : vertices) {
    mesh.bounds.min = glm::min(mesh.bounds.min, vertex.position);
    mesh.bounds.max = glm::max(mesh.bounds.max, vertex.position);
  }
}

Since we need to check for intersections with the camera frustum, we need to bring the local bounds to the world space. The following method accepts a world transform and calculates a new bounding box that contains the transformed points. Notice that we apply the transformation to each of the 8 corners of the box and take all into consideration. The reason is that the original extremes might get replaced by other corners after transformations like rotation or non-uniform scale.

BoundingBox BoundingBox::GetWorldBounds(const glm::mat4& transform) const {
  glm::vec3 corners[8] = {
    {min.x, min.y, min.z},
    {max.x, min.y, min.z},
    {min.x, max.y, min.z},
    {max.x, max.y, min.z},
    {min.x, min.y, max.z},
    {max.x, min.y, max.z},
    {min.x, max.y, max.z},
    {max.x, max.y, max.z}};
  BoundingBox bounds{};
  for (const auto& v : corners) {
    auto v4 = transform * glm::vec4(v, 1.0f);
    auto v3 = glm::vec3(v4);
    bounds.min = glm::min(bounds.min, v3);
    bounds.max = glm::max(bounds.max, v3);
  }
  return bounds;
}

Frustum

Recall that a frustum is defined by six planes: near, far, top, bottom, left and right. The Frustum type is simply a container for these planes.

struct Frustum {
  Plane top{};
  Plane bottom{};
  Plane right{};
  Plane left{};
  Plane far{};
  Plane near{};
  bool InFrustum(const BoundingBox&) const;
};

A plane can be defined in a few different ways. I chose to define it by a point and a normal direction such that the point is on the plane and any vector on the plane is perpendicular to the normal.

struct Plane {
  glm::vec3 point{};
  glm::vec3 normal{};
  bool OnPositiveSide(const BoundingBox&) const;
  float SignedDistance(const glm::vec3&) const;
};

For a clean and clear implementation, normal directions of a frustum’s planes must be consistent such that they all point inwards.

We can create a vector from a point on the plane to an arbitrary point in space, and calculate its dot product with the plane normal to obtain a number. If this number is positive, then we can conclude that the vector makes less than $90^\circ$ angle with the normal, and the point is on the positive side of the plane.

float Plane::SignedDistance(const glm::vec3& point) const {
  return glm::dot(normal, point - this->point);
}

For a box to be considered on the positive side of a plane, any portion of it must lie on the positive side. However, we don’t need to test every corner, we’re only interested in the one that is most likely to pass the test. This is the corner that is most aligned with the plane normal (i.e., that would result in the most positive dot product). If correctly calculated, the max coordinates of a bounding box must be greater than the min coordinates — max.x is greater than min.x and so on. To find the corner farthest in the normal’s direction, check the sign of each normal component and choose the box’s min or max value on that axis accordingly — always taking the value that lies farther along the normal. It doesn’t matter if it has the same sign as the normal component or not — if normal.x is positive and both bounds.min and bounds.max are in the negative x-axis, then bounds.max is the more positive (less negative) of the two in the normal direction. After determining which one of the eight points is the best candidate, we calculate its signed distance from the plane to see if it’s on the positive side.

bool Plane::OnPositiveSide(const BoundingBox& bounds) const {
  glm::vec3 positiveCorner;
  positiveCorner.x = (normal.x >= 0) ? bounds.max.x : bounds.min.x;
  positiveCorner.y = (normal.y >= 0) ? bounds.max.y : bounds.min.y;
  positiveCorner.z = (normal.z >= 0) ? bounds.max.z : bounds.min.z;
  return SignedDistance(positiveCorner) >= 0;
}

Being on the positive side of one plane is not enough for a point to be considered inside the frustum. For example, if a point has a large z coordinate, it may be on the positive side of the near plane, but it might end up in the negative side of the far plane, whose normal is towards the origin. It’s clear that a point must be on the positive side of each plane to be in the camera’s view volume. Hence, the InFrustum method will return false if any one of those 6 checks fails.

bool Frustum::InFrustum(const BoundingBox& bounds) const {
  const Plane planes[6] = {near, far, right, left, top, bottom};
  for (const auto& plane : planes)
    if (!plane.OnPositiveSide(bounds))
      return false;
  return true;
}

This test is conservative: a box can be on the positive side of all six planes and still fall outside the frustum near a corner. That only costs us a draw call for something off screen, which is a fine trade for six dot products.

The implementation is then straightforward: get a reference to the active Camera object and call InFrustum for each entity that has a MeshFilter (container for Mesh) component, then initiate draw calls for the ones that pass the test. There are obviously ways to optimize this process. Instead of individual draw calls, we could group entities that share the same mesh and material settings, and do instanced rendering. I won’t get into that in this post, but I would like to talk about another technique that could significantly reduce the number of tests performed.

Spatial Partitioning

If a scene contains n entities, we have to perform n tests to obtain a set of visible entities. This has $O(n)$ time complexity. We cannot beat that in the worst case, since the test has to return every visible entity, and a camera pointed at the bulk of the scene sees most of them. What we can do is make the cost track the number of entities actually in view rather than the size of the scene, by rejecting whole groups of them with a single test. To achieve that, we have to employ a divide-and-conquer technique. Currently, we have n (invisible) bounding boxes in the scene, each containing an entire object. What if these boxes too were contained inside bigger boxes, and those inside even bigger ones, stacked like Matryoshka dolls, up to a single huge box that contains the entire scene?

An octree is a data structure where each internal node has up to eight children — leaf nodes, which is where the entities actually sit, have none. It can be used to partition 3D space such that each axis is split in half at the node’s own center to create eight subdivisions (octants). Each node can be further (recursively) subdivided as needed. In practice, we work with a bounded volume that is large enough to contain the entire scene or the part we’re interested in.

Initially, every object is inside the root node that is a cubic volume centered around the origin. A node stores a list of items (entities) whose bounding boxes either intersect or are fully contained by the node’s volume, which is a bigger box. If the number of items in a node exceeds a certain limit, the node subdivides and distributes its items to its children. This can be implemented in various ways; for example, if no child fully contains the item it remains associated with the parent. If items are being removed, the opposite happens, that is, the child nodes collapse (merge) by giving their items back to their parent node. But, how does this help with frustum culling?

The upper limit for subdivision should be set proportional to the node volume — child nodes should have lower limits, e.g., 1/8 of those of the parent node.

Without partitioning, we have to check every bounding box for intersection with the frustum to determine the objects to be culled. However, after just one subdivision, we put those objects into 8 separate boxes, plus the root itself for anything that straddles a boundary and so is not fully contained by any child. If any one of these big boxes does not intersect the frustum, then this means that the objects inside it are out of the view, and there is no need to individually test them. With deeper hierarchies, and optimal limits, the search space can be reduced even further.

The following is a demonstration of frustum culling applied to a scene represented by an octree.