Abstract
We present a novel parallel algorithm for mesh simplification that can reduce an input triangle mesh with highly improved performance. To take full advantage of the GPU comprising many computing cores, we enable collapsing of connected edges to be processed at one time by breaking data dependency in the update of the mesh data structure. Our solution is a lazy update method, which temporarily stores edge update information in a table and then updates the mesh data with it in the next step. Thanks to the lazy update method, we can more freely choose a large number of edges in the form of small trees for collapsing. The constructed trees are split to satisfy an error constraint, prevent normal flipping, and preserve the mesh topology. In experiments performed on several test models of various scales, we found that our algorithm consistently outperformed the prior GPU algorithm of Papageorgiou and Platis (Vis Comput 31(2):235–244, 2015) by a factor of 10 or higher.
Similar content being viewed by others
References
Cabiddu, D., Attene, M.: Large mesh simplification for distributed environments. Comput. Graph 51(C), 81–89 (2015)
Cellier, F., Gandoin, P.M., Chaine, R., Barbier-Accary, A., Akkouche, S.: Simplification and streaming of gis terrain for web clients. In: Proc. of the 17th International Conference on 3D Web Technology, Web3D ’12, pp. 73–81. New York (2012)
Cignoni, P., Callieri, M., Corsini, M., Dellepiane, M., Ganovelli, F., Ranzuglia, G.: Meshlab: an open-source mesh processing tool. In: Scarano, V., Chiara, R.D., Erra U. (eds.) Proceedings of Eurographics Italian Chapter Conference, pp. 129–136 (2008)
DeCoro, C., Tatarchuk, N.: Real-time mesh simplification using the GPU. In: Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games, I3D ’07, pp. 161–166. ACM, New York (2007)
Dey, T.K., Edelsbrunner, H., Guha, S., Nekhayev, D.V.: Topology preserving edge contraction. Publ. Inst. Math. 66, 23–45 (1998)
Garland, M., Heckbert, P.S.: Surface simplification using quadric error metrics. In: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’97, pp. 209–216. ACM Press/Addison-Wesley Publishing Co. (1997)
Grund, N., Derzapf, E., Guthe, M.: Instant level-of-detail. In: Proceedings of Vision, Modeling, and Visualization, pp. 293–299 (2011)
Guéziec, A.: Surface simplification with variable tolerance. In: Second Annual Intl. Symp. on Medical Robotics and Computer Assisted Surgery, pp. 132–139 (1995)
Hjelmervik, J., Léon, J.C.: GPU-accelerated shape simplification for mechanical-based applications. In: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2007. SMI ’07, pp. 91–102. IEEE Computer Society, Washington, DC (2007)
Hoppe, H.: Progressive meshes. In: Proc. of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’96, pp. 99–108. ACM, New York (1996)
Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W.: Mesh optimization. Tech. Rep. TR 93-01-01. Dept. of Computer Science, University of Washington (1993)
Kobbelt, L., Campagna, S., peter Seidel, H.: A general framework for mesh decimation. In: Proceedings of Graphics Interface, pp. 43–50 (1998)
Lindstrom, P.: Out-of-core simplification of large polygonal models. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’00, pp. 259–262 (2000)
Luebke, D.P.: A developer’s survey of polygonal simplification algorithms. IEEE Comput. Graph. Appl. 21(3), 24–35 (2001)
Papageorgiou, A., Platis, N.: Triangular mesh simplification on the GPU. Vis. Comput. 31(2), 235–244 (2015)
Rossignac, J., Borrel, P.: Multi-resolution 3d approximation for rendering complex scenes. In: Modeling in Computer Graphics, pp. 455–465. Springer, Berlin, Heidelberg (1993)
Salinas, D., Lafarge, F., Alliez, P.: Structure-aware mesh decimation. Comput. Graph Forum 34(6), 211–227 (2015)
Schaefer, S., Warren, J.: Adaptive vertex clustering using octrees. In: Proceedings of SIAM Geometric Design and Computing (2003)
Schroeder, W.J., Zarge, J.A., Lorensen, W.E.: Decimation of triangle meshes. SIGGRAPH Comput. Gr. 26(2), 65–70 (1992)
Shontz, S.M., Nistor, D.M.: CPU-GPU algorithms for triangular surface mesh simplification. In: Proceedings of the 21st International Meshing Roundtable, pp. 475–492 (2012)
Xiong, H., Jiang, X., Zhang, Y., Shi, J.: Parallel simplification of large meshes on pc clusters. In: Proc. of the 8th Eurographics Conference on Parallel Graphics and Visualization, EGPGV ’08, pp. 33–40 (2008)
Acknowledgments
This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2013R1A1A2011733).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lee, H., Kyung, MH. Parallel mesh simplification using embedded tree collapsing. Vis Comput 32, 967–976 (2016). https://doi.org/10.1007/s00371-016-1242-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-016-1242-z