Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!princeton!acm!markv
From: markv@acm.Princeton.EDU (Mark VandeWettering)
Newsgroups: comp.graphics
Subject: Re: A Ray Tracer Accelerator: ???
Message-ID: <4381@idunno.Princeton.EDU>
Date: 29 Nov 90 17:17:17 GMT
References: <2010@ucf-cs.UCF.EDU>
Sender: news@idunno.Princeton.EDU
Reply-To: markv@acm.Princeton.EDU (Mark VandeWettering)
Organization: Princeton University
Lines: 77

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