“Parametrization quantization with free boundaries for trimmed quad meshing” by Lyon, Campen, Bommes and Kobbelt

  • ©Max Lyon, Marcel Campen, David Bommes, and Leif Kobbelt




    Parametrization quantization with free boundaries for trimmed quad meshing

Session/Category Title:   Meshing



    The generation of quad meshes based on surface parametrization techniques has proven to be a versatile approach. These techniques quantize an initial seamless parametrization so as to obtain an integer grid map implying a pure quad mesh. State-of-the-art methods following this approach have to assume that the surface to be meshed either has no boundary, or has a boundary which the resulting mesh is supposed to be aligned to. In a variety of applications this is not desirable and non-boundary-aligned meshes or grid-parametrizations are preferred. We thus present a technique to robustly generate integer grid maps which are either boundary-aligned, non-boundary-aligned, or partially boundary-aligned, just as required by different applications. We thereby generalize previous work to this broader setting. This enables the reliable generation of trimmed quad meshes with partial elements along the boundary, preferable in various scenarios, from tiled texturing over design and modeling to fabrication and architecture, due to fewer constraints and hence higher overall mesh quality and other benefits in terms of aesthetics and flexibility.


    1. Ergun Akleman, Avneet Kaur, and Lori Green. 2005. Tiled Textures. ISAMA’2008 (2005).Google Scholar
    2. Cecil G. Armstrong, Harold J. Fogg, Christopher M. Tierney, and Trevor T. Robinson. 2015. Common themes in multi-block structured quad/hex mesh generation. Procedia Engineering 124 (2015), 70–82.Google ScholarCross Ref
    3. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-Grid Maps for Reliable Quad Meshing. ACM Transactions on Graphics 32, 4 (2013), 98:1–98:12. Google ScholarDigital Library
    4. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Cláudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-Mesh Generation and Processing: A Survey. Computer Graphics Forum 32, 6 (2013), 51–76. Google ScholarDigital Library
    5. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-Integer Quadrangulation. ACM Transactions on Graphics 28, 3 (2009), 77:1–77:10. Google ScholarDigital Library
    6. Marcel Campen. 2017. Partitioning Surfaces Into Quadrilateral Patches: A Survey. In Computer Graphics Forum, Vol. 36. 567–588. Google ScholarDigital Library
    7. Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized global parametrization. ACM Transactions on Graphics 34, 6 (2015). Google ScholarDigital Library
    8. Marcel Campen, Moritz Ibing, Hans-Christian Ebke, Denis Zorin, and Leif Kobbelt. 2016. Scale-Invariant Directional Alignment of Surface Parametrizations. Computer Graphics Forum 35, 5 (2016).Google Scholar
    9. Marcel Campen and Leif Kobbelt. 2014. Quad Layout Embedding via Aligned Parameterization. Computer Graphics Forum 33, 8 (2014), 69–81. Google ScholarDigital Library
    10. Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial Connections on Discrete Surfaces. Computer Graphics Forum 29, 5 (2010), 1525–1533.Google ScholarCross Ref
    11. Shen Dong, Peer-Timo Bremer, Michael Garland, Valerio Pascucci, and John C. Hart. 2006. Spectral surface quadrangulation. ACM Transactions on Graphics 25, 3 (2006). Google ScholarDigital Library
    12. Hans-Christian Ebke, David Bommes, Marcel Campen, and Leif Kobbelt. 2013. QEx: Robust Quad Mesh Extraction. 32, 6 (2013), 168:1–168:10. Google ScholarDigital Library
    13. Hans-Christian Ebke, Marcel Campen, David Bommes, and Leif Kobbelt. 2014. Level-of-Detail Quad Meshing. ACM Transactions on Graphics 33, 6 (2014), 184:1–184:11. 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 (2016), 218:1–218:13. Google ScholarDigital Library
    15. David Eppstein and Jeff Erickson. 1999. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. Discrete & Computational Geometry 22, 4 (1999), 569–592.Google ScholarCross Ref
    16. David Eppstein, Michael T. Goodrich, Ethan Kim, and Rasmus Tamstorf. 2008. Motorcycle Graphs: Canonical Quad Mesh Partitioning. Computer Graphics Forum 27, 5 (2008), 1477–1486. Google ScholarDigital Library
    17. Xianzhong Fang, Hujun Bao, Yiying Tong, Mathieu Desbrun, and Jin Huang. 2018. Quadrangulation Through Morse-parameterization Hybridization. ACM Trans. Graph. 37, 4 (2018), 92:1–92:15. Google ScholarDigital Library
    18. Gerald E. Farin and Dianne Hansford. 2000. The Essentials of CAGD. A. K. Peters, Ltd., Natick, MA, USA. Google ScholarDigital Library
    19. Thomas-Peter Fries and Ted Belytschko. 2010. The extended/generalized finite element method: an overview of the method and its applications. Internat. J. Numer. Methods Engrg. 84, 3 (2010), 253–304.Google ScholarCross Ref
    20. Huanhuan Gu, Jean Gotman, and Jon P. Webb. 2011. Computed Basis Functions for Finite Element Analysis Based on Tomographic Data. IEEE Transactions on Biomedical Engineering 58 (2011), 2498–2505.Google ScholarCross Ref
    21. Erkan Gunpinar, Masaki Moriguchi, Hiromasa Suzuki, and Yutaka Ohtake. 2014. Feature-aware partitions from the motorcycle graph. Computer-Aided Design 47 (2014). Google ScholarDigital Library
    22. Jin Huang, Muyang Zhang, Jin Ma, Xinguo Liu, Leif Kobbelt, and Hujun Bao. 2008. Spectral quadrangulation with orientation and alignment control. In ACM Transactions on Graphics (TOG), Vol. 27. 147. Google ScholarDigital Library
    23. Jingwei Huang, Yichao Zhou, Matthias Niessner, Jonathan Richard Shewchuk, and Leonidas J Guibas. 2018. QuadriFlow: A Scalable and Robust Method for Quadrangulation. In Computer Graphics Forum, Vol. 37. 147–160.Google ScholarCross Ref
    24. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant field-aligned meshes. ACM Transactions on Graphics 34, 6 (2015), 189. Google ScholarDigital Library
    25. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover – Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3 (2007).Google Scholar
    26. Zhang Kedi, Najafi Ahmad Raeisi, Jin Jian-Ming, and Geubelle Philippe H. 2015. An interface-enriched generalized finite element analysis for electromagnetic problems with non-conformal discretizations. International Journal of Numerical Modelling: Electronic Networks, Devices and Fields 29, 2 (2015), 265–279.Google Scholar
    27. Andrei Khodakovsky, Nathan Litke, and Peter Schröder. 2003. Globally smooth parameterizations with low distortion. ACM Transactions on Graphics 22, 3 (2003). Google ScholarDigital Library
    28. Denis Kovacs, Ashish Myles, and Denis Zorin. 2011. Anisotropic quadrangulation. Computer Aided Geometric Design 28, 8 (2011), 449–462. Google ScholarDigital Library
    29. 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 Transactions on Graphics (TOG) 34, 1 (2014), 11. Google ScholarDigital Library
    30. Celong Liu, Wuyi Yu, Zhonggui Chen, and Xin Li. 2017. Distributed poly-square mapping for large-scale semi-structured quad mesh generation. Computer-Aided Design 90 (2017), 5–17.Google ScholarCross Ref
    31. Manish Mandad and Marcel Campen. 2019. Exact Constraint Satisfaction for Truly Seamless Parametrization. Computer Graphics Forum 38, 2 (2019).Google Scholar
    32. Giorgio Marcias, Nico Pietroni, Daniele Panozzo, Enrico Puppo, and Olga Sorkine-Hornung. 2013. Animation-aware quadrangulation. In Proc. Symposium on Geometry Processing. 167–175. Google ScholarDigital Library
    33. Jan Möbius and Leif Kobbelt. 2012. OpenFlipper: An Open Source Geometry Processing and Rendering Framework. In Curves and Surfaces. Lecture Notes in Computer Science, Vol. 6920. Google ScholarDigital Library
    34. Ashish Myles, Nico Pietroni, Denis Kovacs, and Denis Zorin. 2010. Feature-aligned T-meshes. ACM Transactions on Graphics 29, 4 (2010), 117:1–117:11. Google ScholarDigital Library
    35. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Transactions on Graphics 33, 4 (2014). Google ScholarDigital Library
    36. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Transactions on Graphics 31, 4 (2012). Google ScholarDigital Library
    37. Moës Nicolas, Dolbow John, and Belytschko Ted. 1999. A finite element method for crack growth without remeshing. Internat. J. Numer. Methods Engrg. 46, 1 (1999).Google Scholar
    38. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover – Parameterization of 3D Volumes. Computer Graphics Forum 30, 5 (2011), 1397–1406.Google ScholarCross Ref
    39. Steven J Owen. 1998. A survey of unstructured mesh generation technology.. In IMR.Google Scholar
    40. Daniele Panozzo, Enrico Puppo, Marco Tarini, and Olga Sorkine-Hornung. 2014. Frame fields: Anisotropic and non-orthogonal cross fields. ACM Transactions on Graphics (TOG) 33, 4 (2014), 134. Google ScholarDigital Library
    41. Nico Pietroni, Marco Tarini, Olga Sorkine, and Denis Zorin. 2011. Global parametrization of range image sets. In ACM Transactions on Graphics (TOG), Vol. 30. 149. Google ScholarDigital Library
    42. Helmut Pottmann, Alexander Schiftner, Pengbo Bo, Heinz Schmiedhofer, Wenping Wang, Niccolo Baldassini, and Johannes Wallner. 2008. Freeform Surfaces from Single Curved Panels. ACM Trans. Graph. 27, 3 (2008), 76:1–76:10. Google ScholarDigital Library
    43. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 4, Article 37a (2017).Google ScholarDigital Library
    44. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic global parameterization. ACM Transactions on Graphics 25, 4 (2006), 1460–1485. Google ScholarDigital Library
    45. Nicolas Ray, Vincent Nivoliers, Sylvain Lefebvre, and Bruno Lévy. 2010. Invisible seams. In Computer Graphics Forum, Vol. 29. 1489–1496. Google ScholarDigital Library
    46. Faniry H. Razafindrazaka, Ulrich Reitebuch, and Konrad Polthier. 2015. Perfect Matching Quad Layouts for Manifold Meshes. Computer Graphics Forum 34, 5 (2015), 219–228.Google ScholarDigital Library
    47. Nico Schertler, Daniele Panozzo, Stefan Gumhold, and Marco Tarini. 2018. Generalized motorcycle graphs for imperfect quad-dominant meshes. ACM Transactions on Graphics (TOG) 37, 4 (2018), 155. Google ScholarDigital Library
    48. Nico Schertler, Marco Tarini, Wenzel Jakob, Misha Kazhdan, Stefan Gumhold, and Daniele Panozzo. 2017. Field-aligned online surface reconstruction. ACM Transactions on Graphics (TOG) 36, 4 (2017), 77. Google ScholarDigital Library
    49. Thomas W. Sederberg, Jianmin Zheng, Almaz Bakenov, and Ahmad Nasri. 2003. T-splines and T-NURCCs. ACM Transactions on Graphics 22, 3 (2003), 477–484. Google ScholarDigital Library
    50. Kenji Shimada. 2006. Current trends and issues in automatic mesh generation. Computer-Aided Design and Applications 3, 6 (2006), 741–750.Google ScholarCross Ref
    51. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Trans. Graph. 36, 4, Article 38 (2017), 11 pages. Google ScholarDigital Library
    52. Yiying Tong, Pierre Alliez, David Cohen-Steiner, and Mathieu Desbrun. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. SGP ’06. 201–210. Google ScholarDigital Library
    53. William T. Tutte. 1963. How to Draw a Graph. Proceedings of the London Mathematical Society s3–13, 1 (1963), 743–767.Google ScholarCross Ref
    54. Mirko Zadravec, Alexander Schiftner, and Johannes Wallner. 2010. Designing quad-dominant meshes with planar faces. In Computer Graphics Forum, Vol. 29. 1671–1679.Google ScholarCross Ref
    55. Muyang Zhang, Jin Huang, Xinguo Liu, and Hujun Bao. 2010. A wave-based anisotropic quadrangulation method. ACM Transactions on Graphics (TOG) 29, 4 (2010), 118. Google ScholarDigital Library
    56. Jiaran Zhou, Marcel Campen, Denis Zorin, Changhe Tu, and Claudio T. Silva. 2018. Quadrangulation of non-rigid objects using deformation metrics. Computer Aided Geometric Design 62 (2018), 3–15.Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: