745c64eaa97cd5968b9465af172a79fb3eb51170
[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 #if 0
431         /*
432          * for now, don't just remove "co-linear" faces; some of these faces
433          * being removed are real and cause other things to break
434          */
435                                                 // all differents
436                                                 if (BOP_collinear(vertex1,vertex2,vertex3)) {
437                                                         // collinear triangle 
438                                                         face->setTAG(PHANTOM);
439                                                 }
440 #endif
441                                         }
442                                 }
443                         }
444                 }
445         }
446 }
447
448 /**
449  * Obtains the points of the segment created from the intersection between faceA and planeB.
450  * @param mesh mesh that contains the faces, edges and vertices
451  * @param faceA intersected face
452  * @param sA segment of the intersection between  faceA and planeB
453  * @param planeB intersected plane
454  * @param points array of points where the new points are saved
455  * @param faces array of relative face index to the points
456  * @param size size of arrays points and faces
457  * @param faceValue relative face index of new points
458  */
459 void BOP_getPoints(BOP_Mesh*    mesh, 
460                                    BOP_Face*    faceA, 
461                                    BOP_Segment& sA, 
462                                    MT_Plane3    planeB, 
463                                    MT_Point3*   points, 
464                                    unsigned int*         faces, 
465                                    unsigned int&         size, 
466                                    unsigned int          faceValue) 
467 {
468         MT_Point3 p1,p2;  
469   
470         if (BOP_Segment::isDefined(sA.m_cfg1)) {
471                 if (BOP_Segment::isEdge(sA.m_cfg1)) {
472                         // the new point becomes of split faceA edge 
473                         p1 = BOP_splitEdge(planeB,mesh,faceA,BOP_Segment::getEdge(sA.m_cfg1));
474                 }
475                 else if (BOP_Segment::isVertex(sA.m_cfg1)) {
476                         // the new point becomes of vertex faceA
477                         p1 =  mesh->getVertex(BOP_Segment::getVertex(sA.m_v1))->getPoint();
478                 }
479
480                 if (BOP_Segment::isDefined(sA.m_cfg2)) {
481                         if (BOP_Segment::isEdge(sA.m_cfg2)) {
482                                 p2 = BOP_splitEdge(planeB,mesh,faceA,BOP_Segment::getEdge(sA.m_cfg2));
483                         }
484                         else if (BOP_Segment::isVertex(sA.m_cfg2)) { 
485                                 p2 =  mesh->getVertex(BOP_Segment::getVertex(sA.m_v2))->getPoint();
486                         }
487                         points[size] = p1;
488                         points[size+1] = p2;
489                         faces[size] = faceValue;
490                         faces[size+1] = faceValue;
491                         size += 2;
492                 }
493         
494                 else {
495                         points[size] = p1;
496                         faces[size] = faceValue;
497                         size++;
498                 }
499         }
500 }
501
502 /**
503  * Sorts the colinear points and relative face indices.
504  * @param points array of points where the new points are saved
505  * @param faces array of relative face index to the points
506  * @param size size of arrays points and faces
507  * @param invertA indicates if points of same relative face had been exchanged
508  */
509 void BOP_mergeSort(MT_Point3 *points, unsigned int *face, unsigned int &size, bool &invertA, bool &invertB) {
510         MT_Point3 sortedPoints[4];
511         unsigned int sortedFaces[4], position[4];
512         unsigned int i;
513         if (size == 2) {
514
515                 // Trivial case, only test the merge ...
516                 if (BOP_comp(0,points[0].distance(points[1]))==0) {
517                         face[0] = 3;
518                         size--;
519                 }
520         }
521         else {
522                 // size is 3 or 4
523                 // Get segment extreme points
524                 MT_Scalar maxDistance = -1;
525                 for(i=0;i<size-1;i++){
526                         for(unsigned int j=i+1;j<size;j++){
527                                 MT_Scalar distance = points[i].distance(points[j]);
528                                 if (distance > maxDistance){
529                                         maxDistance = distance;
530                                         position[0] = i;
531                                         position[size-1] = j;
532                                 }
533                         }
534                 }
535
536                 // Get segment inner points
537                 position[1] = position[2] = size;
538                 for(i=0;i<size;i++){
539                         if ((i != position[0]) && (i != position[size-1])){
540                                 if (position[1] == size) position[1] = i;
541                                 else position[2] = i;
542                         }
543                 }
544
545                 // Get inner points
546                 if (position[2] < size) {
547                         MT_Scalar d1 = points[position[1]].distance(points[position[0]]);
548                         MT_Scalar d2 = points[position[2]].distance(points[position[0]]);
549                         if (d1 > d2) {
550                                 unsigned int aux = position[1];
551                                 position[1] = position[2];
552                                 position[2] = aux;
553                         }
554                 }
555
556                 // Sort data
557                 for(i=0;i<size;i++) {
558                         sortedPoints[i] = points[position[i]];
559                         sortedFaces[i] = face[position[i]];
560                 }
561
562                 invertA = false;
563                 invertB = false;
564                 if (face[1] == 1) {
565
566                         // invertA¿?
567                         for(i=0;i<size;i++) {
568                                 if (position[i] == 1) {
569                                         invertA = true;
570                                         break;
571                                 }
572                                 else if (position[i] == 0) break;
573                         }
574
575                         // invertB¿?
576                         if (size == 4) {
577                                 for(i=0;i<size;i++) {
578                                         if (position[i] == 3) {
579                                                 invertB = true;
580                                                 break;
581                                         }
582                                         else if (position[i] == 2) break;
583                                 }
584                         }
585                 }
586                 else if (face[1] == 2) {
587                         // invertB¿?
588                         for(i=0;i<size;i++) {
589                                 if (position[i] == 2) {
590                                         invertB = true;
591                                         break;
592                                 }
593                                 else if (position[i] == 1) break;
594                         }
595                 }
596
597
598                 // Merge data
599                 MT_Scalar d1 = sortedPoints[1].distance(sortedPoints[0]);
600                 MT_Scalar d2 = sortedPoints[1].distance(sortedPoints[2]);
601                 if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[0]) {
602                         if (BOP_comp(0,d2)==0 && sortedFaces[1] != sortedFaces[2])  {
603                                 if (d1 < d2) {
604                                         // merge 0 and 1
605                                         sortedFaces[0] = 3;
606                                         for(i = 1; i<size-1;i++) {
607                                                 sortedPoints[i] = sortedPoints[i+1];
608                                                 sortedFaces[i] = sortedFaces[i+1];
609                                         }
610                                         size--;
611                                         if (size == 3) {
612                                                 // merge 1 and 2 ???
613                                                 d1 = sortedPoints[1].distance(sortedPoints[2]);
614                                                 if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[2])  {
615                                                         // merge!
616                                                         sortedFaces[1] = 3;
617                                                         size--;
618                                                 }
619                                         }
620                                 }
621                                 else {
622                                         // merge 1 and 2
623                                         sortedFaces[1] = 3;
624                                         for(i = 2; i<size-1;i++) {
625                                                 sortedPoints[i] = sortedPoints[i+1];
626                                                 sortedFaces[i] = sortedFaces[i+1];
627                                         }
628                                         size--;
629                                 }        
630                         }
631                         else {
632                                 // merge 0 and 1
633                                 sortedFaces[0] = 3;
634                                 for(i = 1; i<size-1;i++) {
635                                         sortedPoints[i] = sortedPoints[i+1];
636                                         sortedFaces[i] = sortedFaces[i+1];
637                                 }
638                                 size--;
639                                 if (size == 3) {
640                                         // merge 1 i 2 ???
641                                         d1 = sortedPoints[1].distance(sortedPoints[2]);
642                                         if (BOP_comp(0,d1)==0 && sortedFaces[1] != sortedFaces[2])  {
643                                                 // merge!
644                                                 sortedFaces[1] = 3;
645                                                 size--;
646                                         }
647                                 }
648                         }     
649                 }
650                 else {
651                         if (BOP_comp(0,d2)==0 && sortedFaces[1] != sortedFaces[2])  {
652                                 // merge 1 and 2
653                                 sortedFaces[1] = 3;
654                                 for(i = 2; i<size-1;i++) {
655                                         sortedPoints[i] = sortedPoints[i+1];
656                                         sortedFaces[i] = sortedFaces[i+1];
657                                 }
658                                 size--;
659                         }
660                         else if (size == 4) {
661                                 d1 = sortedPoints[2].distance(sortedPoints[3]);
662                                 if (BOP_comp(0,d1)==0 && sortedFaces[2] != sortedFaces[3])  {
663                                         // merge 2 and 3
664                                         sortedFaces[2] = 3;
665                                         size--;
666                                 }
667                         }
668                 }
669     
670                 // Merge initial points ...
671                 for(i=0;i<size;i++) {
672                         points[i] = sortedPoints[i];
673                         face[i] = sortedFaces[i];
674                 }
675
676         }
677 }
678
679
680 /**
681  * Computes the x-segment of two segments (the shared interval). The segments needs to have sA.m_cfg1 > 0 && sB.m_cfg1 > 0 .
682  * @param mesh mesh that contains the faces, edges and vertices
683  * @param faceA face of object A
684  * @param faceB face of object B
685  * @param sA segment of intersection between faceA and planeB
686  * @param sB segment of intersection between faceB and planeA
687  * @param invert indicates if faceA has priority over faceB
688  * @param segmemts array of the output x-segments
689  */
690  void BOP_createXS(BOP_Mesh*    mesh, 
691          BOP_Face*    faceA, 
692          BOP_Face*    faceB, 
693          BOP_Segment  sA, 
694          BOP_Segment  sB, 
695          bool         invert, 
696          BOP_Segment* segments) {    
697          BOP_createXS(mesh, faceA, faceB, faceA->getPlane(), faceB->getPlane(),
698                  sA, sB, invert, segments);
699  }
700
701 /**
702  * Computes the x-segment of two segments (the shared interval). The segments needs to have sA.m_cfg1 > 0 && sB.m_cfg1 > 0 .
703  * @param mesh mesh that contains the faces, edges and vertices
704  * @param faceA face of object A
705  * @param faceB face of object B
706  * @param planeA plane of faceA
707  * @param planeB plane of faceB
708  * @param sA segment of intersection between faceA and planeB
709  * @param sB segment of intersection between faceB and planeA
710  * @param invert indicates if faceA has priority over faceB
711  * @param segmemts array of the output x-segments
712  */
713 void BOP_createXS(BOP_Mesh*    mesh, 
714                                   BOP_Face*    faceA, 
715                                   BOP_Face*    faceB, 
716                                   MT_Plane3    planeA, 
717                                   MT_Plane3    planeB, 
718                                   BOP_Segment  sA, 
719                                   BOP_Segment  sB, 
720                                   bool         invert, 
721                                   BOP_Segment* segments)
722 {    
723         MT_Point3 points[4];  // points of the segments
724         unsigned int face[4]; // relative face indexs (1 => faceA, 2 => faceB)
725         unsigned int size = 0;  // size of points and relative face indexs
726   
727         BOP_getPoints(mesh, faceA, sA, planeB, points, face, size, 1);
728         BOP_getPoints(mesh, faceB, sB, planeA, points, face, size, 2);
729
730         bool invertA = false;
731         bool invertB = false;
732         BOP_mergeSort(points,face,size,invertA,invertB);
733
734         if (invertA) sA.invert();
735         if (invertB) sB.invert();
736         
737         // Compute the configuration label
738         unsigned int label = 0;
739         for(unsigned int i =0; i < size; i++) {
740                 label = face[i]+label*10;    
741         }
742
743         if (size == 1) {
744                 // Two coincident points
745                 segments[0].m_cfg1 = sA.m_cfg1;
746                 segments[1].m_cfg1 = sB.m_cfg1;
747                 
748                 segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
749                                                                                           sA.m_v1, sB.m_v1, invert);
750                 segments[1].m_v1 = segments[0].m_v1;
751                 segments[0].m_cfg2 = segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
752         }
753         else if (size == 2) {
754                 switch(label) {
755                 // Two non-coincident points
756                 case sA_sB:
757                 case sB_sA:
758                         segments[0].m_cfg1 = 
759                         segments[1].m_cfg1 = 
760                         segments[0].m_cfg2 = 
761                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
762                         break;
763       
764                 // Two coincident points and one non-coincident of sA
765                 case sA_sX:
766                         segments[0].m_cfg1 = sA.m_cfg2;
767                         segments[1].m_cfg1 = sB.m_cfg1;
768                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg1,
769                                                                                                   sA.m_v2, sB.m_v1, invert);
770                         segments[1].m_v1 = segments[0].m_v1;
771                         
772                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
773                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
774                         break;
775                 case sX_sA:
776                         segments[0].m_cfg1 = sA.m_cfg1;
777                         segments[1].m_cfg1 = sB.m_cfg1;
778                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
779                                                                                                   sA.m_v1, sB.m_v1, invert);
780                         segments[1].m_v1 = segments[0].m_v1;
781                         
782                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
783                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
784                         break;
785       
786                 // Two coincident points and one non-coincident of sB
787                 case sB_sX:
788                         segments[0].m_cfg1 = sA.m_cfg1;
789                         segments[1].m_cfg1 = sB.m_cfg2;
790                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg1, sB.m_cfg2, 
791                                                                                                   sA.m_v1, sB.m_v2, invert);
792                         segments[1].m_v1 = segments[0].m_v1;
793                         
794                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
795                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
796                         break;
797                 case sX_sB:
798                         segments[0].m_cfg1 = sA.m_cfg1;
799                         segments[1].m_cfg1 = sB.m_cfg1;
800                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 
801                                                                                                   sA.m_v1, sB.m_v1, invert);
802                         segments[1].m_v1 = segments[0].m_v1;
803                 
804                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
805                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
806                         break;
807       
808                 // coincident points 2-2
809                 case sX_sX:
810                         segments[0].m_cfg1 = sA.m_cfg1;
811                         segments[1].m_cfg1 = sB.m_cfg1;          
812                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 
813                                                                                                   sA.m_v1, sB.m_v1, invert);
814                         segments[1].m_v1 = segments[0].m_v1;
815                         
816                         segments[0].m_cfg2 = sA.m_cfg2;
817                         segments[1].m_cfg2 = sB.m_cfg2;          
818                         segments[0].m_v2 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg2, 
819                                                                                                   sA.m_v2, sB.m_v2, invert);
820                         segments[1].m_v2 = segments[0].m_v2;
821                         break;
822                 
823                 default:
824                         break; 
825                 }
826         }
827         else if (size == 3) {
828                 switch(label) {
829                 case sA_sA_sB:
830                 case sB_sA_sA:
831                 case sA_sB_sB:
832                 case sB_sB_sA:
833                         segments[0].m_cfg1 = 
834                         segments[1].m_cfg1 = 
835                         segments[0].m_cfg2 = 
836                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
837                         break;
838       
839                 case sA_sB_sA:
840                         segments[1].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
841                         segments[1].m_cfg1 = sB.m_cfg1;
842                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
843                         segments[0].m_cfg1 = sA.getConfig();
844                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
845                         segments[0].m_v1 = segments[1].m_v1;
846                         break;
847       
848                 case sB_sA_sB:
849                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
850                         segments[0].m_cfg1 = sA.m_cfg1;
851                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
852                         segments[1].m_cfg1 = sB.getConfig();
853                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
854                         segments[1].m_v1 = segments[0].m_v1;
855                         break;
856       
857                 case sA_sX_sB:
858                         segments[0].m_cfg1 = sA.m_cfg2;
859                         segments[1].m_cfg1 = sB.m_cfg1;          
860                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg1, 
861                                                                                                   sA.m_v2, sB.m_v1, invert);
862                         segments[1].m_v1 = segments[0].m_v1;
863                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
864                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
865                         break;
866     
867                 case sB_sX_sA:
868                         segments[0].m_cfg1 = sA.m_cfg1;
869                         segments[1].m_cfg1 = sB.m_cfg2;          
870                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg1, sB.m_cfg2, 
871                                                                                                   sA.m_v1, sB.m_v2, invert);
872                         segments[1].m_v1 = segments[0].m_v1;
873                         segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
874                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
875                         break;
876       
877                 case sX_sA_sB:
878                         segments[0].m_cfg1 = sA.m_cfg1;
879                         segments[1].m_cfg1 = sB.m_cfg1;          
880                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
881                                                                                                   sA.m_v1, sB.m_v1, invert);
882                         segments[1].m_v1 = segments[0].m_v1;
883                         
884                         segments[0].m_cfg2 = sA.m_cfg2;
885                         segments[1].m_cfg2 = sB.getConfig();
886                         segments[0].m_v2 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sA.m_v2);
887                         segments[1].m_v2 = segments[0].m_v2;
888                         break;
889       
890                 case sX_sB_sA:
891                         segments[0].m_cfg1 = sA.m_cfg1;
892                         segments[1].m_cfg1 = sB.m_cfg1;          
893                         segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
894                                                                                                   sA.m_v1, sB.m_v1, invert);
895                         segments[1].m_v1 = segments[0].m_v1;
896                         
897                         segments[0].m_cfg2 = sA.getConfig();
898                         segments[1].m_cfg2 = sB.m_cfg2;
899                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg2,sB.m_v2);
900                         segments[1].m_v2 = segments[0].m_v2;
901                         break;
902       
903                 case sA_sB_sX:
904                         segments[0].m_cfg1 = sA.getConfig();
905                         segments[1].m_cfg1 = sB.m_cfg1;
906                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
907                         segments[1].m_v1 = segments[0].m_v1;
908                         
909                         segments[0].m_cfg2 = sA.m_cfg2;
910                         segments[1].m_cfg2 = sB.m_cfg2;          
911                         segments[0].m_v2 = BOP_getVertexIndex(mesh, points[2], sA.m_cfg2, sB.m_cfg2, 
912                                                                                                   sA.m_v2, sB.m_v2, invert);
913                         segments[1].m_v2 = segments[0].m_v2;
914                         break;
915
916                 case sB_sA_sX:
917                         segments[0].m_cfg1 = sA.m_cfg1;
918                         segments[1].m_cfg1 = sB.getConfig();
919                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
920                         segments[1].m_v1 = segments[0].m_v1;
921                         
922                         segments[0].m_cfg2 = sA.m_cfg2;
923                         segments[1].m_cfg2 = sB.m_cfg2;          
924                         segments[0].m_v2 = BOP_getVertexIndex(mesh, points[2], sA.m_cfg2, sB.m_cfg2,
925                                                                                                   sA.m_v2, sB.m_v2, invert);
926                         segments[1].m_v2 = segments[0].m_v2;
927                         break;
928       
929                 default:
930                         break; 
931                 }
932         }
933         else {
934                 // 4!
935                 switch(label) {
936                 case sA_sA_sB_sB:
937                 case sB_sB_sA_sA:
938                         segments[0].m_cfg1 = 
939                         segments[1].m_cfg1 = 
940                         segments[0].m_cfg2 = 
941                         segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
942                         break;
943       
944                 case sA_sB_sA_sB:
945                         segments[0].m_cfg1 = sA.getConfig();
946                         segments[1].m_cfg1 = sB.m_cfg1;
947                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
948                         segments[1].m_v1 = segments[0].m_v1;
949                         
950                         segments[0].m_cfg2 = sA.m_cfg2;
951                         segments[1].m_cfg2 = sB.getConfig();
952                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sA.m_cfg2,sA.m_v2);
953                         segments[1].m_v2 = segments[0].m_v2;
954                         break;          
955       
956                 case sB_sA_sB_sA:
957                         segments[0].m_cfg1 = sA.m_cfg1;
958                         segments[1].m_cfg1 = sB.getConfig();
959                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
960                         segments[1].m_v1 = segments[0].m_v1;
961                         
962                         segments[0].m_cfg2 = sA.getConfig();
963                         segments[1].m_cfg2 = sB.m_cfg2;
964                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sB.m_cfg2,sB.m_v2);
965                         segments[1].m_v2 = segments[0].m_v2;
966                         break;          
967       
968                 case sA_sB_sB_sA:
969                         segments[0].m_cfg1 = sA.getConfig();
970                         segments[1].m_cfg1 = sB.m_cfg1;
971                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
972                         segments[1].m_v1 = segments[0].m_v1;
973                         
974                         segments[0].m_cfg2 = segments[0].m_cfg1;
975                         segments[1].m_cfg2 = sB.m_cfg2;
976                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sB.m_cfg2,sB.m_v2);
977                         segments[1].m_v2 = segments[0].m_v2;
978                         break;
979       
980                 case sB_sA_sA_sB:
981                         segments[0].m_cfg1 = sA.m_cfg1;
982                         segments[1].m_cfg1 = sB.getConfig();
983                         segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
984                         segments[1].m_v1 = segments[0].m_v1;
985                         
986                         segments[0].m_cfg2 = sA.m_cfg2;
987                         segments[1].m_cfg2 = segments[1].m_cfg1;
988                         segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sA.m_cfg2,sA.m_v2);
989                         segments[1].m_v2 = segments[0].m_v2;
990                         break;
991       
992                 default:
993                         break; 
994                 }
995         }
996         
997         segments[0].sort();
998         segments[1].sort();
999 }
1000
1001 /**
1002  * Computes the vertex index of a point.
1003  * @param mesh mesh that contains the faces, edges and vertices
1004  * @param point input point
1005  * @param cfgA configuration of point on faceA
1006  * @param cfgB configuration of point on faceB
1007  * @param vA vertex index of point on faceA
1008  * @param vB vertex index of point on faceB
1009  * @param invert indicates if vA has priority over vB
1010  * @return final vertex index in the mesh
1011  */
1012 BOP_Index BOP_getVertexIndex(BOP_Mesh* mesh, 
1013                                            MT_Point3 point, 
1014                                            unsigned int       cfgA, 
1015                                            unsigned int       cfgB, 
1016                                            BOP_Index       vA, 
1017                                            BOP_Index       vB, 
1018                                            bool      invert)
1019 {
1020         if (BOP_Segment::isVertex(cfgA)) { // exists vertex index on A
1021                 if (BOP_Segment::isVertex(cfgB)) { // exists vertex index on B
1022                         // unify vertex indexs
1023                         if (invert)
1024                                 return mesh->replaceVertexIndex(vA,vB);
1025                         else 
1026                                 return mesh->replaceVertexIndex(vB,vA);
1027                 }
1028                 else
1029                         return vA;
1030         }
1031         else {// does not exist vertex index on A
1032                 if (BOP_Segment::isVertex(cfgB)) // exists vertex index on B
1033                         return vB;      
1034                 else {// does not exist vertex index on B
1035                         return mesh->addVertex(point);
1036                 }
1037         } 
1038 }
1039
1040 /**
1041  * Computes the vertex index of a point.
1042  * @param mesh mesh that contains the faces, edges and vertices
1043  * @param cfg configuration of point
1044  * @param v vertex index of point
1045  * @return final vertex index in the mesh
1046  */
1047 BOP_Index BOP_getVertexIndex(BOP_Mesh *mesh, MT_Point3 point, unsigned int cfg, BOP_Index v)
1048 {
1049         if (BOP_Segment::isVertex(cfg)) // vertex existent
1050                 return v;       
1051         else {
1052                 return mesh->addVertex(point);
1053         }
1054 }
1055
1056 /******************************************************************************/
1057 /*** TRIANGULATE                                                            ***/
1058 /******************************************************************************/
1059
1060 /**
1061  * Triangulates the input face according to the specified segment.
1062  * @param mesh mesh that contains the faces, edges and vertices
1063  * @param faces set of faces that contains the original face and the new triangulated faces
1064  * @param face face to be triangulated
1065  * @param s segment used to triangulate face
1066  */
1067 void triangulate(BOP_Mesh *mesh, BOP_Faces *faces, BOP_Face *face, BOP_Segment s)
1068 {
1069         if (BOP_Segment::isUndefined(s.m_cfg1)) {
1070                 // Nothing to do
1071         }
1072         else if (BOP_Segment::isVertex(s.m_cfg1)) {
1073                 // VERTEX(v1) + VERTEX(v2) => nothing to do
1074         }
1075         else if (BOP_Segment::isEdge(s.m_cfg1)) {
1076                 if (BOP_Segment::isVertex(s.m_cfg2) || BOP_Segment::isUndefined(s.m_cfg2)) {
1077                         // EDGE(v1) + VERTEX(v2)
1078                         BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
1079                         BOP_triangulateA(mesh,faces,face,s.m_v1,BOP_Segment::getEdge(s.m_cfg1));
1080                         BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
1081                         if (opposite != NULL) {
1082                           unsigned int e;
1083                           opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
1084                           BOP_triangulateA(mesh, faces, opposite, s.m_v1, e);
1085                         }
1086                 }
1087                 else {
1088                         //  EDGE(v1) + EDGE(v2)
1089                         if (BOP_Segment::getEdge(s.m_cfg1) == BOP_Segment::getEdge(s.m_cfg2)) {
1090                                  // EDGE(v1) == EDGE(v2)
1091                                 BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
1092                                 BOP_triangulateD(mesh, faces, face, s.m_v1, s.m_v2, 
1093                                                                  BOP_Segment::getEdge(s.m_cfg1)); 
1094                                 BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
1095                                 if (opposite != NULL) {
1096                                   unsigned int e;
1097                                   opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
1098                                   BOP_triangulateD(mesh, faces, opposite, s.m_v1, s.m_v2, e);
1099                                 }
1100                 }
1101                         else { // EDGE(v1) != EDGE(v2)
1102                                 BOP_Edge *edge1 = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
1103                                 BOP_Edge *edge2 = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg2));
1104                                 BOP_triangulateE(mesh, faces, face, s.m_v1, s.m_v2,
1105                                                                  BOP_Segment::getEdge(s.m_cfg1),
1106                                                                  BOP_Segment::getEdge(s.m_cfg2));
1107                                 BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge1);
1108                                 if (opposite != NULL) {
1109                                   unsigned int e;
1110                                   opposite->getEdgeIndex(edge1->getVertex1(), edge1->getVertex2(),e);
1111                                   BOP_triangulateA(mesh, faces, opposite, s.m_v1, e);
1112                                 }
1113                                 opposite = BOP_getOppositeFace(mesh,faces,face,edge2);
1114                                 if (opposite != NULL) {
1115                                   unsigned int e;
1116                                   opposite->getEdgeIndex(edge2->getVertex1(), edge2->getVertex2(),e);
1117                                   BOP_triangulateA(mesh, faces, opposite, s.m_v2, e);
1118                                 }
1119                         }
1120                 }
1121         }
1122         else if (BOP_Segment::isIn(s.m_cfg1)) {
1123                 if (BOP_Segment::isVertex(s.m_cfg2) || BOP_Segment::isUndefined(s.m_cfg2)) {
1124                         // IN(v1) + VERTEX(v2)
1125                         BOP_triangulateB(mesh,faces,face,s.m_v1);
1126                 }
1127                 else if (BOP_Segment::isEdge(s.m_cfg2)) {
1128                         // IN(v1) + EDGE(v2)
1129                         BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg2));
1130                         BOP_triangulateF(mesh,faces,face,s.m_v1,s.m_v2,BOP_Segment::getEdge(s.m_cfg2));
1131                         BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
1132                         if (opposite != NULL) {
1133                           unsigned int e;
1134                           opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
1135                           BOP_triangulateA(mesh, faces, opposite, s.m_v2, e);
1136                         }
1137                 }
1138                 else // IN(v1) + IN(v2)
1139                         BOP_triangulateC(mesh,faces,face,s.m_v1,s.m_v2);
1140         }
1141 }
1142
1143 /**
1144  * Returns if a face is in the set of faces.
1145  * @param faces set of faces
1146  * @param face face to be searched
1147  * @return if the face is inside faces
1148  */
1149 bool BOP_containsFace(BOP_Faces *faces, BOP_Face *face)
1150 {
1151   const BOP_IT_Faces facesEnd = faces->end();
1152         for(BOP_IT_Faces it=faces->begin();it!=facesEnd;it++)
1153         {
1154                 if (*it == face)
1155                 return true;
1156         }
1157         
1158         return false;
1159 }
1160
1161 /**
1162  * Returns the first face of faces that shares the input edge of face.
1163  * @param mesh mesh that contains the faces, edges and vertices
1164  * @param faces set of faces
1165  * @param face input face
1166  * @param edge face's edge
1167  * @return first face that shares the edge of input face
1168  */
1169 BOP_Face *BOP_getOppositeFace(BOP_Mesh*  mesh, 
1170                                                           BOP_Faces* faces, 
1171                                                           BOP_Face*  face,
1172                                                           BOP_Edge*  edge)
1173 {
1174         if (edge == NULL)
1175           return NULL;
1176   
1177         BOP_Indexs auxfaces = edge->getFaces();
1178         const BOP_IT_Indexs auxfacesEnd = auxfaces.end();
1179         for(BOP_IT_Indexs it = auxfaces.begin(); it != auxfacesEnd; it++) {
1180                 BOP_Face *auxface = mesh->getFace(*it);
1181                 if ((auxface != face) && (auxface->getTAG()!=BROKEN) && 
1182                         BOP_containsFace(faces,auxface)) {
1183                         return auxface;
1184                 }
1185         }        
1186   
1187         return NULL;
1188 }
1189
1190 /******************************************************************************/ 
1191 /***  OVERLAPPING                                                           ***/
1192 /******************************************************************************/ 
1193
1194 /**
1195  * Removes faces from facesB that are overlapped with anyone from facesA.
1196  * @param mesh mesh that contains the faces, edges and vertices
1197  * @param facesA set of faces from object A
1198  * @param facesB set of faces from object B
1199  */
1200 void BOP_removeOverlappedFaces(BOP_Mesh *mesh,  BOP_Faces *facesA,  BOP_Faces *facesB)
1201 {
1202         for(unsigned int i=0;i<facesA->size();i++) {
1203                 BOP_Face *faceI = (*facesA)[i];       
1204                 if (faceI->getTAG()==BROKEN) continue;
1205                 bool overlapped = false;
1206                 MT_Point3 p1 = mesh->getVertex(faceI->getVertex(0))->getPoint();
1207                 MT_Point3 p2 = mesh->getVertex(faceI->getVertex(1))->getPoint();
1208                 MT_Point3 p3 = mesh->getVertex(faceI->getVertex(2))->getPoint();
1209                 for(unsigned int j=0;j<facesB->size();) {
1210                         BOP_Face *faceJ = (*facesB)[j];
1211                         if (faceJ->getTAG()!=BROKEN) {
1212                           MT_Plane3 planeJ = faceJ->getPlane();
1213                           if (BOP_containsPoint(planeJ,p1) && BOP_containsPoint(planeJ,p2) 
1214                               && BOP_containsPoint(planeJ,p3)) {
1215                             MT_Point3 q1 = mesh->getVertex(faceJ->getVertex(0))->getPoint();
1216                             MT_Point3 q2 = mesh->getVertex(faceJ->getVertex(1))->getPoint();
1217                             MT_Point3 q3 = mesh->getVertex(faceJ->getVertex(2))->getPoint();
1218                             if (BOP_overlap(MT_Vector3(planeJ.x(),planeJ.y(),planeJ.z()),
1219                                             p1,p2,p3,q1,q2,q3)) {
1220                               facesB->erase(facesB->begin()+j,facesB->begin()+(j+1));
1221                               faceJ->setTAG(BROKEN);
1222                               overlapped = true;
1223                             }
1224                             else j++;
1225                           }
1226                           else j++;
1227                         }else j++;
1228                 }
1229                 if (overlapped) faceI->setTAG(OVERLAPPED);
1230         }
1231 }
1232
1233 /**
1234  * Computes if triangle p1,p2,p3 is overlapped with triangle q1,q2,q3.
1235  * @param normal normal of the triangle p1,p2,p3
1236  * @param p1 point of first triangle
1237  * @param p2 point of first triangle
1238  * @param p3 point of first triangle
1239  * @param q1 point of second triangle
1240  * @param q2 point of second triangle
1241  * @param q3 point of second triangle
1242  * @return if there is overlapping between both triangles
1243  */
1244 bool BOP_overlap(MT_Vector3 normal, MT_Point3 p1, MT_Point3 p2, MT_Point3 p3, 
1245                                   MT_Point3 q1, MT_Point3 q2, MT_Point3 q3)
1246 {
1247         MT_Vector3 p1p2 = p2-p1;    
1248         MT_Plane3 plane1(p1p2.cross(normal),p1);
1249         
1250         MT_Vector3 p2p3 = p3-p2;
1251         MT_Plane3 plane2(p2p3.cross(normal),p2);
1252         
1253         MT_Vector3 p3p1 = p1-p3;    
1254         MT_Plane3 plane3(p3p1.cross(normal),p3);
1255   
1256         BOP_TAG tag1 = BOP_createTAG(BOP_classify(q1,plane1));
1257         BOP_TAG tag2 = BOP_createTAG(BOP_classify(q1,plane2));
1258         BOP_TAG tag3 = BOP_createTAG(BOP_classify(q1,plane3));
1259         BOP_TAG tagQ1 = BOP_createTAG(tag1,tag2,tag3);   
1260         if (tagQ1 == IN_IN_IN) return true;    
1261   
1262         tag1 = BOP_createTAG(BOP_classify(q2,plane1));
1263         tag2 = BOP_createTAG(BOP_classify(q2,plane2));
1264         tag3 = BOP_createTAG(BOP_classify(q2,plane3));
1265         BOP_TAG tagQ2 = BOP_createTAG(tag1,tag2,tag3);
1266         if (tagQ2 == IN_IN_IN) return true;    
1267         
1268         tag1 = BOP_createTAG(BOP_classify(q3,plane1));
1269         tag2 = BOP_createTAG(BOP_classify(q3,plane2));
1270         tag3 = BOP_createTAG(BOP_classify(q3,plane3));
1271         BOP_TAG tagQ3 = BOP_createTAG(tag1,tag2,tag3);
1272         if (tagQ3 == IN_IN_IN) return true;    
1273   
1274         if ((tagQ1 & OUT_OUT_OUT) == 0 && (tagQ2 & OUT_OUT_OUT) == 0 && 
1275                 (tagQ3 & OUT_OUT_OUT) == 0) return true;
1276         else return false;
1277 }