2 Constructive Solid Geometry (CSG)
Solid modelling systems manipulate descriptions of three-dimensional 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) . 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 non-terminal nodes are boolean operators and terminal nodes are primitives. Recursive divide-and-conquer 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 . 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
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 prim-M (X,S)
ELSE combine (M[X,left-subtree(S)], M[X,right-subtree(S)], root(S))
This is an early sequential example of a skeleton, based on divide-and-conquer, with two customising functions prim-M and combine; prim-M 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) . GEL is a library of skeletons for programming CSG applications, implemented as higher-order 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 () 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