rame 不可见, 那么该 Node 代表的整个子树都被拣选(Cull)掉。
如果 Leaf.VisFrame 不可见, 那么 Leaf 中的所有 Polygon 都被拣选(Cull)掉 RenderSubModels... // 渲染场景中活动的部分 for i 1ilt NumOfModelsi if Modeli.VisFrame 可见 绘制 Modeli RenderActors... // 渲染所有的人物 for i0igtNumOfActorsi Actori的 AABB 的 Center 所在的 Leaf 如果可见 绘制 Actori的 PolygonList,否则不绘制。
因为 Actor 不会同时属于两个 Area,所以只要找到 Actor 的 Center 所在的 Leaf 是否可见就可以判断 Actor 是否可见了。
现在有些游戏使用其它的组织方法,比如 Oni 中就使用了八叉空间分割树(Octtree),比起二叉树、Portal 技术由很大的优势,在 2000 年游戏开发者年会中“Hidden Surface Reduction and Collision Detection Based on Oct Trees”一文(pease.doc)就比较详细的介绍了 Bungie 公司的这个方法,我觉得很值得一试。
我在看了 peace.doc 以后决定采用 oni 的做法,使用他们介绍的那种八叉树+光线追踪(Raycasting)的组织结构。
因为在思考二叉树+Portal 的引擎时有很多问题难以解决,我觉得难点在于构造含有 Portal 的二叉树结构,地图编辑器很难做,Genesis3D 的源代码并不包含地图编辑器的部分,所以你无法得知它是如何构造它的二叉树的。
给出一个静止的场景部分,划分二叉树并不难,但是如果你希望能够构造含有 Portal 的 region 就比较麻烦了。
1)首先,基本上不太会有一个 Leaf 恰好等于一个 region,实际划分可能出现一个 Leaf 与若干 region 相交,我最 如果一个 Leaf 属于某一个 region,后的结论是可以用以下规则来划分, 那么该 Leaf 就不用再划分了,如果它与 n 个ngt1个 region 相交,那么就要将该 Leaf 继续划分下去。
如此应该可以保证每个 Leaf 一定属于某个 region,那么在渲染的时候,只要找到照相机所在的 Leaf 就可以通过该 Leaf 上记录的 region 索引,找到所需处理的 region 了(Genesis3D里面的 Leaf 结构就可以找到他所谓的 Area)。
如果是这种思路,那么下面问题就必须要解决。
2)Region 如何识别或者划分,计算机自动(不太可能,这种 region 的概念完全是人定的),手工识别(如何手工识别,在一个复杂的场景中选择一个个面,然后还必须构成封闭的空间才能定为 region,这样恐怕也不现实)我还想过,所有的模型都有 3DS MAX 来做, (比如一个房间) 我们自己做一个工具去识别包围该 region 每次美工确保做一个 Region ,的多面体,还必须能够手工加少数辅助对该 region 进行 Portal 的指定和识别,然后在地图编辑器中仅仅导入这样的结构,构造实际场景的时候只是设定一下 region 的位置,然后对于每个 Portal 设定他们指向的 region 代号。
看似可行,但是实际上识别或者指定 region 和 portal 真的是很困难的,至少是非常复杂的事情。
每当你想到一点做法,还会发现对其它的一些问题解决不方面,一直找不到关于划分 region,设定 Portal 的文章,所以我觉得做一个二叉树+Portal的引擎,在地图编辑器方面就难以完成。
在 vanly 的 ftp 上面有 Quake 引擎的分析,他们的做法是将场景划分成二叉树以后,对于每个 Leaf 都预先算好它的 PVS。
在渲染的时候,找到照相机所在的 Leaf,然后查表得到预先算好的该 Leaf 的 PVS,然后再绘制 PVS 中的 Leaf。
这里它没有介绍如何计算这个 PVS,而且它如何压缩使得巨大的 PVS 表格只变成 20K 也没有说。
还有它并没有考虑会开关的 Portal。
所以我感觉还是没有什么进展。
最后只有 oni 的八叉树+光线追踪还算有希望,他不需要将处于切分平面上的物体分割,而且不要指定 region 和portal,对于美工建模来说限制很少,可以自由发挥,对于程序来说,地图编辑器因为不要什么识别功能,只要根据现有的数据划分出八叉树就可以了,负担也比较轻,只是它的消隐过程麻烦一些,也有些缺陷,但是感觉代价比二叉树+Portal 要低,至少我们感觉基本可以实现,而二叉树+Portal 的引擎还没什么好的解决方法。
实战八叉树场景拣选例程目 录 1 原理与声明 2 具体的代码 八叉树的程序 八叉树(Octree)是一种空间分割(Space Partitioning)的技术,用来将 3D 空间中的物体做出空间性的区隔与分割。
有了八叉树的技术之后,就可以“选择性”的画出空间中某个区域的物体,减少送入 OpenGL 管道线做渲染的三角形信息量,进而大幅的提升复杂场景的执行效能。
在这个演示程序中,实际应用八叉树分割一个高度图(heightmap)所建构的地形场景;并且可以运行时(runtime)调整八叉树的相关参数值,显示出不同的空间分割结果。
1、原理与声明(First Concept amp Assertion) 什么是八叉树?正如前言所提到的:八叉树是一种空间分割(Space Partitioning)的技术。
为什么需要分割、需要八叉树呢?当我们建立起一个由数万个三角形所组成的复杂场景之时,若想实时(real-time)的绘出整个场景的话,恐怕在目前的平价显示卡上,都难以得到平顺流畅的绘图结果;也就是说在这种情况下,会大幅度的降低程序的执行效能。
想象一下,如果我们能够只画出我们视线范围内“看得见”的场景,而不用去理会其它就算画出来也看不见的场景;如此一来,就可以避免画出场景后 FPS 值却惨不忍睹的局面。
如果你有看过之前“November Days DEMO”的原理解释,就不难发现这个想法(idea)其实似曾相识。
也就是在处理雪花的过程中,有用到了所谓视锥拣选(frustum culling)的观念来将视线范围之外的雪花全都弃之不理,进而提升程序执行的效能。
没错,八叉树其实就是视锥拣选的一种应用。
在使用视锥拣选时, 我们可以检验 3D 空间中的“点”、 (viewing frustum) “圆形”或“正立方体”是否在我们的观察视锥中。
而在“November Days DEMO”中,只用到了其中的圆形检测。
你或许会想,那一个高度图(heightmap)的地形场景,也可以用一般的视锥拣选来处理测试啊?是的,我们可以将场景中的所有三角形都拿来测试是否存在我们的视线中;只是如果这样做的话,恐怕和直接将所有三角形画出,所得到的效能是一样的。
何不想想,有没有方法一次就可以检测“一整个范围”内的所有三角形?如此就仅需要数十次的测试,就能够决定出谁是该画出的三角形,而谁是不该画出的。
八叉树的技术就因此而生了。
其实八叉树的前身也是已经流传已久的技术,就是所谓的四叉树(Quadtree)。
如果了解四叉树的原理,就可以轻易的学会八叉树的观念了。
先把概念缩减到二维的空间中,举个简单的例子:试想在一个有限范围的平面上有数万个“点”,我们有一个二维的照相机(camera)在其中游走(与三维照相机的观念类似,只是少了一个维度的考量),而我们不想一次画出这数万个点,只想画出在照相机视线之内的点。
该如何做?当然你可以用之前提到的方法,一个点一个点的来做测试。
只是如果能够一次测试一个范围内的所有点,或许会是比较好的方法。
如何做?就是使用所谓的“空间分割”。
把平面割成几个大小范围,如此一来,我们就只需要对这些范围的值和照相机的视线做测试;如果你的视线看不到某个“空间范围”,自然也一定看不到该范围内的任何“点”,也就自然无须费心把那些点画出来。
四叉树基本的概念正是如此。
将空间分割成几个部分,分别对这些空间做测试,如果在视线之内的话,就把该空间内的所有物体画出。
八
上一篇:
传智播客_PHP程序员笔记第二天
下一篇:
Function GetIp(IP) 获得ip asp