基于AABB包围盒的碰撞检测算法的研究

doi:10.3969/j.issn.1007130X.2010.

J4 ›› 2010, Vol. 32 ›› Issue (4): 59-61.doi: 10.3969/j.issn.1007130X.2010.

基于AABB包围盒的碰撞检测算法的研究

王晓荣，王萌，李春贵

(广西工学院计算机工程系，广西柳州 545006)

收稿日期:2009-03-26 修回日期:2009-06-19 出版日期:2010-03-28 发布日期:2010-03-28
通讯作者: 王晓荣 E-mail:ccnuxnxs@163.com
作者简介:王晓荣（1978-），女，湖北当阳人，硕士，讲师，研究方向为虚拟现实和遗传算法；王萌，硕士，讲师，研究方向为自然语言处理、人工智能和数据库；李春贵，博士，副教授，研究方向为机器学习和智能系统。
基金资助:
广西教育厅科研项目（200808LX341，200808LX338）；广西工学院基金项目（院科硕0816219，院科自08104202）

Research of Collision DetectionAlgorithms Based on AABB

WANG Xiaorong，WANG Meng,LI Chungui

(Department of Computer Engineering,Guangxi University of Technology,Liuzhou 545006,China)

Received:2009-03-26 Revised:2009-06-19 Online:2010-03-28 Published:2010-03-28
Contact: WANG Xiaorong E-mail:ccnuxnxs@163.com

摘要/Abstract

摘要： 利用虚拟空间中对象运动的特性和AABB包围盒的构造特性，改进了基于AABB层次包围盒的碰撞检测算法。传统的该类算法分为两个检测过程，在初步检测过程中，基于运动对象碰撞行为的局部性，改进了原来的排序方法，采用希尔排序。为了提高检测效率，在相交测试之前将检测对象细分，划分测试区域，避免了不必要的相交测试；在对可能相交的对象进行精确检测过程中，基于AABB包围盒的构造特性，对可能碰撞对象的层次包围盒树进行压缩存储，通过减少算法的存储空间来提高算法的检测速度。对算法的两个检测过程同时进行改进，实验表明在检测对象较多的情况下减少了算法所需的执行时间。

关键词: 碰撞检测, 包围盒树, 相交测试, 希尔排序, 压缩存储

Abstract: An improved collision detection algorithm based on AABB is presented. Collision is a local behavior, during the sorting procedure, each axis is cut into a series of segments containing the same number of projection intervals. This will avoid needless intersecting test of AABB.And Shell sorting is adopted. Then the storage of the AABB tree is compressed.This way can save a large amount of space and speed up the algorithm.

Key words: collision detection;boundingbox tree;intersecting test;Shell sorting;memoryoptimized

中图分类号:

TP391.9

王晓荣，王萌，李春贵. 基于AABB包围盒的碰撞检测算法的研究[J]. J4, 2010, 32(4): 59-61.

WANG Xiaorong，WANG Meng,LI Chungui. Research of Collision DetectionAlgorithms Based on AABB[J]. J4, 2010, 32(4): 59-61.

编辑推荐

Metrics

阅读次数

全文

139

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	0	0	139

来源	本网站	其他网站

次数	51	88
比例	37%	63%

摘要

117

最新录用	在线预览	正式出版

0	0	117

[1]	杨晋生，赵月秋，邱光染，陈为刚. 一种改进的射线跟踪路径搜索算法[J]. 计算机工程与科学, 2017, 39(11): 2049-2053.
[2]	刘敏1，熊岳山1，谭珂2，潘新华2. 基于改进碰撞检测算法的肝门静脉结扎仿真[J]. 计算机工程与科学, 2017, 39(01): 151-157.
[3]	魏巍1,2，郭晨1，段晓东2. 虚拟装配中基于公差约束的装配方法研究[J]. J4, 2013, 35(6): 162-173.
[4]	郑延斌, 郭凌云, 刘晶晶. 基于混合包围盒的碰撞检测优化算法[J]. 计算机工程与科学, 2013, 35(4): 87-92.
[5]	胡咏梅. 基于层次包围盒的混合碰撞检测算法[J]. J4, 2012, 34(6): 127-130.
[6]	申静波唐国维李井辉. 基于夹边边对的凸多边形间快速相交检测算法[J]. J4, 2007, 29(12): 93-94.
[7]	熊玉梅陈一民林锋. 任意多面体的剖分算法及应用[J]. J4, 2004, 26(9): 57-61.
[8]	李超陈一民等. JAVA 3D与VRML在机器人仿真和碰撞检测中的应用[J]. J4, 2002, 24(5): 83-85.
[9]	魏迎梅[1] 吴泉源[2] 等. 虚拟环境中的碰撞检测方法[J]. J4, 2001, 23(2): 44-47.

基于AABB包围盒的碰撞检测算法的研究

Research of Collision DetectionAlgorithms Based on AABB

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 9

编辑推荐

Metrics

本文评价