### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988 |

Editors | Richard J. Beach |

Publisher | Association for Computing Machinery, Inc |

Pages | 31-40 |

Number of pages | 10 |

ISBN (Electronic) | 0897912756, 9780897912754 |

DOIs | |

State | Published - Aug 1 1988 |

Event | 15th International Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988 - Atlanta, United States Duration: Aug 1 1988 → Aug 5 1988 |

### Publication series

Name | Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988 |
---|

### Other

Other | 15th International Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988 |
---|---|

Country | United States |

City | Atlanta |

Period | 8/1/88 → 8/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

*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