aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/ode-0.9/OPCODE/OPC_OptimizedTree.cpp
diff options
context:
space:
mode:
authordan miller2007-10-19 05:20:48 +0000
committerdan miller2007-10-19 05:20:48 +0000
commitd48ea5bb797037069d641da41da0f195f0124491 (patch)
tree40ff433d94859d629aac933d5ec73b382f62ba1a /libraries/ode-0.9/OPCODE/OPC_OptimizedTree.cpp
parentdont ask (diff)
downloadopensim-SC-d48ea5bb797037069d641da41da0f195f0124491.zip
opensim-SC-d48ea5bb797037069d641da41da0f195f0124491.tar.gz
opensim-SC-d48ea5bb797037069d641da41da0f195f0124491.tar.bz2
opensim-SC-d48ea5bb797037069d641da41da0f195f0124491.tar.xz
one more for the gipper
Diffstat (limited to 'libraries/ode-0.9/OPCODE/OPC_OptimizedTree.cpp')
-rw-r--r--libraries/ode-0.9/OPCODE/OPC_OptimizedTree.cpp782
1 files changed, 782 insertions, 0 deletions
diff --git a/libraries/ode-0.9/OPCODE/OPC_OptimizedTree.cpp b/libraries/ode-0.9/OPCODE/OPC_OptimizedTree.cpp
new file mode 100644
index 0000000..11b92f9
--- /dev/null
+++ b/libraries/ode-0.9/OPCODE/OPC_OptimizedTree.cpp
@@ -0,0 +1,782 @@
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 optimized trees. Implements 4 trees:
12 * - normal
13 * - no leaf
14 * - quantized
15 * - no leaf / quantized
16 *
17 * \file OPC_OptimizedTree.cpp
18 * \author Pierre Terdiman
19 * \date March, 20, 2001
20 */
21///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
22
23///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
24/**
25 * A standard AABB tree.
26 *
27 * \class AABBCollisionTree
28 * \author Pierre Terdiman
29 * \version 1.3
30 * \date March, 20, 2001
31*/
32///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
33
34///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
35/**
36 * A no-leaf AABB tree.
37 *
38 * \class AABBNoLeafTree
39 * \author Pierre Terdiman
40 * \version 1.3
41 * \date March, 20, 2001
42*/
43///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
44
45///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
46/**
47 * A quantized AABB tree.
48 *
49 * \class AABBQuantizedTree
50 * \author Pierre Terdiman
51 * \version 1.3
52 * \date March, 20, 2001
53*/
54///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
55
56///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
57/**
58 * A quantized no-leaf AABB tree.
59 *
60 * \class AABBQuantizedNoLeafTree
61 * \author Pierre Terdiman
62 * \version 1.3
63 * \date March, 20, 2001
64*/
65///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
66
67///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
68// Precompiled Header
69#include "Stdafx.h"
70
71using namespace Opcode;
72
73//! Compilation flag:
74//! - true to fix quantized boxes (i.e. make sure they enclose the original ones)
75//! - false to see the effects of quantization errors (faster, but wrong results in some cases)
76static bool gFixQuantized = true;
77
78///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
79/**
80 * Builds an implicit tree from a standard one. An implicit tree is a complete tree (2*N-1 nodes) whose negative
81 * box pointers and primitive pointers have been made implicit, hence packing 3 pointers in one.
82 *
83 * Layout for implicit trees:
84 * Node:
85 * - box
86 * - data (32-bits value)
87 *
88 * if data's LSB = 1 => remaining bits are a primitive pointer
89 * else remaining bits are a P-node pointer, and N = P + 1
90 *
91 * \relates AABBCollisionNode
92 * \fn _BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
93 * \param linear [in] base address of destination nodes
94 * \param box_id [in] index of destination node
95 * \param current_id [in] current running index
96 * \param current_node [in] current node from input tree
97 */
98///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
99static void _BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
100{
101 // Current node from input tree is "current_node". Must be flattened into "linear[boxid]".
102
103 // Store the AABB
104 current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);
105 current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);
106 // Store remaining info
107 if(current_node->IsLeaf())
108 {
109 // The input tree must be complete => i.e. one primitive/leaf
110 ASSERT(current_node->GetNbPrimitives()==1);
111 // Get the primitive index from the input tree
112 udword PrimitiveIndex = current_node->GetPrimitives()[0];
113 // Setup box data as the primitive index, marked as leaf
114 linear[box_id].mData = (PrimitiveIndex<<1)|1;
115 }
116 else
117 {
118 // To make the negative one implicit, we must store P and N in successive order
119 udword PosID = current_id++; // Get a new id for positive child
120 udword NegID = current_id++; // Get a new id for negative child
121 // Setup box data as the forthcoming new P pointer
122 linear[box_id].mData = (size_t)&linear[PosID];
123 // Make sure it's not marked as leaf
124 ASSERT(!(linear[box_id].mData&1));
125 // Recurse with new IDs
126 _BuildCollisionTree(linear, PosID, current_id, current_node->GetPos());
127 _BuildCollisionTree(linear, NegID, current_id, current_node->GetNeg());
128 }
129}
130
131///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
132/**
133 * Builds a "no-leaf" tree from a standard one. This is a tree whose leaf nodes have been removed.
134 *
135 * Layout for no-leaf trees:
136 *
137 * Node:
138 * - box
139 * - P pointer => a node (LSB=0) or a primitive (LSB=1)
140 * - N pointer => a node (LSB=0) or a primitive (LSB=1)
141 *
142 * \relates AABBNoLeafNode
143 * \fn _BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
144 * \param linear [in] base address of destination nodes
145 * \param box_id [in] index of destination node
146 * \param current_id [in] current running index
147 * \param current_node [in] current node from input tree
148 */
149///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
150static void _BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
151{
152 const AABBTreeNode* P = current_node->GetPos();
153 const AABBTreeNode* N = current_node->GetNeg();
154 // Leaf nodes here?!
155 ASSERT(P);
156 ASSERT(N);
157 // Internal node => keep the box
158 current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);
159 current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);
160
161 if(P->IsLeaf())
162 {
163 // The input tree must be complete => i.e. one primitive/leaf
164 ASSERT(P->GetNbPrimitives()==1);
165 // Get the primitive index from the input tree
166 udword PrimitiveIndex = P->GetPrimitives()[0];
167 // Setup prev box data as the primitive index, marked as leaf
168 linear[box_id].mPosData = (PrimitiveIndex<<1)|1;
169 }
170 else
171 {
172 // Get a new id for positive child
173 udword PosID = current_id++;
174 // Setup box data
175 linear[box_id].mPosData = (size_t)&linear[PosID];
176 // Make sure it's not marked as leaf
177 ASSERT(!(linear[box_id].mPosData&1));
178 // Recurse
179 _BuildNoLeafTree(linear, PosID, current_id, P);
180 }
181
182 if(N->IsLeaf())
183 {
184 // The input tree must be complete => i.e. one primitive/leaf
185 ASSERT(N->GetNbPrimitives()==1);
186 // Get the primitive index from the input tree
187 udword PrimitiveIndex = N->GetPrimitives()[0];
188 // Setup prev box data as the primitive index, marked as leaf
189 linear[box_id].mNegData = (PrimitiveIndex<<1)|1;
190 }
191 else
192 {
193 // Get a new id for negative child
194 udword NegID = current_id++;
195 // Setup box data
196 linear[box_id].mNegData = (size_t)&linear[NegID];
197 // Make sure it's not marked as leaf
198 ASSERT(!(linear[box_id].mNegData&1));
199 // Recurse
200 _BuildNoLeafTree(linear, NegID, current_id, N);
201 }
202}
203
204///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
205/**
206 * Constructor.
207 */
208///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
209AABBCollisionTree::AABBCollisionTree() : mNodes(null)
210{
211}
212
213///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
214/**
215 * Destructor.
216 */
217///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
218AABBCollisionTree::~AABBCollisionTree()
219{
220 DELETEARRAY(mNodes);
221}
222
223///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
224/**
225 * Builds the collision tree from a generic AABB tree.
226 * \param tree [in] generic AABB tree
227 * \return true if success
228 */
229///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
230bool AABBCollisionTree::Build(AABBTree* tree)
231{
232 // Checkings
233 if(!tree) return false;
234 // Check the input tree is complete
235 udword NbTriangles = tree->GetNbPrimitives();
236 udword NbNodes = tree->GetNbNodes();
237 if(NbNodes!=NbTriangles*2-1) return false;
238
239 // Get nodes
240 if(mNbNodes!=NbNodes) // Same number of nodes => keep moving
241 {
242 mNbNodes = NbNodes;
243 DELETEARRAY(mNodes);
244 mNodes = new AABBCollisionNode[mNbNodes];
245 CHECKALLOC(mNodes);
246 }
247
248 // Build the tree
249 udword CurID = 1;
250 _BuildCollisionTree(mNodes, 0, CurID, tree);
251 ASSERT(CurID==mNbNodes);
252
253 return true;
254}
255
256///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
257/**
258 * Refits the collision tree after vertices have been modified.
259 * \param mesh_interface [in] mesh interface for current model
260 * \return true if success
261 */
262///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
263bool AABBCollisionTree::Refit(const MeshInterface* mesh_interface)
264{
265 ASSERT(!"Not implemented since AABBCollisionTrees have twice as more nodes to refit as AABBNoLeafTrees!");
266 return false;
267}
268
269///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
270/**
271 * Walks the tree and call the user back for each node.
272 * \param callback [in] walking callback
273 * \param user_data [in] callback's user data
274 * \return true if success
275 */
276///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
277bool AABBCollisionTree::Walk(GenericWalkingCallback callback, void* user_data) const
278{
279 if(!callback) return false;
280
281 struct Local
282 {
283 static void _Walk(const AABBCollisionNode* current_node, GenericWalkingCallback callback, void* user_data)
284 {
285 if(!current_node || !(callback)(current_node, user_data)) return;
286
287 if(!current_node->IsLeaf())
288 {
289 _Walk(current_node->GetPos(), callback, user_data);
290 _Walk(current_node->GetNeg(), callback, user_data);
291 }
292 }
293 };
294 Local::_Walk(mNodes, callback, user_data);
295 return true;
296}
297
298
299///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
300/**
301 * Constructor.
302 */
303///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
304AABBNoLeafTree::AABBNoLeafTree() : mNodes(null)
305{
306}
307
308///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
309/**
310 * Destructor.
311 */
312///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
313AABBNoLeafTree::~AABBNoLeafTree()
314{
315 DELETEARRAY(mNodes);
316}
317
318///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
319/**
320 * Builds the collision tree from a generic AABB tree.
321 * \param tree [in] generic AABB tree
322 * \return true if success
323 */
324///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
325bool AABBNoLeafTree::Build(AABBTree* tree)
326{
327 // Checkings
328 if(!tree) return false;
329 // Check the input tree is complete
330 udword NbTriangles = tree->GetNbPrimitives();
331 udword NbNodes = tree->GetNbNodes();
332 if(NbNodes!=NbTriangles*2-1) return false;
333
334 // Get nodes
335 if(mNbNodes!=NbTriangles-1) // Same number of nodes => keep moving
336 {
337 mNbNodes = NbTriangles-1;
338 DELETEARRAY(mNodes);
339 mNodes = new AABBNoLeafNode[mNbNodes];
340 CHECKALLOC(mNodes);
341 }
342
343 // Build the tree
344 udword CurID = 1;
345 _BuildNoLeafTree(mNodes, 0, CurID, tree);
346 ASSERT(CurID==mNbNodes);
347
348 return true;
349}
350
351inline_ void ComputeMinMax(Point& min, Point& max, const VertexPointers& vp)
352{
353 // Compute triangle's AABB = a leaf box
354#ifdef OPC_USE_FCOMI // a 15% speedup on my machine, not much
355 min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
356 max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
357
358 min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
359 max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
360
361 min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
362 max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
363#else
364 min = *vp.Vertex[0];
365 max = *vp.Vertex[0];
366 min.Min(*vp.Vertex[1]);
367 max.Max(*vp.Vertex[1]);
368 min.Min(*vp.Vertex[2]);
369 max.Max(*vp.Vertex[2]);
370#endif
371}
372
373///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
374/**
375 * Refits the collision tree after vertices have been modified.
376 * \param mesh_interface [in] mesh interface for current model
377 * \return true if success
378 */
379///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
380bool AABBNoLeafTree::Refit(const MeshInterface* mesh_interface)
381{
382 // Checkings
383 if(!mesh_interface) return false;
384
385 // Bottom-up update
386 VertexPointers VP;
387 Point Min,Max;
388 Point Min_,Max_;
389 udword Index = mNbNodes;
390 while(Index--)
391 {
392 AABBNoLeafNode& Current = mNodes[Index];
393
394 if(Current.HasPosLeaf())
395 {
396 mesh_interface->GetTriangle(VP, Current.GetPosPrimitive());
397 ComputeMinMax(Min, Max, VP);
398 }
399 else
400 {
401 const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;
402 CurrentBox.GetMin(Min);
403 CurrentBox.GetMax(Max);
404 }
405
406 if(Current.HasNegLeaf())
407 {
408 mesh_interface->GetTriangle(VP, Current.GetNegPrimitive());
409 ComputeMinMax(Min_, Max_, VP);
410 }
411 else
412 {
413 const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;
414 CurrentBox.GetMin(Min_);
415 CurrentBox.GetMax(Max_);
416 }
417#ifdef OPC_USE_FCOMI
418 Min.x = FCMin2(Min.x, Min_.x);
419 Max.x = FCMax2(Max.x, Max_.x);
420 Min.y = FCMin2(Min.y, Min_.y);
421 Max.y = FCMax2(Max.y, Max_.y);
422 Min.z = FCMin2(Min.z, Min_.z);
423 Max.z = FCMax2(Max.z, Max_.z);
424#else
425 Min.Min(Min_);
426 Max.Max(Max_);
427#endif
428 Current.mAABB.SetMinMax(Min, Max);
429 }
430 return true;
431}
432
433///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
434/**
435 * Walks the tree and call the user back for each node.
436 * \param callback [in] walking callback
437 * \param user_data [in] callback's user data
438 * \return true if success
439 */
440///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
441bool AABBNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const
442{
443 if(!callback) return false;
444
445 struct Local
446 {
447 static void _Walk(const AABBNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data)
448 {
449 if(!current_node || !(callback)(current_node, user_data)) return;
450
451 if(!current_node->HasPosLeaf()) _Walk(current_node->GetPos(), callback, user_data);
452 if(!current_node->HasNegLeaf()) _Walk(current_node->GetNeg(), callback, user_data);
453 }
454 };
455 Local::_Walk(mNodes, callback, user_data);
456 return true;
457}
458
459// Quantization notes:
460// - We could use the highest bits of mData to store some more quantized bits. Dequantization code
461// would be slightly more complex, but number of overlap tests would be reduced (and anyhow those
462// bits are currently wasted). Of course it's not possible if we move to 16 bits mData.
463// - Something like "16 bits floats" could be tested, to bypass the int-to-float conversion.
464// - A dedicated BV-BV test could be used, dequantizing while testing for overlap. (i.e. it's some
465// lazy-dequantization which may save some work in case of early exits). At the very least some
466// muls could be saved by precomputing several more matrices. But maybe not worth the pain.
467// - Do we need to dequantize anyway? Not doing the extents-related muls only implies the box has
468// been scaled, for example.
469// - The deeper we move into the hierarchy, the smaller the extents should be. May not need a fixed
470// number of quantization bits. Even better, could probably be best delta-encoded.
471
472
473// Find max values. Some people asked why I wasn't simply using the first node. Well, I can't.
474// I'm not looking for (min, max) values like in a standard AABB, I'm looking for the extremal
475// centers/extents in order to quantize them. The first node would only give a single center and
476// a single extents. While extents would be the biggest, the center wouldn't.
477#define FIND_MAX_VALUES \
478 /* Get max values */ \
479 Point CMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT); \
480 Point EMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT); \
481 for(udword i=0;i<mNbNodes;i++) \
482 { \
483 if(fabsf(Nodes[i].mAABB.mCenter.x)>CMax.x) CMax.x = fabsf(Nodes[i].mAABB.mCenter.x); \
484 if(fabsf(Nodes[i].mAABB.mCenter.y)>CMax.y) CMax.y = fabsf(Nodes[i].mAABB.mCenter.y); \
485 if(fabsf(Nodes[i].mAABB.mCenter.z)>CMax.z) CMax.z = fabsf(Nodes[i].mAABB.mCenter.z); \
486 if(fabsf(Nodes[i].mAABB.mExtents.x)>EMax.x) EMax.x = fabsf(Nodes[i].mAABB.mExtents.x); \
487 if(fabsf(Nodes[i].mAABB.mExtents.y)>EMax.y) EMax.y = fabsf(Nodes[i].mAABB.mExtents.y); \
488 if(fabsf(Nodes[i].mAABB.mExtents.z)>EMax.z) EMax.z = fabsf(Nodes[i].mAABB.mExtents.z); \
489 }
490
491#define INIT_QUANTIZATION \
492 udword nbc=15; /* Keep one bit for sign */ \
493 udword nbe=15; /* Keep one bit for fix */ \
494 if(!gFixQuantized) nbe++; \
495 \
496 /* Compute quantization coeffs */ \
497 Point CQuantCoeff, EQuantCoeff; \
498 CQuantCoeff.x = CMax.x!=0.0f ? float((1<<nbc)-1)/CMax.x : 0.0f; \
499 CQuantCoeff.y = CMax.y!=0.0f ? float((1<<nbc)-1)/CMax.y : 0.0f; \
500 CQuantCoeff.z = CMax.z!=0.0f ? float((1<<nbc)-1)/CMax.z : 0.0f; \
501 EQuantCoeff.x = EMax.x!=0.0f ? float((1<<nbe)-1)/EMax.x : 0.0f; \
502 EQuantCoeff.y = EMax.y!=0.0f ? float((1<<nbe)-1)/EMax.y : 0.0f; \
503 EQuantCoeff.z = EMax.z!=0.0f ? float((1<<nbe)-1)/EMax.z : 0.0f; \
504 /* Compute and save dequantization coeffs */ \
505 mCenterCoeff.x = CQuantCoeff.x!=0.0f ? 1.0f / CQuantCoeff.x : 0.0f; \
506 mCenterCoeff.y = CQuantCoeff.y!=0.0f ? 1.0f / CQuantCoeff.y : 0.0f; \
507 mCenterCoeff.z = CQuantCoeff.z!=0.0f ? 1.0f / CQuantCoeff.z : 0.0f; \
508 mExtentsCoeff.x = EQuantCoeff.x!=0.0f ? 1.0f / EQuantCoeff.x : 0.0f; \
509 mExtentsCoeff.y = EQuantCoeff.y!=0.0f ? 1.0f / EQuantCoeff.y : 0.0f; \
510 mExtentsCoeff.z = EQuantCoeff.z!=0.0f ? 1.0f / EQuantCoeff.z : 0.0f; \
511
512#define PERFORM_QUANTIZATION \
513 /* Quantize */ \
514 mNodes[i].mAABB.mCenter[0] = sword(Nodes[i].mAABB.mCenter.x * CQuantCoeff.x); \
515 mNodes[i].mAABB.mCenter[1] = sword(Nodes[i].mAABB.mCenter.y * CQuantCoeff.y); \
516 mNodes[i].mAABB.mCenter[2] = sword(Nodes[i].mAABB.mCenter.z * CQuantCoeff.z); \
517 mNodes[i].mAABB.mExtents[0] = uword(Nodes[i].mAABB.mExtents.x * EQuantCoeff.x); \
518 mNodes[i].mAABB.mExtents[1] = uword(Nodes[i].mAABB.mExtents.y * EQuantCoeff.y); \
519 mNodes[i].mAABB.mExtents[2] = uword(Nodes[i].mAABB.mExtents.z * EQuantCoeff.z); \
520 /* Fix quantized boxes */ \
521 if(gFixQuantized) \
522 { \
523 /* Make sure the quantized box is still valid */ \
524 Point Max = Nodes[i].mAABB.mCenter + Nodes[i].mAABB.mExtents; \
525 Point Min = Nodes[i].mAABB.mCenter - Nodes[i].mAABB.mExtents; \
526 /* For each axis */ \
527 for(udword j=0;j<3;j++) \
528 { /* Dequantize the box center */ \
529 float qc = float(mNodes[i].mAABB.mCenter[j]) * mCenterCoeff[j]; \
530 bool FixMe=true; \
531 do \
532 { /* Dequantize the box extent */ \
533 float qe = float(mNodes[i].mAABB.mExtents[j]) * mExtentsCoeff[j]; \
534 /* Compare real & dequantized values */ \
535 if(qc+qe<Max[j] || qc-qe>Min[j]) mNodes[i].mAABB.mExtents[j]++; \
536 else FixMe=false; \
537 /* Prevent wrapping */ \
538 if(!mNodes[i].mAABB.mExtents[j]) \
539 { \
540 mNodes[i].mAABB.mExtents[j]=0xffff; \
541 FixMe=false; \
542 } \
543 }while(FixMe); \
544 } \
545 }
546
547#define REMAP_DATA(member) \
548 /* Fix data */ \
549 Data = Nodes[i].member; \
550 if(!(Data&1)) \
551 { \
552 /* Compute box number */ \
553 size_t Nb = (Data - size_t(Nodes))/Nodes[i].GetNodeSize(); \
554 Data = (size_t) &mNodes[Nb]; \
555 } \
556 /* ...remapped */ \
557 mNodes[i].member = Data;
558
559///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
560/**
561 * Constructor.
562 */
563///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
564AABBQuantizedTree::AABBQuantizedTree() : mNodes(null)
565{
566}
567
568///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
569/**
570 * Destructor.
571 */
572///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
573AABBQuantizedTree::~AABBQuantizedTree()
574{
575 DELETEARRAY(mNodes);
576}
577
578///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
579/**
580 * Builds the collision tree from a generic AABB tree.
581 * \param tree [in] generic AABB tree
582 * \return true if success
583 */
584///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
585bool AABBQuantizedTree::Build(AABBTree* tree)
586{
587 // Checkings
588 if(!tree) return false;
589 // Check the input tree is complete
590 udword NbTriangles = tree->GetNbPrimitives();
591 udword NbNodes = tree->GetNbNodes();
592 if(NbNodes!=NbTriangles*2-1) return false;
593
594 // Get nodes
595 mNbNodes = NbNodes;
596 DELETEARRAY(mNodes);
597 AABBCollisionNode* Nodes = new AABBCollisionNode[mNbNodes];
598 CHECKALLOC(Nodes);
599
600 // Build the tree
601 udword CurID = 1;
602 _BuildCollisionTree(Nodes, 0, CurID, tree);
603
604 // Quantize
605 {
606 mNodes = new AABBQuantizedNode[mNbNodes];
607 CHECKALLOC(mNodes);
608
609 // Get max values
610 FIND_MAX_VALUES
611
612 // Quantization
613 INIT_QUANTIZATION
614
615 // Quantize
616 size_t Data;
617 for(udword i=0;i<mNbNodes;i++)
618 {
619 PERFORM_QUANTIZATION
620 REMAP_DATA(mData)
621 }
622
623 DELETEARRAY(Nodes);
624 }
625
626 return true;
627}
628
629///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
630/**
631 * Refits the collision tree after vertices have been modified.
632 * \param mesh_interface [in] mesh interface for current model
633 * \return true if success
634 */
635///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
636bool AABBQuantizedTree::Refit(const MeshInterface* mesh_interface)
637{
638 ASSERT(!"Not implemented since requantizing is painful !");
639 return false;
640}
641
642///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
643/**
644 * Walks the tree and call the user back for each node.
645 * \param callback [in] walking callback
646 * \param user_data [in] callback's user data
647 * \return true if success
648 */
649///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
650bool AABBQuantizedTree::Walk(GenericWalkingCallback callback, void* user_data) const
651{
652 if(!callback) return false;
653
654 struct Local
655 {
656 static void _Walk(const AABBQuantizedNode* current_node, GenericWalkingCallback callback, void* user_data)
657 {
658 if(!current_node || !(callback)(current_node, user_data)) return;
659
660 if(!current_node->IsLeaf())
661 {
662 _Walk(current_node->GetPos(), callback, user_data);
663 _Walk(current_node->GetNeg(), callback, user_data);
664 }
665 }
666 };
667 Local::_Walk(mNodes, callback, user_data);
668 return true;
669}
670
671
672
673///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
674/**
675 * Constructor.
676 */
677///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
678AABBQuantizedNoLeafTree::AABBQuantizedNoLeafTree() : mNodes(null)
679{
680}
681
682///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
683/**
684 * Destructor.
685 */
686///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
687AABBQuantizedNoLeafTree::~AABBQuantizedNoLeafTree()
688{
689 DELETEARRAY(mNodes);
690}
691
692///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
693/**
694 * Builds the collision tree from a generic AABB tree.
695 * \param tree [in] generic AABB tree
696 * \return true if success
697 */
698///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
699bool AABBQuantizedNoLeafTree::Build(AABBTree* tree)
700{
701 // Checkings
702 if(!tree) return false;
703 // Check the input tree is complete
704 udword NbTriangles = tree->GetNbPrimitives();
705 udword NbNodes = tree->GetNbNodes();
706 if(NbNodes!=NbTriangles*2-1) return false;
707
708 // Get nodes
709 mNbNodes = NbTriangles-1;
710 DELETEARRAY(mNodes);
711 AABBNoLeafNode* Nodes = new AABBNoLeafNode[mNbNodes];
712 CHECKALLOC(Nodes);
713
714 // Build the tree
715 udword CurID = 1;
716 _BuildNoLeafTree(Nodes, 0, CurID, tree);
717 ASSERT(CurID==mNbNodes);
718
719 // Quantize
720 {
721 mNodes = new AABBQuantizedNoLeafNode[mNbNodes];
722 CHECKALLOC(mNodes);
723
724 // Get max values
725 FIND_MAX_VALUES
726
727 // Quantization
728 INIT_QUANTIZATION
729
730 // Quantize
731 size_t Data;
732 for(udword i=0;i<mNbNodes;i++)
733 {
734 PERFORM_QUANTIZATION
735 REMAP_DATA(mPosData)
736 REMAP_DATA(mNegData)
737 }
738
739 DELETEARRAY(Nodes);
740 }
741
742 return true;
743}
744
745///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
746/**
747 * Refits the collision tree after vertices have been modified.
748 * \param mesh_interface [in] mesh interface for current model
749 * \return true if success
750 */
751///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
752bool AABBQuantizedNoLeafTree::Refit(const MeshInterface* mesh_interface)
753{
754 ASSERT(!"Not implemented since requantizing is painful !");
755 return false;
756}
757
758///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
759/**
760 * Walks the tree and call the user back for each node.
761 * \param callback [in] walking callback
762 * \param user_data [in] callback's user data
763 * \return true if success
764 */
765///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
766bool AABBQuantizedNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const
767{
768 if(!callback) return false;
769
770 struct Local
771 {
772 static void _Walk(const AABBQuantizedNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data)
773 {
774 if(!current_node || !(callback)(current_node, user_data)) return;
775
776 if(!current_node->HasPosLeaf()) _Walk(current_node->GetPos(), callback, user_data);
777 if(!current_node->HasNegLeaf()) _Walk(current_node->GetNeg(), callback, user_data);
778 }
779 };
780 Local::_Walk(mNodes, callback, user_data);
781 return true;
782}
generated by cgit v1.1 at 2024-12-28 08:31:58 +0000