RE: [Algorithms] Pack My Spheres Up Your Frustum

[Tom F. <to...@mu...>]

Of course, you realise the real sin in coding these days is to have lots of
hard-to-predict branches, don't you? By that token, spheres are waaaay
faster. Plus, the sphere test can be done in parallel much beter, and has
fewer scheduling conflicts, so the difference in operations may well be
completely absorbed by a decent processor. Both of these need to be
considered.

But in general - trust no-one and nothing but the FPS meter (and keep that
on the "suspicious" list as well). But be aware that fewer operations !=
faster, by any means.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Pierre Terdiman [mailto:p.t...@wa...]
> Sent: 13 October 2000 13:06
> To: gda...@li...
> Subject: Re: [Algorithms] Pack My Spheres Up Your Frustum
> 
> 
> > 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