当前位置:www.5486.com > www.5486.com >

昨天的比“乒乓”要高级得多

   更新时间:2019-09-28   浏览次数:

  让我们从根基的引擎轮回起头吧(列表1)。快速浏览这些代码来获得碰撞检测的相关策略。我们先假设碰撞没有发生,然后更新物体的,若是发觉发生了碰撞,我们将把物体移回本来的不答应它穿越鸿沟(或将物体或施行一些防止办法)。然而,这个假设过分简单由于我们无法得知物体本来的能否仍然无效。你必需为这种环境设想一个方案(不然你可能会体验到坠机或被枪弹击中的感受――就是前面举的例子)。若是你是一个热心的玩家,你可能曾经留意到了正在一些傍边,当你挨着墙壁并试图穿过去的时候,摄像机就起头震动。你正派历的就是将配角移回原位的环境。震动是由于取了较大的时间片惹起的。

  倒霉的是,我们还没有一个很好的方式检测正在一个时间间隔内的碰撞(正在文章开首提到的方式现正在仍正在利用)。然而,我曾经看到有别的的数据布局像BSP树一样起头普遍利用了。

  现正在假设我们曾经有了OBB或者AABB树。那么我们该怎样进行碰撞检测呢?我们先检测最大的包抄盒能否订交,若是订交了,他们可能发生了碰撞,接下来我们将进一步地递归处置它们(不竭地递归用下一级进行处置)。若是我们沿着下一级,发觉子树并没有发生订交,这时我们就能够遏制并得出结论没有发生碰撞。若是我们发觉子树也订交了,那么要进一步处置它的子树曲到达到叶子节点,并最终得出结论。进行订交测试时,我们能够把包抄盒投影到空间坐标轴上并查抄它们能否线性订交。这种给定的坐标轴称为分手坐标轴(separating axis)如图8所示。

  Imagination中文手艺社区权势巨子发布相关Imagination公司CPU,GPU以及毗连IP、无线IP最新资讯,供给相关物联网、可穿戴、通信、汽车电子、医疗电子等使用消息,每日更新大量消息,让你紧跟手艺成长,欢送免费注册。网址:/span>

  风趣的是,前面提到的时间片大小的问题用分手坐标手艺很容易就能处理。回忆一下关于正在两个给按时间内能否发生碰撞的问题。若是我们把速度加上,而且正在所有15条坐标轴上的投影都跌交,申明会发生碰撞。我们能够用雷同于AABB树那样的数据布局区分碰撞物和受碰物,并判断他们能否有可能发生碰撞。这种运算能够快速地解除正在场景中的大大都环境,发生一个接近抱负的O次幂(N logN)的效率。

  有另一种比力容易施行但精度较低的方式,就是把给定的时间段分为两分,然后测试时间中点的订交关系。我们还能够递归地顺次测定各段的时间中点。这个方式比先前的方式要快得多,但不克不及能捕获到所有的碰撞环境。

  但我们仅仅是将这个不太切确的方式做为我们的第一步。我们用一个大的代表整个对象,然后检测它能否和其它的订交。若是检测到发生了碰撞,那么我们就要进一步提高精度,我们能够将大的朋分成一系列小的,并查抄取各小能否发生碰撞。我们不竭地朋分查抄曲到获得对劲的近似值为止。分层并朋分的根基思惟就是我们要尽可能达到适合需要的抱负的环境。

  基于 Portal 的引擎把场景或世界朋分成较小的凸方形区域。凸方形区域很适合图形管道由于它们能避免沉绘现象。倒霉的是,对碰撞检测来说,凸方形区域会给我们带来一些坚苦。正在我比来的一些测试中,一个引擎中平均大约有400到500个凸方形区域。当然,这个数字会跟着分歧的引擎而有所变化,由于分歧的引擎利用分歧的多边形手艺。并且多边形的数目也会因场景的大小而有所分歧。

  能否我们能够连系这两种手艺构成一种夹杂方式?起首我们用凸壳进行碰撞检测然后逐渐正在凸壳所属的部门细分下去,如许就添加了精度。

  正如你所看到的,建立阶段相当复杂,此中包罗了大量的运算。很较着不克不及及时地建立树――只能是事先建立。事先建立可免得去及时改变多边形的可能。另一个错误谬误是OBB要求进行大量的矩阵运算,我们不得不把它们定位正在恰当的处所,而且每棵子树必需取矩阵相乘。

  为肆意的网格模子建立 OBB 树可能是算法里最难的一个部门,并且它还要调整以适合特定的引擎或类型。图7示出了从最后的模子建立一个OBB树的整个过程。能够看到,我们不得不找出包抄给定模子的比来似的包抄盒(或者其它3D体)。

  现正在我们获得了所有的包抄盒,下一步我们来构制一棵树。我们从最后的包抄盒起头从上至下地频频朋分它。别的,我们还能够用从下至上的体例,逐渐地归并小包抄盒从而获得最大的包抄盒。把大的包抄盒朋分成小的包抄盒,我们该当恪守以下几条准绳。我们该当用一个面(这个面垂曲于包抄盒中的一条坐标轴)来朋分包抄盒上最长的轴,然后按照多边形处正在朋分轴的哪一边把多边形分分开来(如图7)。若是不克不及沿着最长的轴进行朋分,那我们就沿第二长的边朋分。我们持续地朋分曲到包抄盒不克不及再朋分为止。根据我们需要的精度(好比,能否我们实的要判断单个三角形的碰撞),我们能够按我们的选择的体例(如是按树的深度或是按包抄盒中多边形的数目)以肆意的前提遏制朋分。

  判断一个物体的多边形能否穿过了场景中的多边形发生的运算量可能会很大。一个最简单的碰撞检测法就是用球形来近似地暗示物体或物体的一部门,然后再判断这些包抄球能否订交。如许我们仅仅需要测试两个核心的距离能否小于它们的半径合(这暗示发生了碰撞)。若是我们是用核心点距离的平方和半径合的平方进行比力,那更好,如许我们能够正在计较距离时除去的开方运算。可是,简单的运算也导致了切确度的降低(见图3)。

  BSP(二叉空间朋分)树是另一品种型的空间朋分手艺,其曾经正在工业上使用了很多年(Doom是第一个利用BSP树的贸易)。虽然正在今天BSP树曾经没像过去那么受欢送了,但现正在三个被承认的引擎――Quake II, Unreal, and Lithtech(:这是2000年的文章,所以指出的这些才这么老:)仍正在普遍地采用这项手艺。当你看一下BSP正在碰撞检测方面那极端清洁标致和高速的效率,立即能让你面前一亮。不单BSP树正在多边形剪切方面表示超卓,并且还能让我们无效地使用world-object式的碰撞检测。BSP树的遍历是利用BSP的一个根基手艺。碰撞检测素质上削减了树的遍历或搜刮。这种方式很有用由于它能正在晚期解除大量的多边形,所以正在最初我们仅仅是对少数面进行碰撞检测。正如我前面所说的,用找出两个物体间的分隔面的方式适合于判断两个物体能否订交。若是分隔面存正在,就没有发生碰撞。因而我们递归地遍历world树并判断朋分面能否和包抄球或包抄盒订交。我们还能够通过检测每一个物体的多边形来提高切确度。进行这种检测最简单的一个方式是测试看看物体的所有部门能否都正在朋分面的一侧。这种运算实的很简单,我们用迪卡尔平面等式 ax + by + cz + d = 0 去判断点位于平面的哪一侧。若是满脚等式,点正在平面上;若是ax + by + cz + d 0那么点正在平面的反面;若是ax + by + cz + d 0点正在平面的后背。

  现正在我们曾经看到了两种多边形物体的碰撞检测,下面一看看若何计较弯曲物体的碰撞。99年发布的几款曾经大量地采用曲面了,因而正在接下来几年里高效的曲面碰撞检测将变得十分主要。曲面碰撞检测(要求有给定点上切确的曲面等式)运算开销极大,所以我们要尽量避开它。现实上我们曾经会商了几种能用正在这种环境下的方式。最较着的方式就是用低网格来近似暗示曲面,然后利用这个多面体进行碰撞检测。以至还有更简单的(但精度比力低),就是正在曲面的节制极点(:大要意义就是说每隔必然量的极点就构制一个凸壳)上构制凸壳用来做碰撞检测。正在这种环境下,曲面的碰撞检测十分近拟于保守的多面体碰撞检测。如图9显示了曲面及它正在节制极点上构成的凸壳。

  坐标轴平行(“Axis-aligned”)不只指盒体取世界坐标轴平行,同时也指盒体的每个面都和一条坐标轴垂曲。如许一个根基消息就能削减转换盒体时操做的次数。AABBs 正在当今的很多中都获得了使用,开辟者经常用它们做为模子的包抄盒。再次指出,提高精度的同时也会降低速度。由于 AABBs 老是取坐标思平行,我们不克不及正在扭转物体的时候简单地扭转 AABBs --- 它们该当正在每一帧都从头计较过。若是我们晓得每个对象的内容,这个计较就不算坚苦并不会降低的速度。 然而,我们还面对着精度的问题。假如我们有一个3D的细长刚性曲棒,而且要正在每一帧动画中都沉建它的AABB。我们能够看到每一帧中的包抄盒的都纷歧样并且精度也会随之改变。

  所以以其用 AABBs,为什么我们不消肆意标的目的能最小化空白区域的包抄盒呢。这是一种基于叫 oriented bounding boxes—OBBs 的手艺,它曾经普遍用于光线逃踪和碰撞检测中。这种手艺不单比 AABBs 手艺更切确并且还更健壮。但 OBBs 实现起来比力坚苦,施行速度慢,而且不太适合动态的或柔性的物体。出格留意的是当我们把一个物体分得越来越小的时候,我们现实上正在建立一棵有条理的树。

  自从计较机呈现以来,法式员就不竭地想法子来更切确地模仿现实世界。就拿乒乓为例子(:Pong—被誉为电子的先人,有幸见过一次:),能见到先人做的感受实是爽啊,想看的能够到FTP上下载“地球故事”就能够看到了:),中有一个意味性的小方块(球)和两支拍子,者需要正在得当的时间将拍子挪动到得当的地址,将小球反弹归去。这个根基操做的背后(以现正在的尺度来看)就是最原初的碰撞检测了。今天的比“乒乓”要高级得多,而且根基上是基于3D的。3D中的碰撞检测比“乒乓”里的要愈加难实现。玩一些晚期模仿飞翔的体验向我们展示出蹩脚的碰撞检测是若何一个的。当穿过一座大山的尖顶的时候仍然活着,感受很不实正在。即即是现正在的一些也仍是有碰撞上的问题,很多玩家已经失望地看着他们喜爱的豪杰或女豪杰的部兼顾体穿进了墙里。以至更糟的是,很多玩家都有过如许蹩脚的体验,就是被那些离得很远的枪弹或火箭击中。由于者们要求提拔实正在性,我们开辟者就不得不想法子让我们的世界尽可能地接近现实世界。

  可是我们的方式出缺陷,我们忘了正在等式中插手时间。图1告诉我们时间太主要了不克不及忘了它。即便物体正在 t1 或 t2 时辰没有发生碰撞,它仍有可能正在 t 时辰穿过鸿沟(t1tt2)。这会正在两个持续帧中发生大幅度地逾越(就好象击中了燃料室或其它雷同的工具)。我们不得不找一个好的方式来处理这个问题。 p=/tt2)。这会正在两个持续帧中发生大幅度地逾越(就好象击中了燃料室或其它雷同的工具)。我们不得不找一个好的方式来处理这个问题。

  正在碰撞没发生的时候有一个主要的工作需要留意,就是一个物体(或它的包抄盒)必需正在朋分面的反面或后背。若是正在平面的反面和后背都有极点,申明物体取这个平面订交了。

  一个简单的方式就是建立一个凸壳来罩住两个分歧时辰的物体。这种方式效率低下可能会较着地降低你的速度。以其建立一个凸壳,还不如建立一个环绕实心体的包抄盒。我们进修其它的手艺后再回来会商这个问题。

  用去近似地代表物体运算量很小,但正在中的大大都物体是方的,我们该当用方盒来代表物体。开辟者一曲用包抄盒和这种递归的快速方式来加快光线逃踪算法。正在现实中,这些算法曾经以八叉和AABB(axis-aligned bounding boxes)的体例呈现了。图5展现了一个AABB和它里面的物体。

  另一个暗藏着的问题是collide_with_other_objects()方式的实现――即判断一个物体能否取场景中的其它物体订交。若是场景中有良多的物体,这个方式可能耗损很大。若是要判断各物体取场景中其它物体能否订交,我们将不得不进行大要N选2次比力。因而比力次数会是N的平方次冪(或暗示成O(N2))。但我们能够用几种方式来避免进行O(N2)对的比力。举个例子,我们能够把场景中的物体分成静态的(被撞物)和动态的(碰撞物――即便它的速度为0也行)。就好象房间中的墙壁是被撞物,而一个扔向墙壁的小球是碰撞物。我们能够建立两棵的树(每一棵对应一类物体),然后测试那些物体可能会碰撞的树。我们以至能够对进行商定让一些碰撞物之间不发生碰撞――好比我们不需要正在两颗枪弹之间进行判断。现正在正在继续之前,(颠末改良之后)我们能够说处置过程变得愈加清晰了。(另一个削减场景中成对的比力的方式就是成立八叉树。这曾经超出了这篇文章的范畴,你能够正在Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods文章中的For Further Info一节里读到更多关于八叉的消息)。现正在让我们来看一下基于 Portal 引擎,领会为什么正在这类引擎中一提到碰撞检测就会那么疾苦。

  我们是选择 AABBs 仍是选择 OBBs 该当按照我们所需的切确程度而定。对一个需要快速反映的3D射击来说,我们可能用 AABB 来进行碰撞检测更好些――我们能够一些精度来换取速度和实现的简单化。这篇文章附带的代码曾经传到 Game Developer 网页上了。里面是从 AABBs 起头讲起,同时还供给了一些实现 OBBs 的碰撞检测包里的代码例子。好了,现正在我们曾经有了关于每一部门是若是工做的认识了,下面我们来看看实现的细节。

  我们能够把时间当作是第四维并将所有运算正在4维空间中进行。然而这可能会让运算变得十分复杂,所以我们会避开这些。我们还能够建立一个以 t1、t2时辰的物体为起始点的实心体,然后用它来取墙进行测试(见图2)

  现正在我们曾经浏览了一些高级的碰撞检测(有一些也是根基的),你该当可以或许决定什么样的系统更适合你的。你要决定的次要工作是精度、速度、实现的简单程度及系统的顺应性。

  为了建立一个抱负的碰撞检测法式,我们不得不正在开辟一个的的图形管道的同时就起头打算并建立它的框架。正在项目标最初插手碰撞检测是相当坚苦的。想正在开辟周期的末尾建立快速的碰撞检测将很有可能会使整个被毁掉,由于我们不成能使它能高效地运转。正在好的引擎中,碰撞检测该当是切确、无效而且十分快速的。这些要求意味着碰撞检测将要取场景的多边形办理管道紧紧地联系起来。这也意味着穷举法将无法工做――今天的3D中每帧处置的数据量很可能导致打格,当你还正在检测一个物体的各多边形能否取场景中的其它多边形碰撞时,时间曾经过去了。

  为了快速地判断订交性,我们利用一种叫分手坐标的方式。这种方式告诉我们,只要15条潜正在的分手坐标。若是跌交的环境正在每一条分手坐标上都发生了,那么包抄盒是订交的。因而,很容易就能判断出两个包抄盒能否订交。

  有几种方式能够事先计较OBB,这此中包罗了很多的数算。此中一个根基的方式是计较极点分布的均值,将它做为包抄盒的核心,然后计较协方差矩阵。然后我们用协方差矩阵的三个特征向量中的两个把多边形和包抄盒连系起来。我们能够凸盒方式进一步加快和优化树的建立。你能够正在Gottschalk, Lin, 和 Manocha的文章中的“For Further Info”一节找到相关消息。成立AABB树要简单得多,由于我们不需要找出物体的最小的包抄体和它们的轴。我们只需决定正在哪分隔模子,并且包抄盒能够建立(只需包抄盒平行于坐标轴而且包含朋分面此中一侧的所有极点)。

  阅读这篇文章前起首假设你对取碰撞检测相关的几何和数学学问曾经有了根基的领会。正在文章的最初,我将供给一些这方面的,免得你对它们感受有点陌生。别的我还假设你曾经读过 Jeff Lander 的图形专栏里关于碰撞检测文章(“Crashing into the New Year,” ; “When Two Hearts Collide,”;和 “Collision Response: Bouncy, Trouncy, Fun,”)。我将起首辈行一个大要的描述,然后快速地切入到焦点内容里,通过这两步从上至下地深切到碰撞检测中。我将会商两品种型的图形引擎中的碰撞检测:基于 portal 的和基于 BSP 的。每种引擎中多边形的组织各不不异,因而正在 world-object 型的碰撞检测上存正在很大的不同。而object-object 型的碰撞检测绝大大都地朴直在上述两种引擎里的是一样的,次要看你是若何实现的了。当我们接触到多边形的碰撞检测时,我们还会尝试若何将其扩展到我们学过的凸型物体上。



Copyright 2019-2022 http://www.snow2003.cn 版权所有 未经协议授权禁止转载