如何在单位立方体世界中进行面部移除？

Question

重要提示:这个问题不是关于几何剔除(截头剔除,背面剔除,遮挡剔除或任何朋友).这个问题是关于在设置时消除几何,早在我们进行剔除和渲染之前.

在一个单位立方体渲染的世界(一个 MineCraft)中,我试图找到如何从我的几何面列表中删除无法从任何角度看到的几何面的算法,无论相机在哪里.

例如,想象2个方块:

+----+      +----+
|    |      |    |
|    |      |    |
+----+      +----+

显然有8个可见的边(每个方格4个.)现在我将方块移动到一起,相对于:

+----+----+
|         |
|         |
+----+----+

而不是有8个方面,现在我只有6个!无论相机放置在何处,也无法看到它所面对的角度,无法看到中间触摸的两个.(方块的纹理不同,所以我们不能称它为4边.)

(同样的东西在3D中使用立方体,但是12个面(每个立方体6个)变为10个,因为2个触摸被消除了.)

我的问题是:有哪些算法可以帮助我识别这些隐藏的面孔？(我很高兴自己做谷歌搜索,但我甚至不知道这叫什么!)特别是,我正在寻找能够处理中间点的空洞点的东西,如果你是但是,因为它们被几何体包围,你无法看到它们.

例如:

+----+----+----+----+
|                   |
|                   |
+    +----+         +
|    |    |         |
|    | A  |         |
+    +----+         +
|                   |
|                   |
+----+----+----+----+

在这种情况下,人们可能认为有18个"可见"的边,但是,因为我们知道相机在几何体之外的事实,所以方形"A"中的4个边是不可见的.

为了使事情进一步复杂化,我希望找到一种算法,如果添加或删除一个块,可以快速更新(再次,一个 MineCraft.)

谢谢!

Answer 1

问题的第一部分非常简单.对于每个多维数据集,如果它与另一个多维数据集直接相邻,则删除它与该多维数据集共享的面.

这不应该是一个性能问题(在修改和上传更改的顶点数据的成本之外),因为您只会在放置或删除块时重新计算它.放置和移除块的效果非常局部; 它只会影响6个相邻的立方体本身,所以它应该不是问题.除了处理基于多维数据集的环境所需的明显数据结构之外,您也不需要任何专门的数据结构.

建造地形的初始成本可能是某种程度,但这是您可以忍受的一次性成本.将其纳入您的加载时间.如果你在一个框架的空间中进行了大量的放置和删除,那么这可能是一个问题.

更难的问题是去除密封的内部.我的建议:这不值得.通过尝试移除密封的内部,放置或移除块变为非本地操作.通过花时间优化批次计数(尽可能使用纹理图集/数组)和顶点数据,您可能会获得更高的性能.

要移除密封的内部,您需要能够检测内部.因此,您需要维护相邻面的双向图.对于每个面,它将具有四个相邻的面.由于它位于两个相邻立方体之间(此前称为"死面")而被剔除的面不应该是图的一部分.

放置多维数据集时,必须更新面图的邻接信息.需要删除死面.放置后的实时面的邻接需要合并由于放置的新块而添加的新面.如果您坐下来确定可能性,那么执行此操作的算法应该相当简单.例如,如果你有这个方块:

  A
+++++
+   +
+   + B
+   +
+++++

面A和面B相邻.如果放置新块,则更改邻接:

     +++++
     +   +
   C +   +
     +   +
  A  +++++
+++++  D
+   +
+   + B
+   +
+++++

A现在与C和B相邻,与D.相邻.

删除多维数据集后,必须再次更新面图的邻接信息.基本上,您必须反转以前的操作.

这个邻接图的要点是这样的:如果所有非死面都连接在图中,那么图的恰好一个周期是可见的; 所有其他图形循环都不可见.图形的循环是一组面,它们全部直接或间接地相互连接.

最大的问题是:你如何找到可见的循环？以下算法假定实体放置/移除块.这意味着放置的任何块的至少一个面是可见的.这也意味着可以看到通过移除块而变为现场的任何死面.

放置块时,可以创建一个或多个新的面周期.要检测到这一点,首先要找到通过放置块创建的所有非死面(与某些东西不直接相邻的面).其中至少有一个是可见的; 找那张脸.

然后,对于新块上的每个其他非死面,使用A*(A-star)图搜索来查找该面.A*是基于优先级队列的图搜索算法.在这种情况下,算法的"距离"是当前面所在的正方形与可见面所在的正方形之间的距离.

如果A*找不到面部,那么你知道你搜索过的每一张脸(你应该在测试它们时将它们存放在缓冲区中)是一个不可见周期的一部分,因此可以被剔除.您应将这些面标记为不可见,以供日后参考.

删除块更容易.当您移除块时,必须至少看到块的一个面(参见上面的假设).因此,如果要移除的块具有一些不可见的面,则包括那些不可见面的循环中的每个面必须变得可见.因此,在移除块之前,请检查是否有任何不可见的面.如果有,请使用深度优先搜索来查找该循环中的所有面,并将它们放在缓冲区中.删除块后,所有这些面都会变为可见.

现在,如果你能够传送块,事情会变得更加复杂.放置一个块时,有可能没有任何块的面可见.所以你需要做的就是找到世界某处可见的面孔.然后像往常一样对你的A*进行搜索.如果可见的脸在附近的某个地方会很好,所以搜索不必走得太远.

通过移除,您需要做的是找到块附近的所有不可见的面循环.然后你需要像以前一样找到一个可见面.然后删除块并使用A*搜索这些循环以查看它们是否可以找到可见面.那些可见的周期.那些不可见的循环.

此外,您需要有一个特殊情况来删除没有活动面的块(即:完全嵌入在其他块中).这会创建一个不可见的6面循环.

也许现在你明白为什么它可能不值得努力？老实说,除非你手头有实际的分析数据表明你需要这个,我强烈建议你不要追求.你可能会做更多不必要的工作,也可能花费大量时间在不相关的事情上.

现在,我把这个帖子从袖口上写下来; 我想到了最简单的算法.我还没有研究过这种算法的可能改进,比如先发制人地找到可以创建内部的块放置,或者找到被移除的块会使内部可见.所以我坦率地承认这个算法非常暴力.但找到一个更好的一个将需要一些努力,所以再次,除非你有分析数据已经说你需要这样做以实现你想要的性能,我建议反对它.