research-article

Connected fermat spirals for layered fabrication

Authors:

Daniel Cohen-Or,

Baoquan ChenAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 35, Issue 4

Article No.: 100, Pages 1 - 10

https://doi.org/10.1145/2897824.2925958

Published: 11 July 2016 Publication History

Abstract

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.

Supplementary Material

ZIP File (a100-zhao-aux.zip)

Supplemental files.

Download
62.68 MB

ZIP File (a100-zhao-supp.zip)

Supplemental files.

Download
5.93 MB

MP4 File (a100.mp4)

Download
342.40 MB

References

[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.

Digital 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.

Digital Library

[3]

Dafner, R., Cohen-Or, D., and Matias, Y. 2000. Context-based Space Filling Curves. Computer Graphics Forum 19, 3, 209--218.

[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.

[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.

Digital 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.

[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.

Digital Library

[8]

Gibson, I., Rosen, D., and Stucker, B. 2015. Additive Manufacturing Technologies, 2nd ed. Springer.

[9]

Held, M., and Spielberger, C. 2014. Improved spiral highspeed machining of multiply-connected pockets. Computer-Aided Design and Applications 11, 3, 346--357.

[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.

Digital 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.

Digital 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.

Digital 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.

[14]

Johnson, A., 2015. Clipper - an open source freeware library for clipping and offsetting lines and polygons. http://www.angusj.com/delphi/clipper.php.

[15]

Kulkarni, P., Marsan, A., and Dutta, D. 2000. A review of process planning techniques in layered manufacturing. Rapid Prototyping Journal 6, 18--35.

[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.

Digital 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.

Digital Library

[18]

Pedersen, H., and Singh, K. 2006. Organic labyrinths and mazes. In Proc. of Non-photorealistic Animation and Rendering (NPAR), 79--86.

Digital 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.

Digital 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.

Digital 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.

[22]

Slic3r, 2016. Slic3r. http://slic3r.org/.

[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.

Digital 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.

Digital 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.

Digital 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.

[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.

[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.

[29]

Wikipedia, 2015. Fermat's spiral --- wikipedia, the free encyclopedia. {Online; accessed 28-November-2015}.

[30]

Wikipedia, 2016. Labyrinth --- wikipedia, the free encyclopedia. {Online; accessed 10-April-2016}.

[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.

[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.

Digital 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.

Digital Library

Cited By

Huang YGuo YSu RHan XDing JZhang TLiu TWang WFang GSong XWhiting EWang C(2024)Learning Based Toolpath Planner on Diverse Graphs for 3D PrintingACM Transactions on Graphics10.1145/368793343:6(1-16)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687933
Noma YSellán SSharp NSingh KJacobson A(2024)Surface-Filling Curve Flows via Implicit Medial AxesACM Transactions on Graphics10.1145/365815843:4(1-12)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658158
Gould JFriedman-Gerlicz CBuechley L(2024)TRAvel Slicer: Continuous Extrusion Toolpaths for 3D PrintingProceedings of the 37th Annual ACM Symposium on User Interface Software and Technology10.1145/3654777.3676349(1-17)Online publication date: 13-Oct-2024
https://dl.acm.org/doi/10.1145/3654777.3676349
Show More Cited By

Index Terms

Connected fermat spirals for layered fabrication
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models
      2. Shape analysis

Recommendations

Euler Bézier spirals and Euler B-spline spirals
Abstract
Euler spirals have linear varying curvature with respect to arc length and can be applied in fields such as aesthetics pleasing shape design, curve completion or highway design, etc. However, evaluation and interpolation of Euler spirals to ...
Highlights
- A class of Bézier curves and B-spline curves are defined by discrete Euler spiral-like control polygons.
- The defined curves are called Euler Bézier spirals and Euler B-spline spirals when the curvature plots are monotone.
- Euler ...
Approximating Cornu spirals by arc splines

While modeling planar parametric curves, it is desirable to approximate them efficiently by arc splines with fewest segments within the prescribed tolerance. Planar arc splines are ideal for describing the path of a numerically controlled cutting ...
Rational cubic spirals

We consider the problem of finding parametric rational Bezier cubic spirals (planar curves of monotonic curvature) that interpolate end conditions consisting of positions, tangents and curvatures. Rational cubics give more design flexibility than ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 35, Issue 4

July 2016

1396 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2897824

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2016

Published in TOG Volume 35, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
2,027
Total Downloads

Downloads (Last 12 months)221
Downloads (Last 6 weeks)23

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang YGuo YSu RHan XDing JZhang TLiu TWang WFang GSong XWhiting EWang C(2024)Learning Based Toolpath Planner on Diverse Graphs for 3D PrintingACM Transactions on Graphics10.1145/368793343:6(1-16)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687933
Noma YSellán SSharp NSingh KJacobson A(2024)Surface-Filling Curve Flows via Implicit Medial AxesACM Transactions on Graphics10.1145/365815843:4(1-12)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658158
Gould JFriedman-Gerlicz CBuechley L(2024)TRAvel Slicer: Continuous Extrusion Toolpaths for 3D PrintingProceedings of the 37th Annual ACM Symposium on User Interface Software and Technology10.1145/3654777.3676349(1-17)Online publication date: 13-Oct-2024
https://dl.acm.org/doi/10.1145/3654777.3676349
Buechley LGould JBell F(2024)CeraMetal: A New Approach to Low-Cost Metal 3D Printing with Bronze ClayProceedings of the 2024 CHI Conference on Human Factors in Computing Systems10.1145/3613904.3642155(1-16)Online publication date: 11-May-2024
https://dl.acm.org/doi/10.1145/3613904.3642155
Zhang ZShi ZZhong FZhang KZhang WGuo JTu CZhao H(2024)Continuous Toolpath Optimization for Simultaneous Four‐Axis Subtractive ManufacturingComputer Graphics Forum10.1111/cgf.15204Online publication date: 4-Oct-2024
https://doi.org/10.1111/cgf.15204
Huahui C(2024)High-quality Approximation of the Fermat Spiral with Polynomial Function2024 4th Asia-Pacific Conference on Communications Technology and Computer Science (ACCTCS)10.1109/ACCTCS61748.2024.00009(18-21)Online publication date: 24-Feb-2024
https://doi.org/10.1109/ACCTCS61748.2024.00009
Zhao TYan ZZhang BZhang PPan RYuan TXiao JJiang FWei HLin SChen S(2024)A comprehensive review of process planning and trajectory optimization in arc-based directed energy depositionJournal of Manufacturing Processes10.1016/j.jmapro.2024.03.093119(235-254)Online publication date: Jun-2024
https://doi.org/10.1016/j.jmapro.2024.03.093
Zhao TYan ZZhao YJia YChen S(2024)Path planning in additive manufacturing with multi-robot collaboration based on structural primitive partitioningAdvances in Engineering Software10.1016/j.advengsoft.2024.103754197:COnline publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1016/j.advengsoft.2024.103754
Kipping JNettig DSchüppstuhl T(2024)Looping: Load-oriented optimized paths in non-planar geometryAdditive Manufacturing10.1016/j.addma.2024.10442694(104426)Online publication date: Aug-2024
https://doi.org/10.1016/j.addma.2024.104426
Zhi YTeng TAkbarzadeh M(2024)Designing 3D-printed concrete structures with scaled fabrication modelsArchitectural Intelligence10.1007/s44223-024-00070-33:1Online publication date: 8-Aug-2024
https://doi.org/10.1007/s44223-024-00070-3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents