Merge of trunk into blender 2.5:
[blender.git] / intern / boolop / intern / BOP_Merge2.cpp
1 /**
2  *
3  * $Id: BOP_Merge22.cpp 14444 2008-04-16 22:40:48Z hos $
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., 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): Marc Freixas, Ken Hughes
27  *
28  * ***** END GPL LICENSE BLOCK *****
29  */
30  
31 #include "BOP_Merge2.h"
32
33 #ifdef BOP_NEW_MERGE
34
35 static void deleteFace(BOP_Mesh *m, BOP_Face *face);
36
37 /**
38  * SINGLETON (use method BOP_Merge2.getInstance).
39  */
40 BOP_Merge2 BOP_Merge2::SINGLETON;
41
42 #ifdef BOP_DEBUG
43 void dumpmesh ( BOP_Mesh *m, bool force )
44 {
45         unsigned int nonmanifold = 0;
46         {
47         BOP_Edges edges = m->getEdges();
48         int count = 0;
49     for (BOP_IT_Edges edge = edges.begin(); edge != edges.end();
50                 ++count, ++edge) {
51                 if (!(*edge)->getUsed() && (*edge)->getFaces().size() == 0 ) continue;
52                 BOP_Vertex * v1 = m->getVertex((*edge)->getVertex1());
53                 BOP_Vertex * v2 = m->getVertex((*edge)->getVertex2());
54
55                 if(v1->getTAG()!= BROKEN || v2->getTAG()!= BROKEN ) {
56                         int fcount = 0;
57                         BOP_Indexs faces = (*edge)->getFaces();
58                         for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); face++) {
59                                 BOP_Face *f = m->getFace(*face);
60                                 if(f->getTAG()== UNCLASSIFIED) ++fcount;
61                         }
62
63
64                         if(fcount !=0 && fcount !=2 ) {
65                                 ++nonmanifold;
66                         }
67                 }
68         }
69         if (!force && nonmanifold == 0) return;
70         }
71         if( nonmanifold )
72                 cout << nonmanifold << " edges detected" << endl;
73 #ifdef DEBUG
74         cout << "---------------------------" << endl;
75
76         BOP_Edges edges = m->getEdges();
77         int count = 0;
78     for (BOP_IT_Edges edge = edges.begin(); edge != edges.end();
79                 ++count, ++edge) {
80                 BOP_Vertex * v1 = m->getVertex((*edge)->getVertex1());
81                 BOP_Vertex * v2 = m->getVertex((*edge)->getVertex2());
82
83                 if(v1->getTAG()!= BROKEN || v2->getTAG()!= BROKEN ) {
84                         int fcount = 0;
85                         BOP_Indexs faces = (*edge)->getFaces();
86                         cout << count << ", " << (*edge) << ", " << faces.size() << endl;
87                         for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); face++) {
88                                 BOP_Face *f = m->getFace(*face);
89                                 if(f->getTAG()== UNCLASSIFIED) ++fcount;
90                                 cout << "  face " << f << endl;
91                         }
92
93
94                         if(fcount !=0 && fcount !=2 )
95                                 cout << "    NON-MANIFOLD" << endl;
96                 }
97         }
98
99         BOP_Faces faces = m->getFaces();
100         count = 0;
101     for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) {
102                 if( count < 12*2 || (*face)->getTAG() != BROKEN ) {
103                         cout << count << ", " << *face << endl;
104                 }
105                 ++count;
106         }
107
108         BOP_Vertexs verts = m->getVertexs();
109         count = 0;
110     for (BOP_IT_Vertexs vert = verts.begin(); vert != verts.end(); vert++) {
111                 cout << count++ << ", " << *vert << " " << (*vert)->getNumEdges() << endl;
112                 BOP_Indexs edges = (*vert)->getEdges();
113             for( BOP_IT_Indexs it = edges.begin(); it != edges.end(); ++it) {
114                         BOP_Edge *edge = m->getEdge(*it);
115                         cout << "   " << edge << endl;
116                 }
117         }
118         cout << "===========================" << endl;
119 #endif
120 }
121 #endif
122
123 /**
124  * Simplifies a mesh, merging its faces.
125  * @param m mesh
126  * @param v index of the first mergeable vertex (can be removed by merge) 
127  */
128
129 void BOP_Merge2::mergeFaces(BOP_Mesh *m, BOP_Index v)
130 {
131         m_mesh = m;
132
133 #ifdef DEBUG
134         cout << "##############################" << endl;
135 #endif
136         cleanup( );
137
138         m_firstVertex = v;
139         bool cont = false;
140
141         // Merge faces
142         mergeFaces();   
143
144         do {
145                 // Add quads ...
146                 cont = createQuads();
147                 // ... and merge new faces
148                 if( cont ) cont = mergeFaces();
149
150 #ifdef DEBUG
151                 cout << "called mergeFaces " << cont << endl;
152 #endif
153                 // ... until the merge is not succesful
154         } while(cont);
155 }
156
157 void clean_nonmanifold( BOP_Mesh *m )
158 {
159         return;
160
161         BOP_Edges nme;
162         BOP_Edges e = m->getEdges();
163         for( BOP_IT_Edges it = e.begin(); it != e.end(); ++it ) {
164                 BOP_Indexs faces = (*it)->getFaces();
165                 if( faces.size() & ~2 )
166                         nme.push_back(*it);
167         }
168         if (nme.size() == 0) return;
169         for( BOP_IT_Edges it = nme.begin(); it != nme.end(); ++it ) {
170                 if( (*it)->getFaces().size() > 1 ) {
171                         BOP_Indexs faces = (*it)->getFaces();
172                         for( BOP_IT_Indexs face = faces.begin(); face != faces.end(); ++face ) {
173                                 MT_Point3 vertex1 = m->getVertex(m->getFace(*face)->getVertex(0))->getPoint();
174                                 MT_Point3 vertex2 = m->getVertex(m->getFace(*face)->getVertex(1))->getPoint();
175                                 MT_Point3 vertex3 = m->getVertex(m->getFace(*face)->getVertex(2))->getPoint();
176                                 if (BOP_collinear(vertex1,vertex2,vertex3)) // collinear triangle
177                                         deleteFace(m,m->getFace(*face));
178                         }
179                         continue;
180                 }
181                 BOP_Face *oface1 = m->getFace((*it)->getFaces().front());
182                 BOP_Face *oface2, *tmpface;
183                 BOP_Index first =(*it)->getVertex1();
184                 BOP_Index next =(*it)->getVertex2();
185                 BOP_Index last = first;
186                 unsigned short facecount = 0;
187                 bool found = false;
188                 BOP_Indexs vertList;
189 #ifdef DEBUG
190                 cout << "  first edge is " << (*it) << endl;
191 #endif
192                 vertList.push_back(first);
193                 BOP_Edge *edge;
194                 while(true) {
195                         BOP_Vertex *vert = m->getVertex(next);
196                         BOP_Indexs edges = vert->getEdges();
197                         edge = NULL;
198                         for( BOP_IT_Indexs eit = edges.begin(); eit != edges.end(); ++eit) {
199                                 edge = m->getEdge(*eit);
200                                 if( edge->getFaces().size() > 1) {
201                                         edge = NULL;
202                                         continue;
203                                 }
204                                 if( edge->getVertex1() == next && edge->getVertex2() != last ) {
205                                         last = next;
206                                         next = edge->getVertex2();
207                                         break;
208                                 }
209                                 if( edge->getVertex2() == next && edge->getVertex1() != last ) {
210                                         last = next;
211                                         next = edge->getVertex1();
212                                         break;
213                                 }
214                                 edge = NULL;
215                         }
216                         if( !edge ) break;
217 #ifdef DEBUG
218                         cout << "   next edge is " << edge << endl;
219 #endif
220                         tmpface = m->getFace(edge->getFaces().front());
221                         if( oface1->getOriginalFace() != tmpface->getOriginalFace() )
222                                 oface2 = tmpface;
223                         else
224                                 ++facecount;
225                         vertList.push_back(last);
226                         if( vertList.size() > 3 ) break;
227                         if( next == first ) {
228                                 found = true;
229                                 break;
230                         }
231                 }
232                 if(found) {
233                         edge = *it;
234 #ifdef DEBUG
235                         cout << "   --> found a loop" << endl;
236 #endif
237                         if( vertList.size() == 3 ) {
238                                 BOP_Face3 *face = (BOP_Face3 *)m->getFace(edge->getFaces().front());
239                                 face->getNeighbours(first,last,next);
240                         } else if( vertList.size() == 4 ) {
241                                 BOP_Face4 *face = (BOP_Face4 *)m->getFace(edge->getFaces().front());
242                                 face->getNeighbours(first,last,next,last);
243                         } else {
244 #ifdef DEBUG
245                                 cout << "loop has " << vertList.size() << "verts"; 
246 #endif
247                                 continue;
248                         }
249                         if(facecount == 1) oface1 = oface2;
250                         next = vertList[1];
251                         last = vertList[2];
252                         if( edge->getVertex2() == next ) { 
253                                 BOP_Face3 *f = new BOP_Face3(next,first,last,
254                                         oface1->getPlane(),oface1->getOriginalFace());
255                                 m->addFace( f );
256 #ifdef DEBUG
257                                 cout << "   face is backward: " << f << endl;
258 #endif
259                                 
260                         } else {
261                                 BOP_Face3 *f = new BOP_Face3(last,first,next,
262                                         oface1->getPlane(),oface1->getOriginalFace());
263                                 m->addFace( f );
264 #ifdef DEBUG
265                                 cout << "   face is forward: " << f << endl;
266 #endif
267                         }
268                 }
269         }
270 }
271
272 /**
273  * Runs through mesh and makes sure vert/face/edge data is consistent.  Most
274  * importantly:
275  * (1) mark edges which are no longer used
276  * (2) remove broken faces from edges
277  * (3) remove faces from mesh which have a single edge belonging to no other
278  *     face (non-manifold edges)
279  */
280
281 void BOP_Merge2::cleanup( void )
282 {
283         BOP_Edges edges = m_mesh->getEdges();
284         for (BOP_IT_Edges edge = edges.begin(); edge != edges.end(); ++edge) {
285                 BOP_Indexs faces = (*edge)->getFaces();
286                 for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); ++face) {
287                         BOP_Face *f = m_mesh->getFace(*face);
288                         if(f->getTAG()== UNCLASSIFIED) ;
289                         else (*edge)->removeFace(*face);
290                 }
291                 if( (*edge)->getFaces().size() == 0) (*edge)->setUsed(false);
292         }
293
294         BOP_Vertexs v = m_mesh->getVertexs();
295         for( BOP_IT_Vertexs it = v.begin(); it != v.end(); ++it ) {
296                 if( (*it)->getTAG() != BROKEN) {
297                         BOP_Indexs edges = (*it)->getEdges();
298                         for(BOP_IT_Indexs i = edges.begin();i!=edges.end();i++)
299                                 if( m_mesh->getEdge((*i))->getUsed( ) == false) (*it)->removeEdge( *i );
300                         if( (*it)->getEdges().size() == 0 ) (*it)->setTAG(BROKEN);
301                 }
302         }
303         // clean_nonmanifold( m_mesh );
304 }
305
306 /**
307  * Simplifies a mesh, merging its faces.
308  */
309 bool BOP_Merge2::mergeFaces()
310 {
311         BOP_Indexs mergeVertices;
312         BOP_Vertexs vertices = m_mesh->getVertexs();
313         BOP_IT_Vertexs v = vertices.begin();
314         const BOP_IT_Vertexs verticesEnd = vertices.end();
315
316         // Advance to first mergeable vertex
317         advance(v,m_firstVertex);
318         BOP_Index pos = m_firstVertex;
319
320         // Add unbroken vertices to the list
321         while(v!=verticesEnd) {
322                 if ((*v)->getTAG() != BROKEN) {
323                         mergeVertices.push_back(pos);
324                 }
325
326                 v++;
327                 pos++;
328         }
329
330         // Merge faces with that vertices
331         return mergeFaces(mergeVertices);
332 }
333
334 /**
335  * remove edges from vertices when the vertex is removed
336  */
337 void BOP_Merge2::freeVerts(BOP_Index v, BOP_Vertex *vert)
338 {
339         BOP_Indexs edges = vert->getEdges();
340         BOP_Vertex *other;
341
342         for( BOP_IT_Indexs it = edges.begin(); it != edges.end(); ++it) {
343                 BOP_Edge *edge = m_mesh->getEdge(*it);
344                 BOP_Indexs edges2;
345                 if( edge->getVertex1() != v )
346                         other = m_mesh->getVertex( edge->getVertex1() );
347                 else
348                         other = m_mesh->getVertex( edge->getVertex2() );
349                 other->removeEdge(*it);
350                 vert->removeEdge(*it);
351         }
352 }
353
354 /**
355  * Simplifies a mesh, merging the faces with the specified vertices.
356  * @param mergeVertices vertices to test
357  * @return true if a face merge was performed
358  */
359 bool BOP_Merge2::mergeFaces(BOP_Indexs &mergeVertices)
360 {
361         // Check size > 0!
362         if (mergeVertices.size() == 0) return false;
363         bool didMerge = false;
364
365         for( BOP_Index i = 0; i < mergeVertices.size(); ++i ) {
366                 BOP_LFaces facesByOriginalFace;
367                 BOP_Index v = mergeVertices[i];
368                 BOP_Vertex *vert = m_mesh->getVertex(v);
369 #ifdef DEBUG
370                 cout << "i = " << i << ", v = " << v << ", vert = " << vert << endl;
371                 if (v==48)
372                         cout << "found vert 48" << endl;
373 #endif
374                 if ( vert->getTAG() != BROKEN ) {
375                         getFaces(facesByOriginalFace,v);
376
377                         switch (facesByOriginalFace.size()) {
378                         case 0:
379                                 // v has no unbroken faces (so it's a new BROKEN vertex)
380                                 freeVerts( v, vert );
381                                 vert->setTAG(BROKEN);
382                                 break;
383                         case 2: {
384 #ifdef DEBUG
385                                 cout << "size of fBOF = " << facesByOriginalFace.size() << endl;
386 #endif
387                                 BOP_Faces ff = facesByOriginalFace.front();
388                                 BOP_Faces fb = facesByOriginalFace.back();
389                                 BOP_Index eindexs[2];
390                                 int ecount = 0;
391
392                                 // look for two edges adjacent to v which contain both ofaces
393                                 BOP_Indexs edges = vert->getEdges();
394 #ifdef DEBUG
395                                 cout << "   ff has " << ff.size() << " faces" << endl;
396                                 cout << "   fb has " << fb.size() << " faces" << endl;
397                                 cout << "   v  has " << edges.size() << " edges" << endl;
398 #endif
399                                 for(BOP_IT_Indexs it = edges.begin(); it != edges.end(); 
400                                                 ++it ) {
401                                         BOP_Edge *edge = m_mesh->getEdge(*it);
402                                         BOP_Indexs faces = edge->getFaces();
403 #ifdef DEBUG
404                                         cout << "  " << edge << " has " << edge->getFaces().size() << " faces" << endl;
405 #endif
406                                         if( faces.size() == 2 ) {
407                                                 BOP_Face *f0 = m_mesh->getFace(faces[0]);
408                                                 BOP_Face *f1 = m_mesh->getFace(faces[1]);
409                                                 if( f0->getOriginalFace() != f1->getOriginalFace() ) {
410 #ifdef DEBUG
411                                                         cout << "   " << f0 << endl;
412                                                         cout << "   " << f1 << endl;
413 #endif
414                                                         eindexs[ecount++] = (*it);
415                                                 }
416                                         }
417                                 }
418                                 if(ecount == 2) {
419 #ifdef DEBUG
420                                         cout << "   edge indexes are " << eindexs[0];
421                                         cout << " and " << eindexs[1] << endl;
422 #endif
423                                         BOP_Edge *edge = m_mesh->getEdge(eindexs[0]);
424                                         BOP_Index N = edge->getVertex1();
425                                         if(N == v) N = edge->getVertex2();
426 #ifdef DEBUG
427                                         cout << "    ## OK, replace "<<v<<" with "<<N << endl;
428 #endif
429                                         mergeVertex(ff , v, N );
430                                         mergeVertex(fb , v, N );
431 // now remove v and its edges
432                                         vert->setTAG(BROKEN);
433                                         for(BOP_IT_Indexs it = edges.begin(); it != edges.end(); 
434                                                         ++it ) {
435                                                 BOP_Edge *edge = m_mesh->getEdge(*it);
436                                                 edge->setUsed(false);
437                                         }
438                                         didMerge = true;
439                                 }       
440 #ifdef DEBUG
441                                 else {
442                                         cout << "   HUH: ecount was " << ecount << endl;
443                                 }
444 #endif
445                                 }
446                                 break;
447                         default:
448                                 break;
449                         }
450                 }
451         }
452
453         return didMerge;
454 }
455
456 void BOP_Merge2::mergeVertex(BOP_Faces &faces, BOP_Index v1, BOP_Index v2)
457 {
458         for(BOP_IT_Faces face=faces.begin();face!=faces.end();face++) {
459                 if( (*face)->size() == 3)
460                         mergeVertex((BOP_Face3 *) *face, v1, v2);
461                 else
462                         mergeVertex((BOP_Face4 *) *face, v1, v2);
463                 (*face)->setTAG(BROKEN);
464 #ifdef DEBUG
465                 cout << "  breaking " << (*face) << endl;
466 #endif
467         }
468 }
469
470 /*
471  * Remove a face from the mesh and from each edges's face list
472  */
473
474 static void deleteFace(BOP_Mesh *m, BOP_Face *face)
475 {
476         BOP_Index l2 = face->getVertex(0);
477         BOP_Faces faces = m->getFaces();
478         for(int i = face->size(); i-- ; ) {
479                 BOP_Indexs edges = m->getVertex(l2)->getEdges();
480                 BOP_Index l1 = face->getVertex(i);
481                 for(BOP_IT_Indexs it1 = edges.begin(); it1 != edges.end(); ++it1 ) {
482                         BOP_Edge *edge = m->getEdge(*it1);
483                         if( ( edge->getVertex1() == l1 && edge->getVertex2() == l2 ) ||
484                                 ( edge->getVertex1() == l2 && edge->getVertex2() == l1 ) ) {
485                                 BOP_Indexs ef = edge->getFaces();
486                                 for(BOP_IT_Indexs it = ef.begin(); it != ef.end(); ++it ) {
487                                         if( m->getFace(*it) == face) {
488                                                 edge->removeFace(*it);
489                                                 break;
490                                         }
491                                 }
492                                 break;
493                         }
494                 }
495                 l2 = l1;
496         }
497         face->setTAG(BROKEN);
498 }
499
500 void BOP_Merge2::mergeVertex(BOP_Face3 *face, BOP_Index v1, BOP_Index v2)
501 {
502         BOP_Index next, prev;
503         face->getNeighbours(v1,prev,next);
504
505         // if new vertex is not already in the tri, make a new tri
506         if( prev != v2 && next != v2 ) {
507                 m_mesh->addFace( new BOP_Face3(prev,v2,next,
508                                         face->getPlane(),face->getOriginalFace()) );
509 #ifdef DEBUG
510                 cout << "mv3: add " << prev << "," << v2 << "," << next << endl;
511         } else {
512                 cout << "mv3: vertex already in tri: doing nothing" << endl;
513 #endif
514         }
515         deleteFace(m_mesh, face);
516 }
517
518 void BOP_Merge2::mergeVertex(BOP_Face4 *face, BOP_Index v1, BOP_Index v2)
519 {
520         BOP_Index next, prev, opp;
521         face->getNeighbours(v1,prev,next,opp);
522
523         // if new vertex is already in the quad, replace quad with new tri
524         if( prev == v2 || next == v2 ) {
525                 m_mesh->addFace( new BOP_Face3(prev,next,opp,
526                                         face->getPlane(),face->getOriginalFace()) );
527 #ifdef DEBUG
528                 cout << "mv4a: add " << prev << "," << next << "," << opp << endl;
529 #endif
530         }
531         // otherwise make a new quad
532         else {
533                 m_mesh->addFace( new BOP_Face4(prev,v2,next,opp,
534                                         face->getPlane(),face->getOriginalFace()) );
535 #ifdef DEBUG
536                 cout << "mv4b: add "<<prev<<","<<v2<<","<<next<<","<<opp<<endl;
537 #endif
538         }
539         deleteFace(m_mesh, face);
540 }
541
542 // #define OLD_QUAD
543
544 /** 
545  * Simplifies the mesh, merging the pairs of triangles that come frome the
546  * same original face and define a quad.
547  * @return true if a quad was added, false otherwise
548  */
549 bool BOP_Merge2::createQuads()
550 {
551   
552         BOP_Faces quads;
553         
554         // Get mesh faces
555         BOP_Faces faces = m_mesh->getFaces();
556         
557     // Merge mesh triangles
558         const BOP_IT_Faces facesIEnd = (faces.end()-1);
559         const BOP_IT_Faces facesJEnd = faces.end();
560         for(BOP_IT_Faces faceI=faces.begin();faceI!=facesIEnd;faceI++) {
561 #ifdef OLD_QUAD
562                 if ((*faceI)->getTAG() == BROKEN || (*faceI)->size() != 3) continue;
563                 for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) {
564                         if ((*faceJ)->getTAG() == BROKEN || (*faceJ)->size() != 3 ||
565                                 (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue;
566
567
568                         BOP_Face *faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ);
569                         if (faceK != NULL) {
570                                 // Set triangles to BROKEN
571                                 deleteFace(m_mesh, *faceI);
572                                 deleteFace(m_mesh, *faceJ);
573 #ifdef DEBUG
574                         cout << "createQuad: del " << *faceI << endl;
575                         cout << "createQuad: del " << *faceJ << endl;
576                         cout << "createQuad: add " << faceK << endl;
577 #endif
578                                 quads.push_back(faceK);
579                                 break;
580                         }
581                 }
582 #else
583                 if ((*faceI)->getTAG() == BROKEN ) continue;
584                 for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) {
585                         if ((*faceJ)->getTAG() == BROKEN ||
586                                 (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue;
587
588                         BOP_Face *faceK = NULL;
589                         if((*faceI)->size() == 3) {
590                                 if((*faceJ)->size() == 3)
591                                         faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ);
592                                 else
593                                         faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face4*)*faceJ);
594                         } else {
595                                 if((*faceJ)->size() == 3)
596                                         faceK = createQuad((BOP_Face3*)*faceJ,(BOP_Face4*)*faceI);
597                                 else
598                                         faceK = createQuad((BOP_Face4*)*faceI,(BOP_Face4*)*faceJ);
599                         }
600
601                         if (faceK != NULL) {
602                                 // Set triangles to BROKEN
603                                 deleteFace(m_mesh, *faceI);
604                                 deleteFace(m_mesh, *faceJ);
605 #ifdef DEBUG
606                         cout << "createQuad: del " << *faceI << endl;
607                         cout << "createQuad: del " << *faceJ << endl;
608                         cout << "createQuad: add " << faceK << endl;
609 #endif
610                                 quads.push_back(faceK);
611                                 break;
612                         }
613                 }
614 #endif
615         }
616
617     // Add quads to mesh
618         const BOP_IT_Faces quadsEnd = quads.end();
619         for(BOP_IT_Faces quad=quads.begin();quad!=quadsEnd;quad++) m_mesh->addFace(*quad);
620         return (quads.size() > 0);
621 }
622
623 /** 
624  * Returns a new quad (convex) from the merge of two triangles that share the
625  * vertex index v.
626  * @param faceI mesh triangle
627  * @param faceJ mesh triangle
628  * @param v vertex index shared by both triangles
629  * @return a new convex quad if the merge is possible
630  */
631 BOP_Face* BOP_Merge2::createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ)
632 {
633         // Test if both triangles share a vertex index
634         BOP_Index v;
635         unsigned int i;
636         for(i=0;i<3 ;i++) {
637                 v = faceI->getVertex(i);
638                 if( faceJ->containsVertex(v) ) break;
639         }
640         if (i == 3) return NULL;
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                                 BOP_Index edge;
661                                 m_mesh->getIndexEdge(v,prevI,edge);
662                                 m_mesh->getVertex(v)->removeEdge(edge);
663                                 m_mesh->getVertex(prevI)->removeEdge(edge);
664                 }
665         }
666         else if (nextI == prevJ) {
667                 if (!BOP_collinear(vPrevI,vertex,vNextJ) && !BOP_collinear(vPrevI,vNextI,vNextJ) &&
668                         BOP_convex(vertex,vNextJ,vNextI,vPrevI)) {
669                                 faceK = new BOP_Face4(v,nextJ,nextI,prevI,faceI->getPlane(),faceI->getOriginalFace());
670                                 faceK->setTAG(faceI->getTAG());
671                                 BOP_Index edge;
672                                 m_mesh->getIndexEdge(v,nextI,edge);
673                                 m_mesh->getVertex(v)->removeEdge(edge);
674                                 m_mesh->getVertex(nextI)->removeEdge(edge);
675                         }
676         }
677         return faceK;
678 }
679
680 /** 
681  * Returns a new quad (convex) from the merge of two triangles that share the
682  * vertex index v.
683  * @param faceI mesh triangle
684  * @param faceJ mesh triangle
685  * @param v vertex index shared by both triangles
686  * @return a new convex quad if the merge is possible
687  */
688 BOP_Face* BOP_Merge2::createQuad(BOP_Face3 *faceI, BOP_Face4 *faceJ)
689 {
690         // Test if triangle and quad share a vertex index
691         BOP_Index v;
692         unsigned int i;
693         for(i=0;i<3 ;i++) {
694                 v = faceI->getVertex(i);
695                 if( faceJ->containsVertex(v) ) break;
696         }
697         if (i == 3) return NULL;
698
699         BOP_Face *faceK = NULL;
700
701         // Get faces data
702         BOP_Index prevI, nextI, prevJ, nextJ, oppJ;
703         faceI->getNeighbours(v,prevI,nextI);
704         faceJ->getNeighbours(v,prevJ,nextJ,oppJ);
705
706         // Quad test
707         BOP_Index edge;
708         if (nextI == prevJ) {
709                 if (prevI == nextJ) {   // v is in center
710                         faceK = new BOP_Face3(nextJ,oppJ,prevJ,faceI->getPlane(),faceI->getOriginalFace());
711                         faceK->setTAG(faceI->getTAG());
712                         m_mesh->getIndexEdge(v,prevI,edge);
713                         m_mesh->getVertex(v)->removeEdge(edge);
714                         m_mesh->getVertex(prevI)->removeEdge(edge);
715                         m_mesh->getIndexEdge(v,nextI,edge);
716                         m_mesh->getVertex(v)->removeEdge(edge);
717                         m_mesh->getVertex(nextI)->removeEdge(edge);
718                         freeVerts(v, m_mesh->getVertex(v));
719                 } else if (prevI == oppJ) {     // nextI is in center
720                         faceK = new BOP_Face3(v,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace());
721                         faceK->setTAG(faceI->getTAG());
722                         m_mesh->getIndexEdge(v,nextI,edge);
723                         m_mesh->getVertex(v)->removeEdge(edge);
724                         m_mesh->getVertex(nextI)->removeEdge(edge);
725                         m_mesh->getIndexEdge(prevI,nextI,edge);
726                         m_mesh->getVertex(prevI)->removeEdge(edge);
727                         m_mesh->getVertex(nextI)->removeEdge(edge);
728                         freeVerts(nextI, m_mesh->getVertex(nextI));
729                 }
730         } else if (nextI == oppJ && prevI == nextJ ) { // prevI is in center
731                 faceK = new BOP_Face3(prevJ,v,oppJ,faceI->getPlane(),faceI->getOriginalFace());
732                 faceK->setTAG(faceI->getTAG());
733                 m_mesh->getIndexEdge(v,prevI,edge);
734                 m_mesh->getVertex(v)->removeEdge(edge);
735                 m_mesh->getVertex(prevI)->removeEdge(edge);
736                 m_mesh->getIndexEdge(nextI,prevI,edge);
737                 m_mesh->getVertex(nextI)->removeEdge(edge);
738                 m_mesh->getVertex(prevI)->removeEdge(edge);
739                 freeVerts(prevI, m_mesh->getVertex(prevI));
740         }
741         return faceK;
742 }
743
744 /** 
745  * Returns a new quad (convex) from the merge of two triangles that share the
746  * vertex index v.
747  * @param faceI mesh triangle
748  * @param faceJ mesh triangle
749  * @param v vertex index shared by both triangles
750  * @return a new convex quad if the merge is possible
751  */
752 BOP_Face* BOP_Merge2::createQuad(BOP_Face4 *faceI, BOP_Face4 *faceJ)
753 {
754         BOP_Face *faceK = NULL;
755         //
756         // Test if both quads share a vertex index
757         //
758         BOP_Index v;
759         unsigned int i;
760         for(i=0;i<4 ;i++) {
761                 v = faceI->getVertex(i);
762                 if( faceJ->containsVertex(v) ) break;
763         }
764         if (i == 3) return NULL;
765
766
767         // Get faces data
768         BOP_Index prevI, nextI, oppI, prevJ, nextJ, oppJ;
769         faceI->getNeighbours(v,prevI,nextI,oppI);
770         faceJ->getNeighbours(v,prevJ,nextJ,oppJ);
771
772         // Quad test
773         BOP_Index edge;
774         if (nextI == prevJ) {
775                 if (prevI == nextJ) {   // v is in center
776                         faceK = new BOP_Face4(nextI,oppI,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace());
777                         faceK->setTAG(faceI->getTAG());
778                         m_mesh->getIndexEdge(v,prevI,edge);
779                         m_mesh->getVertex(v)->removeEdge(edge);
780                         m_mesh->getVertex(prevI)->removeEdge(edge);
781                         m_mesh->getIndexEdge(v,nextI,edge);
782                         m_mesh->getVertex(v)->removeEdge(edge);
783                         m_mesh->getVertex(nextI)->removeEdge(edge);
784                         freeVerts(v, m_mesh->getVertex(v));
785                 } else if (oppI == oppJ) {      // nextI is in center
786                         faceK = new BOP_Face4(v,nextJ,oppJ,prevI,faceI->getPlane(),faceI->getOriginalFace());
787                         faceK->setTAG(faceI->getTAG());
788                         m_mesh->getIndexEdge(v,nextI,edge);
789                         m_mesh->getVertex(v)->removeEdge(edge);
790                         m_mesh->getVertex(nextI)->removeEdge(edge);
791                         m_mesh->getIndexEdge(prevI,nextI,edge);
792                         m_mesh->getVertex(prevI)->removeEdge(edge);
793                         m_mesh->getVertex(nextI)->removeEdge(edge);
794                         freeVerts(nextI, m_mesh->getVertex(nextI));
795                 }
796         } else if (prevI == nextJ && oppI == oppJ) { // prevI is in center
797                 faceK = new BOP_Face4(v,nextI,oppJ,prevJ,faceI->getPlane(),faceI->getOriginalFace());
798                 faceK->setTAG(faceI->getTAG());
799                 m_mesh->getIndexEdge(v,prevI,edge);
800                 m_mesh->getVertex(v)->removeEdge(edge);
801                 m_mesh->getVertex(prevI)->removeEdge(edge);
802                 m_mesh->getIndexEdge(nextI,prevI,edge);
803                 m_mesh->getVertex(nextI)->removeEdge(edge);
804                 m_mesh->getVertex(prevI)->removeEdge(edge);
805                 freeVerts(prevI, m_mesh->getVertex(prevI));
806         }
807         return faceK;
808 }
809
810 /**
811  * Returns if a index is inside a set of indexs.
812  * @param indexs set of indexs
813  * @param i index
814  * @return true if the index is inside the set, false otherwise
815  */
816 bool BOP_Merge2::containsIndex(BOP_Indexs indexs, BOP_Index i)
817 {
818   const BOP_IT_Indexs indexsEnd = indexs.end();
819         for(BOP_IT_Indexs it=indexs.begin();it!=indexsEnd;it++) {
820                 if (*it == i) return true;
821         }
822         return false;
823 }
824
825 /**
826  * Creates a list of lists L1, L2, ... LN where
827  *   LX = mesh faces with vertex v that come from the same original face
828  * @param facesByOriginalFace list of faces lists
829  * @param v vertex index
830  */
831 void BOP_Merge2::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v)
832 {
833         // Get edges with vertex v
834
835         BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges();
836         const BOP_IT_Indexs edgeEnd = edgeIndexs.end();
837         for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) {    
838                 // For each edge, add its no broken faces to the output list
839                 BOP_Edge* edge = m_mesh->getEdge(*edgeIndex);
840                 BOP_Indexs faceIndexs = edge->getFaces();
841                 const BOP_IT_Indexs faceEnd = faceIndexs.end();
842                 for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) {
843                         BOP_Face* face = m_mesh->getFace(*faceIndex);
844                         if (face->getTAG() != BROKEN) {
845                                 bool found = false;
846                                 // Search if we already have created a list for the 
847                                 // faces that come from the same original face
848                                 const BOP_IT_LFaces lfEnd = facesByOriginalFace.end();
849                                 for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin();
850                                 facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) {
851                                         if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) {
852                                                 // Search that the face has not been added to the list before
853                                                 for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) {
854                                                         if ((*facesByOriginalFaceX)[i] == face) {
855                                                                 found = true;
856                                                                 break;
857                                                         }
858                                                 }
859                                                 if (!found) {
860                                                         // Add the face to the list
861                                                   if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face);
862                                                   else facesByOriginalFaceX->push_back(face);
863                                                   found = true;
864                                                 }
865                                                 break;
866                                         }
867                                 }
868                                 if (!found) {
869                                         // Create a new list and add the current face
870                                         BOP_Faces facesByOriginalFaceX;
871                                         facesByOriginalFaceX.push_back(face);
872                                         facesByOriginalFace.push_back(facesByOriginalFaceX);
873                                 }
874                         }
875                 }
876         }
877 }
878
879 /**
880  * Creates a list of lists L1, L2, ... LN where
881  *   LX = mesh faces with vertex v that come from the same original face
882  *        and without any of the vertices that appear before v in vertices
883  * @param facesByOriginalFace list of faces lists
884  * @param vertices vector with vertices indexs that contains v
885  * @param v vertex index
886  */
887 void BOP_Merge2::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v)
888 {
889         // Get edges with vertex v
890         BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges();
891         const BOP_IT_Indexs edgeEnd = edgeIndexs.end();
892         for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) {    
893                 // Foreach edge, add its no broken faces to the output list
894                 BOP_Edge* edge = m_mesh->getEdge(*edgeIndex);
895                 BOP_Indexs faceIndexs = edge->getFaces();
896                 const BOP_IT_Indexs faceEnd = faceIndexs.end();
897                 for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) {
898                         BOP_Face* face = m_mesh->getFace(*faceIndex);
899                         if (face->getTAG() != BROKEN) {
900                                 // Search if the face contains any of the forbidden vertices
901                                 bool found = false;
902                                 for(BOP_IT_Indexs vertex = vertices.begin();*vertex!= v;vertex++) {
903                                         if (face->containsVertex(*vertex)) {
904                                                 // face contains a forbidden vertex!
905                                                 found = true;
906                                                 break;
907                                 }
908                         }
909                         if (!found) {
910                                 // Search if we already have created a list with the 
911                                 // faces that come from the same original face
912                           const BOP_IT_LFaces lfEnd = facesByOriginalFace.end();
913                                 for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin();
914                                         facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) {
915                                         if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) {
916                                                 // Search that the face has not been added to the list before
917                                                 for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) {
918                                                         if ((*facesByOriginalFaceX)[i] == face) {
919                                                                 found = true;
920                                                                 break;
921                                                         }
922                                                 }
923                                                 if (!found) {
924                                                   // Add face to the list
925                                                   if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face);
926                                                   else facesByOriginalFaceX->push_back(face);
927                                                   found = true;
928                                                 }
929                                                 break;
930                                         }
931                                 }
932                                 if (!found) {
933                                         // Create a new list and add the current face
934                                         BOP_Faces facesByOriginalFaceX;
935                                         facesByOriginalFaceX.push_back(face);
936                                         facesByOriginalFace.push_back(facesByOriginalFaceX);
937                                 }
938                         }
939                 }
940         }
941         }
942 }
943
944 #endif  /* BOP_NEW_MERGE */