大规模三维点云快速拾取技术研究

徐胜攀，刘正军，左志权

（1.中国测绘科学研究院，北京100830；2.兰州交通大学 测绘与地理信息学院，甘肃 兰州730071）

0 引 言

在三维交互式图形系统中，拾取是一项重要功能。在通常情况下，三维交互式图形系统不仅要将三维图形或事物的三维模型可视化，还要提供简单的方式使得用户能够直接操纵三维物体，以完成对三维物体形状、位置、颜色、纹理等属性的查询和编辑。用户通过鼠标在图形系统中捕捉图形对象的操作叫拾取，交互式三维图形系统对图形对象的增、删、改等操作都是以拾取为基础的［1，2］。

当前关于三维拾取的研究中，较多的是对图形对象的拾取，对点云拾取的研究则较少。随着LiDAR系统在测绘和地理信息系统中的发展，以点云为基本图元对象的研究不断增多，以点云为基础的地理信息提取、地理事物建模日益受到重视［3］。因此，研究出一套准确可行的、针对三维点云的拾取方法具有十分重要的意义。

计算机三维图形拾取的基本方法，从原理上说主要可分为两类：场景几何相关的拾取方法和场景几何无关的拾取方法［4］。场景几何相关的拾取方法是目前广泛采用的拾取方法，其基本思想是将鼠标输入点转换到三维空间形成一条射线，然后利用此射线在三维空间对场景内的图元求交。在这方面较有代表性的是王剑等［5］和姚继权等［6］的工作，此外2008年朱明亮等［7］提出三维场景中基于视口空间的拾取算法，将基于三维场景的相交检测将维至二维平面，有效地提高了拾取效率。场景几何无关的拾取方法基本思想是对场景作一次特殊的渲染，将物体的信息按颜色编码渲染到后台纹理，通过读取纹理上相应屏幕坐标的颜色值就可以得到对应物体的信息［4，7］。OpenGL选择模式作为一种主要的拾取方法，目前也有大量研究［8－10］，基本思想是利用鼠标在视口中确定一个矩形，通过此矩形计算得到一个特殊的视景体 （这一步由OpenGL实现），然后基于此视景体对场景进行投影变换和裁剪变换，与视景体有交集的图元即为拾取图形。

三维点作为一种特殊的图形对象，其拾取方法与普通的三维图形有相通之处，但也有显著不同。首先点是一种没有大小的图形对象，直接的几何相关拾取方法或几何无关拾取方法并不适用于点云的拾取；其次在实际应用中，点云拾取常常并不限于对单个点的拾取，而且是对点集的拾取，这与普通三维图形拾取中针对单个图形对象的拾取并不一致；第三，点云的在空间的分布呈离散状态，这恰为合理的点云组织以便加速点云拾取提供了空间。

基于此，本文系统研究三维空间点云的拾取问题，提出面向大规模点云数据的快速拾取算法。

1 三维点云拾取基本方法

1.1 点云拾取问题分类

在实际应用中，通常有两类典型的点云拾取问题：第一类是鼠标在屏幕上给定一点，要求找到场景中离给定点距离最近的点 （称这类问题为单点拾取问题），这种情况在通过鼠标查询场景中点的三维坐标、点之间的距离量测等时会遇到；第二类是鼠标在屏幕上确定一个多边形，要求找到场景中落在这个多边形范围内的点 （称这类问题为多点拾取问题），这类问题在LiDAR数据处理中，对点云进行手工分类、观察局部地形剖面等时会遇到，如图1所示。

图1 点云拾取典型问题分类

1.2 三维点云拾取基本方法

上文对计算机三维图形基本拾取方法及其对点云拾取的适用性进行了简单分析。事实上，从OpenGL选择模式需要用到命名栈这一点出发，决定了这种方法并不适合于点云的拾取；另外，这种方法只能对按即时模式绘制的图元进行拾取，当图元以缓冲区对象等形式组织时，这种拾取方式显得无能为力。对于场景几何无关的拾取方法，由于点云不具备面状特征，且离散分布，以读取渲染图像像素颜色来识别图元的方式决定了它不适合用来拾取点云。

场景几何无关的方式是一个值得考虑的方法，为减小相交检测计算的复杂度，本文采取文献 ［7］中的方法——基于视口空间来进行点云拾取。基本思路是将点云由三维场景映射到屏幕，然后在屏幕上进行点的相交检测。在单点拾取时，只需计算各点的屏幕坐标到鼠标点击位置的距离，距离最短者即为拾取点；在进行多点拾取时，对各点的屏幕坐标与由鼠标所确定的多边形进行相交检测，落在多边形内的点即为拾取点。

另外，单点拾取基本方法中涉及到 “距离最短”对应点的查找，原则上需要这样做，但在实际的三维点云可视化中，当视点离场景很远时，点云在屏幕上的显示非常密集，此时寻找距离最短对应点既十分费时，也没有必要。同时，在有些情况下，距离最短原则也不一定总是正确，例如当视点离场景很近时，点云在屏幕上的显示非常分散，此时拾取到的距离最短对应点有可能离鼠标点击位置距离很远，拾取结果并不是用户所需要的点。

可以对单点拾取算法进一步修改，设计一个最小可识别距离 （minimum identifiable distance，MID）和最小容忍距离 （minimum tolerance distance，MTD），拾取时将三维点向屏幕投影，如果投影点到鼠标点击位置小于MID，则该点即为拾取点，拾取结束；如果投影点到鼠标点击位置大于MID而小于MTD，则该点作为被比较对象，后续计算中选取距离最小的点；如果投影点到鼠标点击位置大于MTD，则结束该点的计算，判断后续点。

在具体算法设计中MID、MTD的值可以灵活选取。当MID＝MTD时，拾取过程变为选取任意一个落在以MID为半径的圆内的点。

2 基于四叉树的层次包围盒技术

2.1 四叉树的引入

在实际应用中，系统面对的通常是大规模的三维点云数据，如果进行点云拾取时对三维场景中的点一一进行坐标转换和相交检测，势必给系统带来较大的运算负荷，影响交互速度。层次包围盒［2］是一种能有效提高拾取效率的技术，在拾取时，从层次包围盒上层结点出发，逐步向下判断，如果到达某个结点时与拾取射线或拾取多边形无交集，则其子结点的相交情况无需再判断；当到达最底层结点时，则进行基本的相交检测。

为了构建层次包围盒，点云数据需按树形组织。目前常用于构建空间数据索引的树形结构包括四叉树、八叉树、K－D树［11］、R树［12］等。K－D树、R树缺点是结构复杂、构建速度较慢；八叉树虽然可以快速构建，但它对点云数据按三维划分，而在进行点云拾取时，一条拾取射线往往会贯穿八叉树内的多层结点，所以对于点云拾取而言，这种划分实际上没有必要，而且对于大规模的点云数据，按八叉树的空间划分往往会造成大量的空的结点，浪费较多内存。

相比于上述数据结构而言，四叉树表现出独特的优势。首先，四叉树仅对数据进行二维划分，符合大规模点云数据的尺度变化的特点；其次，当对四叉树进行规则划分时，四叉树各结点与其父结点的形状、位置等表现出严格的数量关系，这有利于结点形状、位置等的计算，可以为四叉树的存储节省大量内存；另外，在下文将可以看到，利用本文提出的高效四叉树处理策略，整个四叉树的构建过程可以大幅度地加速。

基于此，本文利用四叉树构建点云层次包围盒，解决大规模三维点云数据的快速拾取问题。

2.2 高效四叉树处理策略

考虑到点云数据的海量性，四叉树可能具有庞大的索引结构，因此，减少四叉树结点数据量、加速四叉树构建过程具有十分重要的意义。本文采用静态方式构建四叉树（先建立四叉树，再填充点云数据），对点云数据块沿轴向划分 （行沿X方向，列沿Y方向），采用带叶子结点索引的规则划分满四叉树结构 （见图2）。

图2 点云数据块划分与四叉树结点组织

四叉树经过这样处理后，在以下方面具有显著优势：

首先，对于任一结点，只要知道其遍历路径，便可快速计算出结点所代表数据块的X、Y坐标范围，这可以为四叉树的存储节省大量的空间；其次，当四叉树规则划分时，顶点所在的叶子结点行列号可以直接计算得到，当对叶子结点按行列号建立二维索引后，顶点数据就可以直接加入四叉树，而不必自根结点逐步判断，这可以大大加速四叉树的初始化过程，提高系统运行效率。

2.3 四叉树结点点云包围盒的计算

点云包围盒是一个在空间内包含点云数据块所有点的最小长方体，点云包围盒由中心 （Center）、3个轴向 （Axis）以及3个沿轴向方向的延伸尺度 （Extent）定义，其模型如图3所示。

图3 点云包围盒的几何模型

本文中建立点云包围盒时，取V0、V1、V2分别沿X、Y、Z轴，当结点中点云的X、Y、Z最大值和最小值均确定，点云包围盒的形状和位置随之确定。结点的Z最大值和最小值直接存储，X、Y最大值和最小值则根据结点遍历路径计算确定。这样既可以节省内存，又可以使得所有点云包围盒中心并不落在同一平面上，更好地适应空间中点云的形状分布，减少点云包围盒的无效面积［2］。

3 基于四叉树的大规模三维点云快速拾取算法

3.1 基于四叉树的单点拾取算法

结合单点拾取基本方法，本算法基本思想是先利用四叉树寻找基本的点云数据块 （即叶子结点），然后对于叶子结点执行基本的单点拾取算法，如果找到满足条件的点，则返回拾取结果，退出；否则，更新查找记录，对当前结点的兄弟结点继续执行上述查找。

在寻找基本数据块时，需要对数据块与鼠标确定点进行相交检测，方法为先求取鼠标确定点在场景空间对应的射线，然后对射线与点云包围盒进行相交检测。三维空间内射线与长方体的相交检测是一个简单的计算几何算法，其过程为首先确定射线起点是否在长方体内，如果是则相交；否则，求取长方体中心与射线的垂线，如果垂足在射线起点的反方向，则不相交；否则，求取长方体中心到垂足的向量在长方体各轴向 （axis）的投影长度，如果各投影长度均小于相应轴向的延伸尺度 （extent）则相交，否则不相交。

算法流程图如图4所示。

图4 基于四叉树的单点拾取算法

算法中，初始当前结点为四叉树根结点。

3.2 基于四叉树的多点拾取算法

算法基本思想是首先逐步对四叉树结点与鼠标所确定的屏幕多边形进行相交检测，找到与多边形有交集的基本点云数据块，然后再对结点执行多点拾取基本算法 （即将基本点云数据块内的点投影到屏幕上，即点在屏幕上的投影在多边形内的点加入查找集合）。

四叉树结点与鼠标所确定的屏幕多边形的相交检测过程是先将四叉树结点的点云包围盒投影到屏幕形成一个凸多边形，然后对该多边形与鼠标所确定的多边形进行相交检测运算，这是一个基本的计算几何算法。本过程中涉及到的另一个计算几何算法是点是否在多边形内的判断。

为加速基本数据块的查找，在对结点包围盒进行投影之前可以先对结点包围盒与视景体进行相交检测，相交检测可以有条件地进行，例如，当视点与场景近到一定程度时才进行相交检测，同时相交检测算法也可以简化，篇幅所限，这部分内容本文不作详细论述。

算法的流程图如图5所示。

图5 基于四叉树的多点拾取算法

算法中，初始当前结点为四叉树根结点。

4 实验与评价

为检验本文算法的拾取效率和拾取准确性，采用大小约为240M （10 346 373个点）的LAS（由美国摄影测量与遥感协会制定的一种机载激光雷达数据专有格式）文件设计了一组实验，实验中，对对云数据分别在分布密集、分布较密和分布稀疏3种状态 （如图6所示）下进行单点拾取和多点拾取。对单点拾取，采用统计1000个随机点的累计拾取时间计算平均拾取时间；对多点拾取，分别采用尺寸大约为视口尺寸的1／102、1／52、1／32的随机多边形 （顶点个数在10个点以内）进行拾取，统计拾取时间。每组实验进行10次，结果取平均值。表1为拾取时间统计表，实验中，取MID＝5，MTD＝15。

图6 点云分别状态

表1 拾取实验时间统计

为检验拾取精度，采用相同的数据和相同的运行环境，针对单点拾取和多点拾取分别进行实验，以下为实验效果图。图7进行距离量测时，鼠标从一个拾取点移动到另一个拾取点，实现了对两个点的正确捕捉；图8中用鼠标围绕一座建筑物确定一个多边形，将这些点从未定义类划分到建筑物类，实现了多点拾取。

图7 单点拾取效果

从实验结果可以看到，当点的数据量达到千万级以后，单点拾取均能保持很高的拾取速度。多点拾取在点云分布密集和较密集的情况下，对于尺寸分别为1／102、1／52、1／32的任意多边形都能进行较为快速的拾取；当点云分布稀疏时，多点拾取速度有所下降，但仍不至于有过长的时间延迟。从拾取效果上看，单点拾取和多点拾取均能正确地完成拾取，取得了比较好的效果。

图8 多点拾取效果

5 结束语

拾取是交互式图形系统的重要功能，是许多交互式操作的基础。由于生产应用的限制，目前对三维点云拾取的研究并不多见，随着LiDAR系统的发展，对大规模三维点云拾取的研究具有重要意义。本文在系统总结当前计算机三维图形拾取基本方法的基础上，讨论了常用拾取方法与三维点云拾取的适用性问题，进一步提出适合于三维点云拾取的基本方法。针对实际LiDAR点云数据处理中往往为大规模点云数据，通过层次包围盒的思想引入四叉树，提出了基于四叉树的大规模三维点云快速拾取系列算法，试验证明算法在大规模点云拾取速度和精度上均达到了较好效果。另外，虽然本文所提出的四叉树是针对点云拾取设计的，但是由于该四叉树考虑了点的三维特性，采取了有利于节省内存和提高速度的高效策略，且能较好地适应三维点云的空间分布，将该四叉树用于海量点云数据的场景管理以及LOD （level of details）实现同样具有借鉴意义。

［1］YUE Wenli，WANG Jian，DAI Yiru.Research on algorithm for picking up graph in interactive graphics systems［J］.Development ＆ Innovation of Machinery ＆ Elemctrical Products，2008，21（2）：3－4 （in Chinese）.［岳文理，王坚，戴毅茹.交互式图形系统中图形拾取算法的研究与应用 ［J］.机电产品开发与创新，2008，21（2）：3－4.］

［2］ZHANG Xiaohong.Airborne laser radar measurement technology theory and method［M］.Wuhan：Wuhan University Press，2007：1－14 （in Chinese）.［张小红.机载激光雷达测量技术理论与方法 ［M］.武汉：武汉大学出版社，2007：1－14.］

［3］GUO Yanxia，HOU Tongpu，DU Yuanyuan.Picking entities in 3Dscene based on DirectX ［J］.Journal of Liaoning Univer－sity of Petrol Eum ＆ Chemical Technology，2009，29 （3）：77－80（in Chinese）.［郭艳霞，侯彤璞，杜园园.基于DirectX的三维场景实体的拾取 ［J］，辽宁石油化工大学学报，2009，29（3）：77－80.］

［4］ZHANG Jiahua，LIANG Cheng，LI Guiqing.3Dprimitive picking on GPU ［J］.Journal of Engineering Graphics，2009 （1）：46－52（in Chinese）.［张嘉华，梁成，李桂清.GPU三维图元拾取 ［J］.工程图学学报，2009 （1）：46－52.］

［5］WANG Jian，LU Guodong，TAN Jianrong.The selection method of graphics at 3Dgraphic browser［J］.Machine，2004（7）：29－32 （in Chinese）.［王剑，陆国栋，谭建荣.三维场中图形对象的拾取方法 ［J］.机械，2004 （7）：29－32.］

［6］YAO Jiquan，LI Xiaohuo.Research on 3－dimension pick－up of human－computer intersection in computer graphics［J］.Journal of Engineering Design，2006，13 （2）：116－120 （in Chinese）.［姚继权，李晓豁.计算机图形学人机交互中三维拾取方法的研究 ［J］.工程设计学报，2006，13 （2）：116－120.］

［7］ZHU Mingliang，DONG Bing，WANG Yi，et al.Algorithm for picking in 3Dscenes based on viewport space［J］.Enginee－ring Graphics，2008 （2）：94－97 （in Chinese）.［朱明亮，董冰，王祎，等.三维场景中基于视口空间的拾取算法 ［J］.工程图学学报，2008 （2）：94－97.］

［8］HE Jianying，XU Qianghua，YOU Jia.A 3Dpicking method based on OpenGL［J］.Computer Engineering ＆Science，2006，28 （1）：45－46 （in Chinese）.［何健鹰，徐强华，游佳.基于OpenGL的一种三维拾取方法 ［J］.计算机工程与科学，2006，28 （1）：45－46.］

［9］SUN Nifang，YANG Zhiqiang，CHEN Cheng，et al.Control the 3Dmodels interactively in OpenGL ［J］.Computer Applications and Software，2007，24 （10）：207－209 （in Chinese）.［孙妮芳，杨志强，陈诚，等.OpenGL实现3D模型的交互控制［J］.计算机应用与软，2007，24 （10）：207－209.］

［10］ZHU Jincai，CHENG Zhiyong，HUANG Xuefei.On－machine measurement software development based on selection mode of OpenGL［J］.Mechanical ＆ Electrical Engineering，2010，39（5）：13－14 （in Chinese）.［诸进才，程智勇，黄学飞.基于OpenGL拾取技术交互式在机检测软件的开发 ［J］.机电工程技术，2010，39 （5）：13－14.］

［11］LIU Yu，XIONG Youlun.Algorithm for searching nearest－neighbor based on the bounded k－d tree［J］.J Huazhong Univ of Sci ＆Tech （Natural Science Edition），2008，36 （7）：73－76 （in Chinese）.［刘宇，熊有伦.基于有界k－d树的最近点搜索算法 ［J］.华中科技大学学报 （自然科学版），2008，36 （7）：73－76.］

［12］YU Dengfeng.The research and implement of spatial data index technology base on R－Tree［D］.Wuhan：China University of Geosciences，2006：14－24 （in Chinese）.［余登峰.基于R树的空间数据索引技术研究与实现 ［D］.武汉：中国地质大学，2006：14－24.］