“DSCarver: decompose-and-spiral-carve for subtractive manufacturing” by Zhang, Zhang, Xin, Deng, Tu, et al. …

  • ©Haisen Zhang, Hao (Richard) Zhang, Shiqing Xin, Yuanmin Deng, Changhe Tu, Wenping Wang, and Daniel Cohen-Or

  • ©Haisen Zhang, Hao (Richard) Zhang, Shiqing Xin, Yuanmin Deng, Changhe Tu, Wenping Wang, and Daniel Cohen-Or



Entry Number: 137


    DSCarver: decompose-and-spiral-carve for subtractive manufacturing

Session/Category Title: New Additions (and Subtractions) to Fabrication




    We present an automatic algorithm for subtractive manufacturing of freeform 3D objects using high-speed machining (HSM) via CNC. A CNC machine operates a cylindrical cutter to carve off material from a 3D shape stock, following a tool path, to “expose” the target object. Our method decomposes the input object’s surface into a small number of patches each of which is fully accessible and machinable by the CNC machine, in continuous fashion, under a fixed cutter-object setup configuration. This is achieved by covering the input surface with a minimum number of accessible regions and then extracting a set of machinable patches from each accessible region. For each patch obtained, we compute a continuous, space-filling, and iso-scallop tool path which conforms to the patch boundary, enabling efficient carving with high-quality surface finishing. The tool path is generated in the form of connected Fermat spirals, which have been generalized from a 2D fill pattern for layered manufacturing to work for curved surfaces. Furthermore, we develop a novel method to control the spacing of Fermat spirals based on directional surface curvature and adapt the heat method to obtain iso-scallop carving. We demonstrate automatic generation of accessible and machinable surface decompositions and iso-scallop Fermat spiral carving paths for freeform 3D objects. Comparisons are made to tool paths generated by commercial software in terms of real machining time and surface quality.


    1. Rajneesh Kumar Agrawal, D. K. Pratihar, and Roy Choudhury. 2006. Optimization of CNC isoscallop free form surface machining using a genetic algorithm. The International Journal of Advanced Manufacturing Technology 46, 7–8 (2006), 811–819.Google Scholar
    2. Saleh M Amaitik and S Engin Kiliç. 2007. An intelligent process planning system for prismatic parts using STEP features. The International Journal of Advanced Manufacturing Technology 31, 9–10 (2007), 978–993.Google ScholarCross Ref
    3. Karlo Apro. 2008. Secrets of 5-axis machining. Industrial Press Inc. Google ScholarDigital Library
    4. Amit H Bermano, Thomas Funkhouser, and Szymon Rusinkiewicz. 2017. State of the Art in Methods and Representations for Fabrication-Aware Design. Computer Graphics Forum 36, 2 (2017), 509–535. Google ScholarDigital Library
    5. Zhang Wei Bo, Lu Zhen Hua, and Zhu Guang Yu. 2006. Optimization of process route by genetic algorithms. Robotics and Computer-Integrated Manufacturing 22, 2 (2006), 180–188.Google ScholarCross Ref
    6. John Bowers, Rui Wang, Li Yi Wei, and David Maletz. 2010. Parallel Poisson disk sampling with spectrum analysis on surfaces. ACM Transactions on Graphics 29, 6 (2010), 166. Google ScholarDigital Library
    7. Yuri Boykov, Olga Veksler, and Ramin Zabih. 2001. Fast Approximate Energy Minimization via Graph Cuts. IEEE Trans. Pat Ana. & Mach. Int. 23, 11 (2001), 1222–1239. Google ScholarDigital Library
    8. Marcel Campen, Martin Heistermann, and Leif Kobbelt. 2013. Practical anisotropic geodesy. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 63–71. Google ScholarDigital Library
    9. Ahmet Can and Ali Ünüvar. 2010. A novel iso-scallop tool-path generation for efficient five-axis machining of free-form surfaces. The International Journal of Advanced Manufacturing Technology 51, 9–12 (2010), 1083–1098.Google ScholarCross Ref
    10. 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. on Graph 34, 6 (2015), 213:1–213:12. Google ScholarDigital Library
    11. B. Choi and R. Jerrard. 1998. Sculptured Surface Machining: Theory and Applications. Kluwer Academic Publishers.Google Scholar
    12. V. Chvatal. 1979. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research 4, 3 (1979), pp. 233–235. http://www.jstor.org/stable/3689577 Google ScholarDigital Library
    13. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms. MIT Press and McGraw-Hill. Google ScholarDigital Library
    14. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013a. Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow. ACM Trans. on Graph 32, 5 (2013), 152:1–152:11. Google ScholarDigital Library
    15. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013b. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transactions on Graphics 32, 5 (2013), 13–15. Google ScholarDigital Library
    16. Donghong Ding, Zengxi Stephen Pan, Dominic Cuiuri, and Huijun Li. 2014. A tool-path generation strategy for wire and arc additive manufacturing. Int. J. of Adv. Manufact. Tech. 73, 1–4 (2014), 173–183.Google ScholarCross Ref
    17. R. T. Farouki. 2016. Rational rotation-minimizing frames — Recent advances and open problems. Appl. Math. Comput. 272 (2016), 80–91. Google ScholarDigital Library
    18. R. T. Farouki and S. Li. 2013. Optimal tool orientation control for 5-axis CNC milling with ball-end cutters. Computer Aided Geometric Design 30, 2 (2013), 226–239. Google ScholarDigital Library
    19. Matthew C Frank, Richard A Wysk, and Sanjay B Joshi. 2006. Determining setup orientations from the visibility of slice geometry for rapid computer numerically controlled machining. Journal of manufacturing science and engineering 128, 1 (2006), 228–238.Google ScholarCross Ref
    20. Stefan Gottschalk, Ming Lin, Dinesh Manocha, and Eric Larsen. 1999. PQP-the proximity query package. Accessed October 4 (1999), 2011.Google Scholar
    21. YW Guo, Antony R Mileham, Geraint W Owen, Paul G Maropoulos, and WD Li. 2009. Operation sequencing optimization for five-axis prismatic parts using a particle swarm optimization approach. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture 223, 5 (2009), 485–497.Google ScholarCross Ref
    22. Prosenjit Gupta, Ravi Janardan, Jayanth Majhi, and Tony Woo. 1996. Efficient geometric algorithms for workpiece orientation in 4-and 5-axis NC machining. Computer-Aided Design 28, 8 (1996), 577–587.Google ScholarCross Ref
    23. Steffen Hauth and Lars Linsen. 2012. Double-spiral tool path in configuration space. The International Journal of Advanced Manufacturing Technology 54, 9 (2012), 1011–1022.Google ScholarCross Ref
    24. Manjuri Hazarika, Uday Shanker Dixit, et al. 2015. Setup planning for machining. Springer.Google Scholar
    25. Martin Held and Christian Spielberger. 2014. Improved Spiral High-Speed Machining of Multiply-Connected Pockets. Computer-Aided Design and Applications 11, 3 (2014), 346–357.Google ScholarCross Ref
    26. Philipp Herholz, Wojciech Matusik, and Marc Alexa. 2015. Approximating Free-form Geometry with Height Fields for Manufacturing. Computer Graphics Forum (Eurographics) 34, 2 (2015), 239–251. Google ScholarDigital Library
    27. Kristian Hildebrand, Bernd Bickel, and Marc Alexa. 2013. Orthogonal slicing for additive manufacturing. Computers & Graphics 37, 6 (2013), 669 — 675. Shape Model. Intl. (SMI) Conf. Google ScholarDigital Library
    28. Ruizhen Hu, Honghua Li, Hao Zhang, and Daniel Cohen-Or. 2014. Approximate Pyramidal Shape Decomposition. ACM Trans. on Graph 33, 6 (2014), 213:1–213:12. Google ScholarDigital Library
    29. Ralph L Keeney and Howard Raiffa. 1993. Decisions with multiple objectives: preferences and value trade-offs. Cambridge university press.Google Scholar
    30. Su Jin Kim, Dong Yoon Lee, Hyun Chul Kim, Sung Gun Lee, and Min Yang Yang. 2006. CL surface deformation approach for a 5-axis tool path generation. International Journal of Advanced Manufacturing Technology 28, 5–6 (2006), 509–517.Google Scholar
    31. Yuki Koyama, Shinjiro Sueda, Emma Steinhardt, Takeo Igarashi, Ariel Shamir, and Wojciech Matusik. 2015. AutoConnect: Computational Design of 3D-printable Connectors. ACM Trans. on Graph 34, 6, Article 231 (2015), 231:1–231:11 pages. Google ScholarDigital Library
    32. Ali Lasemi, Deyi Xue, and Peihua Gu. 2010. Recent development in CNC machining of freeform surfaces: A state-of-the-art review. Computer-Aided Design 42, 7 (2010), 641–654. Google ScholarDigital Library
    33. Yunjin Lee and Seungyong Lee. 2002. Geometric Snakes for Triangular Meshes. Computer Graphics Forum 21, 3 (2002), 229–238.Google ScholarCross Ref
    34. 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. on Graph 33, 4 (2014), 97:1–97:10. Google ScholarDigital Library
    35. Linjie Luo, Ilya Baran, Szymon Rusinkiewicz, and Wojciech Matusik. 2012. Chopper: Partitioning Models into 3D-Printable Parts. ACM Trans. on Graph 31, 6 (2012), 129:1–129:9. Google ScholarDigital Library
    36. Debananda Misra, V Sundararajan, and Paul K Wright. 2005. Zig-zag tool path generation for sculptured surface finishing. In Geometric and algorithmic aspects of computer-aided design and manufacturing: DIMACS workshop computer aided design and manufacturing, Vol. 67. 265.Google Scholar
    37. Sang C Park, Chang Y C, and Byoung Kyu Choi. 2003. Contour-parallel offset machining without tool-retractions. Computer-Aided Design 35, 9 (2003), 841–849.Google ScholarCross Ref
    38. Helmut Pottmann, Johannes Wallner, Qi-Xing Huang, and Yong-Liang Yang. 2009. Integral invariants for robust geometry processing. Comp. Aided Geom. Design 26, 1 (2009), 37–60. Google ScholarDigital Library
    39. Romain Prévost, Emily Whiting, Sylvain Lefebvre, and Olga Sorkine-Hornung. 2013. Make It Stand: Balancing Shapes for 3D Fabrication. ACM Trans. on Graph 32, 4 (2013), 81:1–81:10. Google ScholarDigital Library
    40. Fei Ren, Yuwen Sun, and Dongming Guo. 2009. Combined reparameterization-based spiral toolpath generation for five-axis sculptured surface machining. Int. J. of Adv. Manufac. Tech. 40, 7 (2009), 760–768.Google ScholarCross Ref
    41. Ariel Shamir. 2008. A survey on Mesh Segmentation Techniques. Computer Graphics Forum 27, 6 (2008), 1539–1556.Google ScholarCross Ref
    42. Siemens. 2016. NX Software. http://www.plm.automation.siemens.com/en_us/products/nx/index.shtml. (2016).Google Scholar
    43. Ondrej Stava, Juraj Vanek, Bedrich Benes, Nathan Carr, and Radomir Měch. 2012. Stress relief: improving structural strength of 3D printable objects. ACM Tran. on Graph 31, 4 (2012), 48:1–48:11. Google ScholarDigital Library
    44. Y-J Tseng and SB Joshi. 1998. Recognition of interacting rotational and prismatic machining features from 3D mill-turn parts. International Journal of Production Research 36, 11 (1998), 3147–3165.Google ScholarCross Ref
    45. Yu Wang, Kai-Min Yu, and Charlie CL Wang. 2015. Spiral and conformal cooling in plastic injection molding. Computer-Aided Design 63 (2015), 1–11. Google ScholarDigital Library
    46. Nuo Xu, Samuel H Huang, and Y Kevin Rong. 2007. Automatic setup planning: current state-of-the-art and future perspective. International journal of manufacturing technology and management 11, 2 (2007), 193–208.Google ScholarCross Ref
    47. Y Yang, HT Loh, JYH Fuh, and YG Wang. 2002. Equidistant path generation for improving scanning efficiency in layered manufacturing. Rapid Prototyping Journal 8, 1 (2002), 30–37.Google ScholarCross Ref
    48. Haisen Zhao, Fanglin Gu, Qi-Xing Huang, Jorge Garcia, Hao Zhang, Daniel Cohen-Or, Yong Chen, Changhe Tu, and Baoquan Chen. 2016. Connected Fermat Spirals for Layered Fabrication. ACM Trans. on Graph 35, 4 (2016). Google ScholarDigital Library
    49. J. Zhao, B. Zhong, and Q. Zou. 2013. Tool orientation planning for five-axis CNC machining of open free-form surfaces. Journal of Systems Science and Complexity 26, 5 (2013), 667–675.Google ScholarCross Ref
    50. Bo Zhou, Jibin Zhao, Lun Li, and Renbo Xia. 2016. A smooth double spiral tool path generation and linking method for high-speed machining of multiply-connected pockets. Precision Engineering (2016).Google Scholar
    51. Qiang Zoua, Juyong Zhanga, Bailin Deng, and Jibin Zhao. 2014. Iso-level tool path planning for free-form surfaces. Computer-Aided Design 53 (2014), 217–225.Google Scholar

ACM Digital Library Publication:

Overview Page: