← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

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

  • 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/collisionpipeline.h
 
1
// ---------------------------------------------------------
 
2
//
 
3
//  collisionpipeline.h
 
4
//  Tyson Brochu 2011
 
5
//  
 
6
//  Encapsulates all collision detection and resolution functions.
 
7
//
 
8
// ---------------------------------------------------------
 
9
 
 
10
#ifndef EL_TOPO_COLLISIONPIPELINE_H
 
11
#define EL_TOPO_COLLISIONPIPELINE_H
 
12
 
 
13
#include <deque>
 
14
#include <options.h>
 
15
#include <vec.h>
 
16
 
 
17
class BroadPhase;
 
18
class DynamicSurface;
 
19
struct ImpactZone;
 
20
 
 
21
// A potentially colliding pair of primitives.  Each pair is a triple of size_ts:
 
22
//  elements 0 and 1 are the indices of the primitives involved.
 
23
//  element 2 specifies if the potential collision is point-triangle or edge-edge
 
24
typedef std::deque<Vec3st> CollisionCandidateSet;
 
25
 
 
26
// --------------------------------------------------------
 
27
///
 
28
/// A collision between a triangle and a vertex or between two edges
 
29
///
 
30
// --------------------------------------------------------
 
31
 
 
32
struct Collision
 
33
{
 
34
    /// Default collision constructor
 
35
    ///
 
36
    Collision() :
 
37
    m_is_edge_edge( false ),
 
38
    m_vertex_indices( Vec4st(static_cast<size_t>(~0)) ),
 
39
    m_normal( Vec3d(UNINITIALIZED_DOUBLE) ),
 
40
    m_alphas( Vec4d(UNINITIALIZED_DOUBLE) ),
 
41
    m_relative_displacement( UNINITIALIZED_DOUBLE )
 
42
    {}   
 
43
    
 
44
    /// Collision constructor
 
45
    ///
 
46
    Collision( bool in_is_edge_edge, const Vec4st& in_vertex_indices, const Vec3d& in_normal, const Vec4d& in_alphas, double in_relative_displacement ) :
 
47
    m_is_edge_edge( in_is_edge_edge ),
 
48
    m_vertex_indices( in_vertex_indices ),
 
49
    m_normal( in_normal ),
 
50
    m_alphas( in_alphas ),
 
51
    m_relative_displacement( in_relative_displacement )
 
52
    {
 
53
        if ( !m_is_edge_edge ) { assert( m_alphas[0] == 1.0 ); }
 
54
    }
 
55
    
 
56
    /// Determine if one or more vertices is shared between this Collision and other
 
57
    ///
 
58
    inline bool overlap_vertices( const Collision& other ) const;
 
59
    
 
60
    /// Determine if ALL vertices are shared between this Collision and other
 
61
    ///
 
62
    inline bool same_vertices( const Collision& other ) const;
 
63
    
 
64
    /// Are the two elements both edges
 
65
    ///
 
66
    bool m_is_edge_edge;
 
67
    
 
68
    /// Which vertices are involved in the collision
 
69
    ///
 
70
    Vec4st m_vertex_indices;
 
71
    
 
72
    /// Collision normal
 
73
    ///
 
74
    Vec3d m_normal;
 
75
    
 
76
    /// Barycentric coordinates of the point of intersection
 
77
    ///
 
78
    Vec4d m_alphas;
 
79
    
 
80
    /// Magnitude of relative motion over the timestep
 
81
    ///
 
82
    double m_relative_displacement;
 
83
    
 
84
};
 
85
 
 
86
 
 
87
// --------------------------------------------------------
 
88
///
 
89
/// The results of processing a group of collision candidates.
 
90
///
 
91
// --------------------------------------------------------
 
92
 
 
93
struct ProcessCollisionStatus
 
94
{
 
95
    /// Constructor
 
96
    ///
 
97
    ProcessCollisionStatus() :
 
98
    collision_found( false ),
 
99
    overflow(false),
 
100
    all_candidates_processed( false )
 
101
    {}
 
102
    
 
103
    /// Whether one or more collisions was found.
 
104
    ///
 
105
    bool collision_found;
 
106
    
 
107
    /// Whether the number of collision candidates overflowed the candidate container.
 
108
    ///
 
109
    bool overflow;
 
110
    
 
111
    /// Whether all collision candidates were processed, or if the processing was terminated early.
 
112
    /// This is not necessarily equivalent to (!overflow): processing might stop early without overflow.
 
113
    ///
 
114
    bool all_candidates_processed;
 
115
    
 
116
};
 
117
 
 
118
 
 
119
// --------------------------------------------------------
 
120
///
 
121
/// Encapsulates all collision detection and resolution.
 
122
///
 
123
// --------------------------------------------------------
 
124
 
 
125
class CollisionPipeline
 
126
{
 
127
    
 
128
public:
 
129
    
 
130
    /// Constructor
 
131
    ///
 
132
    CollisionPipeline(DynamicSurface& surface,
 
133
                      BroadPhase& broadphase,
 
134
                      double in_friction_coefficient );
 
135
    
 
136
    /// Repulsion forces
 
137
    ///
 
138
    void handle_proximities( double dt );
 
139
    
 
140
    /// Sequential impulses
 
141
    ///
 
142
    bool handle_collisions( double dt );
 
143
    
 
144
    /// Get all collisions at once
 
145
    ///   
 
146
    bool detect_collisions( std::vector<Collision>& collisions );
 
147
    
 
148
    /// Get collisions involving vertices in the impact zones
 
149
    /// 
 
150
    bool detect_new_collisions( const std::vector<ImpactZone> impact_zones, 
 
151
                               std::vector<Collision>& collisions );
 
152
    
 
153
    /// Get any collisions involving an edge and a triangle
 
154
    ///
 
155
    void detect_collisions( size_t edge_index, size_t triangle_index, std::vector<Collision>& collisions );
 
156
    
 
157
    /// Re-check the elements in the specified collision objectto see if there is still a collision
 
158
    ///
 
159
    bool check_if_collision_persists( const Collision& collision );
 
160
    
 
161
    /// Friction coefficient to apply during collision resolution
 
162
    ///
 
163
    double m_friction_coefficient;
 
164
    
 
165
private: 
 
166
    
 
167
    friend class DynamicSurface;
 
168
    friend class EdgeCollapser;
 
169
    
 
170
    /// Apply a collision implulse between two edges
 
171
    /// 
 
172
    void apply_edge_edge_impulse( const Collision& collision, double impulse_magnitude, double dt );
 
173
 
 
174
    /// Apply a collision implulse between a triangle and a vertex
 
175
    /// 
 
176
    void apply_triangle_point_impulse( const Collision& collision, double impulse_magnitude, double dt );
 
177
    
 
178
    /// Apply a collision implulse to the specified vertices, weighted by the alphas, along the specified normal
 
179
    ///     
 
180
    void apply_impulse(const Vec4d& alphas, 
 
181
                       const Vec4st& vertex_indices, 
 
182
                       double impulse_magnitude, 
 
183
                       const Vec3d& normal,
 
184
                       double dt );
 
185
    
 
186
    /// Check all triangles for AABB overlaps against the specified vertex.
 
187
    ///
 
188
    void add_point_candidates(size_t vertex_index,
 
189
                              bool return_solid,
 
190
                              bool return_dynamic,
 
191
                              CollisionCandidateSet& collision_candidates );
 
192
 
 
193
    /// Check all edges for AABB overlaps against the specified edge.
 
194
    ///
 
195
    void add_edge_candidates(size_t edge_index,
 
196
                             bool return_solid,
 
197
                             bool return_dynamic,
 
198
                             CollisionCandidateSet& collision_candidates );
 
199
 
 
200
    /// Check all edges for AABB overlaps against the specified edge.
 
201
    ///
 
202
    void add_triangle_candidates(size_t triangle_index,
 
203
                                 bool return_solid,
 
204
                                 bool return_dynamic,
 
205
                                 CollisionCandidateSet& collision_candidates );
 
206
    
 
207
    /// Called when the specified vertex is moved.  Checks all incident mesh elements for AABB overlaps.
 
208
    ///
 
209
    void add_point_update_candidates(size_t vertex_index, 
 
210
                                     CollisionCandidateSet& collision_candidates );
 
211
    
 
212
    /// Run continuous collision detection on a pair of edges.
 
213
    ///
 
214
    bool detect_segment_segment_collision( const Vec3st& candidate, Collision& collision );
 
215
 
 
216
    /// Run continuous collision detection on a vertex-triangle pair.
 
217
    ///
 
218
    bool detect_point_triangle_collision( const Vec3st& candidate, Collision& collision );
 
219
    
 
220
    /// Test the candidates for proximity and apply impulses
 
221
    ///
 
222
    void process_proximity_candidates( double dt,
 
223
                                      CollisionCandidateSet& candidates );
 
224
    
 
225
    /// Test dynamic points vs. solid triangles for proximities, and apply repulsion forces
 
226
    /// 
 
227
    void dynamic_point_vs_solid_triangle_proximities(double dt);
 
228
 
 
229
    /// Test dynamic triangles vs. all vertices for proximities, and apply repulsion forces
 
230
    /// 
 
231
    void dynamic_triangle_vs_all_point_proximities(double dt);
 
232
    
 
233
    /// Test dynamic edges vs. all edges for proximities, and apply repulsion forces
 
234
    /// 
 
235
    void dynamic_edge_vs_all_edge_proximities(double dt);  
 
236
    
 
237
    
 
238
    /// Test the candidates and fix any collisions with impulses
 
239
    ///
 
240
    void process_collision_candidates(double dt,
 
241
                                      CollisionCandidateSet& candidates,
 
242
                                      bool add_to_new_candidates,
 
243
                                      CollisionCandidateSet& new_candidates,
 
244
                                      ProcessCollisionStatus& status );
 
245
    
 
246
    /// Test the candidates and return collision info
 
247
    ///
 
248
    void test_collision_candidates(CollisionCandidateSet& candidates,
 
249
                                   std::vector<Collision>& collisions,
 
250
                                   ProcessCollisionStatus& status );
 
251
    
 
252
    /// Check if any collision exists in the set of candidates.  Stop when the first collision is found.
 
253
    /// 
 
254
    bool any_collision( CollisionCandidateSet& candidates, Collision& collision );
 
255
    
 
256
    /// Check for collisions between dynamic points and solid triangles
 
257
    ///
 
258
    void dynamic_point_vs_solid_triangle_collisions(double dt,
 
259
                                                    bool collect_candidates,
 
260
                                                    CollisionCandidateSet& update_collision_candidates,
 
261
                                                    ProcessCollisionStatus& status );
 
262
    
 
263
    /// Check for collisions between dynamic triangles and all points
 
264
    ///
 
265
    void dynamic_triangle_vs_all_point_collisions(double dt,
 
266
                                                  bool collect_candidates,
 
267
                                                  CollisionCandidateSet& update_collision_candidates,
 
268
                                                  ProcessCollisionStatus& status );
 
269
    
 
270
    /// Check for collisions between dynamic edges and all other edges 
 
271
    ///
 
272
    void dynamic_edge_vs_all_edge_collisions( double dt,
 
273
                                             bool collect_candidates,
 
274
                                             CollisionCandidateSet& update_collision_candidates,
 
275
                                             ProcessCollisionStatus& status );
 
276
    
 
277
    DynamicSurface& m_surface;
 
278
    BroadPhase& m_broadphase;
 
279
    
 
280
};
 
281
 
 
282
// ---------------------------------------------------------
 
283
//  Inline functions
 
284
// ---------------------------------------------------------
 
285
 
 
286
// --------------------------------------------------------
 
287
///
 
288
/// Determine if another collision has any vertices in common with this collision.
 
289
///
 
290
// --------------------------------------------------------
 
291
 
 
292
inline bool Collision::overlap_vertices( const Collision& other ) const
 
293
{
 
294
    for ( unsigned short i = 0; i < 4; ++i )
 
295
    {
 
296
        if ( m_vertex_indices[i] == other.m_vertex_indices[0] || 
 
297
            m_vertex_indices[i] == other.m_vertex_indices[1] || 
 
298
            m_vertex_indices[i] == other.m_vertex_indices[2] || 
 
299
            m_vertex_indices[i] == other.m_vertex_indices[3] )
 
300
        {
 
301
            return true;
 
302
        }
 
303
    }
 
304
    
 
305
    return false;
 
306
}
 
307
 
 
308
// --------------------------------------------------------
 
309
///
 
310
/// Determine if another collision has all the same vertices as this collision.
 
311
///
 
312
// --------------------------------------------------------
 
313
 
 
314
inline bool Collision::same_vertices( const Collision& other ) const
 
315
{
 
316
    bool found[4];
 
317
    for ( unsigned short i = 0; i < 4; ++i )
 
318
    {
 
319
        if ( m_vertex_indices[i] == other.m_vertex_indices[0] || 
 
320
            m_vertex_indices[i] == other.m_vertex_indices[1] || 
 
321
            m_vertex_indices[i] == other.m_vertex_indices[2] || 
 
322
            m_vertex_indices[i] == other.m_vertex_indices[3] )
 
323
        {
 
324
            found[i] = true;
 
325
        }
 
326
        else
 
327
        {
 
328
            found[i] = false;
 
329
        }
 
330
    }
 
331
    
 
332
    return ( found[0] && found[1] && found[2] && found[3] );
 
333
}
 
334
 
 
335
 
 
336
 
 
337
#endif