“Surface2Volume: surface segmentation conforming assemblable volumetric partition” by Araújo, Cabiddu, Attene, Livesu, Vining, et al. …

  • ©Chrystiano Araújo, Daniela Cabiddu, Marco Attene, Marco Livesu, Nicholas Vining, and Alla Sheffer




    Surface2Volume: surface segmentation conforming assemblable volumetric partition

Session/Category Title: Fabrication



    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.


    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

ACM Digital Library Publication:

Overview Page: