← Back to branch summary

~ubuntu-branches/ubuntu/saucy/blender/saucy-proposed

« back to all changes in this revision

Viewing changes to extern/eltopo/eltopo3d/meshpincher.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/meshpincher.cpp
1
 
// ---------------------------------------------------------
2
 
//
3
 
//  meshpincher.cpp
4
 
//  Tyson Brochu 2011
5
 
//  
6
 
//  Identifies "singular vertices", defined as having more than one connected triangle neighbourhoods, and
7
 
//  splits the mesh surface at these vertices.
8
 
//
9
 
// ---------------------------------------------------------
10
 
 
11
 
#include <meshpincher.h>
12
 
 
13
 
#include <broadphase.h>
14
 
#include <surftrack.h>
15
 
 
16
 
 
17
 
// ---------------------------------------------------------
18
 
// Member function definitions
19
 
// ---------------------------------------------------------
20
 
 
21
 
// --------------------------------------------------------
22
 
///
23
 
/// Partition the triangles incident to a vertex into connected components
24
 
///
25
 
// --------------------------------------------------------
26
 
 
27
 
void MeshPincher::partition_vertex_neighbourhood( size_t vertex_index, std::vector< TriangleSet >& connected_components )
28
 
{
29
 
    // triangles incident to vertex
30
 
        TriangleSet triangles_incident_to_vertex = m_surf.m_mesh.m_vertex_to_triangle_map[vertex_index];
31
 
        
32
 
    // unvisited triangles which are adjacent to some visited ones and incident to vt
33
 
    TriangleSet unvisited_triangles, visited_triangles;
34
 
    
35
 
    while ( triangles_incident_to_vertex.size() > 0 )
36
 
    {
37
 
        unvisited_triangles.clear();
38
 
        visited_triangles.clear();
39
 
        unvisited_triangles.push_back( triangles_incident_to_vertex.back() );
40
 
        
41
 
        while ( unvisited_triangles.size() > 0 )
42
 
        {
43
 
            // get an unvisited triangle
44
 
            size_t curr_tri = unvisited_triangles.back();
45
 
            unvisited_triangles.pop_back();
46
 
            
47
 
            // delete it from triangles_incident_to_vertex
48
 
            triangles_incident_to_vertex.erase( find(triangles_incident_to_vertex.begin(), triangles_incident_to_vertex.end(), curr_tri) );
49
 
            
50
 
            // put it on closed
51
 
            visited_triangles.push_back(curr_tri);
52
 
            
53
 
            // get find a triangle which is incident to vertex and adjacent to curr_tri
54
 
            for ( size_t i = 0; i < triangles_incident_to_vertex.size(); ++i )
55
 
            {
56
 
                size_t incident_triangle_index =  triangles_incident_to_vertex[i];
57
 
                
58
 
                if ( curr_tri == incident_triangle_index )
59
 
                {
60
 
                    continue;
61
 
                }
62
 
                
63
 
                if ( m_surf.m_mesh.triangles_are_adjacent( curr_tri, incident_triangle_index ) )
64
 
                {
65
 
                    // if not in visited_triangles or unvisited_triangles, put them on unvisited_triangles
66
 
                    if ( ( find(unvisited_triangles.begin(), unvisited_triangles.end(), incident_triangle_index) == unvisited_triangles.end() ) &&
67
 
                        ( find(visited_triangles.begin(), visited_triangles.end(), incident_triangle_index) == visited_triangles.end() ) ) 
68
 
                    {
69
 
                        unvisited_triangles.push_back( incident_triangle_index );
70
 
                    }
71
 
                }
72
 
            }
73
 
        }
74
 
        
75
 
        // one connected component = visited triangles
76
 
        connected_components.push_back(visited_triangles);
77
 
    }   
78
 
}
79
 
 
80
 
// --------------------------------------------------------
81
 
///
82
 
/// Duplicate a vertex and move the two copies away from each other slightly
83
 
///
84
 
// --------------------------------------------------------
85
 
 
86
 
bool MeshPincher::pull_apart_vertex( size_t vertex_index, const std::vector< TriangleSet >& connected_components )
87
 
{
88
 
    double dx = 10.0 * m_surf.m_proximity_epsilon;
89
 
    
90
 
    TriangleSet triangles_to_delete;
91
 
    std::vector< Vec3st > triangles_to_add;
92
 
    std::vector< size_t > vertices_added;
93
 
    
94
 
    // for each connected component except the last one, create a duplicate vertex
95
 
    for ( int i = 0; i < (int)connected_components.size() - 1; ++i )
96
 
    {
97
 
        // duplicate the vertex 
98
 
        size_t duplicate_vertex_index = m_surf.add_vertex( m_surf.get_position(vertex_index), m_surf.m_masses[vertex_index] );
99
 
        
100
 
        vertices_added.push_back( duplicate_vertex_index );
101
 
        
102
 
        Vec3d centroid( 0.0, 0.0, 0.0 );
103
 
        
104
 
        // map component triangles to the duplicate vertex
105
 
        for ( size_t t = 0; t < connected_components[i].size(); ++t ) 
106
 
        {
107
 
            // create a new triangle with 2 vertices the same, and one vertex set to the new duplicate vertex
108
 
            Vec3st new_triangle = m_surf.m_mesh.get_triangle( connected_components[i][t] ); 
109
 
            
110
 
            for ( unsigned short v = 0; v < 3; ++v ) 
111
 
            {
112
 
                if ( new_triangle[v] == vertex_index )
113
 
                {
114
 
                    new_triangle[v] = duplicate_vertex_index;
115
 
                }
116
 
                else
117
 
                {         
118
 
                    centroid += m_surf.get_position( new_triangle[v] );
119
 
                }
120
 
            }
121
 
            
122
 
            triangles_to_add.push_back( new_triangle );
123
 
            triangles_to_delete.push_back( connected_components[i][t] ); 
124
 
        }
125
 
        
126
 
        // compute the centroid    
127
 
        centroid /= ( connected_components[i].size() * 2 );
128
 
        
129
 
        // move the duplicate vertex towards the centroid
130
 
        
131
 
        Vec3d added_vertex_position = (1.0 - dx) * m_surf.get_position(duplicate_vertex_index) + dx * centroid;
132
 
        
133
 
        m_surf.set_position( duplicate_vertex_index, added_vertex_position );
134
 
        m_surf.set_newposition( duplicate_vertex_index, added_vertex_position );
135
 
        
136
 
    }
137
 
    
138
 
    // check new triangles for collision safety
139
 
    
140
 
    bool collision_occurs = false;
141
 
    
142
 
    if ( m_surf.m_collision_safety )
143
 
    {
144
 
        
145
 
        for ( size_t i = 0; i < triangles_to_add.size(); ++i ) 
146
 
        {
147
 
            const Vec3st& current_triangle = triangles_to_add[i];
148
 
            Vec3d low, high;
149
 
            
150
 
            minmax( m_surf.get_position(current_triangle[0]), m_surf.get_position(current_triangle[1]), m_surf.get_position(current_triangle[2]), low, high );
151
 
            
152
 
            std::vector<size_t> overlapping_triangles;
153
 
            m_surf.m_broad_phase->get_potential_triangle_collisions( low, high, true, true, overlapping_triangles );
154
 
            
155
 
            for ( size_t j=0; j < overlapping_triangles.size(); ++j )
156
 
            {        
157
 
                const Vec3st& tri_j = m_surf.m_mesh.get_triangle(overlapping_triangles[j]);
158
 
                
159
 
                assert( tri_j[0] != tri_j[1] );
160
 
                
161
 
                if ( check_triangle_triangle_intersection( current_triangle, tri_j, m_surf.get_positions() ) )
162
 
                {
163
 
                    // collision occurs - abort separation
164
 
                    collision_occurs = true;
165
 
                    break;
166
 
                }
167
 
            }
168
 
        }
169
 
        
170
 
        // check new triangles vs each other as well
171
 
        for ( size_t i = 0; i < triangles_to_add.size(); ++i ) 
172
 
        {
173
 
            for ( size_t j = i+1; j < triangles_to_add.size(); ++j ) 
174
 
            {
175
 
                if ( check_triangle_triangle_intersection( triangles_to_add[i], triangles_to_add[j], m_surf.get_positions() ) )
176
 
                {
177
 
                    // collision occurs - abort separation
178
 
                    collision_occurs = true;
179
 
                    break;
180
 
                }         
181
 
            }
182
 
        }
183
 
    }
184
 
    
185
 
    // abort separation, remove added vertices and return
186
 
    
187
 
    if ( collision_occurs )
188
 
    {
189
 
        for ( size_t i = 0; i < vertices_added.size(); ++i )
190
 
        {
191
 
            m_surf.remove_vertex( vertices_added[i] );
192
 
        }
193
 
        return false;
194
 
    }
195
 
    
196
 
    // all new triangles check out okay for collision safety.  Add them to the data structure.
197
 
    
198
 
    for ( size_t i = 0; i < triangles_to_add.size(); ++i )
199
 
    {
200
 
        m_surf.add_triangle( triangles_to_add[i] );
201
 
    }
202
 
    
203
 
    for ( size_t i = 0; i < triangles_to_delete.size(); ++i )
204
 
    {
205
 
        m_surf.remove_triangle( triangles_to_delete[i] );
206
 
    }
207
 
    
208
 
    
209
 
    if ( m_surf.m_collision_safety )
210
 
    {
211
 
        m_surf.assert_mesh_is_intersection_free(false);
212
 
    }
213
 
    
214
 
    if ( m_surf.m_verbose ) { std::cout << "pulled apart a vertex" << std::endl; }
215
 
    
216
 
    return true;
217
 
}
218
 
 
219
 
 
220
 
// --------------------------------------------------------
221
 
///
222
 
/// Find vertices with disconnected neighbourhoods, and pull them apart
223
 
///
224
 
// --------------------------------------------------------
225
 
 
226
 
void MeshPincher::separate_singular_vertices()
227
 
{
228
 
    
229
 
    for ( size_t i = 0; i < m_surf.get_num_vertices(); ++i )
230
 
    {
231
 
        // Partition the set of triangles adjacent to this vertex into connected components
232
 
        std::vector< TriangleSet > connected_components;
233
 
        partition_vertex_neighbourhood( i, connected_components );
234
 
        
235
 
        if ( connected_components.size() > 1 ) 
236
 
        {
237
 
            bool pinched = pull_apart_vertex( i, connected_components );
238
 
            if ( pinched )
239
 
            {
240
 
                // TODO: Shouldn't need this.
241
 
                m_surf.rebuild_continuous_broad_phase();
242
 
            }
243
 
        }
244
 
    }
245
 
}
246
 
 
247
 
 
248
 
 
249
 
 
250