论文部分内容阅读
采用哪种方式进行渲染，是当前游戏和电影业界的设计制作者极为关注的问题。因为采用何种渲染方式决定了最终的效果。目前主流的渲染方式，不是在效果真实性不如人意就是对硬件性能的要求极为苛刻。那么，有没有一种不同的渲染技术可以让我们得到更多呢?
追寻体素光线投射渲染技术的历史
在计算机图形学中有多种渲染方式，其中最常见的是目前游戏和电影特效中的三角形光栅化渲染方式，这种渲染方式的好处是性能需求较低，但是缺点是真实性方面颇受诟病，特别是倒影、阴影等效果比较容易穿帮。
如果选择光线追踪渲染方式的话，虽说是符合光学原理，但是性能的需求是在太高了，在可见的一段时期内来说，都很难对复杂场景做到每秒三十帧画面的完全光线追踪渲染。目前的电影制作中，即使是《汽车总动员》也只是在倒影、阴影、环境闭塞等应用中完全采用了光线追踪渲染，而直接可视对象则采用了REYES光栅渲染。
id Software著名技术总监约翰·卡马克在2008年接受采访时候曾经对光线追踪技术有如下的评说：“我想，对于传统意义中的光线追踪，即不论是三角形网面或者高序图元这样常规定义的几何体进行光线相交解析处理，我都不怎么相信这样的技术能真如英特尔所正在推动的那样，可以在主要的渲染任务中占主导地位。从性能立场而言光栅渲染具有巨大的优势，而英特尔他们争辩说只要使用有效的剔除技术就能避免一大堆几何体的计算，但这个论据实际上只是伪辩。因为在光栅渲染中你同样可以使用闭塞查询和条件渲染实现类似的事情。两相比较之下，不管你有多少晶体管可用，光栅渲染都能更有效地使用它们。”
约翰·卡马克对光线追踪并不十分热衷，但是这并非是因为他非常保守以至于希望继续长期使用三角形光栅化渲染技术。事实上在多年前已经有报道指出，约翰咔马克对于实时渲染的未来有其自己的主意，那就是VoxelRay Casting体素光线投射渲染技术。
约翰·卡马克对体素光线投射渲染技术的研究并非前两年才开始，事实上在10多年他已经关注其中。在Quake／QuakeⅡ与Quakem期间，约翰·卡马克就尝试了了多种新兴渲染技术，并用一个代号统称这些研究，即Trinity(三位一体)。Trinity在当时被许多玩家理解为一个未来的产品以及来自id Software的新一代3D引擎。但事实上，idSoftware的QuakegI引擎仍然是沿用相当传统的技术，约翰·卡马克表示Trinity所研究的技术都没有应用到Quakem当中，但是由于这个期间的研究相当广泛，因此其中的某些成果将可能在未来的某个时间得到应用。
在OuakeⅢ开发伊始时，约翰·卡马克也同步开发出两个体素光线投射引擎，这两个引擎虽然差不多已经可以用软件方式运行，但那将是非常低的分辨率下才行得通，和采用硬件渲染多边形相比，这样的结果并未能达成开发目标。
当时约翰·卡马克对体素光线投射渲染的内存访问模式以及所有要点做了一个分析，发现如果能够使用硬件执行体素光线投射追踪器的话，所需的硬件成本将比现有的所有三角形光栅器大大降低，如果有这样的东西出现的话，那么它在许多情况下能表现的视觉效果将比单纯使用软件渲染具备高得多的说服力，换句话说，在具备硬件执行的情况成立下，体素光线投射才会具有较高的使用价值。
讨论体素光线投射渲染技术自然离不开《Outcast》——一个1999年7月上市的游戏，这是11年前的事情，当时的3D引擎已经基本上都迁移到支持3D图形卡加速卡上了，游戏玩家也已经完全认同3D图形卡是3D游戏的必备PC硬件，《Outcast》却逆天而行，采用了完全基于软件(CPU)的3D渲染器。
《Outcast》的最高分辨率只有512×384(这在当时都可以说是一个略低于主流及格标准的分辨率)，你需要一个最先进的处理器而不是一块3D图形卡。对系统资源的高度渴求并非这个引擎让人留下印象的唯一原因，使用体素光线投射渲染技术同样让这个游戏的渲染显得真正的与众不同。
如果你手头还有这个游戏(或者其他Novalogic公司的游戏)的话，不妨重温一下,你就会发现这些标榜基于voxel的渲染实质上只是在地形构造的一种简单构造方式。游戏中的地形是基于高程图(height map)，高程图可以让环境中的每个点都有一个可能的高度，这使得一些复杂的构造例如拱门就无法实现。
这个限制倒并非什么不可克服的限制，因为像拱门这样的构造在自然界中其实本身就相当罕见。尽管如此，地形显示是相当简单的，从视点出发就是以一列一列的方式排列。对于每一列，它的最大值Y会被存储起来(Y-buffer)，在渲染的时候，只有那些从视点观看方向Y值大于靠近视点方向前列的像素才会被显示。
在了解了这些历史后，我们接下来将看看体素光线投射渲染技术对我们的未来意味着什么，而第一步所需要了解的是体素、八分树(octree s)、光线投射(ray castlng)等技术名词是什么意思。
体素光线投射渲染详解
正如Pixel(像素)是名词Picture(图片)和Element(元素)的融合，Voxel(体素)其实也是Volume(体积)和Element的融合，因此Voxel其实是指体积元素，和乐高积木或者金字塔的石块在概念上是一样的，构造的对象是一个具有体积的实体，而三角形网面构造出来的对象就像一个空壳或者实体的表面。
在电子游戏中Voxel已经被多次应用，但是它最常见的传统应用场合是医学领域，这是因为它能很好地把连续横切面影像(MRI核磁共振成像扫描仪生成的影像)重构为实体。
然而采用Voxel来重现实体并非一个完美的办法，在现实世界中，没有多少东西只由一堆四方块组装而成的，大多数的东西并不能透过Voxel重构来获得准确的实体。在图3中，你看到的就是通过Voxel构建而成的一个非常粗糙的圆环面。
不过类似的问题在大多数游戏中所采用的三角形网面构成的模型中也是存在的，这些模型也是一些近似的构造，只不过你可以使用更多的三角形来获得趋近于真实的模型。Voxel同样可以透过采用更精细的栅格来减轻这个问题。不过这样一来，就会带来更多的内存消耗，这也正是采用Voxel所带来的主要缺点。
举个例子，一个1024 Voxel栅格，将消耗1024×4(RGBA)的内存空间，这相当于4GB的内存(假设RGBA各通道只是8位大小)，这样的内存消耗根本谈不上实用，但是幸运的是我们有一个解决方案来减轻这个缺点，它就是octrees或者说octaltrees(八分树)。
“Tree(树)”是在计算机科学中经常采用的数据结构，因为它可以把 数据层次化。当你在使用计算机文件的时候，其实所有人每天都无意中在和“树状结构”打交道。
在一个树状结构文件系统中，有硬盘的“根(我们通常使用“丿”或者“丶”来表示)目录”，根目录中包含若干个“枝干”(目录)，每个枝干包含若干“枝丫”(子目录)，周而复此，直到我们看到的“叶片”(文件)，只对树结构中的一部分进行存取要比对所有部分都分散分布的结构存取高效得多。
树的节点可以有多个分叉，如果最多有两个分叉的话，我们就称这样的树结构为二分树(bmary tree)，如果是0个或者4个分叉的话就是四分树(quaternary tree(quadtree))，如果是O个或者8个分叉的也就自然称作八分树foctree)了。
那么树结构在Voxel渲染上怎么用呢?前面我们提到，Voxel是以规整的栅格方式存放，这样的方式由于连空白位置也都予以编码，存在着巨大的浪费。八分树能透过只在需要之时才动用最细密分辨率的办法来提高内存空间的使用效率。为了简化问题，下面我们使用一个二维的空间对此方法进行阐述。
在这个12×12的栅格中我们画了一个圆形，由于分辨率太低了，因此这个圆实在太粗糙了不过另一方面，你可以看到栅格中有不少的地方是空白的，这些空间事实上都没有被使用到，但是却仍然被保留起来了。如果使用四分树结构的话，情况就会所示。
四分树的建立相当简单：打开原图，在各个方向上平分两份，形成四个象限。当一个象限完全位于空白处或者完全被圆形覆盖的话，就停止拆分计算。如果象限只有一部分被覆盖，那么拆分计算就继续进行下去。这样的拆分动作一直进行，直到所有的象限都是同类型(都被覆盖或者都是空白1，又或者已经达到了给定的拆分深度(我们在这里的例子是停止于树深4，即每个部分受覆盖的维拆分到16份)。正如你所看到的那样，即使是采用我们这样简单的拆分深度，获得的最终结果也更接近于原始的圆形并且只需要更少的空间存放(97个栅格，而正规的栅格需要122个栅格)。而我们接下来说的八分树，不过是将这个技术扩展成三维。
在实际应用中，按照上面的定义所能增加的内存空间可能要比你想象的少一些。这是因为在一个规整的栅格中，Voxel的位置是固定的。与之相反的是，在八分树中每个节点都必须维持一个连通其子级树的链接，而每个节点本身还必须具备Voxel所需的色彩、法线等8个内存指针。不过和八分树的许多其他优点相比，这只是个小缺点。为了让你能对八分树所具有的更重要贡献有充分的了解，我们必须首先对八分树数据结构如果显示到画面上进行阐述。有多种方式把呈现Voxel，但是id Software选择的方式被称作Ray Casting(光线投射)。
Ray Casting(光线投射)
和光线追踪(Ray Tracin曲类似的是，Ray Casting也要对画面的各个像素都发射或者投射光线，所不同的是，一旦出现交集，这个动作就停止并且不会再向这个像素投射第二条光线。
值得注意的是，Ray Casting和Ray Tracing虽然听上去有些类似，并且在开头的计算动作上也是几乎相同，但是两者绝对不是一回事，主要的应用场合也有很大区别，前者主要是用来获取可视面和形态，后者则是主要作光线方向和强度计算，当然由于工作原理接近，少数情况下也可以互通使用。
正因为这样，Ray Casting要比Ray Tracing更快，因为后者投射第二条光线的时候就会涉及内存访问所带来的各种问题。此外，Voxel的光线交集计算也要比三角形快得多，这也是Ray Casting在这里的另一个优势。除此以外，我们无需为加速这些交集计算建立而额外数据结构(在三角形上执行光线追踪的话，一般需要建立被称作KD－tree的数据结构来时实现处理加速)，Voxel的八分树既是数据结构(几何、纹理)，同时也是加速结构。
上面我们讨论的是Voxel八分树内存空间上的优势，那么在渲染的时候，这样的架构又有怎样的优点昵?
Voxel八分树在渲染中的一个主要优势是提供了一个纹理细节度求解的简洁途径，并且在几何体细节度求解上体现此优势(都只需要单一算法)。因为正如我们前面提到的那样，八分树包含了彩色信息，因此我们省略掉了2D纹理，更准确而言，八分树本身既是纹理同时也是几何体。因此在传统渲染方式中必须独立执行的纹理、几何体细节度管理问题现在已经合并为一个单一系统：八分树细节度管理，这使得问题变得相当简单，原则上这其实就是一个在纹理贴图中采用的mipmaping扩展。
Mipmap的作用就是用来尝试保存最接近像素(pixel)尺寸的纹理元素(texel)，为此，纹理会被预计算并保存为若干分辨率的版本，然后由硬件根据不同的mipmap级别选择屏幕上纹理的分辨率。
这样的动态细节度选择技术同样能在Voxel上达成。一旦Voxel的尺寸小于像素尺寸的话，八分树的光线遍历就会在这个级别上被叫停。你所需要的只是保存八分树各个节点子级所包含信息的平均值，然后你就有了一个非常简单的管理细节度途径。这个机制非常适用于流式数据系统，而这又有一点像id Software已经应用于Megatextues(兆级纹理)的数据处理方式。只有这部分八分树需要存储到显卡内存中，另一部分则存放在系统主内存中以加速后续的存取，而八分树的大头实际上保存在硬盘或者其他海量存储媒介当中。
这样的机制可以让我们拥有几乎无限的几何体数量以及纹理。我们可以按照显示时的内存大小和刷新时间，来设定八分树的细节度。能对此限制的只是艺术家们用于创作八分树的时间量以及下一代电脑系统存储媒介的物理上限。
当然，这两个问题其实也是可能有些办法来解决的，例如采用Megatextures或者离散虚拟纹理等虚拟纹理系统，这类纹理系统已经在现有的CryEngine 3和idTech 6等3D引擎中集成。几何体问题的解决要更棘手一些，不过我们也都有几个可能的方案了，最简单的办法就是在不同的分辨率上预先计算若干本版本，这样的基本方案最容易实现，但是在从一个分辨率级别切换到另一个级别的时候就会容易看到突变。
有些研究人员已经在细节度过渡平滑这个课题上使用被称作渐进网面的技术做了一些工作。所谓渐进网面，就是每个几何体细节度的顶点分为两组，一组叫夫顶点，一组叫子顶点。当细节度调低的时候，子顶点的绘制会逐渐向夫顶点靠近，当细节度达到整数的时候，子顶点就被删除掉，此时剩下的都是由夫顶点所连结的边缘。
这个技术的确可行，但是它不够自动化，需要艺术家额外的工作以指示哪些边缘最重要需要被保留，这也意味着减少了对模型精雕细琢的时间了。
另一个实现几何细节度平滑化 过渡的方案是现在大家颇为熟悉的高序图元tessellation(镶嵌)，这是在DirectX 11中正式引入的技术，至少有三个已经上市的DirectX 11游戏使用了该技术，按照NVIDIA在Fermi测试指南中透露的信息，id Software也将会采用tessellation技术。八分树的主要问题是创建相当耗时，无法在游戏运行的时候实时修改数据结构，在采用动态几何体的时候，Voxel八分树的这个缺点显得尤为突出。id Software对此的应对措施和当年N0valogic差不多，只对静态几何体采用VoxelJk，分树渲染，而动态的几何体则采用传统的三角形光栅化渲染显示。这意味这我们将可能无法看到具互动特性的地形，例如爆炸依然只能让地面出现一团黑色的痕迹而不是出现一个真实的弹坑。
此外，虽然Voxel八分树可以透过一些技术让视野渐变或者行进时候看到的几何细节度变化平滑化，但是如果是像突然使用高倍数望远镜或者是传送门之类的装备，仍然会出现一个粗糙的轮廓而后逐渐清晰的几何体重构现象。游戏开发人员必须想办法让这些短时间的变化在一定的条件下变成合情合理，例如望远镜设计成电子式的，画面需要“充电”或者计算才能完全显示观测景象，传送门会让玩家的视野有短暂的眩晕感(或者其他任何合情合理的小把戏)等。
虽然传统的三角形渲染也会有类似的细节度突变问题，但是在大多数情况下都是表现为纹理细节度的变化，这只是让你看几秒的粗糙低分辨贴图效果，而在Voxel八分树中，如果不加一些特殊处理，你看到的将是令人崩溃的粗糙世界。
Voxel渲染的另一个不足是当我们凑近的时候会出现像素放大化痕迹，让画面看上去非常斑驳，这实在不是我们想象中的新一代渲染技术所能呈现的效果，幸运的是，我们可以使用三线性过滤将这个问题解决掉。
最后，虽然八分树数据结构能节省内存空间，但是以Voxel方式存放整个渲染空间所需要的内存依然是相当庞大的，虽然我们提到过，这并不真的影响执行所需的资源。
为了管理、存储、分发这样的数据结构，idSoftware在压缩技术上进行y--些研究，该工作室的约翰·欧力克就曾经谈及这个话题。据他介绍，彩色数据压缩比率预期可以达到8：1，每个Voxel的位置数据可以用1.15个位元实现，与之相比三角形采用传统32－bit(单精度)格式的话每个三角形的所有信息需要160—bit(Voxel与之相比可以达到2.2：1的压缩比率)。
写在最后
GPU的计算能力、可编程能力和内存存取能力越来越强大，这使得一些特别的渲染技术得以在透过GPU实现。Voxel八分树光线投射将是未来游戏中戏剧性增加几何体复杂度中更具可行性的技术之一。在目前，这个技术已经快要从纸面变为现实，Crytek公司推出的新游戏Crysis 2所采用的CryEngin 3游戏引擎就具备相应技术的实现能力。
在这项技术所面对的各种未解制约因素当中，最具决定性的制约因素就是图形艺术家所必须使用的编辑工具。id Software的约翰·欧力克预期这将由目前创作用于增强纹理细节度Megatextures系统演变，这个系统不再是透过使用修改法线的操作来改变几何体形状和细节，而是允许直接对几何体进行搓捏雕琢。在2008年的Siggraph上，约翰·欧力克表示花在工具上的时间大概是1年，然后运行库花了大约3个月时间。
在性能目标上，约翰-欧力克在2008年的时候认为下一代游戏机平台将至少可以达到4倍于GeForce 8800系列的性能，在维持当前几何体复杂度下，有望实现1080p、60fps的性能水平。“下一代游戏机”显然不会在今年上市，而顶级PC硬件通常可以在同样的特效设定下以同样的帧率比同期的游戏机平台跑高一级的分辨率，我们可以预期当下一代游戏机出来的时候，主流PC平台应该能胜任Voxel光线投射游戏。
追寻体素光线投射渲染技术的历史
在计算机图形学中有多种渲染方式，其中最常见的是目前游戏和电影特效中的三角形光栅化渲染方式，这种渲染方式的好处是性能需求较低，但是缺点是真实性方面颇受诟病，特别是倒影、阴影等效果比较容易穿帮。
如果选择光线追踪渲染方式的话，虽说是符合光学原理，但是性能的需求是在太高了，在可见的一段时期内来说，都很难对复杂场景做到每秒三十帧画面的完全光线追踪渲染。目前的电影制作中，即使是《汽车总动员》也只是在倒影、阴影、环境闭塞等应用中完全采用了光线追踪渲染，而直接可视对象则采用了REYES光栅渲染。
id Software著名技术总监约翰·卡马克在2008年接受采访时候曾经对光线追踪技术有如下的评说：“我想，对于传统意义中的光线追踪，即不论是三角形网面或者高序图元这样常规定义的几何体进行光线相交解析处理，我都不怎么相信这样的技术能真如英特尔所正在推动的那样，可以在主要的渲染任务中占主导地位。从性能立场而言光栅渲染具有巨大的优势，而英特尔他们争辩说只要使用有效的剔除技术就能避免一大堆几何体的计算，但这个论据实际上只是伪辩。因为在光栅渲染中你同样可以使用闭塞查询和条件渲染实现类似的事情。两相比较之下，不管你有多少晶体管可用，光栅渲染都能更有效地使用它们。”
约翰·卡马克对光线追踪并不十分热衷，但是这并非是因为他非常保守以至于希望继续长期使用三角形光栅化渲染技术。事实上在多年前已经有报道指出，约翰咔马克对于实时渲染的未来有其自己的主意，那就是VoxelRay Casting体素光线投射渲染技术。
约翰·卡马克对体素光线投射渲染技术的研究并非前两年才开始，事实上在10多年他已经关注其中。在Quake／QuakeⅡ与Quakem期间，约翰·卡马克就尝试了了多种新兴渲染技术，并用一个代号统称这些研究，即Trinity(三位一体)。Trinity在当时被许多玩家理解为一个未来的产品以及来自id Software的新一代3D引擎。但事实上，idSoftware的QuakegI引擎仍然是沿用相当传统的技术，约翰·卡马克表示Trinity所研究的技术都没有应用到Quakem当中，但是由于这个期间的研究相当广泛，因此其中的某些成果将可能在未来的某个时间得到应用。
在OuakeⅢ开发伊始时，约翰·卡马克也同步开发出两个体素光线投射引擎，这两个引擎虽然差不多已经可以用软件方式运行，但那将是非常低的分辨率下才行得通，和采用硬件渲染多边形相比，这样的结果并未能达成开发目标。
当时约翰·卡马克对体素光线投射渲染的内存访问模式以及所有要点做了一个分析，发现如果能够使用硬件执行体素光线投射追踪器的话，所需的硬件成本将比现有的所有三角形光栅器大大降低，如果有这样的东西出现的话，那么它在许多情况下能表现的视觉效果将比单纯使用软件渲染具备高得多的说服力，换句话说，在具备硬件执行的情况成立下，体素光线投射才会具有较高的使用价值。
讨论体素光线投射渲染技术自然离不开《Outcast》——一个1999年7月上市的游戏，这是11年前的事情，当时的3D引擎已经基本上都迁移到支持3D图形卡加速卡上了，游戏玩家也已经完全认同3D图形卡是3D游戏的必备PC硬件，《Outcast》却逆天而行，采用了完全基于软件(CPU)的3D渲染器。
《Outcast》的最高分辨率只有512×384(这在当时都可以说是一个略低于主流及格标准的分辨率)，你需要一个最先进的处理器而不是一块3D图形卡。对系统资源的高度渴求并非这个引擎让人留下印象的唯一原因，使用体素光线投射渲染技术同样让这个游戏的渲染显得真正的与众不同。
如果你手头还有这个游戏(或者其他Novalogic公司的游戏)的话，不妨重温一下,你就会发现这些标榜基于voxel的渲染实质上只是在地形构造的一种简单构造方式。游戏中的地形是基于高程图(height map)，高程图可以让环境中的每个点都有一个可能的高度，这使得一些复杂的构造例如拱门就无法实现。
这个限制倒并非什么不可克服的限制，因为像拱门这样的构造在自然界中其实本身就相当罕见。尽管如此，地形显示是相当简单的，从视点出发就是以一列一列的方式排列。对于每一列，它的最大值Y会被存储起来(Y-buffer)，在渲染的时候，只有那些从视点观看方向Y值大于靠近视点方向前列的像素才会被显示。
在了解了这些历史后，我们接下来将看看体素光线投射渲染技术对我们的未来意味着什么，而第一步所需要了解的是体素、八分树(octree s)、光线投射(ray castlng)等技术名词是什么意思。
体素光线投射渲染详解
正如Pixel(像素)是名词Picture(图片)和Element(元素)的融合，Voxel(体素)其实也是Volume(体积)和Element的融合，因此Voxel其实是指体积元素，和乐高积木或者金字塔的石块在概念上是一样的，构造的对象是一个具有体积的实体，而三角形网面构造出来的对象就像一个空壳或者实体的表面。
在电子游戏中Voxel已经被多次应用，但是它最常见的传统应用场合是医学领域，这是因为它能很好地把连续横切面影像(MRI核磁共振成像扫描仪生成的影像)重构为实体。
然而采用Voxel来重现实体并非一个完美的办法，在现实世界中，没有多少东西只由一堆四方块组装而成的，大多数的东西并不能透过Voxel重构来获得准确的实体。在图3中，你看到的就是通过Voxel构建而成的一个非常粗糙的圆环面。
不过类似的问题在大多数游戏中所采用的三角形网面构成的模型中也是存在的，这些模型也是一些近似的构造，只不过你可以使用更多的三角形来获得趋近于真实的模型。Voxel同样可以透过采用更精细的栅格来减轻这个问题。不过这样一来，就会带来更多的内存消耗，这也正是采用Voxel所带来的主要缺点。
举个例子，一个1024 Voxel栅格，将消耗1024×4(RGBA)的内存空间，这相当于4GB的内存(假设RGBA各通道只是8位大小)，这样的内存消耗根本谈不上实用，但是幸运的是我们有一个解决方案来减轻这个缺点，它就是octrees或者说octaltrees(八分树)。
“Tree(树)”是在计算机科学中经常采用的数据结构，因为它可以把 数据层次化。当你在使用计算机文件的时候，其实所有人每天都无意中在和“树状结构”打交道。
在一个树状结构文件系统中，有硬盘的“根(我们通常使用“丿”或者“丶”来表示)目录”，根目录中包含若干个“枝干”(目录)，每个枝干包含若干“枝丫”(子目录)，周而复此，直到我们看到的“叶片”(文件)，只对树结构中的一部分进行存取要比对所有部分都分散分布的结构存取高效得多。
树的节点可以有多个分叉，如果最多有两个分叉的话，我们就称这样的树结构为二分树(bmary tree)，如果是0个或者4个分叉的话就是四分树(quaternary tree(quadtree))，如果是O个或者8个分叉的也就自然称作八分树foctree)了。
那么树结构在Voxel渲染上怎么用呢?前面我们提到，Voxel是以规整的栅格方式存放，这样的方式由于连空白位置也都予以编码，存在着巨大的浪费。八分树能透过只在需要之时才动用最细密分辨率的办法来提高内存空间的使用效率。为了简化问题，下面我们使用一个二维的空间对此方法进行阐述。
在这个12×12的栅格中我们画了一个圆形，由于分辨率太低了，因此这个圆实在太粗糙了不过另一方面，你可以看到栅格中有不少的地方是空白的，这些空间事实上都没有被使用到，但是却仍然被保留起来了。如果使用四分树结构的话，情况就会所示。
四分树的建立相当简单：打开原图，在各个方向上平分两份，形成四个象限。当一个象限完全位于空白处或者完全被圆形覆盖的话，就停止拆分计算。如果象限只有一部分被覆盖，那么拆分计算就继续进行下去。这样的拆分动作一直进行，直到所有的象限都是同类型(都被覆盖或者都是空白1，又或者已经达到了给定的拆分深度(我们在这里的例子是停止于树深4，即每个部分受覆盖的维拆分到16份)。正如你所看到的那样，即使是采用我们这样简单的拆分深度，获得的最终结果也更接近于原始的圆形并且只需要更少的空间存放(97个栅格，而正规的栅格需要122个栅格)。而我们接下来说的八分树，不过是将这个技术扩展成三维。
在实际应用中，按照上面的定义所能增加的内存空间可能要比你想象的少一些。这是因为在一个规整的栅格中，Voxel的位置是固定的。与之相反的是，在八分树中每个节点都必须维持一个连通其子级树的链接，而每个节点本身还必须具备Voxel所需的色彩、法线等8个内存指针。不过和八分树的许多其他优点相比，这只是个小缺点。为了让你能对八分树所具有的更重要贡献有充分的了解，我们必须首先对八分树数据结构如果显示到画面上进行阐述。有多种方式把呈现Voxel，但是id Software选择的方式被称作Ray Casting(光线投射)。
Ray Casting(光线投射)
和光线追踪(Ray Tracin曲类似的是，Ray Casting也要对画面的各个像素都发射或者投射光线，所不同的是，一旦出现交集，这个动作就停止并且不会再向这个像素投射第二条光线。
值得注意的是，Ray Casting和Ray Tracing虽然听上去有些类似，并且在开头的计算动作上也是几乎相同，但是两者绝对不是一回事，主要的应用场合也有很大区别，前者主要是用来获取可视面和形态，后者则是主要作光线方向和强度计算，当然由于工作原理接近，少数情况下也可以互通使用。
正因为这样，Ray Casting要比Ray Tracing更快，因为后者投射第二条光线的时候就会涉及内存访问所带来的各种问题。此外，Voxel的光线交集计算也要比三角形快得多，这也是Ray Casting在这里的另一个优势。除此以外，我们无需为加速这些交集计算建立而额外数据结构(在三角形上执行光线追踪的话，一般需要建立被称作KD－tree的数据结构来时实现处理加速)，Voxel的八分树既是数据结构(几何、纹理)，同时也是加速结构。
上面我们讨论的是Voxel八分树内存空间上的优势，那么在渲染的时候，这样的架构又有怎样的优点昵?
Voxel八分树在渲染中的一个主要优势是提供了一个纹理细节度求解的简洁途径，并且在几何体细节度求解上体现此优势(都只需要单一算法)。因为正如我们前面提到的那样，八分树包含了彩色信息，因此我们省略掉了2D纹理，更准确而言，八分树本身既是纹理同时也是几何体。因此在传统渲染方式中必须独立执行的纹理、几何体细节度管理问题现在已经合并为一个单一系统：八分树细节度管理，这使得问题变得相当简单，原则上这其实就是一个在纹理贴图中采用的mipmaping扩展。
Mipmap的作用就是用来尝试保存最接近像素(pixel)尺寸的纹理元素(texel)，为此，纹理会被预计算并保存为若干分辨率的版本，然后由硬件根据不同的mipmap级别选择屏幕上纹理的分辨率。
这样的动态细节度选择技术同样能在Voxel上达成。一旦Voxel的尺寸小于像素尺寸的话，八分树的光线遍历就会在这个级别上被叫停。你所需要的只是保存八分树各个节点子级所包含信息的平均值，然后你就有了一个非常简单的管理细节度途径。这个机制非常适用于流式数据系统，而这又有一点像id Software已经应用于Megatextues(兆级纹理)的数据处理方式。只有这部分八分树需要存储到显卡内存中，另一部分则存放在系统主内存中以加速后续的存取，而八分树的大头实际上保存在硬盘或者其他海量存储媒介当中。
这样的机制可以让我们拥有几乎无限的几何体数量以及纹理。我们可以按照显示时的内存大小和刷新时间，来设定八分树的细节度。能对此限制的只是艺术家们用于创作八分树的时间量以及下一代电脑系统存储媒介的物理上限。
当然，这两个问题其实也是可能有些办法来解决的，例如采用Megatextures或者离散虚拟纹理等虚拟纹理系统，这类纹理系统已经在现有的CryEngine 3和idTech 6等3D引擎中集成。几何体问题的解决要更棘手一些，不过我们也都有几个可能的方案了，最简单的办法就是在不同的分辨率上预先计算若干本版本，这样的基本方案最容易实现，但是在从一个分辨率级别切换到另一个级别的时候就会容易看到突变。
有些研究人员已经在细节度过渡平滑这个课题上使用被称作渐进网面的技术做了一些工作。所谓渐进网面，就是每个几何体细节度的顶点分为两组，一组叫夫顶点，一组叫子顶点。当细节度调低的时候，子顶点的绘制会逐渐向夫顶点靠近，当细节度达到整数的时候，子顶点就被删除掉，此时剩下的都是由夫顶点所连结的边缘。
这个技术的确可行，但是它不够自动化，需要艺术家额外的工作以指示哪些边缘最重要需要被保留，这也意味着减少了对模型精雕细琢的时间了。
另一个实现几何细节度平滑化 过渡的方案是现在大家颇为熟悉的高序图元tessellation(镶嵌)，这是在DirectX 11中正式引入的技术，至少有三个已经上市的DirectX 11游戏使用了该技术，按照NVIDIA在Fermi测试指南中透露的信息，id Software也将会采用tessellation技术。八分树的主要问题是创建相当耗时，无法在游戏运行的时候实时修改数据结构，在采用动态几何体的时候，Voxel八分树的这个缺点显得尤为突出。id Software对此的应对措施和当年N0valogic差不多，只对静态几何体采用VoxelJk，分树渲染，而动态的几何体则采用传统的三角形光栅化渲染显示。这意味这我们将可能无法看到具互动特性的地形，例如爆炸依然只能让地面出现一团黑色的痕迹而不是出现一个真实的弹坑。
此外，虽然Voxel八分树可以透过一些技术让视野渐变或者行进时候看到的几何细节度变化平滑化，但是如果是像突然使用高倍数望远镜或者是传送门之类的装备，仍然会出现一个粗糙的轮廓而后逐渐清晰的几何体重构现象。游戏开发人员必须想办法让这些短时间的变化在一定的条件下变成合情合理，例如望远镜设计成电子式的，画面需要“充电”或者计算才能完全显示观测景象，传送门会让玩家的视野有短暂的眩晕感(或者其他任何合情合理的小把戏)等。
虽然传统的三角形渲染也会有类似的细节度突变问题，但是在大多数情况下都是表现为纹理细节度的变化，这只是让你看几秒的粗糙低分辨贴图效果，而在Voxel八分树中，如果不加一些特殊处理，你看到的将是令人崩溃的粗糙世界。
Voxel渲染的另一个不足是当我们凑近的时候会出现像素放大化痕迹，让画面看上去非常斑驳，这实在不是我们想象中的新一代渲染技术所能呈现的效果，幸运的是，我们可以使用三线性过滤将这个问题解决掉。
最后，虽然八分树数据结构能节省内存空间，但是以Voxel方式存放整个渲染空间所需要的内存依然是相当庞大的，虽然我们提到过，这并不真的影响执行所需的资源。
为了管理、存储、分发这样的数据结构，idSoftware在压缩技术上进行y--些研究，该工作室的约翰·欧力克就曾经谈及这个话题。据他介绍，彩色数据压缩比率预期可以达到8：1，每个Voxel的位置数据可以用1.15个位元实现，与之相比三角形采用传统32－bit(单精度)格式的话每个三角形的所有信息需要160—bit(Voxel与之相比可以达到2.2：1的压缩比率)。
写在最后
GPU的计算能力、可编程能力和内存存取能力越来越强大，这使得一些特别的渲染技术得以在透过GPU实现。Voxel八分树光线投射将是未来游戏中戏剧性增加几何体复杂度中更具可行性的技术之一。在目前，这个技术已经快要从纸面变为现实，Crytek公司推出的新游戏Crysis 2所采用的CryEngin 3游戏引擎就具备相应技术的实现能力。
在这项技术所面对的各种未解制约因素当中，最具决定性的制约因素就是图形艺术家所必须使用的编辑工具。id Software的约翰·欧力克预期这将由目前创作用于增强纹理细节度Megatextures系统演变，这个系统不再是透过使用修改法线的操作来改变几何体形状和细节，而是允许直接对几何体进行搓捏雕琢。在2008年的Siggraph上，约翰·欧力克表示花在工具上的时间大概是1年，然后运行库花了大约3个月时间。
在性能目标上，约翰-欧力克在2008年的时候认为下一代游戏机平台将至少可以达到4倍于GeForce 8800系列的性能，在维持当前几何体复杂度下，有望实现1080p、60fps的性能水平。“下一代游戏机”显然不会在今年上市，而顶级PC硬件通常可以在同样的特效设定下以同样的帧率比同期的游戏机平台跑高一级的分辨率，我们可以预期当下一代游戏机出来的时候，主流PC平台应该能胜任Voxel光线投射游戏。