基于二次代數(shù)曲線端點幾何信息的最優(yōu)有理參數(shù)化

厲玉蓉， 姜 麗

（1.山東工商學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院，山東 煙臺 264005；2.山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東 濟(jì)南 250014）

曲線、曲面是計算機(jī)圖形學(xué)(CG)和計算機(jī)輔助幾何設(shè)計(CAGD)中的基本研究對象。參數(shù)曲線曲面具有構(gòu)造簡單直觀、易于顯示等特點，又脫離了對坐標(biāo)系的依賴，因而在計算機(jī)圖形學(xué)中得到廣泛應(yīng)用。在圖形的顯示過程中，參數(shù)化算法的優(yōu)劣會直接影響曲線段的繪制效果。二次代數(shù)曲線的參數(shù)化的數(shù)學(xué)實現(xiàn)并不困難，但僅僅是實現(xiàn)還遠(yuǎn)遠(yuǎn)不能滿足工程需要，一方面，在實際的應(yīng)用中，往往需要對曲線的某一部分進(jìn)行參數(shù)化，而不是整條曲線；另一方面，出于工程需求、造型美觀和計算量等方面的考慮，工程人員往往想要得到曲線的最優(yōu)參數(shù)化方程[1-7]。

理論上來說，弧長參數(shù)化是理想中最優(yōu)的參數(shù)化。代數(shù)曲線的弧長參數(shù)化不可能是有理參數(shù)化方程，而有理參數(shù)化是最常用的一種參數(shù)化形式，因此眾多學(xué)者轉(zhuǎn)為研究最接近弧長參數(shù)化的有理參數(shù)化方程[8-11]。

最優(yōu)參數(shù)化的評判標(biāo)準(zhǔn)對最優(yōu)參數(shù)化的構(gòu)造具有一定程度的影響。Rida[9]提出了一個評判標(biāo)準(zhǔn)，并利用這一標(biāo)準(zhǔn)得到了一類曲線參數(shù)化方程。但是該評判標(biāo)準(zhǔn)存在一定的不足：曲線幾何信息不明確、不能確定該類參數(shù)化所能達(dá)到的最優(yōu)值。從物理意義講，在參數(shù)域[0,1]上，可以將參數(shù)看作時間，曲線上某點的切向量的模看作該點處的移動速率，則曲線上各個動點的移動速率的波動越小越好，若保持均勻，則可弧長參數(shù)化。

本文利用文獻(xiàn)[10]中的評判標(biāo)準(zhǔn)來衡量參數(shù)化效果的優(yōu)劣，這一標(biāo)準(zhǔn)可以簡單的表述為參數(shù)曲線切矢量模的最大值和最小值的比與1的接近程度。

1 二次代數(shù)曲線的最優(yōu)有理參數(shù)化

1.1 問題描述

設(shè)g(x,y)∈R[x,y]是關(guān)于x,y的二次多項式，方程g(x,y)=0定義了一條平面二次代數(shù)曲線C。A、B分別是曲線C上的兩個點，向量n0為A點的單位切向量，求以A為起點，沿n0方向到達(dá)B點的曲線段的最優(yōu)有理參數(shù)化。

不妨設(shè)A=(0,0),B=(x1,y1),n0=(n0x,n0y)=(1,0)，否則可通過平移、旋轉(zhuǎn)變換使其滿足。記向量n1=(nx,ny)為B點的單位切向量，曲線在A點處的曲率半徑為ρ，不失一般性，令曲線段AB的參數(shù)域為[0,1]，如圖1所示。

圖1 參數(shù)域為[0,1]的曲線段AB

1.2 有理參數(shù)化及最優(yōu)評判標(biāo)準(zhǔn)

對于二次曲線：

由于曲線過點A(0,0)，且與x軸相切，則有：

依照文獻(xiàn)[10]的方法可得曲線段AB對應(yīng)于參數(shù)域[0,1]的所有二次有理參數(shù)方程：

其中

λ為非零實數(shù)。

(t)=(x′(t),y′(t))是參數(shù)曲線Pλ(t)的切矢量，記

如果Γ(P*)=min{Γ(P(t))}稱此P*(t)為曲線段AB的最優(yōu)參數(shù)化方程。顯然

Γ(P)=1?P(t)可弧長參數(shù)化。

注意，對于代數(shù)曲線的有理參數(shù)化方程必有Γ(P)＞1。

1.3 參數(shù)λ的確立

定理對于二次曲線段有理參數(shù)化，曲線切矢量的模的值在起點和終點處相同的充分必要條件是λ=（其中l(wèi)是線段AB的長度，ρ表示代數(shù)曲線C在起點A處的曲率半徑，α表示向量n1和直線AB的夾角）。

證明：

必要性：

首先利用曲線段的幾何信息確定其代數(shù)方程：

設(shè)l1、l2、l0分別為三條二次曲線起點處切向量、終點處切向量和由起點指向終點的向量所在的直線（如圖1所示），直線方程分別為：

l1:y=0

根據(jù)文獻(xiàn)[11]利用二次曲線的幾何信息，任意經(jīng)過A、B兩點，且分別以l1,l2為切線的二次曲線可以表示為如下形式：

其中，μ為自由參數(shù)，可由曲線起點處的曲率半徑確定。

分別將l0,l1,l2的直線方程代入式(4)得二次曲線的代數(shù)方程為：

對比方程(1)，(5)可求得二次曲線的系數(shù)：

由曲線起點處的曲率半徑ρ可確定參數(shù)μ為：

由公式(2)，(6)二次有理參數(shù)方程可表達(dá)為：

其中：

由于曲線C的參數(shù)速率在起點和終點處相同，即：

利用式(7)并分別求出x′(0)，y′(0)，x′(1)，y′(1)，代入式(8)化簡得到：

根據(jù)λ的幾何意義，舍去負(fù)根求得：

其中

將式(10)代入式(9)得λ=

充分性：

將λ=代入公式(2)易求：

即曲線端點處切矢量的模相等。 證畢！

由于AB曲線段對應(yīng)[0,1]參數(shù)域的有理參數(shù)方程可由公式(2)給出，λ是其自由參數(shù)，即Γ值由λ決定，則尋求最優(yōu)有理參數(shù)方程即是尋求使得Γ值最小的λ。Γ值是參數(shù)速率的最大值與最小值的比，大量實例表明，若存在二次曲線段的有理參數(shù)方程Pλ(t)滿足且是最值，則此參數(shù)化即為最優(yōu)有理參數(shù)化。此時的λ可由定理給出的公式來構(gòu)造并確定。

2 實例分析

2.1 實例1

已知平面二次代數(shù)曲線：上點A(3,0)和B(0,2)，按逆時針方向求AB弧的最優(yōu)有理參數(shù)化。

用本文方法有理參數(shù)化時得到曲線段AB的參數(shù)方程：

本文方法參數(shù)化后的曲線及曲線的參數(shù)速度分別如圖2中的空心點和圖3中的實線所示，得到的是曲線段的最優(yōu)有理參數(shù)化方程。文獻(xiàn)[10]的方法參數(shù)化后的曲線及曲線的參數(shù)速度分別如圖2中的實心點和圖3中的虛線所示,此時Γ≈1.6204。

圖2 1/4橢圓弧的參數(shù)化對比效果圖

圖3 1/4橢圓弧的參數(shù)速度對比效果圖

2.2 實例2

已知平面二次代數(shù)曲線上點A(2,0)和點B(4,)，按逆時針方向求AB弧的最優(yōu)有理參數(shù)化。

用本文方法有理參數(shù)化時得到曲線段AB的參數(shù)方程：

本文方法參數(shù)化后的曲線及曲線的參數(shù)速度分別如圖4中的空心點和圖5中的實線所示。最優(yōu)的Γ值約為1.1265，本文方法得到的是曲線段的逼近最優(yōu)的有理參數(shù)化方程。文獻(xiàn)[10]的方法參數(shù)化后的曲線及曲線的參數(shù)速度分別如圖4中的實心點和圖5中的虛線所示，此時Γ=4.0000。

圖4 雙曲線弧的參數(shù)化對比效果圖

圖5 雙曲線弧的參數(shù)速度對比效果圖

表1給出了更多實例結(jié)果。

3 結(jié)束語

理論上，最優(yōu)有理參數(shù)化方程可求，但是計算量非常大，對于任意的二次代數(shù)曲線，本文根據(jù)端點處參數(shù)速率相等來直接構(gòu)造出有理參數(shù)化公式，實例也顯示了方法的有效性。對于一段圓弧，橢圓或雙曲線上的具有對稱性質(zhì)部分的有理參數(shù)化，用本文方法得到的就是最優(yōu)有理參數(shù)化；若參數(shù)化曲線段端點處的參數(shù)速率相等且是最值，實驗數(shù)據(jù)顯示也是最優(yōu)的；另外，其他情形非常逼近于最優(yōu)。

本文僅對二次代數(shù)曲線進(jìn)行了最優(yōu)參數(shù)化研究，下一步的研究工作將針對三次或者高次代數(shù)曲線最優(yōu)有理參數(shù)化展開，對于Γ值偏大的曲線如何選擇分段方法以達(dá)到接近弧長的參數(shù)化也是值得研究的。

表1 部分實例結(jié)果與最優(yōu)參數(shù)化和文獻(xiàn)參數(shù)化的對比

[1]Abhyakar S S,Bajaj C.Automatic parameterization of rational curves and surfaces III: Algebraic plane curves [J].Computer Aided Geometric Design,1988,5: 309-321.

[2]Sonia P D,Sendra J R,Sonia L R,Sendra J.Approximate parametrization of plane algebraic curves by linear systems of curves [J].Computer Aided Geometric Design,2010,27(2): 212-231.

[3]Sonia P D,Sendra J,Sendra J R.Parametrization of approximate algebraic curves by lines [J].Theoretical Computer Science,2004,315(2): 627-650.

[4]Kuznetsov E B.Optimal parametrization in numerical construction of curve [J].Journal of the Franklin Institute,2007,344(5): 658-671.

[5]Hartmann E .Numerical parameterization of curves and surfaces [J].Computer Aided Geometric Design,2000,17(3): 251-266.

[6]厲玉蓉,張彩明.三角網(wǎng)格上的代數(shù)曲面重建[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2007,19(4): 460-463.

[7]Zhao Xiuyang,Zhang Caiming,Yang Bo,Li Pingping.Adaptive knot placement using a GMM-based continuous optimizationalgorithm in B-spline curve approximation [J].Computer-Aided Design,2011,43(6): 598-604.

[8]郭鳳華.參數(shù)曲線的最優(yōu)參數(shù)化[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2007,19(4): 464-467.

[9]Rida T F.Optimal parameterizations [J].Computer Aided Geometric Design,1997,(14): 153-168.

[10]厲玉蓉,胡芳剛.平面二次代數(shù)曲線的最優(yōu)參數(shù)化[J].圖學(xué)學(xué)報,2012,33(2): 49-52.

[11]張三元.基于代數(shù)曲線段的G2連續(xù)的曲線造型方法[J].計算機(jī)學(xué)報,2000,23(2): 153-157.