1 School of Information Engineering, Zhengzhou University, Zhengzhou 450000, China;
2 State Key Laboratory of Computer Aided Design and Computer Graphics, Zhejiang University, Hangzhou 310058, China;
3 School of Software, Zhengzhou University, Zhengzhou 450000, China
Abstract The three-dimensional packing problem is generally on how to pack a set of models into a given bounding box using the smallest packaging volume. It is known as an NP-hard problem. When discussing the packing problem in mechanical field, the space utilization of a mechanism is low due to the constraint of mechanical joints between different mechanical parts. Although such a situation can be improved by breaking the mechanism into components at every joint, it burdens the user when reassembling the mechanism and may also reduce the service life of mechanical parts. In this paper, we propose a novel mechanism packing algorithm that deliberately considers the DOFs (degrees of freedom) of mechanical joints. With this algorithm, we construct the solution space according to each joint. While building the search tree of the splitting scheme, we do not break the joint, but move the joint. Therefore, the algorithm proposed in this paper just requires the minimal number of splits to meet the goal of space utilization. Numerical examples show that the proposed method is convenient and efficient to pack three-dimensional models into a given bounding box with high space utilization.
The work was supported by the National Key Research and Development Program of China under Grant No. 2017YFC0804401, the National Natural Science Foundation of China under Grant Nos. 61472370, 61672469, 61379079, 61322204, and 61502433, the Natural Science Foundation of Henan Province of China under Grant No. 162300410262, and the Key Research Projects of Henan Higher Education Institutions of China under Grant No. 18A413002.
About author: Ming-Liang Xu is a professor in the School of Information Engineering,Zhengzhou University,Zhengzhou,and currently is the director of CⅡSR (Center for Interdisciplinary Information Science Research).His research interests include computer graphics and computer vision.Xu got his Ph.D.degree in computer science and technology,Zhejiang University,Hangzhou,in 2011.
Cite this article:
Ming-Liang Xu, Ning-Bo Gu, Wei-Wei Xu, Ming-Yuan Li, Jun-Xiao Xue, Bing Zhou.Mechanical Assembly Packing Problem Using Joint Constraints[J] Journal of Computer Science and Technology, 2017,V32(6): 1162-1171
 Martello S, Pisinger D, Vigo D. The three-dimensional bin packing problem. Operations Research, 2000, 48(2):256-267. Bansal N, Han X, Iwama K, Sviridenko M, Zhang G. A harmonic algorithm for the 3D strip packing problem. SIAM Journal on Computing, 2013, 42(2):579-592. Fanslau T, Bortfeldt A. A tree search algorithm for solving the container loading problem. INFORMS J. Computing, 2010, 22(2):222-235. Bortfeldt A. A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Computers & Operations Research, 2012, 39(9):2248-2257. Attene M. Shapes in a box:Disassembling 3D objects for efficient packing and fabrication. Computer Graphics Forum, 2015, 34(8):64-76. Chen X, Zhang H, Lin J, Hu R, Lu L, Huang Q, Benes B, Cohen-Or D, Chen B. Dapper:Decompose-and-pack for 3D printing. ACM Trans. Graph., 2015, 34(6):213:1-213:12. Vanek J, Galicia J A, Benes B et al. PackMerger:A 3D print volume optimizer. Computer Graphics Forum, 2015, 33(6):322-332. Kim K Y, Manley D G, Yang H. Ontology-based assembly design and information sharing for collaborative product development. Comput. Aided Des., 2006, 38(12):1233-1250. Mitra N J, Yang Y L, Yan D M, Li M, Agrawala M. Illustrating how mechanical assemblies work. Commun. ACM, 2013, 56(1):106-114. Xu M, Li M, Xu W, Deng Z, Yang Y, Zhou K. Interactive mechanism modeling from multi-view images. ACM Trans. Graph., 2016, 35(6):236:1-236:13. Coros S, Thomaszewski B, Noris G, Sueda S, Forberg M, Sumner M, Matusik W, Bickel B. Computational design of mechanical characters. ACM Trans. Graph., 2013, 32(4):83:1-83:12. Egeblad J, Pisinger D. Heuristic approaches for the twoand three-dimensional knapsack packing problem. Computers & Operations Research, 2009, 36(4):1026-1049. Wu Y, Li W, Goh M, de Souza R. Three-dimensional bin packing problem with variable bin height. European Journal of Operational Research, 2010, 202(2):347-355. Gomes A M, Oliveira J F. Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 2006, 171(3):811-829. Crainic T G, Perboli G, Tadei R. Extreme point-based heuristics for three-dimensional bin packing. INFORMS J. Computing, 2008, 20(3):368-384. Morales J L, Nocedal J. Remark on algorithm 778:LBFGS-B:Fortran subrou tines for large-scale bound constrained optimization. ACM Trans. Math. Softw., 2011, 38(1):7:1-7:4. Jiménez P, Thomas F, Torras C. 3D collision detection:A survey. Computers & Graphics, 2001, 25(2):269-285. Johnson D S. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 1974, 9(3):256-278.
Copyright 2010 by Journal of Computer Science and Technology