ｔｈｔｒａｖｅｒｓａｌ ｓｔｏｒａｇ
ｅ点云工程数据规模通常很大，超出主存容量和图形绘制硬件处理能力，一般打开工程时仅调度上面数层节点中的点数据以描述全景，当视点逼近局部场景时，
将通过父节点依次访问子节点直至叶节点，因此广度优先存储和深度优先存储方式均不能完全满足高效调度的要求。本文采用二者混合方案来最大限度提升数据调度效率。以叶节点层为第０层，例如全景显示第２层及以上节点中的点数据时，将第２层及以上层采用广度优先存储，
最下两层按照深度优先存储，至于具体以第几层为分界线，将根据总数据量决定，如果数据量小可以下调，如果数据量大可以上调。图７是本文方法的原理描述，其中第２层是分界线。本文方法采用文件映射技术访问点云文件，每个父节点记录所有子节点地址，
采用类似于访问内存方法根据节点地址访问节点外存数据。本文方法将极有可能连续访问的节点数据集中存储，
有利于提高外存访问效率
。
图７ 混合存储方式原理描述
Ｆｉｇ．７ Ｐｒｉｎｃｉｐａｌ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｍｉｘｅｄ ｓｔｏｒａｇ
ｅ单点数据内容包括三维坐标、颜色以及强度等信息，
可以根据应用需要扩展单点结构。如果采取压缩方式存储，
三维坐标值采用２字节短整型表示，相对于双精度浮点型表示，数据量减少７５％，可以显著减少数据调度量，提升外存访问效率。另外，为最大限度提升三维可视化效率，点数据应当按照图形绘制硬件特点进行组织，
例如，采用Ｏｐ
ｅｎＧＬ绘制引擎时，可以将节点中的点数据组织成ＶＢＯ顶点缓冲形式，
直接送入绘制管线处理。５ 试验结果与分析
本试验采用测试数据是车载激光扫描移动测图系统采集的真实数据，是中国某小型城镇的真
彩色三维点云数据。车辆行驶耗费２０ｍｉｎ扫描该镇全部道路，获取详细的街道、房屋立面、树木以及电线等点模型。原始数据包含９２个点云文件，每个点云文件包含２００多万个点，总数据量约为１４．６ＧＢ（包含坐标、颜色、时间等数据），总点数为２．２亿。测试环境配置如下：笔记本电脑，ＣＰＵ Ｉｎｔｅｌ Ｄｕｏ Ｔ７５００，内存１ＧＢ。５．１ 索引创建效率测试
索引创建效率关系到应用成败，如果索引创建需要十几个小时甚至更长，即使查询效率满足交互要求，也不能适应实际应用需要。由于格网索引的格网尺寸难以确定，
且大量空格网容易导致空间利用率极低，本文不予比较测试。本文分别对八叉树、三维动态Ｒ树和３ＤＯＲ树生成算法进行效率测试。其中，八叉树参数为１００，即节点中点数目小于等于１００时停止分裂，三维Ｒ树的扇出参数为４０和１００，而３ＤＯＲ树中，八叉树分裂参数为１００，Ｒ树扇出参数为４０和１００。
采用一份包含２ ４２６ ４５４个点的点云数据测试索引创建效率，表１中有八叉树、３ＤＯＲ树以及三维动态Ｒ树的创建效率对比。八叉树深度
１
０６
Ａｕｇｕｓｔ ２０１２ Ｖｏｌ．４１ Ｎｏ．４ ＡＧＣＳ ｈｔｔｐ：∥ｘｂ．ｓｉｎｏｍａｐｓ．ｃｏｍ
不平衡，叶节点树深从１到１７不等。３ＤＯＲ树深
度平衡，树深为４。三维动态Ｒ树深度平衡，树深
为５。从测试数据可知，本文的３ＤＯＲ索引方法
创建效率满足准实时要求，树深平衡，并且树深比
另两种方法小。原因是，３ＤＯＲ树本质上仍是Ｒ
树索引结构，且叶节点基本是满负荷，从而节点数
目减少和深度减小。较小的树深直接减少迭代运
算层数，有利于显著改善算法效率。本文对总数
据量１４．６ＧＢ的点云工程创建索引，总耗费时间
约为４０ｍｉｎ。
５．２ 空间利用率测试
相对于ＣＰＵ计算和主存访问效率，外存访
问效率低两个数量级以上且改善空间有限，数据
量大小直接关系到后续外存数据调度效率，进而
影响用户体验。点云工程数据量往往大于主存容
量，动态调度和数据缓存机制成为必须采用的策
略。本文通过中心点平移方法将双精度浮点型数
据转化为单精度浮点型，进一步将单精度浮点型
转化为短整型，并清除冗余点（距离小于１ｃｍ视
为冗余点），数据量压缩显著，表１中有文本格
式、Ｐｏｉｎｔｏｏｌｓ商业格式和本文结构的数据量对
比。不难看出，原始文本数据转化为本文数据格
式，压缩率超过全球业界领先者Ｐｏｉｎｔｏｏｌｓ。
表１ 空间索引重要指标对比
Ｔａｂ．１ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｋｅｙ ｃｒｉｔｅｒｉａ ｆｏｒ ｓｐａｔｉａｌ ｉｎｄｅｘ
空间索引创建效率对比／ｓ空间利用率对比／ＧＢ
八叉树三维
Ｒ树
本文
方法
原始
数据
Ｐｏｉｎｔｏｏｌｓ
本文
结构
测试
数据
５ ５７４ ２５ １６ １．８２ １．４３
５．３ 数据调度与可视化效率测试
如果用户打开和全景显示工程的等待时间过长，将严重影响用户体验。采用Ｐｏｉｎｔｏｏｌｓ商业平台将试验数据转化为其特有ＰＯＤ格式并组织成为工程后，试验环境打开工程耗时超过４ｍｉｎ。由于是商业平台，无法测算其效率瓶颈。值得指出的是，当工程打开后，该商业平台可以保证后续交互操作的流畅性。
本文方法中，点云工程包含２亿多个点，扇出参数为４０和１００，第２层及以上点云模型不会超过１０万个点（２×１０８／（４０×４０）），因此打开工程只需调度第２层及以上的点云模型。第２层以上按照广度优先遍历方法进行存储，后续访问时按照广度优先遍历顺序即可将所需节点外存数据依次读取，不会出现跳跃访问，最大限度地提高数据访问效率，试验结果表明耗时仅需４ｓ，图８是点云工程的全景图。另外，本文设计试验测试深度优先存储方法的访问效率，节点数据重新按照深度优先遍历方式存储，打开整个工程耗时３ｍｉｎ，相比于本文方法，效率下降明显
。
图８ 点云工程全景
Ｆｉｇ．８ Ｆｕｌｌ ｓｃｅｎｅ ｏｆ ｐｏｉｎｔ ｃｌｏｕｄ ｐｒｏｊｅｃｔ
本试验环境允许的数据缓存容量不超过２００兆，单帧绘制点数不超过５００万个，如果超过容许值将自动清理缓冲区。当视点落于场景中近距离浏览地物目标时，自适应可视化机制下最高细节层次作用范围的最远距离一般保持在１５ｍ左右，即使显著改变视点位置，所需调度数据量也不会超过１０ＭＢ，调度时间不超过２ｓ。试验采用多线程机制调度数据，并不影响主线程绘制任务，实现点云场景多细节层次描述效果。