Constructive Solid Geometry — some algorithmic details

 

A ray’s interaction with an object, A, can be stored as an ordered pair:
( inA : Boolean, tAs : float list )
where inA is True if the eye is inside object A and False otherwise. tAs is a list of t-values for which the ray intersects the surface of the object, sorted in increasing order. Of course, all t values are non-negative.

 

Here is an ML function for finding the Constructive Solid Geometry intersection of two objects.

 

fun inter( (inA, tA::tAs), (inB, tB::tBs) )

    =   if( tA < tB ) then

           if( inB ) then

              tA :: inter( (not inA, tAs), (inB, tB::tBs) )

           else

              inter( (not inA, tAs), (inB, tB::tBs) )

       else

           if( inA ) then

              tB :: inter( (inA, tA::tAs), (not inB, tBs) )

           else

              inter( (inA, tA::tAs), (not inB, tBs) )

|   inter( (inA, []), (inB, tB::tBs) )

    =      if( inA ) then

              tB :: tBs

           else

              []

|   inter( (inA, tA::tAs), (inB, []) )

    =      if( inB ) then

              tA :: tAs

           else

              []

|   inter( (inA, []), (inB, []) )

    =          [] ;

 

fun intersection( (inA, tAs), (inB, tBs) )

    =   ( inA andalso inB, inter( (inA, tAs), (inB, tBs) ) ;

 

 

You could try writing an equivalent function to find the difference of two objects, A \ B.

 


You can consider CSG to be driven by a simple state machine, where there are four states:

·        In both A and B.

·        In just A.

·        In just B.

·        In neither A nor B.

 

As one progresses along the ray, each intersection point changes the state. Each of the four possible operations (union, intersection, A \ B and B \ A) requires you to keep the intersection points which transfer you into or out of just one of the four states. Thus A \ B is defined by the transitions into and out of the “In just A” state, while intersection is defined by the transitions into and out of the “In both A and B” state.