Re: [Algorithms] Pack My Spheres Up Your Frustum

[Pierre T. <p.t...@wa...>]

> My question would be why use spheres at all? It is more or less a myth
that they are faster.


100% agreed, BTW. Spheres are certainly not the fastest BV for basic
intersection tests. For example, here's a sphere-sphere intersection test,
from Magic:

bool MgcTestIntersection (const MgcSphere& rkS0, const MgcSphere& rkS1)
{
    MgcVector3 kDiff = rkS1.Center() - rkS0.Center();
    MgcReal fSqrLen = kDiff.SquaredLength();
    MgcReal fRSum = rkS0.Radius() + rkS1.Radius();
    MgcReal fRSumSqr = fRSum*fRSum;

    return fSqrLen <= fRSumSqr;
}

And here's my AABB-AABB intersection code:

  __forceinline bool    Intersect(const AABB& a)
      {
       float tx = mCenter.x - a.mCenter.x; float ex = a.mExtents.x +
mExtents.x; if((IR(tx)&0x7fffffff) > IR(ex)) return false;
       float ty = mCenter.y - a.mCenter.y; float ey = a.mExtents.y +
mExtents.y; if((IR(ty)&0x7fffffff) > IR(ey)) return false;
       float tz = mCenter.z - a.mCenter.z; float ez = a.mExtents.z +
mExtents.z; if((IR(tz)&0x7fffffff) > IR(ez)) return false;
       return true;
      }

When no intersection occurs, the AABB code may exit early, and in that case
it's a clear winner (that's why the way Gomez wrote his Gamasutra code is
*not* good IHMO). In the worst case, when two AABBs collide, there's 6
floating-point operations involved, which is approximatively the same as for
the two first lines of the Sphere-Sphere test.

The difference is probably not very important (I didn't use rdtsc on them to
check), but in many cases (if not all) the AABB code is just as fast, or
even faster than the Sphere one. At the very least, you can't really say the
Sphere code is "faster". The assertion "spheres are faster", is IMHO wrong.

So use the Carmack way, and never trust anything without checking it
yourself (that's the demomaker way of life, BTW. One day I'll tell you the
story of Niclas Thisell...)

Needless to say, my preference goes to AABBs, especially since good bounding
spheres are so much difficult to compute (Dave, you know what I mean!).

Pierre