Bullet 物理引擎详细分析 Dbvt (4)

现在的位置: 首页 > 综合 > 正文

Bullet 物理引擎详细分析 Dbvt (4)

2012年09月28日 ⁄ 综合 ⁄ 共 3975字 ⁄ 字号小中大 ⁄ 评论关闭

光线与AABB 相交检测：
这是一个非常经典的问题， <<real time collision detection>> 5.33章节有非常详尽的讨论。
下面是光线的方程

t是可变参数， P是光线的起始点 RayFrom， d是光线的方向向量

下面这个是平面的方程

向量n是平面的法向量，所以如果光线与任何一个平面相交，应该有如下等式

对于AABB来说是六个平面，每个面的法向量为（0,0,1)(0,1,0) ..... 总之三个坐标有两个是0，另外的一个是1或者－1
AABB同时是3个平面槽的交集，光线与AABB最多有2个相交点，一个是前景点，一个后景点，分别与两个平面相交。
特例是完全与一个平面重合。可以被认为是和相邻的两个平面相交。
btRayAabb2.是bullet中用于检测的相关函数

view plaincopy to clipboardprint?
SIMD_FORCE_INLINE bool btRayAabb2(const btVector3& rayFrom, // point P
const btVector3& rayInvDirection, // Direction Vector inverse
const unsigned int raySign[3],
const btVector3 bounds[2],    // min x, max x AABB volume
btScalar& tmin,
btScalar lambda_min,
btScalar lambda_max)
{
btScalar tmax, tymin, tymax, tzmin, tzmax;
// get the far plane intersect param t along x axis
tmax = (bounds[1-raySign[0]].getX() - rayFrom.getX()) * rayInvDirection.getX();
// get the near plane intersect param t along y axis
tymin = (bounds[raySign[1]].getY() - rayFrom.getY()) * rayInvDirection.getY();
// get the far plane intersect param t along y axis
tymax = (bounds[1-raySign[1]].getY() - rayFrom.getY()) * rayInvDirection.getY();
// if it is not intersect with any plane then exit
if ( (tmin > tymax) || (tymin > tmax) )
return false;
if (tymin > tmin)
tmin = tymin; // update the tmin
if (tymax < tmax)
tmax = tymax; // update tmax
// get the near plane intersect param t along Z axis
tzmin = (bounds[raySign[2]].getZ() - rayFrom.getZ()) * rayInvDirection.getZ();
// get the far plane intersect param t along Z axis
tzmax = (bounds[1-raySign[2]].getZ() - rayFrom.getZ()) * rayInvDirection.getZ();
// if it is not intersect with any plane then exit
if ( (tmin > tzmax) || (tzmin > tmax) )
return false;
// caculate the interval
if (tzmin > tmin)
tmin = tzmin;   // if find nearer point update tmin
if (tzmax < tmax)
tmax = tzmax;   // if found the farer point update tmax
return ( (tmin < lambda_max) && (tmax > lambda_min) );
}
SIMD_FORCE_INLINE bool btRayAabb2(const btVector3& rayFrom, // point P
const btVector3& rayInvDirection, // Direction Vector inverse
const unsigned int raySign[3],
const btVector3 bounds[2],    // min x, max x AABB volume
btScalar& tmin,
btScalar lambda_min,
btScalar lambda_max)
{
btScalar tmax, tymin, tymax, tzmin, tzmax;
// get the far plane intersect param t along x axis
tmax = (bounds[1-raySign[0]].getX() - rayFrom.getX()) * rayInvDirection.getX();
// get the near plane intersect param t along y axis
tymin = (bounds[raySign[1]].getY() - rayFrom.getY()) * rayInvDirection.getY();
// get the far plane intersect param t along y axis
tymax = (bounds[1-raySign[1]].getY() - rayFrom.getY()) * rayInvDirection.getY();
// if it is not intersect with any plane then exit
if ( (tmin > tymax) || (tymin > tmax) )
return false;
if (tymin > tmin)
tmin = tymin; // update the tmin
if (tymax < tmax)
tmax = tymax; // update tmax
// get the near plane intersect param t along Z axis
tzmin = (bounds[raySign[2]].getZ() - rayFrom.getZ()) * rayInvDirection.getZ();
// get the far plane intersect param t along Z axis
tzmax = (bounds[1-raySign[2]].getZ() - rayFrom.getZ()) * rayInvDirection.getZ();
// if it is not intersect with any plane then exit
if ( (tmin > tzmax) || (tzmin > tmax) )
return false;
// caculate the interval
if (tzmin > tmin)
tmin = tzmin;   // if find nearer point update tmin
if (tzmax < tmax)
tmax = tzmax;   // if found the farer point update tmax
return ( (tmin < lambda_max) && (tmax > lambda_min) );
}

现在可以讨论ayTestInternal 函数，这个函数基本的算法就是遍历所有的节点（基于栈）
光线讲和树中的每个节点做相交测试，如果相交就继续处理对应的子结点，否则就跳过。
对应所有最终的相交叶子节点，调用相交处理逻辑（回调函数）来处理。

view plaincopy to clipboardprint?
do
{
//pop out the top of stack
const btDbvtNode* node=stack[--depth];
//set up the AABB BOX
bounds[0] = node->volume.Mins()-aabbMax;
bounds[1] = node->volume.Maxs()-aabbMin;
btScalar tmin=1.f,lambda_min=0.f;
unsigned int result1=false;
// Do the intersect tes t!!
result1 = btRayAabb2(rayFrom,rayDirectionInverse,
signs,bounds,tmin,lambda_min,
lambda_max);
if(result1)
{
//if test pass
if(node->isinternal())
{ //if node is intertal
if(depth>treshold) //dynamic expand stack
{
stack.resize(stack.size()*2);
treshold=stack.size()-2;
}
//push the left child into stack
stack[depth++]=node->childs[0];
//push the right child into stack
stack[depth++]=node->childs[1];
}
else
{
//if node is leaf node,then process it by callback
policy.Process(node);
}
}
} while(depth);