CSG Tree Pruning

csgtree.rst

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.

A	B	OR	AND
-	-	-	-
o	-	-	o
+	-	-	+
-	o	-	o
o	o	o	o
+	o	o	+
-	+	-	+
o	+	o	+
+	+	+	+

- = 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