（机械设计及理论专业论文）基于细分的逆向工程曲面重建技术研究.pdf

浙江大学硕士学位论文摘要 摘要 本文主要研究了细分曲面在逆向工程中的应用，即细分重建技术。 细分曲面是近年来国际图形学领域研究的热点之一。它具有1 、n 瓜b s 所不具 有的任意拓扑性、能够自动保证模型整体连续性、无须拼接，而且还具有与 n ij i i b s 一样的局部性、仿射不变性等优点，因此在工业设计、计算机动画等领 域均得到了广泛的应用。目前关于细分曲面的研究主要集中在连续性分析、细分 模式构造以及在几何造型等领域的应用等方面。本文主要对细分重建技术中的各 项关键技术进行了研究，包括： l ，描述了本文细分重建算法的基本思想、流程以及数据结构，并实现了经 典的l o o p 细分算法。 2 ，提出了一种新的基于边删除的网格简化算法。新的网格简化算法的误差 准则主要概括为三个代价函数：正则性代价函数、共边网格夹角代价函数以及改 进的离散h a u s d o r f f 距离代价函数。通过赋予三个代价函数一定的权值并相加来 综合衡量边删除的代价。实验证明，与原算法相比，新算法的简化速度得到了大 大的提升，并且网格质量也有了明显改善；相同阀值的情况下，新算法的简化率 高于原算法；若要获得相同或相当简化率的简化网格，即使不进行折痕、角点等 尖锐特征的提取，新算法也可以更好、更多地保留特征信息，这是新算法的又一 突出优点。 3 ，提出了一种基于l a p l a c e 光顺算子的网格采样几何优化算法。新算法的 主要优点在于能够理论上避免切向位移，并且由于不需要计算每个顶点的单位外 法向，其优化速度也快于w o o d 切向投影算法，在处理复杂、大型的网格模型时 速度优势更为明显。其次，实验证明本文算法在保证网格质量越来越好的同时使 得网格近似性没有显著降低，这是其又一个优点。为更好地完善对尖锐特征的简 化处理能力，本文也实现了带尖锐特征的网格简化算法，使之能够处理边界等特 征。 4 ，提出了一种新的细分重采样方法。区别于以往所有的投影采样方法，新 的采样方法以初始网格顶点的法向作为投影方向，这是其最显著标志。在此基础 上，本文又将投影、求交转化为求点到法向的距离，避免了复杂的求交运算。实 验证明这种采样方法能够提高采样过程对初始网格轮廓的再现能力。 5 ，本文在前述经典l o o p 细分算法的基础上实现了带尖锐特征的l o o p 细分 算法，并建立了细分重建曲面拟合的数学模型。 关键词：细分曲面；网格简化；网格优化；细分重采样；逆向工程 浙江大学硕士学位论文 a b s t r a c t i nt h i sp a p e r , t h ea p p l i c a t i o no fs u b d i v i s i o ns u r f a c e si nt h er e v e r s ee n g i n e e r i n g ( r e ) ，c a l l e dt h er e c o n s t r u c t i o no f s u b d i v i s i o ns n r f a e x 熔，i se x p l o r e d i nr e c e n t y e a r s , s u b d i v i s i o ns u r f a c e sb e c o m e so n eo ft h e h o tt o p i ci n i n t e r n a t i o n a lc a d c ga r e a s b e s i d e si t sl o c a lc o n t r o l l a b i l i t y 、i m m u t a b i l i t yo fa f t m e t r a n s f o r m a t i o ne t cl i k en u r b s ，t h em o s to u t s t a n d i n ga d v a n t a g eo fs u b d i v i s i o n s u r f a c e si si t sa r b i t r a r yt o p o l o g yt h a tj u s ti st h em o s td i f f i c u l t yo ft h ed e v e l o p m e n to f n u r b s m o r e o v e r , s u b d i v i s i o ns u r f a c e sc a ng u a r a n t e e dc o n t i n u i t ya u t o m a t i c a l l ya n d a v o i dc o n c a t e n a t i n g a l la b o v es t r o n g p o i m sm a k ei t a p p l i e di nm o r ea n dm o r e a r e a s s u c ha sc o m p u t e rc a r t o o n 、i n d u r s t r yd e s i g ne t o t h i st h e s i sm o s t l yr e s e a r c h e st h e k e yt e c h n o l o g i e so f t h er e c o n s t r u c t i o no f s u b d i v i s i o ns u r f a c e s ，i n c l u d i n g ： l ，d e s c r i b i n gt h eb a s et h e o r y 、f l o wa n dd a t a - s t r u e t u r eo ft h er e c o n s t r u c t i o no f s u b d i v i s i o ns u r f a c e sa n di m p l e m e n t i n gt h el o o ps u b d i v i s i o ns c h e m e 2 ，p r e s e n t i n gan e wa l g o r i t h mo f m e s hs i m p l i f i c a t i o nb a s e do ne d g ed e c i m a t i o n t h eg r r o rc r i t e r i o no ft h en e wa l g o r i t h mm o s t l yi n c l u d e st h r e ec o s tf u n c t i o n ：t h e r e g u l a r i t yc o s tf u n c t i o n 、t h ec o s tf u n c t i o no ft h ea n g l eo ft w om e s h e sw i t hc o m m o n e d g e 、t h ec o s tf u n c t i o no f t h ei m p r o v e dd i s c r e t eh a u s d o r f f d i s t a n c e t h ec o s ta r o s e d b yt h ee d g ed e c i m a t i o ni sc a l c u l a t e db yt h ew e i g h t e ds u n 1o f t h r e ec o s tf u n c t i o n t h e e x p e r i m e n tp r o v e dt h a tt h es p e e do fo p e r a t i o no ft h en e wa l g o r i t h mi sf a s t e rt h a nt h e o l da l g o r i t h ma n dt h eq u a l i t yo f m e s h e si si m p r o v e d m o r e o v e r , t h es i m p l i f i c a t i o nr a t e i sb i g g e rw i t h i nt h es a m et h r e s h o l d 。a n o t h e ro u t s t a n d i n gs t r o n g p p i n to ft h en e w a p p r o a c hi st h a ti tc a l lr e s e l v em o r ef e a t u r ew i t h i nt h es a n l eo r n e a rs i m p l i f i c a t i o nr a t e e v e ni f t h es h a r pf e a t u r ei s n tt a g e d 3 ，p r e s e n t i n ga na l g o r i t h mo f m e s hs a m p l i n ga n dg e o m e t r i c a lo p t i m i z a t i o nb a s e d o nl a p l a c es m o o t ha r i t h m e t i co p e r a t o r s t h en e wa l g o r i t h mc a na v o i dt h et a n g e n t d i s p l a c e m e n ti nt h e o r ya n dt h es p e e do fo p e r a t i o ni sf a s t e rt h a nt h ea l g o r i t h mo f t a n g e n tp r o j e c t i o no fw o o de s p e c i a l l yi no p e r a t i n gb i ga n dc o m p l e xm e s hm o d e l b e c a u s ei ta v o i dt h ec a l c u l a t i o no ft h en o r m a lo fe v e r yv e r t e x s e c o n d l y , i ti sp r o v e d t h a tt h eq u a l i t yo fm e s hi sg u a r a n t e e dw h i l eab e t t e ra p p r o x i m a t i o no ft h eo r i g i n a l m e s hi so b t a i n e d i no r d e rt oi m p r o v et h es i m p l i f i c a t i o no fs h a r pf e a t u r e ，t h i st h e s i s a l s oi m p l e m e n t st h es i m p l i f i c a t i o na l g o r i t h mo f m e s hw i t hs h a r pf e a t u r et h a tc a nd e a l s w i t l lam o d e lw i t l lo p e nb o u n d a r y 4 p r e s e n t i n gan e wa p p r o a c ho fs u b d i v i s i o n - r e s a m p l i n g c o m p a r e dw i t l la i l p r e v i o u sa l g o r i t h m s ，t h ep r o j e c t i v ed i r e c t i o no fn e wa l g o r i t h mi st h en o r m a lo ft h e 浙江大学硕士学位论文 a b s t r a c t v e r t e xo fo f i g j n a lm e s hw h i c hi st h em o s tr e m a r k a b l es y m b 0 1 a n dt h e n , i tc a l c u l a t e s t h ed i s t a n c eb e t w c c nt h ev e r t e xa n dt h en o r m a li n s t e a do fp r o j e c t i o na n ds e e k i n g i n t e r s e c t i o n , a v o i d i n gt h ec o m p l e xo p e r a t i o no fs e e k i n gi n t e r s e c t i o n 耽ee x p e r i m e n t p r o v e dt h a ti tc a ni m p r o v et h ea b i l i t yo f r e a p p e a r a n c e 5 i m p l e m e n t i n gt h el o o ps u b d i v i s i o ns c h e m e 谢t l ls h a r pf e a t u r eb a s e do na b o v e c l a s s i c a ll o o ps c h e m ea n dc o n s t r u c t i n gt h em a t h e m a t i c a lm o d e lo fs u b d i v i s i o n s u r f a c e sf i t t i n g k e yw o r d s ：s u b d i v i s i o ns u r f a c e ；m e s hs i m p l i f i c a t i o n ；m e s ho p t i m i z a t i o n ；s u b d i v i s i o n r e s a m p l i n g ；r e v e r s ee n g i n e e r i n g 1 1 1 学号2 q 生q 塞1 3 鱼 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得盘婆盘茎或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 一躲讥务乎：州年日 学位论文版权使用授权书 本学位论文作者完全了解盘望盘茎有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权逝鎏盘茎可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：了蕲磋- 嚷导师签名：j ，、】、芝 i 签字日期：d 积年5 月；日签字日期：名年月；日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 浙江大学硕士学位论文 第一章绪论 第一章绪论 从著名的c o o n s 曲面到今天成为国际s t e p 标准的n u r b s 曲面，几何造型 技术的每一次发展都渗透着人们对更高效、更快捷、更精确的物体几何表达方法 的不懈追求，而这些追求正是几何造型技术进步的原动力。 细分曲面技术正是这种追求的产物。它具有n u r b s 曲面所没有的任意拓扑 性，而且还具有细分规则简单、天生的多分辨表达等诸多优越性，因此正受到越 来越广泛的关注。 本章将从发展逆向工程的现实意义开始，阐述作为逆向工程关键技术之一的 曲面重建方法的重要性；并详细介绍当今最主流的造型方法的发展历史和研究现 状，包括以n u r b s 为主体的参数曲面造型、多用于人体造型的隐式曲面重建以 及虽然简单但现在仍为众多动画、游戏软件所采用的多边形建模技术等；在分析 了以上曲面重建方法不足的基础上，引出突破传统重建方法任意拓扑性限制的细 分曲面重建，并简单介绍了细分方法的发展历史、研究现状、特点以及应用范围 等；最后提出了本文的主要研究内容和意义。 1 1 逆向工程 一般说来，大多数产品来源于概念设计：设计人员首先构思产品的外形、性 能和大致的技术参数等，然后利用c a d ( c o m p u t e r a i d e dd e s i g n ) 技术建立产品 的三维数字化模型，接着制定加工工艺计划，最终将这个模型转入制造流程完成 产品的整个设计制造周期。这样的设计过程我们称之为“正向工程”( f o r w a r d e n g i n e e r i n g ，f e ) 。也就是说传统的产品设计是一个从无到有的过程。对每一个 组件来说，其流程一般如图1 1 所示。 图1 1 正向工程设计过程 最终产品 最终产品 图1 2 逆向工程设计过程 然而，计算机技术以及c a d 技术在全球范围内的飞速发展和推广使得几何 造型领域出现了一些新的设计方法：一些产品并非来自设计概念，而是起源于另 浙江大学硕士学位论文 第一章绪论 一些产品或实物在只有产品原型或实物模型的情况下进行制造。例如，某些 流线型物体、人体器官、艺术雕塑品等。这种情况下首先要对实物进行数字化测 量，在此基础上构造c a d 模型，一旦c a d 模型建立之后，可以对它进行后续 操作，如局部修改、有限元分析、误差分析、数控加工指令生成等。由此产生了 逆向工程( r e v e r s ee n g i n e e r i n g ，r e ) 的概念，也称反求工程。 反求工程是综合性很强的术语，它是以设计方法学为指导，以现代设计理论、 方法、技术为基础，运用各种专业人员的工程设计经验、知识和创新思维，对已 有产品进行解剖、深化和再创造，是己有设计的设计，特别强调再创造是反求的 灵魂。简单地说反求工程的根本目的就是实现智能的三维扫描，通过对已有物体 的测量，建立其表面或实体模型，结果要求可以应用于已有的c a d c a m 系统 中【1 1 。 广义的逆向工程包括影像逆向、软件逆向和实物逆向三种。目前大多数有关 逆向工程技术的研究和应用都集中在重建产品实物的c a d 模型和最终产品的制 造，称之为实物逆向工程。逆向工程技术能快速建立新产品的数据化模型，大大 缩短新产品研发周期，提高企业生产效率。逆向工程的工作过程可用图1 2 表示。 1 2 曲面重建方法 曲面重建技术是逆向工程的关键技术之一，经过逆向工程数据采集环节得到 的海量数据必须通过几何重建技术才能建立采样实体的c a d 模型，在此基础上 才能进行后续的修改、再设计、加工等工作。因此，几何重建技术的发展是逆向 工程的发展的前提。 曲面重建技术作为一种几何造型技术，也是计算机图形学与计算机辅助几何 设计的一项重要内容。它主要研究在计算机图形系统环境下对曲面进行表示、设 计、显示和分析。 近年来，计算机图形显示对于真实性、实时性和交互性的要求越来越高，几 何设计对象也越来越多样、复杂，这都对曲面造型技术和曲面表示方法提出了更 高的要求。目前已经形成的重建方法包括：参数化曲面( r a t i o n a lb s p l i n es u r f a c e ) 重建、隐式代数曲面( i m p l i c i t a l g e b r a i cs u r f a c e ) 重建、多边形建模等。 1 2 1 参数曲面重建 参数曲线曲面造型是传统造型技术中最常用的方法。从f u g e r s o n 提出曲线 曲面的参数向量函数表达式开始，参数曲面经历了一个较长的历史发展时期。参 数曲线曲面发展的历史实际上也即是样条法发展的历史。样条法源于飞机、船舶 的外形放样工艺。1 9 6 2 年，b 6 z i e r 提出一种由控制多边形设计曲线的新方法， 浙江大学硕士学位论文 第一章绪论 这种方法不仅简单易用，而且很好地解决了整体形状控制问题，但它不利于对曲 线进行局部修改。1 9 6 4 年前后，c o o n s 提出了一种由四条边界曲线确定的参数曲 面即著名的c o o n s 曲面，使得分片表示完整曲面成为可能。b 6 z i e r 曲面的特点是 曲面逼近控制网格，而c o o n s 曲面的特点是插值，即构造出来的曲面满足给定的 边界条件，例如经过给定边界，具有给定跨界导矢等等。孔斯曲面中运用得较多 的是双三次孔斯曲面。 1 9 7 2 年，d e b o o r 、g o r d o n 和r i e s e n f e l d 先后提出了b 样条( b s p l i n e ) 的 标准算法并将其应用于形状描述，最终提出了b 样条方法。b 样条法的特点与 b 6 z i e r 方法一样，也是曲线曲面逼近控制网格，它继承了b 6 z i e r 方法的一切优点， 并且b 样条法克服了b 6 z i e r 方法存在的缺点，比较成功地解决了局部控制问题， 从而使自由曲线曲面形状的描述问题得到较好解决，但b 样条方法不能精确表 示圆锥截线及初等解析曲面这样的二次规则曲面，这就造成了产品几何定义的不 唯一，使曲线曲面的表达没有统一的数学描述形式，容易造成混乱。 为了解决使用b 样条方法出现的问题，美国s y r a c u s e 大学的v e r s p r i l l e 首次 提出有理b 样条( r a t i o n a lb s p l i n e ) 方法，后来由p i e g l 和t i l l e r 等人将其发展 为非均匀有理b 样条( n u r b s ) 方法，成为现代曲面造型中最为广泛流行的技 术。国际标准化组织( i s 0 ) 于1 9 9 1 年颁布了关于工业产品数据交换的s t e p 国 际标准，将n 1 j r b s 方法作为定义工业产品几何形状的唯一数学描述方法。 n u r b s 方法的突出优点是：它可以在表示自由曲线曲面的同时，又能精确 地表示二次规则曲线曲面，从而能用统一的数学形式表示规则曲面与自由曲面； n u r b s 具有可影响曲线曲面形状的权因子，使得形状易于控制和实现，而其它 非有理方法无法做到这一点；n u r b s 方法是非有理b 样条方法在四维空间的直 接推广，多数非有理b 样条曲线、曲面的性质及其相应算法也适用于n u r b s 曲 线曲面，便于继承和发展。然而，n u r b s 也存在明显的缺点：在任意拓扑曲面 造型时，很难处理曲面片间的拼接，特别是当实现高阶连续时，不仅运算量大， 而且还容易产生裂缝；权因子的不合适选取可能导致很坏的参数化，甚至毁掉随 后的曲面重构；在创建特征时，虽然可以精确控制，但计算花费时间较多，而且 如果要想在任意地方加入特征，实现也比较困难。正因为以n u r b s 为代表的参 数曲面重建技术存在上述缺点，所以从二十世纪七十年代末期开始，出现了一大 批新的曲面造型技术来弥补n u r b s 曲面的不足。其中，隐式曲面就是具有代表 性的技术之一。 1 2 2 隐式曲面重建 隐式曲面即是形如f ( x ，y ，z ) = 0 隐式表达的代数曲面。 浙江大学硕士学位论文 第一章绪论 隐式曲面具有参数曲面所没有的优越性：参数曲面代数次数很高，而高次代 数曲面使计算及几何操作更复杂，给造型带来困难，因此直接研究低次代数曲面 可避免这个问题；和参数曲面相比，隐式曲面易于判断给定的点是否在曲面上或 者某一侧，同时，隐式曲面能很容易地表示半平面f ( x , y ，z ) s 0 和f ( x , y , z ) 0 ， 这在动画尤其在研究物体碰撞检测中更能发挥优势；隐式曲面经过曲面求交、求 并、位差( o f f s e t ) 等操作之后，仍为代数曲面，这个性质使得隐式曲面被广泛 应用于曲面造型。 近年来，隐式曲面本身的优越性以及表示复杂物体的需要使得隐式曲面在 c a d c g 曲面造型中得到越来越广泛的应用，尤其在构造人体肌肉、水滴、云、 烟等任意拓扑复杂形体方面有很大优势。在计算机动画中，人体造型颇为艰巨， 因为人的肌肉不仅形状复杂，而且还会随着人体的运动而变形。隐式曲面通过采 用元球技术有效地解决了这类问题，当采用元球技术造型时，物体的变形是以一 种自然的方式进行的，这是其它造型技术不容易实现的，而且曲面具有极高的光 滑性。 隐式曲面的缺点是由元球系统构造一张复杂形状曲面需要大量基本体素，且 用户对此难以有效控制，这就给交互设计带来极大的困难。另外隐式曲面难以直 观显示，不能进行细节造型。 1 2 3 多边形建模技术 多边形建模技术的思想就是用小平面来模拟曲面，从而表示各种形状的三维 物体。小平面可以是三角形、矩形或其他多边形，实际中多是简单的三角形或矩 形。使用多边形建模可以通过直接创建基本的几何体，再根据要求采用修改器调 整物体形状或通过使用放样、曲面片造型、组合物体来建立c a d 模型。 多边形建模技术具有造型速度快、简单、方便、容易缝合、而且可以表示任 意拓扑形状等优点，因此一直得到了广泛的应用，尤其是在许多游戏和动画的制 作上。虽然目前并存有n u r b s 曲面建模、隐式曲面建模等高级建模，但多边形 建模技术在许多游戏与动画公司，仍然是优先的建模和动画技术。 然而多边形建模技术只能达到c o 连续，难于生成光滑的曲面，故而只适合 于构造具有规则形状的物体，如大部分的人造物体，同时可根据虚拟现实系统的 要求，仅仅通过调整所建立模型的参数获得不同分辨率的模型，以适应虚拟场景 实时显示的需要。 1 3 细分曲面重建研究现状 n u r b s 尽管早已被国际标准组织1 s o 作为定义工业产品数据交换的s t e p 浙江大学硕士学位论文第一章绪论 标准，在工业造型和动画制作中也得到了广泛的应用，但仍然存在着局限性。单 一的n u r b s 曲面，同其他参数曲面一样，限于表示在拓扑上等价于一张纸、一 个圆柱面或一个圆环面的曲面，不能表示任意拓扑结构的曲面。 一般来说，非有理方法都采用张量积的参数多项式与分段参数多项式描述曲 面。尽管一般的n u r b s 曲面已非张量积曲面，但仍可看作张量积曲面的推广， 而这种张量积曲面在实现拼接的时候通常都是非常困难的。三角b d z i c r 曲面比 四边域曲面具有更宽松的拓扑要求以及更好的边界适应性，在散乱数据的反求 c a d 建模中得到了广泛的应用，特别是随着特征提取、嵌入、再现等技术的深入 研究以及在三角曲面模型重建中的实现，三角b d z i e r 曲面对特征的表达更加充 分和完善。然而不论是采用基于四边域的n u r b s 重建还是采用基于三角域的 b d z i c r 重建，都是先逐片构造，再进行曲面片缝合，因此都必须在曲面剪裁和拼 接上花费大量的时间。并且剪裁和拼接的效果并不一定理想：第一，修剪的代价 是昂贵的，而且有数值误差；第二，要在曲面的接缝处保持光滑，即使是近似的 光滑也是困难的。 分；i 宴吲连续曲线或曲面h 匝产回船= m 回 传统重建方法 细分重建方法 图1 3 传统重建方法与细分重建方法对比 因此，无须剪裁、不需要拼接并且具有整体连续性、任意拓扑性和局部性的 细分曲面便应运而生。 细分曲面是通过用低分辨率的控制网格和定义在控制网格上的细分规则来 表示光滑曲面的。对于给定的初始控制网格，通过运用定义在其上的细分规则， 形成一个由更多的边、面、顶点组成的控制网格，重复运用这个规则，在极限时， 控制网格收敛于一个光滑曲面，这就是细分曲面。 与传统曲面重建方法相比，细分重建方法无须经过分片、拼接形成连续曲面 的过程，而是通过一定的几何、拓扑规则直接从离散点得到显示所需的离散点， 这不但省去了分片、拼接的时问，也节省了连续曲面离散化的时间。如图1 3 所 示。 i 3 i 历史背景及发展现状 细分曲线、曲面的发展始于点的多边形网络。最早可以追溯到1 9 5 0 年左右 g d er h a m 用以描述光滑曲线的角切削( c o m e rc u t t i n g ) 思想，如图1 4 。到 1 9 7 4 年，g c h a i k i n 基于这一思想提出了定义在封闭控制多边形上用于一个曲 线生成的细分方法c h a i k i n 算法。1 9 7 8 年，c a t m u u 和c l a r k l 2 】由双三次b 样 条的递推性质导出任意拓扑网格上的细分曲面模式，d o o 和s a b i n l 3 】贝0 提出了迭 浙江大学硕士学位论文第一章绪论 代细分四边形网格生成双二次b 样 条曲面片的方法，并将其推广到任意 拓扑网格的情况。 此后，把参数曲面的造型技术移 植到细分曲面，并最终把细分方法应 用于c a d 领域成为人们追求的目 标。但随后的几十年中，由于在奇异 点处的连续性问题没有得到解决，细 分曲面研究工作一直没有大的进展。 ? q ? q 图1 4c o m e r c u t t i n g 示意图 到1 9 9 5 年，r e i f l 4 懈决了细分曲面在奇异点处的连续性问题，才使得细分曲面在 理论和实践中获得极大的发展。 在细分技术发展的低潮期，涌现了一些著名的细分模式。1 9 8 7 年，l o o p 在 其硕士论文1 1 6 l 中提出一种基于三角网格的细分模式，它是盒式样条( b o xs p l i n e ) 曲面的推广，也是细分算法中应用最为广泛的算法之一1 9 9 0 年，d y n 等【1 7 】提 出了著名的蝶形( b u t t e r f l y ) 细分模式，其面具与蝴蝶相似因而得名。 细分曲面作为一项几何建模技术一开始并没有被用于逆向工程的曲面重建 中。直到9 0 年代中期，由于细分技术具有n i 瓜b s 所没有的任意拓扑性和基于 n u r b s ，b 6 z i e r 曲面重建的诸多困难，众多学者才逐渐把目光投向如何将细分 方法应用于逆向工程曲面重建的研究，这才形成了细分重构的思想。 在散乱数据的细分重构方面，h o p p e 和s u z u k i 等进行了很多卓有成效的研 究。1 9 9 4 年h o p p e 等【5 i 率先提出了用细分曲面进行几何重建的分段光滑曲面生 成方法。该方法可以获得分片光滑细分曲面、可拟合离散数据集、同时还能保持 尖点的特征，但其重建过程相当复杂，共包括三个步骤：建立初始网格从初 始的散乱点集构造密集的初始三角网格，用于估计待建曲面的初始拓扑结构；网 格简化及优化通过一定的简化、优化准则减少三角网格的数目，提高拟合的 精度；细分重建通过求解庞大的全局优化非线性能量方程组来求出细分曲面 控制网格的顶点位置，最终输出控制网格的顶点数目、位置与连接关系。1 9 9 9 年s u z u k i 等1 6 魄出的细分曲面重建方法则不需要解全局优化方程组，它采取反复 迭代求解局部能量最小的细分控制网格顶点位置。由于该方法在拟合过程中每个 控制顶点相应的极限位置点只在初始密集网格的顶点子集中寻找，所以花费的时 间较少，但它没有考虑待建曲面的特征信息，不能反映出待构物体的细节特征， 且只适应于拓扑等价于球的曲面重建。 1 9 9 9 年，f f s a m a v a t i 和r h b a r r e l s 7 1 对简单的空间曲线、张量积曲 面进行了重建研究，探讨了如何用细分、最 b - - 乘法数据拟合和小波变换来更有 效的定义和表达曲线曲面，提出用最小二乘拟合方法来反求细分规则的方法。该 浙江大学硕士学位论文第一章绪论 方法与特定细分规则相对应，用细分矩阵写出了反求的误差表示，而后采用了与 小波函数类似的写法统一了细分九次之后的误差表达式。但该方法局限于简单的 曲线上，并且在如何将该方法由张量积曲面推广到非张量积曲面等问题上也没有 提出解决的办法。 2 0 0 0 年以及2 0 0 2 年，w m a 和n z h a o 分别在文献【8 、9 】中研究了如何 反求c a t m u l l c l a r k 细分规则，并将其用于逆向工程曲面重建。他们提出了一种 基于参数化拟合c a t m u l l - c l a r k 细分曲面的方法，这种方法充分利用了所有已知 的样本点，在经过网格简化、优化之后得到假定的细分曲面，最后通过最小二乘 法来反求控制顶点。 国内对于细分曲面的研究起步比较晚。近几年，国内细分曲面的研究开始逐 渐增多，其研究方向主要集中在基本算法和工程、图形学领域的应用，见文献 【1 0 1 3 。 1 3 2 细分方法的特点 细分方法的特点在上节已经有所提及，比如其拥有n u r b s 所没有的任意拓 扑性等。这些特点是使得细分方法成为国际图形领域研究的热点、成为与 n u r b s 、隐式曲面并存的重要曲面造型方法之一的重要原因。在此将其主要特 点作一个总结： 首先，细分方法具有n u r b s 表示所具有的优点： 1 ) 简单性 细分算法一般定义规则很少，而且细分规则都比较简单、易于实现。细分曲 面新位矢的计算只需要很少的浮点运算，因此算法效率非常高。 2 ) 局部控制性 和n u r b s 样条法所具有的局部可控性一样，细分方法中一个点影响的最终 曲线或者曲面的区域很小，特别在计算新顶点的位矢时，一般仅依赖于其1 邻域 或2 邻域的控制顶点。 3 ) 仿射不变性 对细分曲面初始控制网格做线性变换( 如平移、比例缩放、旋转等) ，细分曲 面也会相应做同样的变换。 其次，细分方法还具有n u r b s 所不具备的的优点： 1 ) 任意拓扑性( a r b i t r a r yt o p o l o g y ) 任意拓扑性是制约n u r b s 发展的瓶颈。这种拓扑局限性使得传统的曲面造 型方法在遇到诸如人体等这样复杂物体造型时往往显得束手无策，使我们面临很 大的技术挑战。当然，我们可以用最普通的复杂光滑曲面的造型方法，例如对 n u r b s 的修剪( t r i m m i n g ) 来对付。确实，目前已经存在一些商用系统，诸如 浙江大学硕士学位论文 第一章绪论 a l i a s w a v e f r o n t 和s o f l l m a g e 等可以做到这一点，但是它们修剪代价很大且有数 值误差、在曲面的接缝处保持光滑即使是近似的平滑也很困难。而细分曲面的主 要优点则是可以很容易的表示任意拓扑曲面，它有潜力克服以上两个困难。 2 ) 整体连续性 对于任意拓扑控制网格，细分曲面一般自动满足切平面连续( 或者g 2 连续) ， 它们无须修剪、拼接。不需要像n u r b s 一样需要处理曲面片之间的连续性拼接。 3 ) 表示的一致性 传统的曲面表示方法，要么是多边形曲面，要么是样条曲面。而细分曲面既 可以看作是由控制网格定义的连续曲面，又可以看作是离散网格曲面，因此它统 一了曲面片和多面体表示，使得造型系统有了统一处理曲面和多面体表示的手 段。 4 ) 显示、传输、编辑 细分曲面由递归生成，是一个不断细化的过程，具有多分辨率性质，这使得 它在编辑、显示、网络传输方面具有其它造型技术和曲面表示方法所无法比拟的 优势。而它先天的多分辨特性又特别适合于层次细节模型( l o d ) ，从而又可充 分地利用有限的硬件资源。 细分曲面的这些特点使得细分技术不但在理论上为图形学界所承认，在工业 界也得到了越来越广泛的应用。 1 3 3 细分曲面的应用 从现在曲面造型技术的现状和发展趋势来看，目前已经形成了以b d z i c r 和b 样条方法为代表的参数化特征设计和隐式代数曲面表示这两类方法为主体，以插 值( i n t e r p o l a t i o n ) 、拟合( f i t t i n g ) 、逼近( a p p r o x i m a t i o n ) 这三种手段为骨架的几何 理论体系。但随着激光测距扫描等三维数据采样技术和硬件设备的日益完善，与 传统的连续造型相比，离散造型大有后来居上之势，尤其以具有任意拓扑性、整 体性以及局部性的网格细分( s u b d i v i s i o n ) 为代表，这种曲面造型方法在生动逼真 的特征动画和雕塑曲面的设计加工中如鱼得水，已经被广泛应用于工业设计、动 画到科学可视化和仿真模拟等行业。 1 9 9 8 年，著名的计算机图形学家t - d e r o s e 制作的动画短片荣获了奥斯卡大 奖。该片正是基于c a t m u l l c l a r k 细分技术，凭借对其中一个名叫g e r i 的老头以 及周围景色生动细致的造型，赢得了评委和观众的赞誉。这就是美国著名的p i x a r 动画电影制片厂选送的作品”g e r i sg a m e ”。d e r o s e 成功地应用了c a t m u l l c l a r k 细分曲面造型方法，同时发明了构造光滑的变半径的轮廓线及合成物的实际技 术，提出了在服饰模型中碰撞检测的有效新算法，并构造出关于细分曲面的光滑 因子场方法。凭借这些数学和软件基础，他形象逼真地表现了g e r i 老头的头壳， 浙江大学硕士学位论文第一章绪论 手指和衣服，包括茄克衫，裤子，领带和鞋子。这些都是传统的n u r b s 连续曲 面造型所不易做到的。 除了动画方面的应用，细分曲面凭借其显示速度快、显示曲面的质量高、并 且先天具有多分辨表达性质的能力在游戏以及多分辨应用方面都前景广阔。目前 很多游戏动画软件，比如w a v e f x o n t 、m a y a 、s o f l i m a g e 、3 dm a x 等都已经提供 了细分曲面造型功能。 在工程应用方面，研究得比较多的是基于细分曲面的逆向工程曲面重建 5 - d | 。其中h o p p e 等在文献【习中提出的算法重建质量尤其突出。在加工的应用方 面，也有一些学者做了一些尝试，文献 1 2 、1 4 a l p 作者分别就l o o p 、c a t m u l l c l a r k 细分曲面提出一种数控加工刀轨生成算法。 经过众多学者卓有成效的研究，细分技术无论在理论上还是实践应用上都取 得了长足的进展。细分方法已经成为图形学中一个标准的造型技术。 1 4 本文的主要内容及意义 1 4 1 研究目的和意义 由于细分曲面造型具有技术规则简单、拓扑适应能力强、造型方便、自动保 证整体连续性等诸多优点，并且其递归结构与小波和多分辨率分析有着密切的联 系，因此使得细分在图形学领域得到了广泛深入的研究。但要将细分应用于更多 的领域，尤其是工程领域的应用，如逆向工程曲面建模以及指导加工、制造等方 面还需要进一步的研究。 目前很多学者已经在细分重建这方面作了很多研究，h o p p e 等 5 1 提出的方法 虽然重建质量很高，但是由于引入全局优化非线性能量方程组，使得重建代价很 大，速度很慢；s u z u k i 等1 6 1 虽然不需要求解全局优化非线性能量方程组，使得重 建速度大大加快，但它不能反映出待构物体的细节特征；s a m a v a t i 等 7 1 只是基于 简单的曲线提出了用最小二乘法反求细分规则的方法；而m aw 等【s 9 】也探讨了 基于c a t m u l l c l a r k 细分规则用最d , - 乘法拟合细分曲面的方法；文献1 1 3 j 也是基 于c a t m u l l c l a r k 细分规则在细分矩阵基础上进行曲面重建。 而基于四边形网格的c a t m u l l c l a r k 细分规则曲面重建存在着以下缺点：对 网格进行重采样时，由于广义四边形的四个顶点并不一定共面，即使共面，投影 到初始网格之后也可能不共面；其次，投影点的计算必须和原网格求交。同样， 原四边形网格的四个顶点也不一定共面，这也使得网格必须被剖分成三角形再计 算，客观上增加了计算代价。 文献【1 5 】因此在文献【9 】的基础上采用基于三角网格的l o o p 细分模式重建细 分曲面，它主要在网格质量、采样方法方面作了改进。但该方法由于在几何简化 浙江大学硕士学位论文第一章绪论 和优化过程引入大量代价函数和光顺算子，使得在速度方面不尽如人意。 其次，在拟合细分曲面的过程中，曲面简化、几何及拓扑优化、拟合方法等 技术都还需要进一步完善。 因此，本文拟采用基于三角形网格的l o 叩细分规则进行细分重建，对重建 过程中的网格简化、优化、重采样、以及拟合方法进行研究。在保证重建质量的 前提下，提高其运算速度。 1 4 2 本文的内容 第一章主要介绍本文工作的背景、本文的主要内容以及研究目的和意义。 第二章是论文的算法基础和重建的核心思想。主要内容包括：( 1 ) 建立本文 的数据结构；( 2 ) 介绍l o o p 模式的细分几何规则、细分拓扑规则，并用程序实 现，列出几个实例加以说明；( 3 ) 详尽地描述了本文的细分重建思想和流程，主 要包括三大部分：基网格生成、细分重采样以及细分重建。 第三章主要对基网格生成关键技术之一的网格简化技术进行了研究，提出了 一种新的基于边删除的网格简化算法。相比文献 4 0 1 的简化算法，本文算法首先 引入了控制网格质量的正则性代价函数，使得初始网格在不进行高代价的节点重 定位计算优化的情况下也能得到较好质量的简化网格，减少了计算代价；其次， 本文算法提出了一种共边网格夹角代价函数，使得网格简化速度大大加快并具有 高简化率的同时，又保留了更多的特征信息；最后本文对离散h a u s d o r f f 距离公 式作了进一步简化，得到更为合理的曲面距离表达式，使得简化速度得到迸一步 提升。 第四章主要对基网格生成另一关键技术的网格优化技术进行了研究，提出了 基于l a p l a c e 光顺算子的采样优化方法。和文献【1 5 】的优化算法相比，本文采用 向初始网格采样的方法来克服由l a p l a c e 光顺算子引起的网格收缩，避免了切向 投影技术所引起的切向位移。优化后的顶点仍然是初始网格顶点集的子集，也保 证了优化后的网格对初始网格的精确逼近。这一章也研究了