Warning, file /education/gcompris/external/qml-box2d/Box2D/Collision/b2BroadPhase.h was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).
0001 /* 0002 * Copyright (c) 2006-2009 Erin Catto http://www.box2d.org 0003 * 0004 * This software is provided 'as-is', without any express or implied 0005 * warranty. In no event will the authors be held liable for any damages 0006 * arising from the use of this software. 0007 * Permission is granted to anyone to use this software for any purpose, 0008 * including commercial applications, and to alter it and redistribute it 0009 * freely, subject to the following restrictions: 0010 * 1. The origin of this software must not be misrepresented; you must not 0011 * claim that you wrote the original software. If you use this software 0012 * in a product, an acknowledgment in the product documentation would be 0013 * appreciated but is not required. 0014 * 2. Altered source versions must be plainly marked as such, and must not be 0015 * misrepresented as being the original software. 0016 * 3. This notice may not be removed or altered from any source distribution. 0017 */ 0018 0019 #ifndef B2_BROAD_PHASE_H 0020 #define B2_BROAD_PHASE_H 0021 0022 #include <Box2D/Common/b2Settings.h> 0023 #include <Box2D/Collision/b2Collision.h> 0024 #include <Box2D/Collision/b2DynamicTree.h> 0025 #include <algorithm> 0026 0027 struct b2Pair 0028 { 0029 int32 proxyIdA; 0030 int32 proxyIdB; 0031 }; 0032 0033 /// The broad-phase is used for computing pairs and performing volume queries and ray casts. 0034 /// This broad-phase does not persist pairs. Instead, this reports potentially new pairs. 0035 /// It is up to the client to consume the new pairs and to track subsequent overlap. 0036 class b2BroadPhase 0037 { 0038 public: 0039 0040 enum 0041 { 0042 e_nullProxy = -1 0043 }; 0044 0045 b2BroadPhase(); 0046 ~b2BroadPhase(); 0047 0048 /// Create a proxy with an initial AABB. Pairs are not reported until 0049 /// UpdatePairs is called. 0050 int32 CreateProxy(const b2AABB& aabb, void* userData); 0051 0052 /// Destroy a proxy. It is up to the client to remove any pairs. 0053 void DestroyProxy(int32 proxyId); 0054 0055 /// Call MoveProxy as many times as you like, then when you are done 0056 /// call UpdatePairs to finalized the proxy pairs (for your time step). 0057 void MoveProxy(int32 proxyId, const b2AABB& aabb, const b2Vec2& displacement); 0058 0059 /// Call to trigger a re-processing of it's pairs on the next call to UpdatePairs. 0060 void TouchProxy(int32 proxyId); 0061 0062 /// Get the fat AABB for a proxy. 0063 const b2AABB& GetFatAABB(int32 proxyId) const; 0064 0065 /// Get user data from a proxy. Returns NULL if the id is invalid. 0066 void* GetUserData(int32 proxyId) const; 0067 0068 /// Test overlap of fat AABBs. 0069 bool TestOverlap(int32 proxyIdA, int32 proxyIdB) const; 0070 0071 /// Get the number of proxies. 0072 int32 GetProxyCount() const; 0073 0074 /// Update the pairs. This results in pair callbacks. This can only add pairs. 0075 template <typename T> 0076 void UpdatePairs(T* callback); 0077 0078 /// Query an AABB for overlapping proxies. The callback class 0079 /// is called for each proxy that overlaps the supplied AABB. 0080 template <typename T> 0081 void Query(T* callback, const b2AABB& aabb) const; 0082 0083 /// Ray-cast against the proxies in the tree. This relies on the callback 0084 /// to perform a exact ray-cast in the case were the proxy contains a shape. 0085 /// The callback also performs the any collision filtering. This has performance 0086 /// roughly equal to k * log(n), where k is the number of collisions and n is the 0087 /// number of proxies in the tree. 0088 /// @param input the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1). 0089 /// @param callback a callback class that is called for each proxy that is hit by the ray. 0090 template <typename T> 0091 void RayCast(T* callback, const b2RayCastInput& input) const; 0092 0093 /// Get the height of the embedded tree. 0094 int32 GetTreeHeight() const; 0095 0096 /// Get the balance of the embedded tree. 0097 int32 GetTreeBalance() const; 0098 0099 /// Get the quality metric of the embedded tree. 0100 float32 GetTreeQuality() const; 0101 0102 /// Shift the world origin. Useful for large worlds. 0103 /// The shift formula is: position -= newOrigin 0104 /// @param newOrigin the new origin with respect to the old origin 0105 void ShiftOrigin(const b2Vec2& newOrigin); 0106 0107 private: 0108 0109 friend class b2DynamicTree; 0110 0111 void BufferMove(int32 proxyId); 0112 void UnBufferMove(int32 proxyId); 0113 0114 bool QueryCallback(int32 proxyId); 0115 0116 b2DynamicTree m_tree; 0117 0118 int32 m_proxyCount; 0119 0120 int32* m_moveBuffer; 0121 int32 m_moveCapacity; 0122 int32 m_moveCount; 0123 0124 b2Pair* m_pairBuffer; 0125 int32 m_pairCapacity; 0126 int32 m_pairCount; 0127 0128 int32 m_queryProxyId; 0129 }; 0130 0131 /// This is used to sort pairs. 0132 inline bool b2PairLessThan(const b2Pair& pair1, const b2Pair& pair2) 0133 { 0134 if (pair1.proxyIdA < pair2.proxyIdA) 0135 { 0136 return true; 0137 } 0138 0139 if (pair1.proxyIdA == pair2.proxyIdA) 0140 { 0141 return pair1.proxyIdB < pair2.proxyIdB; 0142 } 0143 0144 return false; 0145 } 0146 0147 inline void* b2BroadPhase::GetUserData(int32 proxyId) const 0148 { 0149 return m_tree.GetUserData(proxyId); 0150 } 0151 0152 inline bool b2BroadPhase::TestOverlap(int32 proxyIdA, int32 proxyIdB) const 0153 { 0154 const b2AABB& aabbA = m_tree.GetFatAABB(proxyIdA); 0155 const b2AABB& aabbB = m_tree.GetFatAABB(proxyIdB); 0156 return b2TestOverlap(aabbA, aabbB); 0157 } 0158 0159 inline const b2AABB& b2BroadPhase::GetFatAABB(int32 proxyId) const 0160 { 0161 return m_tree.GetFatAABB(proxyId); 0162 } 0163 0164 inline int32 b2BroadPhase::GetProxyCount() const 0165 { 0166 return m_proxyCount; 0167 } 0168 0169 inline int32 b2BroadPhase::GetTreeHeight() const 0170 { 0171 return m_tree.GetHeight(); 0172 } 0173 0174 inline int32 b2BroadPhase::GetTreeBalance() const 0175 { 0176 return m_tree.GetMaxBalance(); 0177 } 0178 0179 inline float32 b2BroadPhase::GetTreeQuality() const 0180 { 0181 return m_tree.GetAreaRatio(); 0182 } 0183 0184 template <typename T> 0185 void b2BroadPhase::UpdatePairs(T* callback) 0186 { 0187 // Reset pair buffer 0188 m_pairCount = 0; 0189 0190 // Perform tree queries for all moving proxies. 0191 for (int32 i = 0; i < m_moveCount; ++i) 0192 { 0193 m_queryProxyId = m_moveBuffer[i]; 0194 if (m_queryProxyId == e_nullProxy) 0195 { 0196 continue; 0197 } 0198 0199 // We have to query the tree with the fat AABB so that 0200 // we don't fail to create a pair that may touch later. 0201 const b2AABB& fatAABB = m_tree.GetFatAABB(m_queryProxyId); 0202 0203 // Query tree, create pairs and add them pair buffer. 0204 m_tree.Query(this, fatAABB); 0205 } 0206 0207 // Reset move buffer 0208 m_moveCount = 0; 0209 0210 // Sort the pair buffer to expose duplicates. 0211 std::sort(m_pairBuffer, m_pairBuffer + m_pairCount, b2PairLessThan); 0212 0213 // Send the pairs back to the client. 0214 int32 i = 0; 0215 while (i < m_pairCount) 0216 { 0217 b2Pair* primaryPair = m_pairBuffer + i; 0218 void* userDataA = m_tree.GetUserData(primaryPair->proxyIdA); 0219 void* userDataB = m_tree.GetUserData(primaryPair->proxyIdB); 0220 0221 callback->AddPair(userDataA, userDataB); 0222 ++i; 0223 0224 // Skip any duplicate pairs. 0225 while (i < m_pairCount) 0226 { 0227 b2Pair* pair = m_pairBuffer + i; 0228 if (pair->proxyIdA != primaryPair->proxyIdA || pair->proxyIdB != primaryPair->proxyIdB) 0229 { 0230 break; 0231 } 0232 ++i; 0233 } 0234 } 0235 0236 // Try to keep the tree balanced. 0237 //m_tree.Rebalance(4); 0238 } 0239 0240 template <typename T> 0241 inline void b2BroadPhase::Query(T* callback, const b2AABB& aabb) const 0242 { 0243 m_tree.Query(callback, aabb); 0244 } 0245 0246 template <typename T> 0247 inline void b2BroadPhase::RayCast(T* callback, const b2RayCastInput& input) const 0248 { 0249 m_tree.RayCast(callback, input); 0250 } 0251 0252 inline void b2BroadPhase::ShiftOrigin(const b2Vec2& newOrigin) 0253 { 0254 m_tree.ShiftOrigin(newOrigin); 0255 } 0256 0257 #endif