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

Line
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: