朱 慶 ，張琳琳 ，胡 翰 ，翁其強 ，丁雨淋 ，李 赟 ，張葉廷

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

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

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

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

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

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

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

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

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

圖1 算法流程Fig. 1 Algorithm flowchart

1.1 紋理去冗余

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

圖2 紋理更新Fig. 2 Textures updating

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

1.1.1 正常紋理去冗余

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

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

1.1.2 關鍵問題：異常紋理去冗余

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

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

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

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

圖5 紋理更新問題Fig. 5 Problem of textures updating

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

圖6 坐標預處理Fig. 6 Preprocessing of texture coordinates

1.2 紋理合并

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

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

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

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

其中包含兩個關鍵步驟：

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

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

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

步驟2自由矩形選擇

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

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

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

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

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

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

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

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

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

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

1.3 紋理重映射

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

紋理去冗余后，新的紋理坐標計算方法為

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

紋理合并后，新的紋理坐標計算方法為

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

2 實驗分析

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

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

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

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

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

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

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

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

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

圖10（a）為異常紋理對應的紋理集，靠左矩形線框住的部分是正確紋理，靠右矩形線框住的是由于直接對異常紋理進行打包導致被錯誤映射的紋理，圖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ù)量處于平均水平時，本文方法在紋理去冗余步驟耗時較少，在紋理合并步驟耗時少于MaxRectsBinPack，如模型1、3、4、5、7、8；在紋理文件數(shù)量或冗余紋理數(shù)據(jù)量非常大時可能出現(xiàn)異常，如本文方法剔除了模型2中的大量冗余紋理后紋理合并步驟耗時大大減少，而經(jīng)過紋理去冗余步驟模型6中得到大量小尺寸紋理，使一個紋理集中要容納大量小紋理，增加了紋理合并步驟耗時. 在紋理重映射步驟，兩種方法耗時相近.

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

3 結束語

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

致謝：國土資源部城市地監(jiān)測與仿真重點實驗室開放課題（KF-2016-02-022，KF-2016-02-021）.