（计算机软件与理论专业论文）基于空间散乱点的复杂曲面建模与可视化研究.pdf

摘要 曲面蕈建技术红曲面测量造型与，叮视化等领域有着广泛的应用背景。基于散乱点集 曲商重建作为最具普遍性的曲面重建问题，无论在理论上还是在应用上都具有非常重 要的意义。 本文首先对散乱点曲面玺建的应用价值及解决曲面重建问题的儿种相关技术，即二 角剖分与曲面分割、科学计算可视化等重建技术等作了简要介绍。并提出r 本文付诸研 究并取得进展的若于问题。 然后介绍r 曲面j 角剖分、d e l a u n a y 三蔓角剖分及约束三角剖分等曲面剖分技术，并 分析了曲面重建的现状，对曲面重建技术做了简单分类，然后对一冀国内外散乱点曲面 重建的经典算法做了介绍，并进行了分析、归纳与对比。 再次讨论了散乱点曲面重建的关键，并在此基础上提出了基于聚类分析的散乱点曲 面重建方法。对所用到的主成分分析技术、聚类分析技术、凸壳技术等做了详细的介绍 并在此基础上详细阐述了自己的算法，提出了一种新的边界缝合技术，较好的解决了敝 乱点曲面重建问题。， 然后又介绍了o p e n g l 的功能、特点及鼠标跟踪球算法，并介绍r 怎样利用o p e n g l 编程实现三维模型可视化，并实现三维模型的显示变换。最后给出了利用o p e n g l 实现的 模型绘制效果图。 最后对本文的研究工作进行r 总结，并对曲面重建领域的发展前景及下一步努力的 方向进行了展望。 关键词：曲面重建，散乱点，主成分分析，聚类分析，边界拼接。 东 s - p z 大学硕士论文 a b s t r a c t 摘要 t h et e c h n i q u eo fs u r f a c er e c o n s t n l c t i o nh a se x t e n s i v eu s ei ns u r f a c em e a s u r i n g m o d i f i c a t i o n ，v i s u a l i z a t i o n ，a n ds u c ho nf i e l d s t h et e c h n i q u eo fs u r f a c er e c o n s t r u c t i o nf r o m s c a t t e r e dp o i n t s ，f o ri t su n i v e r s a l i t y ，i sv e r yi m p o r t a n tb o t ht h e o r e t i c a l l ya n dp r a c t i c a l l y f i r s t l y ，ab r i e fi n t r o d u c t i o ni sm a d ea b o u tp r a c t i c a lv a l u eo fs u r f a c er e c o n s t r u c t i o no f s c a t t e r e dp o i n t s a n dt h e nt h r e ek i n d so ft e c h n i q u e si n c l u d i n gs u r f a c et r i a n g u l a t i o n ，s u r f a c e s u b d i v i s i o na n ds c i e n t i f i cv i s u a l i z a t i o na r er e v i e w e d f i n a l l y ，s e v e r a lp r o b l e m sa r ep u tf o r w a r d a b o u ts u r f a c er e c o n s t r u c t i o n ，w h i c hh a v eb e e ns t u d i e dc a r e f u l l yi nt h i sd i s s e r t a t i o n s e c o n d l y , s u r f a c et r i a n g u l a t i o nt e c h n i q u e ，w h i c hr e f e r s t ot r i a n g u l a t i o no f2 dp o i n t s ， d e l a u n a yt r i a n g u l a t i o na n dc o n s t r a i n e dd e l a n n a yt r i a n g u l a t i o n ，i si n t r o d u c e da tf i r s t ，a n dt h e n p r e s e n tw o r ka b o u ts u r f a c er e c o n s t r u c t i o ni sa n a l y z e d ，a n dm a i nc l a s s i f i c a t i o n sa r em a d ew i t h s u r f a c er e c o n s t r u c t i o nm e t h o d a f t e rt h a ：【s e v e r a lk i n d so fc l a s s i c a ls u r f a c er e c o n s t r u c t i o n m e t h o d sa r ed e s c r i b e d ，a n da n a l y s i s ，g e n e r a l i z a t i o na n dc o m p a r i s o na r em a d ea b o u tt h e m t h i r d l y , t h ek e yf a c t o r o fs u r f a c er e c o n s t r u c t i o ni sd i s c u s s e d ，t h e nt h es u r f a c e r e c o n s t r u c t i o nm e t h o do fs c a t t e r e dp o i n t sb a s e do nc l u s t e r i n gt e c h n i q u ei sp u tf o r w a r d a n d a l s or e l a t i v et e c h n i q u e si n v o l v e d ，s u c ha sp r i m a r yc o m p o n e n ta n a l y s i st e c h n i q u ea n dc o n v e x t e c h n i q u e ，a r ei n t r o d u c e d a n db a s e do nt h i s ，o u rm e t h o do fs u r f a c er e c o n s t r u c t i o ni s d e s c r i b e di nd e t a i l s t i l lam e t h o do fb o r d e rc o n n e c t i o ni sb r o u g h tf o r w a r d u s i n go u rm e t h o d s u r f a c er e c o n s t r u c t i o nc a nb ew e l lf i n i s h e d f o u r t h l y , f u n c t i o na n dc h a r a c t e ro fo p e n g la r ei n t r o d u c e d ，a n da l s om o u s et r a c k b a l l a l g o r i t h m t h e nw ee x p l a i n e dh o wt oi m p l e m e n tt h e3 dm o d e lv i s u a l i z a t i o nw i t ho p e n g l p r o g r a m m i n g ，a n da l s ot r a n s f o r m a f i o na n dd i s p l a yi sm a d e f i n a l l nr e s u l t e dg r a p h i c su s i n g o p e n g la l es h o w n f i n a l l y , w ed r a ws o m ec o n c l u s i o n so ft h i sd i s s e r t a t i o na n ds u g g e s t 山ef u t u r ew o r kt od o i nr e l a t e dr e s e a r c hf i e l d s k e y w o r d s ：s u r f a c er e c o n s t r u c t i o n ，p c a ，c l u s t e r i n ga n a l y s i s ，s c a t t e r e dp o i n t s ，b o r d e r c o n n e c t i o n 声明 本人呈交给山东科技大学的这篇硕上学位论文，除所列参考文献和世所公 认的文献外，伞部足本人在导师指导下的研究成果。本论文资料尚未肇交于 t 何其他的学术机构作鉴定。 a f f i 砌讧a r n o n 硕士生签名f 一足药 日 期：了j 口 1d e c l a r et h a tt h i sd i s s e r t a t i o ns u b m i t m di nf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ea w a r do fm a s t e ro fp h i l o s o p h yi n s h a n d o n gu n i v e r s i t y o fs c i e n c ea n d t e c h n o l o g y , i sw h o l l ym yo w nw o r ku n l e s s r e f e r e n c e do fa c k n o w l e d g e t h e d o c u m e n th a sn o tb e e ns u b m i t t e df o rq u a l i f i c a t i o na ta n yo t h e ra c a d e m i ci n s t i t u t e s i g n a t u r e ： 憎峙 晰：沙f 、 j 。 山泉事_ 技大学硕二i 学位论文 鳍伦 1 绪论 1 1 问题提出 随着计算机图形显示对于真实性、实时性和交互j 性要求的召益增强，凡何没计对象 体现出向着多样性、特殊性和拓扑结构复杂性靠拢的明显趋势，与此同时图形工业和制 巷啦向着一体化、集成化和网络化快速迈进，激光测距扫描等三维数据采样技术和硬件 设备| 1 臻完善，使得曲面建模技术近几年得到了长足的发展。但是基于散乱点集的二- 维 曲面重建技术，由于其拓手i 、结构的未知性和复杂性，至今仍远未成熟，不能满足多方丽 应用的需要。 所谓散乱点集指的是在2 d 平面域或3 d 空阊域中抽取的随机分布的抽样数据点集 ( 本文讨论的是三维空间点集) ，出于测量的难度和测量的代价，这些点只有独立的坐 标信息，没有连接信息和任何其它信息( 如法向。曲率等) 。在科学计算可视化、雕塑 啦面造型和反求工程等许多应用领域，经常需耍把一个从实体表面提取的散乱点点集， 重新恢复成原来的曲而，保持正确的拓扑和尽可能精确钧曲面，这就是基于散乱点的曲 面重建问题。通过这种方式，可以把现实世界中已有的物体，转变成计算机中的模型， 从而进一步对这些对象进行编辑等操作。 1 2 应用价值 基于散乱点的曲面重建问题，是目前计算机图形学领域所研究的热门问题，元沦在 理论上还是在实践中都极其普遍性，在理论上来说，这是一个极其一般性的问题，而在 实践中，其研究可用于许多领域，如g i s 中的数字高程横型，地质采矿中的岩体表而的 章丰暂，还有虚拟现实和医学图像以及机械制造等许多领域。 1 , 2 1g i s 中的建模问恿 数字地面模型 d i g i t a lt e r r a i nm o d e l ，简称d t m ) 是描述地面特性诸如空问 分； j 的有序数值阵列1 , 2 1 。在一般情况下，地面特性是高程z ，它的宅问分布由x 、y 水平半标系统来描述，也可用经度x 、纬度y 来描述。这种地面特性为高程或海拔高 程的d t m 也称为数字离程模型 d i g i t a le l e v a t i o nm o d e l ，简称d e m ) ，其它地 程的d t m 也称为数字高程模型 d i g i t a le l e v a t i o nm o d e l ，简称d e m ) ，其它地 1 ! - ! 壅登堇查笺堡主兰垡堡茎堕堡 面特性i r 以是诸如地价、土地权属、土壤类型、地貌特征、岩层深度及土地利用等与地 形有关的信息。d e m 可以是每3 个坐标值为一组元的散点结构，也可以是由多项式或 富里叶级数确定的曲面方程。由于地表模型的复杂性及应用的j 。泛性，使得采集一系列 离散点重建地表i 维模型变得非常困难和具有挑战性，并且成为目前3 d g i s 等领域研 究的热点l 、口】题。 随着地质和矿业的产业化，当今地质、矿业界人士希望能够更直观、更精确的圈定 矿体边界，了解地下地质体( 包括地层、断层、褶皱构造等) 的三维形态，准确地解译和圈 定地下地质体，以便指导矿业开发和深部找矿预测。这就必须利用三维可视化建模技术。 地f 三维可视化技术是真三维地理信息系统睁卅的一个分支，它在可视化技术的支持下 揭示地下地质体的特性，它充分利用了真三维地理信息系统( 3 d g i s ) 技术，以n t 视化技 术为基础，以地学问题为核心，将地质上的逻辑思维和空间上的形象思维有机地结合起 来，通过信息的动态反馈来获取矿体空间形态变化和晶位变化等地质规律。但同时又由 于地下工程的不可见性和高度复杂性f 5 j ，就使得采集离散点建立三维地质模型具有r 极 大的挑战性。 1 2 2 逆向工程中的表面建模阀麓 逆向工业( r e v e r s ee n g i n e e r i n g ) 的出现出于以下两种需要：( 1 ) 某些产品采用手工设 计即可满足实际需要，或在计算机出现以前相关的1 i ：艺和技术就已成熟。出于降低人力 成本和缩短产品周期考虑，需要引入c a d c a m 技术。但产品设计并不是全部用c a d 软件来完成，而是在现有的产品模型基础上做一些局部改进。这样从原始曲面七采集离 散点，经三维重构模拟原始曲面，从丽对产品的外型修改分析和设计起到极为重要的作 用。( 2 ) 某些复杂产品，先用手工方式设计出一个模型后，根据实际使用时的舒适度对模 型进行修改。如此反复，直到得到满意的模型，然后将模型数字化，再用c a d 软件进 行后续设计和分析，整个过程比完全采用c a d 软件设计更为有效。由于采样条件的限 制，这些问题的解决通常也一般只能采集到一定数量的离散点，利用这些点来对原始曲 面进行模拟重构以满足应用的需要。在逆向工程中，对于大量离散数据的曲面重构，是 一关键环节，它需要先对表面测量数据进行处理，然后进行拓扑重建，几何熏建，曲面 的修改、削嗄和优化设计。并且目前专业反求软件，功能糟当有限，而且不宜处理大量 点云数据。 2 山东科技大学硕士学位沦文 1 2 3 虚拟现实6 所谓“虚拟现实”，是用计算机技术来生成一个逼真的。i 维视觉、听觉、触觉或f 嗅觉 等感觉世界，让用户司以从自己的视点出发，利用自然的技能和某蝗设备对这一隹成j 内 虚拟世界客体进行浏览和交互考察陋】。这一定义强调的是：逼真的感觉、自然的交巨、 个人的视点及迅速的响应。虚拟现实是一项综合的技术，与计算机图形学联系特别紧密， 大规模数据的场景建模技术是其关键技术之一。影视特技中需要生成逼真的三缝效粜 而且随着硬件和互联网技术的不断发展，游戏和虚拟现实在向交互式三维场景发展对 于人体和复杂物体，现有的三维c a d 软件缺乏有效的自由曲面设计手段，获得更为逼 真的三维效果和 维场景的一种可行的方法是对真实物体数字化，进行曲面重建处理 后，通过纹理绘铷生成所需要的三维效果，所有这些都对三维模型重建提出了更高的要 求。 1 , 2 4 医学图像中的表面毫模问题 f i i 面重建的另一个应用就是医学图像。在医学研究中，经常会有一些器官的生理切 片，这是用医学的薄片切片机得到的。把一系列这样的切片组合起来，也就是把二维的 薄片平行的组合起来，形成一个栈，就是一个完整器官的散乱点数据集合。在加工制造 业中，也可以生成这样的栈，这是通过c a t ( x 射线轴向分层造影扫描机) 扫描机械零件 的相交部分得到的。类似的情况是，利用超声传感器搽测心脏的形状，就是通过将一个 探头仲入食道中，从而得到心脏的边缘数据。与薄片切片机不同，这样的超声得到的边 缘数据不是平行的，而且探头可以生成不同角度不同位置的边缘数据，这样生成的数据 要看它的密度情况来具体处理。对于这些边缘数据，采用散乱点重建曲面的方式生成曲 面表示，可以更有效的进行观察、分析等。 l 2 5 曲面草图 己经有研究考察在平面t 生成一条曲线草隧，也就是由用户通过触感笔或鼠标画f l 轨迹，跟踪这些轨迹直到生成一条瞳线。那么，通过这种方式生成任意曲面的草图，电 足可行的。可以让用户手持触感笔或鼠标，在某个表面上来回移动，这样跟踪它的轨迹， 就是相当于获取散乱点的信息，然后重建曲面，使生成的曲面忠实的反映所获取的散乱 3 山东科技大学硕士学位论文绪论 点。这种方式可以应用在三维物体造型设计，电影特技等领域中。 1 3 三维空间曲面建模问题的特点分析 在任意拓扑结构的封闭或不封闭曲面上采样得到散乱点点集，从这样的散乱点生成 原始曲面是一项难度很大的工作，主要原因如下： 1 ) 采样点只有三维坐标信息，而没有法向量等其他几何信息； 2 ) 采样点集是无序的，彼此没有任何相关信息； 3 ) 采样点的密度是未知的，不知道是均匀采样还是非均匀采样； 4 ) 曲面的耗扑结构完全未知，有可能存在很复杂的拓扑； 5 ) 曲面的表面情况可能较复杂，有可能存在尖角、折痕、裂缝等情况， 6 ) 数据量可能会比较大，需要考虑算法的效率； 所有这些特点，都对系统和算法的健壮性提出了较高的要求，给模型的构建带来了， 极大的挑战性。 1 4 1 三角帮分技术 1 4 曲面重建及可视化的荚麓技术介绍 三角剖分技术是计算几何【7 1 里的经典课题之一，散乱数据的三角剖分是构造散乱数 据插值曲面时必不可少的前置处理。三角铡分可分为对三维散乱数据投影域的剖分和在 空问直接剖分1 8 1 两种类型。直接三角剖分法研究如何直接将三维散乱数据点在空间中连 接成一个最优的三角网格。d e t a u n a y 三角化，对于给定的一组散乱数据点，可获得无限 种不同的三角剖分，其中d e l a u n a y 三角剖分为最优，二维的d e l a u n a y 三角剖分由满足 最小内角最大准则的三角形组成，三维的d e l a u n a y 三角剖分由满足球面准则的四匠体 组成。3 dd e l a u n a y 三角剖分是一种较合理的三角剖分，它是2 dd e l a u n a y 三角剖分由 平面点集向空间点集的推广，1 9 3 , 4 年俄国数学家d e l a u n a y 证明了2 dd e l a u n a y 三角刮 分方祛的特点。对3 d 情况而言，其特点是剖分结果符合空球判据，即每个划分成的四 面体的外接球内不含有点集中的任一点，使得各四面体尽可能接近于正三棱锥，避免_ r 狭长四面体的存在。如果所给点集中没有5 点共球，则这种剖分是唯一的挣1 ，剖分中常 用的性质有最小内角最大和最大空圆原则。最小内角最大原则：对于一个凸四边形的蹦 4 山东科技大学硕士学位沦文 绪绝 种削分，d t 获得的两个三角形中的最小内角最大。最大空圆原则：剖分中任一三角形 的外接圆( = 三维为外接球面，高维为超球面) 内不含有点集中的任何其他点。 f 前二维的气角剖分技术已经比较成熟，而i 维的窀间直接剖分由于其极高的算法 复杂度，在应用方面远小如平面三角占u 分成熟，并且针对本文算法，本文采用了平面三 角剐分作为曲砥重建的基础。 1 4 2 数据分块技术 数据分块( s e g m e n t a t i o n ) 是将点云数据分割成属于不同曲面片的数据子集。在反求 程中，产品表面往往无法由一张曲面进行完整描述，而是由多张曲面片组合而成，斟而 必须将测量数据进行分块，然后对各数据块分别构造曲面模型。数据分块技术大体町以 分为基于边( c d g e _ b a s e d ) 和基于面( f a c e b a s e d ) l 悯种方法1 6 j0 1 。基于边的数据分块方法首 先在测量数据内部确定边界点，如法矢突变、曲率突变或更高阶微分特性发生突变的数 据点，然后将边界点连接为边界曲线，最后利用边界曲线将整个测量数据分割为不同的 区域。由于噪声数据对估算数据点的微分特性影响很大，基于边的方法对于噪声数据比 较敏感，自动跟踪边界点容易出错，在实际工程应用中还必须辅之人工交互的操作才能 比较准确的完成数据分块。 基于面的数据分块方法则采用区域生长的方法，用不同类型的曲面拟合区域数据， 并依据拟合误差大小确定曲面类型，直到拟合误差超出给定的阈值，然后继续选择种子 点进行区域生长和曲面拟合。基于面的方法在区域生长的同时，动态调整拟合曲面的类 型，因而算法效率较低，而且无法处理自由曲面区域的分割。针对噪声数据影响数据分 块准确性的缺点，不少学者还提出了利用神经网络的方法，对测量数据进行自学习，根 据不同的噪声数据自动调整各种阈值参与数据分块，提高数据分块的准确性。另外，由 于基于边的方法没有提供曲面信息，而基于面的方法缺少边界信息，对此又出现了混合 应片j 基于边和基于面的数据分块技术。 本文采用了基于面的数据分块方法，不同的是，分块拟合的曲面并不做动态调整， 拟合面采用的是简单的一次平面，从而提高了拟合算法的效率。 1 4 3o p e n g l 及科学计算可视化技术 科学计算可视化的基本含义是运甩汁算机图形学或者一般图形学的原理和方法，将 5 竖壁壁奎兰堡主兰堕堡塞堕堡 科学与工程计算等产生的大规模数据转换为图形、图像，以直观的形式表示出来”。它 涉及i l 算机图形学、图像处理、计算机视觉、计算机辅助设计及图形用户界面等多个研 究领域，已成为当前计算机图形学研究的重要方向。科学计算可视化的应用领域十分广 泛，几乎涉及自然科学及工程技术的各个方面。主要应用在医学、地质勘探、气象学、 分子模型构造、计算流体力学、有限元分析、空间探测、天体物理、数学等领域。 随着地质和矿业的产业化，当今地质、矿业界人士希望能够更直观、更精确圈定矿 体边界，了解地下地质体( 包括地层、断层、褶皱构造等) 的三维形态，准确地解译和圈 定地下地质体，以便指导矿业开发和深部找矿预测i l2 j 。这就必须利用三维可视化建模技 术，将地质上的逻辑思维和空间上的形象思维有机地结合起来，通过信息的动态反馈来 获取矿体空间形态变化和品位变化等地质规律。 o p e n g l 可以方便的显示三维效果，及变换过程，它可以实现：建模、变换、颜色 模式设霞、光照设置、材质设置、纹理设景、位图等功能【l 引。它简化了常规的三维编程， 一般操作如消隐，光照处理等，只需要直接调用o p e n g l 的a p i 函数即町。用o p e n g l 来实现三维显示，具有简单，直观，效率高的特点，是三维重构非常好的工具。基于此 我们在论文的实现部分利用o p e n g l 和可视化技术实现论文的最终结果的显示和控制。 1 5 本文所做的主要工作及论文的嫡构安排 1 5 1 澡题研究内窖 论文主要以三维空闻复杂多值曲面建模研究为主要内容，从三维离散点的宅闻分析 到最终模型的建立及显示实现。具体包含以下方面： a ) 提出一种对点群进行空间位置分析的动态聚类方法。对三维空问离散数据点集进 行聚类分析，按照一定的标准分别划归翻各自的合理区域，建立起三维散乱点位 雹的局部拓扑关系。 b ) 提出，一种网格曲面边界缝合的算法。对建立的局部曲面拓扑进行了正确缝合进 而得到了整个完整曲面。 c ) 对空间散乱点进行合理三角化对曲面进行模拟逼近的方法。 d ) 利用o p e n g l 图形函数库，对得到的三维曲面模型进行三维显示和控制，得到真 6 山求科技大学硕上学位 仑文绪论 实感曲面。 在前几点的基础上建立起一个对三维散乱点进行分析并建立原始复杂多值面的 绋n r 视化系统，由二维散乱点得到曲面模型。 1 5 2 文章结构安排： 第一章绪论部分，介绍了曲面重建的有关概念，曲面重建的应用价值，重建的关键 技术，课题的研究内容及本论文的结构安排。 第二章曲面重建综述部分，对目前所存在的一些散乱点集曲面造型经典算法做了详 尽的研究，并进行了细致的介绍、分析和比较。 第王章利用聚类分析的曲面重建部分，提出了一种新的基于主成分分析的聚类方法 进行曲面重建的技术，并对该方法及涉及的相关技术和算法进行了详细的介绍和阐述。 第四章o p e n g l 及可视化部分，详细的介绍了o p e n g l 编程工具及怎样来利用 o p e n g l 来对所得出的曲面进行真三维显示与控制的。并介绍了利用跟踪球对所建模 型进行显示控制的算法。 第五章总结与回顾部分，对本文所做工作进行了总结和回顾，并指出了下一步i ：作 的疗向。 7 山东科拄大学硕士学位论文三角剖分及散乱点曲面重掏综述 2 三角剖分技术及散乱点曲面重构综述 2 1 1 三角剖分技术简介 2 1 三角剖分技术 二角剖分是本文算法中确定点与点之问的连接关系的一个非常重要的工具，是本文 算法的实现基础。三角剖分是计算几何| 7 1 中一个非常重要的概念，其研究可追溯到三十 年代，并在七十年代后期得到了较大的发展和应用。其中以d e l a u n a y 三角剖分最具代 表性，它是优化的三角剖分，简记为d t ( d e l a u n a yt r i a n g u l a t i o n ) 。虽然d t 处理的对象 是散乱点的凸包，但是在实际应用中它已拓展到很多其他情况，如本文三维曲面的二i 角 测分问题，也是采用许多d e l a u n a y 三角翻分的原理。1 f 面主要介绍几种主要的三角剖 分。 2 1 2 平面三角剖分 平面点集的三角剖分：称三角形集合r = 征，疋，巧 为平面上m 个非共线有限点 集p 的三角剖分，当且仅当t 满足以下_ _ 三个条件： 1 ) t 的顶点集为p 2 ) p 的凸包c u 瓦 3 ) t 中任两个三角形的交集或者为空集，或者是p 中的点，或者是以t 中两点为 端点的直线段。 下面是几种求平面点集三角剖分的常用算法： 贪心算法： 主要分两步 步1 ：计算所有点之间的所有距离，按距离递增排列距离，记录距离和相应线段； 步2 ：首先往集合里加一条线段，然后对所有线段重复以下操作，依次选一线段， 并判断是否与先加入的线段相交，若相交，则册5 之，否者加入集合。 8 【i j 东科技九学顽i 学位沦文三角剖分盈散乱点曲面重构绿迹 平而剖分的凸壳算法( 最小权角剖分) ： 输人：平面点集 输出：三角剖分 步1 ：求点集凸壳并记录，从点集中删去所求凸壳点； 步2 ：重复步1 操作知道最后所得点集仅有1 个点或者2 个点或者没有点为止； 步3 ：如果没有点，则执行最小权划分算法对第层凸壳所成多边形进行剖分。 如果只有一个点，求上层凸壳所有点与该点的最大距离点。并把它当作直径，用最 小权划分算法进行处理且只处理其另一端点( 上层凸壳点) ； 如果有两个点，则把这两点所成有向线段的左右两边的上层凸壳点分为两个凸壳； 用最小权划分算法进行处理。 步4 ：对紧挨的两曾凸壳之间的区域进行三角剖分。方法是求内层凸壳两相邻点组 成有向线段的右边外层凸壳点，组成凸壳，用最小权划分算法处理。循环所有相邻点， 则完成划分。 步5 ：对每层凸壳边执行一个调整操作。共边的两三角形，若第三点的连线小与公 共边，则凋整三角形。 最小权划分算法：求直径，删除和直径两端点相关的最短边所对的唯一顶点。对点 集重复以上操作直到剩余点为一三角形三顶点为止。 2 1 3 平面点集的d e l a u n a y 三角割分 从平面点集三角刮分的定义不难看出，对于一个给定的点集p 满足定义的三角剖分 不是唯一的，需要对t 附加确定的优化条件才能得到难一结果。理想情况下的三角网格 的各个单元应是等边三角形，但这一目标通常是难以企及的，因此通常只能使：三角形的 内角尽可能的大。这样网格的各个三角形单元的最小内角便成为衡量网格质量的一个萤 螫标准：最小内角越大，网格质量就越好。 1 9 3 4 年，b d e l a u n a y 证明例：必定存在且仅存在一种剖分算法，使得所有三角形的 最小内角最大。这种剖分被命名为d e l a u n a y 三角削分。5 0 年代，g e q o r o n o i l l 4 1 提出 v o r o n o i 图的概念。1 9 7 0 年，m i l e s i j 驯在此基础上建立了较完善的v o r o n o i 基础理论体系， 证明其直线对偶图即是d e l a u n a y 三角剖分，具体说来，其定义形式是这样的： 坐查壁焦查兰堡主兰焦笙茎三塑型坌丝墼垫皇堕堕重塑簦垄 平面点集的d e l a u n a y 三角剖分： 给定二维平面上的点集合v = v 0 ，k ， ( | v 3 ) ，假设这些结点不全共线。、若 d ( v ，v ，) 表示v 与y ，的距离，v ( j ) = x l d ( x ，v ) ( a ( x ，v ，) ，x r 2 ，j = 1 , 2 ，z 巾包 禽的点到k 的距离比到其它任意点y ，e v 的距离都近，称v ( i ) 为v 的v o r o n o i 图，v 为 v ( i ) 的内核。 将点集v 的所有相邻v o r o n o i 多边形的内核相连，形成点集v 的三角剖分d t , 称这 样的剖分结果为点集v 的d e l a u n a y 剖分。称d t 中的三角形为d e l a u n a y 三角形。 d 一三角网的外边界是一个凸多边形，它由节点集中的凸集形成，通常称为凸壳。 d j 角网具有两个非常重要的性质。 ( 1 ) 空外接圆性质：在由点集v 所形成的d 一三角网中，其每个三角形的外接圆均不 包含点集v 中的其他任意点。 ( 2 ) 最大的最小角度性质：在由点集v 所能形成的三角阏中，d 一三角网中三角形的 最小角度是最大的。 由于这两个性质，决定了d 一鼍角网具有极大的应用价值。同时，它也是二维平面 三角网中唯一的、最好的。 实现平面点集的d e l a u n a y 三角制分可以分为三类“6 1 ：分治算法、逐点插入法、三 角网生长法，这里主要介绍逐点插入法和三角网生长法 逐点插入法： 基本思路：先在包含所有数据点的一个多边形中建立初始三角网，然后将余f 的点 逐一插入，用l o p 算法确保其成为d e l a u n a y 三角阏。本算法的基本步骤为： ( 1 ) 定义一个包含所有数据点的初始三角形； ( 2 ) 在初始多边形中建立初始三角网，然后迭代以下步骤，直至所有数据点被 处理： ( 3 ) 插入一个数据点p ，在三角网中找出包含p 点的三角形，把p 点与三角形 的三个顶点相连，生成新的三角形； ( 4 ) 用l o p t l 8 1 算法优化三角网。 l a w s o n 提出的局部优化过程( l o c a lo p t i m i z a t i o np r o c e d u r e ) 算法是为r 生成 d e l a u n a y 三角网。从理论上说，不论用何种方法生成三角网，只要用l o p 算法进行处 1 0 里t 受登垫查竺堡圭兰垡垒墨三鱼型坌墨墼坠皇些堕塞塑墅堡 理，就能使它变成d e l a u n a y 二i 角网。算法的基本含义为：x , t f h 两个共边的三角彤组成 的四边形进行判断，如果其中一个一i 角形的外接圃包含第四个顶点则将这个四边形的 刈角线交换。 三角网生长法： 1 首先寻找两相邻的数据点，或者最近的两点，把此两点的连线作为扩展边( 假 设两点分别为第一点、第二点) ； 2 利用d e l a u n a y 原则寻找第三点，在v o r o n o i 图退化的情况下，三角形外接圆一卜 的数据点数 3 。此时，有多于一个点与扩展边连线的夹角相等。从数据点向扩 展边作垂线，取其垂足离扩展边中点最近的点为扩展点得到当前扩展边的扩展 点，即三角形的第三点。这样，就形成了第一个三角形； 3 利用第一个三角形的三边( 注意，如果从边界开始，就只处理第一点与第三点， 第三点与第二点的连线边) ，使之作为三角形扩展边，得到新的i 角形。重复 相关步骤，形成新的三角形； 4 结束t i n 自动生成的条件是无新的三角彤生成。 2 1 4 平面点集的约束d e l a u n a y 三角匍分( c d t ) 1 1 9 2 1 捌： 由于在很爹隋况下，三角剖分需要有某些约束线段或者约束多边形存在，面传统的 d t 方法很难满足这些约束条件，于是就产生了约束d e l a u n a y 三角剖分( c d t ) 算法。即 所谓c d t 算法，就是满足某些约束条件的d t 算法，或者说是在d t 算法中强制某些约 束条件即边或者多边形必须在三角剖分中出现。由于c d t 算法实际上都是在d t 算法 基础上产生的，因而我们只需要设法让给定的约束条件在d t 算法的剖分结果晕出现实 际上就完成了c d t 算法。最常用的方法有两种，一种是强行嵌入法，这样嵌入后再调 整其影响域尽量使之满足使之d e l a u n a y 特性，但是嵌入影响域很可能不再严格具备 d e l a u n a y 特性。另种就是插点法，是通过插入另外的点把约束边分割使之满足 d e l a u n a y 特性。比较常用的插点方法有中点插入法，就是在约束边的中点插入看是否满 足d e l a u n a y 特性，若不满足，再找中点，由于这种方法可能会插入较多的冗余点，义 有人提h ；了一种约束边与影响域外器圆的交点作为插入点的插入法。下画对这种算法加 以介绍： ( 1 ) 判断特征约束线a b 是否为d t 的边，若不是受 l 进行以下操作； 1 1 东科技大学顿士学位论文三角剖分及散乱点曲面重构综述 ( 2 ) 求出a b 经过的第一个三角形( 简称起始t 角形) 的外接圆与线段a b 的交点q ， 0 lq 即为插入的第一个点； ( 3 ) 运用d t 规则及相应的算法，使点q 及其影响域内的点的连接符合d t 规则； ( 4 ) 把q 作为新的起始点重复( 1 ) 、( 2 ) 操作直到新的起始三角形的外接圆与约束边巾 点与最后一条影响边所成三角形的外接圆相交时为止。为避免插入点离终点太近，最后 的插入点取最后起始点与终止点的中点。 2 2 基于离散点集的空闻曲面建横现状分析 所谓散乱点曲面重建，是指从曲面上的部分采样信息来恢复原始曲面的几何模型。 能否正确重建的关键其实就是如何搞清楚其拓扑结构。所以，关键就是对三维物体进行 卒间结构分析和趋势分析2 引，把拓扑结构搞清楚。当然，要建立整个曲面的拓扑结构， 最首要的就是建立点与点之间，线与线之间，面片和面片之间的拓扑关系。表达点之间 拓扑关系的一个很重要的方法就是八叉树方法矧。在所有的散乱点曲面拓扑重建算 法q t ，又可以大体分为三类算法，局部重建法25 。2 6 ，整体重建法2 9 地圳，和函数重 建法f 2 72 “。 基于散乱点集的任意拓扑空闯曲面的重建，由于其拓扑结构的未知性和复杂性，使 得模型的构建变得特别困难。在这方面，国外不少学者进行了大量的研究，而国内学者 在这万面的研究相对来讲还不是太成熟。散乱点的曲面重构，关键在于其拓扑结构的准 确建立，由于数据信息的有限性，这也成为了问题的难点所在。下面对一些经典的算法 做一f 简单介绍。 2 3 相关算法综述 大部分的曲面重建算法都是要利用采样点的某些相荧信息，例如：曲面的拓扑结构、 数据的结构、曲面的法向的信息等。本文仅讨论散乱点重建曲面的算法，这里的散乱点 是指仅有采样点的三维坐标，而无其他任何附加信息的点，但一般来讲，模型的构建是 1j 点的采样密度紧密相连的。 2 3 1h o p p e 等人的算法田2 8 1 ： 荚国华盛顿大学计算机系h o p p e 等人对基于散乱点集的任意拓扑曲面重构进行了 ) r 创性的研究，提出了一种通过构造零等值面进行模型构建的算法。 1 2 东科技大学硕士学位论文三角削分及散乱点曲面重构综述 这种算法是一种生成近似曲面的方法，这种方法通过定义每个取样点的近似切平 唾，然后把到最近点的切平面的有符号距离，作为在r 3 中的距离函数，插值距离函数， 用步进立方体的算法生成多边形网格，然后再生成曲面。在模型构建过程巾，h o p p e 等 人给出 广一个描述点集密度的简单准则，引入了p 密度样本的概念。在此基础上，他f j 进行了如下几步工作完成了对模型的构建。 首先，为每个采样点用其茁个最临近点构造一个距离平方和最小的切平面来近似 估计其有向切平面。取采样点的邻域内的k 个点，邻域的大小由采样点的密度决定， 求蛙i 这个点的重心，作为估计切平面的中心，再用这墨个点构造协方差矩阵，计算 特征值，从而计算出切平面方程及切平面的法向量，这样计算出来的法向量可以有一正 一负两个取值。 其次，确定切平面的方向。实质就是选取计算出的一正一负两个法向量的取值中的 一个。判定方法是，从一个己知正确法向的切平面出发，判断和它相邻的其他切平面。 当两个采样点距离很近的时候。相应的两个估计切平瓣的法向量的点乘就近似为+ l 或 1 ，l 是正确的结果，而如果是一1 就应该把该相邻切平面的法向量翻转。为解决这个f h l 题，通常采用近似的深度优先搜索树的方法。 再次，构造有符号距离函数。其方法是，在空阊中任意一点p ，到己知曲面m 的有 符号距离函数f q ) ，是p 到曲面上离p 最近的点z 的距离，乘士1 ，正负取值依赖于p 位于曲面的哪一侧。事实上m 是未知的，但可以用如下的定向切平面模拟这一过程。首 先，找到切平面l o i ) ，它的中心o i 是最靠近p 的。这个切平面是m 的局部近似，所以 把到m 的有符号距离函数“p ) ，作为p 和它在瓦( 玉) 上的投影z 之间的有符号距离函数。 然后，确定边界。如果曲面m 已知无边界，这一简单规贝很适用。然而，当曲面 有边界时，规则必须扩展以适应曲面。规定d ( z ，x ) ( z 和x 之间的距离) 的取值范围，当超 过某一域值p 时，就把“p ) 作为边界处理。 最后，进行边界追踪的操作，提取零等值磁，进行模型构建。从一个标罱函数提取 同种曲面。可以选取执行一个步进式立方体变量的算法，此算法在立方体格的向量| 二抽 取函数，在立方体元的四面体分解中发现边界根交。适当选取立方体的边长，通常与点 的密度值大小相近。在实际应用中取略大一点的值，可以加快处理速度，但如果取值过 大，就不能表现原曲面一些微小的特征。把与零集相交的立方体推入队列，根据与近似 切平面的相交关系，推导出有符号距离函数。 1 3 里垒燮叁堂堡主堂焦篓塞 三鱼型坌墨墼塾皇塑堕垦塑堡荽 这样由点集x 生成的是一个初始近似表面，但这样生成的网格比较密集，可能有 很多不想要的折痕和起伏，需要进一步的简化和优化，设定能量函数，去除或增加点， 移动点的位置，改变网格的连接关系( 在保持拓扑不变的条件下) 等，以达到能量函数最 小值，最终生成既简洁又精确的网格曲面表达形式。 图2 1 原始模型 f i 9 2 1o r i g i n a lm o d e 图2 , 3 调整后的法向 f i 9 2 3n o r m a l sa d j u s t e d 图2 2 从原始模型采到的采样点 f i g2 2p o i n t ss a m p l e df r o mo r i g i n a lm o d e l 蹦2 a 经步进立方体后得到的模型 f i 9 2 4m o d e l w i t hm c 图2 5 步进立方俸求解示意图 f 瑭2 5d i a g r a mo fm c 1 4 j 东科拦大学硕士学位论文 三角削分及散乱点曲面重构综述 2 3 2a s h a p e t 2 9 1 和改进的a s h a p e 方法3 0 3 1 9 9 4 年e d e l s b r u n n e r 提出了a s h a p e 的概念，a s h a p e 方法删除了四面体凸包巾其包 罔球或外接圆半径大于a 的边、_ _ 三角形和四面体来得到重建表面。对于均匀一致的数锯 点集a s h a p e 方法很有效，但由于数据点集的不均匀性或表面的某种不连续性，有时很 难自动选择合适的a 值，以保留需要的三角化元素，删除不需要的所有冗素。a s h a p e 足一个点集的凸包的产物。s 是三维实数空间中的一个点集，a 是实数空间的某个值，s 的a s h a p e 是空问的一个多面体，这个多面体不要求是凸包，也不要求是连接的。当a 趋向于无穷大的时候，a s h a p e 等同于点集的凸包，当a 减小的时候，a s h a p e 随着变化， 逐渐生成凹处，这些凹处进一步形成隧道甚至是空洞。理论上认为，如果表面的采样足 够密集，对采样点集进行d e l a u n a y 三角剖分后，从三三角片集合里面抽取的分段线性的 f l l 面