aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/ode-0.9/OPCODE/OPC_HybridModel.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/ode-0.9/OPCODE/OPC_HybridModel.cpp')
-rw-r--r--libraries/ode-0.9/OPCODE/OPC_HybridModel.cpp466
1 files changed, 466 insertions, 0 deletions
diff --git a/libraries/ode-0.9/OPCODE/OPC_HybridModel.cpp b/libraries/ode-0.9/OPCODE/OPC_HybridModel.cpp
new file mode 100644
index 0000000..7016219
--- /dev/null
+++ b/libraries/ode-0.9/OPCODE/OPC_HybridModel.cpp
@@ -0,0 +1,466 @@
1///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2/*
3 * OPCODE - Optimized Collision Detection
4 * Copyright (C) 2001 Pierre Terdiman
5 * Homepage: http://www.codercorner.com/Opcode.htm
6 */
7///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
8
9///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
10/**
11 * Contains code for hybrid models.
12 * \file OPC_HybridModel.cpp
13 * \author Pierre Terdiman
14 * \date May, 18, 2003
15 */
16///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17
18///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
19/**
20 * An hybrid collision model.
21 *
22 * The problem :
23 *
24 * Opcode really shines for mesh-mesh collision, especially when meshes are deeply overlapping
25 * (it typically outperforms RAPID in those cases).
26 *
27 * Unfortunately this is not the typical scenario in games.
28 *
29 * For close-proximity cases, especially for volume-mesh queries, it's relatively easy to run faster
30 * than Opcode, that suffers from a relatively high setup time.
31 *
32 * In particular, Opcode's "vanilla" trees in those cases -can- run faster. They can also use -less-
33 * memory than the optimized ones, when you let the system stop at ~10 triangles / leaf for example
34 * (i.e. when you don't use "complete" trees). However, those trees tend to fragment memory quite a
35 * lot, increasing cache misses : since they're not "complete", we can't predict the final number of
36 * nodes and we have to allocate nodes on-the-fly. For the same reasons we can't use Opcode's "optimized"
37 * trees here, since they rely on a known layout to perform the "optimization".
38 *
39 * Hybrid trees :
40 *
41 * Hybrid trees try to combine best of both worlds :
42 *
43 * - they use a maximum limit of 16 triangles/leaf. "16" is used so that we'll be able to save the
44 * number of triangles using 4 bits only.
45 *
46 * - they're still "complete" trees thanks to a two-passes building phase. First we create a "vanilla"
47 * AABB-tree with Opcode, limited to 16 triangles/leaf. Then we create a *second* vanilla tree, this
48 * time using the leaves of the first one. The trick is : this second tree is now "complete"... so we
49 * can further transform it into an Opcode's optimized tree.
50 *
51 * - then we run the collision queries on that standard Opcode tree. The only difference is that leaf
52 * nodes contain indices to leaf nodes of another tree. Also, we have to skip all primitive tests in
53 * Opcode optimized trees, since our leaves don't contain triangles anymore.
54 *
55 * - finally, for each collided leaf, we simply loop through 16 triangles max, and collide them with
56 * the bounding volume used in the query (we only support volume-vs-mesh queries here, not mesh-vs-mesh)
57 *
58 * All of that is wrapped in this "hybrid model" that contains the minimal data required for this to work.
59 * It's a mix between old "vanilla" trees, and old "optimized" trees.
60 *
61 * Extra advantages:
62 *
63 * - If we use them for dynamic models, we're left with a very small number of leaf nodes to refit. It
64 * might be a bit faster since we have less nodes to write back.
65 *
66 * - In rigid body simulation, using temporal coherence and sleeping objects greatly reduce the actual
67 * influence of one tree over another (i.e. the speed difference is often invisible). So memory is really
68 * the key element to consider, and in this regard hybrid trees are just better.
69 *
70 * Information to take home:
71 * - they use less ram
72 * - they're not slower (they're faster or slower depending on cases, overall there's no significant
73 * difference *as long as objects don't interpenetrate too much* - in which case Opcode's optimized trees
74 * are still notably faster)
75 *
76 * \class HybridModel
77 * \author Pierre Terdiman
78 * \version 1.3
79 * \date May, 18, 2003
80*/
81///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
82
83///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
84// Precompiled Header
85#include "Stdafx.h"
86
87using namespace Opcode;
88
89///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
90/**
91 * Constructor.
92 */
93///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
94HybridModel::HybridModel() :
95 mNbLeaves (0),
96 mNbPrimitives (0),
97 mTriangles (null),
98 mIndices (null)
99{
100}
101
102///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
103/**
104 * Destructor.
105 */
106///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
107HybridModel::~HybridModel()
108{
109 Release();
110}
111
112///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
113/**
114 * Releases everything.
115 */
116///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
117void HybridModel::Release()
118{
119 ReleaseBase();
120 DELETEARRAY(mIndices);
121 DELETEARRAY(mTriangles);
122 mNbLeaves = 0;
123 mNbPrimitives = 0;
124}
125
126 struct Internal
127 {
128 Internal()
129 {
130 mNbLeaves = 0;
131 mLeaves = null;
132 mTriangles = null;
133 mBase = null;
134 }
135 ~Internal()
136 {
137 DELETEARRAY(mLeaves);
138 }
139
140 udword mNbLeaves;
141 AABB* mLeaves;
142 LeafTriangles* mTriangles;
143 const udword* mBase;
144 };
145
146///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
147/**
148 * Builds a collision model.
149 * \param create [in] model creation structure
150 * \return true if success
151 */
152///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
153bool HybridModel::Build(const OPCODECREATE& create)
154{
155 // 1) Checkings
156 if(!create.mIMesh || !create.mIMesh->IsValid()) return false;
157
158 // Look for degenerate faces.
159 udword NbDegenerate = create.mIMesh->CheckTopology();
160 if(NbDegenerate) Log("OPCODE WARNING: found %d degenerate faces in model! Collision might report wrong results!\n", NbDegenerate);
161 // We continue nonetheless....
162
163 Release(); // Make sure previous tree has been discarded
164
165 // 1-1) Setup mesh interface automatically
166 SetMeshInterface(create.mIMesh);
167
168 bool Status = false;
169 AABBTree* LeafTree = null;
170 Internal Data;
171
172 // 2) Build a generic AABB Tree.
173 mSource = new AABBTree;
174 CHECKALLOC(mSource);
175
176 // 2-1) Setup a builder. Our primitives here are triangles from input mesh,
177 // so we use an AABBTreeOfTrianglesBuilder.....
178 {
179 AABBTreeOfTrianglesBuilder TB;
180 TB.mIMesh = create.mIMesh;
181 TB.mNbPrimitives = create.mIMesh->GetNbTriangles();
182 TB.mSettings = create.mSettings;
183 TB.mSettings.mLimit = 16; // ### Hardcoded, but maybe we could let the user choose 8 / 16 / 32 ...
184 if(!mSource->Build(&TB)) goto FreeAndExit;
185 }
186
187 // 2-2) Here's the trick : create *another* AABB tree using the leaves of the first one (which are boxes, this time)
188 struct Local
189 {
190 // A callback to count leaf nodes
191 static bool CountLeaves(const AABBTreeNode* current, udword depth, void* user_data)
192 {
193 if(current->IsLeaf())
194 {
195 Internal* Data = (Internal*)user_data;
196 Data->mNbLeaves++;
197 }
198 return true;
199 }
200
201 // A callback to setup leaf nodes in our internal structures
202 static bool SetupLeafData(const AABBTreeNode* current, udword depth, void* user_data)
203 {
204 if(current->IsLeaf())
205 {
206 Internal* Data = (Internal*)user_data;
207
208 // Get current leaf's box
209 Data->mLeaves[Data->mNbLeaves] = *current->GetAABB();
210
211 // Setup leaf data
212 udword Index = udword((size_t(current->GetPrimitives()) - size_t(Data->mBase)) / sizeof(udword));
213 Data->mTriangles[Data->mNbLeaves].SetData(current->GetNbPrimitives(), Index);
214
215 Data->mNbLeaves++;
216 }
217 return true;
218 }
219 };
220
221 // Walk the tree & count number of leaves
222 Data.mNbLeaves = 0;
223 mSource->Walk(Local::CountLeaves, &Data);
224 mNbLeaves = Data.mNbLeaves; // Keep track of it
225
226 // Special case for 1-leaf meshes
227 if(mNbLeaves==1)
228 {
229 mModelCode |= OPC_SINGLE_NODE;
230 Status = true;
231 goto FreeAndExit;
232 }
233
234 // Allocate our structures
235 Data.mLeaves = new AABB[Data.mNbLeaves]; CHECKALLOC(Data.mLeaves);
236 mTriangles = new LeafTriangles[Data.mNbLeaves]; CHECKALLOC(mTriangles);
237
238 // Walk the tree again & setup leaf data
239 Data.mTriangles = mTriangles;
240 Data.mBase = mSource->GetIndices();
241 Data.mNbLeaves = 0; // Reset for incoming walk
242 mSource->Walk(Local::SetupLeafData, &Data);
243
244 // Handle source indices
245 {
246 bool MustKeepIndices = true;
247 if(create.mCanRemap)
248 {
249 // We try to get rid of source indices (saving more ram!) by reorganizing triangle arrays...
250 // Remap can fail when we use callbacks => keep track of indices in that case (it still
251 // works, only using more memory)
252 if(create.mIMesh->RemapClient(mSource->GetNbPrimitives(), mSource->GetIndices()))
253 {
254 MustKeepIndices = false;
255 }
256 }
257
258 if(MustKeepIndices)
259 {
260 // Keep track of source indices (from vanilla tree)
261 mNbPrimitives = mSource->GetNbPrimitives();
262 mIndices = new udword[mNbPrimitives];
263 CopyMemory(mIndices, mSource->GetIndices(), mNbPrimitives*sizeof(udword));
264 }
265 }
266
267 // Now, create our optimized tree using previous leaf nodes
268 LeafTree = new AABBTree;
269 CHECKALLOC(LeafTree);
270 {
271 AABBTreeOfAABBsBuilder TB; // Now using boxes !
272 TB.mSettings = create.mSettings;
273 TB.mSettings.mLimit = 1; // We now want a complete tree so that we can "optimize" it
274 TB.mNbPrimitives = Data.mNbLeaves;
275 TB.mAABBArray = Data.mLeaves;
276 if(!LeafTree->Build(&TB)) goto FreeAndExit;
277 }
278
279 // 3) Create an optimized tree according to user-settings
280 if(!CreateTree(create.mNoLeaf, create.mQuantized)) goto FreeAndExit;
281
282 // 3-2) Create optimized tree
283 if(!mTree->Build(LeafTree)) goto FreeAndExit;
284
285 // Finally ok...
286 Status = true;
287
288FreeAndExit: // Allow me this one...
289 DELETESINGLE(LeafTree);
290
291 // 3-3) Delete generic tree if needed
292 if(!create.mKeepOriginal) DELETESINGLE(mSource);
293
294 return Status;
295}
296
297///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
298/**
299 * Gets the number of bytes used by the tree.
300 * \return amount of bytes used
301 */
302///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
303udword HybridModel::GetUsedBytes() const
304{
305 udword UsedBytes = 0;
306 if(mTree) UsedBytes += mTree->GetUsedBytes();
307 if(mIndices) UsedBytes += mNbPrimitives * sizeof(udword); // mIndices
308 if(mTriangles) UsedBytes += mNbLeaves * sizeof(LeafTriangles); // mTriangles
309 return UsedBytes;
310}
311
312inline_ void ComputeMinMax(Point& min, Point& max, const VertexPointers& vp)
313{
314 // Compute triangle's AABB = a leaf box
315#ifdef OPC_USE_FCOMI // a 15% speedup on my machine, not much
316 min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
317 max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
318
319 min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
320 max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
321
322 min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
323 max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
324#else
325 min = *vp.Vertex[0];
326 max = *vp.Vertex[0];
327 min.Min(*vp.Vertex[1]);
328 max.Max(*vp.Vertex[1]);
329 min.Min(*vp.Vertex[2]);
330 max.Max(*vp.Vertex[2]);
331#endif
332}
333
334///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
335/**
336 * Refits the collision model. This can be used to handle dynamic meshes. Usage is:
337 * 1. modify your mesh vertices (keep the topology constant!)
338 * 2. refit the tree (call this method)
339 * \return true if success
340 */
341///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
342bool HybridModel::Refit()
343{
344 if(!mIMesh) return false;
345 if(!mTree) return false;
346
347 if(IsQuantized()) return false;
348 if(HasLeafNodes()) return false;
349
350 const LeafTriangles* LT = GetLeafTriangles();
351 const udword* Indices = GetIndices();
352
353 // Bottom-up update
354 VertexPointers VP;
355 Point Min,Max;
356 Point Min_,Max_;
357 udword Index = mTree->GetNbNodes();
358 AABBNoLeafNode* Nodes = (AABBNoLeafNode*)((AABBNoLeafTree*)mTree)->GetNodes();
359 while(Index--)
360 {
361 AABBNoLeafNode& Current = Nodes[Index];
362
363 if(Current.HasPosLeaf())
364 {
365 const LeafTriangles& CurrentLeaf = LT[Current.GetPosPrimitive()];
366
367 Min.SetPlusInfinity();
368 Max.SetMinusInfinity();
369
370 Point TmpMin, TmpMax;
371
372 // Each leaf box has a set of triangles
373 udword NbTris = CurrentLeaf.GetNbTriangles();
374 if(Indices)
375 {
376 const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
377
378 // Loop through triangles and test each of them
379 while(NbTris--)
380 {
381 mIMesh->GetTriangle(VP, *T++);
382 ComputeMinMax(TmpMin, TmpMax, VP);
383 Min.Min(TmpMin);
384 Max.Max(TmpMax);
385 }
386 }
387 else
388 {
389 udword BaseIndex = CurrentLeaf.GetTriangleIndex();
390
391 // Loop through triangles and test each of them
392 while(NbTris--)
393 {
394 mIMesh->GetTriangle(VP, BaseIndex++);
395 ComputeMinMax(TmpMin, TmpMax, VP);
396 Min.Min(TmpMin);
397 Max.Max(TmpMax);
398 }
399 }
400 }
401 else
402 {
403 const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;
404 CurrentBox.GetMin(Min);
405 CurrentBox.GetMax(Max);
406 }
407
408 if(Current.HasNegLeaf())
409 {
410 const LeafTriangles& CurrentLeaf = LT[Current.GetNegPrimitive()];
411
412 Min_.SetPlusInfinity();
413 Max_.SetMinusInfinity();
414
415 Point TmpMin, TmpMax;
416
417 // Each leaf box has a set of triangles
418 udword NbTris = CurrentLeaf.GetNbTriangles();
419 if(Indices)
420 {
421 const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
422
423 // Loop through triangles and test each of them
424 while(NbTris--)
425 {
426 mIMesh->GetTriangle(VP, *T++);
427 ComputeMinMax(TmpMin, TmpMax, VP);
428 Min_.Min(TmpMin);
429 Max_.Max(TmpMax);
430 }
431 }
432 else
433 {
434 udword BaseIndex = CurrentLeaf.GetTriangleIndex();
435
436 // Loop through triangles and test each of them
437 while(NbTris--)
438 {
439 mIMesh->GetTriangle(VP, BaseIndex++);
440 ComputeMinMax(TmpMin, TmpMax, VP);
441 Min_.Min(TmpMin);
442 Max_.Max(TmpMax);
443 }
444 }
445 }
446 else
447 {
448 const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;
449 CurrentBox.GetMin(Min_);
450 CurrentBox.GetMax(Max_);
451 }
452#ifdef OPC_USE_FCOMI
453 Min.x = FCMin2(Min.x, Min_.x);
454 Max.x = FCMax2(Max.x, Max_.x);
455 Min.y = FCMin2(Min.y, Min_.y);
456 Max.y = FCMax2(Max.y, Max_.y);
457 Min.z = FCMin2(Min.z, Min_.z);
458 Max.z = FCMax2(Max.z, Max_.z);
459#else
460 Min.Min(Min_);
461 Max.Max(Max_);
462#endif
463 Current.mAABB.SetMinMax(Min, Max);
464 }
465 return true;
466}
generated by cgit v1.1 at 2024-09-21 17:09:06 +0000