← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/eltopo/eltopo3d/nondestructivetrimesh.cpp

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/eltopo/eltopo3d/nondestructivetrimesh.cpp
 
1
// ---------------------------------------------------------
 
2
//
 
3
//  nondestructivetrimesh.cpp
 
4
//  Tyson Brochu 2008
 
5
//  
 
6
//  Implementation of NonDestructiveTriMesh: the graph of a 
 
7
//  triangle surface mesh.  See header for more details.
 
8
//
 
9
// ---------------------------------------------------------
 
10
 
 
11
// ---------------------------------------------------------
 
12
// Includes
 
13
// ---------------------------------------------------------
 
14
 
 
15
#include <nondestructivetrimesh.h>
 
16
 
 
17
#include <cmath>
 
18
#include <cstdarg>
 
19
#include <cstdlib>
 
20
#include <fstream>
 
21
#include <wallclocktime.h>
 
22
 
 
23
// ---------------------------------------------------------
 
24
// Local constants, typedefs, macros
 
25
// ---------------------------------------------------------
 
26
 
 
27
namespace {
 
28
    
 
29
/// Avoid modulo operator in (i+1)%3
 
30
const unsigned int i_plus_one_mod_three[3] = {1,2,0};
 
31
    
 
32
}   // namespace
 
33
 
 
34
 
 
35
// ---------------------------------------------------------
 
36
// Member function definitions
 
37
// ---------------------------------------------------------
 
38
 
 
39
// --------------------------------------------------------
 
40
///
 
41
/// Clear all mesh information
 
42
///
 
43
// --------------------------------------------------------
 
44
 
 
45
void NonDestructiveTriMesh::clear()
 
46
{
 
47
    m_tris.clear();
 
48
    clear_connectivity();
 
49
}
 
50
 
 
51
 
 
52
// --------------------------------------------------------
 
53
///
 
54
/// Mark a triangle as deleted without actually changing the data structures
 
55
///
 
56
// --------------------------------------------------------
 
57
 
 
58
void NonDestructiveTriMesh::nondestructive_remove_triangle(size_t tri)
 
59
{
 
60
    // Update the vertex->triangle map, m_vertex_to_triangle_map
 
61
    
 
62
    Vec3st& t = m_tris[tri];
 
63
    for(unsigned int i = 0; i < 3; i++)
 
64
    {
 
65
        // Get the set of triangles incident on vertex t[i]
 
66
        std::vector<size_t>& vt = m_vertex_to_triangle_map[t[i]];
 
67
        
 
68
        for( int j = 0; j < (int)vt.size(); j++ )
 
69
        {
 
70
            // If a triangle incident on vertex t[i] is tri, delete it
 
71
            if(vt[j] == tri)
 
72
            {  
 
73
                vt.erase( vt.begin() + j );
 
74
                --j;
 
75
            }
 
76
        }
 
77
    }
 
78
    
 
79
    // Update the triangle->edge map, m_triangle_to_edge_map
 
80
    
 
81
    Vec3st& te = m_triangle_to_edge_map[tri];
 
82
    
 
83
    for(unsigned int i = 0; i < 3; i++)
 
84
    {
 
85
        size_t inc_edge = te[i];
 
86
        
 
87
        std::vector<size_t>& et = m_edge_to_triangle_map[inc_edge];
 
88
        
 
89
        for( int j = 0; j < (int) et.size(); j++)
 
90
        {
 
91
            if(et[j] == tri)
 
92
            {
 
93
                et.erase( et.begin() + j );
 
94
                --j;
 
95
            }
 
96
        }
 
97
        
 
98
        if ( et.size() == 1 )
 
99
        {
 
100
            m_is_boundary_edge[inc_edge] = true;
 
101
        }
 
102
        else
 
103
        {
 
104
            m_is_boundary_edge[inc_edge] = false;
 
105
        }
 
106
        
 
107
        if ( et.empty() )
 
108
        {
 
109
            // No triangles are incident on this edge.  Delete it.
 
110
            nondestructive_remove_edge( inc_edge );
 
111
        }         
 
112
    }
 
113
    
 
114
    // triangle is deleted, clear its auxiliary structures
 
115
    te[0] = te[1] = te[2] = 0;
 
116
    
 
117
    update_is_boundary_vertex( t[0] );
 
118
    update_is_boundary_vertex( t[1] );   
 
119
    update_is_boundary_vertex( t[2] );
 
120
    
 
121
    // Clear t, marking it as deleted
 
122
    t[0] = t[1] = t[2] = 0;
 
123
    
 
124
    
 
125
}
 
126
 
 
127
 
 
128
// --------------------------------------------------------
 
129
///
 
130
/// Add a triangle to the tris structure, update connectivity
 
131
///
 
132
// --------------------------------------------------------
 
133
 
 
134
size_t NonDestructiveTriMesh::nondestructive_add_triangle( const Vec3st& tri )
 
135
{
 
136
    assert( tri[0] < m_vertex_to_edge_map.size() );
 
137
    assert( tri[1] < m_vertex_to_edge_map.size() );
 
138
    assert( tri[2] < m_vertex_to_edge_map.size() );
 
139
    
 
140
    size_t idx = m_tris.size();
 
141
    m_tris.push_back(tri);
 
142
    m_triangle_to_edge_map.resize(idx+1);
 
143
    
 
144
    for(unsigned int i = 0; i < 3; i++)
 
145
    {
 
146
        size_t vtx0 = tri[ i ];
 
147
        size_t vtx1 = tri[ i_plus_one_mod_three[i] ];
 
148
        
 
149
        // Find the edge composed of these two vertices
 
150
        size_t e = get_edge_index(vtx0, vtx1);
 
151
        if(e == m_edges.size())
 
152
        {
 
153
            // if the edge doesn't exist, add it
 
154
            e = nondestructive_add_edge(vtx0, vtx1);
 
155
        }
 
156
        
 
157
        // Update connectivity
 
158
        m_edge_to_triangle_map[e].push_back(idx);       // edge->triangle
 
159
        
 
160
        if ( m_edge_to_triangle_map[e].size() == 1 )
 
161
        {
 
162
            m_is_boundary_edge[e] = true; 
 
163
        }
 
164
        else
 
165
        {
 
166
            m_is_boundary_edge[e] = false;
 
167
        }
 
168
        
 
169
        m_triangle_to_edge_map[idx][i] = e;                // triangle->edge
 
170
        m_vertex_to_triangle_map[tri[i]].push_back(idx);   // vertex->triangle      
 
171
    }
 
172
    
 
173
    update_is_boundary_vertex( tri[0] );
 
174
    update_is_boundary_vertex( tri[1] );
 
175
    update_is_boundary_vertex( tri[2] );
 
176
    
 
177
    return idx;
 
178
    
 
179
}
 
180
 
 
181
// --------------------------------------------------------
 
182
///
 
183
/// Add a vertex, update connectivity.  Return index of new vertex.
 
184
///
 
185
// --------------------------------------------------------
 
186
 
 
187
size_t NonDestructiveTriMesh::nondestructive_add_vertex( )
 
188
{  
 
189
    assert( m_vertex_to_edge_map.size() == m_vertex_to_triangle_map.size() );
 
190
    assert( m_vertex_to_edge_map.size() == m_is_boundary_vertex.size() );
 
191
    
 
192
    m_vertex_to_edge_map.resize( m_vertex_to_edge_map.size() + 1 );
 
193
    m_vertex_to_triangle_map.resize( m_vertex_to_triangle_map.size() + 1 );
 
194
    m_is_boundary_vertex.resize( m_is_boundary_vertex.size() + 1 );
 
195
    
 
196
    return m_vertex_to_triangle_map.size() - 1;
 
197
}
 
198
 
 
199
 
 
200
// --------------------------------------------------------
 
201
///
 
202
/// Remove a vertex, update connectivity
 
203
///
 
204
// --------------------------------------------------------
 
205
 
 
206
void NonDestructiveTriMesh::nondestructive_remove_vertex(size_t vtx)
 
207
{
 
208
    
 
209
    m_vertex_to_triangle_map[vtx].clear();    //triangles incident on vertices
 
210
    
 
211
    // check any m_edges incident on this vertex are marked as deleted
 
212
    for ( size_t i = 0; i < m_vertex_to_edge_map[vtx].size(); ++i )
 
213
    {
 
214
        assert( m_edges[ m_vertex_to_edge_map[vtx][i] ][0] == m_edges[ m_vertex_to_edge_map[vtx][i] ][1] );
 
215
    }
 
216
    
 
217
    m_vertex_to_edge_map[vtx].clear();   //edges incident on vertices
 
218
}
 
219
 
 
220
 
 
221
// ---------------------------------------------------------
 
222
///
 
223
/// Update the number of vertices in the mesh.
 
224
///
 
225
// ---------------------------------------------------------
 
226
 
 
227
void NonDestructiveTriMesh::set_num_vertices( size_t num_vertices )
 
228
{
 
229
    if ( num_vertices >= m_vertex_to_triangle_map.size() )
 
230
    {
 
231
        // expand the vertex data structures with empties
 
232
    }
 
233
    else
 
234
    {
 
235
        // reduce the number of vertices
 
236
        
 
237
        assert( m_vertex_to_triangle_map.size() == m_vertex_to_edge_map.size() );
 
238
        assert( m_vertex_to_triangle_map.size() == m_is_boundary_vertex.size() );
 
239
        
 
240
        for ( size_t i = num_vertices; i < m_vertex_to_triangle_map.size(); ++i )
 
241
        {
 
242
            assert( vertex_is_deleted(i) );
 
243
            assert( m_vertex_to_edge_map[i].size() == 0 );
 
244
            assert( m_vertex_to_triangle_map[i].size() == 0 );
 
245
        }
 
246
    }
 
247
    
 
248
    m_vertex_to_edge_map.resize( num_vertices );
 
249
    m_vertex_to_triangle_map.resize( num_vertices );
 
250
    m_is_boundary_vertex.resize( num_vertices );
 
251
    test_connectivity();
 
252
    
 
253
}
 
254
 
 
255
 
 
256
// --------------------------------------------------------
 
257
///
 
258
/// Add an edge to the list.  Return the index of the new edge.
 
259
///
 
260
// --------------------------------------------------------
 
261
 
 
262
size_t NonDestructiveTriMesh::nondestructive_add_edge(size_t vtx0, size_t vtx1)
 
263
{
 
264
    
 
265
    size_t edge_index = m_edges.size();
 
266
    m_edges.push_back(Vec2st(vtx0, vtx1));
 
267
    
 
268
    m_edge_to_triangle_map.push_back( std::vector<size_t>( 0 ) );
 
269
    
 
270
    m_is_boundary_edge.push_back( true );
 
271
    
 
272
    m_vertex_to_edge_map[vtx0].push_back(edge_index);
 
273
    m_vertex_to_edge_map[vtx1].push_back(edge_index);
 
274
    
 
275
    return edge_index;
 
276
}
 
277
 
 
278
 
 
279
// --------------------------------------------------------
 
280
///
 
281
/// Mark an edge as deleted, update connectivity
 
282
///
 
283
// --------------------------------------------------------
 
284
 
 
285
void NonDestructiveTriMesh::nondestructive_remove_edge( size_t edge_index )
 
286
{
 
287
    // vertex 0
 
288
    {
 
289
        std::vector<size_t>& vertex_to_edge_map = m_vertex_to_edge_map[ m_edges[edge_index][0] ];
 
290
        for ( int i=0; i < (int)vertex_to_edge_map.size(); ++i)
 
291
        {
 
292
            if ( vertex_to_edge_map[i] == edge_index )
 
293
            {
 
294
                vertex_to_edge_map.erase( vertex_to_edge_map.begin() + i );
 
295
                --i;
 
296
            }
 
297
        }
 
298
    }
 
299
    
 
300
    // vertex 1
 
301
    {
 
302
        std::vector<size_t>& vertex_to_edge_map = m_vertex_to_edge_map[ m_edges[edge_index][1] ];
 
303
        for ( int i=0; i < (int)vertex_to_edge_map.size(); ++i)
 
304
        {
 
305
            if ( vertex_to_edge_map[i] == edge_index )
 
306
            {
 
307
                vertex_to_edge_map.erase( vertex_to_edge_map.begin() + i );
 
308
                --i;
 
309
            }
 
310
        }
 
311
    }
 
312
    
 
313
    m_edges[edge_index][0] = 0;
 
314
    m_edges[edge_index][1] = 0; 
 
315
    
 
316
}
 
317
 
 
318
 
 
319
// ---------------------------------------------------------
 
320
///
 
321
/// Determine if the given vertex is on a boundary edge and store in data structure.
 
322
///
 
323
// ---------------------------------------------------------
 
324
 
 
325
void NonDestructiveTriMesh::update_is_boundary_vertex( size_t v )
 
326
{
 
327
    m_is_boundary_vertex[v] = false;
 
328
    
 
329
    for ( size_t i = 0; i < m_vertex_to_edge_map[v].size(); ++i )
 
330
    {
 
331
        size_t edge_index = m_vertex_to_edge_map[v][i];
 
332
        
 
333
        if ( m_is_boundary_edge[edge_index] )
 
334
        {
 
335
            m_is_boundary_vertex[v] = true;
 
336
            return;
 
337
        }
 
338
    }
 
339
    
 
340
}
 
341
 
 
342
 
 
343
// ---------------------------------------------------------
 
344
///
 
345
/// Ensure that all adjacent triangles have consistent orientation.
 
346
///
 
347
// ---------------------------------------------------------
 
348
 
 
349
void NonDestructiveTriMesh::verify_orientation( )
 
350
{
 
351
    for ( size_t i = 0; i < m_edges.size(); ++i )
 
352
    {
 
353
        if ( m_edge_to_triangle_map[i].size() != 2 )
 
354
        {
 
355
            continue;
 
356
        }
 
357
        
 
358
        if ( edge_is_deleted(i) ) { continue; }
 
359
        
 
360
        size_t a = m_edges[i][0];
 
361
        size_t b = m_edges[i][1];
 
362
        const Vec3st& tri0 = m_tris[ m_edge_to_triangle_map[i][0] ];
 
363
        const Vec3st& tri1 = m_tris[ m_edge_to_triangle_map[i][1] ]; 
 
364
        
 
365
        bool orient0 = oriented(a, b, tri0 );
 
366
        bool orient1 = oriented(a, b, tri1 );
 
367
        
 
368
        assert( orient0 != orient1 );
 
369
    }
 
370
}
 
371
 
 
372
 
 
373
// --------------------------------------------------------
 
374
///
 
375
/// Find edge specified by two vertices.  Return edges.size if the edge is not found.
 
376
///
 
377
// --------------------------------------------------------
 
378
 
 
379
size_t NonDestructiveTriMesh::get_edge_index(size_t vtx0, size_t vtx1) const
 
380
{
 
381
    assert( vtx0 < m_vertex_to_edge_map.size() );
 
382
    assert( vtx1 < m_vertex_to_edge_map.size() );
 
383
    
 
384
    const std::vector<size_t>& edges0 = m_vertex_to_edge_map[vtx0];
 
385
    const std::vector<size_t>& edges1 = m_vertex_to_edge_map[vtx1];
 
386
    
 
387
    for(size_t e0 = 0; e0 < edges0.size(); e0++)
 
388
    {
 
389
        size_t edge0 = edges0[e0];
 
390
        
 
391
        for(size_t e1 = 0; e1 < edges1.size(); e1++)
 
392
        {
 
393
            if( edge0 == edges1[e1] && m_edges[edge0][0] != m_edges[edge0][1] )
 
394
            {
 
395
                assert( ( m_edges[edge0][0] == vtx0 && m_edges[edge0][1] == vtx1 ) ||
 
396
                       ( m_edges[edge0][1] == vtx0 && m_edges[edge0][0] == vtx1 ) );
 
397
                
 
398
                return edge0;
 
399
            }
 
400
        }
 
401
    }
 
402
    
 
403
    return m_edges.size();
 
404
}
 
405
 
 
406
 
 
407
// --------------------------------------------------------
 
408
///
 
409
/// Find triangle specified by three vertices.  Return triangles.size if the triangle is not found.
 
410
///
 
411
// --------------------------------------------------------
 
412
 
 
413
size_t NonDestructiveTriMesh::get_triangle_index( size_t vtx0, size_t vtx1, size_t vtx2 ) const
 
414
{
 
415
    Vec3st verts( vtx0, vtx1, vtx2 );
 
416
    
 
417
    const std::vector<size_t>& triangles0 = m_vertex_to_triangle_map[vtx0];
 
418
    for ( size_t i = 0; i < triangles0.size(); ++i )
 
419
    {
 
420
        if ( triangle_has_these_verts( m_tris[triangles0[i]], verts ) )
 
421
        {
 
422
            return triangles0[i];
 
423
        }
 
424
    }
 
425
    
 
426
    return m_tris.size();
 
427
    
 
428
}
 
429
 
 
430
 
 
431
 
 
432
// --------------------------------------------------------
 
433
///
 
434
/// Remove triangles which have been deleted by nondestructive_remove_triangle
 
435
///
 
436
// --------------------------------------------------------
 
437
 
 
438
void NonDestructiveTriMesh::clear_deleted_triangles( std::vector<Vec2st>* defragged_triangle_map )
 
439
{  
 
440
    
 
441
    std::vector<Vec3st> new_tris;
 
442
    new_tris.reserve( m_tris.size() );
 
443
    
 
444
    if ( defragged_triangle_map != NULL )
 
445
    {
 
446
        for ( size_t i = 0; i < m_tris.size(); ++i )
 
447
        {
 
448
            if ( !triangle_is_deleted(i) ) 
 
449
            {
 
450
                new_tris.push_back( m_tris[i] );
 
451
                Vec2st map_entry(i, new_tris.size()-1);
 
452
                defragged_triangle_map->push_back( map_entry );
 
453
            }
 
454
        }
 
455
    }
 
456
    else
 
457
    {
 
458
        for ( size_t i = 0; i < m_tris.size(); ++i )
 
459
        {
 
460
            if ( !triangle_is_deleted(i) ) 
 
461
            {
 
462
                new_tris.push_back( m_tris[i] );
 
463
            }
 
464
        }      
 
465
    }
 
466
    
 
467
    replace_all_triangles( new_tris );
 
468
    
 
469
}
 
470
 
 
471
 
 
472
// --------------------------------------------------------
 
473
///
 
474
/// Remove auxiliary connectivity information
 
475
///
 
476
// --------------------------------------------------------
 
477
 
 
478
void NonDestructiveTriMesh::clear_connectivity()
 
479
{
 
480
    m_edges.clear();
 
481
    m_vertex_to_edge_map.clear();
 
482
    m_vertex_to_triangle_map.clear();
 
483
    m_edge_to_triangle_map.clear();
 
484
    m_triangle_to_edge_map.clear();
 
485
    m_is_boundary_edge.clear();
 
486
    m_is_boundary_vertex.clear();
 
487
    
 
488
}
 
489
 
 
490
 
 
491
// --------------------------------------------------------
 
492
///
 
493
/// Clear and rebuild connectivity information
 
494
///
 
495
// --------------------------------------------------------
 
496
 
 
497
void NonDestructiveTriMesh::update_connectivity( )
 
498
{
 
499
    
 
500
    clear_connectivity();
 
501
    
 
502
    size_t nv = 0;
 
503
    for ( size_t i = 0; i < m_tris.size(); ++i )
 
504
    {
 
505
        nv = max( nv, m_tris[i][0] );
 
506
        nv = max( nv, m_tris[i][1] );
 
507
        nv = max( nv, m_tris[i][2] );      
 
508
    }
 
509
    ++nv;
 
510
    
 
511
    m_vertex_to_triangle_map.resize(nv);
 
512
    m_vertex_to_edge_map.resize(nv);
 
513
    m_triangle_to_edge_map.resize(m_tris.size());
 
514
    
 
515
    for(size_t i = 0; i < m_tris.size(); i++)
 
516
    {
 
517
        Vec3st& t = m_tris[i];
 
518
        
 
519
        if(t[0] != t[1])
 
520
        {
 
521
            
 
522
            assert( t[0] < nv );
 
523
            assert( t[1] < nv );
 
524
            assert( t[2] < nv );
 
525
            
 
526
            for(unsigned int j = 0; j < 3; j++)
 
527
                m_vertex_to_triangle_map[t[j]].push_back(i);
 
528
            
 
529
            Vec3st& te = m_triangle_to_edge_map[i];
 
530
            
 
531
            for(int j = 0; j < 3; j++)
 
532
            {
 
533
                size_t vtx0 = t[j];
 
534
                size_t vtx1 = t[ i_plus_one_mod_three[j] ];
 
535
                
 
536
                size_t e = get_edge_index(vtx0, vtx1);
 
537
                
 
538
                if(e == m_edges.size())
 
539
                {
 
540
                    e = nondestructive_add_edge(vtx0, vtx1);
 
541
                }
 
542
                
 
543
                te[j] = e;
 
544
                m_edge_to_triangle_map[e].push_back(i);
 
545
            }
 
546
        }
 
547
    }
 
548
    
 
549
    // find boundary edges and vertices
 
550
    m_is_boundary_edge.resize( m_edges.size() );
 
551
    m_is_boundary_vertex.resize( nv, false );
 
552
    
 
553
    for ( size_t e = 0; e < m_edge_to_triangle_map.size(); ++e )
 
554
    {
 
555
        if ( m_edge_to_triangle_map[e].size() % 2 == 0 )
 
556
        {
 
557
            m_is_boundary_edge[e] = false;
 
558
        }
 
559
        else
 
560
        {
 
561
            m_is_boundary_edge[e] = true;
 
562
            m_is_boundary_vertex[ m_edges[e][0] ] = true;
 
563
            m_is_boundary_vertex[ m_edges[e][1] ] = true;
 
564
        }
 
565
    }
 
566
    
 
567
}
 
568
 
 
569
 
 
570
// --------------------------------------------------------
 
571
///
 
572
/// Check the consistency of auxiliary data structures
 
573
///
 
574
// --------------------------------------------------------
 
575
 
 
576
void NonDestructiveTriMesh::test_connectivity() const
 
577
{
 
578
    
 
579
    // check sizes
 
580
    
 
581
    assert( m_is_boundary_edge.size() == m_edges.size() );
 
582
    assert( m_edge_to_triangle_map.size() == m_edges.size() );
 
583
    
 
584
    assert( m_is_boundary_vertex.size() == m_vertex_to_edge_map.size() );
 
585
    assert( m_is_boundary_vertex.size() == m_vertex_to_triangle_map.size() );   
 
586
    
 
587
    assert( m_triangle_to_edge_map.size() == m_tris.size() );
 
588
    
 
589
    // m_is_boundary_edge
 
590
    
 
591
    for ( size_t i = 0; i < m_is_boundary_edge.size(); ++i )
 
592
    {
 
593
        if ( edge_is_deleted(i) ) { continue; }
 
594
        if ( m_is_boundary_edge[i] )
 
595
        {
 
596
            assert( m_edge_to_triangle_map[i].size() == 1 );
 
597
        }
 
598
        else
 
599
        {
 
600
            assert( m_edge_to_triangle_map[i].size() > 1 );
 
601
        }
 
602
    }
 
603
    
 
604
    // m_is_boundary_vertex
 
605
    
 
606
    for ( size_t i = 0; i < m_is_boundary_vertex.size(); ++i )
 
607
    {
 
608
        if ( vertex_is_deleted(i) ) { continue; }
 
609
        
 
610
        bool found_incident_boundary_edge = false;
 
611
        for ( size_t j = 0; j < m_vertex_to_edge_map[i].size(); ++j )
 
612
        {
 
613
            size_t inc_edge = m_vertex_to_edge_map[i][j];
 
614
            if ( m_is_boundary_edge[inc_edge] )
 
615
            {
 
616
                found_incident_boundary_edge = true;
 
617
            }
 
618
        }
 
619
        assert( m_is_boundary_vertex[i] == found_incident_boundary_edge );
 
620
    }
 
621
    
 
622
    // m_vertex_to_edge_map
 
623
    
 
624
    for ( size_t i = 0; i < m_vertex_to_edge_map.size(); ++i )
 
625
    {
 
626
        if ( vertex_is_deleted(i) ) { continue; }
 
627
        for ( size_t j = 0; j < m_vertex_to_edge_map[i].size(); ++j )
 
628
        {
 
629
            size_t inc_edge = m_vertex_to_edge_map[i][j];         
 
630
            assert( !edge_is_deleted( inc_edge ) );
 
631
            assert( m_edges[inc_edge][0] == i || m_edges[inc_edge][1] == i );
 
632
        }         
 
633
    }
 
634
    
 
635
    
 
636
    // m_vertex_to_triangle_map
 
637
    
 
638
    for ( size_t i = 0; i < m_vertex_to_triangle_map.size(); ++i )
 
639
    {
 
640
        if ( vertex_is_deleted(i) ) { continue; }
 
641
        for ( size_t j = 0; j < m_vertex_to_triangle_map[i].size(); ++j )
 
642
        {
 
643
            size_t inc_triangle = m_vertex_to_triangle_map[i][j];
 
644
            assert( m_tris[inc_triangle][0] == i || m_tris[inc_triangle][1] == i || m_tris[inc_triangle][2] == i );
 
645
        }         
 
646
    }
 
647
    
 
648
    // m_edge_to_triangle_map
 
649
    
 
650
    for ( size_t i = 0; i < m_edge_to_triangle_map.size(); ++i )
 
651
    {
 
652
        if ( edge_is_deleted(i) ) { continue; }
 
653
        for ( size_t j = 0; j < m_edge_to_triangle_map[i].size(); ++j )
 
654
        {
 
655
            size_t triangle_index = m_edge_to_triangle_map[i][j];
 
656
            size_t num_common_verts = 0;
 
657
            if ( m_tris[triangle_index][0] == m_edges[i][0] || m_tris[triangle_index][0] == m_edges[i][1] )
 
658
            {
 
659
                ++num_common_verts;
 
660
            }
 
661
            if ( m_tris[triangle_index][1] == m_edges[i][0] || m_tris[triangle_index][1] == m_edges[i][1] )
 
662
            {
 
663
                ++num_common_verts;
 
664
            }
 
665
            if ( m_tris[triangle_index][2] == m_edges[i][0] || m_tris[triangle_index][2] == m_edges[i][1] )
 
666
            {
 
667
                ++num_common_verts;
 
668
            }
 
669
            assert( num_common_verts == 2 );
 
670
        }
 
671
    }
 
672
    
 
673
    // m_triangle_to_edge_map
 
674
    
 
675
    for ( size_t i = 0; i < m_triangle_to_edge_map.size(); ++i )
 
676
    {
 
677
        if ( triangle_is_deleted(i) ) { continue; }
 
678
        
 
679
        const Vec3st& inc_edges = m_triangle_to_edge_map[i];
 
680
        
 
681
        const Vec2st& edge0 = m_edges[inc_edges[0]];
 
682
        const Vec2st& edge1 = m_edges[inc_edges[1]];
 
683
        const Vec2st& edge2 = m_edges[inc_edges[2]];
 
684
        
 
685
        assert( !edge_is_deleted( inc_edges[0] ) );
 
686
        assert( !edge_is_deleted( inc_edges[1] ) );
 
687
        assert( !edge_is_deleted( inc_edges[2] ) );
 
688
        
 
689
        assert( edge0[0] != edge0[1] );
 
690
        assert( edge1[0] != edge1[1] );
 
691
        assert( edge2[0] != edge2[1] );
 
692
        
 
693
        assert( edge0[0] == m_tris[i][0] || edge0[0] == m_tris[i][1] || edge0[0] == m_tris[i][2] );
 
694
        assert( edge0[1] == m_tris[i][0] || edge0[1] == m_tris[i][1] || edge0[1] == m_tris[i][2] );
 
695
        assert( edge1[0] == m_tris[i][0] || edge1[0] == m_tris[i][1] || edge1[0] == m_tris[i][2] );
 
696
        assert( edge1[1] == m_tris[i][0] || edge1[1] == m_tris[i][1] || edge1[1] == m_tris[i][2] );
 
697
        assert( edge2[0] == m_tris[i][0] || edge2[0] == m_tris[i][1] || edge2[0] == m_tris[i][2] );
 
698
        assert( edge2[1] == m_tris[i][0] || edge2[1] == m_tris[i][1] || edge2[1] == m_tris[i][2] );
 
699
    }
 
700
    
 
701
}
 
702
 
 
703
 
 
704
 
 
705
 
 
706