基于四叉树的LOD算法实现.ppt

Page ? * 一种基于自适应动态四叉树的实时连续LOD模型生成算法 所谓的LOD建模,其实质就是采用一定的算法思想将原有的网格地形数据进行重组,得到一种更加便于实时绘制使用的数据结构。 Lindstrom提出的基于四叉树的实时连续LOD动态生成算法就是一种典型的实时LOD生成算法。 在利用四叉树方法进行LOD建模的过程中, 其关键就在于怎样对原有的网格数据进行四叉树分层。 四叉树分层方法是: 从整个完整的地形出发,递归的把地形不断的分割( Sub-divide)成相等的四个区域,分割的深度越大,则得到的分辨率越高。如图所示是一个地形的四叉树表示,图中每一个正方形为四叉树的一个节点。每个节点保存了一定区域的信息包括: 经纬度,中心点的高度,边节点的高度等。 地形四叉树表示 在进行四叉树分层的过程中需要注意以下几点: 首先,由于四叉树分层是针对(2?＋1)×(2?＋1)的规则网格而言的,所以我们所采用的数据格式应尽量满足(2?＋1)×(2?＋1)的规则网格的要求,即网格数据必须是一间隔均匀的正方形区域。如果网格数据的大小不满足该条件,则需要扩展其几何图形,让其大小尽可能接近(2?＋1)×(2?＋1),扩展部分的像素用空值填充。 其次，四叉树中相邻的两个节点的层次最大不能相差1,否则在LOD模型连续拼接的地方就会出现裂缝。 其基本思路是: 先把地形一分为四,用递归的方法对每个网格渲染。对每个网格,如果达到最高精度,则退出; 如果不在视野内,也退出。再对符合条件的网格递归下去。 所以针对以上基于四叉树构建LOD模型算法，具有可以改进优化的方面主要集中在以下几点： 在对地形节点进行分析判断是否需要进一步细化划分方面（节点评价机制）； 将地形节点往四叉树结构存储和高效访问方面； 为了实现当视点较远时, 分辨率较低, 当视点较近时, 分辨率较高这个特性而产生的动态误差问题； 消除由于相邻的网格因分割的程度不同而产生的裂缝问题； 综上问题我提出了：一种基于自适应动态四叉树的实时连续LOD模型生成算法 把整个地形作为根结点，然后从根结点出发判断其是否满足某种分割条件，若不满足则不分割并作为叶子结点保存；否则把根结点递归地不断分成相等的4个子结点区域，直到不能再分割为止，最后将所有叶子结点绘制渲染形成简化结果。 分割的深度越大，得到的分辨率就越高，分割时使用结点评价函数对每个行结点进行评价，如果该点精度已经符合结点评价函数的要求，则不再进行分割，否则继续分割直到该结点符合结点评价函数的要求为止。 传统的四叉树分层结构 四叉树存储和访问机制 快速访问四叉树结点的基本思想是将存储DEM （数字高程模型，是用一组有序数值阵列形式表示地面高程的一种实体地面模型）数据的四叉树结点用 一维数组来表示 。主要用两种方法来提高四叉树结点的访问效率 , 其中一种是四叉树结点数据在 一维数组中的存储方式 ,另外一种则是访问四叉树结点数组的方式 。 四叉树结点的存储方式 首先将二维的DEM转化为一维方式组织，其基本原理是 : 先将数据空间划分成大小相同的网格 ,再根据一定的方法将这些网格编码 , 使得每一个网格的标号是唯一识别的 ,并能在一定程度上保持空间邻近性 ,即相邻网格的标号也相邻 ,以便使一个空间对象由一组网格组成 。 再次，考虑到四叉树结点的存储顺序通常用 二维空间填充曲线的方法来确定 , 因为 二维空间填充曲线不仅可以保证遍历空间中的每个数据点 , 而且填充曲线局部区段内的数据点在空间分布上也是相邻的 。 我这里采用著名的希尔伯特空间填充曲线来组织四叉树结点 ,因为希尔伯特值的排序能很好地反映空间邻近性 ,如图给出了用希尔伯特空间填充曲线组织 DEM数据的初始几步网格顶点的索引号 。 DEM数据经过希尔伯特空间填充曲线组织后 , 它自顶向下 ,由粗到细地将各个分辨率的四叉树结点存储到了一个一维数组中 , 这种方法实际上是把单一分辨率的数据变换到多分辨率数据后再进行排序 , 这在3维地形数据的可视化中是一种十分有效的数据组织方式 ,其使用户能够方便地访问四叉树结点数据 四叉树结点的访问方式 四叉树结点访问有隔层四叉树和嵌入四叉树两种常用的方式 。 我在这里利用隔层四叉树来快速访问四叉树结点数据的实现方法 。 隔层四叉树是指在地形网格由粗往细的剖分过程中 , 把地形网格按层次分为白色四叉树和黑色四叉树两种 , 而且每种均为一棵完全的四叉树 。 这种黑白隔层表示顶点的方式是利用四叉树的编码 ,并根据父子结点关系推导出顶点索引号