（计算机科学与技术专业论文）基于三维分割的网格简化算法.pdf

国防科技大学研究生院学位论文 摘要 随着科学技术的进步，在计算机图形学、虚拟现实、计算机辅助设计技术、地理信息 系统和医学图像等领域所构造和使用的模型越来越精细、越来越复杂，这些复杂的模型动 辄就产生数以百万计的面片，而斯坦福大学的数字米开朗基罗计划中著名的大卫( d a v i d ) 雕像的三角面片更高达2 0 亿。这些复杂的模型对计算机的存储容量、处理速度、绘制速 度、传输效率等都提出了很高的要求。然而在很多情况下，高分辨率的模型并不总是必要 的，模型的准确度以及需要处理的时间也要有一个折衷，因此必须用一些相对简单的模型 来代替原始模型，这就是对模型进行简化。 模型简化是指在保持原模型几何形状不变的前提下，采用适当的算法减少该模型的面 片数、边数和顶点数。网格简化对于几何模型的存储、传输、处理，特别是对实时绘制有 着重要的意义。 根据视点敏感的区域对渐进网格算法进行改进，本文提出了一种视点相关的渐近式网 格简化算法。在该算法中，根据能量函数的消耗提出了一种半边折叠简化操作，并利用预 判规则、堆排序以及局部更新等技术提高简化速度和效果。 然后，本文提出了一种基于有意义分割的网格自适应简化算法。由于人类识别物体时 习惯将复杂物体视为不同子部分的组合体，并倾向于把最小负曲率区域看成组成要素的边 界边。根据这一事实，本文提出了一种新型的网格自动分割算法。该算法基于顶点的最小 负曲率，通过确定特征区域，进而抽选区域骨架，而后基于骨架，提取候选的特征轮廓线。 再利用长度、中心性和与中轴线的空间关系等三个因素对轮廓线进行排序，基于捷径规则 进行闭合处理，完成网格模型的有意义分割。在网格分割的基础上，在前面的网格简化算 法中，对不同的点赋予不同级别的能量函数，从而获得自适应的网格简化结果。 实验表明，渐近式网格简化算法能尽量保留视觉敏感的区域，具有视觉感知的合理性。 基于有意义分割的网格自适应简化算法，不仅能够产生自然的视觉分割效果，而且具有很 好的性能。 关键字：网格简化，半边折叠，三维分割，自适应 第i 页 国防科技大学研究生院学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to f c o m p u t e rs c i e n c ea n dt e c h n o l o g y ，m o l ls o p h i s t i c a t e da n dr e a l i s t i c 3 dm o d e l sa 坞r e q u i r e di nm a n yf i e l d s ，s u c ha sc o m p u t e rg r a p h i c s ，v i r t u a lr e a l i t y ，c o m p u t e r a i d e dd e s i g n ，g e o g r a p h i c a li n f o r m a t i o ns y s t e ma n dm e d i c a li n l a g et e c h n o l o g y 。t h e r e f o r e , t h e c o m p l e x i t yo fm o d e l si sc a l c u l a t e db ym o l lt h a nm i l l i o n so ft r i a n g l e s ，i e ，t h ed a v i dm o d e l ， u s e di nd i g i t a lm i c h e l a n g e l op r o j e c ta ts t a n f o r du n i v c r i s t y c 姐r e a c hu pt ot w ob i l l i o nt r i a n g l e s m i l l i o n so ft r i a n g l e sa r er e q u i r e dt oc o n s t r u c ts u c hc o m p l e xm o d e l s - - u pt o2b i l l i o n t r i a n g l e sw e l lu s e d t om o d e lt h es c u l p t u r eo fd a v i di nt h em i c h e l a n g e l op r o j e c ta tt h es t a n d f o r d u n i v e r s i t y t h ec o m p l i c a t e dm o d e l sp r o p o s eg r e a tc h a l l e n g e st ot h es t o r a g ec a p c i t y ，p r o c e s s i n g p o w e r , r e n d i n gs p e e da n dt r a n s m i t t i n gr a t eo fc o m p u t e rs y s t e m h o w e v e r ，h i 【g hr e s o l u t i o ni sn o t a l w a y sn e c e s s a r yi ns o m ea p p l i c a t i o n sa n dt h e r ei sa t r a d e - o f f b e t w e e nr e s o l u t i o na n dp r o c e s s i n g t i m e s os i m p l i f i e dm o d e li su s e di ns o m eo a s e st or e p l a c ec o m p l e xo r i g i n a lm o d e l m e s h s i m p l i f i c a t i o n ，w h i c hr e d u e c e s t h em e s hc o m p l e x i t y , i st h et e c h n o l o g yt og e n e r a t es u c h s i m p l i f i e dm o d e l s u s i n gp r o p e ra l g o r i t h m s ，m e s hs i m p l i f i c a t i o nr e d u c e st h en u m b e ro fp o l y g o n s ，e d g e sa n d v e r t i c e so fam o d e lw h i l er e t a i n i n gi t ss h a p e ，a p p e a r a n c ea n do t h e rm o s ti m p o r t a n tf e a t u r e s m e s hs i m p l i f i c a t i o np l a y sav e r yi m p o r t a n tr o l ei nt h es t o r a g e ，t r a n s m i t t i n g ，p r o c e s s i n ga n d r e n d e r i n go f am o d e l m e s hs 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 gat h r e e - d i m e n s i o n a lp o l y g o n a lm o d e li n t oa s i m p l e rv e r s i o n i tr e d u c e st h en u m b e ro fp o l y g o n sn e e d e dt or e p r e s e n tam o d e lw h i l et r y i n gt o r e t a i nag o o da p p r o x i m a t i o nt ot h eo r i g i n a ls h a p ea n da p p e a r a n c e 。a n di ti sv e r yi m p o r t a n tf o r s t o r a g e ，t r a n s m i s s i o n ，p r o c e s s ，a n dr e a l - t i m er e n d e r i n g ht h i sp a p e r ，t h em e s h sp r o g r e s s i v e a d a p t i v es i m p l i f i c a t i o ni st h o r o u g h l yr e s e a r c h e db a s e do nm e s hs e g m e n t a t i o n , a n dt h em a i nw o r k a n dc o n t r i b u t i o n sw o u l db ea d d r e s s e da sf o l l o w ： c o n s i d e r i n gt h ee f f e c to fv i s u a ls e n s i t i v e n e s sa r e a s ，w ep r o p o s e d av i e w - d e p e n d e n t p r o g r e s s i v em u l t i r e s o l u t i o n m e s hs i m p l i f i c a t i o n a l g o r i t h m i nt h i sa l g o r i t h m ，a h a l fe d g e c o l l a p s eo p e r a t o ri si n t r o d u c e db a s eo nt h ep o w e rf u n c t i o n ，a n da s e r i eo f n e wt e c h n o l o g i e s ，s u c h a sp r e d e t e r m i n a t i o nr u l e r , h e a ps o r t i n ga n dl o c a lu p d a t e ，i sa d a p t e dt oi m p r o v et h es i m p l i f i e d p e r f o r m a n c e i na d d i t i o n ，a n o t h e ra d a p t i v em e s hs i m p l i f i c a t i o na p p r o a c hi sp r o p o s e d ，w h i c hi sb a s eo n t h em e a n i n g f u lm e s hs e g m e n t a t i o n a c t u a l l y ，p e o p l eu s u a l l ya s s u m et h ec o m p l e xo b j e c ta s s i m p l eb a s i ce l e m e n t sc o m b i n a t i o n , a n dt e n dt od i v i d e di t i n t os e v e r a lp a r t sb yt h er e g i o no f m i n i m i z en e g g i v ec u l n a t u r e a c c o r d i n gt ot h i sf a c t ，an e wa u t o m a t i cm e a n i n g f u lm e s h 第i i 页 国防科技大学研究生院学位论文 s e g m e n t a t i o nm e t h o di sp r o p o s e d t h em e t h o dc o n c e n t r a t e so nf e a t u r ec o n t o u r , g o t t e nf r o mt h e m i n i m an e g a t i v ec u r v a t u r ev a l u e ，f o rc u t t i n g b a s e do nm i n i m ar u l ea n dp a r ts a l i e n c et h e o r y f r o mt h ec o g n i t i v et h e o r y ，m ya p p r o a c hd i v i d e sam e s hi n t os a l i e n tp a r t sa l o n gt h ec o n c a v e d i s c o n t i n u i t yo ft h et a n g e n tp l a n e m yn o v e lm e t h o df i r s te x t r a f t sf e a t u r e st of m dc a n d i d a t e c o n t o u r s 。t h e nt h eo p e nc o n t o u r sa r ep r i o r i t i z e da n da u t o m a t i c a l l yc o m p l e t e dt of o r ml o o p s a r o u n dm e s h sp a r t s t h el o o pc o m p l e t i o ni sc o n s t r a i n e db yt w op a r a l l e lc u r i n gp l a n e s 。w h i c h a r es e l e c t e df r o mt h eo p e nf e a t u r ec o n t o u r so r i e n t e db o u n d a r yb o x o nt h eb a s i so ft h e s e g m e n t a t i o nr e s u l t s ，av a r i o u sl e v e lp o w e rf u n c t i o ni sa s s i g n e dt od i f f e r e n tt y p ev e r t i c e si nt h e b e f o r es i m p l i f i c a t i o na l g o r i t h m , a d d r e s s e di nc h a p t e rt w o ，t oo b t a i na d a p t i v em u l t i - r e s o l u t i o n e x p e r i m e n t sp r o v e dt h a tt h ep r o g r e s s i v em e s ha l g o r i t h mh a st h er e s o n a b l e n e s so fh u m a n p e r c e p t i o nw h i l ep r e s e r v i n gh u m a nv i s i o np e r f e r i n gr e g i o n s t h ea u t o m a t i ca d a p t i v em e s h s i m p l i c a t i o n a l g o r i t h m b a s e do n m e a n i n g f u ls e g a m e n t a f i o n c a ng e n e r a t en a t u r a lv i s u a l s e g m e n t a t i o nw i t hh i g hp e r f o r m a n c e k e yw o r d s ：m e s hs i m p l i f i c a t i o n ，h a l f - e d g ec o l l a p s e ，3 ds e g m e n t a t i o n 。a n d a d a p t a t i o n 第i i j 页 国防科技大学研究生院学位论文 表目录 表3 1 本章算法和l e e 算法的性能对比3 8 国防科技大学研究生院学位论文 图目录 图1 1 经过l o d 处理的网格，有不同的细节3 图1 2l o d 处理流程一3 图1 3d a v i d 雕像的三维几何模型，原始数据超过了2 0 亿个三角形，模型由八百万个 三角形组成，其存储量达到了3 2 g b y t e 5 图1 4 顶点删除7 图1 5 三角形折叠。7 图1 6 顶点聚类二9 图1 7t h o m a sf u n k h o u s e r 的分割图1 2 图2 1 三维图形学的核心处理流程1 4 图2 2 三角网格模型实例1 5 图2 3 三角网格模型简化图1 5 图2 4 边折叠与点分裂1 6 图2 5 半边折叠示例图1 8 图2 6 网格拓朴结构1 9 图2 7 半边折叠算法实现实验图2 3 图2 8 “8 ”字模型的简化结果2 3 图2 9b u d d y 模型2 5 图2 1 0h o r s e 模型的下腹部4 8 4 7 5v e r t e x 2 6 图2 1 1h o r s e 模型2 7 图2 1 2v e n u s 模型2 8 图3 1 根据分割结果对网格分割算法的分类3 0 图3 2 网格分割算法流程3 1 图3 3 特征轮廓线提取过程3 2 图3 。4 滞后阀值函数，其中，肼是下限，曰“是上限，c f ( v ) 是绝对主曲率。3 2 图3 5 不同模型的特征区域检测效果3 3 图3 6 轮廓线主方向与中轴线的空间关系的作用3 4 图3 7 特征轮廓线求取特征向量实例图3 5 图3 8l 形物体的分割3 5 图3 9 特征轮廓线闭合方法3 6 图3 1 0 已有特征对轮廓线闭合的影响。3 6 图3 1 1 算法分割效果实例3 7 图3 1 2 本文和l e e 算法分割实例的结果对比3 8 图3 1 3 基于分割的渐近式简化b u n n y 模型3 9 第1 v 页 国防科技大学研究生院学位论文 图3 1 4d r a g o n 模型的两类简化过程。3 9 第v 页 独创性声明 本人声昵所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：塞量至丝坌型鱼! 丑整登坚堡叁 学位论文作者签名：驻l日期：2 加占年j 月7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档。允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：堑兰丝坌邋鲍因整箍! 鲻邀 学位论文作者签名：重型日期：二。舌年，7 月7 日 作者指导教师签名：董! 三型日期：彩年月尹日 国防科技大学研究生院学位论文 第一章绪论 图形给人类与计算机的交流提供了一种最自然的方式，因为人们的高度发达的二维和 三维模式识别能力使我们可以快速、高效地理解和处理图像数据。在当今的许多设计、实 现和构筑过程中，图形所能提供给我们的信息实际上是不可缺少的。自从摄影术和电视发 明以来，计算机图形学是生成图像的最重要的方法。利用计算机，我们不仅可以制作有形 的“真实世界”物体的图像，还可以制作抽象的合成物体的图像。目前，即使是日常工作 当中不使用计算机的人也会在电视广告和电影特技等众多生活方面遇到计算机图形学。计 算机图形学已经深入我们的生活当中，成为必不可少一部分。 1 1 三维模型 计算机图形学始于计算机出现后不久，在硬拷贝绘图仪和阴极射线管荧光屏上显示数 据。在2 0 世纪8 0 年代早期，计算机图形学还是一个狭窄而又特殊的领域，这主要是由于 当时的硬件十分昂贵，而且缺乏易用和廉价的基于图形的应用程序。此后，带有内置式光 栅图形显示器的个人计算机使得人机交互中使用位图图形广为流传。位图是一个在屏幕上 由0 和l 表述的矩形点阵，每一个点称为一个象素或图像单元。位图图形一经出现，便很 快导致了廉价易用的基于图形应用程序的大量涌现。基于图形的用户界面使得数百万的新 用户得以驾驭简单、便宜的应用程序。例如，电子表格，字处理和辅助设计等。由于计算 机图形学的能力与功效几乎在所有领域都得到了承认，因此大量的图形硬件和软件系统得 到了开发。通用计算机甚至许多手持计算器支持二维及三维应用的图形功能已经是很普遍 的。我们可以在个人计算机上使用多种交互输入设备及图形软件包。对于高性能应用，也 有不少复杂的专用图形硬件系统和技术可供选择。然而随着计算机的发展，现在计算机图 形学已经发展到包括产生、存储和操作对象的模型与图像，它已经不是稀罕物，它是所有 计算机用户界面的一个组成部分，并且对于二维、三维和更高维对象的可视化是不可或缺 的。如今在科学、工程、教育、娱乐、广告、动画、军事、医学、商业等各种各样的领域 都离不开计算机图形学，图形也已成为一项交流思想、数据的关键技术。 现在已经开发了许多硬件设备和算法来改善生成图形的效率、真实感和速度。当前， 计算机图形学的趋势是将更多的物理原理结合进三维图形算法中，更好的模拟物体和照明 环境之间的复杂交互。利用计算机图形学，我们可以创建人工显示，进行基于计算机的“探 险”，用自然和直观的方法检验物体和现象，这种方法则利用了我们在视觉模式识别中高 度发达的技巧。 随着计算机图形学迅速普及，人们已经不满足在日常生活当中看到二维图形或者简单 的三维图形。另一方面，扫描以及相关建模技术的发展，使得三维模型的获取和构建更容 易，从而出现大量的三维模型。相对于二维图形，人们可以从任意角度浏览自己感兴趣部 第1 页 国防科技大学研究生院学位论文 分，因此更受人喜爱，用途更广泛。随着三维扫描技术和计算机图形学的发展以及计算机 性能的提高，三维几何模型已成为继声音、图像和视频之后的第4 种多媒体数据类型。对 三维几何模型的使用与研究在娱乐、医学、机械工程、工业应用等领域得到了认同，日益 发达的互联网技术为人们对三维模型的共享和处理提供了条件。 高精度的扫描测绘手段为复杂物体基于多边形网格表示的三维几何建模提供了新的 高效手段，但由于采样精度高，我们得到的三维几何模型的复杂度和数据量都在急剧增长， 由此建立起的三维模型的复杂程度远远超过了当前计算机实时的图形处理能力，而且计算 机和网络的普及使得这些三维模型在网上进行浏览、传输的要求越来越高。如何降低这些 模型的复杂度，减少图形系统需处理的多边形数目，实现实时交互，已经成为计算机图形 学研究中的一个重大课题。 1 2 课题背景 1 2 1 细节层次简介 9 0 年代初，从图形学方向上派生出虚拟现实和科学计算可视化等新的研究领域，这一 类交互式图形应用系统要求图形生成速度满足实时，但计算机所提供的计算能力往往不能 满足复杂三维场景的实时绘制目的。当我们要生具有相当真实感的场景的时候，由于场景 本身的复杂性，要实现实时性往往是不太可能的。我们必须从场景本身的几何特性入手， 通过适当的方法来简化场景的复杂性。因而研究人员提出了多种图形生成加速方法，细节 层次( l e v e lo f d e t a i l ，l o d ) 技术则是其中一种主要方法。l o d 技术是指对同一个场景或 场景中的物体，通过具有不同细节的描述方法得到一组模型，以供绘制时选择使用。由于 人们通常用多边形网格( 特别是三角形网格) 来描述场景中的图形物体，因此，l o d 技术 自动生成模型就转化为三维多边形网格的简化问题。实际应用发现，为物体提供不同的 l o d 描述是控制场景复杂度和加速图形绘制速度的一个非常有效的方法。 细节层次( l e v e lo f d e t a i l ) l o d 技术，是一种符合人的视觉特性的技术。我们知道， 当场景中的物体离观察者很远的时候，它们经过观察、投影变换后在屏幕上往往只是几个 像素甚至是一个像素。我们完全没有必要为这样的物体去绘制它的全部细节，我们可以适 当的合并一些三角形而不损失画面的视觉效果。它是根据一定的规则来简化物体的细节， 我们可以根据需要来选择不同细节程度的物体表达方式。例如：离观察者近的选择较高的 细节程度，反之选择较低的细节程度。 第2 页 国防科技大学研究生院学位论文 图i i 经过l o d 处理的网格 对于一般的应用，我们通常会为同一个物体建立几个不同细节层次的模型，如图1 2 的i s i s 雕像的模型，最左边的有最高的细节层度，而最右边的则经过了很大程度的简化。 图1 2 l o d 处理流程 实现l o d 算法时，除了如何对几何物体进行简化以外，还有一个很重要的问题就是 如何决定是否对一个物体进行简化，或者说在某个时刻该如何决定使用哪个层次细节度的 模型来表示物体。我们需要建立一个评价系统，由这个评价系统来决定要对物体简化到何 种层度。这种评价系统通常是视点相关的，离视点远的物体通常只需要较少的细节，反之 则需要比较多的细节。除此之外，物体本身的特性也必须考虑在内。比如说，一个平坦的 表面只需要很少的三角形就能较好表现出来。而一个凹凸不平的表面，理所当然是需要更 多的三角形去描绘的。 由上可知，l o d 算法其实并不很复杂，本文认为其关键处可概括如下： 第3 页 国防科技大学研究生院学位论文 1 数据的存储布局； 2 数据在内存中的布局必须要方便算法的实现，同时最好还要降低操作系统缺页中 断的次数，也就是降低内外存之间的数据交换的次数； 3 如何在生成连续的l o d 化的网格； 4 。在l o d 化过程中，要让两个不同层度的细节的区域之间能平滑的过度； 5 节点评价系统。 这个系统必须要使生成的网格能尽量的减少几何形变，尽量的使画面质量能接近全分 辨率时候的画面质量，同时还要保证实时性。 1 2 2l o d 和多分辨率模型技术的产生和发展 l o d 技术的产生可以追溯到1 9 7 6 年。当时，c l a r k 认为当物体覆盖屏幕的较小区域时， 可以使用该物体描述较粗的模型，并给出了一个用于可见面判断算法的几何层次模型，以 便对复杂场景进行快速绘制。1 9 9 2 年后，国外研究人员相继提出了多种多边形网格简化算 法和l o d 模型生成方法。目前国内也开展了一些卓有成效的研究工作，其中有些是对已 有的多边形网格算法进行改进，有些是提出新的多边形网格模型的简化方法。 l o d 技术的一个缺点是所需存储量大。当使用l o d 技术进行绘制时，有时需要在不 同的l o d 模型间进行切换，这样就需要生成多个l o d 模型。另一个缺点是离散l o d 技 术不支持模型间的连续过渡。为此，人们开始研究多分辨率模型技术。严格地讲，多分辨 率模型技术是指一种紧凑的模型表示方法，从这个表示方法中可以生成任意多个不同分辨 率的模型，一个典型的代表是1 9 9 6 年h o p p e 提出的渐进网格。不过，由于有些网格简化 方法能生成连续的l o d 模型。因而在一些文献中，也把这类模型统称为多分辨率造型。 细节层次( l o d ) 技术是解决硬件性能不够发达的技术产物，可以说它是一种过渡技 术，也就是说，随着硬件的提速，l o d 技术的要求会降低。但现阶段，细节层次( 【，o d ) 技术还是解决渲染速度瓶颈问题的最有效的技术手段之一。 基于细节层次( l o d ) 降低场景模型的复杂度是当前图形绘制的通用技术思路，它通 过减少场景的复杂度来提高绘制的速度。l o d 技术能保证在一定相似度、不影响画面感知 效果的条件下，从物体场景的几何模型出发，通过简化景物的表面细节来减少场景的几何 复杂性，也就减少了真实图形学算法需要绘制的场景面片数目，从而提高绘制算法的效率， 满足实时的要求。 迄今为止，本地l o d 简化技术已趋于成熟，层次式点聚合和层次式动态简化算法已 被业界接受，并出现a p i 级别的g l o d l l 方法，测量误差的研究重点也从几何逼真度转移 到感知逼真度问题。故本课题将在感知逼真的前提下，扩展g l o d 应用于远程绘制领域， 基于层次式结构提出适用于远程绘制领域的渐进细节1 2 等级算法。 第4 页 国防科技大学研究生院学位论文 一方面，随着科学技术的进步，对于计算机图形学、虚拟现实、计算机辅助设计技术、 地理信息系统、医学图像系统等领域所使用的三维几何模型的复杂度和清晰度成倍增加。 另一方面伴随着三维激光测距和建模技术的不断发展，获得真实物体的三维模型变得 越来越容易。从小型的零件、商品，到人体、雕塑，再到大型的建筑、街道，甚至城市， 三维网格模型的精度和规模都在快速提高，随之急剧增长的就是模型的数据量。目前包含 数以百万计三角形的模型已不鲜见，而像美国斯坦福大学著名的数字米开朗基罗工程( t h e d i g i t a lm i c h e l a n g e l op r o j e c t ) p 】中采集的几尊大型雕像的三维模型，都是由数以亿计的三角 形组成，其数据存储量达到了g b y t e 量级。这些复杂的三维几何模型对计算机的存储容量、 处理速度、绘制速度、传输效率等都提出了很高的要求 圈1 3d a v i d 雕像的三维几何模型，原始数据超过了2 0 亿个三角形，模型由八百万个三角形组成，其存 储量达到了3 2 g b y t e 与此同时，由于计算机硬件成本的不断降低，越来越多的用户在普通电脑上对大量的 三维模型进行浏览、编辑的需求不断提高。当今是网络的时代，网络在世界各地的人们之 间形成了一座沟通的桥梁。越来越多的用户希望在网络上自由地传输复杂的三维模型。于 是，三维模型数据量的不断增长与计算机有限的计算能力和网络带宽限制之间就形成了异 常尖锐的矛盾。 然而在很多情况下，并不是任何时刻都需要高分辨率的三维几何模型。例如在网络传 第5 页 国防科技大学研究生院学位论文 输过程当中，当用户在网上查询所需的某个图像的时候，那么在数据传输过程当中可以先 了解图像的轮廓，如果不是所要查询的那个图像，则可以快速浏览下一个图像，这样可以 节约时间和网络带宽。在科幻电影和三维游戏中，许许多多高复杂的三维模型要耗费大量 的软、硬件资源，在实际当中，并不是所有的三维模型都需要最高精度的显示。譬如：在 远端场景中出现的三维模型就不需要表现得像近端那样具有高清晰度，像科幻电影星球 大战中远端的宇宙飞船就表现得非常简单，而近端的宇宙飞船则十分精细，因为人的肉 眼只着重关注近距离的事物，而对于远处的事物无需精细。 所以，高分辨率的模型并不总是必要的，模型的准确度以及需要处理的时间也要有一 个折衷。因此可以根据用户的需要，对三维模型的不同区域采用不同的分辨率来表示，从 而用尽可能少的数据为用户提供了足够的细节，这就是模型简化。 1 3 三角网格简化 目前，由于网格模型大部分由三角网格表示，因此几何模型的简化是指在保持原几何 模型的基本几何形状不变的前提下，采用适当的简化算法减少该模型的面片数、边数和顶 点数。几何模型的简化对于几何模型的存储、传输、处理，特别是对实时绘制有着重要的 意义。早在2 0 世纪7 0 年代，就有学者讨论网格模型的简化问题【4 】，然而直到9 0 年代以后， 网格简化才得到深入的研究，并有了很多成功的应用。至今，基于网格简化的各种简化算 法相继提出1 5 】。网格模型化简算法有多种分类，例如：根据拓扑结构是否保持，可以分为 拓扑结构保持型和非拓扑结构保持型；根据模型简化的过程，可以分为逐步求精和几何化 简；根据误差可控性，可分为误差受限和误差不受限：根据视点相关性，可以分为视点无 关的化简和视点相关的化简。 需要说明的是，这些分类方法都难以囊括所有的化简算法，同时又有很多算法彼此交 叉。本文首先介绍面片化简的原则和误差测度，然后从静态化简到动态化简这个顺序分别 介绍各种算法，因为按这种顺序介绍，体现了化简算法发展的过程。 由于网格模型大部分由三角面片表示，而且即使原始模型不是三角面片，也可以对其 进行三角化，因此网格模型简化的本质是在尽可能保持原始模型特征的情况下，最大限度 地减少原始模型的三角形和顶点的数目。它通常包括两个简化原则：顶点最少原则，即在 给定误差上界的情况下，使得简化模型的顶点数最少；误差最小原则，给定简化模型的顶 点个数，使得简化模型与原始模型之间的误差最小。我们的方法适用于三角网格模型。 1 3 1 几何元素删除 1 9 9 2 年，s c h r o c d e r 提出了顶点删除的网格简化方法 6 1 ，此后，边折叠m 、三角形删除 嗍等几何元素删除的方法被陆续提出。这些方法的共同特点是基于几何元素的删除而实现 的简化，即根据原模型的几何拓扑信息，在保持一定的几何误差的前提下，删除一些几何 第6 页 国防科技大学研究生院学位论文 图元( 点、边、面) ，而对模型几何特征影响较小。在三角网格中，若一顶点与它周围三 角面片可以被认为是共面的( 这可以通过设定点到平面距离的阈值来判断) 且这一点的删 除不会带来拓扑结构的改变，那么就可将这一点删除，同时所有与该顶点相连的面均被从 原始模型中删除，然后对其邻域重新三角化，以填补由于这一点被删除所带来的空洞。 妒一妒 图1 4 顶点删除 s c h r o e d e r 的顶点删除算法1 6 1 就是通过删除满足距离或者角度标准的顶点来减少三角角 网格的复杂度，但删除顶点留下的空洞要重新三角化填补。 三角形折叠简化方法是指：在简化时三角形作为被删除的基本元素。它是边折叠算法 的延续。h a m a n n 将三角形的权重定义为等角度( e q u i a n g u l a r i t y ) 与曲率的乘积，然后对 网格模型上的所有三角形按权重进行排序，并依次折叠，这样细长且低曲率的面首先被删 除嘲；t r a ns g i e n g 等人也提出类似的三角形折叠简化算法，他们定义每个三角形的权重为 该三角面的面积与曲率等因素的乘积 9 1 ，这种算法复杂度较高，但是它可以较好地保持外 形；i s l e r 等人则将边折叠与三角形折叠结合起来构造了半实时多分辨率模型【10 】；周昆等人 将三角形折叠与q e m 算法结合起来，并给出了一种传递简化误差的方法【1 1 1 ；另外，根据 细分曲面的特性，李桂清等人给出了一种基于细分规则的三角形折叠方法【1 2 l ，国内在这方 面的工作还有文献1 1 3 】等。 1 3 2 小波分解 母日母 图1 5 三角形折叠 l o u n s b e r y 和d e r o s e 在1 9 9 4 年提出的小波分解方法为层次细节模型提供了一个完美 的数学表达方式t 1 4 1 ，它可以将一个表面模型分解成一个基本形状加上一系列顺序的表面细 节。从原始模型中删去不重要的细节信息就可以得到一个逼近模型。l o u n s b e r y 等提出了 任意拓扑类型表面上的多分辨率分析( m u l t i - - r e s o l u t i o na n a l y s i s ：m r a ) 概念，它的主 第7 页 国防科技大学研究生院学位论文 要原理就是利用小波分析的方法将一个三维模型分解成低分辨率部分和细节部分。低分辨 率部分是原始模型的一个子集，它的顶点为原始模型中对应顶点的邻域的加权平均，通常 用低通滤波来实现，因此表现为低频信号：细节部分通常包含抽象的小波系数，这些系数 通过高通率波来得到，表现为高频信号。重建过程就是通过选择适量的高频信号与低频信 号以合成相应精度的三维模型，通过省略其余的更高频分量来达到简化的效果。这种方法 非常简单，而且高效。但是小波方法对网格的几何压缩在几何拓扑方面都是有损的，而且 通过小波分解得到的模型的质量并不高，并且逼近模型无法完全重建出原始模型，特别是 当表面上存在尖锐的折痕时表现很差。 小波分析是一种信号的时间尺度分析方法，它具有多分辨率分析的特点，而且在时频 两个领域都具有表征信号局部特征的能力。利用球面小波可以方便地进行地形数据压缩以 及计算等。 小波分析在图形学中的应用除了面片化简以外，还广泛地应用于面片压缩、面片优化、 面片编辑以及建立多分辨率细节模型等。 1 3 3 动态化简 动态化简的基本思想是：在模型的化简过程中，可以实时地得到具有所需要的分辨率 的近似模型。每个模型的化简程度由模型之外的因素决定，例如视点。动态化简一般是通 过一些简单的局部的几何变换来实现，从而生成具有连续的不同分辨率的近似模型。动态 化简是静态化简的延续，它的很多基本操作采用的是静态化简的方法。 1 3 3 1 层次表示法 i s l e r 等人提出了一种混合方法来实现半实时的层次细节表示【l o l ，该算法预先产生几个 关键的简化模型，并对其中的三角面按视觉重要度排序，在实时绘制中，选择一个比所需 分辨率高的最简的逼近模型，并对该逼近模型按重要度从d , n 大的顺序删除三角面，直到 满足当前精度为止，这样可以部分地解决计算量大的问题。 r r o n f a r d 首先对每条边定义由于它的删除所造成的简化网格模型与原始网格模型之 间的几何偏差，并将其按照从小到大进行排序，然后根据用户对模型复杂程度的需要，依 次进行边删除操作，这个算法可以生成原始网格一系列连续的简化模型【l ”。 1 3 3 2 渐进网格法 在动态化简中最著名的算法当属h o p p e 在s i g g r a p h 9 6 上提出的p m 算法1 1 6 】，p m 算法以边折叠和点分裂为基本操作，记录了模型简化过程中原顶点和新顶点位置以及顶点 间的连接关系的变动信息，从而生成了一个由原始模型的最简化模型和一系列简化信息组 成的p m 表示模式。p m 可以把任意拓扑网格表示为一种高效、无损且具有连续分辨率的 编码。在实时绘制时，通过逆向跟踪简化信息序列，对每条简化信息执行点分裂逆操作， 第8 页 国防科技大学研究生院学位论文 可以逐步恢复所删除的模型细节，实时得到原始模型的连续精度的简化模型，由此实现了 l o d 模型的平滑过渡。p m 很大程度上克服了以往模型的平滑过渡方面的不足，可以支持 不同细节的网格模型的实时生成。但是在实现同一网格不同区域多分辨率的细节的实时生 成方面，p m 仍缺乏有力的数据结构的支持，同时由于边删除的先后顺序与边的几何拓扑 信息无关，因此在模型恢复的过程中必须进行逐一判断，很难实现l o d 模型的实时生成。 陶志良针对p m 的二义性，提出了支持快速恢复的可逆递进网格【1 。”。费广正则利用递 进网格进行多层次模型编辑【1 8 1 。 1 3 3 3 基于视点的化简方法 1 9 9 6 年，j u l i e c x i a 提出了一种实时的、基于视点的三角网格模型简化算法【1 9 1 ，该算 法可以实时的在同一模型的不同区域选择不同的精度层次；h o p p e 定义了一个基于视锥模 型表面法向和屏幕空间几何误差的细化标准，该标准包括视锥原则、面的方向性原则和屏 幕空间几何误差原则，并利用此准则进行选择性的边折叠和点分裂，建立多分辨率的模型 2 0 1 ；d a v i dl u e b k e 等人采用八叉树将空间进行划分，当一个八叉树节点所对应空间的体积 投影到屏幕上小于指定范围时，就将这个节点中的所有顶点折叠在一起，并删除所有的退 化多边形1 2 1 , 2 2 1 。 1 3 4 顶点聚类 顶点聚类方法首先用一个包围盒将原始模型包围起来，然后通过空间划分将包围盒分 成若干个区域。这样，原始模型的所有顶点就分别落在这些小区域内，将区域类的顶点合 并成一个新顶点，再根据原始网格的拓扑关系对这些新顶点进行三角化，就得到简化模型。 这是一种通用的不保持拓扑结构的简化算法，它可以处理任意拓扑类型的网格模型，且速 度较快。由于这