（计算数学专业论文）polygon+model上的fillet操作及算法.pdf

摘要 由于多面体细分算法提供了一个简单而有效的曲面生成方法，它已经成为在计算机 辅助几何设计( c a g d ) o ? 进行复杂曲面造型的一个基本工具。在第二章中，我们介绍了 几个常见的细分曲面。利用细分方法，曲面可以很容易的通过递归地细分多面体网格得 到，但是，在简单而粗糙的多面体网格上( 如日本正在研究的s k e t c h 平台中，用手画经 识别而生成的网格既简单又粗糙) ，很难得到设计者想要的形状。如何有效的控制最终 由细分方法生成的曲面成为摆在用细分方法进行曲面造型者前面的一个难题。 为了解决这一问题，我们提出了一种行之有效的方法：f i l l e t 操作，并且给出了相应 的f i l l e t 规则及算法。f i l l e t 操作及算法主要思想是：首先运用f i l l e t 操作及规则生成一 个复杂而精细的多面体网格，然后再对这个精细的网格进行细分，就可以得到设计者想 要的形状。一般地，对初始网格来说，相交于一个顶点的边数并没有限制，而且，每条 边的f i l l e t 值可以不同。 在我们提出的f i l l e t 规则中，角点协调算法保证了曲面在执行f i l l e t 操作的边上的几 何特征，并且保证了最终生成的网格是一个标准的p o l y g o n m o d e l 。f i l l e t 的概念、规则 及角点协调算法在第三章中详细讲解。为了方便设计者执行f i l l e t 操作，我们还在第四 章中给出了细分曲面上的自适应和交互f i l l e t 操作的思想及算法。 我们提出的f i l l e t 操作及算法将有助于加强用细分方法进行曲面造型的计算机图形 系统( 如在日本的s k e t c h 系统上得到了很好的运用) 。 关键词：细分曲面，l o o p 曲面，f i l l e t 操作及算法 a b s t r a c t a sp o l y h e d r a ls u b d i v i s i o n p r o c e s sp r o v i d e s a s i m p l e a n de f f i c i e n t w a yt og e n e r a t e s u r f a c e so v e rp o l y h e d r a ln e t w o r k s ，i th a sb e c o m eo n eo ft h eb a s i ct o o l si nc 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 ) f o rm o d e l i n gc o m p l e xs u r f a c e s i nc h a p t e r2 ，w ei n t r o d u c es o m e f a m o u ss u b d i v i s i o ns u r f a c e s s u r f a c e sc a nb eg e n e r a t e de a s i l yb ys u b d i v i d i n gp o l y h e d r a l n e t w o r k sr e c u r s i v e l y , h o w e v e r , o v e rs i m p l eo rr o u g hp o l y h e d r a ln e t w o r k ，i ti sd i f f i c u l tt og e t t h es u r f a c e sw h i c hd e s i g n e r sw a n tt o m o d e l ( f o re x a m p l e ，i nt h e s k e t c h s y s t e mb e i n g r e s e a r c h e di nj a p a n ，t h en e t w o r k sg e n e r a t e db yh a n da r em u c hs i m p l ea n dr o u g h ) s o ，t ot h e d e s i g n e r sw h o u s es u b d i v i s i o ns u r f a c e st om o d e ls u r f a c e s ，t h e r ei sad i f f i c u l tq u e s t i o nt h a t h o wt oe f f i c i e n t l yc o n t r o lt h ef i n a ls h a p eg e n e r a t e db ys u b d i v i s i o ns u r f a c e s i no r d e rt os o l v et h i sq u e s t i o n ，w ep r o v i d ea s i m p l ea n de f f i c i e n tw a y ：f i l l e to p e r a t i o n sa s w e l la st h ef i l l e tr u l e sa n da l g o r i t h m t h em a i ni d e ao ff i l l e to p e r a t i o ni st oc r e a t eac o m p l e x o rp r e c i s ep o l y h e d r a ln e t w o r k b y f i l l e to p e r a t i o na n d a l g o r i t h m b yi m p l e m e n t i n gs u b d i v i s i o n o v e rt h ep r e c i s en e t w o r k s ，w ec a ng e tt h es h a p ew h i c h t h ed e s i g n e r sw a n tt om o d e l g e n e r a l l y 血en u m b e ro f e d g e st h a tm e e t a to n ev e r t e xi sn or e s t r i c t i o na n dt h es h a r p n e s so fe v e r ye d g e c a l lb ed i f f e r e n t i nt h er u l e so ff i l l e t o p e r a t i o n ，t h ec o m e rf i t t i n ga l g o r i t h me n s u r e st h a t t h eg e o m e t r i c f e a t u r eo ft h ee d g e sc a nb em a i n t a i n e da f t e ri m p l e m e n t i n gf i l l e to p e r a t i o n ，a n de n s u r e st h a t t h en e t w o r kg e n e r a t e db yf i l l e to p e r a t i o ni sas t a n d a r dp o l y g o nm o d e l w e w i l ld i s c u s st h e f i l l e tc o n c e p t ，r u l e sa n dc o m e r f i t t i n ga l g o r i t h mi nc h a p t e r 3c l e a r l y i no r d e rt om a k ei te a s y f o rt h ed e s i g n e r st oi m p l e m e n tf i l l e to p e r a t i o n ，w ea l s op r o v i d ea na d a p t i v ea l g o r i t h ma n d a l l i n t e r a c t i v eo p e r a t i o no fi m p l e m e n t i n gf i l l e to p e r a t i o n si nc h a p t e r 4 t h ef i l l e to p e r a t i o n sp r o p o s e dh e r ew i l ls t r e n g t h e nt h ef u n c t i o n so fc o m p u t e rg r a p h i c s s v s t e mt h a tb s es u b d i v i s i o ns u r f a c e st om o d e ls u r f a c e s ( f o re x a m p l e ，i tw o r k sw e l li nt h e s k e t c h s y s t e m i nj a p a n ) k e y w o r d s ：s u b d i v i s i o ns u r f a c e ，l o o p s u r f a c e ，f i l l e to p e r a t i o na n da l g o r i t h m i i p o l y g o nm o d e l 上的f i l l e t 操作及算法 1 引言 本章前两节简要介绍细分方法的研究背景及发展阶段，后两节介绍本文的研究目的 以及贡献。 1 1 研究背景 在c a d c g 中，曲面造型是一个有着较长历史的领域，6 0 年代初期就已经诞生。 1 9 6 3 年f u g e r s o n 提出将曲线曲面表示为参数向量函数形式，在此之前曲线曲面都是采 用普通的函数表示形式y = f ( x ) 和z = f ( x ，y ) 或它们的隐式方程表示形式。1 9 6 4 年， c o o n s 发表了一种由四条边界曲线确定的参数曲面即c o o n s 曲面片，从而使分片表示完 整曲面成为可能。b 6 z i e r 于1 9 7 1 年发表的由控制多边形定义曲线的方法，则可以很方 便地控制曲线的形状，但曲线上任一点都与多边形的所有顶点相关，因此对控制多边形 的任何修改都会影响到曲线的整体形状。7 0 年代初d eb o o r ，g o r d o n 和r i e s e n f e l d 等人 发展了b 样条曲线曲面的理论和算法，保留了b 6 z i e r 曲线的大部分优点。另一方面， 由于是分段多项式，因此允许局部控制。但是上述各种方法不能表示圆锥截线和球面椭 球面等初等解析曲面，为此v e r s p r i l l e 于1 9 7 5 年提出有理b 样条方法。最后在p i g e l 和 t i l l e r 等人的努力下，终于在8 0 年代后期发展起来非均匀有理b 样条( n u r b s ) 的一整套 方法，把有理和非有理b 6 z i e r 曲线和b 样条曲线曲面及圆锥曲线和初等解析曲面统一 在一种表示之中，最终使n u r b s 成为c a d c a m 行业的工业标准【旌法中1 9 9 4 ，f a d n 1 9 9 7 ，朱心雄2 0 0 0 】。 上述各种曲面都是定义在矩形参数域上，是矩形曲面片，无法有效地表示任意拓扑 形状的曲面。通常采用逐片构造方法表示复杂物体表面，这时候需要对曲面片进行剪裁 ( t r i m m i n g ) 或直接在非规则的四边形网格上构造曲面片，无论哪种情况都要考虑片与片 之间的光滑连接。尽管也有三角形域上的b 6 z i e r 曲面 f a r i n1 9 8 6 】，但表示复杂物体时 同样需要需要拼接。这是一个相当困难的工作。 细分睦面( s u b d i v i s i o ns u r f a c e s ) 是一个网格序列的极限，网格序列则是通过采用一组 规则( 一般是加权平均) 在给定初始网格中插入新顶点并不断重复此过程而获得。这种方 法克服了参数曲面处理任意拓扑网格( a r b i t r a r yt o p o l o g ym e s h e s ) 存在的困难。因为，在 不规则拓扑处只须采用特殊的细分规则就可以了，不存在拼接的问题。 另一方面，由于三维扫描仪( 3 ds c a n n e r ) 、测距仪( r a n g ef l n d e r ) 和c t 等三维数据获 取设备的日益完善，为几何形状不能或难于用分析曲面表示的对象建模提供了有力的工 具，例如医学的人体器官建模 l o r e n s e n1 9 8 7 、考古学中的古代器件和艺术领域的雕塑 作品三维重构 l e v o y2 0 0 0 等等离散曲面逐渐成为一种重要的几何表示方法细分模 式作为从给定规则产生离散曲面的方法统一了传统的参数曲面与多边形两种实体表面 的表示另外，由于实验获取的三维数据量一般都非常大，多分辨率分析( m u l t i r e s o l u t i o n p o l y g o nm o d e l 上的f i l t e t 操作及算法 a n a l y s i s ) 成为有效地处理这类数据的重要手段细分方法与多分辨率分析、小波变换 ( w a v e l e t t r a n s f o r r n a t i o n ) 之间的深刻联系也是目前细分模式受到关注的个重要原因。 由于多面体细分算法提供了一个简单而有效的曲面生成方法，它已经成为在计算机 辅助几何设计( c a g d ) 中进行复杂曲面造型的一个基本工具。最早的两个基本细分曲面 是由c a t m u l i ，c l a r k 和d o o - s a b i n 在1 9 7 8 提出的。n a s r i 扩展了d o o s a b i n 细分方法以便 在原始多面体网格上进行顶点插值以及在细分曲面上进行b 样条曲线的插值操作。 n d y ne ta 1 提出了b u t t e r y 插值细分曲面，z o f i ne ta l 。扩展了b u t t e r y 方法，f a r i n 和l o o p 讨论了一个基于箱样条的细分算法。m h a l s t e a de ta 1 提出了一个基于c a t r n u l l c l a r k 的插 值细分方法。s e d e r b e r g e ta 1 提出了非均匀细分曲面。最近，c ga n i m a t i o ns t u d i o s 的成 功运用表明了细分曲面将在曲面造型中起着重大的作用。 i 2 细分曲面发展阶段 细分方法可以追溯到5 0 年代gr h a m 的通过对折线角点进俐( c o r n e rc u t ) 来生成 光滑曲线的思想7 0 年代中期，c h a i k i n 生成曲线的细分方法 c h a i k i n ，1 9 7 4 1 正是这种角 切割思想的具体实现。稍后c a t m u l l 和c l a r k 提出了著名的c a t m u l l c l a r k 细分模式 f c a t m u l l1 9 7 8 ，标志着细分方法正式成为曲面建模的手段。当矩形网格没有奇异顶点( 共 享顶点的边数，称为顶点的价。对于四边形网格，价不等于4 的顶点称为奇异顶点) 时， c a t m u l l c l a r k 模式生成三次b 样条曲面；对于有奇异顶点的网格，生成的曲面除有限 个点外，具有二阶光滑，可以说是一张“几乎处处”的三次b 样条曲面。与此同时， d o o 和s a b i n 采用离散f o u r i e r 变换的方法，对c a t m u l l c l a r k 模式的收敛性进行了分析， 开创了细分模式收敛性矩阵特征分析的先河。大致可以把细分方法的发展历史分成如下 三个阶段： 7 0 年代后期c a t m u l l c l a r k 细分模式以及d o o s a b i n 关于奇异点处行为的分析理论标 志着细分方法正式成为曲线曲面造型的一种手段。 8 0 年代末到9 0 年代初的形成期在这一阶段，提出了很多著名的细分方法，对旧方 法也有许多改进以适应不同要求规则情形的收敛性和连续分析理论也逐渐完善，例如 给出了单变元细分模式任意阶光滑的充要条件 c a v a r e t t a1 9 9 1 ，m i e c h e l l i1 9 9 3 1 不过，各 种模式之间仍然缺乏联系，一般情形的收敛性分析方法也是“随身定作”，缺乏一般的 理论指导。 9 0 年代中期到现在的发展期这一时期开始建立系统的收敛性理论，提出了多变元 模式任意拓扑情形下收敛性分析的理论框架 w a r r e n1 9 9 5 ，r e i f1 9 9 5 ，z o r i n1 9 9 8 1 这些 理论反过来指导细分模式的构造，尤其是二阶以上连续曲面的构造此外，各种细分模 式的内在联系也逐渐被揭示出来，例如z o f i n 和s c h r o d e r 为主( p r i m a l ) 四边形网格细分 模式和对偶( d u a l l 四边形网格细分模式建立了统一的框架 z o r i n2 0 0 0 a 】更为重要的是， 在这一时期，细分方法得到了广泛应用，尤其是复杂网格曲面的多分辨率分析的研究取 得了大量成果。 p o l y g o nm o d e l 上的f i l l e t 操作及算法 1 3 研究目的 利用细分方法，曲面可以很容易的通过递归地细分多面体网格得到，但是，在简单 而粗糙的多面体网格上，很难得到设计者想要的形状。如日本正在研究的s k e t c h 系统， s k e t c h 的研究目的是想建立人手描绘与计算机造型之间的一个桥梁，并结合笔与纸的特 征以及c a d 系统的特点提供一个近似造型系统。简单的说是就是想通过人手画出的2 d 图形生成一个3 d 图形，s k e t c h 的研究手段很多，比如利用三维透视、阴影、光照、笔 压等来识别生成三维图形。日本的东京大学、琦玉大学以及i b m 日本研究所等在这方 面做了很多研究工作并取得了许多研究成果。图1 1 是日本琦玉大学近滕研究室研究的 阴影s k e t c h 系统。 图1 1 阴影s k e t c h 系统( 日本琦玉大学近滕研究室) f i g u r e1 1s h a d i n gs k e t c hs y s t e m ( k o n d ol a b s a i t a m au n i v e r s i t y , j a p a n ) s k e t c h 系统采用细分方法来生成光滑曲面，但是由s k e t c h 系统识别生成的网格比较 粗糙，直接对初始网格进行细分，很难得到设计者想要的形状。因此，如何有效的控制 由细分方法生成的曲面形状成为摆在用细分方法进行曲面造型者前面的一个难题。 为了解决这一问题，必须定义复杂丽精确的多面体网格。例如，要用细分方法得到 一个立方体形状( 图1 2 ( d ) ) ，我们必须定义一个新的多面体网格( 图i 2 ( c ) ) ，而不能直接 细分一个简单的立方体网格( 图1 2 ( a ) ) 。根据不同的细分方法( 如l o o p 等) ，特定的多面 体网格必须被定义，显然，有效的定义将是一件困难的事情。 ( a )( b ) ( c )( d ) 图1 2 ：细分曲面( a ) 初始网格( b ) 对1 2 ( a ) 细分两次后的形状( c ) 修改后的网格( d ) 对修 改后的网格1 2 ( c 、细分两次后的形状 f i g u r e1 2 ：s u b d i v i s i o ns t l r f a c e ( a ) t h eo r i g i n a lp o l y h e d r o n ( b ) t b e2 “s u b d i v i s i o ns u r f a c e o v e r1 2 f a ) ( c ) t b em o d i f i e dp o l y h e d r o n ( d ) t h e2 ”l o o ps u b d i v i s i o ns u r f a c eo v e r12 ( c ) ! ! 垒婴! 坚! ! 型主竺! ! ! ! 璺堡堡墨墨堡 1 4 本文的贡献 在1 9 9 8 年，d e r o s ee ta 1 修改了c a t m u l l c l a r k 细分方法用来在他们的动画系统中执 行切分操作：他们称之为混合细分方法。混合细分方法通过无限的尖锐规则在最初的阶 段细分几次可以得到半尖锐的折痕，然后在以后的细分过程中利用光滑算法生成曲面。 然而，该方法存在一些问题： ( 1 ) d e r o s e 提出的方法只能用于c a l m u l l c l a r k 细分曲面。对于其它的细分方法( 如三 角网格上的l o o p 细分曲面) ，还需要进行某些研究并修改。 ( 2 ) 细分步骤的次数及多面体网格的个数也是一个问题。一般地，在用细分方法生 成曲面时，我们只对初始多面体网格细分几次，因为通过几次细分，曲面已经足够光滑 来给出一个好的形状，即使真正的光滑曲面在理论上需要无限次细分才能得到。另外一 个问题是网格的个数在每一步细分过程中都增长的很快。 在1 9 9 9 年，x u 提出了d o o s a b i n 曲面上的切分方法。但却不适合用于l o o p 细分方 法，对于l o o p 等细分方法，也需要进行研究并修改。并且，该方法没有给出一个自动 执行切分操作的算法以及交互算法。 根据以上的问题，在这篇文章中，基于l o o p 细分曲面，我们提出了一套f i l l e t 算法 规则及交互操作来解决这一问题。算法主要是围绕两个三角形的交线进行的，多面体网 格的每条边被赋予一个称作f i l l e t 值的参数，该参数刻画了交线的尖锐程度，当然也可 由用户交互指定并修改该参数，然后，根据每一条边的f i l l e t 值，用文章中提出的规则 对最初的多面体网格进行一次细分操作以生成特定的多面体网格，最后用细分方法来生 成连续曲面。并且在我们提出的方法中： ( 1 ) 我们只是生成一个新的多面体网格。对这个新的包含f i l l e t 信息的多面体网格进 行细分就可以得到设计者想要的形状。 ( 2 ) 初始网格的每一条边赋予一个称作f i l l e t 值的参数。用户可以很容易地修改该参 数来控制最终的形状，f i l l e t 值刻画了边的尖锐程度，决定了最终生成的曲面在这条边 附近的局部形状，f i l l e t 值越小，则生成的曲面在这条边附近越尖锐。 ( 3 ) 初始的多面体网格利用我们提出的规则只需细分一次，因而对网格的数目及细 分的次数没有较大的影响。利用细分方法进行曲面造型时，网格的数目随着细分次数的 增加而增长很快，而我们提出的f i l l e t 操作只需对初始网格执行一次f i l l e t 操作，因而 对生成的网格数目的增长来说影响不大。 ( 4 ) 我们给出了一个自适应算法及交互操作规则。通过自适应算法及交互操作，用 户可以方便地利用f i l l e t 操作进行曲面造型。 p o l y g o nm o d e l 上的f i l l e t 操作及算法 2 细分曲面 本章介绍细分曲面的特点、类型以及一些典型的细分曲面，包括c a t m u l l c l a r k 模式、 l o o p 模式、蝶形模式、d o o s a b i n 模式等，此外，也介绍了这方面一些最新的成果。 2 1 细分曲面特点 细分曲面的研究已经有2 0 年的历史。最早的两个细分曲面是由c a t m u l l 和c l a r k 以 及d o o 和s a b i n 在1 9 7 8 年给出的，到目前已经有许多著名的细分曲面( l o o p ，b u t t e r f l y ， m o d i f i e d b u t t e r f l y ，k o b b e l t ，m i d e d g e ) 。从1 9 7 8 年到1 9 9 5 年，尽管出现了一些新的细 分曲面，但是一个基本的关于细分衄面在非正常点处的光滑性问题却没有解决。 r e i f r e i f 9 5 于1 9 9 5 年给出了一个较满意的回答，最近几年对细分曲面的光滑性分析取 得了较为明确的结果。 细分曲面有许多很好的特性： ( 1 ) 任意拓扑结构( a r b i t r a r yt o p o l o g y ) 传统曲面造型方法遇到复杂物体造型时往往束手无策，因为其控制顶点往往具有复 杂的网格拓扑，这对于利用张量积方法构造的参数曲面而言，拼接或剪裁( t r i m m i n g ) 的困难是显而易见的。但是细分方法不存在这样的问题，部分原因是它的参数空间是初 始网格本身。细分曲面可以从任意网格上生成，这意味着不需要剪裁过程以及保持曲面 片之间的光滑性处理过程。 ( 2 ) 可伸缩性( s c a l a b i l i t y o rl e v e lo f d e t a i l ) 由于细分曲面递归生成，是一个不断细化的过程，其多分辨率分析有坚实的数学基 础，特别适合于层次细节( l o d ) 技术，从而可充分利用有限的硬件资源。根据需要， 细分曲面可在不同细节程度上生成，因此，曲面可实现在不同细节程度上的描写以及在 一定的误差范围内的自适应近似处理。 ( 3 ) 数值稳定。 生( n u m e r i c a ls t a b i l i t y ) 由细分生成的网格有许多好的性质。线性细分方法是一个迭代过程，有很好的数值 稳定性，可用于有限元方法，细分曲面可生成c 1 光滑曲面，可以满足许多数字模拟任 务，如动画系统或系统计算。 ( 4 ) 算法简单( p r o c e s ss i m p l i c i t y ) 易于实现，效率也很高 ( 5 1 表示一致1 生( u n i f o r m i t yo f r e p r e s e m a t i o n ) 这里所说的一致性是指细分法把曲面片与多面体表示统一起来，使得造型系统有了 统处理曲面和多面体表示的手段。并且编辑操作既简单又自由。用户可以任意改变网 格的结构而不用担心保持曲面光滑的条件。 ! ! 生g ! ! 坚! ! 型：! 塑! ! 坚堡堡丝竺鲨 2 2 细分曲面概述 从1 9 7 8 年到1 9 9 8 年，出现了许多细分方法。著名的细分方法有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 ( m o d i f i e db u t t e r f l y ) ，k o b b e l t ，m i d e d g e 。细分曲面发展 历史见表2 1 ，对一个细分方法来说： ( 1 ) 有效性：在计算新顶点的过程中使用尽可能少的浮点运算。 ( 2 ) 局部定义：新的顶点的产生只依赖相邻的一个小的局部范围内的点。 ( 3 ) 仿射不变性：如果初始网格做一变换之石，生成的曲面也应该经历同样的变换。 ( 4 ) 简单性：细分规则应该用少量的算法规则。 ( 5 ) 光滑性：曲面应该能够取得某种光滑性( g 1 ，c 1 ，c 2 ) 。 盆 作者及细分方法 1 9 7 4 c h a i k i n c h a i k i n 7 4 1 a a l g o r i t h mo fg e n e r a t i n gq u a d r m i cb s p l i n ec u r v e 1 9 7 8c a t m u l la n dc l a r k c a t m u l l 7 8 1 ab i c u b eb s p l i n es u r f a c e s ，c a t m u l l c l a r ks c h e m e d o oa n d s a b i n d o o 7 8 1 a b i q u a d r a t i cb s p l i n es u r f a c e ，d o o s a b i ns c h e m e 1 9 8 6t a na n dc h a n t a n 8 6 1 - h i g ho r d e rs u b d i v i s i o ns u r f a c e s 1 9 8 7 n 珊s r i n a s r i 8 7 1 i n t e r p o l m i o np o i n t si nd o o s a b i ns c h e m e _ l o o p l o o p 8 7 】 l o o ps c h e m e b a s e do nt r i a n g u l a rm e s h 1 9 8 8b a l la n ds t o r r y f b a l l 8 8 a n a l y s i s c o n d i t i o n sf o r t a n g e n tp l a n ec o n t i n u i t y o v e rs u b d i v i s i o n s u r f a c e s 1 9 9 0 d y n ，l e v i na n dg r e g o r y d y n 9 0 b u t t e r ys c h e m e ，b a s e d o n t r i a n g u l a rm e s h ，i n t e r p o l a t i o n 1 9 9 3 h a l s t e a d ，k a s sa n dd e r o s e h a l s t e a d 9 3 1 rf a i ri n t e r p o l a t i o nw i t hc a t m u l l 一c l a r ks c h e m e 1 9 9 4 h o p p e e ta 1 h o p p e 9 4 】 i n t r o d u c i n gm a s k d en i t i o n ，s h a r p ，c r e a s ee d g e st ol o o ps c h e m e 1 9 9 5 r e i f r e i f 9 5 1 as e r i o u sa n a l y s i so nt h es m o o t h n e s s p r o p e r t i e so f s u b d i v i s i o ns u r f a c e s 1 9 9 6z o r i na n ds c h r o d e r z o r i n 9 6 i n t e r p o l a t i o nb u t 【e r ys u b d i v i s i o ns u r f a c e s k o b b e l t k o b b e l t 9 6 1 rk o b b e l ti n t e r p o l a t i o nq u a d r i l a t e r a ls c h e m e 1 9 9 7 n a s r i 【n a s r i 9 7 1 】， n a s r i 9 7 2 c u r v ei n t e r p o l a t i o ni nd o o - s a b i ns u r f a c e s -p e t e r sa n dr e i f p e t e r s 9 7 一l1 p o l y g o nm o d e l 上的f i l l e t 操作及算法 b o x s p l i n e ( m i d e d g e ) s u b d i v i s i o n s u r f a c e s 1 9 9 8d e r o s ea n dk a s s d e r o s e 9 8 1 -s u b d i v i s i o ns u r f a c e si nc h a r a c t e ra n i m a t i o n f m o d ie dc a t m u l l - c l a r ks c h e m e ) s e d e r b e r g e ta 1 【s e d e r b e r g 9 8 n o n ，u n i f o r i l lr e c u r s i v es u b d i v i s i o ns u r f a c e s ( d o o s a b i na n dc a t m u l l c l a r k ) 表2 ，1 ：细分曲面发展历史 一 t a b l e2 1 ：t h ed e v e l o p m e n th i s t o r yo fs u b d i v i s i o ns u r f a c e s 细分方法基于不同的多面体网格并且采用不同的细分规则。z o r i n c o u r s e 3 6 根据三个不 同的标准把细分方法进行了分类： ( 1 ) 根据细分规则( 顶点插入或角切割) 。 ( 2 ) 根据生成的网格( 三角网格或四边形网格) 。 ( 3 ) 根据细分方案是插值或是逼近。 分类结果见下表： t a b l e2 2 ：t h ec l a s s i f 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 ( 1 ) 网格类型 三角形和四边形网格是在实际应用中常用的两种多面体网格。这导致了两类不同的 细分方法，在这些细分方法中，所生成网格仍然是三角形和四边形网格a f 2 1 顶点插入或角切割 生成曲面共有两种主要的方法：顶点插入和角切割。前一种方法中，三角形网格或 四边形网格的每一条边被分割成两部分，并且旧的网格顶点被保留下来。这里旧的网格 顶点设保留有两个意思：一是旧网格顶点位置保持不变，二是旧的网格顶点的位置被重 新计算。 ( 3 ) 逼近和插值 顶点插入方法可以用逼近或插值：如果旧的顶点的位置没有改变，则顶点插入方法 被称作插值方法，如果旧的顶点的位置被重新计算，则我们说这种方法是一种逼近方法。 插值是一种具有吸引力的方法，但是，生成的曲面的质量不如用逼近方法生成的曲面， 并且收敛到极限曲面的速度不如逼近方法。 p o l y g o nm o d e l 上的f i l l e t 操作及算法 2 3c h a i k i n 算法 细分曲面的基本思想可追溯到c h a i k i n 的算法，该算法通过削角可从一个多边形生 成一个二次b 样条曲线。每次细分在多边形的每一条边上都生成两个新的顶点。参考 图2 1 ，对一个有n 个顶点( v i ) 闻。的多边形来说，在边( v 。，v 。+ 。) 上，这两个新的顶点可 由下面的算法给出： v ：= 三v ，+ 三v t v ：+ l 。一1 444v 。+ 三4 ”m ( 2 1 ) l 新的多边形由连接新生成的顶点v ：，v ：而成，图2 1 例示了两次细分后的结果。 r i e s e n f e l d 【r i e s e n f e l d 7 5 】证明了由上述算法生成的曲线是一条二次b 样条曲线。 图2 1 ：c h a i k i n 算法空心圆点为初始顶点，实心圆点为细分一次后生成的顶点， 实心方点为细分两次后生成的顶点 f i g u r e2 1 ：c h a i k i n sa l g o r i t h m h o l l o wc i r c l en o d e sa r eo r i g i n a lv e r t i c e s ，w h i l es o l i d c i r c l en o d e sa r et h ev e r t i c e sa r e rl “s u b d i v i s i o n ，s o l i ds q u a r en o d e sa r et h e2 ” s u b d i v i s i o nv e r t i c e s 2 4c a t m u l l c l a r k 细分曲面 c a t m u l l c l a r k 模式是u t a h 大学的c a t m u l l 和c l a r k 于1 9 7 8 年提 c a t m u l l1 9 7 8 】a 这 是最早的曲面模式。其实c a t m u l l 用这种思想生成曲面的时间更早些 c a t m u l l1 9 7 4 ，但 当时还缺乏严格的理论支持。后来d o o 和s a b i n 利用矩阵f o u r i e r 分析的技术对c a t m u l l c l a r k 的收敛性进行分析 d o o1 9 7 8 1 ，标志l 着细分方法的开始成为曲面造型的一种工 具。基于四边形网格的细分方法研究中，很多工作是在c a t m u l l - - c l a r k 模式上展开的 h a l s t e a d1 9 9 3 ，d e r o s e1 9 9 8 ，b i e r m a n n2 0 0 0 1 2 4 1 细分规则 c a t m u l l c l a r k 模式的初始控制网格为四边形网，采用1 - 4 四边形分裂算子生成新网 格的拓扑，计算新顶点的几何规则如下： ( 1 ) f 顶点：设面的四个顶点为v 0 , v 1 ，v 2 , v 3 ，则相应的f - 顶点的位置取为 v f = ( v o + v l + v 2 + v 3 ) 4 ( 2 2 ) ( 2 ) e 顶点：设内部边的端点为v o ，v 1 ，共享此边的两个四边形面分别为 ( v o ，v 1 ，、r2 ，v3 ) 和( v o ，v 1 ，v4 ，v5 ) ，那么与此内部边相对应的e - 顶点为 p o l y g o nm o d e l 上的f i l l e t 操作及算法 v = ( v o + v 1 ) + 去( v 2 + v 3 + v 4 + v 5 ) ( 2 3 ) ( 3 ) u 顶点：若内部顶点, q - 的1 - 环的边界顶点依次为v 0 , v l ，v 2 ，l ，其中”= ivi e 偶数下标的顶点为邻点，奇数下标的顶点为其四边形上的对角顶点，相应的v 顶点为 v ，弧v + 冬篁v ：，+ 鲁篁v ：川 b a ， ni = 0 挖i = 0 c a t m u l l 和c l a r k 取其中的权值为。= 3 ( 2 n ) ，y 。= 1 ( 4 n ) ，d 。= 1 一声。一心 ( 4 ) 边界边( v o ，v 1 ) 上的e 一顶点 v e = 吉( v o + v 1 ) ； ( 5 ) 边界顶点v 在边界上的两个相邻顶点为v 0 , v i ，则v 的v - 顶点为 i 1 6 1 4 3 f b 1 4 l 1 6 v 矿= ( v o + v 1 ) + v 日 j ，1 6 3 8 l 九6 ，彳 么 p _ _ | 1 2 1 2 ( d ) 边界e 一项 卜叫 1 8 3 4 1 8 ( a ) f 顶点( b ) e 一顶点( c ) v 一顶点( e ) 边界v 一顶点 ( f ) ( g ) ( h ) 图2 2 ：c a t m u l l c l a r k 模式的面具及细分过程( f ) 为带边界的初始网格乜) 为一次细分 的结果( h ) 为多次细分后的真实感图 f i g u r e2 2 ：c a t m u l l - c l a r ks u b d i v i s i o nm a s k sa n dp r o c e s s ( f ) o r i g i n a lp o l y h e d r o n ( g ) t h e 1 “s u b d i v i s i o np o l y h e d r o n ( h ) t h es h a p eg e n e r a t e da f t e rs e v e r a ls u b d i v i s i o ns t e p s ( 2 5 ) ( 2 6 ) 式( 2 2 ) 一( 2 6 ) 由f c a t m u l l1 9 7 8 】中的规则约化得到，初始控制网格为任意多边形网格 时，可利用 c a t m u l l1 9 7 8 】中规则作一次细分得到四边形网格，然后再用规则( 1 ) - ( 5 ) 作余 下的细分。式( 2 2 ) ( 2 6 ) 中顶点的权值可分别由图2 2 a e 的面具m a s k s ) 表示。图2 2 f - h 给出一张c a t m u l l c l a r k 曲面的例子，不过本例中在边界上除采用边界细分规则外还引 进了角点规则( 该点在细分过程中保持不变) 。c a t m u l l c l a r k 模式的一个重要推广是 s e d e r b e r g ，郑建民和s w e l l 等的n u r s s s e d e r b e r g1 9 9 8 。 口 2 4 2 权值选取 当初始网格为规则网格时，c a t m u l l - c l a r k