Box2D  2.3.0
A 2D Physics Engine for Games
b2BroadPhase.h
1 /*
2 * Copyright (c) 2006-2009 Erin Catto http://www.box2d.org
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 
19 #ifndef B2_BROAD_PHASE_H
20 #define B2_BROAD_PHASE_H
21 
24 #include <Box2D/Collision/b2DynamicTree.h>
25 #include <algorithm>
26 
27 struct b2Pair
28 {
29  int32 proxyIdA;
30  int32 proxyIdB;
31 };
32 
37 {
38 public:
39 
40  enum
41  {
42  e_nullProxy = -1
43  };
44 
45  b2BroadPhase();
46  ~b2BroadPhase();
47 
50  int32 CreateProxy(const b2AABB& aabb, void* userData);
51 
53  void DestroyProxy(int32 proxyId);
54 
57  void MoveProxy(int32 proxyId, const b2AABB& aabb, const b2Vec2& displacement);
58 
60  void TouchProxy(int32 proxyId);
61 
63  const b2AABB& GetFatAABB(int32 proxyId) const;
64 
66  void* GetUserData(int32 proxyId) const;
67 
69  bool TestOverlap(int32 proxyIdA, int32 proxyIdB) const;
70 
72  int32 GetProxyCount() const;
73 
75  template <typename T>
76  void UpdatePairs(T* callback);
77 
80  template <typename T>
81  void Query(T* callback, const b2AABB& aabb) const;
82 
90  template <typename T>
91  void RayCast(T* callback, const b2RayCastInput& input) const;
92 
94  int32 GetTreeHeight() const;
95 
97  int32 GetTreeBalance() const;
98 
100  float32 GetTreeQuality() const;
101 
105  void ShiftOrigin(const b2Vec2& newOrigin);
106 
107 private:
108 
109  friend class b2DynamicTree;
110 
111  void BufferMove(int32 proxyId);
112  void UnBufferMove(int32 proxyId);
113 
114  bool QueryCallback(int32 proxyId);
115 
116  b2DynamicTree m_tree;
117 
118  int32 m_proxyCount;
119 
120  int32* m_moveBuffer;
121  int32 m_moveCapacity;
122  int32 m_moveCount;
123 
124  b2Pair* m_pairBuffer;
125  int32 m_pairCapacity;
126  int32 m_pairCount;
127 
128  int32 m_queryProxyId;
129 };
130 
132 inline bool b2PairLessThan(const b2Pair& pair1, const b2Pair& pair2)
133 {
134  if (pair1.proxyIdA < pair2.proxyIdA)
135  {
136  return true;
137  }
138 
139  if (pair1.proxyIdA == pair2.proxyIdA)
140  {
141  return pair1.proxyIdB < pair2.proxyIdB;
142  }
143 
144  return false;
145 }
146 
147 inline void* b2BroadPhase::GetUserData(int32 proxyId) const
148 {
149  return m_tree.GetUserData(proxyId);
150 }
151 
152 inline bool b2BroadPhase::TestOverlap(int32 proxyIdA, int32 proxyIdB) const
153 {
154  const b2AABB& aabbA = m_tree.GetFatAABB(proxyIdA);
155  const b2AABB& aabbB = m_tree.GetFatAABB(proxyIdB);
156  return b2TestOverlap(aabbA, aabbB);
157 }
158 
159 inline const b2AABB& b2BroadPhase::GetFatAABB(int32 proxyId) const
160 {
161  return m_tree.GetFatAABB(proxyId);
162 }
163 
164 inline int32 b2BroadPhase::GetProxyCount() const
165 {
166  return m_proxyCount;
167 }
168 
169 inline int32 b2BroadPhase::GetTreeHeight() const
170 {
171  return m_tree.GetHeight();
172 }
173 
174 inline int32 b2BroadPhase::GetTreeBalance() const
175 {
176  return m_tree.GetMaxBalance();
177 }
178 
179 inline float32 b2BroadPhase::GetTreeQuality() const
180 {
181  return m_tree.GetAreaRatio();
182 }
183 
184 template <typename T>
185 void b2BroadPhase::UpdatePairs(T* callback)
186 {
187  // Reset pair buffer
188  m_pairCount = 0;
189 
190  // Perform tree queries for all moving proxies.
191  for (int32 i = 0; i < m_moveCount; ++i)
192  {
193  m_queryProxyId = m_moveBuffer[i];
194  if (m_queryProxyId == e_nullProxy)
195  {
196  continue;
197  }
198 
199  // We have to query the tree with the fat AABB so that
200  // we don't fail to create a pair that may touch later.
201  const b2AABB& fatAABB = m_tree.GetFatAABB(m_queryProxyId);
202 
203  // Query tree, create pairs and add them pair buffer.
204  m_tree.Query(this, fatAABB);
205  }
206 
207  // Reset move buffer
208  m_moveCount = 0;
209 
210  // Sort the pair buffer to expose duplicates.
211  std::sort(m_pairBuffer, m_pairBuffer + m_pairCount, b2PairLessThan);
212 
213  // Send the pairs back to the client.
214  int32 i = 0;
215  while (i < m_pairCount)
216  {
217  b2Pair* primaryPair = m_pairBuffer + i;
218  void* userDataA = m_tree.GetUserData(primaryPair->proxyIdA);
219  void* userDataB = m_tree.GetUserData(primaryPair->proxyIdB);
220 
221  callback->AddPair(userDataA, userDataB);
222  ++i;
223 
224  // Skip any duplicate pairs.
225  while (i < m_pairCount)
226  {
227  b2Pair* pair = m_pairBuffer + i;
228  if (pair->proxyIdA != primaryPair->proxyIdA || pair->proxyIdB != primaryPair->proxyIdB)
229  {
230  break;
231  }
232  ++i;
233  }
234  }
235 
236  // Try to keep the tree balanced.
237  //m_tree.Rebalance(4);
238 }
239 
240 template <typename T>
241 inline void b2BroadPhase::Query(T* callback, const b2AABB& aabb) const
242 {
243  m_tree.Query(callback, aabb);
244 }
245 
246 template <typename T>
247 inline void b2BroadPhase::RayCast(T* callback, const b2RayCastInput& input) const
248 {
249  m_tree.RayCast(callback, input);
250 }
251 
252 inline void b2BroadPhase::ShiftOrigin(const b2Vec2& newOrigin)
253 {
254  m_tree.ShiftOrigin(newOrigin);
255 }
256 
257 #endif