Access Restriction

Author Tilove, Robert B.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Computational geometry ♦ Constructive geometry ♦ Geometric modeling ♦ Interference detection
Abstract Constructive solid geometry (CSG) is the primary scheme used for representing solid objects in many contemporary solid modeling systems. A CSG representation is a binary tree whose nonterminal nodes represent Boolean operations and whose terminal nodes represent primitive solids. This paper deals with algorithms that operate directly on CSG representations to solve two computationally difficult geometric problems—null-object detection (NOD) and same-object detection (SOD). The paper also shows that CSG trees representing null objects may be reduced to null trees through the use of a new concept called primitive redundancy, and that, on average, tree reduction can be done efficiently by a new technique called spatial localization. Primitive redundancy and spatial localization enable a single complex instance of NOD to be converted into a number of simpler subproblems and lead to more efficient algorithms than those previously known.
Description Affiliation: General Motors Research Labs, Warren, MI (Tilove, Robert B.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 27
Issue Number 7
Page Count 11
Starting Page 684
Ending Page 694

Open content in new tab

   Open content in new tab
Source: ACM Digital Library