（应用数学专业论文）卷积曲面造型.pdf

浙江人学坝i j 学位论义摘爱 摘要 卷积曲面造型是计算机图形学中广泛使用的一种隐式曲面造型方法。卷积曲 面实质上是骨架通过卷积方式所定义生成的标量场的一个等值面。虽然卷积曲面 在模拟自然现象和拓扑结构复杂、易变物体时具有很大的优势，但能否解析表达 骨架的势函数，始终是我们面对的一个难题。 奉文解析给出点，直线段，圆弧，二次曲线和三角面片等骨架的势函数，并 且提出一种快速的光线跟踪绘制卷积曲面算法。 本文内容和整体架构如下 在第一章中，主要介绍卷积曲面的背景知识及其应用领域，分析前人工作以 及叙述本文主要研究工作和内容。 在第二章中，我们采用截断多项式函数为核函数，解析的给出点、直线段、 圆弧、二次瞎线和三角面片等骨架的势函数。特别是首次解析表达出具有局 部支撑核函数下的三角面片骨架势函数，为采用大量的三角面片作为卷积曲 面骨架奠定了基础。对于三次b 一样条曲线骨架，我们提出采用降阶的方法， 在给定误差下，将三次b 一样条转化为二次b 一样条，然后将二次b 一样条分段 转化为二次b 6 z i e r 曲线，最后将各个二次b 6 z i e r 曲线势函数相加。相加的结 果近似表达原曲线的势函数。 在第三章中，我们提出了一种较快速的光线跟踪绘制卷积曲面的算法。首先， 运用空间八叉树剖分技术对整个场景进行剖分。然后，对每条光线计算其和 当前格子中每个骨架包围盒的交点，记录下相交区间。再次，用多项式函数 来逼近当前区间上的势函数。最后，将光线方程带入到多项式方程，求解上 面方程，将求得交点作为光线和曲面的交点。 在第四章中，我们对全文进彳亍总结，并提出了未来工作的展望。 关键词：卷积曲面、隐式曲面、几何造型、光线跟踪、降阶 浙江人学坝l ：学位论文 a b s t r a c t a b s t r a c t c o n v o l u t i o ns u r f a c e sm o d e l i n gi so n ek i n do fi m p l i c i ts u r f a c e sm o d e l i n g t e c h n i q u e st h a ti sw i d e l yu s e di nc o m p u t e rg r a p h i c s c o n v o l u t i o ns u r f a c ei sa c t u a l l y a l li s o s u r f a c eo fas c a l a rf i e l dd e f i n e db yc o n v o l v i n gs k e l e t o np r i m i t i v e s w h i l e c o n v o l u t i o ns u r f a c e sa l ea t t r a c t i v ef o rm o d e l i n gn a t u r a l 曲e n o m e n aa n do b j e c t so f c o m p l e xe v o l v i n gt o p o l o g y , t h ea n a l y t i c a l e v a l u a t i o no fi n t e g r a l so fc o n v o l u t i o n m o d e l ss t i l lp o s e ss o m eo p e np r o b l e m s i nt h i st h e s i s ，w eg i v ea n a l y t i c a lc o n v o l u t i o ns o l u t i o n sf o rp o i n t s ，l i n es e g m e n t s ， a r c s ，q u a d r a t i cb t z i e rc u i v e sa n dt r i a n g l es e g m e n t s ，a n dp r e s e n taf a s tm yt r a c i n g a l g o r i t h mo fc o n v o l u t i o ns u r f a c e s t h et h e s i si so r g a n i z e da sf o l l o w s ： i nc h a p t e ro n e ，w ei n t r o d u c eb a c k g r o u n dk n o w l e d g eo fc o n v o l u t i o ns u r f a c e s m o d e l i n g a n a l y z et h ee x i s t i n gw o r ka n dt h ea p p l i c a t i o nf i e l do ft h ec o n v o l u t i o n s u r f a c e sm o d e l i n g ，a n dp r e s e n tt h ei n n o v a t i v ec o n t r i b u t i o no ft h i st h e s i s i n c h a p t e rt w o ，u s i n gp i e c e w i s eq u a r t i cp o l y n o m i a la sk e r n e lf u n c t i o n ，w eg i v e a n a l y u c a lc o n v o l u t i o ns o l u t i o n sf o rp o i n t s ，l i n es e g m e n t s ，a r c s ，q u a d r a t i cb 6 z i e r c u r v e sa n dt r i a n g l es e g m e n t s e s p e c i a l l 5w eg i v eac l o s e df o r ms o l u t i o no f c o n v o l v i n gat r i a n g l es k e l e t o nw i t hk e r n e lo faf i n i t es u p p o r tf o rt h ef i r s tt i m e t h i sl e a das o l i df o u n d a t i o nf o ru s i n gal a r g en u m b e ro ft r i a n g l e sa ss k e l e t o n so f c o n v o l u t i o ns u r f a c e s f o rc u b i cb s p l i n es k e l e t o n ，w ef i r s tr e d u c et h ec u b i c b s p t i n ec u r v et oq u a d r a t i cb - s p l i n e su s i n gc o n s t r a i n e do p t i m i z a t i o nm e t h o d s ， t h e ns u mt h ep o t e n t i a l so fe a c hq u a d r a t i cb - s p l i n es k e l e t o nt oo b t a i nt h ep o t e n t i a l o ft h ew h o l ec u b i cb s p l i n es k e l e t o n i nc h a p t e rt h r e e ，w ep r e s e n taf a s tr a yt r a c i n ga l g o r i t h mo fc o n v o l u t i o ns u r f a c e s f i r s t ，o c t r e ep a r t i t i o n i n gi su s e dt op a r t i t i o nt h ew h o l es p a c eo ft h es c e n e s e c o n d ， f o re a c hr a y , w en o t ed o w nt h ei n t e r s e c t i o ni n t e r v a l sb e t w e e nt h er a ya n dt h e b o u n d i n gb o xo ft h es k e l e t o n s t h i r d ，w eu s eas i xd e g r e ep o l y n o m i a lt o a p p r o x i m a t et h ef i e l df u n c t i o na l o n gt h er a y f i n a l l y , s u b s t i t u t et h er a ye q u a t i o n i n t ot h ep o l y n o m i a le q u a t i o na n ds o l v ei t 。w ec o n s i d e rt h es o l u t i o na st h e 矸 浙江人学坝， 学位论文 i n t e r s e c t i o nb e t w e e nt h er a ya n dt h ec o n v o l u t i o ns u r f a c e s f i n a l l y , w ec o n c l u d et h i sd i s s e r t a t i o na n dd i s c u s st h ef u t u r ew o r k k e y w o r d s ：c o n v o l u t i o ns u r f a c e ；i m p l i c i ts u r f a c e ；g e o m e t r i cm o d e l i n g ；r a y t r a c i n g ；d e g r e er e d u c t i o n i 浙江人学坝1 ：学位论文 第一章绪论 第一章绪论 本章主要介绍卷积曲面的背景知识及其应用领域，分析前人工作以及叙述本 文的研究工作和内容。 1 。1 卷积曲面建模 参数曲面造型是大多数曲面造型系统的基础。参数曲面具有易于精确控制、 绘制方便等优点。但是，在用参数晰面构造光滑封闭的晰面时，我们很难做到光 滑拼接。特别是，在造好的形体上再添加一个部件并保持拼接处的光滑性几乎是 不太可能的。为了克服这些缺陷，在计算机图形学中引入了一些新的造型方法， 最具有代表性的是隐式曲面造型技术。隐式曲面由函数f ：r3 - - - r 定义，空间每 一个点被赋予一个标量值，可以用来描述颜色、温度、密度、压力等，曲面由函 数值为0 的空间点集 x r 3 i ， ) = 0 】构成。设a 是函数，描述的闭合体，则函 数值在a 的边界上为0 值，在a 的内部为负值，在a 的外部为正值。 隐式曲面和参数曲面相比，其主要优点是混合方便。由于不存在拼接问题， 隐式曲面在表现水、云、树干、人体肌肉的造型和动画方面有很大的优势。隐式 曲面的缺点是难以精确控制、绘制较困难。隐式曲面造型和参数曲面造型有很大 的互补性。隐式曲面造型技术主要包括代数曲面 s e d e r b e r g1 9 8 5 【b l o o m e n t h a l 1 9 9 7 、元球 b l i n n1 9 8 2 n i s h i m u r a1 9 8 5 w y v i l l1 9 8 9 、距离曲面田l o o m e n t h a l 1 9 9 0 1 、卷积曲面 b l o o m e n t h a l1 9 9 1 、变分曲面 s a v c h e n k 0 1 9 9 5 等。 卷积曲面造型是在计算机图形学中广泛使用的一种隐式曲面造型方法。 b l o o m e n t h a l 和s h o e m a k e b l o o m e n t h a l1 9 9 1 注意到元球造型实际上是采用点作 为骨架来构造隐式曲面。他们将骨架推广到高维情况，采用曲线、曲面、甚至是 体素来作为基本骨架标志着卷积曲面造型技术在计算机图形学诞生。 卷积曲面实质上是骨架通过卷积方式定义所生成的标量场的一个等值面。骨 架通常是一些点、线段、面片和体素的组合。其数学表达形式为 s = 妣y ，z ) i f a x ，y ，z ) 一t = o j ( 1 ) 其中f 为第i 个骨架的势函数，丁为阈值。通常只有下面定义形式： 浙江人学坝i ：学位论文第一章结论 设p r 3 r ：r3 _ 届为一个势函数，g ：r 3 - r 为表示某一个几何骨架 的三变量函数： f 1 ，p q g ( p ) 2 1 0 ，。施e 删沁 q 为骨架，点q q ，由骨架q 产生的势函数定义为： ，( p ) = i g ( q ) ，( p q ) a 娩( 2 ) n 写成卷积形式为： f ( p ) = ( f g ) ( p ) ，称也称为卷积核函数。可叠加性是卷积曲面的一个最重要的属性，即： f o ( g ，+ 9 2 ) = ( f o g ，) + ( f 9 2 ) 它决定了我们在计算多个骨架组合的势函数时，可以通过简单计算各个骨架势函 数结果后，将计算结果相加即可。这样我们就可以将主要精力去研究单个骨架的 势函数，而不必要考虑多个骨架情况。 运用这种方法定义的隐式曲面很好地解决了距离曲面 b l o o m e n t h a l1 9 9 0 中 的鼓包和裂缝问题，并且生成的曲面保持了原有骨架的大体形状。在理论上说， 骨架可以是任意的几何实体，点、曲线、曲面、三维实体。但是在计算骨架的势 函数时，由于要进行卷积积分运算，结果不一定能解析表达出来。而积分能否解 析表达取决于骨架和核函数两个方面。因此，在实际使用时，骨架和卷积核函数 的选取非常受限制。选取什么样的卷积核对整个卷积曲面生成来说起着至关重要 的作用。表1 列出常用的核函数极其图像。 无论使用什么样的核函数都不可能解析表达出任意骨架的势函数。 b l o o m e n t h a l1 9 9 1 对骨架进行点采样，来近似计算原骨架的势函数，但这种方法 不可避免的带来由于采样不足而导致曲面不连续等许多问题。聊c c o r m a c k 1 9 9 8 ， s h e r s t y u k1 9 9 9 采用c a u c h y 核函数，解析的求出点、圆弧、平面、三 角面片等简单骨架的势函数。但c a u c h y 核函数是一个全局支撑函数，计算空间 一点的标量值要计算所有的骨架对其贡献值。对于大规模的三角面片组合为骨 架，上述方法并不实用，s h e r s t y u k 对每个骨架定义一个包围盒，对于包围盒外 面的点骨架对其贡献的值为零。但这种裁剪会造成最终隐式曲面不连续( 见图1 浙江人学坝i j 学位论文第一章绪论 c a u c h y 函数 ，( r ) = 而南 其中r = l i e q l i ，r o 称为有效半径。以p 为圆心，以r 为半径的球称为裁剪球。 到目前为j e ，使川的核函数还有分段二次多项式以及w y v i u 六次多项式等。 图1 ：卷积曲面 s h e r s t y u k1 9 9 9 1 j i n2 0 0 2 1 采用截断的四次多项式为核函数，解析的求出直线段、圆弧、二次 b 6 z i e r 曲线等曲线骨架的势函数。并且，用一条三次的b 6 z i e r 曲线来控制和调节 曲线骨架单位弧元的贡献值，这样可以得到管状粗细变化的曲面。 图2 ：骨架及其对应的卷积曲面 j i n2 0 0 2 】 嘏江a 掌锄l 。l j 学垃论文 第一章绪论 h o r n u s0 3 运用绌分曲线作为骨架，通过对细分| ；f 秆线骨架势函数计算来近 叛裘这原始襻条蘧线载势丞数，毽戮逶过接澍缨努戆线豹层次潦达到曩声摇定夔 精度要求。 a n g e l i d i s2 0 0 2 是采用绌分曲灏为骨架。 ( 琏) 嚣耱不搿磐次麴爨势曲线生残熬嚣 e 较( 妨不霹屡次缀努莛囊嚣絮及萁生残基嚣 图3 ：纲分骨架极戴器积曲面g - l o r n u s2 0 0 3 、 a n g e l i d i s2 0 0 2 蒡桨鞠鹫架生成的卷粳鹣露在形状上有缀大戆壤经性，聪嚣絮通鬻是低维 的、易控制的。因此，我们可以通过编辑和控制骨架的形状来控制卷积曲面的形 状。 c - l 。t a i2 0 0 4 、【a l e x e2 0 0 5 】正是利熙卷积曲蕊造型这特点，按c s g 树 方式来组织场景结构，分别搭建了其有个性化的基于卷积睦丽的造型系统。 1 2 卷获曲蘧绘裁 卷积趋甏是一嵇隐式馥面，提到卷积魏瑟的绘制裁不褥不挺劐隐式构嚣的绘 制方法。概括地说，隐式曲面的绘制方法主要分为两类：( 1 ) 在给定容许误差的 情况下将隐式曲面转化为多边形模型，然后通过多边形的绘制结果来近似的反映 原始曲面的形状。( 2 ) 赢接光线躐踪。 1 2 1 隐式曲面多边骺化 由于大多数的图形加速卡和商业动画软件包都支持高性能地、基予多边形的 绘制，因此隐式曲面多边形化是臆式i # i 面绘制的一种最常用的方法。隐式f i 面多 迭形亿是计簿机图形擎中一个经典的谋题，已l 有禳多不同种类的算法。德总的来 说，主要分为以下几种方法( 1 ) 空间网格剖分法。( 2 ) 种子点扩张法。( 3 ) 粒子系统 豫式鞠瑟多逑澎纯。一f 蘑分鬟篱单分绍这魑多逮形讫算法。 ( 1 ) 空间网格剖分法 蘧类算法_ l 篷程丈签慝嬉是：先爨瓣格将穆薅空凌进行裁分，嚣算甄格顶点对 麻的函数值，如果网格的一条边的两个端点处对应的函数值个大于零，另一个 4 浙江人学颂l 学位论文 第一章绪论 小于零，那么该边和隐式曲面相交，需要进一步计算该边和隐式曲面的交点。最 后通过分析交点在网格单元中的分布位置情况建立拓扑邻接关系。m a r c h i n g c u b e s 方法 l o r e n s e n1 9 8 7 是此类算法中最常用也是最早的隐式曲面多边形化方 法，但该方法在抽取等值面的时候没有利用曲面空间的连续性，盲目的计算大量 无关节点的函数值，导致效率低下。【b l o o m e n t h a l1 9 8 8 1 、【b l o o m e n t h a l1 9 9 4 给 出一种优化采样的策略，首先从一个种子网格单元( 长方体) 开始，依次往上、下、 左、右、前、后六个方向搜索新的网格单元和隐式曲面交点，算法终止的条件是 到达指定的网格边界或者多边形闭合时。与传统的m a r c h i n g c u b e s 方法不同的 是，该方法使用自适应的空间八叉剖分的数据结构，且很好的利用了曲面的空间 连续性。算法在效率上有极大提高。但是，无论是上面的哪种方法，都是采用长 方体为基本网格单元，利用长方体和己知曲面计算所得交点信息及长方体网格信 息建立拓扑结构。而采用长方体为基本网格单元进行三角化都有可能导致生成多 边形模型的拓扑结构和曲面本身拓扑结构不一致( 见图4 ) 。 ( a ) 不一致的链接。( b ) 实际的拓扑结构。 图中灰色的点表示位于隐式曲面内部的点，红色的点表示位于外部的点。 图4 ：m a r c h i n gc u b e s ；边形化拓扑不一致情况分析 g u 6 z i e c1 9 9 5 1 j 匾过将长方体分解为五个四面体，利用四面体和曲面的交点的分 布情况相对简单，解决了上述问题。相对于m a r c h i n gc u b e s ，该方法产生的三角 面片的数量要多的多。【t r e e c e1 9 9 9 】提出一种基于m a r c h i n g t e t r a h e d r a 改进的方 法，首先运用m a r c i l i n g t e t r a h e d r a 将隐式曲面转化为多面体，然后对多面体中的 顶点进行聚合，最终得到的多面体模型不仅三角片数目较少，而且三角片规则性 高。 ( 2 ) 种子点扩张法 h a r t m a n n1 9 9 8 提出基于种子点向外扩张的三角化算法。该算法从曲面的一 浙江人学硬1 ：学位论文第一章绪论 个种子点或者规定的多边形出发，邂步向外扩张。从已经三角化的部分的边界上 选取未三角化区域角度最d 、( m i n i m a lf r o n ta n g l e ) ( 如图5 所示) 的点，在该顶点的 翻乎瑟土摄捶多长熬太枣确定一个委六透影，然后将六边澎嚣】委点孛篷予最，j 、焦 度之内的顶点投影到滞面上。对投影得到的点判断是将其加入到已经三角纯的区 域，还是合并两个区域或者分割本区域。该算法的主要优点是三角片的规则性商， 它可以得到近似等边的三角形网格；不但可以应用于隐式l 掬面的三角化，而凰可 激运壤予参数翔黼、甚至更广义的的嚣。其疑点是：没有根据麴面弱魏攀来调整 三角片酶大，l 、；强投影斡过程孛需囊计算函数的梯度，有罄时候这释齐镑跫缀大 的，难以接受。 k a r k a n i s2 0 0 1 】是基于曲率的三角化算法，在向外扩张的过稷中， 通过对曲面的 掬率估计来调整步长，这样即能得到近似等边三角形网格，又熊根 据鞠率变化来调熬三角片大小，减少了三角片的数疆，娜速后续绘制速度。 ( a ) 基本概念解释( b ) 投影过程 图5 ：h a r t m a a n 三角化过程解释 ( 3 ) 粒子系统隐式曲面多边形化方法 【w i t k i n1 9 9 4 镬曩粒子戆方滚滚采群窝控懿瑟式麓嚣。羧予积粒子之阉羧 据距离的大小柬定义能量，从而在粒子和粒子之间产生力，这种力使得粒子和离 子之间具有相互排斥的功能。当曲面变动时可以根据| ；i i 谢的大小来产生新的粒子 或去掉多余的粒子。粒子之问相互排斥，粒子分裂和死亡媛终能够使得粒子在曲 嚣上达到一静均匀分毒。最后，可以通过诲多基于点棱登兹三角化方法f 翔 fb e r n a r d i r d1 9 9 9 】) 将离散点集转纯成多边形模壅。 通过多边形化，我们可以把隐式黼面几何和拓扑信恩离散的转化为多边形的 顶点位置和多边形的邻接关系。但魑其缺点是往往难以检测到曲面的微小细节部 分，若容许误差比较小，将产生大量的三角片。这往往浠要花费很长的时间芹越大 量戆存德空涵来突凌这一过程，特翻蹩翟绘摹l 动疆场景辩，每次蠢羹瑟兹变动郡婺 6 浙江大学顿1 “学位论文豁一章绪论 重新多边形化曲面。 1 2 。2 光线跟踪 光线羧踩雾法壹接蒋竞线方稷r ( t ) = 0 + v t ，带入藤式蘧瑟方程f ( 薯弘z ) = 0 得到f ( r ( r ) ) = 0 ，通过求解上面的方程来计算当前光线和隐式曲面的交点，这种 方法在理论上是精确的，完美的。但是，实际上，由于方程f ( x ，y ，z ) = 0 的复杂 淫( 实嚣土壤多瓣媛我翻都不藐写懑f ( x , y ，z ) 具萍表瑷形式，瑟傻莰较据绘定点 p ( x o ，y o ，z o ) 计髀出，( p ) 的值。) ，必须要采用复杂数值方法来求解上面的方程， 导致光线跟踪辣法效率不高。如何快速求解方程f ( ，( f ) ) = 0 ，是光线跟踪方法绘 裁隐式趣面鹊一个核心阔题。针对不嗣的需要，计算枧图形学已经有许多缀好的 方法绘锈不丽瓣疆蘑。下嚣筵擎奔缓下这些方法。 ( 1 ) 光线和三维d 次代数曲面 三维空间中的张d 次代数鞠丽 ij nh f ( x ，y ，z ) = 啄y 7 = o f = # i = 0k = o 其中f + m + = d ，将光线方程带入到上式得到f p + 砩) = o 不妨记 d ( # ) = f ( o + v t ) ；a i r i - - o 当d 5 ，f + ( ) 的实根可以解析给融。否则，需采用数镳方法求解。 ( 2 ) 区间算术法 【m i t c h e l l1 9 9 0 区间算术求根法谮先将交点隔离在游干个区间，使得一个区间 里最多只有一个交点，霉霜牛顿迭我法，二努法等求褥嚣阉肉戆交点。区润簿零 法不仅可黻求您麓线和隐式赫面的鼗近交点，两且能求缀所有酶交点，这在诸鲣 c s g 造型中增加或删减景物时尤其有效；但它需要在区间内定义隐式函数沿光 线的方向导数，因此不能处理一热不规则的隐式曲面。 ( 3 ) l i p s c h i t z 法光线跟踪 濒江a 掌 | ； i ：学位论文 第一章结论 令，仁) 为隐式曲面函数，称，0 ) 具有l i p s c h i t z 性质，当且仅当对定义域中 任意两个点茹、y ，存在常数丑，使褥： l ，曲) 一，j 五降一芦l ( 3 ) 满足上面式予的最小常数a 称为，( 搿) 的l i p s c h i t z 常数，记为l i p f 。当，熙连续 函数时，l i p f 就怒，的最大斜率。 l g 竞线舔稼捺述一类魏够光线缀踩粒稿垂 k a l r a1 9 8 9 1 。令党线方释淹 o + 耽，定义f ( f ) = f ( o + 耽) ，g ( ) = d f d t 。设已是函数，( 工) 定义在3 d 区域r 上的l i p s c h i t z 常数，g 是函数g ( f ) 在闭区间t = 【，屯 上的l i p s c h i t z 常数。即满 足： l f ( x ；) - f ( x ：) l g r t h e nf ( t ) i s m o n o t o n i c o v e r t m t 】 汹i f 菩强) ，g ( t z ) 0 t h e n as i n g l er o o t i s i s o l a t e d 。 浙江人学砸i 一学位论文 第一章绪论 c o ) o t h e r w i s e ，t h e r ei sn or o o ti n t c ，t l o t h e r w i s e ，d i v i d ea n dc o n q u e r , r e p e a t i n gf i r s to n ，t j a n dt h e n t 。，t l 】 | 厂 r ，满足i ，0 】d b ，f 一1 ( 0 ) ) ，则称，( z ) 是其定义的隐式曲 面，_ 1 ( 0 ) 有向距离约束。此时，也称，( 工) 是一个有向距离函数o 瞎n 甜d i s t a n c e b o u n d ) 。若一个函数在区域d 上满足l i p s c h i t z 条件，那么f 2 就是一个有向距 离函数。 不妨设光线最大前进距离为d ，则光线和隐式睦面，。1 ( o ) 求交算法可以用 下面的伪代码来描述。 m m a l i z et = 0 w 1 1 i l et r 图7 ：点骨架极其对麻卷积曲匦 1 2 浙江人学坝，l 学位论文 第二章骨架势函数计算 2 3 直线段骨架势函数计算 设直线方程为： 邵朋+ 黼飙呱黔只i 对于空间任意一点p ，裁剪球和直线交点可由下面的方程得到： r 2 ( s ) = l p - l ( 哪= r 2 上面的式子等价于 s 2 2 旦! 二群s + i l p t , , 1 1 2 - r 2 = 。慨一刚 ” 叫h 2 气邕产 d = 伊一只4 整理上面的式子得 s 2 2 口s + d 2 一r 2 = 0 。 设上面方群的两个解为丑、s 2 ，则吼= 4 一口2 一d 2 + r 2 、j 2 = o + d 2 一d 2 + r 2 。 若s 1 - l 或者s 2 o ，此时直线段对点p 无贡献，即p 点所对应的标量值为零。 反之，有效的支撑区间为 1 l ，1 ：】，其中，= m a x ( o ，s j ) ，f 2 = m i n ( ，s ：) 。则此时点 p 所对应的标量值为： c 耻耽：。, , , f i w - 1 w 。) ，( r 2 胁 = 塞悟肛s 2 2 a s - r 2 + d z ) z 出l j = w 0 7 冗i 肿( p ) + w l ，蜘t ，( p ) + w 2 j 乞。( p ) + ，：。( p ) 其中嵋= w ) 、嵋= ( 一3 + 3 w 1 ) 、 以= f 1 ( 3 w i ，一6 w l + 3 w p 、= f 1 ( 一w 【，+ 3 w 一3 w 2 + w 3 ) 磁j p ) 2 古p ( s 2 - - 2 卅r 2 ) 2 西 经过简单计算可得 吃。( p ) = 可1 ( 弘1 一矸) 一( f ：4 一枷+ 2 3 一z 3 ) ( 2 a 2 _ ( r 2 _ d 2 ) ) + 2 ( 碍一砰) a ( r 2 一d 2 ) - i - ( f ，一1 ) ( r 2 一d 2 ) 2 ) 浙江人学颂j ：学位论文笫二章骨架势函数计算 瓦。( p ) = 1 弘1 一f ? 了4 旷5 枷+ 扣一1 4 ) ( 2 a 2 - ( r 2 - d 2 ) ) + 要( z ；一f ? ) 4 ( r 2 一d2 ) + i 1l f 2 2 1 1 2 ) ( r 2 - d 2 ) 2 ) j二 呓。( p ) = f 1 ( 弘17 一z 卜26 一矸) 谢知5 一f ( 2 a 2 _ ( 9 2 _ d 2 ) ) + ( 譬一z ? ) n ( r 2 一d 2 ) + ；( 譬一f ? ) ( r 2 一d 2 ) 2 ) 吃。( p ) = f 1 ( 掣1 一伊弘47 一n n + 弘i 6 协( 2 a 2 - ( r z - d 2 ) ) + i 4 【l ：5 一彳) d ( e 2 _ d 2 ) + ；( 譬一l ? ) ( r z - d 2 ) 2 ) 图8 ：真线段骨架及其所对应的卷积曲面 2 4 圆弧骨架势函数计算 不妨设圆弧的方程为： a ( 口) = ( r ) c o s 8 ，r ) s i n 8 ，0 ) ，仍0 仍 ( 6 ) 其中0 竹 仍 2 石。设p ( x ，y ，z ) 为空间中一点，圆弧所在的圆和裁剪球所占 区域有交的充要条件是： i i r , - r o i l d ( r z ) ( 8 ) 其中：撕爵，d ：0 _ 尹。若满足( 8 ) 式，此时整个圆都含在裁剪球中。 若满足( 7 ) 式，此时裁剪球球面和圆有交。计算交点所对应的参数可通过下图方 法得到： ， 、 厂 ：蠢“”) 。 i jd ， 、，。 图9 ：裁剪球和圆几何位置关系 1 4 浙江人学颂i ? 学位论文 第二章骨架势函数计算 如图9 所示，妒表示从工轴到o m 的角度，设交点所对应的参数值分别为口、卢， h = r j 2 + d 2 一碌，d = 2 r o x ，b = 2 置，y 。根据余弦定理可知 口：西一a r c c o s 土， 7 2 r d= 妒+ 一o s 南 为了说明方便，我们用下面的代码来描述点p 点实际所对应的支撑区间的求解过 程： i f 口 2 x ；b = ；b 一2 x ： i f 口 仍0 1 仍 o n e e f f e c t i v es p a n 6 p l ，m i n a ，仍 ；s p a n n u m + + ：】 i f 晚 卢( o n e e f f e c t i v es p a n m a x 咿，绷，仍】；s p a n n u m + + 】 设支撑区间【+ 皖，】，o l 或t 2 。，稳线段嚣裁剪球没舂交感e 否剿二次b 6 z i e r 鞠 线和裁剪球相交的有效区间为【 ，屯】( 见图1 1 ( b ) ) 。 ( 3 ) 方程有四个实根，不妨设四个实根分剐为o t s p 曼y - 艿，令= m a x 0 ，烈、 2 = r a i n 1 ，多l 、= m a x 0 ，r 、t 4 = r a i n 1 ，爨。下覆懿过程援述了怎么撵求藤有效 区间。 i f ( t 。 - a f l 。+ 3 彳a ，。+ c ? a t 。 l l = i j i - - t )i = 0i = ( 1 j 运用分部积分得 仁絮竽2 扩l 景2 巩： 一 n + “ n + 。“一2 当n = o 时 = 詈而f + 丢万2 l “+ i ) ， 1 9 澎江人学瑚，| ：学位论文豁- 二章嚣挑势墨数汁蟹： 当n ：1 时，：三p 。+ u 2 ) 3 他， 3 遮鼯递l 胃方式计算穰分，可醵褥爨二次b 6 z i e r 穗线势函数。 剧1 2 ：- 次b 6 z j e r 曲线极其对戍卷积曲赋 2 。巷三次b 祥条曲线骨架势函数 若骨架为三次b 6 z i e ri ! l 线，不妨设其幂基形式为 c 移) = c ，3 + c 2 f 2 + c l t + c o ，0 t 茎l 则窆翅点尹豹势函数为：f 尹净1 2 ( 1 一与) 2 器) 陋 其中a = 9 c 3 c 3 ，b = 1 2 c 3 c 2 ，c = 4 c 3 - c 3 + 6 c i - c 3 ，d = 4 c l ，c 2 ， e = c l c ，f i c ( 0 1 = 4 a t 4 + 所3 + 0 2 + d t + e 对于一般的三次b 6 z i e r 曲线，上面的式子不是娜攒可积的。本文提出了基于降 阶的三次b 祥条曲线骨架卷积阀面势函数计算方法。首先在给定误差下将三次b 梯条曲线( c 1 连续) 降阶为c 1 连续的二次b 样条曲线。然后，捅入黧节点转化 为分段二次b 6 z i e rf | l 线表示，褥通过二次b 6 z i e rf | f 线斡势函数解祈计葬方法来 计算原三次b 样条曲线的势函数。这样，我们可以直接用三次b 样祭曲线骨架 逶行卷积瓣瑟造墼了。 b 样条曲线降阶是近几年c a g d 中的一个热门课题，目前已有不少b 样条 | | 线兹酶玲算法 n e n1 9 9 5 w o l t e r s1 9 9 8 y o n g2 0 0 1 z h a n g2 0 0 4 。b 襻条麴线 降阶通常将样条曲线通过捅入道节点分殷转化为b 6 z i e r 曲线，然后对姆段分别 终玲来实臻。我们露要戆是酶除惹二次b 6 z i e r 鞠线段之闻熊绦持g c l 连续、且 段数尽量少的降阶算法，以使得得到的辫积曲面光滑、计算髓小。我们改进了雍 俊海 y o n g2 0 0 1 等人提出的b 嘲扰动方法。 下面介绍算法的其体步骤： 2 0 浙江人学坝l 学位论文 第二章骨架势函数计算 3 ( 1 ) 不妨设单段三次b 6 z i e r 曲线方程为p ( f ) = 日，3 ( f ) 只，运用 h u1 9 9 8 b 6 z i e r f = 0 曲线b 网扰的方法，设扰动后的曲线为f ( f ) ，由该参考文献知 忙。，一声c r ，i i 坚掣，若曲线在r ：q ，r ：。，q c ：点离散，那么离散后中间 曲线满足0 3 丘，= ( c ：一c ，) 30 岔只磊、丘、t 、曩，为离散后中间啸线的控 制顶点。为了使得离散后的子曲线和原曲线之间的误差小于f ，当 i c 2 二9 c ：, 酬 可愀赇蝴锕蝴：r 蜉段。 - - l ( 2 ) 不妨设三次b 样条曲线的参数方程为p ( f ) = n ( f ) 只，其节点序列r 为、 e - - 0 t l t 。+ 3 ，且o = l = 2 = 屯，f 。= f 。+ 1 = f 2 = f 3 ，节点“，4 k n 一1 重数小于3 。 则该降阶算法司描述为： a ) 对每条b 4 z i e r 曲线段运用上面的方法估算要分的断数，在此段曲线对应的参 数区间上等参数的插入节点每个节点捅入两次，对于原曲线的单重节点t ，插入 节点t f b ) 对曲线p ( r ) ( 经过( a ) 处理后的曲线) 运用b 网扰动的方法得到可退化的三次 b 样条曲线q ( t ) ； c ) 如果曲线p ( r ) ( 捅入节点后的曲线) 与曲线q ( f ) 的误差大于给定误差( l 2 范 数意义下) ，则 ( 1 ) 找出误差极大值点，( 可能不只一个) 。 ( 2 ) 找到所有的区间i i , l + ，使得胁 | ；，f f + i 】。 ( 3 ) 设k ，+ i j 为满足上述条件( 2 ) 中区间长度最大的一个，捅入节点三学两 次。 ( 4 ) 回到步骤b 。 浙江人学坝i ：学位论文 第二章骨架势函数计算 d ) 如果p ( f ) 和q ( f ) 的误差小于给定，q ( f ) 为退化的三次b 样条曲线，分段将 其转化为二次b 4 z i e r 曲线。 e ) 算法结束。 下面来分别详绌地解释步骤) 和( d ) 。对于区间i t 。，t k + 1 ，t 。 “+ 上的曲线 段是退化的三次样条的充要条件是： p 1 f ) ；0 ，r “，t k + 1 ( 1 1 ) 只一只一，e 一一只一：只，一疋：只一：一只一， 上面的式子等价于上盟! l 垒上丑一韭二k l 生l 二玉生：0 ，写成矩阵 + 2 一t k + i t k i 形式可以表达为( a k ，阮，q ，d 。) 一1 a = 。一 。 ( + ，一一2 ) - ( + 。一一) q = 以2 瓦j 了1 瓦 = 0 。其中 j _ 1 气) ( “+ 2 一t k 1 ) ( t k + + 一+ 二! + 二! “) ( + 2 一一i ) ( 气+ 2 一t k ) ( 气+ 2 一气一，) i 但是对于一般的曲线，条件( 1 1 ) 式是不能满足的。我们对每个控制顶点做扰动， 设顶点只的扰动向量为岛，扰动后项点q 。= 只+ s 。，0 i n 一1 ，使得扰动后的 n l 样条曲线q ( f ) = n ( f ) q f 在每个区间 t k , t 川 ，t i “+ 1 上的曲线段 f - - - - 0 k 。( f ) q ，满足条件( 1 1 ) 式，并且1 i n ( n - i 慷1 1 2 ) 。问题转化为求约束条件极值问 题，我们把约束条件简写成矩阵形式为： a q = 0 2 2 ( 1 2 ) 浙江人学坝l 学位论文 笫_ 二章骨架势函数计算 其中a 为系数矩阵，q = ( q 0 ，q l ，一q 。) 7 。 运用l a n g r a n g e 乘子法求极值，将l a n g r a n g e 函数对每个扰动向量8 f 的每个分量 求偏导数后的等式写成矩阵形式为 q = p + a 7 x( 1 3 ) 其中x 为l a n g r a n g e 乘子( 向量形式) 。由( 1 2 ) ( 1 3 ) 两式可以得到 a a l x = 一a p ( 1 4 ) 从而解出x ，代入( 1 3 ) 求出q ( t ) 。 因为q ( r ) 阶数为4 ，而其e p i c 节点重数不大于2 ，因此q ( o 为c 连续的，并 且可以表示为c 1 连续的二次b 样条。 在步骤d ) 中，我们在退化的三次b 样条曲线中插入重节点，将其分段转化 为三次b 6 z i e r 表示，运用下面的定理我们直接将最终二次b e z i e r 曲线表示成幂 基形式。 3 定理设p ( f ) = b ? ( f ) 只为三次退化的b 6 z i e r 曲线，那么p ( f ) 可以表示成 f _ ( r + 3 ( 只一p o ) t + 3 ( ( p 2 一只) 一( 只一e o ) ) t 2 证明：p (