叉树就是把这概念衍生到三维的空间中罢了。
我知道这些概念性的说明,还没有办法帮助你建立起完整的八叉树观念,其中还有需多细节,例如:该怎么切比较公平?要切出几个空间比较合适?在此我就不一一说明了,在文章最后我会列出几个国外网站的八叉树介绍文章,相信能够更加详细且正确的帮助你了解八叉树的架构与观念。
还有一点要先声明的,这个演示的程序代码,并不是由我自己创造出来的,而是参考使用了“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)的最佳化,还有再更加提升效能的可能性。
使用可变四叉树建立连续 LOD 场景网格 目 录 1 问题 2 网格 原 文:Continuous LOD Terrain Meshing Using Adaptive Quadtrees 译 者:Glflush_CN 版 本:to be continue....
上一篇:
传智播客_PHP程序员笔记第二天
下一篇:
马原:环境保护与可持续发展论文(word)