7

我正面临与三角形边缘相交的问题。实际上，我正在尝试使用鼠标选择/相交网格的三角形、顶点、边缘。所以我从鼠标当前位置制作了射线，然后我将它与三角形/多边形、顶点、边缘等网格元素相交以使用它。基本上，3D建模的东西。与三角形相交既简单又有趣。顶点部分很棘手。

但是现在，我不知道如何与三角形边缘相交/拾取。我的意思是当与鼠标射线相交时我如何对待它们？首先，我认为可以将它们视为 3D 线。但最终未能做到 Ray 和 Line 相交。在互联网上搜索但没有找到任何有用的信息。虽然我发现一些开源项目正在使用 OpenGL 内置的拾取功能来拾取/与 Edge 相交。但就我而言，我不能使用它。:(

我当前的边缘拾取代码结构如下所示：

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?
            }
        }
    }
}

所以我被困在这里，真的需要一些帮助。非常感谢任何想法、算法或小帮助。

4

4 回答 4

1

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

于 2016-08-08T06:47:23.787 回答
1

在您的情况下，在 3D 空间中找到三角形和射线之间的交点的问题可以归结为在 2D 空间（平面）中的三角形中找到点位置（内部、外部、边界上）。您应该做的就是在屏幕平面上投影三角形，在边缘找到交点并在边缘执行反向投影。点的位置是鼠标的位置。唯一的问题是处理退化的情况，例如将三角形映射到线段。但我认为这不会有问题，因为这样的情况很容易应付。

于 2016-08-15T07:41:40.773 回答
1

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

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

然后你计算你的射线（它的基点）到这个平面的投影，这将简单地产生一个 2d point rp。

然后通过简单地应用点积将边缘投影到该平面： pv1 = new Vector2(DotProduct(v1, rdir1), DotProduct(v1, rdir2)) pv2 = new Vector2(DotProduct(v2, rdir1), DotProduct(v2, rdir2))

现在您可以计算从这条二维线pv1, pv2到点的距离rp。

假设边缘的方向取自视图矩阵的“前向”方向，则与之正交的两个向量将是视图矩阵的左向量和右向量。

执行上述配方将产生类似于将边缘投影到屏幕上的效果。因此，或者您可以将边缘投影到屏幕上并使用这些坐标。

于 2016-09-02T15:22:00.433 回答
0

首先，两个几何对象 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，这大大简化了问题。

在您的问题中，对象是 line segmentA := {v1 + t*(v2-v1) | 0 <= t <= 1}和 line 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的倍数的部分之和。对于这样的“正交分解”，它总是成立。dv = Ov + MvSquareEuclideanLength(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)and给出的，但相信我，如果不标准化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)).

您已经从点线距离计算中知道了这个公式（就是这样），它是通过对t0 进行微分来解决的。

所以这个方程的最小值是 t = -Dot(Cross(v1 - p, d), Cross(v2 - v1, d))/SquareEuclideanLength(Cross(v2 - v1, d))

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

我希望这可以帮助你 ！

于 2016-09-06T13:18:37.810 回答