基于區(qū)域增長和三角分割的局部紋理映射算法

申世恒， 李柏巖， 劉曉強， 王府梅， 宋 暉

（1.東華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，上海 201620；2.東華大學(xué) 紡織學(xué)院，上海 201620）

在進(jìn)行三維虛擬物體展示時，通常采用真實二維圖像作為貼圖，通過紋理映射技術(shù)將其映射到三維物體模型表面，從而增強三維場景中虛擬物體的真實感。紋理映射通常是針對一個對象，整體進(jìn)行映射的，但在一些情況下，紋理映射只針對對象上一個小區(qū)域進(jìn)行，稱局部紋理映射。例如，在進(jìn)行織物虛擬展示時，需要對展示物指定位置進(jìn)行局部修飾、添加提花圖案等。

針對如何將一張貼圖恰當(dāng)?shù)赜成涞饺S模型指定的局部區(qū)域的問題，文獻(xiàn)［1］提出了基于極坐標(biāo)的方法，以三維物體上一點為中心，在保證與其鄰接點的方向和距離不變的情況下，求出鄰近點的紋理坐標(biāo)，并以鄰接點為中心點，繼續(xù)向周圍鄰接點進(jìn)行擴(kuò)展，保證紋理不會發(fā)生嚴(yán)重的扭曲；文獻(xiàn)［2－3］提出中心擴(kuò)散的方式，以一個種子面開始，采用廣度優(yōu)先搜索方法擴(kuò)散確定局部映射區(qū)域，該方法需手動控制映射區(qū)域，不能自動控制紋理映射區(qū)域，并且在局部細(xì)節(jié)處理上效果不太理想；文獻(xiàn)［4－6］提出基于中間面的方法，通過控制中間面，達(dá)到局部紋理映射的效果。該方法對于規(guī)則化的三維物體能給出很好的映射效果，但對于非參數(shù)化的不規(guī)則三維物體則不能保證很好的映射。關(guān)于紋理合成方法，文獻(xiàn)［7］提出一個快速有效的紋理合成方法，為局部紋理映射提供一種很好的拼接方法；文獻(xiàn)［8］提出一種圖像修復(fù)算法，實現(xiàn)對紋理失真的修復(fù)。

三維模型一般采用三角面為基本單位來進(jìn)行逼近模擬。本文也以三角面為基本的映射單位，通過選定一個基準(zhǔn)點，構(gòu)建一個基準(zhǔn)面，采用向周圍點進(jìn)行擴(kuò)張的方式，確定局部映射區(qū)域。對于相對較大的三角面片，采用一定的算法對其進(jìn)行分割，以控制區(qū)域映射有效范圍，防止過度映射的出現(xiàn)。

1 頂點紋理坐標(biāo)化

為將紋理映射到三維模型上，首先需要給模型的每一個頂點都分配一個合適的紋理坐標(biāo)。本文采用平面展開法，即通過選定基準(zhǔn)點，并以此基準(zhǔn)點所在平面作為一個基準(zhǔn)面，將此基準(zhǔn)面周圍包含基準(zhǔn)面頂點的三角面展平到此平面上，再計算每個頂點到基準(zhǔn)點的距離和方向，實現(xiàn)三維頂點的紋理坐標(biāo)化。

假設(shè)三角面PAB以頂點P為原點，對應(yīng)紋理中心坐標(biāo)點，以頂點P所在的一個面（設(shè)為T）為基準(zhǔn)面。對于所有包含頂點P的面上的頂點，利用下面介紹的方法，計算出各個點所對應(yīng)的紋理坐標(biāo)。

選取包含頂點P的三角面T作為基準(zhǔn)面，搜索模型中所有包含頂點P的面，對于其中任意一個面，及其面上的非P點的頂點A，計算出向量在平面T上的投影點A′，以及向量的模，然后利用、向量，以及用于控制紋理方向的紋理正向向量Qmap，求出A點的紋理坐標(biāo)。而對于三角面上另一頂點B，可以計算向量之間的角度α以及的模，即可以利用α求出B點在平面T上所對應(yīng)的B′及其紋理坐標(biāo)。通過已計算出紋理坐標(biāo)的頂點，再以此頂點所在面為基準(zhǔn)面，此點為基準(zhǔn)點，采用相同的方法計算出其周圍頂點的紋理坐標(biāo)，實現(xiàn)頂點紋理坐標(biāo)化。

首先需要確定用于紋理映射的基準(zhǔn)平面。假設(shè)用來確定基準(zhǔn)平面的方程為：

已知A點坐標(biāo)（x1，y1，z1），面法向量為（a，b，c），設(shè)A′坐標(biāo)為（x2，y2，z2）。通過求解聯(lián)立方程，即

可以得出i，從而求得A′的三維坐標(biāo)（x2，y2，z2）。

其次計算模型上相關(guān)點的紋理坐標(biāo)。通過計算點A′在平面T的坐標(biāo)，可以計算向量，假設(shè)與紋理正向向量Q夾角為θ，通過余弦

map定理可求出夾角的正弦與余弦值，即

2 確定映射區(qū)域

確定映射區(qū)域是實現(xiàn)局部紋理映射的關(guān)健。通過上述方法，可以將三維點展平在一個平面內(nèi)，并計算出各點對應(yīng)的紋理坐標(biāo)。在這個平面內(nèi)，以原點為圓心，紋理半徑R做圓，圓內(nèi)覆蓋的面，即為所要進(jìn)行映射的面。其中R的大小可在交互操作時由用戶確定，同時為了避免重復(fù)計算，通過記錄已映射的點與面，在進(jìn)行映射域擴(kuò)展過程中，對新擴(kuò)展的面進(jìn)行判斷，以使計算工作量最少。算法過程如下：

（1）建立容器V－Vert、V－Face和V－In，分別用來存儲已坐標(biāo)化的點、已映射的面和包含在映射范圍內(nèi)的點。選擇一個初始點作為中心點，加入到V－Vert中，并將此初始點紋理坐標(biāo)設(shè)為（0.5，0.5），并添加到 V－In中。

（2）搜索V－Vert，采用寬度優(yōu)先搜索法，當(dāng)V－Vert不為空時，取其中的第1個點。

（3）如果這個點在V－In中，對包含此點的面，若該面不在V－Face中，則利用前面介紹的方法，對面上的點進(jìn)行紋理坐標(biāo)化，并將這個面中沒有出現(xiàn)在V－Vert中的頂點加入其中，將該面加入V－Face中。對于任意一個已經(jīng)進(jìn)行了紋理坐標(biāo)化的頂點，記其紋理坐標(biāo)為（xv，yv），如果該紋理坐標(biāo)滿足公式R，則將該點加入容器V－In中。

（4）如果這個點不在V－In中，對于包含此點的面，若該面不在V－Face中，則進(jìn)行映射，并對面上其余點進(jìn)行紋理坐標(biāo)化，并把這些點加入V－Vert，把含有選定點的面記入V－Face。

（5）將該點從 V－Vert中刪除，返回步驟（2）。

重復(fù)執(zhí)行步驟（2）～（5），直至 V－Vert為空。根據(jù)這個方法，可以避免重復(fù)計算，并將紋理映射范圍圈定在一個合理的范圍之內(nèi)，以達(dá)到一個較好的局部紋理映射效果。

在進(jìn)行上述步驟的過程中，為避免將三角形都展開在一個平面所帶來的變形問題，本文采用局部平面展平法。對于選定的一個點，以其所在的一個平面作為基準(zhǔn)面，對每一個包含此點的三角面，取其法向量，并求取這些法向量的平均值作為法向量，并基于此點做基準(zhǔn)面［2］，然后將各個三角面展平到此基準(zhǔn)面上。利用上述方法進(jìn)行擴(kuò)展后，對于每一個擴(kuò)展后并被選為新的基準(zhǔn)點的點，以此點所在的一個平面為新的基準(zhǔn)面，再將包含此點的三角面依次展平到此基準(zhǔn)面上。如此循環(huán)，直到滿足上述條件中的終止條件為止。

通過局部展平法，對于每一個點計算出來的紋理坐標(biāo)，其到達(dá)基準(zhǔn)點紋理坐標(biāo)的距離為絕對距離，其到達(dá)中心點坐標(biāo)的距離也為絕對距離，因而貼圖在紋理映射后變形很小。

3 三角面剖分

對三維物體進(jìn)行紋理映射時，通常以三角面為基本映射單位進(jìn)行映射。在局部映射的過程中，對于一塊三角面片，可能只需對一小部分區(qū)域進(jìn)行映射，若將整個面片進(jìn)行映射，則會出現(xiàn)過度映射的現(xiàn)象?？赡艹霈F(xiàn)的情況可分為3種，如圖1所示。

（1）情況1。如圖1a所示，假設(shè)點O為紋理中心，圓環(huán)為紋理映射區(qū)域所覆蓋區(qū)域，若采用基于三角面為基本單位的映射，則A、B、C、D和E點均會被覆蓋在映射區(qū)。隨著紋理映射區(qū)域變小，映射的效果會變得越來越不理想，且會出現(xiàn)過度映射現(xiàn)象。

（2）情況2。如圖1b所示，紋理中心及覆蓋區(qū)域落在一個大的三角形內(nèi)，與第1種情況類似，隨著圓區(qū)域覆蓋面積變小，也會出現(xiàn)過度映射狀況。

（3）情況3。如圖1c所示，因三角形ADC不在需要被映射范圍之內(nèi)，這樣會造成局部紋理映射不完整，而即使加上ADC到映射區(qū)域，也會出現(xiàn)過度映射的狀況。

圖1 確定局部紋理映射區(qū)域

對于上述情況，本文提出了一種通過交點求切線的方法，細(xì)化映射區(qū)域，如圖2所示。

圖2 用切線找到特征點

（1）如圖2a所示，紋理邊界與三角面中的2個邊會有2個交點，以這2個點分別做圓的切線，再從圓邊上取一點做切線，該切線與三角面的第3條邊平行，并且與上面2條切線相交，取相交點為2個特征點，并且取圓與2邊的交點為2個特征點，加上原點5個點為特征點進(jìn)行三角剖分。這5個特征點分別對應(yīng)5個紋理坐標(biāo)。

（2）對于第2種情況，可以從圓心到三角面在3個頂點進(jìn)行三角剖分。如圖2b所示，剖分后的結(jié)果與第1種情況類似，可以使用方法（1）進(jìn)行再次剖分。

（3）對于第3種情況，如圖2c所示，首先判斷ACD面是否需要映射，判斷依據(jù)是圓心到邊上的距離是否小于半徑。若該面需要進(jìn)行映射，除圓與邊的交點做切線外，尋找一條邊與該邊平行的切線，與另外2條切線相交的點，取為特征點，其后剖分的情況與前2種相似。

以圖2a為例進(jìn)行推導(dǎo)。設(shè)圓公式為：

已知A和O的坐標(biāo)，可求出直線AO方程：

聯(lián)立（7）式和（8）式，即可求得F點坐標(biāo)（xF，yF），并以同樣的方法，可以求得G點坐標(biāo)（xG，yG）。

已知圓方程及F、G點坐標(biāo)，可以求出圓上F、G點切線方程如下：

通過A點和B點可以求出切線HI方程，設(shè)

切線HI方程為：

聯(lián)立（9）式、（12）式及（10）式、（12）式即可求出H點及I點坐標(biāo)（xH，yH）和（xI，yI）。

通過上述過程，可求出O、F、G、H、I各點的坐標(biāo)，并通過文中所述的逆方法，求出各點對應(yīng)的三維空間坐標(biāo)，通過這5個特征點進(jìn)行三角剖分后再進(jìn)行紋理映射，達(dá)到預(yù)期效果。

可以證明在取最少特征點的情況下，經(jīng)過這樣的三角剖分后，可以保證局部紋理會被全部映射。而且，所有映射區(qū)域內(nèi)，都不會出現(xiàn)過度映射的情況。

4 實驗效果及分析

為了說明上述算法的實際效果，本文在VC＋＋編程環(huán)境中使用Open GL圖形庫構(gòu)造三維場景環(huán)境，通過在一個針織襪子上映射提花圖案，演示局部紋理映射和三角剖分的效果。紋理貼圖采用大小256×256像素的BMP文件。

在指定的紋理映射區(qū)域與模型中三角面片之間比例較大時（一般情況），使用本文的局部紋理映射算法實現(xiàn)映射的效果如圖3所示。顯然，算法能夠有效地實現(xiàn)局部區(qū)域內(nèi)的紋理映射。

圖3 一般情況下本文算法的映射效果

在指定的紋理映射區(qū)域與三角面之間比例較小時，若不進(jìn)行三角剖分，紋理映射效果往往如圖4所示。顯然，由于構(gòu)成物體模型的三角面片大小不一，在尺度上很接近于貼圖，基本上無法找到適合貼圖大小的映射區(qū)域，因而無法恰當(dāng)?shù)赜成滟N圖，產(chǎn)生圖4所顯示的現(xiàn)象。

圖4 無三角剖分時映射效果

采用本文算法對大的三角面片進(jìn)行三角剖分后，可得到圖5所示的映射效果圖。由于剖分得到更小的三角面片，能更精確地構(gòu)建映射區(qū)域，從而得到較好的局部紋理映射效果。

圖5 有三角剖分時的映射效果

本文的一般算法與三角剖分算法時間復(fù)雜度均為：T（n）＝O（nm），其中m為紋理覆蓋的三角面數(shù)。三角剖分算法較一般算法計算時間略微有所增加，但由于局部紋理映射的范圍一般比較小，紋理貼圖覆蓋的三角面數(shù)非常有限，因此算法仍然能夠滿足實用要求。

5 結(jié)束語

本文通過局部平面展平法進(jìn)行紋理坐標(biāo)計算，可以有效地減少二維紋理貼圖映射到三維物體上變形，通過頂點擴(kuò)張的方法，將紋理映射區(qū)域限制在一個合理的范圍之內(nèi)，并通過三角剖分，避免了因紋理映射區(qū)域與所在三角面片尺度太接近所帶來的過度映射問題，有效地保證了局部區(qū)域紋理映射效果。本文提出的算法成功地運用于虛擬針織織物的修飾和提花設(shè)計中，同時，對于其他類似的虛擬仿真應(yīng)用也具有實用價值。

［1］Ryan S，Cindy G，Brian W.Interactive decal compositing with discrete exponential maps［J］.ACM Transactions on Graphics（TOG），2006，25（3）：605－613.

［2］劉小丹，曾玲玲，孫紅巖.中心擴(kuò)散法局部區(qū)域紋理映射［J］.計算機工程與設(shè)計，2010，31（17）：3852－3855.

［3］Hormann K，Levy B，Sheffer A.Mesh parameterization：theory and practice［C］／／International Conference on Computer Graphics and Interactive Techniques，2007.

［4］江巨浪.多面體表面局部紋理的映射方法［J］.安慶師范學(xué)院學(xué)報：自然科學(xué)版，2003，9（2）：61－64.

［5］黃 燕，王美清.基于立體投影算法的局部球面紋理映射技術(shù)［J］.東莞理工學(xué)院學(xué)報，2009，16（5）：49－54.

［6］張英杰，趙汝嘉，李永紅.基于中間曲面的局部紋理映射技術(shù)［J］.西安交通大學(xué)學(xué)報，1997，31（7）：110－113.

［7］薛 峰，張佑生，江巨浪，等.一種快速、有效的紋理合成方法［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2005，28（11）：1361－1364.

［8］檀結(jié)慶，汪忠慶.新的基于鄰近像素點的圖像修復(fù)算法［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2006，29（9）：1072－1076.