Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16]


Journal of Information Science and Engineering, Vol. 22 No. 4, pp. 843-861 (July 2006)

A Novel Cache-based Approach to Large Polygonal Mesh Simplification

Hung-Kuang Chen1,3, Chin-Shyurng Fhan2, Jeffery J. P. Tsai4 and Ming-Bo Lin1
1Department of Electronic Engineering
2Department of Computer Science and Information Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan
3Department of Information and Design
Asia University
Taichung, 413 Taiwan
4Department of Computer Science
University of Illinois at Chicago
Chicago, IL 60637, U.S.A.

Traditional iterative contraction based polygonal mesh simplification (PMS) algorithms usually require enormous amounts of main memory cost in processing large meshes. On the other hand, fast out-of-core algorithms based on the grid re-sampling scheme usually produce low quality output. In this paper, we propose a novel cachebased approach to large polygonal mesh simplification. The new approach introduces the use of a cache layer to accelerate external memory accesses and to reduce the main memory cost to constant. Through the analysis on the impact of heap size to the locality of references, a constant sized heap is suggested instead of a large greedy heap. From our experimental results, we find that the new approach is able to generate very good quality approximations efficiently with very low main memory cost.

Keywords: cache-based polygonal mesh simplification, large mesh, iterative half-edge collapse, quadric error metrics, independent queuing

Full Text () Retrieve PDF document (200607_08.pdf)

Received April 7, 2004; revised February 1 & August 2, 2005; accepted August 29, 2005.
Communicated by Pau-Choo Chung.