Browse Prior Art Database

Structuring Shapes by Constructive Solid Geometry-Tree Modification

IP.com Disclosure Number: IPCOM000113263D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 46K

Publishing Venue

IBM

Related People

Okano, A: AUTHOR [+3]

Abstract

Disclosed is a method of modifying a CSG-tree (Constructive Solid Geometry tree) into another form of structured tree by equivalent transformation. Sub-trees in the resulting structured tree represent sub-regions in the 3D shape represented by the original CSG-tree. The structured sub-regions are very useful in applications such as classification of shapes, retrieval of sub-regions, and abstraction of complicated 3D shapes.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 75% of the total text.

Structuring Shapes by Constructive Solid Geometry-Tree Modification

      Disclosed is a method of modifying a CSG-tree (Constructive
Solid Geometry tree) into another form of structured tree by
equivalent transformation.  Sub-trees in the resulting structured
tree represent sub-regions in the 3D shape represented by the
original CSG-tree.  The structured sub-regions are very useful in
applications such as classification of shapes, retrieval of
sub-regions, and abstraction of complicated 3D shapes.

      The modification is performed by using the associative law of
Boolean operations.  The law is applied to the following pairs of
elements: two successive '+' nodes; two successive '-' nodes; a '+'
node followed by a '-' node; and a '-' node followed by a '+' node.

      The first two pairs can be simply combined and converted into
sub-tree elements, as shown in Figs. 1 and 2.  In this case, even if
the shapes of "A" and/or "B" are changed, the resulting shapes are
identical to the ones defined by the original CSG-tree.

      The third pair can be converted into an equivalent sub-tree, as
shown in Fig. 3.  When the intersection between "A" and "C" is empty,
it can be further converted into a simpler form, as shown in the same
figure.  This, however, is not an equivalent conversion, because the
resultant shape may not be identical to the original one after the
shapes of "A" and/or "C" have been modified.

      The last pair is converted first into...