Bullet中最近点距离算法在Bullet中，通过类btVoronoiSimplexSolve实现了1到4个顶点的单纯形到原点的距离计算，该类可以在GJK算法中调用，用以代替Johnson distance algorithm[我们前篇文章原点到四面体的距离，实际上就是介绍该算法]算法。

本文我们研究bullet中如何实现该类以及该类的用法。

首先我们看看顶点在btVoronoiSimplexSolve中是什么存储的：用到了三个变量：btVector3 m_simplexVectorW[VORONOI_SIMPLEX_MAX_VERTS];btVector3 m_simplexPointsP[VORONOI_SIMPLEX_MAX_VERTS];btVector3 m_simplexPointsQ[VORONOI_SIMPLEX_MAX_VERTS];m_simplexVectorW中存放的是单纯形的顶点，m_simplexVectorP,m_simplexVectorQ中存放的是两个物体中和单纯形顶点m_simplexVectorW相对应的顶点，注意，这儿单纯形表示是明可夫斯基差形状中的单纯形，所以m_simplexVectorP,m_simplexVectorQ就是表示两个物体中的顶点，并且m_simplexVectorP -m_simplexVectorQ = m_simplexVectorW。

（都是世界坐标系中的值）该类中计算机单纯形到原点距离通过函数closest计算，该函数又调用函数updateClosestVectorAndPoints具体实施。

下面我看看updateClosestVectorAndPoints中的代码：1、一个顶点的单纯形1case1://一个顶点2{3m_cachedP1 = m_simplexPointsP[0];4m_cachedP2 = m_simplexPointsQ[0];5m_cachedV = m_cachedP1-m_cachedP2; //== m_simplexVe ctorW[0]6m_cachedBC.reset();7m_cachedBC.setBarycentricCoordinates(btScalar(1.),b tScalar(0.),btScalar(0.),btScalar(0.)); //只使用了第一个顶点8m_cachedValidClosest = m_cachedBC.isValid();9break;10};单纯形是一个顶点的情况下，直接返回m_simplexVectorW（m_simplexVectorP - m_simplexVectorQ）顶点坐标。

单纯形到原点的距离放在向量m_cachedV中。

2、两个顶点的单纯形1case2://两个顶点2{3//closest point origin from line segment4const btVector3& from = m_simplexVectorW[0];5const btVector3& to = m_simplexVectorW[1];6btVector3 nearest;78btVector3 p (btScalar(0.),btScalar(0.),btScalar (0.));9btVector3 diff = p - from;1btVector3 v = to - from;11btScalar t = v.dot(diff);1213if (t >0) {14btScalar dotVV = v.dot(v);15if (t < dotVV) {16t /= dotVV;17diff -= t*v;1 8m_cachedBC.m_edVertexA = true;1 9m_cachedBC.m_edVertexB = true;20} else {21t =1;22diff -= v;23//reduce to 1 point2 4m_cachedBC.m_edVertexB = true;2}26} else27{28t =0;29//reduce to 1 point3 0m_cachedBC.m_edVertexA =tru e;31}32m_cachedBC.setBarycentricCoordinates(1-t,t);33nearest = from + t*v;343 5m_cachedP1 = m_simplexPointsP[0] + t * (m_simpl exPointsP[1] - m_simplexPointsP[0]);3 6m_cachedP2 = m_simplexPointsQ[0] + t * (m_simpl exPointsQ[1] - m_simplexPointsQ[0]);37m_cachedV = m_cachedP1 - m_cachedP2;383 9reduceVertices(m_cachedBC.m_usedVertices); //移去没有用的顶点，对最近点没有贡献。

这个在求两个物体最近距离时候要用到，没用的点从单纯形中去掉41m_cachedValidClosest = m_cachedBC.isValid();42break;43}44两个顶点的单纯形就是求原点到线段的距离。

如图1所示，在a的情况下，返回t点，在b的情况下返回to点，在c的情况下返回from。

【bullet 代码，原来挺乱的】m_cachedBC.setBarycentricCoordinates(1-t,t)，设置最近点的重心坐标。

图1 原点到线段的距离3、三个顶点的单纯形求空间点到空间三角形最近距离（以及三角形上的最近距离点）的算法主要在函数closestPtPointTriangle中。

例如对于顶点a，如果原点位于它的Voronoi区域，则a点就是三角形到原点的最近距离。

代码如下：1 // Check if P in vertex region outside A2 btVector3 ab = b - a;3 btVector3 ac = c - a;4 btVector3 ap = p - a;5 btScalar d1 = ab.dot(ap);6 btScalar d2 = ac.dot(ap);7 if (d1 <= btScalar(0.0) && d2 <= btScalar(0.0))8 {9 result.m_closestPointOnSimplex = a;10 result.m_edVertexA =true;11 result.setBarycentricCoordinates(1,0,0);12 return true;// a; // barycentric coordinates (1,0,0)13 }接下来判断P是否在b点的Voronoi区域（代码省略），然后判断线段p是否在ab的Voronoi区域，代码如下:1 // Check if P in edge region of AB, if so return projection ofP onto AB2 btScalar vc = d1*d4 - d3*d2;3 //=(p-a).(((p-a)x(p-b))x(c-a)4 if (vc <= btScalar(0.0) && d1 >= btScalar(0.0) && d3 <= btScalar(0.0)) {5 btScalar v = d1 / (d1 - d3);6 result.m_closestPointOnSimplex = a + v * ab;7 result.m_edVertexA =true;8 result.m_edVertexB =true;9 result.setBarycentricCoordinates(1-v,v,0);10return true;11//return a + v * ab; // barycentric coordinates (1-v,v,0)12}注意：d1*d4-d3*d2 = (c-a).(((b-a)x(p-b))x(p-a)接下来是点c，线段ac，bc，代码类似，不再贴出来。

如果以上的测试都为false，则P 点位于三角形内。

4、四个顶点的单纯形主要通过函数closestPtPointTetrahedron计算最短距离。

在该函数中，考虑到了四面体退化的问题，就是四个点在一个平面上，此时没有求最短距离，否则的话，分别对四个平面求到原点最短距离，求出其中最短的距离即为结果。

因为代码比较长，这儿就不贴出来了。

/s/blog_61feffe10100mxnx.html。