楊 勝， 雍俊海

（1. 清華大學(xué)軟件學(xué)院，北京 100084； 2. 清華大學(xué)計算機(jī)科學(xué)與技術(shù)系，北京 100084； 3. 信息系統(tǒng)安全教育部重點實驗室，北京 100084； 4. 信息科學(xué)與技術(shù)清華大學(xué)國家實驗室，北京 100084 5. 第三軍醫(yī)大學(xué)計算機(jī)教研室，重慶 400038）

裁剪面是指定義在參數(shù)曲面上的一片單連通區(qū)域。作為IGES標(biāo)準(zhǔn)的基本幾何體素之一，裁剪面已被廣泛應(yīng)用于實體造型和曲面造型系統(tǒng),參與各種計算[1-4]。裁剪面的計算是實體造型系統(tǒng)的基礎(chǔ)，影響著整個系統(tǒng)的效率和穩(wěn)定性[5]。

裁剪面的計算，總是受到幾何參數(shù)表示誤差和數(shù)值計算誤差的影響。目前，參數(shù)域曲線一般沒有精確的數(shù)學(xué)表示，常用線段、折線或自由曲線等近似表示。根據(jù)曲面上的點計算其對應(yīng)的參數(shù)(又稱為反求參數(shù))，數(shù)值方法通常存在計算誤差；同時，曲面上的點與其參數(shù)的對應(yīng)關(guān)系存在一對多的情形（如封閉曲面縫合邊上的點或極點，對應(yīng)多個參數(shù)值）。這些因素使得建立或修改裁剪面的拓?fù)潢P(guān)系相當(dāng)困難，相應(yīng)的文獻(xiàn)也非常少。因此，尋找穩(wěn)定處理裁剪面的算法，顯得特別重要。

正如文獻(xiàn)[6]所指出，許多針對參數(shù)曲面的算法，并不適用于裁剪面。對于不同參數(shù)表示的互相轉(zhuǎn)換問題，參數(shù)曲面著重于重新參數(shù)化[7-8]，建立重新參數(shù)化公式即可；但裁剪面的表示轉(zhuǎn)換還需要處理：① 計算曲面上曲線對應(yīng)的參數(shù)域曲線；② 重新確定裁剪面的拓?fù)潢P(guān)系。在此過程中，充分利用原有的拓?fù)湫畔?、避免重新建立拓?fù)潢P(guān)系成為轉(zhuǎn)換算法能否穩(wěn)定的關(guān)鍵。

針對裁剪面的參數(shù)表示轉(zhuǎn)換問題，本文首先確定參數(shù)變換對表示信息的影響，然后給出幾何與拓?fù)湫畔⒁恢碌膮?shù)變換的算法。本文還建立了裁剪球面轉(zhuǎn)換問題的參數(shù)變換關(guān)系，具體給出了轉(zhuǎn)換問題的解決方法；對于需要數(shù)值法反求參數(shù)的情形，給出了實現(xiàn)單值映射的算法。

1 裁剪面的參數(shù)變換

設(shè)I=[0,1], D=I×I, S：D→R3為連續(xù)映射，S(D)稱為參數(shù)曲面（或完整面）；若D1?D為單連通區(qū)域，S(D1) 稱為裁剪（參數(shù)）面。根據(jù)IGES標(biāo) 準(zhǔn)[9]，裁剪面的表示信息包括：① 對應(yīng)的參數(shù)曲面（完整面）；② 參數(shù)曲面上的曲線(邊)；③ 映射到邊的參數(shù)域曲線（環(huán)邊）；④ 環(huán)邊的連接關(guān)系（環(huán)）；⑤ 環(huán)之間的包含關(guān)系（面）。標(biāo)準(zhǔn)還規(guī)定了環(huán)的方向：外環(huán)為逆時針，內(nèi)環(huán)為順時針。

裁剪面的參數(shù)域信息分為幾何與拓?fù)湫畔刹糠?，其中幾何信息起決定性作用。一旦修改了參數(shù)域的曲線，一般需要重新建立幾何元素的拓?fù)潢P(guān)系。如下定義的參數(shù)變換是一種常見的參數(shù)修改形式。

定義1 若 f, g：I→I為可逆連續(xù)映射，則稱T：D→D，(s, t) = T(u, v) = ( f(u), g(v))為參數(shù)變換。

設(shè)S(u, v)為曲面的一種參數(shù)表示。

定義1中的參數(shù)變換具有可逆、參數(shù)u和v的變換可分離的特點。

命題1 對裁剪面的參數(shù)域進(jìn)行參數(shù)變換，該變換具有下述性質(zhì)：

（1） u（或v）向等參線，經(jīng)過變換后為s（或t）向等參線；

（2） 不相交的兩條曲線，經(jīng)過變換后也不相交；

（3） 環(huán)經(jīng)過變換后仍為環(huán)；

（4） 內(nèi)環(huán)經(jīng)過變換后仍為內(nèi)環(huán)；

（5） 當(dāng)f, g 同為增函數(shù)或減函數(shù)，環(huán)方向經(jīng)過變換后不變；

（6） 若f, g 變換為非線性變換，變換后曲線類型改變。

針對裁剪面參數(shù)域曲線表示的特點，特作如下定義。

定義2 設(shè)t∈I, C(t)為裁剪面參數(shù)域曲線，對C(t)進(jìn)行變換定義為：

（1） C(t)為等參線 對端點進(jìn)行變換；

（2） C(t)為折線多邊形 對端點和連接點進(jìn)行變換；

（3） C(t)為自由曲線并且變換為線性變換 對控制點進(jìn)行變換；

（4） 其他情形 首先離散C(t)為折線多邊形，然后對折線多邊形的端點和連接點進(jìn)行變換，最后修改C(t)的曲線類型為折線多邊形。

定義3 設(shè)t∈I, C(t)和P(t)為參數(shù)曲線。如果P(t) = C(1-t)，則稱P(t)為C(t)的反轉(zhuǎn)曲線；L = {l1(t), l2(t), …, ln(t)}為參數(shù)曲線的有序集合，則稱{ln(1-t), ln-1(1-t), …, l1(1-t)}為L的反轉(zhuǎn)。

至此，可得到對裁剪面參數(shù)域進(jìn)行變換的算法。

算法1 裁剪面的參數(shù)變換

輸 入裁剪面，命題1 中確定的參數(shù)變換

輸 出變換后的裁剪面

步驟1 對參數(shù)域曲線進(jìn)行變換。

步驟2 如果u 向和v 向變換函數(shù)同為增函數(shù)或減函數(shù)，結(jié)束。

步驟3 曲面上的曲線反轉(zhuǎn)（或者調(diào)整環(huán)邊與邊的方向關(guān)系，如同向→反向，反向→同向）。

步驟4 環(huán)反轉(zhuǎn)。

2 裁剪球面的表示轉(zhuǎn)換

二次裁剪面由幾何參數(shù)表示轉(zhuǎn)換為Nurbs 表示，是裁剪面求交、變形等操作的基礎(chǔ)。下面以裁剪球面為例，利用參數(shù)變換的方法，實現(xiàn)兩種不同參數(shù)表示形式的互相轉(zhuǎn)換。

球面的Nurbs 表示，u 向通常采用7 點法表示圓、v 向采用9 點法的半圓表示（見圖1）。為此，建立球面參數(shù)域的轉(zhuǎn)換關(guān)系。

圖1 Nurbs 表示圓和半圓

引理1 設(shè)單位半圓弧的幾何參數(shù)表示為

C ( t ) = (cosπ t , sinπ t ), t∈[0,1] 該圓弧的三階Nurbs 表示為

其中 Ni,2(u)和 Ri,2(u)分別為B 樣條基函數(shù)和 有理樣條基函數(shù)，P(u)的控制點、權(quán)重和節(jié)點向量分別為

則兩種表示方法的參數(shù)轉(zhuǎn)換關(guān)系為(t, u∈[0,1])

由引理1 以及Nurbs 表示的對稱性，可得到單位圓幾何參數(shù)表示與7 點法Nurbs 表示的參數(shù)轉(zhuǎn)換關(guān)系。

定理1 設(shè)單位圓的幾何參數(shù)表示為

C ( t ) = (cos2π t , sin 2π t ), t∈[0,1]

該圓的三階Nurbs 表示為[8-9]

其中 Ni,2(u)和 Ri,2(u)分別為B 樣條基函數(shù)和 有理樣條基函數(shù)，控制點、權(quán)重和節(jié)點向量分別為

{Pi} = {(1, 0), (1, 1), (-1, 1), (-1, 0), (-1,-1), (1,-1), (1,0)}，{wi} = {1, 0.5, 0.5, 1, 0.5, 0.5, 1}，

U = {0, 0, 0, 0.25, 0.5, 0.5, 0.75, 1, 1, 1}

則兩種表示方法的參數(shù)轉(zhuǎn)換關(guān)系為(t, u∈[0,1])

其中

定理1 給出了單位圓幾何參數(shù)表示轉(zhuǎn)換為Nurbs 表示的參數(shù)轉(zhuǎn)換關(guān)系。為避免奇異情形的出現(xiàn)，該關(guān)系表示為分段函數(shù)的形式。同理，可得到半圓的幾何參數(shù)表示與5 點法Nurbs 表示的參數(shù)轉(zhuǎn)換關(guān)系。

定理2 設(shè)單位半圓弧的幾何參數(shù)表示為

該圓弧的三階Nurbs 表示為[8-9]

其中 Ni,2(u)和 Ri,2(u)分別為B 樣條基函數(shù)和 有理樣條基函數(shù)，控制點、權(quán)重和節(jié)點向量分別為

則兩種表示方法的參數(shù)轉(zhuǎn)換關(guān)系為(t, u∈[0,1])

其中

由定理6 和定理7，裁剪球面由幾何參數(shù)表示轉(zhuǎn)換為Nurbs 表示（參見文獻(xiàn)[10-11]），其實現(xiàn)算法如下。

算法2 裁剪球面的幾何參數(shù)表示轉(zhuǎn)換為Nurbs 表示

輸 入幾何法表示的裁剪球面

輸 出Nurbs 表示的裁剪面

步驟1 修改曲面為Nurbs 表示

步驟2 對參數(shù)域進(jìn)行變換，其中u→s 轉(zhuǎn)換關(guān)系為式(3)，v→t 轉(zhuǎn)換關(guān)系為式(5)。

同理，裁剪球面由Nurbs 表示轉(zhuǎn)換為幾何參數(shù)表示，由轉(zhuǎn)換關(guān)系式(4)和式(6)可得到相應(yīng)的轉(zhuǎn)換算法。對于其他復(fù)雜的參數(shù)表示轉(zhuǎn)換，如裁剪球面轉(zhuǎn)換為高階的Nurbs 形式，直接給出參數(shù)轉(zhuǎn)換的公式相當(dāng)困難；然而，確定變換函數(shù)的單調(diào)性卻比較容易。不妨設(shè)u 向和v 向的變換函數(shù)同為增函數(shù)，應(yīng)用命題2 可得出利用數(shù)值法計算變換參數(shù)的算法，實現(xiàn)參數(shù)之間的單值映射。

算法3 數(shù)值方法的參數(shù)變換

輸 入原有曲面表示S(u, v)及其裁剪面上的參數(shù)點(u0, v0)，轉(zhuǎn)換后曲面表示P(s, t)。

輸 出轉(zhuǎn)換后裁剪面上對應(yīng)的參數(shù)點 (s0, t0)。

計算點Q = S(0.5, v0), 數(shù)值法計算s0, t0使得 P(s0, t0) = Q。

計算點Q = S(u0, 0.5), 數(shù)值法計算s0, t0使得P(s0, t0) = Q。

計算點Q = S(u0, v0), 數(shù)值法計算s0, t0使得P(s0, t0) = Q。

3 結(jié) 束 語

保持裁剪面的形狀不改變的前提下，對參數(shù)域信息進(jìn)行修改是實體造型中經(jīng)常需要的操作。本文由此總結(jié)出可逆、u 向和v 向的變換可分離的參數(shù)變換。首先，給出了該變換對裁剪面表示信息的影響；然后，提出了對裁剪面參數(shù)域進(jìn)行變換的算法。該算法不需要重新建立裁剪面的拓?fù)潢P(guān)系，直接對原有數(shù)據(jù)進(jìn)行調(diào)整，確保了變換后裁剪面幾何信息與拓?fù)湫畔⒌囊恢滦?。對于不同表示形式的互相轉(zhuǎn)換問題，給出了裁剪球面參數(shù)轉(zhuǎn)換公式以及利用參數(shù)變換的解決方法，用實例對該算法的有效性進(jìn)行了驗證。

本文提出的參數(shù)變換方法，還可以應(yīng)用到其他二次裁剪面的參數(shù)表示轉(zhuǎn)換、裁剪面的鏡像變換、裁剪面的合并等問題。下一步擬運用本文的方法處理實體拔模、裁剪面變形等操作下的參數(shù)域修改問題。

[1] Casale M S. Free-form solid modeling with trimmed surface patches [J]. IEEE Computer Graphics and Applications, 1987, 7(1)： 33-43.

[2] Farouki R T. Trimmed-surface algorithms for the evaluation and interrogation of solid boundary representations [J]. IBM Journal of Research and Development, 1987, 31(3)： 314-334.

[3] Piegl L A. Geometric method of intersecting natural quadrics represented in trimmed surface form [J]. Computer-Aided Design, 1989, 21(4)： 201-212.

[4] Piegl L A, Richard A M. Tessellating trimmed NURBS surfaces[J]. Computer-Aided Design, 1995, 27(1)： 16-26.

[5] 劉曉強(qiáng), 唐榮錫. 實體造型技術(shù)的現(xiàn)狀與發(fā)展趨勢[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 1997, 9(3)： 284-287.

[6] 胡事民, 孫家廣, 汪國昭. 基于廣義離散分解trimmed 曲面[J].計算機(jī)學(xué)報, 1999, 22(3)： 296-301.

[7] Farin G. From conics to NURBS： a tutorial and survey [J]. IEEE Computer Graphics and Applications, 1992, 12(5)： 78-86.

[8] 楊義軍, 雍俊海. 有理Bézier 曲面的標(biāo)準(zhǔn)化[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2007, 19(2)： 245-250.

[9] Reed K. The initial graphics exchange specification (IGES) version 6.0 [S]. NISTIR 4412, National Institute of Standards, 1998.

[10] Piegl L A, Tiller W. The nurbs book [M]. New York： Springer, 1997. 295-307.

[11] 施法中. 計算機(jī)輔助幾何設(shè)計與非均勻有理B樣條[M]. 北京： 高等教育出版社, 2001. 435-443.