Converted Opcode and Ice into unix newlines format

1 files changed, 782 insertions, 782 deletions

diff --git a/Opcode/OPC_OptimizedTree.cpp b/Opcode/OPC_OptimizedTree.cpp
index 32e4803..a84ac5a 100644
--- a/Opcode/OPC_OptimizedTree.cpp
+++ b/Opcode/OPC_OptimizedTree.cpp
@@ -1,782 +1,782 @@
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/*

- *	OPCODE - Optimized Collision Detection

- *	Copyright (C) 2001 Pierre Terdiman

- *	Homepage: http://www.codercorner.com/Opcode.htm

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Contains code for optimized trees. Implements 4 trees:

- *	- normal

- *	- no leaf

- *	- quantized

- *	- no leaf / quantized

- *

- *	\file		OPC_OptimizedTree.cpp

- *	\author		Pierre Terdiman

- *	\date		March, 20, 2001

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	A standard AABB tree.

- *

- *	\class		AABBCollisionTree

- *	\author		Pierre Terdiman

- *	\version	1.3

- *	\date		March, 20, 2001

-*/

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	A no-leaf AABB tree.

- *

- *	\class		AABBNoLeafTree

- *	\author		Pierre Terdiman

- *	\version	1.3

- *	\date		March, 20, 2001

-*/

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	A quantized AABB tree.

- *

- *	\class		AABBQuantizedTree

- *	\author		Pierre Terdiman

- *	\version	1.3

- *	\date		March, 20, 2001

-*/

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	A quantized no-leaf AABB tree.

- *

- *	\class		AABBQuantizedNoLeafTree

- *	\author		Pierre Terdiman

- *	\version	1.3

- *	\date		March, 20, 2001

-*/

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-// Precompiled Header

-#include "StdAfx.h"

-

-using namespace Opcode;

-

-//! Compilation flag:

-//! - true to fix quantized boxes (i.e. make sure they enclose the original ones)

-//! - false to see the effects of quantization errors (faster, but wrong results in some cases)

-static bool gFixQuantized = true;

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Builds an implicit tree from a standard one. An implicit tree is a complete tree (2*N-1 nodes) whose negative

- *	box pointers and primitive pointers have been made implicit, hence packing 3 pointers in one.

- *

- *	Layout for implicit trees:

- *	Node:

- *			- box

- *			- data (32-bits value)

- *

- *	if data's LSB = 1 =>	remaining bits are a primitive pointer

- *	else					remaining bits are a P-node pointer, and N = P + 1

- *

- *	\relates	AABBCollisionNode

- *	\fn			_BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)

- *	\param		linear			[in] base address of destination nodes

- *	\param		box_id			[in] index of destination node

- *	\param		current_id		[in] current running index

- *	\param		current_node	[in] current node from input tree

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-static void _BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)

-{

-	// Current node from input tree is "current_node". Must be flattened into "linear[boxid]".

-

-	// Store the AABB

-	current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);

-	current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);

-	// Store remaining info

-	if(current_node->IsLeaf())

-	{

-		// The input tree must be complete => i.e. one primitive/leaf

-		ASSERT(current_node->GetNbPrimitives()==1);

-		// Get the primitive index from the input tree

-		udword PrimitiveIndex = current_node->GetPrimitives()[0];

-		// Setup box data as the primitive index, marked as leaf

-		linear[box_id].mData = (PrimitiveIndex<<1)|1;

-	}

-	else

-	{

-		// To make the negative one implicit, we must store P and N in successive order

-		udword PosID = current_id++;	// Get a new id for positive child

-		udword NegID = current_id++;	// Get a new id for negative child

-		// Setup box data as the forthcoming new P pointer

-		linear[box_id].mData = (udword)&linear[PosID];

-		// Make sure it's not marked as leaf

-		ASSERT(!(linear[box_id].mData&1));

-		// Recurse with new IDs

-		_BuildCollisionTree(linear, PosID, current_id, current_node->GetPos());

-		_BuildCollisionTree(linear, NegID, current_id, current_node->GetNeg());

-	}

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Builds a "no-leaf" tree from a standard one. This is a tree whose leaf nodes have been removed.

- *

- *	Layout for no-leaf trees:

- *

- *	Node:

- *			- box

- *			- P pointer => a node (LSB=0) or a primitive (LSB=1)

- *			- N pointer => a node (LSB=0) or a primitive (LSB=1)

- *

- *	\relates	AABBNoLeafNode

- *	\fn			_BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)

- *	\param		linear			[in] base address of destination nodes

- *	\param		box_id			[in] index of destination node

- *	\param		current_id		[in] current running index

- *	\param		current_node	[in] current node from input tree

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-static void _BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)

-{

-	const AABBTreeNode* P = current_node->GetPos();

-	const AABBTreeNode* N = current_node->GetNeg();

-	// Leaf nodes here?!

-	ASSERT(P);

-	ASSERT(N);

-	// Internal node => keep the box

-	current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);

-	current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);

-

-	if(P->IsLeaf())

-	{

-		// The input tree must be complete => i.e. one primitive/leaf

-		ASSERT(P->GetNbPrimitives()==1);

-		// Get the primitive index from the input tree

-		udword PrimitiveIndex = P->GetPrimitives()[0];

-		// Setup prev box data as the primitive index, marked as leaf

-		linear[box_id].mPosData = (PrimitiveIndex<<1)|1;

-	}

-	else

-	{

-		// Get a new id for positive child

-		udword PosID = current_id++;

-		// Setup box data

-		linear[box_id].mPosData = (udword)&linear[PosID];

-		// Make sure it's not marked as leaf

-		ASSERT(!(linear[box_id].mPosData&1));

-		// Recurse

-		_BuildNoLeafTree(linear, PosID, current_id, P);

-	}

-

-	if(N->IsLeaf())

-	{

-		// The input tree must be complete => i.e. one primitive/leaf

-		ASSERT(N->GetNbPrimitives()==1);

-		// Get the primitive index from the input tree

-		udword PrimitiveIndex = N->GetPrimitives()[0];

-		// Setup prev box data as the primitive index, marked as leaf

-		linear[box_id].mNegData = (PrimitiveIndex<<1)|1;

-	}

-	else

-	{

-		// Get a new id for negative child

-		udword NegID = current_id++;

-		// Setup box data

-		linear[box_id].mNegData = (udword)&linear[NegID];

-		// Make sure it's not marked as leaf

-		ASSERT(!(linear[box_id].mNegData&1));

-		// Recurse

-		_BuildNoLeafTree(linear, NegID, current_id, N);

-	}

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Constructor.

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AABBCollisionTree::AABBCollisionTree() : mNodes(null)

-{

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Destructor.

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AABBCollisionTree::~AABBCollisionTree()

-{

-	DELETEARRAY(mNodes);

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Builds the collision tree from a generic AABB tree.

- *	\param		tree			[in] generic AABB tree

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBCollisionTree::Build(AABBTree* tree)

-{

-	// Checkings

-	if(!tree)	return false;

-	// Check the input tree is complete

-	udword NbTriangles	= tree->GetNbPrimitives();

-	udword NbNodes		= tree->GetNbNodes();

-	if(NbNodes!=NbTriangles*2-1)	return false;

-

-	// Get nodes

-	if(mNbNodes!=NbNodes)	// Same number of nodes => keep moving

-	{

-		mNbNodes = NbNodes;

-		DELETEARRAY(mNodes);

-		mNodes = new AABBCollisionNode[mNbNodes];

-		CHECKALLOC(mNodes);

-	}

-

-	// Build the tree

-	udword CurID = 1;

-	_BuildCollisionTree(mNodes, 0, CurID, tree);

-	ASSERT(CurID==mNbNodes);

-

-	return true;

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Refits the collision tree after vertices have been modified.

- *	\param		mesh_interface	[in] mesh interface for current model

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBCollisionTree::Refit(const MeshInterface* mesh_interface)

-{

-	ASSERT(!"Not implemented since AABBCollisionTrees have twice as more nodes to refit as AABBNoLeafTrees!");

-	return false;

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Walks the tree and call the user back for each node.

- *	\param		callback	[in] walking callback

- *	\param		user_data	[in] callback's user data

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBCollisionTree::Walk(GenericWalkingCallback callback, void* user_data) const

-{

-	if(!callback)	return false;

-

-	struct Local

-	{

-		static void _Walk(const AABBCollisionNode* current_node, GenericWalkingCallback callback, void* user_data)

-		{

-			if(!current_node || !(callback)(current_node, user_data))	return;

-

-			if(!current_node->IsLeaf())

-			{

-				_Walk(current_node->GetPos(), callback, user_data);

-				_Walk(current_node->GetNeg(), callback, user_data);

-			}

-		}

-	};

-	Local::_Walk(mNodes, callback, user_data);

-	return true;

-}

-

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Constructor.

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AABBNoLeafTree::AABBNoLeafTree() : mNodes(null)

-{

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Destructor.

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AABBNoLeafTree::~AABBNoLeafTree()

-{

-	DELETEARRAY(mNodes);

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Builds the collision tree from a generic AABB tree.

- *	\param		tree			[in] generic AABB tree

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBNoLeafTree::Build(AABBTree* tree)

-{

-	// Checkings

-	if(!tree)	return false;

-	// Check the input tree is complete

-	udword NbTriangles	= tree->GetNbPrimitives();

-	udword NbNodes		= tree->GetNbNodes();

-	if(NbNodes!=NbTriangles*2-1)	return false;

-

-	// Get nodes

-	if(mNbNodes!=NbTriangles-1)	// Same number of nodes => keep moving

-	{

-		mNbNodes = NbTriangles-1;

-		DELETEARRAY(mNodes);

-		mNodes = new AABBNoLeafNode[mNbNodes];

-		CHECKALLOC(mNodes);

-	}

-

-	// Build the tree

-	udword CurID = 1;

-	_BuildNoLeafTree(mNodes, 0, CurID, tree);

-	ASSERT(CurID==mNbNodes);

-

-	return true;

-}

-

-inline_ void ComputeMinMax(IcePoint& min, IcePoint& max, const VertexPointers& vp)

-{

-	// Compute triangle's AABB = a leaf box

-#ifdef OPC_USE_FCOMI	// a 15% speedup on my machine, not much

-	min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);

-	max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);

-

-	min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);

-	max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);

-

-	min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);

-	max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);

-#else

-	min = *vp.Vertex[0];

-	max = *vp.Vertex[0];

-	min.Min(*vp.Vertex[1]);

-	max.Max(*vp.Vertex[1]);

-	min.Min(*vp.Vertex[2]);

-	max.Max(*vp.Vertex[2]);

-#endif

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Refits the collision tree after vertices have been modified.

- *	\param		mesh_interface	[in] mesh interface for current model

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBNoLeafTree::Refit(const MeshInterface* mesh_interface)

-{

-	// Checkings

-	if(!mesh_interface)	return false;

-

-	// Bottom-up update

-	VertexPointers VP;

-	IcePoint Min,Max;

-	IcePoint Min_,Max_;

-	udword Index = mNbNodes;

-	while(Index--)

-	{

-		AABBNoLeafNode& Current = mNodes[Index];

-

-		if(Current.HasPosLeaf())

-		{

-			mesh_interface->GetTriangle(VP, Current.GetPosPrimitive());

-			ComputeMinMax(Min, Max, VP);

-		}

-		else

-		{

-			const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;

-			CurrentBox.GetMin(Min);

-			CurrentBox.GetMax(Max);

-		}

-

-		if(Current.HasNegLeaf())

-		{

-			mesh_interface->GetTriangle(VP, Current.GetNegPrimitive());

-			ComputeMinMax(Min_, Max_, VP);

-		}

-		else

-		{

-			const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;

-			CurrentBox.GetMin(Min_);

-			CurrentBox.GetMax(Max_);

-		}

-#ifdef OPC_USE_FCOMI

-		Min.x = FCMin2(Min.x, Min_.x);

-		Max.x = FCMax2(Max.x, Max_.x);

-		Min.y = FCMin2(Min.y, Min_.y);

-		Max.y = FCMax2(Max.y, Max_.y);

-		Min.z = FCMin2(Min.z, Min_.z);

-		Max.z = FCMax2(Max.z, Max_.z);

-#else

-		Min.Min(Min_);

-		Max.Max(Max_);

-#endif

-		Current.mAABB.SetMinMax(Min, Max);

-	}

-	return true;

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Walks the tree and call the user back for each node.

- *	\param		callback	[in] walking callback

- *	\param		user_data	[in] callback's user data

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const

-{

-	if(!callback)	return false;

-

-	struct Local

-	{

-		static void _Walk(const AABBNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data)

-		{

-			if(!current_node || !(callback)(current_node, user_data))	return;

-

-			if(!current_node->HasPosLeaf())	_Walk(current_node->GetPos(), callback, user_data);

-			if(!current_node->HasNegLeaf())	_Walk(current_node->GetNeg(), callback, user_data);

-		}

-	};

-	Local::_Walk(mNodes, callback, user_data);

-	return true;

-}

-

-// Quantization notes:

-// - We could use the highest bits of mData to store some more quantized bits. Dequantization code

-//   would be slightly more complex, but number of overlap tests would be reduced (and anyhow those

-//   bits are currently wasted). Of course it's not possible if we move to 16 bits mData.

-// - Something like "16 bits floats" could be tested, to bypass the int-to-float conversion.

-// - A dedicated BV-BV test could be used, dequantizing while testing for overlap. (i.e. it's some

-//   lazy-dequantization which may save some work in case of early exits). At the very least some

-//   muls could be saved by precomputing several more matrices. But maybe not worth the pain.

-// - Do we need to dequantize anyway? Not doing the extents-related muls only implies the box has

-//   been scaled, for example.

-// - The deeper we move into the hierarchy, the smaller the extents should be. May not need a fixed

-//   number of quantization bits. Even better, could probably be best delta-encoded.

-

-

-// Find max values. Some people asked why I wasn't simply using the first node. Well, I can't.

-// I'm not looking for (min, max) values like in a standard AABB, I'm looking for the extremal

-// centers/extents in order to quantize them. The first node would only give a single center and

-// a single extents. While extents would be the biggest, the center wouldn't.

-#define FIND_MAX_VALUES																			\

-	/* Get max values */																		\

-	IcePoint CMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);												\

-	IcePoint EMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);												\

-	for(udword i=0;i<mNbNodes;i++)																\

-	{																							\

-		if(fabsf(Nodes[i].mAABB.mCenter.x)>CMax.x)	CMax.x = fabsf(Nodes[i].mAABB.mCenter.x);	\

-		if(fabsf(Nodes[i].mAABB.mCenter.y)>CMax.y)	CMax.y = fabsf(Nodes[i].mAABB.mCenter.y);	\

-		if(fabsf(Nodes[i].mAABB.mCenter.z)>CMax.z)	CMax.z = fabsf(Nodes[i].mAABB.mCenter.z);	\

-		if(fabsf(Nodes[i].mAABB.mExtents.x)>EMax.x)	EMax.x = fabsf(Nodes[i].mAABB.mExtents.x);	\

-		if(fabsf(Nodes[i].mAABB.mExtents.y)>EMax.y)	EMax.y = fabsf(Nodes[i].mAABB.mExtents.y);	\

-		if(fabsf(Nodes[i].mAABB.mExtents.z)>EMax.z)	EMax.z = fabsf(Nodes[i].mAABB.mExtents.z);	\

-	}

-

-#define INIT_QUANTIZATION													\

-	udword nbc=15;	/* Keep one bit for sign */								\

-	udword nbe=15;	/* Keep one bit for fix */								\

-	if(!gFixQuantized) nbe++;												\

-																			\

-	/* Compute quantization coeffs */										\

-	IcePoint CQuantCoeff, EQuantCoeff;											\

-	CQuantCoeff.x = CMax.x!=0.0f ? float((1<<nbc)-1)/CMax.x : 0.0f;			\

-	CQuantCoeff.y = CMax.y!=0.0f ? float((1<<nbc)-1)/CMax.y : 0.0f;			\

-	CQuantCoeff.z = CMax.z!=0.0f ? float((1<<nbc)-1)/CMax.z : 0.0f;			\

-	EQuantCoeff.x = EMax.x!=0.0f ? float((1<<nbe)-1)/EMax.x : 0.0f;			\

-	EQuantCoeff.y = EMax.y!=0.0f ? float((1<<nbe)-1)/EMax.y : 0.0f;			\

-	EQuantCoeff.z = EMax.z!=0.0f ? float((1<<nbe)-1)/EMax.z : 0.0f;			\

-	/* Compute and save dequantization coeffs */							\

-	mCenterCoeff.x = CQuantCoeff.x!=0.0f ? 1.0f / CQuantCoeff.x : 0.0f;		\

-	mCenterCoeff.y = CQuantCoeff.y!=0.0f ? 1.0f / CQuantCoeff.y : 0.0f;		\

-	mCenterCoeff.z = CQuantCoeff.z!=0.0f ? 1.0f / CQuantCoeff.z : 0.0f;		\

-	mExtentsCoeff.x = EQuantCoeff.x!=0.0f ? 1.0f / EQuantCoeff.x : 0.0f;	\

-	mExtentsCoeff.y = EQuantCoeff.y!=0.0f ? 1.0f / EQuantCoeff.y : 0.0f;	\

-	mExtentsCoeff.z = EQuantCoeff.z!=0.0f ? 1.0f / EQuantCoeff.z : 0.0f;	\

-

-#define PERFORM_QUANTIZATION														\

-	/* Quantize */																	\

-	mNodes[i].mAABB.mCenter[0] = sword(Nodes[i].mAABB.mCenter.x * CQuantCoeff.x);	\

-	mNodes[i].mAABB.mCenter[1] = sword(Nodes[i].mAABB.mCenter.y * CQuantCoeff.y);	\

-	mNodes[i].mAABB.mCenter[2] = sword(Nodes[i].mAABB.mCenter.z * CQuantCoeff.z);	\

-	mNodes[i].mAABB.mExtents[0] = uword(Nodes[i].mAABB.mExtents.x * EQuantCoeff.x);	\

-	mNodes[i].mAABB.mExtents[1] = uword(Nodes[i].mAABB.mExtents.y * EQuantCoeff.y);	\

-	mNodes[i].mAABB.mExtents[2] = uword(Nodes[i].mAABB.mExtents.z * EQuantCoeff.z);	\

-	/* Fix quantized boxes */														\

-	if(gFixQuantized)																\

-	{																				\

-		/* Make sure the quantized box is still valid */							\

-		IcePoint Max = Nodes[i].mAABB.mCenter + Nodes[i].mAABB.mExtents;				\

-		IcePoint Min = Nodes[i].mAABB.mCenter - Nodes[i].mAABB.mExtents;				\

-		/* For each axis */															\

-		for(udword j=0;j<3;j++)														\

-		{	/* Dequantize the box center */											\

-			float qc = float(mNodes[i].mAABB.mCenter[j]) * mCenterCoeff[j];			\

-			bool FixMe=true;														\

-			do																		\

-			{	/* Dequantize the box extent */										\

-				float qe = float(mNodes[i].mAABB.mExtents[j]) * mExtentsCoeff[j];	\

-				/* Compare real & dequantized values */								\

-				if(qc+qe<Max[j] || qc-qe>Min[j])	mNodes[i].mAABB.mExtents[j]++;	\

-				else								FixMe=false;					\

-				/* Prevent wrapping */												\

-				if(!mNodes[i].mAABB.mExtents[j])									\

-				{																	\

-					mNodes[i].mAABB.mExtents[j]=0xffff;								\

-					FixMe=false;													\

-				}																	\

-			}while(FixMe);															\

-		}																			\

-	}

-

-#define REMAP_DATA(member)											\

-	/* Fix data */													\

-	Data = Nodes[i].member;											\

-	if(!(Data&1))													\

-	{																\

-		/* Compute box number */									\

-		udword Nb = (Data - udword(Nodes))/Nodes[i].GetNodeSize();	\

-		Data = udword(&mNodes[Nb]);									\

-	}																\

-	/* ...remapped */												\

-	mNodes[i].member = Data;

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Constructor.

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AABBQuantizedTree::AABBQuantizedTree() : mNodes(null)

-{

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Destructor.

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AABBQuantizedTree::~AABBQuantizedTree()

-{

-	DELETEARRAY(mNodes);

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Builds the collision tree from a generic AABB tree.

- *	\param		tree			[in] generic AABB tree

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBQuantizedTree::Build(AABBTree* tree)

-{

-	// Checkings

-	if(!tree)	return false;

-	// Check the input tree is complete

-	udword NbTriangles	= tree->GetNbPrimitives();

-	udword NbNodes		= tree->GetNbNodes();

-	if(NbNodes!=NbTriangles*2-1)	return false;

-

-	// Get nodes

-	mNbNodes = NbNodes;

-	DELETEARRAY(mNodes);

-	AABBCollisionNode* Nodes = new AABBCollisionNode[mNbNodes];

-	CHECKALLOC(Nodes);

-

-	// Build the tree

-	udword CurID = 1;

-	_BuildCollisionTree(Nodes, 0, CurID, tree);

-

-	// Quantize

-	{

-		mNodes = new AABBQuantizedNode[mNbNodes];

-		CHECKALLOC(mNodes);

-

-		// Get max values

-		FIND_MAX_VALUES

-

-		// Quantization

-		INIT_QUANTIZATION

-

-		// Quantize

-		udword Data;

-		for(udword i=0;i<mNbNodes;i++)

-		{

-			PERFORM_QUANTIZATION

-			REMAP_DATA(mData)

-		}

-

-		DELETEARRAY(Nodes);

-	}

-

-	return true;

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Refits the collision tree after vertices have been modified.

- *	\param		mesh_interface	[in] mesh interface for current model

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBQuantizedTree::Refit(const MeshInterface* mesh_interface)

-{

-	ASSERT(!"Not implemented since requantizing is painful !");

-	return false;

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Walks the tree and call the user back for each node.

- *	\param		callback	[in] walking callback

- *	\param		user_data	[in] callback's user data

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBQuantizedTree::Walk(GenericWalkingCallback callback, void* user_data) const

-{

-	if(!callback)	return false;

-

-	struct Local

-	{

-		static void _Walk(const AABBQuantizedNode* current_node, GenericWalkingCallback callback, void* user_data)

-		{

-			if(!current_node || !(callback)(current_node, user_data))	return;

-

-			if(!current_node->IsLeaf())

-			{

-				_Walk(current_node->GetPos(), callback, user_data);

-				_Walk(current_node->GetNeg(), callback, user_data);

-			}

-		}

-	};

-	Local::_Walk(mNodes, callback, user_data);

-	return true;

-}

-

-

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Constructor.

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AABBQuantizedNoLeafTree::AABBQuantizedNoLeafTree() : mNodes(null)

-{

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Destructor.

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-AABBQuantizedNoLeafTree::~AABBQuantizedNoLeafTree()

-{

-	DELETEARRAY(mNodes);

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Builds the collision tree from a generic AABB tree.

- *	\param		tree			[in] generic AABB tree

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBQuantizedNoLeafTree::Build(AABBTree* tree)

-{

-	// Checkings

-	if(!tree)	return false;

-	// Check the input tree is complete

-	udword NbTriangles	= tree->GetNbPrimitives();

-	udword NbNodes		= tree->GetNbNodes();

-	if(NbNodes!=NbTriangles*2-1)	return false;

-

-	// Get nodes

-	mNbNodes = NbTriangles-1;

-	DELETEARRAY(mNodes);

-	AABBNoLeafNode* Nodes = new AABBNoLeafNode[mNbNodes];

-	CHECKALLOC(Nodes);

-

-	// Build the tree

-	udword CurID = 1;

-	_BuildNoLeafTree(Nodes, 0, CurID, tree);

-	ASSERT(CurID==mNbNodes);

-

-	// Quantize

-	{

-		mNodes = new AABBQuantizedNoLeafNode[mNbNodes];

-		CHECKALLOC(mNodes);

-

-		// Get max values

-		FIND_MAX_VALUES

-

-		// Quantization

-		INIT_QUANTIZATION

-

-		// Quantize

-		udword Data;

-		for(udword i=0;i<mNbNodes;i++)

-		{

-			PERFORM_QUANTIZATION

-			REMAP_DATA(mPosData)

-			REMAP_DATA(mNegData)

-		}

-

-		DELETEARRAY(Nodes);

-	}

-

-	return true;

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Refits the collision tree after vertices have been modified.

- *	\param		mesh_interface	[in] mesh interface for current model

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBQuantizedNoLeafTree::Refit(const MeshInterface* mesh_interface)

-{

-	ASSERT(!"Not implemented since requantizing is painful !");

-	return false;

-}

-

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-/**

- *	Walks the tree and call the user back for each node.

- *	\param		callback	[in] walking callback

- *	\param		user_data	[in] callback's user data

- *	\return		true if success

- */

-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

-bool AABBQuantizedNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const

-{

-	if(!callback)	return false;

-

-	struct Local

-	{

-		static void _Walk(const AABBQuantizedNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data)

-		{

-			if(!current_node || !(callback)(current_node, user_data))	return;

-

-			if(!current_node->HasPosLeaf())	_Walk(current_node->GetPos(), callback, user_data);

-			if(!current_node->HasNegLeaf())	_Walk(current_node->GetNeg(), callback, user_data);

-		}

-	};

-	Local::_Walk(mNodes, callback, user_data);

-	return true;

-}

+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/*
+ *	OPCODE - Optimized Collision Detection
+ *	Copyright (C) 2001 Pierre Terdiman
+ *	Homepage: http://www.codercorner.com/Opcode.htm
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Contains code for optimized trees. Implements 4 trees:
+ *	- normal
+ *	- no leaf
+ *	- quantized
+ *	- no leaf / quantized
+ *
+ *	\file		OPC_OptimizedTree.cpp
+ *	\author		Pierre Terdiman
+ *	\date		March, 20, 2001
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	A standard AABB tree.
+ *
+ *	\class		AABBCollisionTree
+ *	\author		Pierre Terdiman
+ *	\version	1.3
+ *	\date		March, 20, 2001
+*/
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	A no-leaf AABB tree.
+ *
+ *	\class		AABBNoLeafTree
+ *	\author		Pierre Terdiman
+ *	\version	1.3
+ *	\date		March, 20, 2001
+*/
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	A quantized AABB tree.
+ *
+ *	\class		AABBQuantizedTree
+ *	\author		Pierre Terdiman
+ *	\version	1.3
+ *	\date		March, 20, 2001
+*/
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	A quantized no-leaf AABB tree.
+ *
+ *	\class		AABBQuantizedNoLeafTree
+ *	\author		Pierre Terdiman
+ *	\version	1.3
+ *	\date		March, 20, 2001
+*/
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// Precompiled Header
+#include "StdAfx.h"
+
+using namespace Opcode;
+
+//! Compilation flag:
+//! - true to fix quantized boxes (i.e. make sure they enclose the original ones)
+//! - false to see the effects of quantization errors (faster, but wrong results in some cases)
+static bool gFixQuantized = true;
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Builds an implicit tree from a standard one. An implicit tree is a complete tree (2*N-1 nodes) whose negative
+ *	box pointers and primitive pointers have been made implicit, hence packing 3 pointers in one.
+ *
+ *	Layout for implicit trees:
+ *	Node:
+ *			- box
+ *			- data (32-bits value)
+ *
+ *	if data's LSB = 1 =>	remaining bits are a primitive pointer
+ *	else					remaining bits are a P-node pointer, and N = P + 1
+ *
+ *	\relates	AABBCollisionNode
+ *	\fn			_BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
+ *	\param		linear			[in] base address of destination nodes
+ *	\param		box_id			[in] index of destination node
+ *	\param		current_id		[in] current running index
+ *	\param		current_node	[in] current node from input tree
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+static void _BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
+{
+	// Current node from input tree is "current_node". Must be flattened into "linear[boxid]".
+
+	// Store the AABB
+	current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);
+	current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);
+	// Store remaining info
+	if(current_node->IsLeaf())
+	{
+		// The input tree must be complete => i.e. one primitive/leaf
+		ASSERT(current_node->GetNbPrimitives()==1);
+		// Get the primitive index from the input tree
+		udword PrimitiveIndex = current_node->GetPrimitives()[0];
+		// Setup box data as the primitive index, marked as leaf
+		linear[box_id].mData = (PrimitiveIndex<<1)|1;
+	}
+	else
+	{
+		// To make the negative one implicit, we must store P and N in successive order
+		udword PosID = current_id++;	// Get a new id for positive child
+		udword NegID = current_id++;	// Get a new id for negative child
+		// Setup box data as the forthcoming new P pointer
+		linear[box_id].mData = (udword)&linear[PosID];
+		// Make sure it's not marked as leaf
+		ASSERT(!(linear[box_id].mData&1));
+		// Recurse with new IDs
+		_BuildCollisionTree(linear, PosID, current_id, current_node->GetPos());
+		_BuildCollisionTree(linear, NegID, current_id, current_node->GetNeg());
+	}
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Builds a "no-leaf" tree from a standard one. This is a tree whose leaf nodes have been removed.
+ *
+ *	Layout for no-leaf trees:
+ *
+ *	Node:
+ *			- box
+ *			- P pointer => a node (LSB=0) or a primitive (LSB=1)
+ *			- N pointer => a node (LSB=0) or a primitive (LSB=1)
+ *
+ *	\relates	AABBNoLeafNode
+ *	\fn			_BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
+ *	\param		linear			[in] base address of destination nodes
+ *	\param		box_id			[in] index of destination node
+ *	\param		current_id		[in] current running index
+ *	\param		current_node	[in] current node from input tree
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+static void _BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
+{
+	const AABBTreeNode* P = current_node->GetPos();
+	const AABBTreeNode* N = current_node->GetNeg();
+	// Leaf nodes here?!
+	ASSERT(P);
+	ASSERT(N);
+	// Internal node => keep the box
+	current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);
+	current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);
+
+	if(P->IsLeaf())
+	{
+		// The input tree must be complete => i.e. one primitive/leaf
+		ASSERT(P->GetNbPrimitives()==1);
+		// Get the primitive index from the input tree
+		udword PrimitiveIndex = P->GetPrimitives()[0];
+		// Setup prev box data as the primitive index, marked as leaf
+		linear[box_id].mPosData = (PrimitiveIndex<<1)|1;
+	}
+	else
+	{
+		// Get a new id for positive child
+		udword PosID = current_id++;
+		// Setup box data
+		linear[box_id].mPosData = (udword)&linear[PosID];
+		// Make sure it's not marked as leaf
+		ASSERT(!(linear[box_id].mPosData&1));
+		// Recurse
+		_BuildNoLeafTree(linear, PosID, current_id, P);
+	}
+
+	if(N->IsLeaf())
+	{
+		// The input tree must be complete => i.e. one primitive/leaf
+		ASSERT(N->GetNbPrimitives()==1);
+		// Get the primitive index from the input tree
+		udword PrimitiveIndex = N->GetPrimitives()[0];
+		// Setup prev box data as the primitive index, marked as leaf
+		linear[box_id].mNegData = (PrimitiveIndex<<1)|1;
+	}
+	else
+	{
+		// Get a new id for negative child
+		udword NegID = current_id++;
+		// Setup box data
+		linear[box_id].mNegData = (udword)&linear[NegID];
+		// Make sure it's not marked as leaf
+		ASSERT(!(linear[box_id].mNegData&1));
+		// Recurse
+		_BuildNoLeafTree(linear, NegID, current_id, N);
+	}
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Constructor.
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+AABBCollisionTree::AABBCollisionTree() : mNodes(null)
+{
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Destructor.
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+AABBCollisionTree::~AABBCollisionTree()
+{
+	DELETEARRAY(mNodes);
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Builds the collision tree from a generic AABB tree.
+ *	\param		tree			[in] generic AABB tree
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBCollisionTree::Build(AABBTree* tree)
+{
+	// Checkings
+	if(!tree)	return false;
+	// Check the input tree is complete
+	udword NbTriangles	= tree->GetNbPrimitives();
+	udword NbNodes		= tree->GetNbNodes();
+	if(NbNodes!=NbTriangles*2-1)	return false;
+
+	// Get nodes
+	if(mNbNodes!=NbNodes)	// Same number of nodes => keep moving
+	{
+		mNbNodes = NbNodes;
+		DELETEARRAY(mNodes);
+		mNodes = new AABBCollisionNode[mNbNodes];
+		CHECKALLOC(mNodes);
+	}
+
+	// Build the tree
+	udword CurID = 1;
+	_BuildCollisionTree(mNodes, 0, CurID, tree);
+	ASSERT(CurID==mNbNodes);
+
+	return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Refits the collision tree after vertices have been modified.
+ *	\param		mesh_interface	[in] mesh interface for current model
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBCollisionTree::Refit(const MeshInterface* mesh_interface)
+{
+	ASSERT(!"Not implemented since AABBCollisionTrees have twice as more nodes to refit as AABBNoLeafTrees!");
+	return false;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Walks the tree and call the user back for each node.
+ *	\param		callback	[in] walking callback
+ *	\param		user_data	[in] callback's user data
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBCollisionTree::Walk(GenericWalkingCallback callback, void* user_data) const
+{
+	if(!callback)	return false;
+
+	struct Local
+	{
+		static void _Walk(const AABBCollisionNode* current_node, GenericWalkingCallback callback, void* user_data)
+		{
+			if(!current_node || !(callback)(current_node, user_data))	return;
+
+			if(!current_node->IsLeaf())
+			{
+				_Walk(current_node->GetPos(), callback, user_data);
+				_Walk(current_node->GetNeg(), callback, user_data);
+			}
+		}
+	};
+	Local::_Walk(mNodes, callback, user_data);
+	return true;
+}
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Constructor.
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+AABBNoLeafTree::AABBNoLeafTree() : mNodes(null)
+{
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Destructor.
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+AABBNoLeafTree::~AABBNoLeafTree()
+{
+	DELETEARRAY(mNodes);
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Builds the collision tree from a generic AABB tree.
+ *	\param		tree			[in] generic AABB tree
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBNoLeafTree::Build(AABBTree* tree)
+{
+	// Checkings
+	if(!tree)	return false;
+	// Check the input tree is complete
+	udword NbTriangles	= tree->GetNbPrimitives();
+	udword NbNodes		= tree->GetNbNodes();
+	if(NbNodes!=NbTriangles*2-1)	return false;
+
+	// Get nodes
+	if(mNbNodes!=NbTriangles-1)	// Same number of nodes => keep moving
+	{
+		mNbNodes = NbTriangles-1;
+		DELETEARRAY(mNodes);
+		mNodes = new AABBNoLeafNode[mNbNodes];
+		CHECKALLOC(mNodes);
+	}
+
+	// Build the tree
+	udword CurID = 1;
+	_BuildNoLeafTree(mNodes, 0, CurID, tree);
+	ASSERT(CurID==mNbNodes);
+
+	return true;
+}
+
+inline_ void ComputeMinMax(IcePoint& min, IcePoint& max, const VertexPointers& vp)
+{
+	// Compute triangle's AABB = a leaf box
+#ifdef OPC_USE_FCOMI	// a 15% speedup on my machine, not much
+	min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
+	max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
+
+	min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
+	max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
+
+	min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
+	max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
+#else
+	min = *vp.Vertex[0];
+	max = *vp.Vertex[0];
+	min.Min(*vp.Vertex[1]);
+	max.Max(*vp.Vertex[1]);
+	min.Min(*vp.Vertex[2]);
+	max.Max(*vp.Vertex[2]);
+#endif
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Refits the collision tree after vertices have been modified.
+ *	\param		mesh_interface	[in] mesh interface for current model
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBNoLeafTree::Refit(const MeshInterface* mesh_interface)
+{
+	// Checkings
+	if(!mesh_interface)	return false;
+
+	// Bottom-up update
+	VertexPointers VP;
+	IcePoint Min,Max;
+	IcePoint Min_,Max_;
+	udword Index = mNbNodes;
+	while(Index--)
+	{
+		AABBNoLeafNode& Current = mNodes[Index];
+
+		if(Current.HasPosLeaf())
+		{
+			mesh_interface->GetTriangle(VP, Current.GetPosPrimitive());
+			ComputeMinMax(Min, Max, VP);
+		}
+		else
+		{
+			const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;
+			CurrentBox.GetMin(Min);
+			CurrentBox.GetMax(Max);
+		}
+
+		if(Current.HasNegLeaf())
+		{
+			mesh_interface->GetTriangle(VP, Current.GetNegPrimitive());
+			ComputeMinMax(Min_, Max_, VP);
+		}
+		else
+		{
+			const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;
+			CurrentBox.GetMin(Min_);
+			CurrentBox.GetMax(Max_);
+		}
+#ifdef OPC_USE_FCOMI
+		Min.x = FCMin2(Min.x, Min_.x);
+		Max.x = FCMax2(Max.x, Max_.x);
+		Min.y = FCMin2(Min.y, Min_.y);
+		Max.y = FCMax2(Max.y, Max_.y);
+		Min.z = FCMin2(Min.z, Min_.z);
+		Max.z = FCMax2(Max.z, Max_.z);
+#else
+		Min.Min(Min_);
+		Max.Max(Max_);
+#endif
+		Current.mAABB.SetMinMax(Min, Max);
+	}
+	return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Walks the tree and call the user back for each node.
+ *	\param		callback	[in] walking callback
+ *	\param		user_data	[in] callback's user data
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const
+{
+	if(!callback)	return false;
+
+	struct Local
+	{
+		static void _Walk(const AABBNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data)
+		{
+			if(!current_node || !(callback)(current_node, user_data))	return;
+
+			if(!current_node->HasPosLeaf())	_Walk(current_node->GetPos(), callback, user_data);
+			if(!current_node->HasNegLeaf())	_Walk(current_node->GetNeg(), callback, user_data);
+		}
+	};
+	Local::_Walk(mNodes, callback, user_data);
+	return true;
+}
+
+// Quantization notes:
+// - We could use the highest bits of mData to store some more quantized bits. Dequantization code
+//   would be slightly more complex, but number of overlap tests would be reduced (and anyhow those
+//   bits are currently wasted). Of course it's not possible if we move to 16 bits mData.
+// - Something like "16 bits floats" could be tested, to bypass the int-to-float conversion.
+// - A dedicated BV-BV test could be used, dequantizing while testing for overlap. (i.e. it's some
+//   lazy-dequantization which may save some work in case of early exits). At the very least some
+//   muls could be saved by precomputing several more matrices. But maybe not worth the pain.
+// - Do we need to dequantize anyway? Not doing the extents-related muls only implies the box has
+//   been scaled, for example.
+// - The deeper we move into the hierarchy, the smaller the extents should be. May not need a fixed
+//   number of quantization bits. Even better, could probably be best delta-encoded.
+
+
+// Find max values. Some people asked why I wasn't simply using the first node. Well, I can't.
+// I'm not looking for (min, max) values like in a standard AABB, I'm looking for the extremal
+// centers/extents in order to quantize them. The first node would only give a single center and
+// a single extents. While extents would be the biggest, the center wouldn't.
+#define FIND_MAX_VALUES																			\
+	/* Get max values */																		\
+	IcePoint CMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);												\
+	IcePoint EMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);												\
+	for(udword i=0;i<mNbNodes;i++)																\
+	{																							\
+		if(fabsf(Nodes[i].mAABB.mCenter.x)>CMax.x)	CMax.x = fabsf(Nodes[i].mAABB.mCenter.x);	\
+		if(fabsf(Nodes[i].mAABB.mCenter.y)>CMax.y)	CMax.y = fabsf(Nodes[i].mAABB.mCenter.y);	\
+		if(fabsf(Nodes[i].mAABB.mCenter.z)>CMax.z)	CMax.z = fabsf(Nodes[i].mAABB.mCenter.z);	\
+		if(fabsf(Nodes[i].mAABB.mExtents.x)>EMax.x)	EMax.x = fabsf(Nodes[i].mAABB.mExtents.x);	\
+		if(fabsf(Nodes[i].mAABB.mExtents.y)>EMax.y)	EMax.y = fabsf(Nodes[i].mAABB.mExtents.y);	\
+		if(fabsf(Nodes[i].mAABB.mExtents.z)>EMax.z)	EMax.z = fabsf(Nodes[i].mAABB.mExtents.z);	\
+	}
+
+#define INIT_QUANTIZATION													\
+	udword nbc=15;	/* Keep one bit for sign */								\
+	udword nbe=15;	/* Keep one bit for fix */								\
+	if(!gFixQuantized) nbe++;												\
+																			\
+	/* Compute quantization coeffs */										\
+	IcePoint CQuantCoeff, EQuantCoeff;											\
+	CQuantCoeff.x = CMax.x!=0.0f ? float((1<<nbc)-1)/CMax.x : 0.0f;			\
+	CQuantCoeff.y = CMax.y!=0.0f ? float((1<<nbc)-1)/CMax.y : 0.0f;			\
+	CQuantCoeff.z = CMax.z!=0.0f ? float((1<<nbc)-1)/CMax.z : 0.0f;			\
+	EQuantCoeff.x = EMax.x!=0.0f ? float((1<<nbe)-1)/EMax.x : 0.0f;			\
+	EQuantCoeff.y = EMax.y!=0.0f ? float((1<<nbe)-1)/EMax.y : 0.0f;			\
+	EQuantCoeff.z = EMax.z!=0.0f ? float((1<<nbe)-1)/EMax.z : 0.0f;			\
+	/* Compute and save dequantization coeffs */							\
+	mCenterCoeff.x = CQuantCoeff.x!=0.0f ? 1.0f / CQuantCoeff.x : 0.0f;		\
+	mCenterCoeff.y = CQuantCoeff.y!=0.0f ? 1.0f / CQuantCoeff.y : 0.0f;		\
+	mCenterCoeff.z = CQuantCoeff.z!=0.0f ? 1.0f / CQuantCoeff.z : 0.0f;		\
+	mExtentsCoeff.x = EQuantCoeff.x!=0.0f ? 1.0f / EQuantCoeff.x : 0.0f;	\
+	mExtentsCoeff.y = EQuantCoeff.y!=0.0f ? 1.0f / EQuantCoeff.y : 0.0f;	\
+	mExtentsCoeff.z = EQuantCoeff.z!=0.0f ? 1.0f / EQuantCoeff.z : 0.0f;	\
+
+#define PERFORM_QUANTIZATION														\
+	/* Quantize */																	\
+	mNodes[i].mAABB.mCenter[0] = sword(Nodes[i].mAABB.mCenter.x * CQuantCoeff.x);	\
+	mNodes[i].mAABB.mCenter[1] = sword(Nodes[i].mAABB.mCenter.y * CQuantCoeff.y);	\
+	mNodes[i].mAABB.mCenter[2] = sword(Nodes[i].mAABB.mCenter.z * CQuantCoeff.z);	\
+	mNodes[i].mAABB.mExtents[0] = uword(Nodes[i].mAABB.mExtents.x * EQuantCoeff.x);	\
+	mNodes[i].mAABB.mExtents[1] = uword(Nodes[i].mAABB.mExtents.y * EQuantCoeff.y);	\
+	mNodes[i].mAABB.mExtents[2] = uword(Nodes[i].mAABB.mExtents.z * EQuantCoeff.z);	\
+	/* Fix quantized boxes */														\
+	if(gFixQuantized)																\
+	{																				\
+		/* Make sure the quantized box is still valid */							\
+		IcePoint Max = Nodes[i].mAABB.mCenter + Nodes[i].mAABB.mExtents;				\
+		IcePoint Min = Nodes[i].mAABB.mCenter - Nodes[i].mAABB.mExtents;				\
+		/* For each axis */															\
+		for(udword j=0;j<3;j++)														\
+		{	/* Dequantize the box center */											\
+			float qc = float(mNodes[i].mAABB.mCenter[j]) * mCenterCoeff[j];			\
+			bool FixMe=true;														\
+			do																		\
+			{	/* Dequantize the box extent */										\
+				float qe = float(mNodes[i].mAABB.mExtents[j]) * mExtentsCoeff[j];	\
+				/* Compare real & dequantized values */								\
+				if(qc+qe<Max[j] || qc-qe>Min[j])	mNodes[i].mAABB.mExtents[j]++;	\
+				else								FixMe=false;					\
+				/* Prevent wrapping */												\
+				if(!mNodes[i].mAABB.mExtents[j])									\
+				{																	\
+					mNodes[i].mAABB.mExtents[j]=0xffff;								\
+					FixMe=false;													\
+				}																	\
+			}while(FixMe);															\
+		}																			\
+	}
+
+#define REMAP_DATA(member)											\
+	/* Fix data */													\
+	Data = Nodes[i].member;											\
+	if(!(Data&1))													\
+	{																\
+		/* Compute box number */									\
+		udword Nb = (Data - udword(Nodes))/Nodes[i].GetNodeSize();	\
+		Data = udword(&mNodes[Nb]);									\
+	}																\
+	/* ...remapped */												\
+	mNodes[i].member = Data;
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Constructor.
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+AABBQuantizedTree::AABBQuantizedTree() : mNodes(null)
+{
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Destructor.
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+AABBQuantizedTree::~AABBQuantizedTree()
+{
+	DELETEARRAY(mNodes);
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Builds the collision tree from a generic AABB tree.
+ *	\param		tree			[in] generic AABB tree
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBQuantizedTree::Build(AABBTree* tree)
+{
+	// Checkings
+	if(!tree)	return false;
+	// Check the input tree is complete
+	udword NbTriangles	= tree->GetNbPrimitives();
+	udword NbNodes		= tree->GetNbNodes();
+	if(NbNodes!=NbTriangles*2-1)	return false;
+
+	// Get nodes
+	mNbNodes = NbNodes;
+	DELETEARRAY(mNodes);
+	AABBCollisionNode* Nodes = new AABBCollisionNode[mNbNodes];
+	CHECKALLOC(Nodes);
+
+	// Build the tree
+	udword CurID = 1;
+	_BuildCollisionTree(Nodes, 0, CurID, tree);
+
+	// Quantize
+	{
+		mNodes = new AABBQuantizedNode[mNbNodes];
+		CHECKALLOC(mNodes);
+
+		// Get max values
+		FIND_MAX_VALUES
+
+		// Quantization
+		INIT_QUANTIZATION
+
+		// Quantize
+		udword Data;
+		for(udword i=0;i<mNbNodes;i++)
+		{
+			PERFORM_QUANTIZATION
+			REMAP_DATA(mData)
+		}
+
+		DELETEARRAY(Nodes);
+	}
+
+	return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Refits the collision tree after vertices have been modified.
+ *	\param		mesh_interface	[in] mesh interface for current model
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBQuantizedTree::Refit(const MeshInterface* mesh_interface)
+{
+	ASSERT(!"Not implemented since requantizing is painful !");
+	return false;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Walks the tree and call the user back for each node.
+ *	\param		callback	[in] walking callback
+ *	\param		user_data	[in] callback's user data
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBQuantizedTree::Walk(GenericWalkingCallback callback, void* user_data) const
+{
+	if(!callback)	return false;
+
+	struct Local
+	{
+		static void _Walk(const AABBQuantizedNode* current_node, GenericWalkingCallback callback, void* user_data)
+		{
+			if(!current_node || !(callback)(current_node, user_data))	return;
+
+			if(!current_node->IsLeaf())
+			{
+				_Walk(current_node->GetPos(), callback, user_data);
+				_Walk(current_node->GetNeg(), callback, user_data);
+			}
+		}
+	};
+	Local::_Walk(mNodes, callback, user_data);
+	return true;
+}
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Constructor.
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+AABBQuantizedNoLeafTree::AABBQuantizedNoLeafTree() : mNodes(null)
+{
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Destructor.
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+AABBQuantizedNoLeafTree::~AABBQuantizedNoLeafTree()
+{
+	DELETEARRAY(mNodes);
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Builds the collision tree from a generic AABB tree.
+ *	\param		tree			[in] generic AABB tree
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBQuantizedNoLeafTree::Build(AABBTree* tree)
+{
+	// Checkings
+	if(!tree)	return false;
+	// Check the input tree is complete
+	udword NbTriangles	= tree->GetNbPrimitives();
+	udword NbNodes		= tree->GetNbNodes();
+	if(NbNodes!=NbTriangles*2-1)	return false;
+
+	// Get nodes
+	mNbNodes = NbTriangles-1;
+	DELETEARRAY(mNodes);
+	AABBNoLeafNode* Nodes = new AABBNoLeafNode[mNbNodes];
+	CHECKALLOC(Nodes);
+
+	// Build the tree
+	udword CurID = 1;
+	_BuildNoLeafTree(Nodes, 0, CurID, tree);
+	ASSERT(CurID==mNbNodes);
+
+	// Quantize
+	{
+		mNodes = new AABBQuantizedNoLeafNode[mNbNodes];
+		CHECKALLOC(mNodes);
+
+		// Get max values
+		FIND_MAX_VALUES
+
+		// Quantization
+		INIT_QUANTIZATION
+
+		// Quantize
+		udword Data;
+		for(udword i=0;i<mNbNodes;i++)
+		{
+			PERFORM_QUANTIZATION
+			REMAP_DATA(mPosData)
+			REMAP_DATA(mNegData)
+		}
+
+		DELETEARRAY(Nodes);
+	}
+
+	return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Refits the collision tree after vertices have been modified.
+ *	\param		mesh_interface	[in] mesh interface for current model
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBQuantizedNoLeafTree::Refit(const MeshInterface* mesh_interface)
+{
+	ASSERT(!"Not implemented since requantizing is painful !");
+	return false;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ *	Walks the tree and call the user back for each node.
+ *	\param		callback	[in] walking callback
+ *	\param		user_data	[in] callback's user data
+ *	\return		true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBQuantizedNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const
+{
+	if(!callback)	return false;
+
+	struct Local
+	{
+		static void _Walk(const AABBQuantizedNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data)
+		{
+			if(!current_node || !(callback)(current_node, user_data))	return;
+
+			if(!current_node->HasPosLeaf())	_Walk(current_node->GetPos(), callback, user_data);
+			if(!current_node->HasNegLeaf())	_Walk(current_node->GetNeg(), callback, user_data);
+		}
+	};
+	Local::_Walk(mNodes, callback, user_data);
+	return true;
+}