CSG
csg.jpg

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

Algorithm outline

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

Action tables

Union Enter B Exit B Miss B
Enter A ReturnAIfCloser, ReturnBIfCloser ReturnBIfCloser, AdvanceAAndLoop ReturnA
Exit A ReturnAIfCloser, AdvanceBAndLoop ReturnAIfFarther, ReturnBIfFarther ReturnA
Miss A ReturnB ReturnB ReturnMiss
Difference Enter B Exit B Miss B
Enter A ReturnAIfCloser, AdvanceBAndLoop AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser ReturnA
Exit A ReturnAIfCloser, ReturnBIfCloser, FlipB ReturnBIfCloser, FlipB, AdvanceAAndLoop ReturnA
Miss A ReturnMiss ReturnMiss ReturnMiss
Intersection Enter B Exit B Miss B
Enter A AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser ReturnAIfCloser, AdvanceBAndLoop ReturnMiss
Exit A ReturnBIfCloser, AdvanceAAndLoop ReturnAIfCloser, ReturnBIfCloser ReturnMiss
Miss A ReturnMiss ReturnMiss 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