一种高效的乐高模型自动构造算法  

An Automatic Construction Algorithm of Efficient LEGO Model

作　　者：周银瓶 邓仰东[1] 

机构地区：[1]清华大学微电子学研究所,北京100084

出　　处：《计算机工程》2016年第2期218-223,共6页Computer Engineering

基　　金：国家自然科学基金资助项目(20121302065-61272085)

摘　　要：现有的乐高（LEGO）模型自动构建算法依赖各种局部搜索机制优化构建结果,复杂度较高,在处理复杂、高分辨率模型时较为费时。为此,在归纳比较现有算法存在问题的基础上,提出一种高性能LEGO模型自动构造算法。采用自顶向下解决LEGO问题的方法,减小搜索空间,加快循环收敛。给出一种延迟构造图的方法,在预挖空后再构造竖直方向的图,缩短预挖空步骤的时间。实验结果表明,与现有算法相比,该算法能够在保持模型质量的前提下,对于大型、高分辨率的模型,可缩短50%-78%的构造时间,效率明显提高。Existing LEGO model automatic construction algorithms resort to stochastic optimization techniques to find the solution. Such approaches tend to be time-consuming when dealing with extremely large models. By generalizing and comparing existing research results,this paper proposes a highly efficient LEGO automatic construction algorithm. It devises a partition based top-down optimization flow,which significantly reduces the search space to speed up the arrival of convergence. It develops a delayed graph construction technique,which builds the vertical graph after pre-hollowing to expedite the pre-hollow ing process. Experimental results show that,compared with the existing algorithms,the algorithm reduces the total construction time by 50% - 78% and improves the efficiency.

关 键 词：三维快速原型 乐高建模 自动构造 自顶向下 预挖空 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]