In this post I am going to show an easy and quite efficient way to perform the well-known view frustum culling for axis-aligned bounding boxes (AABB from now on).

## Object local coordinate system

Considering that in our scene we could have objects/nodes with an arbitrary transformation (translation, rotation, scale), we need to work in each object’s local coordinate system so that we can have available its AABB.

Each object has an specific modelview-projection matrix; recall that we can extract its frustum planes in local space from this matrix as explained in Extracting frustum planes from modelview-projection matrix.

## The naive approach

A typical way to perform view frustum culling, given a certain AABB, is basically checking whether or not it is completely behind any of the frustum planes. A naive approach to do this would be verifying that all the (eight) vertices of the AABB lie behind the plane. For a reminder on point-plane classification visit this link.

Yet this operation can be done much more efficiently by comparing a single vertex…

## A more efficient approach

Given a certain plane and an AABB, let us call **p-vertex** (or positive vertex) that vertex in the AABB such that it is located farthest in the direction of the plane normal. We can classify the whole AABB with respect to that plane (outside if it lies completely in the negative half-side of the plane, or inside otherwise) by only looking at the **p-vertex** position. The following images show two different cases:

In the left image, the **p-vertex** lies behind the plane; in such case we can confirm that the whole AABB is behind tha plane, and thus, outside the viewing frustum. In the right image, the **p-vertex** is in the positive half-side of the plane, so the AABB cannot be discarded yet, and therefore we must keep testing the following frustum planes.

## P-Vertex selection

The selection of the **p-vertex** can be done very quickly if we have the minimum and maximum vertices of the AABB.

Our plane is described by the equation (ax + by + cz + d = 0), where we know (a,b,c,d). (a,b,c) is the plane normal and (d) is the distance from the origin (Possibly all these values being unnormalized). We can know the coordinates of the **p-vertex** with the following algorithm:

- If
**sign(a) > 0**, we take**xmax**; otherwise we take**xmin**. - If
**sign(b) > 0**, we take**ymax**; otherwise we take**ymin**. - If
**sign(c) > 0**, we take**zmax**; otherwise we take**zmin**.

Better yet, storing **min-vertex** and **max-vertex** in an array of size two and using a little bit of boolean arithmetic and casts to integer, we can take the coordinates of the **p-vertex** without the need of conditional statements (as seen in the implementation below).

## Implementation

Here I attach a snippet with code that implements the test:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | /** * Tells whether or not b is intersecting f. * @param f Viewing frustum. * @param b An axis aligned bounding box. * @return True if b intersects f, false otherwise. */ bool intersectFrustumAABB( const Frustum &f, const box3 &b) { // Indexed for the 'index trick' later vec3 box[] = {b.min, b.max}; // We have 6 planes defining the frustum static const int NUM_PLANES = 6; const plane3 *planes[NUM_PLANES] = { &f.n, &f.l, &f.r, &f.b, &f.t, &f.f }; // We only need to do 6 point-plane tests for (int i = 0; i < NUM_PLANES; ++i) { // This is the current plane const plane3 &p = *planes[i]; // p-vertex selection (with the index trick) // According to the plane normal we can know the // indices of the positive vertex const int px = static_cast<int>(p.a > 0.0f); const int py = static_cast<int>(p.b > 0.0f); const int pz = static_cast<int>(p.c > 0.0f); // Dot product // project p-vertex on plane normal // (How far is p-vertex from the origin) const float dp = (p.a*box[px].x) + (p.b*box[py].y) + (p.c*box[pz].z); // Doesn't intersect if it is behind the plane if (dp < -p.d) { return false; } } return true; } |

## Further optimizations

Other optimizations for this technique could be:

- Remembering the last discarding plane (temporal coherency)
- Plane Masking in hierarchical AABB
- Octant test
- …

More detailes on this can be seen in this page: Efficient View Frustum Culling.

Great article, the p vertex selection trick is clever.

Is there an error in this section? should it say (a,b,c) is the plane normal & If sign(c) > 0, we take zmax; otherwise we take zmin. ?????

////////

Our plane is described by the equation (ax + by + cz + d = 0), where we know (a,b,c,d). (a,b,d) is the plane normal and (d) is the distance from the origin (Possibly all these values being unnormalized). We can know the coordinates of the p-vertex with the following algorithm:

If sign(a) > 0, we take xmax; otherwise we take xmin.

If sign(b) > 0, we take ymax; otherwise we take ymin.

If sign(d) > 0, we take zmax; otherwise we take zmin.

/////////

In P-Vertex selection instead of “(a,b,d) is the plane normal” should it say: “(a,b,c) is the plane normal”?

Yes! Thank you for the correction, I already updated the post

Thanks for telling me. It’s already corrected

Does this suffer from the same limitation in the naive case described on this page: http://iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm, where an AABB is large enough to intersect multiple planes behind the frustum, resulting in a false positive?

Yes, we have exactly the same issue in this case. The method explained here is the same as the page you posted, just a bit optimized

Ah, is there a reciprocal optimization for the second part? I’m trying to implement some version of this for my engine, using a BVH, and I plan on using huge scale differences, so the case I mentioned is very likely for me.

After a day or so of thinking about it, since a frustum is a convex solid, the same optimization should work in reverse, correct? take the normal of the sides of the AABB and test the closest corner of the frustum against it?

If not, how about applying a perspective transformation so that the frustum becomes a AABB and the AABB becomes a frustum, and then applying the optimized test to that set?