三维不规则图形快速布局方法研究

布局问题亦被称为排样问题，是指将一系列图形互不交叠地放置在给定容器内，并使得未被覆盖的区域尽量小。布局问题的求解以计算复杂度高著称，但鉴于其广泛的应用领域，一直以来是研究人员关注的基础和热点问题。现有的研究方法主要集中在平面简单图形的布局问题，对于复杂三维不规则图形的布局问题仍缺少高效的解决方法。本项目聚焦三维不规则图形布局问题，允许图形具有连续的旋转自由度，拟提出复杂三维图形的简化表示方法，并设计基于“生长”模型的快速启发式方法进行高效求解。我们方法将克服不规则图形复杂几何表达和计算上的困难，充分利用图形在位置和旋转上的自由度，解决庞大的连续可行解空间内的搜索难题，快速给出高质量的布局结果。项目前期的实验结果已经初步表明本项目方法的可行性。本项目研究将提供平面、曲面和三维空间内图形布局问题的统一快速解决框架，有望应用于计算机辅助设计与图形学等多个领域问题，具有重要的理论和实际应用价值。

The packing problem is to place objects in a non-overlapping configuration within a given container to make full use of the space. It is notorious for its high computational complexity. However, due to its wide variety of practical applications, it has attracted widespread interest. Existing research is mainly focused on packing relatively simple 2D shapes. Efficient packing methods for more complex 3D shapes are still lacking. In this project, we will focus on irregular shape packing problems in 3D space, where the objects can be of any shapes and allowed to rotate freely. We propose a simplification method for representing complex 3D shapes, and a “growth” based heuristic method for efficiently packing irregular objects. Our method will be able to overcome difficulties in representation and computation of complex geometries, and generate high-quality packing results by making full use of the degrees of freedom in translation and rotation and efficiently searching in the large solution space. Our preliminary experimental results have shown the feasibility of the proposed method. The study of this project will provide a unified framework for packing problems on planes, surfaces, and in 3D domains. It has a promising prospect in various areas such as computer-aided design and computer graphics, and has great values on both theory and practice.