（应用数学专业论文）基于delaunay三角剖分的曲面拟合.pdf

摘要 近年来，用d e l a u n a y 三角剖分的方法来进行曲线、曲面的拟合与逼近已成为 计算机辅助几何设计( c a g d ) 领域研究的热点问题，它在图形设计等方面有着 广阔的应用前景。 d e l a u n a y 三角剖分是c a g d 中用于曲线、曲面逼近的一种非常有效的方 法，主要有两种方法生成d e l a u n a y 三角剖分，一是给定样本点集，做出它的 v o r o n o i 图，然后，将其v o r o n o i 单元相邻的样本点连接起来，这样就形成了 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 三角剖分方法的基本概念和理 论、模型的构建方法及经典的计算方法。并且，为了解决三角网格的优化问 题，采用对等翻转的方法，优化普通的三角网格，有效的提高了运算速度及曲面 的光滑性。另外，本文还将d e l a u n a y 三角剖分的方法应用到了曲面的逼近。实 例表明，该方法简洁、快速、有效。 对于非凸包区域的处理方面，本文采用了对边界点添加保护圆、边界边添加 保护边的方法，构成缓冲区域，分别对缓冲区域和原区域内部进行三角剖分，两 者就不会相互影响。实践证明该方法能很好的逼近原曲面，更好地保持原曲面在 非凸包区域的几何特征。 关键词：d e l a u n a y 三角剖分v o r o n o i 图空圆定理对等翻转非凸包区域逼近 a b s t r a c t r e c e n t l y ，t h em e t h o do fd e l a u n a yt r i a n g u l a t i o ni nc a g du s e dt oa p p r o x i m a t e t h eo r i g i n a lc u r v eo rs u r f a c eh a sb e e na h o ts u b j e c t ，w h i c hh a sav a s tf u t u r ei ng r a p h d e s i g n d e l a u n a yt r i a n g u l a t i o ni sv e r ye f f e c t i v ei nt h ea p p r o x i m a t i o no f c u r v eo rs u a c e i nc a g d t h e r ea r et w ow a y st oa c h i e v et h i sp u r p o s e f i r s t ，g i v e na s a m p l i n gp o i n t s s e t ，p l o ti t sv o r o n o ig r a p h t h e n ，c o n n e tt h ep o i n t sw h o s ev o r o n o ic e l li sa d j e n t , a n d w h a tw eg e ti st h ed e l a u n a yt r i a n g u l a t i o n i np r a c t i c e ，w en e e dt oc o n s 仃a i l lt h e i n f l u e n c ef i e l ds o m et i m e s ，s ow e g i v ee a c hp o i n tw h i c hw i l lb ec o n s 仃a i 芏l e dap o w e r t oa c h i e v et h eg o a l a n d t h e n ，b yt h ew a yi n t r o d u c e da b o v e ，ad e l a u n a yt r i a n g u l a t i o n i sg o t ，w h i c hi sc a l l e dr e g u l a rt r i a n g u l m i o n s e c o n d , f o r ma t r i a n g u l a t i o n 丘o mt l l e o r i g i n a ls a m p l i n gp o i n t s ，t h e no p t i m i z et h eo b t a i n e dt r i a n g u l a t i o nt om a k ei ts a t i s f y t h ee m p t yc i r c l ep r o p e r t y ，w h i c hi st h ed e l a u n a yt r i a n g u l a t i o na n d a p p r o x i m a t e s t h eo r i g i n a lc u r v eo rs u r f a c eb e t t e r t h i si s s u es u m m a r i z e sa n ds t u d i e st h eb a s i cc o n c e p t i o n sa n d t h e o r i e s ，m o d e l i i l g m e t h o d sa n dc l a s s i cc o m p u t i n gm e t h o d so f d e l a u n a yt r i a n g u l a t i o n a n d ，i no r d e rt 0 o p t i m i z et h et r i a n g u l a t i o n ，t h em e t h o du s i n gb i s t e l l e rf l i pw h i c hm a k e st h e t r i a n g u l a t i o nt h ed e l a u n a yt r i a n g u l a t i o ni sp r o p o s e dh e r e ，w h i c ha c c e l e r a t e sm e c o m p u t i n ga n de n h a n c e st h es m o o t hp r o p e r t y a n di ti sa l s oe x t e n d e di n t oc u r v e a p p r o x i m a t i o n n u m e r i c a le x p e r i m e n t sa r ea l s og i v e nt os h o wt h a tt h ea l g o r i t h mi s s i m p l e ，f a s ta n de f f i c i e n t e s p e c i a l l yf o rt h en o n c o n v e xh u l lr e g i o n ，n e wp o i n t sa n d p r o t e c t i n ge d g e sa r e a d d e dt ot h eo r i g i n a ls u r f a c et oc o n s t r u c tb u f f e rz o n e t h e n t r i a n g u l a t et h eb u 行e rz o n e a n dt h ei n n e rp a r to ft h eo r i g i n a ls u r f a c es e p a r a t e l y ，w h i c hw i l ln o ta f f e c t se a c ho t h e r t h e p r a c t i c ep r o v e st h a tt h i sm e t h o dt r e a t sb e t t e ra p p r o x i m a t i o nt ot h eo r i g i n a l s u r f a c ea n dl o s el e s sg e o m e t r i cc h a r a c t e r i s t i c s k e y w o r d s ：d e l a u n a yt r i a n g u l a t i o n ，v o r o n o ig r a p h ，e m p t y - c i r l e 阶0 p e 咄 b i s t e l l e rf l i p ，n o n - c o n v e xh u l la p p r o x i m a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：讪对字吼川年月，日 学位论文版权使用授权书 本学位论文作者完全了解叁童盘堂有关保留、使用学位论文的规定。 特授权基盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：7 呵年 叫水 6 月如 导师躲汐寸f 伽 签字日期：夕口护7 年厂月莎日 基于d e l a u n a y 三角剖分的曲面拟合 1 1 引言 第一章绪论 长期以来，工业产品的开发都要遵循着严谨的研发流程，从确定功能与规格 的预期指标开始，构思对产品零件的要求，再由各个组件的设计、制造以及检验、 性能测试等程序来完成。每个组件都保留原始的设计图，此设计图目前己广泛采 用c a d 图档来保存。每个组件的加工也有所谓的工作命令图表，对复杂形状组 件则用c a m 软件产生的n c 加工档案来保存。每个组件的尺寸合格与否，则以 产品管理检验报告来记录。这种开发模式称为预定模式，这类开发工程也称为正 向工程。对每一组件来说，其正向工程的流程主要为规格定制、设计、制造、检 验。 正向工程是一个“从无到有”的过程。设计人员首先在大脑中构思产品的外 形、性能、大致的技术参数等，然后通过图纸或在c a d 技术的帮助下建立产品 的三维数字化模型，最后将这个模型转入到制造流程中去，完成产品的整个设计 制造周期。 而逆向工程技术与传统的正向设计存在很大差别。逆向工程产品设计可以认 为是一个“从有到无”的过程。简单地说，逆向工程产品设计就是根据已经存在的 产品模型，反向推出产品设计数据( 包括设计图纸或数字模型) 的过程。从这个 意义上来说，逆向工程这一概念在工业设计中使用已经很久了。早期的船舶工业 中常用的船体放样设计就是逆向工程的典型实例。 随着计算技术在制造领域的广泛应用，特别是数字化测量技术的迅猛发展， 基于数据测量的产品造型技术已经成为逆向工程技术领域所关注的主要对象。通 过数字化测量设备( 如坐标测量机、激光测量设备等) 获取物体表面的空间数据， 然后利用逆向工程c a d 技术获得产品的c a d 数学模型，进而再利用c a m 系统 完成产品的制造。因此，逆向工程技术可以认为是将产品样件转化为c a d 模型 的相关数字化技术和几何模型重构技术的总称。 逆向工程的设计流程为已知样品，然后对其进行外形量测、数据处理、c a d 曲面重构、外形修饰、模具成型、量产复制。 一般地，产品逆向工程包括形状反求、工艺反求和材料反求等几个方面，在 工业领域的实际应用中，主要包括以下几个内容： 基于d e l a u n a y 三角剖分的曲面拟合 ( 1 ) 新零件的设计，主要应用于产品的改型或仿型设计； ( 2 ) 已有零件的复制，再现原产品的改型或仿型设计； ( 3 ) 损坏或磨损零件的还原； ( 4 ) 数字化模型的检测，例如检验产品的变形分析、焊接质量等，以及进行模型 的比较。 逆向工程技术为快速设计和制造提高了很好的技术支持，已经成为制造业信 息传递的重要而简洁的途径之一。 曲线与曲面重构是逆向工程的形状反求中所研究的重要问题。近年来，随着 计算机辅助几何设计和图形学的发展以及计算技术的广泛应用，以曲线、曲面重 构为代表的逆向工程技术无论在理论和应用上都取得了巨大的成功，其应用几乎 涉及了自然科学和工程技术的一切领域，包括汽车、飞机、轮船外形涉及与制造 等工业领域，以及依据大量数据计算和对计算结果进行分析的气象领域，需要实 现形体的网格划分及结果数据显示、优化的有限元分析，以及根据测量数据建立 人体骨骼和器官的计算机模型的医学和定制生成领域等等。 曲线与曲面重构所研究的问题可解释为对未知曲线或曲面，通过采样得到一 组数据点，曲线和曲面重构就是从这组采样数据出发，构造曲线或曲面，使其尽 可能高的精度逼近原始曲线或曲面，并满足某种连续性要求。【l 】 随着曲线、曲面重构技术研究的深入，各种重构方法层出不穷。d e l a u n a y 三 角网格化就是其中的一种。 d e l a u n a y 三角网格化已经有很长的历史了。1 9 0 7 年，g v o r o n o i 率先提出了 这个概念，引起了学术界的广泛关注。此后不久，d e l a u n a y 于1 9 3 2 年首次提出 了解决这类问题的方法，三角网格化的概念应运而生。三角网格化主要有两种准 则：一种称为d e l a u n a y 三角剖分，即在生成的三角形网格中，各三角形的最小 内角和为最大；另一种是在生成的三角网格中，所有三角形的边长和最小。其 中，第一种方法也叫d e l a u n a y 三角剖分，是目前研究应用最广的一种剖分方 法，也是本文研究的重点。 近年来，平面任意点集的三角剖分问题一直是人们密切关注的问题。三角 剖分问题在许多领域有广泛的应用。例如：固体物理学、计算流体力学、统计 学、气象学、计算几何学等。 目前，d e l a u n a y 三角剖分方法日趋成熟，在现代化的几何设计和计算机应 用中发挥着重要的作用。 已知物体表面f 的样本点集s ，表面重构问题就是获取原曲面f 的分段线性 近似。如图1 1 所示，给出了由样本点生成的重构曲面，其中图( a ) 为输入样本点 集，图( b ) 为使用加权法得到的重构表面。 2 基于眦t m a y 三角剁升的曲面拙合 ( 曲样本点集重构表面 图】表面重构 可以采用不同的方法得到输入点集，如使用激光测距扫描仪手工测量数据 三维照相，c t 等等。在机械方面的应用主要有逆向工程，产品设计和个性化医 疗器械的设计。】 表面重构问题已经引起了许多行业的注意，如：计算机图形，固体模型，计 算机图像和计算几何。可以将所有的算法分为两类：第一娄算法只需要样本点的 坐标，或者附加一些其他性质就可以得出重构的曲面；第二类算法则只适用于 特定的输入，如：激光测距扫描仪提供的带样本点法向的测量数据，或者是计算 机图形技术提供的数据。重构算法也可以根据输出的不同进行分类。重构表面可 以用来插值或逼近样本点。一些能够重构致密的物体另外一些则输出带边界的 表面。一些算法重构分段线性表面而另一些则重构出光滑的或分段光滑的函数。 这里蕴藏着大量的工作。下面只介绍与本论文密切相关的工作。 hh o p p e 等的研究工作，使该问题在计算机图形领域中的应用流行起来。 输入是无序的点。该算法利用k 个相邻的样本点估计每一点处的切平面，重构了 一个带标记的距离函数。然后利用遍历算法得到了分段线性表面的取样。 c u r l e s s 和l e v 叫州从测量数据重构表面。他们的方法除了要用到样本点的坐 标以外还用到了其他性质，如表面法向及数据的可靠性，重构出带标记的距离 函数。他们引入了洞的填补，该方法在实践中非常有效并且在m i c 蝴l o 作 品的复制中有着重要的应用，不过该工程的模型过大，计算过度慢。虽然该方法 的输出是稳定的，但并没有理论保证输出的重构是正确的。 h kz h a o 等”悃微分几何及偏微分方程阐述了表面重构问题。他们在固定 的矩形栅格上应用水平集方j 去重构表面。输入数据可以包含点，曲线或曲面的补 丁。对于噪声或者不良好的输入数据的处理，该方法是十分有效的，但运算速度 很慢，并且依赖于噪声栅格。 ho d i l 山等嘲从计算机图像技术，将有噪声的、非正规的且不好解决的测 量数据重构成一个三维函数，并通过该函数得到了光滑、几乎无缝的几何模型。 基于d e l a u n a y 三角剖分的曲面拟合 该三维函数是一组加权半径的基本函数的有序组合。该算法由于是近似，而不是 插值原数据，因此对于噪声很敏感，而且丢失了某些微小的几何变化。 在计算几何中，有许多重构算法是应用样本点的d e l a t m a y 三角剖分得到的。 b o i s s o n n a t t t j g i 造性的提出了从样本点的d e l a u n a y 三角剖分中逐个移除d e l a u n a y 四面体的方法。但是该方法没有理论保证，而且对于一些正常的输入不能得到输 出结果。 e d e l s b r u n n e r 和m n c h k e 【8 】提出的一型也是d e l a u n a y 三角剖分的一个子集。 对不正规的样本，尽管a 一型很有效，但是却很难找到一个合适的直径a 来完成 洞的填补并且有可能丢失部分图形。 1 9 9 9 年，n a m e n t a 等【9 ，1 0 】提出的外壳与我们的工作是最相近的。对于非正 规的样本输入，基于采样的采样情况下，重构图形在几何上逼近原曲面。这是 第一个有理论保证的算法。 给定样本点集合及法向，b o i s s o n n a t 和c a z a l s 】通过插值得出了光滑固定的 曲面。在每一点处，该算法都进行插值，但计算量却十分大。 f b e m a r d i n i 等【1 2 】提出了对于测量数据的球轴的算法。该算法需要有样本点 处的法向。由于不使用d e l a u n a y 三角剖分，于是能有效的处理大量的数据。 由初始的联合体经过一系列的对等翻转可以得到有限的单纯形联合体。对于 这些翻转，它们以一种特殊的方式给出了变换剖分的办法。但这种变换的方法却 有很多可能性。 近些年的应用表明，对等翻转的理论在实践中有着广阔的应用空间，能够从 一个分段线性复本的任意一个三角剖分变换到另外一个三角剖分。有限次数的翻 转可以直接应用于定义在单纯形理论上的任何副本常量。 本文研究的重点是表面重构方法的瓶颈d e l a 岫a y 三角剖分，将普通的三 角剖分优化成d e l a u n a y 三角剖分的方法一对等翻转，及对于非凸包区域的处 理。 1 2 本文的主要工作 本文首先研究三种典型的直接生成d e l a u n a y 三角剖分方法，一是d e l a u n a y 三角剖分。该方法通过给定样本点集，做出它的v o r o n o i 图，然后，将其v o r o n o i 单元相邻的样本点连接起来，这样就形成了d e l a u n a y 三角剖分。但是，为了实 际需要，需要控制样本点对其它样本点的影响范围，因此对其加以限制( 如在需 要加限制的样本点处做圆) ，然后再对加权后的样本点集作v o r o n o i 图，连接 v o r o n o i 单元相邻的样本点，得出了v o r o n o i 图的对偶d e l 帅a y 三角剖分， 4 基于d e l a t m a y 三角剖分的曲面拟合 即常规三角剖分，这是第二种方法。三是在逼近中轴这一想法的基础上，得出对 原曲面进行逼近的加权壳方法。但要精确的计算出中轴是很困难的。因此有许 多关于逼近中轴的工作，一种流行的方法就是用v o r o n o i 图来逼近中轴。 而后，研究了三角剖分的优化算法。该方法由已知的样本点集生成三角剖分， 然后用对等翻转的方法对该三角剖分进行优化，使得三角剖分中的每个三角形 都满足空圆( 球) 定理，这样得到新的三角剖分，即d e l a u n a y 三角剖分。该方 法能更好地逼近初始曲线、曲面。实践证明该方法在应用中快捷、有效。 然而，实际应用中，更多的是出现了很多不规则的区域。因此对于非凸包区 域的处理显得非常重要。本文采用了对于非规则区域的边界点添加保护圆、对非 规则区域的边界边添加保护边的算法，以构成缓冲区域，形成对非规则区域的边 界点和边界边的保护。然后，分别对缓冲区域和原区域内部进行三角剖分。显然， 这两个过程是相互独立的，不会相互影响。最后，将所得的两部分d e l a u n a y 三 角剖分进行合并，得出对原曲面的逼近。实践证明该方法能很好的逼近原曲面， 因为它对原曲面非凸包区域进行了重点剖分，会较好地保持原曲面在非凸包区域 的几何特征。 1 3 本文的内容组织 第一章介绍了本文的研究背景及主要工作； 第二章是对d e l a u n a y 三角剖分的详细研究，主要内容包括两种典型的直接 生成d e l a u n a y 三角剖分的方法，算法的连续性和收敛性的分析； 第三章研究了二维及三维情况下的对等翻转方法，该方法通过将普通的三角 剖分进行对等翻转，从而优化成d e l a t m a y 三角剖分； 第四章是本文的主要章节，在前三章的基础上研究了d e l a u n a y 三角剖分中 网格优化的必要性，并给出了算法的理论推导和示例。而且，对于非规则区域， 采用了构造缓冲区域的方法，然后再进行d e l a u n a y 三角剖分。 第五章是本文的总结及对未来工作的展望。 5 基于d e l a u n a y 三角剖分的曲面拟合 第二章基于v o r o n o i 图的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 三角剖 分方法的特点、分类、性质、计算及应用，并有代表性地研究了两种基本的生 成d e l a u n a y 三角剖分的方法，包括v o r o n o i 图与d e l a u n a y 三角剖分，空圆定理 与三角剖分等。本章最后的算例，演示了v o r o n o i 图与d e l a u n a y 三角剖分，空 圆定理与三角剖分的应用。 虽然该理论可以应用到任意维空间，不过本文重要研究二维及三维情况下 d e l a u n a y 三角剖分的主要内容。 2 1 基本概念 2 1 1 仿射空间与仿射变换 由于仿射空间可以保证结构化数据与坐标系无关，使得仿射变换的几何理 论在参数化建模中得到了广泛的应用。 定义2 1 设e 是非空点集，向量空间云为定义在e 上的向量空间，运算 + ：e x e e ，如果e 、否和运算+ 构成的三元组( e ，否，+ ) ，满足下面条件： ( 1 ) 口+ 石= 口，v a e ； ( 2 ) ( 岔+ “) + ，= 口+ ( “+ ，吩，v a ，b e ，3 v ，y 掰e ； ( 3 ) v a , b e ，j 唯一的五否，使得口+ 云= 6 ， 则称( e ，云，+ ) 为仿射空间。 仿射空问中点的基本操作是仿射组合，通过引入质心组合的概念可以使仿 射组合独立于坐标框架。 定义2 2 对于仿射空间彳”，称 乃q ，其中五= 1 且o 丑l 6 基于d e l a u n a y 三角剖分的曲面拟合 为点集，口。的仿射组合。 仿射组合也称为质心组合，或质心。 定义2 3 已知仿射空间( e ，e ，+ ) ，如果对于e 的子集v 中的任一加权点集 ( 口f ，五x 。， 其中乃= 1 ，满足仿射组合，d 丑口，仍是y 中的点，则称y 为是 ( e ，e ，+ ) 的仿射子空间， 引理2 1 给定仿射空间( e ，云，+ ，对于e 中的点集q ，a n ，称由质心 以口j ( 其中，互= 1 ) 组成的集合y 是包含点集口l ，口。的最小仿射子空间。 i = 1i = 1 定义2 。4 给定两个仿射空间( e ，西，+ ) 和( e ：- g - , , + i ，称：e 专e 是仿射变 h 换，当且仅当对于点中满足乃= 1 的任一加权点集( q ，五) 心，有 厂( 丑口i ) = 五( q ) 令，昱为仿射空间中的点。考虑表达式 p = 眉+ f ( 罡一片) ， 其中( 罡一彳) 为一个向量，且f ( 罡一日) 为向量。如图2 - 1 所示，在二维点集和向 量的仿射空间中，任意点尸是点露和向量( 一暑) 的线性组合。 0 2 - - p l 图2 1 仿射组合 若0 ， - l f s ( q ) 一a ( p ，q ) ： 类似地，可得 l f s ( p ) 一d ( p ，q ) s l f s ( q ) 。 于是有 i l f $ 扫) 一l f s ( q ) 喀d ( p ，q ) 。 证毕。 引理2 2 如果v p ，q 6 f ，满足： a ( p ，q ) s p r n i n l f s 印) ，l f s ( q ) ， 1 3 ， 那么f 在点风q 处的法向的夹角不超过 基于d e l a u n a y 三角剖分的曲面拟合 乓l f s ( p ) 。 l - 3 p 证明：用参数表示线段朋。 设p ( t ) 为p q 上的直径值为t 的点，f ( t ) 为f 上离p ( t ) 最近的点，也就是说， 由p ( t ) 引出的直线首先交f 为f ( t ) ，则厂( f ) 是唯一的。否则p ( t ) 将是中轴上的点， 与 d ( p ，q ) p l f s ( p ) 矛盾。 设玎( f ) 为f 在f ( t ) 的单位法向量，j 刀( f ) i 为关于t 的微分，即f 变化时，刀( f ) 变 化的速率。由p 到g ，刀( f ) 的变化不会超过 l i 力v ) 防， 即 d ( p ，q ) m a x ，i 刀( f ) l 。 在f ( t ) 点，f 的两侧都有半径为l f s ( f ( t ) ) 的切球，故l ”。( f ) 最多也就是沿这 两个球中的一个旋转，由图2 1 5 ，可以看到， d ( t ) ( l f s ( f ( t ) ) - d ( f ( t ) ，p ( t ) ) ) s i no 。 由 l i m s i n 0 = 秒， 故 0 1 m i ( df l 删i m 衍t 面瓦而孟订万而。 由 d ( 厂( ，) ，p ) d ( 厂( f ) ，p o ) ) + d ( p ( f ) ，p ) 2 p l f s ( p ) ， 得 ( 1 2 p ) l f s ( p ) z f s ( p ) - d ( f ( t ) ，p ) l f s ( f ( t ) ) ， 又 1 7 基于d e l a u n a y 三角剖分的曲面拟合 得 故 于是引理得证。 2 2 2 算法 d ( 0 ) ，p o ) ) d ( ，o ) ，p ) p l f s ( p ) ， l f s ( f ( t ) ) ( 1 - 2 p ) l f s ( p ) ， 麟r i i 2 找出含x i 的三角形t f g 1 - 3f l i p ( x ，t ，t ) h e n d f o r 基于d e l a u n a y 三角剖分的曲面拟合 3 1 翻转中，对于三条边( p ，a ) ，b ) ，( p ，c ) 的共用点p ，当三角形( a ，b ，c ) 在剖分内时，则删除p 。这种情况只有在边界时才会出现。 算法3 23 1 f l i p ( p ，t = ，e ，f ) ) ( 从三角剖分t = ( v ，e ，d 中移除p v ，将三角形仁( a ， b ，c ) 插入到t 中幸) f 木拓扑条件： 1 ) 只有三个三角形t l = ( p ，a ，b ) ，t 2 ( p ，岛c ) ，t 3 = ( p ，b ，c ) f ； 2 ) 仁( a b ，c ) 芒f 幸) a 从f 中移除t 1 ，t 2 ，t 3 b 从t 中移除p c 将t 添加到t 中 在2 2 翻转算法中，边的翻转相当于用四边形的一条对角线来代替另一条对 角线。但这却有很多限制。设共用( a ，b ) 的两个三角形为( a ，b ，c ) ，( a ，b ，d ) 。如图 3 2 所示，( a ) 若( c ，d ) 在四边形( a ，c ，b ，d ) 外面，则称( a ，b ) 为几何不可翻转的；( b ) 若( c ，d ) 也在三角剖分中，那么( a ，b ) 称为拓扑不可翻转的。 c c 一 ( a ) 几何不可翻转的( b ) 拓扑不可翻转的 图3 2 ( a ) 几何不可翻转的；( b ) 拓扑不可翻转的 算法3 32 2f l i p ( e ，t ) ( 木从三角剖分t 中移除边( a ，b ) 木) ( 宰拓扑条件：若t 1 = ( a ，b ，c ) ，t 2 = ( a ，b ，d ) f ，则( c ，d ) 仨e 宰) a 从f 中移除t 1 ，t 2 b 从e 中移除e c 添加( c ，d ) 至0e 中 d 添a n - - 角形( a ，c ，d ) ，( b ，c ，d ) 到t 中 有了以上准备，给出l a w s o n sa l g o r i t h m ，它将不是局部d e l a u n a y 的三角形 转化为局部d e l a u n a y 的。给定一个三角剖分，对非局部d e l a u n a y 的三角剖分， 实施2 2 翻转，直到所有的三角形都是局部d e l a u n a y 的。l a w s o n s 算法如下： l a w s o n s d e l a u n a y t r i a n g u l a t i o n a l g o r i t h m a 求出s 的一个初始三角剖分t ( v ，e ，t ) ； 基于d e l a u n a y 三角剖分的曲面拟合 b 创建一个包含所有为两个三角形公用的边e 的队列q ； c w h i l eq 非空d o d 从q 中移出e = 他b ) ；找到以e 为公共边的两个三角形t l = ( a ，b ，c ) 和t 2 - - - ( a ，b ， d ) ( 即e 为四边形( a ，c ，b ，d ) 的对角线； e i f t l 的外接圆包含d ，t h e n 2 - 2 f l i p ( e ，t ) ； g 将不在q 里的边界边插入到q 中，得新的三角形； h e n d i f i e n d w h i l e 若( a ，c ，b ，d ) 不是凸的，则是不可翻转的，但可以认为这两个三角形是局部 d e l a u n a y 的，因为它们满足空圆条件，如图3 3 所示。 图3 3 三角形a b c 和三角形a b d 可以认为是局部d e l a u n a y 的 为了提高精度，对l a w s o n s 算法进行改进，得出d t _ i n s e r t 0 算法。 算法3 4d t _ i n s e r t ( x ，t = ( v ，e ，f ) ) a 找出f 中包含x 的三角形t b ，1 - 3 f i i p ( x , 力 c 创建队列q ，包含所有包含x 的f 中的三角形( a ，b ，x ) 中x 的对边e = ( a ， b ) d ，w h i l eq 非空d 0 e 从q 中移除e = ( a ，b ) f _ 找出与三角形t l = ( a ，b ，x ) 相对的三角形t 2 = ( a ，b ，c ) g 。 i f h 的外接圆包含c ，t h e n h 2 - 2 f l i p ( e ，t ) i 若( a ，c ) ，( b ，c ) 为内边，则将它们插入q 中 j e n d i f k e n d w h i l e 应用l a w s o n s 算法来改进删除点的办法，得算法3 5 。 算法3 5d t _ d e l e t e ( x ，t = ( v ，e ，f ) ) ( 从d e l a u n a y 三角剖分t 中移除点x 牛) a 创建队列q ，包含共用x 的所有边 e 1 ，。，c k 基于d e l a u n a y 三角剖分的曲面拟合 ( 若有边是不可翻转的，则将它的p o w e r 距离设为无穷) b f o r i = lt o k 3 c e = ( 墨a ) = e x t r a c t m i n ( q ) d 令t l = ( x ，a ，b ) ，t 2 = ( x ，毛c ) 为共用边e 的两个三角形 e 2 - 2 f l i p ( e ，t ) 更新q 中( x ，b ) ，( bc ) 的距离 g e n d - f o r h 令t 为与x 相邻三点组成的三角形 i 3 1 f l i p ( x ，t ，t ) 由于本算法应用了优先队列，该算法的时问复杂度为o ( k l o g k ) 。尽管该算法 很有效，却不是最优的。 在一些具体的应用中，是想除去d e l a u n a y 三角剖分中的一点而仍旧保持 d e l a u n a y 性质。如果只是局部的变动，下面引入的方法就很有效。 令线段工( f ) 满足x ( o ) = ，x ( 1 ) = 工，三( f ) = o ( f ) ，工( f ) 工( f ) ) ，其中为起始点，x 为终止点，目的是当点从x ( 0 ) 变动到石( 1 ) 时，使工处的边不论是要被删除还是加 入，都在一个队列里。当；( f ) 沿；( f ) = o ( f ) ，x o ) z ( f ) ) 运动时，优先队列的指标是 建立在能做成映象边的基础上的。 对于上述的2 2 算法下面的定理给出了理论保证。 定理3 1 对于同一样本点集的任意两个最大的三角剖分可以经过一系列的 2 2 拓扑翻转相互转换。 说明：选定一种平面插值算法，给出两种三角剖分互、五的直线差值，满足 外表面的坐标相同。r l 专正的翻转：用l a w s o n 算法，将石翻转成d e l a u n a y 三角 剖分，将五中的点与互中的点一一对应。对于石中的每一内点，移到在互中与其 相对应的位置上，但要保持一直是d e l a u n a y 三角剖分。对互应用l a w s o n 算法时， 逆向应用上述翻转步骤。于是可得，对于同一样本点集的任意两个最大的三角剖 分z 、e ，它们可以经过2 2 的对等翻转相互转换。 3 0 基于d e l a u n a y 三角剖分的曲面拟合 3 2 2 三维情况 先考察r 3 中的v o r o n o i 图。给定空间中含疗个点的样本点集s ，它的v o r o n o i 图分三维空间为疗个区域，每个区域内含一点x s 。该v o r o n o i 图的对偶就是我 们想要的d e l a u n a y 四面体化。 盏令盏令 基于d e l a u n a y 三角剖分的曲面拟合 e 图3 - 6 几何不可翻转与拓扑不可翻转 下面给出一种特殊情况：若三角剖分满足： ( 1 ) 每条边e 为4 个或更多个四面体共用； ( 2 ) 对每个面厂的链接的两个端点形成的边e 与厂不相交， 则该三角剖分只能进行l 一4 几何对等翻转。 其中，( 1 ) 为拓扑条件，( 2 ) 为几何条件。若样本点集的三角剖分中有许多边满足 条件( 1 ) ，那么也就没有什么意义了。 2 3 - 2 9 3 3 算例 研究三角剖分，其中点代表三角剖分，边代表几何对等翻转。前面已经提 到，在三维情况下，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 四面体化中的四面体的个数不是唯一的。图3 - 7 给出了一个三维情况下的例子。 3 4 小结与展望 本节主要给出了对等翻转方法的基本概念和通常的计算方法，并在最后指 出了对等翻转方法在d e l a u n a y 三角剖分中的应用，这说明对等翻转方法作为一 个强有力的工具，已经成为d e l a t m a y 中的重要组成部分。可以预见，今后如何 将对等翻转方法更加完善化，是很有挑战性的。 3 2 基于d e l a u n a y 三角剖分的曲面拟合 。 _ 图3 7 多面体的四面体剖分 3 3 基于d e l a t m a y 三角剖分的曲面拟合 第四章三角剖分的形成与优化 第一章中就已经介绍过，三角剖分方法是当前c a g d 领域中最为流行的一 种曲面逼近的方法，它具有简单、直观、易实现的特点，因而得到了广泛应 用，很多复杂的曲面都能用该方法设计得出。本章是在一般三角剖分的基础上， 通过一系列的优化方法，得到d e l a u n a y 三角剖分，并且通过一个实际的例子来 说明这一问题。 另外，本章的最后还指出，d e l a u n a y 三角剖分的方法不仅仅能用于曲面的 逼近，还能被扩展应用到其它领域。 4 1 卷包算法求样本点集的凸包 4 1 1 凸包的基本概念 在计算几何中，凸包具有广泛的应用，是最普遍、最基本的一种结构，不仅 有许多特殊性质，而且还能用来构造许多其它的几何形状。实际应用中的多数问 题可以归结为求凸包问题。下面给出凸包的基本概念，并以二维为例给出具体的 算例。 定义4 1 平面点集s 的凸壳c h ( s ) 是包含s 的最小凸集。 点集s 的凸壳是由s 中若干个点的所有凸组合组成的集合。对于d 维中的点 集s ，c h ( s ) 是s 的d + 1 ( 或者更少) 个点的所有凸组合的集合，因此二维点集 的凸壳至多是3 个点的所有凸组合的集合。每个凸组合的集合确定一个三角形， 这样，平面点集s 的凸壳是有s 中的点确定的所有三角形的并。 点集s 的凸壳是包含s 的所有凸集的交，或者c h ( s ) 是包含s 的所有半空间 的交。二维中的半空间是半平面，它是位于一个封闭的，并且包括内部所有点的 区域，但在计算几何中，凸壳也理解为上述的域及其边界。 定义4 2 平面点集s 的凸壳边界b c h ( s ) 是一凸多边形，其顶点为s 中的点。 b c h ( s ) 是包围s 的最小凸多边形p ，即不存在多边形p ，使得p 3 p 。3s 成 立。 b c h ( s ) 是具有最小面积，并且封闭的凸多边形尸，或者是有最小周长，并 且封闭的凸多边形p 。 基于d e l a u n a y 三角剖分的曲面拟合 由定义3 2 和定义3 3 可知，凸壳边界或者凸壳必包含凸集。可以这样来想 象平面点集的凸壳，用一根橡皮圈套住s 中的所有点，当橡皮圈收缩时形成的图 形就代表了凸壳的图形。 平面点集s 的凸壳或者凸壳边界是一凸多边形；反之，一个凸多边形必是一 个平面点集的凸壳或凸壳边界。 卷包法的基本思想如下：首先过y 坐标最小的点a 画一条水平直线，显然 该点是凸壳的一个顶点，然后，绕p l 按逆时针方向旋转，碰到s 中的第二个点p ： 时，直线，改绕玖按逆时针方向旋转而在扔与p ：之间留下一条线段，该线段为 凸壳的一条边。继续旋转下去，直到最后直线，旋转3 6 0 。回到p ，便得到所要求 的凸壳。 直线，绕点p ，的旋转是通过以下方法实现的：首先连接p ，于非凸壳顶点 p ，j = f + 1 ，拧，得到线段见p ，然后求这些线段与，( 即p i 一，p i ) 的夹角，组 成最小夹角的另一端点p 即凸壳顶点。【2 z j 4 1 2 凸包的算法 算法4 1 ： 输入e 2 平面上疗个点p l ，p 。的坐标( 五，咒) ，i = l ，胛。 输出点集 p l ，p 。 的凸壳顶点。 ( i ) 计算乃，只的最小值，其对应的点设为p l ； ( i i ) 从a 向右引一条水平射线，记为么； ( i i i ) 计算而与的夹角a n g l e ( p i p ；，) 及n i ；l n 础( 丽，乞) ，i = 2 ，刀，设为 q 。，。是角o f i 的一条边，q 的另一条边的端点是凸壳顶点，记为p ：； ( i v ) j 卜1 ，k 卜3 ，m 卜2 ； ( v ) 以万瓦代替p , - i p j ( p 。p 。= l p 。) ，计算万忑与万鬲( 扛七，以) 的夹角 口n g l e ( p j + l p i ，p j p j + i ) 及m i n a n g l e ( p j + s p i ，p j p j + 1 ) ，设为。的另一条边的端点 即凸壳顶点，记为p k ； ( v i ) j4 - j + l ，k 卜k + l ，柳卜m + l ，g o t os 5 ，直至的另一条边的端点为p l ； ( v j i ) 输出凸壳顶点a ，p 。 算法中找到的凸壳的顶点p 。的编号k ，可能与点集中该点的编号不一致， 比如p ，此时只要交换两点的编号即可。 算法