tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 物理 >>

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


CN43—1258/TP
ISSN 1007—130X

计算机工程与科学
CA)MPUTER ENGINEERING&SCIENCE

2010年第32卷第4期
VoL 32,No.4。2010

文章编号:1007-130X(2010)04-0059-03

基于AABB包围盒的碰撞检测算法的研究。
Research of Collision Detection Algorithms Based
on

AABB

王晓荣。王萌。李春贲 WANG Xiao-rong。WANG Meng。LI
Chun-gui

(广西工学院计算机工程系。广西柳州545006) (Deimrlment
of

Computer Engineering。Guangxi University of Technology,Liuzhou 545006。China)

摘要:利用虚拟空间中对象运动的特性和AABB包围盒的构造特性。改进了基于AAJBB层次包围盒的碰撞检测算 法。传统的该类算法分为两个检测过程,在初步检测过程中,基于运动对象碰撞行为的局部性,改进了原来的排序方法,采 用希尔排序。为了提高检测效率,在相交测试之前将检测对象细分,划分测试区域,避免了不必要的相交测试;在对可能相 交的对象进行精确检测过程中,基于AABB包围盒的构造特性,对可能碰撞对象的层次包围盒树进行压缩存储,通过减少 算法的存储空间采提高算法的检测速度。对算法的两个检测过程同时进行改进,实验表明在检测对象较多的情况下减少 了算法所需的执行时间。
Abstract:An improved collision detection algorithm based the sorting procedure,each axis is will avoid needless pressed.This way
cut on

AABB is presented.Collision is



local behavior。during
is tom-

into



series of segments containing the

s锄e

number of projeetion intervals.This
tree

intersecting
can
save a

test

of AABB.And Shell sorting is adopted.Then the storage of the AABB

large amount of space and speed up the algorithm.

关键词:碰撞检测;包围盒树;相交测试;希尔排序;压缩存储
Key words:collision

detection;bounding-box

tree;intersecting test;Shell

sorting;memory-optimized

doi:10.3969/j.issn.1007—130X.2010.04.017 中图分类号:TP391.9 文献标识码:A

ding

Box,简称从髓)、球包围盒(Sphere)、方向包围盒
Orientation Polytopes,简称Dops)。



引言
快速而精确的碰撞检测是虚拟现实的一项关键技术。

0BB(Oriented Bounding Box,简称OBB)和k-Dops(Dis—
crete

丸址B包围盒在碰撞检测的研究历史中使用得最久最
广。它平行于空问坐标,构造简单,同时适用于刚体和软体 的碰撞检测。基于AAJ3B的层次包围盒碰撞检测算法的 执行速度主要受三个方面的影响:AABB包围盒间的相交 测试、AABB树的遍历和基本几何元素的相交测试。为了 提高算法的执行速度,潘振宽等[2]对AABB包围盒进行了

虚拟环境和虚拟对象的几何复杂度及实时性要求使得碰撞 检测的计算复杂度大大提高。碰撞检测模块需要占用相对 多的存储空间和处理时间。在保证要求的精确性的情况 下,碰撞检测算法采用了一系列方法来提高检测速度。例 如,层次包围盒方法利用近似的几何体代替原物体,可以很 快排除不相交的物体,只有当包围盒发生碰撞时才检测两 个物体之间的几何元素之间的碰撞情况,提高了检测速度。 包围盒类型的选择是层次包围盒方法的关键,对用于 碰撞检测的包围盒一般受简单性和紧密性的约束[1]。常用 的包围盒类型有轴对齐包围盒AABB(Axis-Aligned Boun-

压缩存储,减少了存储姻树所需的内存空间;Li
测算法,减少算法所需的内存空间,提高检测速度。

C F

等【3]对AABB的相交测试进行了优化。本文将结合上述 改进方法来优化传统的基于AABB层次包围盒的碰撞检

基拿堕县:广西熬育厅科研琢目1200;!墨IⅨ311.200.80.8LX3.38)}广西工学院基金项目(院科硕0816219,院科自08104202) ~。 。。。。。… 作童简.介!王睦苤99…78..-):交,塑托当阳1厶。:惩t:.讲师,研窑.方向为虚拟现实和遗传算法;王萌。硕士,诉师,研究方向为自然语言

通讯地址:545006广西柳州市广西工学院计算机工程系;Tel:13407869066;E-mail:cL-nugnxs(园163.c咖 A躺:Department
of Computer Engineering,Guangxi University of Technology,Liuzhou,Guangxi

处理、人工智能和数据摩;李春贵,博上,副教授,研究方向为机器学习和智能系绣。。

545006,P.R China

万方数据  

但是,需要注意的是,坐标轴划分方法虽然被认为是一

2改进算法
2.1算法描述
假设虚拟场景中有挖个对象,由于包围盒间的相交测 试比对象间的相交测试简单,所以为每个对象构造其 AABB包围盒,通过包围盒问的相交测试快速排除不可能 相交的对象对;再对町能相交的对象采用自上而下的方法 构造其层次包围盒即AABB包围盒树,通过遍历包围盒树 找到叮能相交的叶节点,对叶节点包含的几何元素进行精 确的相交测试,从而判断对象对是否发生碰撞。AABB包 围盒的相交测试速度决定了算法在初步检测阶段的时间耗 费,本文基于对象运动的时空相关性改进了AABB相交测 试的方法,同时基于AABB包围盒的数学特性,算法在精 确检测阶段根据包围盒树的构造方法来压缩存储包围盒 树,减少算法所需内存。提高算法的检测速度。

个相等划分策略,但却不同于空间划分方法。传统的空间 划分方法划分一个仿真空间为相等大小的单元,然而对所 有的虚拟空间而言无法选择一个最好的划分尺寸。坐标轴 划分考虑的是对象而不是空间。
2.3

AABB树的存储改进
将对象的整体AABB包围盒作为其平衡二叉树的根

2.3.1建立平衡的AABB树
节点,此节点包含了组成该对象的所有三边形。采用如下 方法递归地对每个节点操作,直到叶节点只包含规定数目 的三角形:(1)采用基于分裂平面[4】的方法将根节点的 AABB包围盒划分成左右两个子节点。(2)分裂平面的选 择是使AABB包围盒树平衡的关键,首先确定分裂轴,使 用最长轴方法,即选择的方向轴是AABB在此方向上最长 的;而后确定分裂点,选择根节点集合中所有基本几何元素 的中心点在分裂轴上的投影,以最小点和最大点为两个中 心点,按距离将所有投影点分为两组。将距离中心点等距 的点归入含投影点少的一组。建立平衡的AABB树提高

2.2丸气BB的相交测试改进
在全局搜索阶段,用AABB包围盒来近似每个对象, 通过对AABB包围盒间的相交测试可以快速确定可能相 交的对象对。两个AABB包围盒相交当且仅当它们在三 个坐标轴上的投影区段都有重叠,所以这里将AABB包围 盒的相交测试转化到一维空间来解决,通过对AABB包围 盒在z、Y、z三个坐标轴上的投影排序来确定相交的 AABB包围盒。传统算法如I-Collide算法中对投影序列采 用的是插入排序法,本文采用希尔排序并对排序过程进行 了改进。 在排序过程中先将每个坐标轴划分为一系列包含相同 数目投影区间的子段。当每个坐标轴上的投影区间数不能 等值划分时,使得最后一个子段的投影区间数小于前面的 子段含有的投影区间数。例如,在某个坐标轴上有70个投 影区间,需要划分为4个子段,则前3个子段含有20个投 影区间,第4个子段含有lO个投影区间。一般来说,坐标 轴划分得越细,算法的执行速度将越快。但是,不能无限制 地划分下去,在一个方向上一个AABB包围盒只能被划分 一次。图1中对象N被划分了两次,则中间斜线阴影部分 将不会参与碰撞检测。而且在实际应用中,一般也不需要 通过细分坐标轴来提高算法的执行性能。如果在应用中碰 到了体积非常大的对象,在执行碰撞检测之前算法也会通 过预处理过程将对象划分为一些体积较小的部分,以方便 算法的执行。进行坐标轴划分后,重叠测试将被限制在每 个子段里进行,这样相距较远的对象之间就不会互相影响, 从而减少了需要进一步进行碰撞检测的对象对数。

了遍历A_搬j树的效率。
2.3.2叶结点的压缩存储
文献I-zq对AABB树中的内部节点进行了存储压缩, 减少了存储AABB树所需的字节数。本文在此基础上进 一步对AABB树的叶结点进行压缩存储,减少算法的执行

时间和存储空间。
AABB树叶节点的常规存储结构包括AABB包围盒 信息和三角形索引两个域。应用M611er[乳6]提出的快速三 角形与三角形相交测试和快速三角形与包围盒相交测试算 法,两个测试对象的AABB树重叠测试过程中涉及到叶节 点的重叠测试都可以不用到包围盒信息而直接用三角形进 行测试,这样就可以从叶节点的存储结构中删去包围盒信 息。叶节点的存储结构中只有三角形的索引信息,此时就 不必再用一个独立的节点表示叶节点。将三角形索引存放 到父节点中,从包围盒树的存储空间中删除叶节点。叶节 点的三角形索引在父节点中存放时不需要为父节点分配额 外的存储空间,直接替换父节点的孩子索引域为孩子叶节 点的三角形索引信息。此时,叶节点的父节点结构如表1 所示。表1中标志位的最后两位取值为l,表示其左右孩 子节点均为叶节点。
表1叶节点的父节点结构

左子节点 三角形索引 (4个字节)

右子节点 三角形索引 (4个字节)

标志位(1个字节)

一棵含有N个叶节点的完全AABB树共有2*N一1 个节点,存储AABB树时不需要为叶节点分配存储空间,

则相当于从包围盒树的节点中删掉了一半的节点。这样大
大节省了存储空间,减少了一半的内存需求。

3实验结果
图1轴划分的限制 我们在PC机上进行了实验,输人数据是包含不同数
60

万方数据  

量的模型。对应该类检测算法的两个阶段分别用常用算法 和改进的算法进行测试。初步检测阶段对AABB包围盒 的相交测试实验对比结果如图2所示,精确检测阶段对 AABB树的遍历实验对比结果如图3所示。

[4]泥宗涛,余英林.基于分层包围盒的连续碰撞检测加速算法
口].计算机工程与应用,2000。36(10):24—26.

[5]Tomas M A Fast Triangle-Triangle [6]Tomas M Fast

Intersection

Test[J].

Journal of Graphics Tools,1997,2(2):25—30. 3D Tfiangle-Box Overlap

TestingD].Journal

of Graphics Tools,2002,6(1):29—33.

(上接第54页)

AABB总数(个)

7结束语
本文给出了一类可调控的三次多项式曲线,该曲线具 有如下特点: (1)是二次B6.zier曲线的扩展,具有诸多与二次B6zier 曲线相似的性质。 (2)当两个形状参数在取值范围内取不同值时,可得 到一组形状不同的曲线,方便设计不同形状的曲线。

图2

AABB排序方法的比较



嚣 掣 鞭 翟



三角面片总数(个) 图3叶节点存储优化前后算法性能比较

(3)在控制顶点不变时,可通过修改两个形状参数对 整条拼接的曲线进行局部或全局调节,从而使曲线具有了 更强的表现能力。为自由曲线设计提供了一种有效的方法。 (4)由于带有两个形状参数,使得在设计曲线时更方 便、更自由。 与二次B6zier曲面类似,可构造张量积曲面,该曲面是 双二次B邑zier曲面的扩展,它不仅具有双二次B6zier曲面 类似的性质,而且其形状是可调的,限于篇幅。将另文讨论。

从图2可以看出,使用改进后的排序方法能提高

从雎相交测试的速度。由于对象运动的时空相关性,对
下一个时间采样点而言,当前时间采样点得到的排序序列 可以认为是几乎排好序的序列,即AABB的一维投影排序 列表在两个时间采样点的改变是微小的。而希尔排序对一 个近乎排好序的输入,能够达到0(N)的速度,同时也比插

入排序要强健。排序前坐标轴的划分也避免了对不必要对
象的相交测试。 从图3可以看出,在为对象构造包围盒树进行精确检 测时,压缩存储内部节点的同时对叶节点进行存储优化,加 快了对树的遍历,节省了存储空间,且没有增加额外的时问 消耗,提高了算法的执行速度。当检测对象较少时,改进方

参考文献:
[1]
B6zier P.The

Mathematical Basis of the UNISURF CAD

System[M].England:Butterworths,1986111—72.

[2]Pottmarm H,Wangner M G.Helix Splines邪an
Affine Tchebycheffian tional

Example of

法所需的检测时间并无明显的减少,但当检测对象或者说
对象所包含的基本几何元素(三角面片)较多时,改进方法 所需的检测时间明显减少。

Splines[J].Advances in Computa-

Mathematics,1994,2(1):123—142.



[3]Pieg
[4]

L.Triller

The NURBS

Book[M].2nd

ed.Berlinl

Springer。1997

141—188.

4结束语
本文改进了基于AABB层次包围盒的碰撞检测算法。 利用改进的排序方法可以快速对对象的AABB包围盒进 行相交测试,从大量对象中筛选出可能相交的对象对;在此

Mamar E,Pefia
ternatives
to

J M。S曲ch凹一Reye吾J.Shape Preserving A1一

the Rational B6zier

ModdEJ].Computer Aided

Geometric Design,2001,18(1):37-60.

[5]齐从谦,邬弘毅.一类可调控B6.zier曲线及其逼近性口].湖
南大学学报(自然科学版)。1996,19(1):15?19.

[6]殷明.刘丽,陈国琪。一类可调控的G1连续分段三次多项式 曲线[J].安徽农业大学学报。2005。32(2):258-262. [7]韩旭里,刘圣军.二次B6zier曲线的扩展[J].中南工业大学
学报(自然科学版),2003,34(2):214—217.

基础上,对可能相交的对象构造平衡的从耶树,一定程
度上减少遍历AABB树所需的时间,然后对AABB树的节 点进行压缩存储,减少了算法所需的内存空间,同时也加快 了算法的执行速度。

[8]吴晓勤,韩旭里.三次l抛ielr曲线的扩展[J].工程图学学报,
2005,26(6):98-102.

参考文献:
11]魏迎梅,王涌,吴泉源。等.碰撞检测中的固定方向凸包包围
盒的研究[J].软件学报,2001.12(7):1056—1063.

[9]吴晓勤.带形状参数的B∈zier曲线[J].中国图象图形学报,
2006。11(2):269—274.

[10]胡钢,秦新强,刘哲,等.B包ier曲线的新扩展[J].计算机工
程,2008,34(12):64—66.

[2]潘振宽,李建波.基于压缩的AABB树的碰撞检测算法[J].
计算机科学,2005,33(2):213-215.

[11]莫蓉,常智勇.计算机辅助几何造型技术[M].北京:科学出
版社,2004.

[3]Lj

C F,Feng Y T,Owen D R
on

J.SMB:Collision Detection
in Ap-

Based plied 2269.

Temporal

Coherence口].Computer Methods

Mechanics and Engineering。2006,195(19-22):2252-

61

万方数据  

基于AABB包围盒的碰撞检测算法的研究
作者: 作者单位: 刊名: 英文刊名: 年,卷(期): 被引用次数: 王晓荣, 王萌, 李春贵, WANG Xiao-rong, WANG Meng, LI Chun-gui 广西工学院计算机工程系,广西,柳州,545006 计算机工程与科学 COMPUTER ENGINEERING AND SCIENCE 2010,32(4) 13次

参考文献(6条) 1.魏迎梅;王涌;吴泉源 碰撞检测中的固定方向凸包包围盒的研究[期刊论文]-软件学报 2001(07) 2.潘振宽;李建波 基于压缩的AABB树的碰撞检测算法[期刊论文]-计算机科学 2005(02) 3.Li C F;Feng Y T;Owen D R J SMB:Collision Detection Based on Temporal Coherence 2006(19-22) 4.泥宗涛;余英林 基于分层包围盒的连续碰撞检测加速算法[期刊论文]-计算机工程与应用 2000(10) 5.Tomas M A Fast Triangle-Triangle Intersection Test 1997(02) 6.Tomas M Fast 3D Triangle-Box Overlap Testing 2002(01)

本文读者也读过(10条) 1. 高玉琴.何云峰.于俊清.GAO Yu-qin.HE Yun-feng.YU Jun-qing 改进的基于AABB包围盒的碰撞检测算法[期刊论 文]-计算机工程与设计2007,28(16) 2. 王晓荣 基于AABB包围盒的碰撞检测算法的研究[学位论文]2007 3. 王立文.刘璧瑶.韩俊伟.WANG Li-wen.LIU Bi-yao.HAN Jun-wei 一种改进AABB包围盒的碰撞检测算法[期刊论文 ]-计算机工程与应用2007,43(33) 4. 陈振华.丑强.杨慧贤 碰撞检测中AABB包围盒以及基本几何元素问的相交测试[期刊论文]-中国科技博览 2008(19) 5. 王晓荣.金汉均.王萌.WANG Xiao-rong.JIN Han-jun.WANG Meng 基于AABB树的碰撞检测算法的内存优化[期刊论 文]-计算机工程与设计2008,29(1) 6. 刘渊.贾渊.姚博.刘薇.LIU Yuan.JIA Yuan.YAO Bo.LIU Wei 一种改进的AABB包围盒树更新算法[期刊论文]-兵 工自动化2008,27(12) 7. 金汉均.王晓荣.王萌.JIN Han-jun.WANG Xiao-rong.WANG Meng 基于层次包围盒的碰撞检测算法的存储优化[期 刊论文]-计算机工程与应用2007,43(16) 8. 郑旭 三维物体碰撞检测包围盒算法分析[期刊论文]-现代商贸工业2010,22(2) 9. 李蒙 基于AABB包围盒的文化粒子群碰撞检测算法的研究与实现[学位论文]2009 10. 陶阳 自定义的AABB碰撞检测算法[期刊论文]-电脑编程技巧与维护2010(21)

引证文献(13条) 1.胡咏梅 基于层次包围盒的混合碰撞检测算法[期刊论文]-计算机工程与科学 2012(6) 2.王萌 基于动态包围盒树的碰撞检测算法研究[期刊论文]-华中师范大学学报(自然科学版) 2012(3) 3.李苗 实时碰撞检测算法分析与比较[期刊论文]-计算机与现代化 2011(6) 4.盛国栋.曹其新 基于力反馈的虚拟脊柱手术模拟系统的构建[期刊论文]-电子技术应用 2013(12) 5.任清川.何赛松.徐雷 数控管切割机三维仿真加工若干问题的研究[期刊论文]-图学学报 2012(6) 6.马超.黄煜.张建伟 优化的标牌自动避让算法[期刊论文]-计算机工程与设计 2012(9) 7.王继水.顾卫杰 矿山生态环境修复虚拟系统的关键技术研究及实现[期刊论文]-遥感技术与应用 2010(6)

8.田园.万毅 基于CUDA的并行碰撞检测算法研究[期刊论文]-甘肃科技 2011(14) 9.伍辉.刘艳斌.黄敏纯.朱晓林 虚拟装配序列生成及其评价系统的研究[期刊论文]-成组技术与生产现代化 2012(2) 10.陈煜.殷凤华 基于拾取算法的产品交互式Web3D模拟的研究与实现[期刊论文]-应用科技 2011(12) 11.温莲芹.朱瑞军 基于碰撞检测的三维板坯库动态注记模型[期刊论文]-计算机应用研究 2012(1) 12.陈煜.林玮 Web3D引擎中三维图形对象拾取的算法与实现[期刊论文]-工程图学学报 2011(6) 13.向宇.侯进.徐芳.吴铃 分类应变限制下的服装仿真[期刊论文]-计算机应用 2012(6)

本文链接:http://d.wanfangdata.com.cn/Periodical_jsjgcykx201004017.aspx



推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com