Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

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

Last change on this file since 216 was 216, checked in by mathiask, 17 years ago
[Physik] add ode-0.9
File size: 9.2 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.
12	* \file OPC_OptimizedTree.h
13	* \author Pierre Terdiman
14	* \date March, 20, 2001
15	*/
16	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17
18	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
19	// Include Guard
20	#ifndef __OPC_OPTIMIZEDTREE_H__
21	#define __OPC_OPTIMIZEDTREE_H__
22
23	//! Common interface for a node of an implicit tree
24	#define IMPLEMENT_IMPLICIT_NODE(base_class, volume) \
25	public: \
26	/* Constructor / Destructor */ \
27	inline_ base_class() : mData(0) {} \
28	inline_ ~base_class() {} \
29	/* Leaf test */ \
30	inline_ BOOL IsLeaf() const { return (mData&1)!=0; } \
31	/* Data access */ \
32	inline_ const base_class* GetPos() const { return (base_class*)mData; } \
33	inline_ const base_class* GetNeg() const { return ((base_class*)mData)+1; } \
34	inline_ size_t GetPrimitive() const { return (mData>>1); } \
35	/* Stats */ \
36	inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
37	\
38	volume mAABB; \
39	size_t mData;
40
41	//! Common interface for a node of a no-leaf tree
42	#define IMPLEMENT_NOLEAF_NODE(base_class, volume) \
43	public: \
44	/* Constructor / Destructor */ \
45	inline_ base_class() : mPosData(0), mNegData(0) {} \
46	inline_ ~base_class() {} \
47	/* Leaf tests */ \
48	inline_ BOOL HasPosLeaf() const { return (mPosData&1)!=0; } \
49	inline_ BOOL HasNegLeaf() const { return (mNegData&1)!=0; } \
50	/* Data access */ \
51	inline_ const base_class* GetPos() const { return (base_class*)mPosData; } \
52	inline_ const base_class* GetNeg() const { return (base_class*)mNegData; } \
53	inline_ size_t GetPosPrimitive() const { return (mPosData>>1); } \
54	inline_ size_t GetNegPrimitive() const { return (mNegData>>1); } \
55	/* Stats */ \
56	inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
57	\
58	volume mAABB; \
59	size_t mPosData; \
60	size_t mNegData;
61
62	class OPCODE_API AABBCollisionNode
63	{
64	IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)
65
66	inline_ float GetVolume() const { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z; }
67	inline_ float GetSize() const { return mAABB.mExtents.SquareMagnitude(); }
68	inline_ udword GetRadius() const
69	{
70	udword* Bits = (udword*)&mAABB.mExtents.x;
71	udword Max = Bits[0];
72	if(Bits[1]>Max) Max = Bits[1];
73	if(Bits[2]>Max) Max = Bits[2];
74	return Max;
75	}
76
77	// NB: using the square-magnitude or the true volume of the box, seems to yield better results
78	// (assuming UNC-like informed traversal methods). I borrowed this idea from PQP. The usual "size"
79	// otherwise, is the largest box extent. In SOLID that extent is computed on-the-fly each time it's
80	// needed (the best approach IMHO). In RAPID the rotation matrix is permuted so that Extent[0] is
81	// always the greatest, which saves looking for it at runtime. On the other hand, it yields matrices
82	// whose determinant is not 1, i.e. you can't encode them anymore as unit quaternions. Not a very
83	// good strategy.
84	};
85
86	class OPCODE_API AABBQuantizedNode
87	{
88	IMPLEMENT_IMPLICIT_NODE(AABBQuantizedNode, QuantizedAABB)
89
90	inline_ uword GetSize() const
91	{
92	const uword* Bits = mAABB.mExtents;
93	uword Max = Bits[0];
94	if(Bits[1]>Max) Max = Bits[1];
95	if(Bits[2]>Max) Max = Bits[2];
96	return Max;
97	}
98	// NB: for quantized nodes I don't feel like computing a square-magnitude with integers all
99	// over the place.......!
100	};
101
102	class OPCODE_API AABBNoLeafNode
103	{
104	IMPLEMENT_NOLEAF_NODE(AABBNoLeafNode, CollisionAABB)
105	};
106
107	class OPCODE_API AABBQuantizedNoLeafNode
108	{
109	IMPLEMENT_NOLEAF_NODE(AABBQuantizedNoLeafNode, QuantizedAABB)
110	};
111
112	//! Common interface for a collision tree
113	#define IMPLEMENT_COLLISION_TREE(base_class, node) \
114	public: \
115	/* Constructor / Destructor */ \
116	base_class(); \
117	virtual ~base_class(); \
118	/* Builds from a standard tree */ \
119	override(AABBOptimizedTree) bool Build(AABBTree* tree); \
120	/* Refits the tree */ \
121	override(AABBOptimizedTree) bool Refit(const MeshInterface* mesh_interface); \
122	/* Walks the tree */ \
123	override(AABBOptimizedTree) bool Walk(GenericWalkingCallback callback, void* user_data) const; \
124	/* Data access */ \
125	inline_ const node* GetNodes() const { return mNodes; } \
126	/* Stats */ \
127	override(AABBOptimizedTree) udword GetUsedBytes() const { return mNbNodes*sizeof(node); } \
128	private: \
129	node* mNodes;
130
131	typedef bool (GenericWalkingCallback) (const void current, void* user_data);
132
133	class OPCODE_API AABBOptimizedTree
134	{
135	public:
136	// Constructor / Destructor
137	AABBOptimizedTree() :
138	mNbNodes (0)
139	{}
140	virtual ~AABBOptimizedTree() {}
141
142	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
143	/**
144	* Builds the collision tree from a generic AABB tree.
145	* \param tree [in] generic AABB tree
146	* \return true if success
147	*/
148	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
149	virtual bool Build(AABBTree* tree) = 0;
150
151	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
152	/**
153	* Refits the collision tree after vertices have been modified.
154	* \param mesh_interface [in] mesh interface for current model
155	* \return true if success
156	*/
157	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
158	virtual bool Refit(const MeshInterface* mesh_interface) = 0;
159
160	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
161	/**
162	* Walks the tree and call the user back for each node.
163	* \param callback [in] walking callback
164	* \param user_data [in] callback's user data
165	* \return true if success
166	*/
167	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
168	virtual bool Walk(GenericWalkingCallback callback, void* user_data) const = 0;
169
170	// Data access
171	virtual udword GetUsedBytes() const = 0;
172	inline_ udword GetNbNodes() const { return mNbNodes; }
173
174	protected:
175	udword mNbNodes;
176	};
177
178	class OPCODE_API AABBCollisionTree : public AABBOptimizedTree
179	{
180	IMPLEMENT_COLLISION_TREE(AABBCollisionTree, AABBCollisionNode)
181	};
182
183	class OPCODE_API AABBNoLeafTree : public AABBOptimizedTree
184	{
185	IMPLEMENT_COLLISION_TREE(AABBNoLeafTree, AABBNoLeafNode)
186	};
187
188	class OPCODE_API AABBQuantizedTree : public AABBOptimizedTree
189	{
190	IMPLEMENT_COLLISION_TREE(AABBQuantizedTree, AABBQuantizedNode)
191
192	public:
193	Point mCenterCoeff;
194	Point mExtentsCoeff;
195	};
196
197	class OPCODE_API AABBQuantizedNoLeafTree : public AABBOptimizedTree
198	{
199	IMPLEMENT_COLLISION_TREE(AABBQuantizedNoLeafTree, AABBQuantizedNoLeafNode)
200
201	public:
202	Point mCenterCoeff;
203	Point mExtentsCoeff;
204	};
205
206	#endif // __OPC_OPTIMIZEDTREE_H__

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

Download in other formats: