MGC - Exemples d'Operacions Booleanes

Boolean Operations between BRep objects
Examples

Here there are two examples of Boolean operations between two cubes, where the first one leads to an uncertainty while reconstructing faces of the resulting object; the second one results in a hole in a face.

Vertices and faces of example cubes

OBJECT A (the coordinates are the same for both examples)

OBJECT B (the coordinates are different for each example, but the representation is the same)

Example 1:
Suppose we have two objects (parallelepipeds) A and B. For simplicity, we use a simple BRep model, in which for each face we only store the relationship F:{V} (vertices are ordered following the right-hand rule, pointing outside the object), and three cordinates of vertices. Note also that considering polygons does not make sense here, since faces does not have holes. If we number vertices and faces of B following those numerated in A to avoid confusion, the BRep for the objects is:

 Object A Object B

 Faces Vertices Faces Vertices

1:{3,4,8,7} 1:(0,0,0) 7:{11,12,16,15} 9:(1,2,2)

2:{2,6,8,4} 2:(3,0,0) 8:{10,14,16,12} 10:(2,2,2)
3:{1,5,6,2} 3:(0,0,3) 9:{ 9,13,14,10} 11:(1,2,5)
4:{1,3,7,5} 4:(3,0,3) 10:{ 9,11,15,13} 12:(2,2,5)

5:{5,7,8,6} 5:(0,3,0) 11:{13,15,16,14} 13:(1,4,2)
6:{1,2,4,3} 6:(3,3,0) 12:{ 9,10,12,11} 14:(2,4,2)
 7:(0,3,3) 15:(1,4,5)

 8:(3,3,3) 16:(2,4,5)

Example 2:
Suppose we have two objects (parallelepipeds) A and B so that we keep A's position, but we have moved B through the y axis:

 Object A Object B

 Faces Vertices Faces Vertices

1:{3,4,8,7} 1:(0,0,0) 7:{11,12,16,15} 9:(1,1,2)

2:{2,6,8,4} 2:(3,0,0) 8:{10,14,16,12} 10:(2,1,2)
3:{1,5,6,2} 3:(0,0,3) 9:{ 9,13,14,10} 11:(1,1,5)
4:{1,3,7,5} 4:(3,0,3) 10:{ 9,11,15,13} 12:(2,1,5)

5:{5,7,8,6} 5:(0,3,0) 11:{13,15,16,14} 13:(1,2,2)
6:{1,2,4,3} 6:(3,3,0) 12:{ 9,10,12,11} 14:(2,2,2)
 7:(0,3,3) 15:(1,2,5)

 8:(3,3,3) 16:(2,2,5)

Obtain result of substraction A - B using face classification algorithm.
1. Creating the list of faces LC
  - Faces belonging to A or B that do not intersect with the other object and therefore we add them directly to list LC:
```
 Example 1 Example 2

Face 2: fromAoutB Face 2: fromAoutB
Face 3: fromAoutB Face 3: fromAoutB
Face 4: fromAoutB Face 4: fromAoutB
Face 6: fromAoutB Face 5: fromAoutB
Face 7: fromBoutA Face 6: fromAoutB
Face 11: fromBoutA Face 7: fromBoutA

 Face 9: fromBinA
```
  - Faces belonging to A that intersect with B and produce two pieces, which are added separately to LC:
```
 Example 1 Example 2

Face 5.1: fromAoutB Face 1.3: fromAoutB
Face 5.2: fromAinB Face 1.4: fromAinB

Face 1.1: fromAoutB
Face 1.2: fromAinB
```
    (faces 1.1 and 5.1 have 8 edges and have the "U" shape, while faces 1.2 and 5.2 have 4 edges; face 1.4 has 4 edges too and face 1.3 has a hole of 4 edges)
  - Faces belonging to B that intersect with A and produce two pieces, which are added separately to LC:
```
 Example 1 Example 2

Face 8.1: fromBoutA Face 8.3: fromBoutA
Face 8.2: fromBinA Face 8.4: fromBinA
Face 9.1: fromBoutA Face 10.3: fromBoutA
Face 9.2: fromBinA Face 10.4: fromBinA
Face 10.1: fromBoutA Face 11.3: fromBoutA
Face 10.2: fromBinA Face 11.4: fromBinA
Face 12.1: fromBoutA Face 12.3: fromBoutA
Face 12.2: fromBinA Face 12.4: fromBinA
```
    (all subfaces have 4 edges excepting 8.1 and 10.1, which have the "L" shape and have 6 edges)
2. Generation of faces of the resulting object from the list of faces LC.
  Since the final object is A - B, in order to get its faces we just walk the list LC and select fromAoutB and fromBinA elements.
3. Generation of vertices of the resulting object.
  Note that vertices belonging to final object are simply the vertices of faces generated at 4.2.
Getting substraction A - B using the vertex classification algorithm
1. Creating the list of vertices LV: Addition of vertices belonging to both A and B. The list LV is as follows (for each vertex, "xyz" means its coordinates, "{...}" is the list of its faces, and “fromX..” represents its type. Note that coordinates and the list of neighboring faces can be obtained directly from the object's BRep model):
```
 Example 1 Example 2


V 1: xyz, {4,3,6}, fromAoutB V 1: xyz, {4,3,6}, fromAoutB
V 2: xyz, {3,2,6}, fromAoutB V 2: xyz, {3,2,6}, fromAoutB
V 3: xyz, {1,4,6}, fromAoutB V 3: xyz, {1,4,6}, fromAoutB
V 4: xyz, {2,1,6}, fromAoutB V 4: xyz, {2,1,6}, fromAoutB
V 5: xyz, {5,3,4}, fromAoutB V 5: xyz, {5,3,4}, fromAoutB
V 6: xyz, {5,2,3}, fromAoutB V 6: xyz, {5,2,3}, fromAoutB
V 7: xyz, {1,5,4}, fromAoutB V 7: xyz, {1,5,4}, fromAoutB
V 8: xyz, {2,5,1}, fromAoutB V 8: xyz, {2,5,1}, fromAoutB
V 9: xyz, {9,10,12}, fromBinA V 9: xyz, {9,10,12}, fromBinA
V10: xyz, {9,8,12}, fromBinA V10: xyz, {9,8,12}, fromBinA
V11: xyz, {7,10,12}, fromBoutA V11: xyz, {7,10,12}, fromBoutA
V12: xyz, {8,7,12}, fromBoutA V12: xyz, {8,7,12}, fromBoutA
V13: xyz, {11,9,10}, fromBoutA V13: xyz, {11,9,10}, fromBinA
V14: xyz, {11,8,9}, fromBoutA V14: xyz, {11,8,9}, fromBinA
V15: xyz, {7,11,10}, fromBoutA V15: xyz, {7,11,10}, fromBoutA
V16: xyz, {8,11,7}, fromBoutA V16: xyz, {8,11,7}, fromBoutA
```
  Although it may be interesting to use more stringent criteria for cyclicity in order to avoid uncertainties in face reconstruction, we assume here that the list of faces fro each vertex is sorted cyclically, because there exist an edge separating each face and its next in the list. It exists a common edge between last and first faces of the list, too. It also could be interesting to store convexity or concavity for each edge around the vertices. See the page of geometric tests to learn how to calculate it.
2. Creating the list of vertices LV: Adding new vertices
  In the following lists we are going to take the convention that the first two new faces at each vertex are shared by the edge that has intersected with the face of the other object, which is third on the list:
```
 Example 1 Example 2

V17: xyz, {9,10,5}, New V23: xyz, {10,11,1}, New
V18: xyz, {8,9,5}, New V24: xyz, {11,8,1}, New
V19: xyz, {1,5,10}, New V25: xyz, {10,12,1}, New
V20: xyz, {1,5,8}, New V26: xyz, {12,8,1}, New
V21: xyz, {10,12,1},New
V22: xyz, {8,12,1}, New
```
  (vertex 17, for instance, is the intersection between edge V9-V13 from object B and face 5 from objecteA. Faces are 9,10,5 because edge 9-13 from object B limits with faces 9 and 10; it is the same with the rest of edges)
  
  Note that edge – face intersections that must be done at this stage have the coincidences between A and B test as a subproduct. When an edge a from one object intersects with face c from the other, the only thing to check is the position of the intersection point P: if P is coincident with one of the edge's vertices, or if P belongs to one of the polygon's edges, we can state that we are in a matching case, so a message must be returned and the algorithm must be stopped. Otherwise, if P is between both edge's vertices and P is inside the face, P must be added to the vertex list LV. Remember that the point inside face test can be performed in 2D using P and c projections on one canonical plane (see page of geometric tests). Calculus of convexity or concavity of new created edges around these vertices depends on the current boolean operations being performed, as shown in the page of geometric tests.
3. Filtering the list LV and obtaining the list of vertices of the resluting object
  As we are generating vertices of A - B, we generate the sublist containing vertices fromAoutB, fromBinA, and new ones:
```
 Example 1 Example 2

V 1: xyz, {4,3,6}, fromAoutB V 1: xyz, {4,3,6}, fromAoutB
V 2: xyz, {3,2,6}, fromAoutB V 2: xyz, {3,2,6}, fromAoutB
V 3: xyz, {1,4,6}, fromAoutB V 3: xyz, {1,4,6}, fromAoutB
V 4: xyz, {2,1,6}, fromAoutB V 4: xyz, {2,1,6}, fromAoutB
V 5: xyz, {5,3,4}, fromAoutB V 5: xyz, {5,3,4}, fromAoutB
V 6: xyz, {5,2,3}, fromAoutB V 6: xyz, {5,2,3}, fromAoutB
V 7: xyz, {1,5,4}, fromAoutB V 7: xyz, {1,5,4}, fromAoutB
V 8: xyz, {2,5,1}, fromAoutB V 8: xyz, {2,5,1}, fromAoutB
V 9: xyz, {9,10,12}, fromBinA V 9: xyz, {9,10,12}, fromBinA
V10: xyz, {9,8,12}, fromBinA V10: xyz, {9,8,12}, fromBinA

 V13: xyz, {11,9,10}, fromBinA
 V14: xyz, {11,8,9}, fromBinA

V17: xyz, {9,10,5}, New V23: xyz, {10,11,1}, New
V18: xyz, {8,9,5}, New V24: xyz, {11,8,1}, New
V19: xyz, {1,5,10}, New V25: xyz, {10,12,1}, New
V20: xyz, {1,5,8}, New V26: xyz, {12,8,1}, New
V21: xyz, {10,12,1},New
V22: xyz, {8,12,1}, New
```
4. Construction of faces of the resulting object
  Let's see the reconstruction of one single face of the final object. We are going to see the reconstruction of face coming from face 1 of A, because this case will allow some discussions.
  
  The fist step is select vertices that have face 1 in its face list from LV:
```
 Example 1 Example 2

V 3: xyz, {4,1,6}, fromAoutB V 3: xyz, {4,1,6}, fromAoutB
V 4: xyz, {2,1,6}, fromAoutB V 4: xyz, {2,1,6}, fromAoutB
V 7: xyz, {4,1,5}, fromAoutB V 7: xyz, {4,1,5}, fromAoutB
V 8: xyz, {5,1,2}, fromAoutB V 8: xyz, {5,1,2}, fromAoutB

V19: xyz, {10,1,5}, New V23: xyz, {11,1,10}, New
V20: xyz, {8,1,5}, New V24: xyz, {8,1,11}, New
V21: xyz, {12,1,10},New V25: xyz, {12,1,10}, New
V22: xyz, {8,1,12}, New V26: xyz, {8,1,12}, New
```
  Note: in order to make things easier for the vertex sequencing algorithm, we have made a circular rotation within each list of faces, so that the face in reconstruction (face 1) is located in the middle. If we had any vertex with more than three faces on his list, only three must be kept at this stage: face being reconstructed at the moment, and the previous and next ones in the circular list. Therefore, the result of extracting the list of vertices from the LV list has always the same structured depicted here, with reduced lists of three faces per vertex.
  
  Note for those with curiosity: Although we are not going to show it here, it is a good idea to impose a coherent sense to the face sublist of each vertex in order to avoid uncertainties in face reconstruction. Sense must be a default one, clockwise or counter-clockwise, observing the vertex from the outside of the resulting object. This implies, in some cases, reversing the cyclic face list. Note that sense depends on the current boolean operation performed: a given vertex may require different senses in its face list, depending on the operation performed (a union or a substraction).
  - Now apply the “domino” algorithm to example 1: We form the following chain (behind each arrow is the face connecting both vertices in the “domino” algorithm):
```
V3 ------> V4 ------> V8 ------> ?
 Face 6 Face 2 Face 5
```
    The problem now is that we have three candidate vertices to be the next of V8 sharing face 5: 7, 19 and 20. Uncertainty must be resolved here. This can be achieved in two ways:
    - Finding the closest vertex in the direction and sense of the edge that we are rebuilding (sense can be known considering normal vectors of adjacent faces, and considering if current reconstructing edge is either convex or concave, see page of geometric tests).
    - Ordering aligned vertices that produce uncertainty (this sorting is performed choosing one of the vertices coordinates, or the value of the parameter in the parametric equation of the support line of the edge, see page of geometric tests): V8, V20, V19, V7 and grouping by pairs ordered vertices. As obviously final edges correspond with these pairs, we can conclude that we have two aligned edges V8 - V20 and V19 - V7, so the next of V8 is V20.
    Once we know that the next of V8 is V20, we can continue the face reconstruction until we close the vertex cycle, returning to V3:
```
V8 ------> V20 ------> V22 ------> V21 -------> V19
 Face 5 Face 8 Face 12 Face 10 |

 |
 | Face 5
 |
 |
 V3 <------ V7 <--
 Face 4
```
    Note that we have reconstructed one face with one polygon alone, which has as vertices
```
V3, V4, V8, V20, V22, V21, V19 and V7.
```

Now apply the “domino” algorithm to example 2: We form the following chain (behind each arrow is the face connecting both vertices in the “domino” algorithm):

V3 ------> V4 ------> V8 ------> V7 ------> V3
 Face 6 Face 2 Face 5 Face 4

thus we have closed a cycle, but the problem is that we have not gone through all vertices in face 1 sublist. This indicates that the new face of A – B, which corresponds to face 1 of A, has more than one polygon. We continue the reconstruction with remaining vertices:

V23 -------> V24 ------> V26 -------> V25 -------> V23
 Face 11 Face 8 Face 12 Face 10

Note that we have reconstructed one face with two polygons, which have as vertices

 V3, V4, V8 and V7

 V23, V24, V26 and V25

Finally two steps more are to be done:

We must check that the sense of the half edges in each polygon is correct (it is not necessary in the case that cyclic face lists are ordered clockwise or counter-clockwise, because the algorithm provides the correct sense of half edges). Note that the sense of normal vector to faces in the resulting object equals its corresponding face in A or B, excepting the case of a face belonging to B in a A-B operation.

We must check that the sense of the half edges in each polygon is correct (it is not necessary in the case that cyclic face lists are ordered clockwise or counter-clockwise). Note that the sense of normal vector to faces in the resulting object equals its corresponding face in A or B, excepting the case of a face belonging to B in a A-B operation – it is necessary to detect what polygon is external to a face and which one is the hole polygon. In this case, the second polygon is the hole polygon, because we can assure that any given vertex – V23 for instance – is interior in respect to the other polygon V3, V4, V8, V7 (see page of geometric tests).

Boolean Operations between BRep objectsExamples

Boolean Operations between BRep objects
Examples