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