- Main Page
- Classes
- Files

- File List
- File Members

# Box2D/Box2D/Collision/b2BroadPhase.h

Go to the documentation of this file.

    00001 /*
    00002 * Copyright (c) 2006-2009 Erin Catto http://www.gphysics.com
    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         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         // Reset pair buffer
    00165         m_pairCount = 0;
    00166
    00167         // Perform tree queries for all moving proxies.
    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                 // We have to query the tree with the fat AABB so that
    00177                 // we don't fail to create a pair that may touch later.
    00178                 const b2AABB& fatAABB = m_tree.GetFatAABB(m_queryProxyId);
    00179
    00180                 // Query tree, create pairs and add them pair buffer.
    00181                 m_tree.Query(this, fatAABB);
    00182         }
    00183
    00184         // Reset move buffer
    00185         m_moveCount = 0;
    00186
    00187         // Sort the pair buffer to expose duplicates.
    00188         std::sort(m_pairBuffer, m_pairBuffer + m_pairCount, b2PairLessThan);
    00189
    00190         // Send the pairs back to the client.
    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                 // Skip any duplicate pairs.
    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         // Try to keep the tree balanced.
    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