“Generalized motorcycle graphs for imperfect quad-dominant meshes” by Schertler, Panozzo, Gumhold and Tarini

  • ©Nico Schertler, Daniele Panozzo, Stefan Gumhold, and Marco Tarini

  • ©Nico Schertler, Daniele Panozzo, Stefan Gumhold, and Marco Tarini



Entry Number: 155


    Generalized motorcycle graphs for imperfect quad-dominant meshes

Session/Category Title:   An Atlas for the World and Other Surfaces




    We introduce a practical pipeline to create UV T-layouts for real-world quad dominant semi-regular meshes. Our algorithm creates large rectangular patches by relaxing the notion of motorcycle graphs and making it insensitive to local irregularities in the mesh structure such as non-quad elements, redundant irregular vertices, T-junctions, and others. Each surface patch, which can contain multiple singularities and/or polygonal elements, is mapped to an axis-aligned rectangle, leading to a simple and efficient UV layout, which is ideal for texture mapping (allowing for mipmapping and artifact-free bilinear interpolation). We demonstrate that our algorithm is an ideal solution for both recent semi-regular, quad-dominant meshing methods, and for the low-poly meshes typically used in games and movies.


    1. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-grid Maps for Reliable Quad Meshing. ACM Trans. Graph. 32, 4, Article 98 (July 2013), 12 pages. Google ScholarDigital Library
    2. David Bommes, Timm Lempfer, and Leif Kobbelt. 2011. Global Structure Optimization of Quadrilateral Meshes. Computer Graphics Forum 30 (2011), 375–384. Issue 2.Google ScholarCross Ref
    3. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-Mesh Generation and Processing: A Survey. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 51–76. Issue 6. Google ScholarDigital Library
    4. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77. Google ScholarDigital Library
    5. Brent Burley and Dylan Lacewell. 2008. Ptex: Per-Face Texture Mapping for Production Rendering. In Eurographics Symposium on Rendering 2008. 1155–1164. Google ScholarDigital Library
    6. Marcel Campen. 2017. Partitioning Surfaces into Quad Patches. In EG 2017 – Tutorials, Adrien Bousseau and Diego Gutierrez (Eds.). The Eurographics Association.Google Scholar
    7. Marcel Campen, David Bommes, and Leif Kobbelt. 2012. Dual loops meshing: quality quad layouts on manifolds. ACM Trans. Graph. 31, 4 (2012), 110. Google ScholarDigital Library
    8. Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized Global Parametrization. ACM Trans. Graph. 34, 6, Article 192 (Oct. 2015), 12 pages. Google ScholarDigital Library
    9. M. Campen and L. Kobbelt. 2014. Quad Layout Embedding via Aligned Parameterization. Computer Graphics Forum 33, 8 (2014), 69–81. Google ScholarDigital Library
    10. Marcel Campen and Denis Zorin. 2017. Similarity Maps and Field-Guided T-Splines: a Perfect Couple. ACM Trans. Graph 36, 4 (2017). Google ScholarDigital Library
    11. Nathan A. Carr, Jared Hoberock, Keenan Crane, and John C. Hart. 2006. Rectangular multi-chart geometry images. In Proc. of the 4th Eurographics symp. on Geom. proc. Google ScholarDigital Library
    12. Joel Daniels, Cláudio T. Silva, Jason Shepherd, and Elaine Cohen. 2008. Quadrilateral Mesh Simplification. In ACM SIGGRAPH Asia 2008 Papers (SIGGRAPH Asia ’08). Article 148, 9 pages. Google ScholarDigital Library
    13. Jonathan D. Denning, William B. Kerr, and Fabio Pellacini. 2011. MeshFlow: Interactive Visualization of Mesh Construction Sequences. ACM Trans. Graph. 30, 4, Article 66 (July 2011), 8 pages. Google ScholarDigital Library
    14. Hans-Christian Ebke, Patrick Schmidt, Marcel Campen, and Leif Kobbelt. 2016. Interactively Controlled Quad Remeshing of High Resolution 3D Models. ACM Trans. Graph. 35, 6, Article 218 (Nov. 2016), 13 pages. Google ScholarDigital Library
    15. David Eppstein, Michael T Goodrich, Ethan Kim, and Rasmus Tamstorf. 2008. Motorcycle graphs: canonical quad mesh partitioning. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1477–1486. Issue 5. Google ScholarDigital Library
    16. Michael S. Floater and Kai Hormann. 2005. Surface Parameterization: a Tutorial and Survey. In Advances in Multiresolution for Geometric Modelling, Neil A. Dodgson, Michael S. Floater, and Malcolm A. Sabin (Eds.). Springer, 157–186.Google Scholar
    17. Xiao-Ming Fu, Chong-Yang Bai, and Yang Liu. 2016. Efficient Volumetric PolyCube-Map Construction. Computer Graphics Forum 35, 7 (2016), 97–106. Google ScholarDigital Library
    18. Inc. Gurobi Optimization. 2016. Gurobi Optimizer Reference Manual. http://www.gurobi.comGoogle Scholar
    19. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant field-aligned meshes. ACM Trans. Graph. 34, 6 (2015), 189. Google ScholarDigital Library
    20. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial complex augmentation framework for bijective maps. ACM Trans. Graph. 36, 6 (2017), 186. Google ScholarDigital Library
    21. Jukka Jylänki. 2010. A thousand ways to pack the bin-a practical approach to two-dimensional rectangle bin packing. retrived from http://clb.demon.fi/files/RectangleBinPack.pdf (2010).Google Scholar
    22. Kestutis Karciauskas, Daniele Panozzo, and Jörg Peters. 2017. T-junctions in spline surfaces. ACM Trans. Graph. 36, 5 (2017). Google ScholarDigital Library
    23. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Trans. Graph. 21, 3 (July 2002), 362–371. Google ScholarDigital Library
    24. Ruotian Ling, Jin Huang, Bert Jüttler, Feng Sun, Hujun Bao, and Wenping Wang. 2014. Spectral Quadrangulation with Feature Curve Alignment and Element Size Control. ACM Trans. Graph. 34, 1, Article 11 (Dec. 2014), 11 pages. Google ScholarDigital Library
    25. Songrun Liu, Zachary Ferguson, Alec Jacobson, and Yotam Gingold. 2017. Seamless: Seam erasure and seam-aware decoupling of shape from mesh resolution. ACM Trans. Graph. 36, 6, Article 216 (Nov. 2017), 15 pages. Google ScholarDigital Library
    26. Martin Marinov and Leif Kobbelt. 2006. A Robust Two-Step Procedure for Quad-Dominant Remeshing. In Computer Graphics Forum, Vol. 25. Wiley Online Library, 537–546. Issue 3.Google Scholar
    27. Ashish Myles, Nico Pietroni, Denis Kovacs, and Denis Zorin. 2010. Feature-aligned T-meshes. ACM Trans. Graph. 29, 4, Article 117 (July 2010), 11 pages. Google ScholarDigital Library
    28. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust field-aligned global parametrization. ACM Transactions on Graphics (TOG) 33, 4 (2014), 135. Google ScholarDigital Library
    29. D. Panozzo, E. Puppo, M. Tarini, N. Pietroni, and P. Cignoni. 2011. Automatic Construction of Quad-Based Subdivision Surfaces Using Fitmaps. IEEE Transactions on Visualization and Computer Graphics 17, 10 (Oct 2011), 1510–1520. Google ScholarDigital Library
    30. Chi-Han Peng, Eugene Zhang, Yoshihiro Kobayashi, and Peter Wonka. 2011. Connectivity Editing for Quadrilateral Meshes. ACM Trans. Graph. 30, 6, Article 141 (Dec. 2011), 12 pages. Google ScholarDigital Library
    31. Nico Pietroni, Enrico Puppo, Giorgio Marcias, Roberto Roberto, and Paolo Cignoni. 2016. Tracing Field-Coherent Quad Layouts. In Comp. Graph. F., Vol. 35. Wiley Online Library, 485–496. Issue 7. Google ScholarDigital Library
    32. Roi Poranne, Marco Tarini, Sandro Huber, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Autocuts: simultaneous distortion and cut optimization for UV mapping. ACM Trans. Graph. 36, 6 (2017), 215. Google ScholarDigital Library
    33. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25 (Oct. 2006), 1460–1485. Issue 4. Google ScholarDigital Library
    34. Nicolas Ray, Vincent Nivoliers, Sylvain Lefebvre, and Bruno Levy. 2010. Invisible Seams. Computer Graphics Forum 29 (2010). Issue 4. Google ScholarDigital Library
    35. Nicolas Ray and Dmitry Sokolov. 2014. Robust Polylines Tracing for N-Symmetry Direction Field on Triangulated Surfaces. ACM Trans. Graph. 33, 3, Article 30 (June 2014), 11 pages. Google ScholarDigital Library
    36. Faniry H. Razafindrazaka and Konrad Polthier. 2017. Optimal base complexes for quadrilateral meshes. Computer Aided Geometric Design 52–53 (2017), 63 — 74. Proc. GMP. Google ScholarDigital Library
    37. Faniry H Razafindrazaka, Ulrich Reitebuch, and Konrad Polthier. 2015. Perfect matching quad layouts for manifold meshes. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 219–228. Issue 5.Google Scholar
    38. P. V. Sander, Z.J. Wood, S.J. Gortler, J. Snyder, and H. Hoppe. 2003. Multi-chart Geometry Images. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP ’03). Eurographics Association, 146–155. Google ScholarDigital Library
    39. Nico Schertier, Marco Tarini, Wenzel Jakob, Misha Kazhdan, Stefan Gumhold, and Daniele Panozzo. 2017. Field-aligned online surface reconstruction. ACM Trans. Graph. 36, 4 (2017), 77. Google ScholarDigital Library
    40. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4, Article 70 (July 2015), 9 pages. Google ScholarDigital Library
    41. Marco Tarini. 2016. Volume-encoded UV-maps. ACM Trans. Graph. 35, 4, Article 107 (July 2016), 13 pages. Google ScholarDigital Library
    42. Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. PolyCube-Maps. ACM Trans. Graph. 23, 3 (Aug. 2004), 853–860. Google ScholarDigital Library
    43. Marco Tarini, Enrico Puppo, Daniele Panozzo, Nico Pietroni, and Paolo Cignoni. 2011. Simple Quad Domains for Field Aligned Mesh Parametrization. ACM Trans. Graph. 30, 6, Article 142 (Dec. 2011), 12 pages. Google ScholarDigital Library
    44. Marco Tarini, Cem Yuksel, and Sylvain Lefebvre. 2017. Rethinking Texture Mapping. In ACM SIGGRAPH 2017 Courses (SIGGRAPH ’17). Article 11, 139 pages. Google ScholarDigital Library
    45. TurboSquid. 2018. 3D Models for professionals. https://www.turbosquid.com {Online; accessed 23-January-2018}.Google Scholar
    46. Francesco Usai, Marco Livesu, Enrico Puppo, Marco Tarini, and Riccardo Scateni. 2015. Extraction of the quad layout of a triangle mesh guided by its curve skeleton. ACM Trans. Graph. 35, 1 (2015), 6. Google ScholarDigital Library
    47. Chaman Singh Verma and Krishnan Suresh. 2015. A robust combinatorial approach to reduce singularities in quadrilateral meshes. Procedia Engineering 124 (2015), 252–264.Google ScholarCross Ref
    48. Chaman Singh Verma and Krishnan Suresh. 2016. αMST: A Robust Unified Algorithm for Quadrilateral Mesh Adaptation. Procedia Engineering 163 (2016), 238 — 250. 25th International Meshing Roundtable.Google ScholarCross Ref
    49. Cem Yuksel. 2017. Mesh Color Textures. In High-Performance Graphics (HPG 2017). 11. Google ScholarDigital Library
    50. Cem Yuksel, John Keyser, and Donald H House. 2010. Mesh colors. ACM Trans. Graph. 29, 2 (2010), 15. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: