On Sat, 04 Jul 1998 03:43:25 +0000, Daren Scot Wilson <dar### [at] pipelinecom>
wrote:

>
>What's the cutting-edge, state-of-the-art algorithm for fastest ray
>intersection tests?   Have any researcher come up with anything amazing?
>Is there the technology to beat POV-Ray's tests?  (It uses octress and
>also bounding shapes around each finite object, as I recall from its
>source code)
>

In some research on radiosity, and in the conjuring of some of my own
algorithms, I have a sketchy idea on this method that bounds all the objects
in a scene.  I started with a number of postulates i called "bounding
postulates" , the first of which goes something like this --> "If the entire
scene is bounded, then every object in the scene is boundable."    This led to
a method of bounding I call voxel bounding.  The POV developers call them
"bounding slabs"  and they only use them for shooting rays out of the
viewpoint.

  A voxel is a rectangular solid that has edges parallel to the coordinate
axes.  In my method, every object is boundable (since the entire scene is
bounded) and every object has a 'minimum bounder' which is a usual POV object
like a sphere or cylinder.  For every minimum bounder we can stick a voxel
around it.  THe question is--"Why would you even want to bound what is already
bounded?"  The answer is that voxels have a hell of alot of properties that we
can use in a rarytracer.  For instance---  A ray/voxel intersection test is
incredably fast (you make intervals and see if they overlap. voila! )  We can
"interleave" all the voxels in the scene, since they are all inside or outside
one another.  (If 2 or more overlap, you say, then notice that the region in
which they overlap is a voxel itself!)  

The most powerful method comes now.  You rewrite the intersection routines so
that the best 'T' is passed into them as an argument.  The "best T" being the
smallest positive T so far.   So that the intersection rountines just don't
proceed blindly with all their calcs, but instead always look to see if it can
beat the smallest 'T'   Voxels are so easy to store that we can attatch them
to the objects' structures of the objects that are bounded by them, so that an
object will contain information that says: "This is smallest the voxel around
me."  So that the first test in any intersection test is "Can we get an
intersection within this bound that is smaller than this current best 'T' ?"
Yes--proceed  No---goodbye!  For quadric and other algebraicly defined
surfaces there are all sorts of algebraic tricks to check to see if we can get
a root inside a given interval.  This can be decided during and also musch
earlier then calling a slower-than-s**t root solver  For a full theoretical
discussion, get a good book on Interval Arithmetic and its use in computation.


 To be honest with you,  voxels, as I have defined them, are in fact intervals
in space!   This leads to all sorts of neat stuff... consider some of this -->
Objects such as torii, spheres, and cylinders have an outer, bounding voxel,
as well as an inner, bounded voxel.  Take these ideas and stir!!!!  


Steve Horn :p ~

Post a reply to this message