（机械设计及理论专业论文）交互式三维模型操作研究.pdf

大连理工大学硕士学位论文 摘要 交互式三维模型操作是基于控制句柄，根据用户对控制句柄的直接操作，使模型本 身产生平滑、具有真实感变形的图形处理技术。该技术可以被广泛应用在虚拟现实、计 算机动画、医学图像处理以及影视娱乐等各个领域。本文对三维模型变形技术和三维模 型网格简化技术进行了研究。 研究了三维几何实体变形技术，通过对几何实体进行层次划分、变形操作来实现三 维实体局部缩放、扭转和弯曲。基于层次操作的三维实体变形技术可精确控制实体的变 形量，并可对几何实体实施组合变形操作，实现复杂的三维实体变形。 研究了三维模型边折叠网格简化算法，将边折叠代价定义为边的长度和其起点重要 度的乘积。简化含有大量顶点的三维模型，生成与之对应的简化网格，有效地降低了三 维模型的求解规模。 研究了基于边折叠网格简化的交互式快速三维形体变形算法。利用边折叠网格简化 算法提取原始三维模型中的形体关键特征点生成简化网格，以交互方式对简化网格添加 位置约束，在简化网格的各个关键点上指定与之相关的仿射变换，通过求解非线性优化 问题来获得各个仿射变换的最优值，获得模型各顶点的变形映射。边折叠网格简化算法 通过提取模型关键特征点，有效地减少了变形操作需要处理的多边形数，结合非线性优 化问题求解，实现了直接交互、实时显示和细节保存的三维形体变形。 基于上述三维模型操作方法的分析研究，开发了三维模型变形系统，分别实现了基 于层次划分的三维几何实体变形和基于边折叠网格简化的三维形体变形。该变形系统利 用v i s u a lc + + 的m f c 框架实现了可视化操作界面，用户使用方便，交互性强。 关键词：三维模型操作；层次划分；边折叠网格简化；仿射变换；非线性优化 交互式三维模型操作研究 s t u d y o ni n t e r a c t i v em a n i p u l a t i o no f3 dm o d e l a b s t r a c t b a s e do l lc o n t r o lh a n d l e sm a n i p u l a t e db yu s e r sd i r e c t l y ，i n t e r a c t i v e3 dm o d e l m a n i p u l a t i o nc a nc r e a t es m o o t ha n dr e a l i s t i cd e f o r m a t i o nr e s u l t s t 【l i st e c h n i q u ei sw i d e l y u s e di nv i r t u a lr e a l i t y ，c o m p u t e ra n i m a t i o n ，m e d i c a li m a g ep r o c e s s i n ga n dm o v i e & t vf i e l d s a3 dg e o m e t r i cs o l i dd e f o r m a t i o nt e c h n i q u ei ss t u d i e d d e f o r m a t i o n so fl o c a lt a p e r i n g ， t w i s t i n ga n db e n d i n ga r ei m p l e m e n t e dv i aa p p l y i n gh i e r a r c h yp a r t i t i o na n dd e f o r m a t i o n o p e r a t i o nt o3 ds o l i d s b a s e do i lh i e r a r c h i c a lo p e r a t i o n ，3 ds o l i dd e f o r m a t i o nt e c h n i q u ec a n c o n t r o l3 ds o l i d sd e f o r m a t i o np r e c i s e l y i tc a na l s oo b t a i nc o m p l e x3 dd e f o r m a t i o nr e s u l t s u s i n gc o m b i n a t i o no fo p e r a t o r s am e s hs i m p l i f i c a t i o na l g o r i t h mt o3 dm o d e li ss t u d i e db yd e f i n i n ge d g ec o l l a p s ec o s to f d i r e c t e d e d g ea s ap r o d u c to fe d g e sl e n g t ha n di t ss t a r t i n gv e r t e x s i m p o r t a n c e t l l i s a l g o r i t h mc a l ls i m p l i f yc o m p l e x3 dm o d e lw i t ha b u n d a n tv e r t i c e se f f e c t i v e l ya n dg e n e r a t ea r e d u c e dm e s h b a s e do ne d g ec o l l a p s em e s hs i m p l i f i c a t i o n ，a ni n t e r a c t i v ea n df a s t3 ds h a p e d e f o r m a t i o na l g o r i t h mi ss t u d i e d u s i n ge d g ec o l l a p s em e s hs i m p l i f i c a t i o nt oe x t r a c tk e y f e a t u r ep o i n t sf r o mo r i g i n a lm o d e l ，3 dr e d u c e dm e s hc a nb eg e n e r a t e d t h e np o s i t i o n a l c o n s t r a i n t sa l ea d d e dt o3 dr e d u c e dm e s hi n t e r a c t i v e l ya n da f f i n et r a n s f o r m a t i o ni ss u p p o s e d f o re a c hn o d ei nt h er e d u c e dm e s h t h r o u g hs o l v i n gan o n l i n e a ro p t i m i z a t i o np r o b l e m ， o p t i m a ls o l u t i o n sa r ef o u n df o ra l la f f i n et r a n s f o r m a t i o n st og e tt h en o d em a p p i n gi no r i g i n a l m o d e l e d g ec o l l a p s em e s hs i m p l i f i c a t i o nc a nb ee f f e c t i v e l yu s e dt or e d u c et h en u m b e ro f p o l y g o ni n3 dm o d e l ，a n dc o m b i n i n g w i t hn o n l i n e a ro p t i m i z a t i o ns o l u t i o n ，ar e a l - t i m ed i s p l a y a n dd e t a i lp r e s e r v e d3 ds h a p ed e f o r m a t i o nc a nb er e a l i z e di n t e r a c t i v e l y as y s t e mo f3 dm o d e ld e f o r m a t i o nh a sb e e ne x p l o i t e dw i t ht h ea b o v em e n t i o n e d m e t h o d s i tc a nr e a l i z e3 ds o l i d sd e f o r m a t i o nb a s e do nh i e r a r c h i c a lo p e r a t i o na n d3 ds h a p e d e f o r m a t i o nb a s e do ne d g ec o l l a p s em e s hs i m p l i f i c a t i o n ，r e s p e c t i v e l y u s i n gm f cf r a m e w o r k o nv c + + p l a t f o r m ，t h es y s t e mh a sv i s u a lo p e r a t i o ni n t e r f a c ea n dm a k e st h eo p e r a t i o n c o n v e n i e n tf o ru s e r s k e yw o r d s ：3 dm o d e lm a n i p u l a t i o n ；h i e r a r c h yp a r t i t i o n ；e d g ec o l l a p s em e s h s i m p l i f i c a t i o n ；a f f i n et r a n s f o r m a t i o n ；n o n l i n e a ro p t i m i z a t i o n 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：塞星塞三丝搓型握笠盈塞 作者签名： 莶绽蛙 日期： 2 1 1j ! 年垃月_ l 日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：塞亘盛三丝搓型握往盈塞 作者签名： 盔经翌 日期： 碰! 望 年堕月j 旦日 导师签名：二拿b 旦4 一 日期：4 年垒月_ 上e 日 大连理工大学硕士学位论文 1绪论 1 1 三维模型操作的研究背景及意义 人类生活在三维世界中，日常生活中所观察到的首先是三维物体。与文字和二维图 像相比，三维模型具有包含信息量大、表现形式直观等特点，更容易被人脑接受、处理 和判别。对三维物体进行建模、变形操作等是计算机图形学和计算机视觉研究的内容， 也正因为如此，关于计算机图形学和计算机视觉的研究越来越受到科研人员的关注，该 领域的研究发展迅速，应用范围广泛。 计算机图形学是研究怎样用计算机表示、生成、处理和显示图形的- - i - 学科l l 】。2 0 世纪5 0 年代初，美国麻省理工学院开始从事现代计算机辅助设计与制造技术的开拓性 研究，这就是关于计算机图形学研究的雏形。当时的工作只是为了在绘图仪和阴极射线 管( c i 盯) 屏幕上输出图形，而随着计算机硬件和算法的发展，计算机图形学已经成为 计算机科学与技术中最为活跃的学科分支之一。 作为一种计算机视觉方面的应用1 2 弓j ，三维模型操作技术近年来备受关注，它的价 值正在研究与实践中不断完善和发展。三维模型操作技术可以使三维模型产生各种各样 的形变，满足产品设计的视觉心理需求等，或对三维网格进行简化，满足传输、存储或 处理三维模型等应用需求。在汽车和飞机的设计与制造、机械产品的计算机辅助设计和 制造、电影特技和动画、军事、医学、工程、艺术、教育和培训、产品展销、虚拟现实 和网络游戏、地理信息系统等众多领域，三维模型操作技术得到广泛的应用。 在医学影像方面，三维模型操作是一种重要应用，可以在计算机中对一些手术进行 模拟【4 】。例如切除肿瘤时，根据手术进展在计算机中动态改变肿瘤的形状和大小，医师 就能清晰地了解肿瘤切除的效果，从而得出最佳的治疗方案。在实际手术过程中，提高 手术的成功率。在医学软件，比如各种治疗计划系统、虚拟手术、虚拟内镜等的开发中， 经常要对所采集的各种模态的医学图像进行三维重建，以更形象地把病人信息展示在医 生面前【5 】。由于医学图像的数据量一般都很大，在处理过程中会产生大量的三角面片， 超出计算机的处理能力，成为系统实际应用的制约因素。基于这些因素，有必要首先对 原始模型进行网格简化，去掉一部分三角面片后再进行三维重建。 在汽车和飞机的设计与制造领域，设计人员可以对汽车或飞机的原始模型进行变形 操作，生成各种形状的模型，设计出不同款式的产品。结合有限元分析等软件，可以在 计算机中对变形后的模型进行力学分析。这样，无须制造出实物，就能预先了解产品性 交互式三维模型操作研究 能的优劣。根据实验结果找出问题的根源，可以多次对三维模型进行变形，直至符合设 计要求。这样不但节约了成本，还缩短了产品开发的周期。 在数控虚拟加工领域，通过对零件进行局部变形从而模拟加工中的切削、洗削或磨 削等加工过程，可在虚拟环境下对零件进行预加工演示，这样能更直观地看出零件加工 过程是否合理，是否会产生干涉。根据模拟结果改进零件加工工艺及加工流程，降低生 产废品的几率。 在艺术造型方面，三维模型操作更有广泛的应用【6 。7 】。自从计算机诞生以后，虚拟 的三维造型艺术也就随之而生。艺术品通常形态怪异，无规则形状，使用三维模型操作 技术，可以在计算机中对规则模型进行变形，生成形态各异的三维模型。这门艺术是在 传统三维造型艺术的基础之上发展起来的，借助于三维模型操作技术，艺术家就能在计 算机虚拟世界中改变艺术品的形态、结构、比例等，在计算机中实现自己的构思，直到 设计出满意的艺术品。 三维模型操作技术也可以用在影视业中的虚拟角色、娱乐、虚拟现实【8 - 9 】等，电影 中常见的应用如从某一动作到另一个动作的变化，或者对于一些给定的卡通人物模型让 它产生跑步、跳舞等复杂的动作变化。这些应用可以使虚拟角色更有生气，使动画效果 更加逼真。 伴随着互联网的快速发展，网上物品浏览受到人们的关注，将呆板的平面展示改为 互动式三维模型操作，可以让客户更清楚地了解产品的特性及结构，具有较高的应用价 值【l0 1 。但三维形体通常信息量大，网络实时显示、浏览、传输这些三维模型对现有的硬 件设备和网络带宽提出了挑战。因而，需要采用模型简化算法对产品模型进行适当的处 理，在保证产品视觉的前提下有效地降低模型的信息量。 在虚拟现实和网络游戏领域，三维模型操作更有广泛的应用。高质量的网络游戏需 要在保证逼真画面的同时保持流畅的速度，这对三维场景的渲染速度提出了很高的要 求。研究发现，当场景中的物体离观察者很远的时候，它们经过观察、投影变换后在屏 幕上往往只是几个像素而己。因而，我们完全没有必要为这样的物体去绘制它的全部细 节信息，可以在不损失画面视觉效果的前提下，适当地合并一些三角形面片。 随着软硬件技术的不断发展，地理信息系统( g i s ) 正逐渐从二维平台向三维人机 交互界面及虚拟现实过渡【l 。三维g i s 可定义为在三维方式下用于采集、存储、管理、 处理、检索、分析和表达地理空间数据的计算机系统。逼真的三维图形显示大大地方便 了人们的日常生活，例如，人们可以从g o o g l ee a r t h 上查看世界各地的地形信息，选择 大连理工大学硕士学位论文 自己的出行线路等。应用网格简化技术可以简化地形，减少地形信息的传送量，大大地 促进了三维地理信息系统的发展。 随着计算机硬件价格的降低和芯片性能的提高，以及计算机交互技术【1 2 】的发展，三 维模型操作的交互性越来越强。人类期望用鼠标在三维空间中按自己的意愿操纵三维模 型，满足自己的设计要求。在这种背景下，交互式三维模型操作技术成为新的研究热点， 涌现出了许多学术论文l l 弘”j 。 交互式三维模型操作主要解决这样一个问题：在三维空间中建立三维模型，用户用 鼠标以点击并拖放的方式在三维模型上选定操纵点；然后，用户按自己的意愿移动操纵 点，三维模型在操纵点的约束下动态地调整自身状态，或改变模型的形状，或产生自然 连贯的动作。该技术具有直接操作和实时显示等优点，应用前景广阔。 总之，随着三维模型操作技术和其它各门应用科学的发展，交互式三维模型操作技 术在这些应用领域的渗透也会越深越广。因此，对交互式三维模型操作技术的研究不仅 具有重要的理论意义，而且，具有重要的实际应用价值。 1 2 三维模型变形技术的研究现状 三维模型变形的一个重要问题是变形控制。为实现变形，需利用控制句柄来操作三 维模型。这些控制句柄可以通过点的形式也可以通过曲线、曲面、甚至是多边形网格， 这些都是三维模型本身的特征。通过改变控制旬柄( 网格、特征线或特征点等) 的方向 和位置对三维模型进行操纵，使形体产生连续、光滑、逼真的变形。因此根据控制句柄 的不同，可以将三维模型变形分为基于点参数控制的变形、基于曲线控制的变形和基于 网格控制的变形。 ( 1 ) 基于点参数控制的三维模型变形技术 此类三维模型变形技术的控制参数和任何隐含的虚拟句柄无直接联系，主要是通过 动态地改变某些参数值，将改变后的值回代到变换公式中，从而重新计算组成三维模型 点的位置，得到变形后的形状。 b 一1 6 j 通过定义变换矩阵实现了三维模型全局或局部变形，此种变换属于点的空间 变换，通过将修改后的参数传递到变换矩阵中，在三维空间的某个坐标轴方向上改变空 间点的位置，得到变形后的形状。可以用鼠标的移动量或鼠标中轮的转动量来修改参数 值，从而精确控制三维模型的形变量。 d e c a u d i n 【1 7 j 在1 9 9 6 年提出了一种空间建模技术。这种技术类似于泥塑，用空间中 一个有一定大小和形状的实体( 称为工具实体) 去影响待变形三维模型点的位置，强迫 待变形模型点按用户的意图移位，从而改变三维模型的形状。这种技术模拟现实生活中 交互式三维模型操作研究 的雕刻工艺，只能对三维模型做粗糙的变形，不能精确地控制模型的形状，主要应用于 艺术作品的创作。 l l 锄2 l s 【i8 1 等人提出了一种称为绞扭器的变形方法，在这种方法中，点的扭转变换用 一个标量函数进行加权。在三维模型上指定一个或多个点位移约束作为句柄，用户可以 抓住在模型表面上或在其临近区域的两个点，同时拖动两个点到新的位置，或在拖动的 过程中旋转句柄产生倾斜、弯曲或扭转等变形。 ( 2 ) 基于曲线控制的三维模型变形技术 基于曲线控制的三维模型变形技术主要是指操作过程中的控制点和一条控制曲线 相关联且在几何上沿着曲线分布，移动控制点时会改变控制曲线的空间形状。在初始状 态，这条控制曲线可以是直线，也可以是曲线。在操作过程中，首先将三维模型上的点 映射到曲线上，用户移动控制点从而改变控制曲线的空间形状，三维模型上的点随着控 制曲线形状的改变而调整自身的位置，从而实现三维模型的变形。 c h a n 9 1 1 9 j 等人提出了一种变形技术，允许用户定义一个贝塞尔曲线坐标轴，在贝塞 尔曲线的每个控制点上都定义了一个局部坐标系。通过操纵各个局部坐标系，用户可以 改变贝塞尔曲线的形状，也就是改变所定义的轴的形状。利用分割递推d ec a s t e l j a u 算 法进行仿射变换，从而改变模型的形状。这种方法属于曲线控制，缺点是不能精确地控 制模型的形变量。为控制模型的变形方向，用户还需对贝塞尔曲线的生成原理有一定的 了解。 上述方法的一个限制是：若三维模型的初始状态为弯曲的，操纵一个初始状态为直 线的控制曲线会得不到期望的变形效果。l a z a r u s t 2 0 j 等人使用初始状态为曲线的控制曲线 对三维模型变形进行了扩展，定义一条参数曲线，空间中的点在沿着曲线的局部坐标系 中进行定义。应用此方法，解决了上述限制。此后，c r e s p i n 2 l 】将曲线变形扩展到表面变 形，取得了比较好的变形效果。 s i n g h 【2 2 】等人受传统雕刻中使用的支架的启发，提出了一个灵活且有效的空间变形 算法。在算法中，用一系列的空间曲线表述三维模型的变形特征，提供了对三维模型粗 糙近似和对其进行变形的方法。s i n 曲嵋3 j 等人将这一概念推广到基于多边形的变形。在 这两种情况下，用户仅仅和代理曲线或多边形交互，而不是和三维模型本身交互。 ( 3 ) 基于网格控制的三维模型变形技术 基于曲线控制的三维模型变形技术的限制是控制点只能沿控制曲线分布，限制了变 形操作的应用范围。基于网格控制的三维模型变形技术可使控制点和空间的三维坐标系 相关联，将三维模型上的点在控制网格中重新参数化，当用户操纵控制网格并改变其形 大连理工大学硕士学位论文 状时，原三维模型随之产生形变，得到变形后的模型。基于控制网格，解决了基于控制 曲线的限制，随后一系列的论文都围绕着这一主题进行了深入的研究。 s e d e r b e r g 2 4 】等人提出了基于网格的自由变形( f r e e f o r md e f o r m a t i o n ，f f d ) 技术， 其主要思想是将三维模型嵌入在一个柔性可塑体中，三维模型点坐标在柔性可塑体中重 新定义，然后在柔性可塑体上定义一个控制网格，当改变控制网格的形状时，模型的形 状也随之改变。f f d 所蕴含的思想是对定义在三维控制网格中的向量进行插值或逼近， 这些向量随后被用来进行空间变换。在s e d e r b e r g 的论文中，使用三元b e m s t e i n 多项式 作为平滑器。实际上，b e m s t e i n 多项式是贝塞尔曲线的调和函数，对于每个空间点，调 和函数是各个控制点对其的权重，离此点越近的控制点其权重越大，换句话说，离此点 越近的控制点对此空间点的影响越大。 在实际应用中，f f d 控制网格的规模不能太大，且控制点只能选在平行六面体上。 为了给用户提供更多的控制点，c o q u i l l a r t 2 5 】提出了一项称为扩展的自由变形技术 ( e f f d ) 。这种方法中的控制网格和三维模型的形状近似，而不再是规则的平行六面 体。这就大大方便了用户对模型的操作。很显然，用户要对变形前三维模型的形状有大 致的了解，才能构建控制网格。 前面所提到的变形技术的一个主要特点是：当模型设计者想要得到所需要的模型 时，必须考虑并设计施加在模型外的控制网格的形状。如果控制网格有一定的自适应性 而且可以进行拓扑的话，设计工作将会变的更加容易。为此，m a c c r a c k e n f 2 6 】等人提出了 基于任意网格拓扑的自由变形技术( s f f d ) ，可以让用户自由定义控制网格并且将其 进行任意拓扑。这种方法的主要思想是利用细分平面技术不断修改原始定义的网格的形 状，当网格变形时由网格定义的变形空间也随之改变，嵌入在网格中的三维模型的形状 也随之发生改变。 尽管h s u 2 7 】等人通过直接操作提供了对三维模型更多的直观控制，但用户仍然受限 于f f d 算法的可表现性。在这些操作中，用户只能通过操纵控制网格来达到操作三维 模型的目的。 前期的变形操作方法主要关注于三维模型形状的改变，不能对三维模型本身进行直 接操作，在变形过程中也没有保存细节信息。这不利于对具有大量细节信息的自然形体 的变形。由于高细节扫描网格的广泛应用，近几年的三维模型变形结合了前三种方法的 优点，所做的研究主要集中在通过直观的用户交互来编辑高质量的网格，以及变形细节 保存等方面。通过多分辨率分解和变分弯曲能最小化，或是操纵微分坐标和求解泊松系 统来获得细节保存的变形表面。 交互式三维模型操作研究 通过产生一个简化网格层次和与之相关的细节系数，多分辨率方法【2 8 】可以取得很好 的细节保存效果。基于微分表示的算法1 2 圳吸收了局部形状属性，如曲率、尺寸和方向等， 利用这些值来表述网格，编辑可以归结为一个试图保存这些值的能量最小化问题。 b o t s c h 3 0 】等人建立了两种方法的外在联系并探讨了它们的内在限制，将两者融合在一种 新的网格变形技术中，保持变形操作的灵活性和有效性。 为解决求解非线性问题收敛速度慢和数值不稳定的问题，h u a n g 3 l 】等人提出了子空 间法，这种技术在原始网格上建立一个粗糙的控制网格并利用平均值插值将变形能和约 束添加到控制网格的顶点。以控制网格顶点的形式在子空间中求解能量最小化问题。在 子空间中，能量最小化求解即快且稳定，并且提供了实时的响应。 以上的算法为保存细节的网格编辑提供了强大的工具。借助于三维模型交互技术的 发展，三维模型变形的交互性成为又一个研究的热点，良好的操作界面方便了用户的操 作，使用户不必再关注于三维模型的表示等繁琐细节，使用鼠标随心所欲地修改三维空 间中模型的形状。z h o u f 3 z j 等人提出了一种对细分平面进行交互变形的算法，让用户在三 维模型的表面上随意地拾取一个点作为句柄，用鼠标操作句柄可使模型上的其他部位随 之产生动作。s u m n e r 3 3 j 等人利用点采样抽取原始模型上的特征点，创建一个与抽样点紧 密相关的称为“变形图表”的简化模型，通过将变形表述为一系列的刚性变换，使得模 型变形尽量刚性。 f e n g 3 4 j 等人基于核典型相关分析( k c c a ) 提出了一种实时数据驱动图形变形方法， 他结合基于泊松变换的方法，采用很少的控制点来同时对整个模型表面进行变形控制， 并基于g p u 技术实时地实现变形的快速计算和显示。b e n c h e n 3 5 】等人提出了一种新的 被称为调和映射的空间变形方法。和原始三维模型相比，映射的结果很自然，且使变形 尽量刚性。 1 3 三维模型网格简化技术的研究现状 在三维模型造型领域，有多种模型表示方式，如实体模型、流型、多边形汤、三角 形网格等。其中，三角形网格是一种常用的表示方式。为保证形体的真实感和层次感， 往往需要高度复杂、高度细节化的三角形网格模型。随着三维数据获取设备的普及，在 计算机中生成和处理具有几百万乃至于上亿个三角形的复杂模型已并不鲜见。所带来的 问题是：计算机存储、计算和处理网格模型的代价往往与模型中三角形面片的数量成正 比，庞大的网格数据对计算机的容量和处理能力等提出较高要求，给模型的存储、传输、 大连理工大学硕士学位论文 计算、绘制等带来困难。因而，可应用网格简化技术对原始模型进行简化处理，满足各 种应用需求。 三维模型网格简化是指在保持原模型几何形状不变的前提下，采用适当的算法减少 该模型的面片数、边数和顶点数【3 6 1 。网格简化对于几何模型的存储、传输、处理，特别 是对实时绘制有着重要的意义。根据网格简化过程中删除掉的网格元素，可将网格简化 方法大致分为三类：基于顶点移除的网格简化、基于面折叠的网格简化和基于边折叠的 网格简化【3 7 】。 ( 1 ) 基于顶点移除的网格简化 该类方法按一定的准则重复删除不必要的顶点，以减少网格模型的顶点数，其基本 准则是尽可能删除那些与其1 环顶点近似共面的顶点( 如在图1 1 中，v 的1 环顶点为 m v 6 ) 。删除该顶点后，采用递归环分割等方法对删除顶点后所留下的孔洞重新进 行三角剖分。 h 哆 v 1 哆k 图1 1项点移除网格简化示意图 f i g 1 1 s c h e m a t i cd i a g r a mo fv e r t e xr e m o v e dm e s hs i m p l i f i c a t i o n s c h r o e d e r 【3 8 1 等人使用的方法就是在网格的局部范围内拟合一张平面，删除那些到该 平面的距离小于预定误差的顶点。h 锄a 1 1 1 1 p 9 j 的方法则通过删除曲率小于预定精度的顶 点来简化网格。 ( 2 ) 基于面折叠的网格简化 面折叠简化算法则通过选择网格中的三角面片，并代之以一个新引入的网格顶点来 简化网格。此类算法的关键是，如何选取将要折叠的三角形以及如何确定引入新顶点的 位置。 通常，面折叠算法在三维网格上搜索共面或近似共面的面片，并将其合并为一个更 大的多边形，而后通过重新三角化得到数量更少的面片，由此得到简化网格，如图1 2 交互式三维模型操作研究 所示。此类算法的关键是应用何种规则确定共面度。超平面方法【删通过边界逼近扩展了 该算法，并提供了更加健壮的重新三角化方法。 图1 2 面折叠网格简化示意图 f i g 1 2 s c h e m a t i cd i a g r a mo ff a c ec o l l a p s e dm e s hs i m p l i f i c a t i o n ( 3 ) 基于边折叠的网格简化 边折叠算法通过反复执行折叠网格中一条边的操作来简化网格模型。与面折叠算法 相似，边折叠算法必须解决的两个问题是如何选取折叠边及如何确定替代折叠边的新顶 点。h o p p e 4 q 在1 9 9 3 年首先采用能量优化的方法实现边折叠算法。该算法定义一个全局 能量函数来确定边折叠的误差，因此时间复杂度高，不适用于对时间要求较高的场合。 为了降低时间复杂度，g a r l a n d 4 2 1 在1 9 9 7 年提出了二次误差测度的边折叠方法。这种方 法计算比较简单、速度快，能够得到与h o p p e 能量优化方法质量很接近的简化模型，但 在误差测度中只考虑了距离的度量，简化后的网格分布较为均匀，因此大规模简化后并 不能很好地保持模型表面重要的几何特征。杜晓掣4 3 】等人在g a r l a n d 算法基础上引入三 角形重要度概念，并加入到误差测度中，使得二次误差测度不仅能够度量距离偏差，而 且能够反映模型局部表面几何变化。 1 4 本文研究的主要内容 基于目前计算机图形学的研究热点和发展方向，本文对交互式三维模型操作技术进 行了研究。着重研究了三维模型变形技术和网格简化技术。 在几何实体变形操作方面，研究了基于层次划分的三维实体变形技术，在交互模式 下，通过对几何实体进行层次划分、变形操作来实现三维实体局部缩放、扭转和弯曲。 并对几何实体实施组合变形操作，实现复杂的三维实体变形效果。 在三维模型网格简化方面，研究了边折叠网格简化算法，将边折叠代价定义为边的 长度与其起点重要度的乘积，并编程实现了三维模型简化效果。 一8 一 大连理工大学硕士学位论文 在三维网格变形操作方面，研究了基于边折叠网格简化的三维形体变形，利用边折 叠网格简化算法提取原始三维模型中的形体关键特征点生成简化网格，以交互方式对三 维模型添加位置约束，在简化网格的各个关键点上指定与之相关的仿射变换，通过求解 非线性优化问题来获得各个仿射变换的最优值，获得原始模型各节点的变形映射。实现 了直接交互、实时显示和细节保存的三维形体变形。 本文各章节的具体安排如下： 第一章：绪论。阐述了三维模型操作技术的研究背景、研究内容和研究意义。介绍 了现有的三维模型变形技术和网格简化技术，并归纳前人研究工作的进展情况。 第二章：基于层次操作的三维实体变形技术。阐述了图形的表示方法、三维实体变 形原理和三维实体局部缩放、扭转和弯曲等概念。并在v c + + 6 o 平台上利用o p e n g l 编程实现了三维实体局部缩放、扭转、弯曲及组合变形。 第三章：边折叠网格简化算法。将边折叠的代价定义为边的长度与其起点重要度的 乘积，并编程实现了三维模型的简化效果。 第四章：基于边折叠网格简化的三维形体变形。介绍基于边折叠网格简化的三维形 体变形的原理、优化目标函数及其优化求解方法。基于边折叠三角形网格简化算法，生 成原始三维形体的简化网格模型。给出三维形体变形的目标函数，利用高斯牛顿迭代求 解此非线性优化问题。通过重新计算形体顶点的位置来实现三维形体交互式变形。并在 v c + + 6 0 平台上利用o p e n g l 编程实现了直接交互、实时显示和细节保存的三维形体变 形。 第五章：系统实现。介绍了三维形体变形系统的设计原则、编程环境及主要的程序 模块和函数，并展示了系统的界面、实现功能等。 总结：总结本文的主要工作，并对以后的工作做出展望。 交互式三维模型操作研究 2 基于层次操作的三维实体变形技术 2 1图形的表示方法 图形通常是由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性 组成【4 4 1 。形体在计算机中常用线框、表面和实体三种形式表示： ( 1 ) 线框模型 线框模型是最早用来表示形体的模型，在计算机图形学和c a d c a m 领域仍在广泛 应用。其特点是结构简单、易于理解，又是表面和实体模型的基础。线框模型是用顶点 和相邻边来表示形体。 ( 2 ) 表面模型 表面模型是用有向棱边围成的部分来定义形体表面，由面的集合来定义形体。表面 模型是在线框模型的基础上，增加有关边( 环边) 信息以及表面特征、棱边的连接方向 等内容。从而可以满足面面求交，线、面消隐、明暗色彩、数控力n - r _ 等应用问题。 ( 3 ) 实体模型 实体模型主要是明确定义了表面的哪一侧存在实体，可以有三种方法来定义。在定 义表面的同时，给出实体存在侧的一点；直接用表面的外法矢来指明实体存在的一侧； 用有向棱边隐含地表示表面的外法矢方向。 形体表示的线框、表面和实体模型是一种广义的概念，并不反映形体在计算机内部， 或对最终用户而言所用的具体表示方式。从用户角度看，形体表示以特征表示和构造的 实体几何表示( c s g ) 较为方便；从计算机对形体的存储管理和操作运算角度看，以边 界表示( b r e p ) 较为实用。 ( 1 ) 特征表示 特征表示是从应用层来定义形体，因而可以较好地表达设计者的意图，为制造和检 验产品和形体提供技术依据和管理信息。 ( 2 ) 构造的实体几何表示 构造的实体几何( c s g ) 的含义是任意复杂的形体都可以用简单形体( 体素) 的组 合来表示。通常用正则集合运算( 构造正则形体的集合运算) 来实现这种组合，其中可 配合执行有关的几何变换。 ( 3 ) 边界表示 边界表示详细记录了构成形体的所有几何信息及其相互连接关系拓扑信息，以 大连理工大学硕士学位论文 便直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、 点为基础的各种几何运算和操作。 对于更复杂的自然形体，可以用n u r b s 、细分平面、隐式曲面、二维图像和三维体 素数据等表示。 2 2 基于层次操作的三维实体变形原理 可以将三维实体变形看作是在变形函数厂作用下由未变形图形映射到变形图形的 过程，从而改变组成三维实体点的坐标值，得到变形后的图形。基于层次操作的三维实 体变形首先将三维实体在某一坐标方向上进行层次划分和精确定义实体的改变量，指定 局部变形部位。然后根据不同的局部变形的变形公式厂，重新计算变形部位点坐标值， 得到变形后的结果。在本章中，设x ，y ，z 表示未变形实体点的坐标，x ，】，z 表示变形后 实体点的坐标。 2 2 1 三维实体局部缩放 局部缩放是指缩放实体局部坐标值，这里设定实体的x 坐标值不变，同比例缩放其 y 和z 两个坐标值。由于x 方向的坐标值不变，一种很自然的想法是将实体沿x 轴分层， 修改所选层的其它两个坐标值。因而定义了一个以x 为自变量的分段线性函数厂( x ) ( 即 为缩放函数) ，来指明实体y 和z 坐标值在x 处是否缩放及其缩放系数。对于坐标值为 的层，当f ( x o ) l 时，此层放大；当f ( x o ) = l 时，此层不缩放；当0 f ( x o ) 1 时，此 层收缩；当f ( x 。) = 0 时，此层变为空间中一点；当f ( x 。) 0 ，此层y 和z 坐标值翻转。 缩放函数定义如下： 厂= 厂( x ) ( 2 1 ) 实体缩放前后点坐标的关系式为： ix = x l y = r y( 2 2 ) lz - - 肱 2 2 2 三维实体扭转 同样以实体绕x 轴扭转为例，将实体沿x 轴分层，当三维实体整体绕x 轴扭转一定 角度时，分别计算各层扭转的角度。为此定义一个扭转函数f ( x ) ，表示坐标值为x 的层 扭转的角度。扭转函数定义如下： 交互式三维模型操作研究 0 = 厂( x ) 上式中a 表示坐标值为x 的层扭转的角度， 变换知识推导扭转前后实体点坐标关系式如下： ( 2 3 ) 记g = c o s ( a ) 、s o = s i n ( a ) 。利用旋转 l x 爿 y = 冯+ 少g ( 2 4 ) 【z = z c o 一妈 2 2 3 三维实体弯曲 同样以三维实体沿x 轴弯曲为例。假设弯曲区间是，】，在弯曲区间之外，实体 的弯曲角度为常数；在弯曲区间之内，弯曲角度线性变化。设三维实体弯曲的曲率为k ， 坐标值为x 的层弯曲角度为0 。当x 。时，实体不弯曲，故口= 0 ；当 x ，秒 线性变化，故口= k ( x 一) ；当x ，实体以常数a = k ( x m = 一) 弯曲。综合以上 三种情况，可由以下公式计算弯曲角度a ： 秒- - - 尼( 圣一x m i i l ) ( 2 5 ) 其中： ix m i n x z m i n 曼= x x m i n x x m 瓠 ( 2 6 ) 【x m 觚x x m a x 记巳= c o s ( a ) 、s o = s i n ( a ) 。利用曲率知识h 5 1 推导弯曲前后实体点坐标关系式如下： i 一( y 一1 七) + x m i 。+ c ；( x 一i n ) x = 一- ( y 一1 七) + x m i n 【一s o ( y 一1 k ) + x m i n + c ( x x 。越) i q ( y 一1 七) + 1 k + s o ( x k i n ) y = g ( y 一1 七) + 1 k 【q ( y 一1 七) + 1 k + s o ( x 一双) z = z x 吒哪 x x m 大连理工大学硕士学位论文 2 3 基于0 p e n g l 的三维实体变形实现 2 3 1 0 p e n g l 简介 o p e n g l 是由s g i 公司推出的独立于操作系统和硬件环境的开放式三维图形库，是 图形硬件的软件接口。从本质上说，它是一个3 d 图形和模型库，具有高度的可移植性， 并且具有很快的渲染速度。它广泛应用于医学图像、地理信息、游戏、气候模拟等领域， 是3 d 图形的工业标准。o p e n g l 使用简单，效率高。它具有强大的功能，如下所述： ( 1 ) 三维物体建模。o p e n g l 图形库使用基本的点、线、多边形等绘制函数绘制三 维物体。除此之外，还提供了如球、锥、多面体、茶壶等复杂三维物体以及像贝塞尔、 n u r b s 等复杂曲线的绘制函数。 ( 2 ) 物体坐标变换。o p e n g l 图形库的变换包括视图变换、模型变换、投影变换和 视口变换。模型变换有平移、旋转、缩放等三种变换，投影变换有平行投影和透视投影 两种变换。 ( 3 ) 材质和光照设置。o p e n g l 定义的光有辐射光、环境光、漫反射光和镜面光。 在一个场景中，可同时使用这几种光类型。材质属性使用光反射率来表示。场景中物体 最终反映到人眼的颜色是光的红绿蓝分量与材质红绿蓝分量的反射率相乘后形成的颜 色。通过混合、抗锯齿、雾和多边形偏移等渲染操作，得到逼真的物体显示效果。 ( 4 ) 颜色模式设置。o p e n g l 颜色模式有两种，即r g b a 模式和颜色索引，可满足 不同的应用需求。 ( 5 ) 双缓存动画。双缓存即前台缓存和后台缓存，简而言之，后台缓存计算场景、 生成画面，前台缓存显示后台缓存己画好的画面。显示时交换前后缓存，使显示效果平 滑过渡，特别适用于渲染大型场景。此外，利用o p e n g l 还能实现深度暗示、运动模糊 等特殊效果。 o p e n g l 是作为一种新型的接口来设计的，它与硬件无关的特性，使其可以在不同 的硬件平台上实现。本章中，首先在m f c 中设置o p e n g l 的渲染环境，调用o p e n g l 的画图函数实现三维实体的显示。借助于m f c 自动生成的窗口框架，处理鼠标和键盘 响应事件，实现程序的交互界面。同时，在o p e n g l 中启用双缓存渲染方式，实现三维 实体显示的平滑过渡，达到实时显示的效果。 2 3 2 三维实体模型生成 本章中的变形是基于点的操作，在实现过程中，为方便实现o p e n g l 的拾取操作1 4 6 1 ， 定义一个空间点结构体如下： 交互式三维模型操作研究 t y p c d c f s t r u c tg l p o i n t g l d o u b l ex ，y # ；空间点的坐标 b o o li s s e l e c t e d ；肼示记此点是否被选中 g l u i n tc o u n t ；点在直线上的编号 s t l a l c to l p o i n t * n e x t ；指向下一个点 ) g l p o i n t ； 利用上述定义的空间点结构体，编写画线函数，此函数实现的功能是：根据直线