基于AABB包围盒的碰撞检测算法的研究[D].pdfVIP

　CN431258/ TP 　　　　计算机工程与科学 20 10 年第 32 卷第 4 期 　 　ISSN 1007130X COM PU T ER EN GIN EER IN G SCIEN CE 　Vol32 ,No4 ,20 10 　 ( ) 文章编号 :1007130X 20 10 基于 A ABB 包围盒的碰撞检测算法的研究 Re search of Colli sio n Det ectio n Al go rit h m s Ba sed o n A ABB 王晓荣 ,王 　萌 ,李春贵 WANG Xiaorong , WANG Meng ,L I Chungui ( 广西工学院计算机工程系 ,广西 柳州 545006) ( Department of Computer Engineering , Guangxi University of Technology ,Liuzhou 545006 , China) 摘 　要 :利用虚拟空间中对象运动的特性和 AABB 包围盒的构造特性 ,改进了基于 AABB 层次包围盒的碰撞检测算 法 。传统的该类算法分为两个检测过程 ,在初步检测过程中 ,基于运动对象碰撞行为的局部性 ,改进了原来的排序方法 ,采 用希尔排序 。为了提高检测效率 ,在相交测试之前将检测对象细分 ,划分测试区域 ,避免了不必要的相交测试 ;在对可能相 交的对象进行精确检测过程中 ,基于 AABB 包围盒的构造特性 ,对可能碰撞对象的层次包围盒树进行压缩存储 ,通过减少 算法的存储空间来提高算法的检测速度 。对算法的两个检测过程同时进行改进 ,实验表明在检测对象较多的情况下减少 了算法所需的执行时间。 Abstract :An imp roved colli sion det ection algorit hm based on AABB i s p resent ed . Colli sion i s a local behavior , during t he sorting p rocedure , each axi s i s cut into a series of segment s cont aining t he same number of p roj ection int erval s. Thi s will avoid needless int er secting t est of AABB . And Shell sorting i s adop t ed . Then t he storage of t he AABB t ree i s com p ressed . Thi s way can save a lar ge amount of sp ace and sp eed up t he algorit hm . 关键词 :碰撞检测 ;包围盒树 ;相交测试 ;希尔排序 ;压缩存储 Key words :colli sion det ection ;boundingbox t ree ;int er secting t est ; Shell sorting ;memoryop timized doi :10 . 3969/ j . i ssn . 1007130X. 20 10 . 04 . 0 17 中图分类号 : TP39 1. 9 文献标识码 :A