（计算数学专业论文）三维动画设计中若干数字几何处理问题研究.pdf

山东大学博士学位论文 三维动画设计中若干数字几何处理问题研究 关东东 ( 山东大学数学与系统科学学院，济南，2 5 0 1 0 0 ) 摘要 动画制作，特别是三维动画制作是一项飞速发展的新兴产业，随着三维动 画大片的推出及三维网络游戏的风行，使人们充分意识到了动画产业的巨大的 市场价值及文化价值，许多国家与地区都将三维动画产业定位为新的经济增长 点，我国政府也开始大力扶持和发展本国动画产业。并将相关科研列为国家科 技发展计划中的一项重要内容。三维动画的制作技术虽日臻成熟，但在提高动 画制作的自动化程度、逼真程度及灵活性方面尚有很大余地，因此与三维动画 制作相关的理论与算法成为近年来计算机图形学领域的研究热点，本文对三维 动画制作过程中的三个重要问题：三维网格模型编辑、中间帧动画插值及三维 网格模型简化进行了研究。 三维多边形网格、n u r b s 曲面及子分曲面是目前三维动画制作中三种通 用的角色建模工具，其中又以三维多边形网格模型最为常用，因此针对三维多 边形网格模型，特别是针对由三维扫描设备输出的真实物体的高密度的多边形 网格模型，进行参数化、网格模型简化、多分辨率分析、动画与空间变形、光 影计算及渲染处理的算法研究成为近年来计算机图形学领域中的热点，这一类 问题被统称为数字几何处理( d i g i t a lg e o m e t r yp r o c e s s i n g ) f 司题，近年来，数字 几何处理的内容与提法在国内外相关会议与刊物的文献中逐渐被采用与认同。 本文所作的研究都是针对动画角色的三维多边形网格模型的，属于数字几何处 理范畴。 本文对数字几何处理中的几个重要问题：三维网格模型编辑、网格模型中 间帧动画插值及三维网格模型简化进行了研究与探讨。其中，三维网格模型编 辑是指对动画角色的三维网格模型进行空间变形、m o r p h i n g 、融合等操作的算 法，是三维关键帧动画及动画特效制作中的重要手段。动画中间帧插值是指实 山东大学博士学位论文 i j 现动画角色的网格模型在关键帧姿态间光滑过渡，生成完整的动画序列的过 程，是三维关键帧动画制作中的重要环节。三维多边形网格模型的简化是数字 几何处理中的经典问题，对于高密度的三维网格模型必须进行合理的简化，才 能用于三维动画制作，是动画角色建模中重要的预处理环节。现将本文所作的 工作及创新之处分别概述如下： 基于局部中值坐标表示的网格模型编辑算法： 文中( 第二章) 提出了三维网格模型几何形状的一种相对表示方法局部中 值坐标表示，其原理是根据每个网格顶点及其邻接顶点构造一个局部保形锥 体，并将每个网格顶点的位置表示为对应的局部保形锥体中诸顶点的凸组合， 相应的凸组合系数称之为当前顶点的局部中值坐标。局部中值坐标表示法反映 了网格顶点位置之间的相互关系，较l a p l a c e 坐标表示法而言，局部中值坐标表 示法具有在整体平移、旋转及缩放变换下的不变性，可视为网格模型局部几何 形状的一种“内蕴”表示。依据局部中值坐标对遭受强烈扰动的网格可有效地 进行形状恢复的实验表明，局部中值坐标对网格几何形状具有良好的“记忆” 能力。在进行空间变形及m o r p h i n g 等网格编辑操作的过程中，将保持局部中值 坐标不变作为约束条件，在网格模型达到预想姿态的同时，可有效保持原始网 格模型的局部几何形状。 为实现由局部中值坐标反求网格模型顶点位置的逆运算，文中提出了一种 迭代算法，在固定少数特征顶点位置作为控制顶点之后，根据局部中值坐标所 反映出的顶点之间的相互位置关系，通过迭代过程计算出网格模型中其余顶点 的位置。利用该迭代算法可有效完成多种网格编辑操作，对人体，人脸，马， 牛等多种三维阿格模型的变形、m o r p h i n g 和抗噪恢复等实验表明该迭代方法 是十分有效的。基于局部中值坐标表示的网格模型编辑算法的突出优点是只需 手动指定较少的变形控制顶点即可获得良好的变形效果，且运算速度较快，。使 实际操作更加简单方便。 基于网格模型的三维动画中问帧插值算法： 为解决宽骨桨的兰维网裙犊型的中间帧动画插值问题，文学伤；三章) 挺出 了一种看法，认为计算耐格模型中间帧姿态的关键是挖掘出能够反映网格模型 山东大学博士学位论文 在相邻关键帧之间的本质性的变形信息，而通过对变形信息进行均分处理就能 把握网格模型姿态的光滑过渡过程。为此本文引入了变形梯度向量 ( d e f o r m a t i o ng r a d i e n tv e c t o r ) 模型，该模型同时考虑了网格顶点及其邻近顶点 的变形信息，体现了变形过程中网格模型的局部互相关关系，可有效表示网格 模型在相邻关键帧之间的变形信息。但如何对变形梯度向量进行合理均分是实 现中间帧动画插值的关键，为此文中提出基于矩阵开方运算与矩阵极化分解运 算的两种变形梯度向量的均分算法，并依据变形梯度向量的均分结果计算出对 应时刻中间帧的网格模型姿态。快速计算对动画制作又是至关重要的，为此文 中设计了中间帧插值的两种快速递推算法，即。帧递推”算法和“标尺递推” 算法，以实现对变形梯度向量的快速均分，同时又提出了衡量均分算法的误差 指标，以便提供一种客观的评价指标。本文提出的动画中间帧插值算法，直接 根据角色网格模型的关键帧姿态自动生成中间帧序列，而无需为动匦角色额外 设计骨架模型。实验证明，采用该方法可快速获取合理的、光滑过渡的中间 帧动画效果，形成完整的动画序列。 平面二叉树剖分网格简化算法： 三维网格模型的简化问题可视为对网格模型进行重采样，以选取简化网格 模型顶点集合的过程，合理的重采样策略应使网格模型平坦处的重采样点分布 相对稀疏，而在细节处分布相对稠密，即具有曲率自适应的特性。文中( 第四 章) 提出的参数平面二叉树剖分网格模型简化算法正是一种曲率自适应的简化 算法。该算法利用网格平面参数化将原始网格模型投影至参数平面上，并将网 格各顶点的曲率属性作为对应投影点的灰度，构造出反映原始网格模型曲率分 布的平面灰度图像即曲率背景图，以表征简化过程中对网格模型各部分不同的 采样密度要求。随后根据等灰度分割的原则对曲率背景图进行二叉树剖分，构 造出反映原始网格模型曲率分布的非均衡二叉树结构，并在每个叶节点所对应 的剖分子块中选取一个优化的代表顶点，以构成简化网格顶点集合，上述方法 可使简化网格的顶点分布具有良好的曲率自适应特性，在网格模型的顶点数目 大幅减少的同时可有效保持原始网格模型的细节信息。在利用三维网格平面参 数化算法构造曲率背景图的过程中，虽然会引入较大的投影畸变，但由于后续 i i l 山东呋学博士学位论文 v 的二叉树剖分过程对投影畸变不敏感，因此本文采用了简单而稳定的f l o a t e r s h a p e p r e s e r v i n g 平面参数化算法，并进行简单的优化过程对投影畸变进行一 定修正之后即可进行网格简化。试验表明该算法可获得良好的网格简化结果， 且具有实现简单，执行速度快的优点。 本文对三维动画中设计中的若干数字几何处理问题进行了研究与探讨，将 这几种算法结合起来，可实现三维动画制作流程：采用本文提出的网格模型简 化算法对来源于三维扫描成像设各( 3 dr a n g es c a n n e r ) 的高密度的角色网格模 型进行适当简化，再通过第二章中提出的网格模型编辑算法调整其姿态，生成 动画关键帧，并采用第三章中韵动画中间帧插值算法在相邻关键帧之间自动插 补光滑合理的中间帧序列，可最终生成完整的动画序列。将这几种算法结合起 来可作为现有三维动画制作模式的一种有益补充。实验表明这些方法是有效 的，具有良好的使用价值，并且对三维动画中相关问题的研究具有一定的理论 启发意义。 关键词：三维动画数字几何处理网格模型编辑动画中间帧网格简化 山东大学博士学位论文 s t u d yo ns o m ed i g i t a ig e o m e t r yp r o c e s s i n gp r o b l e m sf o r 3 da n i m a t i 0 1 1 g u a n d o n g d o n g ( m a t h e m a t i cd e p a r t m e n to fs h a nd o n gu n i v e r s i t y , j i n a n ，2 5 0 1 0 0 ) a b s t r a c t a n i m a t i o nm a k i n g ，e s p e c i a l l y3 da n i m a t i o nm a k i n g ，i sap r o m i s i n gi n d u s t r yd e v e l o p i n ga t ah i g hs p e e d a sm a n y3 da n i m a t i o nm o v i e sc o i t 屺i n t ot h em a r k e ta n d3 dn e tg a m e sb e c o m e p o p u l a r , p e o p l ea r cf u l l ya w a r eo ft h eh u g em a r k e tv a l u ea n dc u l t u r a lv a l u eo fa n i m a t i o n i n d u s t r y 3 da n i m a t i o ni n d u s t r yh a sb e e no r i e n t a t e da san e w e c o n o m i cg r o w t hp o i n ti ne u r o p e ， u s a ，k o r e a ，j a p a na n do t h e rc o u n t r i e so rr e g i o n s i nt h i ss i t u a t i o n ，0 1 1 1 g o v n ta l s o b e g i n st os u p p o r ta n dd e v e l o pn a t i v ea n i m a t i o ni n d u s t r yv i g o r o u s l y , a n dc o n s i d e r si t s r e l e v a n t s c i e n t i f i cr e s e a r c ha sa ni m p o r t a n tp a r ti nt h es t a t es c i e n t i f i ca n dt e c h n o l o g i c a ld e v e l o p m e n t p r o g r a m a l t h o u g ha n i m a t i o ni n d u s t r yi sg e t t i n gm a t u r e ，i t sa u t o m a t i c i t y , v e r i s i m i l i t u d ea n d f l e x i b i l i t yr e m a i nt ob ei m p r o v e d t h e r e f o r e ，c o m p u t e rg r a p h i c sr e s e a r c h e sh a v eb e e nf o c u s i n g o nt h e o r i e sa n da l g o r i t h m sr e l a t e dt o3 da n i m a t i o nm a k i n gi nr e c e n ty e a r s i nt h i sa r t i c l e ，t h r e e k e yq u e s t i o n sh a v eb e e np r o b e di n t o ：3 dm a s he d i t i n g ，t w e e n f r a m ea n i m a t i o ni n t e r p o l a t i o n a n d3 dm e s hs i m p l i f i c a t i o n t h r e em o d e l i n gt o o l sa r ef r e q u e n t l yu s e di nc u r r e n t3 da n i m a t i o nm a k i n g ：3 dp o l y g o n a l m e s h ，n u r b ss u r f a c ea n ds u b d i v i s i o ns u r f a c e t h ef i r s to n ei s t h em o s tp o p u l a r a st o p o l y g o n a lm e s hm o d e s ，e s p e c i a l l yt oh i g h - d e n s i t ym e s hm o d e so fr e a lo b j e c t s ，p a r a m e t r i z a t i o n ， m e s hs i m p l i f i c a t i o n ，m u l t i r e s o l u t i o na n a l y s i s ，a n i m a t i o na n dd e f o r m a t i o n ，s h a d ea n ds h a d o w c a l c u l a t i o na sw e l la sr e n d e r i n gp r o c e s s i n gb e c o m ef o c u s e so fc o m p u t e rg r a p h i c si nr e c e n t y e a r s a l lo ft h e mc a nb es u m m a r i z e du n d e rt h e t i t l eo fd i g i t a lg e o m e t r yp r o c e s s i n g i t s c o n c e p ta n dc o n t e n t sa l eg r a d u a l l ya c c e p t e da n da d o p t e di nd o c u m e n t so fr e l e v a n tc o n f e r e n c e s a n dp u b l i c a t i o n s t h i sa r t i c l ef o c u s e si t ss t u d i e so n3 dp o l y g o n a lm e s hm o d e l s ，a c c o r d i n g l y w i t h i nt h es c o p eo f d i g i t a lg e o m e t r yp r o c e s s i n g t h ef o l l o w i n gq u e s t i o n sh a v eb e e nd i s c u s s e di nt h i sa r t i c l e ：3 dm e s he d i t i n g ，t w e e nf r a m e v 山东大学博士学位论文 i n t e r p o l a t i o na n ds i m p l i f i c a t i o no f3 dm e s hm o d e l s t h ef i r s to n ei sa na l g o r i t h mc o n c e r n i n g s p a t i a ld e f o r m a t i o n ，m o r p h i n g ，b l e n d i n ga n do t h e ro p c m u o n so i l3 dm e s hm o d e t h es e c o n d r e f e r st ot h ep r o c e s si nw h i c hs m o o t ht r a n s i t i o nb e t w e e nk e yf r a m ep o s t u r e si sr e a l i z e d ， g e n e r a t i n gac o m p l e t es e q u e n c eo fa n i m a t i o n s i ti st h ec r u c i a lp a r ti n3 dk e yf r a m ea n i m a t i o n m a k i n g t h el a s to n ei sac l a s s i c a li s s u ei nd i g i t a lg e o m e t r i cp r o c e s s i n g r a t i o n a ls i m p l i f i c a t i o n s h o u l db em a d eo nh i g h - d e n s i t y3 dm e s hm o d eb e f o r ei t su s e di n3 da n i m a t i o nm a k i n g t h e f o l l o w i n gi sag e n e r a li n t a 二d u c t i o no ft h es t u d i e sa n do r i g i n a l i t yo ft h i sa r t i c l e m e s he d i t i n ga l g o r i t h mb a s e do nl o c a lm e a nv a l u ec o o r d i n a t er e p r e s e n t a t i o n c h a p t e r2p u t sf o r w a r dar e l a t i v er e p r e s e n t a t i o nf o r3 dm e s hg e o m e t r y - - - l o c a l m e a nv a l u ec o o r d i n a t e sr e p r e s e n t a t i o n ：i ti st oc o n s t r u c tal o c a ls h a p e p r e s e r v i n g c o n ef o re a c hv e r t e xa c c o r d i n gt oi t sa d j a c e n tv e r t i c e s ，r e p r e s e n t i n gt h ep o s i t i o n so f e a c hv e r t e xa st h ec o n v e xc o m b i n a t i o no fe v e r yv e r t e xo fi t sc o r r e s p o n d i n gl o c a l s h a p e p r e s e r v i n gc o n e t h ec o r r e s p o n d i n gc o n v e xc o m b i n a t i o nc o e f f i c i e n t sa r e c a l l e dt h el o c a lm e a nv a l u ec o o r d i n a t e so ft h ep r e s e n tv e r t e x t h e r e f o r e ，t h i s r e p r e s e n t a t i o ns h o w st h ec o r r e l a t i o no fm e s hv e r t e xp o s i t i o n s c o m p a r e dw i t h l a p l a c ec o o r d i n a t e s ，i tc a nr e m a i ni n v a r i a n tu n d e rt r a n s l a t i o n ，r o t a t i o na n ds c a l i n g t r a n s f o r m a t i o n t h u s ，i tc a nb er e g a r d e da sa ni n t r i n s i cr e p r e s e n t a t i o nf o rm e s hl o c a l g e o m e t r y t h ee x p e r i m e n t ，i nw h i c he f f e c t i v es h a p er e s t o r a t i o n i sc o n d u c t e do n s e r i o u s l yd i s t u r b e dm e s h e sa c c o r d i n gt oi t sl o c a lm e a nv a l u ec o o r d i n a t e ，i n d i c a t e s t h a tl o c a lm e a nv a l u ec o o r d i n a t e so w na ne x c e l l e n tm e m o r yf o rm e s hg e o m e t r i c s h a p e i nm e s he d i t i n gp r o c e s ss u c ha ss p a t i a ld e f o r m a t i o na n dm o r p h i n g ，t h el o c a l g e o m e t r yo fo r i g i n a l m e s hm o d ec a nb em a i n t a i n e dw h i l et h em e s hm o d ei s t r a n s f o r m e dt ot h ep r e s c r i b e dp o s t u r ea sl o n ga st h e i rl o c a lm e a nv a l u ec o o r d i n a t e s r e m a i ni n v a r i a n t a st ot h ei n v e r s eo p e r a t i o nf r o ml o c a lm e a nv a l u ec o o r d i n a t e st ot h ep o s i t i o n so f m e s hv e r t i c e s ，t h i sa r t i c l ep r o p o s e sa ni t e r a t i o na l g o r i t h m ，w h i c h ，a c c o r d i n gt ot h e c o r r e l a t i o no fv e r t i c e sr e p r e s e n t e db yt h e i rl o c a lm e a nv a l u ec o o r d i n a t e s ，w o r k so u t t h ep o s i t i o n so fo t h e rv e r t i c e si nm e s hm o d e lb yi t e r a t i o na f t e rf i x i n gt h ep o s i t i o n s 山东大学博士学位论文 o ff e wf e a t u r ev e r t i c e s m a n yk i n d so fm e s he d i t i n go p e r a t i o n sc a l lb ec o m p l e t e d e f f e c t i v e l yb ys u c hi t e r a t i o na l g o r i t h m ，w h o s ev a l i d i t yh a sb e e np r o v e nb yt h e e x p e r i m e n t so nd e f o r m a t i o no fm a n y3 dm e s hm o d e ss u c ha sh u m a nb o d y , f a c e ， h o r s ea n dc o w ，o nm o r p h i n g ，a n t i n o i s e r e c o n s t r u c t i o n ，e t c b e s i d e s ，t h i sm e t h o dh a s a l lo b v i o u sm e r i tt h a tg o o dd e f o r m a t i o ne f f e c tc a l lb ea c h i e v e db ys p e c i f y i n gaf e w d e f o r m a t i o nf e a t u r ev e r t i c e s ，m a k i n gt h ea c t u a l o p e r a t i o n m o r e s i m p l e a n d c o n v e n i e n t at w e e n - f r a m ei n t e r p o l a t i o na l g o r i t h mf o r3 da n i m a t i o nb a s e do nm e s hm o d e ： i no r d e rt os o l v et h et w e e n f r a m ea n i m a t i o ni n t e r p o l a t i o np r o b l e mi n3 dm e s h m o d e ，av i e w p o i n ti sp u tf o r w a r di nc h a p t e r 3t h a tt h ek e yo fg e n e r a t et w e e n f r a m e p o s t u r ei s t o f i g u r e o u tt h e g e o m e t r i ci n v a r i a n tw h i c hr e f l e c t s t h ee s s e n t i a l i n f o r m a t i o no fm e s hd e f o r m a t i o n ，c o n t r o l l i n gt h es m o o t ht r a n s i t i o no fm e s h p o s t u r e st h r o u l g he q u i p a r t i t i o no fd e f o r m a t i o ni n f o r m a t i o n t h i sa r t i c l ei n t r o d u c e s t h ed e f o r m a t i o ng r a d i e n tv e c t o rm o d e lt or e p r e s e n tt h ed e f o r m a t i o ni n f o r m a t i o no f m e s hm o d eb e t w e e nn e i g h b o r i n gk e yf r a m e s h o w e v e r , s i n c er a t i o n a le q u i p a r t i t i o n o ft h ed e f o r m a t i o ng r a d i e n tv e c t o rp l a y sak e yr o l ei nt h er e a l i z a t i o no ft w e e n f r a m e i n t e r p o l a t i o n ，t w oe q u i p a r t i t i o na l g o r i t h m s a r e p u tf o r w a r db a s e do n m a t r i x e v o l u t i o n o p e r a t i o n a n dp o l a r d e c o m p o s i t i o n i na d d i t i o n ，c o n s i d e r i n g t h e s i g n i f i c a n c eo ff a s tc a l c u l a t i o ni na n i m a t i o nm a k i n g ，t h e i rf a s tr e c u r s i o na l g o r i t h m s a r ed e s i g n e di nt h i sa r t i c l e ，r e f e r r i n gt ot h ef l a m er e c u r s i o na l g o r i t h ma n dt h es c a l e r e c u r s i o na l g o r i t h m m e a n w h i l e ，t h ee r r o rc r i t e r i o nf o rm e a s u r i n ge q u i p a r t i t i o n a l g o r i t h mi sp r o v i d e da sa no b j e c t i v ee v a l u a t i n gi n d e x i th a sb e e nv e r i f i e db y e x p e r i m e n t st h a tt h ea b o v em e t h o d sc a na c c o m p l i s hr a p i d l yar e a s o n a b l ea n d s m o o t ht r a n s i t i v ee f f e c to ft w e e n f r a m ea n i m a t i o n t h em e s hs i m p l i f i c a t i o na l g o r i t h mb ys p l i t t i n gw i t hb i n a r yt r e ei np a r a m e t e rp l a n e m e s hs i m p l i f i c a t i o nc a nb ec o n s i d e r e da sap r o c e s so fr e s a m p l i n gt h eo r i g i n a l m e s h e s ar a t i o n a lr e s a m p l i n gs h o u l dp o s s e s st h ec u r v a t u r e a d a p t e da t t r i b u t e ，t h a t i s ，s p a r s e rr e s a m p l i n gp o i n t sa ts m o o t h e rp a r ta n dd e n s e ro n e sa td e t m l e dp a n s t h e v 山东大学博：b 学位论文 v l i i m e s hs i m p l i f i c a t i o na l g o r i t h mu s i n gn o n b a l a n c eb i n a r yt r e eo np a r a m e t e r p l a n ep r o p o s e di nc h a p t e r4i sac u r v a t u r e a d a p t e ds i m p l i f i c a t i o na l g o r i t h m b y p r o j e c t i n gt h eo r i g i n a lm e s ho n t ot h ep a r a m e t e rp l a n ea n de s t i m a t i n gt h ec u r v a t u r e a t t r i b u t e so fe a c hv e r t e xa st h eg r a y l e v e lo fi t sc o r r e s p o n d i n gp r o j e c t i o np o i n t ，t h i s a l g o r i t h m c o n s t r u c t st h ep l a n a r g r a y l e v e lm a pw h i c hr e f l e c t st h ec u r v a t u r e d i s t r i b u t i o no ft h eo r i g i n a lm e s h e s ，n a m e l y , c u r v a t u r eb a c k g r o u n dm a p ，t or e p r e s e n t d i f f e r e n ts a m p l i n gd e n s i t yr e q u i r e m e n t so ne a c hm e s hp a r ti ns i m p l i f i c a t i o n t h e n ， a ni t e r a t i o na l g o r i t h mi su s e dt os e l e c tt h ec u r v a t u r ea d a p t i v e r e s a m p l e v e r t i c e so nt h ep a r a m e t e r i z a t i o np l a n et oc o n s t r u c tt h es i m p l i f i e dm e s h t h ec u r v a t u r eb a c k g r o u n dm a pi ss p l i ti n t ot w op a r t sw i t ht h es a m e s u m m a t i o no ft h eg r a y l e v e lv a l u ei ne a c hs t e p an o n b a l a n c eb i n a r y t r e ew a sc o n s t r u c t e ds i m u l t a n e o u st h es p t i t t i n gp r o c e d u r ew h i c hr e f l e c t s c u r v a t u r ed i s t r i b u t i o n i nt h e c o r r e s p o n d i n gs u b b l o c k o fe a c hl e a fn o d e ，a n o p t i m i z e dr e p r e s e n t a t i v ev e r t e xi sc h o s e nt oc o m p o s et h ev e r t e xs e tf o r t h e s i m p l i f i e dm e s h t h ea b o v ep r o c e d u r e se n s u r et h ev e r t e xs e tt h ec u r v a t u r e a d a p t e d a t t r i b u t e t h i sa l g o r i t h mr e d u c e st h en u m b e ro fv e r t i c e s c o n s i d e r a b l yw h i l e p r e s e r v i n gt h ed e t a i l se f f e c t i v e l y w h e nc o n s t r u c t i n gt h ec u r v a t u r eb a c k g r o u n dm a p w i t h3 dm e s hp l a n a rp a r a m e t r i z a t i o na l g o r i t h m ，s e r i o u sp r o j e c t i n gd i s t o r t i o nm a y b eb r o u g h ti n h o w e v e la ss u b s e q u e n tb i n a r yt r e es p l i t t i n gi sn o ts e n s i t i v et os u c h p r o j e c t i n gd i s t o r t i o n ，as i m p l ea n ds t a b l es h a p e p r e s e r v i n gp l a n a rp a r a m e t r i z a t i o ni s u s e da n dm e s hs i m p l i f i c a t i o ni sc a r r i e do na f t e rs o m cm o d i f i c a t i o n st op r o j e c t i n g d i s t o r t i o nt h f o u i g h s i m p l eo p t i m i z a t i o n e x p e r i m e n t ss h o wt h a t t h i sa l g o r i t h m a c h i e v e sf a v o r a b l es i m p l i f i c a t i o nr e s u l t sw i t hh i g hs p e e da n d s i m p l eo p e r a t i o n s e v e r a lq u e s t i o n sa b o u td i g i t a lg e o m e t r yp r o c e s s i n gi n3 da n i m a t i o nd e s i g n h a v eb e e np r o b e di n t oi n t h i sa r t i c l e c h a r a c t e r sm e s hm o d e c o m i n gf r o m3 d r a n g es c a n n e r , i sf i r s ts i m p l i f i e db yt h em e s hs i m p l i f i c a t i o na l g o r i t h mp r o p o s e di n t h i sa r t i c l e ，t h e ni t s p o s t u r e sa r ea d j u s t e db yt h em e s he d i t i n ga l g o r i t h m ( s e e c h a p t e r2 ) t og e n e r a t ek e yf r a m e s ，a n df i n a l l yt w e e nf l a m ei n t e r p o l a t i o na l g o r i t h m 山东大学博士学位论文 ( s e ec h a p t e r3 ) i se m p l o y e dt of o r mac o m p l e t es e q u e n c eo fa n i m a t i o n s t h e s e a l g o r i t h m sc o m b i n et ob eag o o dc o m p l e m e n tt ot h ec u r r e n ta n i m a t i o nm a k i n g m o d e e x p e r i m e n t sh a v es h o w nc l e a rt h e i rv a l i d i t y , h i 曲u s ev a l u ea n dc e r t a i n t h e o r e t i c a li m p l i c a t i o n so nr e l e v a n tr e s e a r c hi nf u t u r e k e y w o r d s ： 3 da n i m a t i o n ，d i g i t a lg e o m e t r yp r o c e s s i n g ，m e s he d i t i n g ， t w e e n f r a m ea n i m a t i o n ，m e s hs i m p l i f i c a t i o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：苤垒盘日期：尘望! ! 鏊鲫占日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以