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

王晓荣，王萌 ，李春贵

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

计算机工程与科学 >

2010 , Vol. 32 >Issue 4: 59 - 61

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

论文

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

展开

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

王晓荣（1978-），女，湖北当阳人，硕士，讲师，研究方向为虚拟现实和遗传算法；王萌，硕士，讲师，研究方向为自然语言处理、人工智能和数据库；李春贵，博士，副教授，研究方向为机器学习和智能系统。

收稿日期: 2009-03-26

修回日期: 2009-06-19

网络出版日期: 2010-03-28

基金资助

广西教育厅科研项目（200808LX341，200808LX338）；广西工学院基金项目（院科硕0816219，院科自08104202）

收起

Research of Collision DetectionAlgorithms Based on AABB

Expand

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

Received date: 2009-03-26

Revised date: 2009-06-19

Online published: 2010-03-28

Fold

摘要

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

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

本文引用格式

王晓荣，王萌，李春贵 . 基于AABB包围盒的碰撞检测算法的研究[J]. 计算机工程与科学, 2010 , 32(4) : 59 -61 . DOI: 10.3969/j.issn.1007130X.2010.

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

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract