计算几何，四面体有向体积

Question

我不确定这是否是询问的正确地方，但还是试一下…

简短版：我正在尝试在平面上计算三角形的方向，该三角形由3条边的交点组成，而不必显式计算交点。

详细版：我需要将PSLG三角剖分到3D中的一个三角形上。 PSLG的顶点由线段与通过三角形的平面的交点定义，并保证位于三角形内部。 假设我有交点，我可以投影到2D并使用点-线-侧（或三角形符号区域）测试来确定任意3个交点之间的三角形的方向。

问题在于，由于我的浮点误差在计算线-平面交点时会积累，所以我无法明确计算交点。为了弄清楚线段是否首先击中三角形，我使用了一些可自由使用的稳健几何谓词，它们给出了四面体的体积符号，或等效地给出了点在平面哪一侧。 我可以确定线段端点是否位于三角形通过的平面的相反侧面，然后在线段和三角形的每个边之间形成四面体，以确定交点是否位于三角形内。

由于我无法明确计算交点，我想知道是否有一种方法可以只使用原始点在3D中表达相同的2D方向计算。 如果有3条边击打三角形，那么总共可以使用9个点。 假设我正在询问的即使是可能的（仅使用3D方向测试），那么我猜测我需要在这9个点之间形成所有可能四面体的某些子集。 我甚至难以想象这一点，更不用说将其浓缩成公式或代码了。 我无法找到此类问题的行业标准术语，因此无法使用Google查找。

如何继续处理？ 谢谢。 也许我应该问问MathOverflow……

编辑：阅读了一些评论后，我想到一个事情…也许如果我可以将三条直线之间适合非重叠的四面体，那么任意穿过平面的其中一个的方向就是我要找的答案。 除非边界包围一个简单的三棱柱，否则我不确定此子问题是否可解决。

编辑：所请求的图像。

- mr grumpy

---

我会推荐使用MathOverflow。我并不是说这里没有人能够解决，只是你在那里可能会更快地得到答案（而且你也不必担心你的问题被关闭，因为它与编程无关）。 - bta

这些线段是否垂直于三角形？ - Daniel Brückner

我没有看到它。也许一个图表会有所帮助。 - Ignacio Vazquez-Abrams

@Ignacio Vazquez-Abrams：我的理解是——给你一个定义平面的三个点和三对点（每一对都在平面两侧），定义了三条线段。现在要确定这三条线段与平面相交的三个交点是否按(逆)时针顺序排列。 - Daniel Brückner

MO上的问题链接：http://mathoverflow.net/questions/31578 - BlueRaja - Danny Pflughoeft

Answer 1

我在MO和SO上都回答了这个问题，并扩展了我在MO上的评论。

我的感觉是，使用有符号四面体体积的计算技巧无法避免精度问题，而这是您关注的主要问题。这是因为，如果您有紧密扭曲的线段，则三角形的方向取决于切割平面的精确定位。
[图像已删除；请参见下文]
在上面的示例中，上平面以（a，b，c）[从上面逆时针]的顺序穿过线段：（红色，蓝色，绿色），而下平面则以相反的顺序（c，b，a）穿过：（绿色，蓝色，红色）。切割平面的高度可以由您的最后一位精度确定。

因此，我认为直接在切割平面中计算交点是有意义的，使用足够的精度使计算结果完全准确。如果您的线段端点坐标和平面系数具有L位精度，则只需要增加一些小的常数因子。虽然我不确定这个因子是多少，但它很小——也许是4。您不需要例如L²位，因为计算解决的是线性方程。因此，计算所需的精度不会爆炸。

祝你好运！

（由于我没有声望，所以无法发布澄清图像。请参见MO answer。）

编辑：请查看MO答案，但这里是图像：

- Joseph O'Rourke

---

非常感谢。我会从某个地方获取一个AP库并完成这个任务。 - mr grumpy

Answer 2

我们称三角形的顶点为T [0]，T [1]，T [2]，第一条线段的端点为L [0]和L [1]，第二条线段为L [2]和L [3]，第三条线段为L [4]和L [5]。我想你需要一个函数

int Orient(Pt3 T[3], Pt3 L[6]); // index L by L[2*i+j], i=0..2, j=0..1

如果交点与三角形具有相同的方向，则返回1，否则返回-1。 结果应该在交换j值、i值和T索引时对称。只要您可以计算具有这些对称性的量，那就足够了。

让我们试试

Sign(Product( Orient3D(T[i],T[i+1],L[2*i+0],L[2*i+1]) * -Orient3D(T[i],T[i+1],L[2*i+1],L[2*i+0]) ), i=0..2))

产品应该在指数的循环置换（模3）下进行。我相信这具有所需的所有对称性质。Orient3D是Shewchuk的4点平面定向测试，我假设您正在使用它。

- Victor Liu

---

谢谢，我会试一下这个。如果它下溢或者不起作用，那么我可能会像Joseph建议的那样使用一个任意精度库。 - mr grumpy

好的，你应该将Sign函数分配到每个Orient3D中以防止下溢。 - Victor Liu

抱歉如果我误解了，但每个orient3d看起来像是在三角形的边缘和线段之间形成一个四面体。第二个orient将线段反转，使得tet符号相反，然后negate又使其变回相同。假设所有线段的第一个顶点在平面上方，第二个顶点在下方，所有第一个orient都产生正号（对于所有边缘和线段），因为所有线/平面交点都在三角形内部。最终结果似乎总是+1。 - mr grumpy

是的，我看到问题了。当我发布它时，我对上面的代码的正确性有所怀疑，并且在放弃之前进行了大量编辑。我试图表达的观点是，如果您能想出具有正确对称性的数量，那么您就拥有了所需的一切。不确定这种方法是否会有成果，但只是一个想法。 - Victor Liu

Answer 3

我会编写符号向量方程，使用点积和叉积来找到交点三角形的法线。然后，这个法线与初始三角形的点积的符号给出了方向。最后，你可以将其表示为一个形式为 sign(F(p1,...,p9)) 的表达式，其中 p1 到 p9 是你的点，F() 是一个包含差值的点积和叉积的丑陋公式 (pi-pj)。不知道是否有更简单的方法，但这种通用方法可以完成任务。

- Roman L

---

我明白你的意思，我可以写出公式，但我认为这会让我面临一个更大的问题：如何确定符号。这是与我已经在使用的谓词相同的问题，它们稳健地找到行列式的符号。我很难理解它们是如何工作的，所以我不太乐观能够构建一个类似的新谓词。 - mr grumpy

如果答案有一个纯几何解释，那么我可以使用我已经拥有的预设谓词。 - mr grumpy

我同意，在计算公式F(p1，...，p9)时可能会出现一些数值问题。例如，如果A相对于b非常大，则（A-A）+ b == b但（A + b）-A == 0。然而，当您在数字之间存在巨大差异时（因为您需要低于10 ^ -16双精度），这些事情就会发挥作用。当然，使用现有的解决方法会更简单/更好，但是首先必须找到它。 - Roman L

Answer 4

据我理解，您有三条线相交于平面，并且想要计算由交点形成的三角形的方向，而不需要计算交点本身？

如果是这样：您有一个平面

N·(x - x0) = 0

和六个点...

l1a, l1b, l2a, l2b, l3a, l3b

...形成三条线

l1 = l1a + t(l1b - l1a)
l2 = l2a + u(l2b - l2a)
l3 = l3a + v(l3b - l3a)

这些线与平面的交点发生在特定的t、u、v值处，我将称之为t_i、u_i、v_i

N·(l1a + ti(l1b - l1a) - x0) = 0
N·(x0 - l1a)
ti =  ----------------
      N·(l1b - l1a)
（ui、vi同理）

然后交点的具体位置是

intersect1 = l1a + ti(l1b - l1a)
intersect2 = l2a + ui(l2b - l2a)
intersect3 = l3a + vi(l3b - l3a)

最后，您的三角形方向是

orientation = (intersect2 - intersect1)x(intersect3 - intersect1)的方向

(x表示叉积) 反向计算插入值，您将得到一个仅基于N、x₀和六个点的方向方程。

- BlueRaja - Danny Pflughoeft

---

谢谢回复。是的，我知道我可以符号性地写出它，或者数值计算它。问题在于如何在不违反精度问题的情况下完成它。重新发明我上面提到的谓词是等价的工作，这超出了我的能力范围。理想情况下，我正在寻找一些几何解释答案的方法，以便我可以重用我已经拥有的谓词。 - mr grumpy