（计算机应用技术专业论文）三角网格模型分割及其简化应用.pdf

摘要 捅要 近年来，随着计算机技术和三维扫描技术的发展，出现的一种新的多媒体数据类型 三维几何模型。三维网格模型成为表示数字几何模型的重要手段，并且在娱乐、网 络以及制造业中得到了广泛的应用。如何重用现有的网格模型以及如何根据新的设计目 标修改现有网格模型，成为了一个重要的研究课题。网格分割由此提出，并成为近年网 格模型处理领域的热点研究课题。网格模型的分割也有着重要的应用，如形状匹配、形 状重建、网格编辑、模型简化、纹理映射、参数化等。本文围绕三角网格分割及其应用 中的一种一基于分割的简化展开研究。 首先，研究了三角网格模型的分割问题，根据分割的对象和研究目的的不同，网格 模型的分割类型主要有片面分割和部件分割两类，本文就片面分割提出一种新的方法一 基于法向量差值的区域生长，在进行种子选择中，提出了在侯选种子中选择种子的方法， 根据一种新的二面角的公式即法向量面积加权的差值进行区域生长，分割后对面积过小 的面片区域进行优化处理。 其次，研究了网格分割的一种应用一基于分割的网格模型简化，首先将模型根据区 域生长进行分割，在每个子区域中进行简化，以三角形折叠算法为基础，给出了基于离 散高斯曲率和被折叠三角形为中心的法向量差值的折叠依据和新顶点的获取方法，分割 保证了简化时可以避开特征的地方，同时也使简化的速度更快。 通过实验验证了以上算法是有效的。 关键词：数字几何处理；网格分割；区域生长聚类；种子；网格简化 a b s t r a c t 、- - 。- _ - - 。_ _ _ _ _ - - _ _ _ _ _ _ - - i _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - 。一 a b s t r a c t i nr e c e n ty e a r s ，诵t l lt h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n d3 ds c a n n i n g ，d i g i t a l g e o m e t r ym o d e lh a sb e c o m ean e wt y p eo fm u l t i m e d i a 3 dm e s hm o d e l sa l eo n eo ft h em o s t m e t h o d st or e p r e s e n td i g i t a lg e o m e t r ym o d e la n dh a v ew i d e l yu s e di nm a n yf i e l d s ，s u c ha s i n t e m e t ，e n t e r t a i n m e n ta n dm a n u f a c t u r ei n d u s t r i e s h o wt or e u s em e s hm o d e la n dm o d i f y m e s hm o d e la c c o r d i n gt on e wd e s i g ni sai m p o r t a n tf i e l d s m e s hs e g m e n t a t i o ni sp r o p o s e d a n db e c o m ei m p o r t a n to n eo fm e s hm a n i p u l a t i o n m e s hs e g m e n t a t i o ni su s e di nm a n ym e s h m a n i p u l a t i o na l g o r i t h m s ，s u c ha ss h a p em a t c h i n g ，s h a p er e b u i l d ，m e s he d i t i n g ，m e s h s i m p l i f i c a t i o n ，t e x t u r em a p ，m e s hp a r a m e t e r i z a t i o na n ds oo n t w oo ft h e s ea l g o r i t h m s ，m e s h s e g m e n t a t i o na n dm e s hs i m p l i f i c a t i o nb a s e do ns e g m e n t a t i o n ，w i l lb er e s e a r c h e di nt h ep a p e r f i r s to fa l l ，m e s hs e g m e n t a t i o ni sr e s e a r c h e d w ed i s t i n g u i s hb e t w e e nt w od i f f e r e n t p r i n c i p a lt y p e s o fm e s hs e g m e n t a t i o n t h ef i r s ti st h a tw ew i l lt e r mp a t c h - t y p e s e g m e n t a t i o n ，t h e s e c o n di sm a tw ew i l lt e r mp a r t - t y p es e g m e n t a t i o n ，a c c o r d i n gt o s e g m e n t a t i o no b j e c t i v ea n dg o a l o fs e g m e n t a t i o n an e wr e g i o n g r o w t hb a s e d o n s e g m e n t a t i o na l g o r i t h mi sp r o p o s e d t h em e t h o di so nt h eb a s i so ft h ed i f f e r e n c eo fn o r m a l a n dc h o o s i n gt h es e e d sf r o mt h ec a n d i d a t e s r e g i o ng r o w sa c c o r d i n gt oan e wf o r m u l ao ft h e d i f f e r e n c eo fn o r m a l 、析t l lt h ea r e a s m a l lp a t c hi so p t i m i z e da f t e rs e g m e n t a t i o n s e c o n d l y , m e s hs i m p l i f i c a t i o n ，b a s e do ns e g m e n t a t i o n ，i ss t u d i e d a c c o r d i n gt or e g i o n g r o w t h , s u b m e s hi ss i m p l i f i e d ，a f t e rs e g m e n t a t i o n am e t h o dt ot h ec o l l a p s eo fat r i a n g l e b a s e do nd i s c r e t eg a u s sc u r v a t u r ea n dt h ed i f f e r e n c eo fn o r m a li sg i v e n a l s oam e t h o dt og e t n e wv e r t e xi sg i v e n s i m p l i f i c a t i o nr e t a i nf e a t u r eo fm e s ha n di sf a s tb e c a u s eo fs e g m e n t a t i o n e x p e r i m e n t si l l u s t r a t et h a tt h i sa l g o r i t h m sa r ee f f e c t i v e k e y w o r d s ：d i g i t a l ；g e o m e t r yp r o c e s s i n g ；m e s hs e g m e n t a t i o n ；r e g i o ng r o w i n gc l u s t e r ；s e e d ； m e s hs i m p l i f i c a t i o n l i 独创性：声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意 签 名：盘丝霍 日 期：量翌叟睦i 因翌多 一 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定 签 名： 导师签名： 日 期：地星垒z 旦丝生 第一章绪论 第一章绪论 2 0 年代中后期以来，数字多媒体技术出现并得到了迅猛的发展，分别在7 0 年代出 现了数字声音，8 0 年代诞生了数字图像、9 0 年代又有了数字视频，这是多媒体技术的 三次重大革新。这三次革新都将人类生活带入了一种全新的状态。声音技术的发展，使 人类远距离获取信息成为现实。图像技术的发展，满足了人类对静态的细节、特征、纹 理的欣赏要求。视频技术的发展，使人类多姿多彩的生活得以再现。继数字声音、数字 图像、数字视频之后，第四代数字多媒体数字几何的时代已经到来。这是多媒体领 域里的又一次重大革新，它的出现带来了一种崭新的、真实感的三维视觉感受。数字几 何处理( d i g i t a lg e o m e t r yp r o c e s s i n g ，简称d g p ) 是研究如何利用计算机对三维几何数据 进行处理的一门学科，数字几何处理的研究，起源于工业的应用。同第四代数字多媒体 的出现相对应，一种新的多媒体数据类型三维几何模型应运而生，是继前三种数据 类型后出现的又一种重要的数字媒体载体，它将对多媒体产业以及人类生活带来根本性 的变化。 1 1 数字几何处理的研究现状 1 1 1 三维几何模型简介 计算机图形学始于计算机出现后不久，但是由于当时的硬件十分昂贵，而且缺乏易 用和廉价的基于图形的应用程序，计算机图形学的发展一直很缓慢。后来由于三维扫描 仪硬件设备的出现和更新使三维数据获取系统能很轻易的获取几何信息和表面纹理颜 色信息，随着计算机技术的发展，开发出了很多经济实用的专用图形硬件系统和技术可 供选择，计算机运算能力和存储能力的大幅度提高以及各种图形加速卡的出现使得在个 人计算机上处理三维几何数据变得很容易，加上网络技术的飞速发展使得三维几何将继 声音、图像和视频之后掀起新一轮的多媒体数据革新浪潮。 3 d 模型数据获取( 3 dm o d e l i n g ) 是d g p 工作的前提和基础，因为d g p 研究的对象 就是各种几何模型。目前，3 d 模型数据的来源有如下几个方面：( 1 ) 3 d 建模系统构造法。 这种方法比较适合于简单的几何模型。( 2 ) 三维设备数据获取方法( 3 ds c a n n i n g ) 其实质 就是通过三维扫描仪将物体表面的几何信息扫描出来，然后通过后续的数据处理，并对 整体或者部分数据进行修补，构造出一个完整的三维几何模型。这种获取方式相对比较 简单和方便，目前大部分的3 d 模型都是通过这种方式构造的。 著名的例子是s t a n d f o r d 大学的d i g i t a lm i c h e l a n g e l op r o j e c t i o n t l l ，项目通过一整套三 维扫描硬件和三维重建软件系统完成了一些大型雕塑的数字化过程。另一个著名的例子 是1 9 9 8 年荣获奥斯卡大奖的短篇动画电影、著名的美国p i x a r 公司选送的作品“g e r i s g a m e ”。 江南大学硕士学位论文 数字米开朗基罗工程 1 1 2 三维几何模型的表示 圈】例子 f i g1 - le x a m p l e s g e r i sg a t l e 三维造型技术是建立恰当的模型来表示自然界中形态丰富的三维物体的技术，根据 造型对象将造型技术分成3 类：线框模型、表面模型和实体模型。在计算机图形学中， 三维几何模型通常包含两部分内容：部分是儿何模型的形状，另咭b 分是几何模型的 外观属性，如表面材质、纹理等。 在计算机图形学中提出了很多种表示曲面的边界表示法，包括隐函数曲面、参数曲 面、细分曲面、多边形网格以及点表示方法等。所有这些表示的目的在于能够简便地生 成不同形状的物体表面。多年来，多边形绘制技术一直受到高度的重视，其他曲面表示 方法，诸如隐式曲面、n u r b s 等，最终都被转化为多边形表示以便采用常规图形绘制 硬件进行绘制。这是由于多边形网格模型具有以下优点： ( 1 ) 多边形网格模型比较易于获取，通过成熟的三维扫描技术和嘲格重建的方法， 可以获得大量的模型。其中包括无法得到原始设计图的人工模型( 如手工设计的机械模 型，手工艺品等) ，有些是自然界的物体，如动物模型、人体模型等：对于这些模型， 采用三维扫描技术是最为廉价的快速的方法。另方面，对于其他几何模型，如点云模 型、样条曲面模型、体数据模型、c a d 模型，也都能够使用非常简单的算法转化成网 格模型。因此，网格模型逐渐成为最为通用的几何模型。 ( 2 ) 理论上说，多边形网格模型可以任意精度地逼近任何复杂的曲面。随着计算 机处理能力的增强以及采用更新更好的技术，可以处理的多边形网格的规模越来越大， 精细程度越来越高，表现能力也随之越来越好。 第一章绪论 ( 3 ) 多边形网格模型只保留了物体最为重要的可视信息：表面信息。一方面这使 得它保存的信息量大大减少( 比起体数据而言) ，结构也比较简单，但是另一方面也使 得在处理变形等问题的时候遇到新的挑战。 ( 4 ) 多边形网格模型与硬件绘制的需要非常接近。实际上，现在微机中所用的显 示卡，基本上都采用基于多边形网格的绘制方式，并对这种绘制方式进行了极大的优化。 当绘制其他形式的几何模型时( 如绘制样条曲面、c s g 模型、点云) ，也一般在绘制的 时候转换成网格进行绘制。 ( 5 ) 多边形形状简单，便于计算和处理，只需存储各多边形顶点的位置坐标及属 性即可表示物体的几何信息，在计算多边形内任一可见点的光亮度时所需的信息可由 顶点的信息插值得到，这使得对多边形网格的绘制可采用硬件加速技术来实现。图形硬 件的高速发展以及对几何表面多边形化算法的深入研究进一步巩固了多边形网格在图 形绘制及造型中的地位。本文研究的对象就是多边形网格模型，由于任意多边形可| 三l 方 便地被剖分为三角形，并且现在研究和应用地最广泛的多边形网格即为三角形网格，本 文的主要针对三角形网格模型进行研究。 ( a ) 几何模型( b ) 点模犁( c ) 网格模型 图卜2 三维几何模型的表示 f i g 1 2 e x p r e s so fm o d e l 三角刚格模型是一种重要的三维物体表示方法，它用系列空间一角形逼近表示三 维物体。三角网格模型具有表示简单致，方便算法统一处理的优点住汁算机图形学 等领域有着广泛的应用，它的缺点是为了达到应用领域中需要的模型精度，通常需要刚 大量的三角形束拟合表示三维物体，从而导致庞大物体模型的出现，这给计算机分析、 显示与存储带来了很大的不便。在计算机图形学中，三维几何模型的属性包括几何属性 和外观属性。本文主要研究几何模型的几何属性，即几何模型的外观形状。 蠡 一 江南大学硕士学位论文 1 1 3 网格处理方法 三维几何模型是指对真实物体的表面进行采样而得到的几何数据。它的基本表示形 式有三维点云和多边形网格。三维几何模型处理即用计算机对这种三维几何数据进行处 理，以达到不同应用所要求的数据转换、模型表示或场景绘制等目的。 声音被定义为一维时间直线上的函数；图像被定义为二维平面上的函数；甚至视频 也被定义为三维空间内的函数：一维是时间，另外两维是空间。它们都可以在欧氏空间 内，进行规则的、有序的时间或者空间采样，从而转换为二进制数据。但是，数字几何 数据具有与声音、图像与视频数据完全不同的特殊性质，所以对它的处理有很多它本身 的特点。 它所表示的物体表面通常是任意弯曲、复杂( 流形a f 流形，定向非定向) 和 缺乏连续参数化的，很难找到一种内在的函数形式对其进行描述。 几何数据本身以及各种属性数据都是非规则采样的。对于多边形网格模型，其 连接关系尤其复杂。 对于室内环境和建筑物等对象物，其数据表面的形状变化多样，拓扑结构错综 复杂。 随着三维激光扫描技术的进步，模型的数据量大幅度增长，其增长速度远远超 过了现有处理硬件所能提供的计算能力。 尽管d g p 的研究工作发展很快，但与数字图像处理相比，它还很年轻。因为就目前 而言，d g p 还没有一个相对比较完整的思想理论体系作基础，所以研究还存在着很多挑 战与困难。下面对d g p 的有关研究内容作一下简单介绍。 ( 1 ) 多分辨率与网格压缩 随着d g p 的发展，其应用面越来越广泛，多分辨率( m u l t ir e s o l u t i o n ) 就是其中的一 类应用。我们知道，分辨率是用于记录数据的最小度量单位，一般用来描述在显示设备 上所能够显示的点的数量( 行、列) ，或在影像中一个像元点所表示的面积n 6 1 7 1 。数字几 何处理中的多分辨率就是指以多个不同的数据点和信息量来显示物体模型。与多分辨率 的需求类似，网格压缩( m e s hc o m p r e s s i o n ) 主要解决的问题也是网格模型庞大数据量与 互联网带宽及计算机性能相对较落后之间的矛盾。其主要有两种类型：一是网格有损压 缩：二是网格无损压缩。目前，网格压缩的方法主要有：单分辨率压缩法( s i n g l e r a t et o m p r e s s ) 和多分辨率压缩法( m u l t i s o l u t i o nc o m p r e s s ) 。单分辨率压缩只有全部数据都解压后 才能显示出整个模型。多分辨率压缩又称为渐进( p r o g r e s s i v ec o m p r e s s i o n ) ，常与网格简 化( m e s hs i m p l i f i c a t i o n ) 和l o d ( l e v e l so fd e t a i l ) 技术结合，它的特点是显示过程逐步精 化1 羽。 ( 2 ) 参数化 参数化( p a r a m e t e r i z a t i o n ) 是指将复杂网格模型的整体或者一部分映射到一个二维平 面或三维球面等领域内，然后在二维平面上对数据作一些规范化的处理，如频域变换等， 最后将处理结果映射同原来的三维网格上，这样的处理过程就是网格参数化幢引。其目的 4 第一章绪论 就是通过更方便更完整且确实可行的理论体系思想来解释和处理那些相对较难理解和 处理的未知领域的知识。目前，参数化主要有保面积性、保角性和等距性三种参数变换 形式翱。 ( 3 ) 光顺与去噪 在三维几何的某些应用领域内，有时需要将原始网格模型表面上的一些不必要的众 多细小的凹凸不平的地方清理掉，即将网格模型中的不必要的噪声消除到最低状态。同 时，又不失保持原网格模型的相邻三角形面之间应有的连续性和光滑性。此时，需要对 模型作去噪( d e n o i s e ) 和光) l l 页( s m o o t h i n g ) 处理，使处理后的模型更加均匀与光滑，满足用 户的需求。值得一提的是，去噪与光顺运算绝不可以将网格曲面上应有的高频信号清除 掉，否则无法保持原有网格模型的整体状态信息乜引。 ( 4 ) 网格编辑 网格编辑( m e s he d i t i n g ) 可以包括两个方面的研究内容：一是网格形变( d e f o r m a t i o n ) ； 二是网格渐变( m o r p h i n g ) 。网格形变也就是通常意义上的三维动画。网格渐变是d g p 中 一个非常典型和重要的应用内容之一，关于网格渐变的研究内容与文献非常多汹。网格 渐变研究的是从一个m e s h 至l j 另一个m e s h 的变化过程。其结果只强调整个渐变过程的自然 与协调。网格渐变算法要求整个渐变过程严格作到预先定义的点一一对应。最后，根据 插值算法计算出渐变中的过程网格模型啪3 。 ( 5 ) 细分曲面与曲面拟合 近几年，细分曲面( s u b d i v i s i o ns u r f a c e ) 作为一种网格模型的表示形式，已经成为 d g p 的一个热点。目前，己研究出许多重要的成果，形成了一个相对比较完善的体 系。细分曲面主要是指用一个基本的相对简单的模型利用细分规则作不断地细分来表 示一个相对比较复杂的网格模型。目前，细分曲面的规则有很多，如中点细分、l o o p 细分、螺旋细分等。曲面拟合( s u r f a c ef i t t i n g ) 也是一种网格f h j 面表示方法。它主要是 利用各种不同的多项式曲面( 或参数曲面) 来近似逼近拟合原有的网格曲面模型啪1 。当 存储网格曲面模型时就可以避开存储繁多的网格顶点等信息，而改进按照一定的顺序存 储效率和传输速率。 ( 6 ) 网格重构和重网格化 网格重构( m e s hr e c o n s t r u c t i o n ) 是指根据一些没有任何规则的顶点集，要求重新构 造一个由这些顶点集所组成的简单曲面片。它通常应用到珍贵艺术品的复原与保存。艺 术品等的补漏工作通常很难找到其它类似的物品( 网格模型) 做参照物，只能在现有的 基础上进行主动地尝试重构，产生的代价往往较高啪3 。从广义上来说，重网格化 ( r e m e s h i n g ) 也属于网格重构的一种。因为重网格化也是重新生成一个网格模型，不同 之处在于重网格化可以完全将原来的m e s h 作参照对象，实现起来较之重构要方便很多。 ( 7 ) 逆向工程 逆向工程( r e v e r s ee n g i n e e r i n g ) 在d g p 中也是一个非常重要的内容，其应用面越 来越广泛，而且通常是与其他学科相结合起来使用，尤其是应用在工业设计与制造领域 内m 1 ，沿着模型生成过程相反的方向来处理模型信息的过程就称为逆向工程，又常被称 为反向工程。 5 江南大学硕十学位论文 ( 8 ) 其他 随着三维几何的应用越来越广泛，而且还存在着非常巨大的发展前景，d g p 研究的 内容也日益增多。上面只是领域内的部分研究内容，另外还有网格渲染( m e s hr e n d e f i n g ) 、网格形状分析( s h a p ea n a l y s i s ) 网格模型检索( 3 dm o d e ls e a r c h i n g ) 以及网格模 型分割( m e s hs e g m e n t a t i o n ) 等都属于d g p 中非常重要的研究内容。 q 噻参 e 网格参数化 网格光顺 网格形变 左为原始网格模型，右为b 样条拟合的结果 图1 3 部分g d p 处理算法 盹1 3s o m eo f g d p a 啊t h i n s 第一章绪论 1 2 三角网格模型的分割 三维网格分割是指根据一定的几何及拓扑特征，将封闭的网格多面体或者可定向的 二维流形，依据其表面几何、拓扑特征，分解为一组数目有限、各自具有简单形状意义 的、且各自连通的子网格片的工作，是一种将网格模型分解成为许多有一定意义的连通 网格子集的过程。目前，该工作己经被广泛应用于网格简化、层次细节模型、几何压缩 与传输、交互编辑、纹理映射、网格细分、几何变形、动画对应关系建立、局部区域参 数化以及逆向工程中的样条曲面重建等数字几何处理研究工作中。 随着三维网格分割研究的发展，人们对分割算法也进行了大量的研究，下面是几种 典型的三维网格分割算法： ( 1 ) 分水岭算法雌1 基本思想：把图像看作是测地学上的拓扑地貌，图像中每一点像素的灰度值表示该 点的海拔高度，每一个局部极小值及其影响区域称为集水盆，而集水盆的边界则形成分 水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表面， 刺穿一个d q l ，然后把整个模型慢慢浸入水中，随着浸入的加深，每一个局部极小值的 影响域慢慢向外扩展，在两个集水盆汇合处构筑大坝，即形成分水岭。分水岭算法对微 弱边缘具有良好的响应，但是会产生过度分割的现象。 以上是图像分割中的分水岭算法的基本思想，把分水岭算法应用于网格模型分割 时，其基本思想一样，不同的是在网格模型中，我们要取模型的元素( 三角形或者顶点) 的几何属性( 例如曲率等) 作为高度函数。分水岭算法中种子和高度函数的选择是很重要 的，直接影响分割结果。但是仍然存在过分割的现象。 ( 2 ) 基于拓扑信息的方法 基于几何以及拓扑信息的形状分割方法可以归结为r e e b 图、中轴线和s h o c k 图等， 基于拓扑信息的形状特征描述主要有水平集法和基于拓扑持久性的方法。水平集法具有 较高的计算速度和健壮的计算精度。 r e e b 图简单的说就是：设函数f ：m r 是定义在紧流体m 上的一个连续函数， 把m 上具有相同函数值并且连通的区域用一个节点表示，把结点相互连通后就得到了 r e e b 图。在实际应用中，一般的三维模型都符合紧流体的要求，选择不同的函数f ，三 维模型的r e e b 图就不同，f 函数可以是高度函数也可以是表面测地线距离。 中轴线图又称骨架图，在视觉可视化、计算机图形、计算机视觉等领域得到了广泛 的应用。骨架图可以衡量三维模型的拓扑结构特征。传统的提取骨架的方法有基于数字 形态学的方法和基于距离变换的方法，两种方法在连续域都是完备的。但在离散域各有 其优缺点，细化得到的骨架具有良好的拓扑性，但是骨架点的位置却不准确；基于距离 变换的方法在骨架点的准确度上效果好，但连通性一般却很难保证。 ( 3 ) 基于模糊聚类的层次分解 模糊聚类的层次分解算法，算法处理由粗到精，得到分割片层次树。层次树的根表 示整个网格模型s 。在每个结点，首先确定需要进一步分割为更精细分割片的数目，然 7 江南大学硕士学位论文 后执行一个k w a y 分割。如果输入的网格模型s 由多个独立网格构成，则分另对每个 网格进行同样的操作。分割过程中，算法不强调每个面片必须始终属于特定的分割片。 大规模网格模型的分割在其简化模型上进行，然后将分割片投影到原始网格模型上，在 不同的尺度下计算分割片之问的精确边界。优点是：可以对任意拓扑连接的或无拓扑连 接的、可定向的网格进行处理：避免了过分割和边界锯齿：分割结果适用于压缩和纹理 映射。 ( 4 ) 其他的方法 除去以上方法，还有很多的其它的分割算法。因为三维模型只包含几何属性( 顶点 坐标、法向矢量) 、拓扑连接、以及表面属性( 颜色、纹理等) 底层信息，所以分割算 法也都是基于对这样的底层信息进行的。 号伊号零斡 嘲 r e e b 囤的分割结果 未考虑纹理距离的分割结果考虑纹理距离的分割结果 图卜4 部分分割结果 f 镕卜4r e s u l t so f s e g m e n t a t i o n 1 3 三角网格模型的简化 目前，由于网格模型大部分l 蔓角咧格表示，因此几何模型的简化是指在保持原几 何模型的基本几何形状不变的前提下，采用适当的简化算法减少该模型的面片数、边数 和顶点数。几何模型的简化对于儿何模型的存储、传输、处理，特别是对实时绘制有着 重要的意义。 由于网格模型大部分由三角丽片表示，而且即使原始模型不是三角面片，也可以对 其进行三角化。冈此网格模型简化的本质是在尽可能保持原始模型特征的情况下，最大 限度地减少原始模型的三角形和项点的数目。它通常包括两个简化原则：顶点最少原则， 第一章绪论 即在给定误差上界的情况下，使得简化模型的顶点数最少：误差最小原则，给定简化模 型的顶点个数，使得简化模型与原始模型之间的误差最小。我们就三角网格模型进行研 究。 三角网格的简化算法按照其基本操作的不同大致可以分为以下几类： ( 1 ) 顶点聚类算法 顶点聚类算法是将整个网格模型划分成若干个小的区域，并且将同一区域内的若干 个顶点用一个代表顶点取代，该算法具有快速、简单、易于实现的优点，但同时它也存 在着无法保持网格模型特征、易于破坏模型结构等明硅的缺点，如分别属于两个平面而 又邻近的两个顶点容易被错误的合并为一个顶点从而改变模型的拓扑结构。 ( 2 ) 删除法 删除法是指通过评价辟9 格模型中模型要素的重要性，从原始网格模型中逐一减少模 型要素，从而达到简化模型目的的方法。根据所删除的模型要素的不同，又可以分为顶 点删除法、边折叠法和三角形折叠法等。该类方法能够有效的保持网格模型原有的拓扑 结构，是目前应用最为广泛的网格简化算法。 ( 3 ) 重新布点法 熏新布点法通过在网格表面分布新的顶点，平坦区域分布较少的点，特征区域分布 较多的点，然后根据这些新顶点重构网格模型的算法。 ( 4 ) 细分法 细分法是指从一个粗糙的模型不断对其进行细分使之不断接近原始网格模型的算 法。 1 4 麟| | 繇 盆 循 ( 1 ) 动画制作领域。现代的动i m j 形象埘外部造型要求越来越高，特别足对媒体角色 的逼真度提出了苛刻的要求。在一部动l 咖片一p ，动i 及环境角色可能成千上万数字几 何处理提供了直接从现实模型到数字模型的方法，这样一个直观高小、稳定可靠的造型 工具将推动动画制作技术近向新的台阶。 ( 2 ) 逆向工程领域。逆向工程是从已有的实体模型重建曲面模型，现行的处理方法 通过三维扫描仪输入实体数据然后用解析曲面模型来拟合或逼近这些数据。 捌 江南大学硕士学位论文 ( 3 ) 人体医学影像。当前有大量的仪器设备可以获取人体表面及内部数据，而医务 人员只能通过二维图像进行症断。利用数字几何处理的结果，可以将从仪器获取的数据 恢复三维形状，对外科手术的精确定位能起到关键作用，同时对整形外科也将会产生巨 大的影响。 ( 4 ) g i s 领域。大规模g i s 的数据通常是卫星深度图像，数据量巨大，利用数字几 何处理的结果能够大量简化模型，缩小数据量，复原三维地貌。在城市地理信息系统中， 要得到比较真实的建筑物模型，一种快捷的方法是用高速三维测量仪获取数据，进行三 维合成。 ( 5 ) 文物的保护和修复。对于文物，处于保护的需要，一般不能用接触的方式获取 它们的三维数据，只能用非接触式的三维扫描仪定期获取数据，进行比较，判断毁损程 度，以决定是否需要进行修复。对于已毁损的文物，可通过数字几何处理技术得到它的 三维模型，首先在电脑里进行复原，最后确定复原方案。 1 5 本文工作 本文回顾了数字几何处理的发展及应用领域，列出了各类数字几何处理算法，并且 对其中的两种算法一三角网格分割算法及其在简化中的应用，进行了研究，提出了新 的三角网格分割算法和基于分割的简化算法。全文按照下列结构组织： 第一章回顾了数字几何处理的出现及发展，以及它在各行各业中的应用，同时介绍 国内外对于数字几何处理的研究状况，说明了本文所完成的工作。 第二章介绍了三角网格分割算法和简化算法的研究现状，分析和介绍了各类分割算 法和简化算法。 第三章根据平坦性的要求提出了一种基于区域生长的三角网格模型分割的算法。 第四章提出了基于分割前提下以三角形折叠为依据的三角网格模型的简化算法。 第五章给出了全文工作的总结，并对未来的工作进行了展望。 1 0 第二章网格模型分割和简化简介 第二章网格模型分割和简化简介 网格模型根据定的几何与拓扑特性，对于封闭的网格多面体或者可定向的二维流 形，根据其表面几何、拓扑特性，分割为一组数目有限、各自具有简单形状意义的、且 各自连通的子网格。通常，根据分割的结果，网格分割算法可分为面片分割和部件分割 两类，如图2 - 1 。面片分割遵循网格的平面性，尺寸或凸而等几何属性，将模型分割为 多个面片：而部件分割则将网格划分为有意义的部分，得到的分割结果具有一定的实际 的物理意义。网格简化的目的是把一个多边形网格表示的模型用一个近似模型表示，近 似模型基本保持了原模型的可视特征，但顶点数目少于原始网格的顶点数目。通常的做 法是把一些不重要的图元( 顶点、边或三角形) 从多边形网格中移去。 b a ) 部件分割结果( b ) 面片分割结果 圉2 - 1 根据分割结果时网格分割算法的分类 f i g2 - 1c l a s s i f i c a l i o no f s e g m e n t a t i o n 2 1 分割和简化的意义 211 分割的意义 面片分割算法普遍使用于纹理映射，模型交互编辑和简化以及几何图像生成等工 作，所以它通常要求分割q 减的区域拓扑等价于一个圃盘并月参数化投影到二二维后区域 不能有太大的扭i | ；部件分割算法应用1 形状匹配、形状重建、几何变形等工作，因此 它要求分割的结果耍有实际的物理意义。 三维网格分割有两个背景l ：作：一个是与网格分割有关、并对其影响巨大的一个背 景一作是计算几何的l 分割，其目的是把非凸的多面体分割为较小的凸多面体，以促进 图形学的绘制和渲染效率：另一个是训算机视觉中的深度图像分割，其处理的深度图像 往往具有狠简单的行列拓扑结构，而不足任意的，故其分割算法相对简单。 飞了 r ， h 以 江南大学硕士学位论文 在由点云重建三维模型网格曲面、网格简化、几何压缩、交互编辑、纹理映射、几 何变形、网格细分、动画对应关系建立、局部区域参数化、以及逆向工程中的样条曲面 重建等数字几何研究工作中，三维模型分割的需求已经被广泛地提出了、并得到深入、 实用的研究。 三维模型分割显然是在一定意义上的网格简化，比如将曲率变化剧烈的区域作为分 割边界，从而将曲率变化平缓的区域各自分割开来，就是基于曲率阀值的一种网格简化 方法。网格曲面分割的结果数目应该在去除过分割后被限制在指定的范围内，是有限的。 在交互网格编辑工作中，我们往往是针对某个特定区域进行处理，如何将此区域提 取，并在编辑处理后与其周边邻接区域融合，显然也是网格分割支持的工作内容。 在影视动画制作过程中，动作对象的运动控制、表面的运动变化、以及从一个对象 几何变形为另一个对象的特技处理，如果使用了基于分割的网格曲面局部区域预处理 ( 比如建立动画区域对应关系) ，显然在动画精细度、视觉效果、计算速度和复杂度上 有很好效果( 会节省存储，如果不得不导致速度有所下降的话) 。 显然三维模型的分割会加速光追踪、着色、绘制、求交、碰撞检测的层次包围盒的 计算等工作，并提高精度。三维模型的分割显然会因其局部性而降低纹理映射、纹理贴 图、网格参数化的扭曲效果。同样对点云的分割将使得逆向工程中的样条曲面重建、拟 合高阶模型到多面体网格变的容易得多。 2 1 2 简化的意义 近年来，三角网格数据在逆向工程、虚拟现实、网络图形和三维动画中得到越来越 广泛的应用。随着计算机技术的应用和发展，人们对计算机造型和绘制技术的要求不断 提高，计算机模拟场景的规模越来越大，景物的细节也越来越丰富。另外，三维扫描仪 得到的数据构建的三角网格模型，由于其采样密度均匀，因而造成了数据量庞大，受到 存储和传输带宽的限制，使得其很难在实际应用中直接使用。并且随着三维扫描仪的大 规模普及和发展，扫描获取的几何体的细节以及外形的日渐丰富，所获取的数据规模也 越来越大。 庞大的三维数据量对处理器的处理能力、计算机的容量以及网络传输技术的都提出 了很高的要求，成为实现移动设备图形处理、实时交互、网络三维动画、分布式虚拟显 示等应用的瓶颈。要解决这些由于庞大的数据数量和急剧增长的复杂度以及移动设备相 对较低的三维图形处理能力所带来的问题，是提高三维图形和网络技术中令人感兴趣的 重要课题。 当前，网格模型的精度越来越高，从而模型的数据规模和复杂程度急剧增长，这使 得计算机的运算和图形处理能力不能满足大规模复杂几何模型的绘制要求。随着网络图 形学的发展，越来越多地需要通过网络，特别是国际互联网，来存取放在异地的三维几 何数据。这使得本已有限的网络带宽变得更加的紧张。总之这些复杂的模型对计算机的 1 2 第二章网格模型分割和简化简介 存储、传输、计算、绘制等带来困难。然而在很多情况下模型的准确度不需要这么高。 几何模型的简化对存储、传输、处理，特别是对实时绘制有着重要的意义。 2 2 三角网格分割简介 2 2 1 模型分割的标准 在网格分割算法中，最重要的也是用户最关心的是那些影响分割结果与质量的因 素，主要有分割标准与停止分割的条件。分割标准和停止条件都与分割目的紧密相联系， 不同分割目标的分割算法应该采取不同的分割标准。下面归纳出几种网格分割原则。 ( 1 ) 平坦性 目前，在网格分割的各种算法中，平坦性是个最常用也是最重要的分割标准。依 据网格分割的性质和分割目的的不同，平坦性的定义也有所区别：网格分割的应用领域 不同也会影响平坦性的定义形式。下面列举出了几种常见的平坦性定义方式： l 距离平坦性 己知与子网格片m r 相关联的一个平面方程l ：a x + b y + c z + d = o ，三角网格曲面上的一 顶点v i = ( v x ，v y ，v z ) i ，一个比较小的正数e 0 如果有距离方程e ： e ：i ( 匕，1 ，吃) ( 口，b ，c ，d ) | 0 。如果平均距离方程e ： 1k 2 j 2 ：。：萋1 ，1 ，y 1 ，z c 7 ，6 0 。如果最大法向偏移方程e 江南大学硕士学位论文 豇老善( 1 - ( 巾a g d 脚 ( 2 3 ) 成立，即若点v 到平面l 的法向偏移量小于预先给定正数e ，则将点v 归类到该子网格 片m r 中，否则不予归类。 厶法向平坦性 己知与子网格片m r 相关联的一个平面方程l ：a x + b y + c z + d = o ，三角网格曲面上的一 顶点v 的法向n _ ( n x ，n y ，n z ) ，正数e 0 。如果最大法向偏移方程e e ：三喜击( 1 饥巾a 硎鱼 ( 2 4 ) 成立，即顶点系列v i 满足厶法向平坦性，则将顶点系列v ；归类到子网格片m r 中：否则 不予归类。其中a i 是加权因子，并且有a = e a ；，a 。可以是相应三角形面的面积，或者是 相应顶点的“1 邻域 内的三角形面的面积。 ( 2 ) 基于曲率提取： 曲率计算方法不同，很多算法给出的有意义的分割结果也存在差异诸多应用研究 证明，网格模型基于显著性特征的形状分割，是物体识别、分类、匹配和跟踪的基本问 题而有意义的分割对于网格模型显著占优特征的表示和提取、多尺度的存储和传输以 及分布式局部处理都是十分有意义的。 曲面拟合计算曲率： c ，( 1 ，) 刊( 尼( v ) 一u ) l al ( 2 5 ) 其中：k ( v ) 为顶点v 的绝对主曲率，u 为所有顶点k ( v ) 值的平均值，而盯为所 有顶点k ( v ) 值的标准方差。 最小曲率估计： 蚋) 2 丽1 萎雕m 们旧 ( 2 6 ) 其中lb i 是围绕点v 的有一定半径( 可以根据具体情况选择) 的面积，( p ) 是一个 带符号的角度值( 相邻两个面的法向量的夹角，如果是凸的话就是正，如果是凹的话就 是负) ，e 是b 中网格的边，i p 厂、b i 是一个长度，它在0 到e 之间，e 是和e 同方向的单 位向量。 也可以对最小曲率进行改进得到： ，( v ) = ( j j ( 1 ，) 一u ) a ( 2 7 ) 1 4 第二章网格模型分割和简化简介 其中七( 1 ，) 是最小曲率，a 是所有顶点最小曲率平均值，盯是网格上所有顶点最小 曲率的偏移值。 ( 3 ) 面积、长度、数量与比例 用面积作为分割标准是指规定分割后所产生的各子网格片的面积的大小。具体可以 用最大或最小面积来约束网格分割的程度，使算法达到停止条件。长度阀值与数量阀值 同面积阀值类似，分别是用来约束分割后生成的各网格片的最大( 或最小) 直径距离和各 子网格片中所包含的三角形面的最大( 或最小) 数量值。比例阀值则与前三个约束有一定 的区别，采取比例作分割标准是为了使网格分割结果符合一个相对平衡的状态。例如， 规定分割后的各子网格片的最大面积和最小面积的比例值不能超过某个阀值。比例阀 值通常是与前三个标准中的其中一个结合起来使用，分别为面积比例、长度比例和数量 比例等。基于比例阀值的分割算法一般是属于片状网格分割。 ( 4 ) 其他标准和条件 凸包性可以用来评价判断子网格片是否满足凸包的一些特性，单连通性、同胚性也 不失为一个分割判断标准。在某些情况下，有时需要将那些平坦性不是很好的且局部有 强烈的凹凸感的区域归类到同一个子网格片中来，此时，常采用测地距离( g e o d e s i c ) 、 两面角( d i h e d r a la n g l e ) 距_ 离作为分割标准。 2 2 2 模型分割的算法 我们将现有的方法按照近似技术进行分类。 ( 1 ) 区域生长聚类( r e g i o ng r o w i n g ) 区域生长算法从一个种子元素开始，按照一定的原则生长成一个子网格，如下： 区域生长算