（计算机科学与技术专业论文）勾画式三维网格模型的分割与编辑.pdf

浙江人学硕b 学位论文 摘要 在数字几何处理中，如何便捷有效地对三维网格模型进行编辑，一直是研究 工作者和动画设计师们关注的课题正像图像分割在图像分析和理解中扮演的角 色一样，三维网格分割在三维网格建模和编辑中也起到重要作用，有助于进行纹 理合成、形状分析、识别匹配、建模和渐变等应用 在图形学领域中，许多研究工作围绕自动分割算法进行，但是在某些特定应 用中，诸如模型特定部分的编辑、模型渐变、建模等，自动分割算法无法满足用 户的特定需求；在这种情况下，交互式分部分割方法显得尤为重要本文提出一 种交互式分部分割算法，能够帮助用户从三维网格模型中提取有意义的部分用 户使用勾画线的方式确定前景和背景种子面片，接下来系统分别指定i i 景和背景 种子面片的标量值，并通过求解一个方程组得到模型所有面片的标量值，然后借 助k e a n s 聚类方法，得到分割边界的标量值并利用该值追踪出一条等值线，就 是我们得到的初步分割，分割结果还可以进行优化和修正 在三维网格分割算法的基础上，我们设计了一个对三维网格模型进行几何编 辑的系统框架，并在该框架中实现了几何变形、模型拼接、模型渐变等功能在 几何变形的处理流程中，首先通过分割确定模型的待形变部分，然后用户设定形 变参照勾画线和目标勾画线来控制模型的待变形部分，接着通过求解一个泊松方 程，得到形变后的模型姿态模型拼接操作主要有载入模型、进行分割、设定关 键顶点、模型拼合、连接区域光顺等几个步骤在模型拼接的基础上，还可以对 序列模型分割下来的部分进行模型渐变，从而形成更多的结果姿态 由于不需要计算测地距离，我们的模型分割算法求解速度较快，具有较广泛 的适用性，不仅可以分割单个模型，而且可以分割序列模型实验结果表明，我 们的勾画式三维网格分割与编辑框架交互方式简单直观，结果模型自然平滑，具 有较高的时间和空间效率 关键词三维网格分割，几何变形，模型拼接，模型渐变 浙江人学硕上学位论文 a b s i r a c t a b s t r a c t i l ld i g i t a lg e o m e t r yp m c e s s i n g ，h o wt oc o n v e i l i e m l ya n de 塌c i e n t l ye d i t 仃i a l l 酉e m e s hm o d e l s 量l a sa l 恤y sb e e nas u b j e c tt l l a tr e s e a r c h e r s 锄da i l i m a t i o nd e s i 印e r sp a y a n 曲t i o nt o s i m i l a rt om er o l et l l a ti m a g es e g m e n 诅t i o np l a y si ni m a g ca i l a l y s i s 柚d u n d e r s 诅n d i n g ，m e s hs e g m e n t a t i o n i so n eo ft l em o s ti m p o n a l l to p c r a t i o r 塔i l l g e o m e m cm o d e l i n g 柚dp r o c e s s i n g 肌dh a sal o to fa p p l i c a t i o i l si nc o m p u t e r 伊a p l l i c s 印p l i c a t i o 跚c h 嬲t e ) ( t l l 托s y n t h e s i s ，s h a p ea l l a l y s i s ，r e c o 弘i t i o na i l dm a t c l l i n g ，s h a p c m o d e l i n ga n dm o r p i l i n g i nc o m p u t e rg r a p h i c sc o m m u n i 瓢s e v e r a la p p r o a c h e sh a v eb e e np r o p o s e df o r a u t o m a t i cm e s hs e g m e n t a t i o n h o w e v e f ，m ea u t o m a t i cs e g m e n t a t i o nm a yn o tb ew h a t t l l eu s e fn e e d sf o ras p e c m co p e r a t i o ns u c ha se d i t i n gc e n a i np a n ，m o r p h i n g ，a n d n l o d e l i n g ，t l l u s 锄i 舭m c t i v em e t h o ds h o u l db ec o n s i d e r e di nac e n a i l ls i t u a t i o n w c p r o p 0 姐硫e r a c t ea l g o r i t h mo np a n - t y p es e g m e n t a t i o n ，w h i c hh e l p su s e r s 咖a c t m e a i l i n g f h lp a n s 丘d mm e s hm o d e l s w h e nw eg e tf o r e g r o u n da i l db a c k g r o 咖ds e e d f h c e sf 幻mt 1 1 es k e i c hc u r v e s 也a tu f s 出a w s c a l a rv a l u e sa r e 船s i g n e df o re a c h e d 加es 唧a t e l y 1 蛔1w eo b t a i ns c a l a rv a | u e sf o ra l l 缸e so f 恤m e s hb ys o l v 啦a s p a r s el i n e 村s y s t e m t h ev a l u e sc a nf o m las c a l 孤f i e l d i t lt h i sf i e l d ，w ec 锄t r a c e 锄 i s o l 硫谢ma a l 甜v a j u er e s u l t i n g 舶mk - m e 榔c l 璐t e r i n g n e i s o l i n e i s 缸m i a l c 们i i l gb o 岫d a 彤w i l i c hc 觚b e 胁h e rr e f m c da n dm o d i f i e d 0 nt h eb a s i so fm e s h g m e n t a _ t i o na l g o r i m m ，w ed e s i g nas y s t e mt od og e o m e 町 p m c e s s i l l gf o r 3 dm e s h e s i l lt l l i ss y s t e mw ei m p l e m e n tt l l e 如n c t i o n so fm e s h d e f 0 肌i n g ，m 吲n g 锄dm o r p h i n g i i lt l l en o w o fm e s hd e f o n n i i i g ，l l s e r ss e tt e f e r e n c e a n dt a 唱c ts k e t c hc u r v 髓t oc o n t r d lt h ed e f o f i i l i n gp a r t t h e nw eg e tt 1 1 eg r a d i e n tf i e l d o ft 1 1 ed e f o 衄i n gp a n b y l v i n gap o i s s o ne q u a 廿o n 、ec a l lg c tt h ed e f o 册e dp o s t h em e r g i i l go p e r a t i o nm a i l l l yi n c l u d e sl o a d i n gt l l e m o d e l s ，s e g m e n t i i l gm o d e b ， s e t t i i 培k e yv c n i c e s ，m e r g i n gp a n s ，s m o o m i n gc o 衄e c t i n ga r e 嬲a n d o n a f t e rm e s h m e r g i n g ，w ec 衲d om o r l h m g 叩e r a t i t ot h e 咖i n gp a n ss om 砒m o r er e s u l tp o s e s a l f o 肋e d a sg e o d c s i cd i s t a n c ei sn o tn e c e s s a r yt 0b ec a l c u l a t e d ，o u rs e g m e n 伽o nm e t h o di s f h s t 锄dc 拍b e 谢d c l yu s e d nc a i ls e g i n e l l tb o t hs i n g l em o d e l s 觚d q u e n c en l o d e l s t h ee x p e t i m e n tr e s u l t ss h o wt h a tm e s he d i t i n go p e r a t i o i l sb a 辩d0 ns e g m e n t a t i o nh 鹤 姐e 硒y w a y f o f u s e 培t o i l l t e 】t ，觚d i se m c i e n t i n t i m e 锄ds p a c e m o r e o v w ec a l l o b t a i l ld i 仃c 把n tr c s u l tm e s h e s 、v i t l l9 0 0 dq l l a l i 够 浙江大学硕士学位论文 a b s n 砥 k e y w o r d s m e s hs e g i n e n t a t i o n ，d e f o 黝a t i 咀m e r g i i l g ，m 唧h 吨 浙江大学硕卜学位论文图目录 图目录 图l - 1 几何造型编辑工具1 图1 2s t a 】偷r d 扫描仪及实例。2 图1 3 常见的数字几何模型的表示方法3 图2 1 模型分割算法流程图5 图2 - 2b u 衄y 模型的分割过程5 图2 3e i g h t 模型的分割过程5 图2 4 三维网格表面寻找等值线的方法5 图2 5h a n d 模型的分割5 图2 6 形变梯度示意图5 图2 - 7 面片中心距离对形变距离的影响5 图2 8f 锄d i s k 模型的静态分割5 图2 9 m 憾模型的静态分割5 图2 一1 0g a r g o y l e 模型的静态分割5 图2 一1 1d o m e m o n 模型的静念分割5 图2 1 2c a t 序列模型的分割5 图2 1 3e l e p h 柚t 序列模型的分割5 图2 1 4j 啪p r o p c 序列模型的分割5 图3 - l 勾画式三维网格几何编辑框架5 图3 2 修正分割结果的交互过程5 图3 3 不同变换参数作用的效果5 图3 - 4 网格曲面微分算子和旋转变换示意图5 图3 5 比较平面目标曲线和空间目标曲线5 图3 6 拼接猫模型和人模型5 图3 - 7 剪切部分和粘贴部分的拓扑连接5 图3 8c a t - h o r 模型拼接示例。5 图3 9c a t 序列模型渐变结果。5 图3 1 0h 锄d 模型的变形结果5 图3 1 1 复杂物体的几何变形5 图3 - 1 2h o r 睁c a l 序列模型的剪切与粘贴5 图3 - 1 3h o r 序列模型渐变结果5 浙江大学硕e 学位论文表目录 表目录 表2 1 静态模型分割数据5 表2 2 动态模型分割数据5 浙江大学硕上学位论文第l 章绪论 第l 章绪论 1 1 几何编辑与处理技术概述 1 1 1 发展历史 数字几何处理( d i g i t a lg 它o m e 仃yp r o c e s s i n g ，简称d g p ) 是研究如何利用计算机 对三维几何数据进行处理的一门学科数字几何处理的研究，起源于工业的应 用英国的飞机工业，法国的汽车工业，催生了上世纪6 0 、7 0 年代b e z i e r 方法、b 样条方法、基于边界表示的实体造型等具有原始创新意义的理论与技术这些理 论与技术导致以p a r a s o l i d 、a c i s 为代表的几何造型内核的出现，彻底改变了制造 业生产的模式 随着几何造型技术在工业界的广泛应用，数字几何处理的应用领域也越来越 广，它的触角已经延伸到影视娱乐、医学诊断、军事方针、地质勘探等各个领域， 在真实世界之外构建出另一个虚拟世界其中最有推动意义的是影视娱乐的需 要最为人们所熟知的是影视娱乐行业为了带给观众在真实世界中无法体验到 的视觉感受，大量的三维动画技术被应用到影视制作中，较早的有1 9 8 2 年纽约理 工学院的t o mb r i 曲锄制作的由一个女人变成一只山猫在这些动画效果的制作 过程中，曲面变形技术无疑充当了重要的角色，曲面变形方法与物体的表示有密 切的关系，如可通过移动物体的顶点或控制顶点来对物体进行变形为了使变形 方法能很好地结合到造型和动画系统中，近1 0 年来，人们提出了许多与物体表示 无关的变形方法，在商业动画软件如3 d m a ) 【和m a y a 中也提供了大量的编辑工具 ( a ) p a r a s o i i d 界面 ( b ) 利用3 d s m a x 做出的动画角色 图1 1 几何造型编辑工具 浙江大学硕上学位论文第l 章绪论 硬件的发展也对数字几何处理技术造成很大推动各种三维激光测距仪和投 影相机系统三维几何获取能力的迅速发展，使现实世界中的物体数字化已经不 再困难其中最著名的例子就是s t 柚f b r d 大学的d i g i t a lm i c h e l a i l g e l op r o j e c t 【l 】，该 项目通过一整套三维扫描硬件和三维重建软件系统完成了一些大型雕塑的数字 化过程，生成的最复杂的三维模型包括2 0 亿个多边形和7 0 0 0 幅彩色图像作为 继声音，图像、视频之后的又一种数据表示方式，三维数字几何技术可以直接 将现实世界中的物体数字化，并可方便地利用计算机来进行处理，使之可视化 图1 2 s t a l l f b r d 扫描仪及实例 1 1 2 研究对象 在计算机图形学中，三维几何模型通常包含两部分内容：一部分是几何模型 的形状，另一部分是几何模型的外观属性，如表面材质、纹理等几何模型的表 示方法主要分为分解表示、构造表示和边界表示三大类分解表示是将形体按某 种规则分解为小的、更易于描述的部分，每一小部分又可分为更小的部分，这种 分解过程直至每一小部分都能够直接描述为止构造表示是按照生成过程来定义 形体的方法，通常有扫描表示、构造实体几何表示和特征表示三种边界表示 ( b o u n d a r yr e p r e s e n t a t i o n ，b r ) 也称为b r 表示或b r 印表示，它是几何造型中最 成熟、无二义的表示法 边界表示按照“体一面一环一边一点”的层次，详细记录了构成形体的所有 几何元素的几何信息及其相互连接的拓扑关系边界表示的一个重要特点是在该 2 浙江大学硕士学位论文第l 章绪论 表示法中，描述形体的信息包括几何信息和拓扑信息两个方面【2 】拓扑信息描述 形体上的顶点、边、面的连接关系，拓扑信息形成物体边界表示的“骨架”，形体 的几何信息犹如附着在“骨架”上的肌肉边界表示法分为隐函数曲面、参数曲面、 细分曲面、多边形网格和点几何表示等 从三维计算机图形学发展的初期开始，多边形网格就是最通用的表示物体形 状的方法多边形网格模型具有以下优点：多边形形状简单，便于计算和处理； 多边形可以任意精度逼近一个曲面物体，可以表示拓扑非常复杂的物体；只需存 储各多边形顶点的位置坐标及属性即可表示物体的几何信息，在计算多边形内任 一可见点的光亮度时，所需的信息可由顶点的信息插值得到，这使得对多边形网 格的绘制可采用硬件加速技术来实现因为任意多边形可以很方便地被剖分为三 角形网格，故本文只讨论三角形网格曲面的处理 图1 3 给出了几种常用的数字几何模型的表示方法 ( a ) c s g 实体表示1 3 jf ”网格表示 ( c ) 点云表示1 5 l( d ) 隐式表不1 6 j 图l 一3 常见的数字几何模型的表示方法 1 1 3 主要研究方向 数字几何处理技术在工业、娱乐业等领域的应用促进了科研人员的理论研 究自上世纪九十年代以来，国内外科研人员进行了大量数字几何处理方面的研 3 浙江丈学硕士学位论文第l 章绪论 究工作，逐渐形成了数据表示、数据获取与重建、数据存储与压缩、数据编辑、 数据绘制、数据检索等几个主要研究方向1 7 j 本文的工作属于数据编辑的子问题，下面就详细阐述一下数据编辑 数据编辑是数字图像处理的核心，是指对已有的三维模型进行局部调整、剪 切与粘贴、模型合并、大范围形变等操作，以满足用户对数据的需求常见的几 何编辑类型包括： 几何滤波：通过将离散f o l | r i e r 变换1 8 l 或小波变换【9 】等推广到三维几何上，将三 维模型的空间坐标转换为频谱信号，从而可以针对特定的信号频段进行处理，包 括去噪、增强、光顺等具体滤波类型和操作 最近十年以来，国内外研究人员提出了大量的网格光顺算法1 9 9 5 年，t a u b i n i 硐 从信号处理的角度出发，提出了一个线性的、各向同性的网格光顺算法，该算法 效率较高，并可通过适当选取合适的滤波参数组合来避免网格体积的收缩，然而 这个方法在光顺过程中难以有效保持几何特征，且算法的迭代步长不能太长，否 则稳定性会受到影响d e s b m n 等人1 3 9 】通过引入平均曲率流将t a u b i n 方法加以推 广，该算法允许大迭代步长，显著提高了算法稳定性0 h t a k e 等人【4 0 】将d e s b m n 等人提出的平均曲率流与参数域规整方法相结合，提出了一个网格光顺算法，在 光顺几何的同时也均衡网格的边长上述方法的共同特点是，在光顺过程中，将 几何特征和网格噪声共同看待，容易造成结果的过光顺，在去噪的同时，也损失 了几何特征 为此，研究人员对特征保持和各向异性滤波的网格光顺算法展开了深入研究， 力图将图像处理领域中的各向异性扩散算法的思想推广到三维网格上，并利用网 格表面的曲率张量信息来决定局部扩散过程，从而达到对几何特征的保持乃至增 强 与各向异性扩散方法相仿，双边滤波是另一种保持特征的滤波手段，其核心 思想是将滤波器的权值拆分成两部分：一是距离权，表示邻接数据点到中心预测 点的距离对于预测的影响；另一是信号权，代表邻接数据点处的信号与中心预测 点处的信号之间的差异对于预测的影响这两个权重函数叠加构成了整个预测器 的权重函数，叠加函数一般取数值乘法双边滤波技术在图像去噪领域中取得了 很大成功f 4 “，这直接导致了其在网格去噪方面也得到了重视和成功【4 2 4 3 1 几何变形：研究如何高效地根据用户意图对原始模型进行形变，常用于计算 机动画或三维特效的生成【l0 】问题难点在于如何有效地反映用户意图，并转换成 为内在计算模型所需要的参数信息考察算法好坏的指标一是变形结果的质量， 二是完成特定任务所需的用户交互工作量 4 浙江大学硕 学位论文第l 章绪论 目前，网格曲面的自由变形方法大致可区分为：( 1 ) 基于控制网格的自由变形； ( 2 ) 轴变形方法；( 3 ) 勾画式变形方法；以及( 4 ) 基于偏微分方程( p d e ) 的变形方法等 四类方法 基于控制网格的变形法是将物体嵌入控制网格构成的空间，形成物体顶点位 置到参数的一一对应；当所嵌入的空间变形时，根据初始参数重新计算物体顶点 在空间中的位置，从而实现形变在s e d e r b e r g 和p a n y 【“l 提出初始的f f d 方法后， c o q u i l l a n 【“j 和m a c c m c k e n 等人l ”】以及其他研究者【1 4 】提出了各种拓展方案然而， 基于样条理论的参数对应方法计算代价较大，实现复杂控制形变困难，对任意的 拓扑结构构造控制网格较为繁琐，局限了此类可实施形变的模型种类发韧于小 波分析的多分辨率变形方法i l5 m 】，利用网格重采样和简化技术来生成一个控制网 格序列，可让用户在模型的多个细节层次上编辑任意拓扑的网格曲面 基于中轴( m e d i a la ) 【i s ) 的变形方法旧最初动机来源于自然界许多物体是轴对 称的，物体的变形与其轴线的变形存在对应关系在y o s h i z a w a 等人【l8 j 的自由形变 方法中，首先抽取模型的中轴骨架，然后建立与原始网格顶点的对应，通过操纵 骨架网格计算位移，实现对原始网格的形变该方法适于大尺度变形，但建立骨 架原始网格的合理对应是此类方法的难点 近年来，勾画式的交互造型方法备受重视这种交互方式不拘泥于精确的模 型信息，使用者即使不具有专业的造型经验，也可进行校正和修改在i g a r 鹤l l i 等人1 19 j 的创新工作中，用户只需在屏幕上勾画轮廓线即可快速地建立和编辑物 体在文献【2 0 】的方法中，则借鉴了中轴变形，用草图勾画来定义和变形兴趣区域， 对于关节物体的形变非常有效 微分域方法【2 l ，矧通过调整网格曲面的微分属性来对三维网格进行编辑，通过 拉普拉斯和泊松方程定义最小化能量变化，在变形过程中很好地保持了细节此 类方法通常导出一个稀疏线性系统，可快速求解微分域方法的难点在于如何设 计合理有效的交互，进一步如何控制微分属性，以反映编辑者的意图受【2 3 】工 作的影响，文献 2 4 】中利用轮廓线勾画提供了微分属性的位置约束，在局部形交 应用中取得良好效果，但从本质上未能解决大范围旋转形变的关键问题z 1 1 0 u k 吼等人1 2 副将勾画式的用户交互手段和微分域的变形操作很好的结合在一起，但 是他们的控制曲线是将空间曲线投影在某一个平面后生成的，编辑曲线时也是基 于平面进行操作，导致形变方向具有局限性 几何拼接：几何拼接是一个有效的快速建模方法，来自于不同模型的多个部 分组建拼接成为一个新的整体，常用于迅速生成新的模型数据难点在于如何自 适应地调整子模型的大小和形状，以及如何保持过渡区域的平滑性 布尔运掣2 6 1 是最直接的几何拼接手段，通过布尔求交我们可以得到裁剪后的 浙江大学硕e 学位论文 第l 章绪论 合并网格然而，在网格之间进行布尔求交运算时要求各网格之间的交线必须是 封闭的，否则会导致交线附近的几何特征部分或完全丢失此外，在复杂网格间 的布尔运算十分耗时，而且其计算过程也不是十分稳定 水平集( l e v e ls e t ) 方法1 2 7 j 也可用于物体之间的拼接，并且拼接边界可以通过该 方法得到光顺，但其计算过程较为耗时，一般难以达到交互应用 此外，l e 、俨引提出的参数域外插方法也可用于多片网格的拼接，但该方法要 求待拼接的各片网格已具备平面参数化结果，这大大限制了该方法的适用范 围类似地，基于l a p l a c i a l l 坐标，s o r k i n e 等人【2 9 l 也给出了一个网格拼接方法 几何插值：也叫做形状混合或形状过渡，是计算机图形学中的一个常用算 法研究如何在多个输入模型之问进行插值，从而生成一个随时问渐变的序列， 常用于计算机动画的生成1 3 问题的难点在于如何建立多个模型之b j 的保持特征 的映射，以及如何生成符合物理运动规律的过渡序列 通常，基于边界表示的形状插值算法有两个基本问题，一是对应问题，即如 何在给定输入模型间构建一个一一映射关系二是路径问题，即根据环节得到 的映射关系，如何在对应顶点位置之间生成一条变化路径 在多个输入网格模型之间建立对应关系一般要借助于参数化技术根据所选 取的参数域类型来对现有网格对应算法进行分类，可以分成基于平面、球面和基 网格参数化的对应算法k 锄a i 等人荆用调和映射技术将非封闭网格模型投影 到平面圆盘内，然后在圆盘内进行网格合并并建立顶点之间的对应关系a l e ) 【a 【3 2 】 通过重心坐标将网格模型投影到球面上，然后调整球面上的投影点对其指定的对 应特征点，最后合并球面投影建立顶点对应关系p r a 硼等人【3 3 】提出了一个自动的 网格分片算法，该算法需要用户提供公共基网格以及基网格顶点在各个输入网格 上的对应点，然后各个网格分片被自动地映射到基网格之上并通过半规整重采样 来获得顶点对应 在可查的文献中，s e d e 舭曙和g f c e n w o o d m j 最早考察了路径问题，他们给出 了一个基于物理的多边形插值算法该算法将中间模型的变形信息分解成为伸缩 分量和弯曲分量，然后对多边形对应边长和对应夹角分别进行线性插值，以代替 顶点坐标插值随后，s e d e 慨r g 等人】提出一个纯几何插值算法，通过全局优化 来避免中间折线段的局部自交并保持整体封闭l i u 和w a n g 【3 6 j 将这个算法思想推 广到三维网格上，不过最终生成的渐变序列依赖于二面角和边长的计算顺序 x u 等人1 3 7 j 提出一种泊松形状插值算法在生成输入网格之间的对应网格之 后，计算相应三角形对的局部变换矩阵，并将变换矩阵分解为旋转部分和缩放部 分，最后插值得到中间变换矩阵，将其作用到源模型得到中间梯度场，并由泊松 方程重建得到中间网格模型 6 浙江大学硕士学位论文 第l 章绪论 此外还有几何信息重用和几何重采样问题，由于本文没有这两方面的工作， 在此就不一一赘述 1 2 本文的研究目标和解决方案 在数字几何处理中，如何便捷有效地对三维网格模型进行编辑，一直是研究 工作者关注的课题三维网格模型的编辑在计算机动画领域具有广泛应用，有助 于动画师从已知模型状态生成更多的状态，或者生成新的模型 三维网格模型的编辑工作包括数据表示、数据获取与重建、数据存储与压缩、 数据编辑、数据绘制、数据检索等几个主要研究方向其中，数据编辑是数字图 像处理的核心，常见的几何编辑类型包括几何滤波、几何变形、几何拼接、几何 差值、几何信息重用和几何重采样等其中三维网格分割算法在在网格参数化、 纹理映射、形状匹配、形状插值、多分辨率建模、网格编辑与压缩等三维网格模 型的编辑中具有很强的应用 与图像分割在图像分析和理解中起到的作用相似，三维网格分割在几何建模 和处理中有很多应用三维网格分割技术可以分成分片类型和分部类型前者适 用于c a d 模型的分割，后者需要借助用户交互，从模型中提取出有意义的部分本 文要研究的算法属于分部分割，我们需要提取的有意义的部分是指和模型其他部 分在视觉上有显著区别的部分 一个令人满意的交互式三维网格分割方法需要满足如下性质： 简单系统需要提供简单有效的用户界面用户能够通过界面直观地操纵 模型 高效方法提供较短的交互和响应时间 鲁棒当用户输入具有较小改动的时候，分割边界不会发生很大改变 因此，我们提出对勾画式三维网格分割进行研究的课题，并希望在算法研究 的基础上形成一个便捷、高效的系统框架，能够对三维网格物体进行多种编辑操 作这样的框架将对实验室数字几何处理研究工作的开展起到一定作用，具有较 强的研究价值和实用价值 在我们的三维网格分割算法中，用户交互得到前景和背景种子面片之后，分 别指定前景和背景种子面片的标量值通过求解一个方程组得到模型所有面片的 扩散值，使用k m e a n s 聚类方法，得到分割边界的标量值并利用该值追踪出一条等 值线，就是我们得到的初步分割可以使用图切分】的方法对初步分割结果进行 优化。 得到分割结果之后，可以对模型的前景部分或背景部分进行几何变形即通 浙江大学硕l 学位论文第1 章绪论 过参照勾画线和目标勾画线定义三角形的局部变换利用求最近点的方法，将兴 趣区域和参照勾画线对应起来；再利用弧长参数将参照勾画线上的点和目标勾画 线上的点对应起来这样参照勾画线和目标勾画线就可以作为兴趣区域的控制曲 线，曲线上相应点的变换反映了自由顶点梯度场的变换 我们可以把对不同模型分割得到的结果进行拼接，从而形成新的模型或模型 序列在我们的框架中，模型拼接操作主要有载入模型、进行分割、设定关键顶 点、模型拼合、连接区域光顺等几个步骤 在模型拼接的基础上，框架还可以对动态剪切体进行模型渐变，从而形成更 多的目标姿态 本文结构如下： 第一章概述几何编辑与处理技术的历史、处理对象和主要研究方向 第二章提出一种新的三维网格分割算法，详细介绍算法步骤及其特点，并分 别对静态模型和动态模型的分割结果进行讨论 第三章介绍勾画式三维网格分割与编辑框架，包括框架交互方式和对几何模 型进行变形、拼接、渐变等操作 第四章总结了本论文的工作并提出未来的努力方向，并对今后的工作做了展 望 8 浙江大学硕士学位论文 第2 章三维网格模墅的分割算法 第2 章三维网格模型的分割算法 本章介绍一种半指导学习方式的三维网格分割算法我们将交互式的分割技 术归类为半指导学习问题，并研究出一套三维网格分割算法本章由以下部分组 成：首先介绍三维网格分割和半指导学习的背景知识，告诉读者我们为何要将交 互式分割问题归结为半指导学习；接下来详细阐述我们的分割算法，包括静态模 型的分割和动态模型的分割，以及二者的异同；最后分析算法的时间效率，展示 分割结果 2 1 网格分割与半指导学习 2 1 1 三维网格模型的分割概述 三维网格分割在近些年的网格处理算法中已经扮演了一个很重要的角色这 些算法包括网格参数化、纹理映射、形状匹配、形状插值、多分辨率建模、网格 编辑与压缩等等其中许多分割技术都借鉴了图像分割、有限元网格分割、无指 导机器学习和其它领域的思想 2 1 1 1 分割类型 根据分割目标的不同，可以将分割分成两种基本类型：分片分割( p a t c h t y p e 辩鲫e n t a t i o n ) 和分部分割( p a r t t y l ) cs e g m e n t a t i o n ) 1 4 ”前者将会生成类似圆盘的片， 这些片拥有一定的大小、凸凹、平度( p l 锄a r i 聊等几何属性，因此对于形状规整的 c a d 模型会有很好的分割效果后者旨在将物体分成有意义的组成部分，对分割 结果的评判依赖与人的视觉感知，具有一定的主观性 分片分割通常用于纹理映射、建立图( b u i l d i n gc h a n s ) 和建立几何图像当中这 些操作中，子网格片一定要拓扑等价于圆盘，而且当参数化到二维平面上时一定 不能有较大扭曲：另外一类应用分片分割较多的应用是网格重构和简化在这些 应用中，每个片被一个或一组平面多边形代替，因此，平度0 l 柚a r i 劬就是目标片 的重要属性还有一些分片分割以凸凹性( c o n v e x i 啪或曲率作为分割的约束分 片分割可以在应用中减小模型的复杂度例如，在形状渐变( m o r p l l i n g ) 中，可以 通过分割把所有多边形网格的复杂变换矩阵简化为子片之间的变换矩阵谱分析 中，分片分割也是用于减少矩阵的运算量 与分片分割不同的是，分部分割没有确定的评判标准，它依赖于人的视觉感 知然而，人类的感觉非常复杂单单对“有意义”这个词的定义就很难说清， 9 浙江丈学硕上学位论文第2 章三维网格模型的分割算法 更不要说怎样自动计算有意义的部分了但是根据不同应用需要，科技人员还是 定义了不同标准来评判分割结果分部分割将模型分成有意义的部分而不改变各 部分的拓扑结构这种分割通过识别物体的组成部分，可以帮助进行形状匹配和 重建这种部分匹配也可以辅助形状渐变的操作分部分割还可以建立起物体的 骨架，这些骨架可以驱动物体形变，生成动画角色的运动此外，通过定义物体 各个部分的包围盒可以加速碰撞检测的计算 本文所说的分割是分部分割，即分割出模型中“有意义”的部分 2 1 1 2 主要分割算法 运用于模型分割的主要算法有区域增长、层次聚类、迭代聚类、谱分析、图 切分等 区域增长：区域增长是最简单的用于初步分割的算法它是一种局部贪婪的 算法，首先选定一个种子点到优先级队列中，并建立与该种子点对应的一个类， 通过扩散新增加元素周围的相似的元素来扩大区域的面积，当优先队列中元素被 取完时该区域的增长结束此时再选择新的种子点进行扩散 层次聚类：区域增长算法有时会产生不令人满意的全局结果例如，区域的 数目很大程度上依赖于初始面片的选择层次聚类可以解决这样的问题层次聚 类也是个贪心算法，它可以被看成是“全局贪心”的，因为它会为所有的类选择 做好的拼接操作，而不是仅仅对一个类进行区域增长 迭代聚类：在前面的两种方法中，结果分类的数目事先是不知道的在交互 分类中结果分类的数目已经预先给定了这种方法的基础就是k m e a i l s 算法，有时 也叫l i o y d 或l l o y d m a x 算法钥每个元素被指定分属七个类，然后从这七个类 的元素中重新归纳各个类的属性当属性不再变化的时候过程中止 谱分析：谱分析理论h 柳阐述了图的组合特性与拉普拉斯变换的代数属性之间 的关系如果彳是图g 的邻接矩阵，d 是对角矩阵并且其中顶点f 的度数是九， g 的拉普拉斯变换记为矩阵三= d 一爿令编，卣，磊。) 是三的特征向量通过使 用前d 个特征向量将图g 嵌入到空间中，可以把组合图分割问题转化成几何空 间分割问题【4 9 姗 图切分：图切分是一种基于全局能量优化的分割技术图切分最初被运用于 图像分割5 1 1 ，后来被引入到三维空间进行三维网格的分割近些年，图切分算法 l o 浙江大学硕上学位论文 第2 章三维嗍格模型的分割算法 在三维网格模型分割中的运用十分广泛，既可以用于确定初步分割5 2 1 ，也可以用 来在模糊区域中优化分割边界1 5 3 1 2 1 2 半指导学习概述 半指导问题( s e i i l i s u p e r v i s c d l e a f i l i i l 岛s s l ) 是机器学习研究中的一个重要内容 唧j ，可以作为一种特殊的分类方法，其特点是通过已标记和未标记的数据直接在 不完整样例上作出合理的推断传统的分类器仅仅利用带标记的数据进行训 练然而带标记的数据经常难以得到，代价昂贵或者很费时，需要有经验的人的 指导不带标记的数据采集起来相对容易，但很少有方法可以用到半指导学习 的目的就是从己标记和未标记的数据中训练出更好的分类器因为半指导学习需 要较少的人为努力而提供更高的精确度，所以具有较高的理论和实际应用价值 半指导学习的方法主要有以下几类l 蚓：生成式模型，自训练( s e l f - t r a i n i n g ) ，互 训练( c o ，仃a i n i n g ) 叫，直推式支持向量机( t r a l l s d u c t i v e s u p p o r t v e c t o r m a c h i n e s ， t s v m ) 【7 0 j ，基于图的方法等五种生成式模型利用大量未标记数据来帮助建立 高斯混和模型的各个成分自训练使用一个分类器将未标记利用已有训练样本建 立的模型标记，选出置信度高的样本加入训练集中重新训练，迭代这个过程为 了避免一个分类器强化自己的错误，互训练旧要求在两个独立的并且包含足够信 息的视角上，建立两个分类器，两个分类器每次互相标记一部分置信度高数据给 对方，然后重新训练，迭代到没有更多合适的未标记数据加入直推式支持向量 机1 7 0 j 是通过加入约束项使得未标记数据落在边缘之外，即使得分类的超平面避开 数据密度高的区域基于图的方法通过相似度度量将标记和未标记数据放在联系 起来，假设相似结点标记相近 图切分就是一种基于图的半指导学习方法首先将所有数据分成源( s o u r c e ) 、 渊( s i l l l 【) 和未标定状态，再利用最大流最小割得到未标定面片的分类，从而完成对 数据的分类图切分算法的缺陷在于必须分别设定未标定面片到源和渊的测地距 离，而测地距离的计算需要耗费较多的时间 在我们的算法中，切割网格问题也是一种半指导学习首先通过用户的指定， 标定前景和背景种子面片，接下来通过求解一个扩散方程，得到所有面片的标量 值，进一步通过k - m e a l l s 算法和追踪等值线得到面片属于l 柯景还是背景的信息，这 个过程就是从半标定的数据通过学习获得所有标定的数据在求解扩散方程的过 程中，我们只需要设定相邻面片的信息，不用计算到前景和背景种子面片的测地 距离，从而可以提高算法的时间效率 浙江大学硕士学位论文第2 章三维网格模型的分割算法 2 2 静态三维网格模型的分割算法 本节介绍静态三维网格模型的分割算法，当得到用户交互指定的前景、背景 种子面片后，我们的算法需要经过确定网格表面的标量场、确定初步分割边界、 优化分割边界等几个步骤，得到分割后的边界图2 1 显示了三维网格分割算法的 流程这个流程同样适用于动态分割，只是在画双方框的步骤上有所不同 设定种子 面片 得到网 格表面 扩散的 标量场 确定初步 分割边界 优化分割 边界 斛l 磷懈萋 场转化为il 得到粗分割li 罢翟甚詈 顶点标量| l 和分割标量ll 翟嚣罢景 场 fi 值 li ”“ 图2 1 模型分割算法流程图 许多分割算法( 例如图切割) 需要首先计算三维网格物体表面的测地距离， 消耗了很多时间我们的算法不需要计算测地距离，只需要提供每两个相邻面片 之间的信息然后通过求解一个方程组就可以得到分割结果了相邻面片之间的信 息具有多样性，可以是相邻面片之间的二面角，动画序列中楣邻面片的形变距离 等等通过设定不同的模型信息可以得到不同的分割结果，分别反映了不同的用 户意图对于静态三维网格模型来说，分割的准则主要是模型表面的曲率，我们 的算法中用相邻面片的二面角进行衡量对于动态模型来说，分割的准则是相邻 面片之间的形变距离 2 2 1 基本定义 2 2 1 1 网格分割 假定膨是定义在孵3 上的二维流型( 2 m a l l i f o l d ) 曲面，s = ( k ；x ) 是表示m 的 离散几何的三角形网格其中，置= 矿，e ，毋是网格元素顶点( y = f i l f s 所 ) ， 边( e = ( f ，力i f ，_ ，矿 ) 和三角形( f = ( f ，工七) i f ，_ ，i n ) 的集合，x 表示网格顶点 1 2 浙江大学硕上学位论文第2 章三维网格模型的分割算法 的位置m 的分割就是所有把置分成七个互不相交的部分的分割的子集在本文 的交互式网格分割中，令七= 2 2 2 1 2 动态模型 动态模型也称形变模型或序列模型，是指动画中一系列具有相同拓扑结构的 三维模型，它们是通过不同的形变编辑产生的，提供了同一模型在时域或空域上 的变化在模型分割算法中，动态模型往往能够提供更多的信息一个序列中的 模型能够形成一个形变空间因此研究动态模型的分割算法能够提高动画模型生 成的效率 令d = ( k ；k ，五，x 。) 表示一个模型序列，其中量与2 2 1 1 中的定义相 同符号k 表示在参照姿态中模型顶点的位置，z 代表某一形变姿态 2 2 2 网格表面的标量场 己知一个含有雄个三角形面片的静态网格m = ( y ，e ，丁) ，其中y = “，v 肿) 是 顶点集合，e = ( f ，川f ，_ ，n 是边的集合，丁= ( f ，七) l - ，七矿) 是三角形面片 集合，对于r 上的每个三角形面片( 1 f 打) 定义标量值z ，并且f = ( z ，z ) 在 得到网格表面标量场的步骤中，就是已知前女个三角形面片的标量值6 j ( 1 s f 七) ， 通过解一个最小化能量方