基于非线性规划的凸多面体间碰撞检测算法  

Research on convex polyhedron collision detection algorithm based on non-linear programming

作　　者：赵伟[1] 李文辉[1] 夏云飞[2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]长春工业大学计算机科学与工程学院长春,130012

出　　处：《吉林大学学报（工学版）》2008年第3期676-679,共4页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(60573182);高等学校博士学科点专项科研基金项目(20060183042);吉林省科技发展计划项目(20060527,20040531)

摘　　要：为了提高碰撞检测算法的速度,提出用顶点的凸包表示凸多面体,将两个凸多面体间距离的问题归结为一个带约束条件的非线性规划问题,利用模拟退火遗传算法对该问题进行求解。利用模拟退火的接收准则进行交叉、变异,降低了时间复杂度。结果表明,模拟退火遗传算法计算效率高、速度快。To increase the running speed of the collision detection algorithm, a new approach is proposed, which uses convex Bounding Volume Hierarchies （BVHs） to express convex polyhedron. Thus the distance problem of two convex polyhedrons is come down to a non-linear programming problem with constraints. The non-linear programming problem can be solved by simulated annealing genetic algorithm. Applying the acceptance criterion of the simulated annealing genetic algorithm, intersection and variation are carried out to optimize the time complexity. Results show that the efficiency of the simulated annealing genetic algorithm is high and the computing speed is faster.

关 键 词：计算机软件 碰撞检测 凸多面体 非线性规划 模拟退火遗传算法 

分 类 号：TP311.132[自动化与计算机技术—计算机软件与理论]