[CST-2] Advanced Graphics - CSG

[Mike Pinna]

On Sun, 2 Jun 2002, Simon Crumpton wrote:
> 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. 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]

Constructive Solid Geometry allows us to perform three operations on
primitives and previously constructed objects: intersection, union and
subtraction.  We can therefore regard any object as a binary tree,
where each node stores which of the construction operations it
corresponds to and pointers to the two objects being combined (these
may have been constructed recursively in the same way.  Each leaf
corresponds to a primitive object.

To compute the intersection of a ray with a CSG object, we produce an
algorithm for finding out whether a ray is inside or outside an object:

For a node, merge the list of intersections with the two objects (which
we compute recursively).  From this it is trivial to work out when the
ray goes in and out of our combined object.  For a leaf, we are
effectively given this by the question.

The first intersection point of the ray with the final object will just
be the first element of the list returned here.

HTH,

Mike

-- 
Plese note my new email address:  mike@tropic.org.uk
All my addresses in cam.ac.uk will stop working on 15 July.