aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/ode-0.9/OPCODE/OPC_AABBTree.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--libraries/ode-0.9/OPCODE/OPC_AABBTree.cpp573
1 files changed, 0 insertions, 573 deletions
diff --git a/libraries/ode-0.9/OPCODE/OPC_AABBTree.cpp b/libraries/ode-0.9/OPCODE/OPC_AABBTree.cpp
deleted file mode 100644
index 32214f4..0000000
--- a/libraries/ode-0.9/OPCODE/OPC_AABBTree.cpp
+++ /dev/null
@@ -1,573 +0,0 @@
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 a versatile AABB tree.
12 * \file OPC_AABBTree.cpp
13 * \author Pierre Terdiman
14 * \date March, 20, 2001
15 */
16///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17
18///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
19/**
20 * Contains a generic AABB tree node.
21 *
22 * \class AABBTreeNode
23 * \author Pierre Terdiman
24 * \version 1.3
25 * \date March, 20, 2001
26*/
27///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
28
29///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
30/**
31 * Contains a generic AABB tree.
32 * This is a vanilla AABB tree, without any particular optimization. It contains anonymous references to
33 * user-provided primitives, which can theoretically be anything - triangles, boxes, etc. Each primitive
34 * is surrounded by an AABB, regardless of the primitive's nature. When the primitive is a triangle, the
35 * resulting tree can be converted into an optimized tree. If the primitive is a box, the resulting tree
36 * can be used for culling - VFC or occlusion -, assuming you cull on a mesh-by-mesh basis (modern way).
37 *
38 * \class AABBTree
39 * \author Pierre Terdiman
40 * \version 1.3
41 * \date March, 20, 2001
42*/
43///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
44
45///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
46// Precompiled Header
47#include "Stdafx.h"
48
49using namespace Opcode;
50
51///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
52/**
53 * Constructor.
54 */
55///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
56AABBTreeNode::AABBTreeNode() :
57 mPos (null),
58#ifndef OPC_NO_NEG_VANILLA_TREE
59 mNeg (null),
60#endif
61 mNbPrimitives (0),
62 mNodePrimitives (null)
63{
64#ifdef OPC_USE_TREE_COHERENCE
65 mBitmask = 0;
66#endif
67}
68
69///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
70/**
71 * Destructor.
72 */
73///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
74AABBTreeNode::~AABBTreeNode()
75{
76 // Opcode 1.3:
77 const AABBTreeNode* Pos = GetPos();
78 const AABBTreeNode* Neg = GetNeg();
79#ifndef OPC_NO_NEG_VANILLA_TREE
80 if(!(mPos&1)) DELETESINGLE(Pos);
81 if(!(mNeg&1)) DELETESINGLE(Neg);
82#else
83 if(!(mPos&1)) DELETEARRAY(Pos);
84#endif
85 mNodePrimitives = null; // This was just a shortcut to the global list => no release
86 mNbPrimitives = 0;
87}
88
89///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
90/**
91 * Splits the node along a given axis.
92 * The list of indices is reorganized according to the split values.
93 * \param axis [in] splitting axis index
94 * \param builder [in] the tree builder
95 * \return the number of primitives assigned to the first child
96 * \warning this method reorganizes the internal list of primitives
97 */
98///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
99udword AABBTreeNode::Split(udword axis, AABBTreeBuilder* builder)
100{
101 // Get node split value
102 float SplitValue = builder->GetSplittingValue(mNodePrimitives, mNbPrimitives, mBV, axis);
103
104 udword NbPos = 0;
105 // Loop through all node-related primitives. Their indices range from mNodePrimitives[0] to mNodePrimitives[mNbPrimitives-1].
106 // Those indices map the global list in the tree builder.
107 for(udword i=0;i<mNbPrimitives;i++)
108 {
109 // Get index in global list
110 udword Index = mNodePrimitives[i];
111
112 // Test against the splitting value. The primitive value is tested against the enclosing-box center.
113 // [We only need an approximate partition of the enclosing box here.]
114 float PrimitiveValue = builder->GetSplittingValue(Index, axis);
115
116 // Reorganize the list of indices in this order: positive - negative.
117 if(PrimitiveValue > SplitValue)
118 {
119 // Swap entries
120 udword Tmp = mNodePrimitives[i];
121 mNodePrimitives[i] = mNodePrimitives[NbPos];
122 mNodePrimitives[NbPos] = Tmp;
123 // Count primitives assigned to positive space
124 NbPos++;
125 }
126 }
127 return NbPos;
128}
129
130///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
131/**
132 * Subdivides the node.
133 *
134 * N
135 * / \
136 * / \
137 * N/2 N/2
138 * / \ / \
139 * N/4 N/4 N/4 N/4
140 * (etc)
141 *
142 * A well-balanced tree should have a O(log n) depth.
143 * A degenerate tree would have a O(n) depth.
144 * Note a perfectly-balanced tree is not well-suited to collision detection anyway.
145 *
146 * \param builder [in] the tree builder
147 * \return true if success
148 */
149///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
150bool AABBTreeNode::Subdivide(AABBTreeBuilder* builder)
151{
152 // Checkings
153 if(!builder) return false;
154
155 // Stop subdividing if we reach a leaf node. This is always performed here,
156 // else we could end in trouble if user overrides this.
157 if(mNbPrimitives==1) return true;
158
159 // Let the user validate the subdivision
160 if(!builder->ValidateSubdivision(mNodePrimitives, mNbPrimitives, mBV)) return true;
161
162 bool ValidSplit = true; // Optimism...
163 udword NbPos;
164 if(builder->mSettings.mRules & SPLIT_LARGEST_AXIS)
165 {
166 // Find the largest axis to split along
167 Point Extents; mBV.GetExtents(Extents); // Box extents
168 udword Axis = Extents.LargestAxis(); // Index of largest axis
169
170 // Split along the axis
171 NbPos = Split(Axis, builder);
172
173 // Check split validity
174 if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false;
175 }
176 else if(builder->mSettings.mRules & SPLIT_SPLATTER_POINTS)
177 {
178 // Compute the means
179 Point Means(0.0f, 0.0f, 0.0f);
180 for(udword i=0;i<mNbPrimitives;i++)
181 {
182 udword Index = mNodePrimitives[i];
183 Means.x+=builder->GetSplittingValue(Index, 0);
184 Means.y+=builder->GetSplittingValue(Index, 1);
185 Means.z+=builder->GetSplittingValue(Index, 2);
186 }
187 Means/=float(mNbPrimitives);
188
189 // Compute variances
190 Point Vars(0.0f, 0.0f, 0.0f);
191 for(udword i=0;i<mNbPrimitives;i++)
192 {
193 udword Index = mNodePrimitives[i];
194 float Cx = builder->GetSplittingValue(Index, 0);
195 float Cy = builder->GetSplittingValue(Index, 1);
196 float Cz = builder->GetSplittingValue(Index, 2);
197 Vars.x += (Cx - Means.x)*(Cx - Means.x);
198 Vars.y += (Cy - Means.y)*(Cy - Means.y);
199 Vars.z += (Cz - Means.z)*(Cz - Means.z);
200 }
201 Vars/=float(mNbPrimitives-1);
202
203 // Choose axis with greatest variance
204 udword Axis = Vars.LargestAxis();
205
206 // Split along the axis
207 NbPos = Split(Axis, builder);
208
209 // Check split validity
210 if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false;
211 }
212 else if(builder->mSettings.mRules & SPLIT_BALANCED)
213 {
214 // Test 3 axis, take the best
215 float Results[3];
216 NbPos = Split(0, builder); Results[0] = float(NbPos)/float(mNbPrimitives);
217 NbPos = Split(1, builder); Results[1] = float(NbPos)/float(mNbPrimitives);
218 NbPos = Split(2, builder); Results[2] = float(NbPos)/float(mNbPrimitives);
219 Results[0]-=0.5f; Results[0]*=Results[0];
220 Results[1]-=0.5f; Results[1]*=Results[1];
221 Results[2]-=0.5f; Results[2]*=Results[2];
222 udword Min=0;
223 if(Results[1]<Results[Min]) Min = 1;
224 if(Results[2]<Results[Min]) Min = 2;
225
226 // Split along the axis
227 NbPos = Split(Min, builder);
228
229 // Check split validity
230 if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false;
231 }
232 else if(builder->mSettings.mRules & SPLIT_BEST_AXIS)
233 {
234 // Test largest, then middle, then smallest axis...
235
236 // Sort axis
237 Point Extents; mBV.GetExtents(Extents); // Box extents
238 udword SortedAxis[] = { 0, 1, 2 };
239 float* Keys = (float*)&Extents.x;
240 for(udword j=0;j<3;j++)
241 {
242 for(udword i=0;i<2;i++)
243 {
244 if(Keys[SortedAxis[i]]<Keys[SortedAxis[i+1]])
245 {
246 udword Tmp = SortedAxis[i];
247 SortedAxis[i] = SortedAxis[i+1];
248 SortedAxis[i+1] = Tmp;
249 }
250 }
251 }
252
253 // Find the largest axis to split along
254 udword CurAxis = 0;
255 ValidSplit = false;
256 while(!ValidSplit && CurAxis!=3)
257 {
258 NbPos = Split(SortedAxis[CurAxis], builder);
259 // Check the subdivision has been successful
260 if(!NbPos || NbPos==mNbPrimitives) CurAxis++;
261 else ValidSplit = true;
262 }
263 }
264 else if(builder->mSettings.mRules & SPLIT_FIFTY)
265 {
266 // Don't even bother splitting (mainly a performance test)
267 NbPos = mNbPrimitives>>1;
268 }
269 else return false; // Unknown splitting rules
270
271 // Check the subdivision has been successful
272 if(!ValidSplit)
273 {
274 // Here, all boxes lie in the same sub-space. Two strategies:
275 // - if the tree *must* be complete, make an arbitrary 50-50 split
276 // - else stop subdividing
277// if(builder->mSettings.mRules&SPLIT_COMPLETE)
278 if(builder->mSettings.mLimit==1)
279 {
280 builder->IncreaseNbInvalidSplits();
281 NbPos = mNbPrimitives>>1;
282 }
283 else return true;
284 }
285
286 // Now create children and assign their pointers.
287 if(builder->mNodeBase)
288 {
289 // We use a pre-allocated linear pool for complete trees [Opcode 1.3]
290 AABBTreeNode* Pool = (AABBTreeNode*)builder->mNodeBase;
291 udword Count = builder->GetCount() - 1; // Count begins to 1...
292 // Set last bit to tell it shouldn't be freed ### pretty ugly, find a better way. Maybe one bit in mNbPrimitives
293 ASSERT(!(udword(&Pool[Count+0])&1));
294 ASSERT(!(udword(&Pool[Count+1])&1));
295 mPos = size_t(&Pool[Count+0])|1;
296#ifndef OPC_NO_NEG_VANILLA_TREE
297 mNeg = size_t(&Pool[Count+1])|1;
298#endif
299 }
300 else
301 {
302 // Non-complete trees and/or Opcode 1.2 allocate nodes on-the-fly
303#ifndef OPC_NO_NEG_VANILLA_TREE
304 mPos = (size_t)new AABBTreeNode; CHECKALLOC(mPos);
305 mNeg = (size_t)new AABBTreeNode; CHECKALLOC(mNeg);
306#else
307 AABBTreeNode* PosNeg = new AABBTreeNode[2];
308 CHECKALLOC(PosNeg);
309 mPos = (size_t)PosNeg;
310#endif
311 }
312
313 // Update stats
314 builder->IncreaseCount(2);
315
316 // Assign children
317 AABBTreeNode* Pos = (AABBTreeNode*)GetPos();
318 AABBTreeNode* Neg = (AABBTreeNode*)GetNeg();
319 Pos->mNodePrimitives = &mNodePrimitives[0];
320 Pos->mNbPrimitives = NbPos;
321 Neg->mNodePrimitives = &mNodePrimitives[NbPos];
322 Neg->mNbPrimitives = mNbPrimitives - NbPos;
323
324 return true;
325}
326
327///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
328/**
329 * Recursive hierarchy building in a top-down fashion.
330 * \param builder [in] the tree builder
331 */
332///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
333void AABBTreeNode::_BuildHierarchy(AABBTreeBuilder* builder)
334{
335 // 1) Compute the global box for current node. The box is stored in mBV.
336 builder->ComputeGlobalBox(mNodePrimitives, mNbPrimitives, mBV);
337
338 // 2) Subdivide current node
339 Subdivide(builder);
340
341 // 3) Recurse
342 AABBTreeNode* Pos = (AABBTreeNode*)GetPos();
343 AABBTreeNode* Neg = (AABBTreeNode*)GetNeg();
344 if(Pos) Pos->_BuildHierarchy(builder);
345 if(Neg) Neg->_BuildHierarchy(builder);
346}
347
348///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
349/**
350 * Refits the tree (top-down).
351 * \param builder [in] the tree builder
352 */
353///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
354void AABBTreeNode::_Refit(AABBTreeBuilder* builder)
355{
356 // 1) Recompute the new global box for current node
357 builder->ComputeGlobalBox(mNodePrimitives, mNbPrimitives, mBV);
358
359 // 2) Recurse
360 AABBTreeNode* Pos = (AABBTreeNode*)GetPos();
361 AABBTreeNode* Neg = (AABBTreeNode*)GetNeg();
362 if(Pos) Pos->_Refit(builder);
363 if(Neg) Neg->_Refit(builder);
364}
365
366
367
368///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
369/**
370 * Constructor.
371 */
372///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
373AABBTree::AABBTree() : mIndices(null), mTotalNbNodes(0), mPool(null)
374{
375}
376
377///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
378/**
379 * Destructor.
380 */
381///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
382AABBTree::~AABBTree()
383{
384 Release();
385}
386
387///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
388/**
389 * Releases the tree.
390 */
391///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
392void AABBTree::Release()
393{
394 DELETEARRAY(mPool);
395 DELETEARRAY(mIndices);
396}
397
398///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
399/**
400 * Builds a generic AABB tree from a tree builder.
401 * \param builder [in] the tree builder
402 * \return true if success
403 */
404///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
405bool AABBTree::Build(AABBTreeBuilder* builder)
406{
407 // Checkings
408 if(!builder || !builder->mNbPrimitives) return false;
409
410 // Release previous tree
411 Release();
412
413 // Init stats
414 builder->SetCount(1);
415 builder->SetNbInvalidSplits(0);
416
417 // Initialize indices. This list will be modified during build.
418 mIndices = new udword[builder->mNbPrimitives];
419 CHECKALLOC(mIndices);
420 // Identity permutation
421 for(udword i=0;i<builder->mNbPrimitives;i++) mIndices[i] = i;
422
423 // Setup initial node. Here we have a complete permutation of the app's primitives.
424 mNodePrimitives = mIndices;
425 mNbPrimitives = builder->mNbPrimitives;
426
427 // Use a linear array for complete trees (since we can predict the final number of nodes) [Opcode 1.3]
428// if(builder->mRules&SPLIT_COMPLETE)
429 if(builder->mSettings.mLimit==1)
430 {
431 // Allocate a pool of nodes
432 mPool = new AABBTreeNode[builder->mNbPrimitives*2 - 1];
433
434 builder->mNodeBase = mPool; // ### ugly !
435 }
436
437 // Build the hierarchy
438 _BuildHierarchy(builder);
439
440 // Get back total number of nodes
441 mTotalNbNodes = builder->GetCount();
442
443 // For complete trees, check the correct number of nodes has been created [Opcode 1.3]
444 if(mPool) ASSERT(mTotalNbNodes==builder->mNbPrimitives*2 - 1);
445
446 return true;
447}
448
449///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
450/**
451 * Computes the depth of the tree.
452 * A well-balanced tree should have a log(n) depth. A degenerate tree O(n) depth.
453 * \return depth of the tree
454 */
455///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
456udword AABBTree::ComputeDepth() const
457{
458 return Walk(null, null); // Use the walking code without callback
459}
460
461///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
462/**
463 * Walks the tree, calling the user back for each node.
464 */
465///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
466udword AABBTree::Walk(WalkingCallback callback, void* user_data) const
467{
468 // Call it without callback to compute max depth
469 udword MaxDepth = 0;
470 udword CurrentDepth = 0;
471
472 struct Local
473 {
474 static void _Walk(const AABBTreeNode* current_node, udword& max_depth, udword& current_depth, WalkingCallback callback, void* user_data)
475 {
476 // Checkings
477 if(!current_node) return;
478 // Entering a new node => increase depth
479 current_depth++;
480 // Keep track of max depth
481 if(current_depth>max_depth) max_depth = current_depth;
482
483 // Callback
484 if(callback && !(callback)(current_node, current_depth, user_data)) return;
485
486 // Recurse
487 if(current_node->GetPos()) { _Walk(current_node->GetPos(), max_depth, current_depth, callback, user_data); current_depth--; }
488 if(current_node->GetNeg()) { _Walk(current_node->GetNeg(), max_depth, current_depth, callback, user_data); current_depth--; }
489 }
490 };
491 Local::_Walk(this, MaxDepth, CurrentDepth, callback, user_data);
492 return MaxDepth;
493}
494
495///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
496/**
497 * Refits the tree in a top-down way.
498 * \param builder [in] the tree builder
499 */
500///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
501bool AABBTree::Refit(AABBTreeBuilder* builder)
502{
503 if(!builder) return false;
504 _Refit(builder);
505 return true;
506}
507
508///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
509/**
510 * Refits the tree in a bottom-up way.
511 * \param builder [in] the tree builder
512 */
513///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
514bool AABBTree::Refit2(AABBTreeBuilder* builder)
515{
516 // Checkings
517 if(!builder) return false;
518
519 ASSERT(mPool);
520
521 // Bottom-up update
522 Point Min,Max;
523 Point Min_,Max_;
524 udword Index = mTotalNbNodes;
525 while(Index--)
526 {
527 AABBTreeNode& Current = mPool[Index];
528
529 if(Current.IsLeaf())
530 {
531 builder->ComputeGlobalBox(Current.GetPrimitives(), Current.GetNbPrimitives(), *(AABB*)Current.GetAABB());
532 }
533 else
534 {
535 Current.GetPos()->GetAABB()->GetMin(Min);
536 Current.GetPos()->GetAABB()->GetMax(Max);
537
538 Current.GetNeg()->GetAABB()->GetMin(Min_);
539 Current.GetNeg()->GetAABB()->GetMax(Max_);
540
541 Min.Min(Min_);
542 Max.Max(Max_);
543
544 ((AABB*)Current.GetAABB())->SetMinMax(Min, Max);
545 }
546 }
547 return true;
548}
549
550///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
551/**
552 * Computes the number of bytes used by the tree.
553 * \return number of bytes used
554 */
555///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
556udword AABBTree::GetUsedBytes() const
557{
558 udword TotalSize = mTotalNbNodes*GetNodeSize();
559 if(mIndices) TotalSize+=mNbPrimitives*sizeof(udword);
560 return TotalSize;
561}
562
563///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
564/**
565 * Checks the tree is a complete tree or not.
566 * A complete tree is made of 2*N-1 nodes, where N is the number of primitives in the tree.
567 * \return true for complete trees
568 */
569///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
570bool AABBTree::IsComplete() const
571{
572 return (GetNbNodes()==GetNbPrimitives()*2-1);
573}
generated by cgit v1.1 at 2024-11-10 04:49:30 +0000