CSG Tree Flattening & Pruning
Based on whether the evaluation of two input primitives returns that the region we're operating on is fully inside the primitive (-), fully outside (+), or intersecting with the primitive surface (o), we can predict whether the output of a union (OR), or intersection (AND) operation will be fully inside, outside or potentially intersecting as well.
A CSG subtraction A - B is equal to X AND NOT Y, where the sign of the right operand is inverted.
- = cell fully inside o = cell contains surface + = cell fully outside
We can flatten any CSG tree into a list of operations. For example, this sequential union of four primitives:
A B \ / OR C \ / OR D \ / OR
...can be written as a sequence of operations:
%1 = A %2 = OR %1 B %3 = OR %2 C %4 = OR %3 D
After line-by-line evaluation, %4 holds the result of the computation. The list can be further turned into pseudo-assembly with a single register E0 and two ops, SET and OR:
0: SET E0 + 1: OR E0 [A] 2: OR E0 [B] 3: OR E0 [C] 4: OR E0 [D] 5: END
From the truth table above it becomes apparent that if line 1 evaluates to -, none of the dependent operations need to run, as they will also all evaluate to -. We generalize to all other cases, and extend each binary operator with two branch arguments that serve as a jump table for the two definite result cases - and +, specifying how many operations may be skipped:
0: SET E0 + 1: OR E0 [A] 3 0 2: OR E0 [B] 2 0 3: OR E0 [C] 1 0 4: OR E0 [D] 0 0
Let's observe the translation of a more complex tree with composite operators:
A B C D \ / \ / AND SUB \ / OR E \ / OR
We observe that AND can be skipped if A is outside, that SUB can be skipped if C is outside and that all OR's can be skipped if AND or SUB are inside.
The corresponding flat list requires two registers and looks like this:
0: SET E0 + 1: OR E0 [A] 0 1 2: AND E0 [B] 5 0 3: SET E1 + 4: OR E1 [C] 0 2 5: SUB E1 [D] 2 0 6: OR E0 E1 1 0 7: OR E0 [E] 0 0