投影3D网格的2D轮廓算法

Question

已知：用一组顶点和三角形构建的3D网格。

问题：找出在任意平面上投影的任意旋转网格的2D轮廓。

投影很容易。挑战在于在平面上找到投影的三角形边缘的“外壳”。我需要一些关于研究此算法的输入/指针的帮助。为简单起见，我们可以假设3D边缘被垂直投影到xy平面上。

- ralphtheninja

---

这里蓝色的线看起来不是凸出的。 - Svante

是的，你说得对。我很快就从一个网站上偷了那张图片，并在上面画了一些红线来说明。我仍然希望这个想法能够传达出来 :) - ralphtheninja

@MagnusSkog：我需要完全做到这一点。最终哪种方法最适合你？ - PeteUK

@PeteUK 通过选择例如最东边的节点，测量角度并选择最接近的节点，它运行得非常好。一个警告：在角度上要小心浮点精度！我记得我曾经遇到过这个问题，算法在网格中走了错误的路径。 - ralphtheninja

@MagnusSkog 感谢你的回复和关于FP问题的警告。现在我对这个更有信心了 :) - PeteUK

Answer 1

• 从最右侧的点开始（即具有最大 x 坐标的点）
• 获取该点的所有边
• 沿着与正 x 轴形成的最小角度的边进行操作，同时将其添加到解集中
• 从到达的点继续沿着并添加与从其来的边形成的最小角度的边
• 重复以上步骤，直到返回原始点

- Svante

---

如果将一个圆环体投影到x-y平面上会发生什么？ 这样做无法呈现内部的“孔洞”。 - nsanders

如果有两条边都等于最小角度，会怎样？ - Richard Inglis

嗯...选取两者中较短的一个。 - Richard Inglis

不，只能在一个方向上测量角度，例如逆时针方向。 - Svante

感谢@Svante提供的好解决方案。您能否建议如何适用于其他投影方向？ - flatronka

这个解决方案仅适用于2D。如何获得2D输入完全独立。您可以将任何平面映射到xy平面。 - Svante

Answer 2

补充一下：在投影中找到边缘的一种直观方式是背面剔除！任何一个被剔除和未被剔除的面之间的边缘都应该是轮廓线。如果您想隐藏内部边缘，只需使用z-buffer。背面剔除仅涉及后期投影的顶点顺序，并且计算成本非常低廉。

- starmole

Answer 3

网格投影的二维轮廓是其边缘投影的子集。

基于这个观察，可以使用以下方法确定二维轮廓：

• 属于一个面的每条边的投影都是二维轮廓的一部分，
• 对于其他边，确定其相邻面的法线向量
• 计算这些法线与投影平面法线的点积
• 如果所有点积的符号不同（即一个面朝着投影平面，而至少有另一个面没有朝着投影平面），则该边的投影属于二维轮廓。

请注意，此方法将报告垂直于投影平面的所有边缘，甚至包括那些从投影平面的视角看不到的边缘。例如，在使用环面时，它将找到内部和外部轮廓，即使环面以使其内部孔不可见的方式旋转。要解决哪些边缘是可见的问题，您需要进行一些可见性测试。如果用于用户显示，则可以使用正交投影矩阵计算的深度缓冲区来渲染投影平面的几何形状，并进行一些z测试以确定哪些边缘从该平面可见。如果需要精度，则需要执行射线/三角形相交以确定可见性。

- Sebastien Pellizzari

---

我建议在投影后进行方向测试。我想起来为什么预投影不起作用了，但是无法想出一个好的数学原因。很可能是当我转换法线时弄错了。 - starmole

Answer 4

这个问题中提到的 alpha shapes 技术处理了一组一般点，其中顶点连接未知： Is there an efficient algorithm to generate a 2D concave hull? 然而，由于你已经知道“面”的信息，可以通过投影保留它，这可能不是最好的方法。

暴力算法可能是可行的，特别是如果使用了空间排序结构。例如，对于每个面：

1. 将面投影到平面上
2. 检查投影面是否完全被现有几何图形包围，如果是：完成（无需扩展投影轮廓）
3. 如果点落在现有几何图形之外，则进行三角形交叉以确定哪些部分落在外部，构建一个任意的 n 边形（可能是凹多边形）来填充缺失的空间，然后将 n 边形切成三角形

另一个想法，取决于所需的保真度，就是从投影平面垂直地向原始几何图形射出一堆光线。创建一个 2D 命中/未命中，并使用它来确定您的范围。

- nsanders

Answer 5

我只看到了凸解的答案，所以这里提供一个非凸解的答案。（不太清楚意图是什么。）

将2D三角形中的所有边分组。如果两条边共享两个端点，则它们属于同一组。所有只有一条边的组都是外壳的一部分。

最后，您可以通过将这些外壳边缘连接在一起来将其组合成一个环。

- LaZe

---

对于一个封闭（水密）的3D网格，所有边缘都被两个三角形共享，因此它们的2D投影边缘也将有两个相邻的三角形。然而，如果你丢弃所有法线方向与你要投影到的平面法线相反的三角形，那么你剩下的部分可以用于所描述的算法。 - Dov Grobgeld

Answer 6

1. 找到x坐标最小的点
2. 找到该点的所有边
3. 从这个点开始，想象你有一根棍子（绿色），它顺时针滚动以找到它遇到的第一条边。让我们称之为边A。edge-A
4. 在边A中寻找交点。找到导致交点的边B，让我们称之为inter-A，这个inter-A是你的第二个轮廓点。edge-B
5. 然后考虑，在边B的两个点之间，谁是下一个轮廓点。连接inter-A和起点，我们可以“滚动棍子”以找到下一个轮廓点。（候选点1是其中之一）enter image description here
6. 重复以上步骤，直到找到已经存在于你的集合中的点。

查看找到兔子轮廓的演示 这是上述算法的实现。

- tt h