将非方向图转换为网格

阿达里奥

声明:

我正在创建一个程序,该程序可以让用户布置自己的非方向图(节点和边)。一旦他们按下特定的按钮,我想从图中的每个“间隙”中创建一个三角网格。这是两张图片,应该让您大致了解我的追求:

图形 填充图

有一些警告:

  • 由于用户可以完全控制,所以我可以得到3、4、5 ... n个侧面空间
  • 用户可以创建凸形或凹形
  • 该应用程序是使用C#在Unity中制作的

到目前为止,我自己的尝试效率很低,并且在非常不寻常的图形布局中可能会失败。我的总体计划是抓住一个节点并沿一个周期跟随最锐角,直到我回到第一个节点。这部分起作用,但是我无法知道是否获得了所有空间。另外,我可以得到两个覆盖相同空间的相同网格(尽管节点顺序不同)。

我会很感激您能为我提供的这款树桩帮助。为了帮助解决问题,我已经熟悉凸包算法和三角剖分。

更新:

我无法发布任何代码,因为我处于该项目的NDA之下,但是数据结构非常简单。

节点具有位置(向量3,但y始终为0)和连接边的列表。

边具有第一节点,第二节点和位置(中点)。

我想为每个间隙生成一个Mesh对象。该网格对象具有一个静态的顶点数组(向量3s)和一个静态的三角形数组(三角形,它们是整数,并且与顶点索引有关)。

之前

您的方法是一种好方法。有几点需要改进。

让我们假设图是平面的(如果不是很难定义一个面的话),并且不存在一个度数为1的顶点。具有一阶的顶点不是问题,但是如果没有它们,则描述解决方案会更容易:-)

请注意,每个边将在两个面上。因此,如果您以最大锐角跟随面部,而不是仅在一侧跟随这些边缘。解决方案是创建具有相同节点的有向图,并为每个边沿两个方向创建两个边。一般而言,与初始图相同的图,但边缘加倍。算法是:

take one (directed) edge
follow it in same way by smallest angle
make faces of that cycle
remove face (directed) edges from graph
repeat procedure until there are edges.

同样的方法适用于顶点为一度的图,但是面将具有“切口”(边在一个方向上比在相反方向上)。

如果您不想要外表面,则不要“加倍”外边缘,而应仅使每个外边缘的一个正方向边缘。

更新资料

由于每个多边形和多边形边缘仅传递一次,因此我认为这是一个非常理想的解决方案。只是很少的可能性。

算法的主要步骤是从上次访问的节点中选择下一条边。简单的实现是计算边缘的角度并取下一个角度。角度计算只能执行一次,而不是每次边缘访问节点时都可以进行,甚至可以为节点完成边缘映射->边缘映射。

不需要创建新的有向图,它足以存储每个边的方向数据。两个布尔变量就足够了,每个方向一个。第一步,选择未访问的边开始新的多边形,将变得更加复杂。如果使用较高角度的计算,可以通过从地图中移除访问角度并将节点标记为可见(如果地图中没有更多角度)来解决。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章