论文部分内容阅读
[摘要]随着计算机科学、计算机图形学和地理信息系统的迅速发展，三维数字地形图的研究与实现成为人们研究和关注的热点，基于四叉树、八叉树、KD树的LOD模型技术，针对大数据量三维地形图建立不同细节层次的模型和优化其模型算法进行可视化表达又成为要研究关键技术。
[关键词]LOD模型 四叉树 八叉树 KD树 三维地形 可视化
[中图分类号] P217 [文献码] B [文章编号] 1000-405X（2014）-6-115-2
1引言
随着现代科学技术的迅猛发展，传统的二维地形图已远远地落后于人们对现实世界的认知需要，也满足不了现代经济建设与国防建设的要求。人们需要的是高精度的、信息丰富的三维数字地形图。在三维数字地形图可视化过程中，利用基于四叉树、八叉树、KD树形成的LOD细节层次技术是非常必要的，本文主要研究的是LOD模型对可视化表达的优化。
所谓的LOD建模，其实质就是采用一定的算法思想将原有的网格地形数据进行重组，得到一种更加便于实时绘制使用的数据结构。使用LOD模型实现简化的基本原理是：物体绘制前，根据不同的控制误差δi提前生成若干个不同分辨率的简化模型，即金字塔模型，在绘制时，根据物体距離视点的位置d，用户允许的屏幕误差ρ计算实际物体的最大允许误差δmax，即：
然后在多个简化模型中选择δi<=δmax且与δmax最相近的简化模型。当视点位置变化时重新计算δmax并选择相应的简化模型进行绘制。模型简化的两个准则：一是顶点最少，二是误差最小。
2四叉树LOD模型
树形结构一般都会存在着一个突出的问题就是：相邻树形结构的层次差别太大时，就会产生裂缝；另外一个问题就是：生成的模型面结构或者线结构比较多且复杂，地图渲染和显示速度比较慢。四叉树LOD模型主要解决便是以上两个突出问题。
基于四叉树的LOD算法以四叉树为基础通过递归分割生成层次化的连续地形网格，以此为基础生成地表。在三维仿真系统中，对地形的视觉效果产生影响的主要因素是地表上点到视点的距离和地表的起伏程度。对于地表仿真来说，越是靠近视点的节点细分层次越深，而越是远离视点的节点细分层次越浅。在离视点距离相同的情况下，在地形起伏较大的地方，需要细化节点层次；反之，在地形平坦的地方，较粗的网格就可以将地形描绘出来。
在基于LOD的地形生成算法中，裂缝问题往往是不可避免的，Geomipmapping算法也是如此。在该算法中，当两个相邻块的细节层次级别不一致时，就会产生裂缝，这是由于其相接处的边界上顶点的不完全一致造成。解决裂缝问题的方法通常有两种：一种方法是在较少细节块的相应位置上增加一个顶点，；另一种方法是在较多细节的块上将引起裂缝的顶点删除。相比较而言，第二种方法实现起来更加简单有效。
3八叉树LOD模型
八叉树同样也存在四叉树的两个问题，但是也不能得到很好的解决，本文只是在原有传统八叉树的基础上进一步优化。本文将LOD技术和八叉树相结合，提出了深度八叉树的概念，应用于大规模三维数据体快速体绘制中。为了与深度八叉树相区别，本文将传统的八叉树方法称为广度八叉树。
3.1广度八叉树与深度八叉树
广度八叉树的逻辑结构：令U是一个可以存储某长方体的空间且大小一定，其值为s；V为一个要表示三维数据体，其长、宽、高分别为m，n，k，它的八叉树逻辑结构可以用如下的递归方法来定义：设函数f表示一个体数据所需的空间大小，如果f（V）≤s，那么V的八叉树仅有树根，如果f（V）>s，则将V等分为八个子体Vi（i=0，1，2，3，4，5，6，7），只要f（Vi）>s，就要被8等分，从而对应的节点也就有了8个子节点，这样地递归判断、分割一直要进行到节点所对应的子体f（Vi）≤s。图1是一个深度为3的广度八叉树。内存和磁盘是海量数据处理需要重点考虑的两个层次，八叉树存放于内存，而节点对应的文件存放于外存。用广度八叉树来实现大规模数据场的存储，可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。
深度八叉树与广度八叉树最主要的区别是：广度八叉树只有叶子节点对应一个磁盘文件，而深度八叉树每个节点都对应一个磁盘文件。深度八叉树将体数据分割成若干小体，每一次分割，都是将每一个子体分成8个等份。分割完成后所得到的八叉树的每一个节点对应一个磁盘中的文件，且文件大小相同。
从叶子节点开始，每个节点对应的磁盘文件所存储的数据如下：
（1）叶子节点对应的文件与广度八叉树的完全相同。
（2）每个叶子节点的父节点对应的文件都是由其子节点按X，Y，Z三个方向进行2-抽稀（即每间隔一个点取值）后合并生成，每个子节点经过2-抽稀后大小是原来叶子节点文件大小的1/8，8个子节点合并后得到的文件与子节点对应的文件大小相同。
（3）以此类推，得到全部非叶子节点所对应的文件。图2为一个三层深度八叉树的逻辑和存储结构。
File0，File1到File8经抽稀处理后得到File64；
……
File56，File57到File63经抽稀处理后得到File71；
File64，File65到File71经抽稀处理后得到File72；
共有（8n-1）/7个文件，其中n为八叉树的深度。
3.2八叉树LOD模型的实现
3.2.1数据的表示与组织
基于深度八叉树的分割方法中，LOD处理过程主要是对三维数据体的抽稀，在三维坐标轴的每个方向上应用2-抽稀，总层数N的计算公式为：N=[log8VV0]其中：V为三维数据体字节数，V0为一次适度载入数据的字节数。对三维数据体进行绘制，需要对子体进行编码，从而建立起子体之间的空间关系，便于定位，避免复杂的查找过程。数据编码如下： [LevelNum][XCode][YCode][ZCode]
其中：LevelNum代表该子体所处的细节层次，XCode、YCode和ZCode分别表示在该层内按照X、Y和Z方向的编码。通过对编码分别加1或减1，便可以确定同一层上邻接的子体编码。
3.2.2数据的表示与组织
数据表示与组织展示如下表所示。
八叉树的效果展示如图3所示。
4KD树LOD模型
KD树主要解决的是数据的简化和可视化的加速优化。
KD树LOD模型设计：
本文算法可视化的对象是不规则的点云和由其生成的TIN，算法分两阶段：（1）离线多分辨率层次点云数据的生成；（2）实时的基于视点点云和三角网的更新及可视化。算法本阶段将点云数据划分为若干个近似方块，再分别对各个块内的点云进行KD树分层，然后存入到外存的一个文件中。
KD树是一种由二叉树推广而来的用于多维检索的树的结构形式，它与二叉树不同的是它的每个结点表示k维空间的一个点，并且每一层都根据该层的分辨器对相应对象做出分枝决策。对于不规则的点云，KD树有以下优点：按层分出的数据更能体现地形的趋势；完全平衡树；在空间剖分的灵活性和平衡性上有很大优势。当然，KD树也有它的缺陷，如在配合使用纹理数据方面比较复杂。另外，本文对KD树进行两点改进：不严格交替按x、y方向划分空间，而是按照当前空间内的长轴划分。改进后剖分出的区域更加集中，更能体现点云的趋势。
（1）简化视见体
关键技术主要包括：1）基于视点的实时更新三角形。算法对三角形的更新使用的不是Hoppe的压缩和分裂操作，而是Oscar的方法：①层次地构建Delaunay三角网的算法；②内存中保存各层次三角网的拓扑结构数据，来实现基于视点的实时更新三角网的功能。2）三角网条带化。一般情况下，要绘制n个三角形，需要提供3n个顶点，但如果将三角形如下条带化，则只需要n+2个顶点。三角网条带化，可以减少将近2/3的顶点的开销，可以粗略认为GPU提高到原来3倍的速度。
（2）OpenGL加速
在三角形条带或三角形扇的基础上增加了顶点数组缓冲区对象（VBO）的使用。1）三角形条带。绘制一个三角网，如果它包含n个三角形，使用一般的方法，就需要给图形硬件传输并让其对3n个顶点进行各种运算；而将三角形条带化了，只需要n+2个顶点被传输和进行运算。2）顶点数组缓冲区对象。即使顶点数据不变，使用传统的顶点数组（VA）仍需不断从内存向图形硬件传输相同的数据。使用顶点数组缓冲区对象，可将顶点等数据存储在图形硬件中，在重复渲染顶点时将能获得较好的性能。其效果如图4所示：
5结语
本文通过LOD模型研究了一个应用于具有大量网格数据筛选简化技术。要保证三维数字地形图实时交互显示的质量，为物体提供不同的LOD描述是控制场景复杂度以及加速图形绘制速度的非常有效方法，它可根据一定的判断标准判断物体的重要等级，采取相应不同的处理，重要性较高的显示较多的细节，相反，重要性较低的显示较少的细节。LOD技术已成为近年来研究的热门课题，国内外专家学者提出了不同的解决方案和模型算法，但应用于三维地形显示却存在—些问题。其一，三维地形图数据量大，传统LOD算法生成LOD模型的速度较慢，满足不了实时、交互的需要；其二，三维地形图在动态显示时，交互的过程中同一区域在不同时刻，或者同一时刻的不同区域，往往会有不同的精度要求，这样就满足不了实际要求。随着计算机及图形处理设备性能的不断提高，LOD算法的不断优化，数字地形图的三维可视化技术正向着实时动态显示、交互式控制、具有高度真实感的场感画面显示等方向发展。
参考文献
[1]黄霆，赵红武.动态LOD四叉树虚拟地形绘制[J].武汉科技大学，2010（3）.
[2]姚定忠，何军，刘袆.一种基于KD树的实时大规模地形可视化算法[J].华南理工大學，2012.
[3]邹承明，李引，陆苑，陈金锐.基于四叉树的动态LOD虚拟地形优化[J].武汉理工大学，武汉钢铁（集团）公司，2009（9）.
[4]别玉玉.基于四叉树LOD技术绘制大地形的改进算法[J].中国矿业大学，徐州，2010.
[5]原庆红，韩燮.基于视点的分块LOD大规模地形生成算法研究[J].中北大学，2011.
[6]MarKD.ROAMingTen'ain：Real-timeOptimallyAdaptingmeshes[C].Proc.Visulaization，1997：81-88.
[关键词]LOD模型 四叉树 八叉树 KD树 三维地形 可视化
[中图分类号] P217 [文献码] B [文章编号] 1000-405X（2014）-6-115-2
1引言
随着现代科学技术的迅猛发展，传统的二维地形图已远远地落后于人们对现实世界的认知需要，也满足不了现代经济建设与国防建设的要求。人们需要的是高精度的、信息丰富的三维数字地形图。在三维数字地形图可视化过程中，利用基于四叉树、八叉树、KD树形成的LOD细节层次技术是非常必要的，本文主要研究的是LOD模型对可视化表达的优化。
所谓的LOD建模，其实质就是采用一定的算法思想将原有的网格地形数据进行重组，得到一种更加便于实时绘制使用的数据结构。使用LOD模型实现简化的基本原理是：物体绘制前，根据不同的控制误差δi提前生成若干个不同分辨率的简化模型，即金字塔模型，在绘制时，根据物体距離视点的位置d，用户允许的屏幕误差ρ计算实际物体的最大允许误差δmax，即：
然后在多个简化模型中选择δi<=δmax且与δmax最相近的简化模型。当视点位置变化时重新计算δmax并选择相应的简化模型进行绘制。模型简化的两个准则：一是顶点最少，二是误差最小。
2四叉树LOD模型
树形结构一般都会存在着一个突出的问题就是：相邻树形结构的层次差别太大时，就会产生裂缝；另外一个问题就是：生成的模型面结构或者线结构比较多且复杂，地图渲染和显示速度比较慢。四叉树LOD模型主要解决便是以上两个突出问题。
基于四叉树的LOD算法以四叉树为基础通过递归分割生成层次化的连续地形网格，以此为基础生成地表。在三维仿真系统中，对地形的视觉效果产生影响的主要因素是地表上点到视点的距离和地表的起伏程度。对于地表仿真来说，越是靠近视点的节点细分层次越深，而越是远离视点的节点细分层次越浅。在离视点距离相同的情况下，在地形起伏较大的地方，需要细化节点层次；反之，在地形平坦的地方，较粗的网格就可以将地形描绘出来。
在基于LOD的地形生成算法中，裂缝问题往往是不可避免的，Geomipmapping算法也是如此。在该算法中，当两个相邻块的细节层次级别不一致时，就会产生裂缝，这是由于其相接处的边界上顶点的不完全一致造成。解决裂缝问题的方法通常有两种：一种方法是在较少细节块的相应位置上增加一个顶点，；另一种方法是在较多细节的块上将引起裂缝的顶点删除。相比较而言，第二种方法实现起来更加简单有效。
3八叉树LOD模型
八叉树同样也存在四叉树的两个问题，但是也不能得到很好的解决，本文只是在原有传统八叉树的基础上进一步优化。本文将LOD技术和八叉树相结合，提出了深度八叉树的概念，应用于大规模三维数据体快速体绘制中。为了与深度八叉树相区别，本文将传统的八叉树方法称为广度八叉树。
3.1广度八叉树与深度八叉树
广度八叉树的逻辑结构：令U是一个可以存储某长方体的空间且大小一定，其值为s；V为一个要表示三维数据体，其长、宽、高分别为m，n，k，它的八叉树逻辑结构可以用如下的递归方法来定义：设函数f表示一个体数据所需的空间大小，如果f（V）≤s，那么V的八叉树仅有树根，如果f（V）>s，则将V等分为八个子体Vi（i=0，1，2，3，4，5，6，7），只要f（Vi）>s，就要被8等分，从而对应的节点也就有了8个子节点，这样地递归判断、分割一直要进行到节点所对应的子体f（Vi）≤s。图1是一个深度为3的广度八叉树。内存和磁盘是海量数据处理需要重点考虑的两个层次，八叉树存放于内存，而节点对应的文件存放于外存。用广度八叉树来实现大规模数据场的存储，可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。
深度八叉树与广度八叉树最主要的区别是：广度八叉树只有叶子节点对应一个磁盘文件，而深度八叉树每个节点都对应一个磁盘文件。深度八叉树将体数据分割成若干小体，每一次分割，都是将每一个子体分成8个等份。分割完成后所得到的八叉树的每一个节点对应一个磁盘中的文件，且文件大小相同。
从叶子节点开始，每个节点对应的磁盘文件所存储的数据如下：
（1）叶子节点对应的文件与广度八叉树的完全相同。
（2）每个叶子节点的父节点对应的文件都是由其子节点按X，Y，Z三个方向进行2-抽稀（即每间隔一个点取值）后合并生成，每个子节点经过2-抽稀后大小是原来叶子节点文件大小的1/8，8个子节点合并后得到的文件与子节点对应的文件大小相同。
（3）以此类推，得到全部非叶子节点所对应的文件。图2为一个三层深度八叉树的逻辑和存储结构。
File0，File1到File8经抽稀处理后得到File64；
……
File56，File57到File63经抽稀处理后得到File71；
File64，File65到File71经抽稀处理后得到File72；
共有（8n-1）/7个文件，其中n为八叉树的深度。
3.2八叉树LOD模型的实现
3.2.1数据的表示与组织
基于深度八叉树的分割方法中，LOD处理过程主要是对三维数据体的抽稀，在三维坐标轴的每个方向上应用2-抽稀，总层数N的计算公式为：N=[log8VV0]其中：V为三维数据体字节数，V0为一次适度载入数据的字节数。对三维数据体进行绘制，需要对子体进行编码，从而建立起子体之间的空间关系，便于定位，避免复杂的查找过程。数据编码如下： [LevelNum][XCode][YCode][ZCode]
其中：LevelNum代表该子体所处的细节层次，XCode、YCode和ZCode分别表示在该层内按照X、Y和Z方向的编码。通过对编码分别加1或减1，便可以确定同一层上邻接的子体编码。
3.2.2数据的表示与组织
数据表示与组织展示如下表所示。
八叉树的效果展示如图3所示。
4KD树LOD模型
KD树主要解决的是数据的简化和可视化的加速优化。
KD树LOD模型设计：
本文算法可视化的对象是不规则的点云和由其生成的TIN，算法分两阶段：（1）离线多分辨率层次点云数据的生成；（2）实时的基于视点点云和三角网的更新及可视化。算法本阶段将点云数据划分为若干个近似方块，再分别对各个块内的点云进行KD树分层，然后存入到外存的一个文件中。
KD树是一种由二叉树推广而来的用于多维检索的树的结构形式，它与二叉树不同的是它的每个结点表示k维空间的一个点，并且每一层都根据该层的分辨器对相应对象做出分枝决策。对于不规则的点云，KD树有以下优点：按层分出的数据更能体现地形的趋势；完全平衡树；在空间剖分的灵活性和平衡性上有很大优势。当然，KD树也有它的缺陷，如在配合使用纹理数据方面比较复杂。另外，本文对KD树进行两点改进：不严格交替按x、y方向划分空间，而是按照当前空间内的长轴划分。改进后剖分出的区域更加集中，更能体现点云的趋势。
（1）简化视见体
关键技术主要包括：1）基于视点的实时更新三角形。算法对三角形的更新使用的不是Hoppe的压缩和分裂操作，而是Oscar的方法：①层次地构建Delaunay三角网的算法；②内存中保存各层次三角网的拓扑结构数据，来实现基于视点的实时更新三角网的功能。2）三角网条带化。一般情况下，要绘制n个三角形，需要提供3n个顶点，但如果将三角形如下条带化，则只需要n+2个顶点。三角网条带化，可以减少将近2/3的顶点的开销，可以粗略认为GPU提高到原来3倍的速度。
（2）OpenGL加速
在三角形条带或三角形扇的基础上增加了顶点数组缓冲区对象（VBO）的使用。1）三角形条带。绘制一个三角网，如果它包含n个三角形，使用一般的方法，就需要给图形硬件传输并让其对3n个顶点进行各种运算；而将三角形条带化了，只需要n+2个顶点被传输和进行运算。2）顶点数组缓冲区对象。即使顶点数据不变，使用传统的顶点数组（VA）仍需不断从内存向图形硬件传输相同的数据。使用顶点数组缓冲区对象，可将顶点等数据存储在图形硬件中，在重复渲染顶点时将能获得较好的性能。其效果如图4所示：
5结语
本文通过LOD模型研究了一个应用于具有大量网格数据筛选简化技术。要保证三维数字地形图实时交互显示的质量，为物体提供不同的LOD描述是控制场景复杂度以及加速图形绘制速度的非常有效方法，它可根据一定的判断标准判断物体的重要等级，采取相应不同的处理，重要性较高的显示较多的细节，相反，重要性较低的显示较少的细节。LOD技术已成为近年来研究的热门课题，国内外专家学者提出了不同的解决方案和模型算法，但应用于三维地形显示却存在—些问题。其一，三维地形图数据量大，传统LOD算法生成LOD模型的速度较慢，满足不了实时、交互的需要；其二，三维地形图在动态显示时，交互的过程中同一区域在不同时刻，或者同一时刻的不同区域，往往会有不同的精度要求，这样就满足不了实际要求。随着计算机及图形处理设备性能的不断提高，LOD算法的不断优化，数字地形图的三维可视化技术正向着实时动态显示、交互式控制、具有高度真实感的场感画面显示等方向发展。
参考文献
[1]黄霆，赵红武.动态LOD四叉树虚拟地形绘制[J].武汉科技大学，2010（3）.
[2]姚定忠，何军，刘袆.一种基于KD树的实时大规模地形可视化算法[J].华南理工大學，2012.
[3]邹承明，李引，陆苑，陈金锐.基于四叉树的动态LOD虚拟地形优化[J].武汉理工大学，武汉钢铁（集团）公司，2009（9）.
[4]别玉玉.基于四叉树LOD技术绘制大地形的改进算法[J].中国矿业大学，徐州，2010.
[5]原庆红，韩燮.基于视点的分块LOD大规模地形生成算法研究[J].中北大学，2011.
[6]MarKD.ROAMingTen'ain：Real-timeOptimallyAdaptingmeshes[C].Proc.Visulaization，1997：81-88.