厲玉蓉， 胡芳剛

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

曲線、曲面是計(jì)算機(jī)圖形學(xué)(CG)和計(jì)算機(jī)輔助幾何設(shè)計(jì)(CAGD)中的基本研究對(duì)象。參數(shù)形式和隱式形式是表示曲線、曲面的兩種主要方式。兩種表示形式各有其內(nèi)在的優(yōu)點(diǎn)，有效地實(shí)現(xiàn)二者的相互轉(zhuǎn)換一直是 CAGD的一個(gè)熱點(diǎn)問(wèn)題[1-9]。從數(shù)學(xué)意義上講，二次代數(shù)曲線曲面的有理參數(shù)化問(wèn)題已經(jīng)完全解決了，但遠(yuǎn)不能滿足實(shí)際應(yīng)用的需求。首先，在幾何造型領(lǐng)域中，通常是對(duì)某一曲線上的一部分感興趣，而非整條曲線；其次，工程人員更希望得到最優(yōu)參數(shù)化，即當(dāng)參數(shù)均勻選取時(shí)，對(duì)應(yīng)點(diǎn)間的弧長(zhǎng)也能夠較為均勻。傳統(tǒng)的參數(shù)化方程對(duì)目標(biāo)曲線段的效果很難確定，例如，對(duì)單位圓的有理參數(shù)化，多用下式來(lái)表示

當(dāng)t∈(0,1)時(shí)，表示圓在第1象限的部分，但是，這個(gè)有理參數(shù)化并不是圓在第1象限的最優(yōu)參數(shù)化結(jié)果。

代數(shù)曲線參數(shù)化后，得到新的曲線方程，參數(shù)化因子不同，則得到的參數(shù)曲線的方程不同。不妨將目標(biāo)曲線段的參數(shù)域定為[0, 1]，若將參數(shù)視為時(shí)間，曲線視為物體移動(dòng)路線，最優(yōu)參數(shù)化實(shí)質(zhì)上是尋求物體速率變化最小的參數(shù)化結(jié)果。

對(duì)于一般的有理參數(shù)化而言，弧長(zhǎng)參數(shù)化基本不可能取到，只能在固定參數(shù)化形式中，尋求最接近弧長(zhǎng)的參數(shù)化方程。Farouki[10]提出了最優(yōu)參數(shù)化的標(biāo)準(zhǔn)，并試圖按這個(gè)標(biāo)準(zhǔn)對(duì)曲線的參數(shù)化進(jìn)行優(yōu)化。對(duì)于代數(shù)曲線的參數(shù)化，無(wú)論是評(píng)判標(biāo)準(zhǔn)還是計(jì)算過(guò)程，都過(guò)于復(fù)雜。

為此，本文提出以參數(shù)曲線切矢量模的最大和最小值的比與1的接近程度作為衡量參數(shù)化是否為最優(yōu)的評(píng)判標(biāo)準(zhǔn)，并在此標(biāo)準(zhǔn)下構(gòu)造出任意一段二次曲線的最優(yōu)或逼近最優(yōu)的有理參數(shù)化方程。大量實(shí)例表明，本文方法可以達(dá)到或接近于最優(yōu)標(biāo)準(zhǔn)，且計(jì)算量小，效率高，具有較強(qiáng)的自適應(yīng)性。

1 本文算法

在 CAGD和 CG中常用到代數(shù)曲線的某一段，而不是整條曲線。本算法基本解決了平面二次代數(shù)曲線上任一段曲線的最優(yōu)參數(shù)化問(wèn)題。

1.1 最優(yōu)參數(shù)化

1.2 算法描述

算法的基本思想是：過(guò)A點(diǎn)構(gòu)造一簇直線，參數(shù)方程P(t)即是這簇直線和代數(shù)曲線f ( x,y)=0的異于A的交點(diǎn)。

由于曲線 C : f( x, y) = 0 過(guò)A點(diǎn)，其方程可寫成以下形式

這條直線與曲線 f (x,y) =0有 2個(gè)交點(diǎn)，其中之一為點(diǎn)A。從而，由式(1)、(3)可得曲線段AB對(duì)應(yīng)于參數(shù)[0,1]的二次有理參數(shù)方程

定理 1 對(duì)于一段圓弧，橢圓或雙曲線上的具有對(duì)稱性質(zhì)部分的有理參數(shù)化，用本文算法得到的就是按1.1節(jié)中評(píng)判標(biāo)準(zhǔn)的最優(yōu)結(jié)果。

證 明 在二次代數(shù)曲線上任取一個(gè)異于AB的點(diǎn)E，F(xiàn) =(1-t)A+tB(t∈[0,1])是線段AB上的點(diǎn)，經(jīng)過(guò)點(diǎn)E、F的直線與二次曲線必有二個(gè)交點(diǎn)，P(t)即是這簇直線和代數(shù)曲線f(x,y)= 0 的異于E的交點(diǎn)。這個(gè)過(guò)程可以解釋為，以E為視點(diǎn)，弧AB在線段AB上的透視投影。事實(shí)上，二次代數(shù)曲線的任意有理參數(shù)化都可以按上述方式解釋。顯然，若弧AB有對(duì)稱性，當(dāng)E取為AB的垂直平分線與二次曲線的不在弧AB上的交點(diǎn)時(shí)，為最優(yōu)的有理參數(shù)化表示。此最優(yōu)的參數(shù)化表示與將入方程(4)得到的結(jié)果相同。

證畢。

當(dāng)θ＞90°時(shí)，即AB曲線段相對(duì)彎曲較大時(shí)，任意的有理參數(shù)化結(jié)果都不理想，例如，對(duì)3/4圓弧，此情況下，可對(duì)其分段后再進(jìn)行有理參數(shù)化。

2 實(shí)例分析

2.1 實(shí)例 1

t等距選取時(shí)計(jì)算出的參數(shù)點(diǎn)如圖1中實(shí)心較大方點(diǎn)所示, 此時(shí)

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

2.2 實(shí)例 2

用傳統(tǒng)有理參數(shù)化方程，即

圖2 橢圓弧的參數(shù)化對(duì)比效果

t等距選取時(shí)計(jì)算出的參數(shù)點(diǎn)如圖2實(shí)心較大方點(diǎn)所示, 此時(shí)Γ(P(t))≈1.23。

3 結(jié) 論

本文提出了新的平面代數(shù)曲線最優(yōu)有理參數(shù)化的評(píng)判標(biāo)準(zhǔn)。從理論上講，最優(yōu)有理參數(shù)化方程可求，但是計(jì)算量非常巨大。本文構(gòu)造出平面二次代數(shù)曲線上任一段曲線的十分接近于最優(yōu)的有理參數(shù)化方程，所用計(jì)算量小，效率高，具有較強(qiáng)的自適應(yīng)性。特別是當(dāng)所求曲線段是一段圓弧，或者是橢圓或雙曲線上的具有對(duì)稱性質(zhì)的部分時(shí)，得到的就是按1.1節(jié)中評(píng)判標(biāo)準(zhǔn)的最優(yōu)有理參數(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(4):309-321.

[2]Sendra J R, Winkler F. Symbolic parametrization of curves [J]. Symbolic Computation, 1991, 12(6):607-631.

[3]Hoeij M V. Computing parameterizations of rational algebraic curves [C]//Conf. ISSAC’94, Oxford, 1994:187-190.

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

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

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

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

[8]白鴻武, 葉正麟, 王樹(shù)勛, 等. Bézier曲線的重新參數(shù)化[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2007,19(12): 1576-1579.

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

[10]Farouki R T. Optimal parameterizations [J]. Computer Aided Geometric Design, 1997, 14(2): 153-16.