精細(xì)建筑物碎片化紋理優(yōu)化的二維裝箱方法

朱 慶 ，張琳琳 ，胡 翰 ，翁其強(qiáng) ，丁雨淋 ，李 赟 ，張葉廷

（1. 西南交通大學(xué)地球科學(xué)與環(huán)境工程學(xué)院，四川 成都 611756；2. 武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430079；3. 浙江中海達(dá)空間信息技術(shù)有限公司，浙江 湖州 313200）

隨著多源數(shù)據(jù)多細(xì)節(jié)層次建模技術(shù)的不斷發(fā)展[1-2]，三維城市模型的精細(xì)程度不斷提高，幾何、紋理數(shù)據(jù)量呈幾何級(jí)數(shù)增長(zhǎng)[3-4]. 結(jié)構(gòu)復(fù)雜的精細(xì)建筑物模型，如LOD-3 （level of detail-3）建筑物模型，一個(gè)窗戶有多個(gè)平面，每個(gè)平面對(duì)應(yīng)一個(gè)碎片化紋理[5].現(xiàn)有三維可視化引擎，如Microsoft XNA、Unity 3D等，通常不支持多紋理模式，需要將三維格網(wǎng)分割成多個(gè)簡(jiǎn)單的平面，每平面對(duì)應(yīng)一個(gè)單獨(dú)的紋理，對(duì)不同材質(zhì)紋理需通過(guò)多次指令逐一渲染. 由于每個(gè)平面都會(huì)單獨(dú)調(diào)用CPU （central processing unit）指令進(jìn)行繪制，增加了模型加載壓力，降低了渲染效率，無(wú)法充分利用圖像處理器（graphics processing unit，GPU）批處理機(jī)制，難以滿足大規(guī)模城市三維模型應(yīng)用需求. 因此，如何將碎片化紋理進(jìn)行封裝和優(yōu)化，減輕CPU負(fù)擔(dān)，提高GPU加載和繪制效率，減少磁盤讀取操作次數(shù)，成為當(dāng)前傾斜攝影測(cè)量三維城市模型集成應(yīng)用的關(guān)鍵問(wèn)題.

現(xiàn)有紋理合并工具依賴人工經(jīng)驗(yàn)，自動(dòng)化程度低，應(yīng)用局限較大，如NVIDIA公司的紋理工具軟件（texture tools），Autodesk公司3DMax軟件的UVWUnWrap工具，使用ISOMAP的商業(yè)軟件，以及Open-SceneGraph的NodeOptimizer. 三維模型的紋理組織方法可分為連續(xù)表面模型的紋理組織方法和離散表面模型的紋理組織方法：連續(xù)表面模型的紋理組織方法已有成熟應(yīng)用，如Google Earth、Virtual Earth，主要方法為硬件支持的切片圖方法[6]和瓦片影像金字塔方法[7]；離散表面模型的紋理組織方法有Blockmap方法[8]，紋理集（texture atlas）方法[9]等. 目前相關(guān)的大部分研究主要著眼于如何更優(yōu)的進(jìn)行紋理合并[10-18]，雖然在一定程度上減少了紋理文件個(gè)數(shù)，但因模型中存在UV坐標(biāo)超出[0，1]范圍的異常紋理，導(dǎo)致其結(jié)果存在大量冗余紋理，紋理數(shù)據(jù)量反而增加，通過(guò)犧牲數(shù)據(jù)量換取渲染效率的提高. 雖有一些研究中涉及了異常紋理的處理方法[19]，但是尚無(wú)妥善的解決方案.

針對(duì)上述問(wèn)題，本文提出了一種精細(xì)建筑物碎片化紋理優(yōu)化的二維裝箱方法，通過(guò)紋理去冗余，有效解決了紋理合并中存儲(chǔ)空間與渲染效率無(wú)法兩全的難題，同時(shí)避免了異常紋理坐標(biāo)導(dǎo)致的紋理拉花問(wèn)題.

1 碎片化紋理優(yōu)化的二維裝箱方法

圖1為精細(xì)建筑物模型碎片化紋理優(yōu)化的二維裝箱方法算法流程，主要包括以下3個(gè)部分：

1） 紋理去冗余，為了剔除冗余紋理，處理異常紋理的情況，根據(jù)UV坐標(biāo)是否超出[0，1.0]，將模型中的紋理分為異常紋理和正常紋理兩類，分別進(jìn)行去冗余處理.

2） 紋理合并，為了減少紋理文件個(gè)數(shù)，根據(jù)去冗余得到的簡(jiǎn)化紋理和給定紋理集尺寸，模擬二維裝箱過(guò)程，并按照裝箱結(jié)果進(jìn)行紋理合并.

3） 紋理重映射，為了解決由于紋理去冗余和紋理打包導(dǎo)致紋理映射關(guān)系發(fā)生變化的問(wèn)題，根據(jù)紋理去冗余和紋理合并過(guò)程中的變化信息，重映射紋理坐標(biāo)，得到紋理優(yōu)化后的建筑物模型.

圖1 算法流程Fig. 1 Algorithm flowchart

1.1 紋理去冗余

紋理坐標(biāo)系O-UV是以紋理左下角為坐標(biāo)原點(diǎn)，向右為U軸正方向，向上為V軸正方向建立的平面坐標(biāo)系，一般定義在通過(guò)三維坐標(biāo)和紋理坐標(biāo)（UV坐標(biāo)）可以確定紋理影像坐標(biāo)區(qū)域的外接矩形即有效紋理區(qū)域，有效紋理區(qū)域以外的圖像部分被稱為冗余紋理. 冗余紋理不僅占據(jù)了存儲(chǔ)資源，根據(jù)紋理映射機(jī)制，還可能使慢速硬盤與高速內(nèi)存、顯存之間出現(xiàn)傳輸瓶頸. 因此，在紋理打包前，需要剔除冗余紋理. 如圖2所示，根據(jù)UV坐標(biāo)裁剪原紋理圖像得到新紋理圖像并更新紋理坐標(biāo)，本文將該過(guò)程稱為紋理更新.

圖2 紋理更新Fig. 2 Textures updating

本文定義所對(duì)應(yīng)紋理坐標(biāo)超出[0，1.0]范圍的紋理為異常紋理，反之為正常紋理. 異常紋理在逐基元渲染中可有效處理，但難以進(jìn)行紋理封裝，常導(dǎo)致可視化中的紋理拉花問(wèn)題. 因此，將模型中的紋理分為正常紋理和異常紋理兩類，分別進(jìn)行去冗余，同時(shí)重置異常紋理的UV坐標(biāo)到[0，1.0]范圍內(nèi)，以便進(jìn)行后續(xù)的紋理合并.

1.1.1 正常紋理去冗余

單獨(dú)紋理即該紋理影像僅被一個(gè)面調(diào)用，共用紋理指該紋理影像被多個(gè)面調(diào)用. 根據(jù)單張紋理影像是否被多個(gè)面片使用，將模型中的正常紋理分為共用紋理和單獨(dú)紋理：共用紋理首先計(jì)算該紋理影像對(duì)應(yīng)的所有面片紋理坐標(biāo)并集，然后進(jìn)行紋理更新；單獨(dú)紋理直接進(jìn)行紋理更新，得到簡(jiǎn)化紋理. 正常紋理去冗余流程如圖3所示.

圖3 正常紋理去冗余流程Fig. 3 Flow of redundant normal textures eliminating

1.1.2 關(guān)鍵問(wèn)題：異常紋理去冗余

根據(jù)紋理集定義，被合并的紋理其UV坐標(biāo)應(yīng)在[0，1.0]范圍內(nèi). 但由于建模失誤、生產(chǎn)規(guī)范不足以及重復(fù)紋理等原因，紋理坐標(biāo)超出[0，1.0]范圍的異常情況在目前仍無(wú)法完全避免. 異常紋理獨(dú)立存在并不會(huì)影響模型的可視化效果，但若直接對(duì)其進(jìn)行打包，就可能出現(xiàn)紋理錯(cuò)誤映射等可視化問(wèn)題. 因此，在紋理合并前需要對(duì)異常紋理進(jìn)行紋理更新和坐標(biāo)重置.

首先根據(jù)紋理坐標(biāo)范圍是否超出閾值（本文為2，可根據(jù)經(jīng)驗(yàn)或?qū)嶋H情況設(shè)置）將異常紋理分為重復(fù)紋理和其他異常紋理；然后根據(jù)是否被多個(gè)面共用將其他異常紋理分為共用紋理和單獨(dú)紋理. 重復(fù)紋理即被大量重復(fù)的簡(jiǎn)單紋理（如墻磚、瓦片等）. 重復(fù)紋理復(fù)用量較大，紋理更新和紋理打包會(huì)較大程度上增加其紋理數(shù)據(jù)量，因此不進(jìn)行處理；共用紋理先計(jì)算與該紋理影像對(duì)應(yīng)所有面的紋理坐標(biāo)并集，然后進(jìn)行紋理更新；單獨(dú)紋理進(jìn)行紋理更新. 異常紋理去冗余流程如圖4所示.

圖4 異常紋理去冗余流程Fig. 4 Flow of redundant abnormal textures eliminating

如圖5所示，異常紋理之間的紋理坐標(biāo)可能相差較大，直接使用原紋理坐標(biāo)進(jìn)行并集計(jì)算可能會(huì)使得到的并集范圍很大，造成紋理更新上的困難.

圖5 紋理更新問(wèn)題Fig. 5 Problem of textures updating

由于將紋理坐標(biāo)進(jìn)行整數(shù)量偏移不會(huì)改變紋理貼圖的效果，因此在進(jìn)行并集計(jì)算前，對(duì)紋理坐標(biāo)進(jìn)行預(yù)處理，在U、V方向上各加一個(gè)整數(shù)偏移值，使紋理左下角UV坐標(biāo)值均在[0，1.0]范圍內(nèi). 如圖6所示，通過(guò)坐標(biāo)預(yù)處理，可有效解決紋理坐標(biāo)差異大帶來(lái)的紋理更新問(wèn)題.

圖6 坐標(biāo)預(yù)處理Fig. 6 Preprocessing of texture coordinates

1.2 紋理合并

精細(xì)建筑物模型碎片化紋理文件的特點(diǎn)是紋理個(gè)體小、數(shù)量多，在模型渲染時(shí)引起大量紋理狀態(tài)切換，導(dǎo)致批次數(shù)目急劇增加，嚴(yán)重影響場(chǎng)景渲染效率. 將單個(gè)建筑物模型中的大量碎片化紋理合并為一張大紋理，能夠有效提高場(chǎng)景渲染效率.

裝箱算法起源于物流運(yùn)輸，其研究目標(biāo)是求解小物品裝入大容器中的總體布局方案，并使之在特定約束條件下達(dá)到特定優(yōu)化目標(biāo)，如消耗的容器數(shù)量最少等，與紋理合并目標(biāo)具有一致性[20-22]. 因此，利用二維裝箱算法進(jìn)行紋理合并，能夠最大程度提高紋理集的空間利用率，節(jié)省存儲(chǔ)空間[23-24].

本文中的矩形定義為R={x,y,W,H}，其中：x、y為矩形左下角坐標(biāo)值；W、H為矩形的寬和高.

二維裝箱過(guò)程為：初始條件下給定容器矩形C和待插入物品矩形集合I={r1,r2,r3,···,ri,···,rn}.ri按照一定規(guī)則選擇合適區(qū)域（即自由矩形）插入后，C中放置ri的區(qū)域?yàn)檎加镁匦蝪，占用矩形集合V={v1,v2,v3,···,vn} ；C中剩余區(qū)域W被重新分割為多個(gè)自 由矩 形R，自由 矩 形 集 合U={R1,R2,R3,···,Rn}.

其中包含兩個(gè)關(guān)鍵步驟：

步驟1剩余區(qū)域分割

自由矩形是剩余區(qū)域中的最大矩形，最大的含義為該矩形在每個(gè)方向上長(zhǎng)度最大，即一個(gè)自由矩形碰到容器邊緣或者碰到容器里的占用矩形，它滿足兩個(gè)條件：① ?v∈V,R∩v= ?；② 不存在w∈W，使w.xR.W且w.H>R.H. 每次物品矩形插入后，將容器中的剩余區(qū)域重新分割為多個(gè)自由矩形，以便進(jìn)行下次插入. 如圖7所示，插入紋理1后，容器中的剩余區(qū)域可分割為2個(gè)自由矩形，分別是FHCB、EDCP；插入紋理2后，原自由矩形FHCB被刪除，生成2個(gè)新自由矩形JHCO、EDCP，因此容器中的剩余區(qū)域被重新分割為3個(gè)自由矩形，分別是KNJB、JHCO、EDCP.

圖7 剩余區(qū)域分割示意Fig. 7 Partition of residual region

步驟2自由矩形選擇

選擇R∈U，常用的搜索思想包括：① 令 min(R.W?r.W,R.H?r.H) 值最小，使較短邊長(zhǎng)度最小化；② max(R.W?r.W,R.H?r.H)值最小，使較長(zhǎng)邊長(zhǎng)度最小化；③ ?R′∈U,(R′.W×R′.H)<(R.W×R.H)；④R依次處于最下、最左的位置；⑤ c ontact(V,R) 值最大，c ontact(x,y) 為x、y兩者的接觸面長(zhǎng)度. 使用以上4種搜索算法進(jìn)行實(shí)驗(yàn)，結(jié)果表明，采用名為CP （contact point）的方法 ④ 對(duì)紋理集中的空間利用率最高，因此本文采用CP方法，即盡可能選擇與已插入矩形接觸面最大的位置插入物品矩形.

如圖8所示，紋理3依次放置到自由矩形KNCB、JHCO、EDCP中，得到的接觸長(zhǎng)度之和（圖8中的紅線長(zhǎng)度）分別為l1、l2、l3，由于紋理3為正方形，易知：l2>l1=l3，因此紋理3插入自由矩形JHCO中，獲得最大的接觸長(zhǎng)度之和l2.

經(jīng)過(guò)紋理去冗余，建筑物模型中的紋理被分為簡(jiǎn)化紋理和重復(fù)紋理. 重復(fù)紋理由于復(fù)用量較大，對(duì)其打包會(huì)較大程度上增加數(shù)據(jù)量，因此保留重復(fù)紋理，只合并簡(jiǎn)化紋理.

圖9是紋理合并的算法流程，包含以下3個(gè)步驟：

步驟1對(duì)簡(jiǎn)化紋理進(jìn)行預(yù)處理. 首先，根據(jù)預(yù)設(shè)的紋理集尺寸，將簡(jiǎn)化紋理中尺寸大于該值的紋理縮放到紋理集尺寸；然后，將所有紋理旋轉(zhuǎn)至最長(zhǎng)邊水平，并按其最長(zhǎng)邊進(jìn)行降序排列，得到排序后的待打包紋理，避免裝箱過(guò)程中產(chǎn)生插入沖突.

步驟2根據(jù)預(yù)設(shè)紋理集尺寸以及待打包紋理尺寸，生成相應(yīng)的容器矩形和物品矩形，模擬二維裝箱過(guò)程，若裝箱失敗，則對(duì)待打包紋理進(jìn)行降采樣，重新模擬裝箱，直到將全部物品成功裝入容器中為止.

步驟3根據(jù)裝箱結(jié)果，合并紋理，得到紋理集.

圖8 自由矩形選擇示意Fig. 8 Selection of free rectangle

上述將所有離散紋理合并為一張紋理集并可能對(duì)原始紋理降采樣的紋理合并方法被稱為紋理有損打包，將離散紋理合并為多張紋理集且不縮放原始紋理的紋理合并方法被稱為紋理無(wú)損打包.

圖9 紋理合并打包Fig. 9 Textures Packing

1.3 紋理重映射

紋理去冗余將紋理影像拼接、裁剪；紋理合并將紋理影像縮放、平移及旋轉(zhuǎn). 紋理坐標(biāo)隨之發(fā)生了變化，原始的映射關(guān)系已經(jīng)不再適用，因此，需要進(jìn)行紋理坐標(biāo)重映射.

紋理去冗余后，新的紋理坐標(biāo)計(jì)算方法為

式中：Umin、Vmin分別為原紋理在U、V方向上的最小值；DU、DV分別為原紋理在U、V方向上的長(zhǎng)度.

紋理合并后，新的紋理坐標(biāo)計(jì)算方法為

式中：TU、TV分別為插入紋理集的過(guò)程中紋理在U、V方向上所進(jìn)行的幾何變換信息.

2 實(shí)驗(yàn)分析

本文采用C++ 作為開(kāi)發(fā)語(yǔ)言，在Visual Studio 2015開(kāi)發(fā)平臺(tái)上進(jìn)行實(shí)驗(yàn). 實(shí)驗(yàn)系統(tǒng)微機(jī)硬件配置如下：CPU，Intel（R）Core（TM）i7-5500U CPU @2.40 GHz；內(nèi)存，12.00 GB；顯卡，NVIDIA GeForce GT940M. 實(shí)驗(yàn)數(shù)據(jù)是某區(qū)域建筑群，數(shù)據(jù)格式為Wavefront obj.

表1為8個(gè)建筑物模型的紋理數(shù)據(jù)統(tǒng)計(jì)結(jié)果，橫軸為單位為KB的紋理數(shù)據(jù)量大小. 由表1可知：各模型中數(shù)據(jù)量為1KB和2KB的紋理文件數(shù)量之和最小為58.6%，最大為85.7%，在70%～80%范圍內(nèi)的有4個(gè)，在60%～70%范圍內(nèi)的有2個(gè)，可見(jiàn)該區(qū)域建筑群模型的紋理碎片化程度較高，具有典型代表性，因此使用該區(qū)域建筑群模型進(jìn)行紋理優(yōu)化實(shí)驗(yàn)是適宜的.

表1 原始模型紋理數(shù)據(jù)統(tǒng)計(jì)結(jié)果Tab. 1 Statistics results of original model textures data

利用同樣使用二維裝箱算法的MaxRectsBin-Pack方法[15]與本文方法進(jìn)行對(duì)比分析，以證明本文主要?jiǎng)?chuàng)新點(diǎn)紋理去冗余步驟的優(yōu)越性. 設(shè)定紋理集尺寸為2048 × 2048，紋理縮放系數(shù)為1，實(shí)驗(yàn)結(jié)果如下：

1） 在紋理數(shù)據(jù)量方面，如表2所示，在紋理數(shù)據(jù)量較小或模型中異常紋理及冗余紋理較少的情況下，本文方法與MaxRectsBinPack方法的結(jié)果相近，如模型1、3、4、7；但在紋理數(shù)據(jù)量較大或模型中存在較多異常紋理及冗余紋理的情況下，本文方法具有明顯優(yōu)勢(shì)，如模型2、5、6、8. 整個(gè)建筑群模型使用本文方法，紋理數(shù)據(jù)量減少了71.20%.

表 2 紋理數(shù)據(jù)對(duì)比結(jié)果Tab. 2 Textures data comparison MB

2） 在載入與繪制效率方面，如表3所示，整個(gè)建筑群經(jīng)過(guò)本文方法和MaxRectsBinPack方法處理后紋理文件由4281銳減為27和125個(gè)，分別減少了99.37%和97.08%. 在OSGViewer中進(jìn)行可視化實(shí)驗(yàn)，與原始模型相比，本文方法與MaxRectsBinPack方法的載入耗時(shí)由225.00 s銳減為個(gè)位數(shù)，其中本文方法減少了98.86%，明顯優(yōu)于后者；本文方法的GPU耗時(shí)減少了63.06%，優(yōu)于MaxRectsBinPack方法，兩者結(jié)果均優(yōu)于原始模型；兩種方法的渲染幀率與原始模型相比均無(wú)明顯變化.

表3 載入與繪制效率對(duì)比Tab. 3 Load and draw efficiency comparison

3） 在可視化效果方面，本文方法可有效避免異常紋理引起的紋理錯(cuò)誤映射問(wèn)題. 一張UV坐標(biāo)為（1.0，0）、（2.0，0）、（2.0，1.0）、（2.0，1.0）的異常紋理在使用本文方法模型中貼圖正確，而在使用MaxRectsBinPack方法模型中出現(xiàn)貼圖錯(cuò)誤.

圖10（a）為異常紋理對(duì)應(yīng)的紋理集，靠左矩形線框住的部分是正確紋理，靠右矩形線框住的是由于直接對(duì)異常紋理進(jìn)行打包導(dǎo)致被錯(cuò)誤映射的紋理，圖10（b）為異常紋理在使用本文方法模型中的可視化效果，圖10（c）為異常紋理在使用MaxRects-BinPack方法模型中的可視化效果. 圖11是建筑群模型在OpenSceneGraph中的可視化效果.

圖10 模型中的異常紋理Fig. 10 Abnormal textures in models

圖11 建筑群模型Fig. 11 Building complex model

4） 在算法效率方面，如表4所示，在模型紋理文件數(shù)量或冗余數(shù)據(jù)量處于平均水平時(shí)，本文方法在紋理去冗余步驟耗時(shí)較少，在紋理合并步驟耗時(shí)少于MaxRectsBinPack，如模型1、3、4、5、7、8；在紋理文件數(shù)量或冗余紋理數(shù)據(jù)量非常大時(shí)可能出現(xiàn)異常，如本文方法剔除了模型2中的大量冗余紋理后紋理合并步驟耗時(shí)大大減少，而經(jīng)過(guò)紋理去冗余步驟模型6中得到大量小尺寸紋理，使一個(gè)紋理集中要容納大量小紋理，增加了紋理合并步驟耗時(shí). 在紋理重映射步驟，兩種方法耗時(shí)相近.

表4 算法效率對(duì)比（耗時(shí)）Tab. 4 Algorithm efficiency comparison (time) s

3 結(jié)束語(yǔ)

本文提出了一種精細(xì)建筑物模型碎片化紋理優(yōu)化的二維裝箱方法. 實(shí)驗(yàn)表明，相比傳統(tǒng)紋理合并方法：該方法能夠有效解決傳統(tǒng)紋理合并方法在打包UV坐標(biāo)超出[0，1]范圍紋理時(shí)引起紋理錯(cuò)誤映射的問(wèn)題；該方法能夠在不犧牲紋理分辨率的前提下，顯著減少紋理數(shù)據(jù)量，解決了紋理合并中存儲(chǔ)空間與繪制效率無(wú)法兩全的難題. 本文方法無(wú)需人工經(jīng)驗(yàn)和手動(dòng)操作，自動(dòng)化程度高，但由于增加了紋理去冗余操作，本文方法的算法復(fù)雜度有所增加. 進(jìn)一步的研究將針對(duì)多建筑物共用紋理集的實(shí)例進(jìn)行優(yōu)化，提升大規(guī)模城市場(chǎng)景中重復(fù)建筑物的渲染效率以及大規(guī)模城市場(chǎng)景多細(xì)節(jié)層次紋理的簡(jiǎn)化與合并.

致謝：國(guó)土資源部城市地監(jiān)測(cè)與仿真重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題（KF-2016-02-022，KF-2016-02-021）.