（应用数学专业论文）带法向量的曲面简化.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果论文中 除了特别加以标注和致谢的地方外不包含其他入或其它机构f i 经发表或撰写 过的研究成果其他同志对本研究的启发和所做的贡献均已在论文中作了明确 的声明并表示了谢意 作者签名： 掣日期卑叫 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定即：学校有权保 留送交论文的复露粹，允许论文被查阕和借阕：学校可以公布论文的全部或部 分内容可以采用影印、缩印或其它复制手段保存论文保密的论文在解密后 遵守此规定 艇日期：丑珥 复旦大学理学硕士学位论文 摘要 随着三维扫描和计算机图形学应用的不断发展，人们对图形的真实感和复 杂度要求也越来越高，图形的数据量也在不断增加，因此对图形的简化变得越来 越重要。论文首先对曲面简化方法做了大体的介绍。随后为了在简化的同时考虑 简化后图形的显示效果，本文提出了一种网格曲面简化方法：带法向量的曲面简 化为了得到好的简化显示效果，在简化的过程中考虑保持曲面特征和简化后曲 面顶点法向量的计算。在第三章，介绍了特征的准确定义，并介绍了特征提取算 法，并在特征提取的算法中，介绍了一种计算网格曲面顶点法向量的比较好的方 法。在第四章，利用第三章中的方法提取出来曲面特征线，把特征加到网格曲面 中，使在简化的过程中保留了曲面的重要特征，然后提出曲面简化的具体方法和 步骤，并在简化的同时计算简化过程中曲面顶点的法向量，在法向量的计算上作 者提出了法向量的经纬度表示，利用法向量的经纬度表示，为曲面顶点法向量的 计算提出了显式表达式。并且简化过程中法向量的计算使得简化后图形顶点的法 向量带有原图形的重要信息，因此可以利用法向量来对简化后图形进行加细。最 终的实验结果表明，通过保持曲面特征和简化过程中法向量的计算使得简化模 型，不仅减少了原图形的数据量，并且在保持较小几何误差的同时，在最终简化 曲面的显示上得到好的显示效果。 关键词：曲面简化曲面特征简单三角剖分经纬度表示加细显示效果 复旦大学理学硕士学位论文 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fl a s e rr a n g es c r u n e r sa n dc o m p u t e rg r a p h i c s ， i n c r e a s i n gd e m a n dc o m p l e x i t ya n d3 do f c o m p u t e rg r a p h i c s ，m o r ea n dm o r eg r a p h i c s d a t aa r en e e d e dt or e n d e ro b j e c t s s os b r f a c es i m p l i f i c a t i o ni sb e c o m i n gm o r ea n d m o r ei m p o r t a n t a tf i r s t , t h i sp a p e rp r e s e n t st h eb a c k g r o u n do fs u l - f a c es i m p l i f i c a t i o n t h e ni n o r d e rt op r e s e r v eg o o dd i s p l a ye f f e c t , as u r f a c es i m p l i f i c a t i o nm e t h o do f3 dm e s hi s p r e s e n t e d , w h i c hc a l lp r e s e r v et h ef e a t u r eo f o b j e c t sa n dc a l c u l a t en o r m a ld i r e c t i o n a t c h a p t e rt h r e e ，t h ed e t e c t i o no f s u r f a c ef e a t u r eo nm e s hi si n t r o d u c e d , s u r f a c ef e a t u r ei s d e f i n e da n dt h ea l g o r i t h mo fs u l f a c ef e a t u r ed e t e c t i o ni sp r e s e n t e d a l s oh o wt o c a l c u l a t en o r m a lv e c t o ro ft h eo r i g i n j a ls u r f a c ei si n t r o d u c e d a tc h a p t e rf o u r , a d d i n g t h es u r f a c ef e a t u r ew h i c hi sd e t e c t e da tc m p t e rt h r e et ot h eo r i g i n a ls u r f a c e ，t h e s i m p l i f i c a t i o na l g o r i t h mc a np r e s e r v ei m p o r t a n tf e a t u r eo fo r i g i n a l 文妇t h ed e t a i l o ft h e s i m p l i f i c a t i o na l g o r i t h m i s p r e s e n t e d a l o n g w i t ht h e s i m p l i f i c a t i o n , l o n g i t u d e l a t i t u d ee x p r e s s i o n t 0c a l c u l a t en o r m a ld i r e c t i o ni s p r o v i d e d a n d l o n g i t u d e - l a t i t u d ee x p r e s s i o n 啪e a s i l yc a l c u l a t et h en o r m a lv e c t o ro fn e wv e r t i c e s t h en o r m a lv e c t o rw h i c hi sc a l c u l a t e di nt h es i m p l i f i c a t i o na l g o r i t h mc a np r o v i d e i m p o r t a n ti n f o r m a t i o no ft h eo r i g i n a ls u r f a c e , i tc a na l s ob eu s e di nr e f i n i n gt h e s i m p l i f i e ds 1 1 l f a e e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a to u rm e t h o dc a l ln o to n l y r e d u c eg r a p h i c sd a t aa n dp r e s e r v el e s sg e o m e t r i ce r r o r , b u ta l s op r o v i d eag o o d d i s p l a ye r i e c t k e y w o r d s ：s u r f a c es i m p l i f i c a t i o n , s i l l - f a c ef e a t u r e ，s i m p l et r i a n g u l a t i o n ， l o n g i t u d e l a t i t u d ee x p r e s s i o n , r e f i n e ，d i s p l a ye f f e c t 2 复旦大学理学硕士学位论文 1 1 选题背景与意义 第一章引言 计算机图形学在许多领域都有广泛的应用，如：动画、可视化和虚拟现实。 但随着三维扫描技术的不断发展和计算机图形学的应用的不断深入，人们对图形 的真实感要求也越来越高，这些应用不仅需要高度真实的复杂图形，而且还要响 应用户的实时交互操作。但是随着图形复杂度和真实感的提高，所需要的图形数 据量也随之增加，而有些应用的数据量远远超过了当前计算机图形硬件的实时处 理能力。例如斯坦福大学的数字米开朗基罗计划( d i g i t a lm i c h e l a n g e l o p r o j e c t ) 中著名的大卫( d a v i d ) 雕像的三角形面片更是高达2 0 亿o l 。因此为 了解决真实感和实时交互性之间的矛盾，需要对图形进行一定程度的简化。模型 简化是指在保持原模型几何形状不变的前提下，采用适当的算法减少该模型的面 片数，边数和顶点数。简化对于几何模型的存储、传输、处理，以及实时绘制都 有重要的意义。 例如近年来，文物保护工作得到越来越多的重视，为了永久保存文物的现存 样貌，需要对一些文物进行三维扫描和建模。由于三维模型的数据量也在急剧增 加，为了得到模型的展示效果，需要对模型进行简化。简化的目的不仅是为了减 少数据量，以方便实时交互操作，而且还要考虑模型的简化显示效果。 本文由此提出一种曲面简化算法，在简化的同时不仅减少数据量，保持较小 的几何误差，而且在简化的同时提出保持曲面特征和简化过程中法向量的计算， 来得到曲面简化模型好的显示效果。 1 2 研究内容和成果 虽然学者们在曲面简化方面做了大量的研究，并得到许多不错的简化算法 1 2 0 r a l ，但大部分的研究都集中在减少数据量并保持较小的几何误差上，在简化的 同时考虑保持好的显示效果的研究比较少。本文提出的简化方法，为了得到简化 后图形好的显示效果，简化时考虑保持曲面特征和简化过程中顶点法向量的计 复旦大学理学硕士学位论文 算。 第二章，大概介绍一下常用的曲面简化方法，主要是顶点删除、顶点聚合和 迭代边收缩方法。 第三章，介绍了什么是特征，以及特征的提取。曲面特征 1 3 - 1 7 1 反映了曲面 图形的重要信息，因此在简化的同时，考虑保持住曲面的特征，对简化后的图形 来说就会保留原曲面图形的重要形状信息。因此本文介绍s h i ny o s h i z a w a 等提 出的特征提取方法 t 3 1 提取出特征，为第四章作者的曲面简化算法做准备。 第四章，详细说明作者的工作：带法向量的曲面简化。 首先，把特征加到网格曲面中。最近几年保特征简化的研究也越来越热， 如s h i ny o s h i z a w a 等在提取特征的时候考虑保特征的简化，但这样的简化会 使在特征附近网格比较稠密，离特征较远的地方网格比较稀少，得到的效果不很 理想。本文提出的加特征的方法就解决了这个问题。 然后，介绍作者的曲面简化方法。包括计算收缩权重，收缩方法和收缩准则， 并在简化过程中计算顶点的法向量，而不是在简化后才计算顶点的法向量，这样 可以使简化后图形的法向量带有原图形的一些重要信息，并且可以利用法向量带 有的信息来对简化后图形进行一定程度的加细。但很少有学者在简化的过程中考 虑法向量的计算。本文提出的简化算法在简化的过程中利用法向量的经纬度表示 来比较容易的计算出顶点的法向量，并且利用法向量的经纬度表示来加细显示最 终的图形。 最后，用几组三维模型来展示本文简化方法的效果，通过具体图形，可以看 出本文的简化方法得到比较好的显示效果。 4 复旦大学理学硕士学位论文 第二章几种主要的曲面简化方法 曲面简化经过多年的研究已经出现了很多有效的算法，简化算法也分为很多 种，如根据拓扑结构是否保持可以分为拓扑结构保持型 2 3 1 和非拓扑结构保持型 【4 l ；根据模型简化的过程可以分为逐步求精嗍和几何化简t 6 , 7 1 ；根据误差可控性 可分为误差受限和误差不受限 6 1 ；根据视点相关性可以分为视点无关的简化 2 , 6 1 和视点相关的简化【8 】。需要说明的是，很多算法彼此相互交叉 在图形系统中，三角形面片是最通用的绘图元语，一方面三角形的基本联结 关系简单，另一方面，所有的图形库和图形硬件都能够很方便的处理三角形网格。 本文中的曲面模型都是以三角形网格曲面来表示的，因此研究模型的简化算法主 要是研究三角形网格的简化算法。 因此本文介绍和三角形网格曲面相关的几种最常用的简化方法：顶点删除、 顶点聚合和迭代边收缩。 2 1 顶点删除 在顶点删除的网格简化方面，s c h r o e d e r 等1 9 】提出了有效的算法。 在三角网格中，若一顶点与它周围三角面片可以被认为是共面的( 这可以通 过设定点到平面距离的阀值来判断) ，且这一点的删除不会带来拓扑结构的改变， 那么可以将这一点删除，同时所有与该顶点相连的面均被从原始模型中删除，然 后对其邻域重新三角化，以填补由于这一点被删除所带来的空洞，如图2 1 所示， 继续这种操作直到三角网格中无满足上述条件的顶点为止。 这种算法计算较快，也不需要占用太多的内存，但是由于重新三角化需要将 局部表面投影到一个平面，这种算法只适用于流形，而且它在保持表面的光滑性 方面存在一定困难。 复旦大学理学硕士学位论文 咿一妒 图2 1 顶点删除 2 2 顶点聚合 在顶点聚合的网格简化方面，r o s s i g n a c 等i 伸】提出了对任意多边形网格进行 简化的算法。该算法首先用一个包围盒将原始模型包围起来，然后通过空间划分 将包围盒分成若干个区域，这样，原始模型的所有顶点就分别落在这些小区域内， 将区域内的顶点合并成一个新的顶点，再根据原始网格的拓扑关系对这些新顶点 进行三角化，就得到简化模型，其过程如图2 2 所示。 这是一种通用的不保持拓扑结构的简化算法，他可以处理任意拓扑类型的网格模 型，且速度较快。由于这个方法是将模型的包围盒均匀分割，所以无法保持那些 大于分割频率的特征，同时新顶点的生成只是采用简单的加权平均，而没有较好 的误差控制，因此这种方法生成模型的质量不高。 聚合 边收缩简化算法是指，在每一次收缩中以边作为被删除的基本几何元素( 如 图2 3 所示) 。在进行多次的选择性边收缩后，面片就可以被简化到想要的任何 程度了。点分裂是边收缩的逆变换，可以用来恢复被简化点的信息。h o p p e 2 1 通 过边收缩和点分裂构建了渐进网格( p r o g r e s s i v em e s h ，简称蹦) 模型，实现 6 复旦大学理学硕士学位论文 了多分辨率( m u l t i - r e s o l u t i o n ) 的层次细节模型( 1 e v e lo fd e t a i l 简称l o d ) 的实时生成。 近年来研究的比较多的是迭代边收缩，此方法关键在于如何选择边进行收 缩，以及收缩后新顶点的位置，其中以g a r l a n d 等【1 1 1 在1 9 9 7 年提出的基于二次 误差测度( q u a d r i c e r r o rm e t r i c ，简称q e m ) 的化简方法最具代表性。q 跚 算法误差测度是基于顶点到平面的距离平方和，该算法速度快，是一种非常有效 的简化算法 图2 3 边收缩与点分裂 7 复旦大学理学硕士学位论文 第三章特征提取 曲面特征( 也即曲面折痕，s u r f a c ec r e a s e s ) 在直觉上，是指曲面法向量 有尖锐变化的点组成的曲线。实际上，曲面特征是通过沿曲率线的曲率极值定义 的。 曲面特征反应曲面的重要信息，在计算机图形学和几何模型上都应用广泛。 特征在自由模型曲面质量控制、图像和数据分析、人脸识别，医学图像分析等上 都有广泛的研究。 3 1 特征的定义 考虑一个光滑曲面，k 和k 是它的最大和最小主曲率，k n 七曲，f 。和 t m 是相应的主方向，p 一和e 血是主曲率沿主方向的导数： e 。：船。a 。，8 曲= 徼面a 血 定义凸波峰线： 满足p 。= o ，a p 一西。 i 七。i 的点组成的线。 凹波峰线： 满足e m i l - = o ，& m o t t o 0 ，k m ik a ( 巧) j 对j = 1 、2 ，且e 一( 巧) p 一( ) v ov 点位置由f r r - + ( 卜神r z 确定其中矿为权重萨瓦导瓦， 形巴分别为v 。，r ：的收缩权重( 见4 2 ) 。 2 对特征边y 。r 2 。其中为特征点，进行半一边收缩：即把v l ，p ：收缩 到r 2 ，记为：( y 。，r ：) 一 r 2 。( 关于半一边收缩请参考 1 6 ) 4 3 2 收缩准则 对网格曲面中的每个普通点以收缩权重从小到大进行排序( 即：特征点不参 与排序) ，称这个排序为收缩权重列表。然后迭代的取出收缩权重列表中的最小 点，考虑进行迭代边收缩。 无特征点的边收缩： 取出排序中的最小点r ，如果r 的一环邻域内没有特征点，考虑一环邻 域点的收缩权重，找出_ 一环邻域收缩权重最小的点，比如为，则_ 和v j 进 行边收缩，_ 和y 收缩到新点巧即( p ，矿，) 一 v ；，其中巧2 即。+ ( 卜厣) r ，矿 为权重( 见4 3 1 ) 更新q 和吒一环邻域所有点的收缩权重，并更新这些点在 收缩权重列表中的位置a 最后计算收缩后吒的法向量( 见4 4 ) 有特征点的边收缩： 如果_ 的一环邻域内有特征点，特征点的个数为1 ，设特征点为r ，则v ， 和y 进行半一边收缩，即( _ ，y ，) 一 ”，更新收缩后y j 的一环邻域所有普通点的 权重，并更新这些点在收缩权重列表中的位置，最后计算收缩后r j 的法向量( 见 4 4 ) ；如果r ，的一环邻域内有多于1 个的特征点。则和离p ，最近的特征点进 行半一边收缩。 4 3 3 收缩过程中的细节考虑 在有特征和无特征的边收缩过程中，三角形面片在收缩前后发生变化。一般 复旦大学理学硕士学位论文 情况下，收缩的地方相对曲率较小收缩前后三角形的法向量不会发生太大的变 化，但个别情况法向量会发生反转。而且在边收缩过程中，个别情况下两个三角 形会发生面重合。因此需要在收缩过程中考虑收缩的细节。 法向量的反转： 图4 5 法向量的反转 如图4 5 ，边”2v 3 收缩到h ，收缩前v ov lv 2 收缩后变为v ov i h ，法向量 发生反转。在收缩过程中如果法向量发生反转，则说明收缩对原图形改变比较大， 则这种情况下，不适宜进行此次边收缩。因此跳过此次边收缩，考虑收缩权重列 表中的下一个权重最小的顶点进行边收缩。 三角形面重合： 图4 6三角形面重合 如果在收缩过程中，收缩边的一环邻域中的顶点，其一环邻域顶点的个数为 3 ，则这样情况下，边收缩会发生三角形面重合。如图4 6 ，边hv ：收缩到v 3 ， 7 i 、v 2 的一环邻域的顶点v 4 ，其一环邻域的顶点个数为3 ，则收缩前v ov h 和 复旦大学理学硕士学位论文 v oh3 2 ，收缩后发生面重合，即都为v ov 码。如果在边收缩过程中发生面 重合r 则收缩后删除重合的两个三角形，在图4 6 中即为删除v 0 _ b ( 两个 三角形重合成一个) 。这样边收缩后三角形网格不会出现畸形。 4 4 计算收缩后点的法向量 假设顶点y 的单位法向量为n ( n 。，以：，甩，) ，此法向量在单位球上对应的经纬 r g 为( e ，妒) 其中( 口，p ) e 一石，万 _ 詈，三 单位法向量和单位球上的 经纬度可以相互转化。利用法p - 量的经纬度表示来计算收缩后顶点的法向量。 由法向量似愧，捍：，玛) 计算对应的经纬度( 口，妒) ： a r c 切n 生 啊 0 啊 缸c t a l l 垒+ 石 确 以 a f c 锄j 一万 惕 石 2 万 2 o 2 a r c s l n n 3 玛 0 ，啦2 0 ，l i 0 ，l l = o ，吗 r 。，应用类似的方法可以计算出收缩后点 的法向量。其中( 4 ，4 ) 式中取特殊情况：口：= 展= 0 。 4 4 2 直接计算收缩后点的法向量 利用法向量的经纬度表示可以很容易的计算出收缩后点的法向量，( 4 5 ) ， ( 4 6 ) 式为法向量的计算提出了显式表达式如果用一般法向量的方法计算收 缩后点的法向量，则结果就比较复杂，因为在计算过程中需要对法向量进行 单位化，单位化使得计算最终变得比较复杂。 如图4 7 ，7 0 i i t 0 2 收缩到。设顶点y 。( 1 0 - 0 。 忙i 。十届l ，+ ，。i i 2 = a + 0 7 + r ? + 2 a l8 t n 心n u + 2 a l h n , on o o + 2 , h n nn 鹄 c ，2 筹筹鼎严 设q i 。o 。+ 届1 7 o l 一- - c q 2 + 属2 + 2 + 2 屈i o 1 7 - - c 2 监 一托 + 一+ m 一届一磊 + 一+ o o丝m 刍忙 = 坠儿一儿 + 一+ 4 一 m m 鱼岛 + 一+ m m 旦忱 = ，雌 复旦大学理学硕士学位论文 2 qy tn i o + 2 崩 n 1 72 l 贝o ( n o 心卜生掣羚产 恻酬= 生掣巍掣 则求( 。弼) 2 + ( k ；2 ) 2 的最值，郢为求下面式子的最值： ! ! ! 塾2 = ! 丛! 生当笠! 盐至：垄匕生盐亟丝盐! ： c 2 + n i n 宅2 + n 2 n 因为上式中只有“未知，可以用数值方法求出 也可以用l a g r a n g e 乘数法求解： 设。= ( 8 ，b ，c ) ，n 2 = ( 万，f ，# ) ， “i = ( i ，儿i ，z 0 1 ) ，= ( ，y 观，z 皿) 2 ( z ，j ，力，则： l ( ：r ，y ，刁a ) ：! l 2 兰丛些型丑譬鱼半丑2 单旦尘业兰咝2 c ，+ ( 甜+ 缈+ c z ) + 至：堑丝! 堑兰丝兰鱼生丝：! 堡兰垃兰鱼尘： 砭+ ( d x + b y + 如) + 旯( z 2 + ) 2 2 + z 2 1 ) 上式分别对i ：r 、，、z 、五求偏导，这样就得到一个非线性方程组。 从以上讨论可以看出，用一般计算法向量的方法直接计算收缩后点的法向量 比较麻烦，特别是在大数据曲面简化过程中，这样计算收缩后点的法向量将会使 计算速度明显变慢。因此本文提出的用法向量的经纬度表示来计算收缩后点的法 向量的方法，为法向量的计算提出显式表达式，从而使法向量的计算比较简单， 计算速度较快，且有比较好的简化显示效果。 4 5 简化曲面加细 本文在简化过程中计算新的曲面顶点的法向量，简化后曲面的每个顶点都带 有法向量，计算出来的法向量带有原网格曲面的一些重要信息，因此对简化后图 复旦大学理学硕士学位论文 形的每个三角形，可以用各种方法，f h _ - - 个顶点的法向量来计算三角形面内的每 个点的法向量，对三角形进行不同程度的加细，从而达到对简化图形向原始图形 进行一定程度恢复的显示效果。 例如简化图形在网络传输时，传输了网格曲面的点信息、面信息和简化后顶 点的法向量信息，然后再根据需要对网格曲面进行不同程度的恢复，使简化后图 形的显示效果更接近原图形。 本文在简化曲面显示时用到曲面加细方法。用三角形顶点的经纬度插值来计 算三角形面片内一些点的法向量，对网格进行加细： 图5 1 加细 本文采用比较简单的加细方法，把简化后的一个三角形按每条边的中点加细 成四个三角形显示。如图5 i ，y 1 2 为边y 。y 2 的中点，设，2 的单位法 向量对应的经纬度为( 岛，仍) 、( 岛，) 、( q 2 ，仍：) _ ：点的经纬度是通过v 。， v ：点的经纬度插值得到： ( q ：，馈：) = ( b ，仍) + ( 岛，仍) 然后再转化成单位法向量。v v 的单位法向量的计算方法和r 。：类似 4 6 试验结果 运用本文方法，对几组三维模型进行了简化。本文图形都借助o i ) e n g l 显示， 简化后图形如无特殊说明都采用4 5 中提到的加细显示方法。图6 1 为一个石猴 子的数据，原数据为1 0 0 0 2 个顶点，2 0 0 0 0 个三角形。图6 1 ( a ) 为原始数据模 型的光照显示。图6 2 为一个松鼠的数据，原数据为9 9 9 6 个顶点，2 0 0 0 0 个三 角形。6 2 ( a ) 为原始数据显示。 2 4 复旦大学理学硕士学位论文 本文简化方法。图6 1 ( b ) 、6 2 ( b ) 为原数据顶点应用本文的方法简化约 9 0 的顶点后的光照显示，其中6 1 ( b ) 中加入1 7 5 个特征点，简化后有2 7 8 0 个三角形面。6 2 ( b ) 加入2 1 3 个特征点简化后有3 1 3 0 个三角形面。和原始 数据显示效果相比，可以看出简化后的显示效果和原图形比较接近简化效果较 好。 本文方法和一般计算法向量的简化方法的比较。图6 1 ( c ) 为应用本文的 简化方法，但没有保特征( 即：没有加入特征) ，且只利用一般的计算法向量的 方法得到的简化效果。可以看出这样得到的图形和图6 1 ( b ) 相比，比较平滑， 特征不突出，显示效果较差 保特征和无保特征比较。图6 2 ( c ) 为应用本文的简化方法，但没有保特 征。从图6 2 ( c ) 和6 2 ( b ) 对比，可以看出保特征和不保特征有比较大的区 别，特别是在曲率变化比较大的特征线附近保特征可以防止特征线被拉离原来 的位置，从而在简化后保持更好的显示效果。 大数据简化。本文提出的简化方法对数据量非常大的图形仍有较好的简化效 果。如图6 3 为一个佛像的数据，原数据有5 4 3 6 5 2 个顶点，1 0 8 7 7 1 6 个三角形， 数据文件大小为4 2 2 m b ，图5 3 ( a ) 为原始数据模型的光照显示。对如此大的 数据简化约9 0 9 6 的顶点个数，其中加入1 0 7 5 7 个特征点，简化后显示效果如图6 3 ( b ) ，可以看出简化后的图形和原图形非常接近。对一次简化后的数据再进行简 化约9 0 的顶点数，其中加入6 4 9 个特征点，显示效果如图6 3 ( c ) ，仍有比较 好的显示效果。 加细和无加细比较。图6 3 ( d ) 为应用本文方法的简化，但6 3 ( d ) 和6 3 ( c ) 的显示方法不同，6 3 ( c ) 为加细显示，6 3 ( d ) 为无加细显示，对比此 两种显示效果可以看出，加细显示的整体效果较好，特别是在特征附近，加细显 示更接近原图，显示效果比无加细好 复旦大学理学硕士学位论文 c a ) 原数据( 2 0 0 0 0 ) ( b ) 保特征加细( 2 7 8 0 )( c ) 无特征一般法向量( 1 9 9 8 ) 图6 1 石猴子模型简化( 模型的三角形面数) c a ) 原数据( 2 0 0 0 0 )( b ) 保特征加细( 3 1 3 0 )( c ) 无特征加细( 2 0 3 6 ) 图6 2 松鼠模型简化( 模型的三角形面数) 复旦大学理学硕士学位论文 ( a ) 原数据( 1 0 8 7 7 1 6 )( b ) 一次简化( 1 5 0 8 6 6 ) ( c ) 二次简化加细( 2 0 9 0 0 ) ( d ) 二次简化无加细( 2 0 9 0 0 ) 图6 3 佛像模型简化( 模型的三角形面数) 复旦大学理学硕士学位论文 4 7 总结和展望 本文提出的简化方法，是在一般简化方法的基础上，提出新的视角，简化的 目的不仅是减少数据量，保持较小的几何误差，更重要的是考虑到简化后图形的 显示效果。在简化的过程中保持曲面特征，并在简化的同时计算出迭代边收缩后 点的法向量，用法向量的经纬度表示为法向量的计算提了显式表达式，很好的解 决了用一般法向量的方法将得到一个复杂并难处理的计算这一问题，并对简化后 图形进行加细。最后利用本文简化方法对几组三维网格模型进行了简化，结果表 明本文的简化方法最终得到比较好的简化显示效果。 本文只是从保持曲面特征和简化后图形顶点法向量的计算上来考虑简化方 法。为了得到好的简化显示效果，还可以从别的方面来考虑，如光照条件，光亮 度的计算等方面。另外本文利用了法向量的经纬度表示很好的解决了收缩后曲面 顶点法向量的计算，并在曲面的加细中用到这一方法。其实还可以对法向量的经 纬度表示进行更深入的讨论研究。最后对盘萄的加细也可以有进一步的探讨。 参考文献 l e v o y , m ，p u l l i , k ，c u r l e s s , b e t a 1 t h ed i g i t a lm i c h e l a n g e l op r o j e c t ：3 d s c a n n i n go fl a r g es t a t u e s i n ：p r o c e d d i n g so ft h ec o m p u t e r g r a p h i c s ， s i g g r a p h 2 0 0 0 , 1 3 1 1 4 4 f h o p p e ，h p r o g r e s s i v e m e s h e s i n ：p r o c e e d i n g s o f t h e s i g g r a p h 9 6 1 9 9 6 ，9 9 - 1 0 8 i k a l v i n , a d ，t a y l o r , t l h s u r p e r f a c e s ：p o l y g o n a lm e s hs i m p l i f i c a t i o nw i t h b o u n d e de r r o r w e ec o m p u t e rg r a p h i c sa n d a p p l i c a t i o n a ，1 9 9 6 ，1 6 ( 3 ) ：6 4 - 7 7 l u b k e , d ，e r i k s o n , c v i e w - d e p e n d e n ts i m p l i f i c a t i o no fa r b i t r a r yp o l y g o n a l e n v i r c o n m e n t s i n ：p r o c e e d i n g so ft h ec o m p u t e rg r a p h i c s ，a n n u a lc o n f e r e n c e s e r i e s s i g g r a p h 1 9 9 7 h e c k b e r t , p s ，g a r l a n d , m s u r v e yo f p o l y g o n a ls m f a c es i m p l i f i c a t i o na l g o r i t h m s i n ：p r o c e e d i n g so ft h es i g g r a p h 9 7 , m u l t i r e s o l u t i o ns u r f a c em o d e l i n g c o u r s e 1 9 9 7 s c h r o d e r , w , z a r g e ，j ，l o r e n s e n ，w d e c i m a t i o no ft r i a n g l e m e s h e s c o m p u t e r g r a p h i c s ，1 9 9 2 ，2 6 ( 2 ) ；6 5 - 7 0 h a m a n n , b ad a t ar e d u c t i o ns c h e m ef o rt r i a n g u l a t e ds u r f a c e c o m p u t e ra i d e d g e o m e t r i cd e s i g n 1 _ 9 9 4 1 1 ( 2 ) ：1 9 7 2 1 4 h o p p e m s m o o t hv i e w - d e p e n d e n tl e v e l - o f - d e t a i lc o n t r o la n di t sa p p l i c a t i o nt o t e r r a i nr e n d e r i n g i e e ev i s u a i z a t i o n , 1 9 9 8 w i l l i a mj s c h r o e d e r , j o n a t h a na ，z a r g e ，a n dw i l l i a me l o r e n s e n d e c i m a t i o n o f t r i a n g l em e s h e s j 1 c o m p u t e rg r a p h i c s ，1 9 9 2 , 2 6 ( 2 ) ：6 5 - 7 0 j a r e kr o s s i g n a ca n dp a u lb o r r e l m u l t i - r e s o l u t i o n3 da p p r o x i m a t i o n sf o r r e n d e r i n gc o m p l e xs c e n e s 【j 】m o d e l i n gi nc o m p u t e rc r r a p h i c s ，1 9 9 3 ：4 5 5 - 4 6 5 g r a l a n dm h e c k b e r tps s u r f a c es i m p l i f i c a t i o nu s i n gq l 上a d r i ee r r o rm e t r i c s a 】i n ：c o m p u t e rg r a p h i c sp r o c e e d i n g s ，a n n u a lc o n f e r e n c es e r i e s ，a c m s i g g r a p h ，l o sa n g e l e s ，c a l i f o r n i a , 1 9 9 7 ：2 0 9 2 1 6 k i msj ，k i mch ，l e v i nd s u r f a c es i m p l i f i c a t i o nu s i n gad i s c r e t ec u r v a r t r e 哪 阱 例 问 嘲 嘲 研 嘲 吲 复旦大学理学硕士学位论文 n o l t n 叽c o m p u t e r g r a p h i c s ，2 0 0 2 ，2 6 ( 5 ) ：6 5 7 - 6 6 3 u3 1 s h i ny o s h i z a w a , a l e x a n d e rb e y a e v , h a n s - p e t e rs e i d e l f a s ta n dr o b u s t d e t e c t i o no fc r e s tl i n e so nm e s h e s 【a 】i n ：a c ms y m p o s i u mo ns o l i dm a d p h y s i c a lm o d e l i n g , 2 0 0 5 ：2 2 7 - 2 3 2 【1 4 】y u t a k ao h t a k e ，a l e x a n d e rb d y a e v , h a n s p e t e rs e i d e l r i d g e - v a l l e yt i n e so n m e s h e sv i a i m p l i c i t s l l r f a e e f i t t i n g叨a c m t