RE: [Algorithms] Pack My Spheres Up Your Frustum

[Ratcliff, J. <jra...@ve...>]

I've been developing a really cool tree structure for representing dynamic
data.  It represents things in a hierarchy of balanced spheres.  This is
used for collision detection, ray tracing, range searching, and AI.

The main feature of the algorithm is that the tree can be updated in a
virtually CPU free fashion.  That way you can have thousands of objects in
motion and pay almost no CPU to update their locations in a continuously
valid tree.  Since the tree is always valid you can parse the hierarchy for
ray-tracing, visibility culling, and range searching.

I have a visualization tool that is fairly self-explanatory.  It's cool to
watch the data structure constantly adapt itself to the new spatial
organization each frame.  Spacebar pauses, single steps, enter key goes back
to full speed.

John



-----Original Message-----
From: Pierre Terdiman [mailto:p.t...@wa...]
Sent: Friday, October 13, 2000 3:30 PM
To: gda...@li...
Subject: Re: [Algorithms] Pack My Spheres Up Your Frustum


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

Right, the actual comparison was probably irrelevant, sorry. I just wanted
to point out two things:
- sphere-sphere test may not be the fastest (as I've heard and read too many
times)
- one can speed up the AABB-AABB test by writing it that way.

I added the code just because if I hadn't, someone would have asked for me
to prove my assertions :) Of course, in no way I intended to say your code
was "slow". I think it's just a good idea to use a "reference
implementation" such as Magic when drawing comparisons.

Pierre

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list