（计算数学专业论文）基于海量散乱数据点的曲面重建问题研究.pdf

大连理工大学硕士学位论文 摘要 随着激光测距扫描等三维数据获取硬件技术的日趋完善，人们可以得到精度和密度 都越来越高的物体表面三维数据，利用物体表面三维数据来建立真实的物体数字模型， 也就是反向工程成为近年来国际图形学界的一种发展趋势，曲面重构作为这种建模方法 的一个重要研究课题也得到了广泛的探讨和研究，成为国际上的研究热点之一。 测量密度的提高，虽然有利于模型细节的刻画，但同时也为进一步操作带来了困 难。直接针对大规模点云重建曲面，就目前的计算速度来说还是不现实的。所以在重建 曲面之前进行适当的数据压缩是必要的。针对大规模数据点云的数据压缩，目前已有一 些算法，如文献 2 5 中提出的依据采样点的局部特征尺度对原始采样集进行不均匀降采 样算法，文献 2 6 2 7 1 中提出的针对生成n u r b s 曲面的网格抽样算法等。本文的工作就 是在总结了近年来十几种各具特色的曲面重建算法的基础上，提出了一种新的数据均匀 压缩算法，并根据压缩点的特征，重建网格曲面。本文的内容是这样安排的： 第一章：c a g d ( c o m p u t e r a i d e dg e o m e t r i c d e s i g n ) 的基础背景知识。 第二章：计算几何中相关三角剖分的算法基础。 第三章：国内外基于海量散乱数据点进行曲面重建的经典算法综述。 第四章：基于海量散乱数据点的数据压缩及生成三角网格的曲面重建新方法。 关键词：计算机辅助几何设计；反向工程；曲面重建；数据压缩：拓扑 基于海量散乱数据点的曲面重建阅题研究 r e s e a r c ho ns u r f a c er e c o n s t r u c t i o nf r o m3 d l a r g e s c a l es c a t t e r e d p o i n t s a b s t r a c t i nt h ew a k e o f i m p r o v e m e n t o f h a r d w a r e t e c h n i q u e o f 3 dd a t a s e tc a p t u r i n gs u c ha sl a s e r - r a n g i n g s c a n n i n gt e c h n i q u e a n ds oo n , p e o p l em a yo b t a i ns u r p e r f m a ld a t a s e to f o b j e c t 州t h m o r ea n dm o r et a l l e rp r e c i s i o na n d d e n s i t y t od e p e n d o n u t i l i z i l a gt h e d a t a s e to nt h eg r o u n dt o e s t a b l i s ht h er e a lo b j e c t sn u m e r a lm o d e l ，a l s oi st h er e v e r s ee n g i n e e r i n g ，b e c o m e st h e p a s tf e w y e a r s o n ek i n do f d e v e l o p m e n t t e n d e n c yo f i n t e m a f i o n a lf i g u r ee d u c a t i o n a lc i r c l e s s u r f a c e r e c o n s t r u c t i o na s oo b t a i n s w i d e - r a n g i n gi n q u i r y a n dr e s e a r c ha so n e s i g n i f i c a n tr e s e a r c h t a s ko f t h ek i n do f m o d e l b m l d i n gm e a n s ，a n db e c o m e s o n eo f t h er e s e a r c h h e a t p o i n t i nt h ei n t e m a f i o n m e a s u r e m e n tt h i c k n e s sr a i s i n g ，a l t h o u g hi sf a w ) ro f p o r t r a y i n go f p a t t e r n p a r t i c u l a r s ，y e t a l s ob r i n g sh a r d s h i pf o rm a n i p u l a t i n gi nt h en e x t s t e p d i r e c t l yb e i n g a i m e da tt h e l a r g es c a l e p o i n t c l o u dt or e c o n s t r u c tt h e s u r f a c e , i t i sn o ta c t u a la sf a ra st h e c o m p u t a t i o ns p e e d a it h e m o m e m b e f o r e r e c o n s t r u c t i n gs u r f a c et oc a r r y o nt h e p r o p e rc o m p r e s s i o n o f d a t a s e ti s i n d i s p e n s a b l e b e i n g a i m e d a t t h e d a t a c o m p r e s s i o no f e 砒e n s n e d a t a p o i n tc l o u d , t h e r e a r cs o m e a l g o r i t h m sa tt h em o m e n t 1 1 1 c a s et h e p e r s o n w h o p r o p o s e s a s a m p l i n ga l g o r i t h mi nt h e l i t e r a t u r e 2 5 ，w h i c hi nt h el i g h to f p a r t f e a t u r e y a r d ；m c k ，t h es a m p l i n gs p o ti sn o te v e n l y c o m p r e s s e d ，g r i ds a m p l i n ga l g o r i t h mt h a ti sa i m e d a tg e n e r a t i n gn u r b s c a m b e r , i sp r o p o s e di n t h el i t e r a t u r e 2 6 】【2 7 t h ew o r ko f t h e o r i g i n a li sl i v i n g t os l a r nu pt h e p a s tf e wy e a r s t e n s k i n d so f s u r f a c er e c o n s t r u c t i o n a l g o r i t h m t h a te a c hh a v ei t sc h a r a c t e r i s t i cp a r to nt h e b a s e , p r o p e s i n g o n ek i n do f f r e s hd a t a e v e n l yc o m p r e s s i o na l g o r i t h m , m o r e o v e r o nt h eb a s i so f c o m p r e s s i o nd a t a s e tf e a t u r e ，r e c o n s t r u c t 舒dc a m b e r t h e s u b s t a n c eo f t h e o r i g i n a li sf i x e du p l i k e t h j s ： c h a p t e r o n e ：t h eb a c k g r o u n d o f c o m p u t e r a i d e dg e o m e t r i c d e s i g n ； c h a p t e r t w o ：t h e a 1 9 0 r i t h i nb a s i so f t r i a n g u a t i o ni nc o m p u t e rg e o m e t r y ； c h a p t e rt h r e e ：t h ec l a s s i ca l g o r i t h m sb o t h i n t e r n a t i o n a la n dc i v i lo ns u r f a c er e c o n s t r u c t i o n f r o m l a r g es c a l es c a t t e r r e dp o i n t si ss u m l a t r i z e d ； c h a p t e rf o u r ：p r o p o s e an e w a l g o r i t h m o ns u r f a c er e c o n s t r u c t i o nf r o m3 ds c a t t e r e dp o i n t s k e yw o r d s c a g d ；r e v e r s ee n g i n e e r i n g ；s u r f a c er e c o n s t r u c t i o n ；d a t ao p p r e s s i o n ；t o p o l o g y 独仓i 性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工火学或其他单位的学位或证书所使用过的材料。与我同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：日期： 大连理工大学硕士学位论文 1c a g d 的基础背景知识 1 1 c a g d 的历史与现状 计算机辅助几何设计( c o m p u t e r a i d e dg e a m e t r i cd e s i g n ，简称c a g d ) 这一术语 1 9 7 4 年由巴恩希尔( b a m h i l l ) 与里森费尔德( 硒s e n f e l d ) 在美国犹他( u t a h ) 大学的 一次国际会议上提出，以描述计算机辅助设计( c o m p u t e r a i d e d d e s i g n ) 的更多的数学 方面，为此加上“几何”的修饰词。在当时，其含义包括曲线、曲面和实体的表示，及 其在实时显示条件下的设计，也扩展到其他方面，例如四维曲面的表示与显示。自此以 后，计算机辅助几何设计开始以一门独立的学科出现。 c a g d 主要研究在计算机图象系统的环境下对萄面信息的表示、逼近、分析和综 合。它起源于飞机、船舶的外形放样( l o f t i n g ) 工艺，由c o o n s ( 1 9 1 2 1 9 7 9 ) 、b e z i e r ( 1 9 1 0 1 9 9 9 ) 等大师于2 0 世纪6 0 年代奠定理论基础。典型的曲面表示，2 0 世纪6 0 年代是c o o n s 技术和b e z i e r 技术，2 0 世纪7 0 年代是b 样条技术，2 0 世纪8 0 年代是有 理b 样条技术。现在，曲面表示和造型已经形成了以非均匀有理b 样条( 爪b s ： n o n - - u n i f o n mr a t i o n a lb s p l i n e ) 、参数化特征设计( p a v a m e t e r i z e da n dc h a r a c t e r i s t i c d e s i g n ) 和隐式代数曲面表示( i m p l i c i t g e b r a i cs u r f a c er e p r e s e n t a t i o n ) 这两类方法为主 体，以插值( i n t e r p o l a t i o n ) 、拟合( f i t t i n g ) 、逼近( a p p r o x i m a t i o n ) 这三种手段为骨架 的几何理论体系。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着几何设计 对象向着多样性、特殊性、和拓扑结构复杂性靠拢这种趋势的日益明显，随着图形工业 和制造工业迈向一体化、信息化和网络化步伐的目益加快，随着激光测距扫描等三维数 据采样技术和硬件设备的日益完善c a g d 在近年来得到了长足的发展。这主要表现在 研究领域的急剧扩展和表示方法的开拓创新。 从研究领域来看，c a g d 技术已从传统的研究曲面表示、曲面求交和曲面拼接，扩 充到曲面变形、曲面重建、曲面简化、曲面转换和曲面位差：从表示方法来看，以网格 细分( s u b d i v i s i o n ) 为特征的离散造型与传统的连续造型相比，大有后来居上的鲥新之 势。而且。这手孛曲面造型方法在生动逼真灼特征动画和雕塑曲面的设计加工中如鱼得 水，得到了高度的运用。 1 2 c a g d 的研究对象与核心问题 计算机辅助几何设计是随着航空、汽车等现代工业的发展与计算机的出现而产生与 发展起来的- - f 3 新兴学科。尽管研究对象扩展到四维曲面的表示与显示等，但其主要研 究对象仍是工业产品的几何形状。工业产品的形状大致上可分为两类：一类是仅由初等 基于海量散乱数据点的曲砸重建问题研究 解析曲面( 例如平面、圆柱面、圆锥面、球面、圆环面等) 组成，大多数机械零件属于 这一类，可以用画法几何与机械制图的方法完全清楚表达和传递所包含的全部形状信 息；第二类是不能由初等解析曲面组成，而以复杂方式自由变化的曲线曲面即所谓自由 型曲线曲面组成，例如飞机、汽车、船舶的外形零件。显然，后类形状单纯用画法几 何与机械制图是不能表达清楚的。 在制造飞机和船舶的工厂里，传统上采用模线样板法表示和传递自由型曲线曲面的 形状。模线员与绘图员用均匀的带弹性的细木条、有机玻璃条或金属条通过一系列点绘 制所需要的曲线即模线，依此制成样板作为生产和检验的依据。在曲面上没有模线控制 的部分取成光滑过渡。这种采用模拟量传递信息的设计制造方法所表示与传递的几何形 状因人而异，要求设计与制造人员付出繁重的体力劳动，设计制造周期长，制造精度 低，互换协调性差，不能适应现代航空、汽车等工业的发展。人们一直在寻求用数学方 法唯一地定义自由型曲线曲面地形状，将形状信息从模拟量改变为数值量。由此而来的 大量计算工作手工无法完成，只能由计算机来完成。随着计算机的出现，采用数学方法 定义自由型曲线曲面才达到实际应用的地步。这导致了本学学科的产生与发展。依据定 义形状的几何信息，应用本学科所提供的方法，就可建立相应的曲线曲面方程即数学模 型，并通过在计算机上执行计算和处理程序，计算出曲线曲面上大量的点及其它信息。 其间，通过分析与综合就可了解所定义形状具有的局部和整体的几何特征，这里实时显 示与交互修改工作几乎同步进行。形状的几何定义所有的后置处理( 如数控加工、物性 计算、有限元分析等) 提供了必要的先决条件。 在形状信息的计算机表示、分析与综合中，核心的问题是计算机表示，即要找到既 适合计算机处理且有效的满足形状表示与几何设计要求，又便于形状信息传递和产品数 据交换的形状描述的数学方法。 关于实体造型的理论的发展落后于曲线曲面，虽然近几年来已取得很大进展并进入 实际应用，但仍不及曲线曲面理论那样成熟。 1 3 反向工程与曲面造型技术 反向工程( r e v e r s ee n g i n e e r i n g ) ，是国外近几年随着c a d c a m c a e ( 计算机辅 助设计制造工程) 的迅速普及而发展起来的崭新的信息科学领域。c a d c a m c a e 技术 使人们能够借助计算机工具，十分方便地通过数字模型生成实体模型。然而，实际工程 中经常需要将物理实体转化为数字模型，以便用计算机进行处理。实现这一过程的科学 方法，就是所谓的反向工程。显而易见，反向工程具有极大的普遍意义和实用性。它与 c a d c a m c a e 相辅相成，互为补充，共同构成一个强有力的工具，使得人们可以在实体 模型与数字模型之间、物理实体与虚拟现实之间自由地往来。 2 人连理工大学硕上学位论文 反向工程在娱乐、工业设计和加工、医学、仿真与虚拟现实及网络等领域具有广 泛的应用。在电影、游戏、动画、电视等娱乐产品中三维光滑模型的创建，传统的方 法是用取样器将艺术家制作的小模型一点点地输入到计算机中，既费时又赞力，反向 工程可提供一个便捷而有效的工具。与娱乐业三维光滑模型的创建过程类似，在玩 具、汽车和飞机零部件等工业产品的制造过程中，现有的c a d c a m 软件也不能很好地 解决这些实体的数字模型的建立问题，同样，反向工程是处理这些问题的强有力的工 具。在医学领域，经常需要用c t 或磁共振的切片图像建立三维数字模型，这密切依赖 于反向工程。在网络领域，反向工程也将发挥重要的作用。随着立体电视、电子商务 等科技的发展和产业的需要，三维数据传输必将成为网络技术的重要研究课题，反向 工程魁不u j 缺少的工具。此外，在仿真和虚拟现实的领域中也能遇到大盈的反向工程 问题。从广义而言，二十世纪九十年代末提出的“数字地球”计划，本身就是个规 模巨大的反向工程。 反向工程有两个主要的研究内容：一是实物模型表面数据获取技术；二是曲面重 构技术。数据获取技术的发展为我们处理复杂物体模型提供了可能。例如，在医学图 像可视化中常用c t 切片来得到人体内脏器官表面的三维数据。采样工具获取的实体表 面数据通常是稠密的点集( 称为点云) ，曲面重构技术就是根据获取的“点云”来恢 复原始j i i i 而的几何模型。 以点云或者多边形模型为基础来进行实体表面的曲面重构，必须考虑以下两个问 题：一是曲面数据散乱而且实体表面形状复杂；二是物体表面通常难以用一片曲面构 成。 目前，反向工程的处理过程可以大致分为以下几个主要步骤： 1 提取样本点。通常的方法是用三维扫描仪( 3 ds c a n n e r ) 将样本点的三维坐标提取 到计算机中形成点云( p o i n tc l o u d ) 。点云是一种形象蜕法，说明样本点是海最 的，像一团云彩一样稠密。显然这种数据形式既不便于保存又不便于处理，并且足 无序的，即点与点之间的邻接关系并不清楚；如图1 1 所示。 2 由点云形成多面体模型( p o l y g o nm o d e l ) 。该过程的主要目的是整序( 建立点云 的空间结构) 、初步参数化和数据压缩：如图1 2 所示。 3 形成( 空间) 四边形剖分( 四边形的边不必是直线) ，即将多面体模型分解为满足 一定条件的( 空问) 四边形的并，进一步将其适当参数化；如图1 3 所示。 4 在第3 步的基础上形成n u r b s ( 非均匀有理b 样条) 曲面模型。如图1 4 所示。 - 3 一 蝽丁海剞：敞乱数“j ? 、i 的曲i f 巫建问题研究 图1 1 点云模型 f i g u r e1 1p o i n tc l o u dm o d e 图1 2 多边形模型 f i g u r e1 2p o l y g o n a lm o d e l 图1 3 四边形模型 图1 4 n u r b s 模型 f i g u r e1 3q u a d a n g u l a t i o nm o d e l f i g u r e1 4n u r b sm o d e 使用上述步骤完成反向工程的完整过程如图1 3 5 所示 4 一 大连理工大学硕士学位论文 图1 3 5 反向工程的一种实现过程 我国浙江大学、中国科技大学、北京航空航天大学、吉林大学、大连理工大学等单 位对多元样条、b e z i e r 曲面、隐式代数曲面、单个n u r b s 曲面等进行了多年富有成果 的研究：清华大学、上海科技大学、广州军医大学等单位在医学图像重建方面做了许多 工作。 伴随着计算机图形技术的发展，几何造型技术不仅可应用于原有的外形设计， 还广泛应用于机械制造、医学可视化、虚拟场景生成、铁路勘察设计与环境工程、 地形地貌描述、矿藏储量图示、气象、影视等众多领域。几何造型技术的发展促进 了它的应用领域的扩大，反过来应用领域的扩大又丰富了几何的表示形式，促进了 造型手段和造型方法的发展。在c a d c a g 中，曲面造型是一个有着较长历史的领 域，6 0 年代初期就已经诞生。1 9 6 3 年f u g e r s o n 1 提出将曲线曲面表示为参数向量 函数形式，并引入参数三次曲线，构造了组合曲线和由四个角点的位置矢量及两个 方向的切矢定义的f u g e r s o n 双三次曲面片。在此之前曲线曲面都是采用普通的函数 表示形式y = ，( x ) 和= = s ( x ，y ) 或它们的隐式方程表示形式。1 9 6 4 年，c o o n s 2 3 发 表了一个更具一般性的曲面描述方法，即一种由四条边界曲线确定的参数曲面积 c o o n s 曲面片，从而使分片表示完整曲面成为可能。但这两种曲面都存在形状控制 和光滑拼接问题。s c h o e n b e r g 利用样条函数成功解决了曲面片之间的拼接问题，并 解决了插值问题。但插值样条曲线曲面的自由度较少，所以难以用于自由型曲线曲 面的设计。b 6 z i e r 4 于1 9 7 1 年发表的由控制多边形定义曲线的方法，并将其成功的 用在自由型曲线曲面设计系统u n i s u r f 中。后来f o r r e s t 5 对最初的b 6 z i e r 曲线 形式作了从新处理，得到了当前常用的基于控制顶点b e r n s t e i n 基表示的b 4 z i e r 曲线曲面的形式。 b 6 z i e r 方法是一种由控制多边形( 网格) 定义曲线曲面的方法，从几何变换的角度来 说，即是把b z i e r 控制网格变换为b 6 五e r 曲线曲面，是一种映射关系这种曲线曲面具 有一系列如几何与仿射不变性、凸包性、保凸性、对称性、端点插值性等优良性质：且 具有如d ec a s t e l j a u 求值、离散、升阶、插值、包络生成算法等简单易用的计算方法， 很好地解决了整体形状控制问题b 4 z i e r 方法仍存在拼接问题和局部修改问题 b 4 z i e r 曲线的优点在于，曲线曲面的形状的改变只需简单的移动控制顶点就可 实现，因而具有良好的交互性。在这个基础上人们又陆续提出三角域上的张量积曲 面和b e r n s t e i n 曲面( 即b b 曲面) 。 b 6 z i e r 曲线曲面的不足之处在于他缺少局部性，而且在处理曲面片之间的光滑 拼接方面也存在困难。曲线上任一点都与多边形的所有顶点相关因此对控制多边形 的任何修改都会影响到曲线的整体形状，7 0 年代初期d eb r 6 】和c o x 7 分别独立 提出了b 样条的d eb o o r - c o x 递推公式，使b 样条曲线曲面得以广泛的应用。1 9 7 4 年 g o r d o n 和r i e s e n f e l d 首次将b 样条理论应用于外形设计，较好的克服了b z i e f 曲 5 一 基于海量散乱数据点的曲面重建问题研究 线曲面在局部控制方面的不足。但是上述方法不能精确表示圆锥截面和球面椭球面 等初等解析曲面，为此v e r s p r i l l e 于1 9 7 5 年提出；阿理b 样条方法来克服上述缺陷。 有理b 6 z i e r 曲线曲面不但能表示自由曲线、曲面，而且能精确表示圆锥曲线、二 次曲面与旋转曲面，因而获得广泛的应用 8 ，9 ，1 0 。最后在p i g e l 和t i l l e r 等许多学 者的努力下，在8 0 年代后期形成了丰富的非均匀有理b 样条( n o n - u “i f o r m r a i o n a lb s p l i n e 缩写为n u r b s ) 1 1 ，1 2 的一整套理论和方法，因为它在外形表示 方面的强大功能与潜力，n u r b s 已被作为工业产品数据交换的s t e p 标准，也被作 为描述工业产品几何形状的唯一数学方法。把有理和非有理b 6 z i e r 曲线和b 样条曲 线曲面及圆锥曲线和初等解析曲面统一在一种表示之中，最终使n u r b s 成为 c a d c a m 行业的工业标准。 在数学和计算机科学中，通常也用隐函数来定义几何物体。不等式厂( x ，儿z ) 0 描述了空间中的半空间( 即实体) ，等式厂( x ，y ，z ) = 0 可定义该半空间的边界( 即隐 式曲面) ，这种曲面表示方法在几何造型和图形学中也得到了诸多的应用。参数化 表示具有许多优点，如计算曲线曲面的几何量较简单，曲线曲面的显示方便，具有 离散等优良c 陛质。然而，在另外一些几何操作，如判断一个点是否在益线或曲面上 以及在那一侧时，参数化表示又极为不便。与之相反，隐式化表示给这些操作带来 了极大的方便。同时，隐式化表示在曲线曲面求交方面也有极其重要的应用。因 此，在c a g d 中，也越来越多的使用曲线曲面的隐式化表示。 为了解决任意拓扑上的曲面造型，人们提出并发展了细分曲面( s u b d i v i s i o n s u r f a c e ) 造型方法。细分曲面是一类采用组成曲面的多边形网格点、线、面及其拓 扑信息完整地描述的曲面，这个多边形网格可以从手工模型上输入，也可以从激光 扫描输入。他与连续函数所描述的曲面再方法和数据结构上有着本质的区别。其基 本方法是：从初始多面体网格开始，按某种规则，递归的计算新网格的每个顶点， 这些顶点都是原网格上相邻的几个顶点的加权平均。随着细分的不断进行，控制网 格就被逐渐磨光。在一定条件下( 一定的细分规则) 下，细分无穷多次之后多边形 网格将收敛到一张光滑曲面。细分曲面的最大优点就是算法简单，几乎可以描述任 意复杂曲面，显著地压缩了设计和建立一个原始模型的时间。而且，这种曲面造型 方法在生动逼真的特征动画和雕塑曲面的设计加】：中如鱼得水，得到了高度运用。 人们在发展了曲线曲面的多种表现形式的同时也创造出了曲线曲面的各种构造 技术和方法，包括变形曲面构造技术、散乱点拟合造型技术、蒙皮( s k i n n i n g ) 造 型技术、广义s w e e p i n g 造型技术、基于变分原理的造型技术以及分形造型技术等许 多方法。随着应用领域的扩大和对造型质量要求的提高，人们还是不断地发展新的 造型方法。 随着计算机图形显示对于真实性、实时胜和交互性要求的日益增强，随着集合设计 对象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的日益明显，随着图形工业和制 6 大连理： 大学硕士学位论文 造工业迈向一体化、集成化和网络化步伐的日益加快，随着激光测距扫描等三位数据采 样技术和硬件设备的日益完善，曲面造型在近几年来得到了长足的发展。 一7 基于海量散乱数据点的曲面重建问题研究 2 计算几何中的相关算法 2 1 散乱数据的三角剖分 散乱数据的三角剖分是构造散乱数据插值曲面时必不可少的前置处理三角剖分可 分为对三维散乱数据投影域的剖分和在空间直接剖分这两种类型，散乱数据的投影域包 括平面域和球面域直接三角剖分法研究如何直接将三维散乱数据点在空间中连接成一 个最优的三角网格 2 1 1 与三角剖分有关的若干定义 先给出与三角剖分有关的一些基本概念 ( 1 )域分割 给定平面上( 或空间中) n 个不相重的散乱数据点，对每个散乱点构造一个域，使该 域内的任一点离此散乱点比离其他散乱点更近，这种域分割称为d i r i c h l e t 域分割，又称 为v o r o n o i 图，由定义可知，域边界是连接两相邻散乱点的直线的垂直平分线( 或面) ( 2 ) d c l a u n a y 三角化 对平面上( 或空间中) 的散乱数据点进行域分割后，将具有公共域边界的散乱点对 相连形成的三角剖分称为d e l a u n a y 三角剖分，如图2 1 1 所示，l a w s o n 曾给出一个1 维 d e l a t m a y 三角剖分的定义： 对于给定的一组散乱数据点，可获得无限种不同的三角剖分，其中d e l a u n a y 三角 剖分为最优，二维的d e l a u n a y 三角剖分由满足最小内角最大准则的三角形组成，三维 的d e l a t m a y 剖分则由满足球面准则的四面体组成。 图2 1 1d i 工i c h l e t 域分割( * 咀线) 和d e l 龇a y 三角剞分( 细缝) f i g u r e 2 1 1 d i ，r i e h l e _ tp a r t i t i o n dd e l a t m a yt r i a n g u l a t i o n ( 3 )优化 对三角网格进行优化，就是要使三角网格整体上尽量均匀，避免出现狭长三角形 亦即获得d e l a u n a y 三角化 一8 大连- n _ - e 大学硕士学位论文 2 1 2 三角剖分优化准则 在三角剖分过程中，我们往往用一种比较简单的方法构造散乱数据点的初始三角剖 分然后对其进行优化以获得d d a u n a y 三角剖分优化的方法和效果取决于所采用的优化 准则常用的优化准则有t h i e s s e n 区域准则，最小内角最大准则，圆准则，球面准则 a b n 准 则，p l c 准则，多面体表面积最小准则，多面体体积最大准则及空间光顺准则等前三者为平 面三角剖分优化准则，s i b s o n 证明了这三个准则的等价性，并指出符合这三个准则的三角 剖分只有一个，即d e l a t m a y 三角化，其余准则可视为空间三角网格的优化准则 ( 1 ) 最小内角最大准则 对一个严格凸的四边形进行三角化时，有两种选择最小内角最大准则就是保证对 角线两侧两个三角形中的最小内角为：最大，如图2 1 2 和图2 1 3 所示： 护 圈2 1 s 2 最小内角最大准则 甄弘”2 1 2s m j , i l e s t 删c 咄 图2 1 3 圆准剜 f i g u r e 一2 i 、3e i r c l n 岫 ( 2 )圆准则和球面准则 严格凸四边形中的三个顶点确定一圆，如果第四个顶点落在圆内，则将第四个顶点 与其相对的顶点相连，否则将另两个顶点相连，称为圆准则，如上图所示，球面准则可表 述为：对于两共面的四面体a 和b ，若a 的不属于b 的顶点位于b 的外接球内，则需要 对两四面体的拓扑关系进行变换；若位于b 的外接球外，则四面体不作变换，保持其拓 扑关系不变 ( 3 )a b n 准则( a n g l c s b e t w e e n n o r r n a l s ) 设t 是散乱数据点集p ，( i = l ，2 n ) 的三角剖分定义每一条内边e 的权值c ( e ) 为与 之相邻的两个三角面法矢的夹角、若两三角面处于同一平面上，则c ( e ) = o 对一个严格凸 的四边形三角化时，有两种选择设这两种对角线连接分别为e 和e ，则a b n 准则就是 要选择c ( e ) 和e ( e ) 中权值较小的一种三角化结果 ( 4 ) 光顺准则 对一个严格凸的四边形三角化时，有两种选择设这两种对角线连接分别为e 和 e ，c ( e ) 为连接对角线e 时，四边形四条边上三角形对的夹角中的最小值，c ( e ) 为连接对 角线e 时，四边形四条边上三角形对的夹角中的最小值，光顺准则就是要选择c ( c ) 和 c ( e ) 中数值最小的一种三角化 9 基于海量散乱数据点的曲面重建问题研究 f 5 1 优化与退化 1 ) 局部优化与全局优化 局部优化指的是对任意一个凸四边形的对角线，依据某种优化准则作交换测试后 所得到的三角剖分全局优化则指三角剖分t 中= 每一条内边上的两三角形所形成的凸 四边形都满足局部优化的三角剖分结果 2 ) 退化 当n + 1 个以上的点同处于一个i 3 维超球面时，即为退化构造平面d e l a u n a y 三角 剖分时，若四个或四个以上的散乱数据点共圆，则退化对于三维情况，当五个或五个以 上的散乱数据点位于同一球面上时，出现退化情况导致退化的共圆点或共球点称为 退化点 真正的退化情况并不多见，它不影响剖分结果但由于浮点计算误差而引起的近 似退化却有可能发生近似退化会引起优化过程中的交换测试判断发生错误，从而导 致非法的剖分结果近似退化造成的算法失败主要表现在退化点附近的散乱数据点邻 接关系记录混乱解决这一问题的方法是轻微扰动退化点对其位置作出确切判 断，e d e l s b r u r m e r 等提出了消除退化情况的s o s 扰动方法 退化也泛指散乱数据点中有重合投影点及四边形四个顶点近似共线等情况 2 2 平面和开曲面散乱数据的三角剖分 由于三维散乱数据点之间拓扑关系的复杂性，对其直接剖分的理论和方法尚不完善， 一般仍以投影域三角剖分为主，投影域分为平面域和球面域两种类型，平面域又可分为两 种情况处理： 1 )存在一个平面使三维散乱点与其上的二维投影点一一对应，此时可将三维散乱点投 影到该平面上，在二维平面上对投影点作三角剖分，再将三角剖分的结果映射回三维空 间 2 ) 不存在使三维散乱点与二维投影点一一对应的平面在此情况下涪0 分步骤如下：将三 维散乱点分割成若干部分，再将其分别投影到相对应的平面上，对各自的投影点作三角 剖分，然后将剖分结果分别映射回三维空间，最后，对分割截面两边的三角形坐合并优化 球面域用于构造封闭曲面上散乱数据点的三角剖分，其步骤如下：将散乱数据点投影 映射到球面域上，对投影点作三角剖分，再将三角剖分结果映射回三维空间 2 2 1 平面上散乱数据的三角剖分 无论在理论上还是在应用上，平面凸域内散乱数据点的三角剖分算法都已经比较成 熟不少学者对此作出了贡献：g r e e n 与s i b s o n 和b o w y e r 从d e l a u n a y 三角剖分定义出发， 提出了依据t h i e s s e n 区域准则进行优化的三角剖分方法；l a w s o n ，l e e 与s e h a c h t e r 和 - 1 0 大连n 2 5 大学硕士学位论文 c l i n e 与r c n k a 等提出的方法是：首先对散乱数据点进行三角剖分处理，以最小内角最大准 则进行优化，对散乱数据点实行预排序可大大缩短三角剖分的时间l a w s o n 和c l i n e - r e n k a 三角剖分方法在具体算法及数据结构上不尽相同，但它们的运行效率都比较高，故 获得了广泛的应用 下面根据c l i n e r e n k a 的方法给出平面凸域内散乱数据点的三角剖分算法 d原理 平面凸域内散乱数据点三角剖分方法的关键是解决从一个点能看到哪些边，即边相 对于点的可见性问题对于可见性有如下定义： 定义1 边p p ，相对于点p 。的可见性 对于平面上非共线的三个点p o ，p 1 和p2 ，当且仅当d e t ( po ，p l ，p 2 ) 0 时，称p 1 p 2 相对 于p 。可见；若仅大于号存在，则称p l p 2 相对于p 。严格可见 定义2 边界环 外边界节点按逆时针排列构成外边界环：内边界节点按顺时针排列构成内边界环 平面上散乱数据点三角剖分的基本步骤如下： 1 ) 对平面凸域内的散乱数据点进行预排序，形成顶点表 2 ) 取顶点表中的前几个点构造初始三角形，此三角形就是最初的三角网格 3 ) 从顶点表中顺序取出下一个点，找出多边形边界上能被此点见到的边，用直线段将此 点与所有可见边的端点相连 4 ) 对三角网格进行优化，得到散乱数据点的最优三角剖分，即d e l a u n a y 三角剖分 5 ) 逐次加入新点，继续上述过程直至遍历有序点集中的所有点，最后得到散乱数据点的 三角剖分 ) 优化准则 在对平面上散乱数据点的投影点所构成的三角网格进行优化时，可应用最小内角 最大准则或圆准则。 设平面上相邻两三角形的四顶点p l ，p ：，p3 和p 4 ，并且却。p 3 p ：= 口l ， l f f t p 4 p 2 = ，如图2 , 2 4 所示，p 1 ，p 2 和p 3 三点确定一个圆c 。p 。相对于此圆有三 种情况，相应的，凸四边形的对角线也：有三种选择： 1 ) 当p 。点位于圆周c 上，即口，4 - a ：= 石时，可任意选择对角线。 2 ) 当p 。点位于圆周c 内，即a + a ，) 玎时，对角线需交换。 3 ) 当p 。点位于圆周c 外，即日，+ 口，( 石时，对角线不需交换。 当p 。点位于圆周c 上或其外时，圜准则得到满足。即用圆准则对p 。，p ：，p ，p 。进 行测试结果为真；否则当p 。点位于圆周c 内时，测试结果为假。 f 冤翟品霉浆銎。 1 1 基于海量散乱数据点的曲面重建问题研究 特别需要注意以下两种情况： 1 ) 当p l ，p2 ，p 3 ，p 4 四点近似共线，即a1 “o ，口2 o 或口i 万，口2z ，z - 时，由于 浮点运算误差有可能出现判断错误。 2 ) 由于数据点是散乱分布的，可能出现近似退化。 m ) 算法步骤 1 ) 将平面凸域内的散乱数据点按字典排序方式排序，称为预排序。 2 ) 取顶点表中的头i 个数据点( 称为顶点) ，构造初始的d e l a u n a y 三角剖分t ， 其中j 是保证节点1 ，2 ”0 不是都共线的最小整数，建立各项点的邻接关系并按逆 时针方向建立边界环，如图2 2 5 ( a ) 所示。 3 ) 对k 习+ 1 j + 2 ，n ，构造1 ，2 ，k 的d e l a u n a y 三角剖分t 女。 i )由于顶点经过预排序，顶点p 必在t 。外。在边界上搜索顶点p 。和p ：， 使得按逆时针方向从p ，到p ：间的所有边界边从p 。处都是可见的。除此之 外，不再有从p 。处可见的边界边，如图2 2 5 所示 i i ) 连接p 。和p l ，p ：以及从n 到p2 按逆时针方向经过的所有边界边顶点。修 改边界环及内节点的邻接链表，如图2 2 ，5 c o ) 所示。 蛐对每一个以t 。的边为对角线并且包含顶点p ；的凸四边形，应用最小内 角最大准则( 或圆准则) 进行交换测试，优化三角网格，如图2 2 5 ( c ) 所 刁i o 3 ( a ) 栅始o e l m 苟兰最刮分 ( b ) 从4 处可见的边界迦 岛 岛 b ( c ) 加八县点后三角网格的眈化 图2z 5 平面凸域内散乱数据点的兰角刮分 f i g e22 5 t f i a n 曲h o no f p o m l si n r i a c e 1 2 1，。 翅6 大连理工大学硕士学位论文 上述步骤完成后所得的t 。即为最后的d e l a u n a y 三角剖分。 一般地，如果一组三维散乱数据点能够有效地投影到某个平面上，就可以把 空间三角剖分简化为平面问题处理。曲面较为平坦时，用这种方法处理效果比较 好，否则，投影后将明显改变相邻三角形之间的内角关系，从而影响剖分结果。 因此，c h o i 提出了直接在曲面上对散乱数据点进行三角剖分的方法。这种方法对 于散乱数据点有一定要求，而且只能直接处理开曲面上的散乱数据点。 2 2 2 曲面上散乱数据的三角剖分 设s 为一光滑曲面，p ，( ，= l ，2 r ) 为s 上的一组散乱数据点，当符合下面两个条 件时才能用基于面的方法对其进行三角剖分： 1 )存在一个三维点c ，由此可看到s 上的所有散乱数据点p ，( ，= 1 ，2 h ) 2 )可定义一个以c 为锥顶的凸锥将p ，( ，= 1 ，2 聆) 包含于其中 基于面的直接三角剖分过程如下： a )对散乱数据点作必要的预处理 b )对散乱数据点作初始三角割分 c )三角网格的优化处理，再作主剖分 d )三角网格的编辑，包括边界裁剪、轨迹生成和网格的封闭处理等 n原理 基于面的三角剖分方法的原理是：确定能看见曲面上所有散乱数据点的点c 以及c 为锥顶且包围所有散乱数据点的凸锥的轴矢量u ；将散乱数据点p ，按矢量印，与锥的轴 矢量u 之间夹角的大小排序，形成顶点表v ( ，= l ，2 胛) ：用顶点表中最初的几个顶点 构成初始三角网格瓦，得到其网格边界且l ：在顶点表中顺序取点v ，。与已形成的三角 网格z 一，的边界b 。中所有可见边构成三角形( 由于排序的原因，在已构成的三角网格 中不会包含顶点表v ，以后的顶点) ；在顶点表中顺序的取顶点构成三角形，直到顶点表 中无顶点可取为止，就完成了散乱数据点的三角剖分，但此三角网格t 不是最优的，尚 需对其进行优化，以得到d e l a u n a y 三角割分。 在基于面的三角剖分方法中，关键是确定空间中边相对于点的可见性。现给出可见 性的定义。 x 图226 f i g u r e226 1 3 基于海量散乱数据点的曲面重建问题研究 定义1 点相对于边的可见性 如图2 2 6 所示，将原点0 与边v