如何进行射线和三角形边缘的相交检测？

Question

我遇到了射线与三角形边相交的问题。实际上，我正在尝试使用鼠标选择/相交网格的三角形、顶点、边等元素。因此，我从鼠标当前位置生成射线，然后将其与网格元素（如三角形/多边形、顶点、边等）相交，以便对其进行处理。基本上是3D建模的东西。与三角形相交很容易和有趣。而顶点部分则有些棘手。

但现在，我不知道如何与三角形边相交/选择。我的意思是当与鼠标射线相交时，如何处理它们？起初我认为它们可以像3D线一样处理。但最终未能做到射线和线相交。在互联网上搜索，但没有找到任何有用的信息。虽然我发现一些开源项目正在使用OpenGL内置的拾取功能来选择/相交边缘。但在我的情况下，我不能使用那个。:(

我的当前边缘选择代码结构如下:

void pickEdge(Ray ray, Scene scene)
{
    for each object in scene
    {
        mesh = getMesh(object)
        for each triangle in mesh
        {
            for each edge in triangle
            {
                v1 = getV1(edge)
                v2 = getV2(edge)

                // Do intersect with 'ray' and 'v1', 'v2'. But how?
            }
        }
    }
}

我现在卡住了，真的需要一些帮助。任何想法、算法或小帮助都非常感激。

- Farhad Reza

---

使用距离线公式确定您的拾取点是否在可接受的“半径”范围内，然后进行垂直投影到边缘以产生必要的边缘上的“点”。 - Brett Hale

@Brett Hale，你说“使用距离线公式”。实际上，我在这一点上卡住了。事实上，我还不能实现射线与直线的相交。如果您能发布更详细的答案，那将非常有帮助。感谢您宝贵的评论 :) - Farhad Reza

啊...其实我还是卡住了:( 需要帮忙...拜托了。 - Farhad Reza

Answer 1

在您的情况下，在三维空间中查找三角形和射线之间的交点问题可以简化为在二维空间（平面）中查找三角形中点位置（内部、外部、边界上）。您需要做的就是将三角形投影到屏幕平面上，在边缘上找到交点，并对边缘进行反向投影。点的位置是鼠标的位置。唯一的问题是处理像将三角形映射到线段这样的退化情况。但我认为这不会是问题，因为这种情况很容易处理。

- Alex Aparin

Answer 2

请查看本页末尾和更一般的所有算法，以及该网站提供的所有算法：http://geomalgorithms.com/a05-_intersect-1.html

- abenci

---

哇！那些算法真的非常有用。我必须看看能否明智地使用它们来解决我的问题...谢谢。 - Farhad Reza

Answer 3

第一个方法是将边缘（和光线）正交投影到垂直于光线的平面上，然后计算投影光线到投影边缘的距离。

即，首先确定两个与光线正交的向量rdir1，rdir2。

然后计算光线（其基点）在此平面上的投影，这将简单地产生一个2d点rp。

然后通过简单地应用点积来将边缘投影到该平面上： pv1 = new Vector2(DotProduct(v1, rdir1), DotProduct(v1, rdir2)) pv2 = new Vector2(DotProduct(v2, rdir1), DotProduct(v2, rdir2)) 现在，您可以计算从此2D线pv1，pv2到点rp的距离。

只要从视图矩阵的“前向”方向中获取边缘的方向，那么与之正交的两个向量将是视图矩阵的左右向量。

执行上述步骤将产生类似于将边缘投影到屏幕上的结果。因此，您可以将边缘投影到屏幕上并使用那些坐标来处理。

- VlltStiller

---

哦...我以为我的问题可以通过简单的三维(xyz)数学来解决。但现在看来事情不会那么容易。实际上，我很少理解正交投影，将某些东西投影到...平面...等等。确实，在这些情况下，精通数学是最重要的。而我自己总是卡在这个点上:(... 你明白我的意思吗？无论如何，感谢您提供更好的答案。让我看看能否解决我的问题。哦..我现在没有多少时间了。但还是谢谢！ - Farhad Reza

你好，Mohammad。不要被长篇回复吓到了，其实很简单。确实有一种使用叉积的方法，但答案已经够长了。如果你感兴趣，我可以补充一下那个方法。 - VlltStiller

当然。事实上，我非常乐意从您那里获取更多信息。敬礼。 - Farhad Reza

Answer 4

首先，两个几何对象 A 和 B 之间的距离是什么？它是 A 和 B 上任意两点之间的最小距离，即 dist(A,B) = min { EuclideanLength(x - y) | x in A, y in B}。（如果存在且唯一，则在您的情况下确实存在。）

这里的 EuclideanLength((x,y,z)) = sqrt(x^2 + y^2 + z^2)，正如您已经知道的那样。因为 sqrt 是严格递增的，所以最小化 SquareEuclideanLength((x,y,z)) = x^2 + y^2 + z^2 就足够了，这大大简化了问题。

在您的问题中，对象是线段 A := {v1 + t*(v2-v1) | 0 <= t <= 1} 和一条直线 B := {p + s*d | s is any real number}。（不用担心您问的是射线，直线才是您想要的。）

现在计算距离就是要找到适当的t和s，使得SquareEuclideanLength(v1 + t*(v2-v1) - p - s*d)最小，然后计算EuclideanLength(v1 + t*(v2-v1) - p - s*d)以获得实际距离。

为了解决这个问题，我们需要一些解析几何知识。因为d不为零，我们可以将每个向量v写成与d正交的部分和d的倍数之和的形式：v = Ov + Mv。对于这样的“正交分解”，它总是满足SquareEuclideanLength(v) = SquareEuclideanLength(Ov) + SquareEuclideanLength(Mv)。

由于上述中有d = Md

SquareEuclideanLength(v1 + t*(v2-v1) - p - s*d) = SquareEuclideanLength(Ov1 + t*(Ov2-Ov1) - Op) + SquareEuclideanLength(Mv1 + t*(Mv2-Mv1) - Mp - s*d)

左边的被加数不取决于s，而你无论如何选择t，都可以找到一个s使右边的被加数为0！（记住，Mv1、Mv2等都是d的倍数。）

因此，要找到最小值，你只需要找到这样的映射O、M，并找到极小化器t。

假设d已经被标准化，则它们实际上由Ov := CrossProduct(v, d)和Mv := DotProduct(v, d)*d给出，但请相信我，如果d没有被标准化，这也是有效的。

现在找到距离的方法是：找到0 <= t <= 1，使其最小化

SquareEuclideanLength(Cross(v1 - p, d) + t*Cross(v2 - v1, d)) = SquareEuclideanLength(Cross(v1 - p, d)) + 2*t*Dot(Cross(v1 - p, d), Cross(v2 - v1, d)) + t^2 SquareEuclideanLength(Cross(v2 - v1, d))。

您可能已经从点线距离计算中了解到这个公式（就是它），通过对t求导并将其等于0来解决。

因此，这个方程的最小化器是 t = -Dot(Cross(v1 - p, d), Cross(v2 - v1, d))/SquareEuclideanLength(Cross(v2 - v1, d))

使用这个t，您可以计算出线段A上距离线B最近的点v1 + t*(v2 - v1)，然后将其插入到您的点线距离算法中以找到所需的距离。

希望这能帮助您！

- VlltStiller

---

非常感谢您提供的所有信息！最好的祝福 :) - Farhad Reza