[CST-2] Advanced Graphics - CSG

[George van den Driessche]

> Can somebody explain an answer to (c) in 2000 P9 Q4?
>
> "Describe how an object built using CSG can be represented using a binary
> tree.

If each primitive in the object represents the set of points within it, then
the object is just an expression combining those sets using conjunction,
disjunction, subtraction. The binary tree corresponds to that expression.

> Given the intersection points of a ray with each primitive in the
> tree, show how to calculate the first intersection point of the ray with
the
> entire CSG object." [6]

A node in the binary tree has two children. If the sorted (by distance along
ray) list of intersections for each child is known, then the list for the
parent can be calculated by merging the lists to create a new sorted list,
and then passing a FSA over the new list, which removes items as necessary
according to the operator of the node. The FSA works by keeping track of
whether the ray is currently inside each child object, so for example if
you're calculating (A and B) and the ray is inside both A and B, and
encounters an "exit B" item, you would just delete it, but if it next met an
"exit A" item, you would keep it.

Of course, the FSA could be engineered to have two input streams and select
items based on lower t, thus merging the two lists as it goes along.

Thus each node including that of the whole object can be calculated in terms
of its descendents.