李 钊，李建军，李 冰，李 坚，臧传收

（1.第二炮兵驻石家庄地区军事代表室，河北石家庄050081;2.第二炮兵士官学校，山东青州262500）

0 引言

纹理映射技术是当前计算机图形学中的一个热点问题。然而由于纹理图像数据量大，特别是对于大规模的地形数据模型，如果要求具有较高的真实感，内存的需求量更是十分巨大。很多算法是采用一个单块的地形纹理来进行纹理映射，但是在越来越多的情况下纹理数据远远大于内存容量，需要将纹理分块处理后才能使用[1]。为了能在有限的资源下获得较好的实时绘制效果，研究人员从地形的几何多分辨率表示中得到启示提出多分辨率纹理映射技术[2-4]。该文在总结已有算法的基础上，提出了一种基于四叉树结构的海量数据纹理映射算法。有效地解决了大规模地形场景重建过程中的数据调度与海量数据的纹理映射问题。实验结果证明了该算法的有效性。

1 基于四叉树的多分辨率纹理分块

为了能有效地实现大数据量纹理的实时调度，需要将纹理进行分块管理。一般情况下，纹理图像分割得越细，纹理坐标的计算量就越小，绘制速度就越快，然而这样会大大增加内存中的数据调度次数。该文使用四叉树结构来表示大规模数字地形的多分辨率纹理数据，每个结点用相同尺寸的纹理图像表示，但不同分辨率结点的纹理精细程度不同。四叉树结构的根结点对应覆盖整个地形方形区域，它的4个子结点分别为根节点的四分之一地域，依次类推，每个子结点均按此方法产生4个子结点，直到原始纹理的最精细分辨率或满足纹理划分的要求为止。

多分辨率纹理映射的关键是如何选取与地形LOD相一致的纹理图像的分辨率。一般来说，分辨率的选择是与视点、地形块的位置大小和纹理的原始分辨率相关的。根据文献[4]中的误差计算方法可以类似计算纹理映射误差。与地形误差不同的是，纹理误差要考虑纹理结点的大小与图像的分辨率级别，因此，纹理映射的误差可表示成纹理的分辨率级别与距视点的距离的函数，可用下式表示:

式中，k为纹理图像的分辨率级别;d为纹理分块距视点的距离;w为纹理分块的大小;l为地形数据点之间的行间距和列间距的几何平均值，即λ的计算方法和文献[4]中的一样。

2 纹理调度算法

在大规模的实时绘制时，需要不断地从硬盘到系统内存再到纹理内存调度纹理数据，如果用图形库的函数来实时建立多分辨率纹理则效率不高。该文的方法是预先建立纹理的各个层次细节，存储在数据文件中，当需要的时候对各个层次的纹理数据进行读取，然而使用多级纹理四叉树一次调入的数据量太多时，就会造成帧间停顿时间过长，为了降低停顿时间，必须减少纹理数据的调入量。

2.1 压缩纹理存储的实现

在实际应用中发现，在硬盘到系统内存的传输这一过程可以使用算法对纹理数据进行压缩，再将其存储在硬盘文件上。在使用时，用快速的解码把纹理数据解压到系统内存中。由于纹理图像相邻的纹理象素之间具有某种连贯性，利用这种连贯性对纹理金字塔进行压缩可以有效地减少数据冗余，使得纹理的表示更为紧凑。该文使用类似文献[5]中的图像金字塔，进行多层次的压缩和存储，来对纹理进行有效地压缩、调度及纹理反走样。由于纹理数据需要在绘制时实时进行解码，对解码的时间要求比较高，而矢量量化的方法仅需要建立索引表进行数据检索，效率非常高，因此可以采用矢量量化方法压缩误差图像。用矢量量化编码图像是一种有损的压缩技术，其关键是基于区域进行码本设计。这里使用LBG矢量量化算法对误差图像进行压缩编码[6]。

在执行图像矢量量化的过程中，由于图像各局部区域之间具有相似性，取一定大小的图像子区域进行矢量量化，这些图像子区域区使用相同的编码索引。基于图像子区域进行矢量量化，可以有效地对纹理图像进行压缩。采用矢量化的压缩方法，图像解码快速有效。对于层次多分辨率的纹理，当需要导入高一层分辨率的纹理数据，可以通过使用粗糙一层的纹理数据，以及编码索引号所指向的误差图像矢量量化后的颜色值就可以计算得出。在恢复每一层时，只需要从硬盘读取码本和编码索引号的信息，数据量小，读取非常快，这样既可以节省存储空间，又可以快速地恢复精细层纹理。

2.2 基于误差控制的多分辨率纹理结构

在实际绘制过程中，可以发现在一定误差的控制下，越高分辨率的纹理图像，在离视点越近的区域使用的较多，根据这一现象，在调入纹理数据时，只调入某一分辨率的在一定范围内的纹理数据即可满足实时绘制的需要。因此，首先要根据多分辨率纹理计算的结果确定不同分辨率纹理的范围，将在范围内的多分辨率纹理调入到内存的多分辨率结构中。该文在绘制时将每一层分辨率的纹理数据与预估的结果比较，将符合要求的纹理数据调入内存结构中，此时对于不同层次的纹理映射时会有2种情况:

①需绘制的纹理层次低于调入的纹理节点层次，此种情况可直接使用上一级纹理进行纹理映射;

②需绘制的纹理层次高于调入的纹理节点层次，这种情况要复杂一些，因为调入的纹理不能完全覆盖满足纹理分辨率要求的一个多边形，所以不能直接进行纹理映射，解决的方法是利用己调入的纹理为绘制节点实时生成纹理图像。

2.3 纹理内存释放算法

在进行大规模的纹理调用时，当纹理的缓冲空间达到一定限制时就需要释放一部分纹理，通常的办法是采用LRU算法。

假定当前的视点位置为v1，前一帧视点位置为v0，下一帧视点位置为v2。由此可以估算出在视点v1处的运动方向是（v1-v0）/‖v1-v0‖，运动的速度为‖v1-v0‖/t，其中t是从视点v0运动到视点v1所用的时间，所以在v1处视点的运动矢量为:

式中，f表示在v1时刻的帧频率，于是下一视点v2的估计位置为:

这里假设在3个视点处有相同的帧频率，则在视点v2处的视锥体可以表示成由视点位置v2、视点方向d、视域张角w以及近截面fn和远截面ff的函数，即:

通常情况下，在实时飞行仿真过程中后面3个变量是不变的，只有视点的位置与方向在随时间变化。在飞行仿真过程中，通常离视域范围越远的纹理被释放的可能性就越大，因此可以用纹理块与视域的距离平均距离作为影响内存释放的一个因子，可以用下式计算:

式中，（qx，qy），（rx，ry）分别为纹理分块与预测的下一视点处的视域体在平行于地面平面上投影的重心。

在进行纹理调度时，首先计算内存中纹理分块到视域体的平均距离，然后，对平均距离超过一定阈值的内存纹理分块，使用改进的LUR算法[1]，进行内存释放。改进的LUR策略的优先级由下式给出:

式中，fq为纹理四叉树结点最近一次调用的帧序号;l务纹理四叉树结点的层数，p越小且距离视域平均距离越远的纹理结点的数据最先剔除。

3 实验结果分析

该文对地形纹理的实时绘制进行性能测试，使用的实验数据是深圳地区的DEM数据，地形表面数据的大小为7169×4096个数据点，数据点的实际分辨率为10m，在硬盘中的文件总大小为112MB。对于地形纹理数据，这里使用的是该地区经校正过的卫星图片，其大小为28672×16384，在硬盘中的文件大小约为1.34GB。

图1是该算法实时帧速率与传统算法的实时帧速率比较的结果图。统计了一个给定飞行路线中500帧的数据。从图中可以看出，算法的帧速率要明显高于传统方法的结果，这是因为该算法通过矢量量化图像压缩算法及根据纹理误差范围的数据调度算法，大大减少了实时仿真过程中的系统外存与内存之间的数据调度量，同时基于视域的内存释放算法可以对纹理内存进行有效的管理，减少内存中纹理数据在磁盘和缓冲区之间反复调度，提高了算法实时仿真的效率。

图1 不同算法的帧速率比较

4 结束语

为实现实时的大规模地形的纹理映射，该文提出了一种新的基于四叉树结构的海量数据纹理映射算法。算法对多分辨率纹理数据进行了基于金字塔结构的数据压缩存储，提出了一种有效的纹理映射误差的计算方法，提高了纹理映射的精度，并利用纹理映射误差，减少了实时调度过程中纹理数据的数据量，同时优化了内存释放算法，有效减少了纹理数据在磁盘和缓冲区之间的反复调度，从而解决了大规模地形场景重建过程中的数据调度与海量数据的纹理映射问题，在实际应用中取得了比较满意的效果。

[1]陆雁青.海量地形数据实时绘制的技术研究[D].浙江大学博士学位论文，2003.7.

[2]BLOW J.Terrain rendering at high levels of detail[C]//Proceedings of the Game Developers Conference 2000.California，2000:119-124.

[3]TANNER C，MIGAL C，JONES M.The clipmap:a virtual mipmap[C]//Cohen M.ed.，Proceedings of SIGGRAPH 1998.Orlando，florida.1998.New York:ACM Press，1998:415-422.

[4]黄超超，凌永顺，吕相银.地形纹理映射方法研究[J].计算机仿真，2005，22（1）:209-212.

[5]LINDSTROM P，PASCUCCIV.Terrain simplification simplified:a general framework for view-dependent out-ofcore visualization[J].IEEE Transactions on Visualization and Computer Graphics，2002，8（3）:239-25.

[6]BURT P J，ADELSON E.The laplacian pyramid as a compact image Code[J].IEEE Transactions on Communications，1983，COM-3l（4），532-540。