QuadMixer: layout preserving blending of quadrilateral meshes

Abstract

We propose QuadMixer, a novel interactive technique to compose quad mesh components preserving the majority of the original layouts. Quad Layout is a crucial property for many applications since it conveys important information that would otherwise be destroyed by techniques that aim only at preserving shape.

Our technique keeps untouched all the quads in the patches which are not involved in the blending. We first perform robust boolean operations on the corresponding triangle meshes. Then we use this result to identify and build new surface patches for small regions neighboring the intersection curves. These blending patches are carefully quadrangulated respecting boundary constraints and stitched back to the untouched parts of the original models. The resulting mesh preserves the designed edge flow that, by construction, is captured and incorporated to the new quads as much as possible. We present our technique in an interactive tool to show its usability and robustness.

References

1. Autodesk. 2018. Mudbox. https://www.autodesk.com/education/free-software/mudbox
2. Mikhail Bessmeltsev, Caoyu Wang, Alla Sheffer, and Karan Singh. 2012. Design-driven quadrangulation of closed 3D curves. ACM Trans. Graph. 31, 6 (2012), 178:1--178:11.
3. Henning Biermann, Ioana M. Martin, Fausto Bernardini, and Denis Zorin. 2002. Cut-and-paste editing of multiresolution surfaces. ACM Trans. Graph. 21, 3 (2002), 312--321.
4. Stephan Bischoff and Leif Kobbelt. 2005. Structure Preserving CAD Model Repair. Comput. Graph. Forum 24, 3 (2005), 527--536.
5. David Bommes, Timm Lempfer, and Leif Kobbelt. 2011. Global Structure Optimization of Quadrilateral Meshes. Comput. Graph. Forum 30, 2 (2011), 375--384.
6. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Cláudio T. Silva, Marco Tarini, and Denis Zorin. 2013. Quad-Mesh Generation and Processing: A Survey. Comput. Graph. Forum 32, 6 (2013), 51--76.
7. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77.
8. Marcel Campen. 2017a. Partitioning Surfaces Into Quadrilateral Patches: A Survey. Comput. Graph. Forum 36, 8 (2017), 567--588.
9. Marcel Campen. 2017b. Tiling the Bunny: Quad Layouts for Efficient 3D Geometry Representation. IEEE Computer Graphics and Applications 37, 3 (2017), 88--95.
10. Marcel Campen, David Bommes, and Leif Kobbelt. 2012. Dual loops meshing: quality quad layouts on manifolds. ACM Trans. Graph. 31, 4 (2012), 110:1--110:11.
11. Marcel Campen and Leif Kobbelt. 2010. Exact and Robust (Self-)Intersections for Polygonal Meshes. Comput. Graph. Forum 29, 2 (2010), 397--406.
12. Marcel Campen and Leif Kobbelt. 2014. Dual strip weaving: interactive design of quad layouts using elastica strips. ACM Trans. Graph. 33, 6 (2014), 183:1--183:10.
13. Paolo Cignoni, Marco Callieri, Massimiliano Corsini, Matteo Dellepiane, Fabio Ganovelli, and Guido Ranzuglia. 2008. MeshLab: an Open-Source Mesh Processing Tool. In Eurographics Italian Chapter Conference 2008, Salerno, Italy, 2008. 129--136.
14. CNR. 2013. The Visualization and Computer Graphics Library. http://vcg.isti.cnr.it/vcglib/.
15. Joel Daniels, Cláudio T. Silva, Jason Shepherd, and Elaine Cohen. 2008. Quadrilateral mesh simplification. ACM Trans. Graph. 27, 5 (2008), 148:1--148:9.
16. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Designing N-PolyVector Fields with Complex Polynomials. Comput. Graph. Forum 33, 5 (2014), 1--11.
17. David Eppstein, Michael T. Goodrich, Ethan Kim, and Rasmus Tamstorf. 2008. Motorcycle Graphs: Canonical Quad Mesh Partitioning. Comput. Graph. Forum 27, 5 (2008), 1477--1486.
18. Thomas A. Funkhouser, Michael M. Kazhdan, Philip Shilane, Patrick Min, William Kiefer, Ayellet Tal, Szymon Rusinkiewicz, and David P. Dobkin. 2004. Modeling by example. ACM Trans. Graph. 23, 3 (2004), 652--663.
19. LLC Gurobi Optimization. 2018. Gurobi Optimizer Reference Manual. http://www.gurobi.com
20. Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013a. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph. 32, 4 (2013), 33:1--33:12.
21. Alec Jacobson, Daniele Panozzo, et al. 2013b. libigl: A simple C++ geometry processing library. http://igl.ethz.ch/projects/libigl/.
22. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant field-aligned meshes. ACM Trans. Graph. 34, 6 (2015), 189:1--189:15.
23. Zhongping Ji, Ligang Liu, Zhonggui Chen, and Guojin Wang. 2006. Easy Mesh Cutting. Comput. Graph. Forum 25, 3 (2006), 283--291.
24. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover - Surface Parameterization using Branched Coverings. Comput. Graph. Forum 26, 3 (2007), 375--384.
25. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérôme Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (2002), 362--371.
26. Giorgio Marcias, Nico Pietroni, Daniele Panozzo, Enrico Puppo, and Olga Sorkine-Hornung. 2013. Animation-Aware Quadrangulation. Comput. Graph. Forum 32, 5 (2013), 167--175.
27. Giorgio Marcias, Kenshi Takayama, Nico Pietroni, Daniele Panozzo, Olga Sorkine-Hornung, Enrico Puppo, and Paolo Cignoni. 2015. Data-driven interactive quadrangulation. ACM Trans. Graph. 34, 4 (2015), 65:1--65:10.
28. Carroll Morgan. 1994. Programming from Specifications (2Nd Ed.). Prentice Hall International (UK) Ltd., Hertfordshire, UK, UK.
29. Alessandro Muntoni, Stefano Nuvoli, et al. 2019. CG3Lib: A structured C++ geometry processing library. https://github.com/cg3hci/cg3lib.
30. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust field-aligned global parametrization. ACM Trans. Graph. 33, 4 (2014), 135:1--135:14.
31. Ahmad H. Nasri, Malcolm A. Sabin, and Zahraa Yasseen. 2009. Filling N-Sided Regions by Quad Meshes for Subdivision Surfaces. Comput. Graph. Forum 28, 6 (2009), 1644--1658.
32. Darko Pavic, Marcel Campen, and Leif Kobbelt. 2010. Hybrid Booleans. Comput. Graph. Forum 29, 1 (2010), 75--87.
33. Chi-Han Peng, Michael Barton, Caigui Jiang, and Peter Wonka. 2014. Exploring quadrangulations. ACM Trans. Graph. 33, 1 (2014), 12:1--12:13.
34. Chi-Han Peng, Eugene Zhang, Yoshihiro Kobayashi, and Peter Wonka. 2011. Connectivity editing for quadrilateral meshes. ACM Trans. Graph. 30, 6 (2011), 141:1--141:12.
35. Nico Pietroni, Enrico Puppo, Giorgio Marcias, Roberto Scopigno, and Paolo Cignoni. 2016. Tracing Field-Coherent Quad Layouts. Comput. Graph. Forum 35, 7 (2016), 485--496.
36. Nico Pietroni, Davide Tonelli, Enrico Puppo, Maurizio Froli, Roberto Scopigno, and Paolo Cignoni. 2015. Statics Aware Grid Shells. Comput. Graph. Forum 34, 2 (2015), 627--641.
37. Pilgway. 2017. 3DCoat. https://3dcoat.com/home/
38. Pixologic. 1999. ZBrush. http://pixologic.com
39. Scott Schaefer, Joe D. Warren, and Denis Zorin. 2004. Lofting Curve Networks using Subdivision Surfaces. In Second Eurographics Symposium on Geometry Processing, Nice, France, July 8--10, 2004. 103--114.
40. Ryan Schmidt and Karan Singh. 2010. Meshmixer: An Interface for Rapid Mesh Composition. In ACM SIGGRAPH 2010 Talks (SIGGRAPH '10). ACM, New York, NY, USA, Article 6, 1 pages.
41. Andrei Sharf, Marina Blumenkrants, Ariel Shamir, and Daniel Cohen-Or. 2006. Snap-Paste: an interactive technique for easy mesh composition. The Visual Computer 22, 9--11 (2006), 835--844.
42. Kenshi Takayama, Daniele Panozzo, Alexander Sorkine-Hornung, and Olga Sorkine-Hornung. 2013. Sketch-based generation and editing of quad meshes. ACM Trans. Graph. 32, 4 (2013), 97:1--97:8.
43. Kenshi Takayama, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Pattern-Based Quadrangulation for N-Sided Patches. Comput. Graph. Forum 33, 5 (2014), 177--184.
44. Marco Tarini, Nico Pietroni, Paolo Cignoni, Daniele Panozzo, and Enrico Puppo. 2010. Practical quad mesh simplification. Comput. Graph. Forum 29, 2 (2010), 407--418.
45. 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 (2011), 142:1--142:12.
46. The CGAL Project. 2019. CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board.
47. Julien Tierny, Joel Daniels II, Luis Gustavo Nonato, Valerio Pascucci, and Cláudio T. Silva. 2011. Inspired quadrangulation. Computer-Aided Design 43, 11 (2011), 1516--1526.
48. Amir Vaxman, Marcel Campen, Olga Diamanti, David Bommes, Klaus Hildebrandt, Mirela Ben-Chen, and Daniele Panozzo. 2017. Directional field synthesis, design, and processing. In SIGGRAPH '17 Courses. 12:1--12:30.
49. The Foundry Visionmongers. 2018. Modo 12.1. http://www.thefoundry.co.uk/products/modo
50. Zahraa Yasseen, Ahmad H. Nasri, W. Boukaram, Pascal Volino, and Nadia Magnenat-Thalmann. 2013. Sketch-based garment design with quad meshes. Computer-Aided Design 45, 2 (2013), 562--567.
51. Juyong Zhang, Chunlin Wu, Jianfei Cai, Jianmin Zheng, and Xue-Cheng Tai. 2010. Mesh Snapping: Robust Interactive Mesh Cutting Using Fast Geodesic Curvature Flow. Comput. Graph. Forum 29, 2 (2010), 517--526.
52. Jiaran Zhou, Marcel Campen, Denis Zorin, Changhe Tu, and Cláudio T. Silva. 2018. Quadrangulation of non-rigid objects using deformation metrics. Computer Aided Geometric Design 62 (2018), 3--15.
53. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh arrangements for solid geometry. ACM Trans. Graph. 35, 4 (2016), 39:1--39:15.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Mesh models