机械设计与制造 １０２ 文章编号：１００１—３９９７（２０１ １）０６—０１０２—０２ Ｍａｃｈｉｎｅｒｙ Ｄｅｓｉｇｎ＆Ｍａｎｕｆａｃｔｕｒｅ 第６期 ２０１１年６月 基于Ｍａｔｌａｂ三维数据点三角剖分方法研究术 刘伟哲 王忠良 陈昌建 马铁利 （’河北师范大学，石家庄０５００１６）（ 河北工业职业技术学院，石家庄０５００９１） （。北京汽车工业控股有限责任公司，北京１０００２１） Ｒｅｓｅａｒｃｈ ｏｆ ３Ｄ ｄａｔａ ｐｏｉｎｔ ｔｒｉａｎｇｕｌａｔｉｏｎ ｂａｓｅｄ ｏｎ Ｍａｔｌａｂ ＬＩＵ Ｗｅｉ—ｚｈｅ ，ＷＡＮＧ Ｚｈｏｎｇ—ｌｉａｎｇ ，ＣＨＥＮ Ｃｈａｎｇ－ｊｉａｎ ，ＭＡ Ｔｉｅ—ｌｉ （ Ｈｅｂｅｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｉｊｉａｚｈｕａｎｇ ０５００ １ ６，Ｃｈｉｎａ） （ Ｈｅｂｅｉ Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｄｕｓｔｙ ｒａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈｉｊｉａｚｈｕａｎｇ ０５００９１，Ｃｈｉｎａ） （ Ｂｅｉｊｉｎｇ Ａｕｔｏｍｏｔｉｖｅ Ｉｎｄｕｓｔｙ Ｈｏｌｒｄｉｎｇ Ｃｏ．，Ｌｔｄ．Ｂｅｉｊｉｎｇ １０００２１，Ｃｈｉｎａ） 【摘要】逆向工程中点云数据点三角划分处理，在散乱数据插值曲面构造、快速原型制造以及有 限元分析等方面有着重要的应用。根据Ｄｅｌａｕｎａｙ三角划分理论及Ｌａｗｓｏｎ优化准则，借助于Ｍａｔｌａｂ中 用于点云处理模块快速实现了空间散乱数据点的直接三角划分，给出了数据点三角划分程序代码，并 以某小客车车身外表面点云数据处理过程加以验证，给出其外形数据点Ｄｅｌａｕｎａｙ三角划分以及凸壳包 络图，由此可以早期发现逆向设计过程中可能存在的问题，从而减少后期修改次数，极大缩短新产品的 开发周期，提高了设计精度。 关键词：逆向工程；预处理；Ｖｏｒｏｎｏｉ图；Ｄｅｌａｕｎａｙ三角剖分 【Ａｂｓｔｒａｃｔ】／ｎ ｒｅｖｅｒｓｅ ｅｎｇｉｎｅｅｒｉｎｇ，ｔｈｅ ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｆ３Ｄ ｃｌｏｕｄ ｄａｔａ ｉｓ ｐａｙｉｎｇａｎ ｉｍｐｏｒｔａｎｔ ｒｏｌｅ ｉｎ ｉｎｔｅｒ— ｐｏｌｔｉａｏｎ ｓｕｒｆａｃｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ，ｒａｐｉｄｐｒｏｔｏｔｙｐｉｎｇｍａｎｕｆａｃｔｕｒｉｎｇａｎｄｆｉｎｉｔｅ ｅｌｅｍｅｎｔａｎａｌｙｓｉｓｆｏｒ ｓｃａｔｔｅｒｅｄｄａｔａＩｔ ｆｏｃｕｓ ｏｎ ｔｈｅｆａｓｔ ｔｒｉａｎｇｕｌｔａｉｏｎ ｆｔｏｈｅ ｓｃａｔｔｅｒｅｄｐｏｉｎｔ ｃｌｏｕｄ ｂａｓｅｄ ｏｎ Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌｔｉａｏｎ ａｎｄ Ｌａｗｓｏｎ’ｓ ｏｐｔｉ－ ｍｉｚａｔｉｏｎ ｌａｗ ｗｉｔｈ ｔｈｅ ｈｅＺｐ ｏｆｐｏｉｎｔ ｃｌｏｕｄ ｍｏｄｕｌｅ ｉｎ Ｍａｔｌａｂ．Ｔｈｅｎ ｔｈｅ ｐｒｏｇｒａｍ ｃｏｄｅ ｆｏｒ ｔｈｅ ｔｒｉｎｇａｕｌｔｉａｏｎ ｆｄａｏｔａ ｐｏｉｎｔ ｉｓ ｐｒｏｖｉｄｅｄ ｎｄ ａｉｓ ｖｅｒｉｉｅｄ ｆｗｉｔｈ ｔｈｅ ｐｏｉｎｔ ｃｌｏｕｄ ｄａｔａｐｒｏｃｅｓｓ ｒ ｅｘｔｅｒｎａｌ ｆａ ｏｍｉｎｉｂｕｓ ｂｏ Ｗｉｔｈ ｔｈｅ ｔｒｉａｎ－ ｕｌｇａｔｉｏｎ ａｎｄ ｔｈｅ ｃｏｎｖｅｘ ｈｕｌｌ ｏｆｔｈｅ ｐｏｉｎｔ ｃｌｏｕｄ，ｔｈｅ ｐｒｏｂｌｅｍｓ ｉｎ ｒｅｖｅｒｓｅ ｅｎｇｉｎｅｅｒｉｎｇ ｃａｎ ｂｅ ｄｅｔｅｃｔｅｄ ｉｎ ｔｈｅ ｅａｒｌｙ ｓｔａｇｅｓ．ｈ ｃａｎ ｓｈｏｒｔｅｎ ｔｈｅ ｒｅｓｅａｒｃｈ ｃｙｃｌｅ ａｎｄ ｔｈｅｎ ｉｍｐｒｏｖｅ ｔｈｅ ｄｅｓｉｇｎ ａｎｄ ｍａｎｕｆａｃｔｕｒｅ ｐｒｏｃｅｓｓ． Ｋｅｙ ｗｏｒｄｓ：Ｒｅｖｅｒｓｅ ｅｎｇｉｎｅｅｒｉｎｇ；Ｐｒｅ－ｐｒｏｃｅｓｓ；Ｖｏｒｏｎｏｉ；Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｔｉｏｎ 中图分类号：ＴＨ１２，Ｕ４６文献标识码：Ａ ・ ｊ Ｉ— …ｌ Ｉ商 ， （ ）｝称作由点集Ⅱ生成的Ｖｏｒｏｎｏｉ图，它是Ｓ的一部分。 ｏｎｏｉ多边形的边称作Ｖｏｒｏｎｏｉ边，Ｖｏｒｏｎｏｉ边的端点称作 逆向工程广泛应用在机械产品设计中，随着现代测量技术 这里Ｖｏｒｏｎｏｉ顶点。 的发展，可以得到实体表面数万甚至几十万特征数据点，这在理 Ｖｏｒ论上能够准确地模拟实体表面，但是大量的测量数据带来的问题 若至少存在一个Ｖｏｒｏｎｏｉ顶点，且在该顶点有四条或更多条 ｒｏｎｏｉ边相交，则此Ｖｏｒｏｎｏｉ图 （Ⅱ）为退化的。若Ｖｏｒｏｎｏｉ多 是计算复杂，计算时间很长，计算过程中计算机内存的占用也很 Ｖｏ ）与 （ ）共享一条Ｖｏｒｏｎｏｉ边，则 点与 点称作 大，所以现在逆向工程中的一个“瓶颈”就是数据点的预处理，而 边形 （如图１所示，是ｍａｔｌａｂ中随机给定５０个数据点得到的 这其中的一个重要研究课题就是数据点三角剖分，利用Ｍａｔｌａｂ 相邻点，ｏｎｏｉ多边形。 可以快速实现了散乱数据特别是大规模散乱数据的三角剖分，这 Ｖｏｒ对于迅速构建数据点之间的拓扑连接关系，进而快速准确地生成 优化的三角网格，为构造散乱数据插值曲面做好准备有重要的现 实意义。 ２点云数据的三角剖分相关理论’ ２．１ Ｖｏｒｏｎｏｉ图（域分割） 给定实平面Ｓ（ＳＣＲ ）上一组点ＩＩ＝｛订 ’。， ｝，其中，竹 ＝ （ｘｉ， ）则： （＇ｆｉ）＝｛ ｓ：Ｉ ｌ— Ｉ ｌ≤ｌ ｌ Ｉ Ｉｆｏｒｊ＃ｉ｝ （１） 图１ Ｖｏｒｏｎｏｉ图 称作与１Ｔ 相关的Ｖｏｒｏｎｏｉ多边形，其集合Ｖｓ（ＩＩ）＝｛Ｖ（丌１）， ★来稿日期：２０１０－０８－０６★基金项目：河北省教育厅指导项目（Ｚ２０１０１５４），河北师范大学青年；￣Ｉ（Ｌ２００８Ｑ１７） 第６期 刘伟哲等：基于Ｍａｔｌａｂ三维数据点三角剖分方法研究 １０３ ２．２ Ｄｅｌａｕｎａｙ三角剖分 ｚ＝Ｘ（：，３）； 若点集Ｉ１上的点不共线，则通过连接Ｖｏｒｏｎｏｉ图 （Ⅱ）上 ｄｉｓｐ（‘Ｗａｉｔｉｎｇ…’）； 的相邻点可得到Ｄｅｌａｕｎａｙ三角剖分Ｄ（Ⅱ）。若ＶＲ２（１Ｉ）是退化 ｔ＝ｃｐｕｔｉｍｅ； 的，则Ｄｅｌａｕｎａｙ三角剖分不是唯一的。如图２所示，是根据图１ ％ＴＥＳ１＝ｄｅｌａｕｎａｙ（ｘ，Ｙ）； 的数据得到的Ｄｅｌａｕｎａｙ三角剖分的结果。 ＴＥＳ２＝ｄｅｌａｕｎａｙ３（ｘ，ｙ，ｚ）； ｄｉｓｐ（‘ｓｉｚｅ ｏｆＴＥＳ’）， ％ｄｉｓｐ（ｓｉｚｅ（ＴＥＳ１））， ｄｉｓｐ（ｓｉｚｅ（ＴＥＳ２））； ％ｔｒｉｓｕｒｆ（ＴＥＳ１，ｘ，Ｙ，Ｚ，’ＦａｃｅＣｏｌｏｒ‘，’ｒ’，‘ＥｄｇｅＣｏｌｏｒ’，‘ｎｏｎｅ’）， ｌｉｇｈｔｉｎｇｐｈｏｎｇ，ｓｈａｄｉｎｇｆｌａｔ，ａｘｉｓ ｓｑｕａｒｅ，ｔｉｔｌｅ（‘２－ｄｄｅｌａｕｎａｙ’）； ％ｖｉｅｗ（【一６０，１ｏ］） ％ｔｒｉｓｍｅｓｈ（ＴＥＳ１，ｘ，Ｙ，ｚ，‘ＥｄｇｅＣｏｌｏｒ’，‘ｋ’），ｌｉｇｈｔｉｎｇ ｐｈｏｎｇ， ｘａｉｓｅｑｕａｌ，ｔｉｔｌｅ（‘２－ｄｄｅｌａｕｎａｙ’）； ｔｅｔｒａｍｅｓｈ（ＴＥＳ２，Ｘ，‘ＦａｃｅＣｏｌｏｒ＇，‘ｎｏｎｅ’，‘ＥｄｇｅＣｏｌｏｒ＇，‘ｋ＇），ｌｉｇｈｔｉｎｇ 图２ Ｄｅｌａｕｎａｙ三角剖分 ｐｈｏｎｇ，ａｘｉｓ ｅｑｕａｌ，ｔｉｔｌｅ（‘３－ｄ ｄｅｌａｕｎａｙ’）； ２．３ Ｄｅｌａｕｎａｙ三角剖分优化准则 ｃａｍｏｒｂｉｔ（３７．５，６０）； ｘｌａｂｅｌ（‘Ｘ’）； Ｄｅｌａｕｎａｙ三角剖分有很多特性，在构建搜索Ｄ（Ⅱ）算法时 ％ｃａｍｏｒｂｉｔ（ｄｔｈｅｔａ。ｄｐｈｉ）ｒｏｔａｔｅｓ ｔｈｅ ｃａｍｅｒａ ｐｏｓｉｔｉｏｎ ａｒｏｕｎｄ 的一个重要性质是最大一最小角度准则，又称为Ｌａｗｓｏｎ准则。此 ｔｈｅ ｃａｍｅｒａ ｔａｒｇｅｔ ｂｙ ｔｈｅ ａｍｏｕｎｔｓ ｓｐｅｃｉｆｉｅｄ… 准则可叙述为，任意合并两个三角形且严格外凸的四边形Ｑ，其 ％ｉｎ ｄｔｈｅｔａ ａｎｄ ｄｐｈｉ（ｂｏｔｈ ｉｎ ｄｅｇｒｅｅｓ）．ｄｔｈｅｔａ ｉｓ ｔｈｅ ｈｏｒｉｚｏｎｔａｌ 对角线的选取方法是使由该对角线分得的两个三角形的最小内 ｒｏｔａｔｉｏｎ ａｎｄ ｄｐｈｉ ｉｓ ｔｈｅ ｖｅｒｔｉｃａｌ ｒｏｔａｔｉｏｎ． 角为最大，如图３所示，由于ＡＡＢＤ和ＡＣＢＤ六个角中的最小角 ｔｔ＝ｃｐｕｔｉｍｅ—ｔ；ｄｉｓｐ（ｔｔ）； ￣．ＬＡＡＢＣ和ＡＣＡＤ六个角中的最小角Ｏｌ大，所以ＢＤ连线为所 ｄｉｓｐ（‘ｏｋ’） 求的对角线。Ｓｉｂｓｏｎ指出Ｄｅｌａｕｎａｙ剖分是唯一满足Ｌａｗｓｏｎ准则 ％ｈｏｌｄ ｏｎ，ｐｌｏｔ３（ｘ，ｙ，Ｚ，‘＋ｒ’）； 的三角剖分方法。Ｌａｗｓｏｎ证明了此准则与圆准则是等价的。若ｋ 是通过Ｑ上任意三个顶点的圆，并且第四顶点在圆ｋ的内部，则 连接此顶点与其对应点的线即为所求的对角线。对非退化的 立 Ｖｏｒｏｎｏｉ图 。 （Ⅱ）而言，Ｄ（Ⅱ）是唯一的 。 。 ： ，∞ 一， 一 皇曙：＝ 兰三苦醚 ２ ：嚣 芝 ：＝： ■■＿■■＿ ■■■＿■■■■■ 图４轿车车身部分包络图 图５轿车车身部分数据三角化 ４结论 ＭＡＴＬＡＢ采用了面向对象技术，以矩阵运算为基础，用户可 以非常方便地建立自己的函数或应用程序，特别适于科学计算、 图形图像处理、数据的拟合与可视化，在海量数据点预处理中快 图３ Ｌａｗｓｏｎ准则 速实现了空间散乱数据点的三角化，提高了设计精度和速度。 ３对三维散乱数据点进行三角剖分 参考文献 利用Ｄｅｌａｕｎａｙ三角剖分得到的某轿车车身表面的点云处理 ［１］金涛，童水光．逆向工程技术［Ｍ］．北京：机械工业出版社，２００３． 结果，处理时以ＸＯＹ作为数据基点，该点云有８５７３０个数据点， ［２］朱心雄，等 由曲线曲面造型技术［Ｍ］．北京：科学出版社，２０００． 得到１７１２７１个三角形，程序代码如下所述，Ｍａｔｌａｂ程序输出的结 ［３］Ｄａｖｉｄ Ｒｉｃｈａｒｄ Ｍａｒｋ Ｈｅｒｒｉｅｋ．Ｗａｖｅｌｅｔ ｍｅｔｈｏｄｓ ｆｏｒ ｃｕｌ￣ｅ ａｎｄ ｓｕｒｆａｃｅ ｅｓｔｉｍａｔｉｏｎ［Ｄ］．Ｐｈ．Ｄｔｈｅｓｉｓ，ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓｏｆｔｈｅＦａｃｕｌｔｙｏｆＳｃｉｅｎｃｅ， 果，如图４、图５所示同。 Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｂｒｉｓｔｏｌ，２０００（１）． ｆｕｎｃｔｉｏｎ ３Ｄ＿ｄｅｌａｕｎａｙ２ ［４］Ｒｏｍａｎ Ｋａｚｉｎｎｉｋ ａｎｄ Ｇｅｒｓｈｏｎ ＥｌｂｅＬＯｒｔｈ０ｇ０ｎａｌ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｏｆ Ｎｏｎ— ｌｏａｄ ｂａｃｋｓｈｏｕｋｏｕ ２５２９．ａｓｃ ＵｎｉｆｏｒｍＢｓｐｌｉｎｅＳｐａｃｅｓｕｓｉｎｇＷａｖｅｌｅｔｓ［Ｃ］，１９９７，１６（３）． Ｘ＝ｂａｃｋｓｈｏｕｋｏｕ ２５２９； １５ Ｊ Ｈｏｎｇ—Ｗｅｉ Ｌｉｎ，Ｃｈｉｅｗ—Ｌａｎ Ｔａｉ，Ｇｕｏ－Ｊｉｎ Ｗａｎｇ．Ａ ｍｅｓｈ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｄｒｉｖｅｎ ｂｙ ａｎ ｉｎｔｉｒｎｓｉｃ ｐｒｏｐｅｎｙ ｏｆ ａ ｐｏｉｎｔ ｃｌｏｕｄ…．Ｃｏｍｐｕｔｅｒ－ ｘ＝Ｘ（：，１）； Ａｉｄｅｄ Ｄｅｓｉｇｎ，２００４（３６）：１－９． ｖ＝Ｘ（：，２）； ［６］Ｍａｔｈｗｏｒｋｓ Ｃｏｍｐａｎｙ．ＭＡＴＬＡＢ ｖ６．５ Ｒ１３ Ｏｎｌｉｎｅ ｈｅｌｐ ｄｏｃｕｍｅｎｔ，２０００．