00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
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 const b2AABB& GetFatAABB(int32 proxyId) const;
00062
00064 void* GetUserData(int32 proxyId) const;
00065
00067 bool TestOverlap(int32 proxyIdA, int32 proxyIdB) const;
00068
00070 int32 GetProxyCount() const;
00071
00073 template <typename T>
00074 void UpdatePairs(T* callback);
00075
00078 template <typename T>
00079 void Query(T* callback, const b2AABB& aabb) const;
00080
00088 template <typename T>
00089 void RayCast(T* callback, const b2RayCastInput& input) const;
00090
00092 int32 ComputeHeight() const;
00093
00094 private:
00095
00096 friend class b2DynamicTree;
00097
00098 void BufferMove(int32 proxyId);
00099 void UnBufferMove(int32 proxyId);
00100
00101 bool QueryCallback(int32 proxyId);
00102
00103 b2DynamicTree m_tree;
00104
00105 int32 m_proxyCount;
00106
00107 int32* m_moveBuffer;
00108 int32 m_moveCapacity;
00109 int32 m_moveCount;
00110
00111 b2Pair* m_pairBuffer;
00112 int32 m_pairCapacity;
00113 int32 m_pairCount;
00114
00115 int32 m_queryProxyId;
00116 };
00117
00119 inline bool b2PairLessThan(const b2Pair& pair1, const b2Pair& pair2)
00120 {
00121 if (pair1.proxyIdA < pair2.proxyIdA)
00122 {
00123 return true;
00124 }
00125
00126 if (pair1.proxyIdA == pair2.proxyIdA)
00127 {
00128 return pair1.proxyIdB < pair2.proxyIdB;
00129 }
00130
00131 return false;
00132 }
00133
00134 inline void* b2BroadPhase::GetUserData(int32 proxyId) const
00135 {
00136 return m_tree.GetUserData(proxyId);
00137 }
00138
00139 inline bool b2BroadPhase::TestOverlap(int32 proxyIdA, int32 proxyIdB) const
00140 {
00141 const b2AABB& aabbA = m_tree.GetFatAABB(proxyIdA);
00142 const b2AABB& aabbB = m_tree.GetFatAABB(proxyIdB);
00143 return b2TestOverlap(aabbA, aabbB);
00144 }
00145
00146 inline const b2AABB& b2BroadPhase::GetFatAABB(int32 proxyId) const
00147 {
00148 return m_tree.GetFatAABB(proxyId);
00149 }
00150
00151 inline int32 b2BroadPhase::GetProxyCount() const
00152 {
00153 return m_proxyCount;
00154 }
00155
00156 inline int32 b2BroadPhase::ComputeHeight() const
00157 {
00158 return m_tree.ComputeHeight();
00159 }
00160
00161 template <typename T>
00162 void b2BroadPhase::UpdatePairs(T* callback)
00163 {
00164
00165 m_pairCount = 0;
00166
00167
00168 for (int32 i = 0; i < m_moveCount; ++i)
00169 {
00170 m_queryProxyId = m_moveBuffer[i];
00171 if (m_queryProxyId == e_nullProxy)
00172 {
00173 continue;
00174 }
00175
00176
00177
00178 const b2AABB& fatAABB = m_tree.GetFatAABB(m_queryProxyId);
00179
00180
00181 m_tree.Query(this, fatAABB);
00182 }
00183
00184
00185 m_moveCount = 0;
00186
00187
00188 std::sort(m_pairBuffer, m_pairBuffer + m_pairCount, b2PairLessThan);
00189
00190
00191 int32 i = 0;
00192 while (i < m_pairCount)
00193 {
00194 b2Pair* primaryPair = m_pairBuffer + i;
00195 void* userDataA = m_tree.GetUserData(primaryPair->proxyIdA);
00196 void* userDataB = m_tree.GetUserData(primaryPair->proxyIdB);
00197
00198 callback->AddPair(userDataA, userDataB);
00199 ++i;
00200
00201
00202 while (i < m_pairCount)
00203 {
00204 b2Pair* pair = m_pairBuffer + i;
00205 if (pair->proxyIdA != primaryPair->proxyIdA || pair->proxyIdB != primaryPair->proxyIdB)
00206 {
00207 break;
00208 }
00209 ++i;
00210 }
00211 }
00212
00213
00214 m_tree.Rebalance(4);
00215 }
00216
00217 template <typename T>
00218 inline void b2BroadPhase::Query(T* callback, const b2AABB& aabb) const
00219 {
00220 m_tree.Query(callback, aabb);
00221 }
00222
00223 template <typename T>
00224 inline void b2BroadPhase::RayCast(T* callback, const b2RayCastInput& input) const
00225 {
00226 m_tree.RayCast(callback, input);
00227 }
00228
00229 #endif