Affordable Access

Publisher Website

Computing CSG-tree boundaries as algebraic expressions

Authors
Journal
Computer-Aided Design
0010-4485
Publisher
Elsevier
Publication Date
Volume
26
Issue
6
Identifiers
DOI: 10.1016/0010-4485(94)90064-7
Keywords
  • Solid-Geometry Computation
  • Computer Graphics
  • Bounding-Box Computation
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract Constructive solid geometry (CSG) defines objects as Boolean combinations of primitive solids, and usually stores them in binary trees. A bounding entity is an upper estimate of the extent of a CSG object. One of the problems in CSG is the search for the smallest bounding box of an object with the bounding boxes of the leaves as input. A method is presented that finds the smallest bounding box of the root; only prismatic boxes are considered. The method, called the canonical-form method, introduces an algebra of boxes which is shown to be a lattice. The lattice properties are then used to prove that the algorithm that computes the bounding boxes achieves a better approximation than the others. Some hints on implementation are then presented, and the efficiency of the method is compared with the S-bound method.

There are no comments yet on this publication. Be the first to share your thoughts.