b2BroadPhase.h
上传用户:gb3593
上传日期:2022-01-07
资源大小:3028k
文件大小:6k
源码类别:

游戏引擎

开发平台:

Visual C++

  1. /*
  2. * Copyright (c) 2006-2009 Erin Catto http://www.gphysics.com
  3. *
  4. * This software is provided 'as-is', without any express or implied
  5. * warranty.  In no event will the authors be held liable for any damages
  6. * arising from the use of this software.
  7. * Permission is granted to anyone to use this software for any purpose,
  8. * including commercial applications, and to alter it and redistribute it
  9. * freely, subject to the following restrictions:
  10. * 1. The origin of this software must not be misrepresented; you must not
  11. * claim that you wrote the original software. If you use this software
  12. * in a product, an acknowledgment in the product documentation would be
  13. * appreciated but is not required.
  14. * 2. Altered source versions must be plainly marked as such, and must not be
  15. * misrepresented as being the original software.
  16. * 3. This notice may not be removed or altered from any source distribution.
  17. */
  18. #ifndef B2_BROAD_PHASE_H
  19. #define B2_BROAD_PHASE_H
  20. #include <Box2D/Common/b2Settings.h>
  21. #include <Box2D/Collision/b2Collision.h>
  22. #include <Box2D/Collision/b2DynamicTree.h>
  23. #include <algorithm>
  24. struct b2Pair
  25. {
  26. int32 proxyIdA;
  27. int32 proxyIdB;
  28. int32 next;
  29. };
  30. /// The broad-phase is used for computing pairs and performing volume queries and ray casts.
  31. /// This broad-phase does not persist pairs. Instead, this reports potentially new pairs.
  32. /// It is up to the client to consume the new pairs and to track subsequent overlap.
  33. class b2BroadPhase
  34. {
  35. public:
  36. enum
  37. {
  38. e_nullProxy = -1,
  39. };
  40. b2BroadPhase();
  41. ~b2BroadPhase();
  42. /// Create a proxy with an initial AABB. Pairs are not reported until
  43. /// UpdatePairs is called.
  44. int32 CreateProxy(const b2AABB& aabb, void* userData);
  45. /// Destroy a proxy. It is up to the client to remove any pairs.
  46. void DestroyProxy(int32 proxyId);
  47. /// Call MoveProxy as many times as you like, then when you are done
  48. /// call UpdatePairs to finalized the proxy pairs (for your time step).
  49. void MoveProxy(int32 proxyId, const b2AABB& aabb, const b2Vec2& displacement);
  50. /// Get the fat AABB for a proxy.
  51. const b2AABB& GetFatAABB(int32 proxyId) const;
  52. /// Get user data from a proxy. Returns NULL if the id is invalid.
  53. void* GetUserData(int32 proxyId) const;
  54. /// Test overlap of fat AABBs.
  55. bool TestOverlap(int32 proxyIdA, int32 proxyIdB) const;
  56. /// Get the number of proxies.
  57. int32 GetProxyCount() const;
  58. /// Update the pairs. This results in pair callbacks. This can only add pairs.
  59. template <typename T>
  60. void UpdatePairs(T* callback);
  61. /// Query an AABB for overlapping proxies. The callback class
  62. /// is called for each proxy that overlaps the supplied AABB.
  63. template <typename T>
  64. void Query(T* callback, const b2AABB& aabb) const;
  65. /// Ray-cast against the proxies in the tree. This relies on the callback
  66. /// to perform a exact ray-cast in the case were the proxy contains a shape.
  67. /// The callback also performs the any collision filtering. This has performance
  68. /// roughly equal to k * log(n), where k is the number of collisions and n is the
  69. /// number of proxies in the tree.
  70. /// @param input the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
  71. /// @param callback a callback class that is called for each proxy that is hit by the ray.
  72. template <typename T>
  73. void RayCast(T* callback, const b2RayCastInput& input) const;
  74. /// Compute the height of the embedded tree.
  75. int32 ComputeHeight() const;
  76. private:
  77. friend class b2DynamicTree;
  78. void BufferMove(int32 proxyId);
  79. void UnBufferMove(int32 proxyId);
  80. bool QueryCallback(int32 proxyId);
  81. b2DynamicTree m_tree;
  82. int32 m_proxyCount;
  83. int32* m_moveBuffer;
  84. int32 m_moveCapacity;
  85. int32 m_moveCount;
  86. b2Pair* m_pairBuffer;
  87. int32 m_pairCapacity;
  88. int32 m_pairCount;
  89. int32 m_queryProxyId;
  90. };
  91. /// This is used to sort pairs.
  92. inline bool b2PairLessThan(const b2Pair& pair1, const b2Pair& pair2)
  93. {
  94. if (pair1.proxyIdA < pair2.proxyIdA)
  95. {
  96. return true;
  97. }
  98. if (pair1.proxyIdA == pair2.proxyIdA)
  99. {
  100. return pair1.proxyIdB < pair2.proxyIdB;
  101. }
  102. return false;
  103. }
  104. inline void* b2BroadPhase::GetUserData(int32 proxyId) const
  105. {
  106. return m_tree.GetUserData(proxyId);
  107. }
  108. inline bool b2BroadPhase::TestOverlap(int32 proxyIdA, int32 proxyIdB) const
  109. {
  110. const b2AABB& aabbA = m_tree.GetFatAABB(proxyIdA);
  111. const b2AABB& aabbB = m_tree.GetFatAABB(proxyIdB);
  112. return b2TestOverlap(aabbA, aabbB);
  113. }
  114. inline const b2AABB& b2BroadPhase::GetFatAABB(int32 proxyId) const
  115. {
  116. return m_tree.GetFatAABB(proxyId);
  117. }
  118. inline int32 b2BroadPhase::GetProxyCount() const
  119. {
  120. return m_proxyCount;
  121. }
  122. inline int32 b2BroadPhase::ComputeHeight() const
  123. {
  124. return m_tree.ComputeHeight();
  125. }
  126. template <typename T>
  127. void b2BroadPhase::UpdatePairs(T* callback)
  128. {
  129. // Reset pair buffer
  130. m_pairCount = 0;
  131. // Perform tree queries for all moving proxies.
  132. for (int32 i = 0; i < m_moveCount; ++i)
  133. {
  134. m_queryProxyId = m_moveBuffer[i];
  135. if (m_queryProxyId == e_nullProxy)
  136. {
  137. continue;
  138. }
  139. // We have to query the tree with the fat AABB so that
  140. // we don't fail to create a pair that may touch later.
  141. const b2AABB& fatAABB = m_tree.GetFatAABB(m_queryProxyId);
  142. // Query tree, create pairs and add them pair buffer.
  143. m_tree.Query(this, fatAABB);
  144. }
  145. // Reset move buffer
  146. m_moveCount = 0;
  147. // Sort the pair buffer to expose duplicates.
  148. std::sort(m_pairBuffer, m_pairBuffer + m_pairCount, b2PairLessThan);
  149. // Send the pairs back to the client.
  150. int32 i = 0;
  151. while (i < m_pairCount)
  152. {
  153. b2Pair* primaryPair = m_pairBuffer + i;
  154. void* userDataA = m_tree.GetUserData(primaryPair->proxyIdA);
  155. void* userDataB = m_tree.GetUserData(primaryPair->proxyIdB);
  156. callback->AddPair(userDataA, userDataB);
  157. ++i;
  158. // Skip any duplicate pairs.
  159. while (i < m_pairCount)
  160. {
  161. b2Pair* pair = m_pairBuffer + i;
  162. if (pair->proxyIdA != primaryPair->proxyIdA || pair->proxyIdB != primaryPair->proxyIdB)
  163. {
  164. break;
  165. }
  166. ++i;
  167. }
  168. }
  169. // Try to keep the tree balanced.
  170. m_tree.Rebalance(4);
  171. }
  172. template <typename T>
  173. inline void b2BroadPhase::Query(T* callback, const b2AABB& aabb) const
  174. {
  175. m_tree.Query(callback, aabb);
  176. }
  177. template <typename T>
  178. inline void b2BroadPhase::RayCast(T* callback, const b2RayCastInput& input) const
  179. {
  180. m_tree.RayCast(callback, input);
  181. }
  182. #endif