![]() |
Box2D
2.2.1
A 2D Physics Engine for Games
|
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