给定三维空间中的一组曲面,我尝试将每个曲面分配给一个区域,该区域引用该组所包围的最小 3D 区域,或者如果不适用则不指定任何区域。我还想确定一个表面是否是两个区域之间的界面。因此,例如,如果我们有 11 个表面,代表两个堆叠在一起的立方体,则顶部立方体中的表面将位于同一区域,而底部表面将位于不同区域(界面表面为在两个区域)。
举个例子,我想采用一组表面,例如this http://imgur.com/I6OsCax并将其转换为this https://i.stack.imgur.com/cJzG8.jpg。这里的每种颜色代表一个区域,灰色表示没有关联的区域(如底部的翻盖所示)。
我做了一些搜索,试图找到是否有人已经想出了一种算法来做到这一点,但我还没有找到任何东西(大多数似乎识别区域而不是将表面链接到它们所包围的区域)。因此,我正在尝试提出自己的算法,并且想知道是否还有其他替代方案或者我的方法是否可行。
我假设所有表面都是相连的。
我的想法如下:
- 选择一个随机表面,其各边恰好接触另一个表面,并将其添加到区域 1。
- 将每个连接的表面添加到区域 1,前提是其每一侧恰好接触另一个表面。
- 对于那些至少一侧接触多个表面的连接表面,将其添加到“可能”列表中。
- 对于区域 1 中的每个新表面,重复步骤 2-3。
- 一旦某个表面被添加到“可能”列表两次,请将其添加到区域 1 并从“可能”列表中删除。将此表面标记为区域界面。
- 将区域接口添加到区域 2。
- 从“可能”列表中选择一个随机表面并将其分配给区域 2,并清除“可能”列表。
- 重复步骤 2-7(当然更新区域编号),直到没有未分配的表面。
这似乎适用于简单的场景(例如,两个立方体堆叠在一起),但我不确定是否需要注意任何棘手的条件,或者一旦有两个以上的区域,它是否会分崩离析共同的一面。
对我的粗略算法/替代实现想法的任何改进将不胜感激。谢谢!
编辑:以下是针对一些评论的更多详细信息。
根据我的定义,区域只是一组完全包围 3D 区域、没有间隙的表面。因此,如果我有两个不接触的立方体 A 和 B,我将有两个区域:一个由立方体 A 的所有表面组成,另一个由立方体 B 的所有表面组成。如果我有一个缺失的立方体一侧,不会有与这些表面相关的区域。
我的最终目标是在我正在创建的建模工具中创建一个自动化的曲面分组过程。具体细节是分类的,但本质上我正在处理的模型中,某些属性仅在如上所述的同一“区域”中的表面之间是常见的。我想创建一个创建这些区域的自动化过程,以便用户可以立即将这些属性应用到区域中的所有表面,而不是手动执行。
本质上,问题归结为找到被任意一组表面完全包围的最小 3D 区域,并跟踪哪些表面属于哪些区域。我希望这能让我的问题更清楚。
那么,您感兴趣的是从一组输入多边形中发现闭合表面(体积)网格拓扑;换句话说 - 多面体。这对于几乎所有 3D 建模包来说都很常见。我猜想 Blender 有可以做到这一点的代码。有不同的方法可以做到这一点,但通常使用某种版本的半边图。请参阅此处的维基链接:双链半边图 https://en.wikipedia.org/wiki/Doubly_connected_edge_list。这个想法是遍历您的输入策略并构建这些图表。完成后,您可以轻松查询每个图表以查看是否存在漏洞(边缘缺失等)。
我附上一张图片,解释如何使用半边结构来获得你想要的东西:假设你有一个由五个矩形组成的汤(它们组成一个没有顶部的立方体。U处理你的第一个矩形,比如ABCD,这会创建你的第一个图,比如说 G1。现在你处理第二个多边形,比如说 FEHG,你还没有见过这些顶点,所以你创建第二个图,G2。现在假设你处理多边形 CDGH。你以前已经见过这些顶点,所以而不是创建一个新的图形,您合并(连接)共享这些节点的现有图形。继续,直到处理完所有多边形。您将得到图片中的图形。
现在,查询图表以获取您的信息。一旦您浏览该图,您将看到恰好有四个顶点(节点)缺少边。这些顶点对应于盒子缺失的顶部(图中边缘为红色)。因此您知道该图不是闭合流形。如果您有另一个盒子,它不与这个盒子共享节点,那么您将得到另一张图。因此,一旦您处理完多边形,每个图形都是您的一个“区域”。
请注意,如果您有两个相交的形状,您也可以使用这些图表来跟踪它们,但它要复杂得多。基本上,在处理新的多边形时,您不仅要查看其任何顶点是否属于已处理的图形,还要查看此多边形是否与任何先前处理的多边形相交,如果是,则分割此多边形并将所有这些添加到相交图。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)