解决PolygonSoup碰撞检测的成熟方案是使用层次BV树,根据BV的不同衍生出:AABB,OBB,K-dop三种方案.
在内存使用上: AABB -> OBB -> K-dop递增.在效率上则尚无定论,根据具体的应用环境不同而不同.
Opcode: 开源,完全免费,采用AABB树构造,内存耗用很小,支持复杂模型,起初想使用它,但发现其,基本上没有文档,Sample,1.3版本接口变动巨大,且无文档,自2003年来再无更新,最致命的是不支持Instance transform的Scale,AABBCollider没有Transform支持,而且是在看代码时发现的,吐血.主要设计目标是少的内存耗用,但速度也很快.为ODE,Tokamak,Crystal Space所用.
RAPID: 开源,免费,采用OBB构造,内存耗用巨大,学院派设计,最倒霉的库,因为其他每个库都拿它作比较,都说比它快.
SOLID: GPL开源,商业软件,采用AABB树构造,2005.4月出3.5版本,效率不错,内存耗用中等,在后面4.0会支持AABB数据压缩,有文档,接口简单,代码清晰.支持复杂模型,支持Instance transform的Scale,甚至支持各向不等缩放,支持Penetration Depth计算,cool.作者Gino van den Bergen是3D碰撞研究专家,著有:Collision Detection in Interactive 3D Environments一书,有e版.逻辑顺畅地集成入DM,效果不错,满足使用要求.不过其IndexBuffer是unsigned int,Matrix是DX风格的,但代码很清晰,很容易定制.
SOLID有个严重的Bug,必须确保DT_GetCommonPoint,DT_GetPenDepth,DT_GetClosestPair在检测Complex和Convex对象时,第一个参数必须是Complex对象,否则崩溃.因为SOLID的double dispatch实现有问题,不完整,没有Convex + Complex顺序的对应函数.
QuickCD: 开源,免费,K-dop树构造.
ColDet,支持复杂模型,也不支持Instance Transform的Scale.
Reference:
http://www.codercorner.com/Opcode.htm
http://www.dtecta.com/
http://www.cs.unc.edu/~geom/OBB/OBBT.html
http://www.ams.sunysb.edu/~jklosow/quickcd/QuickCD.html
http://photoneffect.com/coldet/
http://www.merl.com/projects/vclip/
http://www.q12.org/ode/ode.html
void DmModel::SetBoundPolygonSoup(uint32 nPolygonSoupVertices, vec3_type* pVertices, uint32 nTrianglePrims, uint16* pTrianglePrims)
{
ASSERT(m_hSolidShape == NULL);
if(nTrianglePrims == 0) return;
if(nPolygonSoupVertices == 0) return;
// Save polygon soup data for collision test!
m_pPolygonSoupVertices = new vec3_type[nPolygonSoupVertices];
memcpy(m_pPolygonSoupVertices, pVertices, sizeof(vec3_type) * nPolygonSoupVertices);
// Build
DT_VertexBaseHandle hVertexBase = DT_NewVertexBase(m_pPolygonSoupVertices, 0);
m_hSolidShape = DT_NewComplexShape(hVertexBase);
m_hSolidVertexBase = hVertexBase;
// Define mesh triangles
for(uint32 i = 0; i < nTrianglePrims; i += 3)
{
DT_VertexIndices(3, pTrianglePrims + i);
}
// End it
DT_EndComplexShape();
}
void DmModelInstanceNode::BuildPhysics()
{
// Setup Phisic stuffs
DT_ShapeHandle hShape = (DT_ShapeHandle)m_pRefModelInstance->m_pRefModel->m_hSolidShape;
if(hShape)
{
DT_ObjectHandle hObject = DT_CreateObject(NULL, hShape);
DM_SetMatrixf(hObject, m_matTransform);
m_hSolidObject = hObject;
}
}
void DmGameCreature::BuildPhysics()
{
ASSERT(m_hSolidObject == NULL);
vec3_type vMin, vMax;
getBoundBox(vMin, vMax);
DT_ShapeHandle hShape = DT_NewBox(vMax.x - vMin.x, vMax.y - vMin.y, vMax.z - vMin.z);
DT_ObjectHandle hObject = DT_CreateObject(NULL, hShape);
m_hSolidShape = hShape;
m_hSolidObject = hObject;
}
bool DmModelInstanceNode::TestCollision(HANDLE hSolidObject)
{
if(!m_hSolidObject) return false;
DT_ObjectHandle hTestObject = (DT_ObjectHandle)hSolidObject;
DT_ObjectHandle hThisObject = (DT_ObjectHandle)m_hSolidObject;
DT_Vector3 v;
return (DT_GetCommonPoint(hThisObject, hTestObject, v) != 0);
}