Accession Number:

ADA214788

Title:

Solving Computer Graphics Problems through Boolean Combinations of Polygons

Descriptive Note:

Technical rept.

Corporate Author:

NORTH CAROLINA UNIV AT CHAPEL HILL DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1989-08-01

Pagination or Media Count:

14.0

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

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE