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

Question

给定：一个由一组顶点和三角形定义的 3D 网格，这些点构成了网格。

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

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

Answer 1

• 从最右边的点开始（x坐标最大的点）
• 从此点获取所有边
• 沿着与正 x 轴角度最小的边，并将其添加到解决方案集中
• 从到达的点开始，跟随并将具有最小角度的边缘添加到您来自的边缘
• 重复直到到达原点

Answer 2

我只看到凸解决方案的答案，所以这是我的非凸解决方案。（意图是什么有点令人困惑。）

从二维三角形中取出所有边并将它们分组。如果两条边共享两个端点，则它们在同一个组中。所有只有一条边的组都是壳的一部分。

最后，您可以将壳边缘组合成一个环，方法是将它们连接在一起。

Answer 3

补充一点：在投影中查找边缘的一种非常直观的方法是背面剔除！剔除和非剔除面之间的任何边缘都应该是轮廓。如果要隐藏内部边缘，只需使用 z 缓冲区。背面剔除只是投影后的顶点顺序，计算起来非常便宜。

Answer 4

这个问题中提到的 alpha 形状技术处理一组顶点连接未知的通用点：

是否有生成二维凹壳的有效算法？

但是，由于您已经知道可以通过投影保留的“面部”信息，因此这可能不是最好的方法。

蛮力算法可能是可行的，尤其是在使用空间排序结构的情况下。例如对于每个方面：

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

另一个想法，取决于您需要的保真度，只是从您的投影平面射出一束法线光线到您的原始几何体。创建一个 2d hit/miss 并使用它来确定您的范围。

Answer 5

网格投影的 2D 轮廓是其边缘投影的子集。

使用这一观察，可以使用以下方法确定 2D 轮廓：

• 仅属于一个面的每条边的投影是 2D 轮廓的一部分，
• 对于其他边，确定其相邻面的法向量
• 计算这些法线与投影平面法线的点积
• 如果点积的所有符号都不相同，则该边缘的投影属于 2D 轮廓（这意味着，一个面指向投影平面而至少另一个面不指向投影平面，这将边缘标识为大纲）。

请注意，此方法将报告与投影平面正交的所有边缘，即使是从投影平面的角度看不到的边缘。例如，对于圆环，它会找到内部和外部轮廓，即使圆环以这样一种方式旋转，以至于从投影平面的角度看不到它的内部孔。要确定哪些边缘是可见的，您将需要某种可见性测试。如果预期用途是用于用户显示，则可以使用使用正交投影矩阵计算的深度缓冲区从投影平面的视点渲染几何图形，并进行一些 z 测试以确定哪些边缘从平面可见。如果您需要精度，则需要执行射线/三角形相交以确定可见性。

Answer 6

1. 找到 x 为 min 的点
2. 找到该点的所有边
3. 从这一点开始，想象你有一根棍子（绿色），它顺时针滚动以找到它遇到的第一个边缘。让我们称之为边缘-A。 边缘-A
4. 寻找该边 A 中的交叉点。找到导致交叉点的边-B，我们称之为inter-A，这个inter-A是你的第二个轮廓点。 边缘-B
5. 那么我们想一想，在edge-B的两点之间，谁是下一个轮廓点。链接inter-A和起点我们可以“滚动棒”找到下一个轮廓点。（候选点 1 是一个） 在此处输入图像描述
6. 重复上述步骤，直到找到集合中已经存在的点。

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