（计算数学专业论文）平面点云曲线重建的一种新算法.pdf

本人郑重 所取得的成果 体已经发表或 已在文中以明 学位论文 本人在导 根据郑州大学 或机构送交论 可以将本学位 或者其他复制 或与该学位论 保密论文在解 学位论文 摘要 由点云重建出曲线、曲面模型在逆向工程( r e v e r s ee n g i n e e r i n g ) 1 - 4 中有着广泛的 应用某些曲面重建问题可以转化为曲线重建问题来研究针对甲面点云曲线重建可以 通过适当的数据压缩来减少点云的数量，从而减少计算量? 提高重建效率通过构造一个反 映平面点集形状与分布稠密的场函数【5 】，并用场函数曲面的脊线在甲面上的投影作为点 云的重建曲线为了求出重建曲线，首先应当选择一条合适的初始曲线，然后让初始曲线 沿场函数的梯度方向运动，并且以血线的极限位置为重建曲线例证表明该方法足一个简 单、有效、应用较广的曲线重建方法 关键词：点云，数据压缩，曲线重建，场函数 a b s tr a c t t h ec u r v ea n ds u r f a c er e c o n s t r u c t i o nf r o mp o i n tc l o u dp l a y sa ni m p o r t a n tr o l ei n r e v e r s ee n g i n e e r i n g a l s o ，s o m es u r f a c er e c o n s t r u c t i o nc a nb ei n v e s t i g a t e dt h r o u g hc u r v e r e c o n s t r u c t i o n a sf a ra st h ep o i n ts e ti nt h ep l a n ec o n c e r n e d ，w ec a nc o m p r e s st h ep o i n t s t ol e s s e nt h ew o r kn u m e r a t i o n w ec r e a t eaf i e l df u n c t i o nt h a tc a nr e f l e c tt h es h a p ea n d d i s t r i b u t i o no ft h ep o i n ts e t t h e nt h ep r o j e c t i o no fm a i nr i d g ec u r v eo ff i e l df u n c t i o n s u r f a c eo nt h ep l a n ec a nb et a k e na st h er e c o n s t r u c t i o nc u r v eo ft h ep o i n ts e t t of i n dt h e r e c o n s t r u c t i o no ft h ec u r v e ，f i r s t l y , w ec h o o s ea na p p r o p r i a t ei n i t i a lc u r v ea n dm o v ee v e r y p o i n to ft h ec u r v e a l o n gt i l eg r a d i c u td i r e c t i o no ft h ef i e l df u n c t i o n t h u s ，w ec a nc h o o s et h e l i m i tp o s i t i o no fa c t i v ec u r v ea st h er e c o n s t r u c t i o nc u r v e m a n ye x a m p l e ss h o wt h a tt h i si s as i m p l ca n de f f c c t i v ew a yo fc u r v er e c o n s t r u c t i o n k e yw o r d s ：p o i n tc l o u d ，d a t ec o m p r e s s ，c u r v er e c o n s t r u c t i o n ，f i e l df u n c t i o n i i 目录 第一章引言 1 1逆向工程简介1 1 2曲线重建的现状3 1 3本文的主要工作6 第二章基本理论 2 1曲线重建的场函数算法7 2 2平面三角剖分1 1 2 3平面点云的数据压缩2 1 第三章平面点云曲线的构造 3 1图例比较2 4 3 2结论3 3 参考文献3 5 致谢3 8 i i i 第一章引言 1 1逆向工程简介 长期以来，在工业设计中，传统的产品开发过程足根据市场需求，提出目标和技术指 标，进行功能设计，由设计数据构造产品的几何模型，然后经过数控加工等一系列的活动 产生产品的过程，这种开发模式足一种预定模式，我们称之为正向工程正向工程居从有 到无 的过程，其流程如图1 - 1 所示： 图( 1 1 ) 正向工程开发流程 但足在大多数情况下，只有产品的实物模型，而没有产品的原始设计资料和图纸为 了与先进的制造技术的发展相适应，需要把这些样件或模型还原为c a d 模型我们把这 种根据实物模型或样件测量数据，建立数字模型并作改型的方法，统称为“逆向工程”， 或。反求工程”，这里所谓。逆向”事实上足相对于传统的c a d ( c o m p u t e ra i d e dd e - s i g n ) c a m ( c o m p u t e ra i d e dm a n u f a c t u r i n g ) 系统工作流程而言的，可以这么认为，传统的 计算机辅助设计足首先来源于一个设计思想，进而根据该思想建立儿何模型，并最终生产 出产品的过程与此相反的足，在逆向工程当中，首先拥有的是一个物理或实物模型，通过 对它进行数据采集，曲面重建，从而得到它的几何模型和设计思想的过程，逆向工程技术实 质上是一种重建技术其流程如图1 2 所示： l 图( 1 2 ) 逆向工程开发流程 逆向工程技术足一门新兴的产品设计科学技术它与迅速发展的计算机科学技术和测 量技术相结合，可快速实现产品的复制制造它改变了传统设计模式，即在c a d 系统中从 图纸到实物的设计模式，为快速开发产品和产品的快速原型化设计提供了一条新的方法 与此同时，如果把它与快速成型制造技术( r p m ，r a p i dp r o t o t y p em a n u f a c t u r e ) 相结合， 可对复杂物体进行快速的三维复制；而且如果再对其进行c a d 系统修改参数重新建立数 字模型，便可以对零件实现变异复原由于逆向工程技术能在短时间内对实物进行模型复 制，因而可以缩短产品的开发周期，提高企业产品的生产能力、产品的质量和企业的市场 竞争力，从而增加企业的经济效益所以在机械、航空、汽车、家电、玩具等领城有着广泛 的应用 一般来说，可以把逆向工程体系分为离散数据的采集获取，数据预处理建，曲面拟合， 建立c a d 模型等几个步骤 逆向工程的基础足物体的表面数字化( 即采样) ，是关键的第一步只有获得了离散的 采样数据，才能对其进行误差分析和曲面比较，进一步进行曲面曲线重建( c a d 建模) 现在基本上有两类数据的获取方式，可以分为接触式与非接触式接触式测量足指利用测 量仪器对实物外表面进行接触式测量接触式测量数据的特点足高精度低密度而根据作 用方式的不同，可以把非接触式测量法可分为光学法、工业c t 、超声波法和磁共振( m m ) 等我们就称对实体测量后获得的点数据就叫点云数据 在逆向工程中，核心问题足对采样数据点的曲线曲面重建或重构曲线与曲面重构所 研究的问题可描述如下： 对未知曲线或瞌面，通过采样得到一组采样数据点，曲线和曲面重构就足从这组采样 数据出发构造曲线或曲面，并且要使得到的曲线曲面以尽可能高的精度逼近原始曲线与曲 面 2 1 2曲线曲面重建的研究现状 由散乱数据点集重建曲线曲面在几何造型中也是一个重要问题而在某些情况下，曲 线重建在曲面重建问题中发挥着重要作用，例如在研究旋转面和可展面曲面重建的问题时， 通常可以通过线几何的方法计算主要的运动参数( 轴线、斜度等) ，然后由运动的轨道方向， 将已知的数据点集投影到一平面上，进而可以作出一条重建曲线，并把其作为重建曲面的 母线按已知采样点集的性质划分，曲线重建的方法可以分为两种，有序离散点集的曲线重 建、无序散乱点集的曲线重建 有序离散点的曲线重建：对任何已知曲线，按顺序采样一数据点集，而后根据采样的数 据点来构造出一条曲线，使构造出来的曲线尽可能地通过采样点，并把它作为原始曲线的 逼近曲线的二乘拟合可以看成足最早有序数据点的曲线重建，而在逆向工程中，对有序采 样数据点进行曲线拟合时，要求我们得到能够反映出原始点集的形状与特征的重建曲线 对有序数据点的曲线重构，很多学者已经做过研究1 9 8 1 年，m c a l l i s t e r 用二次样条曲线进 行插值，得到了一种重建的算法【6 】，f r i t s d l 和c l a r s o n ，b u t l a n d 等人分析了怎样用分段 三次曲线进行插值曲线重建1 7 - 8 ，更一般的足，p a s s o w 和r o u l i e r 讨论了怎么利用多项式 样条函数进行有序点曲线重建的问题【9 1 随着对有理曲线的进一步研究和对有理曲线性 质的掌握的熟练，越来越多的研究者提出了如何运用有理曲线对有序数据点进行曲线重建 i o - l u j 伴随着多分辨率思想的提山，对如何用多尺度样条拟合数据点这一课题，很多研究 者也做了一些研究例如2 0 0 0 年l a v e r y 在其文中f 1 3 】给一种新方法，即如何用三次光滑 l 1 样条多尺度地保形拟合数据点来重建曲线另外，其它研究者还提出了如何用圆弧样 条、双圆弧样条或其它参数样条对有序点进行曲线重建 1 4 - 1 5 而在逆向工程中，我们更常见的问题足关于无序散乱点集合的曲线重建在采样过程 中，由于方式不同，最终的到得足点云数据，这些点云数据没有固定的组织形式并且由于 这些数据点的采样密度很稠密，找到通过所有数据点的曲线足不可能也是不必要的，我们 只需根据该点集的分布情况，拟合出一条重建曲线，使其能反映出原始数据点集的形状与 3 走向近年来人们对无序点集的曲线重建给予了很多关注，并做了大量工作目前，现有 的工作可以分为以下几类 一、最b - 乘拟合法 对于由无序点集来重建出曲线，l e v i n 于1 9 9 8 年提出了一种曲线重建的方法【蚓，即 移动最z j 、- - 乘法( m o v i n gl e a s t s q u a r e s ) 这种方法由m c l a i n 在7 0 年代最早提出 1 7 - - 1 8 】 的此法一开始主要应用在散乱点数据插值与光滑等领域中1 9 9 8 年，l e v i n 在曲线重建的 领域引入了该方法，通过对点云进行细化，进而求出重建曲线2 0 0 0 年，l e e 把该方法1 1 9 进行了推广，通过对原始点集进行两次局部最小二乘回归的方式来调整数据点的位置，从 而可以细化点云，进而得出要重建的曲线，与此同时，该方法中引入了最小生成树，从而可 以解决当两族点集相距过近无法正确重建出曲线的问题 移动最j 、- - 乘法的基本思想足：对每一个点只，计算一个逼近r 周围一定范围内的 点的曲线g ( 回归线) ，然后把只移动到g 上的一个位置耳 移动最小二乘法的局部误 差足限制在局部最优逼近的范围内因而在该意义上，移动最i j 、- - 乘法足几乎最优的大 多数情况下，该思想的结果比较理想特别足对一个较细的点云，用移动最j 、- - 乘法能得 到很好的结果 设s = p l = ( z i ，y i ，) ：i = 1 ，2 ，n 足二维平面上的点集j 对其中任一点p ，其局 部回归线l ：y = a x + b 可以通过下面的函数得到： n d l = ( a x i + b 一玑) 2 u i i = l 这里的蚍是相对于只的非负权值，距离只越远的点权值越大记p 在直线l 上 的投影是q + ，并以此作为点p 的新位置，从而可以达到细化点云的目的在处理一般的 数据点时，移动最小平方法能得出很好的结果，但足由于点集宽度不够均匀，且回归曲线 会受到噪音的干扰，从而导致重建曲线效果不太理想而l e e 推广了此方法，他对初始点集 进行两次局部最小二乘回归，通过调整数据点的位置达到细化点集的目的，得出重建曲线 同时，引入了最小生成树，使两族点集相距过近无法正确重建出曲线的问题得到解决 虽然移动最小二乘方法引入，使重建曲线的质量提高，但是每个数据点都要根据其邻 域内数据点的分布，通过两次回归调整它的位置，所需的计算量较大 二，模型重建法 4 5 离散方法获得的重建曲线并不能很好的反映点集端点的形状，并且重建曲线的准确性 甚至正确性受到网格分辨率的影响 另外，对散乱数据点集的曲线重建，还有其它一些算法钟纲通过模拟带电粒子的场 函数分布方法达到曲线重建的目的另外他还提出曲线重建的跟踪算法成媛嫒等【2 8 】基 于自适应遗传算法，首先网格化点云分布空间，然后用自适应遗传算法每个网格中寻找特 征点，该特征点能反映出该网格中点集的分布特征然后对每个特征点利用改进的自适应 的s i g 图处理，得出待重建曲线的型值点，最后，确定型值点的拓扑结构，并用b 样条函数 得到重建曲线此外，刘丽提出的最短路逼近算法，把散乱数据点集的曲线重构问题通过 求解带权连通图的最短路径，转化为有序数据点的曲线重构问题 1 3本文的主要工作 在本文中，首先通过数据压缩选择初始曲线，而后再对初始曲线利用场函数算法，从而 得到重建曲线上述文献的算法在某些方面取得了很好的效果，但足存在的不足足只能解 决一些简单的单连通曲线重建问题，很难自动的识别出多连通和封闭的情况，或者足算法 的效率不足太高为此，本文根据以上的一些思想，首先对点集进行压缩，并建立无序点集 之间的关系，实现数据点的有序化，以方便地实现益线的重建对出现复曲线的情况能自 动地识别 本文的安排是第二章主要介绍曲线重建的一个基本算法，平面三角剖分理论，和一种 数据点压缩的算法；第三章足本文的算法和一些实例 6 第二章基本理论 2 1曲线重建的场函数算法 如第一章所述，曲线重建有很多已有的研究，本节介绍本文引用的一个算法，该算法 针对无序点集，模拟带电粒子在空间中形成场分布的现象，通过构造场函数来实现由线重 建 2 1 1 相关定义 s = k ：( 毛，玑) ) 盏1 为已知甲面上的一组无序离散采样数据点，称之为数据点集 设p 为点集s 中的任一点，p ( p ) = q i d ( p , q ) p ，q r 2 ) ，称p ( p ) 为点p 的 邻域 令( s ，p ) = u p s p ( p ) ，则称n ( s ，p ) 为点集s 的p 领域 对一组采样数据点s ，如果存在一个最小的正整数p ，使得对于s 中任意一点的少 邻域，都含有s 中的其它点，那么称s 的采样密度为p a ，b 为点集s 中的任意两点，如果存在s 中的一组点列 岛，r ，r ) ，满足 d ( 只，只+ 1 ) p ，( i = 0 ，n 1 ) ，并且p o = a ，r = b ，则称a ，b 两点p 道路连通 如果s 中任意两点都是p 道路连通的，则称点集s 为少连通 设p 为点集s 中的任意一点，称s 的包含p 点的p 连通子集为：q = q i p , q 两 点户道路连通，q s ) ，也称之为p 连通分支显然，当s 只有一个矿连通子集时，s 是 p 连通的 由以上可以得到如下性质1 ；若点集s 足p 连通的，则它的户邻域足一个连通区域 2 1 2 基本思想 7 设s = k ：( 瓤，犰) ) i n ：- 0 1 为一组数据点，采样密度为p 可以根据点集的连通性将s 分为若干个矿连通分支也可根据待重建的曲线最终足几条，人为地将点集s 分成若干个 子集有上述性质1 ，对于s 的每一个连通分支，它的p 邻域足一个连通区域，于是可以 在它的p 邻域中求出一条曲线使其为重建曲线 对于s 的某个伊连通子集，可以仍记为s ，为了达到由点集s 重建曲线的目的，如果 认为s 中的每一点k 都足带单位电荷的粒子 则带电粒子可以在平面上形成一电场，也就是说平面上的任意一点都有一电场强度， 并且距离k 越远，场强越小；距离k 越近，场强越大整个平面在所有带电粒子共同作用 下就形成了一个电场我们要得到的重建曲线就是在电场分布中场强最大的一条曲线 对于每一点k ，首先我们定义该点对应的场函数仇( z ) 称肌( z ) 为基函数，并且此函 数应该满足以下条件： ， i 吼( z ) = 1 ，d ( x ，k ) 篓p i i1 n g i ( x ) 1 ，p d ( x ，k ) p + ( 2 1 ) i 仇( z ) = 1 n ，d ( x ，k ) = p + l 10 1 ，v m ( s ) ) 芬r ( s ) = 。 吼cz，=一，三：三：荔；三三 这里d ( x ，k ) 为z 和两点之间的的欧式距离，n 为s 中点的个数足用于控制基 函数的形状的可调参数基函数的衰减速度随着e 的变大变慢，相应的场函数分布函数随 着e 的变大变得越甲缓，这时我们得到的重建曲线体现的足点集的整体特征相反地，基 函数的衰减速度随着e 变小变快，相应的场函数分布函数随着的变小变得越急促，而这 时候得到的重建曲线更多地反映出点集的局部细节所以，我们可以根据不同的要求来选 择合适参数在本文中我们选择= 1 就可以的到满意的结果 匿园团 c ，j ) 懈 图( 2 1 )对场分布函数及重建曲线的影响 ( a ) 数据点集 ( b ) ( c ) ( d ) 场分布函数，分别为1 , 5 ，1 0 ( e ) ( f ) ( g ) 重建曲线，e 别为1 , 5 ，1 0 本文的算法主要足根据上述基函数来重建曲线当然基函数的选取足多样的，满足 吼cz，=：乏。d扛，k，一力 三 三：姜；薹三 一 ；j。，：。 ，；： 0 i， 、，o ，儿 惭 m ；l ，歹， 吣 容易验证此基函数也满足式( 2 1 ) 2 1 4 曲线运动方程的构造 对于式( 2 2 ) ，一般很难求出其显式解，所以本文用数值求解法来求解曲线有上文所 述，下( s ) 为脊线的投影曲线，因此，为了求7 ( s ) ，可以首先选取一适当初始曲线7 ( s ，o ) ，然 后让其上的每一点沿场分布函数，的梯度方向运动，则我们在时刻t 得到的曲线足- y ( s ，) ， 由于在平面上考虑，则，y ( s ，t ) = ( z ( s ，t ) ，可( s ，t ) ) ，其中这里的s 为弧长参数，t 为时间参数， 并记场函数，的梯度方向为v f ( x ，y ) = ( ( z ，可) ，( z ，! ，) ) 考虑我们选定的初始曲线7 ( s ，0 ) ，我们想要的结果足? 随着时间的变化，它沿场函数梯 度方向运动的极限位置足场函数的某条脊线，即极限曲线1 ( s ，( 3 0 ) 足场函数的某条脊线，然 后我们就以此作为重建曲线由于平面上的任意一点的场函数值增加最快的方向足函数在 该点的梯度方向所以，为了使得场函数t 厂在极限曲线 ，( s ) 上各点的极大值，( 7 ( s ，o o ) ) 在 嗌线7 ( s ) 的法线方向上取得，我们就把曲线运动到下一时刻的运动的方向设定为厂( 7 ( s ，t ) ) 上各点的梯度方向，从而随着时间的变化，曲线 ，( s ，t ) 需要满足以下方程： 翌掣：一v ，t t t s , t ) ) t “z 3 )丁2 jt ) ) 6 ) 由上述方程，经过离散迭代可以求出要重建的曲线 如果初始曲线为7 0 ，假设经过k 次迭代后变为矿，我们将离散化，可以表示为，y 七： 砧，砖，砖。) 对其中任意一点砖，假如其下一时刻变为q ，则由( 2 3 ) 式，应满足 旦盛h = 专揣，即q = 砖+ h 专揣，i = 0 ，1 ，n 七其中这里的h 为迭代步长， v f ( p i ) 为场函数在此点的梯度方向因为我们足让曲线沿场函数的梯度方向变化的，所以 曲线上的场函数应该逐渐变大假如存在一个i 使f ( q i ) ，? 考、 、 、 图( 2 2 2d e l a u n a y 三角剖 v o r o n o i 图和d e l a u n a y 三角害 j 分有名 s t r a i g h t l i n e e m b e d d i n g ) 图，即i扫s 的 g 图足原来1 1 个点上的一个图这一直线 实线足d e l a u n a y 图，虚线足v o r o n o i 图d e l a u n a y 图事实上就足s 的一个三角剖分，也叫 d e l a u n a y 三角剖分 下面介绍d e l a u n a y 剖分的一些性质 ( 1 ) d e l a u n a y 三角剖分足唯一的 ( 2 ) 在点集s 的d e l a u n a y 三角网格中，任一三角形的外接圆范围内不会包含s 中的 其他基点这叫做d e l a u n a y 三角剖分的空圆( e m p t yc i r c l e ) 性质 ( 3 ) 在形成三角形网格时，总足选择最邻近的点形成三角形 ( 4 ) d e l a u n a y 三角剖分具有最优的形状特征即在s 的所有三角剖分中，d e l a u n a y 三 角剖分最大化最小角这即为d e l a u n a y 三角剖分的最大最小角性质( m a x m i na n g l ep r o p - e r t y ) 由以上的性质我们知道，对于给定的一组平面数据点集s ，可以多种不同的三角剖分， 而其中d e l a u n a y 三角剖分足最优的，二维d e l a u n a y 三角剖分由满足最小内角最大准则的 三角形组成下面我们看三角剖分的一些优化准则 在三角剖分过程中，往往用一种比较简单的方法构造散乱数据点的初始三角网格，然 后对其进行优化，以获得较优化的三角形网格优化的方法和效果取决于所采用的优化准 则平面三角剖分常采用的优化准则有t h i e s s e n 区域准则、最小内角最大准则、圆准则 而且这三个准则足等价的，并且满足这些准则的三角剖分只有一个，d e l a u n a y 三角剖分 t h i e s s e n 区域准则( t h i e s s e nr e g i o nc r i t e r i o n ) t h i e s s e n 区域指对平面进行v o r o n o i 分割后形成的多边形区域如果两个区域具有 非零长度的公共线段，则称这两个区域的生成点为t h i e s s e n 强邻接点( s t r o n gt h i e s s e n n e i g h b o u r s ) ；如果它们的公共部分仅屉一个点，则称为t h i e s s e n 弱邻接点( w e a kt h i e s s e n n e i g h b o u r s ) 一个严格凸的四边形至多有一对相对顶点足t h i e s s e n 强邻接点t h i e s s e n 区 域准则指对一个严格凸的四边形三角化时，将t h i e s s e n 强邻接点相连，若两对顶点都足 t h i e s s e n 弱邻接点，则任选一对相连，这样构造的三角化足最优的，如下图所示： 1 6 最大 在平 证对角线 圆准 对平 则将第四 图( 2 1 0 ) 圆准则 平面三角剖分为平面点云的三角剖分提供了判别标准，也为三维散乱点集的三角剖分 提供了借鉴依据 下面看构造d e l a u n a y 三角剖分的算法 在构造d e l a u n a y 三角剖分时比较常用的算法足逐点插入算法对于甲面无序点集 s = p o ，p 1 ，一，p 。) ，首先选择一个足够的三角形p i p 一2 p 一3 ，将整个点集s 都包围起来 ( 如图2 1 1 所示) 也就是说，如果令q = p 一1 ，p 2p 一3 ) ，那么我们计算的就是s u q 的 d e l a u n a y 三角剖分一旦生成了这一三角剖分，只需将p 一1 p 一2 p 一3 以及与它们关联的各边 都删去，就可以得到s 的d e l a u n a y 三角剖分为此我们所选择的p 一1 ，p 一2 ，p 一3 必须相距足 够远，才不至于对s 的d e l a u n a y 三角剖分中的任何三角形有所影响尤其必须保证的一 点是，p l ，p 一2 ，p 一3 一定不能落在s 总的任何三点的外接圆内 图( 2 1 1 ) 足够大的包围三角形 例如下图所示：p 一1 = ( 3 m ，o ) ，p 一2 = ( 0 ，3 m ) ，p 一3 = ( 一3 m ，一3 m ) 其中这里的m 为s 中 1 8 一 房少一 p ，翻p 。m 形并不满足d e l a u n a y 三角剖分的性质为了消除这些不合法性，需要对每一条可能的非法 边做一个处理这个处理过程实际上就足利用d e l a u n a y 三角剖分的圆性质通过对边进行 翻转操作，将所有的非法边转换为合法边而哪些边有可能在插入点肼后变成非法的呢? 如下图( 2 1 4 ) 所示，原来任何一条合法边p i p j ，只有在与其相关联的三角形( 最多两个) 之一发生变化时，才有可能成为非法边因此，只需检查新生成的那些三角形的各边若有 必要则进行边翻转如图( 2 1 4 ) ，p k 落在三角形p ，p j p i 外接圆的内部，因此p 伊f 为非法边， 从而连接p ，p k ，则p ，p k 为合法边每翻转一条边后，可能又会进而使得其他的某些边变成 非法边，只需再重复以上翻转步骤即可 图( 2 1 4 ) 只有与之相关联的三角形发生变化时， 原先的合法边才可能转为非法边 事实上，上述翻转步骤可通过下面的子函数l e g a l i z e e d g e ( p ，鼽功，) 来实现这 里的为一三角剖分 l e g a l i z e e d g e ( p ，p i p j ，e ) 1 为插入的点，p i p j 为中可能需要翻转的边) 2 i f ( p i p j 为非法边) 3 t h e n 令p i p i p k 为沿着边p i p j 与三角形p r p i p j 相邻的三角形 4 将原来的边p i p j 换成p k p ，( e p 翻转p i p 了) 5 l e g a l i z e e d g e ( p ，a m ，) ( 调用自己) 6 l e g a l i z e e d g e ( p r ，仇乃，) 2 0 由以上表述我们可以对三角剖分的主算法进行描述，如下 a l g o r i t h md e l a u n a y t r i a n g u l a t i o n ( s ) i n p u t 平面上n 个点组成的集合s o u t p u t s 的一个d e l a u n a y 三角剖分 1 适当地选取三个点p - 1 ，p 一2 ，p - 3 ，将s 完全包含在三角形p - l p 一2 p 一3 中 2 将初始化为一个三角形p l p 一2 p 一3 3 随即地选取s 中各点的顺序：p 1 ，仇，骱 4 循环f o r ( r = lt on ) 5 d o ( 将肼插入到中) 6 找到肼所在的三角形p i p j p k e 7 i f ( p ，落在p i p j p k 的内部) 8 t h e n 分别将办与三角形p i p j p k 的三个顶点连接起来( 从而生成三条边将三角形 p i p j p k 一分为三) 9 调用子函数l e g a l i z e e d g e ( p r ，p i p j ，) 把非法边合法化 1 0 l e g a l i z e e d g e ( p ，p j p k ，) 11 l e g a l i z e e d g e ( p ，p 七鼽，e ) 1 2 e l s e ( p ，正好落在三角形p i p j p k 的某一条边( 不妨设为p l p j ) 上) 1 3 将肼分别与p k 以及与p i p j 关联的另一三角形的第三个顶点p l 连接起来从而将与 p i p j 相关联的那两个三角形划分成四个三角形 1 4 l e g a l i z e e d g e ( p r ，鼽铆，) 1 5 l e g a l i z e e d g e ( p ，p l p j ，e ) 1 6 l e g a l i z e e d g e ( p r ，p j p k ，e ) 1 7 l e g a l i z e e d g e ( p ，p k p i ，) 1 8 将点p 一1 ，p 一2 ，p 一3 以及与之关联的所有边都从中删除掉 1 9 r e t u r n 另外还有w a t s o n 的算法，其基本思想足：在已有网格中，每插入一个新点p ，在网格 中寻找包含p 的三角形t 然后从t 开始搜寻外接圆包含p 的三角形，删除这些三角形， 2 1 只保留这些三角形的外边界从而形成一个多边形，该多边形包含了新插入的点p ，然后连 接p 和多边形的顶点，形成一些新的三角形这些三角形就满足d e l a u n a y 性质然后依次 迭代知道处理完所有的节点为止如图( 2 1 5 ) 圆锣 ( a ) 初始化的三角形( b ) 点的插入 q ) 锣 ( c ) 元素的删除( d ) 最终的三角形网格 图( 2 1 5 ) w a t s o n 算法图形演示 2 3平面点云的数据压缩 在对物体表面进行测量后，得到了大规模的散乱点数据，即点云数据由于数据比较 庞大，直接对这些点云进行曲线曲面重建需要耗费很大的计算量为此，对这些大规模散乱 点进行适当的数据压缩足很必要的，这样可以大量减少要重构的数据点，但足在压缩后必 须要保证新得到的数据点和原始数据点保持相似的结构下面我们给出一种数据均匀压缩 的算法，并根据压缩点的特征来重建曲线网格 2 3 1 相关定义 给定平面数据点集：p ： 让l ，缸。) ，我们称这些点为旧点 假设压缩后的点集为：q ： v l ，口m ) ，qep ，称这些压缩后的点为新点 相关点：只= ，讥) ，i = 1 ，礼相关点表示距离旧点u 最近的两个新点 2 2 相关距离：d i = 以j ，也，七) ，i = l ，礼表示旧点u i 与其相关点之间的距离并且记 w i = m i n d i 为牡t 的极小相关距离，w i = m a x d i 为札l 的极大相关距离而且统称u i 的相关点，相关距离，极小相关距离，极大相关距离为u t 的相关记录 2 3 2算法过程 ( 1 ) 首先在旧点中任意选一个点作为第一个新点v i ，这样就可以确定每个旧点的相关 点只= 秒1 ) i = 1 ：n 相关距离d i = d i 1 ) i = 1 n 极大相关距离彬= m a x d i = d i ，1 ) ，极小相关距离w i = m i n d , = d i ，1 ) ( 2 ) 如果屿= y f z a xw i ，1 i 他，则v 2 = u j 然后重新确定每一个旧点的相关点 只= u 1 ，忱 ，相关距离d i = d i ，1 ，d i ，2 ) ，极小相关距离w i = m i n ( d i 1 d t ，2 ) ，极大相关距离 眦= m a x d i ，1 ，d i ，2 ) ( m ) 如果w k = m a xw i ，1 i n ，就令v m = u k 然后重新确定每个旧点的相关记录 由以上m 步过程我们就得到了m 个新点u 1 ，现，因为每个旧点的极小相关距 离可以看成足其附近新点分布疏密程度的一种度量也就是说极小相关距离值越大，就说 明旧点附近新点的分布就越稀疏，反之就越密所以我们每次选取极小相关距离的最大者 作为新点，这样可使得最后得到的所有的新点在旧点的分布域中均匀分布然后可以根据 这些新点来重建曲线 2 3 第三章平面点云曲线的构造 3 1图f f , j l l 较 通过前面的介绍我们知道，对甲面上的散乱点集的曲线重建，初始曲线的选取很重要， 这直接影响到重建的效率和重建的质量由于点云数据量大，如果直接对其进行重建，将 会有很大的计算量所以为了减少计算量，同时又能保持原始点集的形状，本文对点云进 行数据压缩，建立初始曲线，然后对压缩后的点进行曲线重建对于文献，通过把平面 网格化，得到网格点，并定义了网格点的度的概念然后对细化后的网格点采用跟踪算法， 从而得到初始曲线，并由此通过场函数算法得到重建曲线下面通过图例来对两种方法进 行比较，称本文的方法为方法一，文献1 3 1 】的方法为方法二设定1 3 为原始点的个数，n p 为重建后的点的个数，t i m e 为算法运算时间 例1 ：单连通曲线 方法一： 图( 3 1 ) 初始曲线图( 3 2 ) 初始点集 2 4 n = 4 9 3 ，n p = 2 2 方法2 ： 图( 3 8 ) 重建后的曲线 图( 3 9 ) 重建后的点集 图( 3 1 0 ) 重建后的曲线与原始点云 n = 4 9 3 ，n p = 2 3 3 ，t i m e = o 2 1 9 0 0 0 例2 ：简单曲线 方法一： 、 、 j 图( 3 1 1 ) 初始曲线 1 图( 3 1 2 ) 初始点集 j 、 。 一一 图( 3 1 3 ) 重建后的曲线图( 3 1 4 ) 重建后的点集 2 6 n = 1 图( 3 2 0 ) 重建后的曲线与原始点云 n = lll ，n p = 5 4 ，t i m e = o 0 1 5 0 0 0 例3 ：复曲线 方法一。 瓜 瓜 图( 3 2 2 ) 初始点集 j j 瓜 图( 3 2 5 ) 重建后的曲线与原始点云 n = 8 9 2 ，n p = 3 2 9 ，t i m e = o 2 8 1 0 0 0 方法二： 图( 3 2 7 ) 初始点集 图( 3 2 8 ) 重建后的曲线图( 3 2 9 ) 重建后的点 图( 3 3 0 ) 重建后的曲线与原始点云 n = 8 9 2 ，n p = 3 3 9 ，t i m e = o 4 3 7 0 0 0 例4 ：自交曲线 方法一： 图( 3 3 1 ) 初始曲线图( 3 3 2 ) 初始点集 2 9 、， j； ( 、，一、 x 、 t 一 、，。、 图( 3 3 3 ) 重建后的曲线 图( 3 3 4 ) 重建后的点集 图( 3 3 5 ) 重建后的曲线与原始点云 n = 2 9 6 0 ，n p = 1 7 7 ，t i m e = o 5 9 4 0 0 0 方法二： 图( 3 3 7 ) 初始点集 一 f ? ， i “一，一一“ ，! ，+ ： ”、一 图( 3 3 8 ) 重建后的曲线 图( 3 3 9 ) 重建后的点集 图( 3 4 0 ) 重建后的曲线与原始点云 n = 2 9 6 0 ，n p = 2 4 3 ，t i m e = 1 2 1 9 0 0 0 例5 ：复杂曲线 方法一： 图( 3 4 1 ) 初始曲线 图( 3 4 2 ) 初始点集 ，一一一一 图( 3 4 3 ) 重建后的曲线 图( 3 4 4 ) 重建后的点集 3 1 n = 1 图( 3 5 0 ) 重建后的曲线与原始点云 n = 1 2 1 7 ，n p = 3 6 2 ，t i m e - 0 7 1 9 0 0 0 3 2结论 由上面的例子我们可以看出，本文的算法和文献【3 1 1 的算法不但能处理单连通曲线的重建， 而且对于复曲线的重建甚至复杂曲线的重建也能得到很好的结果这相比文献【5 】来说已 有很大的改善而从图例中我们可以看出，本文相比文献来说，在重建曲线的光滑程度 和算法的效率上都有所改观( 时间节约了近一半) 后记：本文主要利用甲面点云数据的压缩算法来得到初始曲线，并结合场函数对初始 曲线进行重建大量实验表明，对于具有任何复杂拓扑结构的平面点云，利用这种方法的 到的重建曲线无论在质量上还足在效率上都有所进步但是从图例我们也可以看出，对于 出现自交情况的曲线重建，在自交点处和曲率比较大的地方，结果还不足很理想，这还有待 进一步的改善还可以考虑d e l a u n a y 三角剖分理论来建立点集之问的拓扑关系，从而得到 初始曲线，并利用场函数算法对初始曲线进行重建这种算法相比较本文的算法的来说，是 否会有所进步，还有待进一步研究 参考文献 【1 】v a x a d yt ，m a r t i nrr ，c o xj r e v e r s ee n g i n e e r i n go fg e o m e t r i cm o d e l s a ni n s t r u c t i o n j c o m p u t e ra i d e dd e s i g n ，1 9 9 7 ，2 9 ( 4 ) ：2 5 5 - 2 6 8 【2 】田晓东，史桂蓉，阮雪榆复杂曲面实物的逆向工程及其关键技术僻机械与制造工程， 2 0 0 5 ，9 ( 4 ) ：1 - 6 【3 】b e n k op ，v a r a d yt c o n s t r a i n e df i t t i n g 伽r e v e r s ee n y i n e e r i n , y j j c o m p u t e ra i d e dg e o m e t r i c d e s i g n 2 0 0 2 ，1 9 ( 3 ) ：1 7 3 - 2 0 5 嗡m c c o r m i cb ，d e f a n t it ，b r o w mm v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n gf j ) c o m p u t e rg r a p h - i c s ，1 9 8 7 ，2 1 ( 6 ) ：1 6 3 - 1 6 9 【5 】5 钟纲，杨勋年，汪国昭基于场表示的平面无序点集曲线重建算法计算机辅助设计与图 形学学报v 0 1 1 4 ，n o 1 1 ，n o v 1 1 ，2 0 0 2 【6 】d f m c a l l i s t e ra n dj a r o u l i e r a na l g o r i t h mf o rc o m p u t i n gas h a p ep r e s e r v i n go s c i l l a t o r y q u a d r a t i cs p l i n e a c mt r a n s a c t i o x mo nm a t h e m a t i c a ls o f t w a r e ，1 9 9 1 ：7 ：3 3 1 3 4 7 【7 】f n f r i t s c ha n d r e c a r l s o n m o n o t o n ep i e c e u r i s ec u b i ci n t e r p o l a t i o n 。s i a mj o u r n a lo fn u - m e r i c a la n a l y s i s ，1 9 8 0 ，1 7 ，2 3 8 - 2 3