| Box2D 2.2.1 A 2D Physics Engine for Games

- Main Page
- Classes
- Files

- File List
- File Members

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