GPU-Accelerated Triangle Mesh Simplification Using Parallel Vertex Removal

Authors: Thomas Odaker, Dieter Kranzlmueller, Jens Volkert

Abstract:

We present an approach to triangle mesh simplification designed to be executed on the GPU. We use a quadric error metric to calculate an error value for each vertex of the mesh and order all vertices based on this value. This step is followed by the parallel removal of a number of vertices with the lowest calculated error values. To allow for the parallel removal of multiple vertices we use a set of per-vertex boundaries that prevent mesh foldovers even when simplification operations are performed on neighbouring vertices. We execute multiple iterations of the calculation of the vertex errors, ordering of the error values and removal of vertices until either a desired number of vertices remains in the mesh or a minimum error value is reached. This parallel approach is used to speed up the simplification process while maintaining mesh topology and avoiding foldovers at every step of the simplification.

Keywords: Computer graphics, half edge collapse, mesh simplification, precomputed simplification, topology preserving.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1338726

References:

[1] Clark, J. H. Hierarchical geometric models for visible surface algorithms, Com. of ACM 19, No. 10, pp.547-554, 1976
[2] Rossignac, J., and Borrell, P. Multi-resolution 3D Approximations for Rendering Complex Scenes, Modeling of Computer Graphics: Methods and Applications, pp.455-465, 1992
[3] Schaefer, S., and Warren., J. Adaptive vertex clustering using octrees, Proceedings of SIAM Geometric Design and Computing 2003, Vol. 2, pp.491-500, 2003
[4] Low, K.-L., and Tan, T., S., Model simplification using vertex-clustering, SI3D Proceedings 1997, pp.75-ff., 1997
[5] Schroeder, W., J., Zarge, J., A., and Lorensen, W., E. Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics Vol. 26, No. 2, pp.65-70, 1992
[6] Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., A., and Stuetzle, W. Mesh optimization, ACM SIGGRAPH Proceedings 1993, pp.19-26, 1993
[7] Hu, L., Sander, P., V., and Hoppe, H. Parallel view-dependent refinemnet of progressive meshes, I3D 2009 Proceedings of the 2009 Symposium on Interactive 3D Graphics and Games, pp.169-176, 2009
[8] DeCoro, C., and Tatarchuk, N. Real-time mesh simplification using the GPU, I3D 2007 Proceedings of the 2007 Symposium on Interactive 3D Graphics Vol. 2007, pp.161-166, 2007
[9] Hoppe, H. Progressive meshes, ACM SIGGRAPH 1996 Proceedings, pp.99-108, 1996
[10] Xia, J., C., El-Sana, J., and Varshney, A. Adaptive real-time level-of-detail-based rendering for polygonal models, IEEE Transactions on Visualization and Computer Graphics Vol. 3, No. 2, pp.171-187, 1997
[11] Garland, M., and Heckbert, P., S. Surface simplification using quadric error metrics, SIGGRAPH Proceedings 1997, pp.209-216, 1997
[12] Hu, L., Sander, P., and Hoppe, H. Parallel view-dependent level of detail control, IEEE Transactions on Visualization and Computer Graphics Vol. 16, No. 5, pp.718-728, 2010
[13] Papageorgiou, A., and Platis, N. Triangular mesh simplification on the GPU, The Visual Computer: International Journal of Computer Graphics Vol. 31, Issue 2, pp.235-244, 2015
[14] Odaker, T., Kranzlmueller, D., Volkert, J. View-dependent Simplification using Parallel Half Edge Collapses, WSCG 2015 Conference Proceedings, pp.63-72, 2015