龚 俊，朱 庆，章汉武，李晓明，周东波

1.江西师范大学 地理与环境学院，江西 南昌330022；2.武汉大学 测绘遥感信息工程国家重点实验室，湖北武汉430079

基于R树索引的三维场景细节层次自适应控制方法

龚 俊1，朱 庆2，章汉武1，李晓明2，周东波2

1.江西师范大学 地理与环境学院，江西 南昌330022；2.武汉大学 测绘遥感信息工程国家重点实验室，湖北武汉430079

针对大规模三维城市建模需要，介绍一种基于三维R树索引的多细节层次（简称LOD）管理方法，从叶节点层向根节点自动生成LOD场景，并设计实现LOD检索的算法。通过试验分析，证明本文的LOD定义参数能够定量控制三维场景中的渲染目标数目，进而实现三维场景的自适应可视化方法，尤其适合于建筑物和树木类型的地物目标。

三维场景；R树；多细节层次；自适应

1 概 述

从20世纪80年代起，研究者从数据管理、LOD可视化乃至预测模型等多个角度对三维场景细节层次的自适应控制方法展开研究。文献［1］将复杂的建筑物场景以较小的独立空间单元进行管理，以帧率稳定为前提采用一种成本－贡献判据自适应地选择合适的离散多细节层次模型来绘制画面。文献［2］基于视点位置和图像空间误差实现对大规模地形数据的实时多细节层次控制。文献［3］则从连续LOD管理的角度提出自适应控制算法。

空间索引是提高空间数据管理效率的重要技术，R树是应用最为广泛的空间索引方法之一。R树扩展至三维空间后，节点重叠引发多路查询激增是效率低下的主要原因。通过改进节点选择和节点分裂，从而改善节点形状可以解决三维R树节点重叠严重问题［4］。为消除空间目标形态对索引效率影响，有研究者依据拓扑关系制定索引构建规则，对不规则三维目标切割成小目标，也可改善节点重叠现象，然而切割过程增加几何和语义维护成本［5］。文献［6］提出全局优化的节点选择和二分为三的节点分裂算法减轻节点重叠现象，三维空间聚簇性增强，三维R树树形更趋合理。良好树形使得R树的天然层次结构与多细节层次技术结合成为可能。

笔者从三维模型数据及其实时可视化需求入手，基于三维R树空间索引特点，提出一种管理和描述大规模多细节层次复杂场景的简便方法，可方便灵活地定量调整场景复杂度，实现三维场景细节层次自适应控制。

2 基于三维R树的多细节层次自适应控制方法

关于R树和多细节层次场景结合的已有研究均试图采用R树的天然层次结构实现目标查询和细节层次查询的双重功能［7－8］。已有研究应用R树节点包围盒作为低细节层次描述，忽略单个目标的LOD描述需求，也不能满足可视化精度要求。

2.1 多细节层次生成方法

传统R树索引方法仅在叶节点中管理目标模型，扩展结构使得中间节点也能管理目标模型。叶节点层管理全部和最精细的目标，从每个子节点按照某种规则挑选一个最有代表性的目标作为较粗层次目标模型集合存于父节点中，因此上层节点中的目标数目和子节点数目相等。举例说明，从每个子节点中选择一个最大高度的目标作为上层节点的目标，或者二维投影面积最大的目标。本文方法借助R树的层次结构，叶节点代表最高的细节层次，中间节点代表中等的细节层次，根节点代表最低的细节层次。

各层的适用范围须合理定义，保证在不同视场范围下可见的目标数目稳定在某个范围之内。以某个理想三维场景为例，即其中目标分布均匀，各层R树节点也分布均匀，保证视线竖直向下，寻找某个临界视点，如果提高视点将有部分区域采用下一细节层次表达，此时整个场景均采用最高细节层次表达，视点到视锥体边缘目标距离即最远视距约等于最高细节层次的最远距离d，采用相同方式寻找第二个临界视点，使得整个场景采用第二细节层次表达，此时最远视距约等于第二细节层次的最远距离D。R树的扇出（fanout）参数是节点包含的子节点数目，它是一个约束值，存在最小值m和最大值M，因此在某个区域内，相邻层的节点数目比值近似在1∶m～1∶M之间。根据本文方法，任意节点中的目标数目均满足扇出系数条件，因此各个节点中的目标数目大致相等。由于两个场景覆盖地域面积的比值为（D／d）2，而节点数目比值为1∶m～1∶M，因此要保证两个场景目标数目近似，则要满足m＜（D／d）2＜M，即因此相邻层的最远距离要满足等比关系，如果m＝4，M＝9，则2＜D／d＜3时，将能保证各种场景下目标绘制数目大致相等。

本文采用三个参数作为多细节层次定义参数，包括R树的层数LevelNum、最高细节层次的最远距离FarDist和相邻细节层次最远距离的比值DistFactor。假设R树有4层节点即Level－Num＝4，令FarDist＝500m，DistFactor＝2，则第一层的作用范围为0～500m，第二层的作用范围为500～1 000m，第三层的作用范围为1 000～ 2 000m，第四层的作用范围为2 000～4 000m（最后一层的最远距离也可设为无穷远）。

2.2 多细节层次场景的检索方法

多细节层次场景生成后，如何高效实现多细节层次检索成为本方法实用化的关键问题。多细节层次模型检索是一个与视点密切相关的功能。根据上节LOD参数定义方法，随视点变动三维场景也相应发生变化，远目标属于上层节点（甚至根节点）管理，近目标属于下层节点（甚至叶节点）管理，检索过程以根节点为入口，借助三维空间查询技术裁剪视场之外的节点和目标。本方法生成的场景效果是，全部场景均可见，视点近的区域目标密度高，视点远的区域目标密度低，符合人类视觉感知规律。以下是基于三维R树的多细节层次检索算法描述。

算法入口：视点和管理多细节层次场景的三维R树索引。

算法出口：待绘制的目标集合。

步骤1：设R树根节点为Node。

步骤2：判断Node（最小包围盒）与视锥体的空间关系。如果相离，终止该分支；如果被视锥体包含，进入步骤3；如果相交，进入步骤5。

步骤3：如果视距大于节点的细节层次作用范围，则终止该分支；如果视距落于节点的细节层次作用范围，则将节点中的目标全部加入目标集合，并终止该分支；如果视距小于节点的细节层次作用范围，则将该节点中的目标全部加入目标集合，并进入步骤4。

步骤4：循环访问各子节点（Child0，Child1，Child2，…），将子节点逐一设为Node并进入步骤3。

步骤5：如果视距大于节点的细节层次作用范围，则终止该分支；如果落于节点的细节层次作用范围，则逐一判断节点中的目标与视锥体的空间关系，如果非相离则加入目标集合，并终止该分支；如果小于节点的细节层次作用范围，则将该节点中不与视锥体相离的目标加入目标集合，并进入步骤6。

步骤6：循环判断各子节点（Child0，Child1，Child2，…）与视锥体的空间关系，如果非相离，则将子节点设为Node并进入步骤2。

步骤7：如果所有查询分支均终止，则退出。

2.3 多细节层次的自适应控制方法

本文方法中，调整最高细节层次的最远距离参数（FarDist）即能调整各层的作用范围，当FarDist增大时，各层的最近距离和最远距离均增大，且作用范围的区间增大。调整FarDist可以改变场景复杂性，FarDist增大则场景复杂，FarDist减小则场景简化。因此，可以实现三维城市场景自适应控制方法。

下面讨论调整参数对于三维场景的影响。令视点接近地表且视线水平，假设最高细节层次最远距离为D，且层间倍数为K，视锥体的水平方向夹角为α。Slod1为LOD1作用范围的面积，Slod2为LOD2作用范围的面积，计算公式分别见式（1）和式（2），各细节层次面积均和D2存在正比关系。假定三维场景属于理想状态，即目标分布密度均匀，各层节点分布密度也基本均匀，则各层覆盖面积决定了覆盖范围内的节点数目也即目标数目，因此各层次范围内的目标数目之和与D2存在正比关系。每个目标数据量相等的前提下，目标数目和处理时间也成正比关系，而三维城市场景中的目标数目通常很大，从统计学上讲，随着统计样本数量增加，平均值趋向稳定，进而获得处理时间和D2成正比的结论。三维场景实时绘制中，根据前几帧的处理时间在每帧绘制前定量调整D值，应对系统负载变化，在保证稳定帧率的前提下提供最为丰富的细节层次场景。

3 试验分析

本试验中的目标模型均采用目标的最小包围盒表示，便于关注空间索引技术本质，实际单个目标包括几何和纹理数据量可能超过1M数据量，测试数据为某城市部分城区的离散目标，总共有23 951个目标，测试环境配置如下：笔记本电脑，CPU Intel Duo T7500，内存1G。

3.1 多细节层次可视化的试验结果

本文方法在三维空间查询的同时，也能实现多细节层次场景目标检索，这种多细节层次可视化的重要特征是，既能实现目标集合的综合和简化，也能支持单个目标的多细节层次表示（当单个目标存在多细节层次模型时），可以实现全部场景的多细节层次描述。

图1～3是在各种视域条件下启动与不启动多细节层次描述的场景对比。图1所示的平视场景，二者可视化效果几乎没有差别，而目标数目却相差明显，这充分体现细节层次自适应控制的优势，那就是保持了近处目标的详细特征，而淡化了远处目标特征。图2是远距离俯视场景，二者具有比较明显的差异，多细节层次描述仍然能够保留原有目标分布特点，目标数目也相差明显，也符合多细节层次描述要求。图3是近距离俯视场景，由于视场内目标与视点的距离均在最高细节层次作用范围的最远距离内，全部采用最高细节层次描述，二者完全相同。

图1 平视场景Fig.1 Head－up display of scenes

图2 远距离俯视场景Fig.2 Overlook of scenes from far distance

图3 近距离俯视场景Fig.3 Overlook of scenes from near distance

3.2 多细节层次自适应控制的试验结果

修改最高细节层次的最远作用距离FarDist调整三维场景复杂度是本文自适应控制方法的核心。设计试验来分析调整参数FarDist会对三维场景多细节层次描述产生的影响。设定多细节层次参数中的层间参数为3。图4是不同参数条件下的三维场景。本试验设置了6次参数，它们满足等比系数为1.5的等比序列，即200m、300m、450m、675m、1 000m和1 500m。按照第2.3节的理论分析，如果目标分布均匀，图中的6个场景中的目标数目满足等比参数为2.25（1.52）的等比序列，试验数据也基本符合理论分析。试验说明，可以通过调整FarDist参数定量控制多细节层次场景描绘中的目标数目。

图4 不同LOD参数条件下的三维场景Fig.4 3Dscenes on the conditions of different LOD parameters

4 结 论

提出一种新的三维场景细节层次控制方法，利用R树的层次结构承载多细节层次目标，通过三个环节控制三维场景中渲染目标的数目：一是视锥体查询裁剪视野外的目标；二是启动多细节层次绘制方法；三是调节多细节层次控制参数。试验表明该方法在空间检索过程中同时完成LOD目标模型检索功能，实现了完整场景的简化描述，描绘效果和效率能够满足大规模三维城市模型的实时绘制需求，并且通过调整多细节层次参数可以定量控制场景中的目标数目和复杂度，实现三维场景的自适应可视化控制，尤其适合建筑物和树木等尺寸均匀的地物目标。进一步工作将延展到地质和地下管线、不规则三角网和三维激光扫描点云等数据处理领域。

［1］ FUNKHOUSER T A，SEQUIN C H.Adaptive Display Algorithm for Interactive Frame Rates during Visualization of Complex Virtual Environments［C］∥SIGGRAPH’93 Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques.New York：ACM Publishings，1993：247－254.

［2］ YANG Chongyuan，ZHANG Jixian，LIN Zongjian.The Real－time LOD Algorithm for Rendering the Virtual Terrain Scene［J］.Acta Geodaetica et Cartographica Sinica，2001，30（2）：133－139.（杨崇源，张继贤，林宗坚.虚拟地形场景绘制中的实时LOD算法［J］.测绘学报，2001，30（2）：133－139.）

［3］ WIMMER M，SCHMALSTIEG D.Load Balancing for Smooth LODs［R］.Vienna：Vienna University of Technology，1998.

［4］ ZHU Qing，GONG Jun.An Improved Full 3DR－tree Spatial Index Method［J］.Geomatics Information Science of Wuhan University，2006，31（4）：340－343.（朱庆，龚俊.一种改进的真三维R树空间索引方法［J］.武汉大学学报：信息科学版，2006，31（4）：340－343.）

［5］ CHEN Peng，MENG Lingkui，SONG Yang.R－tree Structure Appended with Spatial Topology Restrictions in 3DGIS［J］.Geomatics Information Science of Wuhan University，2007，32（4）：347－349.（陈鹏，孟令奎，宋杨.三维GIS中基于空间拓扑约束条件的R树研究［J］.武汉大学学报：信息科学版，2007，32（4）：347－349.）

［6］ GONG Jun，ZHU Qing，Zhang Yeting，et al.An Efficient 3DR－tree Extension Method Concerned with Levels of Detail［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：249－255.（龚俊，朱庆，张叶廷，等.顾及多细节层次的三维R树索引扩展方法［J］.测绘学报，2011，40（2）：249－255.）

［7］ KOFLER M.R－trees for Visualizing and Organizing Large 3DGIS Databases［D］.Graz：Graz University of Technology，1998.

［8］ LI Jun，JING Ning，SUN Maoyin.A Mechanism of Implementing Visualization with Level of Detail at Multi－scale［J］.Journal of Software，2002，13（10）：2037－2043.（李军，景宁，孙茂印.多比例尺下细节层次可视化的实现机制［J］.软件学报，2002，13（10）：2037－2043.）

AnAdaptiveControlMethodofLODsfor3DSceneBasedonR－treeIndex

GONGJun1，ZHUQing2，ZHANGHanwu1，LIXiaoming2，ZHOUDongbo2
1.School of Geography and Environment，Jiangxi Normal University，Nanchang 330022，China；2.State Key Laboratory of Information Engineering in Surveying，Mapping and Remote Sensing，Wuhan 430079，China

Aiming at the requirement of large－scale 3Dcity modelling，a method is puts forward to organize LOD scene based on R－tree’s hierarchical structure.LOD scene can be automatically generated from leaf node layer to root node，and efficient algorithm of LOD search are also designed and implemented.By experimental analysis，it is proved that scene complexity can be quantitatively altered by adjusting one defined LOD parameter，and further adaptively control LOD of 3Dscene，which suits building and tree type especially.

3Dscene；R－tree；levels of detail；adaptive

GONG Jun（1978—），male，PhD，associate professor，majors in theory and application of multidim ensional G IS and 3Dlaser point cloud data processing.

1001－1595（2011）04－0531－04

P208

A

国家自然科学基金（41001222；40871212；40721001）；国家973计划（2010CB731801）；测绘遥感信息工程国家重点实验室开放研究基金（（10）重04）

雷秀丽）

2010－10－25

2011－03－18

龚俊（1978—），男，博士，副教授，主要从事多维地理信息系统和三维激光点云数据处理的理论与应用研究。

E－mail：gongjunbox＠gmail.com