Boundary evaluation in non-manifold environment

Abstract

An information processing system performs boundary evaluation in a non-manifold environment. The system may be used for representation of objects in three dimensions, in a very general manner. Objects are represented by merging boundary representations of constituent sub objects, and selecting portions of the resulting merge boundary representation. Selection is based on criteria applied to a containment history of each portion of the merged boundary representation. A data structure suitable for boundary evaluation in a non-manifold environment includes a constructive solid geometry tree and a boundary representation. The boundary representation further includes boundary descriptions, a list of regions, containment histories of each region and a mark indicative of selection or non-selection of each region.

What is claimed is: 
     
       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.   
     
     
       2. An information processing system as claimed in claim 1, further comprising: a. means for unmerging said merged BREP by removing a constituent BREP therefrom.   
     
     
       3. An information processing system as claimed in claim 1, wherein said means for marking further comprises: a. means for receiving a representation of a Boolean operation to be performed using said plurality of BREPs as operands; and   b. means for writing marks in locations in the memory corresponding to said merged regions representing a result of said Boolean operation received.   
     
     
       4. An information processing system as claimed in claim 1, further comprising: means responsive to said means for marking for displaying images of said marked entities.   
     
     
       5. In a data processing system, a method for displaying a graphical image of an object including a plurality of sub-objects represented in a memory by boundary representations of topological entities and containment histories of the topological entities, the containment histories listing sub-objects containing each 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 method comprising the steps of: a. identifying intersections between topological entities of said sub-objects, in each said boundary representation;   b. constructing a merged boundary representation from said boundary representations and said intersections identified by said step of identifying, thereby forming a plurality of new topological entities;   c. setting a containment history for each new topological entity to a union of the containment histories of the topological entities of the sub-objects from which each new topological entity was formed, the list formed absent an identification of operations performed between topological entities;   d. classifying said new topological entities of said merged boundary representation according to said containment histories;   e. selecting topological entities corresponding to said object, from among said classified merged boundary representation for display, said selecting performed in response to said classifying;   f. retaining all of said classified topological entities, without regard to said step of selecting; and   g. displaying said selected topological entities corresponding to said object, from among said classified merged boundary representation.   
     
     
       6. The method of claim 5, further comprising the step of: f. editing said merged boundary representation.   
     
     
       7. The method of claim 6 for displaying and editing objects including surfaces, faces, edges, vertices and regions belonging to said plurality of sub-objects, wherein step f. further comprises the steps of: identifying a sub-object to be removed;   removing faces for which said classified new topological entities on each side of each said face differ only by said sub-object to be removed;   removing each said edge for which said edge is not adjacent to a face;   removing each said edge for which said edge is adjacent to two faces defining a single surface;   removing each said edge for which said edge is adjacent to exactly one face;   removing each said vertex for which said vertex is not adjacent to an edge and is not adjacent to a face;   removing each said vertex for which said vertex is not adjacent to an edge and is adjacent to a face;   removing each said vertex for which said vertex is adjacent to two edges on one surface and adjacent to two faces; and   removing said sub-object from said classified new to topological entities remaining.   
     
     
       8. The method of claim 5, wherein step d. further comprises the steps: d.1 receiving a selection criterion; and   d.2 marking locations in the memory corresponding to topological entities whose classified containments fit said selection criterion.   
     
     
       9. The method of claim 8, further comprising the steps of: d.3 receiving a new selection criterion;   d.4 deselecting portions of said classified merged boundary representation by unmarking locations in the memory corresponding to topological entities having classified containments fitting said selection criterion; and   d.5 selecting portions of said classified merged boundary representation by marking locations in the memory corresponding to topological entities having classified containments fitting said new selection criterion.   
     
     
       10. A computer system for displaying representations of solid objects comprising: a computer memory for storing a plurality of component geometric models, each component geometric model comprising one of more boundary elements;   a computer input means for specifying one or more combinatorial operations for combining at least two component geometric models to form a combined geometric model;   a computer processor running a software program to perform the specified operation on the component geometric models, thereby generating the combined geometric model, said processor executing steps in the software program to   merge all component geometric models in the combined geometric model,   intersect the combined geometric model to form merged boundaries where each merged boundary and all component geometric models containing the merged boundary intersect at an intersection equal to the merged boundary,   form a containment history for each merged boundary listing identifiers of component geometric models containing each merged boundary by forming a union of containment histories of the component geometric models intersected to form each merged boundary, the list formed absent an identification of operations performed between topological entities, and   identify one or more boundary elements of the combined geometric model as output boundary elements; and   a computer readout and display means for reading from said computer memory and displaying said segment boundary elements identified as output boundary elements of the combined geometric model such that the displaying of the output boundary elements displays the representation of a solid object;   the computer memory further storing   a. an identification of the boundary elements contained in each component model;   b. an identification of the containment history of all the boundary elements identified, the list formed absent an identification of operations performed between topological entities;   c. an identification of the boundary elements which are output boundary elements;   d. an identification of all component models contained in the combined geometric model; and   e. separate from the identification of the containment history, an identification of all the combinatorial operations performed on the identified component models.   
     
     
       11. An information processing system for representing an object in a multi-dimensional coordinate space as a plurality of primitives and operations to be performed therebetween stored in a memory as a constructive solid geometry (CSG) tree and a plurality of original boundary representations (BREPs), the original BREPs including boundaries dividing the coordinate space into a plurality of regions, and the original BREPs further including containment histories of the plurality of regions, the containment history of each region listing identifiers of those primitives containing the region, the list formed absent an identification of operations performed between topological entities, the system comprising: a processor unit executing a software program including instructions to: a. merge the plurality of original BREPs into a merged BREP including all boundaries of the plurality of original BREPs and including all new boundaries created by intersections among objects represented by the plurality of original BREPs, thereby forming a new plurality of regions,   b. add elements to the CSG tree representation of the primitives and operations performed therebetween to form the object, and   c. classify each new region of the new plurality of regions as belonging to all regions of the plurality of regions which contain each new region by forming a union of containment histories of original BREPs containing each new region; and     a memory for storing the original and merged BREPs, including the containment histories of the regions, and for separately storing the CSG tree.   
     
     
       12. A computer system for displaying representations of solid objects comprising: a computer memory for storing a plurality of component geometric models, each component geometric model comprising one of more boundary elements;   a computer input means for specifying one or more combinatorial operations for combining at least two component geometric models to form a combined geometric model;   a computer processor running a software program to perform the specified operation on the component geometric models, thereby generating the combined geometric model, said processor executing steps in the software program to merge all component geometric models in the combined geometric model into a common database,   intersect the combined geometric model to form merged boundaries defining merged regions, where each merged boundary and all component geometric models containing the merged boundary intersect at an intersection equal to the merged boundary,   form a containment history for each merged region, the containment history being a portion of the common database holding a list of identifiers of component geometric models containing each merged region, the containment history formed as a union of containment histories of the component geometric models intersected to form each merged region and the containment history, the list formed absent an identification of operations performed between topological entities, and   identify one or more boundary elements of the combined geometric model as output boundary elements; and     a computer readout and display means for reading from said computer memory and displaying said segment boundary elements identified as output boundary elements of the combined geometric model such that the displaying of the output boundary elements displays the representation of a solid object; the computer memory further containing   a. a list of the boundary elements contained in each component model;   b. for each boundary element identified, a list identifying the containment history of the boundary element identified, the list formed absent an identification of operations performed between topological entities;   c. an identification with the boundary elements identified indicating which are output boundary elements; and   d. separate from each list identifying the containment listing, an identification of all the combinatorial operations performed on the identified component models.