gpu加速物體空間線繪制的通用算法

線描是一種經(jīng)典的非現(xiàn)實(shí)主義繪畫方法，它通過(guò)簡(jiǎn)潔的線條來(lái)表達(dá)物體的形狀特征。作為一種藝術(shù)表現(xiàn)形式，線性繪畫已經(jīng)存在了數(shù)百年。線條的表現(xiàn)也廣泛應(yīng)用于現(xiàn)實(shí)生活中。例如，許多產(chǎn)品的解釋使用了許多圖紙來(lái)解釋產(chǎn)品的功能。此外，許多線條也出現(xiàn)在許多圖紙和書籍插圖中。大多數(shù)手稿都是通過(guò)線條來(lái)表達(dá)的。近年來(lái),線繪制成為非真實(shí)感圖形學(xué)以及表意性繪制領(lǐng)域中的一個(gè)研究熱點(diǎn),其主要研究如何對(duì)輸入的三維網(wǎng)格模型自動(dòng)地抽取特征線,并生成高質(zhì)量的線繪制結(jié)果.人們已提出了許多算法來(lái)解決這一問(wèn)題,這些算法大致可分為物體空間算法與圖像空間算法2類.圖像空間算法首先通過(guò)某種表面繪制方法繪制模型,得到一幅(或多幅)二維圖像,然后通過(guò)對(duì)得到的圖像進(jìn)行某種圖像空間的濾波處理,生成線繪制結(jié)果.該類算法不需要計(jì)算模型表面的各種幾何量,計(jì)算代價(jià)小、容易使用GPU加速、繪制速度較快,并且適用于處理動(dòng)態(tài)變形的幾何模型.但是,圖像空間算法的魯棒性不高.由于在生成圖像的過(guò)程中不可避免地需要進(jìn)行離散化、顏色值量化等操作,因而生成的線繪制結(jié)果常常顯得不夠連續(xù).圖1所示為對(duì)一個(gè)網(wǎng)格模型由圖像空間算法和物體空間算法生成的線繪制結(jié)果的對(duì)比.其中,圖1b與圖1c的特征線定義在理論上是一致的,但是圖1b在圖像空間計(jì)算,而圖1c在物體空間計(jì)算.顯然,物體空間算法更加魯棒,生成的線繪制結(jié)果更加光順、連續(xù).另一方面,圖像空間算法得到的線繪制結(jié)果沒有特征線的幾何信息,所以難以生成風(fēng)格化的線繪制結(jié)果.物體空間算法將網(wǎng)格模型看作一個(gè)二維流形曲面,將特征線定義為模型表面上滿足某種幾何特征的極值線.不同的幾何特征對(duì)應(yīng)于不同的特征線定義方法,例如常用的脊線與谷線分別表示模型表面最凸和最凹的部位,其在數(shù)學(xué)上表示為曲率局部最大及局部最小的點(diǎn)組成的特征線.在線繪制中所采用的幾何特征定義往往依賴于當(dāng)前視點(diǎn),例如輪廓線是滿足視線與模型表面相垂直的特征線.其他常用的特征線定義方法,如近似輪廓線、明顯的脊線、光極線(photicextremumlines,PEL)、拉普拉斯線等也跟視點(diǎn)位置有關(guān).對(duì)于視點(diǎn)相關(guān)的特征線定義,當(dāng)視點(diǎn)發(fā)生變化時(shí),特征線的位置同時(shí)也發(fā)生變化,在繪制時(shí)需要重新計(jì)算.由于物體空間算法通常要基于離散微分幾何原理計(jì)算模型各個(gè)頂點(diǎn)的高階導(dǎo)數(shù)值,因此計(jì)算代價(jià)很大.對(duì)于復(fù)雜的模型,線繪制的速度往往無(wú)法達(dá)到實(shí)時(shí),例如對(duì)于具有100萬(wàn)個(gè)三角面片的網(wǎng)格模型,顯著脊線(apparentridges)與PEL線的繪制速度不到5幀/s.本文提出一種基于GPU的物體空間特征線繪制框架,其中所有物體空間特征線繪制算法都可以利用GPU加速.特別地,本文提出了輪廓線與PEL的GPU加速繪制算法.如圖2所示,使用本文提出的GPU算法進(jìn)行繪制,繪制結(jié)果與傳統(tǒng)CPU算法生成的結(jié)果幾乎沒有區(qū)別,但是繪制速度大大加快.1相關(guān)工作1.1圖像空間線構(gòu)成算法圖像空間線繪制算法通過(guò)對(duì)獲取或生成的二維圖像進(jìn)行圖像處理,從而生成線繪制結(jié)果.Buchanan等提出一種稱為“邊緩存”的數(shù)據(jù)結(jié)構(gòu),能夠在繪制網(wǎng)格模型時(shí)突出顯示重要的特征線.Raskar等提出一種“非真實(shí)感相機(jī)”技術(shù),對(duì)同一個(gè)場(chǎng)景分別使用不同的閃光燈強(qiáng)度拍攝多幅照片,通過(guò)多幅照片的對(duì)比,檢測(cè)照片中深度不連續(xù)的區(qū)域,從而生成輪廓線繪制的結(jié)果.Lee等提出一種基于“抽象光照”的線繪制方法,通過(guò)抽象光照明模型生成模型的光照?qǐng)D,在各像素上通過(guò)函數(shù)擬合計(jì)算多種圖像空間的特征線.Vergne等提出一種圖像空間的模型特征分析方法,通過(guò)在圖像空間的多次濾波操作得到模型的局部幾何特征描述.一般地,圖像空間線繪制算法實(shí)現(xiàn)簡(jiǎn)單、效率高,文獻(xiàn)已實(shí)現(xiàn)了利用GPU加速繪制.本文算法不考慮圖像空間算法,而是針對(duì)更加魯棒的物體空間線繪制算法進(jìn)行設(shè)計(jì).1.2模型特征線面向物體空間線繪制算法通過(guò)在模型表面定義一個(gè)幾何特征函數(shù),并根據(jù)特征函數(shù)計(jì)算特征線的空間位置并生成線繪制結(jié)果.物體空間線繪制算法需要解決的關(guān)鍵問(wèn)題是在哪里畫線,即特征線如何定義,其歸結(jié)為特征函數(shù)如何定義.典型的特征線定義方法包括:1)輪廓線(contours).法向與視線方向垂直的特征線,包括外輪廓(即側(cè)影輪廓線)與內(nèi)輪廓.2)近似輪廓線(suggestivecontours).法向與視線點(diǎn)積的局部最小值,是輪廓線的自然擴(kuò)展.3)高亮線(highlightlines).法向與視線點(diǎn)積的局部最大值.4)顯著脊線(apparentridges).在當(dāng)前視點(diǎn)下模型表面最凸與最凹的部位在數(shù)學(xué)上定義為視點(diǎn)相關(guān)曲率的局部最大或最小值.5)PEL.將Canny圖像邊緣檢測(cè)算子轉(zhuǎn)換到物體空間計(jì)算得到的特征線.6)拉普拉斯線.將LoG圖像邊緣檢測(cè)算子轉(zhuǎn)換到物體空間計(jì)算得到的特征線.7)劃界線(demarcatingcurves).模型表面曲率變化最快的部位.適用于生成考古模型的線繪制結(jié)果.8)高度邊緣線(reliefedges).將模型表面看作是以某個(gè)光滑曲面為基的高度場(chǎng),定義為該高度場(chǎng)的邊緣線.高度邊緣線非常魯棒,適用于處理含有噪聲的模型.在現(xiàn)有的特征線定義中,絕大部分是與視點(diǎn)位置相關(guān)的,當(dāng)視點(diǎn)與模型的相對(duì)位置發(fā)生變化時(shí)特征線的位置也會(huì)隨之變化,需要重新計(jì)算.另外,大部分的特征線定義都需要計(jì)算模型每個(gè)頂點(diǎn)的某種幾何量的二階或更高階導(dǎo)數(shù)值,計(jì)算量非常大.現(xiàn)有的物體空間線繪制算法重點(diǎn)考慮特征如何定義,沒有考慮如何使用GPU加速計(jì)算,對(duì)于復(fù)雜模型繪制速度不能令人滿意.1.3基于相似法的特征線繪制近年來(lái),在線繪制的加速算法方面的研究工作較少.Sander等提出按照模型的法向建立層次結(jié)構(gòu),在繪制特征線時(shí)可以快速地將許多不包含特征線的區(qū)域剔除;但該方法只適用于輪廓線等直接依賴于模型法向的特征線定義,對(duì)其他的特征線無(wú)能為力.Hertzmann等提出一種稱為Gaussmap的數(shù)據(jù)結(jié)構(gòu),將相似法向組合在一起,類似于文獻(xiàn),它也只適用于輪廓線的加速繪制.Markosian等提出一種隨機(jī)跟蹤的線繪制加速策略,首先隨機(jī)確定一些三角形,并對(duì)其中每個(gè)三角形測(cè)試它是否與特征線相交;對(duì)于包含特征線片斷的三角形,沿交點(diǎn)向相鄰三角形進(jìn)行跟蹤,直至得到完整的特征線;該方法適用于任何一種特征線定義,但是由于其隨機(jī)特性,不能保證找出所有的特征線,在視點(diǎn)動(dòng)態(tài)變化時(shí)會(huì)因幀與幀之間的不連續(xù)性而發(fā)生視覺抖動(dòng).最新的NVIDIASDK中包含了一個(gè)使用GPU繪制三角網(wǎng)格模型的輪廓線的實(shí)例,該方法只適用于輪廓線的繪制,不能繪制其他的物體空間特征線.2模型表面特征函數(shù)值的計(jì)算Hertzmann等提出,三維模型的輪廓線可以看作滿足n·v=0的等值線,其中,n和v分別表示模型各點(diǎn)的法向和視線方向.受其啟發(fā),本文提出所有的物體空間線繪制算法都?xì)w結(jié)為繪制模型表面某種函數(shù)值為0的等值線.例如,拉普拉斯線是滿足Δn·v=0的等值線,其中,n和v的含義與輪廓線中的含義相同,而Δn是模型表面法向的拉普拉斯.為方便描述,本文中將這類與特征線定義相關(guān)的函數(shù)稱為特征函數(shù).基于以上觀察,物體空間線繪制算法可以歸納為一個(gè)通用的算法框架,其步驟如下:Step1.根據(jù)特征線的定義計(jì)算模型每個(gè)頂點(diǎn)的特征函數(shù)值.Step2.計(jì)算模型表面特征函數(shù)的值為0的等值線,這可歸結(jié)為一個(gè)逐三角形的計(jì)算.對(duì)每個(gè)三角形,檢查3個(gè)頂點(diǎn)的特征函數(shù)值符號(hào)是否一致;當(dāng)且僅當(dāng)某個(gè)頂點(diǎn)的特征函數(shù)值與其他2個(gè)頂點(diǎn)異號(hào)時(shí),該三角形存在一條特征線片斷,即某條特征線經(jīng)過(guò)該三角形.對(duì)于這樣的情況,通常通過(guò)線性插值計(jì)算出特征線片斷的2個(gè)端點(diǎn)坐標(biāo).相應(yīng)地,本文提出的GPU加速的物體空間特征線繪制也通過(guò)兩步法實(shí)現(xiàn),如圖3所示.pass1.以點(diǎn)為幾何單元繪制模型的所有頂點(diǎn),在頂點(diǎn)渲染器中計(jì)算每個(gè)頂點(diǎn)的特征函數(shù)值,并輸出到一個(gè)二維紋理中.一般地,對(duì)于頂點(diǎn)個(gè)數(shù)為N的網(wǎng)格模型,使用w×h的二維紋理保存所有頂點(diǎn)的特征函數(shù)值,其中w=-√ΝN??√-,h=-ΝwNw-;第i個(gè)頂點(diǎn)對(duì)應(yīng)的紋理坐標(biāo)為(x,y),y=-iwiw-,x=i-y×w.pass2.繪制模型的所有三角形,在頂點(diǎn)渲染器中讀取頂點(diǎn)紋理得到各頂點(diǎn)的特征函數(shù)值.在幾何渲染器中,對(duì)于每個(gè)三角形檢查是否存在某個(gè)頂點(diǎn)的特征函數(shù)值與其他2個(gè)頂點(diǎn)的特征函數(shù)值異號(hào).若存在,則通過(guò)線性插值計(jì)算特征線片斷的2個(gè)端點(diǎn)的坐標(biāo),并將特征線片斷輸出到圖形流水線中.其中,幾何渲染器的輸入幾何單元為三角形,輸出單元為線段.幾何渲染器的偽代碼如下:EndProcedureDrawFeatureLineΡrocedureDrawSegment(p1,p2,p3,f1,f2,f3)α1←f1f1-f2,α2←f1f1-f3,Q1←(1-α1)p1+α1p2,Q2←(1-α2)p1+α2p3OutputSegment(Q1,Q2)#輸出特征線片斷EndProcedureDrawSegment3加快pel輪廓的形成和成像基于圖3所示的算法框架,本文實(shí)現(xiàn)了輪廓線和PEL2種特征線繪制算法的GPU加速.本節(jié)對(duì)這2種特征線的GPU算法進(jìn)行詳細(xì)介紹.3.1gpu加速繪制輪廓線的特征函數(shù)是f=n·v,其中各頂點(diǎn)的法向n是已知的,而視線方向v僅與頂點(diǎn)的三維坐標(biāo)p有關(guān),記視點(diǎn)位置為e,則v=e-p|e-p|.由于輪廓線的特征函數(shù)計(jì)算非常簡(jiǎn)單,因此本文在實(shí)現(xiàn)輪廓線的GPU繪制時(shí)并沒有嚴(yán)格地按照算法框架分兩步計(jì)算,而是把兩步合二為一,通過(guò)單個(gè)步驟實(shí)現(xiàn)輪廓線的GPU加速繪制.如圖4所示,算法以三角形為幾何單元繪制模型,每個(gè)頂點(diǎn)傳入頂點(diǎn)渲染器的屬性值包括三維坐標(biāo)p與法向n;在頂點(diǎn)渲染器中計(jì)算各頂點(diǎn)的視線方向v以及f=n·v,并將各頂點(diǎn)的p和f傳到幾何渲染器.在幾何渲染器中,檢查3個(gè)頂點(diǎn)的特征函數(shù)值是否存在異號(hào)的情況,若存在,則通過(guò)插值計(jì)算特征線片斷的2個(gè)頂點(diǎn)坐標(biāo);像素渲染器僅需簡(jiǎn)單地輸出統(tǒng)一的線條顏色即可.3.2采用平臺(tái)的pel計(jì)算PEL是由Xie等提出的一種網(wǎng)格模型特征線繪制方法,從理論上講,它相當(dāng)于是采用漫反射光照明模型繪制網(wǎng)格模型后,再對(duì)所得光照?qǐng)D采用Canny邊緣檢測(cè)算子得到的圖像邊緣線.與之不同的是,PEL只在物體空間定義的特征線,其計(jì)算在物體空間完成,計(jì)算結(jié)果更加魯棒,生成的線繪制圖像更加光滑和連續(xù).PEL定義為滿足DdI=0,DdDdI<0的特征線,即其特征函數(shù)為f=DdI,其中,d=I/I,I=n·v.如圖5所示,本文通過(guò)4個(gè)pass實(shí)現(xiàn)GPU加速的PEL繪制.其中,pass1用于計(jì)算各頂點(diǎn)的光亮度I=n·v;pass2用于計(jì)算各頂點(diǎn)的I;pass3用于計(jì)算各頂點(diǎn)的特征函數(shù)值Dd|Ι|=I·d.pass1～pass3相當(dāng)于第3節(jié)算法框架中的pass1;而pass4則與算法框架中的pass2相同,根據(jù)之前計(jì)算的各頂點(diǎn)的特征函數(shù)值生成線繪制結(jié)果.3.2.1GPU加速的梯度場(chǎng)計(jì)算在繪制PEL時(shí)最主要的問(wèn)題在于如何計(jì)算模型表面二維標(biāo)量場(chǎng)的梯度場(chǎng),或者說(shuō)給定每個(gè)頂點(diǎn)的一個(gè)標(biāo)量函數(shù)值f,如何計(jì)算出各頂點(diǎn)的梯度f(wàn).Xie等提出一種兩步法計(jì)算各頂點(diǎn)的函數(shù)梯度,該方法歸結(jié)為一個(gè)逐三角形的計(jì)算,并不適用于GPU加速.為此,本文提出一種逐頂點(diǎn)的函數(shù)梯度計(jì)算方法.設(shè)f是網(wǎng)格模型M上的一個(gè)標(biāo)量場(chǎng),p是M的任一頂點(diǎn),u和v是頂點(diǎn)p的2個(gè)主曲率方向.記頂點(diǎn)p的所有相鄰三角面片為Fk(k=1,…,m),并分別記Fk3個(gè)頂點(diǎn)的索引值為k1,k2和k3,函數(shù)值為fk1,fk2和fk3.在Fk上任取平面直角坐標(biāo)系(xk,ok,yk),并將3個(gè)頂點(diǎn)在該坐標(biāo)系下的坐標(biāo)記為(xki,yki),i=1,2,3,則f在三角形Fk內(nèi)的梯度其中,Ak=(xk1yk2-yk1xk2)+(xk2yk3-yk2xk3)+(xk3yk1-yk3xk1)是三角形Fk的有向面積的2倍.容易驗(yàn)證,該定義中的函數(shù)梯度f(wàn)Fk與坐標(biāo)系(xk,ok,yk)的選取無(wú)關(guān).記uk,uk為u,v在三角面片F(xiàn)k上的投影,則頂點(diǎn)p處f的函數(shù)梯度其中wk是Fk相鄰三角面片的加權(quán)系數(shù),可取為頂點(diǎn)p的Voronoi圖中位于三角面片F(xiàn)k中的面積與總面積之比,可以在模型調(diào)入后一次性預(yù)計(jì)算得到.令Ck=wkAk(uk?xkuk?ykvk?xkvk?yk)?(yk2-yk3yk3-yk1yk1-yk2xk3-xk2xk1-xk3xk2-xk1)=(ak1ak2ak3bk1bk2bk3),則有按照式(1)計(jì)算梯度f(wàn)(p)很容易在頂點(diǎn)渲染器中實(shí)現(xiàn).在預(yù)處理階段(讀入模型以后),對(duì)模型中的每個(gè)頂點(diǎn)p計(jì)算每個(gè)相鄰頂點(diǎn)q的權(quán)值α(q)和β(q);在計(jì)算函數(shù)梯度時(shí)(pass2,pass3),對(duì)每個(gè)頂點(diǎn)p將它所有相鄰頂點(diǎn)q的索引號(hào)以及權(quán)值α(q)和β(q)作為頂點(diǎn)屬性值傳入圖形流水線;在頂點(diǎn)渲染器中,根據(jù)各相鄰頂點(diǎn)q的索引號(hào)計(jì)算出相應(yīng)的紋理坐標(biāo),并通過(guò)讀取頂點(diǎn)紋理獲得各頂點(diǎn)的函數(shù)值f(q),并按照式(1)通過(guò)加權(quán)和計(jì)算出當(dāng)前頂點(diǎn)的函數(shù)梯度.4加速的輪廓線繪制我們基于OpenGL和Cg語(yǔ)言實(shí)現(xiàn)了第3節(jié)提出的GPU加速的輪廓線繪制與PEL繪制算法.在實(shí)現(xiàn)中將輪廓線繪制與PEL繪制整合一起,通過(guò)在繪制PEL的pass4中加入輪廓線繪制的代碼,實(shí)現(xiàn)了輪廓線與PEL的同時(shí)繪制.4.1評(píng)估輪廓線與gpu的繪制速度本文對(duì)一些常見模型進(jìn)行了測(cè)試,分別采用GPU算法與傳統(tǒng)CPU算法生成線繪制結(jié)果,并對(duì)繪制速度進(jìn)行比較,結(jié)果如表1所示.表1中,第3,4列分別是使用CPU算法與GPU算法進(jìn)行特征線繪制的速度;第5列是采用GPU加速獲得的加速比,即使用GPU繪制的幀率與使用CPU繪制的幀率之比.其中,CPU算法和GPU算法的繪制速度都是在同時(shí)繪制輪廓線與PEL的情況下測(cè)得的.測(cè)試平臺(tái)的硬件配置為IntelCoreDuo3.0GHzCPU,NVIDIAGTX285GPU.使用本文提出的GPU算法對(duì)所有的測(cè)試模型進(jìn)行繪制,至少比使用傳統(tǒng)CPU算法繪制速度快11倍,在最好的情況下,速度提升超過(guò)16倍(對(duì)于Buddha模型).根據(jù)近年來(lái)CPU與GPU的發(fā)展趨勢(shì)來(lái)看,隨著時(shí)間的推移,GPU相對(duì)CPU的性能優(yōu)勢(shì)會(huì)越來(lái)越明顯,因而采用GPU算法的加速效果也會(huì)越來(lái)越好.另一方面,由于GPU算法與CPU算法相比并沒有采用任何近似計(jì)算,因此GPU算法生成的線繪制結(jié)果與CPU算法的結(jié)果幾乎沒有差別,如圖2所示.圖6展示了更多的使用GPU算法生成的輪廓線與PEL繪制結(jié)果.4.2相鄰點(diǎn)對(duì)點(diǎn)信息占用本文算法消耗的存儲(chǔ)空間(顯存)主要體現(xiàn)在2個(gè)方面:一是作為圖形流水線輸入的各頂點(diǎn)的屬性值,二是用于保存各頂點(diǎn)的特征函數(shù)值或中間值的二維紋理.對(duì)于輪廓線繪制,每個(gè)頂點(diǎn)只需要頂點(diǎn)位置和法向2個(gè)基本的屬性值,而這2個(gè)屬性值在絕大多數(shù)情況下都是必須的;另一方面,輪廓線繪制可以在單個(gè)pass中完成,不需要額外的紋理來(lái)保存各頂點(diǎn)的特征函數(shù)值.因此可以認(rèn)為輪廓線的GPU加速繪制不消耗額外的存儲(chǔ)空間.對(duì)于PEL繪制,每個(gè)頂點(diǎn)需要傳入較多的屬性值.除了位置與法向外,還需要傳入所有相鄰頂點(diǎn)的索引值以及2個(gè)計(jì)算梯度值的加權(quán)系數(shù),這樣,對(duì)每個(gè)相鄰頂點(diǎn)需要保存3個(gè)浮點(diǎn)數(shù).在當(dāng)前的圖形流水線中,要求每個(gè)頂點(diǎn)具有相同大小的屬性數(shù)據(jù).本文在實(shí)現(xiàn)中對(duì)每個(gè)頂點(diǎn)都保存12個(gè)相鄰頂點(diǎn)的索引號(hào)和加權(quán)系數(shù)(包括自身),對(duì)于相鄰頂點(diǎn)數(shù)不足12的頂點(diǎn),將不足的部分記頂點(diǎn)索引號(hào)為-1.在本文測(cè)試的所有模型中,沒有出現(xiàn)相鄰頂點(diǎn)數(shù)達(dá)到