（计算机应用技术专业论文）基于概率函数的三角网格模型简化算法研究与系统实现.pdf

硕士学位论文 摘要 在计算机辅助设计、计算机动画、科学计算可视化、虚拟现实等许多图形 应用系统中，三维物体常用三角网格模型表示，复杂的三角网格模型将给计算机 存储与传输三维物体带来困难。可是，很多情况下人们并不需要对每一模型的细 节都作详细的刻画，如：一个复杂的场景中，远景物体就没有必要有过多的细节。 因此，可根据对模型细节程度的要求不同而对复杂模型进行一定的简化。 本文针对三角网格模型的快速简化方法进行研究。首先，论文介绍了三角 网格模型的有关概念和误差的评估方法，对当前各种简化算法进行了详细的综 述。然后，在总结折叠型简化算法简化过程的基础上，提出了一个基于概率值连 续折叠的三角网格简化算法。算法以三角形折叠为基本简化操作，可调加权控制 函数作为折叠误差控制三角形的简化顺序，根据所有三角形的误差分布，构造一 个概率分布函数，为每个待折叠的三角形计算一个折叠概率值。在简化过程中， 所有三角形按其概率进行折叠，误差较小、概率值较大的三角形优先得到简化。 由于满足简化条件的三角彤个数增加，每次误差排序后，三角形折叠的个数由传 统的1 个增加为若干个，折叠的方式也由传统的单次折叠简化改进为连续折叠简 化。在简化率要求相同的条件下，连续折叠简化的排序次数大大减少。因此，从 误差优先级排序的角度加快了简化速度。 最后，本文设计了一个演示系统，实现了本文算法，并从理论分析与实际系 统运行两方面验证了本文算法和传统的单次折叠简化算法的时间效率，得出了连 续折叠简化的排序时间较单次折叠简化的排序时问快州倍的结论( 肌为平均连 续折叠的三角形个数) 。演示系统的实验结果表明，本算法在保持误差基本相同 的情况下，整体简化速度较单次折叠提高1 0 倍以上。另外，本文还将本算法与 包络控制简化算法进行了比较，结果表明，本算法简化速度快，简化结果更加均 匀。最后通过一组实验验证了选择不同的控制权值可以得到不同形状的简化结 果。 关键词：三角网格模型：三角形折叠；概率函数；连续折叠：模型简化 a b s t r a c t t r i a n g l em e s hm o d e l s a r ew i d e l yu s e di nm a n y c o m p u t e rg r a p h i c ss y s t e m s ，s u c h a s c o m p u t e r - a i d e dd e s i g n ，c o m p u t e ra n i m a t i o n , s c i e n t i f i cv i s u a l i z a t i o n a n dv i r t u a l r e a l i t y ac o m p l e xt r i a n g l em e s hm o d e l w i l lb eh e a v yb u r d e nf o rc o m p u t e rt oa c c e s s a n dt r a n s f e ri t h o w e v e r ，n o ta l l3 do b j e c t sa r ec o n s t r u c t e dw i t hm u c hm o r ed e t a i l s ， f o re x a m p l e ，a l lo b j e c tf a ra w a yf r o mv i e w e r sm a yh a v el e s sd e t a i lt h a na no b j e c t n e a r b y s oi nm o s to fc a s e s ，w ec a l ls i m p l i f yac o m p l e xt r i a n g l em e s hm o d e l t os u i t d i r e n td e m a n d s t h i st h e s i si sd e d i c a t e dt oah i g he f f i c i e n c ym e t h o do ns i m p l i f i n gt r i a n g l em e s h m o d e l s f i r s t ，w ei n t r o d u c es o m eb a s i cc o n c e p t sa b o u tt r i a n g u l a rm e s hm o d e l sa n d e r r o r e v a l u a t i n gm e t h o d s ，a n dt h e n w es u r v e ys o m ee x i s t e dm o d e ls i m p l i f i c a t i o n a l g o r i t h m s o n t h eb a s i so fo u rr e s e a r c hw o r k ，w ep r e s e n tan e wa l g o r i t h mf o r s i m p l i f y i n gt r i a n g l e m e s hm o d e l s ，w h i c hi sb a s e do n p r o b a b i l i t y f u n c t i o na n d a p p l i c a t i o n so fc o n t i n u o u sc o l l a p s eo p e r a t i o nf o rt r i a r i g l e si nm e s h e s i no u ra l g o r i t h m ， a n a d j u s t a b l ew e i g h t e dc o n t r o l f u n c t i o ni su s e di n c o n t r o l l i n gt h es i m p l i f i c a t i o n p r o c e d u r e s p e c i a l l y , ap r o b a b i l i t y f u n c t i o ni sc o n s t r u c t e d b y m e a n so fe r r o r d i s t r i b u t i o n e a c ht r i a n g l ei nam e s hi sd i s t r i b u t e dt oac o r r e s p o n d i n g p r o b a b i l i t y v a l u e b yc o m p u t i n g a l lt r i a n g l e s a r e g r a d u a l l yc o l l a p s e da c c o r d i n g t ot h e i r p r o b a b i l i t yv a l u e t r i a n g l e sw i t hal o w e re r r o ra n d a nu p p e r p r o b a b i l i t ya r ec o l l a p s e d p r e f e r e n t i a l l y i nt h i sw a y , a f t e rr e o r d e r i n gt r i a n g l e s e r r o r s ，t h en u m b e ro fc o l l a p s e d t r i a n g l e si n c r e a s e sf r o m o n et os e v e r a lo n e s ，a n dt h es i n g l e c o l l a p s em o d e i si m p r o v e d t ot h ec o n t i n u o u sc o l l a p s em o d e u n d e rs a m e s i m p l i f i c a t i o nr a t e ，t h es o a i n go p e r a t i o n i nc o n t i n u o u sc 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 m sr e d u c e d r e m a r k a b l yw h e nc o m p a r e d w i t ht h a ti ns i n g l 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 m s a sar e s u l t ，t h ea l g o r i t h mf o r s i m p l i f y i n gt r i a n g l em e s hm o d e lb a s e do np r o b a b i l i t yc o n t i n u o u sc o l l a p s ec a ns p e e d u pt h es i m p l i f i c a t i o np r o c e d u r eo n t h ea s p e c to fe r r o r p r i o r i t ys o r t i nt h i sp a p e r , w e g i v ea na n a l y s i so nt h ee f f i c i e n c yo fo u ra l g o r i t h mi nt h e o r ya n d h a v ea l s od e v e l o p e dad e m o s y s t e mb a s e do no u ra l g o r i t h m r e s u l t sf r o mo u rs y s t e m s h o wt h a tt h es p e e do fc o n t i n o o sc o l l a p s i n go p e r a t i o ni sm t i m e sf a s t e rt h a ns i n g l e c o l l a p s i n go p e r a t i o n i st h ea v e r a g en u m b e ro fc o n t i n u o u sc o l l a p s e s ) ，w h i c hi sj u s t c o n s i s t e n tt ot h er e s u l tf r o mo u rt h e o r e t i ca n a l y s i s a n da l s o ，t i m ec o n s u m p t i o nb y r u n n i n g o u rd e m o s y s t e m i s1 0t i m e sl e s st h a nt h a to f a n ys i n g l ec o l a p s e i l 硕士学位论文 s i m p l i f i c a t i o na l g o r i t h mu n d e r t h es a m ee r r o rt o l e r a n c e b e s i d e s ，w ea l s oc o m p a r eo u r a l g o r i t h mw i t hs i m p l i f i c a t i o nm e t h o db yu s i n g t h ee n v e l o p ea se r r o rt o l e r a n c e r e s u l t i n d i c a t e st h a tt h es p e e do fo u ra l g o r i t h mi sm u c hf a s t e rt h a nt h a to fs i m p l i f i c a t i o n m e t h o d b yu s i n g t h ee n v e l o p ea se r r o rt o l e r a n c e k e yw o r d s ：t r i a n g l em e s hm o d e l ；t r i a n g u l a rc o l l a p s e ；p r o b a b i l i t yf u n c t i o n c o n t i n u o u s c o l l a p s e ：m o d e ls i m p l i f i c a t i o n n l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：主t7 * 曰厶 日期：? 。耷年，月护日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 日期：2 0 0 牟年瑚幻日 日期：枷。 o ，各三角形 折叠的c ( y ) 值将不断增大，因此折叠误差c ) 可作为本算法网格简化的全局累积 误差函数。 ( 2 8 ) 式中，权值i t i 决定了顶点v 的历史误差对与v 相关的三角形集合c l 中各三角形的折叠误差值的“贡献”，i t i 值越大，则c r 中各三角形的折叠误差值 将相应增大，c ，中各三角形折叠的概率将会减小，即c ，所在的局部区域不会很快 再次被简化。在本实验中取m = l ，可以得到很好的简化结果。 2 3 5 概率分布函数的构造 一般来说，折叠误差的大小决定了折叠简化的顺序，折叠操作首先从误差最 小的三角形开始，通常按折叠误差大小将所有三角形面片排为升序优先队列后， 取队首元素折叠，折叠后，修改相关三角形的新点位置和折叠误差，然后重新进 行排序，如此反复。为了加快简化的速度，我们采用连续折叠的方法，根据所有 三角形折叠误差值的分布，定义一个概率分审函数，所有三角形以其分配的概率 进行折叠，然后再重新排为升序优先队列。现分析一次误差排序后如何进行简化 的过程： 设当前所有三角形误差最小值为c 。i 。，最大值为c 。，4 c = c 。c 。构造 概率分布函数为一个分段函数。为确定概率分段的区问，本文根据用户设定的下 限百分比m l 和上限百分比m 2 ( 7 1 m z ) ，定义区间的边界即误差的下限阂值与上 限阈值分别为： m i n c = c m i n + ”l ac ； m a x c = c m i n + 胁2 ac 这时，可以构造分段折叠概率函数p 为：( 如图2 4 ) 其中： 1c r a i n c r a i n c c ( v ) ，m a x c ( 2 9 ) 基于概率函数的三角网格模型简化算法研究与系统实现 一 p m 。，；1 一：一m 。) 堕 ( 2 i 0 ) m 2 1 o )一 肌“ j j jj 图2 4 折叠概率函数 从图中可知，误差在下限阈值以内的三角形都能够被折叠，在上限误差之外 的三角形都不能被折叠，而上下限阈值之间的三角形以某个概率值进行折叠，此 概率是折叠误差的线形函数。如此设置是为了从概率上保证优先折叠误差较小的 三角形，误差越小，三角形被折叠的概率越大，随着误差增大，三角形被折叠的 概率逐渐减小。 。是当误差大于下限阈值时折叠概率的极大值，它的大小与上下限百分比 的宽度及上限百分比的变化相反，当百分比宽度和上限百分比都较大时，说明可 能折叠的三角形较多，因此用较小的概率控制实际折叠的三角形数，而当百分比 宽度和上限百分比都较小时，折叠概率就相应增大。 队列中满足条件的三角形在被连续折叠后，发生形变的其他三角形重新计算 误差函数并进行误差排序，计算新的折叠概率分布函数，开始新一轮的简化过程。 按此方法简化可以推知，每次误差排序后的简化按概率分布函数进行后，被 折叠的三角形个数不再是传统算法中的一个，而是增加为若干个。为了达到要求 的简化率，每次简化的三角形个数增多，减少了误差排序的次数。模型简化的过 程就是三角形折叠和误差排序的循环过程，如果折叠的三角形个数相同，排序的 次数减少就可以加快总的简化速度。本文第4 3 节通过对牛模型和脚骨模型进行 连续折叠简化与单次折叠简化的实验结果比较，较好的体现了本算法简化速度快 的特点。 2 3 6 相关区域的处理 为避免局部区域的过度简化，我们采用冻结相关三角形的方法。即对个三 角形进行简化，生成新点v 后，冻结与顶点v 相关的所有三角形，不参与本次简 硕士学位论文 化，直到队列中误差允许范围内所剩的三角形均被冻结，再将这些三角形同时解 冻，继续进行简化操作。 在算法执行的过程中，如果每进行一次折叠操作都重新计算各相关三角形的 新点位置、控制函数和折叠误差，各折叠三角形的相关三角形集合可能存在交集， 因而会对交集内的三角形进行多次计算。如图2 5 所示，若对图中v 。v 。v ，执行折 叠，新点为p 。，则需要重新计算相关区域内p o v 。v 5 ，p o v ；v 。，p 。v 。v ，ap 。v ，v 。， p 。v 。v 。，p 。v ，v 。的新点和折叠误差，并把它们冻结，假设v 。v 。v ，。的折叠操作 在该简化操作之后执行，新点为p ，同样地，算法对该简化操作相关区域内 p l v 4 v l l ，p l v l l v l 2 ， a p i v l 2 y 1 3 ， p x vl 3 v l ， p l v l 4 v 1 5 ， a p l v i s v 7 ，p l p o v 7 ，p i p o v 的新点和误差进行计算，并把这些三角形冻结。我们注意到，其中对p i p 。v ，和 p l p o v 一的计算使上一次简化后对p 。v t v 5 j p 。v 。v 。，p 。v 。v ，的计算成为冗余。 因此，为了消除这种算法上的冗余，每执行一次折叠操作，其相关区域内的三角 形被冻结，在未被解冻之前不再参加折叠操作，而直接对队列中下一个保持活跃 状态的三角形进行折叠，然后在解冻所有三角形的时候，重新计算它们的新点位 置、控制函数和折叠误差，并进行排序。 v 1 v 1 5 图2 5 三角形v ，v ：v ，和三角形v ；v 。v ：。的相关区域 2 4 算法流程与总结 综上所述，算法流程总结如下： ( 1 ) 初始化原始网格中所有点的历史记录误差e ( v ，) ：0 ； ( 2 ) 计算原始网格中每个三角形面片折叠后的新点坐标、控制函数包含的各 控制分量的值； ( 3 ) 设置控制权值1 4 , d ，坩，w ，计算各三角形在此权值下的控制函数及折叠误 差，并按折叠误差大小将所有三角形排为升序优先队列： ( 4 ) 设置折叠误差的下限阈值、上限阈值，构造分段概率函数： 基于概率函数的三角网格模型简化算法研究与系统实现 取队首元素； w h i l e 误差 上限闽值d o i f 误差 下限闽值t h e n 折叠该三角形； i f 下限阈值 误差 ( 简化率原始面片数) ) 取堆顶元素h e a p t o p ，调整堆； w h i l e ( h e a p t o p p r i o r i t y m a x c ) s w i t h ( h e a p t o p f l a g ) c a s e l , 2 ：b r e a k ； c a s e0 ：i f ( h e a p t o p p r i o r i t y 单次折叠简化模型( 1 1 1 7 个三角形) w a = o 3 ，w ，= 0 3 ，w ，= o 4 c ) 连续折叠简化模型( 1 0 4 8 个三角形) i ，d = 0 3 ，w j = 0 3 ，w ，= 0 4 ， “l = 0 0 2 ，“2 = o 0 6 图4 2 脚骨模型的简化 表4 1 单次折叠与连续折叠简化算法实验结果 参数设置单次折叠简化连续折叠简化 原始模 型及面 简化 简化 简化平均误平均误 平均折 片数 阢 职 ， 1 m 2时间时问 窒 差 叠个数 m s m s 牛5 8 0 4 0 1o 80 10 0 200 53 0 4 5 3 5 90 7 4 6 0 7 73 1 1 0 0 7 5 8 0 188 4 脚骨4 2 0 4 o 3 0 30 40 0 2 0 0 62 5 3 5 2 6 6 0 8 5 0 7 8 32 7 6 60 8 7 9 0 5 97 8 从表中可以看出，连续折叠简化的速度比单次折叠简化的速度有较大程度的 提高，而两种简化方法的平均误差大致相同，图4 1 中牛的两个简化模型的面片 个数、大小、形状都非常相似，图4 2 中脚骨的两个简化模型的面片个数、大小、 形状电都非常相似。 4 4 与简化包络控制三角形折叠简化算法的实验结果比较 简化包络的概念1 2 2 , 5 1 】是：将原始网格模型上的每一个顶点v 。( i = l ，2 ，仃) 都沿着各自的法矢量m 的方向( 或者其法矢量的反方向) 偏移一定的距离，然后 按照原始模型上相应点之间的连接关系，用线段将这些偏移后产生的新点连接起 来。这些线段在顶点处相互连接，共同构成了一个三角形网格，其外形类似于原 始模型a 如果原始网格模型上的顶点是沿着各自的法矢量方向移动的，那么这个 新的三角形网格就是外包络，反之则为内包络，简化包络相当于是原始模型表面 的偏移而成的近似等距面。 基于概率函数的三角网格模型简化算法研究与系统实现 简化包络控制三角形折叠简化算法是以三角形折叠为基本操作，对原始模型 中所有三角形尝试进行折叠，折叠新点的相关三角形环必须在内外包络之问围成 的空间内或是内包络与原始模型之间围成的空间内，也就是说，简化过程要控制 在内外包络之间或是内包络与原始模型之间。包络偏移的距离一般以原始模型包 围盒对角线的某个百分数为度量，当模型中任意一个三角形进行折叠时都超出了 这个包围空问时，简化过程结束。因此算法实现中大部分的时间用于三角形面片 的相交检测。 相比本文的误差控制为一个标量，包络控制简化算法的误差控制在一个三维 空间中，简化结果的形状易于预见，但简化包络算法的实现需要先从原始模型偏 移成内外包络后再在包络之间进行简化，过程实现较为复杂，丽且简化率也不易 控制。另外简化的结果与本文算法的结果也有较大的不同，我们以牛模型为例比 较两种算法的实验结果。 a ) 包络简化模型( 3 6 2 6 个三角形) l ，内外包络简化率6 2 5 c ) 包络简化模型( 2 7 8 4 个三角形) 2 ，内包络简化率4 8 b ) 连续折叠简化模型( 3 5 9 6 个三角形) w d = 0 3 ，w ，= o 3 ，w r - o 4 ， m l = o 0 0 5 ，“2 = o ，0 1 ，简化率6 2 d ) 连续折叠简化模型( 2 7 8 5 个三角形) w d = 0 3 ，w ，= o 3 ，i , v ，= 0 4 m t = o 0 0 5 ，m 2 = o 0 1 ，简化率4 8 图4 3 牛模型的包络简化与折叠简化 硕士学位论文 表4 2 包络简化算法与连续折叠简化算法实验结果 包络控制简化 连续折叠简化 原始 时间 时间 模型 简化 参数设置 构造包 简化参数设置构造数据简化 及面 盎 f 包围盒对角 络时间时阃 ( w a , w 3 ，w i ，m l ，m 心 结构时问时间 片数 线的百分数) m s m s m s m s 牛6 2 5 1 ，内外包络6 9 2 5 05 4 5 4 7 0 3 ，0 3 ，0 4 ，0 0 0 5 , 0 0 1 1 1 4 11 7 3 4 5 8 0 44 8 2 ，内包络3 5 0 0 03 3 2 5 0 0 3 ，0 3 ，0 4 ，0 0 0 5 ，0 0 1 1 1 1 03 4 2 2 从表4 2 可以比较得出，在相同的简化率要求下，本文提出的连续折叠简化 算法比包络控制简化算法在时间上快一个数量级。从简化的结果来看，本文算法 实现的简化模型表面面片的大小和分布都比较均匀，而包络简化的模型简化集中 在较平坦的牛身部分，牛角、牛眼、牛尾巴及四条腿等表面曲率变化较大的部位 简化程度不高，引起这种整体简化不够均匀的原因是平坦部分的包络空间较通 畅、平缓，三角形不易出现相交现象，可以进行多次折叠简化，而表面曲率变化 较大部分的包络空间比较曲折、陡峭，极易发生形变三角形超出包络包围的情况， 简化的次数减少，较多地保持了原始模型的形状。 4 5 不同参数控制的实验结果比较 本算法中控制函数的三个分项分别控制不同几何特性的简化程度，各分项权 值的取值不同，简化的方向就有所不同，图4 4 是m 1 = 0 0 0 5 ，m 2 = 0 。0 1 5 ，简化率 为5 0 串t ，脚骨模型在不同权值分配下的简化结果，( a ) 是二面角权值较大时的 简化模型，( b ) 是面积权值较大时的简化模型，( c ) 是纵横比权值较大时的简化 模型： 4 1 苎王塑至里垫塑三鱼望塑堡鐾堑些篁塑璧窒量皇至篁童堡： a 1 原始牛模型，5 8 0 4 个三角形 b ) w d = 0 9 ，w ，= o 。0 5 ，w ，= 0 0 5 m l = o 0 0 5 ，m z r - o 0 1 5 2 1 0 0 个三角形 c ) w d = 0 0 5 ，w s = o 9 ，w r = 0 0 5 ， d ) w d = 0 0 5 ，w s = o 0 5 ，w ，= 0 9 m 1 - 0 0 0 5 ，“2 - - 0 0 1 5 m l = o 0 0 5 ，m 2 = o 0 1 5 2 1 0 0 个三角形 2 1 0 1 个三角形 图4 4 采用不同权值控制折叠的脚骨模型简化结果 图中b ) 模型较好的保持了原始模型的某些弯曲特征，如骨关节部位简化程 度较低，三角形比较密集，与原始模型相似；c ) 模型中三角形大小较b ) d ) 模型 中的三角形大小要均匀，关节处的三角形分布相对稀疏一些；d ) 模型中三角形 形状比较均匀，原始模型中纵横比较大的、形状比较均匀的三角形得到了很好的 保留，如跟骨、大脚趾部分简化程度较低，基本上与原始模型形状相同。 实验证明，通过设置控制函数中各分项的权值可以得到不同的简化结果，在 图形简化的各种实际应用中，我们可以根据不同的应用要求选择不同的简化模型。 4 ，6 小结 这一章首先从理论上分析计算了本文提出的基于概率函数的连续折叠简化算 法和传统的单次折叠简化算法的排序时问复杂度，得出了连续折叠简化的排序时 间较单次折叠简化的排序时间快m 倍的结论( m 为平均连续折叠的三角形个数) 。 然后以具有代表性的牛模型和脚骨模型为例进行了一组实验。实验结果证明，由 于排序时间的缩短，整个简化速度提高了十倍以上。接着本文算法与包络控制简 化算法也进行了比较，由于两种算法简化机制的不同，本文算法较包络简化速度 要快，简化结果更均匀。最后分析了以不同控制参数进行简化时，本文算法所得 到的不同简化结果，体现了本算法简化结果的多样性。 硕士学位论文 ；= ；j = ；= ；= ；= ；= ；= = ；= l # ；j ；= = = ；i 目 本文工作总结 结论 三维几何模型简化技术一直是虚拟现实技术研究中的一个热点，一个好的模 型简化算法不仅要求简化后的模型具有较高的保真度，而且要求简化的时间尽可 能的短，以满足模型显示的实时性。 本文首先在分析与比较现有模型简化算法的基础上，总结出几何元素折叠型 算法的简化流程就是三角形折叠和误差排序的循环过程，然后从加快排序速度的 角度，提出了一种基于概率函数的连续折叠简化新算法。 算法采用三角形折叠操作来减少原始模型的三角形数目，三角形折叠后以一 个新点代替原三角形。该新点的位置为从三角形三个顶点、三边中点和中心共七 个点中，选择蓟与该三角形相关的所有三角形面片距离最短的点。包含三角形的 面积、纵横比和简化前后相关三角形面片转动最大角这三个分项的可变权值控制 函数与其历史记录之和作为简化误差，控制简化的顺序。算法首次提出了依概率 值连续折叠的方法，改进了每次误差排序后只折叠简化误差最小的一个三角形的 传统做法，根据各三角形的误差太小，定义一个概率分布函数，不同误差的三角 形都分配一个折叠概率值，在每次误差排序后所有三角形按分配的概率迸行折叠 简化，这样每次简化的三角形数由原来的一个增加为若干个。每次简化后三角形 折叠误差函数值会发生改变，概率函数值也会随之修改，以保证误差较小的三角 形分配到较大的折叠概率值，优先得到简化。 接下来，作者利用v c + + 编程工具中的m f c 编写用户界面，利用o p e n g l 函数 库绘制三维图形，设计了个演示系统，实现了本文提出的模型简化算法。本演 示系统能读入s m f 格式的输入模型，设置简化参数后，开始简化，简化结束后给 出简化结果信息，包括实际简化的面片数、简化的时间、平均误差、平均连续折 叠的三角形个数、连续折叠的次数及每次折叠的三角形个数。为了与本文提出的 连续折叠算法相比较，本演示系统还实现了一个单次折叠简化算法。 最后本文从算法分析与实验两方面比较了传统的单次折叠简化与本文提出的 基于概率函数的连续折叠简化的性能优劣。通过对两种算法排序时间复杂度的分 析，得出了连续折叠简化排序时间较单次折叠快，l 倍的结论( _ ，l 为平均连续折叠 的三角形个数) 。两种算法的实验结果也表明本文算法的简化速度较单次折叠算法 有较大的提高。另一组实验还将本算法与简化包络控制三角形折叠的简化算法进 茎王堑至里墼竺三垒星塑查堑堑坠堡塑塑墅窒皇重塑至型坠：一 = = = = = = = ! = = = - = = = ! = = = = = = = = = = = = = = = ! = = = = = = = = = = = = = = = = = = 行了比较，得出了本算法简化速度快， 本算法由于采用可变权值的控制函数， 今后工作展望 简化效果均匀的结论。第三组实验验证了 导致简化结栗的多样性的特点。 模型简化算法设计中需要考虑的方面是很多的，某一个算法不可能面面俱到 地提高各方面的效率，本算法也不例外。由于本算法最大的特点是简化速度较快， 某些方面的处理势必会相对简化一些，因此，今后研究工作中需要改进的地方有 如下几点： 1 、扩展输入模型类型范围。本文算法只适用于封闭的普通流形表面网格，对 于非封闭的、非流形表面网格模型本算法只能读入而不能进行简化处理，若扩展 算法的输入类型范围就能扩展算法的应用领域。 2 、三角形折叠时新点位置的选择。当一个三角形折叠成一个新点的时候，新 点的位置选择比较关键，如果新点的位置不好，会影响到简化模型外形特征的丢 失。本算法利用从七个候选点中选择到平面的距离最短的点作为新点位置，是借 鉴二次误差矩阵的误差控制方法中新点位置计算的方法，但这个新点的计算较复 杂，不一定是最佳的点，因此可以研究寻找最佳位置的方法。 3 、简化控制过程的调整。如概率分布函数的定义，简化过程中上、下限闽 值调整的方法等等。本文选取的是比较简单的分段连续函数作为概率分布函数的 定义，固定误差上、下限百分比来调整上、下限阈值，如何选取更加合理、有效 的概率分布函数和如何调整阂值的大小也是今后研究的主要内容。 总之，设计一个对三维几何模型简化效果好，简化速度又快的算法，并将算 法应用到更多的计算机图形学领域是广大模型简化技术研究人员不断探索的目 标，也是本文今后研究的主要方向。 硕士学位论文 = ；l = ；= ；= ；4 i ；= = ；_ e e ；j 日_ _ ；= ；= 目 参考文献 【i 】h o p p eh ，d e r o s e ts u r f a c er e c o n s t r u c t i o nf r o m u n o r g a n i z e d p o i n t s i n ：p r o c e e d i n g so fc o m p u t e rg r a p h i c s ，s i g g r a p h 9 2 ，c h i c a g o ，1 9 9 2 ，7 1 7 8 【2 】l e v o ym ，p u l l i k ，c u r l e s sb ，e t a 1 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 ：3 d s c a n n i n g o f l a r g es t a t u e s i n ：p r o c e e d i n g s o ft h e2 7 t ha n n u a lc o n f e r e n c e o nc o m p u t e r g r a p h i c sa n d i n t e r a c t i v et e c h n i q u e s n e wo r l e a n s ，2 0 0 0 ，1 3 1 。1 4 4 【3 】 c l a r kjh h i e r a r c h i c a l g e o m e t r i c m o d e l sf o rv i s i b l es u r f a c e a l g o r i t h m s c o m m u n i c a t i o n so ft h ea c m ，1 9 7 6 ，1 9 ( 1 0 ) ：5 4 7 5 5 4 4 】 g o u r r e tjp ，k h a m l i c h ij am o d e lf o rc o m p r e s s i o na n dc l a s s i f i c a t i o no ff a c e d a t as t r u c t u r e c o m p u t e r & g r a p h i c s ，1 9 9 6 ，2 0 ( 6 ) ：8 6 3 8 7 9 【5 】刘新国，鲍虎军，彭群生增量几何压缩软件学报，2 0 0 0 ，1 1 ( 9 ) ：1 1 6 7 1 1 7 5 6 s h a d ej ，l i s c h i n s k i d ，s a l e s i nd ，e ta 1 h i e r a r c h i c a l i m a g ec a c h i n g f o r a c c e l e r a t e d w a l k t h r o u g h s o f c o m p l e xe n v i r o n m e n t s i n ：p r o c e e d i n g s o f s i g g r a p h 9 6 ，n e wo d e a n s ，1 9 9 6 ，7 5 8 2 【7 】h o p p eh p r o g r e s s i v em e s h e s c o m p u t e rg r a p h i c s ，1 9 9 6 ，3 0 ( 1 ) ：9 9 1 0 8 8 】 k a l v i nad ，t a y l o rrh s u r p e r f a c e s ：p o l y g o n a lm e s h s i m p l i f i c a t i o n w i t h b o u n d e de r r o l , i e 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 s ，1 9 9 6 ，1 6 ( 3 ) ：6 4 7 7 9 】r o s s i g n a cj ，b o r r e lp 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 nf o rr e n d e r i n gc o m p l e x s c e n e s i n ：p r o c e e d i n g so ft h e2 “4c o n f e r e n c em o d e l i n g i nc o m p u t e r g r a p h i c s ： m e t h o d sa n d a p p l i c a t i o n s b e r l i n ，1 9 9 3 ，4 5 3 4 6 5 1 0 l u e b k ed ，e r i k s o nc 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 o n m e n t s i n ：p r o c e e d i n g so f t h ec o m p u t e rg r a p h i c s ，s i g g r a p h 9 7 l o s a n g e l e s ，1 9 9 7 ，1 9 9 2 0 8 【1 1 】s c h m i t tf ，b a l k yb ，d uw h a na d a p t i v es u b d i v i s i o nm e t h o df o r s u r f a c e f i t t i n g f r o ms a m p l e dd a t a i n ：p r o c e e 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 8 6 s e a t t l e ，1 9 8 6 ，1 7 9 1 8 8 f 1 2 】s c h r o d e rw ，z a r g ej ，l o r e n s e nw td e c i m a t i o no ft r i a n g l em 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 1 3 】h a m a n nb 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 c d e s i g n ，1 9 9 4 ，1 1 ( 2 ) ：1 9 7 2 1 4 【1 4 】x i a j c ，v a r s h n e ya d y n a m i cv i e w d e p e n d e n ts i m p l i f i c a t i o nf o r p o l y g o u a l 基于概率函数的三角网格模型简化算法研究与系统实现 m o d e l s i n ：p r o c e e d i n g so f i e e ev i s u a l i z a t i o n 9 6 m o n t e r e y , 1 9 9 6 ，3 2 7 - 3 3 4 1 5 】h o p p eh 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 l c 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 n r e n d e r i n g i n ：p r o c e e d i n g s o ft h e1 9 9 8i e e ev i s u a l i z a t i o n l o s a l a m i t o s ，1 9 9 8 ，3 5 - 4 2 【1 6 】l o wk l ，t a nts m o d e ls i m p l i f i c a t i o nu s i n gv e r t e x c l u s t e r i n g i n ：p r o c e e d i n g s o ft h es y m p o s i u mo ni n t e r a c t i v e3 d g r a p h i c s p r o v i d e n c e ，1 9 9 7 ，7 5 8 1 【1 7 】s c h a u f l e rg s t u r z l i n g e rw g e n e r a t i n gm u l t i p l el e v e l so f d e t a i lf r o mp o l y g o n a l g e o m e t r y m o d e l s i n ：p r o c e e d i n g s o ft h e v i r t u a l e n v i r o n m e n t s 9 5 l o n d o n ，1 9 9 5