韓 林 劉 斌

華僑大學，廈門，361021

0 引言

在幾何造型中，曲面上的曲線設計是一項重要的內容。參數(shù)曲面上的曲線表達研究越來越多［1-3］，但對于網(wǎng)格曲面上的曲線，尚沒有理想的表示和設計方法。隨著計算機輔助設計和現(xiàn)代制造業(yè)的發(fā)展，由平面和參數(shù)曲面表示的傳統(tǒng)規(guī)則特征已遠遠不能滿足現(xiàn)代工業(yè)產品設計在外形上的要求，尤其是在計算機動畫、數(shù)字影視制作，以及柔性制品的交互設計中，參數(shù)曲面造型更是存在較多空白。三角網(wǎng)格模型能夠表示任意復雜形狀，以其獨特優(yōu)勢成為主流表示方法之一，故研究網(wǎng)格曲面上曲線的設計方法與配套技術具有適用價值和理論意義。

國內外學者對曲面上曲線的生成方法已有一些研究：Hofer等［4］給出了一種光滑流形曲面上三次樣條曲線的生成方法；Rodriguez等［5］、Park等［6］將De Casteljau算法應用于簡單的流形曲面；Morera等［7］給出了測地Bezier曲線的生成方法；杜宏云［8］在文獻［6］的基礎上給出了測地自由曲線的生成算法；朱文明等［9］從細分的角度構造出流形曲面上的細分曲線。劉斌等［10］提出了一種插值于流形網(wǎng)格曲面上給定點列的測地B樣條曲線生成方法，該方法以網(wǎng)格曲面上兩點間的最短測地線代替歐氏空間中的兩點間直線，將歐氏空間中的德布爾算法拓展到曲面空間，形成與經典B樣條曲線具有統(tǒng)一表示形式的曲面上自由曲線的表達形式。由于測地B樣條具有局部控制性、凸包性等優(yōu)點，故本文以文獻［10］所提出的方法來生成網(wǎng)格上的自由曲線，進行交互操作。

欲實現(xiàn)測地B樣條曲線在彎曲空間中的基本交互操作，使其類似于B樣條曲線在歐氏空間中的基本操作，例如平移、旋轉、縮放等，有效方法之一就是網(wǎng)格參數(shù)化的方法。三角網(wǎng)格參數(shù)化是對這些三角網(wǎng)格幾何和拓撲信息進一步處理的基礎［11］，各種各樣的參數(shù)化方法研究一直是計算機圖形學的熱點。通過分析各種參數(shù)化方法的優(yōu)缺點，發(fā)現(xiàn)離散指數(shù)映射近似法［12］計算高效，而且在局部范圍內保留了三維空間中每一點的距離與方向不變的特性，將其應用于實時交互操作與復用設計，具有獨特的優(yōu)勢。

本文在分析上述領域研究現(xiàn)狀的基礎上，把指數(shù)映射參數(shù)化的方法引入到網(wǎng)格曲面上自由曲線的設計中，提出一種網(wǎng)格曲面上測地B樣條曲線的復用操作方法（主要包括平移、旋轉、縮放等），為優(yōu)秀設計成果的保存和重用提供了支持，提高了形狀設計的智能程度和效率。

1 離散指數(shù)映射

1.1 指數(shù)映射

在曲面S：r＝r（u1，u2）上取定一點p，p點的切平面為Tp，任取切向量v∈Tp，作測地射線Cp，v從p點出發(fā)并且以v／｜v｜為初始切向，則Cp，v由p和v／｜v｜唯一確定，如圖1所示。

圖1 曲面S上點P處的指數(shù)映射

取Cp，v的正向弧長s參數(shù)化ui（s），i＝1，2，使p點在S 上的曲線坐標為（u1（0），u2（1））。定義映射：

即像點Qs＝r（u1（s），u2（s））是CP，v上從p點出發(fā)且經過弧長s后到達的點。由此定義映射為

則此映射稱為曲面S上點p處的指數(shù)映射［13］。

指數(shù)映射expp本質上就是在p點附近的曲面上產生一個二維的坐標系統(tǒng)，將曲面S上的點映射到p點的切平面Tp上，并稱p點為種子點。對任一單位向量v∈Tp來說，都存在一個用弧長來參數(shù)化的測地線gv，使得gv（0）＝p 且g′（0）＝v。對p點周圍相鄰的任一鄰域點Q而言，都會有唯一的測地線gv通過它。因此，Q可用極坐標（ρ，φ）映射到Tp上，ρ是從p到Q的測地線距離，φ是v在TP上的極角，這就是測地極坐標表示形式。極坐標可在Tp上被任意一個正交基底｛η1，η2｝表達成法坐標（u，v），也可以將其看成二維向量e＝（u，v），此二維向量稱為測地線向量。本文中，這2個概念將不加區(qū)分地使用，法坐標為坐標表示形式，測地線向量為向量表示形式。指數(shù)映射參數(shù)化的關鍵步驟就是求取曲面上任意一點到種子點的測地線向量。

1.2 離散型指數(shù)映射逼近

對于網(wǎng)格曲面，為了近似得到曲面S上點p處的指數(shù)映射，若按定義，需要計算曲面上其他點q相對于點p的測地線距離和極角。測地線的計算成本較高，因此，本文采用Schmidt等［12］提出的離散指數(shù)映射逼近法進行測地線的計算，該方法并不具體計算點q到點p的曲面測地線和極角，而是先由Dijkstra算法產生分段線性測地線向量，再通過這些測地線向量疊加，計算點q在點p切平面上的法坐標。

假設網(wǎng)格曲面上有3點，分別為p、r、q，如圖2所示。p到r的測地線向量up，r和r到q的測地線向量ur，q已知，而p到q的測地線向量未知。目標是求取up，q＝expp（q），即點q在切平面Tp上的法坐標。在線性系統(tǒng)中存在

圖2 離散指數(shù)映射逼近

由于（up，q-up，r）未知，用ur，q的一個相關量來代替（up，q-up，r）。具體方法是，將原來用Tr的三維基底（xr，yr，zr）表示的ur，q用Tp的三維基底（xp，yp，zp）來表示。首先，設點p、r處的法矢分別為np與nr，將Tr沿著nr與np的叉積方向（nr×np）旋轉兩矢量之間的夾角α，此時Tr與Tp共面，Tr的基底變成（x′r，y′r，np）；然后，再將Tr沿著np的方向旋轉角度θp，r＝arccos（x′r·xp），從而Tr與Tp具有相同的三維基底。經過兩次旋轉后，Tr上的ur，q就可以用Tp的基底來表示。由于up，r與ur，q都是二維向量，可以忽略第一次旋轉對ur，q造成的影響，因此，up，q的近似值可表示為

式中，Rot2 D（θp，r）表示二維旋轉變換。

雖然用式（2）通過測地線向量旋轉、疊加求取的up，q與實際的三維網(wǎng)格上測地線向量的值會存在誤差（圖2），但是若不謀求網(wǎng)格全局參數(shù)化，只考慮局部映射，精度是能夠保證的，原因是此方法采用了式（2）這樣的矢量疊加，而不是以標量運算。通過式（2）的延伸，就可以近似求出點p局部鄰域網(wǎng)格上每一個頂點在Tp上的測地線向量。

1.3 法坐標歸一化

基于指數(shù)映射的曲線交互設計方法需要確定種子點p和區(qū)域半徑R，如圖3所示。種子點作為算法向外擴張的起始點，種子點的切平面與參數(shù)平面共面；區(qū)域半徑R是種子點到區(qū)域范圍內最遠點的測地線距離，R既決定了區(qū)域的范圍，又是算法的停止條件。計算出區(qū)域內的所有頂點的測地線向量后，便得到了區(qū)域內頂點的法坐標，然后將法坐標進行幾何縮放和平移變換。其中，比例變換矩陣為

平移變換矩陣為

通過2次變換將所有頂點的法坐標映射到［0，1］×［0，1］的參數(shù)空間中。

圖3 法坐標歸一化

2 測地B樣條曲線交互操作

用戶在網(wǎng)格曲面上進行測地B樣條曲線的編輯時，希望看到測地B樣條曲線在網(wǎng)格曲面上的滑動、旋轉和縮放等變換，且要滿足實時交互性。基于這些要求，本文首先在網(wǎng)格模型上輸入型值點，然后插值測地B樣條曲線（圖4a）；其次，在網(wǎng)格模型上選出一塊區(qū)域，該區(qū)域（稱之為源區(qū)域）必須完全覆蓋測地B樣條曲線，按照指數(shù)映射參數(shù)化的方法計算該區(qū)域內測地B樣條曲線控制頂點的法坐標（圖4b）；最后，通過選擇或改變網(wǎng)格模型上區(qū)域（稱之為興趣區(qū)域）的位置、方向或大小實現(xiàn)測地B樣條曲線的重用編輯（圖4c）。結果如圖4d所示。

圖4 曲線交互操作復用流程

2.1 測地B樣條曲線的生成

在網(wǎng)格曲面上生成k次測地B樣條曲線的算法思路是：首先給定三角網(wǎng)格曲面模型G和位于網(wǎng)格曲面上的m＋1個型值點Qj∈G（j＝0，1，…，m）；其次，由各型值點之間的最短測地距離按照積累弦長參數(shù)化方法進行數(shù)據(jù)參數(shù)化，得到各型值點的參數(shù)值，類似于經典B樣條插值理論，在端點處取k＋1重節(jié)點的固支條件，且取規(guī)范定義域，這樣可得欲求曲線的節(jié)點矢量，然后由插值條件確定歐氏空間中各控制頂點；最后，將得到的控制頂點投影到網(wǎng)格曲面上，按擴展德布爾算法得到初始測地B樣條曲線，計算各插值點到其在曲線上對應點的測地距離，即插值誤差，按照誤差反向補償策略，更新型值點，重復上述過程，直至誤差滿足精度要求為止。生成B樣條曲線的同時，把計算出的控制頂點按順序存取，作為后續(xù)步驟的重要信息。

2.2 源區(qū)域選擇和控制頂點參數(shù)化

2.2.1 源區(qū)域參數(shù)化

生成測地B樣條曲線之后，需要進行源區(qū)域的選擇及參數(shù)化源區(qū)域，其關鍵步驟是求取源區(qū)域內任意一點到種子點的測地線向量。

3D網(wǎng)格上的每一個頂點與其所有1-ring鄰域頂點之間的測地線距離，即為連接兩點的邊的長度，因此其所有1-ring鄰域頂點的測地線向量可以很輕易地計算出來。如圖5所示，對于頂點p的1-ring鄰域頂點q，利用旋轉的方式將向量vp，q沿著vp，q與p的切平面法向量np的外積方向旋轉至p的切平面上，這樣既可以得到q點的方向，又能保持p、q之間的距離不變。然后將旋轉過后的三維向量，以切平面上一組正交基底｛xp，yp｝表示成二維向量up，q，up，q即為q點在p的切平面上的測地線向量。

圖5 網(wǎng)格頂點1－ring鄰域的測地線向量

本文以每個頂點的任意一個1-ring鄰域頂點來建立基底。假設一平面Tp由一組正交基底｛η1，η2｝所生成，則在Tp上的某點q與平面的原點p所形成的向量l可表示為

式（3）中，因u、v為標量，η1、η2都是單位向量，故u、v可分別表示為

二維向量up，q＝（u，v）即為q點在Tp上的測地線向量。用同樣的方法可求取源區(qū)域內所有頂點1-ring鄰域的測地線向量。

按照前述離散指數(shù)映射理論，若種子點到源區(qū)域任意頂點的路徑已知，便可利用向量的旋轉疊加得到種子點到源區(qū)域任意頂點的測地線向量。

如圖6所示，假設種子點為p，利用Dijkstra最短路徑方法得到p到網(wǎng)格上源區(qū)域內任一頂點q的最短路徑｛p0，p1，…，pm｝，p0＝｜p｜且pm＝｜q｜，之后沿著最短路徑不斷地將每個切平面上的測地線向量轉換到Tp的基底上，且其q點的測地線向量可表示為

圖6 種子點p到網(wǎng)格上任意頂點q的測地線向量

須注意的是：二維向量upi，pi＋1是用直接轉換成起始點的切平面Tp的基底來表示的，而非前一個切平面Tpi-1的基底。如果通過前一個切平面進行轉換的話，則會增大誤差積累［12］。

計算出源區(qū)域內種子點到所有頂點的測地線向量后，即可對其進行法坐標歸一化處理，使所有頂點的法坐標映射到u∈ （0，1），v∈ （0，1）的范圍中。網(wǎng)格曲面上三角面內部點的法坐標可通過其所在的三角面片的重心坐標求取。

2.2.2 曲線控制頂點參數(shù)化

曲線控制頂點一般不會剛好位于網(wǎng)格曲面的頂點上，一般情況下都位于三角面片內部（包括位于三角面邊上），這時可用其所在三角面片3個頂點的法坐標和該點的三角形重心坐標求取該點的法坐標。如圖7所示，設曲線控制頂點P位于網(wǎng)格曲面的三角面片△ABC內，3個頂點的測地向量分別為a、b、c，P點在三角面片內，A、B、C3個頂點的重心坐標u、v、w可分別表示為

則P點的測地線向量可以表示為

計算曲線所有控制頂點的法坐標（測地向量）并將其存儲備為曲線操作的基礎數(shù)據(jù)。

2.3 參數(shù)匹配

無論是曲線的滑動遷移，還是旋轉縮放，在操作過程中，測地B樣條曲線各控制頂點的法坐標應始終保持不變，改變的只是興趣區(qū)域的位置、方向和大小。選定興趣區(qū)域后的主要任務就是從興趣區(qū)域中找到源區(qū)域的對應點，使其與源區(qū)域一一對應。

圖7 △ABC的內點P的重心坐標

圖8 源區(qū)域G1與興趣區(qū)域G2的參數(shù)化

如圖8所示，假設源區(qū)域為G1，興趣區(qū)域為G2，B樣條曲線上n個控制頂點為pi∈ ｛p0，p1，…，pn｝，兩區(qū)域的方向和大小都沒有改變，只是位置平移。兩區(qū)域是同一網(wǎng)格的不同位置，很難保證兩區(qū)域的網(wǎng)格具有相同的三角面片個數(shù)和相同的連接關系，為此提出一種拓撲不同的三角網(wǎng)格區(qū)域參數(shù)匹配的快速算法，具體步驟如下：

（1）按照參數(shù)化源區(qū)域G1的方法，將興趣區(qū)域G2參數(shù)化。保存G2內所有頂點的法坐標，以此建立k-d樹。搜索G2參數(shù)域內與pi的法坐標（ui，vi）最近的頂點，以該頂點的1-ring鄰接三角形為候選搜索集，求出pi在興趣區(qū)域G2的對應點p′i所在的三角面片 △abc。

（2）取出△abc 3個頂點的法坐標，用這3個法坐標建立虛擬三角形，稱之為該三角面片的參數(shù)三角形。由第（1）步可知，（ui，vi）一定落在△abc的參數(shù)三角形內部（包括落在三角形邊上的情況），利用類似于前述重心坐標的求解方法，得到（ui，vi）在參數(shù)三角形中的重心坐標。

（3）由重心坐標和三角形3個頂點的三維空間坐標，即可計算出p′i的三維空間位置，即pi在興趣區(qū)域中的對應點。

計算出B樣條曲線各個控制頂點在興趣區(qū)域中的對應點之后，按照拓展德布爾算法再生成測地B樣條曲線，就完成了曲線的滑動平移操作。

每一個興趣區(qū)域都是基于種子點、方向及半徑產生的，只要改變興趣區(qū)域的半徑范圍，再以上述步驟重新計算B樣條曲線的控制頂點的法坐標，就可以實現(xiàn)縮放的效果。測地B樣條曲線的旋轉則是將興趣區(qū)域種子點切平面的正交基底｛η1，η2｝沿著切平面的法向量旋轉一個角度，再以上述步驟重新計算B樣條曲線的控制頂點的法坐標的過程。

3 試驗結果與分析

本文通過實例展示算法的結果，主要考慮了算法在各種曲面上的適應性和視覺效果，并對曲線的復用交互設計速度進行了探討分析。

3.1 算法的適應能力及其視覺效果

本文算法使用Microsoft Visual Studio 2008開發(fā)工具和OpenGL函數(shù)庫，在CPU為2.26GHz、內存為2.0GB的PC機上實現(xiàn)，部分結果如圖9所示。圖9a中的曲線位于半球面上，用于測試曲線變換后的視覺效果；圖9b中的帽子模型中部凸起，用于測試曲線在曲率變化較大的曲面上的適應性；圖9c和圖9d為圓鼓和圓臺模型，用于測試各種曲線在具有尖銳特征的曲面上的適應性。試驗結果表明，本文提出的曲面上測地B樣條曲線的復用方法視覺效果良好，曲線對曲面的適應性較強。

3.2 時間效率

良好的視覺效果和較強的適應性是算法的基本要求，要應用于實際工程，還須滿足實時交互的要求，即算法時間應該控制在一定范圍內。為此，選擇圖10所示的Shoe模型和Venus模型作為試驗對象，試驗不同曲線圖形在兩模型中的重用時間。另外，針對本文提出的僅計算局部區(qū)域的快速參數(shù)匹配算法，與計算整個網(wǎng)格區(qū)域的非快速算法進行了時間效率比較，試驗數(shù)據(jù)如表1所示。

從表1中的數(shù)據(jù)可以看出，快速參數(shù)匹配的時間要比非快速參數(shù)匹配的時間低一個數(shù)量級，網(wǎng)格規(guī)模愈大，快速參數(shù)匹配的優(yōu)越性愈明顯。圖10a圖形和圖10b圖形都位于Shoe模型上，但圖10b圖形的匹配時間為圖10a圖形的2倍，因圖10b的控制頂點為圖10a的2倍，變換時須增加匹配次數(shù)，故時間變長。匹配時間與控制頂點的個數(shù)之間基本上呈線性關系，通過Venus模型上的圖10c圖形和圖10d圖形可以進一步給予證實。圖10a圖形和圖10c圖形都為10個控制頂點，但后者所在的參數(shù)區(qū)域的頂點個數(shù)是前者的5倍多，導致圖10c圖形的匹配時間線性增加。圖10d圖形的匹配時間比圖10b長，也是此原因。

圖9 各種網(wǎng)格曲面上測地B樣條曲線圖形的交互操作

4 結論

（1）將指數(shù)映射理論引入網(wǎng)格模型的局部參數(shù)化，實現(xiàn)網(wǎng)格曲面上曲線的遷移、旋轉和縮放等操作，為曲面上曲線的復用和再設計奠定了基礎。

圖10 網(wǎng)格模型上測地B樣條曲線圖形的復用操作

表1 曲線插值迭代時間與模型的關系

（2）所采用的局部參數(shù)化方法計算效率高，變形小，不依賴于父網(wǎng)格模型的整體規(guī)模，能夠滿足實時交互設計要求。

（3）采用測地B樣條作為網(wǎng)格曲面上的曲線建模工具，曲線對曲面的適應性強。

（4）離散指數(shù)映射計算速度快，但由于存在積累誤差，不適宜于大范圍網(wǎng)格區(qū)域的計算，如何減小積累誤差的影響，有待于進一步的深入研究。

［1］藺宏偉，王國瑾.光滑曲面上的G1插值曲線［J］.計算機輔助設計與圖形學學報，2003，15（5）：541-546.

［2］馮結青，彭群生.基于插值的Bernstein多項式復合及其曲線曲面應用［J］.軟件學報，2002，13（10）：2014-2020.

［3］衛(wèi)煒，周來水，王志國.NURBS曲面上的曲線精確表達［J］.南京航空航天大學學報，2008，40（1）：85-88.

［4］Hofer M，Pottmann H.Energy-minimizing Splines in Manifolds［J］.ACM Trans.Graph.，2004，23（3）：284-293.

［5］Rodriguez R C，Leite F S，Jacubiak J.A New Geometric Algorithm to Generate Smooth Interpolating Curves on Riemannian Manifolds［J］.LMS Journal of Computation and Mathematics，2005，8：251-266.

［6］Park F C，Ravani B.Bezier Curves on Riemannian Manifolds and Lie Groups with Kinematic Applications［J］.ASME Journal of Mechanical Design，1995，117：36-40.

［7］Morera D M，Carvalho P C，Velho L.Modeling on Triangulations with Geodesic Curves［J］.The Visual Computer，2008，24（12）：1025-1037.

［8］杜宏云.測地自由曲線及其性質研究［D］.南京：航空航天大學，2008.

［9］朱文明，鄧建松，陳發(fā)來.應用保角映射構造流形上的細分曲線［J］.計算機輔助設計與圖形學學報，2007，19（1）：48-53.

［10］劉斌，黃常標，林俊義，等.流形網(wǎng)格曲面上測地B樣條插值［J］.機械工程學報，2011，47（19）：136-142.

［11］彭群生，胡國飛.三角網(wǎng)格的參數(shù)化［J］.計算機輔助設計與圖形學學報，2004，16（6）：731-739.

［12］Schmidt R，Grimm C，Wyvill B.Interactive Decal Compositing with Discrete Exponential Maps［J］.ACM Trans.Graph.，2006，25（3）：605-613.

［13］王幼寧.微分幾何講義［M］.北京：北京師范大學出版社，2007.