Simplification And Interactive Rendering Of Massive Meshes

There has been an fast improvement in the complexity of 3D meshes during recent years, in part due to the drastic improvements in resolution and accuracy of data acquisition devices. Because of the extremely high fidelity of these gigantic meshes, they are applicable in many fields, such as culture heritage protection, digital museum , virtual human project, movies and video games, etc. However, rendering, transmitting, editing and storing these gigantic meshes bring great challenges. An efficient solution to these problems is to simplify these complex 3D meshes. Traditional mesh simplification methods are not suitable for these gigantic meshes, because they need to load the whole original mesh into the main memory for simplification. Recently, external memory based approaches, i.e. out-of-core algorithms, have been put forward to simplify these large meshes. And out-of-core simplification and interactive rendering of massive mesh are becoming an active area of computer graphics.Traditional mesh simplification methods based on iterative selection of coarsening operations can produce the approximations of original meshes with high quality. However they are usually designed with complex data structures and require long simplification time. Vertex clustering method has been proposed for its fast simplification speed. This method is especially suitable for gigantic meshes. This paper investigates various methods to improve the quality of the simplified meshes and to build multi-resolution representation for massive meshes using vertex clustering method. Our main contributions include:1. We first analyze and compare most traditional mesh simplification algorithms. We design an in-core mesh simplification algorithm based on the vertex clustering scheme. This algorithm partitions the original mesh with a uniform grid and computes the representative vertex of each cell using the improved quadric error metrics which can better preserve the volume of simplified meshes.2. We analyze and compare various state-of-the-art simplification algorithms for gigantic meshes. Inspired by the OoCS algorithm, we implement an algorithm that the memory requirement depends on only the size of output mesh, but does not depend on the size of input mesh. To overcome the complexity limitation of output mesh by the amount of available memory, we propose an improvement to the OoCSx algorithm. Our improved algorithm achieves the independent of input and output mesh on the available memory and can enhance the quality of the simplified meshes.3. We implement an external memory multi-resolution representation and rendering algorithm for massive polygonal meshes. Our multi-resolution representation is stored as an external memory octree and is maintained as an internal memory octree. The data scheduling from disk to main memory is implemented by the memory mapping technology. This multi-resolution representation also enables view-dependent rendering by appending view related parameters such as normal cone in each octree node. Our view-dependent rendering framework includes view frustum test, backface test, screen space coverage test and silhouette test.In addressing the problem brought by the explosion in the size of 3D meshes, we have made improvements to three mesh simplification algorithms based on vertex clustering and to a view-dependent multi-resolution construction and rendering algorithm. The proposed algorithms can produce simplified meshes with high quality, achieve the simplified speed about 50-300k triangles per second, and requires only constant main memory independent on both input and output meshes. Our view-dependent multi-resolution construction and rendering algorithm enables interactive rendering of massive meshes on common personal PC.