![]() |
Box2D
2.2.1
A 2D Physics Engine for Games
|
00001 /* 00002 * Copyright (c) 2009 Erin Catto http://www.box2d.org 00003 * 00004 * This software is provided 'as-is', without any express or implied 00005 * warranty. In no event will the authors be held liable for any damages 00006 * arising from the use of this software. 00007 * Permission is granted to anyone to use this software for any purpose, 00008 * including commercial applications, and to alter it and redistribute it 00009 * freely, subject to the following restrictions: 00010 * 1. The origin of this software must not be misrepresented; you must not 00011 * claim that you wrote the original software. If you use this software 00012 * in a product, an acknowledgment in the product documentation would be 00013 * appreciated but is not required. 00014 * 2. Altered source versions must be plainly marked as such, and must not be 00015 * misrepresented as being the original software. 00016 * 3. This notice may not be removed or altered from any source distribution. 00017 */ 00018 00019 #ifndef B2_DYNAMIC_TREE_H 00020 #define B2_DYNAMIC_TREE_H 00021 00022 #include <Box2D/Collision/b2Collision.h> 00023 #include <Box2D/Common/b2GrowableStack.h> 00024 00025 #define b2_nullNode (-1) 00026 00028 struct b2TreeNode 00029 { 00030 bool IsLeaf() const 00031 { 00032 return child1 == b2_nullNode; 00033 } 00034 00036 b2AABB aabb; 00037 00038 void* userData; 00039 00040 union 00041 { 00042 int32 parent; 00043 int32 next; 00044 }; 00045 00046 int32 child1; 00047 int32 child2; 00048 00049 // leaf = 0, free node = -1 00050 int32 height; 00051 }; 00052 00061 class b2DynamicTree 00062 { 00063 public: 00065 b2DynamicTree(); 00066 00068 ~b2DynamicTree(); 00069 00071 int32 CreateProxy(const b2AABB& aabb, void* userData); 00072 00074 void DestroyProxy(int32 proxyId); 00075 00080 bool MoveProxy(int32 proxyId, const b2AABB& aabb1, const b2Vec2& displacement); 00081 00084 void* GetUserData(int32 proxyId) const; 00085 00087 const b2AABB& GetFatAABB(int32 proxyId) const; 00088 00091 template <typename T> 00092 void Query(T* callback, const b2AABB& aabb) const; 00093 00101 template <typename T> 00102 void RayCast(T* callback, const b2RayCastInput& input) const; 00103 00105 void Validate() const; 00106 00109 int32 GetHeight() const; 00110 00113 int32 GetMaxBalance() const; 00114 00116 float32 GetAreaRatio() const; 00117 00119 void RebuildBottomUp(); 00120 00121 private: 00122 00123 int32 AllocateNode(); 00124 void FreeNode(int32 node); 00125 00126 void InsertLeaf(int32 node); 00127 void RemoveLeaf(int32 node); 00128 00129 int32 Balance(int32 index); 00130 00131 int32 ComputeHeight() const; 00132 int32 ComputeHeight(int32 nodeId) const; 00133 00134 void ValidateStructure(int32 index) const; 00135 void ValidateMetrics(int32 index) const; 00136 00137 int32 m_root; 00138 00139 b2TreeNode* m_nodes; 00140 int32 m_nodeCount; 00141 int32 m_nodeCapacity; 00142 00143 int32 m_freeList; 00144 00146 uint32 m_path; 00147 00148 int32 m_insertionCount; 00149 }; 00150 00151 inline void* b2DynamicTree::GetUserData(int32 proxyId) const 00152 { 00153 b2Assert(0 <= proxyId && proxyId < m_nodeCapacity); 00154 return m_nodes[proxyId].userData; 00155 } 00156 00157 inline const b2AABB& b2DynamicTree::GetFatAABB(int32 proxyId) const 00158 { 00159 b2Assert(0 <= proxyId && proxyId < m_nodeCapacity); 00160 return m_nodes[proxyId].aabb; 00161 } 00162 00163 template <typename T> 00164 inline void b2DynamicTree::Query(T* callback, const b2AABB& aabb) const 00165 { 00166 b2GrowableStack<int32, 256> stack; 00167 stack.Push(m_root); 00168 00169 while (stack.GetCount() > 0) 00170 { 00171 int32 nodeId = stack.Pop(); 00172 if (nodeId == b2_nullNode) 00173 { 00174 continue; 00175 } 00176 00177 const b2TreeNode* node = m_nodes + nodeId; 00178 00179 if (b2TestOverlap(node->aabb, aabb)) 00180 { 00181 if (node->IsLeaf()) 00182 { 00183 bool proceed = callback->QueryCallback(nodeId); 00184 if (proceed == false) 00185 { 00186 return; 00187 } 00188 } 00189 else 00190 { 00191 stack.Push(node->child1); 00192 stack.Push(node->child2); 00193 } 00194 } 00195 } 00196 } 00197 00198 template <typename T> 00199 inline void b2DynamicTree::RayCast(T* callback, const b2RayCastInput& input) const 00200 { 00201 b2Vec2 p1 = input.p1; 00202 b2Vec2 p2 = input.p2; 00203 b2Vec2 r = p2 - p1; 00204 b2Assert(r.LengthSquared() > 0.0f); 00205 r.Normalize(); 00206 00207 // v is perpendicular to the segment. 00208 b2Vec2 v = b2Cross(1.0f, r); 00209 b2Vec2 abs_v = b2Abs(v); 00210 00211 // Separating axis for segment (Gino, p80). 00212 // |dot(v, p1 - c)| > dot(|v|, h) 00213 00214 float32 maxFraction = input.maxFraction; 00215 00216 // Build a bounding box for the segment. 00217 b2AABB segmentAABB; 00218 { 00219 b2Vec2 t = p1 + maxFraction * (p2 - p1); 00220 segmentAABB.lowerBound = b2Min(p1, t); 00221 segmentAABB.upperBound = b2Max(p1, t); 00222 } 00223 00224 b2GrowableStack<int32, 256> stack; 00225 stack.Push(m_root); 00226 00227 while (stack.GetCount() > 0) 00228 { 00229 int32 nodeId = stack.Pop(); 00230 if (nodeId == b2_nullNode) 00231 { 00232 continue; 00233 } 00234 00235 const b2TreeNode* node = m_nodes + nodeId; 00236 00237 if (b2TestOverlap(node->aabb, segmentAABB) == false) 00238 { 00239 continue; 00240 } 00241 00242 // Separating axis for segment (Gino, p80). 00243 // |dot(v, p1 - c)| > dot(|v|, h) 00244 b2Vec2 c = node->aabb.GetCenter(); 00245 b2Vec2 h = node->aabb.GetExtents(); 00246 float32 separation = b2Abs(b2Dot(v, p1 - c)) - b2Dot(abs_v, h); 00247 if (separation > 0.0f) 00248 { 00249 continue; 00250 } 00251 00252 if (node->IsLeaf()) 00253 { 00254 b2RayCastInput subInput; 00255 subInput.p1 = input.p1; 00256 subInput.p2 = input.p2; 00257 subInput.maxFraction = maxFraction; 00258 00259 float32 value = callback->RayCastCallback(subInput, nodeId); 00260 00261 if (value == 0.0f) 00262 { 00263 // The client has terminated the ray cast. 00264 return; 00265 } 00266 00267 if (value > 0.0f) 00268 { 00269 // Update segment bounding box. 00270 maxFraction = value; 00271 b2Vec2 t = p1 + maxFraction * (p2 - p1); 00272 segmentAABB.lowerBound = b2Min(p1, t); 00273 segmentAABB.upperBound = b2Max(p1, t); 00274 } 00275 } 00276 else 00277 { 00278 stack.Push(node->child1); 00279 stack.Push(node->child2); 00280 } 00281 } 00282 } 00283 00284 #endif