基于二叉樹(shù)結(jié)點(diǎn)優(yōu)化的矩形裝箱紋理優(yōu)化方法

馬東嶺朱悅凱李銘通

(山東建筑大學(xué)測(cè)繪地理信息學(xué)院，山東 濟(jì)南 250101)

0 引言

實(shí)景三維模型可以推動(dòng)城市數(shù)字化、智慧化發(fā)展，其建模技術(shù)在完善智慧城市空間數(shù)據(jù)體系中具有重要作用[1]。 當(dāng)前，基于傾斜攝影的大場(chǎng)景實(shí)景三維建模技術(shù)發(fā)展迅速，模型的數(shù)據(jù)量也在飛速增加。 隨著多源數(shù)據(jù)融合建模技術(shù)的不斷發(fā)展[2]，在構(gòu)網(wǎng)階段會(huì)建立更加精細(xì)的白模，生成數(shù)量更多的三角面元，而每個(gè)面元都會(huì)對(duì)應(yīng)一個(gè)碎片化紋理；同時(shí)，相機(jī)配置的發(fā)展提高會(huì)取得更加真實(shí)豐富的紋理信息，隨之而來(lái)的就是單個(gè)紋理文件數(shù)據(jù)大小的增加。 因此，在紋理映射階段要處理數(shù)量更多、單個(gè)紋理大小更大的紋理文件。 在紋理映射的過(guò)程中:(1) 通過(guò)坐標(biāo)確定有效紋理的區(qū)域，利用這種紋理單體化的方式除去了大量的冗余紋理；(2) 通過(guò)建立面元最小外接矩形角點(diǎn)的紋理坐標(biāo)、影像坐標(biāo)與物方空間坐標(biāo)之間的聯(lián)系，將紋理映射到三維模型表面上[3]。 若是對(duì)海量的碎片化紋理不加處理直接渲染，則會(huì)占據(jù)大量?jī)?nèi)存資源。 而如果封裝和優(yōu)化碎片化紋理，則可以減輕CPU 負(fù)擔(dān)，減少磁盤讀寫(xiě)次數(shù)，并充分利用GPU 的批處理能力，減輕內(nèi)存和磁盤的存儲(chǔ)負(fù)擔(dān)。 因此，如何將碎片化紋理更加充分地打包和封裝，成為當(dāng)前實(shí)景三維建模技術(shù)中紋理優(yōu)化的重要研究問(wèn)題。

針對(duì)此問(wèn)題，將碎片化紋理打包封裝的問(wèn)題轉(zhuǎn)化為二維矩形裝箱問(wèn)題，即將若干離散矩形按一定規(guī)則放入某一較大的已有矩形容器，使得容器的空間利用最大化。 早期一些學(xué)者采用了優(yōu)先左下角的方法(Bottom－Left，BL):BAKER 等[4]采用的BL 方法通過(guò)盡可能向下、向左地順序放置每個(gè)矩形；HOPPER 等[5]提出在許多不同的矩形序列上執(zhí)行基于BL 的啟發(fā)式算法并選擇最佳結(jié)果，其可稱為左下遞減(Bottom－Left－Decreasing ，BLD)；鄭巧仙等[6]改進(jìn)了左下角定位模型，提出了可旋轉(zhuǎn)的二維矩形裝箱模型。 這一方法雖實(shí)現(xiàn)較為簡(jiǎn)單，但其無(wú)法充分利用矩形容器的空間，裝箱效果有待進(jìn)一步改善。

另一種常見(jiàn)的方法是基于某種最佳擬合度量(Best Fit，BF)選擇矩形及其位置，而不是對(duì)左下角的位置優(yōu)先級(jí)排序。 BURKE 等[7]提出了包括一系列優(yōu)先權(quán)規(guī)則的最佳擬合方法，其會(huì)在矩形列表中搜索更好的矩形優(yōu)先存放；馬康等[8]提出了一種改進(jìn)的最低水平線搜索算法，通過(guò)判斷排樣中產(chǎn)生廢棄空閑區(qū)域的位置關(guān)系，對(duì)鄰接的空閑區(qū)域有效的合并，并結(jié)合分布估計(jì)算法求解矩形件排樣優(yōu)化問(wèn)題；TAM 等[9]利用最小自由度優(yōu)先方法，依次填充邊界區(qū)域內(nèi)的空白“角落”—空白空間的邊界線—其他空白區(qū)域；梁利東等[10]基于多目標(biāo)優(yōu)化的擇優(yōu)匹配啟發(fā)式方法，先定義排樣空間和匹配值，計(jì)算入排零件與排樣空間的寬、高匹配值，再建立統(tǒng)一的多目標(biāo)優(yōu)化函數(shù)模型，并根據(jù)目標(biāo)函數(shù)值的大小確定排放優(yōu)先規(guī)則。 但是這一方法會(huì)產(chǎn)生很多難以利用的內(nèi)部碎片。

為了避免陷入局部最優(yōu)，也有一些學(xué)者嘗試了幾種元啟發(fā)式方法[11－13]:WEI 等[14]利用最小浪費(fèi)優(yōu)先(Least Wasted First ，LWF)策略，評(píng)估矩形所使用的位置，再引入隨機(jī)局部搜索以改進(jìn)搜索結(jié)果；尚正陽(yáng)等[15]提出了一種改進(jìn)的最優(yōu)剩余空間算法，采用貪婪策略作為最優(yōu)放置策略，矩形的面積越大、其放置坐標(biāo)越小，則越優(yōu)先將其存入；WEI 等[16]研究了貪婪啟發(fā)式的裝箱算法，用一組水平線表示當(dāng)前的裝箱狀態(tài)，每段水平線的左端點(diǎn)或右端點(diǎn)為坐標(biāo)點(diǎn)，將小矩形按順序放置在大矩形中，使矩形的左下角或右下角接觸坐標(biāo)點(diǎn)，每次放置矩形后更新上界線和坐標(biāo)點(diǎn)，但這種方法在矩形數(shù)量較少時(shí)效果一般；陳其賽等[17]在方法[16]的基礎(chǔ)上，引入帶適應(yīng)度值的skyline 裝箱策略，改進(jìn)了禁忌搜索－遺傳混合算法；SCOTT[18]提出了一種基于二叉樹(shù)的矩形裝箱方法，在放入一個(gè)矩形后將剩余空間劃分為兩個(gè)子結(jié)點(diǎn)，并判斷下一個(gè)矩形能否放在這些結(jié)點(diǎn)所代表的矩形空間中。 這種方法在少量離散矩形的裝箱問(wèn)題中空間利用率比上界線算法更高，但是在大量矩形的情況下會(huì)優(yōu)先選取面積較大的位置，造成空間利用率的浪費(fèi)；朱慶等[19]采用基于最大接觸長(zhǎng)度的矩形裝箱算法，使矩形存入后與剩余空間接觸長(zhǎng)度最長(zhǎng)，但需不斷計(jì)算存入矩形與剩余空間的接觸總長(zhǎng)度；翁其強(qiáng)[20]基于自由域分割的最大矩形裝箱算法，在存入矩形后使剩余邊長(zhǎng)最短，但其在每次插入新的矩形后都須考慮新矩形對(duì)剩余空間的擾動(dòng)，在算法上均較為復(fù)雜；王曉坤[21]采用了先利用最大矩形紋理面積與其余矩形紋理面積的差計(jì)算容器面積再進(jìn)行矩形存放的方法，但沒(méi)有考慮剩余空間分割后放置的順序，會(huì)造成容器空間的浪費(fèi)。

綜上所述，基于BL 的二維矩形裝箱算法沒(méi)有考慮矩形存入順序，基于BF 的算法對(duì)于矩形存入后容器的剩余空間沒(méi)有合理利用，而其他一些元啟發(fā)式方法對(duì)于剩余空間被訪問(wèn)的順序沒(méi)有處理，因此都對(duì)矩形裝箱算法的空間利用率產(chǎn)生了一定影響。 文章以紋理數(shù)據(jù)處理中的紋理合并為重點(diǎn)，針對(duì)上述方法存在的問(wèn)題，在二叉樹(shù)矩形裝箱算法的基礎(chǔ)上改進(jìn)，優(yōu)化二叉樹(shù)結(jié)點(diǎn)數(shù)組，按照矩形的面積從大到小作為存入順序，對(duì)于矩形存入后的剩余空間按照合理的面積比最大原則分割，并優(yōu)化了剩余空間被訪問(wèn)的順序。 文章開(kāi)展了一系列的實(shí)驗(yàn)驗(yàn)證此種方法的效果，以期解決矩形優(yōu)先被存放在容器中對(duì)角線位置而造成的空間浪費(fèi)問(wèn)題，進(jìn)一步提升容器的空間利用率，使得三維建模在紋理映射的過(guò)程中可以更加高效地對(duì)大量的紋理進(jìn)行操作，減少了內(nèi)存資源的浪費(fèi)。

1 二維矩形裝箱紋理優(yōu)化方法

文章提出的基于二叉樹(shù)結(jié)點(diǎn)優(yōu)化的二維矩形裝箱紋理優(yōu)化方法主要可分為預(yù)處理、矩形存放和結(jié)點(diǎn)數(shù)組優(yōu)化等3 步。 整體流程圖如圖1 所示。

圖1 整體流程圖

1.1 預(yù)處理

二維矩形裝箱方法中的預(yù)處理即對(duì)二維矩形組成的數(shù)組排序。 在影像被加載后，通過(guò)影像的紋理坐標(biāo)與三維模型的坐標(biāo)確定紋理的有效區(qū)域，去除整張影像中無(wú)用的冗余區(qū)域，得到紋理碎片。 由于從影像中獲取的紋理碎片是雜亂無(wú)序的，如果按照其本來(lái)的順序存放，會(huì)降低紋理集的空間利用率。二維矩形存入容器示意圖如圖2 所示。 將待裝箱紋理矩形存入矩形容器中，圖2(a)為未經(jīng)過(guò)預(yù)處理存入示意圖，其存入順序?yàn)閎－>e－>c－>d－>a；圖2(b)為預(yù)處理后的存入示意圖，其存入順序?yàn)閑－>d－>c－>b－>a。 可以看到，在圖2(a)中，由于矩形存入順序混亂，空間利用不合理，導(dǎo)致矩形a 無(wú)法存入容器；而圖2(b)中5 個(gè)矩形可以全部被存入容器。 因此，為了避免二維裝箱過(guò)程中產(chǎn)生插入沖突而影響算法結(jié)果，在裝箱前要將所有待裝箱矩形紋理按一定規(guī)則排列。 常用的排序方式有高、寬、面積、周長(zhǎng)。文章通過(guò)對(duì)比4 種排序方法實(shí)驗(yàn)可知，按照矩形的面積排序的容器空間利用率最高。 設(shè)矩形數(shù)組I ＝{r1，r2，…，rn}、ri ＝{xi，yi，wi，hi} ，其中xi、yi為矩形i左下角坐標(biāo)；wi、hi分別為矩形i的寬、高，pixel。采用快速排序的方法，排序后的數(shù)組應(yīng)滿足表達(dá)式，由式(1)表示為

圖2 二維矩形存入容器示意圖

1.2 矩形紋理存放

給定一個(gè)按照面積大小排序的矩形紋理組成的數(shù)組，將其依次存入一個(gè)矩形紋理集中。 文章中的矩形紋理集R定義由式(2)表示為

式中x和y分別為矩形紋理集左下角的坐標(biāo)；w和h分別為矩形紋理集的寬度和高度，pixel。

所研方法采用了二叉樹(shù)的思想，原始容器為根結(jié)點(diǎn)，給定一系列小矩形I ＝{r1，r2，r3，r4，…}，在一個(gè)矩形ri存放進(jìn)去后，剩余空間可以劃分為2 個(gè)較小的矩形區(qū)域，即為兩個(gè)子結(jié)點(diǎn)S和L，分別表示面積較小、較大的空間。 矩形①存入容器后示意圖及其對(duì)應(yīng)二叉樹(shù)結(jié)構(gòu)圖如圖3 所示。 可以看出，剩余空間可以分割成A、B 兩部分。

圖3 矩形①存入容器后示意圖及其對(duì)應(yīng)二叉樹(shù)結(jié)構(gòu)圖

接著存入下一個(gè)矩形②，將其存入后子結(jié)點(diǎn)繼續(xù)向下分為新的子結(jié)點(diǎn)。 矩形②存入容器后如圖4(a)所示，將矩形②存入結(jié)點(diǎn)A，并將結(jié)點(diǎn)A 的剩余空間分成C 和D；其二叉樹(shù)結(jié)構(gòu)如圖4(b)所示。

圖4 矩形②存入容器后示意圖與其對(duì)應(yīng)二叉樹(shù)結(jié)構(gòu)圖

在對(duì)剩余部分分割時(shí)，需遵循一定的規(guī)則使容器的空間利用率更高，即分割后兩個(gè)空間的面積差最大。 圖5 表示將矩形①存入容器后兩種不同的分割方法。 假設(shè)矩形①存入容器后，容器的剩余寬rw和剩余高rh的關(guān)系為rh < rw，則通過(guò)推算可知新生成的4 個(gè)空白矩形空間A、B、A′、B′中，矩形空間B 的面積最大。 因此，圖5(b)可以獲得更大的空白區(qū)域來(lái)存放更大的矩形，對(duì)提高容器的空間利用率有一定的幫助。

圖5 對(duì)剩余部分的兩種分割方法圖

為了達(dá)到這種效果，在存放進(jìn)一個(gè)矩形后，可判斷其剩余空間的邊長(zhǎng)。

設(shè)矩形存入容器后剩余寬度和剩余高度為rw、rh，并由式(3)表示為

若rh < rw，則新生成的矩形空間可由式(4)表示為

否則，由式(5)表示為

式中xnode、ynode、wnode、hnode分別為當(dāng)前結(jié)點(diǎn)代表空間的x、y坐標(biāo)以及寬高，pixel。 在實(shí)際紋理合并過(guò)程中，在當(dāng)前矩形紋理被存入紋理集后，剩余的空間將按照上述規(guī)則可分割成兩部分，并生成代表這兩部分的新結(jié)點(diǎn)。 而結(jié)點(diǎn)數(shù)組中刪除了代表當(dāng)前空間的結(jié)點(diǎn)，存入新生成的結(jié)點(diǎn)。 為了優(yōu)先利用面積較小的區(qū)域，從而充分利用紋理集的空間，文章在當(dāng)前矩形紋理存放完后優(yōu)化了結(jié)點(diǎn)數(shù)組，再存放下一個(gè)矩形紋理。

1.3 結(jié)點(diǎn)數(shù)組優(yōu)化

常規(guī)的二叉樹(shù)矩形紋理合并方法利用一個(gè)數(shù)組存放所有的空白結(jié)點(diǎn)，每次存入一個(gè)矩形紋理之后，將當(dāng)前結(jié)點(diǎn)彈出數(shù)組，再將新生成的兩個(gè)子結(jié)點(diǎn)存入數(shù)組的末尾。 在下一個(gè)矩形存放時(shí)，判斷數(shù)組中最后一個(gè)結(jié)點(diǎn)是否可以存入，若存放不下則判斷倒數(shù)第二個(gè)結(jié)點(diǎn)，以此類推。 由于新生成的空間多為面積較大的對(duì)角線位置，因此矩形會(huì)優(yōu)先存入這些位置，而邊界處的空間往往不會(huì)被迭代到，造成空間浪費(fèi)。

為了解決這個(gè)問(wèn)題，文章在此方法基礎(chǔ)上改進(jìn)，在下一個(gè)矩形存放前對(duì)結(jié)點(diǎn)在數(shù)組中的排列順序優(yōu)化處理，按照結(jié)點(diǎn)所代表空間的面積從大到小排序，這樣數(shù)組末尾位置的結(jié)點(diǎn)代表的就是面積最小的空間，即整個(gè)容器的邊角處區(qū)域。 在存放時(shí)優(yōu)先將矩形存入面積最小的空間，使這些面積較小的空間可以得到充分利用。 當(dāng)矩形紋理r存入時(shí)，對(duì)結(jié)點(diǎn)數(shù)組從后向前遍歷，第一個(gè)能滿足Si < Sr的結(jié)點(diǎn)i所代表的空間即為該矩形紋理存放的位置。 如圖6 所示，將結(jié)點(diǎn)數(shù)組[A，C，B]按照結(jié)點(diǎn)A、B 和C 所代表的空間面積大小順序重新排序，排序后為[C，B，A]。 在下一個(gè)矩形存入時(shí)，先對(duì)結(jié)點(diǎn)A 判斷，若A存放不下則判斷結(jié)點(diǎn)B，以此類推。 這種方式充分利用了紋理集的空間，也避免了原本面積較大的結(jié)點(diǎn)被分割得更加破碎，進(jìn)而提升了整個(gè)紋理集的空間利用率，使紋理合并的效果更加緊湊。

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

2.1 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)環(huán)境

為驗(yàn)證文章提出的基于二叉樹(shù)結(jié)點(diǎn)優(yōu)化的二維矩形裝箱方法的有效性，利用程序隨機(jī)生成若干矩形，并設(shè)置兩組實(shí)驗(yàn)分別對(duì)大量矩形和少量矩形兩種情況進(jìn)行裝箱效果測(cè)試。 第一組實(shí)驗(yàn)生成150 個(gè)矩形，其長(zhǎng)、寬尺寸為<600 的隨機(jī)整數(shù)；第二組實(shí)驗(yàn)生成5 000 個(gè)矩形，其長(zhǎng)、寬尺寸為<100 的隨機(jī)整數(shù)。 設(shè)定容器尺寸均為4 096 pixel × 4 096 pixel。(1) 驗(yàn)證1.1 節(jié)對(duì)矩形所采用的排序方式的合理性；(2) 驗(yàn)證1.2 節(jié)中剩余空間分割規(guī)則對(duì)整個(gè)裝箱結(jié)果的影響；(3) 通過(guò)對(duì)比實(shí)驗(yàn)的方法驗(yàn)證所研方法在矩形裝箱中效果的提升。

文章采用C＋＋作為開(kāi)發(fā)語(yǔ)言，在Visual Studio 2019 開(kāi)發(fā)平臺(tái)上實(shí)驗(yàn)。 實(shí)驗(yàn)系統(tǒng)微機(jī)硬件配置如下:CPU，Intel(R)Core(TM)i7－6700 CPU ＠3.40 GHz；內(nèi)存，8.00 GB；顯卡，NVIDIA GeForce GTX 1060 3 GB。

2.2 對(duì)矩形排序方式的對(duì)比

利用程序隨機(jī)生成的150 和5 000 個(gè)矩形，將其存入一個(gè)長(zhǎng)、寬均為4 096 的容器中，分別采用不排序以及按照寬、高、周長(zhǎng)、面積排序的方式。 計(jì)算5 種排序方式的空間利用率，見(jiàn)表1。

由表1 可知:對(duì)于150 個(gè)的少量矩形而言，不對(duì)矩形預(yù)處理最后的空間利用率為89%；對(duì)矩形預(yù)處理后空間利用率有不同程度的提高，其中按照矩形面積排序時(shí)空間利用率可達(dá)95.5%，比不排序提高了6.5%。 當(dāng)矩形數(shù)量增加至5 000 個(gè)時(shí)，不進(jìn)行預(yù)處理的空間利用率為88.6%；如果按照矩形的寬、高或周長(zhǎng)來(lái)排序會(huì)造成空間利用率的降低，而按照面積排序的預(yù)處理方式可以得到最高的空間利用率為91.3%，比不排序提高了2.7%。 由此可知，在對(duì)矩形預(yù)處理時(shí)，按照矩形面積排序可以達(dá)到最高的空間利用率。 另外，矩形的預(yù)處理對(duì)于裝箱效果的提升對(duì)少量矩形來(lái)說(shuō)更為明顯。 5 種排序方式的裝箱結(jié)果如圖7 和8 所示。

由圖7 和8 可知，不論矩形的數(shù)量多少，前4 種方式都不同程度地出現(xiàn)了剩余空間不齊整的情況(箭頭處)。 而按照矩形的面積排序可以最大程度地利用容器的空間，使得剩余空間可以更加高效地存放更多的矩形。

2.3 剩余空間分割對(duì)比

對(duì)1.2 節(jié)中的當(dāng)前矩形存放完畢后剩余空間的分割規(guī)則實(shí)驗(yàn)驗(yàn)證，對(duì)比分析了是否使用該規(guī)則的裝箱效果，實(shí)驗(yàn)結(jié)果如圖9 所示。 圖9(a)和(b)為不使用分割規(guī)則的裝箱結(jié)果，圖9(c)和(d)為使用分割規(guī)則的裝箱結(jié)果。

圖9 分割規(guī)則對(duì)裝箱結(jié)果的影響圖

由圖9(a)和(b)可以看出，若不使用該分割規(guī)則，后續(xù)的矩形在存入容器時(shí)會(huì)優(yōu)先在上一矩形所在橫排存放。 這就導(dǎo)致該橫排上部的空間分割得更加破碎，后續(xù)沒(méi)有矩形能夠存入該區(qū)域，造成了空間上的浪費(fèi)。 而由圖9(c)和(d)可以看出，采用所提空間分割規(guī)則可以對(duì)剩余空間有效地規(guī)劃，在分割時(shí)盡可能地保留了更加完整的空間，在存放時(shí)有效利用了后續(xù)矩形。

使用分割規(guī)則和不使用分割規(guī)則實(shí)驗(yàn)后得到的空間利用率見(jiàn)表2。

由表2 可知，相較于不使用分割規(guī)則，使用分割規(guī)則對(duì)于裝箱空間利用率分別提升了約40%和46.5%，并均提升了近1 倍。 因此，剩余空間的有效分割對(duì)于最后的裝箱結(jié)果有著重要作用。

2.4 裝箱效果對(duì)比

為證明所研方法中對(duì)結(jié)點(diǎn)數(shù)組的優(yōu)化在矩形紋理裝箱過(guò)程中的作用，利用Scott 提出的Binary Tree裝箱方法[18]與所研方法對(duì)比分析。 裝箱結(jié)果如圖10 所示。

圖10 兩種裝箱方法的裝箱結(jié)果圖

圖10(a)和(b)是Binary Tree 方法的裝箱結(jié)果，可以看出，面積更大的矩形更優(yōu)先存放在容器對(duì)角線的位置上，而這會(huì)導(dǎo)致剩余空間的破碎化，不利于后續(xù)矩形的存放。 圖10(c)和(d)為所研方法對(duì)剩余部分結(jié)點(diǎn)數(shù)組優(yōu)化后的裝箱結(jié)果，可以看出，矩形在存放的時(shí)候更優(yōu)先存放于容器的邊上，可以更加有效地利用容器的空間。 兩組實(shí)驗(yàn)結(jié)果說(shuō)明，針對(duì)于少量矩形和大量矩形，所研方法的裝箱效果均優(yōu)于Binary Tree 方法。 兩種裝箱方法在不同矩形數(shù)量實(shí)驗(yàn)中的空間利用率和效率對(duì)比表見(jiàn)表3。

表3 兩種裝箱方法的裝箱空間利用率與效率對(duì)比表

由表3 可知，相比于Binary Tree 方法的空間利用率，所研方法分別提高了11.7%和16.2%，其值可達(dá)90%以上。 在效率方面，當(dāng)模型紋理數(shù)量較少時(shí)，兩種方法在耗時(shí)方面相當(dāng)，但是由于所研方法增加了剩余結(jié)點(diǎn)排序的步驟，因此在紋理數(shù)量非常大時(shí)會(huì)造成裝箱效率降低。 然而，相比于Binary Tree方法，所研方法主要優(yōu)化了紋理集邊緣空間的利用，因此能夠提高裝箱的空間利用率，可以使矩形容器存入更多的矩形，相同數(shù)量的紋理可以打包成更少的紋理集，進(jìn)而減少了三維重建紋理映射過(guò)程中的讀取操作次數(shù)，減輕了內(nèi)存和磁盤負(fù)擔(dān)。

2.5 傾斜影像數(shù)據(jù)實(shí)驗(yàn)效果對(duì)比

為了驗(yàn)證所研方法在傾斜影像實(shí)際應(yīng)用中的效果，文章結(jié)合實(shí)際二維紋理數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證了紋理打包過(guò)程。 文章選取長(zhǎng)春市長(zhǎng)春公園的部分傾斜影像數(shù)據(jù)，該數(shù)據(jù)使用大疆精靈4P 無(wú)人機(jī)搭載5 鏡頭采集，單幅影像的像幅大小為5 456 pixel×3 632 pixel。 通過(guò)Context Capture 軟件獲取了139 個(gè)碎片化紋理文件，分別采用文獻(xiàn)[18]方法和所研方法進(jìn)行紋理打包:(1) 批量讀入碎片化紋理，提取紋理的寬高信息，生成矩形紋理數(shù)組；(2) 利用所研算法紋理合并，生成矩形紋理左下角點(diǎn)在紋理集中的坐標(biāo)并存入矩形紋理數(shù)組；(3) 利用OpenCV 庫(kù)將其合并到一張紋理集上并輸出。 兩種方法生成的紋理集效果圖如圖11所示。

圖11 兩種方法生成的紋理集效果圖

由圖11 可以看出，由于Binary Tree 方法更優(yōu)先將紋理存入紋理集的對(duì)角線位置，因此造成了在紋理集邊界位置的空間浪費(fèi)。 相比于Binary Tree 方法，所研方法會(huì)優(yōu)先選擇邊界位置的空間，使整個(gè)空間利用得更加合理，相同數(shù)量的紋理經(jīng)過(guò)打包后節(jié)省了約50%的空間。 因此在紋理集文件大小方面，Binary Tree 方法生成的紋理集文件大小為1.16 MB，而所研方法生成的紋理集文件大小僅為0.88 MB，縮小了約35%，節(jié)約了磁盤空間。 而在裝箱效率方面，Binary Tree 方法和所研方法耗時(shí)分別為0.025、0.022 s，表明在矩形紋理數(shù)量不多時(shí)，兩種方法耗時(shí)相當(dāng)。

綜上所述，所研方法與Binary Tree 方法相比，在矩形數(shù)量合適的情況下兩種方法的效率相當(dāng)，而所研方法在邊緣利用方面更具優(yōu)勢(shì)，能使矩形容器的邊緣空間得到充分的利用，提高了整體的空間利用率，裝箱后的紋理集文件大小顯著減小，節(jié)約了磁盤空間，減輕了后續(xù)讀寫(xiě)處理的內(nèi)存壓力。

3 結(jié)論

針對(duì)目前三維建模紋理映射過(guò)程中碎片紋理磁盤讀寫(xiě)的優(yōu)化問(wèn)題，文章以紋理數(shù)據(jù)處理中的紋理合并為重點(diǎn)，提出了一種基于二叉樹(shù)結(jié)點(diǎn)優(yōu)化的二維矩形紋理裝箱方法。 經(jīng)研究得到的主要結(jié)論如下:

(1) 在碎片化紋理合并之前對(duì)其排序預(yù)處理可以避免因順序混亂而導(dǎo)致的插入沖突，其中按照矩形面積排序的方法效果最好，與不排序直接紋理合并相比空間利用率提高了約5%。

(2) 在矩形存入后對(duì)剩余空間按照面積差最大的原則分割可以使紋理合并的空間利用率提高約1 倍。

(3) 相較于傳統(tǒng)的基于二叉樹(shù)的紋理合并方法，文章側(cè)重對(duì)紋理集的邊緣空間利用。 無(wú)論對(duì)于少量矩形還是大量矩形，通過(guò)對(duì)二叉樹(shù)結(jié)點(diǎn)數(shù)組的優(yōu)化均能使紋理合并的利用率提高>10%，而合并后的紋理集文件大小也可縮小35%，為后續(xù)紋理重映射過(guò)程中的磁盤讀寫(xiě)和內(nèi)存減輕了壓力。