（计算机应用技术专业论文）基于局部误差测度的几何模型简化方法研究.pdf

摘要 摘要 三维几何模型简化是计算机图形学领域始终备受关注的研究方向，也是未来 相当长时间内的热点方向。随着获取和建模技术的迅速发展，得到高精度、大数 据量的三维几何模型变得越来越容易。虽然计算机图形硬件性能在不断提高，但 其处理和绘制几何模型的速度与人们的期望仍然存在一定差距。这就需要在一定 情况下对模型进行简化，在模型的精确程度和处理速度之间进行折衷。三维几何 模型简化就是在尽量保持原始模型几何外观不变的情况下，尽可能地减少构成原 始模型的图元数量。高质量的三维几何模型简化算法研究仍然是计算机图形学研 究人员需要长期进行的工作。 本文在总结和深入研究当前国内外几何模型简化的各项技术基础上，针对三 角网格和点云这两类最常用的三维几何模型，提出新的算法，解决几何模型简化 中存在的一些问题。本文首先研究了三角网格的核内简化方法；对于点云模型， 分别研究了核内的迭代简化和大型点云自适应的核外简化，最后将多分辨率模型 的构造应用在基于视点的点云绘制上。本文算法在简化过程中用到的的误差测度 均为局部误差测度，即只考虑模型局部表面改变引起的误差。论文取得主要研究 成果如下： 。 1 基于广义曲率误差测度的边折叠简化。研究的是三角网格模型的简化方 法。分析了网格简化中基于边折叠简化的典型算法，针对这些算法在大 规模简化后不能很好保持模型尖锐特征的弱点，提出了广义曲率的概 念，并将广义曲率加入二次误差测度中，使得新的误差测度不仅能够度 量距离偏差，而且能够反映模型局部表面几何变化。实验结果表明，新 算法简化后的模型能够在保持较低误差水平的同时，保留相当多的重要 几何特征，整体视觉效果较好。 2 基于局部误差测度的点云迭代简化。研究的是点云模型的核内简化方 法。为了得到高质量的简化模型，目前基于点对收缩的点云迭代简化算 法往往需要借助原始模型进行误差度量，内存占用较大。本文提出一种 基于局部误差测度的点云迭代简化算法。该算法在进行误差度量时只根 北京t 业入学t 学博i + 学位论义 i i 据当日订的中阳j 简化结果进行，使用体积优化和距离优化策略计算点对收 缩后的最优点位置并对点对进行排序，可以在内存占用较小的情况下得 到误差较低的简化模型。 3 基于二次型矩阵分析的大型点云自适应核外简化。研究的是点云模型的 核外简化方法。目前大多数点云简化算法不能处理一次无法载入内存的 。大型点云模型。本文提出了一个大型点云自适应的简化算法。陔算法充 分利用二次型矩阵来分析表面几何变化程度，以自适应地分布点云密 度。将简化过程第一个阶段得到的二次型矩阵直接用于后续的表面细节 分析和进一步简化中，提高了效率。由于本算法内存占用只与输出模型 相关，因此可以对大型点云进行简化，得到较高质量的简化模型。对于 有边缘的点云模型，还给出了一个简便有效的检测边缘点的方法。 4 基于视点的点云绘制系统。这部分是在上述研究的基础上实现了个基 于视点的点云绘制系统。目前基于视点的点云绘制方法中都是用聚类方 法构造多分辨率结构，本文采用点对收缩构造多分辨率结构，能够提供 比空间分割聚类更细的颗粒度，以及比区域增长聚类更少的树根数量和 树深度。同时借鉴静态简化的优点为多分辨率结构建立索引链表，有利 于提高细节搜索效率。通过融合多种基于视点的分辨率选择标准，在模 型不同视觉敏感区进行细节分配。该系统得到的基于视点的动念简化模 型绘制效果能够较好地符合视觉要求。 关键词模型简化；局部误差测度：三角网格；点云模型 a b s t r a c t a b s t r a c t t h es i m p l i f i c a t i o no f3 dg e o m e t r i cm o d e l si sar e s e a r c ha r e at h a th a sa l w a y s b e e nc o n c e r n e di nt h ef i e l do fc o m p u t e rg r a p h i c s i ta l s ow o u l db eah o tr e s e a r c ha r e a f o ral o n gt i m ei nt h ef u t u r e w i t ht h er a p i dd e v e l o p m e n to fa c q u i r i n ga n dm o d e l i n g t e c h n o l o g y i ti se a s i e rt oo b t a i n3dg e o m e t r i cm o d e l sw i t hh i g h p r e c i s i o na n dl a r g e v o l u m et h a ne v e r t h ep e r f o r m a n c eo fc o m p u t e rg r a p h i c sh a r d w a r eh a sb e e ni n c r e a s i n g ， b u tt h e r es t i l le x i s tac e r t a i ng a pb e t w e e np e o p l e se x p e c t a t i o no ff a s td a t ap r o c e s s i n go f l a r g em o d e l sa n dt h eh a n d l i n gc a p a c i t yo fh a r d w a r e t h i sr e q u i r e st h a tt h em o d e lc a nb e s i m p l i f i e dt om a k et h ea c c u r a c ya n dt h ep r o c e s s i n gs p e e df o rc o m p r o m i s e t h ep u r p o s e o fs i m p l i f i c a t i o ni sa sm u c ha sp o s s i b l et or e d u c et h ev o l u m eo fg r a p h i cp r i m i t i v e so f o r i g i n a l m o d e l sw h i l ea sf a ra s p o s s i b l et om a i n t a i nt h eg e o m e t r i ca p p e a r a n c e u n c h a n g e d t h er e s e a r c ho fh i g h q u a l i t ya l g o r i t h m sf o rs i m p l i f y i n g3 dg e o m e t r i c m o d e l si ss t i l lal o n g t e r mp r o c e s sf o rc o m p u t e rg r a p h i c sr e s e a r c h e r s a f t e rc o n c l u d i n ga n ds t u d y i n go fm o d e ls i m p l i f i c a t i o nt e c h n o l o g i e sa th o m ea n d a b r o a di nd e p t h ，w ep r e s e n tn e wa l g o r i t h m st os i m p l i f yt r i a n g u l a rm e s ha n dp o i n tc l o u d m o d e l s o u ra l g o r i t h m so v e r c o m es o m eo ft h e p r o b l e m st h a t e x i s ti nm o d e l s i m p l i f i c a t i o n a n d a c h i e v e g o o dr e s u l t s f i r s t l y , t h i st h e s i ss t u d i e si n c o r e s i m p l i f i c a t i o no f t r i a n g u l a r m e s h e s t h e n f o rp o i n tc l o u d s i t e r a t i v ei n c o r e s i m p l i f i c a t i o n a n da d a p t i v eo u t - o f - c o r e s i m p l i f i c a t i o n a r e s t u d i e d f i n a l l y ，t h e c o n s t r u c t i o no fm u l t i r e s o l u t i o nm o d e l si su s e di nv i e w d e p e n d e n td y n a m i cr e n d e r i n go f p o i n tc l o u d sb a s e do na b o v er e s e a r c h e s t h ee r r o rm e t r i c su s e di nt h i sp a p e ra r el o c a l e r r o rm e t r i c s t h a ti st os a y , t h ee r r o r sc a u s e db yl o c a ls u r f a c ec h a n g e sa r ec o n s i d e r e d t h em a i nr e s e a r c hr e s u l t sa r es u m m a r i z e db e l o w ： 1 e d g ec o l l a p s es i m p l i f i c a t i o nb a s e do nt h eg e n e r a lc u r v a t u r ee r r o rm e t r i c s w e a n a l y z et h et y p i c a la l g o r i t h m so fe d g ec o l l a p s e a f t e rd r a s t i cs i m p l i f i c a t i o n p r o c e s s ，m o s to ft h ee x i s t i n gs i m p l i f i c a t i o na l g o r i t h m s b a s e do ne d g e c o l l a p s ed on o tp r e s e r v ef i n es h a p ef e a t u r e so ft h eo r i g i n a lm o d e lv e r yw e l l a n dl e a dt ov i s u a ld i s t o r t i o n w ed e f i n et w og e n e r a lc u r v a t u r e sa n de m b e d t h e mi n t ot h eq u a d r i ce r r o rm e t r i c ，s ot h a tt h em e t r i c sc a nn o to n l ym e a s u r e d i s t a n c ee r r o rb u ta l s or e f l e c tg e o m e t r i cv a r i a t i o n so fl o c a ls u r f a c e t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en o v e la l g o r i t h m sc a nd i s t r i b u t em e s h e s r e a s o n a b l ys ot h a tt l e yc a l lp r e s e r v eq u i t ean u m b e ro fi m p o r t a n ts h a p e f e a t u r e sa n dr e d u c ev i s u a ld i s t o r t i o ne v e na tv e r yl o wr e s o l u t i o n 2 i t e r a t i v es i m p l i f i c a t i o no fp o i n tc l o u d sb a s e do nl o c a le r r o rm e t r i c s t h e e x i s t i n gi t e r a t i v es i m p l i f i c a t i o na l g o r i t h m so fp o i n tc l o u d so f t e nm a i n t a i nt h e i n f o r m a t i o no ft h eo r i g i n a lm o d e la n do c c u p yl a r g e rm e m o r yi nt h ep r o c e s s o fs i m p l i f i c a t i o n w ep r e s e n ta ni t e r a t i v ea l g o r i t h mt h a tn e e dn o tu s et h e o r i g i n a lm o d e lw h e nc a l c u l a t i n ge r r o r s t h i sa l g o r i t h mu s e sv o l u m ea n d d i s t a n c eo p t i m i z a t i o n st oc o m p u t et h en e wp o i n ta n ds o r tt h ec o n t r a c t i o n o p e r a t i o n s 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 ra l g o r i t h mc a no b t a i n s i m p l i f i e dm o d e l sw i t hl o we r r o ru n d e rt h ec o n d i t i o no fs m a l l e rm e m o r y o c c u p a t i o n a d a p t i v eo u t o f - c o r es i m p l i f i c a t i o no fl a r g ep o i n tc l o u d sb a s e do na n a l y s i so f q u a d r i cm a t r i c e s m o s to ft h ee x i t i n gp o i n t b a s e ds i m p l i f i c a t i o nm e t h o d s i i i 北京工业大学工学博上学佗论文 c a n tc o p ew i t hm o d e l st h a ta r et o o a l la d a p t i v eo u t o f - c o r es c h e m ef o r l a r g et of i ti nm a i nm e m o r y w ep r e s e n t s i m p l i f y i n gl a r g ep o i n t s a m p l e dm o d e l s o u rm e t h o du s e sq u a d r i cm a t r i c e st o a n a l y z et h ec h a n g e so fs u r f a c e g e o m e t r ya n da v o i d se s t i m a t i n gc u r v a t u r e s t h ec o m p u t a t i o n a le f f i c i e n c yi s i m p r o v e d q u a d r i cm a t r i c e so b t a i n e di nt h ef i r s ts t e pa r eu s e dd i r e c t l yi nt h e a n a l y s i so fs u r f a c ed e t a i l sa n df u r t h e rs i m p l i f i c a t i o n ，a sar e s u l tt h en u m b e r o ft r a v e r s i n gt h eo r i g i n a lm o d e la n dt h es y s t e mo v e r h e a da r er e d u c e d s i n c e t h ea l g o r i t h mi si n p u ti n s e n s i t i v e ，i t q u a l i t ya n dl o wm e m o r yr e q u i r e m e n t o b t a i n ss i m p l i f i e dm o d e l sw i t hh i g h v i e w - d e p e n d e n tr e n d e r i n go fp o i n tc l o u d s t h ec u r r e n tv i e w d e p e n d e n t r e n d e r i n gm e t h o d so fp o i n tc l o u d sc o n s t r u c tm u l t i r e s o l u t i o ns t r u c t u r eu s i n g c l u s t e r i n gm e t h o d s t h i sp a p e rp r e s e n t sav i e w d e p e n d e n tr e n d e r i n gm e t h o d o fp o i n tc l o u d st h a tb u i l d st h ef o r e s ts t r u c t u r eu s i n gp o i n t p a i rc o n t r a c t i o n s t h ef o r e s ts t r u c t u r ei no u rm e t h o di sa b l et op r o v i d em o r ef i n e l yg r a n u l a r i t y t h a ns p a c e - d i v i s i o nc l u s t e r i n ga n dl e s sn u m b e ro fr o o t sa n dl e s s d e p t ho f t r e e st h a nr e g i o n a lg r o w t hc l u s t e r i n g o u rm e t h o da l s oc o n s t r u c t si n d e x l i n k e dl i s t sf o rt h em u l t i r e s o l u t i o ns t r u c t u r e w h i c hc a ni m p r o v et h e e f f i c i e n c yo fs e a r c hd e t a i l s w ec o m b i n ev a r i o u sv i e w d e p e n d e n tc r i t e r i at o d i s t r i b u t ed e t a i l sa tr e g i o n sw i t hd i f f e r e n tv i s u a ls e n s i t i v i t y t h ee x p e r i m e n t a l r e s u l t ss h o wt h a to u rm e t h o dc a ng e n e r a t eb e t t e rs i m p l i f i e dm o d e l sa c c o r d i n g t ov i s u a lr e q u i r e m e n t s k e y w o r d sm o d e ls i m p l i f i c a t i o n ；l o c a le r r o rm e t r i c s ；t r i a n g l em e s h ；p o i n tc l o u dm o d e l i v 插图 皇! 曼! ! ! 曼! ! ! ! ! ! 曼! 曼! ! 曼皇! ! ! 曼! 曼曼曼曼曼曼皇曼曼! 曼! 鼍曼曼! 鼍曼皇i i i ii i i i i 曼苎皇 插图 图1 1 数字米开朗基罗i ：稃扫描的人甲模型l 图1 2 三角网格数据格式5 幽1 3 点元记录的信息6 幽1 4 顶点删除并重新二角化9 幽1 5 边折瞽9 图1 6 点对收缩1 0 图1 7 二角形删除1 1 幽1 8 顶点剑顶点的距离2 0 图i - 9 顶点剑平面的距离2 1 幽1 10 点剑表面的距离2l 图1 1 1 表面到表面的距离2 1 图1 1 2l i n d s t r o m 和t u r k 获取模型图像示意图2 5 图2 1 二角面片的法向量和顶点法向量3 3 图2 2 相对曲率定义3 5 图2 3 顶点v 所在的二角形扇形3 6 图2 4 点对收缩时受影响的二角面片p 3 7 幽2 - 5 新顶点的位置3 9 幽2 - 6 边折叠的次序4 1 图2 7 简化后牛模型的最大误著和平均误差曲线一4 4 图2 8 简化后恐龙模型的最大误差和平均误著曲线4 5 图2 - 9 简化屙脚骨模型的最大误著和平均误差曲线4 6 图2 1 0 原始牛模型及不同算法简化结果比较4 7 幽2 1l 原始恐龙模硝及不同算法简化结果比较4 7 图2 1 2 原始脚骨模型及不同算法简化结果比较4 8 图3 1 点云点对收缩4 9 图3 2 由顶点v 雨i 近邻点构成的切平面一5 0 图3 3 凸的区域体积减少5 2 图3 4 无效点对5 4 图3 5 两个距离很近的面5 5 图3 - 6 新点引起的体积变化5 5 幽3 7 误著颜色条带5 9 图3 8 人象点云原始模型6 0 图3 - 9 人象模型简化到l0 时外观比较6 0 图3 - 1 0 人象模型简化到1 0 时误差分布：6 1 图3 1 1 人体点云原始模型6 1 图3 1 2 人体模型简化剑1 0 时外观比较6 2 图3 1 3 人体模型简化到1 0 时误差分布6 2 图3 一1 4 圣诞老人点云原始模型6 3 图3 1 5 圣诞老人模型简化到1 0 时外观比较6 3 图3 16 圣诞老人模型简化到1 0 时误差分布6 4 图3 1 7 鱼点云原始模型6 4 图3 1 8 鱼模型简化剑1 0 时外观比较6 5 幽3 1 9 鱼模型简化到1 0 时误差分布6 5 图3 2 0 人象模拟简化误差比较6 5 v 1 1 北京t 业人学下学博l 学位论文 图3 2 1 人体模矸! 简化误筹比较6 6 幽3 2 2 圣诞老人模删简化误若比较6 6 图3 2 3 鱼模叶4 简化误筹比较6 7 幽4 1 二次误著等值面反映了表面形状7 3 幽4 2v 的近邻7 4 幽4 3 边缘检测7 5 幽4 - 4 头像原始模喇及简化结果7 6 图4 5 内存数据访问7 8 图4 - 6 原始l u c y 模型及简化结果7 9 幽4 7 原始龙模型及简化结果8 0 幽4 8 原始佛模型及简化结果一8 l 图5 1 距离较远的两个部分划分到一个单元中8 4 幽5 - 2 基丁视点绘制的流群图8 6 幽5 3 生成的森林结构j 8 7 幽5 - 4 带索引的森林结构8 8 幽5 51 ，点指针链表8 8 图5 - 6 法向锥的定义利轮廓的判断8 9 幽5 7 光强和i 误著关系一9 0 图5 8 结果比较。9 2 v i i i f i g u r e f i g u r e f i g 1 1t h ed i v i dm o d e is c a n n e db yt h ed i g i t a im i c h e l a n g e l op r o j e c t 1 f i g 1 2t h ed a t af o r m a to f at r i a n g l em e s h 5 f i g 1 - 3 下h ei n f o r m a t i o ni n c l u d e di nas u r f e l 6 f i g 1 4v e r t e xd e c i m a t i o na n dr e t r i a n g u l a t i o n 9 f i g ，7 5e d g ec o l l a p s e j9 f i g 1 6v e r t e x p a i rc o n t r a c t o n 1 ( ) f i g 1 7t r i a n g l ed e c i m a t i o n 1l f i g 1 8v e r t e x v e r t e xd i s t a n c e 2 0 f i g 1 9v e r t e x e p l a n ed i s t a n c e 21 f i g 1 1 0p o i n t - s u r f a c ed i s t a n c e ，2 1 f i g 1 11s u r f a c e s u r f a c ed i s t a n c e 21 f i g 1 - 12t h es c h e m eo fc a p t u r e i n gi m a g e su s e db yl i n d s t r o ma n d t u r k 2 5 f i g 2 1t h ef a c en o r m a la n dv e r t e xn o r m a l s 3 3 f i g 2 ，2t h ed e f i n i t i o no fr e l a t i v ec u r v a t u r e 3 5 f i g 2 3t h et r i a n g l ef a no f v e r t e x 、，：；6 f i g 2 4t h et r i a n g l epi n f l u e n c e db ye d g ec o l l a p s e 3 7 f i g 2 5t h ep o s i t i o no fn e wv e r t e x ：；9 f i g 2 6t h eo r d e ro f e d g ec o l l a p s e 4 1 f i g 2 7m a x a n dm e a ne r r o r so ft h es i m p l i f i e dc o wm o d e l 4 4 f i g 2 8m a x a n dm e a ne r r o r so f t h es i m p l i f i e dd r a g o nm o d e l 7 4 5 f i g 2 9m a x a n dm e a ne r r o r so f t h es i m p l i f i e db o n e sm o d e l 4 6 f i g 2 1 0t h eo r i g i n a la n ds i m p l i f i e dc o wm o d e l s 4 7 f i g 2 1 1t h eo r i g i n a la n ds i m p l i f i e dd i n o s a u rm o d e l s 4 7 f i g 2 12t h eo r i g i n a la n ds i m p l i f i e db o n e sm o d e l s 4 8 f i g 3 1p o i n t p a i rc o n t r a c t i o n 4 9 f i g 3 - 2t a n g e n tp l a n tf o rc a l c u l a t i n gq u a d r i ce r r o r ! ；( ) f i g 3 - 3v o l u m ec o n t r a c ti nc o n v e xr e g i o n s ! ；：! f i g 3 - 4i n v a l i dp o i n t p a i r ! ；z i f i g 3 - 5t w oo p p o s i n gs u r f a c e st h a tc o m ec l o s et o g e t h e r 5 5 f i g 3 - 6v o l u m ev a r i a t i o nc a u s e db yt h en e wp o i n t 5 5 f i g 3 - 7c o l o rs t r i p eo fe r r o r 5 9 f i g 3 - 8t h ep o i n tc l o u do fao r i g i n a le l e p h a n t 6 ( ) f i g 3 - 9a p p e a r a n c ec o m p a r i s o no fe l e p h a n tm o d e l ss i m p l i f i e dt o1o 6 0 f i g 3 10e r r o rd i s t r i b u t i o no fe l e p h a n tm o d e l ss i m p l i f i e dt olo 61 f i g 3 1l 下h ep o i n tc l o u do f ao r i g i n a lm a n 6 1 f i g 3 一1 2a p p e a r a n c ec o m p a r i s o no f m a nm o d e l ss i m p l i f i e dt o1 0 6 2 f i g 3 1 3e r r o rd i s t r i b u t i o no f m a nm o d e l ss i m p l i f i e dt ol o 一6 2 f i g 3 1 4t h ep o i n tc l o u do f ao r i g i n a ls a n t a 6 3 f i g 3 15a p p e a r a n c ec o m p a r i s o no fs a n t am o d e l ss i m p l i f i e dt o10 6 3 f i g 3 1 6e r r o rd i s t r i b u t i o no f s a n t am o d e l ss i m p l i f i e dt o1 0 6 4 f i g 3 l7t h ep o i n tc l o u do fao r i g i n a lf i s h 6 4 f i g 3 一l8a p p e a r a n c ec o m p a r i s o no ff i s hm o d e l ss i m p l i f i e dt o10 6 5 f i g 3 1 9e r r o rd i s t r i b u t i o no f f i s hm o d e l ss i m p l i f i e dt o1 0 6 5 f i g 3 2 0e r r o rc o m p a r i s o n so ne l e p h a n tm o d e l 6 5 f i g 3 21e r r o rc o m p a r i s o n so nm a l lm o d e i 6 6 f i g 3 2 2e r r o rc o m p a r i s o n so ns a n t am o d e l 6 6 f i g 3 2 3e r r o rc o m p a r i s o n so nf i s hm o d e l 6 7 f i g 4 1q u a d r i ce r r o ri s o s u r f a c e sc h a r a c t e r i z et h el o c a is h a p eo ft h es u r f a c e 7 3 f i g 4 2t h en e i g h b o r so f v 7 4 f i g 4 - 3d e t e c t i n gb o u n d a r y 7 5 f i g 4 - 4t h eo r i g i n a la n ds i m p l i f i e dm a n n e q u i nm o d e l s 7 6 i x 北京t 业人学t 学博f 学位论义 f i g 4 5m e m o r vd a t aa c c e s s 7 8 f i g 4 6t h eo r i g i n a la n ds i m p l i f i e dl u c ym o d e l s 7 9 f i g 4 7t h eo r i g i n a la n ds i m p l i f i e dd r a g o nm o d e l s 8 0 f i g 4 8t h eo r i g i n a la n ds i m p l i f i e db u d d h am o d e l s 8 1 f i g 5 1t w od i s t a n