Tools:
[blender.git] / intern / boolop / intern / BOP_Merge.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_Merge.h"
35
36
37 #ifdef _MSC_VER
38 #if _MSC_VER < 1300
39 #include <list>
40 #endif
41 #endif
42
43 /**
44  * SINGLETON (use method BOP_Merge.getInstance).
45  */
46 BOP_Merge BOP_Merge::SINGLETON;
47
48 /**
49  * Simplifies a mesh, merging its faces.
50  * @param m mesh
51  * @param v index of the first mergeable vertex (can be removed by merge) 
52  */
53 void BOP_Merge::mergeFaces(BOP_Mesh *m, BOP_Index v)
54 {
55         m_mesh = m;
56         m_firstVertex = v;
57
58         bool cont = false;
59
60         // Merge faces
61         mergeFaces();
62
63         /*
64          * HACK: somehow triangular faces are being created with two vertices the
65          * same.  If it's happening in BOP_Mesh::replaceVertexIndex() we should
66          * be catching it, so either it's not happening there or we aren't
67          * catching it (duh).  Until we figure this out, this hack cleans things.
68          * 
69          * Test for any invalid faces: if any two vertices are the same of a
70          * triangle, the face is broken.  Further, I don't believe it's possible
71          * to have any quads at this point, so if we find one send a message
72          * to stdout.
73          */
74
75         BOP_Faces faces = m_mesh->getFaces();
76         const BOP_IT_Faces ifacesIEnd = (faces.end());
77         for(BOP_IT_Faces faceI=faces.begin();faceI!=ifacesIEnd;faceI++) {
78                 if ((*faceI)->getTAG() != BROKEN ) {
79                         BOP_Index i1 = (*faceI)->getVertex(0);
80                         BOP_Index i2 = (*faceI)->getVertex(1);
81                         BOP_Index i3 = (*faceI)->getVertex(2);
82                         if ( (*faceI)->size() == 4)
83                                 cout << "BOP_Merge::mergeFaces found a quad: this is an error" << endl;
84                         if (i1 == i2 || i2 == i3 || i3 == i1 )
85                                 (*faceI)->setTAG(BROKEN);
86                 }
87         }
88
89         do {
90                 // Add quads ...
91                 cont = createQuads();
92                 if (cont) {
93                         // ... and merge new faces
94                         cont = mergeFaces();
95                 }
96                 // ... until the merge is not succesful
97         } while(cont);
98 }
99
100 /**
101  * Simplifies a mesh, merging its faces.
102  */
103 bool BOP_Merge::mergeFaces()
104 {
105         BOP_Indexs mergeVertices;
106         BOP_Vertexs vertices = m_mesh->getVertexs();
107         BOP_IT_Vertexs v = vertices.begin();
108         const BOP_IT_Vertexs verticesEnd = vertices.end();
109
110         // Advance to first mergeable vertex
111         advance(v,m_firstVertex);
112         BOP_Index pos = m_firstVertex;
113
114         // Add unbroken vertices to the list
115         while(v!=verticesEnd) {
116                 if ((*v)->getTAG() != BROKEN) mergeVertices.push_back(pos);
117                 v++;pos++;
118         }
119
120         // Merge faces with that vertices
121         return mergeFaces(mergeVertices);
122 }
123
124
125 /**
126  * Simplifies a mesh, merging the faces with the specified vertices.
127  * @param mergeVertices vertices to test
128  * @return true if a face merge was performed
129  */
130 bool BOP_Merge::mergeFaces(BOP_Indexs &mergeVertices)
131 {
132         // Check size > 0!
133         if (mergeVertices.size() == 0) return false;
134
135         // New faces added by merge
136         BOP_Faces newFaces;
137
138         // Old faces removed by merge
139         BOP_Faces oldFaces;
140
141         // Get the first vertex index and add it to 
142         // the current pending vertices to merge
143         BOP_Index v = mergeVertices[0];
144         BOP_Indexs pendingVertices;
145         pendingVertices.push_back(v);
146
147         // Get faces with index v that come from the same original face
148         BOP_LFaces facesByOriginalFace;
149         getFaces(facesByOriginalFace,v);
150
151         bool merged = true;
152
153         // Check it has any unbroken face
154         if (facesByOriginalFace.size()==0) {
155                 // v has not any unbroken face (so it's a new BROKEN vertex)
156                 (m_mesh->getVertex(v))->setTAG(BROKEN);
157                 merged = false;
158         }
159
160         // Merge vertex faces   
161         const BOP_IT_LFaces facesEnd = facesByOriginalFace.end();
162         
163         for(BOP_IT_LFaces facesByOriginalFaceX = facesByOriginalFace.begin();
164                 (facesByOriginalFaceX != facesEnd)&&merged;
165                 facesByOriginalFaceX++) {               
166                         merged = mergeFaces((*facesByOriginalFaceX),oldFaces,newFaces,pendingVertices,v);
167         }
168
169         // Check if the are some pendingVertices to merge
170         if (pendingVertices.size() > 1 && merged) {
171                 // There are pending vertices that we need to merge in order to merge v ...
172                 for(unsigned int i=1;i<pendingVertices.size() && merged;i++) 
173                         merged = mergeFaces(oldFaces,newFaces,pendingVertices,pendingVertices[i]);
174         }
175
176         // If merge was succesful ...
177         if (merged) {
178                 // Set old faces to BROKEN...
179           const BOP_IT_Faces oldFacesEnd = oldFaces.end();
180                 for(BOP_IT_Faces face=oldFaces.begin();face!=oldFacesEnd;face++) 
181                         (*face)->setTAG(BROKEN);
182
183                 // ... and add merged faces (that are the new merged faces without pending vertices)
184                 const BOP_IT_Faces newFacesEnd = newFaces.end();
185                 for(BOP_IT_Faces newFace=newFaces.begin();newFace!=newFacesEnd;newFace++) {
186                         m_mesh->addFace(*newFace);
187                         // Also, add new face vertices to the queue of vertices to merge if they weren't
188                         for(BOP_Index i = 0;i<(*newFace)->size();i++) {
189                                 BOP_Index vertexIndex = (*newFace)->getVertex(i);
190                                 if (vertexIndex >= m_firstVertex && !containsIndex(mergeVertices,vertexIndex))
191                                         mergeVertices.push_back(vertexIndex);
192                         }
193                 }
194                 // Set the merged vertices to BROKEN ...
195                 const BOP_IT_Indexs pendingEnd = pendingVertices.end();
196                 for(BOP_IT_Indexs pendingVertex = pendingVertices.begin(); pendingVertex != pendingEnd;pendingVertex++) {
197                         BOP_Index pV = *pendingVertex;
198                         m_mesh->getVertex(pV)->setTAG(BROKEN);
199                         // ... and remove them from mergeVertices queue
200                         const BOP_IT_Indexs mergeEnd = mergeVertices.end();
201                         for(BOP_IT_Indexs mergeVertex = mergeVertices.begin(); mergeVertex != mergeEnd;mergeVertex++) {
202                                 BOP_Index mV = *mergeVertex;
203                                 if (mV == pV) {
204                                         mergeVertices.erase(mergeVertex);
205                                         break;
206                                 }
207                         }
208                 }
209         }
210         else {
211                 // The merge  was not succesful, remove the vertex frome merge vertices queue
212                 mergeVertices.erase(mergeVertices.begin());
213                 
214                 // free the not used newfaces
215                 const BOP_IT_Faces newFacesEnd = newFaces.end();
216                 for(BOP_IT_Faces newFace=newFaces.begin();newFace!=newFacesEnd;newFace++) {
217                         delete (*newFace);
218                 }
219         }
220
221         // Invoke mergeFaces and return the merge result
222         return (mergeFaces(mergeVertices) || merged);
223 }
224
225
226 /**
227  * Simplifies a mesh, merging the faces with vertex v that come from the same face.
228  * @param oldFaces sequence of old mesh faces obtained from the merge
229  * @param newFaces sequence of new mesh faces obtained from the merge
230  * @param vertices sequence of indexs (v1 ... vi = v ... vn) where :
231  *   v is the current vertex to test,
232  *   vj (j < i) are tested vertices, 
233  *   vk (k >= i) are vertices required to test to merge vj
234  * (so if a vertex vk can't be merged, the merge is not possible).
235  * @return true if the vertex v was 'merged' (obviously it could require to test
236  * some new vertices that will be added to the vertices list)
237  */
238 bool BOP_Merge::mergeFaces(BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v) {
239
240         bool merged = true;
241
242         // Get faces with v that come from the same original face, (without the already 'merged' from vertices)
243         BOP_LFaces facesByOriginalFace;
244         getFaces(facesByOriginalFace,vertices,v);
245   
246         if (facesByOriginalFace.size()==0) {
247                 // All the faces with this vertex were already merged!!!
248                 return true;
249         }
250         else {
251                 // Merge faces
252           const BOP_IT_LFaces facesEnd = facesByOriginalFace.end();
253                 for(BOP_IT_LFaces facesByOriginalFaceX = facesByOriginalFace.begin();
254                         (facesByOriginalFaceX != facesEnd)&&merged;
255                         facesByOriginalFaceX++) {
256                                 merged = mergeFaces((*facesByOriginalFaceX),oldFaces,newFaces,vertices,v);
257                 }
258         }
259         return merged;
260 }
261
262
263 /**
264  * Merge a set of faces removing the vertex index v.
265  * @param faces set of faces
266  * @param oldFaces set of old faces obtained from the merge
267  * @param newFaces set of new faces obtained from the merge
268  * @param vertices sequence of indexs (v1 ... vi = v ... vn) where :
269  *   v is the current vertex to test,
270  *   vj (j < i) are tested vertices, 
271  *   vk (k >= i) are vertices required to test to merge vj
272  * (so if a vertex vk can't be merged, the merge is not possible).
273  * @param v vertex index
274  * @return true if the merge is succesful, false otherwise
275  */
276 bool BOP_Merge::mergeFaces(BOP_Faces &faces, BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v)
277 {
278
279         bool merged = false;
280
281         if (faces.size() == 2) {
282                 // Merge a pair of faces into a new face without v
283                 BOP_Face *faceI = faces[0];
284                 BOP_Face *faceJ = faces[1];
285                 BOP_Face *faceK = mergeFaces(faceI,faceJ,vertices,v);
286                 if (faceK != NULL) {
287                         newFaces.push_back(faceK);
288                         oldFaces.push_back(faceI);
289                         oldFaces.push_back(faceJ);
290                         merged = true;
291                 } 
292                 else merged = false;
293         }
294         else if (faces.size() == 4) {
295                 // Merge two pair of faces into a new pair without v
296                 // First we try to perform a simplify merge to avoid more pending vertices
297                 // (for example, if we have two triangles and two quads it will be better
298                 // to do 3+4 and 3+4 than 3+3 and 4+4)
299                 BOP_Face *oldFace1 = faces[0];
300                 BOP_Face *oldFace2, *newFace1;
301                 unsigned int indexJ = 1;
302                 while (indexJ < faces.size() && !merged) {
303                         oldFace2 = faces[indexJ];
304                         newFace1 = mergeFaces(oldFace1,oldFace2,v);
305                         if (newFace1 != NULL) merged = true;
306                         else indexJ++;
307                 }
308                 if (merged) {
309                         // Merge the other pair of faces 
310                         unsigned int indexK, indexL;
311                         if (indexJ == 1) {indexK = 2;indexL = 3;}
312                         else if (indexJ == 2) {indexK = 1;indexL = 3;}
313                         else {indexK = 1;indexL = 2;}
314                         BOP_Face *oldFace3 = faces[indexK];
315                         BOP_Face *oldFace4 = faces[indexL];
316                         unsigned int oldSize = vertices.size();
317                         BOP_Face *newFace2 = mergeFaces(oldFace3,oldFace4,vertices,v);
318                         if (newFace2 != NULL) {
319                                 newFaces.push_back(newFace1);
320                                 newFaces.push_back(newFace2);
321                                 oldFaces.push_back(oldFace1);
322                                 oldFaces.push_back(oldFace2);
323                                 oldFaces.push_back(oldFace3);
324                                 oldFaces.push_back(oldFace4);
325                                 merged = true;
326                         }
327                         else {
328                                 // Undo all changes
329                                 delete newFace1;
330                                 merged = false;
331                                 unsigned int count = vertices.size() - oldSize;
332                                 if (count != 0)
333                                         vertices.erase(vertices.end() - count, vertices.end());
334                         }
335                 }               
336                 if (!merged) {
337                         // Try a complete merge
338                         merged = true;
339                         while (faces.size()>0 && merged) {
340                                 indexJ = 1;
341                                 BOP_Face *faceI = faces[0];
342                                 merged = false;
343                                 while (indexJ < faces.size()) {
344                                         BOP_Face *faceJ = faces[indexJ];
345                                         BOP_Face *faceK = mergeFaces(faceI,faceJ,vertices,v);
346                                         if (faceK != NULL) {
347                                                 // faceK = faceI + faceJ and it does not include v!
348                                                 faces.erase(faces.begin()+indexJ,faces.begin()+(indexJ+1));
349                                                 faces.erase(faces.begin(),faces.begin()+1);
350                                                 newFaces.push_back(faceK);
351                                                 oldFaces.push_back(faceI);
352                                                 oldFaces.push_back(faceJ);
353                                                 merged = true;
354                                                 break;
355                                         }
356                                         else indexJ++;
357                                 }
358                         }
359                 }
360         }
361         else merged = false; // there are N=1 or N=3 or N>4 faces!
362
363         // Return merge result
364         return merged;
365 }
366
367 /**
368  * Returns a new quad from the merge of two faces (one quad and one triangle) 
369  * that share the vertex v and come from the same original face.
370  * @param faceI mesh face (quad or triangle) with index v
371  * @param faceJ mesh face (quad or triangle) with index v
372  * @param v vertex index shared by both faces
373  * @return if the merge is possible, a new quad without v
374  */
375 BOP_Face* BOP_Merge::mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v)
376 {
377         if (faceI->size() == 3) {
378                 if (faceJ->size() == 4)
379                         return mergeFaces((BOP_Face4*)faceJ,(BOP_Face3*)faceI,v);
380         }
381         else if (faceI->size() == 4) {
382                 if (faceJ->size() == 3)
383                         return mergeFaces((BOP_Face4*)faceI,(BOP_Face3*)faceJ,v);
384         }
385         return NULL;
386 }
387
388 /**
389  * Returns a new face from the merge of two faces (quads or triangles) that
390  * share te vertex v and come from the same original face.
391  * @param faceI mesh face (quad or triangle) with index v
392  * @param faceJ mesh face (quad or triangle) with index v
393  * @param pending vector with pending vertices (required to merge two quads into 
394  * a new quad or one quad and one triangle into a new triangle; these merges 
395  * suppose to remove two vertexs, v and its neighbour, that will be a pending 
396  * vertex to merge if it wasn't)
397  * @param v vertex index shared by both faces
398  * @return if the merge is possible, a new face without v
399  */
400 BOP_Face* BOP_Merge::mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Indexs &pending, BOP_Index v)
401 {
402         if (faceI->size() == 3) {
403                 if (faceJ->size() == 3)
404                         return mergeFaces((BOP_Face3*)faceI,(BOP_Face3*)faceJ,v);
405                 else if (faceJ->size() == 4)
406                         return mergeFaces((BOP_Face4*)faceJ,(BOP_Face3*)faceI,pending,v);
407         }
408         else if (faceI->size() == 4) {
409                 if (faceJ->size() == 3)
410                         return mergeFaces((BOP_Face4*)faceI,(BOP_Face3*)faceJ,pending,v);
411                 else if (faceJ->size() == 4)
412                         return mergeFaces((BOP_Face4*)faceI,(BOP_Face4*)faceJ,pending,v);
413         }
414         return NULL;
415 }
416
417 /** 
418  * Returns a new triangle from the merge of two triangles that share the vertex
419  * v and come from the same original face.
420  * @param faceI mesh triangle
421  * @param faceJ mesh triangle
422  * @param v vertex index shared by both triangles
423  * @return If the merge is possible, a new triangle without v
424  */
425 BOP_Face* BOP_Merge::mergeFaces(BOP_Face3 *faceI, BOP_Face3 *faceJ, BOP_Index v)
426 {
427         BOP_Face *faceK = NULL;
428
429         // Get faces data
430         BOP_Index prevI, nextI, prevJ, nextJ;   
431         faceI->getNeighbours(v,prevI,nextI);
432         faceJ->getNeighbours(v,prevJ,nextJ);
433         MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
434         MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
435         MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
436         MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
437         MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
438
439         // Merge test
440         if (prevI == nextJ) {
441                 // Both faces share the edge (prevI,v) == (v,nextJ)
442                 if (BOP_between(vertex,vNextI,vPrevJ)) {
443                         faceK = new BOP_Face3(prevI,prevJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
444                         faceK->setTAG(faceI->getTAG());
445                 }
446         }
447         else if (nextI == prevJ) {
448                 // Both faces share the edge (v,nextI) == (prevJ,v)
449                 if (BOP_between(vertex,vPrevI,vNextJ)) {
450                         faceK = new BOP_Face3(prevI,nextJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
451                         faceK->setTAG(faceI->getTAG());
452                 }
453         }
454         return faceK;
455 }
456
457 /** 
458  * Returns a new quad from the merge of one quad and one triangle that share 
459  * the vertex v and come from the same original face.
460  * @param faceI mesh quad
461  * @param faceJ mesh triangle
462  * @param v vertex index shared by both faces
463  * @return If the merge is possible, a new quad without v
464  */
465 BOP_Face* BOP_Merge::mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Index v)
466 {
467         BOP_Face *faceK = NULL;
468
469         // Get faces data
470         BOP_Index prevI, nextI, opp, prevJ, nextJ;
471         faceI->getNeighbours(v,prevI,nextI,opp);
472         faceJ->getNeighbours(v,prevJ,nextJ);
473         MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
474         MT_Point3 vOpp = m_mesh->getVertex(opp)->getPoint();
475         MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
476         MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
477         MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
478         MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
479
480         // Merge test
481         if (prevI == nextJ) {
482                 if (BOP_between(vertex,vNextI,vPrevJ) && !BOP_collinear(vPrevJ,vPrevI,vOpp)
483                         && BOP_convex(vOpp,vPrevI,vPrevJ,vNextI)) {
484                         faceK = new BOP_Face4(opp,prevI,prevJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
485                         faceK->setTAG(faceI->getTAG());
486                 }
487         }
488         else if (nextI == prevJ) {
489                 if (BOP_between(vertex,vPrevI,vNextJ) && !BOP_collinear(vNextJ,vNextI,vOpp)
490                         && BOP_convex(vOpp,vPrevI,vNextJ,vNextI)) {
491                         faceK = new BOP_Face4(opp,prevI,nextJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
492                         faceK->setTAG(faceI->getTAG());
493                 }
494         }
495         return faceK;
496 }
497
498 /** 
499  * Returns a new face (quad or triangle) from the merge of one quad and one 
500  * triangle that share the vertex v and come from the same original face.
501  * @param faceI mesh quad
502  * @param faceJ mesh triangle
503  * @param pending vector with pending vertices (required to merge one quad 
504  * and one triangle into a new triangle; it supposes to remove two vertexs,
505  * v and its neighbour, that will be a new pending vertex if it wasn't)
506  * @param v vertex index shared by both faces
507  * @return If the merge is possible, a new face without v
508  */
509 BOP_Face* BOP_Merge::mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Indexs &pending, BOP_Index v)
510 {
511         BOP_Face *faceK = NULL;
512
513         // Get faces data
514         BOP_Index prevI, nextI, opp, prevJ, nextJ;
515         faceI->getNeighbours(v,prevI,nextI,opp);
516         faceJ->getNeighbours(v,prevJ,nextJ);
517         MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
518         MT_Point3 vOpp = m_mesh->getVertex(opp)->getPoint();
519         MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
520         MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
521         MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
522         MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
523
524         // Merge test
525         if (prevI == nextJ) {
526                 if (BOP_between(vertex,vNextI,vPrevJ)) {
527                         if (!BOP_collinear(vPrevJ,vPrevI,vOpp) && BOP_convex(vOpp,vPrevI,vPrevJ,vNextI)) {
528                                 // The result is a new quad
529                                 faceK = new BOP_Face4(opp,prevI,prevJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
530                                 faceK->setTAG(faceI->getTAG());
531                         }
532                         else if (BOP_between(vPrevI,vPrevJ,vOpp)) {
533                                 // The result is a triangle (only if prevI can be merged)
534                                 if (prevI < m_firstVertex) return NULL; // It can't be merged
535                                 faceK = new BOP_Face3(nextI,opp,prevJ,faceI->getPlane(),faceI->getOriginalFace());
536                                 faceK->setTAG(faceI->getTAG());
537                                 if (!containsIndex(pending, prevI)) pending.push_back(prevI);
538                         }
539                 }
540         }
541         else if (nextI == prevJ) {
542                 if (BOP_between(vertex,vPrevI,vNextJ)) {
543                         if (!BOP_collinear(vNextJ,vNextI,vOpp) && BOP_convex(vOpp,vPrevI,vNextJ,vNextI)) {
544                                 // The result is a new quad
545                                 faceK = new BOP_Face4(opp,prevI,nextJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
546                                 faceK->setTAG(faceI->getTAG());
547                         }
548                         else if (BOP_between(vNextI,vOpp,vNextJ)) {
549                                 // The result is a triangle (only if nextI can be merged)
550                                 if (nextI < m_firstVertex) return NULL;
551                                 faceK = new BOP_Face3(prevI,nextJ,opp,faceI->getPlane(),faceI->getOriginalFace());
552                                 faceK->setTAG(faceI->getTAG());
553                                 if (!containsIndex(pending, nextI)) pending.push_back(nextI);
554                         }
555                 }
556         }
557         return faceK;
558 }
559
560 /** 
561  * Returns a new quad from the merge of two quads that share 
562  * the vertex v and come from the same original face.
563  * @param faceI mesh quad
564  * @param faceJ mesh quad
565  * @param pending vector with pending vertices (required to merge the two
566  * quads supposes to remove two vertexs, v and its neighbour, 
567  * that will be a new pending vertex if it wasn't)
568  * @param v vertex index shared by both quads
569  * @return If the merge is possible, a new quad without v
570  */
571 BOP_Face* BOP_Merge::mergeFaces(BOP_Face4 *faceI, BOP_Face4 *faceJ, BOP_Indexs &pending, BOP_Index v)
572 {
573         BOP_Face *faceK = NULL;
574
575         // Get faces data
576         BOP_Index prevI, nextI, oppI, prevJ, nextJ, oppJ;
577         faceI->getNeighbours(v,prevI,nextI,oppI);
578         faceJ->getNeighbours(v,prevJ,nextJ,oppJ);
579         MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
580         MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
581         MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
582         MT_Point3 vOppI = m_mesh->getVertex(oppI)->getPoint();
583         MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
584         MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
585         MT_Point3 vOppJ = m_mesh->getVertex(oppJ)->getPoint();
586
587         // Merge test
588         if (prevI == nextJ) {
589                 // prevI/nextJ will be a new vertex required to merge
590                 if (prevI < m_firstVertex) return NULL; // It can't be merged
591                 if (BOP_between(vertex,vPrevJ,vNextI) && BOP_between(vNextJ,vOppJ,vOppI)) {
592                         faceK = new BOP_Face4(oppJ,prevJ,nextI,oppI,faceI->getPlane(),faceI->getOriginalFace());
593                         faceK->setTAG(faceI->getTAG());
594                         // We add prevI to the pending list if it wasn't yet
595                         if (!containsIndex(pending, prevI)) pending.push_back(prevI);
596                 }
597         }
598         else if (nextI == prevJ) {
599                 // nextI/prevJ will be a new vertex required to merge
600                 if (nextI < m_firstVertex) return NULL; // It can't be merged
601                 if (BOP_between(vertex,vPrevI,vNextJ) && BOP_between(vNextI,vOppI,vOppJ)) {
602                         faceK = new BOP_Face4(oppI,prevI,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace());
603                         faceK->setTAG(faceI->getTAG());
604                         // Add nextI to the pending list if it wasn't yet
605                         if (!containsIndex(pending, nextI)) pending.push_back(nextI);
606                 }
607         }
608         return faceK;
609 }
610
611
612 /** 
613  * Simplifies the mesh, merging the pairs of triangles that come frome the
614  * same original face and define a quad.
615  * @return true if a quad was added, false otherwise
616  */
617 bool BOP_Merge::createQuads()
618 {
619   
620         BOP_Faces quads;
621         
622         // Get mesh faces
623         BOP_Faces faces = m_mesh->getFaces();
624
625         
626     // Merge mesh triangles
627         const BOP_IT_Faces facesIEnd = (faces.end()-1);
628         const BOP_IT_Faces facesJEnd = faces.end();
629         for(BOP_IT_Faces faceI=faces.begin();faceI!=facesIEnd;faceI++) {
630                 if ((*faceI)->getTAG() == BROKEN || (*faceI)->size() != 3) continue;
631                 for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) {
632                         if ((*faceJ)->getTAG() == BROKEN || (*faceJ)->size() != 3 ||
633                                 (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue;
634
635                         // Test if both triangles share a vertex index
636                         BOP_Index v;
637                         bool found = false;
638                         for(unsigned int i=0;i<3 && !found;i++) {
639                                 v = (*faceI)->getVertex(i);
640                                 found = (*faceJ)->containsVertex(v);
641                                 
642                         }
643                         if (!found) continue;
644
645                         BOP_Face *faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ,v);
646                         if (faceK != NULL) {
647                                 // Set triangles to BROKEN
648                                 (*faceI)->setTAG(BROKEN);
649                                 (*faceJ)->setTAG(BROKEN);
650                                 quads.push_back(faceK);
651                                 break;
652                         }
653                 }
654         }
655
656     // Add quads to mesh
657         const BOP_IT_Faces quadsEnd = quads.end();
658         for(BOP_IT_Faces quad=quads.begin();quad!=quadsEnd;quad++) m_mesh->addFace(*quad);
659         return (quads.size() > 0);
660 }
661
662 /** 
663  * Returns a new quad (convex) from the merge of two triangles that share the
664  * vertex index v.
665  * @param faceI mesh triangle
666  * @param faceJ mesh triangle
667  * @param v vertex index shared by both triangles
668  * @return a new convex quad if the merge is possible
669  */
670 BOP_Face* BOP_Merge::createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ, BOP_Index v)
671 {
672         BOP_Face *faceK = NULL;
673
674         // Get faces data
675         BOP_Index prevI, nextI, prevJ, nextJ;
676         faceI->getNeighbours(v,prevI,nextI);
677         faceJ->getNeighbours(v,prevJ,nextJ);
678         MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
679         MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
680         MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
681         MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
682         MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
683
684         // Quad test
685         if (prevI == nextJ) {
686                 if (!BOP_collinear(vNextI,vertex,vPrevJ) && !BOP_collinear(vNextI,vPrevI,vPrevJ) &&
687                         BOP_convex(vertex,vNextI,vPrevI,vPrevJ)) {
688                                 faceK = new BOP_Face4(v,nextI,prevI,prevJ,faceI->getPlane(),faceI->getOriginalFace());
689                                 faceK->setTAG(faceI->getTAG());
690                 }
691         }
692         else if (nextI == prevJ) {
693                 if (!BOP_collinear(vPrevI,vertex,vNextJ) && !BOP_collinear(vPrevI,vNextI,vNextJ) &&
694                         BOP_convex(vertex,vNextJ,vNextI,vPrevI)) {
695                                 faceK = new BOP_Face4(v,nextJ,nextI,prevI,faceI->getPlane(),faceI->getOriginalFace());
696                                 faceK->setTAG(faceI->getTAG());
697                         }
698         }
699         return faceK;
700 }
701
702 /**
703  * Returns if a index is inside a set of indexs.
704  * @param indexs set of indexs
705  * @param i index
706  * @return true if the index is inside the set, false otherwise
707  */
708 bool BOP_Merge::containsIndex(BOP_Indexs indexs, BOP_Index i)
709 {
710   const BOP_IT_Indexs indexsEnd = indexs.end();
711         for(BOP_IT_Indexs it=indexs.begin();it!=indexsEnd;it++) {
712                 if (*it == i) return true;
713         }
714         return false;
715 }
716
717 /**
718  * Creates a list of lists L1, L2, ... LN where
719  *   LX = mesh faces with vertex v that come from the same original face
720  * @param facesByOriginalFace list of faces lists
721  * @param v vertex index
722  */
723 void BOP_Merge::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v)
724 {
725         // Get edges with vertex v
726         BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges();
727         const BOP_IT_Indexs edgeEnd = edgeIndexs.end();
728         for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) {    
729                 // Foreach edge, add its no broken faces to the output list
730                 BOP_Edge* edge = m_mesh->getEdge(*edgeIndex);
731                 BOP_Indexs faceIndexs = edge->getFaces();
732                 const BOP_IT_Indexs faceEnd = faceIndexs.end();
733                 for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) {
734                         BOP_Face* face = m_mesh->getFace(*faceIndex);
735                         if (face->getTAG() != BROKEN) {
736                                 bool found = false;
737                                 // Search if we already have created a list for the 
738                                 // faces that come from the same original face
739                                 const BOP_IT_LFaces lfEnd = facesByOriginalFace.end();
740                                 for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin();
741                                 facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) {
742                                         if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) {
743                                                 // Search that the face has not been added to the list before
744                                                 for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) {
745                                                         if ((*facesByOriginalFaceX)[i] == face) {
746                                                                 found = true;
747                                                                 break;
748                                                         }
749                                                 }
750                                                 if (!found) {
751                                                         // Add the face to the list
752                                                   if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face);
753                                                   else facesByOriginalFaceX->push_back(face);
754                                                   found = true;
755                                                 }
756                                                 break;
757                                         }
758                                 }
759                                 if (!found) {
760                                         // Create a new list and add the current face
761                                         BOP_Faces facesByOriginalFaceX;
762                                         facesByOriginalFaceX.push_back(face);
763                                         facesByOriginalFace.push_back(facesByOriginalFaceX);
764                                 }
765                         }
766                 }
767         }
768 }
769
770 /**
771  * Creates a list of lists L1, L2, ... LN where
772  *   LX = mesh faces with vertex v that come from the same original face
773  *        and without any of the vertices that appear before v in vertices
774  * @param facesByOriginalFace list of faces lists
775  * @param vertices vector with vertices indexs that contains v
776  * @param v vertex index
777  */
778 void BOP_Merge::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v)
779 {
780         // Get edges with vertex v
781         BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges();
782         const BOP_IT_Indexs edgeEnd = edgeIndexs.end();
783         for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) {    
784                 // Foreach edge, add its no broken faces to the output list
785                 BOP_Edge* edge = m_mesh->getEdge(*edgeIndex);
786                 BOP_Indexs faceIndexs = edge->getFaces();
787                 const BOP_IT_Indexs faceEnd = faceIndexs.end();
788                 for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) {
789                         BOP_Face* face = m_mesh->getFace(*faceIndex);
790                         if (face->getTAG() != BROKEN) {
791                                 // Search if the face contains any of the forbidden vertices
792                                 bool found = false;
793                                 for(BOP_IT_Indexs vertex = vertices.begin();*vertex!= v;vertex++) {
794                                         if (face->containsVertex(*vertex)) {
795                                                 // face contains a forbidden vertex!
796                                                 found = true;
797                                                 break;
798                                 }
799                         }
800                         if (!found) {
801                                 // Search if we already have created a list with the 
802                                 // faces that come from the same original face
803                           const BOP_IT_LFaces lfEnd = facesByOriginalFace.end();
804                                 for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin();
805                                         facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) {
806                                         if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) {
807                                                 // Search that the face has not been added to the list before
808                                                 for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) {
809                                                         if ((*facesByOriginalFaceX)[i] == face) {
810                                                                 found = true;
811                                                                 break;
812                                                         }
813                                                 }
814                                                 if (!found) {
815                                                   // Add face to the list
816                                                   if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face);
817                                                   else facesByOriginalFaceX->push_back(face);
818                                                   found = true;
819                                                 }
820                                                 break;
821                                         }
822                                 }
823                                 if (!found) {
824                                         // Create a new list and add the current face
825                                         BOP_Faces facesByOriginalFaceX;
826                                         facesByOriginalFaceX.push_back(face);
827                                         facesByOriginalFace.push_back(facesByOriginalFaceX);
828                                 }
829                         }
830                 }
831         }
832         }
833 }