“Connected fermat spirals for layered fabrication” by Zhao, Gu, Huang, Garcia, Chen, et al. …

  • ©Haisen Zhao, Fanglin Gu, Qi-xing Huang, Jorge A. Garcia, Yong Chen, Changhe Tu, Bedrich Benes, Hao Zhang, Daniel Cohen-Or, and Baoquan Chen



Session Title:



    Connected fermat spirals for layered fabrication




    We develop a new kind of “space-filling” curves, connected Fermat spirals, and show their compelling properties as a tool path fill pattern for layered fabrication. Unlike classical space-filling curves such as the Peano or Hilbert curves, which constantly wind and bind to preserve locality, connected Fermat spirals are formed mostly by long, low-curvature paths. This geometric property, along with continuity, influences the quality and efficiency of layered fabrication. Given a connected 2D region, we first decompose it into a set of sub-regions, each of which can be filled with a single continuous Fermat spiral. We show that it is always possible to start and end a Fermat spiral fill at approximately the same location on the outer boundary of the filled region. This special property allows the Fermat spiral fills to be joined systematically along a graph traversal of the decomposed sub-regions. The result is a globally continuous curve. We demonstrate that printing 2D layers following tool paths as connected Fermat spirals leads to efficient and quality fabrication, compared to conventional fill patterns.


    1. Arkina, E. M., Feketeb, S. P., and Mitchell, J. S. 2000. Approximation algorithms for lawn mowing and milling. Computational Geometry 17, 1-2, 25–50. Google ScholarDigital Library
    2. Chen, X., Zhang, H., Lin, J., Hu, R., Lu, L., Huang, Q., Benes, B., Cohen-Or, D., and Chen, B. 2015. Dapper: Decompose-and-pack for 3D Printing. ACM Trans. on Graph 34, 6, 213:1–213:12. Google ScholarDigital Library
    3. Dafner, R., Cohen-Or, D., and Matias, Y. 2000. Context-based Space Filling Curves. Computer Graphics Forum 19, 3, 209–218.Google ScholarCross Ref
    4. Ding, D., Pan, Z. S., Cuiuri, D., and Li, H. 2014. A tool-path generation strategy for wire and arc additive manufacturing. Int. J. of Adv. Manufact. Tech. 73, 1-4, 173–183.Google ScholarCross Ref
    5. Dinh, H. Q., Gelman, F., Lefebvre, S., and Claux, F. 2015. Modeling and Toolpath Generation for Consumer-level 3D Printing. In ACM SIGGRAPH Courses, 17:1–17:273. Google ScholarDigital Library
    6. Dwivedi, R., and Kovacevic, R. 2004. Automated torch path planning using polygon subdivision for solid freeform fabrication based on welding. J. of Manufact. Sys. 23, 4, 278–291.Google ScholarCross Ref
    7. El-Midany, T. T., Elkeran, A., and Tawfik, H. 1993. Tool path pattern comparison: contour-parallel with direction-parallel. In Geom. model. and imaging — new trends, 77–82. Google ScholarDigital Library
    8. Gibson, I., Rosen, D., and Stucker, B. 2015. Additive Manufacturing Technologies, 2nd ed. Springer.Google Scholar
    9. Held, M., and Spielberger, C. 2014. Improved spiral highspeed machining of multiply-connected pockets. Computer-Aided Design and Applications 11, 3, 346–357.Google ScholarCross Ref
    10. Hildebrand, K., Bickel, B., and Alexa, M. 2013. Orthogonal slicing for additive manufacturing. Computers & Graphics 37, 6, 669–675. Shape Model. Intl. (SMI) Conf. Google ScholarDigital Library
    11. Hu, R., Li, H., Zhang, H., and Cohen-Or, D. 2014. Approximate pyramidal shape decomposition. ACM Trans. on Graph 33, 6, 213:1–213:12. Google ScholarDigital Library
    12. Jin, G., Li, W., and Gao, L. 2013. An adaptive process planning approach of rapid prototyping and manufacturing. Robotics and Computer-Integrated Manufacturing 29, 1, 23–38. Google ScholarDigital Library
    13. Jin, Y. A., He, Y., Fu, J. Z., Gan, W. F., and Lin, Z. W. 2014. Optimization of tool-path generation for material extrusion-based additive manufacturing technology. Additive Manufacturing 1, 4, 32–47.Google ScholarCross Ref
    14. Johnson, A., 2015. Clipper – an open source freeware library for clipping and offsetting lines and polygons. http://www.angusj.com/delphi/clipper.php.Google Scholar
    15. Kulkarni, P., Marsan, A., and Dutta, D. 2000. A review of process planning techniques in layered manufacturing. Rapid Prototyping Journal 6, 18–35.Google ScholarCross Ref
    16. Lu, L., Sharf, A., Zhao, H., Wei, Y., Fan, Q., Chen, X., Savoye, Y., Tu, C., Cohen-Or, D., and Chen, B. 2014. Build-to-last: Strength to weight 3D printed objects. ACM Trans. on Graph 33, 4, 97:1–97:10. Google ScholarDigital Library
    17. Luo, L., Baran, I., Rusinkiewicz, S., and Matusik, W. 2012. Chopper: Partitioning models into 3D-printable parts. ACM Trans. on Graph 31, 6, 129:1–129:9. Google ScholarDigital Library
    18. Pedersen, H., and Singh, K. 2006. Organic labyrinths and mazes. In Proc. of Non-photorealistic Animation and Rendering (NPAR), 79–86. Google ScholarDigital Library
    19. Pottmann, H., Wallner, J., Huang, Q.-X., and Yang, Y.-L. 2009. Integral invariants for robust geometry processing. Comp. Aided Geom. Design 26, 1, 37–60. Google ScholarDigital Library
    20. Prévost, R., Whiting, E., Lefebvre, S., and Sorkine-Hornung, O. 2013. Make It Stand: Balancing shapes for 3D fabrication. ACM Trans. on Graph 32, 4, 81:1–81:10. Google ScholarDigital Library
    21. Ren, F., Sun, Y., and Guo, D. 2009. Combined reparameterization-based spiral toolpath generation for five-axis sculptured surface machining. Int. J. of Adv. Manufac. Tech. 40, 7, 760–768.Google ScholarCross Ref
    22. Slic3r, 2016. Slic3r. http://slic3r.org/.Google Scholar
    23. Stava, O., Vanek, J., Benes, B., Carr, N., and Měch, R. 2012. Stress relief: improving structural strength of 3D printable objects. ACM Trans. on Graph 31, 4, 48:1–48:11. Google ScholarDigital Library
    24. Vanek, J., Garcia, J., Benes, B., Mech, R., Carr, N., Stava, O., and Miller, G. 2014. PackMerger: A 3D print volume optimizer. Computer Graphics Forum 33, 6, 322–332.Google ScholarDigital Library
    25. Vanek, J., Galicia, J. A. G., and Benes, B. 2014. Clever support: Efficient support structure generation for digital fabrication. Computer Graphics Forum 33, 5, 117–125.Google ScholarDigital Library
    26. Wang, L., and Cao, J. 2012. A look-ahead and adaptive speed control algorithm for high-speed CNC equipment. Int. J. of Adv. Manufact. Techn. 63, 705–717.Google ScholarCross Ref
    27. Wang, L., Cao, J. F., and Li, Y. Q. 2010. Speed optimization control method of smooth motion for high-speed CNC machine tools. Int. J. of Adv. Manufact. Tech. 49, 313–325.Google ScholarCross Ref
    28. Wasser, T., Jayal, A. D., and Pistor, C. 1999. Implementation and evaluation of novel buildstyles in fused deposition modeling. Strain 5, 6, 95–102.Google Scholar
    29. Wikipedia, 2015. Fermat’s spiral — wikipedia, the free encyclopedia. {Online; accessed 28-November-2015}.Google Scholar
    30. Wikipedia, 2016. Labyrinth — wikipedia, the free encyclopedia. {Online; accessed 10-April-2016}.Google Scholar
    31. Yang, Y., Loh, H., Fuh, J., and Wang, Y. 2002. Equidistant path generation for improving scanning efficiency in layered manufacturing. Rapid Prototyping Journal 8, 1, 30–37.Google ScholarCross Ref
    32. Yao, M., Chen, Z., Luo, L., Wang, R., and Wang, H. 2015. Level-set-based partitioning and packing optimization of a printable model. ACM Trans. on Graph 34, 6, 214:1–214:11. Google ScholarDigital Library
    33. Zhang, X., Le, X., Panotopoulou, A., Whiting, E., and Wang, C. C. L. 2015. Perceptual Models of Preference in 3D Printing Direction. ACM Trans. Graph. 34, 6, 215:1–215:12. Google ScholarDigital Library

ACM Digital Library Publication: