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
22#include <Box2D/Common/b2Settings.h>
23#include <Box2D/Collision/b2Collision.h>
24#include <Box2D/Collision/b2DynamicTree.h>
25#include <algorithm>
26
27struct b2Pair
28{
29 int32 proxyIdA;
30 int32 proxyIdB;
31};
32
33/// The broad-phase is used for computing pairs and performing volume queries and ray casts.
34/// This broad-phase does not persist pairs. Instead, this reports potentially new pairs.
35/// It is up to the client to consume the new pairs and to track subsequent overlap.
36class b2BroadPhase
37{
38public:
39
40 enum
41 {
42 e_nullProxy = -1
43 };
44
45 b2BroadPhase();
46 ~b2BroadPhase();
47
48 /// Create a proxy with an initial AABB. Pairs are not reported until
49 /// UpdatePairs is called.
50 int32 CreateProxy(const b2AABB& aabb, void* userData);
51
52 /// Destroy a proxy. It is up to the client to remove any pairs.
53 void DestroyProxy(int32 proxyId);
54
55 /// Call MoveProxy as many times as you like, then when you are done
56 /// call UpdatePairs to finalized the proxy pairs (for your time step).
57 void MoveProxy(int32 proxyId, const b2AABB& aabb, const b2Vec2& displacement);
58
59 /// Call to trigger a re-processing of it's pairs on the next call to UpdatePairs.
60 void TouchProxy(int32 proxyId);
61
62 /// Get the fat AABB for a proxy.
63 const b2AABB& GetFatAABB(int32 proxyId) const;
64
65 /// Get user data from a proxy. Returns NULL if the id is invalid.
66 void* GetUserData(int32 proxyId) const;
67
68 /// Test overlap of fat AABBs.
69 bool TestOverlap(int32 proxyIdA, int32 proxyIdB) const;
70
71 /// Get the number of proxies.
72 int32 GetProxyCount() const;
73
74 /// Update the pairs. This results in pair callbacks. This can only add pairs.
75 template <typename T>
76 void UpdatePairs(T* callback);
77
78 /// Query an AABB for overlapping proxies. The callback class
79 /// is called for each proxy that overlaps the supplied AABB.
80 template <typename T>
81 void Query(T* callback, const b2AABB& aabb) const;
82
83 /// Ray-cast against the proxies in the tree. This relies on the callback
84 /// to perform a exact ray-cast in the case were the proxy contains a shape.
85 /// The callback also performs the any collision filtering. This has performance
86 /// roughly equal to k * log(n), where k is the number of collisions and n is the
87 /// number of proxies in the tree.
88 /// @param input the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
89 /// @param callback a callback class that is called for each proxy that is hit by the ray.
90 template <typename T>
91 void RayCast(T* callback, const b2RayCastInput& input) const;
92
93 /// Get the height of the embedded tree.
94 int32 GetTreeHeight() const;
95
96 /// Get the balance of the embedded tree.
97 int32 GetTreeBalance() const;
98
99 /// Get the quality metric of the embedded tree.
100 float32 GetTreeQuality() const;
101
102 /// Shift the world origin. Useful for large worlds.
103 /// The shift formula is: position -= newOrigin
104 /// @param newOrigin the new origin with respect to the old origin
105 void ShiftOrigin(const b2Vec2& newOrigin);
106
107private:
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
131/// This is used to sort pairs.
132inline 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
147inline void* b2BroadPhase::GetUserData(int32 proxyId) const
148{
149 return m_tree.GetUserData(proxyId);
150}
151
152inline 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
159inline const b2AABB& b2BroadPhase::GetFatAABB(int32 proxyId) const
160{
161 return m_tree.GetFatAABB(proxyId);
162}
163
164inline int32 b2BroadPhase::GetProxyCount() const
165{
166 return m_proxyCount;
167}
168
169inline int32 b2BroadPhase::GetTreeHeight() const
170{
171 return m_tree.GetHeight();
172}
173
174inline int32 b2BroadPhase::GetTreeBalance() const
175{
176 return m_tree.GetMaxBalance();
177}
178
179inline float32 b2BroadPhase::GetTreeQuality() const
180{
181 return m_tree.GetAreaRatio();
182}
183
184template <typename T>
185void 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
240template <typename T>
241inline void b2BroadPhase::Query(T* callback, const b2AABB& aabb) const
242{
243 m_tree.Query(callback, aabb);
244}
245
246template <typename T>
247inline void b2BroadPhase::RayCast(T* callback, const b2RayCastInput& input) const
248{
249 m_tree.RayCast(callback, input);
250}
251
252inline void b2BroadPhase::ShiftOrigin(const b2Vec2& newOrigin)
253{
254 m_tree.ShiftOrigin(newOrigin);
255}
256
257#endif
258