4.18 使用逐三角形检查检测射线-模型碰撞

问题

你想检测一根3D射线是否与模型发生碰撞，如果你想进行一个最高细节的碰撞检测这是必须的，可以作为教程4-11的拓展进行子弹是否与物体发生碰撞的高细节碰撞。如下一个教程所示，这可以用来检测鼠标是否在模型上。

而且，这个方法也可以用来进行模型之间的最高精度的检测，这是因为对应一条射线的每一个三角形的边缘可以用来进行与另一个模型的碰撞检测。

这个教程会处理最复杂的情况，允许模型的不同部分独立地被转换，使这个教程可以适用于模型动画，这些变换作用在模型顶点的最终位置上。例如，如果一个人移动手臂，手臂顶点的最终位置会发生移动。这个教程会考虑到这个变换。

解决方案

这个教程使用教程4-13和4-14中的自定义素材管道的混合，因为在模型的每个ModelMesh的Tag属性中储存了三角形对象的数组，每个三角形对象存储了三个Vector3定义一个三角形。

让每个ModelMesh都存储各自Triangle对象数组的好处是让你可以使用ModelMesh 的Bone矩阵对它们进行转换。无论当前作用在ModelMesh 上的变换是什么，你总能通过使用ModelMesh的绝对变换矩阵找到Triangle对象在3D空间中的绝对位置（见教程3-9和4-17)。这是必须的，因为大多数情况下3D Ray是定义在绝对3D空间中的，所以你需要知道顶点的绝对3D位置。

知道了每个模型三角形的绝对3D位置后，剩下的问题就是对模型每个三角形进行射线-三角形碰撞检测了。

工作原理

因为内容管道使用了教程4-15中的自定义类(Triangle)，最简单的方法是将这个内容管道项目添加到项目中。你可以右击解决方案并选择Add Existing Project，找到内容管道的. Csproj文件并选择它。

下一步是让XNA项目能够访问到这个内容管道项目，可参加教程3-9的步骤1–5。最后两步是让XNA反串行化Triangle对象，这在教程4-15中已经解释过了。

6. 将新创建的引用添加到项目中。

7. 选择新创建的处理器处理模型。

8. 设置项目依赖项。

9. 在XNA项目中，添加内容管道的引用。

10. 添加内容管道命名空间。

别忘了第7步，选择ModelMeshTriangleProcessor处理你导入的模型。

这个处理器将Triangle对象的数组储存在模型的ModelMesh的Tag属性中。

变换

现在你可以处理所有的模型顶点位置，你可以定义一个方法检测射线－模型间的碰撞：

private bool ModelRayCollision(Model model, Matrix modelWorld, Ray ray) 
{ 
    Matrix[] modelTransforms = new Matrix[model.Bones.Count]; 
    model.CopyAbsoluteBoneTransformsTo(modelTransforms); 
    
    bool collision = false; 
    foreach (ModelMesh mesh in model.Meshes) 
    {
        Matrix absTransform = modelTransforms[mesh.ParentBone.Index] *modelWorld; 
        Triangle[] meshTriangles = (Triangle[])mesh.Tag; 
        
        foreach (Triangle tri in meshTriangles) 
        {
            Vector3 transP0 = Vector3.Transform(tri.P0, absTransform); 
            Vector3 transP1 = Vector3.Transform(tri.P1, absTransform);
            Vector3 transP2 = Vector3.Transform(tri.P2, absTransform);
            
            // if (Ray-Triangle collision) 
                // return true; 
        }
    }
    return collision; 
}

思路很简单：你首先将collision设置为false。对模型的每个部分，你遍历所有三角形对象，包含三角形位置。对每个三角形，你检查三角形是否和ray碰撞，如果发生碰撞则返回true。

存储在Triangle对象中的位置是相对于ModelMesh的初始位置的，这意味你要首先通过ModelMesh的绝对变换矩阵进行变换获得相对于模型的位置，然后使用模型的世界矩阵获取在3D空间中的位置(换句话说，绝对位置)。

第一个变换看似多余，但事实上它有很大的好处：如果你想旋转模型的一个ModelMesh (例如，人的手臂)，这个旋转也会被考虑进去。通过绝对变换矩阵变换了手臂的顶点位置后，你就获得了相对应模型初始位置的位置并考虑了旋转！

在前面的代码中，你首先计算了模型所有Bone的绝对变换矩阵。接下来，将绝对矩阵和世界矩阵组合起来，使用最终的结果矩阵将ModelMesh中的每个三角形变换到绝对3D空间。

最后，你获得了ModelMesh中的每个三角形的确切3D空间位置，可以施加想要的任何动画了。

Ray-Triangle碰撞

有了每个三角形的绝对位置，你将检测三角形和射线之间的碰撞。

这个过程可以分为两部分。首先找到射线与三角形平面的碰撞点。因为三角形和这个相交点是在同一个平面上，所以问题就转化为了一个2D问题，如图4-25所示。接下来，你要检查碰撞点是否在三角形的内部。

图4-25 将3D问题（左图）简化为2D问题(右图)

你将编写两个方法处理问题。第一个方法，RayPlaneIntersection，接受一个Plane和一个Ray为参数并返回射线上的碰撞点的距离。由这个方法可以计算射线和三角形之间的相交点。

第二个方法，PointInsideTriangle，接受三角形的三个坐标和一个额外点（在本教程的情况中即相交点，返回点是否在三角形的内部。

如果在内部，你就检测到了射线和模型的碰撞了。下面的代码要替换掉前面的两行伪代码（译者注：即// if (Ray-Triangle collision) //return true;）：

Plane trianglePlane = new Plane(transP0, transP1, transP2); 
float distanceOnRay = RayPlaneIntersection(ray, trianglePlane); 
Vector3 intersectionPoint = ray.Position + distanceOnRay * ray.Direction; 

if (PointInsideTriangle(transP0, transP1, transP2, intersectionPoint)) 
    return true;

首先基于三角形的三个顶点创建一个三角形plane。将这个plane和Ray传递到 RayPlaneIntersection方法，获取射线上相交点的位置，这可以用来计算相交点的位置。最后检查相交点是否在三角形内部。

注意：更多Ray对象的使用方法可参加教程4-11和4-19。

获取Ray和Plane之间的碰撞点

你很幸运，第一个方法主要是代数运算。我选择了一个基于矢量的方法让你可以形象地看到这个过程，如图4-26所示。

图4-26 找到射线上的碰撞点的位置

给定一条Ray和一个Plane，这个方法可以找到ray.Direction和collisionPoint两点间的距离，注意这个方法中的变量的所有长度在图中显示在左右两侧。

private float RayPlaneIntersection(Ray ray, Plane plane) 
{
    float rayPointDist = -plane.DotNormal(ray.Position); 
    float rayPointToPlaneDist = rayPointDist - plane.D; 
    float directionProjectedLength = Vector3.Dot(plane.Normal, ray.Direction); 
    float factor = rayPointToPlaneDist / directionProjectedLength; 
    return factor; 
}

首先找到rayPointDist，它是射线投影长度，位于平面法线上(垂直于屏幕的线段)。变量plane. D定义为初始点 (0,0,0)离开平面的最短距离，即沿着平面法线的距离。

有了这两个沿着法线的距离，你可以通过将两者相减找到ray. Position和平面间的距离(即rayPointToPlaneDist)。

这个离开射线的最短距离，从ray. Position指向平面并垂直于平面，即仍是沿着平面法线方向。现在决定射线方向沿平面法线的距离，换句话说，如果你从ray. Position出发发射一条射线，它离开平面有多远？

你可以通过将ray. Direction投影到平面法线上获取这个长度，这可以使用两者的点积。这个长度在图4-26右边显示。

知道了ray. Direction偏离平面的程度和ray. Position偏离平面的距离，你就可以计算需要在ray. Position上乘以ray. Direction的多少倍！这个因子由方法返回用来找到射线和平面相交点的确切位置。首先定义Ray的出发点(=ray. Position)，并通过这个因子添加Ray方向上，你就获得了碰撞点。这一步在ModelRayCollision方法中实现：

Vector3 intersectionPoint = ray.Position + distanceOnRay * ray.Direction;

检查碰撞点是否在三角形内部

知道了射线在哪儿与三角形平面相交后，你要检查相交点是否在三角形内部。否则，射线和三角形并没有真正相交。

这又一次可以使用一个基于向量的方法。图4-27展示了基本原理。如果你还记得碰撞点位于与三角形相同的平面的内部，这个图不是很复杂。

图4-27 检查碰撞点是否在三角形内部

在图4-27的左边，碰撞点在三角形的外部。首先考虑三角形上的T0,T1边界。你想知道collisionPoint 在边界的哪一面上。看一下图4-27左边到矢量A = (collisionPoint – T0) 和B = (T1-T0)。如果你从A旋转到B，将是逆时针方向。

但是在图4-27的右边，collisionPoint在三角形内部，即在T0,T1边界的另一边，当从A旋转到B将是顺时针方向！

显然你可以通过这个方法检查collisionPoint在边界的那一边。你可以使用A和B的叉乘， A × B，返回一个向量，当逆时针旋转时这个向量指向平面的外部。如果顺时针旋转，如图4-27右边所示，这个向量指向下方。

下面的代码计算A和B向量和它们的叉乘：

Vector3 A = point - p0; 
Vector3 B = p1 - p0; 
Vector3 cross = Vector3.Cross(A, B);

让我们再进一步：如果collisionPoint在三角形边界的同一侧说明它在三角形的内部，换句话说，如果三个叉乘矢量同一方向则collisionPoint在三角形的内部。

所以为了检测点是否在三角形的内部，你要计算三角形每个边界的叉乘矢量。当这些矢量的分量的符号相同说明它们指向相同的方向。下面是代码：

private bool PointInsideTriangle(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 point)
{
    if (float.IsNaN(point.X)) 
        return false; 
    
    Vector3 A0 = point - p0;
    Vector3 B0 = p1 - p0; 
    Vector3 cross0 = Vector3.Cross(A0, B0); 
    
    Vector3 A1 = point - p1; 
    Vector3 B1 = p2 - p1; 
    Vector3 cross1 = Vector3.Cross(A1, B1); 
    
    Vector3 A2 = point - p2;
    Vector3 B2 = p0 - p2; 
    Vector3 cross2 = Vector3.Cross(A2, B2);
    
    if (CompareSigns(cross0, cross1) && CompareSigns(cross0, cross2))
        return true; 
    else
        return false; 
}

上述方法以三角形的三个顶点和collisionPoint位置为参数。如果射线与平面平行，找不到collisionPoint，则point的每个分量都会是NaN(NaN即Not a Number)。如果发生这种情况，方法立即返回，对于一个平行的射线，三角形永远不会和它相交。

如果不平行，这个方法继续运行。对于三角形的每一边，你计算叉乘。如果所有的叉乘矢量都指向相同的方向(这意味着分量的符号是相同的),那么collisionPoint就在三角形的内部！

CompareSigns方法接受两个Vector3参数。它检测两个X分量，Y分量，Z分量是否符号相同。简而言之，这个方法检查这个方向的夹角是否小于90度。下面是代码：

private bool CompareSigns(Vector3 first, Vector3 second) 
{
    if (Vector3.Dot(first, second) > 0) 
        return true; 
    else 
        return false; 
}

你只是简单地计算两个矢量的点积，将一个矢量投影到另一个矢量上，结果是一个 single类型，如果两个向量夹角大于90度结果为负，垂直时为0，小于90度为正。

性能优化

对于模型的每个三角形都有调用这个检测，所以，让它进行得尽可能快是很重要的。下面，你会学习几个性能优化的建议。

转换射线而不是位置

在ModelMesh中，你使用绝对变换矩阵转换了每个位置，将这些位置转换到绝对3D空间中，这样才可以和Ray比较，因为它同样定义在绝对3D空间中。

更好的做法是将射线转换到ModelMesh的坐标空间中，因为这样做只需对每个 ModelMesh操作一次。这样Ray和三角形位置都在相同的坐标空间中，它们也可以进行比较。

使用以下代码替换ModelRayCollision方法：

private bool ModelRayCollision(Model model, Matrix modelWorld, Ray ray) 
{
    Matrix[] modelTransforms = new Matrix[model.Bones.Count]; 
    model.CopyAbsoluteBoneTransformsTo(modelTransforms); 
    
    bool collision = false; 
    foreach (ModelMesh mesh in model.Meshes) 
    {
        Matrix absTransform = modelTransforms[mesh.ParentBone.Index] * modelWorld; 
        Triangle[] meshTriangles = (Triangle[])mesh.Tag; 
        
        Matrix invMatrix = Matrix.Invert(absTransform); 
        Vector3 transRayStartPoint = Vector3.Transform(ray.Position, invMatrix); 
        Vector3 origRayEndPoint = ray.Position + ray.Direction; 
        Vector3 transRayEndPoint = Vector3.Transform(origRayEndPoint, invMatrix); 
        Ray invRay = new Ray(transRayStartPoint, transRayEndPoint - transRayStartPoint); 
        
        foreach (Triangle tri in meshTriangles) 
        {
            Plane trianglePlane = new Plane(tri.P0, tri.P1, tri.P2); 
            float distanceOnRay = RayPlaneIntersection(invRay, trianglePlane);
            Vector3 intersectionPoint = invRay.Position + distanceOnRay * invRay.Direction; 
            
            if (PointInsideTriangle(tri.P0, tri.P1, tri.P2, intersectionPoint)) 
                return true; 
        }
    }
    return collision; 
}

你将Ray从绝对3D空间转换到ModelMesh空间而不是将三角形位置转换到绝对3D空间，这是absTransform 变换的反变换，所以你要取逆矩阵。然后，你获取射线的两个点，将它们使用逆矩阵进行变换，并创建一个新的射线。有了在ModelMesh空间中的射线，就可以将这些与未经变换的顶点位置做比较了，因为此时它们在相同的坐标空间！

这样，对每个ModelMesh你只需进行两次变换，而不是对每个三角形进行三次变换！

首先进行一个包围球检测

相对于对射线和所有三角形进行碰撞检测，更好的做法是进行射线和ModelMesh的包围球之间的碰撞检测，如果这个简单快速的检查返回false，那就没必要检查每个三角形了！

如果这个检测返回true，在转到繁重的逐三角形检测之前，更好的方法是检测射线和更小的ModelMesh的包围球之间的碰撞。或者可以做得更好，检测所有ModelMeshPart包围球之间的碰撞（在模型的一个ModelMesh有多个ModelMeshPart的情况下）。

如你所见，一个模型可以分成几个ModelMesh，因为你拥有了更多（也更精确）的包围球，导致更少的三角形检测，所以让更精确的动画和加速碰撞检测成为可能。

代码

这是检测射线和模型间碰撞的最终方法：

private bool ModelRayCollision(Model model, Matrix modelWorld, Ray ray)
{
    Matrix[] modelTransforms = new Matrix[model.Bones.Count]; 
    model.CopyAbsoluteBoneTransformsTo(modelTransforms); 
    
    bool collision = false; 
    foreach (ModelMesh mesh in model.Meshes) 
    {
        Matrix absTransform = modelTransforms[mesh.ParentBone.Index] * modelWorld;
         Triangle[] meshTriangles = (Triangle[])mesh.Tag; 
         
         foreach (Triangle tri in meshTriangles) 
         {
             Vector3 transP0 = Vector3.Transform(tri.P0, absTransform); 
             Vector3 transP1 = Vector3.Transform(tri.P1, absTransform); 
             Vector3 transP2 = Vector3.Transform(tri.P2, absTransform); 
             
             Plane trianglePlane = new Plane(transP0, transP1, transP2);
             float distanceOnRay = RayPlaneIntersection(ray, trianglePlane); 
             Vector3 intersectionPoint = ray.Position + distanceOnRay * ray.Direction; 
             
             if (PointInsideTriangle(transP0,transP1, transP2, intersectionPoint)) 
                 return true; 
        }
    }
    return collision; 
}

这个方法调用RayPlaneIntersection方法，返回一个平面和一条射线之间的碰撞点的位置：

private float RayPlaneIntersection(Ray ray, Plane plane) 
{
    float rayPointDist = -plane.DotNormal(ray.Position); 
    float rayPointToPlaneDist = rayPointDist - plane.D; 
    float directionProjectedLength = Vector3.Dot(plane.Normal, ray.Direction); 
    float factor = rayPointToPlaneDist / directionProjectedLength; 
    
    return factor; 
}

PointInsideTriangle方法用来检测碰撞点是否在三角形的内部：

private bool PointInsideTriangle(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 point)
{
    if (float.IsNaN(point.X)) 
        return false; 
    
    Vector3 A0 = point - p0; 
    Vector3 B0 = p1 - p0; 
    Vector3 cross0 = Vector3.Cross(A0, B0); 
    
    Vector3 A1 = point - p1; 
    Vector3 B1 = p2 - p1;
    Vector3 cross1 = Vector3.Cross(A1, B1);
    
    Vector3 A2 = point - p2; 
    Vector3 B2 = p0 - p2; 
    Vector3 cross2 = Vector3.Cross(A2, B2); 
    
    if (CompareSigns(cross0, cross1) && CompareSigns(cross0, cross2)) 
        return true; 
    else 
        return false;
}

这个方法检测碰撞点是否在三角形的同一侧，这可以通过检测叉乘矢量是否同一方向实现，这个检测是在CompareSigns方法中实现的：

private bool CompareSigns(Vector3 first, Vector3 second) 
{
    if (Vector3.Dot(first, second) > 0)
        return true;
    else 
        return false; 
}

发布时间：2009/9/7 下午4:34:02 阅读次数：7530