← Back to branch summary

~ubuntu-branches/ubuntu/trusty/blender/trusty

« back to all changes in this revision

Viewing changes to intern/decimation/intern/LOD_ManMesh2.cpp

  • Committer: Package Import Robot
  • Author(s): Jeremy Bicha
  • Date: 2013-03-06 12:08:47 UTC
  • mfrom: (1.5.1) (14.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20130306120847-frjfaryb2zrotwcg
Tags: 2.66a-1ubuntu1
https://launchpad.net/bugs/1076930
https://launchpad.net/bugs/1089256
https://launchpad.net/bugs/1052743
https://launchpad.net/bugs/999024
* Resynchronize with Debian (LP: #1076930, #1089256, #1052743, #999024,
  #1122888, #1147084)
* debian/control:
  - Lower build-depends on libavcodec-dev since we're not
    doing the libav9 transition in Ubuntu yet

Show diffs side-by-side

added added

removed removed

Lines of Context:
intern/decimation/intern/LOD_ManMesh2.cpp
1
 
/*
2
 
 * ***** BEGIN GPL LICENSE BLOCK *****
3
 
 *
4
 
 * This program is free software; you can redistribute it and/or
5
 
 * modify it under the terms of the GNU General Public License
6
 
 * as published by the Free Software Foundation; either version 2
7
 
 * of the License, or (at your option) any later version.
8
 
 *
9
 
 * This program is distributed in the hope that it will be useful,
10
 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
 
 * GNU General Public License for more details.
13
 
 *
14
 
 * You should have received a copy of the GNU General Public License
15
 
 * along with this program; if not, write to the Free Software Foundation,
16
 
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17
 
 *
18
 
 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19
 
 * All rights reserved.
20
 
 *
21
 
 * The Original Code is: all of this file.
22
 
 *
23
 
 * Contributor(s): none yet.
24
 
 *
25
 
 * ***** END GPL LICENSE BLOCK *****
26
 
 */
27
 
 
28
 
/** \file decimation/intern/LOD_ManMesh2.cpp
29
 
 *  \ingroup decimation
30
 
 */
31
 
 
32
 
 
33
 
#include "LOD_ManMesh2.h"
34
 
 
35
 
#include "MT_assert.h"
36
 
#include <algorithm>
37
 
#include "LOD_MeshException.h"
38
 
#include "CTR_TaggedSetOps.h"
39
 
#include "CTR_UHeap.h"
40
 
#include "LOD_ExternBufferEditor.h"
41
 
 
42
 
 
43
 
using namespace std;
44
 
 
45
 
LOD_ManMesh2::
46
 
LOD_ManMesh2(
47
 
) :
48
 
        m_bbox_min(0,0,0),
49
 
        m_bbox_max(0,0,0)
50
 
{
51
 
}
52
 
        
53
 
 
54
 
        LOD_ManMesh2 *
55
 
LOD_ManMesh2::
56
 
New(
57
 
){
58
 
        MEM_SmartPtr<LOD_ManMesh2> output(new LOD_ManMesh2());
59
 
        if (output == NULL) return NULL;
60
 
 
61
 
        // build the vertex, edge and face sets.
62
 
 
63
 
        MEM_SmartPtr<vector<LOD_Vertex> > verts(new vector<LOD_Vertex>);
64
 
        MEM_SmartPtr<vector<LOD_TriFace> > faces(new vector<LOD_TriFace>);
65
 
        MEM_SmartPtr<vector<LOD_Edge> > edges(new vector<LOD_Edge>);
66
 
        
67
 
        if ((faces == NULL) || (edges == NULL) || (verts == NULL)) {
68
 
                return NULL;
69
 
        }
70
 
        
71
 
        output->m_verts = verts.Release();
72
 
        output->m_faces = faces.Release();
73
 
        output->m_edges = edges.Release();
74
 
 
75
 
        return output.Release();
76
 
}       
77
 
 
78
 
// take ownership of the vertices.
79
 
 
80
 
        bool    
81
 
LOD_ManMesh2::
82
 
SetVertices(
83
 
        MEM_SmartPtr<vector<LOD_Vertex> > verts
84
 
){
85
 
 
86
 
 
87
 
        // take ownership of vertices
88
 
        m_verts = verts;
89
 
 
90
 
        // create a polygon and edge buffer of half the size 
91
 
        // and just use the automatic resizing feature of vector<>
92
 
        // to worry about the dynamic array resizing
93
 
        
94
 
        m_faces->clear();
95
 
        m_edges->clear();
96
 
 
97
 
        m_faces->reserve(m_verts->size()/2);
98
 
        m_edges->reserve(m_verts->size()/2);
99
 
 
100
 
        return true;    
101
 
 
102
 
}
103
 
 
104
 
        
105
 
// add a triangle to the mesh
106
 
 
107
 
        void
108
 
LOD_ManMesh2::
109
 
AddTriangle(
110
 
        int verts[3]
111
 
) {
112
 
 
113
 
        MT_assert(verts[0] < int(m_verts->size()));
114
 
        MT_assert(verts[1] < int(m_verts->size()));
115
 
        MT_assert(verts[2] < int(m_verts->size()));
116
 
 
117
 
        LOD_TriFace face;
118
 
        face.m_verts[0] = verts[0];
119
 
        face.m_verts[1] = verts[1];
120
 
        face.m_verts[2] = verts[2];
121
 
 
122
 
        LOD_FaceInd face_index = m_faces->size();
123
 
 
124
 
        m_faces->push_back(face);       
125
 
 
126
 
        // now work out if any of the directed edges or their
127
 
        // companion edges exist already.
128
 
        // We go through the edges associated with each of the given vertices 
129
 
 
130
 
        // the safest thing to do is iterate through each of the edge sets
131
 
        // check against each of the 2 other triangle edges to see if they are there
132
 
        
133
 
        vector<LOD_EdgeInd> new_edges;
134
 
        new_edges.reserve(3);
135
 
 
136
 
        InsertEdge(verts[0],verts[1],face_index,new_edges);
137
 
        InsertEdge(verts[1],verts[2],face_index,new_edges);
138
 
        InsertEdge(verts[2],verts[0],face_index,new_edges);
139
 
 
140
 
}
141
 
        
142
 
// Adds the index of any created edges to new_edges
143
 
 
144
 
        bool
145
 
LOD_ManMesh2::
146
 
InsertEdge(
147
 
        const LOD_VertexInd v1,
148
 
        const LOD_VertexInd v2,
149
 
        const LOD_FaceInd f,
150
 
        vector<LOD_EdgeInd> &new_edges
151
 
){
152
 
        
153
 
        MT_assert(!v1.IsEmpty());
154
 
        MT_assert(!v2.IsEmpty());
155
 
        MT_assert(!f.IsEmpty());
156
 
 
157
 
        vector<LOD_Vertex> &verts = VertexSet();
158
 
        vector<LOD_Edge> &edges = EdgeSet();
159
 
        
160
 
        LOD_EdgeInd e;
161
 
 
162
 
        e = FindEdge(v1,v2);
163
 
 
164
 
        if (e.IsEmpty()) {
165
 
                // This edge does not exist -- make a new one 
166
 
 
167
 
                LOD_Edge temp_e;
168
 
                temp_e.m_verts[0] = v1;
169
 
                temp_e.m_verts[1] = v2;
170
 
 
171
 
                e = m_edges->size();
172
 
 
173
 
                // set the face ptr for this half-edge
174
 
                temp_e.m_faces[0] = f;
175
 
 
176
 
                m_edges->push_back(temp_e);
177
 
 
178
 
                // add the edge index to it's vertices 
179
 
 
180
 
                verts[v1].AddEdge(e);
181
 
                verts[v2].AddEdge(e);
182
 
 
183
 
                new_edges.push_back(e);
184
 
 
185
 
        } else {
186
 
 
187
 
                // edge already exists
188
 
                // insure that there is no polygon already
189
 
                // attached to the other side of this edge
190
 
 
191
 
                // swap the empty face pointer in edge with f
192
 
 
193
 
                LOD_Edge &edge = edges[e];
194
 
 
195
 
                edge.SwapFace(LOD_FaceInd::Empty(),f);
196
 
        }
197
 
                
198
 
 
199
 
        return true;
200
 
 
201
 
}
202
 
 
203
 
        void
204
 
LOD_ManMesh2::
205
 
ConnectTriangle(
206
 
        LOD_FaceInd fi,
207
 
        std::vector<LOD_EdgeInd> & new_edges
208
 
){
209
 
 
210
 
        vector<LOD_TriFace> &faces = FaceSet();
211
 
 
212
 
        MT_assert(!faces[fi].Degenerate());
213
 
 
214
 
        LOD_TriFace & face = faces[fi];
215
 
 
216
 
        InsertEdge(face.m_verts[0],face.m_verts[1],fi,new_edges);
217
 
        InsertEdge(face.m_verts[1],face.m_verts[2],fi,new_edges);
218
 
        InsertEdge(face.m_verts[2],face.m_verts[0],fi,new_edges);
219
 
};
220
 
 
221
 
 
222
 
 
223
 
 
224
 
// geometry access
225
 
//////////////////
226
 
 
227
 
        vector<LOD_Vertex> &
228
 
LOD_ManMesh2::
229
 
VertexSet(
230
 
) const {
231
 
        return m_verts.Ref();
232
 
}               
233
 
 
234
 
        vector<LOD_TriFace> &
235
 
LOD_ManMesh2::
236
 
FaceSet(
237
 
) const {
238
 
        return m_faces.Ref();
239
 
}
240
 
 
241
 
        vector<LOD_Edge> &
242
 
LOD_ManMesh2::
243
 
EdgeSet(
244
 
) const {
245
 
        return m_edges.Ref();
246
 
};
247
 
 
248
 
LOD_ManMesh2::
249
 
~LOD_ManMesh2(
250
 
){
251
 
        //auto ptr takes care of vertex arrays etc.
252
 
}
253
 
 
254
 
        LOD_EdgeInd
255
 
LOD_ManMesh2::
256
 
FindEdge(
257
 
        const LOD_VertexInd v1,
258
 
        const LOD_VertexInd v2
259
 
) {
260
 
 
261
 
        vector<LOD_Vertex> &verts = VertexSet();
262
 
        vector<LOD_Edge> &edges = EdgeSet();
263
 
 
264
 
        LOD_Edge e;
265
 
        e.m_verts[0] = v1;
266
 
        e.m_verts[1] = v2;
267
 
        
268
 
        vector<LOD_EdgeInd> &v1_edges = verts[v1].m_edges;
269
 
        vector<LOD_EdgeInd>::const_iterator v1_end = v1_edges.end();
270
 
        vector<LOD_EdgeInd>::iterator v1_begin = v1_edges.begin();
271
 
 
272
 
        for (; v1_begin != v1_end; ++v1_begin) {
273
 
                if (edges[*v1_begin] == e) return *v1_begin;
274
 
        }
275
 
        
276
 
        return LOD_EdgeInd::Empty();
277
 
}
278
 
 
279
 
// face queries
280
 
///////////////
281
 
 
282
 
        void
283
 
LOD_ManMesh2::
284
 
FaceVertices(
285
 
        LOD_FaceInd fi,
286
 
        vector<LOD_VertexInd> &output
287
 
){      
288
 
        const vector<LOD_TriFace> &faces = FaceSet();
289
 
        const LOD_TriFace & f = faces[fi];
290
 
 
291
 
        output.push_back(f.m_verts[0]);
292
 
        output.push_back(f.m_verts[1]);
293
 
        output.push_back(f.m_verts[2]);
294
 
}
295
 
        
296
 
        void
297
 
LOD_ManMesh2::
298
 
FaceEdges(
299
 
        LOD_FaceInd fi,
300
 
        vector<LOD_EdgeInd> &output
301
 
){
302
 
        const vector<LOD_TriFace> &faces = FaceSet();
303
 
        vector<LOD_Edge> &edges = EdgeSet();
304
 
        vector<LOD_Vertex> &verts = VertexSet();        
305
 
 
306
 
        const LOD_TriFace & f = faces[fi];
307
 
        // intersect vertex edges
308
 
 
309
 
        vector<LOD_EdgeInd> & v0_edges = verts[f.m_verts[0]].m_edges;
310
 
        vector<LOD_EdgeInd> & v1_edges = verts[f.m_verts[1]].m_edges;
311
 
        vector<LOD_EdgeInd> & v2_edges = verts[f.m_verts[2]].m_edges;
312
 
 
313
 
        CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v0_edges,v1_edges,edges,output);
314
 
        CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v1_edges,v2_edges,edges,output);
315
 
        CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v2_edges,v0_edges,edges,output);
316
 
 
317
 
        MT_assert(output.size() == 3);
318
 
        if (output.size() != 3) {
319
 
                LOD_MeshException e(LOD_MeshException::e_non_manifold);
320
 
                throw(e);       
321
 
        }
322
 
}
323
 
        
324
 
 
325
 
// edge queries
326
 
///////////////
327
 
 
328
 
        void
329
 
LOD_ManMesh2::
330
 
EdgeVertices(
331
 
        LOD_EdgeInd ei,
332
 
        vector<LOD_VertexInd> &output
333
 
){
334
 
        const vector<LOD_Edge> &edges = EdgeSet();
335
 
        const LOD_Edge & e = edges[ei];
336
 
 
337
 
        output.push_back(e.m_verts[0]);
338
 
        output.push_back(e.m_verts[1]);
339
 
}
340
 
 
341
 
        void
342
 
LOD_ManMesh2::
343
 
EdgeFaces(
344
 
        LOD_EdgeInd ei,
345
 
        vector<LOD_FaceInd> &output
346
 
){
347
 
        const vector<LOD_Edge> &edges = EdgeSet();
348
 
        const LOD_Edge & e = edges[ei];
349
 
 
350
 
        if (!e.m_faces[0].IsEmpty()) {
351
 
                output.push_back(e.m_faces[0]);
352
 
        }
353
 
        if (!e.m_faces[1].IsEmpty()) {
354
 
                output.push_back(e.m_faces[1]);
355
 
        }
356
 
}       
357
 
 
358
 
// vertex queries
359
 
/////////////////
360
 
 
361
 
        void
362
 
LOD_ManMesh2::
363
 
VertexEdges(
364
 
        LOD_VertexInd vi,
365
 
        vector<LOD_EdgeInd> &output
366
 
){
367
 
        // iterate through the edges of v and push them onto the 
368
 
        // output
369
 
        
370
 
        vector<LOD_Vertex> &verts = VertexSet();
371
 
 
372
 
        vector<LOD_EdgeInd> & v_edges = verts[vi].m_edges;
373
 
        vector<LOD_EdgeInd>::iterator v_it = v_edges.begin();
374
 
 
375
 
        for (; v_it != v_edges.end(); ++v_it) {
376
 
                output.push_back(*v_it);
377
 
        }       
378
 
}
379
 
 
380
 
        void
381
 
LOD_ManMesh2::
382
 
VertexFaces(
383
 
        LOD_VertexInd vi,
384
 
        vector<LOD_FaceInd> &output
385
 
){
386
 
        const vector<LOD_Vertex> &verts = VertexSet();
387
 
        vector<LOD_Edge> &edges = EdgeSet();
388
 
        vector<LOD_TriFace> &faces = FaceSet();
389
 
 
390
 
        const vector<LOD_EdgeInd> &v_edges = verts[vi].m_edges;
391
 
        vector<LOD_EdgeInd>::const_iterator e_it = v_edges.begin();
392
 
 
393
 
        for (; e_it != v_edges.end(); ++e_it) {
394
 
 
395
 
                LOD_Edge &e = edges[*e_it]; 
396
 
 
397
 
                if ((!e.m_faces[0].IsEmpty()) && (!faces[e.m_faces[0]].SelectTag())) {
398
 
                        output.push_back(e.m_faces[0]);
399
 
                        faces[e.m_faces[0]].SetSelectTag(true);
400
 
                }
401
 
 
402
 
                if ((!e.m_faces[1].IsEmpty()) && (!faces[e.m_faces[1]].SelectTag())) {
403
 
                        output.push_back(e.m_faces[1]);
404
 
                        faces[e.m_faces[1]].SetSelectTag(true);
405
 
                }
406
 
        }
407
 
 
408
 
        vector<LOD_FaceInd>::iterator f_it = output.begin();
409
 
 
410
 
        for (; f_it != output.end(); ++f_it) {
411
 
                faces[*f_it].SetSelectTag(false);
412
 
        }
413
 
};
414
 
                
415
 
        void
416
 
LOD_ManMesh2::
417
 
SetBBox(
418
 
        MT_Vector3 bbox_min,
419
 
        MT_Vector3 bbox_max
420
 
){
421
 
        m_bbox_min = bbox_min;
422
 
        m_bbox_max = bbox_max;
423
 
};
424
 
 
425
 
        void
426
 
LOD_ManMesh2::
427
 
SC_TriFace(
428
 
        LOD_FaceInd f
429
 
){
430
 
        LOD_TriFace face = (*m_faces)[f];
431
 
        
432
 
        // check for unique vertices
433
 
 
434
 
        if (
435
 
                (face.m_verts[0] == face.m_verts[1]) ||
436
 
                (face.m_verts[1] == face.m_verts[2]) ||
437
 
                (face.m_verts[2] == face.m_verts[0])
438
 
        ) {
439
 
                MT_assert(false);
440
 
        }       
441
 
 
442
 
}
443
 
 
444
 
 
445
 
        void
446
 
LOD_ManMesh2::
447
 
SC_EdgeList(
448
 
        LOD_VertexInd v
449
 
){
450
 
        vector<LOD_Edge> &edges = EdgeSet();
451
 
        vector<LOD_Vertex> &verts = VertexSet();
452
 
 
453
 
        vector<LOD_EdgeInd>::iterator e_it = verts[v].m_edges.begin();
454
 
 
455
 
        for (;e_it != verts[v].m_edges.end(); ++e_it) {
456
 
                MT_assert( (edges[*e_it].m_verts[0] == v) || (edges[*e_it].m_verts[1] == v));
457
 
        }                               
458
 
 
459
 
};
460
 
        
461
 
        void
462
 
LOD_ManMesh2::
463
 
DeleteVertex(
464
 
        LOD_ExternBufferEditor & extern_editor,
465
 
        LOD_VertexInd v
466
 
){
467
 
 
468
 
        vector<LOD_Edge> &edges = EdgeSet();
469
 
        vector<LOD_Vertex> &verts = VertexSet();
470
 
        vector<LOD_TriFace> &faces = FaceSet();
471
 
 
472
 
        // need to update all the edge and polygons pointing to 
473
 
        // the last vertex in m_verts
474
 
 
475
 
        if (verts.size() == 1) {
476
 
                verts.clear();
477
 
                return;
478
 
        }
479
 
 
480
 
        LOD_VertexInd last = LOD_VertexInd(size_t(verts.end() - verts.begin() - 1));
481
 
 
482
 
        if (!(last == v)) {
483
 
 
484
 
                // we asume that v is already disconnected
485
 
 
486
 
                vector<LOD_FaceInd> v_faces;
487
 
                vector<LOD_EdgeInd> v_edges;
488
 
 
489
 
                v_faces.reserve(64);
490
 
                v_edges.reserve(64);
491
 
 
492
 
                VertexFaces(last,v_faces);
493
 
                VertexEdges(last,v_edges);
494
 
 
495
 
                // map the faces and edges to look at v 
496
 
 
497
 
                vector<LOD_FaceInd>::iterator face_it = v_faces.begin();
498
 
 
499
 
                for(; face_it != v_faces.end(); ++face_it) {
500
 
                        faces[*face_it].SwapVertex(last,v);
501
 
                }
502
 
                vector<LOD_EdgeInd>::iterator edge_it = v_edges.begin();
503
 
 
504
 
                for (; edge_it != v_edges.end(); ++edge_it) {
505
 
                        edges[*edge_it].SwapVertex(last,v);
506
 
                }
507
 
 
508
 
                // copy the last vertex onto v and pop off the back.
509
 
 
510
 
                verts[v] = verts[last];
511
 
 
512
 
                // tidy external buffer
513
 
                extern_editor.CopyModifiedFaces(*this,v_faces);
514
 
        }
515
 
 
516
 
        verts.pop_back();       
517
 
        extern_editor.CopyBackVertex(v);
518
 
 
519
 
 
520
 
};              
521
 
 
522
 
        void
523
 
LOD_ManMesh2::
524
 
DeleteEdge(
525
 
        LOD_EdgeInd e,
526
 
        CTR_UHeap<LOD_Edge> * heap
527
 
){
528
 
        vector<LOD_Edge> &edges = EdgeSet();
529
 
        vector<LOD_Vertex> &verts = VertexSet();
530
 
 
531
 
        if (edges.size() == 1) {
532
 
                edges.clear();
533
 
                return;
534
 
        }
535
 
 
536
 
        LOD_EdgeInd last = LOD_EdgeInd(size_t(edges.end() - edges.begin() - 1));
537
 
 
538
 
        if (!(last == e)) {
539
 
                vector<LOD_EdgeInd> e_verts;
540
 
                e_verts.reserve(2);
541
 
                EdgeVertices(last,e_verts);
542
 
                // something is wrong if there arent two!
543
 
 
544
 
                verts[e_verts[0]].SwapEdge(last,e);
545
 
                verts[e_verts[1]].SwapEdge(last,e);
546
 
 
547
 
                // edges[e] should already have been removed from the heap
548
 
 
549
 
                MT_assert(edges[e].HeapPos() == -1);
550
 
 
551
 
                edges[e] = edges[last];
552
 
                // also have to swap there heap positions.!!!!!
553
 
 
554
 
                heap->HeapVector()[edges[e].HeapPos()] = e;
555
 
 
556
 
 
557
 
        }
558
 
        edges.pop_back();
559
 
};
560
 
        
561
 
        void
562
 
LOD_ManMesh2::
563
 
DeleteFace(
564
 
        LOD_ExternBufferEditor & extern_editor,
565
 
        LOD_FaceInd f
566
 
){
567
 
 
568
 
        vector<LOD_Edge> &edges = EdgeSet();
569
 
        vector<LOD_TriFace> &faces = FaceSet();
570
 
 
571
 
        if (faces.size() == 1) {
572
 
                faces.clear();
573
 
                return;
574
 
        }
575
 
 
576
 
        LOD_FaceInd last = LOD_FaceInd(size_t (faces.end() - faces.begin() - 1));
577
 
 
578
 
        if (!(last == f)) {
579
 
                
580
 
                // we have to update the edges which point to the last 
581
 
                // face 
582
 
 
583
 
                vector<LOD_EdgeInd> f_edges;
584
 
                f_edges.reserve(3);
585
 
 
586
 
                FaceEdges(last,f_edges);
587
 
 
588
 
                vector<LOD_EdgeInd>::iterator edge_it = f_edges.begin();
589
 
                vector<LOD_EdgeInd>::const_iterator edge_end = f_edges.end();
590
 
        
591
 
                for (; edge_it != edge_end; ++edge_it) {
592
 
                        edges[*edge_it].SwapFace(last,f);
593
 
                }
594
 
 
595
 
                faces[f] = faces[last];
596
 
 
597
 
        }
598
 
        faces.pop_back();
599
 
 
600
 
        // tidy external buffers
601
 
        extern_editor.CopyBackFace(f);
602
 
};      
603
 
 
604
 
 
605
 
 
606
 
 
607
 
 
608
 
 
609
 
 
610
 
 
611
 
 
612
 
 
613
 
 
614
 
 
615
 
 
616
 
 
617
 
 
618