›› 2017, Vol. 32 ›› Issue (6): 1162-1171.doi: 10.1007/s11390-017-1791-2

Special Issue: Computer Graphics and Multimedia

• Special Section of CAD/Graphics 2017 • Previous Articles     Next Articles

Mechanical Assembly Packing Problem Using Joint Constraints

Ming-Liang Xu1, Member, CCF, Ning-Bo Gu1, Wei-Wei Xu2,*, Member, ACM, Ming-Yuan Li1, Member, ACM, Jun-Xiao Xue3, Member, CCF, Bing Zhou1   

  1. 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
  • Received:2017-06-26 Revised:2017-10-13 Online:2017-11-05 Published:2017-11-05
  • Contact: Wei-Wei Xu E-mail:xww@cad.zju.edu.cn
  • 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.
  • Supported by:

    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.

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.

[1] Martello S, Pisinger D, Vigo D. The three-dimensional bin packing problem. Operations Research, 2000, 48(2):256-267.

[2] 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.

[3] Fanslau T, Bortfeldt A. A tree search algorithm for solving the container loading problem. INFORMS J. Computing, 2010, 22(2):222-235.

[4] Bortfeldt A. A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Computers & Operations Research, 2012, 39(9):2248-2257.

[5] Attene M. Shapes in a box:Disassembling 3D objects for efficient packing and fabrication. Computer Graphics Forum, 2015, 34(8):64-76.

[6] 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.

[7] Vanek J, Galicia J A, Benes B et al. PackMerger:A 3D print volume optimizer. Computer Graphics Forum, 2015, 33(6):322-332.

[8] 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.

[9] 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.

[10] 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.

[11] 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.

[12] Egeblad J, Pisinger D. Heuristic approaches for the twoand three-dimensional knapsack packing problem. Computers & Operations Research, 2009, 36(4):1026-1049.

[13] 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.

[14] 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.

[15] Crainic T G, Perboli G, Tadei R. Extreme point-based heuristics for three-dimensional bin packing. INFORMS J. Computing, 2008, 20(3):368-384.

[16] 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.

[17] Jiménez P, Thomas F, Torras C. 3D collision detection:A survey. Computers & Graphics, 2001, 25(2):269-285.

[18] Johnson D S. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 1974, 9(3):256-278.
No related articles found!
Full text



[1] Chen Yiyun;. Head Boundedness of Nonterminating Rewritings[J]. , 1995, 10(3): 281 -284 .
[2] Zhang Zhong;. Simulation of ATPG Neural Network and Its Experimental Results[J]. , 1995, 10(4): 310 -324 .
[3] WANG Xiaodong; XU Ming; ZHOU Xingming;. Fast Multicast on Multistage Interconnection Networks Using Multi-Head Worms[J]. , 1999, 14(3): 250 -258 .
[4] Wei-Sheng Si and Cheng-Zhi Li. RMAC: A Reliable MAC Protocol Supporting Multicast for Wireless Ad Hoc Networks[J]. , 2005, 20(5): 702 -712 .
[5] Yong-Dong Zhang, Sheng Tang, and Jin-Tao Li. Secure and Incidental Distortion Tolerant Digital Signature for Image Authentication[J]. , 2007, 22(4): 618 -625 .
[6] You-Jian Zhao, Zu-Hui Yue, and Jian-Ping Wu. Research on Next-Generation Scalable Routers Implemented with H-Torus Topology[J]. , 2008, 23(4 ): 684 .
[7] Kwangjin Park and Hyunseung Choo. Location-Based Data Dissemination for Spatial Queries in Wireless Broadcast Environments[J]. , 2010, 25(2): 330 -346 .
[8] Bin Wang, Member, CCF, Xiao-Chun Yang, Senior Member, CCF, Member ACM, IEEE, Guo-Ren Wang, Senior Member, CCF, Member, ACM, IEEE, and Ge Yu, Senior Member, CCF, Member, ACM, IEEE. Outlier Detection over Sliding Windows for Probabilistic Data Streams[J]. , 2010, 25(3): 389 -400 .
[9] Benjamín Sahelices, Agustín de Dios, Pablo Ibáñez, Member, IEEE, Víctor Viñals-Yúfera, Member, ACM, IEEE, and José María Llabería. Efficient Handling of Lock Hand-off in DSM Multiprocessors with Buffering Coherence Controllers[J]. , 2012, 27(1): 75 -91 .
[10] Ke-Yan Cao, Guo-Ren Wang, Dong-Hong Han, Guo-Hui Ding, Ai-Xia Wang, and Ling-Xu Shi. Continuous Outlier Monitoring on Uncertain Data Streams[J]. , 2014, 29(3): 436 -448 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved