如何在 Minecraft 的单位立方体世界中进行面部去除? [英] How to do face removal in a unit-cube world a la Minecraft?

问题描述

重要提示:这个问题与几何剔除(视锥体剔除、背面剔除、遮挡剔除或它们的任何朋友)无关.这个问题与几何消除有关在设置时，早在我们开始剔除和渲染之前.

Important note: This question is NOT about geometry culling (frustrum culling, back face culling, occlusion culling or any of their friends.) This question is about geometry elimination at set-up time, long before we get to culling and rendering.

在单位立方体渲染的世界(a la MineCraft)中，我正在尝试寻找算法来从我的几何面列表中删除从任何角度都无法看到的几何面，无论相机在哪里.

In a unit-cube rendered world (a la MineCraft), I'm trying to find algorithms for how to remove from my list of geometry faces that can't possibly be seen from any angle, no matter where the camera is.

例如，假设有 2 个正方形:

For example, imagine 2 squares:

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

显然有 8 个可见边(每个正方形 4 个).现在我将这些正方形移动到一起，vis:

clearly there are 8 visible sides (4 on each square.) Now I move the squares together, vis:

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

现在我只有 6 个面，而不是 8 个面！中间相触的两人，无论相机放在什么位置，无论面对什么角度，都看不到.(正方形的纹理不同，所以我们不能称之为 4 边.)

Rather than having 8 sides, now I only have 6! The two that are touching in the middle can't be seen, no matter where the camera is placed, nor what angle it is facing. (The squares are textured differently, so we can't call it 4 sides.)

(同样的事情在立方体的 3D 中也有效，但 12 个面(每个立方体 6 个)因为 2 个接触被消除而变成了 10 个.)

(The same thing works in 3D with cubes, but 12 faces (6 per cube) become 10 as the 2 touching are eliminated.)

我的问题是:有哪些算法可以帮助我识别这些隐藏的面孔?(我很高兴自己用谷歌搜索，但我什至不知道这叫什么！)特别是，我正在寻找可以处理中间空心点的东西——如果你是，这些点可能是可见的但是，因为它们被几何图形包围，所以你看不到它们.

My question is: what are some algorithms that help me to recognize these hidden faces? (I'm happy to do my own Googling, but I don't even know what this is called!) In particular, I'm looking for something that handles hollow spots in the middle -- spots which COULD be visible if you were in there but, because they're surrounded by geometry, you can't see them.

例如:

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

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

In this case, one might think there 18 "visible" sides but, because we know for a fact that the camera is outside of the geometry, the 4 sides in square "A" aren't visible.

让事情更复杂的是，我希望找到一种算法，如果添加或删除一个块，可以快速更新(再次，a la MineCraft.)

To further complicate things, I'm hoping to find an algorithm that can make quick updates if a block is added or removed (again, a la MineCraft.)

谢谢！

推荐答案

您问题的第一部分非常简单.对于每个立方体，如果它与另一个立方体直接相邻，则移除它与该立方体共享的面.

The first part of your question is really quite simple. For each cube, if it is directly adjacent to another cube, you remove the face it shares with that cube.

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

This is not something that should be a performance issue (outside of the cost of modifying and uploading the changed vertex data), since you will only recompute this when a block is placed or removed. The effects of placing and removing a block are quite local; it will only affect the 6 neighboring cubes and itself, so it shouldn't be a problem. You also don't need any specialized data structures, other than the obvious ones you need to handle a cube-based environment.

建造地形的初始成本可能有些高，但这是您可以承受的一次性成本.将其计入您的加载时间.如果您要在一个框架的空间中进行大量的放置和移除操作，这可能是一个问题.

The initial cost of building the terrain may be something, but that's a one-time cost that you can live with. Factor it into your loading time. If you're doing a lot of placements and removals in the space of a frame, it could be an issue.

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

The more difficult issue is removing sealed interiors. My suggestion: it's not worth it. By trying to remove sealed interiors, placing or removing a block becomes a non-local operation. You would probably get more performance by spending time optimizing your batch count (use texture atlases/arrays where possible) and your vertex data.

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

To remove sealed interiors, you need to be able to detect interiors. And therefore, you will need to maintain a bidirectional graph of adjacent faces. For each face, it will have four adjacent faces. Faces that were culled because it was between two adjacent cubes (heretofore referred to as "dead faces") should not be part of the graph.

放置立方体时，必须更新人脸图的邻接信息.需要去除死面.放置后实时面的邻接需要合并由于放置的新块而添加的新面.如果您坐下来规划可能性，那么执行此操作的算法应该相当简单.例如，如果您有这个正方形:

When a cube is placed, you must update the adjacency information for the face graph. Dead faces need to be removed. The adjacency for live faces after placement needs to incorporate the new faces that were added due to the new block that was placed. The algorithm to do this should be fairly straightforward if you sit down and map out the possibilities. For example, if you have this square:

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

面 A 和 B 相邻.如果你放置一个新块，你会改变邻接:

The faces A and B are adjacent. If you place a new block, you change the adjacency:

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

A 现在与 C 相邻，B 与 D 相邻.

A is now adjacent to C and B adjacent to D.

当一个立方体被移除时，你必须再次更新人脸图的邻接信息.本质上，您必须反转之前的操作.

When a cube is removed, you must again update the adjacency information for the face graph. Essentially, you have to reverse the previous operation.

这个邻接图的要点是:如果图中所有的非死面都连接起来，那么正好可以看到图的一个循环；所有其他图形循环将不可见.图的一个环是一组直接或间接相互连接的人脸.

The point of this adjacency graph is this: if all of the non-dead faces are connected in the graph, then exactly one cycle of the graph will be visible; all other graph cycles will not be visible. A cycle of the graph being a group of faces that are all connected to one another, either directly or indirectly.

最大的问题是:如何找到可见循环?以下算法假定块由实体放置/移除.这意味着放置的任何块的至少一个面是可见的.这也意味着通过移除块而变得活跃的任何死脸都是可见的.

The big question is this: how do you find the visible cycle? The following algorithm assumes that blocks are placed/removed by an entity. This means that at least one face of any block that is placed is visible. It also means that any dead faces that become live by removing a block are visible.

当您放置一个块时，您可以创建一个或多个新的面循环.要检测到这一点，您首先要找到通过放置块创建的所有非死人脸(不直接与某物相邻的人脸).其中至少有一个是可见的；找到那张脸.

When you place a block, you may create one or more new cycles of faces. To detect this, you first find all of the non-dead faces (the ones that aren't directly adjacent to something) that you have created by placing the block. At least one of these will be visible; find that face.

然后，对于新块上的所有其他未死人脸，使用 A*(A 星)图搜索来查找该人脸.A* 是一种基于优先级队列的图搜索算法.在这种情况下，算法的距离"是当前人脸所在的正方形与可见人脸所在的正方形之间的距离.

Then, for every other non-dead face on the new block, use an A* (A-star) graph search to find that face. A* is a priority-queue-based graph search algorithm. In this case, the "distance" for the algorithm is the distance between the square that the current face is on and the square that the visible face is on.

如果 A* 找不到人脸，那么您就知道您搜索过的每个人脸(您可能应该在测试时将它们存储在缓冲区中)都是不可见循环的一部分，因此可以被剔除.您应该将这些面孔标记为不可见以供日后参考.

If the A* cannot find the face, then you know that every face that you searched through (you should probably store them in a buffer as you test them) is part of a non-visible cycle and can therefore be culled. You should mark these faces as being non-visible for later reference.

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

Removing a block is much easier. When you're removing a block, at least one face of the block must be visible (see the assumption above). Therefore, if the block to be removed had some non-visible faces, every face in a cycle including those non-visible faces must become visible. So before removing the block, check it for any non-visible faces. If there are any, use a depth-first search to find all of the faces in that cycle, and put them in a buffer. Once you remove the block, all of those faces now become visible.

现在，如果你能够传送方块，事情就会变得更加复杂.当您放置一个块时，有可能该块的面都不可见.所以你需要做的是在世界中某处找到一张可见的脸.然后像往常一样对那张脸进行 A* 搜索.如果可见人脸在附近某处就好了，这样搜索就不必走得太远.

Now, if you're able to teleport blocks, things become more complex. When you place a block, there is the chance that none of that block's faces are visible. So what you need to do is find a face somewhere in the world that is visible. Then do your A* searching towards that face as normal. It would be good if the visible face were somewhere nearby, so the search didn't have to go too far.

移除后，您要做的就是找到与块相邻的所有不可见的面循环.然后你需要像以前一样找到一张可见的脸.然后移除块并使用 A* 搜索这些循环以查看它们是否可以找到可见的面.那些可见的循环.那些看不见的循环.

With removal, what you have to do is find all of the non-visible face cycles adjacent to the block. Then you need to find that one visible face as before. Then you remove the block and search those cycles with A* to see if they can find the visible face. Those cycles that can are visible. Those cycles that cannot are not visible.

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

Also, you need to have a special case for removing a block that had no live faces (ie: is fully embedded in other blocks). This creates a 6-face cycle that is non-visible.

也许现在您明白为什么不值得付出努力了吧?老实说，除非您手头有实际的分析数据表明您需要这样做，否则我强烈建议您不要这样做.您可能会做更多不必要的工作，并且可能会在一些无关紧要的事情上花费大量时间.

Perhaps now you see why it's probably not worth the effort? Honestly, unless you have actual profiling data in hand that shows that you need this, I strongly advise you not to pursue that. You will likely be making more work than necessary, as well as potentially spending a lot of time on something irrelevant.

现在，我立即写下了这篇文章；我想到了最简单的算法.我还没有研究过这个算法的可能改进，比如先发制人地找到可以创建内部的块放置，或者找到如果删除就会使内部可见的块.所以我坦率地承认这个算法是相当蛮力的.但是找到一个更好的需要一些努力，所以再说一次，除非您有分析数据并说您需要这样做才能实现您想要的性能，否则我建议不要这样做.

Now, I wrote this post off the cuff; I thought of the simplest algorithm I could that would work. I have not researched possible improvements to this algorithm, like preemptively finding block placements that could create interiors, or finding blocks that if removed would make an interior visible. So I freely admit that this algorithm is pretty brute force. But finding a better one will require some effort, so again, unless you have profiling data in had saying that you need to do this to achieve the performance you want, I advise against it.

这篇关于如何在 Minecraft 的单位立方体世界中进行面部去除?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！