“Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects” by Cui, Rong, Chen and Matusik
Conference:
Type:
Title:
- Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects
Session/Category Title: Fabulous Fabrication: From Knitting to Circuits
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Packing 3D objects into a known container is a very common task in many industries such as packaging, transportation, and manufacturing. This important problem is known to be NP-hard and even approximate solutions are challenging. This is due to the difficulty of handling interactions between objects with arbitrary 3D geometries and a vast combinatorial search space. Moreover, the packing must be interlocking-free for real-world applications. In this work, we first introduce a novel packing algorithm to search for placement locations given an object. Our method leverages a discrete voxel representation. We formulate collisions between objects as correlations of functions computed efficiently using Fast Fourier Transform (FFT). To determine the best placements, we utilize a novel cost function, which is also computed efficiently using FFT. Finally, we show how interlocking detection and correction can be addressed in the same framework resulting in interlocking-free packing. We propose a challenging benchmark with thousands of 3D objects to evaluate our algorithm. Our method demonstrates state-of-the-art performance on the benchmark when compared to existing methods in both density and speed.
References:
1. Luiz JP Araújo, Ender Özcan, Jason AD Atkin, and Martin Baumers. 2019. Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset. International Journal of Production Research 57, 18 (2019), 5920–5934.
2. Richard Carl Art Jr. 1966. An approach to the two dimensional irregular cutting stock problem. Ph.D. Dissertation. Massachusetts Institute of Technology.
3. Autodesk. 2023. Autodesk Netfabb. https://www.autodesk.com/products/netfabb/ Build: 47, Release: 2023.1.
4. Edmund K Burke, Robert SR Hellier, Graham Kendall, and Glenn Whitwell. 2007. Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research 179, 1 (2007), 27–49.
5. Elizabeth R Chen, Michael Engel, and Sharon C Glotzer. 2010. Dense crystalline dimer packings of regular tetrahedra. Discrete & Computational Geometry 44, 2 (2010), 253–280.
6. Rulin Chen, Ziqi Wang, Peng Song, and Bernd Bickel. 2022. Computational design of high-level interlocking puzzles. ACM Trans. Graph. 41, 4 (2022), 1–15.
7. Xuelin Chen, Hao Zhang, Jinjie Lin, Ruizhen Hu, Lin Lu, Qi-Xing Huang, Bedrich Benes, Daniel Cohen-Or, and Baoquan Chen. 2015. Dapper: decompose-and-pack for 3d printing. ACM Trans. Graph. 34, 6 (2015), 213–1.
8. Nikolai Chernov, Yuriy Stoyan, and Tatiana Romanova. 2010. Mathematical model and efficient algorithms for object packing problem. Computational Geometry 43, 5 (2010), 535–553.
9. Erwin Coumans and Yunfei Bai. 2016–2021. PyBullet, a Python module for physics simulation for games, robotics and machine learning. http://pybullet.org.
10. Jens Egeblad, Claudio Garavelli, Stefano Lisi, and David Pisinger. 2010. Heuristics for container loading of furniture. European Journal of Operational Research 200, 3 (2010), 881–892.
11. Christer Ericson. 2004. Real-time collision detection. Crc Press.
12. Filippo Andrea Fanni, Fabio Pellacini, Riccardo Scateni, and Andrea Giachetti. 2022. PAVEL: Decorative Patterns with Packed Volumetric Elements. ACM Transactions on Graphics (TOG) 41, 2 (2022), 1–15.
13. Michael Fogleman. 2019. Pack3d. https://github.com/fogleman/pack3d
14. Michael Garland and Paul S Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. 209–216.
15. Michael Goldwasser, J-C Latombe, and Rajeev Motwani. 1996. Complexity measures for assembly sequences. In Proceedings of IEEE International Conference on Robotics and Automation, Vol. 2. IEEE, 1851–1857.
16. Ankit Goyal and Jia Deng. 2020. PackIt: A Virtual Environment for Geometric Planning. In International Conference on Machine Learning.
17. Si Hang. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw 41, 2 (2015), 11.
18. Ruizhen Hu, Juzhan Xu, Bin Chen, Minglun Gong, Hao Zhang, and Hui Huang. 2020. TAP-Net: transport-and-pack using reinforcement learning. ACM Trans. Graph. 39, 6 (2020), 1–15.
19. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.
20. David S Johnson. 1973. Near-optimal bin packing algorithms. Ph. D. Dissertation. Massachusetts Institute of Technology.
21. Ephraim Katchalski-Katzir, Isaac Shariv, Miriam Eisenstein, Asher A Friesem, Claude Aflalo, and Ilya A Vakser. 1992. Molecular surface recognition: determination of geometric fit between proteins and their ligands by correlation techniques. Proc Natl Acad of Sci 89, 6, 2195–2199.
22. Carlos Lamas-Fernandez, Julia A Bennell, and Antonio Martinez-Sykora. 2022. Voxel-Based Solution Approaches to the Three-Dimensional Irregular Packing Problem. Operations Research (2022).
23. Lei Lan, Danny M Kaufman, Minchen Li, Chenfanfu Jiang, and Yin Yang. 2022. Affine body dynamics: Fast, stable & intersection-free simulation of stiff materials. arXiv preprint arXiv:2201.10022 (2022).
24. Steven M LaValle. 2006. Planning algorithms. Cambridge university press.
25. Aline AS Leao, Franklina MB Toledo, José Fernando Oliveira, Maria Antónia Carravilla, and Ramón Alvarez-Valdés. 2020. Irregular packing problems: A review of mathematical models. European Journal of Operational Research 282, 3 (2020), 803–822.
26. Xiao Liu, Jia-min Liu, An-xi Cao, and Zhuang-le Yao. 2015. HAPE3D—a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology & Electronic Engineering 16, 5 (2015), 380–390.
27. Yuexin Ma, Zhonggui Chen, Wenchao Hu, and Wenping Wang. 2018. Packing irregular objects in 3D space via hybrid optimization. Comp. Graph. Forum (SGP) 37, 5 (2018), 49–59.
28. Silvano Martello, David Pisinger, and Daniele Vigo. 2000. The three-dimensional bin packing problem. Operations research 48, 2 (2000), 256–267.
29. NVIDIA. 2022a. CUDA, release: 12.0. https://developer.nvidia.com/cuda-toolkit
30. NVIDIA. 2022b. CUDA, release: 12.0. https://developer.nvidia.com/cufft
31. Dzmitry Padhorny, Andrey Kazennov, Brandon S Zerbe, Kathryn A Porter, Bing Xia, Scott E Mottarella, Yaroslav Kholodov, David W Ritchie, Sandor Vajda, and Dima Kozakov. 2016. Protein-protein docking by fast generalized Fourier transforms on 5D rotational manifolds. Proc Natl Acad Sci 113, 30, E4286–E4293.
32. Alexander Pankratov, Tatiana Romanova, and Igor Litvinchev. 2020. Packing oblique 3D objects. Mathematics 8, 7 (2020), 1130.
33. Bernhard Reinert, Tobias Ritschel, and Hans-Peter Seidel. 2013. Interactive by-example design of artistic packing layouts. ACM Transactions on Graphics (TOG) 32, 6 (2013), 1–7.
34. David W Ritchie and Graham JL Kemp. 2000. Protein docking using spherical polar Fourier correlations. Proteins: Structure, Function, and Bioinformatics 39, 2 (2000), 178–194.
35. David W Ritchie and Vishwesh Venkatraman. 2010. Ultra-fast FFT protein docking on graphics processors. Bioinformatics 26, 19 (2010), 2398–2405.
36. Tatiana Romanova, Julia Bennell, Yuriy Stoyan, and Aleksandr Pankratov. 2018. Packing of concave polyhedra with continuous rotations using nonlinear optimisation. European Journal of Operational Research 268, 1 (2018), 37–53.
37. Michael Schwarz and Hans-Peter Seidel. 2010. Fast parallel surface and solid voxelization on GPUs. ACM transactions on graphics (TOG) 29, 6 (2010), 1–10.
38. Sculpteo. 2023. Sculpteo Fabpilot. https://www.fabpilot.com/.
39. Pitchaya Sitthi-Amorn, Javier E Ramos, Yuwang Wangy, Joyce Kwan, Justin Lan, Wenshou Wang, and Wojciech Matusik. 2015. MultiFab: a machine vision assisted platform for multi-material 3D printing. Acm Transactions on Graphics (Tog) 34, 4 (2015), 1–11.
40. Peng Song, Chi-Wing Fu, and Daniel Cohen-Or. 2012. Recursive interlocking puzzles. ACM Trans. Graph. 31, 6 (2012), 1–10.
41. Yuriy Stoyan, Aleksandr Pankratov, and Tatiana Romanova. 2016. Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization 65, 2 (2016), 283–307.
42. Yunsheng Tian, Jie Xu, Yichen Li, Jieliang Luo, Shinjiro Sueda, Hui Li, Karl DD Willis, and Wojciech Matusik. 2022. Assemble Them All: Physics-Based Planning for Generalizable Assembly by Disassembly. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–11.
43. UnionTech. 2018. Polydevs. https://polydevs3d.com/ Version 2.2.5.33.
44. Juraj Vanek, JA Garcia Galicia, Bedrich Benes, R Měch, N Carr, Ondrej Stava, and GS Miller. 2014. Packmerger: A 3d print volume optimizer. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 322–332.
45. Fan Wang and Kris Hauser. 2019. Stable bin packing of non-convex 3D objects with a robot manipulator. In 2019 International Conference on Robotics and Automation (ICRA). IEEE, 8698–8704.
46. Ziqi Wang, Peng Song, and Mark Pauly. 2018. DESIA: A general framework for designing interlocking assemblies. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–14.
47. Ziqi Wang, Peng Song, and Mark Pauly. 2021. State of the Art on Computational Design of Assemblies with Rigid Parts. Eurographics 2021 STAR 40 (2021).
48. Randall H Wilson and Jean-Claude Latombe. 1994. Geometric reasoning about mechanical assembly. Artificial Intelligence 71, 2 (1994), 371–396.
49. Zifei Yang, Shuo Yang, Shuai Song, Wei Zhang, Ran Song, Jiyu Cheng, and Yibin Li. 2021. PackerBot: Variable-Sized Product Packing with Heuristic Deep Reinforcement Learning. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 5002–5008.
50. Miaojun Yao, Zhili Chen, Linjie Luo, Rui Wang, and Huamin Wang. 2015. Level-set-based partitioning and packing optimization of a printable model. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1–11.
51. Cha Zhang and Tsuhan Chen. 2001. Efficient feature extraction for 2D/3D objects in mesh representation. In Proceedings 2001 International Conference on Image Processing (Cat. No. 01CH37205), Vol. 3. IEEE, 935–938.
52. Xinya Zhang, Robert Belfer, Paul G Kry, and Etienne Vouga. 2020. C-Space tunnel discovery for puzzle path planning. ACM Transactions on Graphics (TOG) 39, 4 (2020), 104–1.
53. Hongkai Zhao. 2005. A fast sweeping method for eikonal equations. Mathematics of computation 74, 250 (2005), 603–627.
54. Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu. 2021. Online 3D bin packing with constrained deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 741–749.
55. Qingnan Zhou and Alec Jacobson. 2016. Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797 (2016).
