Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: code/branches/ode/ode-0.9/OPCODE/OPC_OptimizedTree.cpp @ 216

Last change on this file since 216 was 216, checked in by mathiask, 17 years ago
[Physik] add ode-0.9
File size: 31.8 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: