实战八叉树场景拣选例程

茵为你值得

前言：
  八叉树（Octree）是一种空间分割（Space Partitioning）的技术，用来将3D 空间中的物体做出空间性的区隔与分割。有了八叉树的技术之后，就可以“选择性”的画出空间中某个区域的物体，减少送入OpenGL 管道线做渲染的三角形信息量，进而大幅的提升复杂场景的执行效能。在这个演示程序中，实际应用八叉树分割一个高度图（heightmap）所建构的地形场景；并且可以运行时（runtime）调整八叉树的相关参数值，显示出不同的空间分割结果。

1、原理与声明（First Concept & Assertion）
  什么是八叉树？正如前言所提到的：八叉树是一种空间分割（Space Partitioning）的技术。为什么需要分割、需要八叉树呢？当我们建立起一个由数万个三角形所组成的复杂场景之时，若想实时（real-time）的绘出整个场景的话，恐怕在目前的平价显示卡上，都难以得到平顺流畅的绘图结果；也就是说在这种情况下，会大幅度的降低程序的执行效能。想象一下，如果我们能够只画出我们视线范围内“看得见”的场景，而不用去理会其它就算画出来也看不见的场景；如此一来，就可以避免画出场景后Fps 值却惨不忍睹的局面。如果你有看过之前“November Days DEMO”的原理解释，就不难发现这个想法（idea）其实似曾相识。也就是在处理雪花的过程中，有用到了所谓视锥拣选（frustum culling）的观念来将视线范围之外的雪花全都弃之不理，进而提升程序执行的效能。没错，八叉树其实就是视锥拣选的一种应用。
  在使用视锥拣选时，我们可以检验3D 空间中的“点”、“圆形”或“正立方体”是否在我们的观察视锥（viewing frustum）中。而在“November Days DEMO”中，只用到了其中的圆形检测。你或许会想，那一个高度图（heightmap）的地形场景，也可以用一般的视锥拣选来处理测试啊？是的，我们可以将场景中的所有三角形都拿来测试是否存在我们的视线中；只是如果这样做的话，恐怕和直接将所有三角形画出，所得到的效能是一样的。何不想想，有没有方法一次就可以检测“一整个范围”内的所有三角形？如此就仅需要数十次的测试，就能够决定出谁是该画出的三角形，而谁是不该画出的。
  八叉树的技术就因此而生了。其实八叉树的前身也是已经流传已久的技术，就是所谓的四叉树（Quadtree）。如果了解四叉树的原理，就可以轻易的学会八叉树的观念了。先把概念缩减到二维的空间中，举个简单的例子：试想在一个有限范围的平面上有数万个“点”，我们有一个二维的照相机（camera）在其中游走（与三维照相机的观念类似，只是少了一个维度的考量），而我们不想一次画出这数万个点，只想画出在照相机视线之内的点。该如何做？当然你可以用之前提到的方法，一个点一个点的来做测试。只是如果能够一次测试一个范围内的所有点，或许会是比较好的方法。如何做？就是使用所谓的“空间分割”。把平面割成几个大小范围，如此一来，我们就只需要对这些范围的值和照相机的视线做测试；如果你的视线看不到某个“空间范围”，自然也一定看不到该范围内的任何“点”，也就自然无须费心把那些点画出来。四叉树基本的概念正是如此。将空间分割成几个部分，分别对这些空间做测试，如果在视线之内的话，就把该空间内的所有物体画出。八叉树就是把这概念衍生到三维的空间中罢了。我知道这些概念性的说明，还没有办法帮助你建立起完整的八叉树观念，其中还有需多细节，例如：该怎么切比较公平？要切出几个空间比较合适？在此我就不一一说明了，在文章最后我会列出几个国外网站的八叉树介绍文章，相信能够更加详细且正确的帮助你了解八叉树的架构与观念。

  还有一点要先声明的，这个演示的程序代码，并不是由我自己创造出来的，而是参考使用了“GameTutorials”网站中，一系列有关八叉树的演示所写出来的。并且做了一些修改与调整，使整个程序的结构能够更适用于使用高度图的地形场景“GameTutorials”网站所提供的三个八叉树演示都相当的优秀，是我曾看过的八叉树相关程序中，程序架构写得最好的，真的非常值得一看。


2、具体的代码（Code Stuff）
  在建构八叉树的开始时，需要先取得场景的维度大小，这样才能确定我们所将切割的空间刚好能满足这个区域范围，而不是太大或太小。所以在InitSceneSize()的过程中，把高度图（heightmap）的所有三角形坐标都传入函数，分别计算出x、y、z 方向的最大值；然后我们再取出其中最大的值，当作八叉树初始空间的尺寸大小。也就是说，我们所决定的八叉树所形成的空间，其实是一个正立方体。接着算出这个场景的中心点，并以此中心点为基准来做之后的空间切割。而整个八叉树的重点就是在于CreateSceneNode()函数的工作。因为这个函数要负责分割空间、并建立八叉树八个相对应的子节点（node）。每一次“分割”的动作，就等同于将该范围的空间切成“八等份”。要把一个正立方体所形成的空间分成等份的八块，其实很容易也很直觉；但我们往往会发现到，只将场景的空间做出一次的分割是不够的；往往需要数次的分割才能达到良好的效果。难的地方在于我们要如何决定应该分割几次？如何让分割的动作依照某种形式自动执行下去？在此我们设立了两项阈值参数（threshold）来确立八叉树的分割能够恰如其份的如我们所预期。
  一是每个节点三角形的最大量（Number of maximum triangles per node）：每一个节点的空间范围最多可以容忍多少个三角形在其中？如果该空间中的三角形总数超过这个阈值，则我们应该再把此空间做一次“分割”的动作，切成更小的八等份。
  二是细分处理的最大量（Number of maximum subdivisions）：我们允许“分割”这个动作执行几次？以目前的分割次数来与这个值比较，如果目前分割的次数还没到达阈值，我们就需要继续分割下去。
  因此，这两个参数值的决定，就确定了我们最终的八叉树将会切割成多少个子节点。我们以上述的方法来控制八叉树子节点的建立；若从程序的观点来看，我们是使用递归程序（recursive）的方法来实现（implement）这样的一个函数，使其有效的利用相同的程序代码来执行重复性的动作。在执行演示时，就可以清楚看到这两项信息的数值，并且能够透过按键来实时修改该数值。同时可以从画面中“NodeCount”的数值了解到，改变这两个数值，将会影响最后建立的子节点个数。而主要的Render()绘图函数同样是利用递归程序（recursive）的方法，画出八叉树所有节点中的三角形。只是在画出之前多了一个步骤，也就是视锥拣选的测试：使用“正立方体”的测试方法来检验该节点的空间范围，是否存在我们照相机的视线当中。若存在视线之中，则继续往下测试该节点的八个子节点，直到确认该节点为leaf node 为止（也就是没有子节点），就可以画出该空间内的所有三角形；若不存在视线之中，则无须做任何动作。因此在演示的执行过程中，移动鼠标或方向键，就可以看到画面中“NodeDrawn”的数值因此而增加或减少，也就是代表目前所画出的节点（node）总数了。
  整个程序的主要架构就是如此了。而为了看清楚八叉树所做的空间分割结果，所以除了GLoctree 对象类别所做的主要工作之外，还多了一个GLoctreedebug 的对象类别来负责显示一些网格线，用以表示八叉树所分割建立的空间。另外，这个演示中的另一个重点是如何把场景的三角形数据做出最佳化的处理；解决方法可能不止一种，在此我只用了最容易的显示列表（display list）方法来包装顶点及纹理的信息，就已经可以获得很不错的效能了；如果还能更进一步加上顶点数组（vertex array）的最佳化，还有再更加提升效能的可能性。

foreverzzu

学习一下

myonkyo

不错啊，谢谢分享！