第 30卷第 1期2010年 1月计算机应用Journal of ComputerApplicationsVol . 30 No. 1Jan. 2010文章编号: 1001 - 9081 (2010) 01 - 0047 - 03基基于于深深度度八八叉叉树树的的三三维维数数据据场场 LOD可可视视化化马晓晨1, 2,孔小利2(1.天津大学 机械工程学院 ,天津 300072;2. 承德石油高等专科学校 计算机与信息工程系 ,河北 承德 067000)(maxiaochen@ sina. com)摘摘要要 :提出了广度八叉树 、 深度八叉树概念 ,分析了它们逻辑结构和存储结构三维数据场可视化,探讨了这两种数据结构在三维数据场可视化中的应用 ,把深度八叉树应用于三维数据场 LOD 体绘制算法中 。算法在某三维震波数据场进行了体绘制实验 ,并与传统方法进行了比较分析 。结果表明 ,该方法通过逐层简化细节来减少场景的复杂性 ,提高了渲染效率 ,将全局和局部体绘制相结合 ,既提高了绘制速度 ,又实现了精细观察。关键词关键词 :广度八叉树 ;深度八叉树 ;细节层次;体绘制 ;三维数据场中图中图分分类号类号 : TP391文文献标志码献标志码 :A3D data set LOD visualization based on depth2oct2treeMA Xiao2chen1, 2, KONG Xiao2li2(1. School of M echanical Engineering, Tianjin University, Tianjin 300072, China;2. Departm ent of Com puter and Infor m ation Engineering, Chengde Petroleum College, Chengde Hebei 067000, China)Abstract: This paper put forward the concepts of breadth2 oct2tree and depth2 oct2tree.and storage structures, which were applied in 3D data set visualization. Depth2 oct2tree was used in LOD volume renderingalgorithm which was tested on a sismic wave data set . Compared with the traditional method, the new algorithm was muchfaster . On the contrary, the traditionalmethod cannot be applied in PCs due to the large amount of ti me and space required.The results indicate that the new method can improve the performance of volume rendering . Especially, combining the wholeand part volume rendering method, the speed was higher and more elaborated observation was achieved.Key words: breadth2 oct2tree; depth2 oct2tree; LevelOf Detail (LOD); volume rendering; 3D data setIt analyzed their logic structures0 引言随着数据采集技术的快速发展 ,震波 CT、 工业 CT等三维数据越来越精细 ,其体数据也越来越大 ,有的数据体达到几吉字节 、 十几吉字节 ,甚至几十吉字节 ,给大规模三维数据体快速可视化技术带来了难题 ,尤其是基于微机的大规模数据场快速可视化 ,在传统方式下几乎难以实现 ,因此对数据进行预处理是实现快速可视化的前提。

近几年 ,人们针对大规模三维数据场体绘制技术研究了很多方法 ,文献 [ 1 ]提出的动态纹理载入的方法和文献 [ 2 ]提出的半自适应分块的方法更多地依赖纹理体绘制进行快速体绘制 ,由于受硬件纹理空间大小的限制 ,基于纹理的体绘制方法无法有效地针对超大规模的体数据 ,将数据块多次从系统缓存中载入到纹理 内存直接影响了大规模 体数据绘制的速度 。文献 [ 3 ]提出的基于矢量化压缩的方法虽然提高了大规模数据的体绘制速度 ,但针对超大规模数据场 ,如 10 GB 以上的数据场 ,此方法也很难实现快速体绘制 。大规模三维数据场的体绘制要求必须对空间数据进行分割等预处理 ,这主要是由于一方面尽管目前计算机的性能有较大的提高 ,但对于大规模数据场的可视化而言 ,内存容量 、 计算和绘制性能仍然是非常有限的 ,不可能将海量的空间数据一次性从外存读入进行处理 ,而必须是分块调度 ;另一方面是根据人眼在观察事物时的规律 ,对较远处的场景人眼能够获得的信息相对较少 ,而随着距离的拉近 ,对细节的观察越来越详细 ,因此对远近不同的场景可以采用不同的“ 粒度 ” 进行描述 ,这就是细节层次(LOD )方法的基本原理 。

LOD 技术最早是在 1976 年由 C la rk提出 , 1992年后 ,国内外学者相继提出了许多 LOD 模型的生成算法[ 4 ]。在三维数据 处理中八叉树是传统的且 效果较好的数据结构 ,因此在超大规模三维体数据处理过程中 ,应用八叉树对数据进行分解 ,按需要分级导入 ,可以实现对大规模三维数据局部进行快速可视 化[ 5 ]。但是当需要对全 局或者对超过计算机容量的较大局部进行概览和分析时 ,此方法无法实现 ,因此需要应用 LOD 技术 。本文将 LOD 技术 和八叉树相结合 ,提出了深度八叉树的概念 ,应用于大规模三维数据体快速体绘制中 ,为了与深度八叉树相区别 ,本文将传统的八叉树方法称为广度八叉树。1 广度八叉树与深度八叉树1. 1 广度广度八八叉树叉树广度八叉树的逻辑结构令 U 是一个可以存储某长方体的空间且大小一定 ,其值为 s, V 为一个要表示三维数据体 ,其长 、 宽 、 高分别为 m , n, k, 它的八叉树逻辑结构可以用如下的递归方法来定义 :设函数 f表示一个体数据所需的空间大小 , 让八叉树的每个节点与 V的一个子体对应 ,如果 f (V) ≤ s,那么 V的八叉树仅有树根 ,如果 f(V)> s,则将 V等分为八个子体 Vi( i = 0, 1, 2,收收稿稿日期日期: 2009 - 06 - 17;修修回回日日期期 : 2009 - 08 - 17。

第 30卷第 1期2010年 1月计算机应用Journal of ComputerApplicationsVol . 30 No. 1Jan. 2010基基金金项目项目:河北省自然科学基金资助项目 (602405) ;中国石油天然气集团公司石油科技中青年创新基金资助项目 (05E7048)。作作者者简介简介:马晓晨 (1968 - ) ,男 ,河北保定人 ,教授 ,博士研究生 ,主要研究方向:三维可视化、 智能诊断;人 ,教授 ,博士 ,主要研究方向:虚拟现实。孔小利 (1962 - ) ,男 ,天津蓟县48计算机应用第 30卷3, 4, 5, 6, 7) ,每个子体与树根的一个子节点相对应 ,如图 1。图 1子体的 8等分只要 f (Vi) > s,就要被 8等分 ,从而对应的节点也就有了8个子节点 , 这样地递归判断 、 分割一直要进行到节点所对应的子体 f (Vi) ≤ s。广度八叉树的存储结构按照此八叉树逻辑结构 ,可以将体数据分割成若干小体 ,每一次分割 ,都是将每一个子体分成八个部分 。 最终得到一棵满八叉树 ,分割完成后所得到的八叉树的每一个叶子节点对应一个磁盘中的文件 ,图 2是一个File64, File65到 File71经抽稀处理后得到 File72;共有 (8n- 1) /7个文件 ,其中 n为八叉树的深度。

2 广度八叉树的应用当一个大规模三维数据场的数据远大于计算机内存的容量时 , 计算机已经不能对三维数据体实现较为正常和全面的可视化功能 ,更不用说快速可视化了 。 因此 ,将大规模三维数据场分割存储以及合理调度是可视化工作必要的前提 , 应用广度八叉树可以较好地解决这个问题 。 按照本文广度八叉树的定义 ,首先确定可以存储某长方体的空间 U,其大小为 s,这里 s即为当前计算机实现快速调度的内存块的大小 , 因此 s是根据不同计算机的内存大小而不同 ,根据 s的大小 ,可以计算所需广 度 八 叉 树 的 深 度 , 八 叉 树 的 深 度 要 满 足 公 式(d - 1)深度为 3的广度八叉树。内存和磁盘是海量数据处理需要重点考虑的两个层s ×8≥m × n × k × p,其中 d为八叉树的层数 , p为数据场次[6 ],八叉树存放于内存 ,而节点对应的文件存放于外存。 用广度八叉树来实现大规模数据场的存储 , 可以看成是四叉树方法在三维空间的推广 , 也可以认为是用三维体素阵列表示形体方法的一种改进。图 2广度八叉树1. 2深度八深度八叉叉树树深度八叉树与广度八叉树最主要的区别是 : 广度八叉树只有叶子节点对应一个磁盘文件 , 而深度八叉树每个节点都对应一个磁盘文件。

深度八叉树的逻辑结构与广度八叉树相同。 深度八叉树的存储结构按照此八叉树逻辑结构 ,可以将体数据分割成若干小体 ,每一次分割 ,都是将每一个子体分成 8个部分 ,即一个子体被 8等分 。 最终得到一棵满八叉树 ,分割完成后所得到的八叉树的每一个节点对应一个磁盘中的文件 ,且文件大小相同。图 3深度八叉树的逻辑结构从叶子节点开始 , 每个节点对应的磁盘文件所存储的数据如下 :1) 叶子节点对应的文件与广度八叉树的完全相同。2) 每个叶子节点的父节点对应的文件都是由其子节点按 X , Y, Z三个方向进行 22 抽稀 (即每间隔一个点取值 ) 后合并生成 , 每个子节点经过 22抽稀后大小是原来叶子节点文件大小的 1 / 8, 8个子节点合并后得到的文件与子节点对应的文件大小相同。3) 以此类推 ,得到全部非叶子节点所对应的文件。图 3为一个三层深度八叉树的逻辑和存储结构。File0, File1到 File8经抽稀处理后得到 File64;⋯ ⋯File56, File57到 File63经抽稀处理后得到 File71;48计算机应用第 30卷0体素所需要的内存空间大小。 令 L = m ×n ×k ×p/s,则有 :d ≥ log (L /8) + 1为了实现每次对子体进行 8等分 ,需要 m, n, k分别满足 被2 ( d - 1) 整除 ,如果不能满足 ,可以对原始三维数据体填充 空体元 ,适当增加 m , n, k的值 ,得到 m ′ , n′ , k′ ,使得 s(d - 1) ≥ m′ ×n′ ×k′ ×p。

当八叉树的深度为 d时 ,数据场被分割为个(8点 , 即 8n- 1) /7子体 , (8n- 1) /7个节点 ,其中包括 8d- 1个叶子节d - 1个分割文件 。 当进行局部体绘制以及和切片可视化和表面建模时 , 可以应用广度八叉树进行调度 , 根据需要读入所需数据。3 深度八叉树的应用大规模三维数据体可视化是实际应用中的一个重要研究问题 ,实时性要求三维场景能够以很高的帧速率按照用户的交互指令动态显示 。但是海量数据和复杂的运算对体绘制速度造成很大影响 ,为了达到较高真实感的三维可视化 ,即便是最高端的图形工作站也不能满足实时绘制的需求 ,必须采用一些算法来改进和加速绘 制过程[ 7 ]。本文应用了 深度八叉树实现了大规模三维数据体的 LOD体绘制。3. 1 数据三维数据场有结构化和非结构化等不同的数据结构数据的的表示与表示与组组织织[ 8 ],常用的结构化数据结构主要包括正方形网格结构 、 矩形网格结构 、 不规则结构等 ,由于规则排列的正方形网格除了每个网格点处的属性值以外 ,只需要记录一个起算点的位置坐标和网格间距 ,因此存储量很小 ,适合于大规模的使用和管理 。由于采用网格数据结构 ,数据的分

来源【首席数据官】，更多内容/合作请关注「辉声辉语」公众号，送10G营销资料！