wilson@ucf-cs.UCF.EDU (tom wilson) (11/29/90)
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.
Tommarkv@acm.Princeton.EDU (Mark VandeWettering) (11/30/90)
In article <2010@ucf-cs.UCF.EDU> wilson@ucf-cs.UCF.EDU (tom wilson) writes:
[ Synopsis: Tom suggests putting simple objects _inside_ complex ones.
The idea is if the ray intersects the simple object, then it MUST
intersect the simple one. This is only good for shadow testing
obviously, since we would need the REAL intersection for view rays.]
My guess is that while this would work, it is not necessarily a good thing to
do. Whether it is an actual speedup is basically a result of how often
you hit the internal bound versus how often you hit the object. As a crude
guess, we might imagine that the probability of hitting an object is
roughly proportional to its surface area. Further suppose that our complex
object has surface area = A, and for the sake of argument, spherical.
As a typical example of our inner bound, lets assume it is a sphere as well,
but with radius 10% smaller. (This seems pretty tight, I bet you could not do
much better for real objects).
If the object has unit radius, its surface area is 4*Pi. Our "unbounding
sphere" has surface area .81 * 4 * Pi. So, we can assume for this argument
that 81% of all rays that penetrate the object will penetrate the inner
volume.
Examining the costs:
81% of the time: we just intersect the cheap volume
19% of the time: we need to intersect BOTH volumes to determine
whether or not the object intersects the ray.
To generalize: let
C(cheap) be the cost of intersecting the cheap volume
C(object) be the cost of intersecting the real object
p be the probability of a ray which hits the object hitting the
inner cheap bounding volume.
Then, this scheme is a potential speedup if
p C(cheap) + (1-p) * (C(cheap) + C(object)) < C(object)
Is this a speedup? I dunno. One scene in Eric Haines' SPD data base includes
a large gear with 144 edges. The polygon intersection routine I use is linear
in the number of edges for a polygon. The majority of rays fall within
a disc which probably accounts for 90% or more of the total area of the
face. I am pretty sure that a scheme like you suggest would be useful
for this case.
But in general? I dunno. It really depends on the probability p. For
most objects, my guess is you might be able to get p = 0.5, which would make
the inequality something like
C(cheap) + 0.5 * C(object) < C(object)
or
C(cheap) < 0.5 * C(object)
which actually does seem to make it attractive.
In general, if the ratio of C(cheap)/C(object) = r, then we can solve for
the percentage of inner bounding volumes we need to make this scheme profitable.
p C(cheap) + (1-p) C(cheap) + (1-p) C(object) < C(object)
p C(cheap) + C(cheap) - p C(cheap) + C(object) - p C(object) < C(object)
C(cheap) + C(object) - p C(object) < C(object)
- p C(object) < -C (cheap)
p > r
What this means, if the ratio of speed from cheap to expensive is 1/10, then
we need to have probability greater than 10% to achieve a speedup.
Hmmm. This probably bears looking into. Any comments?
Mark
Mark VandeWettering
markv@acm.princeton.edujohng@neptune.uucp (John A. Gregor) (11/30/90)
In article <4381@idunno.Princeton.EDU> markv@acm.Princeton.EDU (Mark VandeWettering) writes: > >Hmmm. This probably bears looking into. Any comments? Well, to add another data point, the Wavefront software has both a "trace object" and a "shadow object" associated with each object being rendered. The trace object is the object used in reflections. Usually, these objects are left undefined, or point to a lower complexity, but similarly shaped, object. Since shadows and objects appearing as reflections are typically small and are there to provide visual cues and since Wavefront's running time is decidedly non-linear to number of polygons in the scene, this is a win. Also, you can achieve some neat tricks using this. You can have an object cast a shadow from a completely different object (e.g. a kitten casting a lion's shadow) or appearing as something else in mirrors. Using the same object with a different offset or scale can lead to some pretty neat effects occasionally also. -John -- John Gregor Applications for .signature file now being accepted.
wilson@ucf-cs.UCF.EDU (tom wilson) (11/30/90)
In article <4381@idunno.Princeton.EDU> markv@acm.Princeton.EDU (Mark VandeWettering) writes: [comments and analysis of value of inner bounding volume for shadows] >But in general? I dunno. In general? I doubt it. Consider the "standard" bounding volume for a general object. Do you make a bounding volume for a sphere? Na. How about a polygon? Well, you can but I doubt you would use a sphere because there's too much empty space. My point: it's not any more straightforward to choose an inner bounding volume than it is to choose the normal bounding volume. It may even be harder. I have considered a special case of generating an inner bounding volume for a convex object given that an outer bounding volume can be generated. It is quick but not necessarily an efficient volume. Given the outer volume, you can scale it so that it fits entirely within the object itself. This should work since the object is convex. I have been unable to think of an example where it wouldn't work (but that doesn't mean there isn't one, of course). What I'm hoping is that someone already has a scene with a complicated object that is really expensive to intersect a ray with since that is where the idea would prove to be most useful. Obviously, finding a good inner volume for this object may be a task. Tom