“Polyhedral voronoi diagrams for additive manufacturing” by Martínez, Hornus, Song and Lefebvre

  • ©Jonàs Martínez, Samuel Hornus, Haichuan Song, and Sylvain Lefebvre



Entry Number: 129

Session Title:

    Textiles & Microstructures


    Polyhedral voronoi diagrams for additive manufacturing




    A critical advantage of additive manufacturing is its ability to fabricate complex small-scale structures. These microstructures can be understood as a metamaterial: they exist at a much smaller scale than the volume they fill, and are collectively responsible for an average elastic behavior different from that of the base printing material making the fabricated object lighter and/or flexible along specific directions. In addition, the average behavior can be graded spatially by progressively modifying the micro structure geometry.The definition of a microstructure is a careful trade-off between the geometric requirements of manufacturing and the properties one seeks to obtain within a shape: in our case a wide range of elastic behaviors. Most existing microstructures are designed for stereolithography (SLA) and laser sintering (SLS) processes. The requirements are however different than those of continuous deposition systems such as fused filament fabrication (FFF), for which there is currently a lack of microstructures enabling graded elastic behaviors.In this work we introduce a novel type of microstructures that strictly enforce all the requirements of FFF-like processes: continuity, self-support and overhang angles. They offer a range of orthotropic elastic responses that can be graded spatially. This allows to fabricate parts usually reserved to the most advanced technologies on widely available inexpensive printers that also benefit from a continuously expanding range of materials.


    1. Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec. 1995. Voronoi Diagrams in Higher Dimensions Under Certain Polyhedral Distance Functions. In Proceedings of the Eleventh Annual Symposium on Computational Geometry. 79–88. Google ScholarDigital Library
    2. Guylaine Boittin, Daniela Garajeu, Alice Labé, Hervé Moulinec, Fabrice Silva, and Pierre Suquet. 2014. CraFT. http://craft.lma.cnrs-mrs.fr/Google Scholar
    3. Guylaine Boittin, Pierre-Guy Vincent, Hervé Moulinec, and Mihai Gărăjeu. 2017. Numerical simulations and modeling of the effective plastic flow surface of a bi-porous material with pressurized intergranular voids. Computer Methods in Applied Mechanics and Engineering 323, Supplement C (2017), 174 — 201.Google ScholarCross Ref
    4. L. Paul Chew and Robert L. (Scot) Dyrsdale, III. 1985. Voronoi Diagrams Based on Convex Distance Functions. In Proceedings of the First Annual Symposium on Computational Geometry. 235–244. Google ScholarDigital Library
    5. A.G. Corbalan, M. Mazon, and T. Recio. 1996. Geometry of bisectors for strictly convex distances. International Journal of Computational Geometry & Applications 06, 01 (1996), 45–58.Google ScholarCross Ref
    6. Lorna J Gibson and Michael F Ashby. 1999. Cellular solids: structure and properties. Cambridge university press.Google Scholar
    7. Richard Hill. 1952. The elastic behaviour of a crystalline aggregate. Proceedings of the Physical Society Section A 65, 5 (1952), 349.Google ScholarCross Ref
    8. Samuel Hornus, Sylvain Lefebvre, Jérémie Dumas, and Frédéric Claux. 2016. Tight Printable Enclosures and Support Structures for Additive Manufacturing. In Proceedings of the Eurographics Workshop on Graphics for Digital Fabrication (GraDiFab ’16). 11–21. Google ScholarDigital Library
    9. Christian Icking and Lihong Ha. 2001. A Tight Bound for the Complexity of Voronoi Diagrams Under Polyhedral Convex Distance Functions in 3D. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing. 316–321. Google ScholarDigital Library
    10. Christian Icking, Rolf Klein, Ngoc-Minh Lé, and Lihong Ma. 1995. Convex distance functions in 3-space are different. Fundamenta Informaticae 22, 4 (1995), 331–352. Google ScholarDigital Library
    11. Christian Icking, Rolf Klein, Lihong Ma, Stefan Nickel, and Ansgar Weißler. 2001. On bisectors for different distance functions. Discrete Applied Mathematics 109, 1 (2001), 139–161. Google ScholarDigital Library
    12. Alexandra Ion, Johannes Frohnhofen, Ludwig Wall, Robert Kovacs, Mirela Alistar, Jack Lindsay, Pedro Lopes, Hsiang-Ting Chen, and Patrick Baudisch. 2016. Metamaterial Mechanisms. In Proceedings of the 29th Annual Symposium on User Interface Software and Technology (UIST ’16). 529–539. Google ScholarDigital Library
    13. Rolf Klein and Derick Wood. 1988. Voronoi diagrams based on general metrics in the plane. Springer Berlin Heidelberg, 281–291. Google ScholarDigital Library
    14. M. Leary, M. Babaee, M. Brandt, and A. Subic. 2013. Feasible Build Orientations for Self-Supporting Fused Deposition Manufacture: A Novel Approach to Space-Filling Tesselated Geometries. Advanced Materials Research 633 (2013), 148–168.Google ScholarCross Ref
    15. Jusung Lee and Kunwoo Lee. 2017. Block-based inner support structure generation algorithm for 3D printing using fused deposition modeling. The International Journal of Advanced Manufacturing Technology 89, 5 (2017), 2151–2163.Google ScholarCross Ref
    16. Mokwon Lee, Qing Fang, Joonghyun Ryu, Ligang Liu, and Deok-Soo Kim. 2018. Support-Free Hollowing for 3D Printing via Voronoi Diagram of Ellipses. Computer-Aided Design 101 (2018), 23–36. https://arxiv.org/abs/1708.06577Google ScholarCross Ref
    17. Sylvain Lefebvre. 2015. 3D infilling: faster, stronger, simpler, http://sylefeb.blogspot.fr/2015/07/3dprint-3d-infilling-faster-stronger.html.Google Scholar
    18. Xingchen Liu and Vadim Shapiro. 2016. Homogenization of material properties in additively manufactured structures. Computer-Aided Design 78, Supplement C (2016), 71–82. Google ScholarDigital Library
    19. Marco Livesu, Stefano Ellero, Jonas Martínez, Sylvain Lefebvre, and Marco Attene. 2017. From 3D Models to 3D Prints: An Overview of the Processing Pipeline. Computer Graphics Forum 36 (2017), 537–564. Google ScholarCross Ref
    20. Lin Lu, Andrei Sharf, Haisen Zhao, Yuan Wei, Qingnan Fan, Xuelin Chen, Yann Savoye, Changhe Tu, Daniel Cohen-Or, and Baoquan Chen. 2014. Build-to-last: Strength to Weight 3D Printed Objects. ACM Trans. Graph. 33, 4, Article 97 (July 2014), 10 pages. Google ScholarDigital Library
    21. Mathias H. Luxner, Juergen Stampfl, and Heinz E. Pettermann. 2007. Numerical simulations of 3D open cell structures – influence of structural irregularities on elasto-plasticity and deformation localization. International Journal of Solids and Structures 44, 9 (2007), 2990 — 3003.Google ScholarCross Ref
    22. Lihong Ma. 2000. Bisectors and Voronoi diagrams for convex distance functions. Ph.D. Dissertation. Fernuniversität, Fachbereich Informatik.Google Scholar
    23. Jonàs Martínez, Jérémie Dumas, and Sylvain Lefebvre. 2016. Procedural Voronoi Foams for Additive Manufacturing. ACM Trans. Graph. 35, 4 (2016), 44:1–44:12. Google ScholarDigital Library
    24. Jonàs Martínez, Haichuan Song, Jérémie Dumas, and Sylvain Lefebvre. 2017. Orthotropic k-nearest foams for additive manufacturing. ACM Transactions on Graphics 36, 4 (July 2017), 121:1–121:12. Google ScholarDigital Library
    25. H. Martini and K.J. Swanepoel. 2004. The geometry of Minkowski spaces – A survey. Part II. Expositiones Mathematicae 22, 2 (2004), 93 — 144.Google Scholar
    26. Sara McMains, Jordan Smith, Jianlin Wang, and Carlo Sequin. 2000. Layered Manufacturing of Thin-Walled Parts. In ASME Design Engineering Technical Conference, Baltimore, Maryland. arXiv:http://www.cs.berkeley.edu/ sequin/PAPERS/ASMEdetc00.pdfGoogle Scholar
    27. Asla Medeiros e Sá, Vinícius Moreira Mello, Karina Rodriguez Echavarria, and Derek Covill. 2015. Adaptive voids. The Visual Computer 31, 6 (2015), 799–808. Google ScholarDigital Library
    28. Maher Moakher and Andrew N. Norris. 2006. The Closest Elastic Tensor of Arbitrary Symmetry to an Elasticity Tensor of Lower Symmetry. Journal of Elasticity 85, 3 (2006), 215–263.Google ScholarCross Ref
    29. H. Moulinec and P. Suquet. 1998. A numerical method for computing the overall response of nonlinear composites with complex micro structure. Computer Methods in Applied Mechanics and Engineering 157, 1 (1998), 69–94.Google ScholarCross Ref
    30. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, and Sung Nok Chiu. 2009. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons.Google ScholarDigital Library
    31. Julian Panetta, Abtin Rahimian, and Denis Zorin. 2017. Worst-case Stress Relief for Micro structures. ACM Transactions on Graphics 36, 4 (2017), 122:1–122:16. Google ScholarDigital Library
    32. Julian Panetta, Qingnan Zhou, Luigi Malomo, Nico Pietroni, Paolo Cignoni, and Denis Zorin. 2015. Elastic Textures for Additive Fabrication. ACM Trans. Graph. 34, 4 (2015), 135:1–135:12. Google ScholarDigital Library
    33. Alexander Pasko, Oleg Fryazinov, Turlif Vilbrandt, Pierre-Alain Fayolle, and Valery Adzhiev. 2011. Procedural function-based modelling of volumetric microstructures. Graphical Models 73, 5 (2011), 165–181. Google ScholarDigital Library
    34. A.P. Roberts and E.J. Garboczi. 2002. Elastic properties of model random three-dimensional open-cell solids. J. Mech. Phy. Solids 50, 1 (2002), 33 — 55.Google ScholarCross Ref
    35. Christian Schumacher, Bernd Bickel, Jan Rys, Steve Marschner, Chiara Daraio, and Markus Gross. 2015. Microstructures to Control Elasticity in 3D Printing. ACM Trans. Graph. 34, 4 (2015), 136:1–136:13. Google ScholarDigital Library
    36. Ole Sigmund, Niels Aage, and Erik Andreassen. 2016. On the (non-)optimality of Michell structures. Structural and Multidisciplinary Optimization 54, 2 (2016), 361–373. Google ScholarDigital Library
    37. TCT Ting and Tungyang Chen. 2005. Poisson’s ratio for anisotropic elastic materials can have no bounds. Quart. J. Mech. Appl. Math. 58, 1 (2005), 73–82.Google ScholarCross Ref
    38. Kiril Vidimče, Szu-Po Wang, Jonathan Ragan-Kelley, and Wojciech Matusik. 2013. OpenFab: A Programmable Pipeline for Multi-material Fabrication. ACM Trans. Graph. 32, 4 (2013), 136:1–136:12. Google ScholarDigital Library
    39. W. Wang, Y. J. Liu, J. Wu, S. Tian, C. C. L. Wang, L. Liu, and X. Liu. 2017. Support-Free Hollowing. IEEE Transactions on Visualization and Computer Graphics (2017).Google Scholar
    40. Jun Wu, Charlie C.L. Wang, Xiaoting Zhang, and Rüdiger Westermann. 2016. Self-supporting rhombic infill structures for additive manufacturing. Computer-Aided Design 80 (2016), 32–42.Google ScholarCross Ref
    41. Yue Xie and Xiang Chen. 2017. Support-free interior carving for 3D printing. Visual Informatics 1, 1 (2017), 9–15.Google ScholarCross Ref
    42. Qingnan Zhou. 2015. A study in fabricating microstructures. https://medium.com/3d-printing-stories/a-study-in-fabricating-microstructures-part-1-f267d298326e.Google Scholar
    43. Bo Zhu, Mélina Skouras, Desai Chen, and Wojciech Matusik. 2017. Two-Scale Topology Optimization with Microstructures. ACM Trans. Graph. 36, 5, Article 164 (July 2017), 16 pages. Google ScholarDigital Library

ACM Digital Library Publication: