1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
|
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
* OPCODE - Optimized Collision Detection
* Copyright (C) 2001 Pierre Terdiman
* Homepage: http://www.codercorner.com/Opcode.htm
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Contains code for a tree collider.
* \file OPC_TreeCollider.h
* \author Pierre Terdiman
* \date March, 20, 2001
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Include Guard
#ifndef __OPC_TREECOLLIDER_H__
#define __OPC_TREECOLLIDER_H__
//! This structure holds cached information used by the algorithm.
//! Two model pointers and two colliding primitives are cached. Model pointers are assigned
//! to their respective meshes, and the pair of colliding primitives is used for temporal
//! coherence. That is, in case temporal coherence is enabled, those two primitives are
//! tested for overlap before everything else. If they still collide, we're done before
//! even entering the recursive collision code.
struct OPCODE_API BVTCache : Pair
{
//! Constructor
__forceinline BVTCache()
{
ResetCache();
}
void ResetCache()
{
Model0 = null;
Model1 = null;
id0 = 0;
id1 = 1;
}
OPCODE_Model* Model0; //!< Model for first object
OPCODE_Model* Model1; //!< Model for second object
};
class OPCODE_API AABBTreeCollider
{
public:
// Constructor / Destructor
AABBTreeCollider();
~AABBTreeCollider();
// Generic collision query
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Generic collision query for generic OPCODE models. After the call, access the results with:
* - GetContactStatus()
* - GetNbPairs()
* - GetPairs()
*
* \param cache [in] collision cache for model pointers and a colliding pair of primitives
* \param world0 [in] world matrix for first object
* \param world1 [in] world matrix for second object
* \return true if success
* \warning SCALE NOT SUPPORTED. The matrices must contain rotation & translation parts only.
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool Collide(BVTCache& cache, const Matrix4x4& world0, const Matrix4x4& world1);
// Collision queries
bool Collide(const AABBCollisionTree* tree0, const AABBCollisionTree* tree1, const Matrix4x4& world0, const Matrix4x4& world1, Pair* cache=null);
bool Collide(const AABBNoLeafTree* tree0, const AABBNoLeafTree* tree1, const Matrix4x4& world0, const Matrix4x4& world1, Pair* cache=null);
bool Collide(const AABBQuantizedTree* tree0, const AABBQuantizedTree* tree1, const Matrix4x4& world0, const Matrix4x4& world1, Pair* cache=null);
bool Collide(const AABBQuantizedNoLeafTree* tree0, const AABBQuantizedNoLeafTree* tree1, const Matrix4x4& world0, const Matrix4x4& world1, Pair* cache=null);
// Settings
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Settings: select between full box-box tests or "SAT-lite" tests (where Class III axes are discarded)
* \param flag [in] true for full tests, false for coarse tests
* \see SetFullPrimBoxTest(bool flag)
* \see SetFirstContact(bool flag)
* \see SetTemporalCoherence(bool flag)
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline void SetFullBoxBoxTest(bool flag) { mFullBoxBoxTest = flag; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Settings: select between full triangle-box tests or "SAT-lite" tests (where Class III axes are discarded)
* \param flag [in] true for full tests, false for coarse tests
* \see SetFullBoxBoxTest(bool flag)
* \see SetFirstContact(bool flag)
* \see SetTemporalCoherence(bool flag)
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline void SetFullPrimBoxTest(bool flag) { mFullPrimBoxTest = flag; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Settings: reports all contacts (false) or first contact only (true)
* \param flag [in] true for first contact, false for all contacts
* \see SetFullBoxBoxTest(bool flag)
* \see SetFullPrimBoxTest(bool flag)
* \see SetTemporalCoherence(bool flag)
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline void SetFirstContact(bool flag) { mFirstContact = flag; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Settings: test pairs of colliding triangles from previous frame before anything else
* \param flag [in] true to enable temporal coherence, false to discard it
* \warning Only works in "First contact" mode, and currently wouldn't work in an N-body system (last pair is cached in AABBTreeCollider)
* \see SetFullBoxBoxTest(bool flag)
* \see SetFullPrimBoxTest(bool flag)
* \see SetFirstContact(bool flag)
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline void SetTemporalCoherence(bool flag) { mTemporalCoherence = flag; }
// Stats
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Stats: a method to get the number of BV-BV overlap tests after a collision query.
* \see GetNbPrimPrimTests()
* \see GetNbBVPrimTests()
* \return the number of BV-BV tests performed during last query
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline udword GetNbBVBVTests() const { return mNbBVBVTests; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Stats: a method to get the number of Triangle-Triangle overlap tests after a collision query.
* \see GetNbBVBVTests()
* \see GetNbBVPrimTests()
* \return the number of Triangle-Triangle tests performed during last query
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline udword GetNbPrimPrimTests() const { return mNbPrimPrimTests; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Stats: a method to get the number of BV-Triangle overlap tests after a collision query.
* \see GetNbBVBVTests()
* \see GetNbPrimPrimTests()
* \return the number of BV-Triangle tests performed during last query
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline udword GetNbBVPrimTests() const { return mNbBVPrimTests; }
// Data access
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* A method to get the number of contacts after a collision query.
* \see GetContactStatus()
* \see GetPairs()
* \return the number of contacts / colliding pairs.
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline udword GetNbPairs() const { return mPairs.GetNbEntries()>>1; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* A method to get the pairs of colliding triangles after a collision query.
* \see GetContactStatus()
* \see GetNbPairs()
* \return the list of colliding pairs (triangle indices)
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline Pair* GetPairs() const { return (Pair*)mPairs.GetEntries(); }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* A method to get the last collision status after a collision query.
* \see GetPairs()
* \see GetNbPairs()
* \return true if the objects overlap
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline bool GetContactStatus() const { return mContact; }
// Callback control
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Callback control: a method to setup user-data assigned to callback 0.
* \param data [in] user-defined data
* \see SetUserData1(udword data)
* \return Self-Reference
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline AABBTreeCollider& SetUserData0(udword data) { mUserData0 = data; return *this; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Callback control: a method to setup user-data assigned to callback 1.
* \param data [in] user-defined data
* \see SetUserData0(udword data)
* \return Self-Reference
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline AABBTreeCollider& SetUserData1(udword data) { mUserData1 = data; return *this; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Callback control: a method to setup callback 0. Must provide triangle-vertices for a given triangle index.
* \param callback [in] user-defined callback
* \see SetCallbackObj1(OPC_CALLBACK callback)
* \return Self-Reference
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline AABBTreeCollider& SetCallbackObj0(OPC_CALLBACK callback) { mObj0Callback = callback; return *this; }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Callback control: a method to setup callback 1. Must provide triangle-vertices for a given triangle index.
* \param callback [in] user-defined callback
* \see SetCallbackObj0(OPC_CALLBACK callback)
* \return Self-Reference
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
__forceinline AABBTreeCollider& SetCallbackObj1(OPC_CALLBACK callback) { mObj1Callback = callback; return *this; }
private:
// Colliding pairs
Container mPairs; //!< Pairs of colliding primitives
// User callback
udword mUserData0; //!< User-defined data sent to callbacks
udword mUserData1; //!< User-defined data sent to callbacks
OPC_CALLBACK mObj0Callback; //!< Callback for object 0
OPC_CALLBACK mObj1Callback; //!< Callback for object 1
// Stats
udword mNbBVBVTests; //!< Number of BV-BV tests
udword mNbPrimPrimTests; //!< Number of Primitive-Primitive tests
udword mNbBVPrimTests; //!< Number of BV-Primitive tests
// Precomputed data
Matrix3x3 mAR; //!< Absolute rotation matrix
Matrix3x3 mR0to1; //!< Rotation from object0 to object1
Matrix3x3 mR1to0; //!< Rotation from object1 to object0
Point mT0to1; //!< Translation from object0 to object1
Point mT1to0; //!< Translation from object1 to object0
// Dequantization coeffs
Point mCenterCoeff0;
Point mExtentsCoeff0;
Point mCenterCoeff1;
Point mExtentsCoeff1;
// Leaf description
Point mLeafVerts[3]; //!< Triangle vertices
udword mLeafIndex; //!< Triangle index
// Settings
bool mFullBoxBoxTest; //!< Perform full BV-BV tests (true) or SAT-lite tests (false)
bool mFullPrimBoxTest; //!< Perform full Primitive-BV tests (true) or SAT-lite tests (false)
bool mFirstContact; //!< Report all contacts (false) or only first one (true)
bool mTemporalCoherence; //!< Use temporal coherence or not
// Collision result
bool mContact; //!< Final contact status after a collision query
// Internal methods
// Standard AABB trees
void _Collide(const AABBCollisionNode* b0, const AABBCollisionNode* b1);
// Quantized AABB trees
void _Collide(const AABBQuantizedNode* b0, const AABBQuantizedNode* b1, const Point& a, const Point& Pa, const Point& b, const Point& Pb);
// No-leaf AABB trees
void _CollideTriBox(const AABBNoLeafNode* b);
void _CollideBoxTri(const AABBNoLeafNode* b);
void _Collide(const AABBNoLeafNode* a, const AABBNoLeafNode* b);
// Quantized no-leaf AABB trees
void _CollideTriBox(const AABBQuantizedNoLeafNode* b);
void _CollideBoxTri(const AABBQuantizedNoLeafNode* b);
void _Collide(const AABBQuantizedNoLeafNode* a, const AABBQuantizedNoLeafNode* b);
// Overlap tests
void PrimTest(udword id0, udword id1);
void PrimTestTriIndex(udword id1);
void PrimTestIndexTri(udword id0);
bool BoxBoxOverlap(const Point& a, const Point& Pa, const Point& b, const Point& Pb);
bool TriBoxOverlap(const Point& center, const Point& extents);
bool TriTriOverlap(const Point& V0, const Point& V1, const Point& V2, const Point& U0, const Point& U1, const Point& U2);
// Init methods
void InitQuery(const Matrix4x4& world0, const Matrix4x4& world1);
bool CheckTemporalCoherence(Pair* cache);
};
#endif // __OPC_TREECOLLIDER_H__
// END-OF-FILE\n
|
