（计算机应用技术专业论文）细分模式构造及其拟合技术.pdf

摘要 细分方法是近些年几何造型领域最活跃的研究热点之一：细分曲面连续性分 析理论逐渐完善；新的细分模式不断涌现；细分技术被广泛应用于三维模型的多 分辨率表示、计算机动画、数字几何处理。但是，大部分细分模式都是孤立地被 提出来的，虽然人们多少掌握了它们的一些基本性质( 比如连续性) ，但对彼此 间有何联系却了解不多。细分曲面质量的影响因素及其评估与改进方法也有待进 一步探索。在细分技术应用方面，面向图形学多分辨表示的应用相对成熟，但面 向c a d 的重构与拟合的工作却不多见。本文对细分模式构造和细分益面拟合进 行了较深入的研究，主要内容包括： 口提出了一个改进的k o b b e l t 插值模式。新模式非规则情形模板( m a s k ) 的构造 方法是：先把规则情形的张量积模板分解为卜邻域的规则小模板；其次，利 用块状循环矩阵的f o u r i e r 分析技术把规则小模板推广到非规则小模板；最 后把非规则小模板合并为非规则大模板。与原来模板相比，新模板除了具有 更清晰的数学背景外，另一个重要优点是所生成的极限曲模板有有限曲率， 从而改善细分曲面的光顺性。此外，不论是四边形还是多边形初始网格，新 方法都不需要作预处理。由于规则情形下新方法与k o b b e l t 插值模式一致， 因此达到c 1 连续。而在奇异顶点处新模式是g 1 连续的。 口 提出4 8 模式的。种四边形网格实现技术，因为基于四边形网格的2 分裂， 因此称为2 细分。为平衡不同入度( v a l e n c e ) 的项点基函数的最大值，引进 一组新的权值计算v 一顶点。对于规则网格，2 细分曲面与4 8 细分曲面相 同是c 4 光滑的。对特征映射的初步分析表明，非规则情形下极限曲面仍为c i 连续。由于用四边形网格表示3 - 4 网格，可以减少；的网格边、的网格面， 因此2 细分的存储方式更紧致。相应地，运行效率也更高。与4 8 模式相比， 2 细分的另一个优点是可以自然地推广到任意多边形初始网格。 口 同样基于2 分裂算子，本文还提出了一个新的插值模式。该模式是插值3 细分在四边形网格巾的对应物。初步分析以及实验结果表明，插值、2 细分曲 面是c 1 连续的。当网格面个数受到限制时，2 插值模式可以比其它插值模 式提供更多的分辨率层从而改善l o d 的效果。 口 实现一个基于带尖锐特征的l o o p 细分曲面的三角网格拟合系统。基本原理 来自【m ae ta 1 2 0 0 2 1 ，但在系统设计层面对原算法作了相当大的补充和完善。 整个系统框架包括尖锐特征提取、保持尖锐特征的三角网格简化、保持尖锐 特征的网格平滑和拓扑优化、基于最近点策略的重采样和线性拟合系统求 解。所得到的拟合曲面质量较之原来的结果明显提高。 口 考虑到绝大部分离散光顺算法都是针对三角网格提出的，一般不能应用于任 意多边形网格，本文提出了一个任意多边形网格光顺算法。给出了一种新的 防止收缩策略：假定网格面中心的噪声为零，因此平滑时要求插值这些中心 点。设计算法的迭代式的权值时利用了i 分裂算子和c a t m u l l - c l a r k 细分模 式的系数。 a b s t r a c t s u b d i v i s i o ni so n eo ft h em o s ta c t i v er e s e a r c hh o t s p o t si ng e o m e t r i cm o d e l i n g ， e s p e c i a l l ys u r f a c ed e s i g n ，i n c u r r e n ty e a r s i ti s c o m p r e h e n d e dm o r ea n dm o r e p r o f o u n d l yb yr e s e a r c h e r sw i t hc o m p l e t ee s t a b l i s h m e n to fc o n t i n u i t ya n a l y s i st h e o r y o fs u b d i v i s i o ns u r f a c e s ，i n c e s s a n te m e r g e n c eo fn e ws c h e m e sa n de x t e n s i v e a p p l i c a t i o n so fs u b d n i s i o nt e c h n i q u e st om u l t i r e s o l u t i o nr e p r e s e n t a t i o no f3 dm o d e l s ， c o m p u t e ra n i m a t i o n ，d i g i t a lg e o m e t r yp r o c e s s i n ga n ds oo n h o w e v e r , a l t h o u g ht h e i r b a s i cp r o p e r t i e s ( f o re x a m p l e ，c o n t i n u i t y ) w e r ei n v e s t i g a t e ds i m u l t a n e o u s l yw h e nt h e y w e r ep r o p o s e ds o l e l y ，p e o p l ek n o wl i t t l ea b o u tt h e i rr e l a t i o n s h i p m o r e o v e r , i ti s n e c e s s a r y f u r t h e rt o e x p l o i ti n f u e n c e df a c t o r s ，e v a l u a t i o na n di m p r o v e m e n to f s u b d i v i s i o ns u r f a c eq u a l i t y a sf o rt h e i ra p p l i c a t i o n s ，t e c h n i q u e sf o rc o m p u t e r g r a p h i c s ，f o re x a m p l e ，m u l t i r e s o l u t i o nr e p r e s e n t a t i o nb a s e d o ns u b d i v i s i o na p p r o a c h e s ， a r er e l a t i v e l ym o r es u c c e s s f u li nc o n t r a s tt or e c o n s t r u c t i o n ，f i t t i n g ，a n dp r o c e s s i n g c a do r i e n t e d ，t h i sr e p o r td i s c u s s e sc o n s t r u c t i o no fs u b d i v i s i o ns c h e m e sa n df i t t i n g o f s u b d i v i s i o ns u r f a c e s m a j o r c o n t r i b u t i o n s l i s t a s f o l l o w s 口am o d i f i e dk o b b e l ti n t e l p o l a t o r ys u b d i v i s i o ni sp r o p o s e d n e wr u l e sa r e e s t a b l i s h e di nt h r e es t e p s ：f i r s t l y ，t h er e g u l a rt e n s o r - p r o d u c tm a s ki sd e c o m p o s e d i n t of o u rs m a l lr e g u l a rm a s k so f1 - n i e g h b o r h o o d ；s e c o n d l y ，t h e s es m a l lr e g u l a r m a s k sa l ee x t e n d e dt oi r r e g u l a rc a s e s ；f i n a l l y ，t h es m a l li r r e g u l a rm a s k sa r e s y n t h e s i z e di n t or e q u i r e di r r e g u l a rm a s k s c o m p a r i n gt ok o b b e l t sm a s k s ，t h e n e wr u l e sn o to n l yo w nc l e a rm a t h e m a t i c a lb a c k g r o u n db u ta l s op r o d u c el i m i t s u r f a c e sw i t hb o u n d e dc u r v a t u r et h e r e f o r ea r ea b l et op r o d u c ei n t e r p o l o a t o r y s u r f a c e so f h i g h e rq u a l i t y m o r e o v e r ，n e wr u l e sc a nd i r e c t l yb ep e r f o r m e dw i t h o u t p r e p r o c e s s i n gf o rb o t hq u a d r i l a t e r a la n dp o l y g o n a lo r i g i n a lm e s h e s ，f o rr e g u l a r m e s h e s ，t h em o d i f i e dv e r s i o ng e n e r a t e st h es a m er e s u l ta st h a to ft h ek o b b e l t a p p r o a c ha n dt h u si s c ic o n t i n u o u s a te x t r a o r d i n a r yv e r t i c e s ，t h el i m i ts u r f a c e s a r ep r o v e dt ob eg 1c o n t i n u o u s ， 口a q u a d r i l a t e r a lv e r s i o o ft h e4 8s u b d i v i s i o ni s d i s c u s s e da n dc a l l e d 压 s u b d i v i s i o nd u et oe m p l o y m e n to ft h e4 2 s p l i t t i n go p e r a t o r t ob a l a n c et h e m a x i m a lm a g n i t u d eo ft h eb a s i sf u n c t i o n sf o rd i f f e r e n tv a l e n c e s ，an e ws e to f w e i g h t si sd e s i g n e dt oc o m p u t ev - v e r t i c e s f o rr e g u l a rm e s h e s ，4 2s u b d i v i s i o n p r o d u c e st h el i m i ts u r f a c e si na c c o r d a n c e w i t ht h o s eo ft h e4 - 8s c h e m ea n d t h e r e f o r ei sc 4 s m o o t h e l e m e n t a r ya n a l y s i s o nc h a r a c t e r i s t i c m a p s d e m o n s t r a t e st h a tt h e4 2s u b d i v i s i o na l s og e n e r a t e sc 1r e s u l t si ni r r e g u l a r c a s e s d a t as t o r a g eo ft h e4 2s u b d i v i s i o ni sm o r ec o m p a c tb e c a u s eo ft h ef a c t t h a ts u b s t i t u t i n gq u a d r i l a t e r a lm e s h e sf o r3 - 4m e s h e sc a nr e d u c ee 电e sb y i 1 a n d f a c e sb y ，a c c o r d i n g l y ，r u n n i n ge f f i c i e n c yi si m p r o v e db y 山en e ws c h e m e a n o t h e ra d v a n t a g eo ft h e 2s u b d i v i s i o ni st h a ti t sg e o m e t r i cr u l e sc a n n a m m u yg e n e r a l i z e dt oa r b i t r a r i l yp o l y g o n a lc o n l r o lm e s h e s 一 口i nt h es a m ew a y ，an e wi n t e r p o l a t o r ys u b d i v i s i o n ，n a m e da si n t e r p o l a t o r y4 2 s u b d i v i s i o n , i sp r e s e n t e db a s e do rt h e 2s p l i t t i n go p e r a t o r t h es c h e m ei st h e c o t m t e r p a r t i n q u a d r i l a t e r a ls c 牡i n g s o ft h e i n t e r p o a t o r y4 3 s u b d i v i s i o n 。 n u m e r i c a la n a l y s i si sa l s op e r f o r m e do nt h ec h a r a c t e r i s t i cm a p so fs u b d i v i s i o n m a t r i c e st os h o wt h ec 1c o n t i n u i t yo ft h es c h e m e w h e nt h ef a c en u m b e r s u b j e c t st og i v e ns i z e ，t h ei n t e r p o l a t o r y4 2 s c h e m ei sa b l et os u p p l i e sm o r e m u l t i r e s o l u t i o nl e v e l ss oa st oe n l l a n c et h e 【d de f 凫c t 口af i t t i n gs y s t e mi sd e v e l o p e dt ot i tt r i a n g u l a rm e s h e su s i n gt h el 0 叩s u r f a c e s w i t hs h a r pf e a t u r e s t h es y s t e mi sb a s e do nt h em e t h o dd e s c r i b e di n m ae ta 1 2 0 0 2 ，b u ti tr e i n f o r c e sa n dc o n s u m m a t et h eo r i g i n a la l g o r i t h mg r e a t l yi nt h e i m p l e m e n t a t i o nl e v e l t h ew h o l ef m x n e w o r ki n c l u d e ss h a r pf e a t u r ee x t r a c t i o n ， s i m p l i f i c a t i o n ，s m o o t h i n g ，t o p o l o g i c a lo p t h n i z a t i o n ，r e s a m p l i n ga n ds o l u t i o no f f i t t i n gs y s t e m s e x p e r i m e n t sn r a n i f e s tt h a tt h eq u a l i t yo fr e s u l t i n gs u r f a c e sh a s b e e ni n g n o v e dc o n s i d e r a b l y 口 c o n s i d e r i n gt h a tm o s to ft h ed i s c r e t ef a i r i n gm e t h o d sw e r ep r o p o s e dt od e n o i s e t r i a n g u l a rm e s h e sa n da r en o ts u i t a b l et op r o c e s sa r b i t r a r i l yp o l y g o n a lm e s h e s ， t h i sr e p o r td e s i g n sa s m o o t h i n ga l g o r i t h mt o f a i rt h e m t op r e v e n ts h r i n k a g e ，w e a s s u m et h a tt h ec e n t r o i d so fm e s hf a c e sa r en o i s e f r e eh e n c et h e s ep o i n t ss h o u l d b ei n t e r p o l a t e dw h i l es m o o t h i n g t h el a p l a c e l i k ei t e r a t i v ef o r m u l aj se s t a b l i s h e d l l s j l 】gm c 3s p l i r d n go p e r a t o rm a dw e i g h t so f t h ec a l m u l l - c l a r ks u b d i v i s i o n 第1 章细分曲面技术概述 细分方法最早可以追溯到1 9 5 0 年左右g d e r h a m 用以描述光滑曲线的角切 削思想1 9 7 4 年，g ，c h a i k i n 给出了基于这一思想的一个曲线生成方法一一 c h a i k i n 算法 c h a i k i n1 9 7 4 而e c a t m u l l 和j c l a r k 则于1 9 7 8 年由双三次b 样 条的递推性质导出任意拓扑网格上的细分曲面模式 c a t m u l la n dc l a r k1 9 7 8 1 同 时，d d o o 和m s a b i n 对双二次b 样条的作为细分曲面推广 d o oa n ds a b i n1 9 7 8 1 ； 此后，把参数曲面的造型技术移植到细分曲面，并最终把细分方法应用于c a d 领域成为人们追求的目标另一方面，由于三维扫描仪、c t 及m r i 等设备的出现， 使大规模三维数据的获取变得很容易例如，v i s i b l eh u m a n 计划已生成上百亿 体素的数据m i c h e l a n g e l o 计划l 巾的大卫雕像就有2 0 亿三角面片 l e v o y2 0 0 0 至于三维地形网格，其数据量更加惊人由此产生的二维流形数据由于无法表示 成规则参数域上的函数形式，因此难以应用现有的数字信号处理技术来处理这些 复杂数据寻找新的分析工具已成为数字几何处理( d g p ，d i g i t a g e o m e t r y d r o c e s s i n g ) 的重要研究内容幸运的是，对二维流形数据作重采样不难得到半 规则( s e m i - r e g u l a r ) 的网格模型而细分网格的半规则性质( 或细分连通性： s u b d i v i s i o nc o n n e c t i v i t y ) 及多分辨率结构使细分方法成为d g p 理论与算法的基 本构造单元( f u n d a m e n t a lb u i l d i n gb l o c k s ) s c h r 6 d e r2 0 0 2 ， 经过二l 多年的发展，细分模式的构造、细分曲面性质分析及其在多分辩率 表示中的应用等方面的研究都取得了长足的进步细分方法已经成为图形学的 一个标准造型技术不但被学术圈所理解同时也被_ t 业界所广泛接受例如，象 w a v e f r o n t ，m a y a , s o f l i m a g e 等一些著名的3 d 造型系统都加入了支持细分造型的 功能，有关细分方法较全面的回顾，可参看 z o r m & s c h r b d e r2 0 0 0 ，李2 0 0 1 ，张 2 0 0 2 ，张2 0 0 3 本章只简要阐述细分模式构造及细分曲面拟合的相关工作并介 绍一些基本概念，其中一些内容在 李2 0 0 1 中也有论述 1 1 基本概念 细分曲面( s u b d i v i s i o ns u r f a c e s ) ，也称子分曲面或剖分曲面利用一组拓扑 规则( t o p o l o g i cr u l e s 闻几何规m l j ( g e o m e t r i cd e s ) 对初始多边形网格进行细化，生 成更细密的新网格不断重复这一过程，得到一个网格序列泓。，m ，) 其极 限 m 。= l i r a m ， n “ 称为细分曲面其中，拓扑规则确定新网格的顶点插入力法及连接关系，而几何 规则则用以计算新网格顶点的位置拓扑规则和几何规则的集合称为细分模式 ( s u b d i v i s i o ns c h e m e ) 几何规则的图形表示称为模板( m a s k s ) 细分曲面的重要特 点是思想简洁、适用于任意拓扑网格且具有多分辨率结构， 1 1 1 有关网格的若干概念 这里，网格( m e s h e s ) 是指由顶点、边和面构成的整个或部分多面体表面本 文考虑的多面体表面都是二维流形的，也就是说，以表面上仃意一点为中心，都 存在半径足够小的球，使得它与表面的交与匮i 盘( d i s k ) 同胚如果一个网格有边 界边( 该边只属于一个网格面) ，称其为开网格，否则称为闭网格边界边的顶 点称为边界顶点，其余顶点称内部顶点如果所有网格面均为三角形，称其为三 角网格( t r i a n g u l a rm e s h e s ) ：类似地有四边形网格( q u a d r i l a t e r a lm e s h e s ) ；如果网 格面中包含有不同类型的多边形面，则称为任意多边形网格( a r b i t r a r i l yp o l y g o n a l m e s h e s ) 一个网格顶点的邻接边条数称为它的入度( v a l e n c e ) 对三角( 四边形) 网格， 入度为六( 四) 的顶点称为规则的( r e g u l w x 否则称为非规则或奇异的( h 唰班l a r e x t r a o r d i n a r y ) 如果三角( 四边形) 网格的所有内部顶点的入度都为六( 四) ， 则称该网格是规则网格，否则称为非规则网格如果一条网格边的两个端点都是 规则的，则称该边为规则边；一个网格面的所有顶点都是规则的，则称其为规则 面 考虑一个无限大的三角或四边形网格，除一个奇异顶点v 外其余均为规则顶 点以此顶点为中心由到此顶点的距离小于k 的所有网格面及其相应的顶点和边 组成的子网称为顶点的j 一邻域，记为帆( v ) 这坐个网格面到一个顶点的距离 是指该网格面1 1 所有顶点到该顶点的最短路径的最大边数 1 1 2 分裂算子 细分拓扑规则必须使得网格不断加密一般可以用网格的基本元素( 即顶点、 边和面) 的分裂操作米加以描述，阁此也称为分裂算子( s p l m i n go p e r a t o r s ) 待分 裂的网格称为旧闷格，所得的结果称为新网格在每个网格面中插入的新顶点称 为f 一顶点，在每条边中插入的新顶点则称为e _ 顶点，而新网格中与原来顶点对 应的顶点称为v 一顶点，下面介绍几个常用的分裂算子 细分方法中最常用的一大类分裂算子属于网格面分裂算子其中有一类算 子分别把旧网格边和旧网格面分裂为m 段( m 是整数) 和m 2 个新的网格面，称为 卜m2 分裂算子例如，细分方法模式中最常j j 的拓扑规则是1 4 分裂算子( 见图 1 1 a d ) 【c a t m u l l & c l a r k1 9 7 8 ，l o o p1 9 8 7 ，d y ne ta 1 1 9 9 0 ，k o b b e l t1 9 9 6 事实上， 迄今还没有出现摹于1 - m2 ( m 4 ) 分裂算予的细分模式 2 在三角网格巾有- - e 分裂，作两次后得到的结果与1 - 9 分裂等价亦即两次 细分之后，网格边被一分为三，| 夭】此称为拈蜀 k o b b e l t2 0 0 0 分裂在每个 三角形面中插入一个f 顶点，并与该三角形的三个顶点相连，共享一条边的两 个三角形对应的f 一顶点也相连，最后删除原米的边得到新网格( 见图1 1 e f ) 4 - 8 分裂则基于一种特殊的三角网格，称为3 - 4 网格( t r i - q u a dm e s h e s ) ，其三 角形面两两配成一对，每对都共享一条边，称为内边( i n t e r n a le d g e s ) ，其它边被 称为外边( e x t e r n a le d g e s ) 4 8 分裂算子在每条内边中插入个e 顶点，并与相 应的对角顶点相连，从而使两个三角形都被一分为二v d h o z o r i n2 0 0 0 ，对这 种分裂，其规则网格巾入度为4 和8 的顶点相问出现，其中与入度为4 的顶点相 邻的顶点入度都是8 ，而入度为8 的顶点与4 个入度为4 和4 个入度为8 的顶点 相邻，如图1 1 9 - h 如果把一个三角形对当作一个四边形面看，3 - 4 网格其实就是 四边形网格对于四边形网格，如果在每个四边形面中插入一个f 一顶点，并且每 条边形成个新的四边形面( 其项点由边的两个端点及共享该边的两个面的f 一 顶点构成) ，所得到的新网格也是四边形网格两次这样的分裂等价于次1 - 4 分裂，亦即两次分裂后所有网格边被分为二由于这。分裂与3 分裂有许多 相似之处，因此称之为2 分裂第3 、4 章两章将有详细讨论 基于面分裂的算子称为主分裂算子( p r i m a ls p l i t t i n go p e r a t o r s ) 这种分裂中旧 网格的顶点在新网格巾被保留下来而基于顶点分裂的算子则称为对偶分裂算子 辩鞲盛纛 薅潦羰桊 ( e )( d幢) 弗耩辩瓣 ( i )廿) ( k ) 图11 分裂算r 图例：( a ) 和( b ) 为四边形旧格1 - 4 分裂；( c ) 和( d ) 为三角例格l 一4 分裂；( e ) 和( f ) - - 角网 格的4 7 分裂；( 曲和( h ) 为3 - 4 刚_ f 的4 - 8 分裂；( i ) 十4 1 ( j ) 1 - 4 分裂的对偶分裂算r ；( k ) 和( 1 ) 是 分裂 的剐偶算r 中边分裂注意：图( b ) ，( d ) 和( h ) ，新叫格包含宴线和虚线而( d ，0 ) 和n ) 巾新刚格完个 山虚线构成 ( d u a ls p l i r i n go p e r a t o r s ) ，在新网格中旧网格的顶点被新网格面所代替相对应的 主分裂算子和对偶分裂算子生成的新网格互为对偶例如，与四边形网格的1 4 分裂对应的对偶分裂被用作d o o s a b i n 的模式拓扑规则( 见图1 1 ；i ) ；中边模式 ( m i d e d g es u b d i v i s i o n ) 中的分裂算子( 见图1 1 k ，1 ) 则是2 分裂的对偶3 分裂 也有相应的对偶算子，与该对偶算子相对应的正规网格为六边形网格 o s w a l d & s c h r 6 d e r2 0 0 2 张2 0 0 2 ， 1 1 3 细分模式分类 本节对已有的一些细分模式进行分类从前面关于细分方法的描述已经知 道，构成一个细分模式的几个要素为：初始网格、拓扑规则、几何规则，所谓的 分类无外乎根据这些要素来进行，因此可根据需要设计出各种分类方法，下面只 提几个本文涉及的方法 根据细分所生成的网格类型，可有三角细分模式、四边形细分模式、六边形 细分模式及多边形细分模式等在多边形模式中，有一种特殊的情形，细分网格 中只包含三角形和四边形，可称之为四边形三角形细分模式( q u a d t r i a n g l e s u b d i v i s i o n , 简称4 3 混合模式1 如果一个模式在不同的细分层采用相同的细分规则( 权值) ，则称其为静态 细分模式否则称为动态细分模式最近还出现半静态细分的提法，用来描述动 态细分中其细分权值在不同细分层以可以显式表示的规律变化的模式 张2 0 0 2 本文研究的细分模式都是静态的 表1 1 细分模式分类 璺i | 分模式 网格类型逼近储主，对分裂算连续阶 c a l r a u l l c l a r k c a t m u l l c l a r k1 9 7 8 四边形逼近主 1 4 c2 c d o o s a b i n d 。o s a b i n1 9 7 8 】两边彤为主的多近形逼近对偶i 4 对偶c l o o pi l o o p1 9 8 7 】三角形逼近主l - 4c 2 ，c 蝶形【d ”e ta l1 9 9 0 】三角形插值主1 4c i k o b b e l t 四边形【k o b b e l t1 9 9 6 】 四边形插值主1 4c 中边 p e t e r s r e i f1 9 9 7 】p q 边形为主的多边形逼近对偶暑。剥偶c k o b b e l t 压 k o b b e l t2 0 0 0 i三角形逼近主矗c l a b s i k l a b s i k g r e i n e r2 0 0 0 三角形 捕值主、店c o s w a l d 盯 o s w a l d s c h r 6 d e r 2 0 0 2 六垃彤逼近对偶 、医对羁c 4 8i v e l h o z o f i n2 0 0 1 】特殊的三角网格逼近主4 8 c c i s t a m 混合 s t a r e l o o p2 0 0 3 】 三角和四边彤混合逼近主l _ 4c 3 c i l o o p 三重缃分 l o o p2 0 0 3 】三角形逼近主 l - 9 c2 c 1 三重插值细分 d o d g s o ne ta l ，2 0 0 2 】 三角形 插值主 1 - 9 c 24 + 对 z o r i ne ta l1 9 9 6 1 d ? 的改进扳值，曲面在奇异顶点达到处一阶连续 “对规则阚格一阶光滑的 i f l ! 日仍术完善，而非规则情形尚未构造 4 堡l 壁垄堑丝蚕基垄窒丝垄堑堡套耋堡当星出煞蛰叁 根据所采用分裂算子的对偶性，还可把细分模式分成主细分模式和对偶细分 模式。在主细分模式中，如果日网格的顶点在新网格中的坐标保持不变则称为插 值细分( i n t e r p o l a t o r ys u b d i v i s i o n ) ，否则称为逼近细分( a p p r o x i m a t o r ys u b d i v i s i o n ) 1 1 列举了一些主要的静态细分模式的所属类别 1 2 细分模式构造技术 最常用也是最早提出的几个细分模式分别是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 9 7 8 、d o o - s a b i n d o o & s a b i n1 9 7 8 、l o o p l o o p1 9 8 7 和蝶形 d y ne ta 1 1 9 9 0 3 细分模式其中前三个模式均是逼近模式，分别是双三次均匀b 样条、双二次均 匀b 样条和二次三角箱样条的推广，因此规则情形下分别是c 2 、c 2 和c 1 连续的 而在奇异顶点处它们也都达到c 1 连续蝶形模式定义于三角网格，是最早的曲面 插值细分模式z o r i n 和s c h r 6 d e r 注意到蝶形细分曲面在奇异点处不光滑，并提出 了改进算法 z o r i ne ta 1 1 9 9 6 最早的四边形网格插值模式由k o b b e l t 于1 9 9 6 年 提出 k o b b e l t1 9 9 6 1 规则情形下该模式的模板由四点曲线插值细分作张量积牛 成最新的个插值模式则是l a b s i k 和g r e i n e r 的3 插值模式 l a b s i k g r e i n e r 2 0 0 0 1 值得注意的是，所有这些插值模式的模板均可由三次插值多项式计算得 到 最近几年，根据不同需要提出了很多新的模式本节根据其解决问题的目标 来对它们进行归类虽然这种归类不一定确切，不过我们可以方便地建立不同模 式间的一利，联系 l 2 , 1 基于多分辩率甚数的考虑 一些细分方法的网格面增长较慢，使得两个相继细分层之间的层数较多，从 而过渡也比较平滑另一些则增长较快，因而在最大网格面数吲定的限制下，不 同分辨率的层数相对较少，相邻层之问过渡会产生较明显的跳跃前期的细分模 式大都采用1 - 4 分裂算子，网格面每次增加3 倍试图增加多分辨层数的努力最 早要追溯到p e t e r s 和r e i f 的中边模式( m i d e d g es u b d i v i s i o n ) p e t e r s r e i f 1 9 9 7 1 ，生成的细分曲面是4 向箱样条的推广h a b b i b 和w a r r e n 也提出了相似的 算法 h a b b i b & w a r r e n1 9 9 9 1 。次边中点模式细分之后，新网格中新增的面数为 原网格面的顶点数，因此网格面数基本上是成倍增长k o b b e l t 则讨沧了一利r 基于 3 分裂的逼近细分，3 细分，其网格面每次增加2 倍 k o b b e l t2 0 0 0 与此同时， l a b s i k 和g r e i n e r 给出了相应的插值模式，即3 插值模式 l a b s i k & g r e i n e r2 0 0 0 在最大网格面数固定的情况下，v e l h o 和z o f i n 提出的4 8 模式可以提供更多的 分辩率层，因为其网格面每次只增长1 倍 v e l h o & z o r i n2 0 0 1 1 与此相反，有几个作者考虑了网格面增长更快的模式这里所谓的增长更快 是相对于基于1 - 4 分裂的方法而言在m a f l l o t 和s t a r e 的一个细分模式中，一饮 可以允许l - d2 分裂，就是说一个旧网格面会分裂成d 2 个新网格面 m a i l l o t & s t a m 2 0 0 i 另外两个例子分别是l o o p 的三重逼近细分( t e r n a r ya p p r o x i m a t o r y s u b d i v i s i o n ) 曲面f l o o p2 0 0 3 和d o d g s o n 等人的三重插值细分曲面 d o d g s o ne ta 1 2 0 0 2 前者是四次三角箱样条( 规则网格) 的三重细分到任意拓扑三角网格的推 广采用三重分裂算子的目的是为了构造一个具有如下性质的细分模式：曲率有 界、满足凸包性且具有2 邻域支撑( 即顶点影响范围不超过到它的拓扑距离等于 2 的顶点) 后者从一个c 2 连续的三重4 点插值模式 t t a s s a ne ta 1 2 0 0 2 出发，希 望构造一个定义在规则三角网格上c 2 连续的曲面插值模式此前提出的插值算 法即使对规则网格都达不到二阶光滑不过作者尚未把它推广到任意拓扑网格 情形，而且规则情形的c 2 连续性分析也需要进一步完善 1 。2 2 细分模式的统一s 整合 绝大多数的细分模式都是单独被提出来，所采用的方法五花 k f q ，不一而足 那么这些模式之间是否存在某种内在的联系? 能不能把它们统一到一个框架之 中? 这样做的好处是明显的如果答案肯定，就有可能为这些不同的模式设计统 一的数据结构和算法，从而在不增加系统复杂性的前提下提供多样性选择有趣 的是，有的工作不但把部分已知的细分模式统起来，还衍生出了一些新的模 式 这方面最出色的工作是类基于细分规则分解与合成的方法，其思想来源 于c o h e n 等人的b 样条曲线离散生成技术 c o h e ne ta 1 1 9 8 0 ，w a r r e n1 9 9 5 1 假设 有多边形顶点序列 ，v 0p ，v ：，吨，；，定义下述分裂与平均方法： 顶点分裂与复制：，v 0 ，h ，v 】，v l ，v 2 ，v 2 ，k ，唯， 线性样条( 第一次平均) ： 婚鼍生炜生孚岣，鼍玉 ， 二次样条( 第二次平均) ： 三次样条( 第三次平均) ： 兰二二鱼兰! ! 蔓兰堕堡 需要注意的是上述过程除顶点分裂外，其它操作都不生成新顶点，因此所有操作 组合起米得到一个细分模式其中平均操作可以不断进行下去以得到任意阶b 6 样条曲线的细分模式 z o r i n 和s c h r 6 d e r 利用这思想建立了主尉偶( p r i m a l d u a l ) 四边形细分模 式的统一框架 z o r i n 和s c h r 6 d e r2 0 0 13 在此基础上很容易给出d o o s a b i n 细分 和c a t m u l l - c l a r k 细分的变 l l ( v a r i a n t ) 形式这里之所以称为变种，是因为所导出 的奇异情形模板不同于原模式的模板此外，他们还给出了双四次样条推广到任 意四边形网格细分的具体权值 s t a r e 亦提出了类似的算法以推广任意阶张量积b 样条曲面 s t a m2 0 0 1 ，不 过在实现上有所不同而且，s t a m 进一步把算法移植到了三角网格，得到的细分 模式是总次数为3 m + l 的三角箱样条在任意拓扑三角网格上的推广，其中m = 1 为 l 0 0 p 模式值得提的是，对规则网格，沿两个参数方向先后使用两次上述b 样条细分模式( 得到张量积形式) 时，如果两次所采用的平均操作次数不同则可 以得到两个方向上次数不同的b 样条曲面，但文 s t a r e2 0 0 1 没有把这种情形推 广到非规则网格 如果说前面介绍的工作是经典b 样条曲面的推广，o s w a l d 和s c h r 6 d e r 关于 合成主) c 寸偶3 细分则建立在新近提出的细分模式之上他们对牛成b 样条的分 裂与平均方法进行了修改首先，把顶点的分裂与复制分成两步，第一步得到序 列：，2 v o ，0 ，2 h ，0 ，2 v 2 ，q ，2 咋0 ，第二步就是平均操作其次把平均算子分成 主平均算子v f ( v e r t e xt of a c e ) 和对偶平均算子f v ( f a c et ov e r t e x ) 两利l 类型在 此基础上抽象出摹元平均规贝0 ( e l e m e n t a r ye v e r a g i n gr u l e s ) 的概念，这里基元包括 顶点、边和面，极大地拓广了平均算子范畴通过对基元规则进行组合，可以得 到一系列新的算法，其中也包含k o b b e r