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

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

&’()*+,-等,

基于.&算法,使用瞬时相关性假设来加快复杂情景中的碰撞检测并开发了著名的/0&1../23软件包。这一假设是,时间步长非常小,以至于在连续的前后帧之间,物体不会移动较大的距离。使用瞬时相关性假设可以将*个同时运动物体的1(*!)迭代减少到1(*45),其中5代表物体的轴对齐包容体重叠的物体的个数。对于复杂情景数据库,多分辨率建模技术如模型简化也被用于层次包容体技术+%-。多分辨率层次包容体的主要思想是计算和使用原始物体和简化物体之间的相关性。

最近,1*6和789:);<+="-也使用了最近特征的概念来实现更有效的7>?算法。在应用到运动路径规划的情况下(只有两个物体),当运动路径不碰撞并且具有高瞬时相关性时,他们报告的结果与.&算法取得的结果相似,

当瞬时相关性低时,则具有!0="倍的改善。@8;<8A(+==-在描述他的B’;’*’80A98C(B0&98C)算法时(基于.&方法)比较了.&,&D5);’*的增强型7>?算法和他的B0&98C算法对于单一物体对的情况。@8;<8A(只进行了浮点比较,而没有进行计算时间比较。@8;<8A(注意到边0面和面0面碰撞是.&算法中最具问题的情况,它们是造成代码复杂性和死循环的主要原因。在B0&98C算法中,对边0面问题进行了简化,而面0面问题则不再存在。@8;<8A(同时指出了.&算法、B0&98C算法和增强型7>?算法的健壮性问题。一种速度快和更健壮的7>?版本,

增强型7>?算法得以实现,而相应最快速的7>?算法出现在E1./2软件包中+=!-

。

在对/0&1../23和E1./2进行测试时,发现这些.&算法和7>?算法的实现在有些情况下会失败。/0&1../23经常失败的情况是当一个物体从某一个面的方向与另一个物体碰撞,或者当一个物体包含另一个物体的情况,如图=所示。在测试中,E1./2比/0&1../23更容易失败。图的上半部分是/0

&1../23算法失败时的面0面相碰撞的两个例子。单向箭头表

示两个物体的运动方向,在这里两个物体作无穿透的滑动。图的下半部分是一个物体完全包含在另一个物体的情况。小物体是一个!"个顶点的物体,

而大物体是一个球(尽管看起来像一个椭球)。另外一种对这些算法造成困难情况是当一个物体比另一个物体小很多的情况。笔者注意到.&算法和7>?算法在数学计算上都是正确的,但在/0&1../23和E1./2的实现却不是健壮的。总而言之,经测试表明/0&1../23比E1./2要健壮一些。

图=现有算法的健壮性问题

在计算机图形学界,人们知道可以使用数学编程方法来进

行碰撞检测已有些时日。但是,在现有的文献报道中,当使用于实时计算机图形学领域时,这些技术被认为效率不够+=#-+=F-。而在试验中,通过对碰撞问题进行创造性建模,辅之在对数学编程技巧有充分了解基础上的有效实现,可以得到一种更好的方法。在基于充分试验后得到的结论似乎与线性规划方法(.8*G

)D;H;’6;D558*60.H)由于速度慢而不适用于碰撞检测的论断

相矛盾。发现基于.H的对凸多面体进行碰撞检测的方法无论

在效率和健壮性方面均优于当今最流行的算法实现。

下面介绍基于凸多面体三角形面信息的对偶模型的建模和求解过程。

!问题建模

!$=基于凸多面体面信息的数学模型(

对偶模型02ID9@’J)9)

对于三维凸问题,由平面方程组成的不等式约束定义了三维凸包的内部区域。一旦一个物体的内部区域被定义为线性规划约束,则可以建立优化方程来检查另外一个物体上的一个点、一条线是否与该物体相交。通常情况下,这样的优化模型建立如下:

5DK0!!"#"

$=

=

=

%&’(%)’*%+,!!0=$!

!

!

%&’(%)’*%+,!!0=&,),+""

与属于每个物体的顶点对应有一个约束方程。这里引入了人工变量!以便在两个物体不碰撞的情况下,

方程有可行解。在上面的公式中,如果两个凸多面体之间不存在碰撞,!的值将大于零。相反,如果存在碰撞,则在!等于零的情况下线性规划方程存在可行解。

!$=$=对偶(2ID9)

模型设-.为一个多面体,

其顶点为/.%#!#,由这些顶点构成的三角形为0.1#!#,其中.LM=,!N,%LM=,!,#$$$2.N,1LM=,!,$$$3.N。2.是属于第.个凸多面体的顶点个数,3.是属于第.个凸多面体的三角形个数。当三角形以逆时针方向索引时(如图!0D所示,这在计算机图形学三维物体表示中是一种通用的格式,如BO@.、/*P)*<’;、E’Q<85D6)等等。),三角形的法线(4.%#!#)指向凸包的外面,如图!0:所示。如果面的平面方程写成指向面法线相反方向的不等式方程,这些平面方程在线性规划方程中定义了凸多面体的内部。

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

图

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

!

物体在三维空间的表示

上一页第2页

你可能喜欢

热门文档

相关文档

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