“Error-bounded compatible remeshing” by Yang, Zhang, Liu, Liu and Fu

  • ©Yang Yang, Wen-Xiang Zhang, Yuan Liu, Ligang Liu, and Xiao-Ming Fu




    Error-bounded compatible remeshing

Session/Category Title: Shape Modeling



    We present a novel method to construct compatible surface meshes with bounded approximation errors. Given two oriented and topologically equivalent surfaces and a sparse set of corresponding landmarks, our method contains two steps: (1) generate compatible meshes with bounded approximation errors and (2) reduce mesh complexity while ensuring that approximation errors are always bounded. Central to the first step is a parameterization-based remeshing technique, which is capable of isotropically remeshing the input surfaces to be compatible and error-bounded. By iteratively performing a novel edge-based compatible remeshing and increasing the compatible target edge lengths, the second step effectively reduces mesh complexity while explicitly maintaining compatibility, regularity, and bounding approximation errors. Tests on various pairs of complex models demonstrate the efficacy and practicability of our method for constructing high-quality compatible meshes with bounded approximation errors.


    1. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Trans. Graph. 35, 6 (2016), 190:1–190:12.Google ScholarDigital Library
    2. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted bijections for low distortion surface mappings. ACM Trans. Graph. 33, 4 (2014), 69:1–69:12.Google ScholarDigital Library
    3. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015. Seamless Surface Mappings. ACM Trans. Graph. 34, 4 (2015), 72:1–72:13.Google ScholarDigital Library
    4. Marc Alexa. 1999. Merging Polyhedral Shapes with Scattered Features. In Proceedings of the International Conference on Shape Modeling and Applications. 202–210.Google ScholarDigital Library
    5. Pierre Alliez, Éric Colin de Verdière, Olivier Devillers, and Martin Isenburg. 2005. Centroidal Voronoi diagrams for isotropic surface remeshing. Graphical Models 67, 3 (2005), 204 — 231.Google ScholarDigital Library
    6. Pierre Alliez, Mark Meyer, and Mathieu Desbrun. 2002. Interactive Geometry Remeshing. ACM Trans. Graph. 21, 3 (2002), 347–354.Google ScholarDigital Library
    7. Pierre Alliez, Giuliana Ucelli, Craig Gotsman, and Marco Attene. 2008. Recent advances in remeshing of surfaces. In Shape analysis and structuring. 53–82.Google Scholar
    8. H Borouchaki and PJ Frey. 2005. Simplification of surface mesh using Hausdorff envelope. Computer methods in applied mechanics and engineering 194, 48-49 (2005), 4864–4884.Google Scholar
    9. Mario Botsch and Leif Kobbelt. 2004. A Remeshing Approach to Multiresolution Modeling. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP ’04). 185–192.Google ScholarDigital Library
    10. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Lévy. 2010. Polygon mesh processing. AK Peters/CRC Press.Google Scholar
    11. Shuangming Chai, Xiao-Ming Fu, Xin Hu, Yang Yang, and Ligang Liu. 2018. Sphere-based Cut Construction for Planar Parameterizations. Computer & Graphics 74 (2018), 66–75.Google ScholarCross Ref
    12. Shuangming Chai, Xiao-Ming Fu, and Ligang Liu. 2019. Voting for Distortion Points in Geometric Processing. IEEE. T. Vis. Comput. Gr. (2019), 1–1.Google ScholarCross Ref
    13. Long Chen and Jin-chao Xu. 2004. Optimal delaunay triangulations. Journal of Computational Mathematics (2004), 299–308.Google Scholar
    14. Xiao-Xiang Cheng, Xiao-Ming Fu, Chi Zhang, and Shuangming Chai. 2019. Practical Error-Bounded Remeshing by Adaptive Refinement. Computers & Graphics 82 (2019), 163–173.Google ScholarDigital Library
    15. Paolo Cignoni, Claudio Rocchini, and Roberto Scopigno. 1998. Metro: measuring error on simplified surfaces. In Comput. Graph. Forum, Vol. 17. 167–174.Google ScholarCross Ref
    16. Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, Frederick Brooks, and William Wright. 1996. Simplification envelopes. In Siggraph, Vol. 96. 119–128.Google Scholar
    17. Qiang Du, Vance Faber, and Max Gunzburger. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM review 41, 4 (1999), 637–676.Google Scholar
    18. Marion Dunyach, David Vanderhaeghe, Loïc Barthe, and Mario Botsch. 2013. Adaptive remeshing for real-time mesh deformation. In Eurographics 2013 – Short Papers.Google Scholar
    19. Danielle Ezuz, Justin Solomon, and Mirela Ben-Chen. 2019. Reversible Harmonic Maps between Discrete Surfaces. ACM Trans. Graph. 38, 2 (2019).Google ScholarDigital Library
    20. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing locally injective mappings by advanced MIPS. ACM Trans. Graph. 34, 4 (2015), 71:1–71:12.Google ScholarDigital Library
    21. Xiao-Ming Fu, Yang Liu, John Snyder, and Baining Guo. 2014. Anisotropic simplicial meshing using local convex functions. ACM Trans. Graph. 33, 6 (2014), 182:1–182:11.Google ScholarDigital Library
    22. Kai Hormann, Bruno Lévy, and Alla Sheffer. 2007. Mesh Parameterization: Theory and Practice. In ACM SIGGRAPH 2007 Courses (SIGGRAPH ’07).Google ScholarDigital Library
    23. K. Hu, D. Yan, D. Bommes, P. Alliez, and B. Benes. 2017. Error-Bounded and Feature Preserving Surface Remeshing with Minimal Angle Improvement. IEEE. T. Vis. Comput. Gr. 23, 12 (2017), 2560–2573.Google ScholarCross Ref
    24. Xin Hu, Xiao-Ming Fu, and Ligang Liu. 2018. Advanced Hierarchical Spherical Parameterizations. IEEE. T. Vis. Comput. Gr. 24, 6 (2018), 1930–1941.Google ScholarCross Ref
    25. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Trans. Graph. 36, 6 (2017), 186:1–186:9.Google ScholarDigital Library
    26. Vladimir G. Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended Intrinsic Maps. ACM Trans. Graph. 30, 4 (2011).Google ScholarDigital Library
    27. Vladislav Kraevoy and Alla Sheffer. 2004. Cross-parameterization and compatible remeshing of 3D models. ACM Trans. Graph. 23, 3 (2004), 861–869.Google ScholarDigital Library
    28. Tsz-Ho KwoK, Yunbo Zhang, and Charlie CL Wang. 2012. Efficient optimization of common base domains for cross parameterization. IEEE. T. Vis. Comput. Gr. 18, 10 (2012), 1678–1692.Google ScholarDigital Library
    29. Aaron W. F. Lee, David Dobkin, Wim Sweldens, and Peter Schröder. 1999. Multiresolution Mesh Morphing. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). 343–350.Google ScholarDigital Library
    30. Xin Li and SS Iyengar. 2015. On computing mapping of 3d objects: A survey. ACM Computing Surveys (CSUR) 47, 2 (2015), 34.Google ScholarDigital Library
    31. Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive Parameterizations. ACM Trans. Graph. 37, 4 (2018), 41:1–41:12.Google ScholarDigital Library
    32. Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, Dong-Ming Yan, Lin Lu, and Chenglei Yang. 2009. On Centroidal Voronoi Tessellation—Energy Smoothness and Fast Computation. ACM Trans. Graph. 28, 4 (2009), 101:1–101:17.Google ScholarDigital Library
    33. Manish Mandad, David Cohen-Steiner, and Pierre Alliez. 2015. Isotopic approximation within a tolerance volume. ACM Trans. Graph. 34, 4 (2015), 64:1–64:12.Google ScholarDigital Library
    34. Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. 2017. Variance-minimizing Transport Plans for Inter-surface Mapping. ACM Trans. Graph. 36, 4 (2017), 39:1–39:14.Google ScholarDigital Library
    35. Simone Melzi, Jing Ren, Emanuele Rodolà, Abhishek Sharma, Peter Wonka, and Maks Ovsjanikov. 2019. Zoomout: Spectral upsampling for efficient shape correspondence. ACM Transactions on Graphics (TOG) 38, 6 (2019), 155.Google ScholarDigital Library
    36. Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional Maps: A Flexible Representation of Maps between Shapes. ACM Trans. Graph. 31, 4 (2012).Google ScholarDigital Library
    37. Yue Peng, Bailin Deng, Juyong Zhang, Fanyu Geng, Wenjie Qin, and Ligang Liu. 2018. Anderson acceleration for geometry optimization and physics simulation. ACM Transactions on Graphics (TOG) 37, 4 (2018), 42.Google ScholarDigital Library
    38. Emil Praun, Wim Sweldens, and Peter Schröder. 2001. Consistent Mesh Parameterizations. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). 179–184.Google ScholarDigital Library
    39. Jing Ren, Adrien Poulenard, Peter Wonka, and Maks Ovsjanikov. 2018. Continuous and Orientation-preserving Correspondences via Functional Maps. ACM Trans. Graph. 37, 6 (2018), 248:1–248:16.Google Scholar
    40. Patrick Schmidt, Janis Born, Marcel Campen, and Leif Kobbelt. 2019. Distortion-minimizing Injective Maps Between Surfaces. ACM Trans. Graph. 38, 6 (2019), 156:1–156:15.Google ScholarDigital Library
    41. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-surface Mapping. ACM Trans. Graph. 23, 3 (2004), 870–877.Google ScholarDigital Library
    42. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4 (2015), 70:1–70:9.Google ScholarDigital Library
    43. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry Processing. 109–116.Google ScholarDigital Library
    44. Jian-Ping Su, Chunyang Ye, Ligang Liu, and Xiao-Ming Fu. 2020. Efficient Bijective Parameterizations. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
    45. Vitaly Surazhsky, Pierre Alliez, and Craig Gotsman. 2003. Isotropic remeshing of surfaces: a local parameterization approach. In Proceedings of the 12th International Meshing Roundtable. 204–231.Google Scholar
    46. Vitaly Surazhsky and Craig Gotsman. 2003. Explicit Surface Remeshing. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP ’03). 20–30.Google ScholarDigital Library
    47. Oliver Van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. 2011. A survey on shape correspondence. In Comput. Graph. Forum, Vol. 30. 1681–1707.Google ScholarCross Ref
    48. Matthias Vestner, Roee Litman, Emanuele Rodola, Alex Bronstein, and Daniel Cremers. 2017. Product Manifold Filter: Non-Rigid Shape Correspondence via Kernel Density Estimation in the Product Space. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).Google ScholarCross Ref
    49. J. Vorsatz, Ch. Rössl, and H.-P. Seidel. 2003. Dynamic Remeshing and Applications. Journal of Computing and Information Science in Engineering 3, 4 (2003), 338–344.Google ScholarCross Ref
    50. Y. Wang, D. Yan, X. Liu, C. Tang, J. Guo, X. Zhang, and P. Wonka. 2019. Isotropic Surface Remeshing without Large and Small Angles. IEEE. T. Vis. Comput. Gr. 25, 7 (2019), 2430–2442.Google ScholarCross Ref
    51. Yang Yang, Xiao-Ming Fu, Shuangming Chai, Shi-Wei Xiao, and Ligang Liu. 2019b. Volume-Enhanced Compatible Remeshing of 3D Models. IEEE. T. Vis. Comput. Gr. 25, 10 (2019), 2999–3010.Google ScholarCross Ref
    52. Yang Yang, Xiao-Ming Fu, and Ligang Liu. 2019a. Computing Surface PolyCube-Maps by Constrained Voxelization. Comput. Graph. Forum 38, 7 (2019), 299–309.Google ScholarCross Ref
    53. Tianyu Zhu, Chunyang Ye, Shuangming Chai, and Xiao-Ming Fu. 2020. Greedy Cut Construction for Parameterizations. Comput. Graph. Forum 39, 2 (2020).Google Scholar

ACM Digital Library Publication:

Overview Page: