← Back to branch summary

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

« back to all changes in this revision

Viewing changes to extern/eltopo/eltopo3d/surftrack.h

  • 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/surftrack.h
1
 
// ---------------------------------------------------------
2
 
//
3
 
//  surftrack.h
4
 
//  Tyson Brochu 2008
5
 
//  
6
 
//  The SurfTrack class: a dynamic mesh with topological changes and mesh maintenance operations.
7
 
//
8
 
// ---------------------------------------------------------
9
 
 
10
 
#ifndef EL_TOPO_SURFTRACK_H
11
 
#define EL_TOPO_SURFTRACK_H
12
 
 
13
 
#include <dynamicsurface.h>
14
 
#include <edgecollapser.h>
15
 
#include <edgeflipper.h>
16
 
#include <edgesplitter.h>
17
 
#include <meshmerger.h>
18
 
#include <meshpincher.h>
19
 
#include <meshsmoother.h>
20
 
 
21
 
// ---------------------------------------------------------
22
 
//  Forwards and typedefs
23
 
// ---------------------------------------------------------
24
 
 
25
 
class SubdivisionScheme;
26
 
typedef std::vector<size_t> TriangleSet;
27
 
 
28
 
// ---------------------------------------------------------
29
 
//  Class definitions
30
 
// ---------------------------------------------------------
31
 
 
32
 
// ---------------------------------------------------------
33
 
///
34
 
/// Structure for setting up a SurfTrack object with some initial parameters.  This is passed to the SurfTrack constructor.
35
 
///
36
 
// ---------------------------------------------------------
37
 
 
38
 
struct SurfTrackInitializationParameters
39
 
{
40
 
    
41
 
    ///  Constructor. Sets default values for parameters which are not likely to be specified.
42
 
    ///
43
 
    SurfTrackInitializationParameters();
44
 
    
45
 
    /// Elements closer than this are considered "near" (or proximate)
46
 
    ///
47
 
    double m_proximity_epsilon;
48
 
    
49
 
    /// Coefficient of friction to apply during collisions
50
 
    ///
51
 
    double m_friction_coefficient;
52
 
    
53
 
    /// Smallest triangle area to allow
54
 
    ///
55
 
    double m_min_triangle_area;
56
 
    
57
 
    /// Collision epsilon to use during mesh improvment operations (i.e. if any mesh elements are closer than this, the operation is 
58
 
    /// aborted).  NOTE: This should be greater than collision_epsilon, to prevent improvement operations from moving elements into 
59
 
    /// a collision configuration.
60
 
    ///
61
 
    double m_improve_collision_epsilon;
62
 
    
63
 
    /// Whether to set the min and max edge lengths as fractions of the initial average edge length
64
 
    ///
65
 
    bool m_use_fraction;
66
 
    
67
 
    // If use_fraction is true, the following three values are taken to be fractions of the average edge length of the new surface.
68
 
    // If use_fraction is false, these are absolute.
69
 
    
70
 
    /// Smallest edge length allowed
71
 
    ///
72
 
    double m_min_edge_length;
73
 
    
74
 
    /// Longest edge length allowed
75
 
    ///
76
 
    double m_max_edge_length; 
77
 
    
78
 
    /// Maximum change in volume allowed for one operation
79
 
    ///
80
 
    double m_max_volume_change;
81
 
    
82
 
    /// Smallest interior angle at a triangle vertex allowed
83
 
    ///
84
 
    double m_min_triangle_angle;
85
 
    
86
 
    /// Largest interior angle at a triangle vertex allowed
87
 
    ///
88
 
    double m_max_triangle_angle;   
89
 
    
90
 
    /// Whether to scale by curvature when computing edge lengths, in order to refine high-curvature regions
91
 
    ///
92
 
    bool m_use_curvature_when_splitting;
93
 
 
94
 
    /// Whether to scale by curvature when computing edge lengths, in order to coarsen low-curvature regions
95
 
    ///
96
 
    bool m_use_curvature_when_collapsing;
97
 
    
98
 
    /// The minimum curvature scaling allowed
99
 
    ///
100
 
    double m_min_curvature_multiplier;
101
 
    
102
 
    /// The maximum curvature scaling allowed
103
 
    ///
104
 
    double m_max_curvature_multiplier;
105
 
    
106
 
    /// Whether to allow vertices to move during improvement
107
 
    ///
108
 
    bool m_allow_vertex_movement;
109
 
    
110
 
    /// Minimum edge length improvement in order to flip an edge
111
 
    //
112
 
    double m_edge_flip_min_length_change;
113
 
    
114
 
    /// Elements within this distance will trigger a merge attempt   
115
 
    ///
116
 
    double m_merge_proximity_epsilon;
117
 
    
118
 
    /// Type of subdivision to use when collapsing or splitting (butterfly, quadric error minimization, etc.)
119
 
    ///
120
 
    SubdivisionScheme *m_subdivision_scheme;   
121
 
    
122
 
    /// Whether to enforce collision-free surfaces (including during mesh maintenance operations)
123
 
    ///
124
 
    bool m_collision_safety;
125
 
    
126
 
    /// Whether to allow changes in topology
127
 
    ///
128
 
    bool m_allow_topology_changes;
129
 
    
130
 
    /// Whether to allow non-manifold (edges incident on more than two triangles)
131
 
    ///
132
 
    bool m_allow_non_manifold;
133
 
    
134
 
    /// Whether to allow mesh improvement
135
 
    ///
136
 
    bool m_perform_improvement;
137
 
    
138
 
};
139
 
 
140
 
// ---------------------------------------------------------
141
 
///
142
 
/// Used to build a list of edges sorted in order of increasing length.
143
 
/// 
144
 
// ---------------------------------------------------------
145
 
 
146
 
struct SortableEdge
147
 
{    
148
 
    /// Constructor
149
 
    ///
150
 
    SortableEdge( size_t ei, double el ) : 
151
 
    m_edge_index(ei), 
152
 
    m_edge_length(el) 
153
 
    {}
154
 
    
155
 
    /// Comparison operator for sorting
156
 
    ///
157
 
    bool operator<( const SortableEdge& other ) const
158
 
    {
159
 
        return (this->m_edge_length < other.m_edge_length);
160
 
    }
161
 
    
162
 
    /// The index of the edge
163
 
    ///
164
 
    size_t m_edge_index;
165
 
    
166
 
    /// The stored edge length
167
 
    ///
168
 
    double m_edge_length;
169
 
 
170
 
};
171
 
 
172
 
 
173
 
// ---------------------------------------------------------
174
 
///
175
 
/// Keeps track of a vertex removal or addition.  If it's an addition, it also points to the edge that was split to create it.
176
 
///
177
 
// ---------------------------------------------------------
178
 
 
179
 
struct VertexUpdateEvent
180
 
{
181
 
    /// Constructor
182
 
    ///
183
 
    VertexUpdateEvent(bool is_remove = false, 
184
 
                      size_t vertex_index = (size_t)~0, 
185
 
                      const Vec2st& split_edge = Vec2st((size_t)~0) ) :
186
 
    m_is_remove( is_remove ),
187
 
    m_vertex_index( vertex_index ),
188
 
    m_split_edge( split_edge )
189
 
    {}
190
 
    
191
 
    /// Tag for identifying a vertex removal
192
 
    ///
193
 
    static const bool VERTEX_REMOVE = true;
194
 
    
195
 
    /// Tag for identifying a vertex addition
196
 
    ///
197
 
    static const bool VERTEX_ADD = false;
198
 
    
199
 
    /// Wether this event is a vertex removal
200
 
    ///
201
 
    bool m_is_remove;
202
 
    
203
 
    /// The index of the vertex being added or removed
204
 
    ///
205
 
    size_t m_vertex_index;   
206
 
    
207
 
    /// If this is a vertex addition due to edge splitting, the edge that was split
208
 
    ///
209
 
    Vec2st m_split_edge;
210
 
    
211
 
};
212
 
 
213
 
 
214
 
// ---------------------------------------------------------
215
 
///
216
 
/// Keeps track of a triangle removal or addition. If addition, contains the three vertices that form the new triangle.
217
 
///
218
 
// ---------------------------------------------------------
219
 
 
220
 
struct TriangleUpdateEvent
221
 
{
222
 
    /// Constructor
223
 
    ///
224
 
    TriangleUpdateEvent(bool is_remove = false, 
225
 
                        size_t triangle_index = (size_t)~0, 
226
 
                        const Vec3st& triangle = Vec3st((size_t)~0) ) :
227
 
    m_is_remove( is_remove ),
228
 
    m_triangle_index( triangle_index ),
229
 
    m_tri( triangle )
230
 
    {}
231
 
    
232
 
    /// Tag for identifying a triangle removal
233
 
    ///
234
 
    static const bool TRIANGLE_REMOVE = true;
235
 
    
236
 
    /// Tag for identifying a triangle addition
237
 
    ///
238
 
    static const bool TRIANGLE_ADD = false;
239
 
    
240
 
    /// Wether this event is a triangle removal
241
 
    ///
242
 
    bool m_is_remove;
243
 
    
244
 
    /// The index of the triangle being added or removed
245
 
    ///
246
 
    size_t m_triangle_index;  
247
 
    
248
 
    /// If this is a triangle addition, the triangle added
249
 
    ///
250
 
    Vec3st m_tri;
251
 
    
252
 
};
253
 
 
254
 
 
255
 
// ---------------------------------------------------------
256
 
///
257
 
/// A DynamicSurface with topological and mesh maintenance operations.
258
 
///
259
 
// ---------------------------------------------------------
260
 
 
261
 
class SurfTrack : public DynamicSurface
262
 
{
263
 
    
264
 
public:
265
 
    
266
 
    /// Create a SurfTrack object from a set of vertices and triangles using the specified paramaters
267
 
    ///
268
 
    SurfTrack(const std::vector<Vec3d>& vs, 
269
 
              const std::vector<Vec3st>& ts, 
270
 
              const std::vector<double>& masses,
271
 
              const SurfTrackInitializationParameters& initial_parameters );
272
 
    
273
 
    /// Destructor
274
 
    ///
275
 
    ~SurfTrack();
276
 
    
277
 
private:
278
 
    
279
 
    /// Disallow copying and assignment by declaring private
280
 
    ///
281
 
    SurfTrack( const SurfTrack& );
282
 
    
283
 
    /// Disallow copying and assignment by declaring private
284
 
    ///
285
 
    SurfTrack& operator=( const SurfTrack& );
286
 
    
287
 
    
288
 
public:
289
 
    
290
 
    //
291
 
    // Mesh bookkeeping
292
 
    //
293
 
    
294
 
    /// Add a triangle to the surface.  Update the underlying TriMesh and acceleration grid. 
295
 
    ///
296
 
    size_t add_triangle(const Vec3st& t);
297
 
    
298
 
    /// Remove a triangle from the surface.  Update the underlying TriMesh and acceleration grid. 
299
 
    ///
300
 
    void remove_triangle(size_t t);  
301
 
    
302
 
    /// Add a vertex to the surface.  Update the acceleration grid. 
303
 
    ///
304
 
    size_t add_vertex( const Vec3d& new_vertex_position, double new_vertex_mass );
305
 
    
306
 
    /// Remove a vertex from the surface.  Update the acceleration grid. 
307
 
    ///
308
 
    void remove_vertex(size_t v);
309
 
    
310
 
    /// Remove deleted vertices and triangles from the mesh data structures
311
 
    ///
312
 
    void defrag_mesh();
313
 
 
314
 
    //
315
 
    // Main operations
316
 
    //
317
 
    
318
 
    /// Run mesh maintenance operations
319
 
    ///
320
 
    void improve_mesh( );
321
 
    
322
 
    /// Run edge-edge merging
323
 
    ///
324
 
    void topology_changes( );
325
 
    
326
 
    //
327
 
    // Mesh cleanup
328
 
    //
329
 
    
330
 
    /// Check for and delete flaps and zero-area triangles among the given triangle indices, then separate singular vertices.
331
 
    ///
332
 
    void trim_non_manifold( std::vector<size_t>& triangle_indices );
333
 
    
334
 
    /// Check for and delete flaps and zero-area triangles among *all* triangles, then separate singular vertices.
335
 
    ///
336
 
    inline void trim_non_manifold();
337
 
    
338
 
    /// Fire an assert if any degenerate triangles or tets (flaps) are found.
339
 
    /// 
340
 
    void assert_no_degenerate_triangles();
341
 
    
342
 
    //
343
 
    // Member variables
344
 
    //
345
 
    
346
 
    /// Edge collapse operation object
347
 
    ///
348
 
    EdgeCollapser m_collapser;
349
 
    
350
 
    /// Edge split operation object
351
 
    ///
352
 
    EdgeSplitter m_splitter;
353
 
    
354
 
    /// Edge flip operation object
355
 
    ///
356
 
    EdgeFlipper m_flipper;
357
 
    
358
 
    /// NULL-space surface smoothing
359
 
    /// 
360
 
    MeshSmoother m_smoother;
361
 
    
362
 
    /// Surface merging object
363
 
    ///
364
 
    MeshMerger m_merger;
365
 
    
366
 
    /// Surface splitting operation object
367
 
    ///
368
 
    MeshPincher m_pincher;
369
 
    
370
 
    /// Collision epsilon to use during mesh improvment operations
371
 
    ///
372
 
    double m_improve_collision_epsilon;
373
 
    
374
 
    /// Minimum edge length improvement in order to flip an edge
375
 
    ///
376
 
    double m_edge_flip_min_length_change;
377
 
    
378
 
    /// Maximum volume change allowed when flipping or collapsing an edge
379
 
    ///
380
 
    double m_max_volume_change;
381
 
    
382
 
    /// Mimimum edge length.  Edges shorter than this will be collapsed.
383
 
    ///
384
 
    double m_min_edge_length;   
385
 
    
386
 
    /// Maximum edge length.  Edges longer than this will be subdivided.
387
 
    ///
388
 
    double m_max_edge_length;   
389
 
    
390
 
    /// Elements within this distance will trigger a merge attempt
391
 
    ///
392
 
    double m_merge_proximity_epsilon;
393
 
    
394
 
    /// Try to prevent triangles with area less than this
395
 
    ///
396
 
    double m_min_triangle_area;
397
 
    
398
 
    /// Don't create triangles with angles less than this.  If angles less than this do exist, try to remove them.
399
 
    ///
400
 
    double m_min_triangle_angle;
401
 
    
402
 
    /// Don't create triangles with angles greater than this.  If angles greater than this do exist, try to remove them.
403
 
    ///
404
 
    double m_max_triangle_angle;
405
 
    
406
 
    /// Interpolation scheme, determines edge midpoint location
407
 
    ///
408
 
    SubdivisionScheme *m_subdivision_scheme;
409
 
    
410
 
    /// If we allocate our own SubdivisionScheme object, we must delete it in this object's deconstructor.
411
 
    ///
412
 
    bool should_delete_subdivision_scheme_object;
413
 
    
414
 
    /// Triangles which are involved in connectivity changes which may introduce degeneracies
415
 
    ///
416
 
    std::vector<size_t> m_dirty_triangles;
417
 
    
418
 
    /// Whether to allow merging and separation
419
 
    ///
420
 
    bool m_allow_topology_changes;
421
 
    
422
 
    /// Whether to allow non-manifold (edges incident on more than two triangles)
423
 
    ///
424
 
    bool m_allow_non_manifold;
425
 
    
426
 
    /// Whether to perform adaptivity operations
427
 
    ///
428
 
    bool m_perform_improvement;
429
 
    
430
 
    /// When doing mesh optimization, whether to allow the vertices to move.  If set to false, we allow edge flipping, edge 
431
 
    /// splitting, and edge collapsing (where the edge is collapsed down to one of its endpoints).  If true, we do mesh smoothing,
432
 
    /// as well as allowing a collapsed edge to collapse down to some point other than an endpoint.
433
 
    ///
434
 
    bool m_allow_vertex_movement;
435
 
        
436
 
    /// History of vertex removal or addition events
437
 
    ///
438
 
    std::vector<VertexUpdateEvent> m_vertex_change_history;
439
 
    
440
 
    /// History of triangle removal or addition events
441
 
    ///    
442
 
    std::vector<TriangleUpdateEvent> m_triangle_change_history;
443
 
    
444
 
    /// Map of triangle indices, mapping pre-defrag triangle indices to post-defrag indices
445
 
    ///
446
 
    std::vector<Vec2st> m_defragged_triangle_map;
447
 
    
448
 
    /// Map of vertex indices, mapping pre-defrag vertex indices to post-defrag indices
449
 
    ///
450
 
    std::vector<Vec2st> m_defragged_vertex_map;
451
 
    
452
 
};
453
 
 
454
 
// ---------------------------------------------------------
455
 
//  Inline functions
456
 
// ---------------------------------------------------------
457
 
 
458
 
// ---------------------------------------------------------
459
 
///
460
 
/// Search the entire mesh for non-manifold elements and remove them
461
 
/// NOTE: SHOULD USE THE VERSION THAT ACCEPTS A SET OF TRIANGLE INDICES INSTEAD.
462
 
///
463
 
// ---------------------------------------------------------
464
 
 
465
 
inline void SurfTrack::trim_non_manifold()
466
 
{
467
 
    
468
 
    std::vector<size_t> triangle_indices;
469
 
    triangle_indices.resize( m_mesh.num_triangles() );
470
 
    for ( size_t i = 0; i < triangle_indices.size(); ++i )
471
 
    {
472
 
        triangle_indices[i] = i;
473
 
    }
474
 
    
475
 
    trim_non_manifold( triangle_indices );
476
 
}
477
 
 
478
 
#endif
479