? 基于关节约束的机械模型包装问题
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | Help
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2017, Vol. 32 Issue (6) :1162-1171    DOI: 10.1007/s11390-017-1791-2
Special Section of CAD/Graphics 2017 << Previous Articles | Next Articles >>
基于关节约束的机械模型包装问题
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 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
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 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

摘要
参考文献
相关文章
Download: [PDF 950KB]  
摘要 三维包装问题是装载给定的一组模型到不限体积的容器中,使得包装容器体积最小,它是著名的NP难问题.而在机械模型的包装问题中,由于机械零件之间存在机械关节的约束,所以使机械模型本身的空间利用率非常低.为了提高模型包装时的空间利用率,传统的静态模型的分割-包装算法[1-3]需要对机械零件进行多次切割,不仅会破坏零件原有设计,还可能影响零件使用寿命.本文提出一种新的基于关节自由度的机械模型包装算法,其根据机械模型中每个关节的自由度构造解空间,并建立拆分方案搜索树.通过利用搜索算法选取候选拆解方案,调整并优化机械关节参数,最终获取在最少次数的拆分条件下获得满足目标空间利用率的最优拆分方案.实验表明,该算法极大提高了三维机械模型的包装时的空间利用率,同时,相对其他算法有效降低了模型的拆分次数.
关键词NP难问题   装箱问题   搜索树     
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.
KeywordsNP-hard problem   packing problem   search tree     
Received 2017-06-26;
本文基金:

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.

通讯作者: Wei-Wei Xu     Email: 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.
引用本文:   
Ming-Liang Xu, Ning-Bo Gu, Wei-Wei Xu, Ming-Yuan Li, Jun-Xiao Xue, Bing Zhou.基于关节约束的机械模型包装问题[J]  Journal of Computer Science and Technology , 2017,V32(6): 1162-1171
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
链接本文:  
http://jcst.ict.ac.cn:8080/jcst/CN/10.1007/s11390-017-1791-2
Copyright 2010 by Journal of Computer Science and Technology