New files from new booleans
[blender.git] / intern / boolop / intern / BOP_Face2Face.cpp
1 /**
2  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version. The Blender
8  * Foundation also sells licenses for use in proprietary software under
9  * the Blender License.  See http://www.blender.org/BL/ for information
10  * about this.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software Foundation,
19  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
20  *
21  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
22  * All rights reserved.
23  *
24  * The Original Code is: all of this file.
25  *
26  * Contributor(s): none yet.
27  *
28  * ***** END GPL/BL DUAL LICENSE BLOCK *****
29  */
30  
31 #include "BOP_Face2Face.h"
32 #include "BOP_BBox.h"
33
34 // TAGS for segment classification in x-segment creation
35 // sA -> point of sA
36 // sB -> point of sB
37 // sX -> point of sA and SB
38 #define sA_sB 12
39 #define sB_sA 21
40 #define sX_sA 31
41 #define sA_sX 13
42 #define sX_sB 32
43 #define sB_sX 23
44 #define sX_sX 33
45     
46 #define sA_sA_sB 112
47 #define sB_sB_sA 221
48 #define sB_sA_sA 211
49 #define sA_sB_sB 122
50 #define sA_sB_sA 121
51 #define sB_sA_sB 212
52 #define sA_sX_sB 132
53 #define sB_sX_sA 231
54 #define sX_sA_sB 312
55 #define sX_sB_sA 321
56 #define sA_sB_sX 123
57 #define sB_sA_sX 213
58
59 #define sA_sA_sB_sB 1122
60 #define sB_sB_sA_sA 2211
61 #define sA_sB_sA_sB 1212
62 #define sB_sA_sB_sA 2121
63 #define sA_sB_sB_sA 1221
64 #define sB_sA_sA_sB 2112
65
66 void BOP_intersectCoplanarFaces(BOP_Mesh*  mesh, 
67                                                                 BOP_Faces* facesB, 
68                                                                 BOP_Face*  faceA, 
69                                                                 BOP_Face*  faceB, 
70                                                                 bool       invert);
71
72 void BOP_intersectCoplanarFaces(BOP_Mesh*   mesh, 
73                                                                 BOP_Faces*  facesB, 
74                                                                 BOP_Face*   faceB, 
75                                                                 BOP_Segment sA, 
76                                                                 MT_Plane3   planeA, 
77                                                                 bool        invert);
78
79 void BOP_intersectNonCoplanarFaces(BOP_Mesh*  mesh, 
80                                                                    BOP_Faces* facesA,  
81                                                                    BOP_Faces* facesB, 
82                                                                    BOP_Face*  faceA, 
83                                                                    BOP_Face*  faceB);
84
85 void BOP_getPoints(BOP_Mesh*    mesh, 
86                                    BOP_Face*    faceA, 
87                                    BOP_Segment& sA, 
88                                    MT_Plane3    planeB, 
89                                    MT_Point3*   points, 
90                                    unsigned int*         faces, 
91                                    unsigned int&         size, 
92                                    unsigned int         faceValue);
93
94 void BOP_mergeSort(MT_Point3 *points, unsigned int *face, unsigned int &size, bool &invertA, bool &invertB);
95
96 void BOP_createXS(BOP_Mesh*    mesh, 
97                                   BOP_Face*    faceA, 
98                                   BOP_Face*    faceB, 
99                                   BOP_Segment  sA, 
100                                   BOP_Segment  sB, 
101                                   bool         invert, 
102                                   BOP_Segment* segments);    
103
104 void BOP_createXS(BOP_Mesh*    mesh, 
105                                   BOP_Face*    faceA, 
106                                   BOP_Face*    faceB, 
107                                   MT_Plane3    planeA, 
108                                   MT_Plane3    planeB, 
109                                   BOP_Segment  sA, 
110                                   BOP_Segment  sB, 
111                                   bool         invert, 
112                                   BOP_Segment* segments);    
113
114 BOP_Index BOP_getVertexIndex(BOP_Mesh* mesh, 
115                                            MT_Point3 point, 
116                                            unsigned int       cfgA, 
117                                            unsigned int       cfgB, 
118                                            BOP_Index       vA, 
119                                            BOP_Index       vB, 
120                                            bool      invert);
121
122 BOP_Index BOP_getVertexIndex(BOP_Mesh *mesh, MT_Point3 point, unsigned int cfg, BOP_Index v);
123
124 void triangulate(BOP_Mesh *mesh,  BOP_Faces *faces, BOP_Face *face, BOP_Segment s);
125
126 BOP_Face *BOP_getOppositeFace(BOP_Mesh*  mesh, 
127                                                           BOP_Faces* faces, 
128                                                           BOP_Face*  face, 
129                                                           BOP_Edge*  edge);
130
131 bool BOP_overlap(MT_Vector3 normal, 
132                                  MT_Point3  p1, 
133                                  MT_Point3  p2, 
134                                  MT_Point3  p3, 
135                                  MT_Point3  q1, 
136                                  MT_Point3  q2, 
137                                  MT_Point3  q3);
138
139 void BOP_mergeVertexs(BOP_Mesh *mesh, unsigned int firstFace);
140
141
142 /**
143  * Computes intersections between faces of both lists.
144  * @param mesh mesh that contains the faces, edges and vertices
145  * @param facesA set of faces from object A
146  * @param facesB set of faces from object B
147  */
148 void BOP_Face2Face(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB)
149 {               
150         for(unsigned int idxFaceA=0;idxFaceA<facesA->size();idxFaceA++) {
151                 BOP_Face *faceA = (*facesA)[idxFaceA];
152                 MT_Plane3 planeA = faceA->getPlane();
153                 MT_Point3 p1 = mesh->getVertex(faceA->getVertex(0))->getPoint();
154                 MT_Point3 p2 = mesh->getVertex(faceA->getVertex(1))->getPoint();
155                 MT_Point3 p3 = mesh->getVertex(faceA->getVertex(2))->getPoint();
156
157                 BOP_BBox boxA(p1,p2,p3);
158         
159                 for(unsigned int idxFaceB=0;
160                         idxFaceB<facesB->size() && (faceA->getTAG() != BROKEN) && (faceA->getTAG() != PHANTOM);) {
161                         BOP_Face *faceB = (*facesB)[idxFaceB];
162                         if ((faceB->getTAG() != BROKEN) && (faceB->getTAG() != PHANTOM)) {
163                           BOP_BBox boxB(mesh->getVertex(faceB->getVertex(0))->getPoint(),
164                                         mesh->getVertex(faceB->getVertex(1))->getPoint(),
165                                         mesh->getVertex(faceB->getVertex(2))->getPoint());
166                           if (boxA.intersect(boxB)) {
167
168                             MT_Plane3 planeB = faceB->getPlane();
169                             if (BOP_containsPoint(planeB,p1) && 
170                                 BOP_containsPoint(planeB,p2) && 
171                                 BOP_containsPoint(planeB,p3)) {
172                               if (BOP_orientation(planeB,planeA)>0) {
173                                 BOP_intersectCoplanarFaces(mesh,facesB,faceA,faceB,false);
174                               }
175                             }
176                             else {
177                               BOP_intersectNonCoplanarFaces(mesh,facesA,facesB,faceA,faceB);
178                             }
179                           }                       
180                         }
181                         if (faceB->getTAG()==BROKEN){
182                           facesB->erase(facesB->begin()+idxFaceB);
183                         }else
184                           idxFaceB++;
185                 }
186         }
187         
188         
189         // Clean broken faces from facesA
190         BOP_IT_Faces it;
191         it = facesA->begin();
192         while (it != facesA->end()) {
193                 BOP_Face *face = *it;
194                 if (face->getTAG() == BROKEN) it = facesA->erase(it);
195                 else it++;
196         }
197         /*
198         it = facesB->begin();
199         while (it != facesB->end()) {
200                 BOP_Face *face = *it;
201                 if (face->getTAG() == BROKEN) it = facesB->erase(it);
202                 else it++;
203         }
204         */
205 }
206
207 /**
208  * Computes intesections of coplanars faces from object A with faces from object B.
209  * @param mesh mesh that contains the faces, edges and vertices
210  * @param facesA set of faces from object A
211  * @param facesB set of faces from object B
212  */
213 void BOP_sew(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB)
214 {
215         for(unsigned int idxFaceB = 0; idxFaceB < facesB->size(); idxFaceB++) {
216                 BOP_Face *faceB = (*facesB)[idxFaceB];
217                 MT_Plane3 planeB = faceB->getPlane();
218                 MT_Point3 p1 = mesh->getVertex(faceB->getVertex(0))->getPoint();
219                 MT_Point3 p2 = mesh->getVertex(faceB->getVertex(1))->getPoint();
220                 MT_Point3 p3 = mesh->getVertex(faceB->getVertex(2))->getPoint();
221                 
222                 for(unsigned int idxFaceA = 0;
223                         idxFaceA < facesA->size() &&
224                         faceB->getTAG() != BROKEN &&
225                         faceB->getTAG() != PHANTOM;
226                         idxFaceA++) {
227                         BOP_Face *faceA = (*facesA)[idxFaceA];
228                         if ((faceA->getTAG() != BROKEN)&&(faceA->getTAG() != PHANTOM)) {
229                                 MT_Plane3 planeA = faceA->getPlane();
230                                 if (BOP_containsPoint(planeA,p1) && 
231                                         BOP_containsPoint(planeA,p2) && 
232                                         BOP_containsPoint(planeA,p3)) {
233                                         if (BOP_orientation(planeA,planeB) > 0) {
234                                                 BOP_intersectCoplanarFaces(mesh,facesA,faceB,faceA,true);
235                                         }
236                                 }
237                         }
238                 }
239         }
240 }
241
242 /**
243  * Triangulates faceB using edges of faceA that both are complanars.
244  * @param mesh mesh that contains the faces, edges and vertices
245  * @param facesB set of faces from object B
246  * @param faceA face from object A
247  * @param faceB face from object B
248  * @param invert indicates if faceA has priority over faceB
249  */
250 void BOP_intersectCoplanarFaces(BOP_Mesh*  mesh,
251                                                                 BOP_Faces* facesB, 
252                                                                 BOP_Face*  faceA, 
253                                                                 BOP_Face*  faceB, 
254                                                                 bool       invert)
255 {
256         unsigned int oldSize = facesB->size();
257         unsigned int originalFaceB = faceB->getOriginalFace();    
258         
259         MT_Point3 p1 = mesh->getVertex(faceA->getVertex(0))->getPoint();
260         MT_Point3 p2 = mesh->getVertex(faceA->getVertex(1))->getPoint();
261         MT_Point3 p3 = mesh->getVertex(faceA->getVertex(2))->getPoint();
262         
263         MT_Vector3 normal(faceA->getPlane().x(),faceA->getPlane().y(),faceA->getPlane().z());
264         
265         MT_Vector3 p1p2 = p2-p1;
266         
267         MT_Plane3 plane1((p1p2.cross(normal).normalized()),p1);
268         
269         BOP_Segment sA;
270         sA.m_cfg1 = BOP_Segment::createVertexCfg(1);
271         sA.m_v1 = faceA->getVertex(0);
272         sA.m_cfg2 = BOP_Segment::createVertexCfg(2);
273         sA.m_v2 = faceA->getVertex(1);
274         
275         BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane1,invert);
276         
277         MT_Vector3 p2p3 = p3-p2;
278         MT_Plane3 plane2((p2p3.cross(normal).normalized()),p2);
279         
280         sA.m_cfg1 = BOP_Segment::createVertexCfg(2);
281         sA.m_v1 = faceA->getVertex(1);
282         sA.m_cfg2 = BOP_Segment::createVertexCfg(3);
283         sA.m_v2 = faceA->getVertex(2);
284   
285         if (faceB->getTAG() == BROKEN) {
286                 for(unsigned int idxFace = oldSize; idxFace < facesB->size(); idxFace++) {
287                         BOP_Face *face = (*facesB)[idxFace];
288                         if (face->getTAG() != BROKEN && originalFaceB == face->getOriginalFace())
289                                 BOP_intersectCoplanarFaces(mesh,facesB,face,sA,plane2,invert);
290                 }
291         }
292         else {
293                 BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane2,invert);
294         }
295   
296         MT_Vector3 p3p1 = p1-p3;
297         MT_Plane3 plane3((p3p1.cross(normal).normalized()),p3);
298         
299         sA.m_cfg1 = BOP_Segment::createVertexCfg(3);
300         sA.m_v1 = faceA->getVertex(2);
301         sA.m_cfg2 = BOP_Segment::createVertexCfg(1);
302         sA.m_v2 = faceA->getVertex(0);
303   
304         if (faceB->getTAG() == BROKEN) {
305                 for(unsigned int idxFace = oldSize; idxFace < facesB->size(); idxFace++) {
306                         BOP_Face *face = (*facesB)[idxFace];
307                         if (face->getTAG() != BROKEN && originalFaceB == face->getOriginalFace())
308                                 BOP_intersectCoplanarFaces(mesh,facesB,face,sA,plane3,invert);
309                 }
310         }
311         else {
312                 BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane3,invert);
313         } 
314 }
315
316 /**
317  * Triangulates faceB using segment sA and planeA.
318  * @param mesh mesh that contains the faces, edges and vertices
319  * @param facesB set of faces from object B
320  * @param faceB face from object B
321  * @param sA segment to intersect with faceB
322  * @param planeA plane to intersect with faceB
323  * @param invert indicates if sA has priority over faceB
324  */
325 void BOP_intersectCoplanarFaces(BOP_Mesh*   mesh, 
326                                                                 BOP_Faces*  facesB, 
327                                                                 BOP_Face*   faceB, 
328                                                                 BOP_Segment sA, 
329                                                                 MT_Plane3   planeA, 
330                                                                 bool        invert)
331 {
332         BOP_Segment sB = BOP_splitFace(planeA,mesh,faceB);
333
334         if (BOP_Segment::isDefined(sB.m_cfg1)) {
335                 BOP_Segment xSegment[2];
336                 BOP_createXS(mesh,NULL,faceB,planeA,MT_Plane3(),sA,sB,invert,xSegment);
337                 if (BOP_Segment::isDefined(xSegment[1].m_cfg1)) {
338                         unsigned int sizefaces = mesh->getNumFaces();
339                         triangulate(mesh,facesB,faceB,xSegment[1]);
340                         BOP_mergeVertexs(mesh,sizefaces);
341                 }
342         }
343 }
344
345 /**
346  * Triangulates faceB using edges of faceA that both are not complanars.
347  * @param mesh mesh that contains the faces, edges and vertices
348  * @param facesB set of faces from object B
349  * @param faceA face from object A
350  * @param faceB face from object B
351  */
352 void BOP_intersectNonCoplanarFaces(BOP_Mesh *mesh, 
353                                                                    BOP_Faces *facesA, 
354                                                                    BOP_Faces *facesB, 
355                                                                    BOP_Face *faceA, 
356                                                                    BOP_Face *faceB)
357 {
358         // Obtain segments of faces A and B from the intersection with their planes
359         BOP_Segment sA = BOP_splitFace(faceB->getPlane(),mesh,faceA);
360         BOP_Segment sB = BOP_splitFace(faceA->getPlane(),mesh,faceB);
361         
362         if (BOP_Segment::isDefined(sA.m_cfg1) && BOP_Segment::isDefined(sB.m_cfg1)) {    
363                 // There is an intesection, build the X-segment
364                 BOP_Segment xSegment[2];
365                 BOP_createXS(mesh,faceA,faceB,sA,sB,false,xSegment);
366                 
367                 unsigned int sizefaces = mesh->getNumFaces();
368                 triangulate(mesh,facesA,faceA,xSegment[0]);
369                 BOP_mergeVertexs(mesh,sizefaces);
370         
371                 sizefaces = mesh->getNumFaces();
372                 triangulate(mesh,facesB,faceB,xSegment[1]);
373                 BOP_mergeVertexs(mesh,sizefaces);
374         }
375 }
376
377 /**
378  * Tests if faces since firstFace have all vertexs non-coincident of colinear, otherwise repairs the mesh.
379  * @param mesh mesh that contains the faces, edges and vertices
380  * @param firstFace first face index to be tested
381  */
382 void BOP_mergeVertexs(BOP_Mesh *mesh, unsigned int firstFace)
383 {
384         unsigned int numFaces = mesh->getNumFaces();
385         for(unsigned int idxFace = firstFace; idxFace < numFaces; idxFace++) {
386                 BOP_Face *face = mesh->getFace(idxFace);
387                 if ((face->getTAG() != BROKEN) && (face->getTAG() != PHANTOM)) {
388                         BOP_Index v1 = face->getVertex(0);
389                         BOP_Index v2 = face->getVertex(1);
390                         BOP_Index v3 = face->getVertex(2);
391                         MT_Point3 vertex1 = mesh->getVertex(v1)->getPoint();
392                         MT_Point3 vertex2 = mesh->getVertex(v2)->getPoint();
393                         MT_Point3 vertex3 = mesh->getVertex(v3)->getPoint();
394                         int dist12 = BOP_comp(vertex1,vertex2);
395                         int dist13 = BOP_comp(vertex1,vertex3);
396                         int dist23 = BOP_comp(vertex2,vertex3);
397
398                         if (dist12 == 0) {
399                                 if (dist13 == 0) {
400                                         // v1 ~= v2 , v1 ~= v3 , v2 ~= v3
401                                         mesh->replaceVertexIndex(v2,v1);
402                                         mesh->replaceVertexIndex(v3,v1);                
403                                 }
404                                 else {
405                                         if (dist23 == 0) {
406                                                 mesh->replaceVertexIndex(v1,v2);
407                                                 mesh->replaceVertexIndex(v3,v2);
408                                         }
409                                         else {
410                                                 mesh->replaceVertexIndex(v1,v2);
411                                         }
412                                 }
413                         }
414                         else {
415                                 if (dist13 == 0) {
416                                         // v1 ~= v3
417                                         if (dist23 == 0) {
418                                                 mesh->replaceVertexIndex(v1,v3);
419                                                 mesh->replaceVertexIndex(v2,v3);
420                                         }
421                                         else {
422                                                 mesh->replaceVertexIndex(v1,v3);
423                                         }
424                                 }
425                                 else {
426                                         if (dist23 == 0) {
427                                                 // v2 ~= v3
428                                                 mesh->replaceVertexIndex(v2,v3);
429                                         } else {
430                                                 // all differents
431                                                 if (BOP_collinear(vertex1,vertex2,vertex3)) {
432                                                         // collinear triangle 
433                                                         face->setTAG(PHANTOM);
434                                                 }
435                                         }
436                                 }
437                         }
438                 }
439         }
440 }
441
442 /**
443  * Obtains the points of the segment created from the intersection between faceA and planeB.
444  * @param mesh mesh that contains the faces, edges and vertices
445  * @param faceA intersected face
446  * @param sA segment of the intersection between  faceA and planeB
447  * @param planeB intersected plane
448  * @param points array of points where the new points are saved
449  * @param faces array of relative face index to the points
450  * @param size size of arrays points and faces
451  * @param faceValue relative face index of new points
452  */
453 void BOP_getPoints(BOP_Mesh*    mesh, 
454                                    BOP_Face*    faceA, 
455                                    BOP_Segment& sA, 
456                                    MT_Plane3    planeB, 
457                                    MT_Point3*   points, 
458                                    unsigned int*         faces, 
459                                    unsigned int&         size, 
460                                    unsigned int          faceValue) 
461 {
462         MT_Point3 p1,p2;  
463   
464         if (BOP_Segment::isDefined(sA.m_cfg1)) {
465                 if (BOP_Segment::isEdge(sA.m_cfg1)) {
466                         // the new point becomes of split faceA edge 
467                         p1 = BOP_splitEdge(planeB,mesh,faceA,BOP_Segment::getEdge(sA.m_cfg1));
468                 }
469                 else if (BOP_Segment::isVertex(sA.m_cfg1)) {
470                         // the new point becomes of vertex faceA
471                         p1 =  mesh->getVertex(BOP_Segment::getVertex(sA.m_v1))->getPoint();
472                 }
473
474                 if (BOP_Segment::isDefined(sA.m_cfg2)) {
475                         if (BOP_Segment::isEdge(sA.m_cfg2)) {
476                                 p2 = BOP_splitEdge(planeB,mesh,faceA,BOP_Segment::getEdge(sA.m_cfg2));
477                         }
478                         else if (BOP_Segment::isVertex(sA.m_cfg2)) { 
479                                 p2 =  mesh->getVertex(BOP_Segment::getVertex(sA.m_v2))->getPoint();
480                         }
481                         points[size] = p1;
482                         points[size+1] = p2;
483                         faces[size] = faceValue;
484                         faces[size+1] = faceValue;
485                         size += 2;
486                 }
487         
488                 else {
489                         points[size] = p1;
490                         faces[size] = faceValue;
491                         size++;
492                 }
493         }
494 }
495
496 /**
497  * Sorts the colinear points and relative face indices.
498  * @param points array of points where the new points are saved
499  * @param faces array of relative face index to the points
500  * @param size size of arrays points and faces
501  * @param invertA indicates if points of same relative face had been exchanged
502  */
503 void BOP_mergeSort(MT_Point3 *points, unsigned int *face, unsigned int &size, bool &invertA, bool &invertB) {
504   MT_Point3 sortedPoints[4];
505   unsigned int sortedFaces[4];
506   unsigned int position[4];
507   if (size == 2) {
508
509     // Trivial case, only test the merge ...
510     if (BOP_comp(0,points[0].distance(points[1]))==0) {
511       face[0] = 3;
512       size--;
513     }
514   }
515   else {
516     // size is 3 or 4
517     // Get segment extreme points
518     MT_Scalar maxDistance = -1;
519     for(unsigned int i=0;i<size-1;i++){
520       for(unsigned int j=i+1;j<size;j++){
521         MT_Scalar distance = points[i].distance(points[j]);
522         if (distance > maxDistance){
523           maxDistance = distance;
524           position[0] = i;
525           position[size-1] = j;
526         }
527       }
528     }
529
530     // Get segment inner points
531     position[1] = position[2] = size;
532     for(unsigned int i=0;i<size;i++){
533       if ((i != position[0]) && (i != position[size-1])){
534         if (position[1] == size) position[1] = i;
535         else position[2] = i;
536       }
537     }
538
539     // Get inner points
540     if (position[2] < size) {
541       MT_Scalar d1 = points[position[1]].distance(points[position[0]]);
542       MT_Scalar d2 = points[position[2]].distance(points[position[0]]);
543       if (d1 > d2) {
544         unsigned int aux = position[1];
545         position[1] = position[2];
546         position[2] = aux;
547       }
548     }
549
550     // Sort data
551     for(unsigned int i=0;i<size;i++) {
552       sortedPoints[i] = points[position[i]];
553       sortedFaces[i] = face[position[i]];
554     }
555
556     // invertA, invertB ¿?
557     invertA = false;
558     invertB = false;
559     if (face[1] == 1) {
560       // invertA¿?
561       for(unsigned int i=0;i<size;i++) {
562         if (position[i] == 1) {
563           invertA = true;
564           break;
565         }
566         else if (position[i] == 0) break;
567       }
568       // invertB¿?
569       if (size == 4) {
570         for(unsigned int i=0;i<size;i++) {
571           if (position[i] == 3) {
572             invertB = true;
573             break;
574           }
575           else if (position[i] == 2) break;
576         }
577       }
578     }
579     else if (face[1] == 2) {
580       // invertB¿?
581       for(unsigned int i=0;i<size;i++) {
582         if (position[i] == 2) {
583           invertB = true;
584           break;
585         }
586         else if (position[i] == 1) break;
587       }
588     }
589
590
591     // Merge data
592     MT_Scalar d1 = sortedPoints[1].distance(sortedPoints[0]);
593     MT_Scalar d2 = sortedPoints[1].distance(sortedPoints[2]);
594     if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[0]) {
595       if (BOP_comp(0,d2)==0 && sortedFaces[1] != sortedFaces[2])  {
596         if (d1 < d2) {
597           // merge 0 and 1
598           sortedFaces[0] = 3;
599           for(unsigned int i = 1; i<size-1;i++) {
600             sortedPoints[i] = sortedPoints[i+1];
601             sortedFaces[i] = sortedFaces[i+1];
602           }
603           size--;
604           if (size == 3) {
605             // merge 1 and 2 ???
606             d1 = sortedPoints[1].distance(sortedPoints[2]);
607             if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[2])  {
608               // merge!
609               sortedFaces[1] = 3;
610               size--;
611             }
612           }
613         }
614         else {
615           // merge 1 and 2
616           sortedFaces[1] = 3;
617           for(unsigned int i = 2; i<size-1;i++) {
618             sortedPoints[i] = sortedPoints[i+1];
619             sortedFaces[i] = sortedFaces[i+1];
620           }
621           size--;
622         }        
623       }
624       else {
625         // merge 0 and 1
626         sortedFaces[0] = 3;
627         for(unsigned int i = 1; i<size-1;i++) {
628           sortedPoints[i] = sortedPoints[i+1];
629           sortedFaces[i] = sortedFaces[i+1];
630         }
631         size--;
632         if (size == 3) {
633           // merge 1 i 2 ???
634           d1 = sortedPoints[1].distance(sortedPoints[2]);
635           if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[2])  {
636             // merge!
637             sortedFaces[1] = 3;
638             size--;
639           }
640         }
641       }     
642     }
643     else {
644       if (BOP_comp(0,d2)==0 && sortedFaces[1] != sortedFaces[2])  {
645         // merge 1 and 2
646         sortedFaces[1] = 3;
647         for(unsigned int i = 2; i<size-1;i++) {
648           sortedPoints[i] = sortedPoints[i+1];
649           sortedFaces[i] = sortedFaces[i+1];
650         }
651         size--;
652       }
653       else if (size == 4) {
654         d1 = sortedPoints[2].distance(sortedPoints[3]);
655         if (BOP_comp(0,d1)==0 && sortedFaces[2] != sortedFaces[3])  {
656           // merge 2 and 3
657           sortedFaces[2] = 3;
658           size--;
659         }
660       }
661     }
662     
663     // Merge initial points ...
664     for(unsigned int i=0;i<size;i++) {
665       points[i] = sortedPoints[i];
666       face[i] = sortedFaces[i];
667     }
668
669   }
670 }  
671
672
673 /**
674  * Computes the x-segment of two segments (the shared interval). The segments needs to have sA.m_cfg1 > 0 && sB.m_cfg1 > 0 .
675  * @param mesh mesh that contains the faces, edges and vertices
676  * @param faceA face of object A
677  * @param faceB face of object B
678  * @param sA segment of intersection between faceA and planeB
679  * @param sB segment of intersection between faceB and planeA
680  * @param invert indicates if faceA has priority over faceB
681  * @param segmemts array of the output x-segments
682  */
683 void BOP_createXS(BOP_Mesh*    mesh, 
684                                   BOP_Face*    faceA, 
685                                   BOP_Face*    faceB, 
686                                   BOP_Segment  sA, 
687                                   BOP_Segment  sB, 
688                                   bool         invert, 
689                                   BOP_Segment* segments) {    
690         return BOP_createXS(mesh, faceA, faceB, faceA->getPlane(), faceB->getPlane(),
691                                                 sA, sB, invert, segments);
692 }
693
694 /**
695  * Computes the x-segment of two segments (the shared interval). The segments needs to have sA.m_cfg1 > 0 && sB.m_cfg1 > 0 .
696  * @param mesh mesh that contains the faces, edges and vertices
697  * @param faceA face of object A
698  * @param faceB face of object B
699  * @param planeA plane of faceA
700  * @param planeB plane of faceB
701  * @param sA segment of intersection between faceA and planeB
702  * @param sB segment of intersection between faceB and planeA
703  * @param invert indicates if faceA has priority over faceB
704  * @param segmemts array of the output x-segments
705  */
706 void BOP_createXS(BOP_Mesh*    mesh, 
707                                   BOP_Face*    faceA, 
708                                   BOP_Face*    faceB, 
709                                   MT_Plane3    planeA, 
710                                   MT_Plane3    planeB, 
711                                   BOP_Segment  sA, 
712                                   BOP_Segment  sB, 
713                                   bool         invert, 
714                                   BOP_Segment* segments)
715 {    
716         MT_Point3 points[4];  // points of the segments
717         unsigned int face[4]; // relative face indexs (1 => faceA, 2 => faceB)
718         unsigned int size = 0;  // size of points and relative face indexs
719   
720         BOP_getPoints(mesh, faceA, sA, planeB, points, face, size, 1);
721         BOP_getPoints(mesh, faceB, sB, planeA, points, face, size, 2);
722
723         bool invertA = false;
724         bool invertB = false;
725         BOP_mergeSort(points,face,size,invertA,invertB);
726
727         if (invertA) sA.invert();
728         if (invertB) sB.invert();
729         
730         // Compute the configuration label
731         unsigned int label = 0;
732         for(unsigned int i =0; i < size; i++) {
733                 label = face[i]+label*10;    
734         }
735
736         if (size == 1) {
737                 // Two coincident points
738                 segments[0].m_cfg1 = sA.m_cfg1;
739                 segments[1].m_cfg1 = sB.m_cfg1;
740                 
741                 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
742                                                                                           sA.m_v1, sB.m_v1, invert);
743                 segments[1].m_v1 = segments[0].m_v1;
744                 segments[0].m_cfg2 = segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
745         }
746         else if (size == 2) {
747                 switch(label) {
748                 // Two non-coincident points
749                 case sA_sB:
750                 case sB_sA:
751                         segments[0].m_cfg1 = 
752                         segments[1].m_cfg1 = 
753                         segments[0].m_cfg2 = 
754                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
755                         break;
756       
757                 // Two coincident points and one non-coincident of sA
758                 case sA_sX:
759                         segments[0].m_cfg1 = sA.m_cfg2;
760                         segments[1].m_cfg1 = sB.m_cfg1;
761                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg1,
762                                                                                                   sA.m_v2, sB.m_v1, invert);
763                         segments[1].m_v1 = segments[0].m_v1;
764                         
765                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
766                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
767                         break;
768                 case sX_sA:
769                         segments[0].m_cfg1 = sA.m_cfg1;
770                         segments[1].m_cfg1 = sB.m_cfg1;
771                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
772                                                                                                   sA.m_v1, sB.m_v1, invert);
773                         segments[1].m_v1 = segments[0].m_v1;
774                         
775                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
776                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
777                         break;
778       
779                 // Two coincident points and one non-coincident of sB
780                 case sB_sX:
781                         segments[0].m_cfg1 = sA.m_cfg1;
782                         segments[1].m_cfg1 = sB.m_cfg2;
783                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg1, sB.m_cfg2, 
784                                                                                                   sA.m_v1, sB.m_v2, invert);
785                         segments[1].m_v1 = segments[0].m_v1;
786                         
787                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
788                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
789                         break;
790                 case sX_sB:
791                         segments[0].m_cfg1 = sA.m_cfg1;
792                         segments[1].m_cfg1 = sB.m_cfg1;
793                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 
794                                                                                                   sA.m_v1, sB.m_v1, invert);
795                         segments[1].m_v1 = segments[0].m_v1;
796                 
797                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
798                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
799                         break;
800       
801                 // coincident points 2-2
802                 case sX_sX:
803                         segments[0].m_cfg1 = sA.m_cfg1;
804                         segments[1].m_cfg1 = sB.m_cfg1;          
805                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 
806                                                                                                   sA.m_v1, sB.m_v1, invert);
807                         segments[1].m_v1 = segments[0].m_v1;
808                         
809                         segments[0].m_cfg2 = sA.m_cfg2;
810                         segments[1].m_cfg2 = sB.m_cfg2;          
811                         segments[0].m_v2 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg2, 
812                                                                                                   sA.m_v2, sB.m_v2, invert);
813                         segments[1].m_v2 = segments[0].m_v2;
814                         break;
815                 
816                 default:
817                         break; 
818                 }
819         }
820         else if (size == 3) {
821                 switch(label) {
822                 case sA_sA_sB:
823                 case sB_sA_sA:
824                 case sA_sB_sB:
825                 case sB_sB_sA:
826                         segments[0].m_cfg1 = 
827                         segments[1].m_cfg1 = 
828                         segments[0].m_cfg2 = 
829                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
830                         break;
831       
832                 case sA_sB_sA:
833                         segments[1].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
834                         segments[1].m_cfg1 = sB.m_cfg1;
835                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
836                         segments[0].m_cfg1 = sA.getConfig();
837                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
838                         segments[0].m_v1 = segments[1].m_v1;
839                         break;
840       
841                 case sB_sA_sB:
842                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
843                         segments[0].m_cfg1 = sA.m_cfg1;
844                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
845                         segments[1].m_cfg1 = sB.getConfig();
846                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
847                         segments[1].m_v1 = segments[0].m_v1;
848                         break;
849       
850                 case sA_sX_sB:
851                         segments[0].m_cfg1 = sA.m_cfg2;
852                         segments[1].m_cfg1 = sB.m_cfg1;          
853                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg1, 
854                                                                                                   sA.m_v2, sB.m_v1, invert);
855                         segments[1].m_v1 = segments[0].m_v1;
856                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
857                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
858                         break;
859     
860                 case sB_sX_sA:
861                         segments[0].m_cfg1 = sA.m_cfg1;
862                         segments[1].m_cfg1 = sB.m_cfg2;          
863                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg1, sB.m_cfg2, 
864                                                                                                   sA.m_v1, sB.m_v2, invert);
865                         segments[1].m_v1 = segments[0].m_v1;
866                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
867                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
868                         break;
869       
870                 case sX_sA_sB:
871                         segments[0].m_cfg1 = sA.m_cfg1;
872                         segments[1].m_cfg1 = sB.m_cfg1;          
873                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
874                                                                                                   sA.m_v1, sB.m_v1, invert);
875                         segments[1].m_v1 = segments[0].m_v1;
876                         
877                         segments[0].m_cfg2 = sA.m_cfg2;
878                         segments[1].m_cfg2 = sB.getConfig();
879                         segments[0].m_v2 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sA.m_v2);
880                         segments[1].m_v2 = segments[0].m_v2;
881                         break;
882       
883                 case sX_sB_sA:
884                         segments[0].m_cfg1 = sA.m_cfg1;
885                         segments[1].m_cfg1 = sB.m_cfg1;          
886                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
887                                                                                                   sA.m_v1, sB.m_v1, invert);
888                         segments[1].m_v1 = segments[0].m_v1;
889                         
890                         segments[0].m_cfg2 = sA.getConfig();
891                         segments[1].m_cfg2 = sB.m_cfg2;
892                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg2,sB.m_v2);
893                         segments[1].m_v2 = segments[0].m_v2;
894                         break;
895       
896                 case sA_sB_sX:
897                         segments[0].m_cfg1 = sA.getConfig();
898                         segments[1].m_cfg1 = sB.m_cfg1;
899                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
900                         segments[1].m_v1 = segments[0].m_v1;
901                         
902                         segments[0].m_cfg2 = sA.m_cfg2;
903                         segments[1].m_cfg2 = sB.m_cfg2;          
904                         segments[0].m_v2 = BOP_getVertexIndex(mesh, points[2], sA.m_cfg2, sB.m_cfg2, 
905                                                                                                   sA.m_v2, sB.m_v2, invert);
906                         segments[1].m_v2 = segments[0].m_v2;
907                         break;
908
909                 case sB_sA_sX:
910                         segments[0].m_cfg1 = sA.m_cfg1;
911                         segments[1].m_cfg1 = sB.getConfig();
912                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
913                         segments[1].m_v1 = segments[0].m_v1;
914                         
915                         segments[0].m_cfg2 = sA.m_cfg2;
916                         segments[1].m_cfg2 = sB.m_cfg2;          
917                         segments[0].m_v2 = BOP_getVertexIndex(mesh, points[2], sA.m_cfg2, sB.m_cfg2,
918                                                                                                   sA.m_v2, sB.m_v2, invert);
919                         segments[1].m_v2 = segments[0].m_v2;
920                         break;
921       
922                 default:
923                         break; 
924                 }
925         }
926         else {
927                 // 4!
928                 switch(label) {
929                 case sA_sA_sB_sB:
930                 case sB_sB_sA_sA:
931                         segments[0].m_cfg1 = 
932                         segments[1].m_cfg1 = 
933                         segments[0].m_cfg2 = 
934                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
935                         break;
936       
937                 case sA_sB_sA_sB:
938                         segments[0].m_cfg1 = sA.getConfig();
939                         segments[1].m_cfg1 = sB.m_cfg1;
940                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
941                         segments[1].m_v1 = segments[0].m_v1;
942                         
943                         segments[0].m_cfg2 = sA.m_cfg2;
944                         segments[1].m_cfg2 = sB.getConfig();
945                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sA.m_cfg2,sA.m_v2);
946                         segments[1].m_v2 = segments[0].m_v2;
947                         break;          
948       
949                 case sB_sA_sB_sA:
950                         segments[0].m_cfg1 = sA.m_cfg1;
951                         segments[1].m_cfg1 = sB.getConfig();
952                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
953                         segments[1].m_v1 = segments[0].m_v1;
954                         
955                         segments[0].m_cfg2 = sA.getConfig();
956                         segments[1].m_cfg2 = sB.m_cfg2;
957                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sB.m_cfg2,sB.m_v2);
958                         segments[1].m_v2 = segments[0].m_v2;
959                         break;          
960       
961                 case sA_sB_sB_sA:
962                         segments[0].m_cfg1 = sA.getConfig();
963                         segments[1].m_cfg1 = sB.m_cfg1;
964                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
965                         segments[1].m_v1 = segments[0].m_v1;
966                         
967                         segments[0].m_cfg2 = segments[0].m_cfg1;
968                         segments[1].m_cfg2 = sB.m_cfg2;
969                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sB.m_cfg2,sB.m_v2);
970                         segments[1].m_v2 = segments[0].m_v2;
971                         break;
972       
973                 case sB_sA_sA_sB:
974                         segments[0].m_cfg1 = sA.m_cfg1;
975                         segments[1].m_cfg1 = sB.getConfig();
976                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
977                         segments[1].m_v1 = segments[0].m_v1;
978                         
979                         segments[0].m_cfg2 = sA.m_cfg2;
980                         segments[1].m_cfg2 = segments[1].m_cfg1;
981                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sA.m_cfg2,sA.m_v2);
982                         segments[1].m_v2 = segments[0].m_v2;
983                         break;
984       
985                 default:
986                         break; 
987                 }
988         }
989         
990         segments[0].sort();
991         segments[1].sort();
992 }
993
994 /**
995  * Computes the vertex index of a point.
996  * @param mesh mesh that contains the faces, edges and vertices
997  * @param point input point
998  * @param cfgA configuration of point on faceA
999  * @param cfgB configuration of point on faceB
1000  * @param vA vertex index of point on faceA
1001  * @param vB vertex index of point on faceB
1002  * @param invert indicates if vA has priority over vB
1003  * @return final vertex index in the mesh
1004  */
1005 BOP_Index BOP_getVertexIndex(BOP_Mesh* mesh, 
1006                                            MT_Point3 point, 
1007                                            unsigned int       cfgA, 
1008                                            unsigned int       cfgB, 
1009                                            BOP_Index       vA, 
1010                                            BOP_Index       vB, 
1011                                            bool      invert)
1012 {
1013         if (BOP_Segment::isVertex(cfgA)) { // exists vertex index on A
1014                 if (BOP_Segment::isVertex(cfgB)) { // exists vertex index on B
1015                         // unify vertex indexs
1016                         if (invert)
1017                                 return mesh->replaceVertexIndex(vA,vB);
1018                         else 
1019                                 return mesh->replaceVertexIndex(vB,vA);
1020                 }
1021                 else
1022                         return vA;
1023         }
1024         else {// does not exist vertex index on A
1025                 if (BOP_Segment::isVertex(cfgB)) // exists vertex index on B
1026                         return vB;      
1027                 else {// does not exist vertex index on B
1028                         return mesh->addVertex(point);
1029                 }
1030         } 
1031 }
1032
1033 /**
1034  * Computes the vertex index of a point.
1035  * @param mesh mesh that contains the faces, edges and vertices
1036  * @param cfg configuration of point
1037  * @param v vertex index of point
1038  * @return final vertex index in the mesh
1039  */
1040 BOP_Index BOP_getVertexIndex(BOP_Mesh *mesh, MT_Point3 point, unsigned int cfg, BOP_Index v)
1041 {
1042         if (BOP_Segment::isVertex(cfg)) // vertex existent
1043                 return v;       
1044         else {
1045                 return mesh->addVertex(point);
1046         }
1047 }
1048
1049 /******************************************************************************/
1050 /*** TRIANGULATE                                                            ***/
1051 /******************************************************************************/
1052
1053 /**
1054  * Triangulates the input face according to the specified segment.
1055  * @param mesh mesh that contains the faces, edges and vertices
1056  * @param faces set of faces that contains the original face and the new triangulated faces
1057  * @param face face to be triangulated
1058  * @param s segment used to triangulate face
1059  */
1060 void triangulate(BOP_Mesh *mesh, BOP_Faces *faces, BOP_Face *face, BOP_Segment s)
1061 {
1062         if (BOP_Segment::isUndefined(s.m_cfg1)) {
1063                 // Nothing to do
1064         }
1065         else if (BOP_Segment::isVertex(s.m_cfg1)) {
1066                 // VERTEX(v1) + VERTEX(v2) => nothing to do
1067         }
1068         else if (BOP_Segment::isEdge(s.m_cfg1)) {
1069                 if (BOP_Segment::isVertex(s.m_cfg2) || BOP_Segment::isUndefined(s.m_cfg2)) {
1070                         // EDGE(v1) + VERTEX(v2)
1071                         BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
1072                         BOP_triangulateA(mesh,faces,face,s.m_v1,BOP_Segment::getEdge(s.m_cfg1));
1073                         BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
1074                         if (opposite != NULL) {
1075                           unsigned int e;
1076                           opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
1077                           BOP_triangulateA(mesh, faces, opposite, s.m_v1, e);
1078                         }
1079                 }
1080                 else {
1081                         //  EDGE(v1) + EDGE(v2)
1082                         if (BOP_Segment::getEdge(s.m_cfg1) == BOP_Segment::getEdge(s.m_cfg2)) {
1083                                  // EDGE(v1) == EDGE(v2)
1084                                 BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
1085                                 BOP_triangulateD(mesh, faces, face, s.m_v1, s.m_v2, 
1086                                                                  BOP_Segment::getEdge(s.m_cfg1)); 
1087                                 BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
1088                                 if (opposite != NULL) {
1089                                   unsigned int e;
1090                                   opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
1091                                   BOP_triangulateD(mesh, faces, opposite, s.m_v1, s.m_v2, e);
1092                                 }
1093                 }
1094                         else { // EDGE(v1) != EDGE(v2)
1095                                 BOP_Edge *edge1 = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
1096                                 BOP_Edge *edge2 = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg2));
1097                                 BOP_triangulateE(mesh, faces, face, s.m_v1, s.m_v2,
1098                                                                  BOP_Segment::getEdge(s.m_cfg1),
1099                                                                  BOP_Segment::getEdge(s.m_cfg2));
1100                                 BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge1);
1101                                 if (opposite != NULL) {
1102                                   unsigned int e;
1103                                   opposite->getEdgeIndex(edge1->getVertex1(), edge1->getVertex2(),e);
1104                                   BOP_triangulateA(mesh, faces, opposite, s.m_v1, e);
1105                                 }
1106                                 opposite = BOP_getOppositeFace(mesh,faces,face,edge2);
1107                                 if (opposite != NULL) {
1108                                   unsigned int e;
1109                                   opposite->getEdgeIndex(edge2->getVertex1(), edge2->getVertex2(),e);
1110                                   BOP_triangulateA(mesh, faces, opposite, s.m_v2, e);
1111                                 }
1112                         }
1113                 }
1114         }
1115         else if (BOP_Segment::isIn(s.m_cfg1)) {
1116                 if (BOP_Segment::isVertex(s.m_cfg2) || BOP_Segment::isUndefined(s.m_cfg2)) {
1117                         // IN(v1) + VERTEX(v2)
1118                         BOP_triangulateB(mesh,faces,face,s.m_v1);
1119                 }
1120                 else if (BOP_Segment::isEdge(s.m_cfg2)) {
1121                         // IN(v1) + EDGE(v2)
1122                         BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg2));
1123                         BOP_triangulateF(mesh,faces,face,s.m_v1,s.m_v2,BOP_Segment::getEdge(s.m_cfg2));
1124                         BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
1125                         if (opposite != NULL) {
1126                           unsigned int e;
1127                           opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
1128                           BOP_triangulateA(mesh, faces, opposite, s.m_v2, e);
1129                         }
1130                 }
1131                 else // IN(v1) + IN(v2)
1132                         BOP_triangulateC(mesh,faces,face,s.m_v1,s.m_v2);
1133         }
1134 }
1135
1136 /**
1137  * Returns if a face is in the set of faces.
1138  * @param faces set of faces
1139  * @param face face to be searched
1140  * @return if the face is inside faces
1141  */
1142 bool BOP_containsFace(BOP_Faces *faces, BOP_Face *face)
1143 {
1144   const BOP_IT_Faces facesEnd = faces->end();
1145         for(BOP_IT_Faces it=faces->begin();it!=facesEnd;it++)
1146         {
1147                 if (*it == face)
1148                 return true;
1149         }
1150         
1151         return false;
1152 }
1153
1154 /**
1155  * Returns the first face of faces that shares the input edge of face.
1156  * @param mesh mesh that contains the faces, edges and vertices
1157  * @param faces set of faces
1158  * @param face input face
1159  * @param edge face's edge
1160  * @return first face that shares the edge of input face
1161  */
1162 BOP_Face *BOP_getOppositeFace(BOP_Mesh*  mesh, 
1163                                                           BOP_Faces* faces, 
1164                                                           BOP_Face*  face,
1165                                                           BOP_Edge*  edge)
1166 {
1167         if (edge == NULL)
1168           return NULL;
1169   
1170         BOP_Indexs auxfaces = edge->getFaces();
1171         const BOP_IT_Indexs auxfacesEnd = auxfaces.end();
1172         for(BOP_IT_Indexs it = auxfaces.begin(); it != auxfacesEnd; it++) {
1173                 BOP_Face *auxface = mesh->getFace(*it);
1174                 if ((auxface != face) && (auxface->getTAG()!=BROKEN) && 
1175                         BOP_containsFace(faces,auxface)) {
1176                         return auxface;
1177                 }
1178         }        
1179   
1180         return NULL;
1181 }
1182
1183 /******************************************************************************/ 
1184 /***  OVERLAPPING                                                           ***/
1185 /******************************************************************************/ 
1186
1187 /**
1188  * Removes faces from facesB that are overlapped with anyone from facesA.
1189  * @param mesh mesh that contains the faces, edges and vertices
1190  * @param facesA set of faces from object A
1191  * @param facesB set of faces from object B
1192  */
1193 void BOP_removeOverlappedFaces(BOP_Mesh *mesh,  BOP_Faces *facesA,  BOP_Faces *facesB)
1194 {
1195         for(unsigned int i=0;i<facesA->size();i++) {
1196                 BOP_Face *faceI = (*facesA)[i];       
1197                 if (faceI->getTAG()==BROKEN) continue;
1198                 bool overlapped = false;
1199                 MT_Point3 p1 = mesh->getVertex(faceI->getVertex(0))->getPoint();
1200                 MT_Point3 p2 = mesh->getVertex(faceI->getVertex(1))->getPoint();
1201                 MT_Point3 p3 = mesh->getVertex(faceI->getVertex(2))->getPoint();
1202                 for(unsigned int j=0;j<facesB->size();) {
1203                         BOP_Face *faceJ = (*facesB)[j];
1204                         if (faceJ->getTAG()!=BROKEN) {
1205                           MT_Plane3 planeJ = faceJ->getPlane();
1206                           if (BOP_containsPoint(planeJ,p1) && BOP_containsPoint(planeJ,p2) 
1207                               && BOP_containsPoint(planeJ,p3)) {
1208                             MT_Point3 q1 = mesh->getVertex(faceJ->getVertex(0))->getPoint();
1209                             MT_Point3 q2 = mesh->getVertex(faceJ->getVertex(1))->getPoint();
1210                             MT_Point3 q3 = mesh->getVertex(faceJ->getVertex(2))->getPoint();
1211                             if (BOP_overlap(MT_Vector3(planeJ.x(),planeJ.y(),planeJ.z()),
1212                                             p1,p2,p3,q1,q2,q3)) {
1213                               facesB->erase(facesB->begin()+j,facesB->begin()+(j+1));
1214                               faceJ->setTAG(BROKEN);
1215                               overlapped = true;
1216                             }
1217                             else j++;
1218                           }
1219                           else j++;
1220                         }else j++;
1221                 }
1222                 if (overlapped) faceI->setTAG(OVERLAPPED);
1223         }
1224 }
1225
1226 /**
1227  * Computes if triangle p1,p2,p3 is overlapped with triangle q1,q2,q3.
1228  * @param normal normal of the triangle p1,p2,p3
1229  * @param p1 point of first triangle
1230  * @param p2 point of first triangle
1231  * @param p3 point of first triangle
1232  * @param q1 point of second triangle
1233  * @param q2 point of second triangle
1234  * @param q3 point of second triangle
1235  * @return if there is overlapping between both triangles
1236  */
1237 bool BOP_overlap(MT_Vector3 normal, MT_Point3 p1, MT_Point3 p2, MT_Point3 p3, 
1238                                   MT_Point3 q1, MT_Point3 q2, MT_Point3 q3)
1239 {
1240         MT_Vector3 p1p2 = p2-p1;    
1241         MT_Plane3 plane1(p1p2.cross(normal),p1);
1242         
1243         MT_Vector3 p2p3 = p3-p2;
1244         MT_Plane3 plane2(p2p3.cross(normal),p2);
1245         
1246         MT_Vector3 p3p1 = p1-p3;    
1247         MT_Plane3 plane3(p3p1.cross(normal),p3);
1248   
1249         BOP_TAG tag1 = BOP_createTAG(BOP_classify(q1,plane1));
1250         BOP_TAG tag2 = BOP_createTAG(BOP_classify(q1,plane2));
1251         BOP_TAG tag3 = BOP_createTAG(BOP_classify(q1,plane3));
1252         BOP_TAG tagQ1 = BOP_createTAG(tag1,tag2,tag3);   
1253         if (tagQ1 == IN_IN_IN) return true;    
1254   
1255         tag1 = BOP_createTAG(BOP_classify(q2,plane1));
1256         tag2 = BOP_createTAG(BOP_classify(q2,plane2));
1257         tag3 = BOP_createTAG(BOP_classify(q2,plane3));
1258         BOP_TAG tagQ2 = BOP_createTAG(tag1,tag2,tag3);
1259         if (tagQ2 == IN_IN_IN) return true;    
1260         
1261         tag1 = BOP_createTAG(BOP_classify(q3,plane1));
1262         tag2 = BOP_createTAG(BOP_classify(q3,plane2));
1263         tag3 = BOP_createTAG(BOP_classify(q3,plane3));
1264         BOP_TAG tagQ3 = BOP_createTAG(tag1,tag2,tag3);
1265         if (tagQ3 == IN_IN_IN) return true;    
1266   
1267         if ((tagQ1 & OUT_OUT_OUT) == 0 && (tagQ2 & OUT_OUT_OUT) == 0 && 
1268                 (tagQ3 & OUT_OUT_OUT) == 0) return true;
1269         else return false;
1270 }