Posted: 20 Feb 2010 12:35
The most widely known algorithms for rendering constructive solid geometry (CSG) require finding all intersections of a line with a primitive and then computing the intersections by examining the intervals. This is clearly inefficient because you need to store and compute all the intersections for all the sub-objects of the CSG tree. Not only you don't really need to know all intersections to find the nearest one but the storage/deletion of many hits within a rendering loop is a real performance killer. Another issue is that you must rewrite all your primitive intersection routines to support CSG which increases the code bloat.
Therefore, CSG support within XRT is based on a different algorithm described in a short paper from Andrew Kensler: Ray Tracing CSG Objects Using Single Hit Intersections. This paper is no longer available on the web but you can find a local copy here.
As the author states in his introduction:
"The [algorithm] computes intersections with binary CSG objects using the [nearest] intersection. Though it may need to do several of these per sub-object, the usual number needed is quite low. The only limitation of this algorithm is that the sub-objects must be closed, non-self-intersecting and have consistently oriented normals."1
A ray is shot at each sub-object to find the nearest intersection, then the intersection with the sub-object is classified as one of entering, exiting or missing it. Based upon the combination of the two classifications, one of several actions is taken:
- returning a hit
- returning a miss
- changing the starting point of the ray for one of the objects and then shooting this ray, classifying the intersection. In this case, the state machine enters a new loop.
The paper finally describes the state machine and the 3 different state tables (one for each CSG operation Union, Intersection and Difference) needed to raytrace a CSG tree. This a very neat idea expressed clearly and concisely: the paper is 3 pages long, 2/3 of it made of diagrams, state tables and pseudo code ready to be translated into C++. A real programmer's heaven.
But it doesn't work.
The state table for Union is OK but the state tables for Intersection and Difference are not. Even with very simple cases, when you run the routine with pen and paper, it fails. The good news are that it can be fixed with a few minor changes:
- create two other actions
- change the result of one combination in the Difference and Intersection tables
- update the state machine
My changes are given below in bold.
List of actions
|ReturnMiss||Exit, reporting no intersection|
|ReturnAIfCloser||Return the intersection with A if it is closer|
|ReturnAIfFarther||Return the intersection with A if it is farther|
|ReturnA||Always return the intersection with A|
|ReturnBIfCloser||Return the intersection with B if it is closer|
|ReturnBIfFarther||Return the intersection with B if it is farther|
|ReturnB||Always return the intersection with B|
|FlipB||If returning an intersection with B, flip its normal|
|AdvanceAAndLoop||Continue with the next intersection with A|
|AdvanceBAndLoop||Continue with the next intersection with B|
|AdvanceAAndLoopIfCloser||Continue with the next intersection with A if the current intersection with A is closer|
|AdvanceBAndLoopIfCloser||Continue with the next intersection with B if the current intersection with B is closer|
|Union||Enter B||Exit B||Miss B|
|Enter A||ReturnAIfCloser, ReturnBIfCloser||ReturnBIfCloser, AdvanceAAndLoop||ReturnA|
|Exit A||ReturnAIfCloser, AdvanceBAndLoop||ReturnAIfFarther, ReturnBIfFarther||ReturnA|
|Difference||Enter B||Exit B||Miss B|
|Enter A||ReturnAIfCloser, AdvanceBAndLoop||AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser||ReturnA|
|Exit A||ReturnAIfCloser, ReturnBIfCloser, FlipB||ReturnBIfCloser, FlipB, AdvanceAAndLoop||ReturnA|
|Intersection||Enter B||Exit B||Miss B|
|Enter A||AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser||ReturnAIfCloser, AdvanceBAndLoop||ReturnMiss|
|Exit A||ReturnBIfCloser, AdvanceAAndLoop||ReturnAIfCloser, ReturnBIfCloser||ReturnMiss|
State machine pseudo-code
The algorithm is slightly modified to take into account the new actions. Please note that minA and minB must not be initialized to 0.
minA = minB = min // current nearest intersection ( tA, NA ) = IntersectWithA( O, D, minA ) ( tB, NB ) = IntersectWithB( O, D, minB ) stateA = ClassifyEnterExitOrMiss( tA, NA ) stateB = ClassifyEnterExitOrMiss( tB, NB ) loop action = table [stateA, stateB] if ReturnMiss ∈ action then return miss else if ReturnA ∈ action or ( ReturnAIfCloser ∈ action and tA <= tB ) or ( ReturnAIfFarther ∈ action and tA > tB ) then return tA, NA else if ReturnB ∈ action or ( ReturnBIfCloser ∈ action and tB <= tA ) or ( ReturnBIfFarther ∈ action and tB > tA ) then if FlipB ∈ action then NB = −NB end if return tB, NB else if AdvanceAAndLoop ∈ action or ( AdvanceAAndLoopIfCloser ∈ action and tA <= tB ) then minA = tA ( tA, NA ) = IntersectWithA( O, D, minA ) stateA = ClassifyEnterExitOrMiss( tA, NA ) else if AdvanceBAndLoop ∈ action or ( AdvanceBAndLoopIfCloser ∈ action and tB <= tA ) then minB = tB ( tB, NB ) = IntersectWithB( O, D, minB ) stateB = ClassifyEnterExitOrMiss( tB, NB ) end if end loop
You will find some examples of this feature in the gallery