首页 文章

计算几何，四面体符号体积

提问于
浏览 次
6

我不确定这是否是正确的地方，但是这里......

Short version: 我正在尝试计算平面上三角形的方向，由三条边的交点形成，而不显式计算交点 .

Long version: 我需要在3D三角形上对三角形上的PSLG进行三角测量 . PSLG的顶点由线段与穿过三角形的平面的交点定义，并保证位于三角形内 . 假设我有交点，我可以投影到2D并使用点线侧（或三角形有符号区域）测试来确定任意3个交叉点之间的三角形的方向 .

问题是我无法明确计算交点，因为当我找到线平面交点时累积的浮点误差 . 为了弄清楚线段是否在第一个位置撞击三角形，我使用了一些可自由使用的强大几何谓词，它给出了四面体体积的符号，或等效于点所在平面的哪一侧 . 我可以确定线段 endpoints 是否位于通过三角形的平面的相对侧，然后在线段和三角形的每个边之间形成四面体以确定交叉点是否位于三角形内 .

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

任何想法如何处理这个？谢谢 . 也许我应该问MathOverflow ......

编辑：在阅读了一些评论之后，我发生了一件事......也许如果我能在3个线段之间拟合非重叠的四面体，那么任何一个穿越平面的方向将是答案我我正在寻找 . 除了边缘包围一个简单的三角形棱镜之外，我不确定这个子问题是否也可以解决 .

编辑：请求的图像 .
alt text

math geometry

4 回答

  • 1

    让我们调用你的三角形顶点 T[0] ， T[1] ， T[2] ，第一个线段的 endpoints 是 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 's 4-point plane orientation test, which I assume you'重新使用 .

    回复于
  • 1

    据我所知，你有三条与平面相交的线，你想计算交点形成的三角形的方向，而不计算交点本身？

    如果是这样的话：你有一架飞机

    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值，我称之为ti，ui，vi

    N·(l1a + ti(l1b - l1a) - x0) = 0

      N·(x0 - l1a)
ti =  ----------------
      N·(l1b - l1a)
(similarly for ui, vi)

    然后具体的交点是

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

    最后，你的三角形的方向是

    orientation = direction of (intersect2 - intersect1)x(intersect3 - intersect1)

    （x是交叉积）向后插入值，你将得到一个仅基于N，x0和你的六点的方向方程 .

    回复于
  • 1

    我在MO＆SO上回答这个问题，扩大了我对MO的评论 .

    我的感觉是，没有带有签名四面体体积的计算技巧可以避免主要关注的精度问题 . 这是因为，如果您有紧密扭曲的线段，三角形的方向取决于切割平面的精确定位 .
    [图片已删除;见下文]
    在上面的例子中，上平面按顺序（a，b，c）[从上面的ccw] :(红色，蓝色，绿色）穿过片段，而下平面以相反的顺序交叉（c，b，a ）:(绿色，蓝色，红色） . 切割平面的高度可以由您的最后一点精度确定 .

    因此，我认为继续计算切割平面中的交点是有意义的，使用足够的精度来使计算精确 . 如果你的段 endpoints 坐标和平面系数有L位精度，那么只有一小部分需要增加恒定因子 . 虽然我不确定该因素究竟是什么，但它很小 - 可能是4.你不需要例如L2位，因为计算是求解线性方程 . 因此，精确计算所需的精度不会出现爆炸性增长 .

    祝好运！

    （由于我没有声誉，我被禁止发布澄清图片 . 请参阅MO answer . ）

    Edit ：看到MO答案，但这里是图片：

    Image

    回复于
  • 6

    我会用点和交叉积来编写符号向量方程，以找到交叉三角形的法线 . 然后，该法线的点积与初始三角形的符号给出方向 . 所以最后你可以在一个表格符号（F（p1，...，p9））中表达这一点，其中p1到p9是你的点，而F（）是一个丑陋的公式，包括差异的点和叉积（pi-pj） . 不知道这是否可以更简单，但这种一般方法可以完成这项工作 .

    回复于

相关问题