吉林大学学报(工学版)

• • 上一篇    下一篇

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

赵伟1,2;李文辉1;夏云飞2   

  1. 1.吉林大学 计算机科学与工程学院, 长春 130012; 2.长春工业大学 计算机科学与技术学院 长春 130012
  • 收稿日期:2007-02-18 修回日期:2007-04-18 出版日期:2008-05-01 发布日期:2008-05-01
  • 通讯作者: 李文辉

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

Zhao

Wei1,2;Li Wen-hui1;Xia Yun-fei2
  

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012,China; 2.College of Computer Science and Engineering, Chanchun University of Technology, Changchun 130012, China
  • Received:2007-02-18 Revised:2007-04-18 Online:2008-05-01 Published:2008-05-01

摘要:

为了提高碰撞检测算法的速度,提出用顶点的凸包表示凸多面体,将两个凸多面体间距离的问题归结为一个带约束条件的非线性规划问题,利用模拟退火遗传算法对该问题进行求解。利用模拟退火的接收准则进行交叉、变异,降低了时间复杂度。结果表明, 模拟退火遗传算法计算效率高、速度快。

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

Abstract: 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.

Key words: computer software, collision detection, convex polyhedron, nonlinear programming, anneal genetic algorithms

中图分类号: 

  • TP311.132
[1] 马健, 樊建平, 刘峰, 李红辉. 面向对象软件系统演化模型[J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[2] 罗养霞, 郭晔. 基于数据依赖特征的软件识别[J]. 吉林大学学报(工学版), 2017, 47(6): 1894-1902.
[3] 曲慧雁, 赵伟, 秦爱红. 基于优化算子的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[4] 应欢, 王东辉, 武成岗, 王喆, 唐博文, 李建军. 适用于商用系统环境的低开销确定性重放技术[J]. 吉林大学学报(工学版), 2017, 47(1): 208-217.
[5] 李勇, 黄志球, 王勇, 房丙午. 基于多源数据的跨项目软件缺陷预测[J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[6] 王念滨, 祝官文, 周连科, 王红卫. 支持高效路径查询的数据空间索引方法[J]. 吉林大学学报(工学版), 2016, 46(3): 911-916.
[7] 赵伟, 曲慧雁. 基于云计算Map-Reduce模型的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2016, 46(2): 578-584.
[8] 特日跟, 江晟, 李雄飞, 李军. 基于整数数据的文档压缩编码方案[J]. 吉林大学学报(工学版), 2016, 46(1): 228-234.
[9] 康辉, 王家琦, 梅芳. 基于Pi演算的并行编程语言[J]. 吉林大学学报(工学版), 2016, 46(1): 235-241.
[10] 陈鹏飞, 田地, 杨光. 基于MVC架构的LIBS软件设计与实现[J]. 吉林大学学报(工学版), 2016, 46(1): 242-245.
[11] 刘磊, 王燕燕, 申春, 李玉祥, 刘雷. Bellman-Ford算法性能可移植的GPU并行优化[J]. 吉林大学学报(工学版), 2015, 45(5): 1559-1564.
[12] 冯晓宁, 王卓, 张旭. 基于L-π演算的WSN路由协议形式化方法[J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[13] 李明哲, 王劲林, 陈晓, 陈君. 基于网络处理器的流媒体应用架构模型(VPL)[J]. 吉林大学学报(工学版), 2015, 45(5): 1572-1580.
[14] 王克朝, 王甜甜, 苏小红, 马培军. 基于频繁闭合序列模式挖掘的学生程序雷同检测[J]. 吉林大学学报(工学版), 2015, 45(4): 1260-1265.
[15] 黄宏涛,王静,叶海智,黄少滨. 基于惰性切片的线性时态逻辑性质验证[J]. 吉林大学学报(工学版), 2015, 45(1): 245-251.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!