“Piecewise-smooth surface fitting onto unstructured 3D sketches” by Yu, Arora, BÆrentzen, Singh and Bousseau

We propose a method to transform unstructured 3D sketches into piecewise smooth surfaces that preserve sketched geometric features. Immersive 3D drawing and sketch-based 3D modeling applications increasingly produce imperfect and unstructured collections of 3D strokes as design output. These 3D sketches are readily perceived as piecewise smooth surfaces by viewers, but are poorly handled by existing 3D surface techniques tailored to well-connected curve networks or sparse point sets. Our algorithm is aligned with human tendency to imagine the strokes as a small set of simple smooth surfaces joined along stroke boundaries. Starting with an initial proxy surface, we iteratively segment the surface into smooth patches joined sharply along some strokes, and optimize these patches to fit surrounding strokes. Our evaluation is fourfold: we demonstrate the impact of various algorithmic parameters, we evaluate our method on synthetic sketches with known ground truth surfaces, we compare to prior art, and we show compelling results on more than 50 designs from a diverse set of 3D sketch sources.

1. Fatemeh Abbasinejad, Pushkar Joshi, and Nina Amenta. 2011. Surface patches from unorganized space curves. In Computer Graphics Forum, Vol. 30.Google ScholarCross Ref
2. Adobe. 2020. Adobe Medium. https://www.adobe.com/products/medium.html.Google Scholar
3. Sung Joon Ahn, W. Rauh, Hyung Suck Cho, and H.-J. Warnecke. 2002. Orthogonal distance fitting of implicit curves and surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 24, 5 (2002).Google Scholar
4. Rahul Arora, Rubaiat Habib Kazi, Fraser Anderson, Tovi Grossman, Karan Singh, and George W Fitzmaurice. 2017. Experimental Evaluation of Sketching on Surfaces in VR. In ACM Conference on Human Factors in Computing Systems (CHI), Vol. 17.Google Scholar
5. Seok-Hyung Bae, Ravin Balakrishnan, and Karan Singh. 2008. ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models. In ACM Symposium on User Interface Software and Technology (UIST).Google ScholarDigital Library
6. Erhan Batuhan Arisoy, Gunay Orbay, and Levent Burak Kara. 2012. Free form surface skinning of 3d curve clouds for conceptual shape design. Journal of computing and information science in engineering 12, 3 (2012).Google Scholar
7. Jean-Philippe Bauchet and Florent Lafarge. 2020. Kinetic shape reconstruction. ACM Transactions on Graphics 39, 5 (2020).Google ScholarDigital Library
8. Matthew Berger, Andrea Tagliasacchi, Lee M Seversky, Pierre Alliez, Gael Guennebaud, Joshua A Levine, Andrei Sharf, and Claudio T Silva. 2017. A survey of surface reconstruction from point clouds. In Computer Graphics Forum, Vol. 36.Google ScholarDigital Library
9. Mikhail Bessmeltsev, Caoyu Wang, Alla Sheffer, and Karan Singh. 2012. Design-driven quadrangulation of closed 3d curves. ACM Transactions on Graphics (Proc. SIGGRAPH Asia) 31, 6 (2012).Google Scholar
10. Blender. 2020. Blender. https://www.blender.org/.Google Scholar
11. Yuri Boykov, Olga Veksler, and Ramin Zabih. 2001. Fast approximate energy minimization via graph cuts. IEEE Transactions on pattern analysis and machine intelligence 23, 11 (2001).Google ScholarDigital Library
12. Yuri Y. Boykov and Marie-Pierre Jolly. 2001. Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. In IEEE International Conference on Computer Vision.Google Scholar
13. Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. 2020. Fast and Robust Mesh Arrangements using Floating-point Arithmetic. ACM Transactions on Graphics (Proc. SIGGRAPH Asia) 39, 6 (2020).Google Scholar
14. David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational shape approximation. In ACM Transactions on Graphics (Proc. SIGGRAPH). 905–914.Google Scholar
15. Forrester Cole, Aleksey Golovinskiy, Alex Limpaecher, Heather Stoddart Barros, Adam Finkelstein, Thomas Funkhouser, and Szymon Rusinkiewicz. 2008. Where do people draw lines? In ACM Transactions on Graphics (Proc. SIGGRAPH).Google Scholar
16. Jacopo Colò. 2021. Penzil. https://www.penzil.app/.Google Scholar
17. Andrew Delong, Anton Osokin, Hossam N Isack, and Yuri Boykov. 2012. Fast approximate energy minimization with label costs. International journal of computer vision 96, 1 (2012).Google ScholarDigital Library
18. Xingyi Du, Qingnan Zhou, Nathan Carr, and Tao Ju. 2021. Boundary-Sampled Halfspaces: A New Representation for Constructive Solid Modeling. ACM Transactions on Graphics (Proc. SIGGRAPH) 40, 4 (2021).Google ScholarDigital Library
19. Marek Dvorožňák, Saman Sepehri Nejad, Ondřej Jamriška, Alec Jacobson, Ladislav Kavan, and Daniel Sýkora. 2018. Seamless Reconstruction of Part-Based High-Relief Models from Hand-Drawn Images. In Proceedings of International Symposium on Sketch-Based Interfaces and Modeling. Article 5.Google Scholar
20. Ricardo Fabbri and Benjamin B. Kimia. 2010. 3D Curve Sketch: Flexible Curve-Based Stereo Reconstruction and Calibration. In IEEE Conference on Computer Vision and Pattern Recognition.Google Scholar
21. Shachar Fleishman, Daniel Cohen-Or, and Cláudio T Silva. 2005. Robust moving least-squares fitting with sharp features. ACM Transactions on Graphics 24, 3 (2005).Google ScholarDigital Library
22. Michael Garland and Paul S Heckbert. 1997. Surface simplification using quadric error metrics. In Annual conference on computer graphics and interactive techniques (SIGGRAPH). 209–216.Google ScholarDigital Library
23. Google. 2016. Tilt Brush. https://www.tiltbrush.com.Google Scholar
24. Giorgio Gori, Alla Sheffer, Nicholas Vining, Enrique Rosales, Nathan Carr, and Tao Ju. 2017. FlowRep: Descriptive Curve Networks for Free-Form Design Shapes. ACM Transaction on Graphics (Proc. SIGGRAPH) 36, 4 (2017).Google Scholar
25. GravitySketch. 2017. Gravity Sketch. https://www.gravitysketch.com/.Google Scholar
26. Yulia Gryaditskaya, Mark Sypesteyn, Jan Willem Hoftijzer, Sylvia C Pont, Frédo Durand, and Adrien Bousseau. 2019. OpenSketch: a richly-annotated dataset of product design sketches. ACM Transactions on Graphics(Proc. SIGGRAPH Asia) 38, 6 (2019).Google Scholar
27. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1992. Surface reconstruction from unorganized points. In Annual conference on computer graphics and interactive techniques (SIGGRAPH). 71–78.Google ScholarDigital Library
28. Alexander Hornung and Leif Kobbelt. 2006. Robust reconstruction of watertight 3D models from non-uniformly sampled point clouds without normal information. In Symposium on geometry processing. 41–50.Google Scholar
29. H. Huang, S. Wu, M. Gong, D. Cohen-Or, U. Ascher, and H. Zhang. 2013. Edge-Aware Point Set Resampling. ACM Transactions on Graphics 32 (2013). Issue 1.Google Scholar
30. Zhiyang Huang, Nathan Carr, and Tao Ju. 2019. Variational implicit point set surfaces. ACM Transactions on Graphics (Proc. SIGGRAPH) 38, 4 (2019).Google Scholar
31. Hossam Isack and Yuri Boykov. 2012. Energy-based geometric multi-model fitting. International journal of computer vision 97, 2 (2012), 123–147.Google ScholarDigital Library
32. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant Field-Aligned Meshes. ACM Transactions on Graphics (Proc. SIGGRAPH Asia) 34, 6 (Nov. 2015).Google ScholarDigital Library
33. Philipp Jenke, Michael Wand, Wolfgang Straßer, and A AKA. 2008. Patch-Graph Reconstruction for Piecewise Smooth Surfaces. In VMV. Citeseer, 3–12.Google Scholar
34. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson surface reconstruction. In Proceedings of the fourth Eurographics symposium on Geometry processing, Vol. 7.Google ScholarDigital Library
35. Yongkwan Kim and Seok-Hyung Bae. 2016. SketchingWithHands: 3D sketching handheld products with first-person hand posture. In ACM Symposium on User Interface Software and Technology (UIST).Google ScholarDigital Library
36. Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Marc Alexa, Denis Zorin, and Daniele Panozzo. 2019. Abc: A big cad model dataset for geometric deep learning. In IEEE Conference on Computer Vision and Pattern Recognition.Google ScholarCross Ref
37. Changjian Li, Hao Pan, Yang Liu, Alla Sheffer, and Wenping Wang. 2017. BendSketch: Modeling Freeform Surfaces Through 2D Sketching. ACM Transactions on Graphics (Proc. SIGGRAPH) 36, 4 (2017).Google ScholarDigital Library
38. Yangyan Li, Xiaokun Wu, Yiorgos Chrysathou, Andrei Sharf, Daniel Cohen-Or, and Niloy J Mitra. 2011. Globfit: Consistently fitting primitives by discovering global relations. In ACM Transactions on Graphics (Proc. SIGGRAPH).Google ScholarDigital Library
39. Mayra D Barrera Machuca, Paul Asente, Wolfgang Stuerzlinger, Jingwan Lu, and Byungmoon Kim. 2018. Multiplanes: Assisted freehand VR Sketching. In Proceedings of the Symposium on Spatial User Interaction. ACM.Google ScholarDigital Library
40. Mayra Donaji Barrera Machuca, Wolfgang Stuerzlinger, and Paul Asente. 2019. The Effect of Spatial Ability on Immersive 3D Drawing. In Proceedings of the ACM Conference on Creativity & Cognition (C&C’19).Google ScholarDigital Library
41. Aron Monszpart, Nicolas Mellado, Gabriel J Brostow, and Niloy J Mitra. 2015. RAPter: rebuilding man-made scenes with regular arrangements of planes. ACM Transactions on Graphics (Proc. SIGGRAPH) 34, 4 (2015).Google ScholarDigital Library
42. Andrew Nealen, Takeo Igarashi, Olga Sorkine, and Marc Alexa. 2006. Laplacian mesh optimization. In Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia. 381–389.Google ScholarDigital Library
43. Andrew Nealen, Takeo Igarashi, Olga Sorkine, and Marc Alexa. 2007. FiberMesh: Designing Freeform Surfaces with 3D Curves. ACM Transactions on Graphics (Proc. SIGGRAPH) 26, 3 (2007).Google ScholarDigital Library
44. GüNay Orbay and Levent Burak Kara. 2012. Sketch-based surface design using malleable curve networks. Computers & Graphics 36, 8 (2012), 916–929.Google ScholarDigital Library
45. Hao Pan, Yang Liu, Alla Sheffer, Nicholas Vining, Chang-Jian Li, and Wenping Wang. 2015. Flow aligned surfacing of curve networks. ACM Transactions on Graphics (Proc. SIGGRAPH) 34, 4 (2015).Google Scholar
46. Trung T. Pham, Markus Eich, Ian Reid, and Gordon Wyeth. 2016. Geometrically Consistent Plane Extraction for Dense Indoor 3D Maps Segmentation. In IROS.Google Scholar
47. Pixologic. 2016. ZBrush. http://pixologic.com/features/about-zbrush.php.Google Scholar
48. Enrique Rosales, Chrystiano Araújo, Jafet Rodriguez, Nicholas Vining, Dongwook Yoon, and Alla Sheffer. 2021. AdaptiBrush: Adaptive General and Predictable VR Ribbon Brush. ACM Transaction on Graphics (Proc. SIGGRAPH Asia) 40, 1 (2021).Google Scholar
49. Enrique Rosales, Jafet Rodriguez, and Alla Sheffer. 2019. SurfaceBrush: from virtual reality drawings to manifold surfaces. ACM Transactions on Graphics (Proc. SIGGRAPH) 38, 4 (2019).Google ScholarDigital Library
50. Bardia Sadri and Karan Singh. 2014. Flow-complex-based shape reconstruction from 3d curves. ACM Transactions on Graphics (TOG) 33, 2 (2014).Google ScholarDigital Library
51. Ryan Schmidt, Azam Khan, Karan Singh, and Gord Kurtenbach. 2009. Analytic drawing of 3D scaffolds. ACM Transactions on Graphics (Proc. SIGGRAPH Asia) 28, 5 (2009).Google Scholar
52. Ruwen Schnabel, Patrick Degener, and Reinhard Klein. 2009. Completion and reconstruction with primitive shapes. In Computer Graphics Forum, Vol. 28.Google ScholarCross Ref
53. Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence 22, 8 (2000).Google Scholar
54. Smoothstep. 2021. Quill. https://quill.art/.Google Scholar
55. Olga Sorkine and Daniel Cohen-Or. 2004. Least-squares meshes. In Proceedings Shape Modeling Applications, 2004. IEEE, 191–199.Google ScholarCross Ref
56. Tibor Stanko, Stefanie Hahmann, Georges-Pierre Bonneau, and Nathalie Saguin-Sprynski. 2016. Smooth interpolation of curve networks with surface normals. In Eurographics 2016 Short Papers. Eurographics Association, 21–24.Google Scholar
57. Andrea Tagliasacchi, Hao Zhang, and Daniel Cohen-Or. 2009. Curve skeleton extraction from incomplete point cloud. In ACM SIGGRAPH 2009 papers. 1–9.Google ScholarDigital Library
58. T. Tasdizen, J.-P. Tarel, and D.B. Cooper. 2000. Improving the stability of algebraic curves for applications. IEEE Transactions on Image Processing 9, 3 (2000).Google ScholarDigital Library
59. Gabriel Taubin. 1993. An improved algorithm for algebraic curve and surface fitting. In 1993 (4th) International Conference on Computer Vision. IEEE, 658–665.Google Scholar
60. Anil Usumezbas, Ricardo Fabbri, and Benjamin B. Kimia. 2017. The Surfacing of Multiview 3D Drawings via Lofting and Occlusion Reasoning. In IEEE Conference on Computer Vision and Pattern Recognition.Google Scholar
61. Jianhua Wu and Leif Kobbelt. 2005. Structure Recovery via Hybrid Variational Surface Approximation. Computer Graphics Forum 24, 3 (2005).Google Scholar
62. Baoxuan Xu, William Chang, Alla Sheffer, Adrien Bousseau, James McCrae, and Karan Singh. 2014. True2Form: 3D curve networks from 2D sketches via selective regularization. ACM Transactions on Graphics (Proc. SIGGRAPH) 33, 4 (2014).Google ScholarDigital Library
63. Dong-Ming Yan, Wenping Wang, Yang Liu, and Zhouwang Yang. 2012. Variational mesh segmentation via quadric surface fitting. Computer-Aided Design 44, 11 (2012).Google Scholar
64. Emilie Yu, Rahul Arora, Tibor Stanko, J Andreas Bærentzen, Karan Singh, and Adrien Bousseau. 2021a. CASSIE: Curve and Surface Sketching in Immersive Environments. In ACM Conference on Human Factors in Computing Systems (CHI). 1–14.Google Scholar
65. Xue Yu, Stephen DiVerdi, Akshay Sharma, and Yotam Gingold. 2021b. ScaffoldSketch: Accurate Industrial Design Drawing in VR. In ACM Symposium on User Interface Software and Technology (UIST).Google Scholar
66. Yang Zhou, Kangxue Yin, Hui Huang, Hao Zhang, Minglun Gong, and Daniel Cohen-Or. 2015. Generalized Cylinder Decomposition. ACM Transactions on Graphics (Proc. SIGGRAPH Asia) 34, 6 (2015).Google Scholar
67. Yixin Zhuang, Ming Zou, Nathan Carr, and Tao Ju. 2013. A general and efficient method for finding cycles in 3D curve networks. ACM Transactions on Graphics (Proc. SIGGRAPH Asia) 32, 6 (2013).Google Scholar