大范围、高质量的三维城市模型数据已经成为城市基础地理空间框架重要的组成部分，高精度三维建模方法的应用在提高了智慧城市三维场景逼真度的同时，也导致三维城市模型的数据量急剧增加，模型的纹理数据量一般远大于几何数据^[1]，纹理数据占据了大量的存储与绘制设备资源。这些纹理数据特点是数量多^[2]，但单个纹理数据量小，因此，对单个纹理做简化和压缩的意义不大。但是这些数量众多的小纹理在三维城市模型实时绘制中显著增加了纹理载入次数和绘制批次^[3]，严重影响了模型的绘制效率，如果能把模型数量众多的小纹理合并为一张大纹理，就能有效解决这个问题。

目前，对于大规模的模型数据的组织^{[4, 5, 6, 7, 8, 9, 10]}与管理已有许多研究成果^{[11, 12, 13, 14, 15, 16, 17, 18, 19]}，而针对三维城市模型纹理合并的研究较少。基于纹理集^{[20, 21]}和超面^{[22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34]}的纹理优化算法提高了绘制效率。开源软件OSG(Open Scene Graph)中的Optimizer类提供了一种纹理合并的算法，但其只能合并类型尺寸完全相同的纹理，而实际模型的纹理尺寸往往并不相同，因此，其应用意义不大；一些商业软件提供了类似的纹 理合并解决方案：Autodesk公司的3DMax软件提供的UVW-UnWrap工具箱，其原理是将包裹在三维模型表面的纹理从内向外投影展开到平面上，但该投影过程需要人工参与，首先要凭经验将整体模型拆分成多个可以投影展开的小块，然后对各小块分别设置投影参数进行展开操作，最后将所有展开的结果合并为一张纹理。使用ISOMAP算法的商业软件，其原理是首先沿模型表面曲率较高的地方凭经验人工划一条切割线将模型切开成两个半球，再对两个半球分别投影展开成两个圆，但该方法同样无法做到自动化处理。

上述纹理合并方案或多或少需要人工干预和使用经验，无法实现全程自动化，显然不适合大规模三维城市模型纹理数据的批处理。张剑清^[25]针对物体三维重建中影像文件多、纹理数据量大这一问题,提出了影像纹理数据重组织的数学模型和解决方案，该方案能去除纹理的冗余数据，并且能做到纹理合并结果的局部最优，但该方法不能保证结果是全局最优。针对纹理合并的自动化需求，本文提出了一种基于贪心算法(Greedy Algorithm,GA)和模拟退火算法(Simulated Annealing,SA)的纹理自动合并方法，其合并结果能趋于全局最优，适用于大规模三维城市模型纹理数据的自动合并操作，能有效地提高三维城市模型绘制效率。

1 多纹理自动合并总体方案

要将尺寸不一的多个小纹理合并成一个大纹理，并尽可能地节省大纹理的存储空间是一个复杂的组合最优化问题。从数学计算复杂性理论看，它属于最高计算复杂性问题——NP完全问题^[11]。这样的组合优化问题无法用一个方程式来获取确切解，但可以用贪心算法近似得到一个最优解。贪心算法具体来说就是一种策略，即每一步都要选择当前看来最好的去执行，这样将组合优化问题化为一个(仅仅一个)子问题，这是一个顺序的求解过程，这样求解空间实际上就是一个线性的空间，最后可以得到近似局部最优解。

结合贪心算法将整体纹理合并最优问题分解为：在可用的大纹理空间中，选择一块与待合并小纹理大小相同并且当前最能节省大纹理空间的区域，然后将待合并小纹理放入该区域中，这样对剩下的小纹理和剩下的大纹理空间递归操作，最后可以将所有纹理合并成为一个大纹理。

通过贪心算法得到的结果，虽然每一步都是最优选择，但这是一个顺序求解过程，得到的是一个局部最优解，只能算作近似全局最优解，因此，本文引入模拟退火算法，保证每一步求得的解都收敛于全局最优解。模拟退火算法最早由Kirkpatrick^[26]等应用于大规模组合最优化问题。它与一般的局部搜索最优问题的不同之处在于它能以一定的概率跳出局部最优并最终趋于全局最优，是一种用来求解组合优化问题的随机启发式算法。结合贪心算法和退火算法，能将小纹理合并成一张大纹理，并且组合方式趋于全局最优，即合并后的大纹理占用纹理空间最小。

2 多纹理自动合并实现过程 2.1 基于贪心算法的多纹理自动合并

1) 将所有纹理存到待合并列表里，并根据纹理高度进行排序；

2) 判断是否已经存在条状纹理空间；

3) 如果不存在，则创建第一个条状纹理空间，高度与该纹理高度相同，并将该纹理放入到新创建的条状纹理空间中，放置顺序为从左向右，如图 1所示；

图 1 纹理合并示意图 Fig. 1 Texture Merging Sketch Map

图选项

4) 如果存在，依次从列表中取出一个纹理，从下到上依次尝试放入到每一个水平条纹理空间中；

5) 如果任何已有的条状纹理空间都无法容下该纹理，则新创建一个与该纹理高度相同的条状纹理空间，并将该纹理放入其中，放置顺序为从左向右；

6) 如果有一个或多个条状纹理空间都能容下该纹理 ，则记录放置纹理后该条状纹理空间剩余空间的大小，选择剩余空间最小的放置该纹理；

7) 重复步骤4)~步骤6)，直到待合并列表为空，算法结束。

如图 1所示，纹理1加入纹理空间的时候创建了条状纹理空间1。纹理2和纹理3依次从左到右加入到了条状纹理空间1中。此时条状纹理空间1虽然还有剩余空间，但无法容下纹理4，所以条状纹理空间2被创建，高度与纹理4一致，同理纹理5被放入到条状纹理空间2中。条状纹理空间1和条状纹理空间2都可以容下纹理6，但是条状纹理空间1放入纹理6后剩余空间较少，因此，纹理6被放入到条状纹理空间1中。依次操作，当待合并列表中的纹理处理完后，所有条状纹理空间的集合即为最终合并的大纹理，处理的流程图如图 2所示。

图 2 基于贪心算法的纹理合并流程图 Fig. 2 Texture Merging Flow Diagram Based on Greedy Algorithm

图选项

贪心算法得到的是局部的最优解，结合模拟退火算法引入退火速度因素，可以使得贪心算法每一步搜索出的解都收敛于全局最优解，引入模拟退火机制进行迭代求解，具体步骤如下：

1) 设 置降温公式为T=αT，其中降温系数α∈(0,1)，设置能量函数为E = F(X_n)，设置初始温度T = T₀和温度下限T_min；

2) 使用贪心算法搜索到的纹理序列作为初始解X₀；

3) 随机交换解X₀纹理序列中的两个小纹理的位置，根据贪心算法得到一个新的解X₁；

4) 计算模拟退火算法中的能量差值：ΔE=F(X₁)-F(X₀)；

5) 如果ΔE≥0，则接受新解X₁，赋值给X₀，X₀=X₁；

6) 如果ΔE<0，则以如下概率接受新解：判断条件exp(ΔE/T)≥random[0,1]，若成立，则接受新解X₁，将X₁赋值给X₀，X₀ = X₁；

7) 继续降温：T=αT；

8) 重复步骤3)~步骤7)，直到T≤T_min时停止迭代。

其中降温系数α为经验值，若降温系数α过大，则搜索到全局最优解的概率较高，但搜索过程较长，若α过小，则搜索过程会很快，但最终可能会达到一个局部最优值。能量函数E=F(X_n)为所有小纹理空间总和与实际使用的大纹理空间的比值，若能量函数值E越大，说明组合后生成的大纹理空间越小，小纹理组合越合理，即纹理空间使用效率越高。在贪心算法搜索到的局部最优解的基础上，进一步使用模拟退火算法使得最后的解全局 最优，即找到了小纹理合并成大纹理的最优方式。

3 实验与分析

采用C⁺⁺作为开发语言，在VS2008开发平台上使用OSG(Open Scene Graph)开源引擎和OpenGL三维图形接口进行实验。实验系统微机硬件配置如下：CPU: 4 Intel(R) Core(TM) i5 M560 @2.67 GHz，内存：3.09 GHz 3.10 GB，显卡：NVIDIA NVS 3100 M。实验选取了5个典型的三维城市建筑模型数据，数据格式是3DS。分别在实验可视化平台上加载并绘制这5个三维城市模型，记录绘制的基本信息。分别对这5个模型的纹理数据进行合并处理，再加载到实验平台上，记录新的绘制信息。

表 1记录了5组实验对比结果。 从表 1可以看出，随着模型的复杂度增加，渲染和GPU耗时逐渐增加；模型纹理个数越多，渲染耗时越多；模型顶点数越多，GPU耗时则越多。模型小纹理数量越多，则合并处理后渲染效率提高的越多。 经过合并处理的模型的渲染时间缩短，GPU的耗时明显减少。这主要得益于纹理的预处理合并减少了纹理加入到GPU中的批次，节约了渲染时间。从第四组和第五组数据可以看出，模型数据的纹理越琐碎，经过纹理合并所带来的优势会更 加明显。图 3显示的是单个模型使用合并后的纹理数据进行渲染的效果，可以看出纹理合并对模型可视化效果没有影响。图 4(a)是存放在文件夹中的一个模型的纹理文件，可以看到这些纹理数据数量多，而且每个纹理数据量较小，图 4(b)显示的是将图 4(a)中的纹理数据合并后的效果图。

图 3 纹理合并后的模型 Fig. 3 3D Model Based Texture Merging

图选项

图 4 模型纹理合并后的结果 Fig. 4 Texture Merging Result

图选项

将本文提出的纹理自动合并算法应用在武汉大学测绘遥感信息工程国家重点实验室开发的Virtual World 网络三维可视化平台中，Virtual World软件是武汉大学测绘遥感信息工程国家重点实验室开发的一款在网络环境下实现对海量空间数据(包括影像、矢量、地形和三维模型等数据类型)实时可视化的软件平台。 整个中等规模的3DMax城市建筑精细建模在进行了纹理自动合并和多级LoD处理后，在三维客户端的多线程调度和GPU绘制支持下，能够满足每秒30帧以上的可视化效率，从工程上验证了本文算法的有效性,绘制效果如 图 (5)所示。

图 5 基于纹理合并的模型大规模显示效果 Fig. 5 Large Scale 3D Models Rendering Based on Texture Merging

图选项

本文通过使用贪心算法和退火算法，将三维城市模型的多个小纹理自动的合并为一个大纹理，并且纹理组合方式趋向于全局最优。由于纹理合并的预处理操作，减少了模型绘制时纹理载入显存的批次，节约了渲染时间，提高了绘制效率。由于模型的小纹理往往大小不一致，合并之后的大纹理空间部分无法被充分利用，因此，大纹理空间是大于小纹理集合的。但是考虑到大纹理带来的管理上和绘制效率上的优势，以空间换取效率，少量的纹理空间牺牲是值得的。同时，本文提出的纹理自动合并方法也可以作为模型纹理数据压缩与简化的预处理步骤，提高压缩与简化的效率。