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  阅读次数:6284

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

沪ICP备18037240号-1

沪公网安备 31011002002865号