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 "../Common/b2Settings.h"
23 #include "b2Collision.h"
24 #include "b2DynamicTree.h"
25 #include <algorithm>
26
27 struct b2Pair
28 {
29 juce::int32 proxyIdA;
30 juce::int32 proxyIdB;
31 juce::int32 next;
32 };
33
34 /// The broad-phase is used for computing pairs and performing volume queries and ray casts.
35 /// This broad-phase does not persist pairs. Instead, this reports potentially new pairs.
36 /// It is up to the client to consume the new pairs and to track subsequent overlap.
37 class b2BroadPhase
38 {
39 public:
40
41 enum
42 {
43 e_nullProxy = -1
44 };
45
46 b2BroadPhase();
47 ~b2BroadPhase();
48
49 /// Create a proxy with an initial AABB. Pairs are not reported until
50 /// UpdatePairs is called.
51 juce::int32 CreateProxy(const b2AABB& aabb, void* userData);
52
53 /// Destroy a proxy. It is up to the client to remove any pairs.
54 void DestroyProxy(juce::int32 proxyId);
55
56 /// Call MoveProxy as many times as you like, then when you are done
57 /// call UpdatePairs to finalized the proxy pairs (for your time step).
58 void MoveProxy(juce::int32 proxyId, const b2AABB& aabb, const b2Vec2& displacement);
59
60 /// Call to trigger a re-processing of it's pairs on the next call to UpdatePairs.
61 void TouchProxy(juce::int32 proxyId);
62
63 /// Get the fat AABB for a proxy.
64 const b2AABB& GetFatAABB(juce::int32 proxyId) const;
65
66 /// Get user data from a proxy. Returns NULL if the id is invalid.
67 void* GetUserData(juce::int32 proxyId) const;
68
69 /// Test overlap of fat AABBs.
70 bool TestOverlap(juce::int32 proxyIdA, juce::int32 proxyIdB) const;
71
72 /// Get the number of proxies.
73 juce::int32 GetProxyCount() const;
74
75 /// Update the pairs. This results in pair callbacks. This can only add pairs.
76 template <typename T>
77 void UpdatePairs(T* callback);
78
79 /// Query an AABB for overlapping proxies. The callback class
80 /// is called for each proxy that overlaps the supplied AABB.
81 template <typename T>
82 void Query(T* callback, const b2AABB& aabb) const;
83
84 /// Ray-cast against the proxies in the tree. This relies on the callback
85 /// to perform a exact ray-cast in the case were the proxy contains a shape.
86 /// The callback also performs the any collision filtering. This has performance
87 /// roughly equal to k * log(n), where k is the number of collisions and n is the
88 /// number of proxies in the tree.
89 /// @param input the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
90 /// @param callback a callback class that is called for each proxy that is hit by the ray.
91 template <typename T>
92 void RayCast(T* callback, const b2RayCastInput& input) const;
93
94 /// Get the height of the embedded tree.
95 juce::int32 GetTreeHeight() const;
96
97 /// Get the balance of the embedded tree.
98 juce::int32 GetTreeBalance() const;
99
100 /// Get the quality metric of the embedded tree.
101 float32 GetTreeQuality() const;
102
103 private:
104
105 friend class b2DynamicTree;
106
107 void BufferMove(juce::int32 proxyId);
108 void UnBufferMove(juce::int32 proxyId);
109
110 bool QueryCallback(juce::int32 proxyId);
111
112 b2DynamicTree m_tree;
113
114 juce::int32 m_proxyCount;
115
116 juce::int32* m_moveBuffer;
117 juce::int32 m_moveCapacity;
118 juce::int32 m_moveCount;
119
120 b2Pair* m_pairBuffer;
121 juce::int32 m_pairCapacity;
122 juce::int32 m_pairCount;
123
124 juce::int32 m_queryProxyId;
125 };
126
127 /// This is used to sort pairs.
b2PairLessThan(const b2Pair & pair1,const b2Pair & pair2)128 inline bool b2PairLessThan(const b2Pair& pair1, const b2Pair& pair2)
129 {
130 if (pair1.proxyIdA < pair2.proxyIdA)
131 {
132 return true;
133 }
134
135 if (pair1.proxyIdA == pair2.proxyIdA)
136 {
137 return pair1.proxyIdB < pair2.proxyIdB;
138 }
139
140 return false;
141 }
142
GetUserData(juce::int32 proxyId)143 inline void* b2BroadPhase::GetUserData(juce::int32 proxyId) const
144 {
145 return m_tree.GetUserData(proxyId);
146 }
147
TestOverlap(juce::int32 proxyIdA,juce::int32 proxyIdB)148 inline bool b2BroadPhase::TestOverlap(juce::int32 proxyIdA, juce::int32 proxyIdB) const
149 {
150 const b2AABB& aabbA = m_tree.GetFatAABB(proxyIdA);
151 const b2AABB& aabbB = m_tree.GetFatAABB(proxyIdB);
152 return b2TestOverlap(aabbA, aabbB);
153 }
154
GetFatAABB(juce::int32 proxyId)155 inline const b2AABB& b2BroadPhase::GetFatAABB(juce::int32 proxyId) const
156 {
157 return m_tree.GetFatAABB(proxyId);
158 }
159
GetProxyCount()160 inline juce::int32 b2BroadPhase::GetProxyCount() const
161 {
162 return m_proxyCount;
163 }
164
GetTreeHeight()165 inline juce::int32 b2BroadPhase::GetTreeHeight() const
166 {
167 return m_tree.GetHeight();
168 }
169
GetTreeBalance()170 inline juce::int32 b2BroadPhase::GetTreeBalance() const
171 {
172 return m_tree.GetMaxBalance();
173 }
174
GetTreeQuality()175 inline float32 b2BroadPhase::GetTreeQuality() const
176 {
177 return m_tree.GetAreaRatio();
178 }
179
180 template <typename T>
UpdatePairs(T * callback)181 void b2BroadPhase::UpdatePairs(T* callback)
182 {
183 // Reset pair buffer
184 m_pairCount = 0;
185
186 // Perform tree queries for all moving proxies.
187 for (juce::int32 i = 0; i < m_moveCount; ++i)
188 {
189 m_queryProxyId = m_moveBuffer[i];
190 if (m_queryProxyId == e_nullProxy)
191 {
192 continue;
193 }
194
195 // We have to query the tree with the fat AABB so that
196 // we don't fail to create a pair that may touch later.
197 const b2AABB& fatAABB = m_tree.GetFatAABB(m_queryProxyId);
198
199 // Query tree, create pairs and add them pair buffer.
200 m_tree.Query(this, fatAABB);
201 }
202
203 // Reset move buffer
204 m_moveCount = 0;
205
206 // Sort the pair buffer to expose duplicates.
207 std::sort(m_pairBuffer, m_pairBuffer + m_pairCount, b2PairLessThan);
208
209 // Send the pairs back to the client.
210 juce::int32 i = 0;
211 while (i < m_pairCount)
212 {
213 b2Pair* primaryPair = m_pairBuffer + i;
214 void* userDataA = m_tree.GetUserData(primaryPair->proxyIdA);
215 void* userDataB = m_tree.GetUserData(primaryPair->proxyIdB);
216
217 callback->AddPair(userDataA, userDataB);
218 ++i;
219
220 // Skip any duplicate pairs.
221 while (i < m_pairCount)
222 {
223 b2Pair* pair = m_pairBuffer + i;
224 if (pair->proxyIdA != primaryPair->proxyIdA || pair->proxyIdB != primaryPair->proxyIdB)
225 {
226 break;
227 }
228 ++i;
229 }
230 }
231
232 // Try to keep the tree balanced.
233 //m_tree.Rebalance(4);
234 }
235
236 template <typename T>
Query(T * callback,const b2AABB & aabb)237 inline void b2BroadPhase::Query(T* callback, const b2AABB& aabb) const
238 {
239 m_tree.Query(callback, aabb);
240 }
241
242 template <typename T>
RayCast(T * callback,const b2RayCastInput & input)243 inline void b2BroadPhase::RayCast(T* callback, const b2RayCastInput& input) const
244 {
245 m_tree.RayCast(callback, input);
246 }
247
248 #endif
249