（计算机应用技术专业论文）网格曲面中变形算法的研究.pdf

浙ij 大学硕士学位论史摘赞 摘要 为了解决造型过程中出现的形状编辑问题，常常需要进行曲面变形与编辑。 本文针对这个问题，主要研究了自由变形、l a p l a c i a n 编辑、骨架提取和基于骨 架的曲面变形技术。 通过比较多种自由变形技术，本文使用了一种实现简单且直观的自由变形方 江、。通过交互的调整参数，我们可以随意的对模型网格进行自由变形。实验证明 该方法在交互性以及效率上同比相关算法有很大的优势。本文中的l a p l a c i a n 编 辑算法能够很好地保持网格变形之后局部细节的特征。使用该技术。我们开发了 相关的一些编辑技术，比如基于轮廓绘制的变形。通过选取网格轮廓的区域。对 其进行2 d 的重绘，网格轮廓上的顶点将重新调整，该调整将作为l a p l a c i a n 编 辑的约束条件，随后通过求解线性系统来得到变形后的网格曲面。骨架的提取我 们选择使用v o r o n o i 图的方法，通过使用q h u l l 或g p u 方法来为曲面网格计算 v o r o n o i 图，得到一个v o r o n o i 顶点集，然后去除曲面网格外部的v o r o n o i 顶点， 最后对内部的各个v o r o n o i 域顶点计算其算术平均，这样我们可以为每个v o r o n o i 域计算出一个均值点，该点我们认为是骨架顶点。骨架顶点与曲面网格顶点一一 对应，并且继承了对应点的拓扑关系。这为骨架恢复成原始网格提供了实现基础。 给定某个模型网格，对其进行骨架提取，然后对骨架进行自由变形或l a p l a c i a n 编辑，最后将变形后的骨架恢复成原始网格的过程是本篇论文硪究的思路。 本文的算法在原型系统中实现，通过测试多个模型，验证了它们的有效性。 关键词 自由变形，l a p l a c i a n 编辑，基于v o r o n o i 的骨架网格 塑! ! 查兰堡主兰丝堡兰 ! 坚竺竺 a b s t r a c t t os o l v eo b j e c tm o d e l i n gp r o c e s so fe d i t i n gs h a p e s ，o f t e nr e q u i r es u r f a c e d e f o r m a t i o na n de d i t i n g f r e e - f o 加d e f o r m a t i o n l a p l a c i a ne d i t i n g ，s k e l e t o ne x t r a c t i o n a n dt h es k e l e t o n b a s e ds u r f a c ed e f o r m a t i o nt e c h n i q u e sa r es t u d i e df o rt h en e e d so ft h i s p r o b l e m b yc o m p a r i n gm a n yf r e e f o r md e f o r m a t i o nt e c h n o l o g i e s ，t h ep a p e r u s e sas i m p l e a n di n t u i t i v er e a l i z a t i o no ft h ef r e e f o r md e f o r m a t i o nm e t h o d t h r o u g hi n t e r a c f i v e a d j u s t m e n to fp a r a m e t e r s ，w ec a n 窑i v ct h em o d e lm e s hf r e e - f o r md e f o r m a t i o ne a s i l y e x p e r i m e n t sh a v ep r o v e dt h a tt h em e t h o do fi n t e r a c t i o na n dt h ee f f i c i e n c yo f a l g o r i t h m si sa ne n o r m o u sa d v a n t a g e i nt h i sp a p e r , t h el a p l a c i a ne d i t i n ga l g o r i t h m c a nc a l t yi n f o r m a t i o na b o u tt h el o c a ls h a p eo ft h es u r f a c e ，t h es i z ea n do r i e n t a t i o no f l o c a ld e t a i l s t h eu s eo ft h et e c h n o l o g y , w ed e v e l o p e ds o m er e l e v a n te d i t i n g t e c h n i q u e s s u c ha ss i l h o u e t t es k e t c h i n gd e f o r m a t i o n b yc h o o s i n gt h em e s hs i l h o u e t t e o ft h er e g i o n a la n ds k e t c h i n gt h e2 dm e s hs i l h o u e t t e t h e na d j u s tt h es i l h o u e t t ev e a i c e s t h ea d j u s t m e n tw i l ls e l w ea st h el a p l a c i a ne d i t i n gc o n s t r a i n t s ，f o l l o w e db ys o l v i n g l i n e a rs y s t e m st og e tt h ed e f o r m e dm e s h w eu s et h ev o r o n o jd i a g r a mt oe x t r a c t i n g s k e l e t o n ，a n du s et h eq h u l lo rg p um e t h o dt oc o m p u t ev o r o n o id i a g r a mf o rs u r f a c e ， t h e nw eg e tav o r o n o iv e r t i c e s r e m o v et h eo u t e rv e r t i c e so fs u r f a c ef r o mt h e m ap o i n t c o r r e s p o n d i n gt oam e s hv e r t e xi sc o m p u t e d 硒t h ea r i t h m e t i cm e a no ft h er e m a i n i n g v o r o n o iv e r t i c e so ft h ev o m n o ir e g i o nc o n t a i n i n gt h em e s hr e f l e x f i n a l l yt h eo b t a i n e d s e to ft h es k e l e t o nv e f l i c e si se q u i p p e dw i t ht 1 1 ec o n n e c t i v i t yo ft h eo r i g i n a lm e s h g i v e na 西dm o d e _ i ，g c ti t ss k e i e t o ne x t r a c t i o n ，a n dt h e nd of r e e f o r md e f o r m a t i o no f l a p l a c i a ne d i t i n go nt h es k e l e t o nm e s h ，f i n a l l y , t h er e c o n s t r u c t i o no ft h ed e f o r m a t e d s k e l e t o nm e s ht ot h eo r i g i n a lm e s hi st h em a i ni d e ao ft h i sp a p e r 耵l ea l g o r i t h m si nt h i sp a p e ra l ep r o v e dp r a c t i c a la n de f f i c i e n ti no u rp r o t o t y p e s y s t e m k e y w o r d s f r e e f o r md e f o r m a t i o n ，l a p a l i c a ns u r f a c ee d i t i n g ，v o r o n o i b a s e ds k e l e t a l m e s h i i 浙i l 大宁硕士宁位论文第1 章绪论 第1 章绪论 计算机辅助设计与制造( c o m p u t e ra i d e dd e s i g n & c o m p u t e ra i d e d m a n u f a c t u r e ，简写为c a d c a m ) 技术，是计算机应用的最重要的领域之一，它指 利用计算机技术完成设计过程中的信息检索、分析、计算、综合、修改及文件编 制工作。它是先进制造技术的重要组成部分，是计算机在工程中最有影响的应用 技术之。c a d c a m 技术从根本上政变了过去的手- 绘图、发图、凭图纸组织 整个生产过程的技术管理方式，将它变为在图形工作站上交互设计、用数据文件 发送产品定义、在统一的数字化产品模型下进行产品设计打样、分析计算、工艺 计划、工艺装备设计、数控加工、质量控制、编印产品维护手册、组织备件订货 供应等等。 c a d 技术的迅速发展和推广应用，给古老的制造工业带来了蓬勃生机，使传 统的设计方法与生产组织模式发生了深刻的变化为企业实现产品设计现代化、缩 短设计周期、提高产品质量、增强市场应变能力和生存能力、参与国际市场竞争 提供了强有力的技术手段。c a d 技术的开发与应用水平已成为衡量一个国家科技 现代化和工业现代化水平的重要标志之一。c a d c a m 技术已日趋成熟，其应用 范围也从早期的军事、航空航天、机械、电子等工业部门扩展到冶金，建筑、化 学、医学、教育、影视、广告等各个专业领域。 作为c a d c a m 技术的理论基础的计算机辅助几何设计( ( 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 ，简写为c a g d ) ，在1 9 7 4 年的第一届c a g d 国际会议上被首 次提出以后。计算机辅助几何设计开始以一门独立的学科出现。c a g d 是对几何 外形信息的计算机表示、分析和综合，研究的是计算机表示以及用计算机控制有 关形状信息的问题。几何外形信息是指那些定义曲线曲面的点、切矢、扭矢、控 制多边形等。按照这些几何信息构造曲线曲面的数学模型存储于计算机，这就是 计算机表示。用计算机控制就是控制曲线曲面的形状，使构造的曲线曲面符合设 计要求。c a g d 是由函数逼近论、微分几何、代数几何、计算数学，特别是数控 技术等形成的边缘学科。随着现代工业的发展，计算机在几何设计中的应用愈来 愈多，有关计算机辅助几何设计的数学方法的研究也在不断深化。并逐渐形成了 具有自己的独特优点和研究领域的新学科。它的每一个重大技术突破都会影响着 诸如计算机图形学、计算机视觉、机器人技术、医学图象处理、可视化、多媒体 技术等许多相关领域的进步与发展。 l1 曲面变形技术综述 造型技术在计算机建模和动画中应用广泛，现有的许多技术己经被用于造型 工作和乏维人物变形，帮助人们设计更真实、更复杂的几何体，提高设计质量， 并大大减少设计的工作量。 几何曲面在计算机中是通过离散曲面表示的，通常会使用三角曲面或四边形 新“大学硕士学位论文第1 章绪论 曲面，本文主要研究离散点曲面的自由变形以及三角曲面的变形。曲面变形中主 要包括曲面编辑操作。 曲面编辑是指用户通过交互方式，对曲面上的一些点或线进行拖动或重绘， 使其形状随着用户所期望的方式变化，最终目标曲面不仅要经过这些拖动后的点 或线，而且要保持原曲面的细节特征。 为了更方便、更直观地构造和编辑三维模型，b a r d i | 最早提出了整体和局部变 形的方法。模拟了力学中常见的几种变形，如拉伸、均匀张缩、扭转和弯曲等， 并给出了这些变形的数学表示。在对物体的各个部分实施变形时，其变换是基于 位置的函数。应用b a r r 的方法，可以生成血多类型的i 维几何形状。由于该方法 只能用于特定的几何形体，一般将其称为非自由型变形。 此后许多学者继续探索如何进行自由变形以及如何将变形造型方法融入到传 统的c a d c a m 系统中。s e d e r b e r g 等人1 2 】最早提出了自由变形方法肿 ( f r e e - f o r md e f o r m a t i o n ) 。其核心思想是：不直接对物体进行变形操作，而是作 用与物体所嵌入的空间格子( l a t t i c e ) ，然后传播到物体本身。见图1 - 1 。 图1 - 1 自由变形( 2 d ) c o q u i l l a r t l 3 1 提出的扩展b f d ( e x t e n d e d f r e e f o r m d e f o r m a t i o n ) 方法，使得初 始的格子可以有更多的形状，如棱柱体、圆柱体等，从而增加了f f d 技术的使用 范围。有理f f d ( r a t i o n a lf r e e f o r md e f o r m a t i o n 。r f f d ) 方法是对f f d 方法的 另一种推广，它把格子表示为有理形式的三参数张量积b e z i e r 体，从而使用户还 可以通过权因子来控制变形。h s u 等【4 受i j 运行用户直接控制嵌入曲面上的点的变 化位置，然后反求格子顶点的变化以达到所需要的变形。l a m o u s i n 等1 5 j 提出了一 浙i l 大学硕士学位论史第l 章绪论 种基于n u r b s 的f f d 方法( n f f d ) ，把整体和部分变形有机地结合起来，对所 嵌入的物体提供了更多的控制余地。1 9 9 6 年，m a c c r a c k c n 和j o y l 6 提出了用任意 拓扑的格子来控制物体变形，使得变形控制更加直观和灵活。 自由变形方法具有很大的灵活性，但是当格子中控制顶点数目比较多时，调 整格子中控制顶点的工作将变得耗时。 y o s h i z a w a l 7 1 介绍了一系列的自由变形技术，其中一个比较显著的特征是没有 使用仟何的网格连通信息，因此可以被用于针对散乱点的自由变形。虽然该算法 是众所周知的自由变形方法的修改，但在具体实现上更加简单而直观。 最近基于曲面的网格编辑方法，由于其能够得到很好的效果同时在用户使用 上保持了数据计算的透明性，逐渐受到重视。用户只要确定一个结果目标，可以 通过调整控制点位置，关键帧或者轮廓，然后变形系统会自动的求解一个稀疏矩 阵方程来满足限制。尽管如此，一个严重的问题，其延展性仍然阻碍了使用该技 术。当网格变得相当大而复杂时，求解算术方程的性能将会是整个系统的瓶颈。 而针对该问题的解决方法是，更小的感兴趣区域( r o d ，预计算的矩阵分解，以 及预计算的变形基础，这些都限制了编辑操作的范围。 在计算机图形学中通常情况下使用全局坐标系来表示曲面：对点，顶点或节 点通常使用绝对的欧氏坐标系来明确表示。用于在欧式空间中定义的函数集来明 确表示曲面形状。全局坐标系通常被用于进行渲染显示，相交检测的计算以及平 移旋转等操作。而局部曲面造型往往更关注于局部的形状而不需要知道在欧氏空 间中的绝对的位置和方向。 操作和修改曲面的同时保持曲面原有的细节特征在曲面编辑中相当重要，在 前面提到的一系列的自由变形中也一样。而在这些操作中点的绝对位置已经不那 么重要了。我们将会引入一种内部曲面表示法。 我们在描述几何曲面时，使用顶点差坐标系表示法。该方法提供了有效的内 部曲面表示，当曲面重构到全局坐标系时，它将根据我们在使用时所给出的模型 限制条件，来尽可能多地保持原曲面的局部细节特征。使用表示差来做编辑操作 已经在图像中获得很好的效果惮l 。 s o r k i n e 等人1 9 1 提出了在曲面网格编辑中，使用一种顶点与其相邻点的关系的 坐标方法。顶点与其周围相邻点的差被称为l a p l a c i a n 坐标呲1 1 1 2 - 13 1 。l a p l a c i a n 坐 标是全局几何网格的线性函数，它能够通过求解稀疏线性系统来转换绝对法和内 部法表示的曲面。但是l a p l a c i a n 坐标不适合进行缩放和旋转。这是它存在的一个 实际问题。 浙z i 大学硕士学位论立 第1 章绪论 局部与全局的自由变形技术在计算机图形学以及造型应用上都非常重要。针 对网格的多种解决方法5 ，7 哪已经被使用在可视化交互造型上。最近基于骨架 的全局自由变形方法逐渐得到大家的注意1 9 , 2 0 2 1 , 2 2 1 ，因为它能够实现形状的骤然 变化。 在本文中，我们也给出了种基于骨架的全局变形方法。首先，我们提取出 三角网格的骨架网格，该骨架网格保持原始网格的连通性，并且与原始网格中的 顶点一一对应。对于获得的骨架我们需要进行一些平滑处理。这样原始网格就波 表示为骨架网格上各个顶点的偏移。网格变形的过程包括对骨架网格的变形和空 间偏移的变化。最后，我们需要从骨架恢复成几何网格，并通过使用l a p l a c i a n 编辑的方法来保持网格原有的局部特征。 简单的骨架变形思想如图l 一2 所示： ，、 ， ，j 、礤专。“ ! 、 i 、 ，、? ? |、。、；、! jf ；li ?：jl ： ?j ： ?f j 1 2 本文结构 本文其它章节安排如下： 第二章给出网格变形的相关理论，讲述自由变形的理论基础，给出数学 上的定义；讲述l a p a l a c i a n 变形的思想，给出各步骤的数学解释；讲述网格骨架 提取过程。 第三章 网格变形的一些实现应用。针对自由变形，l a p a l a c i a n 变形。基 于s k e t c h 轮廓的变形，以及骨架提取和重构网格曲面给出实现应用和实现细节。 第四章简要介绍了本文用到的自主开发的三维核心系统的框架和数据 结构。 第五章总结了全文，并提出一些可行的研究方向。 浙 i 大学硕上学位论立第2 章网格变形理论 第2 章网格变形理论 2 1 自由变形 1 9 8 6 年，由s e d e r b e r g 和p a r r y l 2 1 提出的自由变形( f f d ) 核心思想在于：变 形操作不是直接作用于模型，而是作用于模型所嵌入的牢间：如果卒间被改变了， 则嵌入其中的模型自然随之改变。f f d 首先引入了一个变形工具。由一个均匀剖 分的= 三参数张量积b 6 z i e r 体的控制顶点组成，称为格子( l a t t i c e ) 。然后将变形模 型线性地嵌入此b 6 z i e r 体的参数空间，当调整格子中的控制顶点位置时，参数体 的形状会发生变化，嵌入其中的模型就会随之变形。f f d 方法是柔性物体变形中 最适用的一种方法，但其格子的形状为平行六面体。这在一定程度上限制了它的 应用。c o q u i l l 抓+ 1 3 1 提出的扩展f f d ( e x t e n d e df r e e f o r md e f o r m a t i o n ，e f f i ) ) 方 法使得初始的格子可以有更多的形状，如棱柱体、圆柱体等，从而增加了f f d 技 术的使用范围。 f f d 方法具有很大的灵活性，但是当格子中控制顶点数目较多时，调整格子 中控制顶点的工作将变得繁琐而费时，鉴于此也有很多研究做了一些这方面的改 进，但基本上是以牺牲一部分变形的自由度来换取变形的复杂性。 y o s h i z a w a ”介绍了系列的自由变形技术，其中一个比较显著的特征是没有 使用任何的网格联通信息，因此可以被用于针对散乱点的自由变形。虽然该算法 是众所周知的自由变形方法的修改，但在具体实现上更加简单而直观。 本节所提到绝大多数的技术都很常见，唯一比较新的内容是使用虚拟控制点。 2 1 - l 基本思想 给定一个网格和一个控制顶点c ，将网格上的顶点0 移动到一个新位置p 定 义如下： p = d + o ( c ，0 ) 其中距离向量d 定义如下： d ( c ，o ) = 考w ( c ，o x o c ) 同时， ( 2 1 ) ( 2 2 ) 澌 j 大学硕十学位 仑上 第2 章网格变形理论 吣d ) e x p f 一簪1 亿， 盯= w ( c ，0 。)( 2 4 ) 在等式( 2 4 ) 中0 。是网格上距离控制顶点c 最近的点。y ，口和是可用于调整 的参数。也可以选择其它的凸起形状函数来替换等式( 2 3 ) ，比如在n i t z b e r g t 2 3 1 的 讲义中就是用到了局部高斯的方法。 在等式( 2 4 ) 中参数，的符号，代表了变形的方式是凹陷还是凸起。例如当y 是 1 时变形的方式为凹陷变形。当，是1 时变形的方式为凸起变形。图2 - 1 给出了 凸起变形的效果。 图2 - 1 自由变形( 3 d ) 2 1 2 虚拟控制顶点 现在我们可以通过控制点来进行变形操作，但由于，符号的不同凹陷方式和 凸起方式变形的偏移方向正好相反。为了能够使用控制点来正确的进行凹陷方式 和凸起方式变形操作，我们引入虚拟控制点。简单来说虚拟控制点v 就是控制点 c 相对0 。的对称顶点，0 。是我们在之前提到过的在网格上距离控制顶点c 最近的顶点。这样我们将使用以下的距离向量来替换等式( 2 2 ) d ( c ，d ) = - 导w ( c ，o x o y ) ( 2 5 ) 图2 - 2 给出了使用虚拟点的凹陷变形和不使用虚拟控制点的凸起变形的效果， 在引入了虚拟控制点之后，我们以控制点所在的位置来确定凹陷方式和凸起方式 6 浙t l 大学硕士学位论史 第2 章网捂变形理论 的变形的方向。 图2 - 2 使用虚拟控制点的凹陷( 左) ；不使用虚拟控制点的凸起( 右) 2 。i 3 参数调整 在等式( 2 2 ) ，( 2 3 ) ，( 2 5 ) 中通过变化参数，口和，为用户提供了灵活的交 互变形操作，它们分别表示的含义是变形区域范围，形状尖锐程度o t 以及变形 方式，( i 和1 ) 。 多控制顶点：针对多项点情况，我们采用叠加的方法。例如，以下的规则将替换 等式( 2 1 ) p = o + d ( c 。，0 ) ( 2 6 ) 其中求和运算针对所有的控制顶点c 。而对于每个控制顶点g 都有独立的控制 参数。 然而当两个或多个控制顶点很相近时，为了达到一个较好的混合效果，我们 使用以下的方法来替换等式( 2 6 ) + 逊z 裟t o ( c 铲 亿， 。，o ) 4 类似的混合过程也在s i n g h 和f i u m e 【“1 的论文中使用到。其中口是一个可调整的 参数用来调整混合度。 2 1 4 约束关系 在控制顶点距离曲面两部分都很接近时，变形操作将会产生不希望的结果。 其原因可能就是我们使用的w ( c ，0 ) ，如果控制顶点c 距离网格的两部分都很近 新“大学硕士学位论史第2 章网格变形理论 时，这两部分上的点与控制顶点c 的约束关系w ( c ，0 1 权值很接近，因此两部分 都会产生变形。而我们并没有需要这样的结果。显然，针对这种情况。我们需要 更改约束关系，让这两部分点上的约束关系权值不同。我们使用w ( o 0 ) 来替 换等式( 2 2 ) w ( c ，0 ) 并设置仃= 1 。此处d 。是网格上距离控制顶点c 最近的点。 这样权值函数的中心就从控制顶点的c 转移到p 。上，简单地就不会出现之前提 到的问题了图2 - 3 给出了使用两种约束关系所产生的不同变形结果。 图2 - 3 左；使用o 。来计算约束关系。右：使用c 来代替o 。 图2 - 3 中在使用w ( d 。，d ) 作为权值关系的情况下，当调整参数和口时，会 出现变形的凸起部分与网格交错的情况，此时的权值中没有考虑到距离控制顶点 c 近的曲面另一部分点的约束关系，我们引入另外一个参数来控制新的约束关 系 w = w ( c ，d ) x + w ( d 。，o ) ( 1 一) ( 2 8 ) 使用等式( 2 8 ) 来替换等式( 2 2 ) ，可以让变形更加灵活，能够达到上图的两种 极端的情况，并拥有两者之间过渡的效果。 2 。1 5 变形方向 引入虚拟控制顶点用来保证变形向着我们希望的方向进行，在网格上选定一 点r ( 该点在网格上，不一定是网格顶点，可以是网格= 三角面内的点，也可以是 在三角面的边上) ，0 。是距离点r 最近的网格上的顶点，拖动点r ，就产生了 我们称之为控制项点的c 。那么虚拟控制点y 可以定义为控制顶点c 相对点r 的 对称点： v = 2 r c ( 2 9 ) 我们也可以使用w ( r ，0 ) 来代替权值关系中的w ( o 。，d ) ，由于月和0 。距离 撕t j 大学硕士学位论文第2 章网格变形理论 比较近，变形后的效果相差不大。 2 2l a p l a c i a n 曲面变形 曲面表示与处理是计算机图形学，几何造型以及计算机辅助设计中一个相当 重要的话题。简单来说，3 d 模型定义的方式对其应用的范围有很大的影响。不 同的对象表示可能会腱现出不吲的儿何性，连通性甚至是感性形状。举例来说， 二儿常流行的分段线性蓝面表示法( 三角网格) 提供了很直接地曲面显示，拓扑关 系构造，针对曲面平滑化的一些逼近处理等。但是，许多建模工作却很难在网格 上实施。此外，现今扫描获得的曲面通常都很详细而复杂，时常会出现一些噪声 存在于网格中，需要进行一些几何处理工作，比如过滤，采样以及高效存储和数 据流中的压缩等等。 本节，我们阐述s o r k i n e 9 ”提出的基于l a p l a c i a n 框架和差分表示法的网格处 理和建模。在此框架下，基于此网格的给出了一些线性运算，并研究曲面网格的 差分属性。这些线性运算是不同类型的网格l a p l a c i a n 计算，它们使用了新的曲面 表示方式，这有益于许多的网格处理应用。传统的全局笛卡尔坐标系，它仅仅能 够告诉我们每个点的宅问位置，而基于差分的曲面表示法携带了许多局部曲面形 状的信息，局部大小与方向等。因此，在对应用差分表示法的曲面上进行的编辑 处理时，得到的结果会是保持原有细节的曲面网格。 在接下来的讲述中。我们将会仔细的研究l a p l a c i a n 运算，差分表示法以及相 应的曲面重构问题。 2 2 1l a p l a c i a n 运算定义和曲面差分表示 接下来。我们首先回顾下差分坐标系( 占坐标系) 的定义，网格l a p l a c i a n 运 算以及曲面重构框架，并讨论l a p l a c i a n 运算的相关性质。 令m = ( v ，e ，f ) 为有n 个点的= 三角网格。其中v 表示顶点的集合，e 表示边的 集合，f 表示面的集合。对于每个顶点f 材使用笛卡尔绝对坐标系表示，记为 咋= 托，y 。，z ，) 。在网格上，我们定义差分或者艿坐标为v ，的绝对坐标与其直接邻 近点的中心之差， 新把大学硕士学位论史第2 章网格变形理论 点= 秽摊v ，一言薪亿姗 其中j ( f ) = ( j l ( i ，j ) e ) 并且d = l n ( i 】是点i 的直接邻近顶点个数( 或者称为度) 。 笛卡尔绝对坐标系与j 坐标系间的向量变换可以表示为矩阵的形式。令a 为 网格上的邻接( 连通关系) 矩阵： = 七笔2 急 偿 并令d 为对角矩阵其中d h = d 。那么绝对坐标与相对坐标之间的矩阵变换表示 为 l = i d a 。 通常使用l 的对称矩阵会更加方便，定义为l ，= d l = d a ， f d i = ， 也) 。= 一1 ( f ，j ) e ( 2 1 2 ) 1 0 o t h e r w i s e 那么。l , x = d 6 ( “，l 。】，= d 8 ( w ，j = d s ( “，其中x 是由所有顶点x 轴坐标组成的 1 1 维向量，y ，z 雷同。图2 - 4 是网格矩阵的一个简单例子。 一川 q1 3 一i - 1 - 1s - 畸t - 1q4 1- 1 ，qq - 14 - 1 - 1 一i 1 - i6q 叫_ 1 1 一16 - 1 1 q - 13 1 一1 _ 1 _ 14 图2 - 4 一个三角网格的例子，一以及它的关联矩阵k 矩阵t ( 或l ) 称为网格的拓扑( 图) l a p l a c i a n 2 ”。l a p l a c i a n 图已经在代数 和图论中被专门的研究过，其主要原因是它们的代数性质关系到图表示的组合性 质。 如果假设网格肘是分段线性逼近的平滑曲面，则从差分几何的角度，6 坐标 可以认为是连续l a p l a c e b e l t r a m i 运算| 2 5 1 的离散化。我们将差分坐标向量写为 1 0 浙大学硕士学位论j 第2 章网格变形理论 最= 了1 ( v ，一v ，) ( 2 1 3 ) ，胙 上式中求和运算是以下曲线积分的离散化：两1 一v 川，其中y 是曲面上围 绕u 的闭合曲线并且m 是，的长度。从差分几何中得知 i 翌南，( v 。一v 妞o ) = 一日( v ，如， ( 2 “) 其中m ( v ，) 是在点_ 处的平均曲率n ，是曲面法向量。因此，差分坐标中向量的方 向是局部法相量方向的逼近并且其强度值在数值上也很逼近平均曲率删( 根据平 均曲率缩放的法向量称作平均曲率法向量) 直观地说，这就意味着j 坐标秉审蕴 藏了曲面的局部形状( 见图2 5 ) 。 西= 壶岛( 尔v f 一_ ) 南j v y ( v i v ) c ，( v ) 图2 - 5 某点的差分坐标的向量是曲面局部形状属性的逼近；法向里方向和平均曲率 应该说l a p l a e i a n 的几何离散有更好的逼近质量。m e y e r 等人卅提出使用余切 的权值来代替均匀权值( 首先由p i n k a u 和p o l t h i e 一2 8 1 提出) ： 彰2 南磊，扣+ c o t 成如，1 ) ( 2 1 5 ) 其中i q 1 是第f 个v o r o n o i 格的大小并且嘞，岛表示边( 1 ，j ) 所对的两个角度( 见 图) ，用于逼近平均距离法相量。这些几何独立的权值使得向量贸仅仅含有法相 量的构成，而不像之前定义的一还拥有切线的成分，这样在平面环上也不大会出 现零值的情况。余切的权值可能会出现负值情况，这种情况是由于非常大的角度 而引起的余切值与万接近导致。凸包权值模仿了余切的权值称为均值坐标系1 2 9 1 驴堂掣笔幽 ( 2 1 s ) 一”川 其中p 角如图2 - 6 所示。对于网格几何性质已知的几何离散有益于一些应用，比 如网格过滤和编辑，因为它们能够更加精确地逼近差分属性。 浙n 大学硕士学位论空 第2 章网格变形理论 图2 - 6 在余切权值中使用的角度和边( i j ) 的均值坐标 2 2 2 从j 坐标系重构曲面 接下来，我们将沿着上面定义的曲面差分表示法继续，在j 坐标系下进行一 些的运算操作。而这些操作的最后一步都是曲面重构，换句话说，我们需要将肘 上的顶点坐标恢复成笛卡尔坐标。 给定一个占坐标集合，我们如何来唯一性地恢复成全局坐标呢? 答案显然是 不可能，因为我们用于全局和差分坐标系变换的矩阵l ( 或t ) 是奇异的，这样 表达式x = 。占( 。是不确定的。矩阵l 的每行之和为零，即矩阵l 含有一个非平 凡零向量( 1 , 1 ，l r 。艿坐标中平移的不可变性因此矩阵是奇异的：如果我们使用 权值w ，( 和为1 ) 来定义l a p l a c i a n 运算并且让网格使用向量“变换成v 7 新点，那 么 l ( ) = w ( 一v ；) = 这样 嬉 ，( n ( j ) j e n ( i ) 咐( ( ，+ u ) 一( v j + u ) ) = w i j ( v i v j ) = l ( v i ) r a n k ( l ) = n k ， 1 2 ( 2 1 7 ) ( 2 1 8 ) 淅让大学硕士学位论文第2 章同格变形理论 如果我们记c = l ，2 。，m ) ，那么需要求解的线性系统表示如下： 岛h 黝 亿：。， 对于y 和z 轴坐标向量雷同。方程( 2 2 0 ) 中的系统矩阵记为三，在最小二乘上- 我- f t 使用位置约束条件( 2 1 9 ) ：我们添加以上的表达式到线性系统中作为附加的几行， 而不是做一些矩阵中的替换。这样，对于每个点j ec 我们仍然可以保证其原有 倒 0 可以用来调整位置约束条件重要性( 基本上，每个约束都应该有自己权值， 束条件可以使我们的线性系统考虑得更加周到，基本上没有完全精确的解存在。 更= a r 垆畔1 1 2 + 厍。彩2 x - - c j l 2j 亿z ， 分析最小二乘解，可以通过方程( 2 2 0 ) 中由长方形仁+ m ) h 系统的矩阵来表示： 岩= ( p ) - 1 l v b ，( 2 2 2 ) 其中b = ( 毋( t i c 。纰，。) 7 是线性系统中的右侧向量。图2 - 7 表示的是一个4 , 3 型庵j 浙门大学硕士学位论文第2 章网格变形理论 - 1 - - 1 一- 1 5 - - 1- 1 - 1 q4- i- 1 3 - 1- 1 - 141 - 1 1 1- 16 - 1 一1 1 - 1 - 161 1 川一3 - 1 11 叫- 14 ， 1 图2 - 7 关联矩阵 在对6 坐标系下的网格进行重构时，一个相当重要的实现因素需要考虑。即 效率以及解决最小二乘问题( 2 2 1 ) 的精确度。最近研究蚓显示对该类问题采取直 接的方法会更加适合，特别是在当今这般巨大的网格( 高达几十万数据点) 情况 下。系统( 2 2 1 ) 可以通过应用c h o l e s k y 分解来求解，得到以下方程 ( 驴1 x = r 艿( 2 2 3 ) 其中矩阵是稀疏的，矩阵肘= f 是稀疏且正定的。可以计算稀疏矩阵肼的 c h o l e s k y 分解为： m = r 7 r( 2 2 4 ) 其中r 是上角稀疏矩阵。分解只需要计算一次，我们通过回代法来求解多个网 格函数( x ，y 和z ) ： r 7 f = f 艿( 2 2 5 ) r x = 善 ( 2 2 6 ) 这里分解计算过程消耗了大量的时间，而回代步骤速度很快。使用高级线性求解 工具，如t a u c s 库，可以使得计算更加迅速。 另外一个好处使用直接求解法是矩阵处理( 分解) 与右侧计算的分离，这样 使得计算只需要专注于快速的回代过程，而只不需要多次地去计算耗时费力的分 解过程。当系统的矩阵非常巨大时( 上百万或更多) ，分解因子将会过大而不能 放入内存中。这种情况下，我们可以使用外存版本的c h o l e s k y 分解( t a u c s 库) 或使用复杂度随系统大小线性变化的迭代法来求解( 例如，最近有关m u l t i g r i d 求 解法1 3 2 , 3 3 1 的研究工作) 。 注意求解的精确度很大程度上依靠线性系统的约束条件。总结来说，从全局 笛卡尔表示法变换成差分表示法是通过应用线性运算并附加上局部约束，这就是 4 1 3 1 1 一h h h h 新i i 大学硕士学位论土第2 章网格变形理论 网格l a p l a c i a n 。反之亦然。为了从差分表示法恢复到笛卡尔坐标系，需要求解一 个最小二乘的稀疏线性问题。这为曲面操作提供了很强大的框架基础：我们将会 在差分坐标中应用一些差分修改或给出一些模型约束等，最后通过求解最小二乘 法问题来重构曲面。该框架的优点可以总结如下： 在尽可能多的约束下，它力图保持表面局部细节 最小二乘法顺利地将错误分散到整个网格域，提供了一个优雅的重构 稀疏矩阵系统可以被迅速的求解 2 3 基于骨架变形 通俗地，对于图像，图像的骨架是指图像中央的骨骼部分，动物的骨骼决定 了动物的外形，与此相似，图像的骨架是描述图像的拓扑结构和集合性质的重要 性质之一，利用骨架表示原始图像。可以在保持图像重要拓扑性质的前提下，减 少图像中的冗余信息，突出图像的形态特征。 用骨架描述形态的方法最早是b l um 1 3 4 , 3 5 1 提出来的，他使用了中轴( m e d i a l a x i s ) 的概念。骨架自从最初被b l u m 提出后，它已得到广泛的发展。骨架有如下 几个性质： 1 骨架保留了原物体各部分间的连通关系，具有拓扑不变性； 2 骨架使用曲线抽象物体的形状特征，具有降维和数据压缩的效果：例如： 它将一个i 维物体变成了一组相连的点线，面，这些点，线，面和它们对应的 半径函数就能描述出物体的具体信息。 3 骨架含有物体的表面信息，可以从骨架恢复重构物体。当一个物体用它的 骨架表示后，骨架和它对应的半径可由人来控制，物体的轮廓就会非常自然的跟 着变换，这一性质可用在计算机动画上。 最后，骨架变换还可应用在文档的编码和其他一些图像处理中。 由于骨架的重要性，许多学者对此进行了深入的研究，提出了许多方法和概 念。且前的骨架算法主要分为两类：一类处理基于连续模型的对象，如多边形 模型，使用严格的数学方法求解，得到的骨架较精确，但是此类方法适用的范围 较窄，对于某些物体特别是在三维空间中，精确骨架的计算十分复杂，而且存 在多解、无解的情况；另一类处理的对象是离散域的二值图像，通过对像素或体 素的操作得到骨架，但是结果不可避免的受到离散化对精确度的影响。本文主要 讨论离散二值图像的骨架求取问题。 浙i 】大学硕士学位论文第2 章网格变形理论 在此我们主要针对连续模型对象进行考虑，在b l u m 提出骨架并进行了一番 探讨后不久，计算一蝗特殊平面图的连续骨架算法相继给出，主要包括两类：基 于方程和基于v o r o n o i 图。在节的对于骨架变形的算法中，我们使用基于v o r o n o i 图的骨架。 本节我们阐述y o s h i z a w a 提出的基于自由变形骨架i 的全局网格变形技术。 首先从所给的原始网格中提取基于v o r o n o i 的骨架网格。接着使用自由变形或 l a p l a c i a n 变形技术修改骨架网格。然后最终需要的全局变形可以通过重构已变形 的骨架网格来得到。 2 3 1 基于v o r o n o i 的骨架网格 一个图像的骨架( 中轴) 是在图像内部的一些点集合，这些点能够在图像轮 廓上找到多于一个的最近点。骨架最早由b l u m l 3 4 , 3 5 在2 d 图像中提出，用于进行 对称图像表示法f 的形状感知与识别。在3 d 中，骨架最近的研究主要是形状控 制3 7 3 3 堋与组刎4 0 1 。 给定有向曲面，骨架可以唯一地表示为曲面上有向的距离函数h “。这样我们 从有向曲面中区分出两个骨架，内部骨架和外部骨架( 其中一个可能会是空集， 例如，曲面包围了一个凸包图像) ， 我们先来看看v o r o n o i 项点。i i 维空间中给定一个顶点集。每个顶点的v o r o n o i 图把空间划分成各个区域( v o r o n o i 域) 。域内的空间点到该域的顶点的距离比到 任何顶点的距离都近。每个v o r o n o i 域为凸包类型，它们的顶点称为v o r o n o i 顶点。 每个v o r o n o i 顶点与n + 1 个或更多的原始项点等距离。在n 维空间中超曲面的骨 架是一个点集合，满足在超曲面上存在距离该点最近的点多于一个。 这样我们可以认为，如果原始顶点是均匀并一定密度的分布在所给超曲面上， 那么v o r o n o i 顶点将会是骨架的一个优良逼近。在2 d 已经证明是正确的，图2 - 8 中沿着2 d 曲线均匀分布的点和其对应的v o r o n o i 图。然而在1 1 维空间中，v o r o n o i 顶点的子集才是骨架1 4 2 a 3 1 的逼近。 浙江大学硕士学位论文第2 章同格变形理论 图2 培沿着曲线均匀分布点的v o r o n o i 顶点逼近了曲线的骨架。更细的分布提供了更好的骨 架逼近 图2 - 9 左显示了逼近椭球的点集合和其v o r o n o i 顶点集( 由于顶点集合有些较 小的凹陷，一些v o r o n o i 顶点在椭球体的外部) 。一个椭球体的骨架在一个平面上， 由其最大的两个基础轴确定，并由椭圆形曲线和其内部组成。因此许多的v o r o n o i 顶点并没有在骨架附近。 l 。二| | ， ， 图2 - 9 左；分布在椭球体上的点与其v o r o n o i 顶点。由于细小的凹陷，一些v o r o n o i 顶点落 在椭球体的外部。右：在椭球体上分布的点与其对应的内部v o r o n