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 
49 using namespace Opcode;
50 
51 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
52 /**
53  *	Constructor.
54  */
55 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
AABBTreeNode()56 AABBTreeNode::AABBTreeNode() :
57 	mPos			(null),
58 #ifndef OPC_NO_NEG_VANILLA_TREE
59 	mNeg			(null),
60 #endif
61 	mNodePrimitives	(null),
62 	mNbPrimitives	(0)
63 {
64 #ifdef OPC_USE_TREE_COHERENCE
65 	mBitmask = 0;
66 #endif
67 }
68 
69 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
70 /**
71  *	Destructor.
72  */
73 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
~AABBTreeNode()74 AABBTreeNode::~AABBTreeNode()
75 {
76 	// Opcode 1.3:
77 	const AABBTreeNode* Pos = GetPos();
78 #ifndef OPC_NO_NEG_VANILLA_TREE
79 	const AABBTreeNode* Neg = GetNeg();
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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Split(udword axis,AABBTreeBuilder * builder)99 udword 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Subdivide(AABBTreeBuilder * builder)150 bool 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
_BuildHierarchy(AABBTreeBuilder * builder)333 void 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
_Refit(AABBTreeBuilder * builder)354 void 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
AABBTree()373 AABBTree::AABBTree() : mIndices(null), mPool(null), mTotalNbNodes(0)
374 {
375 }
376 
377 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
378 /**
379  *	Destructor.
380  */
381 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
~AABBTree()382 AABBTree::~AABBTree()
383 {
384 	Release();
385 }
386 
387 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
388 /**
389  *	Releases the tree.
390  */
391 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Release()392 void 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Build(AABBTreeBuilder * builder)405 bool 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 dTriIndex[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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ComputeDepth() const456 udword 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Walk(WalkingCallback callback,void * user_data) const466 udword 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Refit(AABBTreeBuilder * builder)501 bool 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Refit2(AABBTreeBuilder * builder)514 bool 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
GetUsedBytes() const556 udword 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 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
IsComplete() const570 bool AABBTree::IsComplete() const
571 {
572 	return (GetNbNodes()==GetNbPrimitives()*2-1);
573 }
574