• Advertisement
Sign in to follow this  

sphere-cone test with no sqrt() (for frustum culling)

This topic is 2997 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I've found a method for checking if a sphere is partially or totally included inside a cone without using a square root, as the square root has a big overhead on some FPUs, especially on mobile platforms (e.g., on the VFP11 and NEON units of the armv6 and armv7 processors).

Original algorithm

I started with Charles Bloom's algorithm as presented in the second part of this page :
V = sphere.center - cone.apex_location
a = dotProduct(V, cone.direction_normal)
b = a * cone.tan
c = sqrt( dotProduct(V,V) - a*a )
d = c - b
e = d * cone.cos

now  if ( e >= sphere.radius ) , cull the sphere (return 0)
else if ( e <=-sphere.radius ) , totally include the sphere (return 1)
else the sphere is partially included (return -1)

What's going on in this cone-sphere test? Basically, I'm trying to find
'e' which is the shortest distance from the center of the sphere to the
surface of the cone. You can draw some pictures and see what's going on.
'a' is how far along the ray of the cone the sphere's center is. 'b' is
the radius of the cone at 'a'. 'c' is the distance from the center of the
sphere to the axis of the cone, and 'd' is the distance from the center
of the sphere to the surface of the cone, along a line perpendicular to
the axis of the cone (which is not the closest distance).

Simplified form

The algorithm can be simplified and turned into the following:
V = sphere.center - cone.apex_location
a = dotProduct(V, cone.direction_normal)
x = cone.cos * sqrt( dotProduct(V,V) - a*a ) - a * cone.sin
if abs(x)>sphere.radius:
    if x<0, totally include the sphere (return 1)
    else,   cull the sphere (return 0)
else the sphere is partially included (return -1)

Sqrt() must die!

Using squared inequalities, this in turn leads to the following sqrt-free formulation:
V = sphere.center - cone.apex_location
a = dotProduct(V, cone.direction_normal)
p = a * cone_sin
q = cone_cos * cone_cos * dotProduct(V, V) - a * a
r = q - sphere_radius * sphere_radius
if (p<sphere_radius) || (q>0):
     if (r < 2 * sphere_radius * p), the sphere is partially included (return -1)
     else if q<0, the sphere is totally included (return 1)
     else cull the sphere (return 0)
else:
    if ( -r < 2 * sphere_radius * p), the sphere is partially included (return -1)
    else if q<0, the sphere is totally included (return 1)
    else cull the sphere (return 0)

Source code

Here is the source of the two methods: Charles Bloom's and mine:
// V=(sphere.center - cone.apex_location)
// dotProduct_V_V = dotProduct(V, V)
// a = dotProduct(V, cone.direction_normal)
int cbloom_test(float dotProduct_V_V, float a, float sphere_radius, float cone_sin, float cone_cos) {
    const float x(cone_cos*sqrt(dotProduct_V_V - a*a) - a*cone_sin);
    return (fabsf(x)>=sphere_radius)?(x<0):-1;
}

int jcayzac_test(float dotProduct_V_V, float a, float sphere_radius, float cone_sin, float cone_cos) {
    const float p(a*cone_sin);
    const float q(cone_cos*cone_cos*dotProduct_V_V-a*a);
    const bool tmp(q<0);
    float lhs[2];
    lhs[0]=(sphere_radius*sphere_radius - q);
    lhs[1]=-lhs[0];
    return (lhs[(p<sphere_radius) || !tmp]<2.f*sphere_radius*p)?-1:tmp;
}





Tested on an iPod Touch 2G (armv6 + vfp11), my implementation was 20% faster on average. Also note that since it doesn't use any division nor square root, it is well suited for being used with fixed points.

Share this post


Link to post
Share on other sites
Advertisement
So you are basically squaring everything in the equation where the sqrt() is used. It's a technique I also use in some calculations, particularly for testing.

Share this post


Link to post
Share on other sites
Quote:
Original post by Tachikoma
So you are basically squaring everything in the equation where the sqrt() is used. It's a technique I also use in some calculations, particularly for testing.


Yes, though it wasn't as trivial as it sounds (especially the case when a*cone_sin<sphere_radius).

Share this post


Link to post
Share on other sites
Why are you using a cone instead of the actual frustum planes?

Is a cone faster than the combined 6 plane checks? I assume it would be less accurate...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement