根据它们所包含的三维区域将曲面分配给区域

Question

在三维空间中给定一组曲面，我试图将每个曲面分配给一个区域，该区域指的是最小的3D区域，如果这是不适用的，则没有区域。我还想确定曲面是否是两个区域之间的接口。因此，例如，如果我们有11个表面，代表两个立方体堆叠在一起，在顶部立方体的表面将在同一区域，而在底部的表面将在一个不同的区域(在两个区域的界面表面)。

举个例子，我想要接受一组曲面，比如这，并将它提交给这。这里的每一种颜色都代表一个区域，灰色是没有关联的区域(如底部的襟翼)。

我已经做了一些搜索，试图找出某人是否已经想出了一个算法来完成这个任务，但是我什么也没有找到(大多数看起来都是识别区域，而不是将曲面链接到他们所包围的区域)。因此，我试图想出自己的算法，并想知道是否还有其他替代方案，或者我的方法是否有效。

我假设所有的表面都是相连的。

我的想法如下：

1. 选择一个随机曲面，其两侧各与另一个表面完全接触，并将其添加到区域1中。
2. 将每个连接的表面添加到第1区，条件是它的每一方都完全接触到另一个表面。
3. 对于那些在其至少一侧接触多个表面的连通曲面，将其添加到“可能”列表中。
4. 对于区域1中的每个新表面，重复步骤2-3。
5. 一旦一个曲面被两次添加到“可能”列表中，将其添加到区域1并从“可能”列表中删除。将此表面标记为区域接口。
6. 将区域接口添加到区域2。
7. 从“可能”列表中选择一个随机曲面，并将其分配给区域2，并清除“可能”列表。
8. 重复步骤2-7 (当然是更新区域号)，直到没有未分配的曲面为止。

这似乎适用于简单的场景(例如，两个多维数据集相互叠在一起)，但我不确定是否有任何棘手的条件需要注意，或者，如果有两个以上的区域共享一个边，它是否会崩溃。

对我的粗略算法/替代的实现思路的任何改进都将不胜感激。谢谢!

编辑:以下是回应一些评论的更多细节。根据我的定义，一个区域只是一组曲面，它完全绑定了一个没有空隙的三维区域。所以，如果我有两个立方体，A和B，不接触的话，我会有两个区域，一个由立方体A的所有表面组成，另一个是立方体B的所有表面。如果我有一个立方体，它的一侧没有，就不会有与这些曲面相关联的区域。

我的最终目标是在我正在创建的建模工具中创建一个对曲面进行分组的自动化过程。细节是分类的，但本质上我处理的模型中，某些属性只有在相同的“区域”的表面之间是共同的，如上文所述。我想要建立一个自动的过程，创建这些区域，以便用户可以一次将这些属性应用到区域中的所有表面，而不是手动执行。

本质上，问题归结为找到被任意一组曲面完全包围的最小三维区域，并跟踪哪些曲面属于哪个区域。我希望这使我的问题更加明确。

Answer 1

那么，您感兴趣的是从一组输入多边形中发现封闭的曲面(体积)网格拓扑；换句话说--多边形。这对于几乎每个3d建模包来说都是很常见的。我猜Blender有这样的代码。有不同的方法来做到这一点，然而，通常，一些版本的半边图被使用。请参阅这里的wiki链接：双连通半边图。其想法是遍历您的输入策略，并构建这些图表。一旦完成，您可以很容易地查询每个图，看看是否有漏洞(边缘缺失，等等)。

​

​

我附上了一张图片，解释了如何使用半边结构来得到你想要的东西:假设你得到了一个五个矩形的汤(它们构成一个没有顶部的立方体)。你处理你的第一个矩形，比如说ABCD，这就创建了你的第一个图形，比如G1。现在你处理第二个多边形，比如说FEHG，你还没有看到这些顶点，所以你创建了第二个图，G2。现在假设您处理多边形CDGH。您以前见过这些顶点，所以不是创建一个新的图，而是合并(连接)共享这些节点的现有图。继续，直到你处理所有多边形。你可以在图片中得到图表。

现在，查询图表以获取您的信息。一旦您遍历该图，您将看到正好有四个顶点(节点)是缺少边的。这些箭头对应于盒的缺失顶部(插图中的边缘是红色的)。因此，你知道这个图不是一个闭流形。如果您有另一个没有与此共享节点的框，则会有另一个图。因此，每一个图形，一旦你完成你的多边形处理，是一个“区域”对你。

注意，如果你有两个相交的形状，你也可以用这些图形来追踪，但它要复杂得多。基本上，当处理一个新的多边形时，你不仅要看它的任何一个顶点是否属于已经处理过的图形，而且还要看看这个多边形是否与以前处理过的多边形相交，如果是这样的话，将这个多边形分开并将所有这些添加到相交的图形中。