
2 Constructive Solid Geometry (CSG)
Solid modelling systems manipulate descriptions of threedimensional objects. The distinguishing feature of solid models is completeness: a description of a solid contains sufficient information to compute any geometric property of that solid.
A representation for solids which has received much attention is Constructive Solid Geometry (CSG) [4]. In CSG, solids are represented by a set of primitive solids combined using regularised boolean operations such as union, intersection and difference. This leads to a binary tree whose nonterminal nodes are boolean operators and terminal nodes are primitives. Recursive divideandconquer algorithms compute results for primitives, then combine the results using boolean operators when returning up the tree.
Tilove described a class of geometric problems, including point membership classification (PMC) and solid interference, which can be viewed as examples of a generic set membership classification (SMC) paradigm [4]. For example, PMC determines whether a point lies inside, outside or on a the boundary of solid. Tilove proposed a generic set membership classification function M[X,S] to classify a candidate set X with respect
1
to a reference set S; this specifies which segments of X are inside, outside, and on the boundary of the (constructively defined) set S.
M[X,S] IF (S is a primitive) THEN primM (X,S)
ELSE combine (M[X,leftsubtree(S)], M[X,rightsubtree(S)], root(S))
This is an early sequential example of a skeleton, based on divideandconquer, with two customising functions primM and combine; primM classifies the point with respect to the primitive and combine merges two classifications by means of a boolean operator at an interior node of the tree.
Davy and Dew generalised Tilove's SMC function to provide a generic parallel CSG traversal operation as part of a Geometric Evaluation Library (GEL) [5]. GEL is a library of skeletons for programming CSG applications, implemented as higherorder functions in the functional language Hope+. It enables concise and rapid development of a range of CSG and other geometric applications, illustrating the speed and simplicity of the skeleton approach. Though GEL was only implemented sequentially, an efficient implementation of a parallel PMC operation ([6]) paves the way for a more general parallel CSG skeleton.
3 A CSG Skeleton
The CSG skeleton uses three customising functions: solve carries out an operation
on a primitive, intersect and union define how results are combined under the boolean
operations for (intersection) and [ (union). The user of the skeleton must also specify
the candidate object (such as point or line to be classified), the reference CSG tree,
and the identities I and I[ of the result type under and [. For instance, for PMC,
the candidate point may be classified as IN, OUT or ON with respect to the reference
solid; I and I[ are IN and OUT respectively.
Thus, the prototype skeleton can be viewed as a higher order function invoked as