“Surface2Volume: surface segmentation conforming assemblable volumetric partition” by Araújo, Cabiddu, Attene, Livesu, Vining, et al. …
Conference:
Type(s):
Title:
- Surface2Volume: surface segmentation conforming assemblable volumetric partition
Session/Category Title: Fabrication
Presenter(s)/Author(s):
Abstract:
Users frequently seek to fabricate objects whose outer surfaces consist of regions with different surface attributes, such as color or material. Manufacturing such objects in a single piece is often challenging or even impossible. The alternative is to partition them into single-attribute volumetric parts that can be fabricated separately and then assembled to form the target object. Facilitating this approach requires partitioning the input model into parts that conform to the surface segmentation and that can be moved apart with no collisions. We propose Surface2Volume, a partition algorithm capable of producing such assemblable parts, each of which is affiliated with a single attribute, the outer surface of whose assembly conforms to the input surface geometry and segmentation. In computing the partition we strictly enforce conformity with surface segmentation and assemblability, and optimize for ease of fabrication by minimizing part count, promoting part simplicity, and simplifying assembly sequencing. We note that computing the desired partition requires solving for three types of variables: per-part assembly trajectories, partition topology, i.e. the connectivity of the interface surfaces separating the different parts, and the geometry, or location, of these interfaces. We efficiently produce the desired partitions by addressing one type of variables at a time: first computing the assembly trajectories, then determining interface topology, and finally computing interface locations that allow parts assemblability. We algorithmically identify inputs that necessitate sequential assembly, and partition these inputs gradually by computing and disassembling a subset of assemblable parts at a time. We demonstrate our method’s robustness and versatility by employing it to partition a range of models with complex surface segmentations into assemblable parts. We further validate our framework via output fabrication and comparisons to alternative partition techniques.
References:
1. Maneesh Agrawala, Doantam Phan, Julie Heiser, John Haymaker, Jeff Klingner, Pat Hanrahan, and Barbara Tversky. 2003. Designing effective step-by-step assembly instructions. ACM Trans. Graphics 22, 3 (2003), 828–837. Google ScholarDigital Library
2. Thomas Alderighi, Luigi Malomo, Daniela Giorgi, Nico Pietroni, Bernd Bickel, and Paolo Cignoni. 2018. Metamolds: Computational Design of Silicone Molds. ACM Trans. Graph. 37, 4 (2018), 136:1–136:13. Google ScholarDigital Library
3. Marco Attene. 2015. Shapes in a box: Disassembling 3D objects for efficient packing and fabrication. Computer Graphics Forum 34, 8 (2015), 64–76. Google ScholarDigital Library
4. Amit Bermano, Amir Vaxman, and Craig Gotsman. 2011. Online Reconstruction of 3D Objects from Arbitrary Cross-sections. ACM Trans. Graph. 30, 5 (2011), 113:1–113:11. Google ScholarDigital Library
5. Yuri Boykov and Vladimir Kolmogorov. 2004. An experimental comparison of mincut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Analysis and Machine Intelligence 26, 9 (2004), 1124–1137. Google ScholarDigital Library
6. Yuri Boykov, Olga Veksler, and Ramin Zabih. 2001. Fast approximate energy minimization via graph cuts. IEEE. Trans. Pattern Analysis and Machine Intelligence 23, 11 (2001), 1222–1239. Google ScholarDigital Library
7. Xuelin Chen, Hao Zhang, Jinjie Lin, Ruizhen Hu, Lin Lu, Qi-Xing Huang, Bedrich Benes, Daniel Cohen-Or, and Baoquan Chen. 2015. Dapper: Decompose-and-Pack for 3D printing. ACM Trans. Graphics 34, 6 (2015). Google ScholarDigital Library
8. Chi-Wing Fu, Peng Song, Xiaoqi Yan, Lee Wei Yang, Pradeep Kumar Jayaraman, and Daniel Cohen-Or. 2015. Computational interlocking furniture assembly. ACM Trans. Graphics 34, 4 (2015), 91. Google ScholarDigital Library
9. Thomas Funkhouser, Michael Kazhdan, Philip Shilane, Patrick Min, William Kiefer, Ayellet Tal, Szymon Rusinkiewicz, and David Dobkin. 2004. Modeling by Example. In Proc SIGGRAPH. 652–663. Google ScholarDigital Library
10. A. Guéziec, G. Taubin, F. Lazarus, and B. Horn. 2001. Cutting and stitching: Converting sets of polygons to manifold surfaces. IEEE TVCG 7, 2 (2001), 136–151. Google ScholarDigital Library
11. LLC Gurobi Optimization. 2018. Gurobi Optimizer Reference Manual. (2018). http://www.gurobi.comGoogle Scholar
12. Jingbin Hao, Liang Fang, and Robert E Williams. 2011. An efficient curvature-based partitioning of large-scale STL models. Rapid Prototyping Journal 17, 2 (2011), 116–127.Google ScholarCross Ref
13. Jean Hergel and Sylvain Lefebvre. 2014. Clean color: Improving multi-filament 3D prints. Computer Graphics Forum 33, 2 (2014), 469–478. Google ScholarDigital Library
14. Philipp Herholz, Wojciech Matusik, and Marc Alexa. 2015. Approximating Free-form Geometry with Height Fields for Manufacturing. Computer Graphics Forum 34, 2 (2015), 239–251. Google ScholarDigital Library
15. Kristian Hildebrand, Bernd Bickel, and Marc Alexa. 2013. Orthogonal slicing for additive manufacturing. Computers & Graphics 37, 6 (2013), 669–675. Google ScholarDigital Library
16. Tan-Chi Ho, Jung-Hong Chuang, et al. 2012. Volume Based Mesh Segmentation. Journal of Information Science and Engineering 28, 4 (2012), 705–722.Google Scholar
17. Ruizhen Hu, Honghua Li, Hao Zhang, and Daniel Cohen-Or. 2014. Approximate pyramidal shape decomposition. ACM Trans. Graphics 33, 6 (2014), 213–1. Google ScholarDigital Library
18. Leo Joskowicz and Elisha Sacks. 1999. Computer-Aided Mechanical Design Using Configuration Spaces. Computing in Science & Engineering 1, 6 (1999), 14–21. Google ScholarDigital Library
19. Leo Joskowicz and Elisha P Sacks. 1991. Computational kinematics. Artificial Intelligence 51, 1–3 (1991), 381–416. Google ScholarDigital Library
20. Dan Julius, Vladislav Kraevoy, and Alla Sheffer. 2005. D-Charts: Quasi-Developable Mesh Segmentation. Computer Graphics Forum 24, 3 (2005).Google Scholar
21. Yuki Koyama, Shinjiro Sueda, Emma Steinhardt, Takeo Igarashi, Ariel Shamir, and Wojciech Matusik. 2015. AutoConnect: Computational Design of 3D-Printable Connectors. ACM Trans. Graph. 34, 6 (2015), Article No. 231. Google ScholarDigital Library
22. Roee Lazar, Nadav Dym, Yam Kushinsky, Zhiyang Huang, Tao Ju, and Yaron Lipman. 2018. Robust Optimization for Topological Surface Reconstruction. ACM Trans. Graph. 37, 4 (2018), 46:1–46:10. Google ScholarDigital Library
23. L. Liu, C. Bajaj, J. O. Deasy, D. A. Low, and T. Ju. 2008. Surface Reconstruction From Non-parallel Curve Networks. Computer Graphics Forum 27, 2 (2008), 155–163.Google ScholarCross Ref
24. Marco Livesu. 2018. A Heat Flow Relaxation Scheme for n Dimensional Discrete Hyper Surfaces. Computers & Graphics 71 (2018), 124 — 131.Google ScholarCross Ref
25. Marco Livesu, Stefano Ellero, Jonàs Martínez, Lefebvre Sylvain, and Marco Attene. 2017. From 3D models to 3D prints: an overview of the processing pipeline. Computer Graphics Forum 36, 2 (2017), 537–564. Google ScholarCross Ref
26. Kui-Yip Lo, Chi-Wing Fu, and Hongwei Li. 2009. 3D Polyomino Puzzle. ACM Trans. Graphics 28, 5 (2009). Google ScholarDigital Library
27. Linjie Luo, Ilya Baran, Szymon Rusinkiewicz, and Wojciech Matusik. 2012. Chopper: Partitioning Models into 3D-Printable Parts. ACM Trans. Graphics 31, 6 (2012). Google ScholarDigital Library
28. Asla Medeiros e Sá, Karina Rodriguez Echavarria, Nico Pietroni, and Paolo Cignoni. 2016. State Of The Art on Functional Fabrication. In Eurographics Workshop on Graphics for Digital Fabrication (2016). Google ScholarDigital Library
29. Alessandro Muntoni, Marco Livesu, Riccardo Scateni, Alla Sheffer, and Daniele Panozzo. 2018. Axis-Aligned Height-Field Block Decomposition of 3D Shapes. ACM Trans. Graphics 37, 5 (2018). Google ScholarDigital Library
30. Kazutaka Nakashima, Thomas Auzinger, Emmanuel Iarussi, Ran Zhang, Takeo Igarashi, and Bernd Bickel. 2018. CoreCavity: Interactive Shell Decomposition for Fabrication with Two-piece Rigid Molds. ACM Trans. Graph. 37, 4 (2018), 135:1–135:13. Google ScholarDigital Library
31. J. Nocedal and S. Wright. 2000. Numerical Optimization. Springer New York.Google Scholar
32. Daniele Panozzo, Olga Diamanti, Sylvain Paris, Marco Tarini, Evgeni Sorkine, and Olga Sorkine-Hornung. 2015. Texture Mapping Real-World Objects with Hydrographics. Computer Graphics Forum 34, 5 (2015), 65–75.Google ScholarDigital Library
33. Tim Reiner, Nathan Carr, Radomír Měch, Ondřej Št’ava, Carsten Dachsbacher, and Gavin Miller. 2014. Dual-color mixing for fused deposition modeling printers. Computer Graphics Forum 33, 2 (2014), 479–486. Google ScholarDigital Library
34. Christian Schüller, Daniele Panozzo, Anselm Grundhöfer, Henning Zimmer, Evgeni Sorkine, and Olga Sorkine-Hornung. 2016. Computational thermoforming. ACM Trans. Graphics 35, 4 (2016), 43. Google ScholarDigital Library
35. Ariel Shamir. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6 (2008), 1539–1556.Google ScholarCross Ref
36. Nick Sharp and Keenan Crane. 2018. Variational Surface Cutting. ACM Trans, Graphics 37, 4 (2018). Google ScholarDigital Library
37. Hang Si. 2015. TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator. ACM Trans. Math. Softw. 41, 2, Article 11 (2015), 36 pages. Google ScholarDigital Library
38. Pitchaya Sitthi-Amorn, Javier E. Ramos, Yuwang Wangy, Joyce Kwan, Justin Lan, Wenshou Wang, and Wojciech Matusik. 2015. MultiFab: a machine vision assisted platform for multi-material 3D printing. ACM Trans. Graphics 34 (2015). Issue 4. Google ScholarDigital Library
39. Peng Song, Bailin Deng, Ziqi Wang, Zhichao Dong, Wei Li, Chi-Wing Fu, and Ligang Liu. 2016. CofiFab: coarse-to-fine fabrication of large 3D objects. ACM Trans. Graphics 35, 4 (2016), 45. Google ScholarDigital Library
40. Peng Song, Chi-Wing Fu, and Daniel Cohen-Or. 2012. Recursive interlocking puzzles. ACM Trans. Graphics 31, 6 (2012), 128. Google ScholarDigital Library
41. Peng Song, Zhongqi Fu, Ligang Liu, and Chi-Wing Fu. 2015. Printing 3D objects with interlocking parts. Computer Aided Geometric Design 35 (2015), 137–148. Google ScholarDigital Library
42. Olga Sorkine and Marc Alexa. 2007. As-Rigid-As-Possible Surface Modeling. In Proc. Symp. Geometry Processing. 109–116. Google ScholarDigital Library
43. Birgit Strodthoff and Bert Jüttler. 2017. Automatic decomposition of 3D solids into contractible pieces using Reeb graphs. Computer-Aided Design 90 (2017), 157–167.Google ScholarCross Ref
44. Robert W Sumner and Jovan Popović. 2004. Deformation Transfer for Triangle Meshes. In ACM Trans. Graphics, Vol. 23. ACM, 399–405. Google ScholarDigital Library
45. Juraj Vanek, JA Galicia, Bedrich Benes, R Mech, N Carr, Ondrej Stava, and GS Miller. 2014. PackMerger: A 3D print volume optimizer. Computer Graphics Forum 33, 6 (2014). Google ScholarDigital Library
46. Weiming M Wang, Cédric Zanni, and Leif Kobbelt. 2016. Improved surface quality in 3d printing by optimizing the printing direction. Computer Graphics Forum 35, 2 (2016), 59–70.Google ScholarCross Ref
47. Ziqi Wang, Peng Song, and Mark Pauly. 2018. DESIA: A General Framework for Designing Interlocking Assemblies. ACM Trans. Graph. 37, 6 (2018), 191:1–191:14. Google ScholarDigital Library
48. Jan D Wolter. 1991. On the automatic generation of assembly plans. In Computer-Aided Mechanical Assembly Planning. Springer, 263–288.Google Scholar
49. Shiqing Xin, Chi-Fu Lai, Chi-Wing Fu, Tien-Tsin Wong, Ying He, and Daniel Cohen-Or. 2011. Making burr puzzles from 3D models. ACM Trans. Graphics 30, 4 (2011), 97. Google ScholarDigital Library
50. Jiaxian Yao, Danny M Kaufman, Yotam Gingold, and Maneesh Agrawala. 2017. Interactive Design and Stability Analysis of Decorative Joinery for Furniture. ACM Trans. Graphics 36, 2 (2017), 20. Google ScholarDigital Library
51. Miaojun Yao, Zhili Chen, Linjie Luo, Rui Wang, and Huamin Wang. 2015. Level-set-based Partitioning and Packing Optimization of a Printable Model. ACM Trans. Graphics 34, 6 (2015). Google ScholarDigital Library
52. Yinan Zhang, Emily Whiting, and Devin Balkcom. 2016. Assembling and disassembling planar structures with divisible and atomic components. Algorithmic Foundations of Robotics (WAFR) PP, 99 (2016).Google Scholar
53. Yizhong Zhang, Chunji Yin, Changxi Zheng, and Kun Zhou. 2015. Computational Hydrographic Printing. ACM Trans. Graphics 34, 4 (2015). Google ScholarDigital Library
