Frustum culling based on MVP matrix?

Question

Tutorials on the internet usually say to extract plane data from MVP (model view projection) matrix (or VP?) and then test the bouding volume against each of the frustum planes. I've thought of a different approach:

1. calculate model's bounding sphere (center + radius)
2. define point A = center, B = center + float3(radius, 0, 0) - some point on the sphere
3. multiply A and B by MVP matrix to get point coords in clip(?) space
4. calculate radius in clip space (distance from A to B)
5. check if sphere is in the frustum, sth like: A.x - radius < 1 && A.x + radius > -1

Would this work (it would be only an approximation but should be good enough)? In (5) what values should I test against? -1 and 1? Because I'm not sure if I'm not mixing up spaces.

Answer 1

No, it won't work.

The transformation of a sphere by a projection into NDC is not a sphere. You pick a single point on the sphere, and then assume you get the whole bounding volume back with just a single distance, but it is incorrect (i tried finding pictures of the resulting volume but failed. While you can see the deformation on how a sphere turns into an ellipsoid in xy plane, the transformation along the z-axis is the one that is most dramatic).

Let's walk through an example (using OpenGL projection, but the principle is the same in other NDC spaces), with near=1, far=infinity, -left=right=-bottom=top=1. The resulting projection matrix is:

[1  0  0  0]
[0  1  0  0]
[0  0 -1 -2]
[0  0 -1  0]

Take a sphere centered at [0, 0, -10], of radius 1... And let's transform 3 points on the sphere:

[0, 1, -10, 1],
[0, 0,  -9, 1] and 
[0, 0, -11, 1] 

the post-projection coords give resp:

[0, 1, 10 - 2, 10]
[0, 0,  9 - 2,  9]
[0, 0, 11 - 2, 11]

in NDC, this gives:

[0, 0.1, 0.8     ]
[0, 0,   0.777...]
[0, 0,   0.8181..]

so, the sphere points are respectively 0.1, 0.0222.., 0.01818... away from the center in NDC. This is a single example, but you can clearly see they're not on a sphere in NDC space, and the Z direction completely changes the proportions along Z.

Not only that, but actually transforming to the NDC is incorrect if you don't clip your volume to the clipping planes first.

Say for example you want to test the point [0, 0, 2] (behind the camera). The projection gives: [0, 0, -3, -4]. A naïve simple w divide gives [0, 0, 0.75]... and that's "inside" the NDC cube.

Answer 2

Clip-space does not have the range [-1,1] that you are describing. That is NDC space, which is achieved by dividing the clip-space coordinate by its W component. What is more, depending on the API, NDC may not be [-1,1] in all directions. This is the case in OpenGL, but in D3D the Z component ranges from [0,1] in NDC while X and Y range from [-1,1].

I mention this because unless you have an orthogonal projection (and even then, W is not guaranteed to be 1.0), W is going to vary by distance in clip-space in order to produce perspective and therefore the actual frustum shape. Now, this frustum shape only applies in other coordinate spaces. Once you get into NDC space, the viewing volume is a cube (or in the case of D3D, half of a cube) and all of the geometry has been warped for perspective. At this point all you need to do is test your object's bounding volume (sphere in your case) against this cube.

In short, frustum culling does not apply if you transform your coordinates as far as you seem to be proposing. The shape of the viewing volume is no longer a frustum. The general idea behind frustum culling is to avoid transforming the input objects that far and cull them in a more natural space such as world, where the shape of the viewing volume is actually a frustum.