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