渲染大量立方体的剔除技术

Question

我正在进行一个个人学习项目，制作一个Minecraft克隆版。这个项目很好地运作着，除了一个问题。与Minecraft类似，我的地形由许多沿Y轴堆叠的立方体所组成，因此您可以挖掘下去。尽管我进行了截锥体剔除，但这仍意味着我无用地绘制了所有在我下面的立方体层。这些立方体是按X、Y和Z排序的（尽管只有在一个方向上，因此它在技术上不被相机排序为Z）。基本上，从玩家的位置开始，我只向周围的立方体添加指针。然后对这些指针进行截锥体剔除。我没有进行八叉树分割。我想过简单地不渲染玩家下面的层，但是如果玩家向下看一个洞时，这种方法就行不通了。鉴于此，我应该如何避免渲染我看不到的立方体层以及被其他立方体遮挡的立方体。

谢谢

void CCubeGame::SetPlayerPosition()
{
PlayerPosition.x = Camera.x / 3;
PlayerPosition.y = ((Camera.y - 2.9) / 3) - 1;
PlayerPosition.z = Camera.z / 3;
}

void CCubeGame::SetCollids()
{

SetPlayerPosition();

int xamount = 70;
int zamount = 70;
int yamount = 17;

int xamountd = xamount * 2;
int zamountd = zamount * 2;
int yamountd = yamount * 2;
PlayerPosition.x -= xamount;

PlayerPosition.y -= yamount;

PlayerPosition.z -= zamount;


collids.clear();
CBox* tmp;

    for(int i = 0; i < xamountd; ++i)
    {
        for(int j = yamountd; j > 0; --j)
        {
            for(int k = zamountd; k > 0; --k)
            {

                tmp = GetCube(PlayerPosition.x + i, PlayerPosition.y + j, PlayerPosition.z + k);



                if(tmp != 0)
                {
                    if(frustum.sphereInFrustum(tmp->center,25) != NULL)
                    {
                        collids.push_back(tmp);
                    }
                }

            }
        }

}

- jmasterx

---

至少，当您从前到后渲染排序时，可以快速拒绝所有底部的立方体。但是八叉树是一个好主意。 - GManNickG

@GMan 如果我的角度是65度x，70度y，我该如何从前到后渲染呢？在这种情况下，我怎么能不通过从相机到玩家的距离检查来实现呢？ - jmasterx

克隆一个克隆体。我很高兴决定不尝试制作自己的克隆体。 - Jon Purdy

首先使用八叉树来最小化你要绘制的立方体数量。然后按距离平方排序。（"遮挡查询"是一个你可能想要查找的东西。） - GManNickG

Answer 1

以下是我编写自己的克隆版本时学到的知识：

1. 不要只是简单地将每个立方体都倒入OpenGL中，但也不要担心自行完成所有的可见性剪枝。正如另一个答案所述，检查所有6个面是否被相邻块完全遮挡。只渲染可能可见的面。这大致将你的面数从立方项（n * n * n的立方体）减少为平方项（仅约为n * n的表面）。
2. OpenGL可以比您更快地执行视图截锥剔除。一旦您将所有表面面渲染到显示列表或VBO中，只需将整个blob发送到OpenGL。如果您将几何分成切片（或Minecraft称之为块），您可能会避免绘制相机后面的块。
3. 将整个几何图形渲染到显示列表中（或多个列表中）并每次重绘。如果您使用直接模式，这是一步容易实现的，因为您只需在glNewList / glEndList中包装现有代码，并使用glCallList重新绘制。减少OpenGL调用次数（每帧）将产生比减少要呈现的多边形的总体积更大的影响。
4. 一旦您看到生成显示列表所需的时间比绘制它们所需的时间长多少，您就会开始考虑如何将更新放入线程中。这就是转换为VBO的好处：线程渲染成普通的数组（例如添加3个浮点数到数组中而不是调用glVertex3f），然后GL线程仅需使用glBufferSubData将这些数据加载到显卡中。您赢了两次：代码可以在线程中运行，并且只需进行3个数组写入而不是3个函数调用即可“绘制”一点。

我注意到的其他事情：

VBO（顶点缓冲对象）和显示列表的性能非常相似。很可能某个OpenGL实现内部使用VBO来存储显示列表。我跳过了顶点数组（一种类似于客户端VBO的东西），所以对它们不太确定。请使用ARB扩展版本的VBO，而不是GL 1.5标准，因为Intel驱动程序仅实现扩展（尽管声称支持1.5），nvidia和ATI驱动程序则无所谓。

纹理图集很棒。如果您每面使用一个纹理，请看看图集是如何工作的。

如果要查看我的代码，请在github上找到我。

- Ben Jackson

---

感谢您提供的想法列表，您将获得赏金。 - Adam Davis

Answer 2

从前到后渲染。为此，您不需要排序，使用八叉树即可。叶子节点不是单独的立方体，而是更大的那些立方体组。

每个这样的叶子节点的网格应缓存在顶点缓冲区中。当您生成此网格时，不要以暴力方式生成所有立方体。相反，对于每个立方体面，请检查其是否具有同一叶子内的不透明邻居，如果有，则根本不需要生成此面。因此，您只渲染实心立方体和空间之间的表面。您还可以将具有相同材质的相邻面合并成单个长方形。您还可以将网格分为六个集合，每个主方向一个集合：+/-XYZ面。仅绘制可能朝向摄像机的那些面集。

仅仅从前到后渲染并不能帮助太多。然而，您可以利用现代硬件提供的遮挡剔除从这种排序中获益。在渲染八叉树叶子之前，请检查其bbox是否通过了遮挡查询。如果它没有通过，则根本不需要绘制它。

遮挡查询的替代方法可能是射线跟踪。射线跟踪对于渲染这样的环境非常好用。您可以投射一组稀疏的射线来近似可见的叶子，并仅绘制那些叶子。但是，这将低估可见性集。

- Yakov Galka

Answer 3

像其他人一样，我一直在使用Ogre玩弄一个块世界“引擎”，并在写文章时进行了一些尝试（请参见Block World Articles）。我采用的基本方法是：

• 仅创建块的可见面（不包括块之间的面）。
• 将世界分成较小的块（仅为更快速地更新单个块而必要）。
• 将块纹理合并到一个纹理文件中（纹理集）。

仅使用这些方法就可以在大型简单块世界上获得非常好的性能（例如，在良好的硬件上的1024x1024x1024）。

- uesp

Answer 4

我目前正在使用python/pyglet制作一个Minecraft克隆版，只是出于好奇。

我像Minecraft一样将数据分成块，然后针对每个块创建基于方块可见性的OpenGL显示列表。接着，我对这些块进行简单的2D视锥剔除，并在玩家一定距离内调用每个显示列表。

对于方块的添加/删除，我重新创建块的显示列表。

除了被完全包围的方块外，没有遮蔽剔除。

对于简单的场景，在视距为约200个方块的情况下，这可以达到600fps以上，适用于中等显卡。

- Bobmitch

---

有一件事，你如何进行碰撞检测？ - jmasterx

我的Python代码中的一个地图类使用了一个“块”的字典。该字典的每个键都是一个二维元组，表示真实世界中的整数坐标。每个块包含一个块字典，其中每个块键都是一个三维元组。因此，碰撞检测涉及到在给定更新时查看玩家是否移动到了一个新的“块”，然后查找字典以查看是否存在块。 - Bobmitch

Answer 5

八叉树等方法肯定可行，但解决您特定问题的另一种可能方法是为每个立方体对象添加一个usigned char visible。 visible字段的值计算如下：

• 如果右侧（沿x轴查看）没有相邻的方块，则设置第一个位（1）。
• 如果左侧（沿负x轴查看）没有相邻的方块，则设置第二个位（2）。
• 如果前侧（沿z轴查看）没有相邻的方块，则设置第三个位（4）。
• ...以此类推，使每个立方体的6个面各有1位。

每当玩家挖掘一个方块时，您都必须更新其所有相邻方块的visible字段。

那么，这会有什么帮助呢？如果一个立方体的visible值为0，那么它就很容易——永远不会显示。但是假设立方体的visible值为1。那么，只有当Xplayer < Xcube时，该立方体（可能）才能被看到。其他面也是类似的，我认为这样一个函数可以决定一个立方体是否可见，速度相当快，并且能够跳过许多隐藏的立方体。

缺点是，这个测试只是一个针对每个立方体的测试，你不能用它来跳过整个组。因此，也许一个八叉树（用于跳过完整的区域）和像这里描述的可见字段一样，用于跳过该区域内数量众多的隐藏立方体（由于这些立方体是堆叠在一起的，隐藏立方体的数量将比可见立方体的数量高得多），可能是一个好的解决方案。

- tux21b

Answer 6

你可以使用PVS（潜在可见集）来实现这一点，尽管它通常用于地形，但相同的原则也适用于剔除看不见的内容。Gamedev.net还有一篇关于地形变形的文章涵盖了这一点。

- Necrolis

---

PVS需要预处理，因此无法在像这里所需的动态世界中使用。 - Yakov Galka

Answer 7

如果只是绘图是问题（而不是未使用顶点的旋转），那么类似c-buffer这样的东西会有用吗？我用它取得了相当大的成功，它需要排序的多边形（例如画家算法）和几乎零内存（与z缓冲相比）。

- Miro Kropacek

Answer 8

只跟踪描述您表面的立方体。您可以通过简单的数据结构来实现这一点，其中每个立方体都保留对其邻居的引用。在任何现代图形卡上，将所有这些三角形推送出去不应该是问题。从后往前渲染。同时，仅呈现比查看者特定距离更近的立方体。 "世界" 可以从一个巨大的 "立方体-立方体" 开始，由立方体制成的立方体的外壳。如果有人挖下去，您必须检查邻居位置是否已经包含立方体，如果没有，则创建这些立方体并将它们链接起来。

例如：挖掉一个平坦的表面：删除挖掘完成的位置处的立方体，添加 9 个新的立方体在下面（但要检查这些位置是否已经被使用，在这种情况下使用它们），将表面连接在一起，但将新的立方体链接到被移除的那个立方体的邻居立方体。

因此： 对于包含 1000x1000x1000 个立方体的世界，您将获得：1000*1000*2+998*999*4 = 5988008 而不是 1000*1000*1000 = 1000000000，或者是立方体数量减少了 167 倍。

当然，您不应该绘制所有这些立方体，而是从简单的距离查看者开始进行子选择。

你也可以将8个立方体（组）分为1组，然后继续这样做，直到在顶层只剩下一个立方体组（已经提到了八叉树）。该树可用于射线跟踪需要绘制和不需要绘制的世界部分。如果一个组包含对其他8个立方体组的引用，则那些在其后面的组将不会被显示。在这里，“后面”指的是那些不相交或位于从用户开始并通过测试组边缘的射线跟踪锥体之外的立方体组。（描述不太好，但我希望您能从中得到一些优化的提示）。在今天的图形卡上可能不需要这样做。

祝你的项目好运。

- UnixShadow