精细建筑物碎片化纹理优化的二维装箱方法
2021-06-06张琳琳翁其强丁雨淋张叶廷
朱 庆 ，张琳琳 ，胡 翰 ，翁其强 ，丁雨淋 ，李 赟 ，张叶廷
（1. 西南交通大学地球科学与环境工程学院，四川 成都 611756；2. 武汉大学测绘遥感信息工程国家重点实验室，湖北 武汉 430079；3. 浙江中海达空间信息技术有限公司，浙江 湖州 313200）
随着多源数据多细节层次建模技术的不断发展[1-2]，三维城市模型的精细程度不断提高，几何、纹理数据量呈几何级数增长[3-4]. 结构复杂的精细建筑物模型，如LOD-3 （level of detail-3）建筑物模型，一个窗户有多个平面，每个平面对应一个碎片化纹理[5].现有三维可视化引擎，如Microsoft XNA、Unity 3D等，通常不支持多纹理模式，需要将三维格网分割成多个简单的平面，每平面对应一个单独的纹理，对不同材质纹理需通过多次指令逐一渲染. 由于每个平面都会单独调用CPU （central processing unit）指令进行绘制，增加了模型加载压力，降低了渲染效率，无法充分利用图像处理器（graphics processing unit，GPU）批处理机制，难以满足大规模城市三维模型应用需求. 因此，如何将碎片化纹理进行封装和优化，减轻CPU负担，提高GPU加载和绘制效率，减少磁盘读取操作次数，成为当前倾斜摄影测量三维城市模型集成应用的关键问题.
现有纹理合并工具依赖人工经验，自动化程度低，应用局限较大，如NVIDIA公司的纹理工具软件（texture tools），Autodesk公司3DMax软件的UVWUnWrap工具，使用ISOMAP的商业软件，以及Open-SceneGraph的NodeOptimizer. 三维模型的纹理组织方法可分为连续表面模型的纹理组织方法和离散表面模型的纹理组织方法：连续表面模型的纹理组织方法已有成熟应用，如Google Earth、Virtual Earth，主要方法为硬件支持的切片图方法[6]和瓦片影像金字塔方法[7]；离散表面模型的纹理组织方法有Blockmap方法[8]，纹理集（texture atlas）方法[9]等. 目前相关的大部分研究主要着眼于如何更优的进行纹理合并[10-18]，虽然在一定程度上减少了纹理文件个数，但因模型中存在UV坐标超出[0，1]范围的异常纹理，导致其结果存在大量冗余纹理，纹理数据量反而增加，通过牺牲数据量换取渲染效率的提高. 虽有一些研究中涉及了异常纹理的处理方法[19]，但是尚无妥善的解决方案.
针对上述问题，本文提出了一种精细建筑物碎片化纹理优化的二维装箱方法，通过纹理去冗余，有效解决了纹理合并中存储空间与渲染效率无法两全的难题，同时避免了异常纹理坐标导致的纹理拉花问题.
1 碎片化纹理优化的二维装箱方法
图1为精细建筑物模型碎片化纹理优化的二维装箱方法算法流程，主要包括以下3个部分：
1） 纹理去冗余，为了剔除冗余纹理，处理异常纹理的情况，根据UV坐标是否超出[0，1.0]，将模型中的纹理分为异常纹理和正常纹理两类，分别进行去冗余处理.
2） 纹理合并，为了减少纹理文件个数，根据去冗余得到的简化纹理和给定纹理集尺寸，模拟二维装箱过程，并按照装箱结果进行纹理合并.
3） 纹理重映射，为了解决由于纹理去冗余和纹理打包导致纹理映射关系发生变化的问题，根据纹理去冗余和纹理合并过程中的变化信息，重映射纹理坐标，得到纹理优化后的建筑物模型.
图1 算法流程Fig. 1 Algorithm flowchart
1.1 纹理去冗余
纹理坐标系O-UV是以纹理左下角为坐标原点，向右为U轴正方向，向上为V轴正方向建立的平面坐标系，一般定义在通过三维坐标和纹理坐标（UV坐标）可以确定纹理影像坐标区域的外接矩形即有效纹理区域，有效纹理区域以外的图像部分被称为冗余纹理. 冗余纹理不仅占据了存储资源，根据纹理映射机制，还可能使慢速硬盘与高速内存、显存之间出现传输瓶颈. 因此，在纹理打包前，需要剔除冗余纹理. 如图2所示，根据UV坐标裁剪原纹理图像得到新纹理图像并更新纹理坐标，本文将该过程称为纹理更新.
图2 纹理更新Fig. 2 Textures updating
本文定义所对应纹理坐标超出[0，1.0]范围的纹理为异常纹理，反之为正常纹理. 异常纹理在逐基元渲染中可有效处理，但难以进行纹理封装，常导致可视化中的纹理拉花问题. 因此，将模型中的纹理分为正常纹理和异常纹理两类，分别进行去冗余，同时重置异常纹理的UV坐标到[0，1.0]范围内，以便进行后续的纹理合并.
1.1.1 正常纹理去冗余
单独纹理即该纹理影像仅被一个面调用，共用纹理指该纹理影像被多个面调用. 根据单张纹理影像是否被多个面片使用，将模型中的正常纹理分为共用纹理和单独纹理：共用纹理首先计算该纹理影像对应的所有面片纹理坐标并集，然后进行纹理更新；单独纹理直接进行纹理更新，得到简化纹理. 正常纹理去冗余流程如图3所示.
图3 正常纹理去冗余流程Fig. 3 Flow of redundant normal textures eliminating
1.1.2 关键问题：异常纹理去冗余
根据纹理集定义，被合并的纹理其UV坐标应在[0，1.0]范围内. 但由于建模失误、生产规范不足以及重复纹理等原因，纹理坐标超出[0，1.0]范围的异常情况在目前仍无法完全避免. 异常纹理独立存在并不会影响模型的可视化效果，但若直接对其进行打包，就可能出现纹理错误映射等可视化问题. 因此，在纹理合并前需要对异常纹理进行纹理更新和坐标重置.
首先根据纹理坐标范围是否超出阈值（本文为2，可根据经验或实际情况设置）将异常纹理分为重复纹理和其他异常纹理；然后根据是否被多个面共用将其他异常纹理分为共用纹理和单独纹理. 重复纹理即被大量重复的简单纹理（如墙砖、瓦片等）. 重复纹理复用量较大，纹理更新和纹理打包会较大程度上增加其纹理数据量，因此不进行处理；共用纹理先计算与该纹理影像对应所有面的纹理坐标并集，然后进行纹理更新；单独纹理进行纹理更新. 异常纹理去冗余流程如图4所示.
图4 异常纹理去冗余流程Fig. 4 Flow of redundant abnormal textures eliminating
如图5所示，异常纹理之间的纹理坐标可能相差较大，直接使用原纹理坐标进行并集计算可能会使得到的并集范围很大，造成纹理更新上的困难.
图5 纹理更新问题Fig. 5 Problem of textures updating
由于将纹理坐标进行整数量偏移不会改变纹理贴图的效果，因此在进行并集计算前，对纹理坐标进行预处理，在U、V方向上各加一个整数偏移值，使纹理左下角UV坐标值均在[0，1.0]范围内. 如图6所示，通过坐标预处理，可有效解决纹理坐标差异大带来的纹理更新问题.
图6 坐标预处理Fig. 6 Preprocessing of texture coordinates
1.2 纹理合并
精细建筑物模型碎片化纹理文件的特点是纹理个体小、数量多，在模型渲染时引起大量纹理状态切换，导致批次数目急剧增加，严重影响场景渲染效率. 将单个建筑物模型中的大量碎片化纹理合并为一张大纹理，能够有效提高场景渲染效率.
装箱算法起源于物流运输，其研究目标是求解小物品装入大容器中的总体布局方案，并使之在特定约束条件下达到特定优化目标，如消耗的容器数量最少等，与纹理合并目标具有一致性[20-22]. 因此，利用二维装箱算法进行纹理合并，能够最大程度提高纹理集的空间利用率，节省存储空间[23-24].
本文中的矩形定义为R={x,y,W,H}，其中：x、y为矩形左下角坐标值；W、H为矩形的宽和高.
二维装箱过程为：初始条件下给定容器矩形C和待插入物品矩形集合I={r1,r2,r3,···,ri,···,rn}.ri按照一定规则选择合适区域（即自由矩形）插入后，C中放置ri的区域为占用矩形v，占用矩形集合V={v1,v2,v3,···,vn} ；C中剩余区域W被重新分割为多个自 由矩 形R，自由 矩 形 集 合U={R1,R2,R3,···,Rn}.
其中包含两个关键步骤：
步骤1剩余区域分割
自由矩形是剩余区域中的最大矩形，最大的含义为该矩形在每个方向上长度最大，即一个自由矩形碰到容器边缘或者碰到容器里的占用矩形，它满足两个条件：① ∀v∈V,R∩v= Ø；② 不存在w∈W，使w.x
图7 剩余区域分割示意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.
经过纹理去冗余，建筑物模型中的纹理被分为简化纹理和重复纹理. 重复纹理由于复用量较大，对其打包会较大程度上增加数据量，因此保留重复纹理，只合并简化纹理.
图9是纹理合并的算法流程，包含以下3个步骤：
步骤1对简化纹理进行预处理. 首先，根据预设的纹理集尺寸，将简化纹理中尺寸大于该值的纹理缩放到纹理集尺寸；然后，将所有纹理旋转至最长边水平，并按其最长边进行降序排列，得到排序后的待打包纹理，避免装箱过程中产生插入冲突.
步骤2根据预设纹理集尺寸以及待打包纹理尺寸，生成相应的容器矩形和物品矩形，模拟二维装箱过程，若装箱失败，则对待打包纹理进行降采样，重新模拟装箱，直到将全部物品成功装入容器中为止.
步骤3根据装箱结果，合并纹理，得到纹理集.
图8 自由矩形选择示意Fig. 8 Selection of free rectangle
上述将所有离散纹理合并为一张纹理集并可能对原始纹理降采样的纹理合并方法被称为纹理有损打包，将离散纹理合并为多张纹理集且不缩放原始纹理的纹理合并方法被称为纹理无损打包.
图9 纹理合并打包Fig. 9 Textures Packing
1.3 纹理重映射
纹理去冗余将纹理影像拼接、裁剪；纹理合并将纹理影像缩放、平移及旋转. 纹理坐标随之发生了变化，原始的映射关系已经不再适用，因此，需要进行纹理坐标重映射.
纹理去冗余后，新的纹理坐标计算方法为
式中：Umin、Vmin分别为原纹理在U、V方向上的最小值；DU、DV分别为原纹理在U、V方向上的长度.
纹理合并后，新的纹理坐标计算方法为
式中：TU、TV分别为插入纹理集的过程中纹理在U、V方向上所进行的几何变换信息.
2 实验分析
本文采用C++ 作为开发语言，在Visual Studio 2015开发平台上进行实验. 实验系统微机硬件配置如下：CPU，Intel（R）Core（TM）i7-5500U CPU @2.40 GHz；内存，12.00 GB；显卡，NVIDIA GeForce GT940M. 实验数据是某区域建筑群，数据格式为Wavefront obj.
表1为8个建筑物模型的纹理数据统计结果，横轴为单位为KB的纹理数据量大小. 由表1可知：各模型中数据量为1KB和2KB的纹理文件数量之和最小为58.6%，最大为85.7%，在70%～80%范围内的有4个，在60%～70%范围内的有2个，可见该区域建筑群模型的纹理碎片化程度较高，具有典型代表性，因此使用该区域建筑群模型进行纹理优化实验是适宜的.
表1 原始模型纹理数据统计结果Tab. 1 Statistics results of original model textures data
利用同样使用二维装箱算法的MaxRectsBin-Pack方法[15]与本文方法进行对比分析，以证明本文主要创新点纹理去冗余步骤的优越性. 设定纹理集尺寸为2048 × 2048，纹理缩放系数为1，实验结果如下：
1） 在纹理数据量方面，如表2所示，在纹理数据量较小或模型中异常纹理及冗余纹理较少的情况下，本文方法与MaxRectsBinPack方法的结果相近，如模型1、3、4、7；但在纹理数据量较大或模型中存在较多异常纹理及冗余纹理的情况下，本文方法具有明显优势，如模型2、5、6、8. 整个建筑群模型使用本文方法，纹理数据量减少了71.20%.
表 2 纹理数据对比结果Tab. 2 Textures data comparison MB
2） 在载入与绘制效率方面，如表3所示，整个建筑群经过本文方法和MaxRectsBinPack方法处理后纹理文件由4281锐减为27和125个，分别减少了99.37%和97.08%. 在OSGViewer中进行可视化实验，与原始模型相比，本文方法与MaxRectsBinPack方法的载入耗时由225.00 s锐减为个位数，其中本文方法减少了98.86%，明显优于后者；本文方法的GPU耗时减少了63.06%，优于MaxRectsBinPack方法，两者结果均优于原始模型；两种方法的渲染帧率与原始模型相比均无明显变化.
表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方法模型中出现贴图错误.
图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所示，在模型纹理文件数量或冗余数据量处于平均水平时，本文方法在纹理去冗余步骤耗时较少，在纹理合并步骤耗时少于MaxRectsBinPack，如模型1、3、4、5、7、8；在纹理文件数量或冗余纹理数据量非常大时可能出现异常，如本文方法剔除了模型2中的大量冗余纹理后纹理合并步骤耗时大大减少，而经过纹理去冗余步骤模型6中得到大量小尺寸纹理，使一个纹理集中要容纳大量小纹理，增加了纹理合并步骤耗时. 在纹理重映射步骤，两种方法耗时相近.
表4 算法效率对比（耗时）Tab. 4 Algorithm efficiency comparison (time) s
3 结束语
本文提出了一种精细建筑物模型碎片化纹理优化的二维装箱方法. 实验表明，相比传统纹理合并方法：该方法能够有效解决传统纹理合并方法在打包UV坐标超出[0，1]范围纹理时引起纹理错误映射的问题；该方法能够在不牺牲纹理分辨率的前提下，显著减少纹理数据量，解决了纹理合并中存储空间与绘制效率无法两全的难题. 本文方法无需人工经验和手动操作，自动化程度高，但由于增加了纹理去冗余操作，本文方法的算法复杂度有所增加. 进一步的研究将针对多建筑物共用纹理集的实例进行优化，提升大规模城市场景中重复建筑物的渲染效率以及大规模城市场景多细节层次纹理的简化与合并.
致谢：国土资源部城市地监测与仿真重点实验室开放课题（KF-2016-02-022，KF-2016-02-021）.
