在刚刚结束的SIGGRAPH 2012上，Cyril Crassin提出的Sparse Voxel Octree（SVO）极其热门，几乎每个涉及到real time rendering的course和talk都免不了提及SVO。加上UE4将会采用SVO、idTech6早就说了将会采用SVO，更是起到了推波助澜的作用。那么SVO是什么，它能解决什么样的问题呢？
SVO简介
Voxelization
传统的mesh都表示成以三角形和四边形为单位的图元。而在SVO里，图元是更为简单和离散的voxel。每个voxel有其中心位置、大小等信息，但不需要考虑相互之间的拓扑关系。各种求交计算也变得简单了。从mesh转成voxel表达的过程就称为voxelization。
Voxelization的方法也是逐步发展过来的。从基于CPU的方法，到NVIDIA基于一层一层渲染的方法，在SIGGRAPH Asia 2010上，Michael Schwarz和 Hans-Peter Seidel的paper “Fast Parallel Surface and Solid Voxelization on GPUs”可以在一个pass内直接把一个mesh分解成voxel。经过改进后，分解一个Stanford dragon的速度在5ms之内，相当高效。
Sparse Voxel Octree
Voxel的表达也有它的弱点，主要是存储和访问的不方便。如果把整个场景不管是否有voxel占用的地方都密集存储，那么所需要的空间是惊人的。比如一个512x512x512分辨率的场景，一共有128M个voxel，如果每个voxel只有32字节的属性，场景也轻松突破4GB。直接存在显存里是不现实的。所以这里需要引入sparse voxel octree。通过把voxlization后的结果存放在octree的节点上，可以略过很多场景中的空区域，空间消耗可以减少到200MB-1GB。同时，因为有了层次结构，访问起来只需要遍历某个分支，速度也能提高。
通过在GPU上实现了全套octree维护的操作，octree可以不需要CPU的帮助，完全在GPU上添删节点。用这种方法，初次建立一个场景的octree需要70ms，之后每次更新只需要4-5ms。
Cone tracing
在准备好了octree之后，渲染场景就需要用到cone tracing。ray tracing是对每一个像素发射一个ray，达到表面后根据BRDF反射和折射出新的ray。cone tracing与此类似，只是把ray换成了圆锥。因为有了SVO的数据结构，可以把irradiance先cache在octree里，view pass只要gather就可以了。
能解决的问题
有了SVO + cone tracing之后，很多长期以来一直很困难的实时渲染问题可以直接得到解决。如soft shadow、area light、multiple lights、multiple bounces global illumination、glossy reflection、refraction、AO等效果，就不再需要用各种不同的方法进行hack，只要进行一次tracing就全部搞定。
另外，通过对SVO的一些prefiltering，还可以完成电影级的depth of field、LOD和anti aliasing。甚至，和以往的技术不同的是，在SVO的框架中，模糊表示只要和树的较粗层次节点求交，而忽略礁溪层次的节点，所以，这就意味着越模糊越快！对于一些体效果，比如烟雾和云，也能通过修改cone tracing来实现。
其他一些有趣的应用包括：把signed distance field存入SVO，就可以进行procedural content creating和处理可破坏场景；用SVO做bake light map的工具；collision detection也可以容易地放入SVO框架。
总的来说，很少有一个技术能用同样的框架同时解决这么多个领域的这么多问题。从这方面看，SVO确实很有效。
挑战
当然，SVO也不是万能的，在目前的软硬件条件下仍有一些限制。下面看看SVO面临的一些挑战。
速度
对于实时渲染来说，速度提升是个永恒的主题。虽然SVO + cone tracing的速度在demo中已经能达到70fps，但对于游戏这样的大系统来说，还是远远不够的。这也是为什么UE4和idTech6都定位于未来硬件的原因之一。在这里，常见的优化是改用混合流水线：传统方法渲染direct lighting（Forward和Deferred都可以），SVO负责indirect lighting。在indirect lighting本身，UE4也用了和KlayGE 4一样的multiresolution的方法，能有2-3倍的提速。
空间占用
要把超大场景表示成SVO，空间的占用仍会是巨大的。好在SVO很适合streaming，可以随着视角等因素动态载入需要的节点，类似于virtual texturing。idTech6所描述的方法类似于此。
动态物体
无动态物体不成游戏。如果把所有物体存在一起，如果有的物体需要每帧变化，就意味着需要把整个场景重新voxelization、重新建树，开销很大。在这里UE4的改进方法很直接，把动态物体和静态物体分别放在两个SVO上，静态的只建立一次，动态的在变化后voxelization并更新树的部分节点。
对于deformation型的动态物体，可以用shell texture的方式，把SVO建立在物体表面。每帧只要根据deform过的物体来平移/旋转/放缩SVO，而SVO的内容本身保持不变。
KDTree？
对于tracing来说，KDTree在很多时候比Octree更平衡，但在GPU上建KDTree则较为复杂。所以不是没有可能用KDTree取代Octree进行数据存储和跟踪，这就成了SVKD。
Comments