三维点云模型区域选择算法设计与实现

鲍彬　武云涛

摘要：本文提出一种基于射线的拾取算法和一种点云模型区域填充算法，实现了在点云模型上交互地选择区域。本文将算法应用于点云模型实例，实验结果表明提出的算法有效，快速且容易实现。

关键词：点云模型;拾取;区域填充

中图分类号：TP391.41 文献标识码：A 文章编号：1007-9416（2019）02-0126-02

0 引言

随着各种三维扫描技术的迅速发展，三维扫描产生了大量的高精度、大数据量的模型，点云模型就是用物体表面大量采样点来表示三维物体的高精度模型，对点云模型的处理已成为近年来研究的热点。实现点云模型上的交互，能够在点云模型上选择感兴趣的区域并得到其中的点云数据，这对于进一步研究点云模型是很有意义的。点云模型上拾取的难点在于，点云模型要拾取的是大量点云数据中的一点，而通常图形学中的交互是在场景中拾取某个物体，显然点云模型上的拾取对拾取精确度有更高要求;另外由于点云数据量很大，对于效率也必须有更多的考虑。本文针对这些问题，设计了一种基于射线的拾取算法。点云模型上区域填充的难点在于，点云模型是由大量的离散点表示，点与点之间没有任何拓扑联系。首先采用单元网格剖分点云数据，将问题转化为对包含点云数据盒子的填充，然后借鉴种子填充算法的思想设计填充算法。转化之后，不能直接把种子填充算法扩展到三维，这样会出现填充溢出问题，本文重点分析了溢出的原因和路径，得到点云模型上的一种有效区域填充算法。

1 点云模型拾取方法

1.1 点云模型拾取的特点及拾取方法的选择

点云模型是用大量点来表示物体表面的模型，点云模型上的拾取问题是如何由屏幕上一点得到点云模型上的一点。点云模型上拾取的特点如：（1）点云模型要拾取的是大量点云数据中的一点，而通常图形学中的交互是在场景中拾取某个物体，显然点云模型上的拾取对拾取精确度有更高要求。另外由于点云数据量很大，对于效率也必须有更多的考虑。（2）点云模型上的点是离散的，即点与点之间是有空隙的，在点绘制时采用相应的技术填充孔洞，从而得到连续的图像。所以，屏幕上一点并不直接也不一一对应点云上一点，它们之间的对应关系还与绘制时填充孔洞的方式有关。这就使得点云模型上的拾取不容易得到完全精确的结果[1]。

基于上述特点，首先，选择射线拾取的方式，是由于在常见的几种射线拾取方法中，射线拾取是一种精确度和效率都比较高的方法。其次，算法设计中不能用射线直接与点比较，需要先预处理用单元网格剖分点云数据，转化为射线与盒子求交。射线拾取的原理是：由于屏幕上绘制的实际上是人眼观察的结果，所以屏幕上一点对应于三维世界坐标系中的一条射线。通过判断这条射线与三维物体的相交情况，就可以得到拾取的结果。

1.2 点云模型上的射线拾取算法

点云模型上的点数量巨大且是散乱的，点与点之间存在空洞，所以不适合用射线直接与点比较。首先进行预处理：用包围盒划分点云散乱点，从而转化为射线与包围盒求交。所以首先用单元网格剖分点云数据：用分别垂直于X，Y，Z三个坐标轴的三组平行平面对点云数据进行均匀剖分，X，Y，Z方向剖分的步长不同，得到若干长方体盒子，从而把点云数据划分到若干盒子中[2]。其次通过射线逆运算方法计算射线上两点，从而确定屏幕上一点对应的射线。将射线与垂直于Z轴的那组平行平面（预处理中用分别垂直于X，Y，Z轴的3组平行平面划分点云数据）按Z值递增的顺序顺次求交。对每一个平面，计算平面与射线的交点，然后计算交点所在的盒子号，判断该盒子是否有效，直到找到第一个有效盒子，这就是射线拾取的盒子。上一步拾取的盒子中一般有几个到十几个点，计算这些点与射线的距离，取距离最小的一点为拾取得结果。

2 点云模型区域的交互定义和预处理

点云模型上的点是散乱的，点之间没有联接关系，对于这个问题，首先采用前面提到的单元网格剖分点云数据，从而问题转化为对包含点云数据盒子的填充。经过预处理，对点云模型的区域填充就转化为对包含这块区域中点的盒子的填充。区域的边界是Dijkstra最短路径算法计算得到的盒子序列。在点云模型上交互的拾取几个点，用Dijkstra最短路径算法计算两点间连线，从而用线连结这几个点，这样就选中一块区域。连接这几个点的封闭曲线就构成区域的边界。

3 点云模型区域填充

区域填充是指将区域内的一点（常称种子点）赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。在光栅图形学中，区域是二维的并具备一定连通性：四连通或八连通。常用的算法是种子填充算法。用盒子表示的点云模型是三维模型，对于每一个盒子，边邻接的盒子是12个，点邻接的是8个，面邻接的是6个，所以共有26个邻接的盒子，即点云模型上的区域是26连通的。将种子填充算法直接改为26连通就可以得到一个递归的填充算法，但是这个算法用于点云模型会出现填充溢出。下面通过分析溢出的原因和路径，得到点云模型上的一种有效区域填充算法[3-4]。

3.1 溢出分析

点云模型是用大量的点来表示三维物体的表面，所以原问题是一个曲面填充问题，用一条封闭曲线作边界，填充时不会溢出。经过预处理，对点云模型的区域填充就轉化为对包含这块区域中点的盒子的填充。问题转化后的模型是26连通的3维体，形状近似于曲面。要保证26连通的3维体一定不溢出，其边界应该是一个封闭的曲面。模型虽然形状近似于曲面，但其实还是26连通的3维体，所以一条封闭的曲线作边界不能保证不溢出。

以上是从理论上分析溢出原因，下面通过一个溢出实例分析溢出原因。从图1所示中可以看到，盒子m是内点，盒子n是外点。边界无法阻挡从m到n的扩散，即填充时会通过盒子m溢出。正如前面提到的盒子模型是26连通3维体，但其形状是近似于曲面的，这就把溢出路径限制在边界附近。进一步分析溢出路径，图2所示显示了两条边界附近的溢出路径，路径1通过盒子b溢出，路径2通过盒子c溢出。考虑点云模型的曲面是薄薄的一层点云，在把点划分到盒子中时，盒子b中有点是很有可能的，但盒子c中有点的可能性就很小，即溢出路径2发生的可能性很小。由以上分析猜测：算法1中的溢出都是通过边界盒子的相邻盒子溢出的。填充算法的设计就是基于这个猜测。

3.2 填充算法設计与实现

种子填充是遇到边界点则停止扩散，即对边界点不再扩散其邻点。针对点云模型上的填充会通过边界盒子的相邻盒子溢出的情况，填充算法的思路就是若遇到一个盒子其相邻盒子中有边界盒子，则停止对该盒子扩散。算法如下：对包含点云数据的盒子设置颜色，边界盒子为border-color，边界盒子的邻接盒子为badj-color，种子盒子为new-color，其它有效盒子是old-color。建立堆栈S，初始时S中仅包含种子盒子。对于每个出栈的盒子，将其26个邻接的盒子作如下处理：颜色为old-color的压栈并置为new-color，颜色为border-color的置为new-color。反复这个过程直至S为空。最后，颜色为new-color的盒子就是填充结果，填充这些盒子中的点，就得到点云模型上的填充结果。

结合前文提出的射线拾取算法，使用OpenGL实现程序并在dragon点云模型上测试，实验结果如图3所示。

4 结语

本文主要讨论了点云模型上的拾取和区域填充问题，提出有效算法。并实现了在点云模型上交互地选择区域得到区域中的点云数据，为进一步研究点云模型提供了有用结果。对于拾取算法，还可以考虑将点云数据组织成一定的层次结构，从而获得更高的效率;另外，为了获得更高的精确度，还可以进一步考虑具体的点绘制方式。对于区域填充，本文提出的算法是基于一定的猜测的，虽然实验中证明这种猜测对于大多数情况是正确的，但是也不排除例外情况，还有进一步研究的必要;另外，预处理有可能把相靠近的两个面连接在一起，这时也会填充溢出，但这与算法无关，是模型转化的问题，可以将盒子划分的更密或者采用其它方式转化模型。

参考文献

[1] Tomas Akenine-Moller，Eric Haines.实时计算机图形学（第2版）[M].北京：北京大学出版社，2004.

[2] OpenGL体系结构审核委员会，Dave Shreiner，Mason Woo等. OpenGL编程指南（第四版）[M].人民邮电出版社，2005.

[3] 杜培林，屠长河，王文平.点云模型上测地线的计算[C].第二届全国几何设计与计算学术会议，2005.

[4] 唐荣锡，汪嘉业，彭群生.计算机图形学教程[M].科学出版社，1994.

Design and Implementation of Region Selection

Algorithms for 3D Point Cloud Model

BAO Bin1， WU Yun-tao2

（1.Shangdong Woman University School of Data Science and Computer Science， Jinan Shandong  250300;

2.Shandong Kaiwen College of Science & Technology， Jinan Shandong  250200）

Abstract：In this paper a ray-based pick-up algorithm and a point cloud model area filling algorithm are proposed to realize the interactive selection of regions on the point cloud model. In this paper the algorithm is applied to the point cloud model. The experimental results show that the proposed algorithm is effective， fast and easy to implement.

Key words：point cloud model; pickup; region filling