b2DynamicTree.h
Go to the documentation of this file.
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 
00124         void ShiftOrigin(const b2Vec2& newOrigin);
00125 
00126 private:
00127 
00128         int32 AllocateNode();
00129         void FreeNode(int32 node);
00130 
00131         void InsertLeaf(int32 node);
00132         void RemoveLeaf(int32 node);
00133 
00134         int32 Balance(int32 index);
00135 
00136         int32 ComputeHeight() const;
00137         int32 ComputeHeight(int32 nodeId) const;
00138 
00139         void ValidateStructure(int32 index) const;
00140         void ValidateMetrics(int32 index) const;
00141 
00142         int32 m_root;
00143 
00144         b2TreeNode* m_nodes;
00145         int32 m_nodeCount;
00146         int32 m_nodeCapacity;
00147 
00148         int32 m_freeList;
00149 
00151         uint32 m_path;
00152 
00153         int32 m_insertionCount;
00154 };
00155 
00156 inline void* b2DynamicTree::GetUserData(int32 proxyId) const
00157 {
00158         b2Assert(0 <= proxyId && proxyId < m_nodeCapacity);
00159         return m_nodes[proxyId].userData;
00160 }
00161 
00162 inline const b2AABB& b2DynamicTree::GetFatAABB(int32 proxyId) const
00163 {
00164         b2Assert(0 <= proxyId && proxyId < m_nodeCapacity);
00165         return m_nodes[proxyId].aabb;
00166 }
00167 
00168 template <typename T>
00169 inline void b2DynamicTree::Query(T* callback, const b2AABB& aabb) const
00170 {
00171         b2GrowableStack<int32, 256> stack;
00172         stack.Push(m_root);
00173 
00174         while (stack.GetCount() > 0)
00175         {
00176                 int32 nodeId = stack.Pop();
00177                 if (nodeId == b2_nullNode)
00178                 {
00179                         continue;
00180                 }
00181 
00182                 const b2TreeNode* node = m_nodes + nodeId;
00183 
00184                 if (b2TestOverlap(node->aabb, aabb))
00185                 {
00186                         if (node->IsLeaf())
00187                         {
00188                                 bool proceed = callback->QueryCallback(nodeId);
00189                                 if (proceed == false)
00190                                 {
00191                                         return;
00192                                 }
00193                         }
00194                         else
00195                         {
00196                                 stack.Push(node->child1);
00197                                 stack.Push(node->child2);
00198                         }
00199                 }
00200         }
00201 }
00202 
00203 template <typename T>
00204 inline void b2DynamicTree::RayCast(T* callback, const b2RayCastInput& input) const
00205 {
00206         b2Vec2 p1 = input.p1;
00207         b2Vec2 p2 = input.p2;
00208         b2Vec2 r = p2 - p1;
00209         b2Assert(r.LengthSquared() > 0.0f);
00210         r.Normalize();
00211 
00212         // v is perpendicular to the segment.
00213         b2Vec2 v = b2Cross(1.0f, r);
00214         b2Vec2 abs_v = b2Abs(v);
00215 
00216         // Separating axis for segment (Gino, p80).
00217         // |dot(v, p1 - c)| > dot(|v|, h)
00218 
00219         float32 maxFraction = input.maxFraction;
00220 
00221         // Build a bounding box for the segment.
00222         b2AABB segmentAABB;
00223         {
00224                 b2Vec2 t = p1 + maxFraction * (p2 - p1);
00225                 segmentAABB.lowerBound = b2Min(p1, t);
00226                 segmentAABB.upperBound = b2Max(p1, t);
00227         }
00228 
00229         b2GrowableStack<int32, 256> stack;
00230         stack.Push(m_root);
00231 
00232         while (stack.GetCount() > 0)
00233         {
00234                 int32 nodeId = stack.Pop();
00235                 if (nodeId == b2_nullNode)
00236                 {
00237                         continue;
00238                 }
00239 
00240                 const b2TreeNode* node = m_nodes + nodeId;
00241 
00242                 if (b2TestOverlap(node->aabb, segmentAABB) == false)
00243                 {
00244                         continue;
00245                 }
00246 
00247                 // Separating axis for segment (Gino, p80).
00248                 // |dot(v, p1 - c)| > dot(|v|, h)
00249                 b2Vec2 c = node->aabb.GetCenter();
00250                 b2Vec2 h = node->aabb.GetExtents();
00251                 float32 separation = b2Abs(b2Dot(v, p1 - c)) - b2Dot(abs_v, h);
00252                 if (separation > 0.0f)
00253                 {
00254                         continue;
00255                 }
00256 
00257                 if (node->IsLeaf())
00258                 {
00259                         b2RayCastInput subInput;
00260                         subInput.p1 = input.p1;
00261                         subInput.p2 = input.p2;
00262                         subInput.maxFraction = maxFraction;
00263 
00264                         float32 value = callback->RayCastCallback(subInput, nodeId);
00265 
00266                         if (value == 0.0f)
00267                         {
00268                                 // The client has terminated the ray cast.
00269                                 return;
00270                         }
00271 
00272                         if (value > 0.0f)
00273                         {
00274                                 // Update segment bounding box.
00275                                 maxFraction = value;
00276                                 b2Vec2 t = p1 + maxFraction * (p2 - p1);
00277                                 segmentAABB.lowerBound = b2Min(p1, t);
00278                                 segmentAABB.upperBound = b2Max(p1, t);
00279                         }
00280                 }
00281                 else
00282                 {
00283                         stack.Push(node->child1);
00284                         stack.Push(node->child2);
00285                 }
00286         }
00287 }
00288 
00289 #endif


mvsim
Author(s):
autogenerated on Thu Sep 7 2017 09:27:47