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