（运筹学与控制论专业论文）曲面简化与细分曲面造型的研究.pdf

中文摘要 随着置维扫描等测量技术的发展，获得的三维数据越趋于复杂，从而由曲面 重构及其等值面抽取等方法得到的模型网格相当复杂、稠密。这给计算机的显示、 传输与存储等带来很大的不便。近些年，围绕该问题人们拓宽了血面造型技术 的研究领域，其中曲面简化与细分曲面技术成为了一个焦点。 本文较为综合的描述了曲面简化与细分曲面造型技术。盘面简化是在保持原 模型的特征的情况下，逐步删除模型的面与顶点，从而除去了模型一些细节特征， 得到初始模型的一个较简单的逼近模型。细分曲面是一个网格序列的极限曲面， 即通过采用一组规则在给定的初始网格中插入新顶点并不断重复此过程而获得。 首先本文较全面的介绍了当今各种有效的曲面简化算法并分析了它们的优 缺点。算法主要有顶点聚类、顶点删除、区域合并、小波分解、边折叠等等。其 次，本文提出了一种基于尖特征度的边折叠简化算法。目6 f 存在的自动简化算法 在低分辨率的状态下往往忽略模型的重要儿何特征，如尖角或者曲率大的区域， 从而导致视觉上的退化；本文在q e m 算法基础上，引入尖特征度的概念，不仅 保留了模型的重要几何特征，而且合理分配网格，在曲率大的区域稠密、平坦区 域稀疏，简化效果更好。再次，本文研究了绷分曲面造型技术及其在图形学中的 应用。并列出了两个基于三角形网格的细分模式：l o o p 细分与改进的b u t t e r f l y 细分。最后，本文阐述了一种由稠密二角网格构造蝶形细分曲面的方法。利用边 折叠简化的精度高、速度快的优点及其蝶形细分模式的插值性构造出具有较好视 觉效果的蝶形细分曲面。其中，一同介绍了连续多分辨率模型的构造及其在网络 传输中的应用，曲面简化与细分是构造离散或连续多分辨率模型的丰要7 j 法，所 以找到一种理想的简化方法与细分模式是将来需要继续的工作。 关键词；。曲面简化，细分曲面，o e m ，尖特征度，边折叠，b u t t e r f l y 细分 a b s t r a c t n o wl a s e rr a n g eg e a n n a r sa n dm e d i c a li m a n n gd e v i c e sc a r lp r o v i d ev a s td a t ao f i n r i c a t ep h y s i c a lo b j e c t sm o d e l sp r o d u c e db ys u r f a c er e c o n s t r u c t i o na n di s o s u r f a c e e x t r a c t i o nm e t h o d sc a no f t e nb ev e r yd e n s e l ys a m p l e dm e s h e st h e s em o d e l sa r e b u r d e n i n gi nr r l a n ya p p l i c a t i o n ss u c ha sr e a l t i m ed i s p l a y , t r a n s m i s s i o na n ds t o r a g e t h e r e f o r e ，s u r f a c es i m p l i f i c a t i o na n ds u b d i v i s i o ns u r f a c em o d e l i n gh a v eb e e nt w o s u b j e c t so ft h es u r f a c e sm o d e l i n gr e s e a r c h t h i st 1 1 e s i sm a i n l yd e s c r i b e ss u r f a e es i m p l i f i c a t i o na n ds u b d i v i s i o ns u r f a c e s m o d e l i n g s i m p l i f i c a t i o ni st h ea c to ft r a n s f o r m i n gad e t a i l e d3 dp o l y g o n a lm o d e l i n t oas i m p l e rv e r s i o n ，a n dag o o ds i m p l i f i c a t i o na l g o r i t l u nr e d u c e st h en u m b e ro f v e r t i c e sa n dp o l y g o n sw h i l et r y i n gt or e t a i nt h eg o o da p p r o x i m a t i o no ft h eo r i g i n a l s h a p es u b d i v i s i o nd e f i n e sas m o o t hs u r f a c ea st h el i m i to fas e q u e n c eo fs u c c e s s i v e r e f i n e m e n t s t h e ns u b d i v i s i o ns u r f a c e sa r eo b t a i n e du s i n gs o m es c h e m e st o i n s e r t n e wv e r t i c e sa n dm o d i r yo l dv e r t i c e s f i r s t l y , t h i st h e s i sb e g i n sw i t has u r v e yo ft i l em o s tn o t a b l ea v a i l a b l ea l g o r i t l w n s o fs u r f a c e s s i m p l i f i c a t i o n ，s u c h a sv e r t e x c l u s t e r i n g ，v e r t e xd e c i m a t i o n ，r e g i o n m e r g i n g ，w a v e l e td e c o m p o s i t i o na n de d g ec o l l a p s e s e c o n d l y , t h et h e s i si n t r o d u c e sa e d g ec o l l a p s es i m p l i f i c a t i o na l g o r i t h mb a s e do ns h a r pd e g r e e t h ee x i s t i n ga u t o m a t i c m e s hs i m p l i f i c a t i o na l g o r i t h m sa t p r e s e n tn w a y si g n o r es o m ei m p o r t a n ts h a p e f e a t u r e so ft h eo r i g i n a lm o d e l ，s u c ha st h ec o r n e r sa n dh i g h c u r v a t u r er e 百o n s i nt h e l o w l e v e lm o d e l a n dt h i sw i l ll e a dt od e g e n e r a t i o ni nt h es e n s eo fs i g h tt h e r e f o r e ， w ei n t r o d u c et h ec o n c e p to fs h a r pd e g r e ea n dp r e s e n to u tm e t h o db a s e do nq e m a l g o r i t b m ，w h i c hc a nn o to n l y p r e s e r v et h ei m p o r t a n tf e a t u r e so fm o d e lb u ta l s o d i s t r i b u t em e s h e sm a s o n a b l y w ec a ng e tab e t t e rs i m p l i f i e dm o d e w h i c hh a sd e n s e m e s h e si nt h eh i g h c u r v a t u r er e g i o n sa n ds p a r s em e s h e si nt h ef l a tr e g i o n s t h i r d l y , t h et h e s i ss t u d i e st h em o d e l i n ga n da p p l i c a t i o no fs u b d i v i s i o ns u r i a c e s s u b d i v i s i o n m e t h o dh a sb e c o m ea ni m p o r t a n tt o o li nc o m p u t e rg r a p h i c se s p e c i n l yi n3 dm o d e l i n g a n da n i m a t i o nf i e l d s t w oi m p o r t a n ts u b d i v i s i o ns c h e m e sb a s e do i lt r i a n g u l a rm e s h e s f l o o ps u b d i v i s i o na n dm o d i f i e db u t t e r f l y , s u b d i v i s i o l l ) a r el i s t e di nt h ee n df i n a l l y , t i l et h e s i sp r e s e r _ l t sam e t h o do fc r e a t i n gb u t t e r f l ys u b d i v i s i o ns u r f a c e sf r o md e n s e m e s h e ss u r f a c es i m p l i f i c a t i o na l g n r i t h mi sb a s e do nq e mw h i c ha p p l i e sas e a e e t l c e o f e d g ec o l l a p s eo p e r a t i o n _ i h r o u g hi tw eo b t a i ns u b d i v i s i o ns u r f a c e s lc o n t r o lm e s h e s t h e ns u b d i v i s i o ns u r f a c e st h a th i g h l ya p p r o x i m a t et ot h e i ro r i g i n a ls u r f a e e sa r e g e n e r a t e db ys u b d i v i d i n gt h ec o n t r o lm e s h e su s i n gm o d i f i e db u t t e r f l ys u b d i v i s i o n s c h e m ei nt h ee n 正t h e s i si n t r o d u c e st h ec o n t i n u o u sm u l t i r e s o l u t i o nm o d e l s c o n s t l n c t i o na n dt h e a p p l i c a t i o ni n _ w e b t r a n s m i s s i o n a t p r e s e n t ，s u r f a c e s s i m p l i f i c a t i o n a n ds u b d i v i s i o n a r cd i et w om a i nm e t h o do f c o n s t r u c t i n g m u l t i - i e s o l u t i o nm o d e l st h e r e f o r e ，i ti sn e e d e dt oc o n t i n u es e a r c h i n gap r o p e l s i m p l i f i c a t i o na l g o r i t h ma n das u b d i v i s i o ns c h e m e k e yw o r d s ：s u r f a c e ss i m p l i f i c a t i o n ，s u b d i v i s i o ns u r f a c e s ，q e m ，s h a r pd e g r e e e d g ec o l l a p s e ，b u t t e r f l ys u b d i v i s i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导卜进行的研究t 作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文埠1 不包含其他人已经发表 或撰写过的研究成果，电不包含为获得墨洼盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同一 作的同志对奉研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：i 1 萌起- 一签字日期：w 识夕年月甲日 学位论文版权使用授权书 本学位论文作者完全了解：叁空盘堂有关保留、使用学位论文的规定。 特授权盘洼叁茔a ，u 将学位论文的全部或部分内容编入有关数据库进行检 索，并采f ； j 影印、缩印或扫描等复制手段保存、汇编以供查阒和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文庄解密后适川本授权说叭) 学位论文作者箨名 翱欢一 签字目期：2 d 愁年r l 扫 导帅签名 纠弘 誉字臼期：伽年fl j 怔口 犬沣夫节硕十学位论文 第j 绪论 1 1 引言 第一章绪论 蛀面造型是计算机图形学和计算机辅助几何设计( 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 ) g - - 项重要内窖，主要研究在计算机图象系统的环境下对曲而的表示、 设计、显示和分析。它起源于飞机、船舶的外形放样工艺，由c o o n s 、b e z i e r 等 大师十六十年代奠定理论基础。经三十多年发展，现在它已经形成了以b e z i e r 和b 样条方法为代表晌参数化特征设计和隐式代数曲面表示这两类方法为主体， 以插值( 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 ) 这三种手段为泞架的 几何理论体系。 随着计算机图形显示对于真实性、实时性相交互性要求的曰益增强，随着几 何设计对象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的r 益明显，随着 图形t 业和制造工业迈向一体化、集成化和网络化步伐的日盏加快，随着激光测 距扫描等三维数据采样技术和硬件设备的日益完善，曲面造型在近几年来得到了 长足的发展。这主要表现存研究领域的急剧扩展和表示方法的开拓乜新。 从研究领域来看，曲面造型技术已从传统的研究曲面表示、曲面求交和曲砸 拼接，扩充到曲面变形、曲面重建、曲面简化、曲面转换。本文主要研究的是其 巾的曲面简化技术：曲面简化( s u r f a c e ss i m p l i f i c a t i o n ) 这一研究领域e f 前是旧际热 点之一。其基本思想在于从三维重建后的离散曲面或造型软件的输出结果( 主要 是三角嘲格) 中去除冗余信息而又保汪模型的准确度，以利于图形显示的实时性、 数掘存储的经济胜和数掘传输的快速性。对于多分辨率曲面模型而言，返一技术 还有利于建立曲面的层次逼近模型，进行曲面的分层显示，分层传输和分埕编辑。 只体的曲面简化方法自很多如：顶点删除算法、重新划分网格算法、藩域台井算 法、，j 、波分解算法、项，点聚类算法、边折叠算法等等。 从表示方法来看日葑已经有多种曲面表示方法，自够较好的表示：b 耳种复 杂的三维模型， 天伴大学颂- k 忙论文 第一章绪论 1 2 常用的曲面表示方式 一般在| 维数据场可视化的研究中，三维复杂物体的几何表示方法大体上可 以分两类：一类为体( v o l u m e ) 表示；另一类为面( s u r f a c e ) 表示。这两类表示方法 各有特点f 1 。对于体表示方法，不仅可以给出物体的表面特征，而且出可以给 出物体的内部特征，因此，便干给出模型的物体描述。体模型的表示占用空间较 大，表示和处理都不便，而且体表示的某些技术还不成熟。但是体表示的优点也 表明它是一个非常有潜力的研究方向。面表示方法足类比较流行的表示方法， 这种方法的优点就是只给出被表示的物体的表面特征，这样兢大大减少了内存的 占用量。在很多应用中，并不需要物体内部特征，所以，这种表示方法是非常有 用的。前面介绍的曲面造型技术就是基于面表示方法进行研究的。面表示方法有 多种，对于静态物体的描述可以大致归结为以f 四类： ( 1 ) 多边形网格表示方法 多边形网格模型表示方法，是最直接的表示方法，在计算机图形学诞生之时 就已丌始使用。而今，配合纹理映劓与光照材瓶，仍广泛应用于备类动面系统。 多边形网格的最大优点是数学模型简单，它直接使用点，直线段和平面片来逼近 真实的形体，因此容易理解适于绘制。其中，三角形表示力法较为普遍下一 节将给出它的具体描述。 ( 2 1 参数表示方法 参数曲线曲面表示直是描述几何形状主要1 具，它起源j + 飞机船舶的外形 放样设计工芝。由c o o n s ，b 6 z i e r 等人在6 0 年代奠定其理论基础。1 9 7 1 年，法 国k e n a u k 汽车公司的b 6 z i e r 提出了用控制网格定义曲线的方法，并将其成功地 用于自由曲线曲面设引系统u n i s u r f 中，b 6 z i e r 曲线具有端点插值等多种良好 交互性；1 9 7 5 年，v e r s p r i l l e 在其1 毒十沧文中首先提出了有理b 样条方法，它可 解决二次曲面的精确表示问题。至8 0 年代术，非均匀有理b 样条m o n - u n i f o r m r a t i o n a lb - s p l i n e ) b 9n u r b s 成为曲线曲面描述中的最流行技术。整个9 0 年代是 n u r b s 走向完美的阶段，今天的多数主流造型系统都包含有n u r b s 功能，m j 著名的几何建横软件r h i n o 就完全用n u r b s 作为其基本的数学表示模型。 总之，参数曲线曲而造型的基本思想是以一组基函数为权因予，利用一组初 始控制向量的线性( 或自理线性) 组台来得到形体的连续表示。如今改类力法已 经形成以拟合、插值和逼近这三种手段为主的实用儿何理论体系。 ( 3 ) 隐式表示方法 在数学和一算机科学中，以隐匝数j e 义儿何物体的方法也比较伟见。在二维 守划情形，成州，_ 用j i 等式，( o ) 20j ；：定义的半空问柬揣述戈体：月等式 犬洋大学硕士学位呛文 f ( x ，弘= ) = 0 所定义的宅叫边界来表示隐函数曲雨i ，当函数，是多项式时，：一式 定义了 张代数曲面。隐函数表示的优点是儿何求变方便，而且善于表示封闭光 滑形体，因此更适于确l 向绘制的应用。二次代数曲面是最早实用化的晡而模型之 一，作为实体造型方法的基础，它可以方便地表示球体，晦锥面，抛物面和双曲 而。 离散扫描表示，包括图像和体数据可被看成是某个连续函数g ( x ，) 在整数格 点上的取值如，进步，令g ( x ，y ) 一g 。= 0 即转化为隐函数表示。基于此观点， 可方便地进行图像光汴设计、边缘提取、距离场求解等多种图像处理操作；它也 是这一领域的主要思想方法。 f 4 1 细分表示方法 细分表示方法虽然于七一l 年代已被明确地提出来，但直到九十年代随着计算 机硬件能力的提高和应用的深入，才得咀大敖异彩。它与传统的连续造型相比大 有后来屠上之势。由于细分方法不受控制网格拓扑的限制，可以对任意拓扑网 格进行曲面造型，而且其递归结构与小波和多分辨率分析有着密切联系，使得细 分方法在图形学领域得到了深入的研究和广泛的应用。本文第四章将给出细分方 法的详细论述。 1 3 三角网格的基本概念 存以上介绍的曲而表示方法中，多边形网格表示方法特别是i 角刚格表示方 法是众多表示方法中比较流行的一种。本文中的模型简化方法采用的是兰角刚格 模型，为讨论方便，在这里给出三角网格模型的有关概念和术语 2 。 1 3 1 单纯复形 般的，三角网格是指由顶点、边和三角片构成的集合。它与图论中的图的 概念相比多了一种兀素，即由顶点和边构成的三角片。如果忽略网格顶点晌几何 位置信息，只考虑其拓扑关系，就得到种抽象的三角网格，称之为单纯复形 ( s i m p l i c i a lc o m p l e x e s ) u 定义11 设集台r 为 0 ，l ，2 ，n 一”，其中n 为顶点数， 屺 p p = ( f ，j ：吼，i p 7 y 固p 7 r = f ( l 。，七) ：v i ，七f 7 ，删单纯复形是满足 条仁( 1 ) 一( 3 ) 的二元纽k = ( 旷，e ，) ，这5 口y 中的一素称为顶 点：e i e “t ) v y ；) 的元素称为边：尸( f ，二f 7 0 r 矿) 7 门元素称为三角面。， 大律火学硕士学位论文 第章堵沦 r ( r ，v ，z ) ：o 所定义的空叫边界来表示隐函数曲丽，当函数厂是多项式叫t 一式 定义了一张代数曲面。隐函数表示的优点是几何求交方便，而且善于表不划闭光 滑形体，因此更适于面1 向绘制的应用。二次代数曲面是最早实用化的曲面模趔之 ，作为实体造型方法的基础，它可以方便地表环球体，匮锥面，抛物向和双日圭 面。 离散扫描表示，包括图像和体数据可被看成是某个连续函数g ( z ，) 在整数格 点上的取值g 。，进一步，令烈j ，y ) - g 。= o 即转化为隐函数表示。基于此观点， 可方便地进行图像光滑设计、边缘提取、距离场求解等多种图像处理操作；它也 是这一领域的主要思想方法。 ( 4 ) 细分表示方法 细分表示方法虽然于七十年代已被明确地提出来，但直到九十年代随着计算 机硬件能力的提高和应用的深入，才得以大放异彩。它与传统的连续造型相比大 育后来屑上之势，由于细分方法不受控制网格拓扑的限制，可以对任意拓扑网 格进行曲面造型，而且其递归结构与小波和多分辨率分析有着密切联系，使得细 分方法在图形学领域得到了深入的研究和广泛的应用。本文第四章将给出细分方 法的详细论述。 1 3 三角网格的基本概念 在以上介绍的曲面表示方法中，多边形网格表不方法特别是三角网格表示方 法是众多表示方法中比较流行的一种。本文中的模型简化方法采用的是三角网格 模型，为讨论方便，在这里给出三角网格模型的有关概念和术语 2 a 1 3 1 单纯复形 一般的，三角网格是指由顶点、边和三角片构成的集合。它与图沦中的罔的 概念相比多丁一种元素，即由顶点和边构成的三角片。如果忽略网格顶点的几何 位置信息，只考虑其拓扑关系，就得到一种抽象的= 三角网格，称之为勇自k 复形 ( s i m p l i c i a lc o m p l e x e s ) u 定义11 设集合v 为 0 ，1 ，2 ，n 一1 j ，其中n 为顶点数，记 r = ( ，j ) v i ，矿 y o i ，o v = “l ，七) ：v 2 ，ke 矿l ，划单纯曼形是满足 条f l ( 1 ) f 3 ) 的元组丘= ( 旷，e ，) ，这甲矿由晌元紊称为j 页 点：p i e c l ( i ，) y 0r 1 ) 自乞儿豢称为边：f ( f cv 矿) 的元豢称为三角面。 点：f 【亡l ( i ，) y 1 ) 舵儿索称为边 f ( f c r 矿) 的元豢称为三角面。 天津大学硕士学位论文 第一章绪论 ( 1 ) f 中的所有边属于：v ( b 即ii 2 ) f ，( r ，0 ，。州。) e ( 0 至f 2 ( 2 ) e 中的每条边一定属于某个面：，) c e ，罩，i 工j f ； ( 3 ) v 中的每个项点定属于某条边：r ，可使得( z ，) 占； 定义12 如果单纯复形的一条边只属于个面，称这条边为边界边 ( b o u n d a we d g ej ；如果一个顶点属于边界边则称此顶点为边界顶点( 或边界 点，b o l d l yv e r t e x ) ；至少包含一个边界顶点的面称为边界面( b o u n d s , f a c e ) 。 非边界的边、顶点和面分别称为内部边( h t e m a le d g e ) 、内部顶点( i n t e m a lv 酣e x ) 和内部面( i n t e m a f a c e ) 。 定义1 3 设单纯复形k = ( v ，e ，) ，对丁i _ 顶点i v ，如果存在j v ，使 得8 = ( i ，) e ，称e 为顶点i 的邻边，称为顶点i 的相邻顶点，f 和，称为e 的 端点。 1 3 2 三角网格的定义 定义1 4 吖= 暇，中) 称为三角网格，其中k 为单纯复形，中：v _ r 3 足顶 点到二维空间的单射函数。 因此，三角网格是由一些公共边和公共顶点相连的三角形组成的集台。这样， 三角网格模型的数据结构可以采用顶点表和三角形表组织，如图1 - 1 所示：其中 项点的信息记录顶点的位置、法向、材质等，而三角形表记录每一个三角形三个 顶点的标号。 磺点。顶点0 的信息 顶点1顶点1 的信息 顶点2顶点2 的信息 顶点i顶点i 日勺信息 顶点表 三角形0 顶点讳 顶点畸顶点屹 三角形i 顶点v 3 厦点u 顶点b 三角形2 顶点h 顶点顶点k 三角形i顶点h 顶点 顶点、j ， 三角形表 天，母大学硕- t 学位论文第一章绪论 1 4 本文的研究内容和论文的组织 根据前面的讨论可以看出，三角网格模型的表示在曲面造型技术中非常有价 值。本文主要就三角刚格模型的简化及其在三维造型中的应用作了详细论述。主 要内容包括： i 介绍了曲面简化技术的发展及其国内外的相关工作；对各种曲面简化算法做 了较为详细的论述。 2 提出了一个基于尖特征度的边折叠简化算法。其特点是：在g a r l a n d 的q e m 简 化算法的基础上，引入尖特征度的概念，不仅保留了模型的重要几何特征， 而且合理分配三角网格，在曲率大的区域稠密、平坦区域稀疏，简化效果更 好。 3 概述了细分曲面造型技术的发展及其优点，并详细的介绍基于三角彤网格的 两种细分模式：l o o p 细分模式和改进的b u t t e r f l y n 分模式。 4 论述了基于边折叠简化的细分曲面实现及其应用。阐述一个由稠密网格经过 边折叠简化构造蝶形( b u t t e r f l y ) 细分曲面的方法。网格简化时，应用尖特征 度并结台李现民的边折叠简化算法，构造控制网格；然后，用改进的蝶形细 分模式产生细分曲面，得到初始摸型的完好逼近；并给出构造连续多分辨率 模型及其在网络传输中的应用。 本文中的组织结构如下：第二章对曲面简化及其方法作了系统的总结，分析 了目前研究的热点和存在的问题；第三章绐出了一种改进的q e m 的简化算法， 即基于尖特征度的边折叠简化算法i 第蜉章介绍了细分曲面造型技术的发展及其 特点；第五章阐述了基于边折叠简化的细分曲面实现及其应用；第六章是本文的 结束语。 天津大学硕士学位论文 第一二章网格模，诬的简化方法综述 第二章网格模型的简化方法综述 本章主要介绍网格简化，对国内外在此方面的主要工作做一个详纲综述，包 括简化原则、误差测度和各种网格简化算法的比较f 3 】。 2 1 网格模型简化的意义 随着科学技术的进步，在讨算机图形学、虚拟现实、计算机辅助议计技术、 地理信息系统、医学图像系统等领域所构造和使用的模型越来越精细、越来越复 杂，这些复杂的模型动辄就产生数斟百万计的面片，而斯坦福大学的数字米开朗 基罗计划( d i g i t a lm i c h e m l g e l op r o j e c t ) = f 著名的大卫( d a v i d ) 雕像的三角面片更足 高达2 0 亿 4 。这些复杂的模型对计算机的存储容量、处理速度、绘制速度、传 输效率等都提出了很高的要求。然而存很多情况下，高分辨率的模型并不总是必 要的，模型的准确度以及需要处理的时间也要有一个折衷，囡此必须用一些相对 简单的模型来代替原始模型，这就是对模型进行简化。模型简化是指在保持原模 型几何形状不变的前提下，采用适当的算法减少该模型的而片数、边数和顶点数。 简化对于几何模型的存储、传输、处理，特别是对实时绘制有着重要的意义。早 在2 0 世纪7 0 年代，就有学者讨论网格模型的简化问题，然而直到9 0 年代以后， 网格简化才得到深入的研究并有了很多成功的应用。 2 2 简化原则和误差测度 2 2 i 简化原则 出于网格模型大部分由三角面片表示，而且即使原始模型不是三角面片，也 可以对其进行三角化，因此网格模型简化的本质是：在尽可能保持原始模型特 j f 的情况下，摄大限度地减少原始模型的三角形和顶点的数目。它通常包括两个原 则 5 t ) 顶点最少原则，即在给定以差上界的情况下，使得简化模犁的1 员点数 最少： 2 j 误差最小原! _ 、| j 给定简化填型的顶点个数，使得简化模犁 o 原始模挚 天津天学硕十学位论文 第章网格稹型的简化方法综述 之间的误差最小。 2 2 2 误差测度 误差测度是用来量化输入模型和输出模型的差异，它引导模型简化，使得简 化后的误差在用户允许误差范围之内。误差测度包括外观相似测度和儿何误差测 度 6 。外观相似测度用来计算原始模型与简化模型投影到视平面的差异，它最 符合人们的视觉习惯，但由于它需要从各个视点进行采样，计算量大，因此在实 际应用中通常用几何相似测度来代替。 一个经常用到的几何误差测度被定义为 ，、 占m x ( m t ，m 。) 2 m “【( 罢黔d ( 吖。) ，? 嚣o v ( m ，) ，j ， 其中dc 吖) 表示一个顶点v 到一个模型村的距离( 以( m ) = ? 珊肛一叫川f 是两个向 量的欧氏距离) ，这个误差用来测量两个模型之间的堆大偏差。 同样两个模型之间的平均偏差可以定义为 圪w ，m ，) 2 吉k 似：) + 亡k “j ( m ，) 在这里，和w ，分别是m ，和，的面积。 几何相似测度还有些其他类型的表述：如s c h r o d e r n j 用点到平面的平均距离 作为局部误差测度来控制顶点的删除 7 1 ，t u r k 采用的是曲率度量f 8 1 。 2 3 网格模型简化算法 网格模型简化算法分类有多种，如根据拓扑结构是否保持可阻分为拓扑结构 保持型 9 ，1 0 和非拓扑结构保持型 1 1 ；根据模型简化的过程可以分为遂步求精 1 2 ，13 和几何简化 7 ，1 4 ，1 5 1 ：根据误差可控性可分为误差受限 1 0 1 和误差不受隈 1 2 】；根据视点相关性可以分为视点无关的简化 9 ，1 2 和视点相关的简化f 1 6 ，1 7 1 。 需要说明的是，这些分类方法都难以囊括所有的简化算法，同刖有很多算法 彼此交叉。下面从静态简化到动态简化这个顺序分别介纠各种算法因为这种顺 序体现了简化算法发展的过程。 早期的模型简化算法大多属于静态简化，它是根据一定的精简原则，出复杂 模型构造出简单模型用于绘制，它只考虑模型自身的信息，与视点无关，电不能 恢复原模型的信息。静态简化瞍可以构造多分辨率模型，但是它要事先存储多个 1 i 同分辨章的近似模型，需要占用鞍多的内存而e l 在不同分辨率的模型进行切 换的川。关，由于相邻两层模型之i 可的面片数差别较大，冈此会引起跳跃的惑芷。 天津人学硕士学位亡文 第一章网播模，刊的简化方法综述 2 3 1 静态简化方法 2 3 1 1 顶点聚类法 j 厦点聚类方法 1 1 首先用个包围盒将原始模型包围起来，然后通过空间划 分将包围盒分成若干个区域，这样，原始模型的所有顶点就分别落在返些小区域 内，将区域类的顶点合并成一个新项点，再根据原始网格的拓扑关系对这些新顶 点进行三角化，就得到简化模型，其过程如图2 1 所示。这是一种通用的不保持 拓扑结构的简化算法，它可以处理任意拓扑类型的网格模型，且速度较| 夹。由于 这个方法是将模型的包围盒均匀分割，所以无法保持那些大于分割频率的特征。 图2 1 项点聚粪 2 3 1 2 区域台并法 同时新顶点的生成只是采取简单的加 权平均，而没有较好的误差控制，因 此这种方法生成模型的质量不高。周 昆等人采用了八叉树对阿格包围盒作 目适应划分，同时采用二次误差测度 来控制新顶点的生成f 1 8 。 k a j v i n 和t a y l o r j f 是了一种比较典型的区域合并方法 1 0 ，该方法选择一个三 角面为种子面，根据一定的准则将周围的面合并起来形成一个更大的面( 称为超 面) ，再将超面边界拉直，并对其重新三角化，从而达到面片简化的目的。这种 算法可以由用户自己控制简化模型的误差，且可以保持模型的拓扑结构，但是由 于无法避免带洞超面的产生，且重新三角剖分计算复杂，影响了算法的运行效率。 李捷、唐泽圣等人对此进行了改进，采用区域分割算法消除超面周界投影轮廓的 自相交，而避免了带洞超面的产生，冈此该算法的运行效率提高了1 倍 1 9 ，2 0 。 j o n a t h a nc o h e n 等人提出了一个简化| , ? ：k e ( s i m p l i f i c a t i o ne n v e l o p e s ) 的框架，该算法 可以保证简化在全局误差范围内进行，不改变原始模型的拓扑结构，同时可以很 好地保持原始模型的尖锐特征旧。 2 , 3 1 3 重新布点法 g r o gf u r k 在1 9 9 2 年提出了蓬新布点法( r e t i l i n g ) 8 ，算法先将m 用户指定数目 的项点根据各个三角面片的同积大v 、分布在模型表面r ，其次根据模型表面r 顺 点之州的斥力以使顶点在表面卜的分伟更均匀，然后将模型上的原始顾点弓新加 入的瑚，童混合在一起进行二角剖分最后将原始顶点一个个地册l 去，开及时地刑 天津犬学硕士学位论文 第二章网格模型的简化方法综述 删除顶点所造成的空洞进行i 角化。 2 3 1 4 逐步求精法 逐步求精方法首先给出个原始网格的逼近网格，然后逐步增加细节，并重 新进行局部三角化，直到近似模型达到用户满意的精度为止 】2 ，1 3 ，它包括贪婪 插入法和层次细分法。 贪婪插入法在每一次遍历过程中选择误差晟太的位置作为插入新顶点的位 置。r o b e r tj f o w l e r l j a m e s j l i t t l e 等人首先使用一个2 x 2 的滤波器来选择特征点 并进行三角化，然后使用多次遍历的并行贪婪插入f 2 1 。g a r l a n d 和h e e k b e r t 在1 9 9 5 年实现了高效准确的贪婪插入算法 2 2 】。 层次细分法是基于层次表示结构，采用分治策略来进行层次三角化，将模型 上的表面根据其复杂程度分层次地组织成一棵树，从而可以快速地给出指定分辨 率的模型。比较著名的细分模式包括c a t m u l l c l a r k 模式 2 3 ，l o o p 模式 2 4 以及 d o o s a b i n 模式 2 5 等。由于筠1 j 分方法不受控制网格拓扑的限制，可以对任意拓扑 网格进行曲面造型，而且其递归结构与小波和多分辨率分析有着密切联系 2 6 1 ， 撮近又有不少学者利用细分法构造多分辨率模型，其中有k o b b e h 的订模式f 2 7 l 、 l u i zv e l h o 和d e n i sz o n n 的4 8 模式 2 8 】、l e x i n gy i n g i d e n i sz o f i n 的非流形细分 2 9 等。 2 3 1 5 几何元素删除法 1 9 9 2 年，s c h r o e d e r 提出了顶点删除的网格简化方法f 7 1 ，此后，基于边折叠 f 1 4 ，3 0 、基于三角形删除 1 5 等几何元索删除的方法被相继提出。这些方法的共 同特点是以几何元素的删除实现模型的简化，即根据原模型的几何拓扑信息，在 保持定的几何误差的前提下册0 除对模型几何特征影响相对较小的几何“图 元”：( 点、边、面) 。下面将分别介绍顶点删除法、边折叠法( 顶点对的删除) 、三凭 形简化方法等。 ( 1 ) 顶点删除法 在二三角网格中，若顶点与它周围三角面片可以被认为是共面的( 这可以通过 设定点到平面距离的闽值来判断) 且遮一点的删除不会带来拓扑结构的改变， 那么就可将这一点删险，同时所有与该顶点相连的而均被从原始模型中删除，然 后对其邻域重新三角化，以填补l u 于这一点被删除所带来的空洞，如图2 - 2 昕示， 继续这种操作直到三角网格中无满足上述条件的顶点为止7 。 这种算法计算较快，也一；需要占用太多的内存，但是由于重新三角化需要将 局部表而投影到一个半面，这利一算法只适用于流形，而且它在保持表而的光，胃一陀 天津大学硕士学位论文第二= 章网格模型的简化方法综述 方面存在一定困难。实际上顶点删除与边折叠算法极为相似，通过边折叠来删 除顶点比重新三角化要鲁棒得多 6 。 圈2 - 2 顶点删除图2 。3 边折叠与点分裂 ( 2 ) 边折叠法 边折叠简化算法是指在每一次简化操作中以边作为被删除的基本几何元素 f 如图2 3 所示) 。在进行多次的选择性边折叠后，蕊片就可以被简化到我们想要的 任何程度了。点分裂是边折叠的逆变换，可以用来恢复被简化掉的信息。h o p p e 通过边折叠和点分裂构建了渐进网格( p r o g r e s s i v e m e s h ，简称p m ) 模型，实现了多 分辨率( m u l t i 。r e s o l u t i o n ) 的层次细节模型( 1 e v e lo f d e t a i l ，简称l o d ) 的实时生成 9 。 边折叠的关键是折叠的次序以及边折叠后耨顶点的位置。h o p p e 在1 9 9 3 年采 用能量优化的方式采确定折叠次序和新顶点的位置 1 4 1 ，能量优化计算复杂，所 需时间较长，但是生成模型的效果却是在所有简化方法中最好的。g a r l a n d 和 h e c k b e r t 在1 9 9 7 年提出了一种基于二次误差测度( q u a d r i ce r r o r m e t r i c ，简称q e m ) 的简化算法 3 0 。q e m 算法误差测度是基于顶点到平面的距离平方和，该算法速 度快，简化生成的模型质量仅次于h o p p e 的能量优化方法，是一种非常有效的简 化算法。h o p p e 将法向量、颜色以及纹理等信息加入到o e m 算法中，然后采用叫 作翼边( w e d g e ) 的数据结构来加以实现，也得到了较好的效果 3 1 。l i n d s t r o m 和 t u r k 在1 9 9 8 年用简化莳后体积和面积的变化作为误差测度，也得到了与0 e m 类 似的数学表达 3 2 】，这种方法在计算边折叠队列和新顶点的位置时只需要网格模 型面的连接信息和顶点的位置，所以此算法占用内存量小，运算速度快。李现民 采用改进的蝶形细分算法柬计算新顶点的位餮，效果较好，但是时州复杂度较离 2 】。 ( 3 ) 三角形折叠简化方法 三角形折叠简化方法是指，在简化时三角面作为被删除的基本，i 豢。它是边 折叠算法的延续，掘l 图2 。4 所示，次三角形折叠可以删除4 个三角形、两个顼点。 天津大学硕士学化论文第二章网格模型的简化方法综述 。媳_ 。，粥，。黧蕃鸳蒸纛 “”“” 于细分规则的三角形折叠方法f 3 6 。 2 3 1 6 小波分解 小波分解方法为层次细节模型提供了个完美的数学表达方式，它首先由 l o u n s b e r y 取l d e r o s e 在1 9 9 4 年提出f 2 6 1 。它的主要原理就是利用小波分析的方法将 一个三维模型分解成低分辨率部分和细节部分，低分辨率部分是原始模型的一个 子集，它的顶点为原始模型中对应顶点的邻域的加权平均，通常用低通滤波来实 现，因此表现为低频信号；细节部分通常包含抽象的小波系数，这些系数通过高 通率波来得到，表现为高频信号。重建过程就是通过选择适量的高频信号与低频 信号以合成相应精度的三维模型，通过略去其余的更高频分量来达到简化的效 果。这种方法简单、高效，但是它只适用于具有细分连通性的三角网格。1 9 9 5 年，m a r h i a se c k 等人改进了上述算法使其能够处理任意拓扑的网格 3 7 ，3 8 。 2 3 2 动态简化方法 动态简化的基本思想是：在模型的简化过程中，可咀