选择由某个顶点子集包围的网格的所有面

Question

我很确定这是一个常见问题，但无论我如何改写，我都无法在互联网上找到任何答案。

我正在为用户制作一个用户界面，通过 select 多个顶点 select 网格内的一个区域。
更准确地说，给定一个三角形网格和一组顶点（它是网格顶点的子集），我想得到所有被顶点子集包围的面。

我查阅了一些算法，例如多边形中的点、Dijkstra 算法等，但它们似乎没有帮助。
非常感谢。

Answer 1

首先，您需要在表示轮廓的网格上嵌入一条闭合多段线。一旦你有了这个轮廓，你就可以填充它的内部以获得相应的面。

轮廓线

有多种获取轮廓线的方法。一种方法是使用像 A* 这样的路径查找算法来查找选择集中两个连续顶点之间的最短路径（即 (v0 -> v1), (v1 -> v2) ... (vn -> v0)）。这将为您提供一条多段线，表示为网格的有向边。

根据用户选择的表现，您可能需要稍微清理一下轮廓。例如，如果轮廓包含一条在两个方向上都经过的边（例如 v1 -> v2 -> v3 -> v2 -> v4 -> ...），您可以只删除这对边。如果您有自交集，则需要进行类似的清理。

填充内部

一旦有了有向轮廓线，就可以通过 breadth-first 遍历来填充其内部。这个想法是从轮廓边缘开始，然后迭代添加入射面。基本算法可以概述如下：

Input:
    E: directed edges of the contour

O <- empty list of faces to examine
V <- empty list of visited faces    

// Initialization
for every e in E:
    calculate the face left of e (-> f)
    add f to O
    add f to V

// Do BFS
while O is not empty:
    take the first element out of O (-> f)
    for all faces g adjacent to f and not in V:
        add g to O
        add g to V

完成此步骤后，所选面孔将在 V 中。然而，有一个关键部分：

calculate the face left of e

首先，left of和right of的概念应该从网格本身就清楚了。面的顶点通常按 counter-clockwise 或顺时针顺序（面缠绕顺序）排序。因此，每个 non-boundary 边 {v1, v2} 都存在于两个面中：一次是 (v1 -> v2)，一次是 (v2 -> v1)。根据缠绕顺序，您可以选择包含正确方向边的面。然后，如果您知道轮廓的缠绕顺序，这就是您需要做的全部。 IE。如果你的轮廓总是顺时针方向并且你的网格面总是顺时针顺序，你就完成了。

如果轮廓可以在任何一个方向上，事情就会变得有点复杂。然后，不清楚用户想要标记的部分（考虑轮廓为赤道的球体）。有两个简单的选项：

使用较小的区域
让用户在目标区域内选择一个点并使用该点。

对于这两个选项，您需要从轮廓的两个方向进行 BFS（准确地说，它们是两个独立的 BFS）。出于性能原因，最好同时执行这两项操作。然后，只要区域中的任何一个用完 O 中的开放面（选项 1，该区域将是较小的）或遇到附加点（选项 2，仅为此继续 BFS），您就可以中止地区）。

为了有效地执行此 BFS，您需要一种将边映射到其相应面的方法 and/or 网格上的邻域数据结构。如果你想使用后者，你可能要考虑半边数据结构

选择由某个顶点子集包围的网格的所有面

Selecting all faces of a mesh surrounded by some vertex subset

3d

geometry

mesh

connected-components

轮廓线

填充内部