b2BroadPhase.h
Go to the documentation of this file.
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 
25 #include <algorithm>
26 
27 struct b2Pair
28 {
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 
117 
119 
123 
127 
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 
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 
165 {
166  return m_proxyCount;
167 }
168 
170 {
171  return m_tree.GetHeight();
172 }
173 
175 {
176  return m_tree.GetMaxBalance();
177 }
178 
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
int32 GetTreeBalance() const
Get the balance of the embedded tree.
Definition: b2BroadPhase.h:174
int32 m_queryProxyId
Definition: b2BroadPhase.h:128
b2Pair * m_pairBuffer
Definition: b2BroadPhase.h:124
int32 m_moveCount
Definition: b2BroadPhase.h:122
GLenum GLenum GLenum input
Ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
Definition: b2Collision.h:147
float32 GetTreeQuality() const
Get the quality metric of the embedded tree.
Definition: b2BroadPhase.h:179
int32 m_proxyCount
Definition: b2BroadPhase.h:118
int32 proxyIdB
Definition: b2BroadPhase.h:30
A 2D column vector.
Definition: b2Math.h:52
void Query(T *callback, const b2AABB &aabb) const
Definition: b2BroadPhase.h:241
int32 GetProxyCount() const
Get the number of proxies.
Definition: b2BroadPhase.h:164
signed int int32
Definition: b2Settings.h:31
void UpdatePairs(T *callback)
Update the pairs. This results in pair callbacks. This can only add pairs.
Definition: b2BroadPhase.h:185
void RayCast(T *callback, const b2RayCastInput &input) const
Definition: b2BroadPhase.h:247
void ShiftOrigin(const b2Vec2 &newOrigin)
Definition: b2BroadPhase.h:252
int32 GetTreeHeight() const
Get the height of the embedded tree.
Definition: b2BroadPhase.h:169
const b2AABB & GetFatAABB(int32 proxyId) const
Get the fat AABB for a proxy.
Definition: b2BroadPhase.h:159
An axis aligned bounding box.
Definition: b2Collision.h:162
int32 m_pairCount
Definition: b2BroadPhase.h:126
int32 m_moveCapacity
Definition: b2BroadPhase.h:121
int32 * m_moveBuffer
Definition: b2BroadPhase.h:120
void * GetUserData(int32 proxyId) const
Get user data from a proxy. Returns NULL if the id is invalid.
Definition: b2BroadPhase.h:147
b2DynamicTree m_tree
Definition: b2BroadPhase.h:116
int32 m_pairCapacity
Definition: b2BroadPhase.h:125
bool b2TestOverlap(const b2Shape *shapeA, int32 indexA, const b2Shape *shapeB, int32 indexB, const b2Transform &xfA, const b2Transform &xfB)
Determine if two generic shapes overlap.
bool b2PairLessThan(const b2Pair &pair1, const b2Pair &pair2)
This is used to sort pairs.
Definition: b2BroadPhase.h:132
bool TestOverlap(int32 proxyIdA, int32 proxyIdB) const
Test overlap of fat AABBs.
Definition: b2BroadPhase.h:152
int32 proxyIdA
Definition: b2BroadPhase.h:29
float float32
Definition: b2Settings.h:35


mvsim
Author(s):
autogenerated on Fri May 7 2021 03:05:51