“DHFSlicer: double height-field slicing for milling fixed-height materials” by Yang, Araújo, Vining, Ferguson, Rosales, et al. …
Conference:
Type(s):
Title:
- DHFSlicer: double height-field slicing for milling fixed-height materials
Session/Category Title: Fabrication: Carving, Dicing, and Printing
Presenter(s)/Author(s):
Abstract:
3-axis milling enables cheap and precise fabrication of target objects from precut slabs of materials such as wood or stone. However, the space of directly millable shapes is limited since a 3-axis mill can only carve a height-field (HF) surface during each milling and their size is bounded by the slab dimensions, one of which, the height, is typically significantly smaller than the other two for many typical materials. Extending 3-axis milling of precut slabs to general arbitrarily-sized shapes requires decomposing them into bounded-height 3-axis millable parts, or slices, which can be individually milled and then assembled to form the target object. We present DHFSlicer, a novel decomposition method that satisfies the above constraints and significantly reduces both milling time and material waste compared to alternative approaches. We satisfy the fabrication constraints by partitioning target objects into double height-field (DHF) slices, which can be fabricated using two milling passes: the HF surface accessible from one side is milled first, the slice is then flipped using appropriate fixtures, and then the second, remaining, HF surface is milled. DHFSlicer uses an efficient coarse-to-fine decomposition process: It first partitions the inputs into maximally coarse blocks that satisfy a local DHF criterion with respect to per-block milling axes, and then cuts each block into well-sized DHF slices. It minimizes milling time and material waste by keeping the slice count small, and maximizing slice height. We validate our method by embedding it within an end-to-end DHF milling pipeline and fabricating objects from slabs of foam, wood, and MDF; demonstrate that using the obtained slices reduces milling time and material waste by 42% on average compared to existing automatic alternatives; and highlight the benefits of DHFSlicer via extensive ablation studies.
References:
1. 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. 145–154.Google Scholar
2. C. Araújo, D. Cabiddu, M. Attene, M. Livesu, N. Vining, and Alla Sheffer. 2019. Surface2Volume: Surface Segmentation Conforming Assemblable Volumetric Partition. ACM Trans. Graph. 38, 4 (2019).Google ScholarDigital Library
3. S. Asafi, A. Goren, and D. Cohen-Or. 2013. Weak Convex Decomposition by Lines-of-sight. In Proc. Eurographics SGP 2013.Google Scholar
4. M. Attene. 2015. Shapes in a box: Disassembling 3D objects for efficient packing and fabrication. Computer Graphics Forum 34, 8 (2015).Google Scholar
5. Autodesk. 2020. Fusion 360. https://www.autodesk.com/products/fusion-360/.Google Scholar
6. O.J. Bakker, T.N. Papastathis, A.A. Popov, and S.M. Ratchev. 2013. Active fixturing: literature review and future research directions. International Journal of Production Research 51, 11 (2013), 3171–3190.Google ScholarCross Ref
7. Z. M. Bi and W. J. Zhang. 2001. Flexible fixture design and automation: Review, issues and future directions. International Journal of Production Research 39, 13 (2001).Google ScholarCross Ref
8. B. Bickel, P. Cignoni, L. Malomo, and N. Pietroni. 2018. State of the Art on Stylized Fabrication. Computer Graphics Forum 37, 6 (2018), 325–342.Google ScholarCross Ref
9. V. Boykov, O. Veksler, and R. Zabih. 2001. Fast approximate energy minimization via graph cuts. IEEE. Trans. Pattern Analysis and Machine Intelligence 23, 11 (2001), 1222–1239.Google ScholarDigital Library
10. Y. Boykov and V. Kolmogorov. 2004. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Analysis and Machine Intelligence 26, 9 (2004), 1124–1137.Google ScholarDigital Library
11. B. Chazelle. 1984. Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm. SIAM J. Comput. 13, 3 (1984).Google ScholarDigital Library
12. 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. Graphics 34, 6 (2015).Google ScholarDigital Library
13. Cirtes. 1991. Cirtes: Recherche et Developpement. https://cirtes.com/en/stratoconception/.Google Scholar
14. R. Cook. 1984. Shade Trees. ACM Siggraph Computer Graphics 18, 3 (1984).Google Scholar
15. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. 2001. Introduction to Algorithms (2nd ed.). MIT Press.Google Scholar
16. B. Delebecque, Y. Houtmann, G. Lauvaux, and C. Barlier. 2008. Automated generation of assembly features in layered manufacturing. Rapid Prototyping Journal (2008).Google Scholar
17. M. Doggett and J. Hirche. 2000. Adaptive view dependent tessellation of displacement maps. In Proc. Graphics hardware. ACM.Google ScholarDigital Library
18. H. Edelsbrunner and J. Harer. 2008. Persistent homology — a survey. In Surveys on discrete and computational geometry, Vol. 453.Google Scholar
19. S. Fekete and J. Mitchell. 2001. Terrain decomposition and layered manufacturing. International Journal of Computational Geometry & Applications 11, 06 (2001).Google ScholarCross Ref
20. W. Gao, Y. Zhang, D. Nazzetta, K. Ramani, and R. Cipra. 2015. RevoMaker: Enabling multi-directional and functionally-embedded 3D printing using a rotational cuboidal platform. In Proc. User Interface Software & Technology (UIST). ACM.Google Scholar
21. M. Garey, D. Johnson, and R. Sethi. 1976. The complexity of flowshop and jobshop scheduling. Mathematics of operations research 1, 2 (1976), 117–129.Google Scholar
22. J. Hao, L. Fang, and R. Williams. 2011. An efficient curvature-based partitioning of large-scale STL models. Rapid Prototyping Journal 17, 2 (2011).Google ScholarCross Ref
23. P. Herholz, W. Matusik, and M. Alexa. 2015. Approximating Free-form Geometry with Height Fields for Manufacturing. Computer Graphics Forum 34, 2 (2015).Google Scholar
24. K. Hildebrand, B. Bickel, and M. Alexa. 2013. Orthogonal slicing for additive manufacturing. Computers & Graphics 37, 6 (2013).Google Scholar
25. Y. Houtmann, B. Delebecque, G. Lauvaux, C. Barlier, and G. Ris. 2007. Decomposition applied to layered manufacturing using critical points. Virtual and Physical Prototyping 2, 2 (2007), 127–133.Google ScholarCross Ref
26. R. Hu, H. Li, H. Zhang, and D. Cohen-Or. 2014. Approximate Pyramidal Shape Decomposition. ACM Trans. Graph. 33, 6, Article 213 (2014).Google ScholarDigital Library
27. Y. Hu, Q. Zhou, X. Gao, A. Jacobson, D. Zorin, and D. Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4 (2018), 60:1–60:14.Google ScholarDigital Library
28. A. Jacobson, D. Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.Google Scholar
29. C.-S. Jun, D.-S. Kim, J.S. Hwang, and T.-C Chang. 1998. Surface slicing algorithm for rapid prototyping and machining. Geometric Modeling Processing (1998).Google Scholar
30. B. Keinert, M. Innmann, M. Sänger, and M. Stamminger. 2015. Spherical Fibonacci Mapping. ACM Trans. Graph. 34, 6 (2015).Google ScholarDigital Library
31. Y. Koyama, S. Sueda, E. Steinhardt, T. Igarashi, A. Shamir, and W. Matusik. 2015. Auto-Connect: Computational Design of 3D-Printable Connectors. 34, 6 (2015).Google Scholar
32. V Kraevoy, D Julius, and A Sheffer. 2007. Shuffler: Modeling with interchangeable parts. The Visual Computer (2007).Google Scholar
33. B. Lévy, S. Petitjean, N. Ray, and J. Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (2002), 362–371.Google ScholarDigital Library
34. J-M. Lien and N. Amato. 2007. Approximate convex decomposition of polyhedra. In Proc. ACM Symposium on Solid and physical modeling.Google Scholar
35. 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).Google Scholar
36. L. Luo, I. Baran, S. Rusinkiewicz, and W. Matusik. 2012. Chopper: Partitioning Models into 3D-printable Parts. ACM Trans. Graph. 31, 6 (2012).Google ScholarDigital Library
37. A. Mahdavi-Amiri, F. Yu, H. Zhao, A. Schulz, and H. Zhang. 2020. VDAC: Volume Decompose-and-Carve for Subtractive Manufacturing. In Proc. SIGGRAPH Asia 2020. To appear.Google Scholar
38. A. Medeiros e Sá, K. Rodriguez Echavarria, N. Pietroni, and P. Cignoni. 2016. State Of The Art on Functional Fabrication. In Proc. Workshop on Graphics for Digital Fabrication.Google Scholar
39. H Medellín, T Lim, J Corney, JM Ritchie, and JBC Davies. 2007. Automatic subdivision and refinement of large components for rapid prototyping production. Journal of Computing and Information Science in Engineering 7, 3 (2007).Google ScholarCross Ref
40. 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
41. A. Muntoni, L.D. Spano, and R. Scateni. 2019. Split and Mill: User Assisted Height-field Block Decomposition for Fabrication. In Smart Tools and Apps for Graphics – Eurographics Italian Chapter Conference.Google Scholar
42. C. Rattat. 2017. CNC Milling for Makers: Basics – Techniques – Applications. Rocky Nook.Google Scholar
43. R. Schmidt and K. Singh. 2010. Meshmixer: An Interface for Rapid Mesh Composition. In ACM SIGGRAPH 2010 Talks. Article 6.Google Scholar
44. P. Song, B. Deng, Z. Wang, Z. Dong, W. Li, C-W. Fu, and L. Liu. 2016. CofiFab: Coarse-to-Fine Fabrication of Large 3D Objects. ACM Trans. Graph (SIGGRAPH 2016) 35, 4 (2016).Google Scholar
45. P. Song, Z. Fu, L. Liu, and C-W. Fu. 2015. Printing 3D objects with interlocking parts. Computer Aided Geometric Design 35 (2015), 137–148.Google ScholarDigital Library
46. J. C. Trappey and C. R. Liu. 1990. A literature survey of fixturedesign automation. The International Journal of Advanced Manufacturing Technology 5, 3 (01 Aug 1990).Google ScholarCross Ref
47. J. Tyberg and J.H. Bohn. 1998. Local Adaptive Slicing. Rapid Prototyping Journal 4, 3 (1998).Google ScholarCross Ref
48. J. Yao, D. Kaufman, Y. Gingold, and M. Agrawala. 2017. Interactive Design and Stability Analysis of Decorative Joinery for Furniture. ACM Trans. Graphics 36, 2 (2017), 20.Google ScholarDigital Library
49. M. Yao, Z. Chen, L. Luo, R. Wang, and H. Wang. 2015. Level-set-based Partitioning and Packing Optimization of a Printable Model. ACM Trans. Graph. 34, 6 (2015), 214:1–214:11.Google ScholarDigital Library
50. Q. Zhou, E. Grinspun, D. Zorin, and A. Jacobson. 2016. Mesh Arrangements for Solid Geometry. ACM Trans. Graph. 35, 4, Article 39 (July 2016).Google ScholarDigital Library
