cococococos 2 d-xノード(b 2 DynamicTree.h)API
8741 ワード
本論文はhttp://blog.csdn.net/runaying ,引用は出典を明記しなければならない!
cococococos 2 d-xノード(b 2 DynamicTree.h)API
みなさんがよりよく勉強できるように、私のブログを見ることを強くおすすめします. Cocos 2 d-X権威ガイドノート
//システムの衝突検出の速度を上げるために使用します.
//主にユーザーデータを操作して軸を揃えて取り囲むボックス(axis-alignedbounding bounding boxes、AABBs)を操作して、ツリーの様々な操作を完成します.また、AABBツリーから受け継いで、ツリー上の各ノードには子供が二人います.リーフノードは単独のユーザーAABBです.不活性入力でも、全体の数字は回転でバランスを維持できます.
cococococos 2 d-xノード(b 2 DynamicTree.h)API
みなさんがよりよく勉強できるように、私のブログを見ることを強くおすすめします. Cocos 2 d-X権威ガイドノート
//システムの衝突検出の速度を上げるために使用します.
//主にユーザーデータを操作して軸を揃えて取り囲むボックス(axis-alignedbounding bounding boxes、AABBs)を操作して、ツリーの様々な操作を完成します.また、AABBツリーから受け継いで、ツリー上の各ノードには子供が二人います.リーフノードは単独のユーザーAABBです.不活性入力でも、全体の数字は回転でバランスを維持できます.
///cocos2d-x-3.0alpha0/external/Box2D/Collision
// 。
// （axis-alignedbounding boxes,AABBs） 。 AABB ， 。 AABB。 ， 。
#ifndef B2_DYNAMIC_TREE_H
#define B2_DYNAMIC_TREE_H
#include <Box2D/Collision/b2Collision.h>
#include <Box2D/Common/b2GrowableStack.h>
//
#define b2_nullNode (-1)
/// ，
struct b2TreeNode
{
//
bool IsLeaf() const
{
return child1 == b2_nullNode;
}
/// Enlarged AABB
// aabb
b2AABB aabb;
//
void* userData;
// ( ) ( )
// ， n
// 。 ，
union
{
int32 parent;
int32 next;
};
//
int32 child1;
int32 child2;
// 0， -1
// leaf = 0, free node = -1
int32 height;
};
// AABB broad-phase, Nathanael Presson's btDbvt.
// 。
// b2_fatAABBFactor aabb ， aabb 。
//
// ，
class b2DynamicTree
{
public:
/// ，
b2DynamicTree();
/// ，
~b2DynamicTree();
///
// * ：aabb ：aabb
// user :
// * ： , .
int32 CreateProxy(const b2AABB& aabb, void* userData);
// ， id
// * ：poxyid : id
// * ： ,
void DestroyProxy(int32 proxyId);
// AABB, AABB
// 。 ，
// * ：proxyId ： id
// aabb : aabb
// displacement：
// * ： true :
// false:
bool MoveProxy(int32 proxyId, const b2AABB& aabb1, const b2Vec2& displacement);
// * ： userData
// * ：proxyId： id
// * ：id ， userData
// id ， 0
void* GetUserData(int32 proxyId) const;
// * ： AABB
// * ：proxyId： id
// * ：aabb
const b2AABB& GetFatAABB(int32 proxyId) const;
// * ：callback ：
// aabb ： aabb
// * ：aabb
template <typename T>
void Query(T* callback, const b2AABB& aabb) const;
// * ： 。
//
// 。
// k * log(n), k ，n
// * ：callback ： ，
// input ： ， p1 + maxFraction * (p2 - p1)
template <typename T>
void RayCast(T* callback, const b2RayCastInput& input) const;
/// ，
void Validate() const;
// O(N) ，
int32 GetHeight() const;
/// 。
int32 GetMaxBalance() const;
///
float32 GetAreaRatio() const;
/// ， ，
// * ：(void)
// * ：
void RebuildBottomUp();
private:
int32 AllocateNode(); // .
void FreeNode(int32 node); //
void InsertLeaf(int32 node); //
void RemoveLeaf(int32 node); //
int32 Balance(int32 index); // a ， * ：iA ： * ：
int32 ComputeHeight() const; //
int32 ComputeHeight(int32 nodeId) const; // * ：nodeid：
void ValidateStructure(int32 index) const; // * ：index:
void ValidateMetrics(int32 index) const; // * ：index:
int32 m_root; // ( )
b2TreeNode* m_nodes; // ，
int32 m_nodeCount; //
int32 m_nodeCapacity; //
int32 m_freeList; //
/// //
uint32 m_path;
int32 m_insertionCount; //
};
// id userData
inline void* b2DynamicTree::GetUserData(int32 proxyId) const
{
// id
b2Assert(0 <= proxyId && proxyId < m_nodeCapacity);
return m_nodes[proxyId].userData;
}
// id AABB
inline const b2AABB& b2DynamicTree::GetFatAABB(int32 proxyId) const
{
// id
b2Assert(0 <= proxyId && proxyId < m_nodeCapacity);
return m_nodes[proxyId].aabb;
}
// aabb ， AABB
template <typename T>
inline void b2DynamicTree::Query(T* callback, const b2AABB& aabb) const
{
// ，
b2GrowableStack<int32, 256> stack;
stack.Push(m_root);
//
while (stack.GetCount() > 0)
{
// id
int32 nodeId = stack.Pop();
if (nodeId == b2_nullNode)
{
//
continue;
}
//
const b2TreeNode* node = m_nodes + nodeId;
//
if (b2TestOverlap(node->aabb, aabb))
{
//
if (node->IsLeaf())
{
//
bool proceed = callback->QueryCallback(nodeId);
if (proceed == false)
{
return;
}
}
else
{
//
stack.Push(node->child1);
stack.Push(node->child2);
}
}
}
}
//
template <typename T>
inline void b2DynamicTree::RayCast(T* callback, const b2RayCastInput& input) const
{
b2Vec2 p1 = input.p1;
b2Vec2 p2 = input.p2;
b2Vec2 r = p2 - p1;
b2Assert(r.LengthSquared() > 0.0f);
r.Normalize();
//v r
b2Vec2 v = b2Cross(1.0f, r);
b2Vec2 abs_v = b2Abs(v);
// p80
// 《Collision Detection in Interactive 3D Environments》 by Gino van den Bergen
// 【 http://download.csdn.net/detail/cg0206/4875309 】
// ：|dot(v, p1 - c)| > dot(|v|, h)
float32 maxFraction = input.maxFraction;
//
b2AABB segmentAABB;
{
b2Vec2 t = p1 + maxFraction * (p2 - p1);
segmentAABB.lowerBound = b2Min(p1, t);
segmentAABB.upperBound = b2Max(p1, t);
}
// ，
b2GrowableStack<int32, 256> stack;
stack.Push(m_root);
//
while (stack.GetCount() > 0)
{
//
int32 nodeId = stack.Pop();
if (nodeId == b2_nullNode)
{
//
continue;
}
//
const b2TreeNode* node = m_nodes + nodeId;
// AABB
if (b2TestOverlap(node->aabb, segmentAABB) == false)
{
continue;
}
// Separating axis for segment (Gino, p80). // // p80
// |dot(v, p1 - c)| > dot(|v|, h)
b2Vec2 c = node->aabb.GetCenter();
b2Vec2 h = node->aabb.GetExtents();
float32 separation = b2Abs(b2Dot(v, p1 - c)) - b2Dot(abs_v, h);
if (separation > 0.0f)
{
continue;
}
//
if (node->IsLeaf())
{
b2RayCastInput subInput;
subInput.p1 = input.p1;
subInput.p2 = input.p2;
subInput.maxFraction = maxFraction;
float32 value = callback->RayCastCallback(subInput, nodeId);
if (value == 0.0f)
{
//
return;
}
if (value > 0.0f)
{
//
maxFraction = value;
b2Vec2 t = p1 + maxFraction * (p2 - p1);
segmentAABB.lowerBound = b2Min(p1, t);
segmentAABB.upperBound = b2Max(p1, t);
}
}
else
{
//
stack.Push(node->child1);
stack.Push(node->child2);
}
}
}
#endif