点云数据场剖面云图绘制算法

第２Ｏ卷第４期　２０１１年１２月　计算机辅助工程　

Ｃｏｍｐｕｔｅｒ　Ａｉｄｅｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖ０１．２０　Ｎｏ．４　

Ｄｅｃ．２Ｏｌ１　

文章编号：１００６—０８７１（２０１　１）０４　００１９—０６　

点云数据场剖面云图绘制算法　徐龙　，　武殿梁　，　程奂羽中　，　（１．上海交通大学机械与动力工程学院，上海２００２４０；　２．上海市网络化制造与企业信息化重点实验室，上海２０００３０）　

摘要：为考察点云数据场中关键区域物理量数据分布，提出一种点云数据场剖面云图绘制算法．将　点云数据向剖面上投影，通过对获得的二维平面点集进行边界识别建立边环嵌套关系；通过确定物　理量与颜色的映射关系对剖面各区域进行颜色填充，可获得点云数据场任意位置的剖面云图．应用　结果表明该算法的鲁棒性和适用性较好，可用于考察点云数据场关键区域的物理量分布．　关键词：点云数据场；云图；Ｋ邻域；边界　中图分类号：ＴＰ３９１．７２　文献标志码：Ａ　

Ｒｅｎｄｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｏｎ　ｓｅｃｔｉｏｎ　ｃｏｎｔｏｕｒ　ｏｆ　ｐｏｉｎｔ　ｃｌｏｕｄ’。　ｆｉｅｌｄｐｏｉｎｔ　ａａｔａ　

ＸＵ　Ｌｏｎｇ　，ＷＵ　Ｄｉａｎｌｉａｎｇ　，ＣＨＥＮＧ　Ｈｕａｎｃｈｏｎｇ　，　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａｎｇｈａｉ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２００２４０，Ｃｈｉｎａ；　２．Ｓｈａｎｇｈａｉ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ａｄｖａｎｃｅｄ　Ｍａｎｕｆａｃｔｕｒｉｎｇ　Ｅｎｖｉｒｏｎｍｅｎｔ，Ｓｈａｎｇｈａｉ　２０００３０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｏ　ｉｎｖｅｓｔｉｇａｔｅ　ｔｈｅ　ｐｈｙｓｉｃａｌ　ｑｕａｎｔｉｔｙ　ｄａｔａ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｃｒｉｔｉｃａｌ　ｒｅｇｉｏｎｓ　ｉｎ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ　ｆｉｅｌｄ，ａ　ｒｅｎｄｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｏｎ　ｓｅｃｔｉｏｎ　ｎｅｐｈｏｇｒａｍ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｆｏｒ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ　ｆｉｅｌｄ．Ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ　ｉｓ　ｐｒｏｊｅｃｔｅｄ　ｔｏ　ｔｈｅ　ｓｅｃｔｉｏｎ，ｔｈｅｎ　ｎｅｓｔｅｄ　ｒｅｌａｔｉｏｎｓ　ｂｅｔｗｅｅｎ　ｂｏｕｎｄａｒｙ　ｅｄｇｅｓ　ａｒｅ　ｃｏｎｓｔｒｕｃｔｅｄ　ｂｙ　ｂｏｕｎｄａｒｙ　ｉｄｅｎｔｉｆｉｃａｔｉｏｎ　ｏｆ　２Ｄ　ｐｌａｎｅ　ｐｏｉｎｔ　ｓｅｔ；ａｌｌ　ｔｈｅ　ｒｅｇｉｏｎ　ｏｆ　ｔｈｅ　ｓｅｃｔｉｏｎ　ｉｓ　ｆｉｌｌｅｄ　ｗｉｔｈ　ｃｏｌｏｒ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｍａｐｐｉｎｇ　ｂｅｔｗｅｅｎ　ｐｈｙｓｉｃａｌ　ｑｕａｎｔｉｔｙ　ａｎｄ　ｔｈｅ　ｃｏｌｏｒ，ａｎｄ　ｔｈｅ　ｓｅｃｔｉｏｎ　ｎｅｐｈｏｇｒａｍ　ｑｕａｎｔｉｔｙ　ｉｎ　ａｒｂｉｔｒａｒｙ　ｐｏｓｉｔｉｏｎ　ｏｆ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ　ｆｉｅｌｄ　ｃａｎ　ｂｅ　ｏｂｔａｉｎｅｄ．Ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｇｏｏｄ　ｒｏｂｕｓｔｎｅｓｓ　ａｎｄ　ａｄａｐｔａｂｉｌｉｔｙ，ａｎｄ　ｃａｎ　ｂｅ　ｕｓｅｄ　ｔｏ　ｓｔｕｄｙ　ｔｈｅ　ｐｈｙｓｉｃａｌ　ｑｕａｎｔｉｔｙ　ｄａｔａ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｃｒｉｔｉｃａｌ　ｒｅｇｉｏｎｓ　ｉｎ　ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ　ｆｉｅｌｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｐｏｉｎｔ　ｃｌｏｕｄ　ｄａｔａ　ｆｉｅｌｄ；ｃｏｎｔｏｕｒ；Ｋ—ｎｅｉｇｈｂｏｒｈｏｏｄ；ｂｏｕｎｄａｒｙ　

０　引　言　云图用颜色连续变化的图像表示某个物理现象　或科学计算结果的变化趋势，将复杂数值：　问的变　化信息转换为图像颜色之间的变化关系，可使人直　观地了解数据的变化趋势．由于具有直观、形象的特　点以及能比数据提供更多信息的优点，云图成为科　学计算可视化＿ｌ　中常见的方法之一．目前，云图绘　制方法　主要包括单元网格填充法、等值线填充法　和扫描线算法等，但这些算法只处理含有有限元网　格信息的数据场，对于用点云数据描述的数据场，如　何得到任意位置的剖面云图，目前尚无成熟的理论．　

收稿日期：２０１０．１１　ｌｌ修回日期：２０１１—０１—０７　基金项目：上海市信息化发展专项资金　作者简介：徐龙（１９８４一），男，安徽阜阳人，硕士研究生，研究方向为科学计算可视化，（Ｅ－ｍａｉｌ）ｘｕｌｏｎｇｒｏｍａｎ＠ｓｊｔｕ．ｅｄｕ．ＣＢ　２０　计算机辅助工程　２０１１年　本文提出一种点云数据场剖面云图绘制算法，通过　将点云数据在剖面上投影，对获得的二维投影点集　进行边界识别　，建立边环嵌套关系，确定物理量　与颜色之间的映射关系，对剖面各区域进行颜色填　充，获得点云数据场任意位置的剖面云图．　

１　算法实现步骤　１．１点云网格划分和剖面投影　假设点云在空问中均匀分布，为加快处理速度，　需对点云进行网格划分．描述点云空间分布特征的　是点云密度　

点集合　Ｐ＝｛Ｐ　＝　，Ｐ，＝　１　Ｐ∈Ｐ，　∈　｝　相交网格中的点向平面上投影见图２，其中，黑点表　示原始投影点，圆圈表示平面上的点．　

图２相交网格中的点向平面上的投影　Ｆｉｇ．２　Ｉｎｔｅｒｓｅｃｔｅｄ　ｇｒｉｄｓ　ｐｍｊｃｏｔｉｎｇ　ｔｏ　ｐｌａｎｅ　ｏｆ　ｐｏｉｎｔｓ　

ｐ＝　Ｎ　（１）　１．２　二维点集边界自动识别　

式中：　为点云根路径包围盒体积；Ⅳ为点云数目．　设每个栅格中至多有ｎ个点，由点云密度可获　得栅格的边长　

（２）　为提高处理速度，应使分割出来的栅格形状接近于　立方体．点云根路径包围盒划分栅格过程采用半长　边二叉树分割方法，即每次都沿包围盒边长最大的　方向将包围盒分成２个子包围盒；若得到的子包围　盒的３条边长都小于Ｚ，则停止分割．将点云中的离　散点根据坐标值压人不同的空间栅格．在点云关键　区域设置剖面．厂，搜索点云中与　剖面距离在ｄ之内且投影在剖　面上的离散点．可利用网格加　速搜索，将剖面．厂沿其法线方　向移动ｄ（ｄ＞０）得到．　，移动　一ｄ得到．　，然后分别检测与　ｌ厂　和　相交的网格　，得到　的相交网格集合见图】．设相　

图１　

交网格包含的离散点集合为Ｆｉｇ．Ｉ　

，对于　∈力，若满足式（３）和　

（４），则　为平面ｌ厂投影点．　×Ａ＋　×Ｂ＋　Ｘ　Ｃ—Ｄ　

、　

与剖面及其平　行面相交的网　格示意　Ｇｒｉｄ　ｉｎｔｅｒｓｅｃｔｅｄ　ｔｈ　ｓｅｃｔｉｏｎ　ａｎｄ　ｐａｒａｌｌｅｌ　ｆａｃｅ　

＜ｄ　（３）　

ｖ＇＝ｖ￣Ｍｏｌ，　Ｉ　ｖ：ｌ＜　㈩　

Ｂｙ＋　＋Ｄ＝０；Ｍｒ），为由全局坐标系Ｍ０到厂平面局　部坐标系　的变换矩阵。　

南投影点集　可得投影到　平面上的二维离散　

用边界自动识别算法可找出．厂平面上的二维点　集Ｐ的内边界集和外边界集．该算法可分为Ｋ邻域　点搜索、边界特征点辨识和内外边界识别．Ｋ邻域点　搜索建立点集Ｐ中每个点与其周周点之间的联系；　边界特征点辨识在Ｋ邻域建立的基础上找出可能　的边界点；内外边界识别将找出的边界特征点连接　成边界线，同时排除不在边界线上的特征点．　１．２．１　Ｋ邻域点搜索　Ｋ邻域点搜索是点集预处理中的常用方法之　一，

利用空间分块策略　进行　个最近点搜索．假　

定点集Ｐ均匀分布，依据厂的面积Ｓ＝ｎ×ｂ和点集　

总数，ｖ可计算出正方形网格的边长ｆ　，将平面分成　许多大小相同的网格，每个采样点占据一个网格．在　首次划分时，网格边长　

（５）　在首次划分的基础上修正网格边长　

＝ｉ０√　（６）　

式中：Ⅳ　为非空网格数目；Ｎ　为所有网格数目．　再次对平面进行网格划分，随后遍历点集Ｐ，将　Ｐ中的每个点都归入相应的网格中．在搜索每个离　散点Ｐ（Ｐ∈Ｐ）的　邻域点前，还需设定搜索范围ｔ　（　与Ｐ的密度有关）．若Ｐ在　邻域点中部分点与Ｐ　的距离大于ｔ，则可认为这些点与Ｐ的关系不够紧　密，可将这些点从Ｐ的Ｋ邻域点中剔除．　基于上述思想的　邻域点搜索算法步骤如下：　步骤１根据式（５）和（６），对　划分网格，将所　有栅格存放在二维数组Ａｒｒａｙ中，对于栅格　Ａｒｒａｙ［ｉ］［Ｊ］，其邻近栅格在Ａｒｒａｙ中的下标（ｉ　√　）为　ｉ　＝ｉ±１；．　＝

．　

１　（７）　

＝　ｆ　第４期　徐龙，等：点云数据场剖面云图绘制算法　２ｌ　步骤２找到Ｐ所在平面网格，对该网格进行　逐步扩展，直到扩展ｍ倍边长Ｚ后，得到的子空间　Ｓ（ｍ）中包含的离散点数目第一次大于等于　步骤３在空间５（ｍ）中寻找Ｐ的Ｋ邻域点，首　先排除空间Ｓ（ｍ）中与Ｐ距离超过ｔ的点，剩余的点　组成点集　（ｎ），ｎ代表点集容量．若／２≤Ｋ，则　（／２）　为Ｐ的Ｋ邻域点集合；　否则，设ｄ　和ｄ　分别　为Ｐ到空间５（ｍ一１）　的　方向２条边和Ｙ方　向２条边中距离最小　值（见图３，图中黑点为　Ｋ邻域中的点），　ｄ：ｒａｉｎ（ｄ　，ｄ　），　（ｎ）　中与Ｐ距离小于ｄ的　／２　个点（０≤凡　≤ｎ）必　

。　。　一十　・　

●　●　・）　／　●　

０　‘＼　●　Ｃ　——　●　●　●　０　

图３　点Ｐ的Ｋ邻域点搜索　Ｆｉｇ．３　Ｋ—ｎｅｉｇｈｂｏｒｈｏｏｄ　ｓｅａｒｃｈ　ｏｆ　ｐｏｉｎｔＰ　

然在Ｐ的Ｋ邻域中，随后将　（ｎ）中剩余点按照与Ｐ　的距离进行排序，取距离最小的　—ｎ　个点作为Ｐ的　Ｋ邻域中剩下的点．　步骤４返回步骤２，直到点集中所有离散点都　处理完毕．　１．２．２边界特征点辨识　Ｋ邻域的建立为边界特征点　的检测提供基　础．如果点集ＪＰ中某点是边界特征点，其　邻域点　的分布将偏向某侧；如果是内部点，其　邻域点将　均匀地分布在该点的周围（见图４（ａ）和４ｌ＝ｂ））　

Ｐ　．　Ｐ．Ｐ　：　．‘　ｒ　

Ｉ　

、　．　ｆ　

●　

（ａ）ｐ点为边界特征点　（ｂ）ｐ点为内部点　

ｏ　ｏ　ｏ　

ＰＰ？，以ＰＰ？为基准，分别计算由点Ｐ到其余　邻域点　Ｐ：（０＜ｉ＜ｋ）的有向线段　：按照逆时针方向旋转到　ｐｐ？所经过的角度　，从而得到一个角度序列Ｓ＝　（　ｌ，Ｏ／２，…，　一１）．　步骤２对角度序列ｓ进行升序排列并加上２　个极值角度，得到新的角度序列　＝（０，　，　：，…，　＆　，２盯）．　步骤３计算　的角度序列差　Ｚ　＝　＋ｌ—　，ｉ＝０，１，…，ｋ一１　步骤４求出角度序列差中的最大值Ｚ…．假设　ｚ…为向量ＰＰ：和　之间的夹角，以ＰＰ　为　轴正方　向建立直角坐标系（见图４（ｃ）），若Ｐ在点集内部，　则Ｋ邻域点分布在４个象限中；若Ｐ是边界特征点，　则至少有１个象限没有　邻域点的分布．因此，可　由Ｚ　的大小判断边界特征点，即如果Ｚ　超过某阈　值，则判定Ｋ邻域点分布不均匀，Ｐ为边界特征点；　否则Ｐ为内部点．将ｚ　的阈值取为叮ｒ／２就能满足