5.10 计算光标与地形的碰撞点：表面拾取

问题

你想获取地形上由光标指示的位置的精确3D坐标。

解决方案

如教程4-19的介绍中讨论的那样，通过光标指示的屏幕上的一个2D点对应3D场景中的一条射线。在本教程中，我们将沿着这条射线直到它与地形发生碰撞。

你可以使用一个二分法搜索（binary search algorithm）做到这点，这可以根据你选择的精度获取碰撞位置。

对高低起伏的地形来说，可能在射线和地形之间有多个碰撞点，如图5－20所示。所以，在二分法搜索之前需要进行线性搜索，以保证检测到的碰撞是最靠近相机的。

工作原理

下面的这个方法将光标的2D屏幕位置转换为一个3D射线，这已经在教程4－19的第一部分介绍过了。

private Ray GetPointerRay(Vector2 pointerPosition) 
{
    Vector3 nearScreenPoint = new Vector3(pointerPosition.X, pointerPosition.Y, 0); 
    Vector3 farScreenPoint = new Vector3(pointerPosition.X, pointerPosition.Y, 1); 
    
    Vector3 near3DWorldPoint = device.Viewport.Unproject(nearScreenPoint, moveCam.ProjectionMatrix, moveCam.ViewMatrix, Matrix.Identity); 
    Vector3 far3DWorldPoint = device.Viewport.Unproject(farScreenPoint, moveCam.ProjectionMatrix, moveCam.ViewMatrix, Matrix.Identity); 
    
    Vector3 pointerRayDirection = far3DWorldPoint - near3DWorldPoint; 
    Ray pointerRay = new Ray(near3DWorldPoint, pointerRayDirection); 
    
    return pointerRay; 
}

注意：本教程中你没有归一化射线的方向，我等会儿会解释这个问题。

二分法搜索

射线包含一个起点(本例中就是射线与近裁平面的交点)和方向。射线和地形如图5-19所示。起点用A表示。射线的方向为A和B之间的向量。二分法搜索的思路很直观、首先从A、B两点开始，你应确保碰撞点位于这两点之间。计算出A、B的中点，在图5-19中用1表示。你检查这个点在地形之上还是之下。如果这个点在地形的上方(比如本图中的情景)，那你就知道了碰撞点位于1和B之间。

图5－19

图5-19 使用二分法搜索检测射线和地形的碰撞

然后继续找到1和B之间的点2，这个点位于地形之下，所以你知道碰撞点位于1和2之间。

继续缩小搜索范围。看一下位于1和2之间的点3，这个点在地形之上，所以碰撞点位于3和2之间。

接着，3和2之间的点4在地形之下，所以碰撞点在3和4之间。

最后，检查位于3和4之间的点5。你发现点5的高度非常接近地形上(X,Z)位置的高度，所以你找了碰撞点！

找到点A和点B

在开始二分法搜索之前，你需要从射线上的两个点A、B开始，必须确保碰撞点位于两点之间。

你可以安全地使用射线的起点作为A点，因为这是射线上最接近与相机的点(它位于近裁平面上，可见教程4-19)。

现在，可以取射线与远裁平面的交点作为B点，这个主意不错，因为这是相机内可见的射线上的最远点。

如教程4-19的GetPointerRay方法中解释的那样，pointerRay. Direction等于从A指向B的向量。

二分法搜索方法

现在知道了点A和指向B的方向，就可以检测与地形的碰撞了二分法搜索算法前面已经解释过了，翻译成伪代码如下：

只要当前点和在其之下的地形间的高度差过大，就执行以下操作：

  1. 将射线方向一分为二。
  2. 将结果方向添加到当前点获取下一个点。
  3. 如果下一个点仍在地形上方，将这个点作为当前点。

可以把这个步骤想象成在射线上行走，在放脚之前，你要检查脚是否位于地形下方。如果不是，则将步幅缩小一半继续。一但脚位于地形上方，你要及时撤回脚将它向下移动一半，直到脚位于地形之上与地形接触。

下面是代码： 

private Vector3 BinarySearch(Ray ray) 
{
    float accuracy = 0.01f; 
    
    float heightAtStartingPoint = terrain.GetExactHeightAt(ray.Position.X, -ray.Position.Z); 
    float currentError = ray.Position.Y - heightAtStartingPoint; 
    
    while (currentError > accuracy) 
    {
        ray.Direction /= 2.0f; 
        Vector3 nextPoint = ray.Position + ray.Direction; 
        float heightAtNextPoint = terrain.GetExactHeightAt(nextPoint.X, -nextPoint.Z); 
        
        if (nextPoint.Y > heightAtNextPoint) 
        {
            ray.Position = nextPoint; 
            currentError = ray.Position.Y - heightAtNextPoint; 
        }
    }
    return ray.Position; 
}

首先计算射线上的开始点与地形的高度差。

当这个高度差小于你预设的0.01的accuracy才跳出while循环。如果高度差仍太大，你要将步幅减半并计算射线上的下一个点。如果下一个点在地形之上，你要计算这个点的高度差。如果下一个点位于地形之上，则不作任何操作，这样下一次循环步幅再次减半。

跳出while循环后，ray. Position将会包含射线上与地形的高度差小于0.01的点的位置。

这个方法需要首先有GetPointerRay 方法创建的AB射线：

pointerPos = BinarySearch(pointerRay);

注意：如果你的光标不在地形上，这个方法会永远停留在while循环中。 那么，如果计数器大于某个值就跳出while循环就很有用了，这会在后面的代码中讲到。

二分法搜索的问题

大多数情况中，二分法搜索做得很好，但在某些情况中会失败，如图5-20所示。

图5－20

图5-20 二分法搜索会出问题的情况

因为二分法搜索不会检测点0和1之间的地形高度，导致射线与第一个山头的碰撞不会被检测到，会返回同样的结果（点5）作为射线和地形间的碰撞。

要解决这个问题，在二分法搜素之前应进行线性搜索，线性搜素相对来说比较简单。

线性搜索

在线性搜索中，你需要将射线分割成相同长度的几部分，例如，分成8段，如图5-21所示。

图5－21

图5-21 线性搜索

你只是简单地以相同的步幅沿着射线前进，直到碰到一个位于地形下方的点。这不会给出一个精确的结果，但至少你检测到了射线与第一个山头的碰撞。

因为图5-21中的点1和点2都没有足够接近地形，所以需要使用二分法搜索找到点1和2之间的精确碰撞点。

LinearSearch方法以AB间的射线为参数，将这根射线分成相同的线段，返回对应哪段发生碰撞的一部分射线：

private Ray LinearSearch(Ray ray) 
{
    ray.Direction /= 300.0f; 
    
    Vector3 nextPoint = ray.Position + ray.Direction; 
    float heightAtNextPoint = terrain.GetExactHeightAt(nextPoint.X, -nextPoint.Z); 
    
    while (heightAtNextPoint < nextPoint.Y) 
    {
        ray.Position = nextPoint; 
        nextPoint = ray.Position + ray.Direction; 
        heightAtNextPoint = terrain.GetExactHeightAt(nextPoint.X, -nextPoint.Z); 
    }
    return ray; 
}

本例中，射线被分成不超过300段。增加这个值会增加检测到的可能性但需要更多处理能力。

对每个点，你计算了下一点并检测下一个点在地形之上还是之下。如果在地形之上，则继续。如果下一个点在地形之下，返回包含碰撞前的点和碰撞发生段信息的当前射线。

返回的这条射线用在了BinarySearch方法中： 

Ray shorterRay = LinearSearch(pointerRay); 
pointerPos = BinarySearch(shorterRay);

指定程序的优化

线性搜索让你可以检测到小的山峰，而接下来的二分法搜索精度更高。

在前面的代码中，你取射线与近裁平面和远裁平面的交点作为A点和B点。这工作良好，但是如果近裁平面和远裁平面间的距离很大，射线也会很大。这意味着你要进行很多无用的检查。

作为替代，你只需考虑可能发生碰撞的高度范围内的射线。在本书中用到的地形最大高度为30，最低为0。因此，更好的做法是在射线上找到Y坐标为30的点并将它作为起始点A。然后找到将射线上Y坐标为0的点作为终点B点。

这根射线由下面的方法构建：

private Ray ClipRay(Ray ray, float highest, float lowest) 
{
    Vector3 oldStartPoint = ray.Position; 
    float factorH = -(oldStartPoint.Y-highest) / ray.Direction.Y; 
    Vector3 pointA = oldStartPoint + factorH * ray.Direction; 
    float factorL = -(oldStartPoint.Y-lowest) / ray.Direction.Y;     
    Vector3 pointB = oldStartPoint + factorL * ray.Direction; 
    Vector3 newDirection = pointB - pointA; 
    
    return new Ray(pointA, newDirection); 
}

要找到射线上指定Y坐标的点，需要找到这个Y坐标和射线起始点的Y坐标之差。如果知道射线方向上的高度差，你就知道了需要将射线的哪一部分（存储在factor中）添加到起始点上以到达你要求的Y值的点。

注意：oldStartPoint的Y坐标是正的，当射线下降时direction的Y坐标是负的。你想让factor为一个正值，所以前面有个 – 号。

如果从输出的射线开始，在线性搜索中你只需进行少得多的检测就可以达到同样的检测率。

代码

你可以使用下面的代码检测光标射线与地形的碰撞点： 

protected override void Update(GameTime gameTime) 
{
    GamePadState gamePadState = GamePad.GetState(PlayerIndex.One); 
    
    if (gamePadState.Buttons.Back == ButtonState.Pressed) 
        this.Exit(); 
    
    MouseState mouseState = Mouse.GetState(); 
    KeyboardState keyState = Keyboard.GetState(); 
    
    Vector2 pointerScreenPos = new Vector2(mouseState.X, mouseState.Y); 
    Ray pointerRay = GetPointerRay(pointerScreenPos); 
    Ray clippedRay = ClipRay(pointerRay, 30, 0); 
    Ray shorterRay = LinearSearch(clippedRay); 
    pointerPos = BinarySearch(shorterRay); 
    
    base.Update(gameTime); 
}

这个代码首先调用ClipRay方法返回Y坐标为0到30之间的一段射线： 

private Ray ClipRay(Ray ray, float highest, float lowest) 
{
    Vector3 oldStartPoint = ray.Position; 
    float factorH = -(oldStartPoint.Y-highest) / ray.Direction.Y; 
    Vector3 pointA = oldStartPoint + factorH * ray.Direction; 
    float factorL = -(oldStartPoint.Y-lowest) / ray.Direction.Y; 
    Vector3 pointB = oldStartPoint + factorL * ray.Direction; 
    Vector3 newDirection = pointB - pointA; 
    
    return new Ray(pointA, newDirection); 
}

然后调用LinearSearch方法将一条很长的射线优化为一个短射线，这个射线包含最接近相机的碰撞点： 

private Ray LinearSearch(Ray ray) 
{
    ray.Direction /= 50.0f; 
    Vector3 nextPoint = ray.Position + ray.Direction; 
    float heightAtNextPoint = terrain.GetExactHeightAt(nextPoint.X, -nextPoint.Z); 
    
    while (heightAtNextPoint < nextPoint.Y) 
    {
        ray.Position = nextPoint; 
        nextPoint = ray.Position + ray.Direction; 
        heightAtNextPoint = terrain.GetExactHeightAt(nextPoint.X, -nextPoint.Z); 
    }
    
    return ray; 
}

要精确找到碰撞的3D位置，要在这条短射线上调用BinarySearch方法： 

private Vector3 BinarySearch(Ray ray) 
{
    float accuracy = 0.01f; 
    
    float heightAtStartingPoint = terrain.GetExactHeightAt(ray.Position.X,-ray.Position.Z); 
    float currentError = ray.Position.Y - heightAtStartingPoint; 
    
    int counter = 0; 
    while (currentError > accuracy) 
    {
        ray.Direction /= 2.0f; 
        Vector3 nextPoint = ray.Position + ray.Direction; 
        float heightAtNextPoint = terrain.GetExactHeightAt(nextPoint.X, -nextPoint.Z); 
        
        if (nextPoint.Y > heightAtNextPoint) 
        {
            ray.Position = nextPoint; 
            currentError = ray.Position.Y - heightAtNextPoint; 
        }
        
        if (counter++ == 1000) 
            break; 
    }
    return ray.Position; 
}

注意：如果while循环进行了1,000次，代码会跳出这个循环。

发布时间：2009/9/16 11:08:17  阅读次数：6287

2006 - 2024，推荐分辨率1024*768以上，推荐浏览器Chrome、Edge等现代浏览器，截止2021年12月5日的访问次数：1872万9823。 站长邮箱

沪ICP备18037240号-1，

沪公网安备 31011002002865号