Solving Computer Graphics Problems through Boolean Combinations of Polygons
Abstract
Several important computer graphics problems can be solved by formulating the problem as a boolean combination of sets of coplanar polygons. We describe an implementation of an efficient plane sweep algorithm, which solves these problems by triangulating the polygonal regions defined by boolean combinations of sets of polygons. Example applications include, but are not limited to, triangulating a concave polygon with holes, computing complex clipping operations, detecting modelling errors, transforming a tiling into a planar subdivision and even the hidden surface problem. We present new techniques to handle the difficulties encountered with real world input, which are typically omitted in presentations of geometric algorithms in the computational geometry literature. Finally, we describe how the above applications may be cast as boolean combinations and solved with our algorithm. (kr)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1989
- Accession Number
- ADA214788
Entities
People
- John M. Airey
Organizations
- University of North Carolina at Chapel Hill