遍历 3D 三角形

计算科学 线性代数 delaunay三角剖分
2021-12-07 16:55:21

给定一个由 R3 空间 {p1, p2, p3} 中的三个点形成的三角形平面,我想通过使用两个变量 x0,y0 来遍历三角形平面上的所有点,如下例所示:http://demonstrations .wolfram.com/DirectionalDerivativesIn3D/该网站中的示例使用方向导数。

如果这是在 2D 中,通过使用 2 个 for 循环(每个用于 x 和 y 轴)并循环通过由该三角形形成的矩形边界框,很容易遍历三角形。然后我可以使用重心坐标来隔离落在三角形内的点。

但是,对于 3D 空间,我不知道该怎么做。任何帮助或想法将不胜感激。

4个回答

为什么不将坐标转换为三角形平面并在那里进行迭代呢?

如果您使用重心坐标,则嵌入三角形的维数无关紧要;从重心坐标到欧几里得坐标的转换只是三角形顶点处欧几里得点的凸组合。

要迭代三角形点,您可以遵循以下算法:

  • 找到最长边并将其用作内循环的方向,以下假设最长边为(p1,p2),第三点为p3

  • 对于内部循环,总是沿方向 D 迭代:(p1->p2)

  • 从点 A=p1 开始以给定的步长 L 沿着这条线迭代,直到到达 B=p2。

  • 通过更新 A=p1 + (p3-p1)*L13 和 B=p2+(p3-p2)*L23 移动到点 p3 的方向。L13、L23 是根据 p3 到线 (p1,p2) 的距离拾取的第二维的步长计算的。获得正确的公式应该是微不足道的。

  • 使用相同的方向向量 D 重复从 A 到 B 的迭代

  • 继续直到所有的三角形都被覆盖。

可以在此处找到一些实现此功能的 C++ 代码,查找draw_triangle,但请注意,该代码还会检查线的点是否在给定的边界框内,并且您可以将draw_point替换为您想要在三角形上运行的任何操作观点。

(由于我是此 GPL 代码的作者,我特此授权自由使用在 3D 空间中填充三角形的部分作为自己实现的蓝图)。

您可以计算平面的法线(通过叉积)并沿相反方向旋转平面。这将使 &z& 坐标相同。然后您可以通过简单地忽略 &z& 将平面投影到 2D 笛卡尔坐标系上。然而,您仍然拥有 3D 中的每个三角形坐标与 2D 中的坐标的直接映射(对应关系)。您可以在 2D 网格中迭代并始终​​映射到 3D。