三次b樣條曲線控制頂點的求法

三次b樣條曲線控制頂點的求法

0反求三次b樣條曲線控制頂點的快速算法b樣曲線是計算機圖形學中的一個非常重要的曲線。三次B樣條曲線被應用最多,高于三次的B樣條曲線由于計算過于復雜用得很少。在實際工程應用中,經(jīng)常需要反求三次B樣條曲線的控制頂點,而且所涉及的計算量相當?shù)拇?因此有必要找出反求三次B樣條曲線的控制頂點的快速算法。反求三次B樣條曲線控制頂點的問題在某些情況下可歸結為求解一個系數(shù)矩陣為三對角矩陣的方程組。一般通過追趕法或LU分解法(這兩種方法在理論上是完全等價的)去求解該方程組,該文通過對A-1的研究提出一種快速求解算法。1控制頂點ps,p2p反求三次B樣條曲線控制頂點的問題可以描述為:已知三次B樣條曲線個分段點Q1,Q2,…,Qn,求其n+2個控制頂點P1,P2,…,Pn,Pn+1,Pn+2。根據(jù)三次B樣條曲線的性質,可得求解其控制頂點的方程組為:(Pi+Pi+1+Pi+2)/6=Qii=1,2,…,n(1)該方程組有n個方程,n+2個未知數(shù),因此需補充兩個邊界條件方程才能求解。(1)qq2qn0[-111410141?01411-1][Ρ1Ρ2?ΡnΡn+1Ρn+2]=6[0Q1Q2?Qn0](2)????????????111410141?01411?1??????????????????????P1P2?PnPn+1Pn+2???????????=6???????????0Q1Q2?Qn0???????????(2)(2)控制頂點關于b樣條曲線控制頂點問題Q′1=12(Ρ3-Ρ1)(3)若將末段看成是二次B樣條曲線,可得另一個邊界條件:-Pn-1+3Pn-3Pn+1+Pn+2=0(4)將式1、3、4聯(lián)立,并對所得的方程組作變換,可得:[0.511410141?01411-1][Ρ1Ρ2Ρ3?ΡnΡn+1]=6[(3Q1-Q′1)/12Q1Q2?Qn-1(Qn-1-Qn)/6](5)解出式5,再由式4可求得Pn+2。此外,若已知B樣條曲線末端點處的一階導數(shù)Q′n,將B樣條曲線的首段當成是二次B樣條曲線即可;若始末端點處的一階導數(shù)均未知,則可將B樣條曲線的首末兩段均視為二次B樣條曲線。在前面所討論的一些情況下,反求三次B樣條曲線的控制頂點的問題可歸結為求解線性方程組Ax=s,其中A=[b111410?01411bn](A為n階方陣),x=[x1,x2,…,xn]T,s=[s1,s2,…,sn]T。找出A-1的規(guī)律,可得到該方程組的快速解法。2關于a-1的研究2.1a的行列式令Dn=|41141?14114|n×n?Dn有下面的遞推式:{Dn=4Dn-1-Dn-2(n≥2)D1=4D0=1D-1=0(6)則可以證明A的行列式可以表示為:|A|=b1bnDn-2-(b1+bn)Dn-3+Dn-4(n≥4)(7)2.2aij、iA的伴隨矩陣,A*=[Aij]n×n(1≤i,j≤n),它是一個對稱矩陣。經(jīng)過歸納證明可得:Aij=(-1)i+jMiNj(i≤j)(8)Μi={1i=1b1Di-2-Di-32≤i≤n,Νj={bnDn-j-1-Dn-j-2i≤j≤n-11j=n(9)2.3算法型ax由式6、式8和式9可得:{A1n=(-1)n+1A2n=(-1)n+2b1Ain=-4Ai-1n-Ai-2n(3≤i≤n)(10)由式10可求出A*的第n行元素的值。根據(jù)式7、8、9又可得到:|A|=bnAnn+An-1n(n≥4)(11)由式8、9,可推出:Ain-k=(-1)kAin(bnDk-1-Dk-2)(1≤k≤n-1,1≤i≤n-k)(12)由式10、11、12可求出A-1。在實際求解方程組Ax=s時,無需求出完整的A-1,采用算法1即可:算法1(1)由式10求出A*的第n行元素;(2)由式11求出|A|;(3)xn=(n∑i=1AinSi)/|A|?Xn-1=(-bn)xn+sn;(4)由遞推公式xi+4xi+1+xi+2=si+1最終解出方程組。3與分解法的比較3.1lie-n的算法計算采用LU分解法求解要求矩陣A必須是主對角占優(yōu)的,而該文提出的算法1則沒有這個限制。若直接采用LU分解法,時間復雜度為O(n3),充分考慮A的特殊性,其時間復雜度能降到與算法1相同的O(n),此時LU分解法的計算量約為次乘除法和3n次加減法,而算法1的計算量則約為3n次乘除法和4n次加減法。LU分解法的計算過程需要約2n的存儲空間,而算法1僅為n。顯然,無論是從運算量還是空間需求上考慮,該文的算法1均優(yōu)于LU分解法。3.2反求控制頂點性能比較三次B