基于贪心优化策略的网格排布算法

《基于贪心优化策略的网格排布算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于贪心优化策略的网格排布算法摘要：针对由存储带宽和数据访问速度导致的复杂数据集绘制性能低下等问题，提出了一种基于贪心优化策略的三介形排布算法，通过对绘制数据集进行重排以改善数据的空间局部性和时间局部性。该算法首先将顶点分为三类，根据改进的代价函数选择代价度量最小的顶点作为活动顶点；然后绘制(即输出)英所有未绘制的邻接三角形，并将相邻顶点压入缓存，算法迭代执行直到所冇顶点的邻接三角形都绘制完成，得到重新排列后的三角形序列。实验结果表明，该算法不仅具备较高的顶点缓存命中率，还提高了渲染速度，减少了排序的时间，有效地解决了图形处理器的处理速度不断提升而数据访问速度严重滞后的问题。关键词

2、：缓存优化；网格排布；贪心优化策略；平均缓存失配率；三维网格模型中图分类号：TP391.41文献标志码：A0引言尽管近年来屮央处理器(CentralProcessingUnit,CPU)与图形处理器(GraphicsProcessingUnit,GPU)的处理能力都有了很大的提升，但复杂数据集的绘制性能问题仍然存在，这主要是山于存储带宽和数据访问速度的增长远落后于处理能力的增长，数据的输入输出成为大规模数据处理最主要的瓶颈。为此，现代计算机系统大量采用了缓存机制，使用小容量的高速存储器为人容量的低速存储器提供缓存。为了充分利用缓存机制，数据应该有良好的局部性(locality)0局

3、部性有两种基本形式:空间局部性(spatiallocality)与时间局部性(temporallocality)。空间局部性表示与当前访问的数据单元邻近的数据单元很可能会被访问。时间局部性表示如果一个数据单元正在被访问，那在近期它很可能会被再次访问［1］。为了提高CPU和GPU之间的数据交换速度，减轻顶点读取时的带宽要求，GPU采用顶点缓存机制与纹理缓存机制避免重复的顶点计算以提高缓存性能［2］,目前已有多种优化纹理缓存访问效率的算法［3］,而提高顶点缓存访问效率的算法屈指可数。顶点缓存的访问性能通常用平均缓存失配率(AverageCacheMissRate,ACMR)來衡量，定义

4、为绘制每个三角形的平均缓存失配次数，即缓存的总失配次数与总访问次数之比，ACMR的取值范围为［0.5,3.0］,因为每个顶点至少失配一次，至多失配三次。需要注意的是，ACMR无法达到最小值，主耍是因为顶点缓存区容量的限制。若顶点缓存区可以装下所有顶点，则以任何方式组织的三角形都可以使ACMR接近于0.5,但是缓存容量很小，很难装下所有的顶点，假设缓存容量为k,三角形顶点个数为n,k往往小于n,在理想情况下ACMR可以达到的最小值为k/2(k-1)二0.5+Q(1/k)，其中Q(1/k)是1/k的线性函数⑷。此外，网格的形状也会导致ACMR额外的开销，因此要提高顶点缓存访问效率，需降

5、低ACMR值，进行缓存优化。1网格排布优化缓存优化技术除了与硬件性能有直接关系，还与数据访问方式和数据排列方式有关。针对后者，设计缓存优化算法，通过重排技术来提高缓存访问性能。重排技术包括计算重排与数据重排［5］：1）计算重排，即根据重新排列指令顺序，提高访问相同数据单元指令的局部性，通常由编译器对应用程序编译后的指令序列进行重排来完成，对于指令，重新组织程序而不影响程序的正确性；2）数据重排，即根据指令对数据单元的访问方式求解出缓存连贯的数据排布，由应用程序直接对数据进行重排來完成，通过优化改善数据的空间局部性和时间局部性。目前基于网格排布的缓存优化技术（以下简称网格排布优化技术

6、）是计算机图形学与可视化领域的重点研究方向之一，该技术基于数据重排。根据求解技术手段的不同，网格排布优化技术可分为基于优化策略、基于空间填充曲线和基于谱序列三类［lh根据网格描述方式的不同，可分为基于三角形、基于三角形条带、基于三角形扇，每种描述方式又可分为索引形式和三角形形式［6］。因为索引形式只需少量数据，传输代价小，使之成为目前使用最为普遍的方式，但顶点随机读取也带来了ACMR的增加,因此许多研究者提出对网格图元的存储顺序进行重新排布，可以减小ACMR,降低顶点处理的运算量，提高渲染速度。Hoppe［2］提岀了基于贪心优化策略的条带算法，沿着逆时针方向生成条带，进行三角形条带

7、合并，在合并的过程屮不断检测预期的ACMR,以此降低顶点缓存失配率。Bogomjakov等［7］提出了基于空间填充曲线的非条带算法，该算法使用图划分软件包Metis［8］将网格分成多个三角形簇，保证每个簇内三角形序列的ACMR最优，从而形成整个网格的ACMR最优化。Lin等［9］也提出了一种基于优化策略的三角形绘制序列生成算法，应用启发式条件对网格顶点进行全局搜索，同样可以得到很低的ACMRoSander等［10］対Lin等［9］算法进行了改进，该算法只在上一个输出的