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.