Re: [Algorithms] Pack My Spheres Up Your Frustum

[Dave E. <eb...@ma...>]

From: "Pierre Terdiman" <p.t...@wa...>


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

Perhaps you can clarify?  In the sphere-sphere code, I count 7
floating-point operations and 1 floating-point compare.  In the aabb-aabb
code in worst case, I see 6 floating-point operations, 3 integer compares,
and 3 integer 'and' operations.  I assume your macro is just a typecast of
some type (no 'cost' assigned to it).  Seems like in worst case the
sphere-sphere code wins.  At any rate, on average the aabb-aabb comparison
is faster because of the quick outs.

I am certain you know what I am about to say, but I'll say it anyway.

For other geometric queries such as sphere-frustum intersection or
aabb-frustum intersection, things are not so fortunate.  That is the curse
of bounding volumes;  the trade-offs between using two different types of
bounding volumes change depending on the geometric query.

Also, the code at my web site is constructed to provide algorithmic
solutions.  Sometimes I pay attention to the need for optimizations at a
*high level*, but you will not find hard-coded assembly.  I develop on a PC,
but intend the code to be portable for folks who do not.  Use the code with
a grain of salt, but feel free to optimize it for a specific platform.  Also
avoid making timing comparisons with it and your own code as a way of
arguing whether or not one algorithm is better than another.  And finally,
never assume my code is correct or robust :)  Test it for your own
applications.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com