← Back to branch summary

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

« back to all changes in this revision

Viewing changes to extern/eltopo/eltopo3d/meshmerger.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:
extern/eltopo/eltopo3d/meshmerger.cpp
1
 
// ---------------------------------------------------------
2
 
//
3
 
//  meshmerger.cpp
4
 
//  Tyson Brochu 2011
5
 
//  
6
 
//  Search for mesh edges which are near to each other, zipper their neighbouring triangles together.
7
 
//
8
 
// ---------------------------------------------------------
9
 
 
10
 
 
11
 
#include <meshmerger.h>
12
 
 
13
 
#include <broadphase.h>
14
 
#include <collisionqueries.h>
15
 
#include <queue>
16
 
#include <runstats.h>
17
 
#include <surftrack.h>
18
 
 
19
 
// ---------------------------------------------------------
20
 
//  Extern globals
21
 
// ---------------------------------------------------------
22
 
 
23
 
extern RunStats g_stats;
24
 
 
25
 
// ---------------------------------------------------------
26
 
// Member function definitions
27
 
// ---------------------------------------------------------
28
 
 
29
 
// --------------------------------------------------------
30
 
///
31
 
/// Move vertices around so v[0] and v[4] are closest together
32
 
///
33
 
// --------------------------------------------------------
34
 
 
35
 
void MeshMerger::twist_vertices( size_t *zipper_vertices )
36
 
{
37
 
    double min_dist = 1e+30, dist;
38
 
    Vec2st min_pair((size_t)~0, (size_t)~0);
39
 
    
40
 
    // find the closest pair among the 8 vertices
41
 
    for (int i=0; i<4; ++i) 
42
 
    {
43
 
        for (int j=4; j<8; ++j) 
44
 
        {
45
 
            dist = mag( m_surf.get_position(zipper_vertices[i]) - m_surf.get_position(zipper_vertices[j]) );
46
 
            if (dist < min_dist) 
47
 
            {
48
 
                min_dist = dist;
49
 
                min_pair[0] = i;
50
 
                min_pair[1] = j;
51
 
            }
52
 
        }
53
 
    }
54
 
    
55
 
    size_t new_vertices[8];
56
 
    for (int i=0; i<4; ++i) 
57
 
    {
58
 
        new_vertices[i]   = zipper_vertices[(min_pair[0] + i) % 4];
59
 
        new_vertices[i+4] = zipper_vertices[(min_pair[1] + i - 4) % 4 + 4];
60
 
    }
61
 
    
62
 
    memcpy( zipper_vertices, new_vertices, 8 * sizeof(size_t) );
63
 
    
64
 
}
65
 
 
66
 
// --------------------------------------------------------
67
 
///
68
 
/// Create a set of triangles to add to perform the zippering operation
69
 
///
70
 
// --------------------------------------------------------
71
 
 
72
 
bool MeshMerger::get_zipper_triangles( size_t edge_index_a, size_t edge_index_b, std::vector<Vec3st>& output_triangles )
73
 
{
74
 
    assert( output_triangles.size() == 8 );
75
 
    
76
 
    const Vec2st& edge_a = m_surf.m_mesh.m_edges[edge_index_a];
77
 
    const Vec2st& edge_b = m_surf.m_mesh.m_edges[edge_index_b];
78
 
    
79
 
    size_t zipper_vertices[8];
80
 
    
81
 
    zipper_vertices[0] = edge_a[0];
82
 
    zipper_vertices[2] = edge_a[1];
83
 
    zipper_vertices[4] = edge_b[0];
84
 
    zipper_vertices[6] = edge_b[1];
85
 
    
86
 
    const std::vector<size_t>& incident_triangles_a = m_surf.m_mesh.m_edge_to_triangle_map[edge_index_a];
87
 
    
88
 
    assert( incident_triangles_a.size() == 2 );       // should be checked before calling this function
89
 
    
90
 
    const Vec3st& inc_tri_a0 = m_surf.m_mesh.get_triangle( incident_triangles_a[0] );
91
 
    const Vec3st& inc_tri_a1 = m_surf.m_mesh.get_triangle( incident_triangles_a[1] );
92
 
    
93
 
    size_t third_vertices[2];
94
 
    third_vertices[0] = m_surf.m_mesh.get_third_vertex( zipper_vertices[0], zipper_vertices[2], inc_tri_a0 );
95
 
    third_vertices[1] = m_surf.m_mesh.get_third_vertex( zipper_vertices[0], zipper_vertices[2], inc_tri_a1 );
96
 
    
97
 
    if ( m_surf.m_mesh.oriented(zipper_vertices[0], zipper_vertices[2], inc_tri_a0 ) ) 
98
 
    {
99
 
        zipper_vertices[1] = third_vertices[0];
100
 
        zipper_vertices[3] = third_vertices[1];
101
 
    } 
102
 
    else if ( m_surf.m_mesh.oriented(zipper_vertices[0], zipper_vertices[2], inc_tri_a1) ) 
103
 
    {
104
 
        zipper_vertices[3] = third_vertices[0];
105
 
        zipper_vertices[1] = third_vertices[1];
106
 
    } 
107
 
    else 
108
 
    {
109
 
        // Should not happen
110
 
        std::cout << "Orientation check failed" << std::endl;
111
 
        assert( false );
112
 
    }
113
 
    
114
 
    const std::vector<size_t>& incident_triangles_b = m_surf.m_mesh.m_edge_to_triangle_map[edge_index_b];
115
 
    
116
 
    assert( incident_triangles_b.size() == 2 );       // should be checked before calling this function
117
 
    
118
 
    assert( edge_index_b < m_surf.m_mesh.m_edges.size() );
119
 
    
120
 
    const Vec2st& ce = m_surf.m_mesh.m_edges[edge_index_b];
121
 
    const std::vector<size_t>& et = m_surf.m_mesh.m_edge_to_triangle_map[edge_index_b];
122
 
    
123
 
    const Vec3st& inc_tri_b0 = m_surf.m_mesh.get_triangle( incident_triangles_b[0] );
124
 
    const Vec3st& inc_tri_b1 = m_surf.m_mesh.get_triangle( incident_triangles_b[1] );
125
 
    
126
 
    third_vertices[0] = m_surf.m_mesh.get_third_vertex( ce[0], ce[1], m_surf.m_mesh.get_triangle( et[0] ) );
127
 
    
128
 
    third_vertices[0] = m_surf.m_mesh.get_third_vertex( zipper_vertices[4], zipper_vertices[6], inc_tri_b0 );
129
 
    third_vertices[1] = m_surf.m_mesh.get_third_vertex( zipper_vertices[4], zipper_vertices[6], inc_tri_b1 );   
130
 
    
131
 
    if ( m_surf.m_mesh.oriented(zipper_vertices[4], zipper_vertices[6], inc_tri_b0) ) 
132
 
    {
133
 
        zipper_vertices[5] = third_vertices[0];
134
 
        zipper_vertices[7] = third_vertices[1];
135
 
    } 
136
 
    else if ( m_surf.m_mesh.oriented(zipper_vertices[4], zipper_vertices[6], inc_tri_b1) ) 
137
 
    {
138
 
        zipper_vertices[7] = third_vertices[0];
139
 
        zipper_vertices[5] = third_vertices[1];
140
 
    } 
141
 
    else 
142
 
    {
143
 
        // Should not happen
144
 
        std::cout << "Orientation check failed" << std::endl;
145
 
        assert( false );
146
 
    }
147
 
    
148
 
    // Check for degenerate case
149
 
    for ( unsigned int i = 0; i < 8; ++i) 
150
 
    {
151
 
        for ( unsigned int j = i+1; j < 8; ++j) 
152
 
        {
153
 
            
154
 
            if ( zipper_vertices[i] == zipper_vertices[j] )         // vertices not distinct
155
 
            {
156
 
                return false;
157
 
            }
158
 
            
159
 
            // Check if an edge already exists between two vertices in opposite edge neighbourhoods
160
 
            // (i.e. look for an edge which would be created by zippering)
161
 
            
162
 
            if ( (i < 4) && (j > 3) )
163
 
            {
164
 
                
165
 
                for ( size_t ii = 0; ii < m_surf.m_mesh.m_vertex_to_edge_map[ zipper_vertices[i] ].size(); ++ii )
166
 
                {
167
 
                    for ( size_t jj = 0; jj < m_surf.m_mesh.m_vertex_to_edge_map[ zipper_vertices[j] ].size(); ++jj )
168
 
                    {
169
 
                        if ( m_surf.m_mesh.m_vertex_to_edge_map[ zipper_vertices[i] ][ii] == m_surf.m_mesh.m_vertex_to_edge_map[ zipper_vertices[j] ][jj] )
170
 
                        {
171
 
                            return false;
172
 
                        }
173
 
                    }
174
 
                }
175
 
            }
176
 
            
177
 
        }
178
 
    }
179
 
    
180
 
    // Twist so that vertices 0 and 4 are the pair closest together
181
 
    twist_vertices( zipper_vertices );
182
 
    
183
 
    // now we can use a closed formula to construct zippering triangles
184
 
    
185
 
    output_triangles[0] = Vec3st( zipper_vertices[0], zipper_vertices[4], zipper_vertices[1] );  // a e b
186
 
    output_triangles[1] = Vec3st( zipper_vertices[1], zipper_vertices[4], zipper_vertices[7] );  // b e h
187
 
    output_triangles[2] = Vec3st( zipper_vertices[1], zipper_vertices[7], zipper_vertices[2] );  // b h c
188
 
    output_triangles[3] = Vec3st( zipper_vertices[2], zipper_vertices[7], zipper_vertices[6] );  // c h g
189
 
    output_triangles[4] = Vec3st( zipper_vertices[2], zipper_vertices[6], zipper_vertices[3] );  // c g d
190
 
    output_triangles[5] = Vec3st( zipper_vertices[3], zipper_vertices[6], zipper_vertices[5] );  // d g f
191
 
    output_triangles[6] = Vec3st( zipper_vertices[3], zipper_vertices[5], zipper_vertices[0] );  // d f a
192
 
    output_triangles[7] = Vec3st( zipper_vertices[0], zipper_vertices[5], zipper_vertices[4] );  // a f e
193
 
    
194
 
    return true;
195
 
}
196
 
 
197
 
 
198
 
// --------------------------------------------------------
199
 
///
200
 
/// Check whether the introduction of the new zippering triangles causes a collision 
201
 
///
202
 
// --------------------------------------------------------
203
 
 
204
 
bool MeshMerger::zippering_introduces_collision( const std::vector<Vec3st>& new_triangles, 
205
 
                                                const std::vector<size_t>& deleted_triangles )
206
 
{
207
 
    for ( size_t i = 0; i < new_triangles.size(); ++i )
208
 
    {
209
 
        // Check all existing edges vs new triangles
210
 
        Vec3d low, high;
211
 
        minmax(m_surf.get_position(new_triangles[i][0]), m_surf.get_position(new_triangles[i][1]), m_surf.get_position(new_triangles[i][2]), low, high);
212
 
        
213
 
        std::vector<size_t> overlapping_triangles;
214
 
        m_surf.m_broad_phase->get_potential_triangle_collisions( low, high, true, true, overlapping_triangles );
215
 
        
216
 
        const Vec3st& current_triangle = new_triangles[i];
217
 
        
218
 
        // Check to make sure there doesn't already exist triangles with the same vertices
219
 
        for ( size_t t = 0; t < overlapping_triangles.size(); ++t )      
220
 
        {
221
 
            const Vec3st& other_triangle = m_surf.m_mesh.get_triangle(overlapping_triangles[t]);
222
 
            
223
 
            if (    ((current_triangle[0] == other_triangle[0]) || (current_triangle[0] == other_triangle[1]) || (current_triangle[0] == other_triangle[2]))
224
 
                && ((current_triangle[1] == other_triangle[0]) || (current_triangle[1] == other_triangle[1]) || (current_triangle[1] == other_triangle[2]))
225
 
                && ((current_triangle[2] == other_triangle[0]) || (current_triangle[2] == other_triangle[1]) || (current_triangle[2] == other_triangle[2])) ) 
226
 
            {
227
 
                return true;
228
 
            }
229
 
        }
230
 
        
231
 
        // Check all existing triangles vs new triangles
232
 
        for ( size_t t = 0; t < overlapping_triangles.size(); ++t )      
233
 
        {
234
 
            bool go_to_next_triangle = false;
235
 
            for ( size_t d = 0; d < deleted_triangles.size(); ++d )
236
 
            {
237
 
                if ( overlapping_triangles[t] == deleted_triangles[d] )
238
 
                {
239
 
                    go_to_next_triangle = true;
240
 
                    break;
241
 
                }
242
 
            }
243
 
            if ( go_to_next_triangle )   
244
 
            { 
245
 
                continue; 
246
 
            }
247
 
            
248
 
            if ( check_triangle_triangle_intersection( new_triangles[i], 
249
 
                                                      m_surf.m_mesh.get_triangle(overlapping_triangles[t]), 
250
 
                                                      m_surf.get_positions() ) )
251
 
            {
252
 
                return true;
253
 
            }     
254
 
        }
255
 
        
256
 
        // Check new triangles vs each other
257
 
        for ( size_t j = 0; j < new_triangles.size(); ++j )
258
 
        {
259
 
            if ( i == j )  { continue; }
260
 
            
261
 
            if ( check_triangle_triangle_intersection( new_triangles[i], 
262
 
                                                      new_triangles[j], 
263
 
                                                      m_surf.get_positions() ) )
264
 
            {
265
 
                return true;
266
 
            }
267
 
        }      
268
 
    }
269
 
    
270
 
    // For real collision safety, we need to check for vertices inside the new, joined volume.  
271
 
    // Checking edges vs triangles is technically not enough.
272
 
    
273
 
    return false;
274
 
}
275
 
 
276
 
 
277
 
// --------------------------------------------------------
278
 
///
279
 
/// Attempt to merge between two edges
280
 
///
281
 
// --------------------------------------------------------
282
 
 
283
 
bool MeshMerger::zipper_edges( size_t edge_index_a, size_t edge_index_b )
284
 
{
285
 
    // For now we'll only zipper edges which are incident on 2 triangles
286
 
    if ( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_a].size() != 2 || m_surf.m_mesh.m_edge_to_triangle_map[edge_index_b].size() != 2 )
287
 
    {
288
 
        g_stats.add_to_int( "merge_non_manifold_edges", 1 );
289
 
        return false;
290
 
    }
291
 
    
292
 
    //
293
 
    // Get the set of 8 new triangles which will join the two holes in the mesh
294
 
    //
295
 
    
296
 
    std::vector<Vec3st> new_triangles;
297
 
    new_triangles.resize(8);
298
 
    if ( false == get_zipper_triangles( edge_index_a, edge_index_b, new_triangles ) )
299
 
    {
300
 
        g_stats.add_to_int( "merge_no_set_of_triangles", 1 );
301
 
        return false;
302
 
    }
303
 
    
304
 
    // Keep a list of triangles to delete
305
 
    std::vector<size_t> deleted_triangles;
306
 
    deleted_triangles.push_back( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_a][0] );
307
 
    deleted_triangles.push_back( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_a][1] );
308
 
    deleted_triangles.push_back( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_b][0] );
309
 
    deleted_triangles.push_back( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_b][1] );   
310
 
    
311
 
    //
312
 
    // Check the new triangles for collision safety, ignoring the triangles which will be deleted
313
 
    //
314
 
    
315
 
    bool saved_verbose = m_surf.m_verbose;
316
 
    m_surf.m_verbose = false;
317
 
    
318
 
    if ( m_surf.m_collision_safety && zippering_introduces_collision( new_triangles, deleted_triangles ) )
319
 
    {
320
 
        m_surf.m_verbose = saved_verbose;
321
 
        g_stats.add_to_int( "merge_not_intersection_safe", 1 );
322
 
        return false;
323
 
    }
324
 
    
325
 
    m_surf.m_verbose = saved_verbose;
326
 
    
327
 
    //
328
 
    // Add the new triangles
329
 
    //
330
 
    
331
 
    size_t new_index = m_surf.add_triangle( new_triangles[0] );
332
 
    m_surf.m_dirty_triangles.push_back( new_index );
333
 
    new_index = m_surf.add_triangle( new_triangles[1] );
334
 
    m_surf.m_dirty_triangles.push_back( new_index );
335
 
    new_index = m_surf.add_triangle( new_triangles[2] );
336
 
    m_surf.m_dirty_triangles.push_back( new_index );
337
 
    new_index = m_surf.add_triangle( new_triangles[3] );
338
 
    m_surf.m_dirty_triangles.push_back( new_index );
339
 
    new_index = m_surf.add_triangle( new_triangles[4] );
340
 
    m_surf.m_dirty_triangles.push_back( new_index );
341
 
    new_index = m_surf.add_triangle( new_triangles[5] );
342
 
    m_surf.m_dirty_triangles.push_back( new_index );
343
 
    new_index = m_surf.add_triangle( new_triangles[6] );
344
 
    m_surf.m_dirty_triangles.push_back( new_index );
345
 
    new_index = m_surf.add_triangle( new_triangles[7] );
346
 
    m_surf.m_dirty_triangles.push_back( new_index );
347
 
    
348
 
    //
349
 
    // Remove the old triangles
350
 
    //
351
 
    
352
 
    m_surf.remove_triangle( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_a][0] );
353
 
    m_surf.remove_triangle( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_a][0] );
354
 
    m_surf.remove_triangle( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_b][0] );
355
 
    m_surf.remove_triangle( m_surf.m_mesh.m_edge_to_triangle_map[edge_index_b][0] );
356
 
    
357
 
    return true;
358
 
    
359
 
}
360
 
 
361
 
 
362
 
// ---------------------------------------------------------
363
 
///
364
 
/// Look for pairs of edges close to each other, attempting to merge when close edges are found.
365
 
///
366
 
// ---------------------------------------------------------
367
 
 
368
 
bool MeshMerger::merge_pass( )
369
 
{
370
 
    
371
 
    std::queue<Vec2st> edge_edge_candidates;
372
 
    
373
 
    //
374
 
    // Check edge-edge proximities for zippering candidates
375
 
    //
376
 
    
377
 
    bool merge_occured = false;
378
 
    
379
 
    // sorted by proximity so we merge closest pairs first
380
 
    std::vector<SortableEdgeEdgeProximity> proximities;
381
 
    
382
 
    for(size_t i = 0; i < m_surf.m_mesh.m_edges.size(); i++)
383
 
    {
384
 
        const Vec2st& e0 = m_surf.m_mesh.m_edges[i];
385
 
        
386
 
        if ( e0[0] == e0[1] ) { continue; }
387
 
        if ( m_surf.edge_is_solid(i) ) { continue; }
388
 
        
389
 
        if ( m_surf.m_mesh.m_is_boundary_vertex[ e0[0] ] || m_surf.m_mesh.m_is_boundary_vertex[ e0[1] ] )  { continue; }  // skip boundary vertices
390
 
        
391
 
        Vec3d emin, emax;
392
 
        m_surf.edge_static_bounds(i, emin, emax);
393
 
        emin -= m_surf.m_merge_proximity_epsilon * Vec3d(1,1,1);
394
 
        emax += m_surf.m_merge_proximity_epsilon * Vec3d(1,1,1);
395
 
        
396
 
        std::vector<size_t> edge_candidates;
397
 
        m_surf.m_broad_phase->get_potential_edge_collisions( emin, emax, false, true, edge_candidates );
398
 
        
399
 
        for(size_t j = 0; j < edge_candidates.size(); j++)
400
 
        {
401
 
            size_t proximal_edge_index = edge_candidates[j];
402
 
            const Vec2st& e1 = m_surf.m_mesh.m_edges[proximal_edge_index];
403
 
            
404
 
            if ( proximal_edge_index <= i )
405
 
            {
406
 
                continue;
407
 
            }
408
 
            
409
 
            if ( m_surf.m_mesh.m_is_boundary_vertex[ e1[0] ] || m_surf.m_mesh.m_is_boundary_vertex[ e1[1] ] )  { continue; }  // skip boundary vertices
410
 
            
411
 
            if(e0[0] != e1[0] && e0[0] != e1[1] && e0[1] != e1[0] && e0[1] != e1[1])
412
 
            {
413
 
                double distance, s0, s2;
414
 
                Vec3d normal;
415
 
                
416
 
                check_edge_edge_proximity( m_surf.get_position(e0[0]), 
417
 
                                          m_surf.get_position(e0[1]), 
418
 
                                          m_surf.get_position(e1[0]), 
419
 
                                          m_surf.get_position(e1[1]), 
420
 
                                          distance, s0, s2, normal );
421
 
                
422
 
                if (distance < m_surf.m_merge_proximity_epsilon)
423
 
                {
424
 
                    
425
 
                    if ( m_surf.m_verbose ) 
426
 
                    { 
427
 
                        std::cout << "proximity: " << distance << " / " << m_surf.m_merge_proximity_epsilon << std::endl; //proximities[i].distance << std::endl; 
428
 
                    }
429
 
                    
430
 
                    if ( zipper_edges( i, proximal_edge_index ) )
431
 
                    {
432
 
                        
433
 
                        m_surf.trim_non_manifold( m_surf.m_dirty_triangles );
434
 
                        
435
 
                        if ( m_surf.m_verbose ) 
436
 
                        { 
437
 
                            std::cout << "zippered" << std::endl; 
438
 
                        }
439
 
                        
440
 
                        merge_occured = true;
441
 
                        
442
 
                        g_stats.add_to_int( "merge_success", 1 );
443
 
                    }
444
 
                    else
445
 
                    {
446
 
                        g_stats.add_to_int( "merge_failed", 1 );
447
 
                    }
448
 
                    
449
 
                }
450
 
            }
451
 
        }
452
 
    }
453
 
    
454
 
    
455
 
    if ( merge_occured )
456
 
    {
457
 
        m_surf.assert_no_degenerate_triangles();
458
 
    }
459
 
    
460
 
    return merge_occured;
461
 
    
462
 
    
463
 
}