激光扫描系统能够直接获取被测目标表面的三维空间坐标，具有采样密度高、点云分布密集等特点，正逐渐成为三维空间信息快速获取的主要手段之一，被广泛应用于文物保护、三维重建、数字地面模型生产、城市规划等领域^[1]。现代车载激光扫描系统，通常安装多个激光扫描头采集三维点云数据，如Optech公司的LYNX系统，Riegl公司的VMX-450系统。车载激光扫描系统沿着某一轨迹采集数据，多个高频采样激光头数据相互叠加，产生海量三维点云数据，其数据量随着轨迹的延长而线性增加。例如，VMX-450系统在约一个小时内，可获取40 km左右长度的点云数据，数据量高达1 TB。对于车载激光扫描系统采集的海量三维点云数据，单在数据量方面即对后续数据处理(如点云滤波、分割，目标识别，三维重建和可视化等)带来巨大的挑战。为实现海量点云数据的空间分析及可视化，需要实时、高效地完成点云数据的调度和查询工作。空间数据的调度，关键在于数据的索引与检索，索引的性能优劣直接影响到系统的效率和分析能力。因此，如何建立合理的空间索引机制，是解决海量空间数据组织和快速调度的关键问题。许多标志性索引方法已被广泛应用于空间数据的检索、查询、存储以及管理，如四叉树^[2]、R树^{[3, 4]}、R*树^[5]和八叉树^[6]等。

在地理信息系统中，支持二维空间数据的索引方法已非常成熟。但是，随着三维点云数据的广泛应用，迫切需要在虚拟地理环境下可视化全部三维点云数据。在三维点云数据可用性不断增强的驱动下，出现了一些具有可视化和三维点云数据管理功能的商业软件^{[7, 8]}。然而，Quick Terrain Reader、Point Tools等商业点云处理软件对载入点云数据量有严格限制，不支持车载海量激光点云数据的实时三维可视化，从而引发了完善三维激光点云数据空间索引方法的热潮。

R树或R*树的每个子块包含一个对象，这些子块可以彼此重叠。文献^[9]提出利用三维 R 树结构管理虚拟环境下的三维建筑物。文献^[10]提出使用三维 R 树结构快速索引激光点云数据。但是，如何有效解决R 树子块重叠是三维点云数据管理尚未解决的问题。四叉树索引是一种基于树的空间索引，它按照一定的规则，将已知范围的空间递归地均分成4个部分，直到每个子块满足条件为止^[11]。文献^[12]提出了一种基于四叉树的三维点云渲染方法，此方法在假设连续点属于同一条扫描线的前提下，只存储每个叶子节点内的点的位置以节省存储空间。但是，这种方法无法对多扫描仪获取的无序点云建立索引。八叉树作为四叉树的3D扩展亦被广泛应用于三维数据索引。 文献^[13]提出了基于八叉树的三维点云数据的多尺度可视化方法。文献^[14]提出了一种开源的八叉树点云数据索引标准数据格式，并测试其在海量点云特征提取算法方面的适用性。文献^[15]通过哈希表数据结构优化八叉树结构，实现三维点云数据的快速检索。文献^[16]设计了一种基于外存的多分辨率数据结构，实现了海量点云数据的实时可视化与交互编辑 。一般情况下，基于八叉树的树结构比较适合处理三维点云数据，并且该方法有现行开源标准数据格式^[14]。但是，对车载激光扫描系统采集的三维数据使用八叉树索引具有分布不均等缺点，会出现大量空的叶节点。这直接造成了点云存储空间的低利用率，并且增加了空间数据查询的复杂度。相比四叉树结构，八叉树结构需要更多的存储空间，更难实现。快速检索算法通常需要耗费较大的存储空间，在时间和空间之间不能保持一个合理的平衡。KD树索引在邻域查找效率方面优于八叉树、四叉树以及R 树、R*树索引结构，常被用于单个激光点相邻区域点云数据查找，但对于海量点云数据存储管理与实时可视化，其邻域关系的重建将耗费大量的计算资源，整体效率低于八叉树索引结构^{[14, 17]}。

本文提出了一种基于内外存调度的海量三维点云数据管理与实时可视化方法，用户在台式计算机或网络环境下可以流畅地检索和可视化三维点云。由于区域四叉树是最重要、应用最广泛的四叉树表示法^[18]，对几何空间的划分没有重叠，通过特定的编码可以快速查找几何区域所在的行列，同时还可以根据空间对象的稠密程度来确定空间数据的分辨率。因此，本文在解决海量三维激光点云数据的可视化时，采用双层区域四叉树方法对数据建立索引，实现海量激光点云数据的管理与动态调度。

区域四叉树是将有边界的几何空间划分为连续的4个相同大小的区域，递归划分该区域为4个相同大小的较小的区域，直到得到的区域仅包含一个几何对象(见图 1)。若被划分区域根据相应的判别条件被判别为最小划分单元，那么该区域将不再继续划分。

图 1 四叉树平面分割及其结构图 Fig. 1 Quad-Tree Plane Segmentation and its Structure Diagram

图选项

激光扫描点云数据处理的首要步骤就是三维点云数据的检索和可视化。海量点云数据处理的一个难点是如何克服台式计算机有限的内存存储空间。为实现三维点云数据的快速可视化，本文提出的方案满足以下条件：

1) 利用高效的数据索引快速检索点云数据；

2) 将点云数据从外部磁盘动态加载到计算机的主存储器中；

3) 多细节层次(levels of detail,LoD)可视化三维点云。

车载激光扫描系统采集的三维点云一般存储在LAS文件中^[19]，该文件记录每个激光点的坐标和强度。存储千万点级别的LAS文件可能达到GB级。车载激光扫描系统通常沿着某一轨迹(街道、高速公路等)采集三维点云。获得的三维点云可能覆盖了一个较大的范围区域，而其中仅有一小部分区域包含点云数据(见图 2)。

图 2 车载激光扫描系统采集的激光点云 Fig. 2 A Snapshot of MMS Collecting Point Clouds

图选项

激光扫描的目的不仅仅是进行可视化，为了使获取的三维激光扫描数据具有较好的查询性能，应该对点云数据进行有效的管理和检索。但是，如果建立四叉树、R树或者八叉树来索引LAS文件中的点云数据，将会导致大量空的叶节点和无效的存储空间。为了解决这一难题，首先将三维点云沿着扫描路径分成一系列连续区域块，每块仅包含一部分数据。这样可以通过减少空的叶节点来节约索引文件的存储空间，并有效减少索引树高度，可提高检索性能以及点云加载的速度。

本文提出的方法首先将采集到的三维点云分割成连续的矩形块，对每个矩形内的点用区域四叉树进行索引，然后对全部矩形块进行四叉树索引。利用双层四叉树结构组织三维点云的关键步骤为：

1) 设置最小矩形块的大小(比如300 m×200 m)。当前车载激光扫描仪的最大扫描范围约为150 m。

2) 采用内存映射文件技术访问磁盘上的LAS数据文件，实现LAS数据的分块读入，分块建立四叉树并记录每块的空间范围<x_min,y_min,x_max,y_max >，不对LAS文件执行直接I/O操作或内容缓存，降低应用程序对操作系统的内存需求。

3) 构建四叉树文件索引所有的矩形块，建立树的集群，并按照树之间的相互关系建立统一的数据检索入口(见图 3)。

图 3 三维点云的双层四叉树结构 Fig. 3 A Two-Level Quad-Tree Data Structure for 3D Point Clouds

图选项

4) 存储每块数据文件和相关联的四叉树索引文件。

双层四叉树结构由上述4个步骤完成(见图 3)。第一层四叉树管理所有的矩形块，第二层四叉树管理每个矩形块内的数据点。与LAS文件相比较，每个数据块只包含一小部分点云数据，存储体积小，能够快速地从硬盘加载到计算机主存储器中。数据块之间无块间数据内容关联，搭建索引服务器亦可实现海量点云文件的分布式存储管理。

由于计算机内存的限制，无法一次性将所有矩形块内的点云数据加载到计算机主存储器中。可视化的首要步骤是判别可见或近可见的矩形块，然后，判断当前视景体中的激光点集。矩形块的可见性与用户在三维场景中的视景体范围相关，一旦确定了视景体的覆盖范围，依据构建的第一级四叉树结构，就可判断出可见矩形块。最后加载可见矩形块中的激光点到计算机主存储器，以便进一步的可视化。

当用户以漫游方式浏览三维点云时，矩形块的可见性发生快速变化，近可见的矩形块从磁盘加载到主存储器中，不可见的矩形块从主存储器内删除。不同矩形块之间的平滑过渡至关重要，否则，很难实现海量点云数据的快速可视化。为了满足这一要求，设计邻近矩形块缓存机制，通过快速检索并加载可视和近可视点到可视化缓存区完成视点移动中的场景平滑过渡。在加载过程中，分配B₁和B₂两个缓存区。缓存区B₁存储可见矩形块中的点云，缓存区B₂存储近可见矩形块中的点云。当可见矩形块变为不可见时，缓存区B₂与内存交换以实现可视化；缓存区B₁和缓存区B₂内的点云轮流交换到视频内存，从而进行不同矩形块之间的平滑过渡。

与地形LoD可视化相比，三维点云的LoD可视化要简单得多。由于每个矩形块都有限定范围<x_min,y_min,x_max,y_max >，以计算得到的可见矩形块到视点的距离以及可视叶节点到视点的距离作为选择三维点云LoD层次的依据。本文方法将计算得到的距离分成6个区间，分别为[0 m,100 m]、[100 m,300 m]、[300 m,700 m]、[700 m,1 500 m]、[1 500 m,2 500 m]、[2 500 m,+∞]。对可视叶节点内的点云数据根据距离间隔进行采样。设计位于6个间隔区间内的激光点分别按原始点的100%、90%、80%、70%、50%和40%进行采样，从而在保证运行效率的前提下实现无明显变化的动态渲染。该方法实现动态LoD是空间点云密度自适应的，用较高的密度渲染较近的点，用较低的密度渲染较远的点，从而形成对场景的分层表达。

本文利用C++语言实现海量车载激光扫描点云数据的快速索引、动态调度以及LoD场景表达，利用OpenGL渲染机对场景进行绘制。实验数据为海南某高速公路3.7千万个车载激光扫描点。实验环境为Intel Core i7 870(2.93 GHz)处理器、3 GB内存、GT220显卡。为验证算法性能，将本文算法与海量激光点云索引管理与八叉树索引方法^[14]进行对比。八叉树索引方法的实现使用其提供的开源软件包3DTK^[20]。

索引建立阶段，对原始点云文件创建双层四叉树索引并存储为文件，用于管理三维点云数据。本文四叉树索引方法与八叉树索引方法在建立文件索引耗时、耗内存方面进行比较的结果如图 4所示。八叉树索引方法^[14]耗费最大内存2.1 GB，消耗时间为559 s。双层四叉树索引耗费最大内存为1.3 GB，消耗时间只需337 s。双层四叉树结构较八叉树结构简单，计算复杂度小，在同等代码实现效率下，四叉树索引在构建速度方面明显优于八叉树。在计算资源消耗方面，八叉树索引方法需要把全部点读入内存后才能建立八叉树，数据大小与消耗内存呈线性关系，构建索引内存消耗随数据量的增加而升高。本文提出的双层四叉树方法在内存消耗上呈连续马鞍状，内存消耗峰值稳定，不随数据量的增加而不断上升，优于八叉树索引方法。本文方法建立索引内存消耗可控，使用双层四叉树方法结构建立索引需要消耗的内存与点云数据大小无关，具有对超内存存储量点云数据建立数据索引的能力。

图 4 建立数据索引消耗的资源与时间比较 Fig. 4 Comparison of Time and Ram Consumptionat Building Index Stage

图选项

在数据浏览阶段，本文方法与Elseberg八叉树索引方法内存消耗比较如图 5所示。基于八叉树索引的方法消耗的内存为492 MB，使用本文方法消耗的内存约为50 MB。本文方法不用把数据一次性读入内存，内存消耗较少。由于八叉树索引为整体索引结构，需要一次性读入全部数据，数据大小与消耗内存以及读入时间成线性关系。当输入数据过于庞大时，基于八叉树的方法无法载入数据或载入速率非常缓慢。图 6为利用本文方法与基于八叉树的方法在浏览帧率方面的比较。双层四叉树索引结构、多线程动态数据调度以及LoD技术的综合使用降低了海量激光点云数据可视化对硬件带来的压力，浏览帧速度大幅度优于八叉树索引方法。

图 5 数据漫游内存消耗比较 Fig. 5 Comparison of Data Roaming Ram Consumption

图选项

图 6 数据漫游帧率比较 Fig. 6 Comparison of Rendering Performance

图选项

图 7为三维点云动态可视化例图。实验证明，本文提出的方法在内存消耗和可视化速度方面有较好的性能，更有利于海量点云数据的实时可视化。与八叉树索引方法相比，本文的双层四叉树结构具有更简单的数据结构，更容易实现和维护。本文方法首先将三维点云分成连续的矩形块，利用四叉树管理所有的矩形块，然后构建每个矩形块的四叉树数据结构。这种分而治之的策略使点云数据动态加载更加简单而有效。此外，每个矩形块的四叉树数据结构较容易保持良好的平衡，并具有相对较低的树高度，有效减少了构建索引的内存与时间消耗，并提高了查询速度。实验结果表明，本文方法实现了高效率的海量三维点云管理与实时可视化。

图 7 三维点云动态可视化 Fig. 7 Dynamic Visualization of 3D Point Clouds

图选项

海量三维点云数据的流畅可视化是对车载激光扫描数据进行处理和结果检验的关键性基础工作之一。本文方法可以有效地进行海量数据的存取、调度以及可视化，大大加快数据响应的速度。同时，本文以文件形式存储索引文件，通过查询索引文件来获取点云数据。虽然该查询方式牺牲了一部分时间用于事先建立索引文件，但是却能有效地避免现有点云数据索引方式需要将数据索引与原始点云文件全部载入内存的弊端。对TB级车载激光扫描数据而言，是在充分利用内存资源和快速有效调度这两方面均能兼顾的可行手段和方法。实验结果证明了本文方法在动态加载三维点云数据、海量数据可视化、快速漫游和减少存储空间等方面的优异性能，具有实用价值。下一步的研究将关注可视化质量的提高以及构建基于双层四叉树索引的GPU并行化处理。