On 22 Jul 1998 06:37:13 -0500, Nieminen Mika <war### [at] assaricctutfi> wrote:
>  We have now a counter which starts from 0.
>  The first ray hits the outer surface of the first sphere. Since the counter
>is 0. the coloration of this surface is calculated and we increase the counter.
>  A second ray is cast. It hits the outer surface of the second sphere. Since
>the counter is greater than 0, we just ignore this surface (ie. no coloration
>is calculated). We increase the counter (which is now 2, since we are inside
>2 objects).
>  A third ray is cast. Now it hits the inner surface of the first sphere, so
>we decrease the counter. Since it's not 0 after the decrementation, we ignore
>this surface too.
>  A fourth ray is cast. It hits the outer surface of the third sphere. Since
>the counter is not 0, we ignore this surface and increment the counter.
>  And so on and so on.
>  At last, we hit the inner surface of the last sphere and decrement the
>counter. Now the counter becomes 0, so we calculate the coloration of this
>surface.

Actually, I just reread this and realized that it's not the algorithm 
POV-Ray uses.  POV-Ray determines all of the intersections with the given
object, then picks the closest one.  In the process of doing so, it checks
each intersection to determine whether it is inside any of the other things
in the CSG.  For a union, however, it just returns the complete list of
intersections.  This means that finding all of the intersections in a union
is order n on the number of unioned objects, while a merge is order n^2.

Your algorithm would run into trouble in practice.  At each real surface, 
potentially two new rays are formed, plus as many shadow rays as you have
light sources.  Each of those rays would need its own copy of the counter.  
In addition, each ray would need to have a counter for every CSG object it
passed through.  That could get ugly very quickly.

It could be modified to work, though.  POV already keeps a stack of which 
objects each ray is inside, for IOR calculations.  It could just pop the top 
intersection off the stack, then check to see whether the container stack 
contains any of the other objects in this CSG.  If it does, then this surface 
should be ignored and we should go on to the next surface, after modifying 
the container stack to reflect the invisible transition.  If it doesn't, 
this is a "real" surface, so we should push it back on the intersection stack 
and return.  This would make merge on transparent objects almost as fast as 
union on opaque ones (union on transparent objects would probably be slower
than merge, because of the coloring step at each surface).

Post a reply to this message