Path: utzoo!utgpu!watserv1!watmath!att!fang!alfred!tous!tarpit!ucf-cs!wilson
From: wilson@ucf-cs.UCF.EDU (tom wilson)
Newsgroups: comp.graphics
Subject: A Ray Tracer Accelerator: ???
Message-ID: <2010@ucf-cs.UCF.EDU>
Date: 28 Nov 90 19:00:11 GMT
Article-I.D.: ucf-cs.2010
Organization: Univ. of Central Florida, Orlando
Lines: 54

I posted an article a couple of weeks ago, but it seems that no one has seen
it. Therefore, I'm reposting it. My apologies if it really did appear.

------------------------------------------------------------------------

[some info on original post date and id]
Subject: A Ray Tracer Accelerator: ???
Message-ID: <1984@ucf-cs.UCF.EDU>
Date: 14 Nov 90 02:01:57 GMT

Out of nowhere, I have come up with a new (?) speedup (?) technique for
shadow testing in ray tracing. I don't have the kind of code necessary to
test it. It is kind of the inverse of a bounding volume:

Consider an expensive-to-intersect object (and for this example, a convex
solid. I'll generalize later). Now typically a bounding volume tells you
when a ray misses the object or parts of the objects (for hierarchies).
Eventually you have to intersect the object itself (I'm assuming the object
hasn't been broken down into polygons or whatever). Now what would be good is
a volume that, if intersected, would tell you the object is hit without
intersecting the object at all (of course it won't always work). Suppose for
this example we have a bloboid sphere or a megafaced convex polyhedron and
we put a sphere inside the object such that the entire sphere is enclosed in
the real object. Now if a ray hits the sphere, it definitely hits the object.
If the ray misses the sphere, it may still hit the object somewhere between
the bounding volume and the "inner tube" volume. Now this scheme is ideal for
shadow testing, since where the object is hit by the ray is usually irrelevent.
A "normal" ray needs the intersection point, so this scheme may not help much
(I don't know).

  :::::::::::::            An ugly (and pretty bad) 2D example:
 :       000   :
:      00   00  :          0's define the sphere inside the object :'s
:     0       *--:
:    0         0 -:--
 :   0         0  :  ----
  :   0       0  :       ----<   Shadow ray that hits at *
   ::: 00   00  :
      :::000   :
         ::::::

The object could really be any type of object (not just convex) provided a
sufficient inner tube volume can be constructed. It's really the same problem
as the bounding volume: the better the bounding volume (inner tube) the more
rays that are culled as misses (hits).

Is it feasible? I don't know. I don't have any complicated-objects code in my
tracer, so I can't test yet (without writing the code first obviously). Perhaps
someone who has the type of setup necessary can incorporate this and find out
(for that matter, has anyone already done it?). If it's a good scheme, maybe
I should change my thesis 8-) (I really just wanted to get into the next issue
of the RT News). Please give some feedback.

Tom