23 #ifndef B2_DYNAMIC_TREE_H
24 #define B2_DYNAMIC_TREE_H
28 #include "b2_growable_stack.h"
30 #define b2_nullNode (-1)
37 return child1 == b2_nullNode;
78 int32 CreateProxy(
const b2AABB& aabb,
void* userData);
81 void DestroyProxy(int32 proxyId);
87 bool MoveProxy(int32 proxyId,
const b2AABB& aabb1,
const b2Vec2& displacement);
91 void* GetUserData(int32 proxyId)
const;
93 bool WasMoved(int32 proxyId)
const;
94 void ClearMoved(int32 proxyId);
97 const b2AABB& GetFatAABB(int32 proxyId)
const;
101 template <
typename T>
102 void Query(T* callback,
const b2AABB& aabb)
const;
111 template <
typename T>
115 void Validate()
const;
119 int32 GetHeight()
const;
123 int32 GetMaxBalance()
const;
126 float GetAreaRatio()
const;
129 void RebuildBottomUp();
134 void ShiftOrigin(
const b2Vec2& newOrigin);
138 int32 AllocateNode();
139 void FreeNode(int32 node);
141 void InsertLeaf(int32 node);
142 void RemoveLeaf(int32 node);
144 int32 Balance(int32 index);
146 int32 ComputeHeight()
const;
147 int32 ComputeHeight(int32 nodeId)
const;
149 void ValidateStructure(int32 index)
const;
150 void ValidateMetrics(int32 index)
const;
156 int32 m_nodeCapacity;
160 int32 m_insertionCount;
165 b2Assert(0 <= proxyId && proxyId < m_nodeCapacity);
166 return m_nodes[proxyId].userData;
169 inline bool b2DynamicTree::WasMoved(int32 proxyId)
const
171 b2Assert(0 <= proxyId && proxyId < m_nodeCapacity);
172 return m_nodes[proxyId].moved;
175 inline void b2DynamicTree::ClearMoved(int32 proxyId)
177 b2Assert(0 <= proxyId && proxyId < m_nodeCapacity);
178 m_nodes[proxyId].moved =
false;
183 b2Assert(0 <= proxyId && proxyId < m_nodeCapacity);
184 return m_nodes[proxyId].
aabb;
187 template <
typename T>
193 while (stack.GetCount() > 0)
195 int32 nodeId = stack.Pop();
196 if (nodeId == b2_nullNode)
207 bool proceed = callback->QueryCallback(nodeId);
208 if (proceed ==
false)
215 stack.Push(node->child1);
216 stack.Push(node->child2);
222 template <
typename T>
232 b2Vec2 v = b2Cross(1.0f, r);
238 float maxFraction = input.maxFraction;
243 b2Vec2 t = p1 + maxFraction * (p2 - p1);
251 while (stack.GetCount() > 0)
253 int32 nodeId = stack.Pop();
254 if (nodeId == b2_nullNode)
270 float separation = b2Abs(b2Dot(v, p1 - c)) - b2Dot(abs_v, h);
271 if (separation > 0.0f)
279 subInput.p1 = input.p1;
280 subInput.p2 = input.p2;
281 subInput.maxFraction = maxFraction;
283 float value = callback->RayCastCallback(subInput, nodeId);
295 b2Vec2 t = p1 + maxFraction * (p2 - p1);
302 stack.Push(node->child1);
303 stack.Push(node->child2);