Point-solid classification algorithm for CSG
 

function ClassifyPoint(P:point, n:CSGnode) returns InOnOut

    if IsLeaf(n) then

      case (n.type)

        Cube: r:=ClassifyPointCube(P,n)
        Cylinder: r:=ClassifyPointCylinder(P,n)
        Sphere: r:=ClassifyPointSphere(P,n)
        ...

      endcase

    else

      r:=Combine(n.operation,ClassifyPoint(P,n.rightChild),
      ClassifyPoint(P,n.leftChild))

    endif
    return r

endfunction

Combine(op, A, B)
 

AUB

in

on

out

in

in

in

in

on

in

on

on

out

in

on

out

A^B

in

on

out

in

in

on

out

on

on

on

out

out

out

out

out

A-B

in

on

out

in

out

on

in

on

out

on

on

out

out

out

out

 

The algorithm can be optimized pruning branches that we do not need to explore (for instance, if after an intersection the result kept in the left branch is "out", right branch can be discarded).
 

Line-solid classification algorithm for CSG

In this case, the operation result is more complicated, because a list of intervals InOnOut must be represented. If line r is parametrized as r= (P +lambda * v), list elements can be pairs [lambda,classification]. The algorithm is identical to point classification, replacing “point” with “line”.

The Combine function must combine both interval lists, using the same tables in the above algorithm (the classification of a line's interval equals the classification of any of its points, i.e. the midpoint). In the resulting list intervals must be compacted using the same classification. For example (we use notation l1 .. l4 for the intersection parameters lambda1 .. lambda4):

Union result : [l1,in] [l2,on] [l4,out]
(two "in" intervals are compacted)

Solid A : [l1,in] [l2,out]
Solid B : [l3,on] [l4,out]

Intersection result : [l1,out] [l3,on] [l2,out]
(two "out" intervals are compacted)

Substraction result : [l1,in] [l3,on] [l2,out]
(two "out" intervals are compacted)