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