aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/ode-0.9/OPCODE/OPC_OptimizedTree.h
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/ode-0.9/OPCODE/OPC_OptimizedTree.h')
-rw-r--r--libraries/ode-0.9/OPCODE/OPC_OptimizedTree.h206
1 files changed, 206 insertions, 0 deletions
diff --git a/libraries/ode-0.9/OPCODE/OPC_OptimizedTree.h b/libraries/ode-0.9/OPCODE/OPC_OptimizedTree.h
new file mode 100644
index 0000000..36aea07
--- /dev/null
+++ b/libraries/ode-0.9/OPCODE/OPC_OptimizedTree.h
@@ -0,0 +1,206 @@
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__
generated by cgit v1.1 at 2024-11-09 21:55:33 +0000