三维散乱点云凸包快速求解算法

机械设计与研究第25卷第25卷第4期2009年8月机械设卄与研究Machine Design and Research机械设计与研究第25卷机械设计与研究第25卷文欢缩号：1006-2343( 2009)044)11-03三维散乱点云岳包快速求解算法孙殿柱，朱昌志.李延瑞，刘健(山东理工大学 机械工程学院，淄博25509LE-mail： zhuchzhi)摘 S：极出一种三维散見点云凸包快逢求辑算法该算法建立点集內外包图盒.依捋包囲盒对点云議擁 进行初純排除大量不可能构成凸包的数据点减小束解凸包时的敏摒处理量過过才析简后的点集求解四包 实现对整个点云的凸包求解茨例表明该算法实现简单可显著提高凸包的求解效卓关律词：敵乱点云；内包围盒;外包图盒;精简;凸包中图分英号：TP391.72 文献标识码：AAccelerating Algorithm for 3D Convex Hull Construction of Scattered DataSUN Dian-zhu, ZHU Changdi, U Yan-rui, UU Jian(School o Mechanical Engineering, Shandong University of Technology, Shandong Zibo 255091, China)Abstract： An accelerating algorithm for 3D convex hull construction of scattered data is proposed, which han three steps： first, the inner and outer boundary box of scattered daU is constructed; second, the scattered data is reduced according to inner boundary box; third, the solution for the convex hull construction of whole scattered data is realized just through constructing the convex hull of dala after reduction Bus algorithm has been proved simple to implement and more efficient than traditional methods.Key words： scattered data； inner boundary box； outer boundary box； data reductKO； convex hull机械设计与研究第25卷机械设计与研究第25卷凸包求解算法在逆向工程、计算机图形学、先进制逍技 术等领域有着广泛的应用同时作为最小覆強问题i的求解方 法之一，广泛应用于建筑体建模、卫星通信、无线电广播尊 领域“叫目前国内外学昔对凸包求解算法进行了大的研究. 但对散乱点云的凸包求解还不成熟。文献1.4采用卷包寰 算法由初始凸包面片迭代求解与其含公共边且夹角R大的 面片实现点云凸包的求解文紙5-7采用增最法求解点 云凸包即由初始四面体开始通过逐个引入外部点来迭代 求解凸包。上述方法在求解凸包时需迓历点云所有点而通 常悄况下凸包只是由部分数据点构成如能将不可能成为凸 包頂点的数据点预先剧除則可较大提高凸包的求解效率。 文猷8对点云进行空间櫃格划分，通过两次投够排除不可 能包含凸包頂点的榻辂再对各层榻格求解凸包该方法求 解的是栅格的凸包而不是点云的凸包不能准确反映点云 的凸包信息且采用逐层投够方法排除内部点计算it大。针对上述问题F面拟构建包含点云所有点的最小外包 围盒分别求解谏包圈盒八个顶点的嚴近点建立该点集釣 各条棱均平行于坐标轴的内包圈盒依据内包圈盒对点云进 行精简通过对榊简旨的点集求解凸包实现对整个点云的凸 包求解实例证明该It法具有实现简单、运行效率高的优点。收9!： 2009 -02-23基金項目：发晨卄划贵助填目(63计划.2006AA04Z105)1数据精简为提离敵乱点云凸包的求解速度可通过建立点集内外 包围盒对数据点进行辅简排除大量不可能成为凸包頂点的 数据点具体精简步骤如下：Stepl：求解点集外包围盒求解图la所示点集在三个坐标轴上的极值j龙2、儿z*. 如图 lb 所示以 % =(%_/*)、 为对角顶点建立包含所有点且各条棱均 平行于坐标轴的外包围盒0RB =此时外包围盒的其它六个頂点坐标可求。Step2：求解外包围盒备頂点的最近点 分别求解外包国盒OBR = (%,%)的八个顶点的最近 点构成点集I |pJi=0Jt t7|oStep3：建立点集内包围食如图lc所示建立不包含X中任一点且各条梭均平行 于坐标轴的内包围盒/ = (叫山)气、叫分别为内包甩盒 的最小、最大頂点。Slep4：对数据点进行辅简若点P欄足叫pvi9则表示该点位于内包国盒内部, 将其从点集庠列中制除实现数据点的精简，对图la所示点云数据进行精简图lb Jc分别为外包 围盒及内包阖盒包含的数据点从图中可以看岀，采用精简 算法，推除了大不可能成为凸包頂点的数据点，桟少了参 与求解凸包的数据达到了精简的目的。(a)点云教撫(b)外包阳金(c)内包働金图1点云敢据的榊简2凸包求解令CH(S)为构成凸包的三角面片集合初始值为空求 解点云S凸包的算法步驟如下：S(epl :任取不共面空四点构成四鹵体作为初始凸包将 四个面片添加到集合C(S)中；S(ep2：采用公式(I)计算凸包务面片的外部点集；Sep3：若各面片的外部点集均为空程序结束;否則执行3ep4；S0所以可对公式(1)简化，采用公式 (2)计算d值大小。+ D(2)若d大丁零农示该面片与点p相互可见否则不可见。 图2为三维凸包计算过程的一个迭代步51。对于给定 点集S假定经i迭代得到的凸包为CH(SJ.p为CH(SJ的 外部点杳询点P的可见面片并将其从Cf/(S.)中咼除提取 该面片集合组成区域的边界连接点p及各边界边的端点, 形成新的面片集合并添加到CH(SJ中得到凸包CH(St9p)9 如图2 b所禾。()三结凸包CH(St) (b)增加一个点后的三维凸包CH(Sj.p)图2三维凸包计算过程的一个这代步3算法分析计算点云在三个坐标紬上的六个极值点求解最小外包 围盒只需遍历一次点云，时间复杂度为0(n)；询最小包 围长方体的八个頂点的斤近点时间复杂度为05);构建八 个说近点的最大内包围金时间复朵度为0(1)；采用增最法 求解点云凸包时间复杂度为0：创十卅)“为点云数据点 数为组成凸包的面片数;因为本文对数据点进行了精简， 预先排除了大内部点所以实际参加凸包求解的点数小于 叭上述算法的时间复杂度小于Oimnm2).4应用实例可以采用大fit实例来验证上述算法。图3为其中四组， H3 3四组点云及其凸包第4期孙殿柱等:三维散乱点云凸包快速求解算法13从图中可以看出采用该算法求解点云凸包是准确可行的。 下表为该算法与文猷8j算法运行时间之比较从表中可以 看出，该算法只对点云30% -80%的数据点求解凸包截小 了数据处理最提髙了求解效率,平均提A 29% -78% 0对 于复杂外形点云，诙算法将更加显着的提髙其凸包求解本文算法与文M(S)法运行时何比絞聂点云文献8算法本文算法点云点数外部点数时间/外部点数时间/点云】2 6552 6550.16112000.102点云2675167511.1593 1230.571点云31274412 7442.1975 8951.834丄云430 936309365.00719 3353.1395结论上述算法与相关算法相比具有以下优点：(0通过建立内外包圈盒对点云糯简排除了大債不可 能成为凸包頂点的数据点提高了凸包的求解效率；(2) 对数据点精简的算法易于实现且同样适用于卷襄 法等其他凸包求解算法。參考文献1 Chand D R. Kaqur S S. An alpriihm for coarex polytope* J. JACM.1970J7 (l)：78 -86.21 0筝陈 晓周宏周等.基于凸包算法的三集表中边 缘轮饶提取(JJ-M 机发 *.2004.14(12):39-41.443 吴威刨步味基于三角龙的三维点集C包快速求取算 东华大学学报(自体科学版).2008.34(3):311 -314.4 吳克動杨冠杰空何点集卷包農算法的优化实现J)青岛海 洋大学:学报,2003.33(4)血7633.5 Yang W,Ding H.Xkm Y. Manufacturability Analy&is for a Sculptured Surface Using Visibility Cone CocnpuUtion J . Intcm&Uonal Journal of Advanced Manufictuhng Technology, 1999,14(2) ：317、 321.6 Yang W Y.Ding H.Xiong YL. Manufictunbility Anftlywis (or Sculptured Surface Usinf Viability Cone Computation J . Intemaiional JounuJ of Advanced Manufacturing Technologj*,1999,15(5) 317 * 321.7 杨文玉胡雯養廉冇伦基于三壊凸包的可变形髙敵网J中国机械匸程.2004.15(22)：2040 20438 杨妫年汪国昭.三维凸包的快速算浙江大学学报. 1999,33 (2) ：111 *113.作者蒲介研克才向为反欢工 tCAD/CAM-体化巳发晨论丈76茂.及。第4期孙殿柱等:三维散乱点云凸包快速求解算法13第4期孙殿柱等:三维散乱点云凸包快速求解算法1300。000。8。0008000。8只。008000800000。0080000008。0800800800000000000。880(上接第10页)第4期孙殿柱等:三维散乱点云凸包快速求解算法13第4期孙殿柱等:三维散乱点云凸包快速求解算法133结论以上提出了一种新的产品设计理念及方一RPS。 RPS基于MPM技术使用一系列可塑性模块来构建一个系 统模型。在RP5中用户期望的系统可以由一个二维或三 维图像表示於后RPS方法以可塑性模块MPM为原材 料” 根据自动计算所得岀的布局方案来填充”这个图像所 表示的空间最后使用手工或考计算机辅助方法来完成产品 的系统实体模型。事实上，如果我们把MPM作为一种粉末 或者颗粒状的原材料那么RP-C中的选区激光烧结技术 (selective laser sintering)就与 RPS 非常相似的。尽管RP-S可以大大提高系统设计的效率以及质*於 而要真正得将此项技术椎广到实际运用还需要大的后续 工作比如:将运动和动力模块布置到MPM系统中使用一 种更便捷的虚拟模型表达方式根据MPM布置方案自动拼 装实体模5!等等。參考文献(1) 辛;en祁文隼孙文為等.逆向工程与快連成u体化在现 代产品设计中的应用口机床与液压.2007 . 35(12)：52 54.2 张兰成.快速原取技术对传统产品设计的形响J集团经济 研究.2007.237 ： 270.3 Alibaba Retrieved July 22 2008, OL t http：/lieoong. (mat-pawi. alibabaproduct/12214846/FDM_ Rapid .Prototyping_Services, html.41青木昌彥.模块时代一i?产业结构的本质M上梅:远东出 版社.2003.5 Gizznodo. Retrieved December 31,2007. 0L . http：/pzmodo com/ gad|*eU/|dgeU/ legtHni ndslorrm-tut-preorder-Urt-april -1 162297. php.6 PpOlO(“ d. ). Retrieved April 19 . 2009. web site, http：/ www. ppOIO. (xxik/images/prodDeUila/5835. jpg.7 Paipai, (n. d. ). Retrieved April 19. 2009. web Etc. http：/im- 畔.paipai. com/ac59bb32/iua031279BDB39C22400000000005 B36C2030D6HB. I.jpg3.jpg8 Wanihanfhai, ( n. d. ). Retrieved April 19. 2009. web site, hi- tp：/www. wanphanhai. com/ SH POOOO1 / fruntcvKL/shopdiu/ SHP00001/inee/prod/l(XX)l24342 jpg.9 Ledzx. (n.i) Retheved April 19 . 2009. web wte, http：/ www. ledzx.exxn/uter/ pnxiuct/srodDcSila/4487. jpg.11J Jirjen9 (n. d. ). Retrieved Ajml 19 , 2009, web tile, http：/ www. jirjen de/ wocdpreee/*p)ntent/ pix/ 12 Gwr|3ba0eiuem ( u. d. Retrieved Apvil I9t 20091 web bHc. www. georfsbasement. coo/PandWplaner. btm.作者简介:X丈(1985左生，主要研丸才向为现代设卄才法理论及应厲。第4期孙殿柱等:三维散乱点云凸包快速求解算法13三维散乱点云凸包快速求解算法作者：孙殿柱，朱昌志，李延瑞，刘健，SUN Dian-zhu， ZHU Chang-zhi， LI Yan-rui ， LIU Jian作者单位：山东理工大学机械工程学院淄博,255091刊名：机械设计与研究|二|：|厂-1英文刊名：MACHINE DESIGN AND RESEARCH年，卷(期):2009,25(4)参考文献(8条)1. Chand U R;Kaqur S S An algorithm for convex polytepes 1970(01)2. 吴克勤;杨冠杰 空间点集卷包裹算法的优化实现期刊论文-青岛海洋大学学报(自然科学版)2003(04)3. 吴威;谢步瀛 基于三角形的三维点集凸包快速求取算法期刊论文-东华大学学报(自然科学版)2008(03)4. 曾筝;陈晓;周宏周基于凸包算法的三维表面重建中边缘轮廓提取期刊论文-微机发展2004(12)5. 杨勋年;汪国昭三维凸包的快速算法1999(02)6. 杨文玉;胡雯蔷;熊有伦基于三维凸包的可变形离散网格模型期刊论文-中国机械工程2004(22)7. Yang W Y;Ding H;Xiong Y L Manufacturability Analysis for Sculptured Surface Using Visibility ConeComputation 1999(05)8. Yang W;Ding H;Xiong Y Manufacturability Analysis for a Sculptured Surface Using Visibility ConeComputation 1999(02)本文读者也读过10条)1. 赵小林.陈朔鹰.刘然一种在计算机上生成凸包的算法期刊论文-计算技术与自动化2003,22(4)2. 刘润涛.王三.安晓华.LIU Run-tao . WANG SaiAN Xiao-hua求平面点集凸壳的一种新算法期刊论文-计算机工 程与应用2009,45(3)3. 张飞.谢步瀛.闫星宇.刘政.ZHANG Fe.iXIE Buying . YAN Xingyu. LIU Zheng改进的三维点集凸包求取算法期刊 论文-计算机辅助工程2009,18(1)4. 马朝霞.高健.陈新.MA Zhaoxia. GAO Jian. CHEN Xin修复过程中磨损曲面重构的研究期刊论文-机床与液压 2009,37(10)5. 李志.李儒琼.LI Zhi . LI Ru-qiong 一种改进的快速三维凸包生成算法及实现期刊论文-计算机工程与科学2011,33(2)6. 陈平.汪国昭.CHEN Ping WANG Guo-zha(基于有序点列的平面点集凸包的新算法期刊论文-科技通报2007,23(6)7. 吴克勤.杨冠杰 空间点集卷包裹算法的优化实现期刊论文-青岛海洋大学学报(自然科学版)2003,33(4)8. 刘润涛简单多边形凸包的算法期刊论文-哈尔滨理工大学学报2002,7(2)9. 杨中华.Yang Zhonghua平面有限点集最小凸包集的计算方法期刊论文-北京工业大学学报2000,26(4)10. 李光军.郑军红.张光忠.LI Guang-jun . ZHENG Jun-hongZHANG Guang-zhon旷种凸包的改进算法设计与实现期刊论文-现代计算机(专业版)2010(6)本文链接：