AN EFFICIENT ALGORITHM FOR FINDING THE CSG REPRESENTATION OF A SIMPLEPOLYGON

Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an ob ject explicitly but represent its interior only implicitly, and constr uctive solid geometry representations, which model a complex object, s urface and interior together, as a boolean combination of simpler obje cts. Because neither representation is good for all applications, conv ersion between the two is often necessary. We consider the problem of converting boundary representations of polyhedral objects into constru ctive solid geometry (CSG) representations. The CSG representations fo r a polyhedron P are based on the half-spaces supporting the faces of P. For certain kinds of polyhedra this problem is equivalent to the co rresponding problem for simple polygons in the plane. We give a new pr oof that the interior of each simple polygon can be represented by a m onotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main cont ribution is an efficient and practical 0(n log n) algorithm for doing this boundary-to-CSG conversion for a simple polygon of n sides. We al so prove that such nice formulae do not always exist for general polyh edra in three dimensions.