基于非线性规划理论的凸多面体最小平移距离算法  

A Minimum Translational Distance Algorithm of Convex Polyhedra Based on Nonlinear Programming Theory

作　　者：周之平[1] 张少博[1] 吴介一[1] 张飒兵[1] 

机构地区：[1]东南大学CIMS中心,南京210096

出　　处：《中国图象图形学报》2006年第10期1487-1493,共7页Journal of Image and Graphics

基　　金：江苏省自然科学基金重点项目(BK2001204)

摘　　要：凸多面体的最小平移距离问题一直以来都成为计算机图形学的一个研究热点。目前已有的距离算法在稳定性、可实现性、精确度和实现效率这几方面或多或少都存在一定的缺陷。为此,从最小平移距离定义出发,引入广义分离平面概念,提出一种用非线性规划求解距离问题的新算法。算法先定义一对最优广义分离平面以确定凸多面体最小平移距离;然后,将最优广义分离平面对的搜索问题等效变换为非线性规划问题;最后,用非线性优化工具软件对非线性规划问题进行求解,从而确定最小平移距离。实验结果表明:该算法能提供一个准确的距离值和实现向量,其性能优于其他同类算法;迭代次数与多面体的顶点数呈线性关系。此外,该算法只需提供顶点信息即可实现,求解过程中避免了死循环,故实现简单、可靠。因此,此算法是一种快速而有效的距离算法。The problem of minimum translational distance（ MTD for short） of convex polyhedra is always an active subfield of computer graphics. The current distance algorithms are deficient in such requirements as stability, realizability, accuracy and efficiency more or less. In order to overcome these limitations, the generalized separable plane is introduced based on the definition of MTD and a new algorithm of the MTD problem using nonlinear programming is presented in the paper. This algorithm is carried out as follow. Firstly, the MTD measure is determined by defining the optimal generalized separable plane-pair. Secondly, the problem of searching the optimal plane-pair is equivalent with nonlinear programming problem under some transforms. Finally, a nonlinear optimization software is used to solve the equivalent model, and therefore MTD measure is determined by the solution. The results show that the proposed algorithm performs linearly with the size of model and over the other algorithms in most of the tests. Besides, it can provide both an accurate measure and the witness vector in a few iterations, which are gently linear with the vertex number. In addition, the implementation is simple and reliable, because only the information of vertex is required and the cycle can be avoided. So, it is a fast and efficient distance algorithm.

关 键 词：凸多面体 最小平移距离 分离平面 实现向量 非线性规划 

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