The real-time interactive 3D multimedia applications such as 3D computer games and virtual reality (VR) have become prominent multimedia applications in recent years. In these applications, both visual fidelity and degree of interactivity are usually crucial to the success or failure of employment. Although the visual fidelity can be increased using more polygons for representing an object, it takes a higher rendering cost and adversely affects the rendering efficiency. To balance between the visual quality and the rendering efficiency, a set of level-of-detail (LOD) meshes has to be generated in advance. In this paper, we propose a highly efficient polygonal mesh simplification algorithm that is capable of generating a set of high-quality discrete LOD meshes in linear run time. The new algorithm adopts memoryless vertex quadric computation, and suggests the use of constant size replacement selection min-heap, pipelined simplification, two-stage optimization, and a new hole-filling scheme, which enable it to generate very high-quality LOD meshes using relatively small amount of main memory space in linear runtime.
