文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 基于线性规划的碰撞检测算法研究
侵权投诉

基于线性规划的碰撞检测算法研究

基于线性规划的碰撞检测算法研究

C.)CA/L*,LM,G+3D+*<2N<<!

&(华东交通大学机电工程学院,南昌##""&#)

周新建&

!

(美国伊利偌依大学芝加哥分校虚拟现实研究所)

摘要介绍了虚拟环境中一种基于凸多面体面信息对偶线性规划模型(的快速旋转和移动物体之间干涉FL+.@0,<.)

碰撞实时检测方法。该文详细介绍了建模过程和求解步骤,物体由构成凸多面体的三角形面信息表示,而物体的运动由一组虚拟现实环境中的全局移动和旋转矩阵表示。这种数学编程方法具有数据结构简单、算法可靠和速度快等优点,同内点方法来解线性规划方程,具时能够很好地解决高速(运动帧)碰撞的问题。这一方法通过使用主>对偶(O2)5+.>,L+.)有很好的效果,能够检测多物体对之间的碰撞。实验结果表明,基于数学编程的方法相对两种著名的工具包P>(E’’PFQ和RE’PF,具有速度快和稳定可靠的优点,而P>(E’’PFQ和RE’PF工具包基于两种著名的算法:最近特’)*(+**-(’()。征算法和89:算法(Q*4+*S<,8).;<23904*=0*+*,:<<34)+./02)345)关键词

虚拟现实

碰撞检测

对偶模型

线性规划文献标识码C

中图分类号UG#"&$J

文章编号&""!>T##&>(!""#)!%>"&"I>"#

!"#"$%&’()*(++,#,()-"."&.,()/+0(%,.’12$#"3()-4$+5(3"+

6’(47,)8,$)9/+,/:04)34;,<$.2$)"%8""=

&(@<S4320*)SRS400.0VQ+=3(4)*+9)+030*/W*)X<2=)3-,Y+*S4+*/,9)+*/Z)##""&#)!(P*,L=32)+.?)23L+.[<+.)3-P*=3)3L3<+3W*)X<2=)3-0VP..)*0)=+3(4)S+/0,WRC)

/>#.%$&.:U4)=O+O<2O2<=<*3=+2<+.>3)5<S0..)=)0*,<3<S3)0*5<340,0.0/-;<3B<<*+O+)20VS0*X<ZO0.-4<,2+.0;N<S3=

L*,<2/0)*/V+=3203+3)0*+.+*,32+*=.+3)0*+.503)0*,B4)S450,<.=34<S0..)=)0*,<3<S3)0*O20;.<5+=+,L+.50,<..)*<+2O20/2+5;+=<,0*S0*X<Z32)+*/.<)*V025+3)0*$U4<O+O<2)*320,LS<=34<50,<.)*/O20S<==+*,=0.L3)0*5<340,)*,<3+).$U4<0;N<S3=+2<=O<S)V)<,;-+=<30V32)+*/.<=,+*,50X<5<*3==O<S)V)<,;-+=<30V/.0;+.32+*=.+3)0*+*,203+3)0*5+32)S<=/<*<2+3<,3420L/4+*-X)23L+.2<+.)3-<*X)20*5<*3$U4<5+34<5+3)S+.O20/2+55)*/+OO20+S40VV<2=20;L=3*<==,=O<<,,=)5O.<2,+3+=32LS3L2<=,+*,)3*+3L2+..-+,,2<==<==)3L+3)0*==LS4+=4)/4=O<<,()*3<2V2+5<)S0..)=)0*=$U4<=32<*/340V,<X<.0O<,+OO20+S4)=,<50*=32+3<,;-=0.X)*/34</<*<2+3<,.)*<+2O20/2+5=L=)*/+O2)5+.>,L+.)*3<2)02O0)*35<340,$U4<5<340,S+*,<3<S3S0..)=)0*=;<3B<<*5L.3)O.<0;N<S3O+)2=$QZO<2)5<*3+.2<=L.3==40B34+35+34<5+3)S+.O20/2+55)*/+OO20+S4<=0VV<2=L;=3+*3)+.+,X+*3+/<=)*=O<<,+*,20;L=3*<==,B4<*S05O+2<,B)343B0B<..A*0B*300.A)3=V0234)=O20;.<5:P>(E’’PFQ+*,RE’PF,B4)S4O20X),<<+=-30L=<OL;.)S,05+)*+SS<==V023B00V34<50=3O0OL.+2+./02)345=>’)*(+**-(’()S.0=<=3V<+3L2<+./02)345+*,Q*4+*S<,8).;<23904*=0*+*,:<<234)(89:)+./02)345$?"@A(%3#:?)23L+.[<+.)3-,(0..)=)0*F<3<S3)0*,FL+.@0,<.,’)*<+2G20/2+5

&引言

虚拟环境下快速运动物体之间的碰撞检测是虚拟现实技

个特征分别来自两个凸多面体),然后检测最近点是否落在这两个特征上。这是一种涉及当前候选特征对临近特征的局部测试,如果最近点不落在候选特征对上,则对候选特征对的临近特征进行检测并且循环往复进行。在进行适当的预处理后,可以保证每一个特征具有不变的临近特征个数。89:算法则对进行碰撞检测的凸多面体使用迭代的@)*A0B=A)差分算法。

为了有效地实现复杂虚拟场景,几乎所有的干涉碰撞方法都使用层次包容体6#7。具有简单形状的包容体被用来作为初步干涉测试。如果包容体之间不存在干涉,则可确保相应物体之间不存在碰撞,这样可以大大减少需检测物体的形状特征数,特别是当物体之间距离不近的情况。可供选择的包容体包括:轴对齐包容盒(,有向包容盒(,球,圆锥体,CCDD=)EDD=)A>

术中的关键技术之一。碰撞检测算法速度的提高直接影响到软件系统环境中可有效管理的情景的规模大小,而碰撞检查在此是必须的。值得注意的是,在一个复杂的情景中,每秒需要检测大量的干涉碰撞(从数十万到数百万)。在这种情况下,一个理想的干涉碰撞检测算法应该在各种不同的情况下运行良好,无论是对于低速运动物体之间的碰撞检测还是对于高速运动物体之间的碰撞检测,无论是对于高度密集的环境中大量的碰撞检测还是对于稀疏的环境中少量的碰撞检测。

最著名的两种碰撞检测算法是’((’)*+*,(+**-+./01

6&76!7

算法和89:(算法。’(最2)345)8).;<23,904*=0*+*,:<<234))

近特征算法利用了瞬时相关性原理>最靠近的特征(面、边或顶

点)在凸多面体沿细分离散路径非快速运动的情况下变化较小。根据?020*0)区域决定一组候选特征对(这一特征对的两

FEG=6H76I76J76K7等。尽管包容体的使用可以大大缩短远离物体之间

干涉碰撞检测时间,在物体距离较近时,’(最近特征算法和89:算法仍然是必须的。

作者简介:周新建(,男,教授,主要研究方向:虚拟现实技术。&%J#>)(CF\(C@技术,

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email