page 2  (10 pages) 1 3

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) [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 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 [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 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) [5]. 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 ([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