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

doi:10.11772/j.issn.1001-9081.2016.07.1954

计算机应用 ›› 2016, Vol. 36 ›› Issue (7): 1954-1958.DOI: 10.11772/j.issn.1001-9081.2016.07.1954

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

娄自婷, 张亚萍

云南师范大学信息学院, 昆明 650500

收稿日期:2015-12-07 修回日期:2016-03-21 出版日期:2016-07-10 发布日期:2016-07-14
通讯作者: 娄自婷
作者简介:娄自婷(1990-),女,云南昆明人,硕士研究生,主要研究方向:计算机图形学;张亚萍(1979-),女,云南临沧人,副教授,博士,主要研究方向:计算机图形学、并行计算。
基金资助:
国家自然科学基金资助项目（61262070，61462097）。

Mesh layout algorithm based on greedy optimization strategy

LOU Ziting, ZHANG Yaping

College of Information Science and Technology, Yunnan Normal University, Kunming Yunnan 650500, China

Received:2015-12-07 Revised:2016-03-21 Online:2016-07-10 Published:2016-07-14
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61262070,61462097).

摘要/Abstract

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

关键词: 缓存优化, 网格排布, 贪心优化策略, 平均缓存失配率, 三维网格模型

Abstract: Concerning low rendering performance of complex data sets which is caused by the limited memory bandwidth and data access speed, a triangle mesh layout algorithm based on greedy optimization strategy was proposed, by rearranging the triangle sequences to improve spatial locality and temporal locality of data. Firstly, the vertices were divided into three categories, according to the improved cost function, the vertex with the minimum cost was chosen as currently active vertex. Then, all adjacent triangles which were not rendered were output, and the neighbors were pushed into buffer. The above steps were executed iteratively until adjacent triangles of all vertices were rendered. Finally, the rearranged triangle sequence was got. The experimental results show that the proposed algorithm can provide a higher vertex cache hit ratio, improve the rendering speed, and reduce the execution time of the sorting, which can effectively solve the problem of data access speed lagging behind the processing speed of Graphics Processing Unit (GPU) seriously.

Key words: cache optimization, mesh layout, greedy optimization strategy, Average Cache Miss Rate (ACMR), 3D mesh model

中图分类号:

TP391.41

娄自婷, 张亚萍. 基于贪心优化策略的网格排布算法[J]. 计算机应用, 2016, 36(7): 1954-1958.

LOU Ziting, ZHANG Yaping. Mesh layout algorithm based on greedy optimization strategy[J]. Journal of Computer Applications, 2016, 36(7): 1954-1958.

参考文献

[1] 熊华.面向并行环境的绘制加速技术研究[D].杭州:浙江大学,2008:71-80. (XIONG H. Research of rendering acceleration techniques for parallel environments[D]. Hangzhou:Zhejiang University, 2008:71-80.)
[2] HOPPE H. Optimization of mesh locality for transparent vertex caching[C]//SIGGRAPH'99:Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. New York:ACM, 1999:269-276.
[3] 戴雪峰,熊汉江,龚健雅.一种三维城市模型多纹理自动合并方法[J].武汉大学学报:信息科学版,2015,40(3):347-352. (DAI X F, XIONG H J, GONG J Y. A multi-texture automatic merging approach for the 3D city models[J]. Geomatics and Information Science of Wuhan University, 2015, 40(3):347-352.)
[4] 陈思远,史广顺,王庆人.通过三角形strip衍生实现三维模型数据的渲染优化[J].计算机辅助设计与图形学学报,2009,21(8):1155-1163.(CHEN S Y, SHI G S, WAND Q R. Data optimization for 3D model rendering by triangle strip deriving[J]. Journal of Computer-Aided Design & Computer Graphics, 2009, 21(8):1155-1163.)
[5] YOON S-E, LINDSTROM P. Mesh layouts for block-based caches[J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(5):1213-1220.
[6] 秦爱红,石教英.基于混合模式缓存优化的三角形条带化[J].计算机辅助设计与图形学学报,2011,23(6):1006-1012. (QIN A H, SHI J Y. Cache-friendly triangle strip generation based on hybrid model[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(6):1006-1012.)
[7] BOGOMJAKOV A, GOTSMAN C. Universal rendering sequences for transparent vertex caching of progressive meshes[J]. Computer Graphics Forum, 2002, 21(2):137-148.
[8] KARYPIS G, KUMAR V. Multilevel k-way partitioning scheme for irregular graphs[J]. Journal of Parallel and Distributed Computing, 1998, 48(1):96-129.
[9] LIN G, YU T P Y. An improved vertex caching scheme for 3D mesh rendering[J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(4):640-648.
[10] SANDER P V, NEHAB D, BARCZAK J. Fast triangle reordering for vertex locality and reduced overdraw[J]. ACM Transactions on Graphics, 2007, 26(3):89-97.
[11] NEHAB D, BARCZAK J, SANDER P. Triangle order optimization for graphics hardware computation culling[C]//Proceeding of 2006 Symposium on Interactive 3D Graphics and Games. New York:ACM, 2006:207-211.
[12] YOON S, LINDSTROM P, PASCUCCI V, et al. Cache-oblivious mesh layouts[J]. ACM Transactions on Graphics, 2005, 24(3):886-893.
[13] LIU R, ZHANG H, VAN KAICK O. Spectral sequencing based on graph distance[C]//GMP 2006:Proceeding of the 4th International Conference on Geometric Modeling and Processing, LNCS 4077. Berlin:Springer, 2006:632-638.
[14] BARTHOLDI J J, GOLDSMAN P. Multiresolution indexing of triangulated irregular networks[J]. IEEE Transactions on Visualization and Computer Graphics, 2004, 10(4):484-495.
[15] LIMPER M, JUNG Y, BEHR J, et al. The POP buffer:rapid progressive clustering by geometry quantization[J]. Computer Graphics Forum, 2013, 32(7):197-206.
[16] 石教英.分布并行图形绘制技术及其应用[M].北京:科学出版社,2010:189-274.(SHI J Y. Distributed Parallel Rendering Technique and Its Application[M]. Beijing:Science Press, 2010:189-274.)
[17] 陆扬.基于CUDA的三角形并行处理[D].合肥:中国科学技术大学,2010:13-21. (LU Y. Parallel triangle processing with CUDA[D]. Hefei:University of Science and Technology of China, 2010:13-21.)

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

Mesh layout algorithm based on greedy optimization strategy

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	张倩郭嗣琮. 基于有限状态机和Trie数的分级地址模型[J]. 计算机应用, 2013, 33(03): 854-857.
[2]	周昕俞晓明朱涛王箫萧石教英. 一种基于小波变换的三维网格模型水印算法[J]. 计算机应用, 2007, 27(5): 1156-1159.
[3]	艾青松周祖德刘泉. 基于奇异值分解的三维网格模型数字水印算法[J]. 计算机应用, 2007, (12): 2931-2933.