基于改进型四叉树算法的室外大规模场景实时渲染

基于改进型四叉树算法的室外大规模场景实时渲染 第 27卷第 9 期 计算机应用 Vo l. 27 No. 9 2007年 9 月Comp u te r App lica tion s Sep. 2007 ( ) 文章编号 : 1001 - 9081 2007 09 - 2095 - 02 基于改进型四叉树算法的室外大规模场景实时渲染 1 1 2万旺根 ,周俊玮 ,唐经洲 ( ) 1. 上海大学 通信与信息工程学院 ,上海 200072; 2. 南台科技大学 电子工程系 ,台湾 73502634 ()wanwg@ staff. shu. edu. cn 摘 要 :在大规模场景渲染过程中 ,场景中节点的存储 、查找 ,以及视域剔除是影响渲染速度的重 要因素 。采用一种改进型四叉树算法存储和查找顶点 ,采用迭代算法替换了原有的递归生成算法 ,利 用该四叉树算法实现了射线检测和视域剔除 。实验结果表明 ,该方法能够有效提高室外场景的渲染 帧数 ,利用它在视域剔除上能发挥本身的层次特性和编码的有序性优点 ,可以避免和减少视域剔除算 法中大量直线与面相交的计算 ,提高视域剔除算法的效率 。 关键词 :四叉树 ;场景管理 ;迭代算法 ;视域剔除 中图分类号 : TP301. 6文献标志码 : A Rea l2t im e ren der in g of 3D la rge2sca le scen e ba sed on im proved qua d tree a lgor ithm 1 1 2WAN W ang2gen, ZHOU J un2we i, TAN G J ing2zhou (200072, Ch ina; S hangha i U n iversity, S hangha i 1. S chool of C omm un ica tion and Inform a tion Eng ineering, )2. D epa rtm en t of E lectron ic Eng ineering, S ou thern Ta iw an U n iversity of Technology, Ta iw an 73502643, Ch ina A b stra c t: The sto rage, look2up and view fru stum cu lling of node s in 3D scene a re the key p rob lem s tha t affec t the rende ring effic iency in la rge sca le scene. The p ap e r in troduced an imp roved quad tree a lgo rithm to sto re and look up node s and p ropo sed an ite ra tive a lgo rithm in p lace of recu rsion a lgo rithm. A nd we imp lem en ted the rad ia l de tec tion and viewed fru stum cu lling ba sed on th is a lgo rithm. The exp e rim en ta l re su lts show tha t FPS is inc rea sed a lo t in th is way. The a lgo rithm fea tu re s in h ie ra rchy of itse lf and sequence of cod ing, wh ich avo id s la rge comp u ta tion in view fru stum cu lling a lgo rithm. Key word s: quad tree; scene m anagem en t; ite ra tive a lgo rithm; view fru stum cu lling () ,大规模室外场景 随着计算机数字媒体技术的广泛应用 间 如图 1所示 。将水帄面均匀划分成四个象限 且在树上 的每个非叶子节点处存储四 个数据元素 。每个 元素称 为 体 的实时渲染被运用到越来越多的领域中 ,随之出现的问题是 元 ,以该象限为水帄面的自下而上的柱面体三维空间称为体 如何有效解决场景的优化处理和实时管理 。传统的四叉树管 素 。在三维空间中 ,如果一个体素是空的 ,则该体元的类型用 理主要是应用在地形管理和地形渲染中 ,而室外场景管理主 “NULL ”表示 ,非空的体 素就以该体素中心为原点 再一次均 [ 1 ] 要是应用空间八叉树来实现 ,考虑到实际应用课题的特殊匀的划分成四个象限 ,这样就可以把三维空间中的所有模型 性 ,主要模型节点都位于水帄面附近 ,如果采用传统的八叉树 节点归属到四叉树的相应叶子节点上 。为了防止由于模型节 点过多造成四叉树划分过深的情况 ,我们需要在四叉树的层 进行场景管理将大大增加树节点的数量并不利于水帄面模型 次上做一些限制 。 节点的分布归属运算 ,本文提出了一种基于四叉树的对场景 中所有对象节点进行管理的有效方法 。该方法可以大大提高 节点的查找速度 。如果采用传统的场景节点以顺序方式存储 , 在需要查找顶点时 , 则需要按照顺序依次进行查找 , 帄均查找 ( ) () 长度为 n + 1/ 2 其中 n为顶点个数 , 这不利于大规模室外 场景的实时渲染 。 本文提出的基于四叉树管理的查找算法 , 帄均查找长度 为 logn。试验结果表明 , 与传统的图形顶点存储和查找方法 4 相比 , 采用该算法查找场景节点的速度和三维场景实时渲染 的帧数都能得到很大提高 。图 1 四叉树空间划分图 四叉树算法的特点是数据结构简单 ,集合运算容易 ,形体 1 四叉树的基本原理 上各元素已按空间位置排成了一定的顺序 ,容易找到其所在 四叉树不是对物体的描述 ,它是划分空间的一种方法 ,用 的空间位置 。当然分割的深度越大 ,查找节点的速度越快 ,但 这种方法可以高效地解决一定的渲染问题 。四叉树的分层树 是分割深度的增加会直接导致四叉树节点的指数级增加 ,而 结构将指定的三维空间区域按水帄面的四个象限分成四个空 ( ) ( ) 基金项目 : 信息产业部电子信息产业发展基金资助项目 2005688 ;上海市重点学科建设项目 T0102 。 收稿日期 : 2007 - 07 - 02。 ( ) ( ) 作者简介 :万旺根 1961 - ,男 ,江西南昌人 ,教授 ,博士 ,主要研究方向 : 虚拟现实 、数字媒体 、多媒体信号 ; 周俊玮 1982 - ,男 ,上海人 , ( ) 硕士研究生 ,主要研究方向 :数字媒体 、虚拟现实 ; 唐经洲 1964 - ,台湾台南人 ,教授 ,博士 ,主要研究方向 : 数据可视化 、虚拟现实 。 会超出程序员的控制并且对堆栈的需求也会超出可用栈空 [ 2, 3 ]数据结构 2. 1 的范 围 。以 一 个 满 的 8 层 深 度 的 四 叉 树 为 例 , 总 共 8 4= 65 536个构造函数 ,每个函数需要一次压栈操作 , 一次 本文提出的改进型四叉树算法是一种建立在传统四叉树栈操作 ,所以一共需要 2 ×65 536 = 131 072次堆栈操作 。这 算法的基础上 ,结合相关应用项目改进生成的一种改进的四 是仅限于 8层深度的树结构 ,如果树结构更深 ,那么操作数 叉树算法 ,该算法可以对室外场景很好地划分并封装 ,可以很 好地处理 3 . xm l格 式 的 模 型 文 件 , 室 外 场 景 通 过 算 法 处 理 成指数级放大 。后 ,生成如下的四叉树数据结构 Q uadTreeNode: 鉴于这种构造方法的一些弊端 ,本文采用迭代方法来 成整个树结构的生成 ,通过循环调用 ,自上而下地完成所有 C la ss Q uadTreeNode 叉树节点的生成 。如图 3 所示 ,首先根据场景中所有的模 { 节点确定根节点的范围 ,即确立一个立体空间把所有的模 in t index; 节点都囊括进去 ;然后循环调用节点构造函数 ,按照不同的 in t dep th; 点类型进行构造 。因为四叉树的层数已经固定 ,所以可以 in t w id th; 节点数量作为循环的条件 ,这样就可以用迭代的方法完成 po sition3D po sition; 来递归构造的过程 。虽然这样做使程序的复杂度上升 ,易 Q uadTreeNode 3 fa the r; 性也下降了 ,但是却可以避免大数量的堆栈操作和可能出 ch ild ren [ 4 ]; Q uadTreeNode 3 的堆栈溢出问题 ,对于用户来说可以有效地提高运行速度 M e sh m e sh [ n ]; / /成员函数 } () 其中 : index是树节点的序号 采用深度遍历排序 ; dep th描述 () 的是四叉树节点的深度信息 如图 2 所示 。根节点的深度 信息为 0 ,而它的四个子节点 ,也就是第一层的四个节点的深 度信息为 1,以此类推 。深度信息的主要作用是程序对树结 构的深度进行实时检测 ; po sition主要 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 的是四叉树节点所 在空间位置的中 心点 , 而 w id th 记录的是中 心点到空间边界 的位置 。由于空间是一个以水帄面为基准面的自下而上的立 体空间 ,所以利用一个中心点坐标 ,一个距离值就能完全还原 () 该立体空间 ; fa the r记录的是该节点的父节点 如图 2 所示 。 第一层节点的父节点就是根节点 ,第二层节点的父节点是第 一层的某个子节点 ,除了根节点外 ,所有的节点都应该有一个 父节点 ; ch ild ren记录以本节点为父节点的 4 个子节点 ,叶子 节点无子节点 ; m e sh 是叶子节点特有的成员变量 ,记录该叶 子节点所包围立体空间中的所有模型节点 。 图 3 四叉树构造函数流程 3 基于改进型四叉树的场景管理 3. 1 面向四叉树的射线检测 图 2 四叉树节点层次图 [ 4, 5 ]构造函数 2. 2 传统的四叉树构造函数主要采用递归方法 ,该算法一般 可以描述为 : ( )Func tion n { / /相关操作 ( )Func tion n - 1 2113 第 9期 解成俊等 :基于分段可逆矩阵变换的超光谱图像无损压缩算法 IEEE Tran sac tion s on Geo science s and R emo te Sen sing, 2000 , 38 ( ) 果表明 , 无 损 压 缩 性 能 略 好 于 3D 2CD F 2 , 2 DW T, 远 好 于 () 1 : 416 - 428. J PEG2L S、W inZip、ARJ、D PCM、中国科学院一小组 、NM ST、M ST 杜振洲 ,周付根. 基于帧间去相关的超光谱图像压缩方法 [ J ]. 红 [5 ] 的结果 。() 外与激光工程 , 2006 , 33 6 : 642 - 645. 参考文献 :张培强 ,柴焱 ,张晓玲 ,等. 基于波段分组的 3D 2SP IH T高光谱图 [ 6 ] [ 1 ] 王晋 , 张晓玲 ,沈兰荪 ,等. 一种基于网格编码量化的高光谱图 ( ) 像无损压缩算 法 [ J ]. 中 国 图 象 图 形 学 报 , 2005 , 10 4 : 425 - () 像无损压缩方法 [ J ]. 中国图 象图 形学报 , 2006 , 11 1 : 123 -430. 127. 马晨光 ,郭雷. 基于 3 维 SP IH T编码的超光谱图像压缩 [ J ]. 量子 [ 7 ] () 电子学报 , 2005 , 22 5 : 682 - 684. () [ 2 ] 张雷 ,黄廉卿. 超光谱数据压缩技术 [ J ]. 红外 , 2005 , 1 : 9 - 12.李永峰. 遥感卫星高光谱图像压缩编码方法研究 [D ]. 西安 : 西 R YAN M J , ARNOLD J F. The lo ssle ss comp re ssion of AV IR IS im 2 [ 3 ] 安电子科技大学 , 2004. [ 8 ] age s by vec to r quan tiza tion [ J ]. IEEE Tran sac tion s on Geo science s 刘恒殊. 超光谱遥感图像压缩算法的研究 [D ]. 长春 : 长春光学 () and R emo te Sen sing, 1997 , 35 3 : 546 - 550. 精密机械与物理研究所 , 2002. [ 9 ] DRA GO TT I P L , PO GG I G, RA GO Z IN I A P R. Comp re ssion of [ 4 ] m u ltisp ec tra l im ages by th ree2d im en siona l SP IH T a lgo rithm [ J ]. ()上接第 2096页 待处理的模型对象及其部位 ,面向四叉树的射线检测主要解 表 1 两种算法之间的对比 决的是射线和包围盒的 求交问题 。整个检 测过程可以 采 用 顺序查找 四叉树 提高 测试内容 管理 / F 管理 / F 效率 / % 图 4中的步骤 。首先计算射线和四叉树子节点的相交情况 , 321 878 个面 、106 个节点 24 41 70. 8 如果不相交则放弃遍历以该节点为根节点的整个子树 ,如果 57 83 45. 6 147 152 个面 、57 个节点相交则继续遍历直到叶子节点为止 ,遍历至叶子节点后顺序 156 185 18. 6 25 272 个面 、12 个节点遍历该叶子节点包含的所有模型包围盒 ,得出检测结果 。 [ 6 ] 3. 2 摄像机视椎体裁减 从测试结果可以看出 ,在面数和节点相同的情况下 ,相对 由于整个室外场景是摄像机视椎体中所有模型的透视投于一般的顺序查找算法 ,利用本文所提到的改进型四叉树算 影 ,所以处于视椎体之外的所有模型将不出现在用户的视野 法在渲染帧数上有较大提高 。比较三次测试结果不难发现 , 中 。因此 ,为了提高场景渲染速度 ,我们可以把摄像机视椎体 在节点越多 ,面数越多的场景中 ,应用改进型四叉树管理后 , 以外的所有模型节点在渲染前进行事先剔除 ,不将它们送入 显示帧数的速率提高表现得更加明显 。因此我们不难得出这 渲染管道 ,避免不必要的渲染流程 。整个流程与射线检测相 似 ,首先判断四叉树子节点是否处于视椎体内 ,如果不处于内 样的结论 ,在大规模室外场景实时渲染中 ,利用四叉树算法将大大提高显示效率 ,减少了 GPU 开销 。该算法的主要优点就 部则放弃遍历以该节点为根节点的整个子树 ; 如果处于内部 是将四叉树划分方法合理地应用到室外场景管理过程中 ,有 则继续遍历直到叶子节点为止 ,遍历至叶子节点后顺序遍历 效地提高了射线检测和视域剔除的效率 ,改进了原有的树节 该叶子节点包含的所有模型包围盒 ,得出需要渲染的所有模 点递归生成算法效率 ,减少了堆栈的运算和使用 ,既符合工程 型 。 开发流程 ,也减少了场景调入等待的时间 。该算法可以作为 场景管理模块添加到 3D 室外场景渲 染引擎中 , 有 效提高引 擎对复杂室外场景的渲染效率 ,增加引擎的实用性 。4 实验结果 参考文献 : 根据 本 文 提 出 的 方 法 , 在 VC. N ET 的 编 译 环 境 下 使 用 D irec t3D 渲染某大规模场景 ,按照四叉树进行分块 ,并使用视 [ 1 ] TORBOR G J G. D isp lay techn ique s fo r oc tree2encoded ob jec ts [ J ]. () 锥体剔除技术使得渲染速度有了明显提高 。渲染效果如图 5 IEEE Comp u te r Grap h ic s & App lica tion, 1981 , 1 3 : 29 - 38. PAJAROLA R. O ve rview of quad tree2ba sed te rra in triangu la tion and [ 2 ] 所示 。 visua liza tion [ EB /OL ]. [ 2007 - 03 - 10 ]. h ttp: / /www. ifi. uzh. ch / vmm l / adm in / up load /UC I2ICS202 201. p df. PAJAROLA R , SA IN Z M , CON FETT I G . O b jec t 2 sp ace po in t [3 ] b lend ing and sp la tting [ J ]. IEEE Tran sac tion s on V isua liza tion and () Comp u te r Grap h ic s, 2004 , 10 5 : 598 - 608. GRO SS M H , STAAD T O G, GA TT I G. Effic ien t triangu la r su rface [ 4 ] app roxim ation s u sing wave le ts and quad tree data struc tu re s [ J ]. IEEE Tran sac tion s on V isua liza tion and Comp u te r Grap h ics, 1996 , () 2 2 : 130 - 143. CHAN Y K, CHAN G C C. A n effic ien t da ta struc tu re fo r sto ring [ 5 ] sim ila r b inary im age s [ C ] / / P roceed ings of the F ifth In te rna tiona l 图 5 复杂室外场景渲染效果 ( )Conference on Foundation s of D a ta O rgan iza tion FODO π98 . Ko2 ( 实验帄台 : In te l双核 2. 4 GH z, Q uad ro FX 3450 256 MB be: [ s. n. ] , 1998: 268 - 275. ) ( ) ) ( 显存 , DDR II 667 1 GB ×2, WD120 GB 7 200转 。 下面我[6 ] GOV INDARAJU N K, SUD A , YOON S E, et a l. In te rac tive visi2 们对大规模室外场景进行渲染 ,用顺序查找管理 b ility cu lling fo r comp lex environm en ts u sing occ lu sion2sw itches[ C ] 和四叉树管理两种方法做比较实验 ,在测试帄台相同的情况/ / P roceed ings of the 2003 Sympo sium on In te rac tive 3D Grap h ic s. 下得到的测试结果如表 1所示 。Mon te rey: [ s. n. ] , 2003: 103 - 112.