← Back to branch summary

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

« back to all changes in this revision

Viewing changes to extern/eltopo/eltopo3d/broadphasegrid.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/broadphasegrid.h
1
 
// ---------------------------------------------------------
2
 
//
3
 
//  broadphasegrid.h
4
 
//  Tyson Brochu 2008
5
 
//  
6
 
//  Broad phase collision detection culling using three regular, volumetric grids.
7
 
//
8
 
// ---------------------------------------------------------
9
 
 
10
 
#ifndef EL_TOPO_BROADPHASEGRID_H
11
 
#define EL_TOPO_BROADPHASEGRID_H
12
 
 
13
 
// ---------------------------------------------------------
14
 
// Nested includes
15
 
// ---------------------------------------------------------
16
 
 
17
 
#include <broadphase.h>
18
 
#include <accelerationgrid.h>
19
 
 
20
 
// ---------------------------------------------------------
21
 
//  Forwards and typedefs
22
 
// ---------------------------------------------------------
23
 
 
24
 
class DynamicSurface;
25
 
 
26
 
// ---------------------------------------------------------
27
 
//  Class definitions
28
 
// ---------------------------------------------------------
29
 
 
30
 
// --------------------------------------------------------
31
 
///
32
 
/// Broad phase collision detector using three regular grids: one grid each for vertices, edges and triangles.
33
 
///
34
 
// --------------------------------------------------------
35
 
 
36
 
class BroadPhaseGrid : public BroadPhase
37
 
{
38
 
public:
39
 
    
40
 
    /// Default constructor, just initialize empty grids
41
 
    ///
42
 
    BroadPhaseGrid() :
43
 
    m_solid_vertex_grid(),
44
 
    m_solid_edge_grid(),
45
 
    m_solid_triangle_grid(),
46
 
    m_dynamic_vertex_grid(),
47
 
    m_dynamic_edge_grid(),
48
 
    m_dynamic_triangle_grid()
49
 
    {}
50
 
    
51
 
    
52
 
    /// Do-nothing destructor
53
 
    ///
54
 
    ~BroadPhaseGrid() 
55
 
    {}
56
 
    
57
 
    /// Rebuild the broad phase
58
 
    ///
59
 
    void update_broad_phase( const DynamicSurface& surface, bool continuous );
60
 
    
61
 
    /// Add a vertex with the specified bounding box to the broad phase
62
 
    ///
63
 
    inline void add_vertex( size_t index,
64
 
                           const Vec3d& aabb_low,
65
 
                           const Vec3d& aabb_high,
66
 
                           bool is_solid );
67
 
    
68
 
    /// Add an edge with the specified bounding box to the broad phase
69
 
    ///
70
 
    inline void add_edge( size_t index,
71
 
                         const Vec3d& aabb_low,
72
 
                         const Vec3d& aabb_high,
73
 
                         bool is_solid );
74
 
 
75
 
    /// Add a triangle with the specified bounding box to the broad phase
76
 
    ///
77
 
    inline void add_triangle( size_t index,
78
 
                             const Vec3d& aabb_low,
79
 
                             const Vec3d& aabb_high,
80
 
                             bool is_solid );
81
 
 
82
 
    /// Update a vertex's broad phase entry
83
 
    ///
84
 
    inline void update_vertex( size_t index,
85
 
                              const Vec3d& aabb_low,
86
 
                              const Vec3d& aabb_high,
87
 
                              bool is_solid );
88
 
    
89
 
    /// Update an edge's broad phase entry
90
 
    ///
91
 
    inline void update_edge( size_t index,
92
 
                            const Vec3d& aabb_low,
93
 
                            const Vec3d& aabb_high,
94
 
                            bool is_solid );
95
 
 
96
 
    /// Update a triangle's broad phase entry
97
 
    ///
98
 
    inline void update_triangle( size_t index,
99
 
                                const Vec3d& aabb_low,
100
 
                                const Vec3d& aabb_high,
101
 
                                bool is_solid );
102
 
 
103
 
    /// Remove a vertex from the broad phase
104
 
    ///
105
 
    inline void remove_vertex( size_t index );
106
 
    
107
 
    /// Remove an edge from the broad phase
108
 
    ///    
109
 
    inline void remove_edge( size_t index );
110
 
    
111
 
    /// Remove a triangle from the broad phase
112
 
    ///        
113
 
    inline void remove_triangle( size_t index ); 
114
 
    
115
 
    /// Get the stored axis-aligned bounding box of a vertex
116
 
    ///
117
 
    virtual void get_vertex_aabb( size_t index, bool is_solid, Vec3d& aabb_low, Vec3d& aabb_high );
118
 
    
119
 
    /// Get the stored axis-aligned bounding box of an edge
120
 
    ///
121
 
    virtual void get_edge_aabb( size_t index, bool is_solid, Vec3d& aabb_low, Vec3d& aabb_high );
122
 
    
123
 
    /// Get the stored axis-aligned bounding box of a triangle
124
 
    ///
125
 
    virtual void get_triangle_aabb( size_t index, bool is_solid, Vec3d& aabb_low, Vec3d& aabb_high );
126
 
    
127
 
    /// Get the set of vertices whose bounding volumes overlap the specified bounding volume
128
 
    ///
129
 
    inline void get_potential_vertex_collisions( const Vec3d& aabb_low, 
130
 
                                                const Vec3d& aabb_high,
131
 
                                                bool return_solid,
132
 
                                                bool return_dynamic,
133
 
                                                std::vector<size_t>& overlapping_vertices );
134
 
    
135
 
    /// Get the set of edges whose bounding volumes overlap the specified bounding volume
136
 
    ///
137
 
    inline void get_potential_edge_collisions( const Vec3d& aabb_low, 
138
 
                                              const Vec3d& aabb_high, 
139
 
                                              bool return_solid,
140
 
                                              bool return_dynamic,
141
 
                                              std::vector<size_t>& overlapping_edges );
142
 
    
143
 
    /// Get the set of triangles whose bounding volumes overlap the specified bounding volume
144
 
    ///
145
 
    inline void get_potential_triangle_collisions( const Vec3d& aabb_low, 
146
 
                                                  const Vec3d& aabb_high,
147
 
                                                  bool return_solid,
148
 
                                                  bool return_dynamic,
149
 
                                                  std::vector<size_t>& overlapping_triangles );
150
 
    
151
 
    /// Rebuild one of the grids
152
 
    ///
153
 
    void build_acceleration_grid( AccelerationGrid& grid, 
154
 
                                 std::vector<Vec3d>& xmins, 
155
 
                                 std::vector<Vec3d>& xmaxs,
156
 
                                 std::vector<size_t>& indices,
157
 
                                 double length_scale, 
158
 
                                 double grid_padding );
159
 
    
160
 
    /// Regular grids for solid mesh elements
161
 
    ///
162
 
    AccelerationGrid m_solid_vertex_grid;
163
 
    AccelerationGrid m_solid_edge_grid;
164
 
    AccelerationGrid m_solid_triangle_grid;
165
 
 
166
 
    /// Regular grids for dynamic mesh elements
167
 
    ///
168
 
    AccelerationGrid m_dynamic_vertex_grid;
169
 
    AccelerationGrid m_dynamic_edge_grid;
170
 
    AccelerationGrid m_dynamic_triangle_grid;
171
 
    
172
 
};
173
 
 
174
 
// ---------------------------------------------------------
175
 
//  Inline functions
176
 
// ---------------------------------------------------------
177
 
 
178
 
// --------------------------------------------------------
179
 
///
180
 
/// Add a vertex to the broad phase
181
 
///
182
 
// --------------------------------------------------------
183
 
 
184
 
inline void BroadPhaseGrid::add_vertex( size_t index, const Vec3d& aabb_low, const Vec3d& aabb_high, bool is_solid )
185
 
{
186
 
    if ( is_solid )
187
 
    {
188
 
        m_solid_vertex_grid.add_element( index, aabb_low, aabb_high );
189
 
    }
190
 
    else
191
 
    {
192
 
        m_dynamic_vertex_grid.add_element( index, aabb_low, aabb_high );
193
 
    }
194
 
}
195
 
 
196
 
// --------------------------------------------------------
197
 
///
198
 
/// Add an edge to the broad phase
199
 
///
200
 
// --------------------------------------------------------
201
 
 
202
 
inline void BroadPhaseGrid::add_edge( size_t index, const Vec3d& aabb_low, const Vec3d& aabb_high, bool is_solid )
203
 
{
204
 
    if ( is_solid )
205
 
    {
206
 
        m_solid_edge_grid.add_element( index, aabb_low, aabb_high );
207
 
    }
208
 
    else
209
 
    {
210
 
        m_dynamic_edge_grid.add_element( index, aabb_low, aabb_high );
211
 
    }
212
 
}
213
 
 
214
 
// --------------------------------------------------------
215
 
///
216
 
/// Add a triangle to the broad phase
217
 
///
218
 
// --------------------------------------------------------
219
 
 
220
 
inline void BroadPhaseGrid::add_triangle( size_t index, const Vec3d& aabb_low, const Vec3d& aabb_high, bool is_solid )
221
 
{
222
 
    if ( is_solid )
223
 
    {
224
 
        m_solid_triangle_grid.add_element( index, aabb_low, aabb_high );
225
 
    }
226
 
    else
227
 
    {
228
 
        m_dynamic_triangle_grid.add_element( index, aabb_low, aabb_high );
229
 
    }
230
 
}
231
 
 
232
 
 
233
 
// ---------------------------------------------------------
234
 
///
235
 
/// Update a vertex's broad phase entry
236
 
///
237
 
// ---------------------------------------------------------
238
 
 
239
 
inline void BroadPhaseGrid::update_vertex( size_t index, const Vec3d& aabb_low, const Vec3d& aabb_high, bool is_solid )
240
 
{
241
 
    if ( is_solid )
242
 
    {
243
 
        m_solid_vertex_grid.update_element( index, aabb_low, aabb_high );
244
 
    }
245
 
    else
246
 
    {
247
 
        m_dynamic_vertex_grid.update_element( index, aabb_low, aabb_high );
248
 
    }
249
 
}
250
 
 
251
 
// ---------------------------------------------------------
252
 
///
253
 
/// Update an edge's broad phase entry
254
 
///
255
 
// ---------------------------------------------------------
256
 
 
257
 
inline void BroadPhaseGrid::update_edge( size_t index, const Vec3d& aabb_low, const Vec3d& aabb_high, bool is_solid )
258
 
{
259
 
    if ( is_solid )
260
 
    {
261
 
        m_solid_edge_grid.update_element( index, aabb_low, aabb_high );
262
 
    }
263
 
    else
264
 
    {
265
 
        m_dynamic_edge_grid.update_element( index, aabb_low, aabb_high );
266
 
    }
267
 
}
268
 
 
269
 
// ---------------------------------------------------------
270
 
///
271
 
/// Update a triangle's broad phase entry
272
 
///
273
 
// ---------------------------------------------------------
274
 
 
275
 
inline void BroadPhaseGrid::update_triangle( size_t index, const Vec3d& aabb_low, const Vec3d& aabb_high, bool is_solid )
276
 
{
277
 
    if ( is_solid )
278
 
    {
279
 
        m_solid_triangle_grid.update_element( index, aabb_low, aabb_high );
280
 
    }
281
 
    else
282
 
    {
283
 
        m_dynamic_triangle_grid.update_element( index, aabb_low, aabb_high );
284
 
    }
285
 
}
286
 
 
287
 
 
288
 
// --------------------------------------------------------
289
 
///
290
 
/// Remove a vertex from the broad phase
291
 
///
292
 
// --------------------------------------------------------
293
 
 
294
 
inline void BroadPhaseGrid::remove_vertex( size_t index )
295
 
{
296
 
    m_solid_vertex_grid.remove_element( index );
297
 
    m_dynamic_vertex_grid.remove_element( index );
298
 
}
299
 
 
300
 
// --------------------------------------------------------
301
 
///
302
 
/// Remove an edge from the broad phase
303
 
///
304
 
// --------------------------------------------------------
305
 
 
306
 
inline void BroadPhaseGrid::remove_edge( size_t index )
307
 
{
308
 
    m_solid_edge_grid.remove_element( index );
309
 
    m_dynamic_edge_grid.remove_element( index );
310
 
}
311
 
 
312
 
// --------------------------------------------------------
313
 
///
314
 
/// Remove a triangle from the broad phase
315
 
///
316
 
// --------------------------------------------------------
317
 
 
318
 
inline void BroadPhaseGrid::remove_triangle( size_t index )
319
 
{
320
 
    m_solid_triangle_grid.remove_element( index );
321
 
    m_dynamic_triangle_grid.remove_element( index );
322
 
}
323
 
 
324
 
// --------------------------------------------------------
325
 
///
326
 
/// Query the broad phase to get the set of all vertices overlapping the given AABB
327
 
///
328
 
// --------------------------------------------------------
329
 
 
330
 
inline void BroadPhaseGrid::get_potential_vertex_collisions( const Vec3d& aabb_low,
331
 
                                                            const Vec3d& aabb_high,
332
 
                                                            bool return_solid,
333
 
                                                            bool return_dynamic,
334
 
                                                            std::vector<size_t>& overlapping_vertices )
335
 
{
336
 
    if ( return_solid )
337
 
    {
338
 
        m_solid_vertex_grid.find_overlapping_elements( aabb_low, aabb_high, overlapping_vertices );
339
 
    }
340
 
    
341
 
    if ( return_dynamic )
342
 
    {
343
 
        m_dynamic_vertex_grid.find_overlapping_elements( aabb_low, aabb_high, overlapping_vertices );
344
 
    }
345
 
}
346
 
 
347
 
// --------------------------------------------------------
348
 
///
349
 
/// Query the broad phase to get the set of all edges overlapping the given AABB
350
 
///
351
 
// --------------------------------------------------------
352
 
 
353
 
inline void BroadPhaseGrid::get_potential_edge_collisions( const Vec3d& aabb_low,
354
 
                                                          const Vec3d& aabb_high,
355
 
                                                          bool return_solid,
356
 
                                                          bool return_dynamic,
357
 
                                                          std::vector<size_t>& overlapping_edges )
358
 
{
359
 
    if ( return_solid )
360
 
    {
361
 
        m_solid_edge_grid.find_overlapping_elements( aabb_low, aabb_high, overlapping_edges );
362
 
    }
363
 
    
364
 
    if ( return_dynamic )
365
 
    {
366
 
        m_dynamic_edge_grid.find_overlapping_elements( aabb_low, aabb_high, overlapping_edges );
367
 
    }
368
 
}
369
 
 
370
 
// --------------------------------------------------------
371
 
///
372
 
/// Query the broad phase to get the set of all triangles overlapping the given AABB
373
 
///
374
 
// --------------------------------------------------------
375
 
 
376
 
inline void BroadPhaseGrid::get_potential_triangle_collisions( const Vec3d& aabb_low,
377
 
                                                              const Vec3d& aabb_high,
378
 
                                                              bool return_solid,
379
 
                                                              bool return_dynamic,
380
 
                                                              std::vector<size_t>& overlapping_triangles )
381
 
{
382
 
    if ( return_solid )
383
 
    {
384
 
        m_solid_triangle_grid.find_overlapping_elements( aabb_low, aabb_high, overlapping_triangles );
385
 
    }
386
 
    
387
 
    if ( return_dynamic )
388
 
    {
389
 
        m_dynamic_triangle_grid.find_overlapping_elements( aabb_low, aabb_high, overlapping_triangles );
390
 
    }
391
 
}
392
 
 
393
 
 
394
 
// ---------------------------------------------------------
395
 
///
396
 
/// Get the stored axis-aligned bounding box of a vertex
397
 
///
398
 
// ---------------------------------------------------------
399
 
 
400
 
inline void BroadPhaseGrid::get_vertex_aabb( size_t index, bool is_solid, Vec3d& aabb_low, Vec3d& aabb_high )
401
 
{
402
 
    if ( is_solid )
403
 
    {
404
 
        aabb_low = m_solid_vertex_grid.m_elementxmins[index];
405
 
        aabb_high = m_solid_vertex_grid.m_elementxmaxs[index];
406
 
    }
407
 
    else
408
 
    {
409
 
        aabb_low = m_dynamic_vertex_grid.m_elementxmins[index];
410
 
        aabb_high = m_dynamic_vertex_grid.m_elementxmaxs[index];      
411
 
    }
412
 
}
413
 
 
414
 
// ---------------------------------------------------------
415
 
///
416
 
/// Get the stored axis-aligned bounding box of an edge
417
 
///
418
 
// ---------------------------------------------------------
419
 
 
420
 
inline void BroadPhaseGrid::get_edge_aabb( size_t index, bool is_solid, Vec3d& aabb_low, Vec3d& aabb_high )
421
 
{
422
 
    if ( is_solid )
423
 
    {
424
 
        aabb_low = m_solid_edge_grid.m_elementxmins[index];
425
 
        aabb_high = m_solid_edge_grid.m_elementxmaxs[index];
426
 
    }
427
 
    else
428
 
    {
429
 
        aabb_low = m_dynamic_edge_grid.m_elementxmins[index];
430
 
        aabb_high = m_dynamic_edge_grid.m_elementxmaxs[index];      
431
 
    }
432
 
}
433
 
 
434
 
// ---------------------------------------------------------
435
 
///
436
 
/// Get the stored axis-aligned bounding box of a triangle
437
 
///
438
 
// ---------------------------------------------------------
439
 
 
440
 
inline void BroadPhaseGrid::get_triangle_aabb( size_t index, bool is_solid, Vec3d& aabb_low, Vec3d& aabb_high )
441
 
{
442
 
    if ( is_solid )
443
 
    {
444
 
        aabb_low = m_solid_triangle_grid.m_elementxmins[index];
445
 
        aabb_high = m_solid_triangle_grid.m_elementxmaxs[index];
446
 
    }
447
 
    else
448
 
    {
449
 
        aabb_low = m_dynamic_triangle_grid.m_elementxmins[index];
450
 
        aabb_high = m_dynamic_triangle_grid.m_elementxmaxs[index];      
451
 
    }   
452
 
}
453
 
 
454
 
 
455
 
#endif
456
 
 
457
 
 
458