An efficient algorithm for finding the CSG representation of a simple polygon

David Dobkin, Leonidas Guibas, John Hershberger, Jack Snoeyink

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

We consider the problem of converting boundary representations of polyhedral objects into constructive-solid-geometry (CSG) representations. The CSG representations for 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 corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practical O(n log n) algorithm for doing this boundary-to-CSG conversion for a simple polygon of n sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.

Original languageEnglish (US)
Title of host publicationProceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988
EditorsRichard J. Beach
PublisherAssociation for Computing Machinery, Inc
Pages31-40
Number of pages10
ISBN (Electronic)0897912756, 9780897912754
DOIs
StatePublished - Aug 1 1988
Event15th International Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988 - Atlanta, United States
Duration: Aug 1 1988Aug 5 1988

Publication series

NameProceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988

Other

Other15th International Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988
CountryUnited States
CityAtlanta
Period8/1/888/5/88

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design

Keywords

  • Boundary-to-CSG conversion algorithms
  • Constructive solid geometry
  • Simple polygons
  • Solid modeling

Fingerprint Dive into the research topics of 'An efficient algorithm for finding the CSG representation of a simple polygon'. Together they form a unique fingerprint.

  • Cite this

    Dobkin, D., Guibas, L., Hershberger, J., & Snoeyink, J. (1988). An efficient algorithm for finding the CSG representation of a simple polygon. In R. J. Beach (Ed.), Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988 (pp. 31-40). (Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988). Association for Computing Machinery, Inc. https://doi.org/10.1145/54852.378472