[CST-2] AdvGraph: CSG

[Phebe Mann]

On Thu, 31 May 2001, M.Y.W.Y. Becker wrote:

> Can anyone remember how a binary tree representation of a CSG object can be
> used to compute intersection points of a ray with the entire object
> (1999/9/4)?
>

http://www.geocities.com/pm258_cam/AGraphHCI/9994.doc

99/9/4								Phebe Mann

CSG has 3 operations -
UNION : ray is in at least one of the objects
INTERSECTION : ray is in both of the object and
DIFFERENCE : ray is in one object but not the other

A CSG object can be represented as a binary tree by insisting that each
operation has exactly 2 operands. This does not restrict the range of
possible CSG object in any way

When a ray, the intersection points of that ray with every primitive
(leaf) are calculated. These lists of points are then passes up the tree
to fins the intersection points of the entire CSG object with the ray, and
hence the best intersection point..

The list of intersection points consists of an empty pairs of values. Each
pair represents the intersection points as the ray enters. The values are
that of the parameter t, representing distance along the ray



Given 2 lists of pairs from its 2 children, a node combines them into a
single list of pairs in the following ways

UNION : ray is in at least one of the objects
INTERSECTION : ray is in both of the object and
DIFFERENCE : ray is in one object but not the other



These processing can be achieved parsing the 2 lists in order of t value
and keeping track of inside/outside for the 2 objects


> It's not in the notes but it seems to be examinable...
>
> Moritz
>
>
>
>
> _______________________________________________
> CST-2 mailing list
> CST-2@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-2
>