← Back to branch summary

~diresu/blender/blender-command-port

« back to all changes in this revision

Viewing changes to intern/boolop/intern/BOP_Merge2.cpp

  • Committer: theeth
  • Date: 2008-10-14 16:52:04 UTC
  • Revision ID: vcs-imports@canonical.com-20081014165204-r32w2gm6s0osvdhn
copy back trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 */