学位论文 > 优秀研究生学位论文题录展示

基于AABB包围盒的文化粒子群碰撞检测算法的研究与实现

作　者: 李蒙
导　师: 童小念
学　校: 中南民族大学
专　业: 计算机应用技术
关键词: 虚拟现实碰撞检测 AABB包围盒粒子群算法文化算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2009年
下　载: 84次
引　用: 1次
阅　读: 论文下载

内容摘要

随着虚拟现实技术和仿真技术的兴起,快速、健壮的碰撞检测检测算法在虚拟现实、计算机游戏、计算机辅助设计等领域扮演着重要角色。在刚体对象的碰撞处理中,由于模型不会发生形变,所以其包围盒等关键数据都可以在预处理阶段处理完毕。对于软体对象即变形体对象,由于在移动时其对象顶点之间的相对位置要发生变化,导致包围盒不断发生改变,必须更新大量的数据以重构包围盒,而这种庞大的运算量在虚拟现实系统中会严重影响到系统的实时性。因此,优化碰撞检测算法的研究已成为虚拟现实领域的热点。粒子群优化算法是一种新型的群体智能算法,系统初始化为一组随机解,通过叠代搜寻最优值。文化粒子群算法则将粒子群算法融合到文化算法框架中,它在群体空间的基础上增加了一个知识空间,两个空间交互通信,以指导粒子的优化飞行,同时提高算法的收敛速度。为了提高碰撞检测的实时效率,本文提出了基于AABB包围盒的文化粒子群优化算法AABB-CAPSO。该算法首先利用AABB包围盒做粗略检测,如果变形体模型碰撞后发生形变,则利用文化粒子群算法进行精确的碰撞信息计算。本文将粒子群算法与文化算法相结合,组成基于粒子群算法的主群体空间和知识空间,两空间独立并行演化,下层主群体空间定期贡献优选个体给上层知识空间,上层知识空间经演化后,也定期贡献优选个体给下层主群体空间,这种“双演化双促进”机制避免了PSO可能因为“早熟”现象而陷入局部最优解,提高了AABB包围盒寻优更新数据的运算效率。本文的创新点在于将文化算法框架同粒子群算法相结合,基于AABB包围盒碰撞检测策略,提出了AABB-CAPSO检测算法。AABB-CAPSO基于文化算法框架,增加了粒子群算法的群体多样性,充分利用了历史信息,为后期的寻优过程提供了良好的指导。本文的实验结果表明,AABB-CAPSO算法提高了碰撞检测的实时效率,在虚拟仿真的应用中有实用价值。

全文目录

摘要  7-8
ABSTRACT  8-9
第1章绪论  9-11
  1.1 研究背景  9
  1.2 国内外研究现状  9
  1.3 本文结构  9-11
第2章层次包围盒方法  11-16
  2.1 层次包围盒方法基本原理  11
  2.2 包围盒的分类  11-13
    2.2.1 包围球  11-12
    2.2.2 AABB 包围盒  12-13
    2.2.3 OBB 包围盒  13
  2.3 构建层次包围盒树  13-14
  2.4 更新层次包围盒树  14-15
  2.5 算法比较  15-16
第3章文化粒子群算法  16-20
  3.1 粒子群优化算法  16-18
    3.1.1 基本PSO 模型  16-17
    3.1.2 引入惯性权重的PSO 模型  17
    3.1.3 引入收缩因子的PSO 模型  17-18
  3.2 文化算法  18-20
    3.2.1 文化算法简介  18-20
第4章基于AABB 包围盒的文化粒子群碰撞检测算法  20-31
  4.1 AABB-CAPSO 碰撞检测算法  20-25
    4.1.1 算法流程  20-21
    4.1.2 坐标变换及更新  21-22
    4.1.3 更新包围盒树  22-23
    4.1.4 文化粒子群算法  23-25
  4.2 模拟试验  25-31
    4.2.1 开发环境  25
    4.2.2 试验效果  25-31
总结与展望  31-32
参考文献  32-35
致谢  35-36
附录A 攻读学位期间所发表的学术论文目录  36

基于AABB包围盒的文化粒子群碰撞检测算法的研究与实现

内容摘要

全文目录

相似论文