（应用数学专业论文）loop细分曲面的曲线插值与形状控制.pdf

福建师范大学刘晓芬硕士学位论文 摘要 为了增强细分方法表达曲面的能力，满足实际生产应用中对曲面形状 控制的需求，本文主要对细分曲面造型方法及其应用进行研究，重点研究 细分曲面插值已知曲线和细分曲面的形状控制问题。本文首先回顾了细分 曲面的产生背景、历史和应用，特别是在细分曲面插值和形状控制方面的 应用。然后介绍了细分曲面造型方法的特点、分类标准和几种经典的细分 方法的定义规则等。接着，针对三角网格本文提出了基于l o o p 细分方法 的曲线插值方法并证明了该方法的收敛性。该方法不需要修改细分规则， 只需在被插值曲线的控制多边形两侧构造对称三角网格带，该对称三角网 格带将收敛于插值曲线。因此，包含有该三角网格带的多面体网格的极限 曲面将经过插值曲线。本文还给出了自动构造对称三角网格带的算法。若 要插值多条相交曲线只需在交点处构造全对称三角网格。运用本方法可在 三角网格生成的细分曲面中插值多达六条的相交曲线。在此方法基础上， 最后本文提出了通过插值曲线控制细分曲面形状的几种不同方法。主要基 于两种思想：一、插值曲线的控制多边形保持不变，修改对称三角网格带 的形状：二、修改插值曲线的控制多边形。具体实现方法为：1 、曲率控制： 2 、旋转控制；3 、法向控制：4 、缩放控制：5 、自由变形。 关键词：曲面造型、细分曲面、曲线插值、l o o p 细分、形状控制 福建师范大学刘晓芬硕士学位论文 a b s t r a c t i no r d e rt oe n h a n c ee x p r e s s i n ga b i l i t yo fs u b d i v i s i o nm e t h o da n ds a t i s f y a c t u a ld e m a n do fs u r f a c e s h a p ec o n t r o l l i n g ，t h i s t h e s i s m a i n l ys t u d i e s m o d e l i n ga n da 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 s ，t h ed i s c u s s e dp o i n ti sh o w t o i n t e r p o l a t et h eg i v e nc u r v e si nt h es u b d i v i s i o ns u r f a c ea n dh o wt oc o n t r o l t h es h a p eo fs u b d i v i s i o ns u r f a c e s f i r s t l y ，w er e v i e wt h eb a c k g r o u n d ，h i s t o r y a n da 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 em o d e l i n g s e c o n d l y ，f o rt r i a n g l em e s h ， w ep r e s e n tt h ec h a r a c t e r i s t i ca n dc l a s s i f i c a t i o no fs u b d i v i s i o nm e t h o d sa n dt h e d e f i n i t i o nr u l e so fs o m er e p r e s e n t a t i v es u b d i v i s i o nm e t h o d s t h i r d l y ，w e p r o p o s eam e t h o dt h a tn e e d n tm o d i f ys u b d i v i s i o nr u l e sf o ru s i n gs y m m e t r i c t r i a n g l es t r i p s h a p e dm e s ht og e n e r a t el o o ps u b d i v i s i o ns u r f a c e sw i t hc u r v e i n t e r p o l a t i o n c o n s t r a i n t s t h e s y m m e t r i ct r i a n g l es t r i p s h a p e dm e s hi s c o n s t r u c t e db yd e s i g n i n gs y m m e t r i ct r i a n g l e sf o rb o t hs i d e so ft h ec o n t r o l p o l y g o no fi n t e r p o l a t e dc u r v e t h i sc o n t r o lp o l y g o ni sr e f e r r e da sc e n t r a l p o l y g o n w ec a np r o v et h a tt h es y m m e t r i ct r i a n g l es t r i p s h a p e dm e s hc a n c o n v e r g et ot h ei n t e r p o l a t e dc u r v e s ot h el i m i t e ds u r f a c eo ft h eg i v e nm e s h w i t ht h es y m m e t r i ct r i a n g l es t r i p s h a p e dm e s hw i l lc o n t a i ni n t e r p o l a t e dc u r v e t h i sp a p e rp r o v i d e st h ea r i t h m e t i co ft h ea u t o m a t i cp r o d u c i n gt h es y m m e t r i c t r i a n g l es t r i p s h a p e dm e s h i ft h ei n t e r p o l a t e dc u r v e si n t e r s e c ta tp o i n tv ，w e c a nd e s i g naf u l ls y m m e t r i ct r i a n g l em e s ha tp o i n tv t h em e t h o dp r o p o s e di n t h i sp a p e rw i l li n t e r p o l a t ei n t e r s e c t i n gc u r v e si nt h eg i v e nm e s h t h en u m b e r s o fi n t e r s e c t i n gc u r v e sa r eu pt os i x o nt h eb a s i so ft h i sm e t h o d ，l a s t l y ，w e p r o p o s es o m em e t h o d st h a tc a nc o n t r o lt h es h a p eo fs u b d i v i s i o ns u r f a c e sw i t h t h ei n t e r p o l a t e dc u r v e t h e ym a i n l yb a s eo nt w oi d e a s o n e ，k e e p i n gt h es h a p e o ft h ec o n t r o lp o l y g o no f i n t e r p o l a t e dc u r v e ，w em o d i f yt h es h a p eo ft h e s y m m e t r i ct r i a n g l es t r i p s h a p e dm e s h t w o ，w em o d i f yt h es h a p eo ft h e c o n t r o lp o l y g o no fi n t e r p o l a t e dc u r v e t h em e t h o d si n c l u d i n g ：1 c u r v a t u r e i i 福建师范大学刘晓芬硕士学位论文 c o n t r o ! l i n g ；2 r e v o l u t i o nc o n t r o l l i n g ；3 n o r m a lc o n t r o l l i n g ；4 z o o m c o n t r o l l i n g ；5 f r e e d o mt r a n s f o r m k e y w o r d s ：s u r f a c em o d e l i n g ，s u b d i v i s i o ns u r f a c e ，c u r v ei n t e r p o l a t i o n ，l o o p s u b d i v i s i o n ，s h a p ec o n t r o l l i n g 福建师范大学刘晓芬硕士学位论文 中文文摘 近年来，细分曲面造型技术已经成为计算机辅助几何设计和计算机图 形学领域内的一个国际性研究热点。细分曲面除了具有传统的曲面表示一 一n u r b s 曲面所具有的许多优点：简单高效、局部性、连续性、仿射不变性 等外，还具有任意拓扑性、可伸缩性、表示一致性、数值稳定性、实现的 简单性等特点。这些特点使得细分曲面造型技术能够克服以n u r b s 曲面为 代表的传统的参数曲面表示的一些缺点，如在对人的头、手、自然花卉等 复杂的任意拓扑结构的曲面进行表示时遇到的裁剪和拼接问题。当前，随 着计算机图形显示对于真实性、实时性和交互性要求的提高和几何设计对 象复杂度的提升，细分曲面造型技术的应用越来越广泛，其应用领域包括 工业造型设计、计算机动画、计算机游戏和医学图像处理等。 本文主要研究细分曲面造型方法及其应用，重点研究细分曲面插值已 知曲线和细分曲面的形状控制问题。在实际生产中常常需要对细分曲面进 行曲线插值使得该细分曲面经过一些特征曲线从而控制细分曲面的形状， 甚至需要有一些灵活方便的方法对细分曲面的形状进行进一步的控制以达 到理想的效果。为了满足这些实际应用需求，同时，又由于在实践中三角 形网格是常见的一种网格，所以也为了应用的普遍性，本文选择研究基于 l o o p 细分方法的曲线插值和l o o p 细分曲面的形状控制问题。本文提出了 一种基于l o o p 细分方法的曲线插值方法，并给出了几种通过插值曲线来控 制l o o p 细分曲面的形状的方法。这些曲线插值和形状控制的方法不仅易于 实现，而且有效地增强了细分方法表达曲面的能力，更好地满足了实际生 产应用中对曲面形状控制的需求。本文共分五章： 第一章，绪论。回顾细分方法产生的背景及其发展历史，介绍细分方 法的应用，特别是在细分曲面的插值和形状控制方面的应用，以及本文的 研究内容。 第二章，细分方法综述。综合阐述了细分方法的特点及分类标准，集 中介绍了几种经典的细分方法，如d o o s a b i n 细分方法、c a t m u l l c l a r k v 福建师范大学刘晓芬硕士学位论文 细分方法、l o o p 细分方法、改进的b u t t e r f ly 细分方法以及3 细分方法 等。 细分规则通常由两部分组成。一是拓扑分裂规则( t o p 0 1 0 9 ic a ls p l i t r u le ) ，描述网格经过一次细分后得到的所有顶点之间的连接方式；另一 个是几何规则( g e o m e t r i cr u le ) ，决定经过一次细分后产生的新点的几 何位置。根据细分方法分类标准，d o o s a b i n 细分方法是基于四边形网格， 采用点分裂操作作为拓扑规则的细分方法，该细分方法生成的细分曲面是 双二次均匀b 样条曲面向任意拓扑结构网格的推广，所以它生成的极限曲 面为c 连续：c a t m u l l c l a r k 细分方法与d o o s a b i n 细分方法一样是基于 四边形网格，但它采用l 一4 四边形分裂法生成新网格的拓扑，利用该细分 方法生成的细分曲面是双三次均匀b 样条曲面向任意拓扑结构网格的推 广，所以它生成的极限曲面为c2 连续：与c a t m u l l 一c l a r k 细分方法和 d o o s a b in 细分方法不同，l o o p 细分方法是一种基于三角网格的细分方法， 所生成的细分曲面是盒式样条( b o xs p l in e ) 曲面的推广，它采用卜4 三 角形分裂法生成新网格的拓扑，在规则的三角网格上能生成c2 连续的极限 曲面，对于非规则的三角网格，除奇异点处是c 。连续外，其余点都是c ! 连续：以上三神经典的细分方法都属于逼近型细分方法。 通过对各种经典的细分方法的比较，本文选择l o o p 细分方法作为研究 的对象，这是因为1 、前人在这方面研究的还不是很多，2 、l o o p 细分方法 是基于三角网格的，而三角网格是最常见一种拓扑结构。本文研究的主要 内容是基于l o o p 细分方法的曲线插值和l o o p 细分曲面的形状控制问题。 第三章，基于l o o p 细分方法的曲线插值。给出了一种新的利用l o o p 细分方法进行曲线插值的方法。该方法不需要修改细分规则，只要在被插 值曲线的控制多边形两侧构造对称三角网格带即可。被插值曲线可以是一 条或多条不相交的曲线，也可以是多条相交的曲线。 曲线插值是指在构造曲面过程中通过一定的方法使最终生成的曲面经 过预先指定的曲线。本文提出的基于l o o p 细分方法的曲线插值方法，关键 的思想是在被插值曲线的控制多边形两侧构造对称三角网格带。所谓对称 三角网格带是由一系列对称三角形构成，其中每对相邻的对称三角形都可 构成对称三角网格。对称三角网格的定义为以被插值曲线的控制多边形的 v 福建师范大学刘晓芬硕士学位论文 任意两条相邻边为公共边，向其两侧构造三角形，每对有公共边的三角形 的两个相对点关于公共边的中点对称。本文证明了，一个对称三角网格带， 经过k ( k - - o 。) 次l o o p 细分后得到的极限曲线是一条由对称三角网格带的中 心多边形确定的三次均匀b 样条曲线。因此，欲插值一条三次均匀b 样条 曲线，只要对该曲线的控制多边形构造对称三角网格带就能实现。本文给 出了自动构造对称三角网格带的算法。进一步，要插值相交曲线，需在插 值点处构造全对称三角网格。全对称三角网格是在对称三角网格基础上加 强条件，使得每对通过对称三角网格中心点的线段共线且相等。本文证明 了，经过k ( k _ 0 0 ) 次l o o p 细分后，极限曲线将经过全对称三角网格的中心 点，即多条曲线的相交点，从而使最终生成的细分曲面插值多条相交曲线。 第四章，基于插值曲线的l o o p 细分曲面形状控制。在第三章介绍的曲 线插值方法的基础上，给出了控制l o o p 细分曲面形状的不同方法：这些方 法的核心思想是利用插值曲线及其对称三角网格带的仿射变换来调节 l o o p 细分曲面形状。 本文提出的控制细分曲面形状的几种不同方法主要是通过插值曲线的 变化来进行控制。主要基于两种思想：一、插值曲线的控制多边形保持不 变，修改对称三角网格带的形状：二、修改插值曲线的控制多边形。对于 第一种思想，具体实现方法有：1 、曲率控制；2 、旋转控制：3 、法向控制。 对于第二种思想的具体实现方法为：l 、缩放控制；2 、自由变形。 曲率控制：对于对称三角网格带，改变其每条中心边中点到对应的相 对点的长度，当，变大时，细分曲面的曲率变小；当f 变小时，细分曲面 的曲率变大。 旋转控制：对于对称三角网格带，设每对对称三角形共面的面为m ， 将其对应的两相对点在面m ，上绕着它们的公共边的中点旋转 只( 石 只 丌) 。 法向控制：对于对称三角网格带，将有公共边的每对对称三角形绕其 公共边旋转( 一万 l 3 时成= 击。 ( 2 ) 拓扑结构的建立 连接每个新顶点与其周围的新边点； 连接每个新边点与其周围的新边点。 图2 7 2 8 显示了l o o p 细分方法的模板。图2 9 显示了对三角形网格 运用l o o p 细分方法一次后网格的联接情况。 3 1 8 1 培 图27e 一顶点模板图 图28v 一顶点模板图 图2 9l o o p 细分方法的拓扑规则 福建师范大学刘晓芬硕士学位论文 2 4 4 改进的b u t t e r f iy 细分方法 b u t t e r f l y 细分方法是d y n 、g r e g o r y 和l e v i n “”于1 9 9 0 年提出的一种适 用于三角形网格的细分新方法，由于其模板与蝴蝶相似而得名。这种细分 方法与l o o p 细分方法有相似之处，都是基于面分裂的细分方法，即每个三 角形一分为四。但是与l o o p 细分方法不同的是，它是属于插值型细分方法， 每次细分时，原来网格的顶点位置不变，只是对每条边生成一个新的顶点， 即新边点( e - 顶点) 。最初的b u t t e r f l y 细分方法生成的极限曲面在规则点 处达到c 1 连续，但在奇异点处不能达到c 连续。后来z o r i l l s 1 提出了改进的 b u t t e r f l y 细分方法，它可以在任意的三角形网格上生成c 连续的曲面。 下面主要介绍改进的b u t t e r f l y 细分方法。对于三类不同情况的网格边 产生三类新边点( e - 顶点) ，第一类网格边是内部边且该边的两个端点的 度数均为6 ，第二类网格边是内部边且该边至少有一个端点的度数不等于6 ， 第三类网格边是内部边且该边的两个端点的度数均不为6 。 ( 1 ) 几何规则 第一类新边点( e 一顶点) ：对于网格中一内部边v v ，该边两个端点的 度数均为6 ，则产生该边对应的新边点( e - 顶点) 的细分模板见图2 1 0 ， 其中d = 一，b = + 2 w ，c 1 6，d = 0 3 ，0 蔓甜- l ，一般取0 3 = 0 。边v ，v 上的新边点v 。的计算公式为 v f = a ( v j + v ) + b ( v 8 + v 4 ) + c ( v l + v 3 + v 5 + v 7 ) + d ( v 2 + v 6 ) 第二类新边点( e - 顶点) ：对于网格中一内部边，该边一个端点为规则 点( 度数为6 ) ，另一个端点为奇异点( 度数7 6 ) ，则产生该边对应 的新边点( e - 顶点) 的细分模板见图2 1 1 ，点v 为奇异点。其中各邻接 点的权值表示如下： 当盯5 时，- = i i i i + c o s 等! + 号c 0 5 专2 ) f = 0 ，n 一1 ； 当玎= 3 时，s o = 吉，s = 是= 一古： 当n = 4 时，s o = ，s t = 邑= 0 ，s 2 = 一 。 新边点v 。的计算公式为： 第2 章细分方法综述 v 。= v + s v l i - o 第三类新边点( e - 顶点) ：对于网格中一内部边，该边两个端点的度数 均不为6 ，为了得到该边的新边点，先对该边的两端点分别应用第二类 新边点的模板产生两个新顶点，则该边的新边点就是这两个新顶点的 平均值。 礴圆岛 图2 1 0e - 顶点模板图 f i g2 10e v e r t e xm a s k 该边为两端点度数均为6 的内部边 图2 1 1e - 顶点模板图 f i g2 11 e - v e r t e xm a s k 该边为一端点度数为6 的内部边 ( 2 ) 拓扑结构的建立 改进的b u t e r f ly 细分方法的拓扑结构的建立与l o o p - - 羊，即每个三角 形一分为四。 连接每个顶点与其周围的新边点： 连接每个新边点与其周围的新边点。 2 4 5 , f i 细分方法 前面介绍的四种细分方法除d o o s a b i n 细分方法外都采用卜4 网格分 裂，因此每次细分都使多边形面片数增加4 倍，面片增长速度太快，不利于 多分辨率处理。k o b b e l t 2 9 在2 0 0 0 年提出一种称为3 细分方法的算法有效 地减缓了面片增长速度。该方法以三角网格为初始控制网格，采用一种新 的顶点插入和分裂方式。经过一次细分，三角形面的个数增加3 倍，两次细 分后，三角形面的个数增加9 倍，能达到一阶光滑。 ( 1 ) 几何规则 福建师范大学刘晓芬硕士学位论文 新面点( f - 顶点) ：设三角形的三个顶点为v 。，v 。，v ：，则该面的新面点 为三个顶点的平均，即 v f = ( v o + v l + v 2 ) 新顶点( v 一顶点) ：设顶点v 的n 个相邻点为v 。，”l j 一，v 。，则顶点v 的新 顶点为该点本身和其所有相邻顶点的加权和，即 v r = ( 一a ) v + 鲁萎v ， 其中口= ( 4 2 c o s ( 2 叫n ) ) 9 。 ( 2 ) 拓扑结构的建立 每次细分时，先将每个三角形面的新面点与三角形的三个顶点相连， 然后去掉原三角形的内部边，最后将每个面的新面点与同该面相邻的所有 面的新面点相连。 图2 1 2 2 1 3 为3 细分方法的模板。图2 1 4 显示了3 细分方法细分 二次的过程。 图2 1 2f - 顶点模板图 f i g2 i2f - v e r t e xm a s k 图2 1 3v - 顶点模板图 f i g2 13v v e r t e xm a s k 第2 章细分方法综述 2 5 小结 笪么么 ( a )( b )( c ) & 氐 ( d )( e ) 图2 1 4 i 细分方法示意图。 一 f i g2 1 44 3 s u b d i v i s i o ns k e t c hm a p ( a ) 初始网搭；( b ) 一( c ) 第一次细分；( d ) 一( e ) 第二次细分。 本章首先解释了细分方法描述中的一些常用术语，接着介绍了细分方 法的主要特点及几种分类方式，最后描述了几种经典的细分方法，如 d o o s a b i n 细分方法、c a t m u l l c l a r k 细分方法、l o o p 细分方法、改进的 b u t t e r f l y 细分方法、手细分方法等，并对每一种细分方法给出其模板及 拓扑结构的连接方式示意图。 福建师范大学刘晓芬硕士学位论文 第3 章基于l o o p 细分方法的曲线插值 3 1 引言 所谓曲线插值是指在构造曲面过程中通过一定的方法使最终生成的曲 面经过预先指定的曲线。这在实际应用中有很重要的意义。例如，在产品 外观设计中，我们需要使最后成形的曲面经过特定的些曲线，这些曲线 决定了产品的最后形状特征。最早研究细分曲面中的曲线插值问题的是 n a s r p 2 。43 。川。他提出了基于d o o s a b i n 细分方法生成带有曲线插值约束的 细分曲面“2 ”3 和基于c a t m u l l - c l a r k 细分方法生成带有曲线插值约束的细 分曲面“。这些方法所插值的曲线都是均匀b 样条曲线，为了能够插值 n u r b s 曲线，张景峤n ”等提出了基于非均匀c a t m u l l 一c l a r k 细分方法的曲 线插值方法。以上这些方法基于的初始网格都是四边形网格，而在实践中 三角形网格是常见的一种网格，若要应用上述方法需先将三角形网格转换 成四边形网格，这样必然会增加计算量。若能直接在三角网格的基础上实 现曲线插值，则会很大的提高计算效率。基于这个思想本章给出了基于 l o o p 细分方法生成带有曲线插值约束的细分曲面的方法。 本章给出的基于l o o p 细分方法的曲线插值方法不需要修改细分规则， 只需以插值曲线的控制多边形为中心多边形，向其两侧构造对称三角网格 带，该对称三角网格带将收敛于插值曲线。因此，包含有该三角网格带的 多面体网格的极限曲面将经过插值曲线。运用本章提出的方法可在三角网 格生成的细分曲面上插值多种情况的曲线：( 1 ) 单条闭合曲线或开曲线： ( 2 ) 多条不相交的闭合曲线或开曲线；( 3 ) 多条相交曲线，最多可达到六 条。 3 2l o o p 多边形网格带 为了实现生成带有曲线插值约束的l o o p 细分曲面，本节首先定义一种 第3 章基于l o o p 细分方法的曲线插值 最终能生成一条满足条件的插值曲线的三角网格带。该三角网格带可根据 预先给定的条件定义。 ? 考阀上汐仍景坎 定义1设有a 、b 、c 三点，若该三点基线且点b 为线段a c 的中点， 即la b | = j b cl ，则称点a 、c 关于。直b 过称。( 参见图3 1 ) 定义2对于两相邻三角形( v 。，v ；，v ：) 和( v 。，v ，v ，) ，若点v ：、v ：， 关于公共边vo v 的中点e 对称，则称avo v 。v 。与v o v v ：。为对称三角形。公 共边v o v 称为中心边，点v 。、v 。称为关于中心边v0 v i 的相对点。( 参见图 3 2 ) 定义3设有两组对称三角形，两条中心边相交于公共点v ，则将两 对相对点中位于两中心边同一侧的两点连接所构成的三角网格称为对称三 角网格，公共点v 称为中心点。 图3 3 所示三角网格为对称三角网格，其中c a 。v 与c ，b v 为对称 三角形，aca o 。v 与c ：b ：v 为对称三角形，点v 为中心点。 幽3i 对称图32 对称二角形 f i g3 1s y m m e t r y f i g3 2s y m m e t r yt r i a n g l e b 图33 对称二角网格 f i g3 3s y m m e t r yt r i a n g l e m e s h 定义4设s 为对称三角网格，中心点为点v ，点a t 、b - 为关于中心边 c ，v 的相对点，点a ：、b ：为关于中心边v c ：的相对点，若点a 、v 、bz 三点 共线且la v i = iv b ：】，点c 、v 、c ：三点共线且lc - v l2 lv cz i ，点0 2 、v 、b t 三 点共线且la ：v l = v b i ，则称s 为全对称三角网格。( 参见图3 4 ) 定义5 由一系列对称三角形构成的三角网格带称为砬箍三鱼旦坚 直，其中则! 塑堕銎签三鱼受叠旦生幽整三堑幽，由中心边构成的 多边形称为中心多边形。 福建师范大学刘晓芬硕士学位论文 图3 5 所示为一对称三角网格带，其中以点c 。、c 、c ：、c 。、c t 、cs 为 顶点的多边形为中心多边形。 图3 4 全对称三角网格 f i g3 4f u l ls y m m e t r i c t r i a n g l em e s h 3 3 对称三角网格带的收敛 图3 5 对称三角网格带 f i g3 5s y m m e t r i ct r i a n g l e s t r i p - s h a p e dm e s h 根据3 2 小节的定义，下面分析用l o o p 细分方法对对称三角网格带进 行细分的情况。 引理1对于给定的对称三角网格带g ，若对g 进行一次l o o p 细分( 不 考虑边界情况) 所得到三角网格带g7 仍为对称三角网格带。 证明：根据对称三角网格带的定义( 定义5 ) ，显然要证对一个对称三 角网格带进行一次l o o p 细分后仍得到一个对称三角网格带，只要证明一个 对称三角网格经过一次l o o p 细分后仍得到一个对称三角网格。对于任意一 个对称三角网格( 如图3 6 所示) ，其中，点v 为中心点，边c 1 扎c ：v 为中 心边，点a 、b l 为关于中心边c i v 的相对点，点口2 、b 2 为关于中心边c 2 v 的 相对点，点e 。为中心边c l v 的中点，点e ：为中心边c ：v 的中点。相应的点c f 、 c 2 、d ：、a ；、b 0 毯、v 为一次l o o p 细分后产生的新点。点e ：为边c ；v 的 中点，点e ：为边c ；v 的中点。 显然要证一个对称三角网格经过一次l o o p 细分后仍得到一个对称三 角网格，我们只要证明2 e ，- a f + b f 2 e c t ；+ b i 。 第3 章基于l o o p 细分方法的曲线插值 图3 6 对称三角网格 f i g3 6s y m m e t r yt r i a n g l em e s h 由定义1 有a i + b i = 2 e 】 a 2 + b 2 = 2 e 2 c 1 + v = 2 e 1 c 2 + v = 2 e2 根据l o o p 细分公式有 c ，_ ( c 1 + v ) + ( d + 岛) a f = ( d l + v ) + ( c l + a 2 ) b i = ( 6 l + v ) + ( c l + b 2 ) v7 = 古( c l 十c 2 + d l + a 2 + b l + b 2 ) + 言v 将式( 3 1 ) 一( 3 - 4 ) 代入上述诸式得 c f _ ；- 2 p l + 2 e 1 = e 1 v = f f ( 2 e i + 2 e 2 + c l + c 2 ) + ；v = ( p l + e 2 ) + v d f + 6 ：= ( 2 v + 2 e i ) + ( 2 c i + 2 e 2 ) = 号p l + 8 2 + v 2 e f = c ：+ v = p i + p 2 + v 即证得2 e ：= a f + “，同理可证2 e ；= 日：+ 噬。 证毕。 ( 3 1 ) ( 3 - 2 ) ( 3 3 ) ( 3 - 4 ) ( 3 - 5 ) ( 3 - 6 ) 引理2给定一个对称三角网格带g ，把g 的中心多边形看作一条三 次均匀b 样条曲线的控制多边形，把每个节点区间的中点作为新节点插入， 得到一条新的控制多边形，它与g 经过一次l o o p 细分后，所得的对称三角 网格带g7 的中心多边形相同。 证明：e h 式( 3 - 5 ) ( 3 - 6 ) 有 福建师范大学刘晓芬硕士学位论文 = 铲华 z c 2 = 半 ( 3 - 7 ) ( 3 - 8 ) v = 撕+ 8 ：) + v = ( 毕+ 竿) + v = ( c i 4 - c 2 ) + v ( 3 9 ) 式( 3 - 7 ) 一( 3 - 9 ) 即为将每个节点区间的中点作为新节点插入所得的 新的控制顶点“。 证毕。 根据引理卜2 可推出下面定理。 定理1设g 为一对称三角网格带，经过( 女一( 3 0 ) 次l o o p 细分后得到 的极限曲线是一条由g 的中心多边形确定的三次均匀b 样条曲线。 证明：( 1 ) 根据l o o p 细分理论“，经过k 次l o o p 细分，当k 哼0 0 时， 对称三角网格带将收敛于其中心多边形；( 2 ) 根据b 样条曲线理论”1 ，反 复插入各节点区间中点将使得控制多边形收敛于相应的b 样条曲线。于是 由( 1 ) 、( 2 ) 及引理2 知本定理成立。 证毕。 定理2 设g 为一对称三角网格带，c i c ：c 。是g 的中心多边形，当点 c h 、c i 、c j + i ( 2 f n 一1 ) 三点共线且ic ) - i c ，i = 1c i c i 时，g 经过( 斗) 次l o o p 细分后得到的极限曲线将插值于点c i 。 证明：当点c h 、c ，、c 三点共线且lc i _ l c 。i = 1c i c l 时，经过一次l o o p 细分后，由式( 3 - 6 ) 可得c q 。又r - h 式( 3 - 5 ) 得c ：1 = 华：c 2 ，= ! l 等量； 所以点c ：。、c _ 三点共线且lc - c ；i = 1c ：c ：+ i ，由此知经任意次l o o p 细分 后点c 总在中心多边形上。于是由定理1 的证明知，g 经过( 七一) 次l o o p 细分后得到的极限曲线将插值于点c ，。 证毕。 推论1设g ，f - 1 , 2 ，m 是共享同一个全对称三角网格f 的m ( m 6 ) 个对称三角网格带，为g 的中心多边形的终边，f 的中心点为g 。的中心 多边形的倒数第二个顶点，则经过k ( k 斗) 次l o o p 细分后，m 个对称三角 2 6 第3 章基于l o o p 细分方法的曲线插值 网格带收敛于m 条相交于全对称三角网格f 的中心点的三次均匀b 样条曲 线只，i = 1 , 2 ，m 。若l ，与l ，共线，则g 与g ，对应的曲线只与0 在f 的中心 点处c 1 连续，反之，则c o 连续。 3 4 插值多条不相交曲线 根据定理l ，可以对给定的三角网格构造l o o p 细分曲面，使得该曲面 通过指定的一条或多条不相交的曲线。问题描述如下： 给定一个三角网格h ，在上指定m 个控制多边形印，f _ l ，2 ，m ，由 印，确定的m 条三次均匀b 样条曲线只不相交，要求构造插值m 条由c p ， f - 1 , 2 ，确定的三次均匀b 样条曲线p 的l o o p 细分曲面。 为了能够使得的l o o p 细分曲面插值m 条不相交的由叩，确定的三次 均匀b 样条曲线p ，根据定理1 只要在上以印。为中心多边形构造嵌入对 称三角网格带，对得到的三角网格运用l o o p 细分规则，生成的极限曲 面就能实现插值m 条不相交的曲线。 由于m 个对称三角网格带的构造方法类似，本文以一个对称三角网格 带的构造为例。对于某个控制多边形印，设它的n 个控制顶点为c ， i = 1 , 2 ，n ，n l 条边为l 。、l ? 、l 。，l j = c ，c ，j = l ，2 ，n l ，则构造 以印为中心多边形的对称三角网格带的具体方法是：( 1 ) 在印，的每条边 l 。，j 2 l ，2 ，n 一1 的两侧构造对称三角形c j 。川口，】和c 0 + r 点a a ，2 为 关于中心边l 。的相对点；( 2 ) 分别将位于c p ，同侧的相对点连接起来。在构 造中应遵循的原则是：1 、基于数据量方面的考虑，选取点口、口，：时应尽 量选取在给定三角网格上的点，在一定范围内可适当调整原三角网格上的 点的位置，使得最终新生成的三角形尽量少：2 、若印，上的顶点的度大于 6 ，则删除多余的边，多余边的另一个端点根据就近原则与相近的点连接； 3 、若印，上的顶点的度小于6 ，则添加边，即对印，上以该顶点为端点的两 条边l ，、l 。重新选取各自的相对点使得该顶点的度为6 。 对称三角网格带可手动构造实现，也可自动构造实现。手动构造即手 动选取控制多边形印上每条边的相对点。而自动构造的实现方法见本文 3 5 节。 福建师范大学刘晓芬硕士学位论文 图3 7 显示了进行曲线插值的例子，其初始网格为位于立方体表面的 三角网格，最终的极限曲面通过以立方体四个面的中线为控制多边形确定 的曲线。其中，上行从左到右为：初始网格、加入插值控制多边形( 加粗) 的初始网格和嵌入对称三角网格带的修改后的网格：下行从左到右为：无 插值曲线的极限曲面、对嵌入对称三角网格带的修改后的网格进行一次 l o o p 细分和三次l o o p 细分后的效果( 黑粗线为插值曲线) 。图3 8 给出了 一个对称三角网格带的例子。其中，黑实线为一个一般的对称三角网格带， 白实线为它的中心多边形、虚线为第一次细分的效果和黑粗线为极限曲线。 图3 9 显示了一个插值两条不相交曲线的例子。其中，左边从上到下为： 初始网格和嵌入对称三角网格带的修改后的网格：右边从上到下为：无插 值曲线的极限曲面和对嵌入对称三角网格带的修改后的网格进行三次 l o o p 细分后的效果( 黑粗线为插值曲线) 。 赂路 图3 7 立方体曲面插值曲线 第3 章基于l o o p 细分方法的曲线插值 图3 8 对称三角网格带 图3 9 插值两条不相交的曲线 3 5 自动构造对称三角网格带 设插值曲线的控制多边形为c i c ：巳，在原始网格中以边 c i c f + i ，i = l ，2 仃一1 为公共边的两三角形为q t + l6 i 和kc , c 6 f 2 ，边q 气l 的中 点为e 。，则实现自动构造以控制多边形c j c ：0 为中心多边形的对称三角网 格带的关键是确定关于中心边c , c 。的相对点口。和口f 2 0 为了使对称三角网格 福建师范大学刘晓芬硕士学位论文 带实现自动构造，首先给定一个网格上的点可调整的移动范围s ，当点包移 至点b , 位置或点b j ：移至点6 ；2 位置时，应满足i 阳- b , 0 占或0 6 f 2 一b , 2 i i f 。在本 节提出的自动构造对称三角网格带的算法中主要分三种情况考虑。 情况一：移动点6 f 。或岛：。当点岛。在移动范围占内移动时，能够使得点 成为关于中心边c ，c 。的相对点，即口。= 且a 。：= b 则移动点b ”或者， 当点岛：在移动范围s 内移动时，能够使得点成为关于中心边c l c o 的相对 点，即口。= b i 且q 2 = ，则移动点6 f ：。否则，考虑情况二。 情况二：添加点a ，l 或a 1 2 0 当情况一不可行时，若点日f l 向c i c 。6 i 方向 上的投影点落在公共边为边c 6 f 。、c j + l6 l 。的三角形面内，取口，：= b 2 ，添加点口“ 或者，若点q ：向c i c i + 。6 f ：方向上的投影点落在公共边为边c ，6 f ：、c j + 。岛：的三 角形面内，取口。= b i 。，添加点口，否则，考虑情况三。 情况三：同时添加点a 口i 2 0 当情况二不可行时，为了使得原网格总 体形状不作太大变化，则只有同时添加两点a 。口， 在本算法中，除了考虑关于中心边e c 。的相对点a 。和q ：的确定以外， 还应考虑的是中心多边形上的点的度数问题，应始终保持这些点的度数为 6 ，为此就须适当地增、减边数。具体算法如下： p o r1 = lt 0n l 求点6 f 关于中心边q c j + 。的中点e ，的对称点及点包：关于中心边e t + 的中 点e ，的对称点6 f l 。 i f 点、包2 的距离i b ；2 b , 2 i s t h e n 将点6 j 2 移至点的位置，即6 ：= ，使得口。= b a ，：= 包2 。 e l s ei f 点、b i l 的距离f b , b , i i 6 t h e n 删除多余的边，将点口川，i 与点口川相连接，点。_ 1 2 与点口膳相连 接，删除的边上除点c ，外的另一个端点按就近原则与邻近它的 点相连接构成三角形面。 e n d ： e n d 福建师范大学刘晓芬硕士学位论文 3 6 插值多条相交曲线 根据本文3 3 小节的结论，还可生成插值多条相交曲线的l o o p 细分曲 面。 设给定一个三角网格日，在日上指定i n 个控制多边形e p ，i = 1 , 2 ，m ， 由c p 。确定的三次均匀b 样条曲线为只。为了使l o o p 细分曲面插值多条相 交曲线，不妨设m ( 1 m 6 ) 个插值曲线的控制多边形印相交于点v ，且 这些控制多边形c p 。满足下面的条件。 条件1 ：交点v 为每个控制多边形的倒数第二个顶点，且在点v 处可 构造共享全对称三角网格。 根据定理l 和定理2 ，可构造插值m 条交于点v 的曲线只只，只的 l o o p 细分曲面。 实现方法包括三个步骤：( 1 ) 构造1 1 1 个对称三角网格带；( 2 ) 在中心 多边形的交点处构造共享的全对称三角网格；( 3 ) 应用l o o p 细分方法对修 改后的三角网格进行细分。 ( 1 ) 构造m 个对称三角网格带 构造方法可参见本文3 4 节、3 5 节。 ( 2 ) 构造共享全对称三角网格 为简便起见，首先考虑m = 2 的情况，即两条益线相交的情况。根据条 件l ，可分两种情况讨论。情况一，两个控制多边形的相交于点v 的终边 共线：情况二，两个控制多边形的相交于点v 的终边不共线。对于情况一 可直接用步骤( 1 ) 中构造对称三角网格的方法实现。现在讨论情况二。 设两个控制多边形c p ，、c p ，相交于点v ，如图3 1 0 所示，边c v 为c p 的终边，边d v 为c p 。的终边，边c v 、d v 不共线。构造共享全对称三角网 格步骤如下： 步骤 步骤 步骤 步骤 联接点a 和d 、点b 和c 。 过点v 作边a d 、b c 的平行线e f ，使得| e vj = lv f l = la d | = lb c l 联接点d 和f ，点e 和b ，点f 和c 以及点e 和a 。 将构造的共享全对称三角网格嵌入原网格中。 第3 章基于l o o p 细分方法的曲线插值 图3 1 0 共享全对称三角网格 f i g3 10s h a r i n gr u t is y m m e t r y t r i a n 2 l em e s h 在进行步骤4 操作时，应遵循的原则是：1 、若点v 的度大于6 ，则删 除多余的边。多余边的另一个端点根据就近原则与相近的点连接：2 、对于