Box2D  2.2.1
A 2D Physics Engine for Games
b2BroadPhase.h
00001 /*
00002 * Copyright (c) 2006-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_BROAD_PHASE_H
00020 #define B2_BROAD_PHASE_H
00021 
00022 #include <Box2D/Common/b2Settings.h>
00023 #include <Box2D/Collision/b2Collision.h>
00024 #include <Box2D/Collision/b2DynamicTree.h>
00025 #include <algorithm>
00026 
00027 struct b2Pair
00028 {
00029         int32 proxyIdA;
00030         int32 proxyIdB;
00031         int32 next;
00032 };
00033 
00037 class b2BroadPhase
00038 {
00039 public:
00040 
00041         enum
00042         {
00043                 e_nullProxy = -1
00044         };
00045 
00046         b2BroadPhase();
00047         ~b2BroadPhase();
00048 
00051         int32 CreateProxy(const b2AABB& aabb, void* userData);
00052 
00054         void DestroyProxy(int32 proxyId);
00055 
00058         void MoveProxy(int32 proxyId, const b2AABB& aabb, const b2Vec2& displacement);
00059 
00061         void TouchProxy(int32 proxyId);
00062 
00064         const b2AABB& GetFatAABB(int32 proxyId) const;
00065 
00067         void* GetUserData(int32 proxyId) const;
00068 
00070         bool TestOverlap(int32 proxyIdA, int32 proxyIdB) const;
00071 
00073         int32 GetProxyCount() const;
00074 
00076         template <typename T>
00077         void UpdatePairs(T* callback);
00078 
00081         template <typename T>
00082         void Query(T* callback, const b2AABB& aabb) const;
00083 
00091         template <typename T>
00092         void RayCast(T* callback, const b2RayCastInput& input) const;
00093 
00095         int32 GetTreeHeight() const;
00096 
00098         int32 GetTreeBalance() const;
00099 
00101         float32 GetTreeQuality() const;
00102 
00103 private:
00104 
00105         friend class b2DynamicTree;
00106 
00107         void BufferMove(int32 proxyId);
00108         void UnBufferMove(int32 proxyId);
00109 
00110         bool QueryCallback(int32 proxyId);
00111 
00112         b2DynamicTree m_tree;
00113 
00114         int32 m_proxyCount;
00115 
00116         int32* m_moveBuffer;
00117         int32 m_moveCapacity;
00118         int32 m_moveCount;
00119 
00120         b2Pair* m_pairBuffer;
00121         int32 m_pairCapacity;
00122         int32 m_pairCount;
00123 
00124         int32 m_queryProxyId;
00125 };
00126 
00128 inline bool b2PairLessThan(const b2Pair& pair1, const b2Pair& pair2)
00129 {
00130         if (pair1.proxyIdA < pair2.proxyIdA)
00131         {
00132                 return true;
00133         }
00134 
00135         if (pair1.proxyIdA == pair2.proxyIdA)
00136         {
00137                 return pair1.proxyIdB < pair2.proxyIdB;
00138         }
00139 
00140         return false;
00141 }
00142 
00143 inline void* b2BroadPhase::GetUserData(int32 proxyId) const
00144 {
00145         return m_tree.GetUserData(proxyId);
00146 }
00147 
00148 inline bool b2BroadPhase::TestOverlap(int32 proxyIdA, int32 proxyIdB) const
00149 {
00150         const b2AABB& aabbA = m_tree.GetFatAABB(proxyIdA);
00151         const b2AABB& aabbB = m_tree.GetFatAABB(proxyIdB);
00152         return b2TestOverlap(aabbA, aabbB);
00153 }
00154 
00155 inline const b2AABB& b2BroadPhase::GetFatAABB(int32 proxyId) const
00156 {
00157         return m_tree.GetFatAABB(proxyId);
00158 }
00159 
00160 inline int32 b2BroadPhase::GetProxyCount() const
00161 {
00162         return m_proxyCount;
00163 }
00164 
00165 inline int32 b2BroadPhase::GetTreeHeight() const
00166 {
00167         return m_tree.GetHeight();
00168 }
00169 
00170 inline int32 b2BroadPhase::GetTreeBalance() const
00171 {
00172         return m_tree.GetMaxBalance();
00173 }
00174 
00175 inline float32 b2BroadPhase::GetTreeQuality() const
00176 {
00177         return m_tree.GetAreaRatio();
00178 }
00179 
00180 template <typename T>
00181 void b2BroadPhase::UpdatePairs(T* callback)
00182 {
00183         // Reset pair buffer
00184         m_pairCount = 0;
00185 
00186         // Perform tree queries for all moving proxies.
00187         for (int32 i = 0; i < m_moveCount; ++i)
00188         {
00189                 m_queryProxyId = m_moveBuffer[i];
00190                 if (m_queryProxyId == e_nullProxy)
00191                 {
00192                         continue;
00193                 }
00194 
00195                 // We have to query the tree with the fat AABB so that
00196                 // we don't fail to create a pair that may touch later.
00197                 const b2AABB& fatAABB = m_tree.GetFatAABB(m_queryProxyId);
00198 
00199                 // Query tree, create pairs and add them pair buffer.
00200                 m_tree.Query(this, fatAABB);
00201         }
00202 
00203         // Reset move buffer
00204         m_moveCount = 0;
00205 
00206         // Sort the pair buffer to expose duplicates.
00207         std::sort(m_pairBuffer, m_pairBuffer + m_pairCount, b2PairLessThan);
00208 
00209         // Send the pairs back to the client.
00210         int32 i = 0;
00211         while (i < m_pairCount)
00212         {
00213                 b2Pair* primaryPair = m_pairBuffer + i;
00214                 void* userDataA = m_tree.GetUserData(primaryPair->proxyIdA);
00215                 void* userDataB = m_tree.GetUserData(primaryPair->proxyIdB);
00216 
00217                 callback->AddPair(userDataA, userDataB);
00218                 ++i;
00219 
00220                 // Skip any duplicate pairs.
00221                 while (i < m_pairCount)
00222                 {
00223                         b2Pair* pair = m_pairBuffer + i;
00224                         if (pair->proxyIdA != primaryPair->proxyIdA || pair->proxyIdB != primaryPair->proxyIdB)
00225                         {
00226                                 break;
00227                         }
00228                         ++i;
00229                 }
00230         }
00231 
00232         // Try to keep the tree balanced.
00233         //m_tree.Rebalance(4);
00234 }
00235 
00236 template <typename T>
00237 inline void b2BroadPhase::Query(T* callback, const b2AABB& aabb) const
00238 {
00239         m_tree.Query(callback, aabb);
00240 }
00241 
00242 template <typename T>
00243 inline void b2BroadPhase::RayCast(T* callback, const b2RayCastInput& input) const
00244 {
00245         m_tree.RayCast(callback, input);
00246 }
00247 
00248 #endif
 All Classes Files Functions Variables Enumerations Enumerator Defines