基于贪心优化策略的网格排布算法
来源：计算机应用杂志2016年第7期北京时间：
作者：娄自婷, 张亚萍
单位：云南师范大学 信息学院, 昆明 650500
摘要：针对由存储带宽和数据访问速度导致的复杂数据集绘制性能低下等问题，提出了一种基于贪心优化策略的三角形排布算法，通过对绘制数据集进行重排以改善数据的空间局部性和时间局部性。该算法首先将顶点分为三类，根据改进的代价函数选择代价度量最小的顶点作为活动顶点；然后绘制（即输出）其所有未绘制的邻接三角形，并将相邻顶点压入缓存，算法迭代执行直到所有顶点的邻接三角形都绘制完成，得到重新排列后的三角形序列。实验结果表明，该算法不仅具备较高的顶点缓存命中率，还提高了渲染速度，减少了排序的时间，有效地解决了图形处理器的处理速度不断提升而数据访问速度严重滞后的问题。
关键词：缓存优化,网格排布,贪心优化策略,平均缓存失配率,三维网格模型
基金资助：国家自然科学基金资助项目（61262070，61462097）。
