稀疏体素八叉树是什么？

Question

我已经阅读过很多关于未来图形引擎中使用稀疏体素八叉树的潜在应用的文章。

然而，我一直无法找到有关它们的技术信息。

我知道什么是体素，但我不知道稀疏体素八叉树是什么，也不知道它们如何比现在使用的多边形技术更有效。

能否有人解释或指向一份解释？

- pdeva

Answer 1

这里有关于id Software的片段，涉及到技术内容：链接

id Tech 6将采用一种更高级的技术来构建基于MegaTexture思想的虚拟几何体和纹理，使得可以达到像素等效下独特的三维形状：稀疏八叉树（SVO）。

它通过在八叉树中存储由体素（而非三角形）表示的几何体来进行光线追踪处理。

其目标是能够将八叉树的部分数据流式传输到显存中，在靠近物体的区域往下移动至更低层级以增加细节，并在较远物体使用级别更高、尺寸更大的体素来实现同时适用于几何体和纹理的自动细节级别（LOD）系统。

此外，这篇论文也论述了相关内容。

还有在这篇优秀的博客文章中可以找到更多信息。

只使用体素本身并不是那么有趣，因为对于任何具有合理细节的模型，你都需要大量的体素（如果使用均匀网格）。

所以，需要一个分级系统，这就引出了八叉树。 八叉树是一种非常简单的空间数据结构，将每个节点细分为8个同样大小的子节点。

稀疏八叉树是一种八叉树，其中大部分节点为空，类似于离散化微分方程时获得的稀疏矩阵。

- Ólafur Waage

---

我之前看过这个，但是它并没有提供任何硬技术细节。比如说，这些树的“稀疏”在哪里？为什么要用八叉树而不是二叉树或者“六叉”树？ - pdeva

它们被称为八叉树，因为每次将空间分成8个相等大小的子空间。 - schnaader

对于均匀八叉树，一个八叉树节点通过插入3个平面进行细分，这些平面彼此正交且每个平面都垂直于三个基向量x、y和z中的一个，并穿过要被划分的体积的中心点。一个被3个正交平面划分的体积会被分成8个子体积。 - CynicismRising

嗨，我在19/04/2012检查时发现论文链接已经失效了。你能分享一个新链接或者这篇论文的标题吗？ - Lefteris

@JustinMeiners 不是的。只有当你使用网格系统时才会有这个问题。使用八叉树，你的场景大小只需要足够包含你的对象即可。 - nonchip

Answer 2

八叉树有8个邻居，因为如果你想象一个正方形被均等地切成四份，就像这样：

______________
|     |      |
|     |      |
|_____|______|
|     |      |
|     |      |
|_____|______|

那么在三维空间中，你需要使用一个立方体而不是平面，这样水平、垂直和沿着Z轴切割后，你会得到8个块而不是4个，这就是所谓的“四叉树”。

    _____________
   /     /     / |
  /-----/-----/  |
 /_____/_____/ | |
 |     |     | |/|
 |-----|-----|/| |
 |     |     | |/
 |_____|_____|/

希望这有意义... SVO 的独特之处在于它存储了体素信息，即空间中的一个点，具有颜色、法线等属性。SVO 的理念是通过将三角形和纹理合并到单个 SVO 中来忽略三角形和纹理的需要，其中包含体素化三角形壳（模型）及其表面纹理。之所以需要八叉树，是因为否则均匀网格结构需要太多的内存，现有的图形卡难以处理。因此使用 SVO 允许一种类似 Mip-Mapped 的 3D 纹理。MipMapping 基本上是相同的图像，但在不同的尺度下，一个具有更多细节，最新的则具有较少的细节（但从远处看相当相似）。这样，近距离的物体可以从带有更多细节的 SVO 流式传输，而远离的物体则流式传输较少的细节。而如果像"Euclideon"一样打破常规，使用 "无限细节"，那么就可以使用视锥体切片和平面/轴对齐边界盒交集来查找每个像素在屏幕上的颜色，而不是使用 Nvidia 的天真 "光束优化" 射出光线和宽度*高度像素。PS（有点离题）：对于任何不理解 Euclideon 如何做到这一点的人，我认为这是最实用的解决方案，并且我有理由支持他们没有使用射线跟踪。他们最大的谜团不在于渲染，而在于存储他们的数据... RLE 简单地不能胜任... 因为一些体积/体素数据可能更随机，较少 "实心"，其中 RLE 无用，而我的压缩通常需要至少 5 个字节才能转换成更小的格式。他们说通过压缩可将输出减少约一半，所以他们正在使用 2.5 个字节，这与三角形现在的大小相当。

- Kyle Gibbar

Answer 3

一篇名为高效稀疏八叉树 - 分析，扩展和实现的NVIDIA白皮书在此处进行了详细描述。

- XiaJun

Answer 4

实际上，1.15位让我怀疑他们只是以一种非常简单的方式按顺序存储事物。也就是说，如果他们只存储了体积数据而没有颜色或纹理数据等其他东西。

这样想：1个体素只需要1个比特位：它是否存在？（换句话说，要么是，要么不是）。包含8个体素和一个比特位用于存储该物体是否包含任何内容的八叉树节点。每个体素加上每8个体素一个比特位，即为1个体素加上1/8个比特位=1.125。再添加一个父节点和7个兄弟节点，则为1个体素加上1/8个比特位加上1/8/8个比特位=1.140625。这与他们提到的1.15非常接近，虽然我可能完全错了，但这可能会给某人一些提示。

- Martijn Dekker

---

1+1/8+1/8/8+1/8/8/8+1/8/8/8/8+1/8/8/8/8/8+1/8/8/8/8/8/8+1/8/8/8/8/8/8/8+1/8/8/8/8/8/8/8/8+1/8/8/8/8/8/8/8/8/8 = 1.14285714179277420043 - nonchip

做了一些更多的计算，使用GNU基本计算器和mathlib得到1.14285714285714285705是最准确的值。我想我们可以用这个值来工作。 - nonchip

@nonchip 这是一个几何级数，答案确切为8/7。 - lisyarus

Answer 5

你甚至可以简单地光栅化所有的点，现在不需要进行光线追踪或光线投射，因为显卡可以投射大量的点。你使用八叉树是因为它是一个立方体形状，不断分割成越来越小的立方体（体素）。我正在开发一款使用光栅化技术的引擎，效果很好。对于那些认为无法对体素进行动画的人，我认为他们没有仔细思考这个问题，当然是可能的。在我看来，制作世界很像“无限3D涂鸦”，所以请查找3D涂鸦，这个程序的级别设计将非常类似于这个程序的工作方式。主要的缺点包括流媒体速度不够快，光线追踪或光栅化不能完全达到60帧每秒，而绘制实际的体素对象非常计算密集。目前，我可以在大约12秒钟内绘制一个1024x1024x1024的球体，但所有这些问题都可以得到解决，这是一个令人兴奋的未来。我目前的最大世界大小是1兆乘1兆乘1兆，但我实际上可能会将其扩大8倍。当然，另一个问题实际上相当严重，即即使经过压缩，存储8192x8192x8192个字符也需要大约100兆，因此环境甚至更多。尽管如此，与今天的游戏中所看到的相比，说你将拥有8192x8192x8192的角色是完全荒谬的...整个世界曾经是8192x8192x8192 :)

如果你只存储每个指针的位，那么指针将在视频内存中运行时构建...理解这一点，你就可以拥有自己的引擎。 :)

- Magnus Wootton