View frustum culling (AABB vs Frustum)

View frustum cullong

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:

P-Vertex selection

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.

AABB min and max vertices

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.

  1. 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.
    /////////

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

  3. 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 :-)

  4. 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.

  5. 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?

  6. 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?

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>