“VDAC: volume decompose-and-carve for subtractive manufacturing” by Mahdavi-Amiri, Yu, Zhao, Schulz and Zhang
Conference:
Type(s):
Title:
- VDAC: volume decompose-and-carve for subtractive manufacturing
Session/Category Title: Fabrication: Carving, Dicing, and Printing
Presenter(s)/Author(s):
Abstract:
We introduce carvable volume decomposition for efficient 3-axis CNC machining of 3D freeform objects, where our goal is to develop a fully automatic method to jointly optimize setup and path planning. We formulate our joint optimization as a volume decomposition problem which prioritizes minimizing the number of setup directions while striving for a minimum number of continuously carvable volumes, where a 3D volume is continuously carvable, or simply carvable, if it can be carved with the machine cutter traversing a single continuous path. Geometrically, carvability combines visibility and monotonicity and presents a new shape property which had not been studied before. Given a target 3D shape and the initial material block, our algorithm first finds the minimum number of carving directions by solving a set cover problem. Specifically, we analyze cutter accessibility and select the carving directions based on an assessment of how likely they would lead to a small carvable volume decomposition. Next, to obtain a minimum decomposition based on the selected carving directions efficiently, we narrow down the solution search by focusing on a special kind of points in the residual volume, single access or SA points, which are points that can be accessed from one and only one of the selected carving directions. Candidate carvable volumes are grown starting from the SA points. Finally, we devise an energy term to evaluate the carvable volumes and their combinations, leading to the final decomposition. We demonstrate the performance of our decomposition algorithm on a variety of 2D and 3D examples and evaluate it against the ground truth, where possible, and solutions provided by human experts. Physically machined models are produced where each carvable volume is continuously carved following a connected Fermat spiral toolpath.
References:
1. M. Al-wswasi, A. Ivanov, and H. Makatsoris. 2018. A survey on smart automated computer-aided process planning (ACAPP) techniques. The International Journal of Advanced Manufacturing Technology 97, 1 (2018), 809–832.Google Scholar
2. T. Alderighi, L. Malomo, D. Giorgi, B. Bickel, P. Cignoni, and N. Pietroni. 2019. Volume-Aware Design of Composite Molds. ACM Trans. Graph. 38, 4, Article 110:1–110:12 (2019).Google Scholar
3. T. Alderighi, L. Malomo, D. Giorgi, N. Pietroni, B. Bickel, and P. Cignoni. 2018. Metamolds: computational design of silicone molds. ACM Trans. Graph. 37, 4 (2018), 136:1–136:13.Google ScholarDigital Library
4. G. Alemanno, P. Cignoni, N. Pietroni, F. Ponchio, and R. Scopigno. 2014. Interlocking Pieces for Printing Tangible Cultural Heritage Replicas. In Eurographics Workshop on Graphics and Cultural Heritage, Reinhard Klein and Pedro Santos (Eds.). The Eurographics Association.Google Scholar
5. C. Araújo, D. Cabiddu, M. Attene, M. Livesu, N. Vining, and A. Sheffer. 2019. Surface2Volume: Surface Segmentation Conforming Assemblable Volumetric Partition. ACM Trans. Graph. 38, 4 (2019), 80:1–80:16.Google Scholar
6. P. Bose and M. van Kreveld. 2005. Generalizing monotonicity: on recognizing special classes pf polygons and polyhedra. International Journal of Computational Geometry & Applications 15, 6 (2005), 591–608.Google ScholarCross Ref
7. X. Chen, H. Zhang, J. Lin, R. Hu, L. Lu, Q.-X. Huang, B. Benes, D. Cohen-Or, and B. Chen. 2015. Dapper: decompose-and-pack for 3D printing. ACM Trans. Graph. 34, 6 (2015), 213:1–213:12.Google ScholarDigital Library
8. B. Choi and R. Jerrard. 1998. Sculptured Surface Machining: Theory and Applications. Kluwer Academic Publishers.Google Scholar
9. D. Ding, Z. S. Pan, D. Cuiuri, and H. Li. 2014. A tool-path generation strategy for wire and arc additive manufacturing. The international journal of advanced manufacturing technology 73, 1–4 (2014), 173–183.Google Scholar
10. S. P. Fekete and J. S. Mitchell. 2001. Terrain decomposition and layered manufacturing. Int. J. Computational Geometry & Applications 11, 06 (2001), 647–668.Google ScholarCross Ref
11. M. R. Garey and D. S. Johnson. 1983. Computers and Intractability. A Guide to the Theory of NP-Completeness. (1983).Google Scholar
12. A. Hattab and G. Taubin. 2019. Rough Carving of 3D Models with Spatial Augmented Reality. In ACM Symp. Computational Fabrication.Google Scholar
13. S. Hauth and L. Linsen. 2011. Double-spiral tool path in configuration space. Int. J. Advanced Manufacturing Technology 54, 9–12 (2011), 1011–1022.Google ScholarCross Ref
14. P. Herholz, W. Matusik, and M. Alexa. 2015. Approximating Free-form Geometry with Height Fields for Manufacturing. Computer Graphics Forum 34, 2 (2015), 239–251.Google ScholarDigital Library
15. R. Hu, H. Li, H. Zhang, and D. Cohen-Or. 2014. Approximate Pyramidal Shape Decomposition. ACM Trans. Graph. 33, 6, Article 213 (Nov. 2014), 213:1–213:12 pages.Google Scholar
16. A. Jacobson. 2017. Generalized matryoshka: Computational design of nesting objects. Computer Graphics Forum 36, 5 (2017), 27–35.Google Scholar
17. A. Jacobson, D. Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.Google Scholar
18. J. M. Keil. 1985. Decomposing a Polygon into Simpler Components. SIAM J. Comput. 14, 4 (1985), 799–817.Google Scholar
19. D. E. Knuth. 2000. Dancing links. arXiv preprint cs/0011047 (2000).Google Scholar
20. A. Lasemi, D. Xue, and P. 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
21. M. Livesu, S. Ellero, J. Martínez, S. Lefebvre, and M. Attene. 2017. From 3D models to 3D prints: an overview of the processing pipeline. Computer Graphics Forum 36, 2 (2017), 537–564.Google ScholarCross Ref
22. B. T. Lowerre. 1976. The HARPY speech recognition system. Technical Report. CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE.Google Scholar
23. L. Luo, I. Baran, S. M. Rusinkiewicz, and W. Matusik. 2012. Chopper: Partitioning models into 3D-printable parts. ACM Trans. Graph. 31, 6 (2012), 129:1–129:9.Google ScholarDigital Library
24. L. Malomo, N. Pietroni, B. Bickel, and P. Cignoni. 2016. FlexMolds: automatic design of flexible shells for molding. ACM Trans. Graph. 35, 6 (2016), 223:1–223:12.Google ScholarDigital Library
25. A. Muntoni, M. Livesu, R. Scateni, A. Sheffer, and D. Panozzo. 2018. Axis-aligned height-field block decomposition of 3D shapes. ACM Trans. Graph. 37, 5 (2018), 169:1–169:15.Google ScholarDigital Library
26. A. Rivers, I. E. Moyer, and F. Durand. 2012. Position-correcting Tools for 2D Digital Fabrication. ACM Trans. Graph. 31, 4 (2012), 88:1–88:7.Google ScholarDigital Library
27. A. Sá, K. Rodriguez-Echavarria, N. Pietroni, and P. Cignoni. 2016. State of the art on functional fabrication. In Proceedings of the Eurographics Workshop on Graphics for Digital Fabrication. Eurographics Association, 1–9.Google Scholar
28. Siemens Industry Software Inc. 2020. NX software. www.plm.automation.siemens.com/global/en/products/nx/.Google Scholar
29. O. Stein, A. Jacobson, and E. Grinspun. 2019. Interactive design of castable shapes using two-piece rigid molds. Computers & Graphics 80 (2019), 51–62.Google ScholarCross Ref
30. G. Toussaint. 1985. Movable separability of sets. Comput. Geom. (1985), 335–375.Google Scholar
31. X. Wei, A. Joneja, and D. M. Mount. 2012. Optimal uniformly monotone partitioning of polygons with holes. Computer-Aided Design 44 (2012), 1235–1252.Google ScholarDigital Library
32. Y. Yang, H. T. Loh, J. Fuh, and Y. Wang. 2002. Equidistant path generation for improving scanning efficiency in layered manufacturing. Rapid Prototyping 8, 1 (2002), 30–37.Google ScholarCross Ref
33. H. Zhao, F. Gu, Q.-X. Huang, J. Garcia, Y. Chen, C. Tu, B. Benes, H. Zhang, D. Cohen-Or, and B. Chen. 2016. Connected Fermat spirals for layered fabrication. ACM Trans. Graph. 35, 4 (2016), 100:1–100:10.Google ScholarDigital Library
34. H. Zhao, H. Zhang, S. Xin, Y. Deng, C. Tu, W. Wang, D. Cohen-Or, and B. Chen. 2018. DSCarver: Decompose-and-Spiral-Carve for Subtractive Manufacturing. ACM Trans. Graph. 37, 4 (2018), 137:1–137:14.Google Scholar
