Abstract:
A method for performing Boolean operations using a computer to create geometric models from primary geometric objects and their facets, comprises calculating intersection lines of facets, splitting facets through which the intersection lines pass, determining each facet is obvious or obscure, and regrouping the facets to form one or more geometric objects. This method does not utilize the most popular data structures CSG and B-REP in CAD/CG/Solid Modeling systems, but has the advantages of both CSG and B-REP: easy to implement and flexible.

Description:
BACKGROUND 
     Field of the Invention 
       [0001]    This invention provides an immediate Boolean operation method for building three (3) dimensional solid geometric models from primary geometric objects to Computer Aided Design, Computer Graphics, and Solid Modeling systems, which are widely used in product design, manufacturing, and simulation. Mechanic industry, culture and sports, everywhere there are geometric shapes, may have CAD/CG applications. 
       Related Art 
       [0002]    Computer hardware is so highly developed that even an ordinary Personal Computer may be used to install and run a commercial CAD/CG system, which normally has Boolean operation functions including AND, OR, and NOT. PC components comprise input devices, like a mouse and a keyboard, a main machine, a screen, and a printer. The software system contains geometric and non geometric functions.  FIG. 1  shows the main PC components and  FIGS. 2A through 2D  depict a typical CAD/CG software system architecture. 
         [0003]    Boolean operations provide a general process of building complex solid geometric objects from different geometric shapes, which include primary geometric objects, swept or extruded objects, to CAD/CG/Solid Modeling systems. Lee applied Boolean operations to divide surface [Lee U.S. Pat. No. 6,307,555]. 
         [0004]    Boolean operations may rely on Constructive Solid Geometry, CSG, to record primary geometry objects and operation sequence in a hierarchy way, which technically is easy to implement, whereas Boundary Representation, B-REP, is regarded as a more flexible way that supports more geometric object types like extended geometries [Gusoz, 1991]. 
         [0005]    This invention presents five (5) Boolean operation commands: combination, intersection, exclusion, difference, and division, which directly work on triangles decomposed from geometric facets used for rendering functions and do not require the data structure Constructive Solid Geometry or Boundary Representation. The data structures defined in this invention are a few of simple classes, algorithms are concise and easy to implement, and the five (5) commands allow the user to create geometric models not only by selecting the types of geometric objects but also by defining their facets.  FIG. 3  presents a box with 6 facets and a sphere with different facets make distinct results. 
         [0006]    This invention presents different data structures and algorithms compared with CSG and B-REP, the algorithms include triangle-triangle intersections, splitting triangles with sub-intersection lines, and regrouping triangles to form Boolean operation results. 
       BRIEF SUMMARY OF THE INVENTION 
       [0007]    This invention provides a set of data structures and algorithms for performing Boolean operations, which are used to build complex geometric models and work directly on triangles decomposed from geometric facets used as rendering data by computer hardware and rendering functions like OpenGL libraries. Geometries, for example, sphere, cone, cylinder, box, triangular facets, extruded or swept geometries, are triangulated to form a set, noted as TriangleSet, for displaying. When two geometries are selected for performing a Boolean operation, neighboring triangles will be added to each triangle in TriangleSet to form another set, BlOpTriangleSet. 
         [0008]    The second step of a Boolean operation this invention described is to search and build intersection lines between triangle sets. It starts with finding the first pair of intersecting triangles: this system builds an axis aligned minimum bounding box for each triangle and checks whether two bounding boxes overlap to decide if edge-triangle intersection needs to be calculated. Once the edge-triangle intersection point(s) falls inside a triangle, this system completes the searching task and stores the point data into an intersection line set. 
         [0009]    To extend current intersection line, this method traces neighboring triangles and calculates edge-triangle intersection points until the intersection line becomes closed. 
         [0010]    The third step of a Boolean operation this invention described is to split triangles. Each segment of the intersection lines references two (2) triangles, each of the triangles has at least one sub-intersection line that contains one or more segments, which divide a triangle into three (3) or more smaller triangles. After splitting the triangles, the original triangles are removed, and those smaller triangles are added to the BlOpTriangleSet. 
         [0011]    The fourth step of a Boolean operation this invention described is to decide each triangle is obscure or visible. If a triangle is enclosed by other triangles, it is obscure. A triangle is visible means it is outside another object. 
         [0012]    The fifth step of a Boolean operation this invention described is to regroup the triangles: some of them have to be removed and some need to be put together, and there are five (5) cases for regrouping. 
         [0013]    The final step of a Boolean operation this invention described is to map BlOpTriangleSet to TriangleSet. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]      FIG. 1  shows the main personal computer components, which generally contain a main machine, input devices including mouse and keyboard, a display, and a printer. A highly developed CAD/CG system can run on a PC machine. 
           [0015]      FIGS. 2A through 2D  describe a software architecture in which a CAD/CG/Solid Modeling system uses Boolean operations to build geometric models. 
           [0016]      FIG. 3  represents that different facets make various results even their original geometric object types and sizes are the same: the left side example has less facets and the right side has more facets. In these examples, Boolean Intersection operations work on a box and a sphere. 
           [0017]      FIG. 4  is a flowchart for immediate Boolean operations using geometric facets. 
           [0018]      FIG. 5  depicts that a triangle has three (3) neighbors. Given a triangle and its two vertices, there is one and only one neighboring triangle in solid models. 
           [0019]      FIGS. 6A and 6B  show two minimum bounding boxes do not overlap and two boxes overlap each other. Each triangle virtually has a minimum bounding box. If two boxes do not overlap, the triangles contained in the two boxes do not intersect. If the boxes overlap, edge-triangle intersection calculation is required. 
           [0020]      FIGS. 7A through 7C  depict three (3) edge-triangle intersection cases: an intersection point falls inside a triangle, an intersection point locates on an edge of a triangle, an intersection point is a vertex of a triangle. 
           [0021]      FIGS. 8A through 8D  show the searching candidate set, which allows the system to travel next triangle for extending intersection lines by conducting edge-triangle calculation. Triangles filled with colors are the last pair triangles that intersect each other, the triangles not filled are referenced by the member m_NeigTri of the data structure Triangle3dEx, which guides the system searching a minimum set of triangles when building intersection lines. The set contains one triangles, two triangles, or zero. 
           [0022]      FIGS. 9A through 9D  show four (4) examples of intersection lines. A box intersects a sphere, which has different facet numbers. 
           [0023]      FIGS. 10A through 10C  give three (3) examples of sub-intersection lines in darker color.  FIG. 10A  has one (1) sub-intersection line,  10 B two (2), and  10 C one (1). 
           [0024]      FIGS. 11A through 11D  show four (4) examples that sub-intersection lines divided a triangle into a set of triangles. 
           [0025]      FIGS. 12A through 12H  show a Delaunay mesh sequence in which each intersection point is inserted into the mesh step by step. 
           [0026]      FIG. 13  is the flowchart of Delaunay mesh Watson method that created the sequence of  FIGS. 12A through 12H . 
           [0027]      FIG. 14  shows that a triangle and its Delaunay mesh. The original triangle is removed and only the Delaunay mesh is reserved for late computations. 
           [0028]      FIG. 15  shows t-Buffer where t may be negative and positive. If the size of negative t and positive t is balanced in t-Buffer, the triangle concerned is closed by another object and is obscure. 
           [0029]      FIGS. 16A through 16E  show five (5) examples of Boolean operations conducted with a box and a sphere.  FIGS. 16F and 16G  depict the internal mesh of two Boolean operation resultants: Combination and Exclusion. 
       
    
    
     DETAILED DESCRIPTION 
       [0030]    This invention defines these data structures: Point3dEx, Triangle3dEx, and BlOpTriangle3dSet that inherit Point3d, Triangle3d, Triangle3dSet storing facets for rendering geometric objects. When performing a Boolean operation, the system maps rendering facets to BlOpTriangle3dSet and all following processes focus on the members and attributes of BlOpTriangle3dSet.  FIG. 4  is the flowchart describing the main procedure of Boolean operations conducted by the present invention. After a Boolean operation completed, the system maps the resultant stored in BlOpTriangle3dSet to rendering facets. 
       Geometric Facets for Rendering 
       [0031]    CAD systems render facets to represent a geometric object, such as sphere, cone, box, cylinder, extruded or swept object. A facet may compose three (3) more more points, and facets are usually decomposed into triangles for easy calculations. A box has six (6) facets decomposed into twelve (12) triangles. A sphere may have eighteen (18) facets, composing twenty four (24) triangles. A sphere may also be rendered using more than thousand (1,000) facets and triangles.  FIG. 3  shows a sphere rendered with different facets. This method uses Triangle3dSet to note triangle set data structure for rendering a geometric object, it contains two (2) attributes: a three (3) dimensional point set and a triangle set, where Triangle3d references Point3d. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 class Triangle3dSet 
               
               
                   
                 { 
               
               
                   
                    DataSet&lt;Point3d&gt;  m_PointSet; 
               
               
                   
                    DataSet&lt;Triangle3d&gt; m_TriangleSet; 
               
               
                   
                 }; 
               
               
                   
                 class Triangle3d 
               
               
                   
                 { 
               
               
                   
                    Reference&lt;Point3d&gt; m_P0, m_P1, m_P2; 
               
               
                   
                 }; 
               
               
                   
                 class Point3d 
               
               
                   
                 { 
               
               
                   
                    DataTypeI m_X, m_Y, m_Z; 
               
               
                   
                 }; 
               
               
                   
                   
               
             
          
         
       
     
       Triangles for Boolean Operations 
       [0032]    The Boolean Operation method described in this invention defined three (3) key classes: BlOpTriangleSet, Triangle3dEx, and Point3dEx. 
         [0000]    
       
         
               
               
             
               
               
               
             
               
               
               
             
               
               
             
               
               
               
             
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 class BlOpTriangleSet 
               
               
                   
                 { 
               
             
          
           
               
                   
                  DataSet&lt;Point3dEx&gt; 
                 m_PointSet; 
               
               
                   
                  DataSet&lt;Triangle3dEx&gt; 
                 m_TriangleSet; 
               
               
                   
                 }; 
               
               
                   
                 class Point3dEx : Point3d 
               
               
                   
                 { 
               
             
          
           
               
                   
                   DataTypeII 
                 m_ID; // position and sequence index 
               
               
                   
                   DataTypeIII 
                 m_X, m_Y, m_Z; // DataType III 
               
               
                   
                   
                 may be different from DataTypeI 
               
               
                   
                 }; 
               
             
          
           
               
                   
                 class Triangle3dEx : Triangle3d 
               
               
                   
                 { 
               
             
          
           
               
                   
                   DataTypeII 
                 m_ID; 
               
               
                   
                   Plane 
                 m_Plane; 
               
               
                   
                   DataTypeIV 
                 m_Normal[3]; 
               
             
          
           
               
                   
                   Triangle3dEx*m_NeigTri[3]; // neighboring triangles 
               
               
                   
                 }; 
               
               
                   
                   
               
             
          
         
       
     
         [0033]    DataTypeI may be int, long, unsigned long, or other integer types. DataTypeII is a float point data type, such as float, double, even long double. 
         [0034]    The class Triangle3dEx specifies each triangle may have 3 neighboring triangles, and every triangle is stored just one (1) copy in BlOpTriangleSet. Given the box example, the simplest way it has 12 triangles, even each of them has three (3) neighbors, BlOpTriangleSet still stores total 12 triangles. 
         [0035]    Technically Triangle3d may have the attribute m Normal. If DataTypeI and DataTypeIII are the same type, for example, double, the attribute m_Normal can be inherited. 
       Data Mapping 
       [0036]    The process of mapping Triangle3dSet to BlOpTriangleSet copies point set and triangle set from rendering statue and fills default attributes. Data mapping contains the following procedures:
   1) Copy points from Triangle3dSet to BlOpTriangleSet and ensure there are not identical points.   2) Copy triangles from Triangle3dSet to BlOpTriangleSet.   3) For each triangle in BlOpTriangleSet, set its neighboring triangles.   4) Calculate normal and build plane equation for each triangle in BlOpTriangleSet.   
 
         [0041]    Remark 1: Given two (2) points a and b, if |x a −x b  |&lt;ε and |y a −y b |&lt;ε and |z a −z b |&lt;ε, where ε is a positive float point number, for example 5.0e-16, then b is identical to a. 
         [0042]    Remark 2: When mapping points from rendering data to BlOpTriangleSet, the system checks if there is an identical point in BlOpTriangleSet. 
         [0043]    Remark 3: A triangle, which has three (3) points, defines a plane whose mathematical formula is ax+by+cz+d=0 and the class Plane internally records it as an array of four (4) numbers, such as double m_ABCD[4]. 
         [0044]    Remark 4: A triangle, if its three (3) points are not identical, always has a valid normal. Even it is related to m_ABCD, a separation copy makes things more clear and easy to handle later. 
         [0045]    Remark 5: Every triangle has three (3) edges, when there are no duplicated points, it has three (3) neighboring triangles in solid models.  FIG. 5  shows an example: a triangle filled with dark color and its three (3) neighbors. 
       The First Intersection Point 
       [0046]    Every triangle has three (3) vertices, which define a minimum bounding box. This method adopted axis aligned minimum bounding box. 
         [0047]    Given a pair of triangles, if their bounding box do not overlap, the two triangles have no intersection point; otherwise, this method carries out edge-triangle intersection calculation. 
         [0048]    If an edge of a triangle T a  intersects with a plane defined by a triangle T b  and the intersection point pet falls inside T b , then pet is the first intersection point. If pet is outside of T b , then switch the triangle position in the pair, (T a , T b ) changed to (T b , T a ), and conduct edge-triangle intersection calculation. 
         [0049]    Given the i-th edge of a triangle T a , i∈[0, 2], its formula is: p=p i +t*(p(i+1)% 3−p i ), and the plane defined by the triangle T b , its formula is: ax+by+cz+d=0. If the two formulas have a solution, the edge intersects with the plane. If the edge-plane intersection point falls inside the triangle T b , then the point is the edge-triangle intersection point. 
       Extending an Intersection Line 
       [0050]    This method defines a data structure for recording an intersection point as PntEgTri: 
         [0000]    
       
         
               
               
             
           
               
                   
               
             
             
               
                 class PntEgTri 
                   
               
               
                 { 
               
               
                    Triangle3dEx 
                 m_Tri0, m_Tri1; 
               
               
                    DataTypeI 
                 m_EdgeIndex; 
               
               
                    DataTypeI 
                 m_PointPosi; 
               
               
                    Point3dEx 
                 m_Point; 
               
               
                    Point3dEx 
                 *m_PntGlobalIndexA, *m_PntGlobalIndexB; 
               
               
                 }; 
               
               
                   
               
             
          
         
       
     
         [0051]    According to the location of an intersection point on a triangle, a PntEgTri, simply pet, can be classified into three (3) categories shown in  FIGS. 7A through 7C .
   1) The most popular case is edge-triangle intersection, pet locates on an edge of triangle T a  and inside triangle T b .   2) Edge-edge intersection, pet locates on an edge of triangle T a  and on an edge of triangle T b .   3) Edge-vertex intersection, pet locates on an edge of triangle T a  and on a vertex of triangle T b .   
 
         [0055]    To extend an intersection line, this method catches next neighboring triangle(s) and checks edge-triangle intersection until the intersection line gets closed. 
       Sub-Intersection Line 
       [0056]    An intersection line passes through a set of triangles and divides each triangle into multi partitions. The segments of an intersection line inside a triangle is a sub-intersection line.  FIGS. 10A through 10C  show three examples in which the dark lines are sub-intersection lines. In practice, a triangle may have zero, one, or two sub-intersection lines. 
         [0057]    The following algorithm shows how to get a valid reference to a triangle that has at least one sub-intersection line:
   for each intersection line
       for each intersection point, get the triangle references: (m_Tri0, m_Tri1)
           for each triangle of the triangle pair, if it is not split
               for each intersection line
                   search and build a sub-intersection line   
                   
               
           
       
 
         [0063]    Given a valid triangle and an intersection line, to decide if a pet belongs to the sub-intersection line of the triangle, this method checks whether
   1) pet is on an edge of the triangle,   2) or pet is inside the triangle,   3) or pet equals a vertex of the triangle.   
 
       Splitting a Triangle 
       [0067]    Given a set of sub-intersection lines, to split a triangle, this method
   1) Removes duplicated pets. If neighboring pets are identical, this method reserves just one copy.   2) Identifies the position of end pets: checks each pet locates on which edge of the triangle.   3) Splits the upper partition, down partition, and middle partition of the triangle where applicable.   
 
         [0071]    Given a set of points on a plane that represents a partition of a triangle, to decompose the plane into a group of triangles, this invention modified Delaunay 2D mesh Watson method, which is published in 1981 [Watson, 1981]. 
         [0072]    A Delaunay 2D mesh has three (3) data set: triangle set that holds the generated triangles, deleted triangle set that stores just deleted triangles, and polygon that records the outline of deleted triangle set. 
         [0073]    The modified Delaunay 2D mesh method contains the following steps:
   1) Build an outline point sequence that links sub-intersection lines and vertices of the triangle where applicable;   2) Map the three (3) dimensional point sequence to two (2) dimensional points according to the aspect of the plane;   3) Add four (4) points to form a bigger bounding box that encloses all the two (2) dimensional points;   4) Assume that one dialog line of the bounding box splits the box into two (2) triangles and adding them into the triangle set;   5) Insert every point except that bounding ones into the triangle set.
       a) For each point, checking every triangle in the triangle set whether its circumcircle contains the point or the last segment passes through the triangle. If the condition is true, erase it from the triangle set and add it to the deleted triangle set.   b) Use the deleted triangle set to extend polygon and clear the deleted triangle set immediately.   c) Use the polygon to generate triangle set and add them to the triangle set.   
       
 
         [0082]      FIGS. 12A through 12H  show a Delaunay 2D mesh sequence. 
       Deleting Split Triangles 
       [0083]    In the above step, a split triangle got a mark. After all triangles have been traversed, this method deletes the marked triangles.  FIG. 14  shows a deletion result. 
       Obscure Facets 
       [0084]    Given two sets of triangles A and B, if A bounds a triangle of B, T b , then T b  is obscure; if B bounds a triangle of A, T a , then T a  is obscure. 
         [0085]    To check whether a triangle T is bounded by an object O, this invention uses the following steps.
   (1) Calculate the centroid, c, of the triangle T   (2) Build a line l: p=c+t*N, which starts from the centroid and passes along the normal N of the triangle T   (3) For each triangle T o  of the object O, calculate line-plane intersection point. If there is a valid intersection point pet that falls inside the triangle T o , then calculate t that determined by centroid c and the pet, and add t to a depth buffer, butterT,   (4) Check the size of negative t and positive t stored in butterT. If the two sizes are equal, than the triangle T is bounded and obscure.   
 
       Regrouping the Facets 
       [0090]    This invention presents five (5) kinds of Boolean operations: combination, intersection, exclusion, difference, and division, each of them has a different regrouping procedure. 
         [0091]    The combination operation, logically it is OR, combines two solid geometric objects and generates a new object, which normally discards obscure partitions and reserves visible ones viewing from outside, has the following procedure.
   1) Delete obscure triangles of object A;   2) Delete obscure triangles of object B;   3) Merge the triangles of object A and B.   
 
         [0095]    The intersection operation, logically it is AND, which creates a solid geometric object using public section(s) of two geometric objects and discards any partitions of A and B outside the shared public section(s), has the following procedure.
   1) Delete NOT obscure triangles of object A;   2) Delete NOT obscure triangles of object B;   3) Merge the triangles of object A and B.   
 
         [0099]    The exclusion operation, which builds a solid geometric object by removing public section(s) of two geometric objects and keeps not shared partitions, has following procedure.
   1) Copy object A&#39;s obscure triangles to a buffer, buffer A;   2) Delete obscure triangles from object A;   3) Copy object B′s obscure triangles to object A;   4) Delete obscure triangles from object B;   5) Copy the triangles in buffer A to object B;   6) Reverse the normal of every obscure triangle of A and B;   7) Merge the triangles of the two objects.   
 
         [0107]    The difference operation, which cuts geometric object A with another object B by removing any partitions of A inside B, has the following procedure.
   1) Delete obscure triangles of object A;   2) Delete NOT obscure triangles of object B;   3) Reverse the normal of every triangle of object B;   4) Merge triangles of object A and B.   
 
         [0112]    The division operation, which divides two solid geometric object A and B into three (3) objects, public section(s) of the two geometric objects, the NOT shared partitions of A and partitions of B, has the following procedure.
   1) Copy object A&#39;s obscure triangles to a buffer, buffer A;   2) Copy object B′s obscure triangles to buffer A;   3) Copy object A&#39;s obscure triangles to another buffer, buffer B;   4) Delete object A&#39;s obscure triangles;   5) Copy object B′s obscure triangles to object A;   6) Delete object B′s obscure triangles;   7) Copy object A′s obscure triangles stored in buffer A to object B;   8) Reverse the normal of every obscure triangles of A and B.   
 
       Mapping to Rendering Facets 
       [0121]    Once a Boolean operation finished, this method maps BlOpTriangleSet to rendering triangles.
   1) Each Point3dEx of BlOpTriangleSet is mapped to a Point3d of TriangleSet;   2) Each Triangle3dEx of BlOpTriangleSet is mapped to a Triangle3d of TriangleSet.   
 
         [0000]    
       
         
               
             
               
               
               
               
               
             
           
               
                   
               
               
                 U.S. PATENT DOCUMENTS 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 6,307,555 
                 October 2001 
                 Lee 
                 345/423 
               
               
                   
                   
               
             
          
         
       
     
       OTHER PUBLICATIONS 
       [0000]    
       
         “Boolean Set Operations on Non-Manifold bounding Representation Objects”, E. Gursoz et al., Computer-Aided Design 23 (1991) January/February No. 1 London, GB. “Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopest”, D. F. Watson”, The Computer Journal 24 (2) 1981.