3D引擎场景管理

3D 引擎场景管理 我认为对于一个 3D 引擎来说，最核心的部分应该算是场景组织（scene graph）了，如果这部分你都没有设计好， 那 么就别指望开发一个成熟的 3D 引擎了。为了开发 3d 引擎，所以我首先就研究这方面的内容，对一个 3D 的场景来说， 又很多的物体，最简单的组织 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 就是把他们用一个 List 连接起来，然后在绘制没一帧的时候依次送入渲染器（render） 进行处理。 这显然不是一个很有效的方法，当处理一个普通的游戏场景都会显得非常慢的。实际上虽然一个场景中的物品很多， 但是通常可见的指是以小部分，如何能够用很小的计算代价排除那些不可见的物品呢，这种方法叫做剔除隐藏面，减少 绘制元素（Hidden Surface Complexity Reduction）。为了实现这样的方法，牵涉到空间排序（Spatial Sorting），最基本的 方法要算二叉空间分割树（BSP）了，DOOM 是第一个使用了二叉树的商业游戏。二叉树的构造简单地说就是对于要处理 的一组对象，选择一个平面，将该组对象分成两组（如果由某个对象与该平面相交则用这个平面将这个对象分成两个对 象）作为该结点的两个儿子，然后分别对两组对象用相同的方法，直到满足一个特定的条件（通常是到结点上只有一个 对象）为止。 二叉树确实是一种很有效的场景组织结构，因为，当给出视锥（view frustum）以后，在穿过（traverse）这棵树的 时候，如果发现视锥（frustum）与结点所代表的平面不相交，那么这个结点上有一棵子树必然不可见,那么这个子树就 不用送入渲染器了，当遇到 Leaf 的时候，就可以获得所需的多边形数据，可以送入渲染器处理。 虽然二叉树已经是非常有效的方法，但是仅仅依靠二叉树还是不能满足游戏的要求，因为现在的游戏的场景是在是 很大很复杂，又很多的物品，按照二叉树的方法凡是与 view frustum 相交的 Leaf 必然要送入渲染器，因为 view frustum 是很大的，所以会有很多的 Leaf 与他相交，这就意味着渲染器还是要处理很多的数据，如果你确实能够看到这么多的 物体，那也没有办法，但是通常，比如很多室内的场景，虽然在你的 frustum 里面会由很多物体，但是你真正能够看到 的还是很少的一部分，比如一个封闭的房间。 因此被称为 Portal 的技术被引入到游戏中来，之所以能够使用 Portal 技术，那是因为很多室内场景自身的限制条 件所致。我们引入 region 的概念，一个 region 就是一个相对封闭的空间，比如一个房间，region 与 region 之间都是 通过 Portal（比如门或窗）相连接，因此，如果你处于一个 region 当中，你就只能看到这个 region 中的物体，如果你 能够看到其他 region 中的物体，那么你一定是通过 Portal 看到的，所以处理的过程如下（考虑 Portal 是单向的情况， 如果两个 region 可以通过一个门相互看到，我就是用两个单向的 Portal）。 void CRegion::Draw(LPRender lpRender_) { if (m_bVisited) return; // 防止两个相邻的 region 的 Portal 形成死循环 m_bVisited = TRUE; for (int i=0;i< m_NumOfPortals;i++) { if (m_aPortals[i].m_bOpen) { // 如果 Portal 在 view frustum 中 if (!lpRender->Cull(m_aPortals[i])) m_aPortals[i].m_pRegion->Draw(lpRender_); } m_apObjects->Draw(lpRender_); } m_bVisited = FALSE; } 通常我们使用二叉树的方法来组织 region，理想的情况下每个二叉树树的 Leaf 就是一个 region，通过二叉树的遍 历可以很容易的找到照相机（camera）所在的 region。不过我觉得实际做场景的时候不会这么理想，因该是一个 region 可能被划分成了几个 leaf，不过只要保证每个 leaf 一定属于某个 region，我们就可以对每个 leaf 增加一个 region 的 引索（index），同样可以很方便的找到所在的 region。 Portal 引擎的一个不太好的地方就是，你必须手动设定许多 Portal，设计场景的会有一些限制，否则得不到很好 的效果。在了解了这些技术以后我又去看了“Genesis3D”的源代码，只看了场景组织的部分，我先把我的理解说一下。 Trace.h Trace.c vis.h vis.c world.h world.c Genesis3D 有如下几个概念： Model // Model[0]表示场景所有中不动的部分， // Model[i](i>0)表示场景中的活动物体（比如：门，升降台） // Model[0]对应一个二叉树 // Model 中还有 FirstLeaf，NumOfLeafs 来记录对应的 Leafs // Model 结构中有一个 int Area[2]的结构， // 对于本身是活动门的 Model，正好可以记录连通的两个 Area Cluster // 不敢肯定，推测是一种区域的概念，比 Area 要大 // 而且 Cluster 之间没有动态的连通关系，只有临街关系。 Area // 相当于我们上面所说的 Region 的概念， // Genesis3D 的一个场景中最多允许 256 个 Area， // 这可以从它的 world 结构中的 AreaConnection[256][256]看出， // 1 表示连通，0 表示不通 // Area 之间的连通性通过 Model[i](i>0)来控制 // int VisFrame 表示 Area 是否可见 Node // BSP 上的结点 // int VisFrame 表示 Node 是否可见 Leaf // 划分世界的二叉树的叶子， // 每个 Leaf 上都有一个 Area 的 index // 每个 Leaf 上都有一个 Cluster 的 index // 以及一个 Polygon List 的指针 Actor // 活动的人 因此我可以基本推断若干 Leaf 构成一个 Area，若干 Area 又可以构成一个 Cluster？（猜测）对于二叉树上的每个 Node 都设置了一个 VisFrame，用于判断是该结点代表的子树是否可见。我们可以看到它的渲染过程： RenderScene(...) { Vis_VisWorld(...); // 检测并设定可见性 RenderWorldModel(...); // Render 场景不动的部分就是 Model[0] RenderSubModels(...); // Render 场景中活动的部分 RenderActors(...); // Render 所有的人物 } 下面我们来分析每个过程： Vis_VisWorld(...) { 将所有的结点设置为不可见 // 它用的方法很巧妙，这个留给读者自己去看了 找到 Camera 所在的 Leaf，假设为 Leaf[E] Leaf[E].VisFrame=可见 Area[Leaf[E].AreaIndex].VisFrame=可见 // 通过一下这个递归过程设定所有 Area 的可见性 // 通过 AreaConnection[][]来判断， // 凡是跟 Area[Leaf[E].AreaIndex]能够连通的都设定为可见 // 具体方法比较简单，留给读者自己去看了 Vis_Flood_r(Area[Leaf[E].AreaIndex]) for (int i=0;i< Model[0].NumOfLeafs;i++) { // 我就是根据这里的顺序，推测 Cluster 是比 Area 更大的区域 // 否则就应该先判断 Area 了 if (Cluster[Leaf[E].ClusterIndex]与 Cluster[Leaf[i].ClusterIndex ]不相通) continue; // 如果 Leaf[i]所在的 Area 不可见，那么 Leaf[i]不可见 if (Area[Leaf[i].AreaIndex] != 可见) continue; Leaf[i].VisFrame = 可见 // 既然 Leaf[i]可见，那么 i 的所有父结点都应该可见， // 这个方法也很简单，留给读者自己去看了 MarkVisibleParents(i); // 下面的过程是将 Leaf 所包含的所有 surface 设定为可见 // 我不清楚他为什么要做这一步 ... } for (i = 1;i>NumOfModels;i++) { // 判断 Model[i]是否可见的方法是， // 求 Model[i]的 Axis-Aligned Bouding Box 的 Center // 遍历 Model[0]的二叉树，找到 Center 所在的 Leaf // 如果该 Leaf 可见，那么该 Model 可见 // 否则该 Model 不可见 if (ModelVisible(Model[i])) Model[i].VisFrame = 可见 } } RenderWorldModel(...); // 渲染场景不动的部分就是 Model[0] { 遍历 Model[0]对应的二叉树， 除了一般用 Frustum 来剪枝以外， 一旦发现 Node.VisFrame 不可见， 那么该 Node 代表的整个子树都被拣选（Cull）掉。 如果 Leaf.VisFrame 不可见， 那么 Leaf 中的所有 Polygon 都被拣选（Cull）掉 } RenderSubModels(...); // 渲染场景中活动的部分 { for (i = 1;i< NumOfModels;i++) { if (Model[i].VisFrame = 可见) 绘制 Model[i] } } RenderActors(...); // 渲染所有的人物 { for (i=0;i>NumOfActors;i++) { Actor[i]的 AABB 的 Center 所在的 Leaf 如果可见 绘制 Actor[i]的 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 相交，我最 后的结论是可以用以下 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 来划分，如果一个Leaf属于某一个region，那么该Leaf就不用再划分了，如果它与n个(n>1) 个 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 & 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）的最佳化，还有再更加提升效能的可能性。 使用可变四叉树建立连续 LOD 场景网格 目 录 1 问题 2 网格 原 文：Continuous LOD Terrain Meshing Using Adaptive Quadtrees 译 者：Glflush_CN 版 本：to be continue... 编辑手记：《雪域骑士 - Soul Ride》这是一个引人入胜的滑雪游戏，你可以由此想象一下那些景色迷人的滑雪胜地。 因为游戏中的场景完全依赖全球卫星系统提供的数据 资料 新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单 加以绘制，所以数千平方英里的滑雪场地会使你深深地沉浸其 中。最特别的是游戏中的滑雪路线是非线性的开放式地图，你可以向任意方向滑去。因此在这个游戏中赛道显示器就显 得更为吸引人了。 场景渲染一直是游戏编程世纪的热点。现在我们讨论一种十分有趣的场景技术，因为场景中的多边形的预算远远 超过硬件的实时的绘制能力，但是优秀的游戏引擎可以用 LOD 的方法适度的绘制场景中的多边形。当然，即使 LOD 可以 绘制相当大和复杂的场景，但却必须在这两者间调整，也就是场景面积和细致级别的矛盾。 Terrain rendering is a perennial hot issue in the world of game programming. Right now we're at a particularly interesting point in the development of terrain rendering technology, because polygon budgets have risen to the point where, in conjunction with real-time LOD meshing algorithms taken from published academic papers, state-of-the-art game engines are able to draw quite a bit of reasonably detailed terrain. However, the techniques which are currently in common use must compromise either on terrain size or on close-up detail. 在我现在开发中的游戏《雪域骑士》中，我在验证了大家都知道的算法以后，发展出了解决场景大小和细致级别的 方法。这篇文章就是讲解我的算法的。 As part of the R&D for Soul Ride, the game I'm currently working on HERE, I experimented with the published algorithms, and eventually came up with an extension that eliminates the tradeoff between terrain size and close-up detail. This article presents my algorithm, along with its similarities and differences from the above-mentioned algorithms. 我将从复习场景渲染的问题开始，并且回顾被［1］、［2］、［3］（文献）解决的问题。然后我解释我的算法解 决的问题。（此处略去作者自吹废话若干） I'll start by reviewing the problem of terrain rendering, and describe the problem solved by [1], [2], and [3] (see references at the end of this article). Then I'll explain the additional problem solved by my algorithm. I'll present a detailed description of the algorithm, and discuss some of the problems with it and some of the untapped potential. And last but not least, I'll provide the source code to a demo that implements my algorithm, which you can use to help understand it, evaluate its effectiveness, and incorporate directly into your own projects if you want. This article is not a general tutorial or review of terrain rendering. I'm going to assume some familiarity on your part with the problem. If things aren't making much sense, you may want to consult the excellent references listed at the end of the article. 1、问题（The Problems） 我们想从一个场景渲染器中获得什么？我们需要一个没有破裂和 T 错误的连续网格从眼前一直延伸到地平线。我们 希望在不惜声场景的细致级别的情况下获得更大的场景面积。我们希望从我们的脚下一直到遥远的山脉都有凹凸感。为 了讨论的方便，我们假设我的场景描绘能力的需求是从 1 米到 100000 米，很大吧？ What do we want from a terrain renderer? We want a single continuous mesh from the foreground all the way to the horizon, with no cracks or T-junctions. We want to view a large area over a large range of detail levels: we want to see the bumps in front of our feet to the mountains in the background. For the sake of discussion, let's say that we want feature size to range from 1m up to 100000m; five orders of magnitude. 我们怎样做？如果我们建立一个 100000*100000 的表格，每个用 16 位来存储高度值，然后就这样描绘出网格的话 （图 1），我们就会被两个大问题。第一，就是三角形的问题，每一帧需要让我们的渲染 API 绘制 20 亿的多边形，而现 在的绘制能力才开始超过每秒 1000 万。第二，就是内存问题，我们的高度值需要占用 20G 的空间，呵呵。 How can we do it? The brute-force approach won't work on ordinary computers circa Y2K. If we make a 100000m x 100000m grid of 16-bit height values, and just draw them in a mesh (Figure 1), we'll end up with two big problems.First, the triangle problem: we'll be sending up to 20 billion triangles/frame to our rendering API. Second, the memory problem: our heightfield will consume 20 GB of data. It will be many years before hardware advances to the point where we can just use brute-force and get good results. 图 1 Brute force approach to a heightfield mesh. 有许多得以有的方法可以解决三角形的问题。用得最多的算法就是使用递归算法（文献［1］、［2］、［3］）。 使用这样的算法我们可以使用很少的三角形显示出我们所需的场景（我将会翻译另外的文章讲解这些算法）。但是，我 们还有存储器的问题。 There are several previously-published methods which successfully tackle the triangle problem. The most widely used ones employ a clever family of recursive meshing algorithms [1], [2], [3]. Using one of these algorithms, we can effectively tame our mesh, and render a seamless terrain with a few thousand triangles, with the vertices intelligently selected on the fly from the 10 billion in the dataset. However, we still have a memory problem, since the heightfield dataset consumes 20 GB (plus some overhead to support the meshing algorithm). 一个明显的方法就是减少高度表的长度。1000*1000才是比较适合今天的计算机的能力的。最近的一个叫TREADMARKS 的游戏就是使用 1000*1000 数据集，效果相当的好［4］（文献），当然，1000*1000 距离 10 万*10 万还是有很大的差 距的。我们的目标是对场景的大小和可视距离没有限制，对前景的细致程度也没有限制。 One obvious solution is to compromise on detail by making the heightfield dimensions smaller. 1k x 1k is a good practical size for a heightfield with today's machines. A recently released game called TreadMarks uses a 1k x 1k dataset to excellent effect [4] (see references at the end of the article). Unfortunately, 1k x 1k is still a far cry from 100k x 100k. We end up having to limit either the size of the terrain and the view distance, or the amount of foreground detail. 我这里的解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 就是可变四叉树，用来代替 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的高度表，来表示场景的高度信息。使用这种四叉树，我们可以 在场景的不同的地方用不同的方法压缩高度数据。具个例子，在一个驾驶游戏中，你希望马路周围的场景十分的细致， 而你永远不会开到的地方就没有这样的必要（其实，大家看看就知道是这样了，但是，驾驶游戏的引擎的实现方法有很 多，这是其中一种，其实，LOD 不是最适合的方法）。 One obvious solution is to compromise on detail by making the heightfield dimensions smaller. 1k x 1k is a good practical size for a heightfield with today's machines. A recently released game called TreadMarks uses a 1k x 1k dataset to excellent effect [4] (see references at the end of the article). Unfortunately, 1k x 1k is still a far cry from 100k x 100k. We end up having to limit either the size of the terrain and the view distance, or the amount of foreground detail. The solution which I cover in this article is to use an adaptive quadtree, instead of a regular grid, to represent the terrain height information. Using this quadtree, we can encode height data at different resolutions in different regions in the terrain. For example, in a driving game, you would want lots of fine detail on and around the roads, ideally showing every bump, but you wouldn't need that much detail for the surrounding wilderness that you can't drive to; you only need enough detail for the general shape of hills and valleys. 这种四边形树也可以用来解决内存的问题。方法就是在粗糙的级别上预先定义场景的形态，然后在视觉图像生成时 计算机自动计算出良好的细致级别，而在不使用后，从内存中删除。 The quadtree can also be used for another attack on the memory problem: procedural detail. The idea is to pre-define the shape of the terrain at a coarse level, and have the computer automatically generate fine detail on the fly for the area immediately around the viewer. Because of the quadtree's adaptive nature, this detail can be discarded when the viewer moves, freeing up memory for creating procedural detail in a different region. 分开来讲，四叉树的两维可变表示法和四叉树的递归网格算法都是很有名的。（下面又略去作者的自夸若干，就是 自己可以…） Separately, the use of quadtrees for adaptive representation of 2D functions, and the use of quadtrees for recursive meshing [1], [3] are both well-known. However, [1] and [3] both use regular grids for their underlying heightfield representation. Extending their meshing approach to work with a true adaptive quadtree presents numerous complications, and requires some tricky programming. Hence this article and the accompanying demo code. 2、网格（Meshing） 网格有两个部分。我定义第一个部分为 Update()，另一个部分为 Render()，在 Update()期间，我们要决定哪些定 点要被包括在输出网格中。然后，在 Render()时，我们将生成包含这些定点的三角形网格。我们从一个极端简单的高度 表（3*3）开始（图 2）。在 Update()时，我们将观察每一个可选的顶点而决定是否把其包括到网格中。只有一个顶点 是“enabled”，我们才使用它来建立网格。 My meshing algorithm is based on [1], which has also influenced [2] and [3]. There are a few key modifications, but much of the basic approach is the same, and I borrow a lot of the [1] terminology. There are two parts to meshing. I call the first part Update() and the second part Render(), after [1]. During Update(), we'll decide which vertices to include in the output mesh. Then, during Render() we'll generate a triangle mesh that includes those vertices. I'll start by explaining Update() and Render() for an extremely simple heightfield: a 3x3 grid (Figure 2). To Update() it, we'll look at each of the optional vertices and decide whether to include them in the mesh. Following the terminology of [1], we'll say that if and only if a vertex is "enabled", then we'll use it in the mesh. 图 2 A 3x3 heightfield. Dashed lines and vertices are optional in an LOD mesh. 我们可以看到，这个简单的高度表的角和中心都是 enabled，所以现在就需要计算四个边上的四个顶点的状态，根 据一些 LOD 算法就可以算出。 Take as given that the center and corner vertices are enabled. So the task is to calculate the enabled state for each of the four edge vertices, according to some LOD calculation which takes the viewpoint and the vertex attributes into account. 在我们了解了哪些顶点是 enabled 之后，我们可以 Render()这个网格。这是非常简单的，就是连成三角形。参看图 3。 Once we know which vertices are enabled, we can Render() the mesh. It's easy; we just make a triangle fan with the center vertex as the hub, and include each enabled vertex in clockwise order around the outside. See Figure 3 for examples. 图 3 Examples of LOD meshes on the 3x3 heightfield. Disabled vertices in black. Continuous LOD Terrain Meshing Using Adaptive Quadtrees By Thatcher Ulrich Gamasutra February 28, 2000 URL: http://www.gamasutra.com/features/20000228/ulrich_01.htm Terrain rendering is a perennial hot issue in the world of game programming. Right now we're at a particularly interesting point in the development of terrain rendering technology, because polygon budgets have risen to the point where, in conjunction w