Box2D  2.2.1
A 2D Physics Engine for Games
b2DynamicTree.h
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
 All Classes Files Functions Variables Enumerations Enumerator Defines