Patent Document ID: 5561747
Application ID: 08351871
Patent Status: 1

Claim One:
1. An information processing system for representing in a memory in the system a non-manifold object in a three-dimensional coordinate space as a plurality of boundary representations (BREPs), the BREPs including boundaries dividing the coordinate space into a plurality of topological entities each topological entity having a containment history list structure associated therewith, each containment history consisting of a list of identifiers of original BREPs containing the topological entity, absent an identification of operations performed therebetween, and further representing the object as a constructive solid geometry (CSG) tree defining boolean operations to be performed between the original BREPs, the system comprising: a. means for merging said plurality of original BREPs to form a merged BREP having merged boundaries and for storing said merged BREP including all said boundaries of said plurality of original BREPs in the memory, and said means for merging including means for forming merged boundaries defining merged topological entities at intersections between said plurality of original BREPS, means for forming a list consisting of a union of the containment history list data structures of said plurality of topological entities of said plurality of BREPs from which are formed each merged topological entity, the list formed absent an identification of operations performed between topological entities, and means for storing into locations of the memory associated with each merged topological entity the list containing the containment history of each merged topological entity; b. means for comparing a result of a boolean expression combining original BREPs with the containment histories to determine whether each topological entity is within a combination of original BREPs represented by the boolean expression; and c. means for in locations of the memory associated with each topological entity marking for further processing those entities within the combination of original BREPs from among said merged topological entities, the marked entities forming a set of topological entities corresponding to said object represented, and the means for marking responsive to said means for merging.