| Box2D 2.2.1 A 2D Physics Engine for Games

- Main Page
- Classes
- Files

- File List
- File Members

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