“Optimal Discrete Slicing” by Alexa, Hildebrand and Lefebvre

  • ©Marc Alexa, Kristian Hildebrand, and Sylvain Lefebvre




    Optimal Discrete Slicing

Session/Category Title: Fabricating Curves, Surfaces & Volumes



    Slicing is the procedure necessary to prepare a shape for layered manufacturing. There are degrees of freedom in this process, such as the starting point of the slicing sequence and the thickness of each slice. The choice of these parameters influences the manufacturing process and its result: The number of slices significantly affects the time needed for manufacturing, while their thickness affects the error. Assuming a discrete setting, we measure the error as the number of voxels that are incorrectly assigned due to slicing. We provide an algorithm that generates, for a given set of available slice heights and a shape, a slicing that is provably optimal. By optimal, we mean that the algorithm generates sequences with minimal error for any possible number of slices. The algorithm is fast and flexible, that is, it can accommodate a user driven importance modulation of the error function and allows the interactive exploration of the desired quality/time tradeoff. We demonstrate the practical importance of our optimization on several three-dimensional-printed results.


    1. Nina Amenta and Marshall Bern. 1999. Surface reconstruction by voronoi filtering. Discr. Comput. Geom. 22, 4 (1999), 481–504. DOI:http://dx.doi.org/10.1007/PL00009475 Google ScholarCross Ref
    2. Moritz Bächer, Bernd Bickel, Doug L. James, and Hanspeter Pfister. 2012. Fabricating articulated characters from skinned meshes. ACM Trans. Graph. 31, 4, Article 47 (July 2012), 9 pages. DOI:http://dx.doi.org/10.1145/2185520.2185543 Google ScholarDigital Library
    3. Bernd Bickel, Moritz Bächer, Miguel A. Otaduy, Hyunho Richard Lee, Hanspeter Pfister, Markus Gross, and Wojciech Matusik. 2010. Design and fabrication of materials with desired deformation behavior. ACM Trans. Graph. 29, 4, Article 63 (July 2010), 10 pages. DOI:http://dx.doi.org/10.1145/1778765.1778800 Google ScholarDigital Library
    4. Alan Brunton, Can Ates Arikan, and Philipp Urban. 2015. Pushing the limits of 3D color printing: Error diffusion with translucent materials. ACM Trans. Graph. 35, 1, Article 4 (Dec. 2015). DOI:http://dx.doi.org/10.1145/2832905 Google ScholarDigital Library
    5. Xuelin Chen, Hao Zhang, Jinjie Lin, Ruizhen Hu, Lin Lu, Qixing Huang, Bedrich Benes, Daniel Cohen-Or, and Baoquan Chen. 2015. Dapper: Decompose-and-pack for 3D printing. ACM Trans. Graph. 34, 6, Article 213 (Oct. 2015). DOI:http://dx.doi.org/10.1145/2816795.2818087 Google ScholarDigital Library
    6. W. Cheng, J. Y. H. Fuh, A. Y. C. Nee, Y. S. Wong, H. T. Loh, and T. Miyazawa. 1995. Multiobjective optimization of part building orientation in stereolithography. Rapid Prototyp. J. 1, 4 (1995), 12–23. DOI:http://dx.doi.org/10.1108/13552549510104429 Google ScholarCross Ref
    7. Denis Cormier, Kittinan Unnanon, and Ezat Sanii. 2000. Specifying nonuniform cusp heights as a potential aid for adaptive slicing. Rapid Prototyp. J. 6, 3 (2000), 204–212. DOI:http://dx.doi.org/10.1108/13552540010337074 Google ScholarCross Ref
    8. Stelian Coros, Bernhard Thomaszewski, Gioacchino Noris, Shinjiro Sueda, Moira Forberg, Robert W. Sumner, Wojciech Matusik, and Bernd Bickel. 2013. Computational design of mechanical characters. ACM Trans. Graph. 32, 4, Article 83 (July 2013). DOI:http://dx.doi.org/10.1145/2461912.2461953 Google ScholarDigital Library
    9. Stéphane Danjou and Peter Köhler. 2009. Determination of optimal build direction for different rapid prototyping applications. In Proceedings of the 14th European Forum on Rapid Prototyping, Alain Bernard (Ed.). Ecole Centrale Paris.Google Scholar
    10. André Dolenc and Ismo Mäkelä. 1994. Slicing procedures for layered manufacturing techniques. Comput.-Aid. Des. 26, 2 (1994), 119–126. Google ScholarCross Ref
    11. Jérémie Dumas, Jean Hergel, and Sylvain Lefebvre. 2014. Bridging the gap: Automated steady scaffoldings for 3D printing. ACM Trans. Graph. 33, 4, Article 98 (July 2014). DOI:http://dx.doi.org/10.1145/2601097.2601153 Google ScholarDigital Library
    12. Herbert Federer. 1959. Curvature measures. Trans. Am. Math. Soc. 93, 3 (1959), 418–491. Google ScholarCross Ref
    13. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY.Google Scholar
    14. Mohammad T. Hayasi and Bahram Asiabanpour. 2013. A new adaptive slicing approach for the fully dense freeform fabrication (FDFF) process. J. Intell. Manufact. 24, 4 (2013), 683–694. Google ScholarDigital Library
    15. Jean Hergel and Sylvain Lefebvre. 2014. Clean color: Improving multi-filament 3D prints. Comput. Graph. Forum 33, 2 (2014), 469–478. DOI:http://dx.doi.org/10.1111/cgf.12318 Google ScholarDigital Library
    16. Kristian Hildebrand, Bernd Bickel, and Marc Alexa. 2013. Orthogonal slicing for additive manufacturing. Comput. Graph. 37, 6 (2013), 669–675. DOI:http://dx.doi.org/10.1016/j.cag.2013.05.011 Google ScholarDigital Library
    17. R. L. Hope, R. N. Roth, and P. A. Jacobs. 1997. Adaptive slicing with sloping layer surfaces. Rapid Prototyp. J. 3, 3 (1997), 89–98. DOI:http://dx.doi. org/10.1108/13552549710185662 Google ScholarCross Ref
    18. Ruizhen Hu, Honghua Li, Hao Zhang, and Daniel Cohen-Or. 2014. Approximate pyramidal shape decomposition. ACM Trans. Graph. 33, 6, Article 213 (Nov. 2014). DOI:http://dx.doi.org/10.1145/2661229.2661244 Google ScholarDigital Library
    19. Pu Huang, Charlie C. L. Wang, and Yong Chen. 2013. Intersection-free and topologically faithful slicing of implicit solid. J. Comput. Inf. Sci. Eng. 13, 2 (2013), 021009. DOI:http://dx.doi.org/10.1115/1.4024067 Google ScholarCross Ref
    20. Hiroshi Konno and Takahito Kuno. 1988. Best piecewise constant approximation of a function of single variable. Operat. Res. Lett. 7, 4 (1988), 205–210. DOI:http://dx.doi.org/10.1016/0167-6377(88)90030-2 Google ScholarDigital Library
    21. Bongjin Koo, Wilmot Li, JiaXian Yao, Maneesh Agrawala, and Niloy J. Mitra. 2014. Creating works-like prototypes of mechanical objects. ACM Trans. Graph. 33, 6, Article 217 (Nov. 2014). DOI:http://dx.doi.org/10.1145/2661229.2661289 Google ScholarDigital Library
    22. Prashant Kulkarni and Debasish Dutta. 1996. An accurate slicing procedure for layered manufacturing. Comput.-Aid. Des. 28, 9 (1996), 683–697. Google ScholarCross Ref
    23. Chang Ha Lee, Amitabh Varshney, and David W. Jacobs. 2005. Mesh saliency. ACM Trans. Graph. 24, 3 (July 2005), 659–666. DOI:http://dx.doi.org/10.1145/1073204.1073244 Google ScholarDigital Library
    24. Sylvain Lefebvre. 2013. IceSL: A GPU accelerated CSG modeler and slicer. In 18th European Forum on Additive Manufacturing (AEFA’13).Google Scholar
    25. Linjie Luo, Ilya Baran, Szymon Rusinkiewicz, and Wojciech Matusik. 2012. Chopper: Partitioning models into 3D-printable parts. ACM Trans. Graph. 31, 6, Article 129 (Nov. 2012). DOI:http://dx.doi.org/10.1145/2366145.2366148 Google ScholarDigital Library
    26. K Mani, P Kulkarni, and D Dutta. 1999. Region-based adaptive slicing. Comput.-Aid. Des. 31, 5 (1999), 317–333. DOI:http://dx.doi.org/10.1016/S0010-4485(99)00033-0 Google ScholarCross Ref
    27. H. S. Masood, W. Rattanawong, and P. Iovenitti. 2000. Part build orientations based on volumetric error in fused deposition modelling. Int. J. Adv. Manuf. Technol. 16, 3 (2000), 162–168. DOI:http://dx.doi.org/10.1007/s001700050022 Google ScholarCross Ref
    28. PM Pandey, N Venkata Reddy, and SG Dhande. 2003a. Real time adaptive slicing for fused deposition modelling. Int. J. Mach. Tools Manuf. 43, 1 (2003), 61–71. Google ScholarCross Ref
    29. Pulak Mohan Pandey, N Venkata Reddy, and Sanjay G Dhande. 2003b. Slicing procedures in layered manufacturing: A review. Rapid Prototyp. J. 9, 5 (2003), 274–288. Google ScholarCross Ref
    30. Tim Reiner, Nathan Carr, Radomir Mech, Ondrej Stava, Carsten Dachsbacher, and Gavin Miller. 2014. Dual-color mixing for fused deposition modeling printers. Comput. Graph. Forum 33, 2 (2014), 479–486. DOI:http://dx.doi.org/10.1111/cgf.12319 Google ScholarDigital Library
    31. Emmanuel Sabourin, Scott A Houser, and Jan Helge Bøhn. 1996. Adaptive slicing using stepwise uniform refinement. Rapid Prototyp. J. 2, 4 (1996), 20–26. Google ScholarCross Ref
    32. Emmanuel Sabourin, Scott A. Houser, and Jan Helge Bøhn. 1997. Accurate exterior, fast interior layered manufacturing. Rapid Prototyp. J. 3, 2 (1997), 44–52. DOI:http://dx.doi.org/10.1108/13552549710176662 Google ScholarCross Ref
    33. Ryan Schmidt and Nobuyuki Umetani. 2014. Branching support structures for 3D printing. In ACM SIGGRAPH 2014 Studio (SIGGRAPH’14). ACM, New York, NY, Article 9. DOI:http://dx.doi.org/10.1145/2619195.2656293 Google ScholarDigital Library
    34. Yuliy Schwartzburg, Romain Testuz, Andrea Tagliasacchi, and Mark Pauly. 2014. High-contrast computational caustic design. ACM Trans. Graph. 33, 4, Article 74 (Jul. 2014). DOI:http://dx.doi.org/10.1145/2601097.2601200 Google ScholarDigital Library
    35. S. K. Singhal, Prashant K Jain, and Pulak M Pandey. 2008. Adaptive slicing for SLS prototyping. Comput.-Aid. Des. Appl. 5, 1-4 (2008), 412–423.Google Scholar
    36. Mélina Skouras, Bernhard Thomaszewski, Stelian Coros, Bernd Bickel, and Markus Gross. 2013. Computational design of actuated deformable characters. ACM Trans. Graph. 32, 4 (Jul. 2013), 82:1–82:10. DOI:http://dx.doi.org/10.1145/2461912.2461979 Google ScholarDigital Library
    37. 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. Graph. 35, 4, Article 45 (July 2016). DOI:http://dx.doi.org/10.1145/2897824.2925876 Google ScholarDigital Library
    38. Kamesh Tata, Georges Fadel, Amit Bagchi, and Nadim Aziz. 1998. Efficient slicing for layered manufacturing. Rapid Prototyp. J. 4, 4 (1998), 151–167. Google ScholarCross Ref
    39. K. Thrimurthulu, Pulak M. Pandey, and N. Venkata Reddy. 2004. Optimum part deposition orientation in fused deposition modeling. Int. J. Mach. Tools Manuf. 44, 6 (2004), 585–594. Google ScholarCross Ref
    40. Justin Tyberg and Jan Helge Bøhn. 1998. Local adaptive slicing. Rapid Prototyp. J. 4, 3 (1998), 118–127. Google ScholarCross Ref
    41. Justin Tyberg and Jan Helge Bøhn. 1999. FDM systems and local adaptive slicing. Mater. Des. 20, 2 (1999), 77–82. Google ScholarCross Ref
    42. Nobuyuki Umetani and Ryan Schmidt. 2013. Cross-sectional structural analysis for 3D printing optimization. In SIGGRAPH Asia 2013 Technical Briefs (SA’13). Article 5. DOI:http://dx.doi.org/10.1145/2542355.2542361 Google ScholarDigital Library
    43. 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 (Jul. 2013), 136:1–136:12. DOI:http://dx.doi.org/10.1145/2461912.2461993 Google ScholarDigital Library
    44. Weiming Wang, Haiyuan Chao, Jing Tong, Zhouwang Yang, Xin Tong, Hang Li, Xiuping Liu, and Ligang Liu. 2015. Saliency-preserving slicing optimization for effective 3D printing. Comput. Graph. Forum 34, 6 (2015), 148–160. DOI:http://dx.doi.org/10.1111/cgf.12527 Google ScholarDigital Library
    45. W. M. Wang, C. Zanni, and L. Kobbelt. 2016. Improved surface quality in 3D printing by optimizing the printing direction. Comput. Graph. Forum 35, 2 (2016), 59–70. DOI:http://dx.doi.org/10.1111/cgf.12811 Google ScholarDigital Library
    46. F Xu, Y. S Wong, H. T. Loh, J. Y. H. Fuh, and T. Miyazawa. 1997. Optimal orientation with variable slicing in stereolithography. Rapid Prototyp. J. 3, 3 (1997), 76–88. Google ScholarCross Ref
    47. Xiaoting Zhang, Xinyi Le, Athina Panotopoulou, Emily Whiting, and Charlie C. L. Wang. 2015. Perceptual models of preference in 3D printing direction. ACM Trans. Graph. 34, 6, Article 215 (Oct. 2015). DOI:http://dx.doi.org/10.1145/2816795.2818121 Google ScholarDigital Library
    48. Zhiwen Zhao and Zhiwen Luc. 2000. Adaptive direct slicing of the solid model for rapid prototyping. International J. Prod. Res. 38, 1 (2000), 69–83. DOI:http://dx.doi.org/10.1080/002075400189581 Google ScholarCross Ref

ACM Digital Library Publication:

Overview Page: