2
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The point of frustum culling is to avoid transforming all geometry. My proposed solution only transforms 2 points per object. On CPU. Regardless of how one would call it, do you think my method would work? \$\endgroup\$ – NPS Apr 20 '14 at 18:30
  • \$\begingroup\$ Probably not, because the sphere is not uniformly warped by the perspective divide. Where you choose those two points will produce very different results assuming you are not using orthographic projection. You'd probably have to transform your radius as well to compensate for the change in shape. However, if you were doing this without perspective it could very well work but frustum culling generally implies perspective. \$\endgroup\$ – Andon M. Coleman Apr 21 '14 at 18:35
  • \$\begingroup\$ I know the sphere doesn't stay a sphere after projection transformation but it should still be a good enouh approximation. But the last paragraph from Bahbar's answer is a deal breaker. :P \$\endgroup\$ – NPS Apr 21 '14 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.