三角網(wǎng)格曲面紋理合成技術(shù)研究

王元龍1，張榮國1，馮軍華1，劉 焜2

?

三角網(wǎng)格曲面紋理合成技術(shù)研究

王元龍，張榮國，馮軍華，劉 焜

（1. 太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西太原 030024；2. 合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院，安徽合肥 230009）

紋理合成是真實(shí)感圖形繪制中重要的技術(shù)。對(duì)由三角網(wǎng)格組成的曲面模型，提出了一種基于表面三角塊矢量場的紋理合成方法。首先用矢量加平滑方法來計(jì)算曲面上每個(gè)三角塊上的紋理方向矢量，并根據(jù)這些紋理方向來合成紋理；然后在樣本紋理空間按掃描線順序搜索樣本紋理空間，找出最匹配的紋理坐標(biāo)；算法用隊(duì)列作為存取結(jié)構(gòu)，并且結(jié)果保存在隊(duì)列中，達(dá)到了實(shí)時(shí)繪制效果。實(shí)驗(yàn)結(jié)果與理論分析表明，算法紋理合成質(zhì)量較高，運(yùn)行結(jié)果較好。

計(jì)算機(jī)圖形學(xué)；紋理合成；矢量平滑；三角網(wǎng)

在計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)等領(lǐng)域使用紋理來表現(xiàn)幾何模型的細(xì)節(jié)，是一項(xiàng)最為常用的技術(shù)，它不僅提高了繪制的效率，而且降低了場景建模的復(fù)雜度。其中紋理映射和紋理合成就成為最近幾年人們的一個(gè)研究熱點(diǎn)。二者各有優(yōu)點(diǎn)，其中也有很多研究人員把它們結(jié)合起來進(jìn)行研究。

紋理映射作為應(yīng)用于真實(shí)感圖形繪制中的一項(xiàng)實(shí)用技術(shù)，首先是由Catmull在70年代中期提出的，稱作Catmull算法，實(shí)現(xiàn)了參數(shù)曲面上的紋理映射。后來有很多改進(jìn)算法，這些算法的基本目標(biāo)是減少或避免映射中引起的接縫和扭曲。在1978年，Blinn提出利用擾動(dòng)函數(shù)來生成凹凸效果的凹凸紋理映射技術(shù)，該技術(shù)增強(qiáng)了物體表面的真實(shí)感。1986年，Bier和Sloan提出了兩步紋理映射技術(shù)，該技術(shù)取得了很好的效果。后來江等人提出了兩步紋理的改進(jìn)算法，顯著提高了兩步紋理映射的質(zhì)量與真實(shí)感。最近幾年人們對(duì)基于約束的紋理映射做了大量的研究，也是紋理映射的發(fā)展趨勢，如Tang等人提出基于約束的紋理映，就是給紋理映射加了邊界約束和斜率約束，來控制對(duì)象表面上特定的位置映射到紋理空間上的特定的紋理；Lee等人也提出了基于約束的紋理映射方法，這種方法是首先給出對(duì)象表面到紋理空間的一些約束點(diǎn)，然后通過邊交換技術(shù)得到整個(gè)表面的紋理坐標(biāo)。現(xiàn)在基于約束的紋理映射正越來越成為人們的研究熱點(diǎn)。

紋理合成是為了解決小樣本紋理映射到大的曲面上造成表面紋理的變形、扭曲以及模糊不清而提出的。它的基本思想是：給定一個(gè)有限的小樣本紋理，生成任意大的樣本紋理視覺上相似的紋理圖像。早期的合成是基于樣圖的二維紋理合成，比較典型的有：①特征匹配的方法。如Heeger和Bergeg利用拉普拉斯和可控的金字塔進(jìn)行的紋理合成；②基于馬爾可夫隨機(jī)場模型的紋理合成算法。如Wei和Levoy采用多分辨率模型進(jìn)行匹配，提高了合成速度；③基于紋理塊拼接的紋理合成。最有效果的是Wang Tiles方法，它能實(shí)時(shí)的合成紋理，并且適合于多種紋理合成。

最近10多年來，人們對(duì)曲面紋理合成也做了大量的研究。2001年SIGGRAPH會(huì)議上，Wei和Levoy提出了曲面紋理合成算法，Turk也提出了曲面紋理合成算法，他們雖然算法上有所不同，但都采用了多分辨率的思想，把二維紋理合成基于點(diǎn)匹配的思想拓展到了三維空間。受到二維紋理合成的塊拼接思想和曲面最終可以轉(zhuǎn)變成三角形塊的啟發(fā)，人們開始采用三角塊紋理匹配的方法逐個(gè)合成網(wǎng)格中的每個(gè)三角形塊，完成曲面紋理合成。湯等人提出用優(yōu)先度方法從當(dāng)前待合成三角塊的相鄰已合成三角塊中提取紋理模版來合成當(dāng)前待合成三角塊算法，該算法用優(yōu)先隊(duì)列來控制優(yōu)先度最高的三角塊最先合成，并且用戶可以控制紋理的方向和比例，所以合成效果很好，但對(duì)于三角塊較多曲面速度較慢。吳等人提出了基于三角塊的曲面紋理合成，它根據(jù)曲面切向量的方向，利用三角紋理塊的方法直接在曲面上生成紋理，該方法提高了紋理的生成速度，但由于它不進(jìn)行任何的預(yù)處理，對(duì)于曲面上少量的狹小三角形塊效果仍不好。之后，薛等人對(duì)上述兩種方法做了改進(jìn)，它根據(jù)當(dāng)前待合成三角塊的相鄰已合成三角塊個(gè)數(shù)的不同，提出了基于紋理延伸和三角塊拼接的曲面紋理合成，由于有一大部分三角塊紋理是通過延伸得到的，所以該算法明顯提高了合成的速度，但是它必須對(duì)輸入的樣本紋理做預(yù)處理生成可無縫自拼接的紋理，這就給算法增加了復(fù)雜度，且對(duì)結(jié)構(gòu)性強(qiáng)的紋理效果也不是很好。

有些研究人員把紋理映射和紋理合成結(jié)合起來運(yùn)用到曲面上，如江等人提出了局部紋理映射的紋理合成算法，它把曲面分成若干映射區(qū)和合成區(qū)，在映射區(qū)運(yùn)用紋理映射方法，在合成區(qū)運(yùn)用紋理合成的方法。它大幅度提高了曲面紋理合成的速度。

該文受到文獻(xiàn)[10, 13]的啟發(fā)，提出了一種實(shí)時(shí)曲面紋理合成的算法，運(yùn)用隊(duì)列存取控制曲面三角塊，最后達(dá)到實(shí)時(shí)的紋理合成。和其它算法相比，優(yōu)點(diǎn)在于：① 只要用戶指定曲面上若干個(gè)三角塊的紋理矢量方向（即整個(gè)曲面大致的紋理方向），就可以計(jì)算出曲面上每個(gè)三角塊的紋理方向，這樣可以按照用戶預(yù)想的紋理方向合成紋理，提高可控性；② 該算法用隊(duì)列作為存取結(jié)構(gòu)，并且最終曲面信息都存放在隊(duì)列中，這樣當(dāng)需要繪制曲面時(shí)，遍歷整個(gè)隊(duì)列就可以，達(dá)到了實(shí)時(shí)繪制的目的。

1 原理和方法

1.1 紋理矢量場的計(jì)算

大多數(shù)自然或人工紋理都有方向性，在曲面合成紋理時(shí)需要用戶指定紋理方向，才能達(dá)到滿意的效果。曲面紋理矢量場就是用來控制紋理在曲面上的大致走向。

曲面通常是由三角網(wǎng)格構(gòu)成的，曲面矢量場是用曲面上每個(gè)三角形中心射出的矢量表示。計(jì)算矢量場：用戶指定若干三角網(wǎng)格的矢量方向，然后用插值方法計(jì)算出剩下三角網(wǎng)格的矢量方向，最終生成一個(gè)平滑的矢量場，如圖1所示。

圖1 用戶輸入的矢量及插值生成的矢量場

1.2 紋理塊尺寸的控制

紋理塊的尺寸越大，紋理合成時(shí)間越短；反之，紋理合成時(shí)間就越長。但是，紋理塊過大，塊與塊之間容易出現(xiàn)不連貫的情況；紋理塊過小，可能會(huì)失去紋理的全局特征。所以紋理塊選取的是否得當(dāng)直接影響到合成結(jié)果。

此外，樣本紋理中信息的變化是有一定周期性的，如果所選的紋理塊尺寸對(duì)這個(gè)周期有比較好的反映，并且每個(gè)紋理塊中的信息能比較好的反映出紋理的全局信息，那么這個(gè)所選的紋理塊既可以反映出樣本紋理的全局特性，又可以反映出樣本紋理的局部特性。

1.3 搜索匹配

搜索匹配就是在樣本紋理中搜索與已紋理化三角塊匹配且和該三角塊相鄰的未紋理化的三角塊的紋理坐標(biāo)。這個(gè)過程是紋理合成中的關(guān)鍵步驟。

已紋理化三角塊中的匹配區(qū)域用以約束紋理塊的選取。如果匹配區(qū)域過窄，則在樣本紋理空間中的候選塊的個(gè)數(shù)就會(huì)增加，從而選到干擾塊的概率就比較大，這將影響到紋理合成質(zhì)量；如果匹配區(qū)域過寬，那么計(jì)算量就會(huì)增大，這就影響到了搜索的速度，從而大大增加了紋理的合成時(shí)間。因此，要選擇合適寬度的匹配區(qū)域，使其既保證合成質(zhì)量，又有較快的合成速度。

大部分計(jì)算匹配區(qū)域的誤差距離為

=S{(R-R)+(G-G)+(B+B)}或

=S{(R-R)^2+(G-G)^2+(B+B)^2}

其中,,是顏色的三個(gè)分量，下標(biāo)和分別表示已紋理化三角塊的匹配區(qū)域和當(dāng)前待合成三角塊在樣本紋理空間中的匹配區(qū)域。

2 曲面紋理合成

曲面紋理合成的目的是根據(jù)一定的算法遍歷曲面網(wǎng)格上的每個(gè)三角塊，計(jì)算其在樣本紋理空間中的紋理坐標(biāo)，并保證這些三角片紋理的連續(xù)性。而曲面上每個(gè)三角塊的法向量不平行，這給計(jì)算曲面紋理矢量場帶來了很大的困難，該文提出了一種計(jì)算曲面矢量場的方法。

2.1 相關(guān)的知識(shí)

（1）計(jì)算兩個(gè)矢量的夾角

設(shè)矢量={,,},={,,},和的夾角是。那么

（2）旋轉(zhuǎn)三角形

把一個(gè)三角形繞任意軸旋轉(zhuǎn)一定的角度且旋轉(zhuǎn)后三角形的大小形狀都不變，設(shè)一個(gè)任意軸，點(diǎn)的坐標(biāo)為(,,),的方向矢量為{,,}, 則一個(gè)三角形繞旋轉(zhuǎn)角度所對(duì)應(yīng)的就是三角形3個(gè)頂點(diǎn)分別乘上矩陣，而為

2.2 曲面紋理矢量場的計(jì)算

首先旋轉(zhuǎn)曲面上的每個(gè)三角形使三角形3個(gè)頂點(diǎn)的軸坐標(biāo)相同（間接的確認(rèn)每個(gè)三角形在同一個(gè)平面上），設(shè)任意三角形的3個(gè)頂點(diǎn)的坐標(biāo)分別是(,,)，(,,)，(,,)，三角形的法向?yàn)?{,,}。作者的方法分兩步進(jìn)行。

第一步，把點(diǎn)、繞過點(diǎn)并且平行于面的矢量旋轉(zhuǎn)（該矢量在三角形面上），使該三角形的法向量和面平行。旋轉(zhuǎn)矩陣為

第二步，把點(diǎn)、繞過點(diǎn)且平行于軸的矢量旋轉(zhuǎn)，使三角形的法向量平行于軸正方向。旋轉(zhuǎn)矩陣為

曲面上的每個(gè)三角塊被旋轉(zhuǎn)后法向量都平行于軸，這樣可以把旋轉(zhuǎn)后的三角塊看成是在同一個(gè)平面上，這樣就容易計(jì)算矢量場了。

作者用個(gè)矢量的平均矢量等于這個(gè)矢量的和，最后把它單位化，來計(jì)算除用戶指定外曲面三角網(wǎng)格的矢量方向，最終生成一個(gè)平滑的矢量場。此方法編程簡單，易用，且速度快，如圖2所示。

圖2 矢量加來計(jì)算平均矢量

2.3 搜索匹配的過程

該文用到的搜索方法是從已紋理化的紋理三角塊中提取模版（也就是匹配區(qū)域），根據(jù)當(dāng)前待紋理化三角塊的紋理方向矢量，在樣本紋理中按掃描線的順序搜索，找到與提取模版紋理值最相近的紋理坐標(biāo)作為當(dāng)前待紋理化三角塊的紋理坐標(biāo)值。

從已紋理三角塊中提取匹配模版，該文取所在邊長的1/5，如圖3所示（陰影部分是所提取的匹配模版。

圖3 匹配模版

圖4是一個(gè)待合成三角塊根據(jù)紋理方向旋轉(zhuǎn)且按紋理塊尺寸縮放得到的，曲面上的每個(gè)三角塊都用此方法來確定三角塊提取模版在樣本紋理空間中的初始位置。

圖4 紋理方向旋轉(zhuǎn)且按紋理塊尺寸縮放

然后，把已合成三角塊相鄰的當(dāng)前待合成的三角塊按照上述的方向旋轉(zhuǎn)放到紋理空間底部，并同樣提取出匹配模版（緊貼相鄰已紋理化三角塊），接著按一定的步長用掃描線的方法順序搜索樣本紋理空間，找出和已紋理化三角塊的模版最相近的紋理坐標(biāo)賦給當(dāng)前待合成三角塊，如圖5所示。

圖5 搜索過程

3 算法的具體步驟

根據(jù)模型表面三角塊的蔬密程度來控制紋理合成塊的大小，同時(shí)用戶也能控制紋理合成塊的大小。首先，在紋理合成前計(jì)算每個(gè)三角塊中的最長邊，用最長邊來控制各個(gè)三角塊紋理的大小。然后設(shè)置一個(gè)用戶能控制的參數(shù)ratio乘到這個(gè)最長邊上，這樣用戶就可以控制要合成模型表面的整體紋理了。具體步驟如下：

Step 1 根據(jù)用戶指定三角塊的紋理方向矢量，計(jì)算出曲面上每個(gè)三角塊的紋理方向矢量。

Step 2 從曲面中隨機(jī)地選取一個(gè)種子三角塊，把它放入隊(duì)列中，其中包括該三角塊的頂點(diǎn)信息和已計(jì)算出的紋理矢量方向信息。根據(jù)紋理矢量方向信息隨機(jī)給種子三角塊賦紋理坐標(biāo)。

Step 3 從隊(duì)列頭部獲取一個(gè)三角塊，根據(jù)所得三角塊的紋理坐標(biāo)，從樣本紋理中分別搜索和此三角塊匹配的相鄰未合成的三角塊的紋理坐標(biāo)，并把它們放入隊(duì)列中。

Step 4 融合邊界區(qū)域，回到Step 3，直到遍歷完整個(gè)曲面的每個(gè)三角塊。

Step5 紋理曲面的繪制。

曲面上三角塊信息（包括頂點(diǎn)坐標(biāo)和紋理坐標(biāo)）都存放在一個(gè)隊(duì)列中了，當(dāng)需要繪制地形時(shí)，只要遍歷整個(gè)隊(duì)列提取出每個(gè)三角形的信息進(jìn)行繪制就可以了，達(dá)到了實(shí)時(shí)繪制。作者用到的三角形每個(gè)頂點(diǎn)的結(jié)構(gòu)如下：

typedef struct TexturePoint

{

float x, y, z; //點(diǎn)的坐標(biāo)

float u,v; //紋理的坐標(biāo)

float psx,psy,psz; //點(diǎn)的方向矢量

}TexturePoint;

每個(gè)三角形由三個(gè)點(diǎn)（TexturePoint）構(gòu)成，

typedef struct queue

{

TexturePoint point1;

TexturePoint point2;

TexturePoint point3;

struct queue * next;

}queue

存放在隊(duì)列中的三角形結(jié)點(diǎn)。

4 實(shí)驗(yàn)及結(jié)果分析

在Windows XP系統(tǒng)下，使用OpenGL圖形開發(fā)包工具和VC++6.0編繹環(huán)境進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6所示。

這里圖6(a1)和圖6(c1)樣本紋理圖用.RGB格式和圖6(b1)用.jpg格式，原紋理樣圖大小都是128*128像素。地形曲面由32個(gè)三角塊組成，球體曲面都是由768個(gè)三角塊組成，由圖6可以看出，該文算法合成質(zhì)量較高。表1給出了實(shí)驗(yàn)數(shù)據(jù)。

從表1中的數(shù)據(jù)可以看出，該文算法繪制時(shí)間較短，比較適合實(shí)時(shí)的繪制。為了進(jìn)一步說明該文的合成效率，基于相同的三角網(wǎng)格數(shù)，作者給出了該文算法和文獻(xiàn)[12]算法的合成時(shí)間對(duì)比，如表2所示。

與傳統(tǒng)算法相比，由于該文不需要進(jìn)行樣本紋理的預(yù)處理，所以比文獻(xiàn)[12]節(jié)省了時(shí)間。實(shí)驗(yàn)數(shù)據(jù)表明，對(duì)于一般的網(wǎng)格模型，該文算法的合成時(shí)間約為文獻(xiàn)[12]算法的1/3，并且該文用隊(duì)列存儲(chǔ)了紋理坐標(biāo)，所以顯示是實(shí)時(shí)的。

該文算法主要是在搜索匹配的過程中花費(fèi)了一些時(shí)間，需要曲面上的每個(gè)三角塊都搜索一遍樣本紋理空間，但這個(gè)過程是在預(yù)處理函數(shù)中進(jìn)行的，預(yù)處理之后曲面上各頂點(diǎn)的信息都放到隊(duì)列中了，當(dāng)需要繪制時(shí)只要遍歷隊(duì)列就行，所以這不影響模型繪制的實(shí)時(shí)性。

圖6 該文算法合成

表1 合成紋理實(shí)驗(yàn)數(shù)據(jù)

表2 該文算法和文獻(xiàn)[12]算法時(shí)間對(duì)比

5 結(jié)束語

該文提出了一種實(shí)時(shí)曲面的紋理合成的算法。實(shí)現(xiàn)用戶控制紋理方向?qū)崟r(shí)的紋理合成。研究主要針對(duì)虛擬現(xiàn)實(shí)中隨視點(diǎn)的改變地形需要實(shí)時(shí)的繪制來進(jìn)行的，接下來就是把它應(yīng)用到虛擬現(xiàn)實(shí)中。如果曲面不夠光滑（也就是相鄰三角塊間的夾角太大），那么相鄰三角塊間的紋理也就不太光滑。此時(shí)就需要對(duì)曲面進(jìn)行細(xì)分預(yù)處理，文獻(xiàn)[15]是三角網(wǎng)格細(xì)分的一種方法。這也成為將來工作的重點(diǎn)之一。

[1] 彭群生, 鮑虎軍, 金小剛. 計(jì)算機(jī)真實(shí)感圖形的算法基礎(chǔ)[M]. 北京: 科學(xué)出版社, 1999. 235-291.

[2] 江巨浪, 張佑生, 等. 兩步紋理映射的改進(jìn)[J]. 系統(tǒng)仿真學(xué)報(bào), 2006, 18(5): 1157-1160.

[3] Tang Ying, Wang Jin, Bao Hujun, et al. RBF-based constrained texture mapping [J]. Computer Graphics, 2003, 27(3): 415-422.

[4] Lee Tong-Yee, Yen Shao-Wei, Yeh I-Cheng. Texture mapping with hard constraints using warping scheme [J]. IEEE Transactions on Visualization and Graphics, 2008, 41(2): 382-395.

[5] Heeger David J, James R Bergen. Pyramid based texture anlysis/synthesis [C]//Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH 95), 1995: 229-238.

[6] Wei Livi, Levey Marc. Fast texture synthesis using tree-structured vector quantization [C]//Proceedings of SIGGRAPH 2000, 2000: 179-488.

[7] 王 棟, 王去峰, 常寧寧. 紋理合成典型算法及分類比較[C]//科技信息(高校講壇), 2008: 166-166.

[8] Wei Liyi, Levoy Marc. Texture synthesis over arbitrary manifold surfaces [C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, California, 2001: 355-360.

[9] Turk G. Texture synthesis on surfaces [C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angles, 2001: 347-354.

[10] 湯穎, 孫漢秋, 張宏鑫, 等. 用戶控制的紋理合成[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2004, 16 (10): 1412-1418.

[11] 吳福禮, 石教英. 基于三角塊的曲面紋理合成[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(2): 236-242.

[12] 薛 峰, 張佑生, 江巨浪, 等. 基于紋理延伸和三角塊拼接的快速曲面紋理合成[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2007, 19(2): 221-226.

[13] 江巨浪, 張佑生, 等. 運(yùn)用局部紋理映射加速曲面紋理合成[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2008, 20(11): 1507-1513.

[14] 聶俊嵐, 王艷芬. 塊紋理合成中紋理塊尺寸自適應(yīng)算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2008, 20(10): 1353-1357.

[15] 王艷艷, 張榮國, 王 蓉, 等. 向量線性相關(guān)的三角網(wǎng)格自適應(yīng)Loop細(xì)分方法[J]. 工程圖學(xué)學(xué)報(bào), 2009, 30(1): 91-96.

Study on the Texture Synthesis of Triangular Mesh Surfaces

WANG Yuan-long, ZHANG Rong-guo, FENG Jun-hua, LIU Kun

( 1. School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan Shanxi 030024, China;2. School of Mechanical and Automotive Engineering, Hefei University of Technology, Hefei Anhui 230009, China )

Texture synthesis is an important technology in a realistic figure rendering. A texture synthesis method is presented which is based on surface triangular mesh vector field for surface model consisting of the triangular mesh. First, the texture vector direction of each triangle of surface is calculated by using the vector sum method, and the texture vector direction is used to synthesize surfaces texture. Second, the best match of the texture coordinates is found in the sample texture space by scanning line sequence. The algorithm uses a queue as the structure of depositing and withdrawing, and the results are stored in the queue to achieve real-time rendering. Some experimental results and theoretical analysis show that texture synthesis quality of algorithm is higher and running results are better.

computer graphics; texture synthesis; vector smooth; triangular mesh

TP 391

A

1003-0158(2011)01-0104-07

2009-06-30

國家自然科學(xué)基金資助項(xiàng)目（50775060）；山西省教育廳資助項(xiàng)目（20081086）

王元龍（1983-），男，山西大同人，碩士，主要研究方向?yàn)橛?jì)算機(jī)圖形圖像處理。