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