11.2 图元距离(下)在线视频

讲的其实是点到几何体之间那个最短距离

然后呢

再复杂一些的就是凸包与凸包之间

或者说认为是几何体几何体之间

然后为什么讲这个凸包与凸包

因为像我们的那个元

就是球体

然后Box

就是那个盒子几何几个盒子

然后呢

像刚才还之前还讲课

讲到的这个

讲到的这个这个胶囊体

它们其实都有一个这种共性

它们都是凸包

凸包的话

凸包它其实一个最简单的定义的就是说

它就是说

你连接凸包表面的任意的两点

它的那个直线的一定是在那个

这个几何体的内部

这是它的一个就是它的一个性质

所以呢

这个凸包与凸包之间

求它的最短距离

其实就是一个可以理解成就是说在游戏中

或者在我们的这个3D几何学里边

它一个相当于是一个通用的求解方法

这里边的其实提到一个

就是说我提到一个那种技巧

就是任何物体

它与与那个圆或者与球体

它的那个碰撞检测

或者说他的那个最短距离的求解其实呢

是可以做一次

这种就是等价的一个可以叫变形吧

比如说在这里面的我要求一个这个

正方与一个圆的最短距离

其实它可以等价

就是说把元变成一点

然后呢

应该是说把这个正方形进行膨胀

就是你可以这么想

就是说简单讲就是比如说我举个例子

比如说两个球之间的距离对吧

其实是可以等价于

就是说其中一个球在变大

另外一个球变小

然后呢

在这里边的

只要其中一物体是球

另外一个物体其实也可以进行膨胀

但是它膨胀了之后呢

就不是原来的那个形状

但是原来那个形状相似的一个几何体

在这里边的一种简单的做法呢

其实就是把这个元为就是这个元

你把它围绕着

这个正方形的表面

进行就是进行叫什么

就是进行运动

运动之后

它经过的那个空间

就是组合成了一个新的一个

形成一个新的那个几何体

然后这时候这个膨胀的这个几何体

应该就是一个类似就是凸包的东西

你这时候呢

你要求它们两的距离你就等价于这个点了

在这个凸包的最近距离

这个呢是一种

就是一种就是说一种处理变换的

非常就是说

对于求解一个就是元到几何体之间的距离

就是说非常有用的

像这个距离求解

它其实在你拿到的那个

就是它还有一个作用的就是说

其实可以做一个最简单的碰撞检测

就是如果说我与一个物体的那个距离

是正的话

那说明他其实跟我没有碰撞

但是如果说我求它的距离

是负的或者小于零的话

那说明其实我跟它是有碰撞的

在这个求解凸包与凸包之间

一个通用算法呢

这点的就是得提到这个《GJK》（算法）

《GJK》（算法）是三个人发明的

然后呢

以他们的名字的首字母来命名的一个算法

这个算法呢

大家了解下就好了

就是其实他是通过闵可夫斯基的和来做的

基本的原理就是说

我把两个物体

就是两个凸包或者两个几何体

它其实都是可以理解成这个点的几何

或者说到包围的或者围住的点的一个几何

如果说它两

如果说它两个物体真有相交的话

那其实可以简单理解成这个几何相交

几何相交就说

比如说在这里面画了简单的A跟B

就是如果假设空间中有一个位置对吧

它这个位置呢

它既属于这个A几何也属于这个B几何

或者属于A的包围体也属于B的包围体

那它俩是不是发生的碰撞

就是或者说

从几何概念讲的

其实就是几何有共同的集合

那集合它们个有并集

并集就是它们相交的那个集合

在它这里边的就是

其实你可以做一次那个集合的那种相减

就是先把从集合上的意义来说呢

B呢

就是说它的那个元素全部变成负的

这个负呢

相当于是三维上的一个趋伏

比如说它原来的那个位置

或比如他是一一

这时候我们趋伏的话就是负1负1

然后在这里边看的

其实就相当于是做了一次

就是在3D空间中也是旋转

就是围绕着原点旋转到了它那个

相当于那个叫什么

就旋转到另外一个上线了

在这里了就是变成负B

然后呢

把负B与那A做一次加法

其实就相当于在A减B最后

最后得出了这个减后的几何体

它其实简单的说

其实跟我刚才讲的这个方法呢

其实是有很像的

这里边我这个方法里面讲的围绕的表面

但是其实这里面减出来的和

形成了一个几何体的

其实是你可以理解成是把一个几何体

然后的顶点

然后放在的放在了这个

放在了就是另外一个几何体内部

不断的运动在它内部不断运动之后

最后他它经过绕过的空间或者经过的空间

形成了一个新的那个几何体

如果说这个几何体

它包含原点的话

包含原点的话

那就是结合刚才讲的

就是说两个元素我相等

因为它们两个人两个元素相减了之后呢

有元素在原点

但那其实就是说明它们有相等的元素

就是在这个减后的这个几何级数

包含原点的话

那就说明它也相交在这里面

这个图里面

它其实没有相交

所以你看这个原点原点

它并不在这个包围体里面

如果说这个包围体的话

它是包含原点的话

那说明原来的AB两点

它这个是相交的

这个呢

其实是一个就是说这个《GJK》

它用到的一个原理

但是呢

我们在算法里面的其实不是这么做的

这里呢

也简单的讲一下

这个就是《GJK》一个算法

就实线的算法呢

它这里来要用一个简单的概念

就是一个Support（求给定方向上最远点算法）方法

Support方法的话

就是说我给了一个几何体

然后我要能求出我给一个

任意轴上的一个最远点

或者说你可以理解成是几何体在这根轴上

投影的端点

比如说在这里

我给了一个Support那个轴的话

那对于这个几何体来说

那其实相当于是在这个方向的投影

那就是这个W点

简单的讲《GJK》的思路

就是说我不断的通过求这个Support的点

以及这个support就是说

这个在某一个方向上的最远点

不断地去求解去逼近到

它就是说我最短距离的轴

其实这个这里面

就涉及到那个算法的一个方法了

就是说我们大部分的方法其实都是迭代法

就是我我一次取不到值

但是呢

我通过多次的迭代的不断的逼近那个值

因为毕竟就是说有些词

可能是无法真正求出精确解的

那我们就一个近似解也可以

在这里面的其实那个我觉得

可能深入在讲了会花非常多的时间

然后然后呢

大家理解一下这个就是它的一个

具体的思路和原理就好了

如果是详细的方法的

大家给课后跟我讨论

或者说课后再联系

就是这里边

其实我就是刚才讲到还有一个重要的特性

就是说那个凸包

它其实只要你给一个方向的话

它其实是这个它的两个端点

一定是在凸包内

这样能保证的那个凸包在迭代的过程中呢

就是说每一次逼近的

都会更就是说可以更接近我原来了点

他那个逼近的那个具体方法呢

在这里呢

我简单说一下

就是说

我在那这个O其实是起点

O是起点

然后呢

我在这里比如说那个凸包内任取一点

我跟他做一个连线

这个连线的作为那个support的那个轴

这时候呢

结合刚才提到Support方法呢

这时候呢可以求的这个W点

求的是个W点W零点

然后呢

再根据刚才的方法

就是把W零点跟那个起点的做个连线

然后呢

以这个连线的做一个Support轴

然后求出一个新的这个W一点

这时候再将那个W零和W一做一次连线

然后求的这个原点到这个W零

这个线段W零到W1最近点这里呢

这里是个V二

然后再拿这个求到这个点了

跟那个起点的做连线

然后求的这个@上的一个最近点

这个W二

到现在为止呢

我们其实已经求出了

就是说根据它的@那个方法

求出了三个点

就是W零W一W二

其实还是可以不断的去求一个W三W四

但是你在求的这个过程中呢

你会求你会构建出从一开始的一个点

到线段到那三角形

甚至到一个四面体

然后像在这里面的求出的三角变的和

或者四面体就会不断的逼近

就是说不断的逼近那个起点

在这个过程中呢

我可以设置一个迭代的最大次数

比如在这里面呢

我们其实除了总共有应该是起了四个点

四个点

但其实这个四面体的

其实大家可以看这个四面体

其实是这里可能看不出来

四面体

但是这一全点击的话

它其实是

它其实是明显是比其它凸包

那些点的要更接近于这个起点

我们这时候呢

可以用从刚才最开始不是我讲过吗

就是说求一个点到四面体的最短距离

或者一个一个点到三角形

或者说那个线段的最远距离

在这个过程中的就是通过

通过呢

我最后最终求这个点到四面体或三角形

根据你所需要的精度

你可以去选择你迭代的次数

以及所说所对应的算法

那你可以求的就是说一个起点

就是说近似在这个突破表面上的点

就是整个这个凸包求解呢

就是跟我其实也跟我最开始讲的那些方法

就是逐步逐步的

逐步就是说

有简单可能会逐步的变复杂

但是呢

整个你会发现有了这些基础的算法之后

或者计算方法之后呢

就可以解决一些非常复比较复杂的问题

然后比这个再复杂的一个方法

那就是因为这里提到的是点到凸包的距离

那就凸凹与凸包之间的距离

求解算法是怎么样的呢

比如说要求解两个

两个凸包与凸包之间的碰撞

那怎么求

其实用刚才的类似的方法

只是把其中的一个点的替换成一个凸包

那这个这时候怎么做呢

其实两个凸凹有了Support轴

然后呢

这个轴它们方向相反

方向相反地去求得它们的这个

一开始的这个Support那个端点

然后呢

端点做一次连线形成

形成了一个新的轴

这个轴呢

再做一次

这个Support

然后相当于就是两两的去做这种

做这种Support的操作

最后呢

你在在第三个图里面

你可以得到就是其实4个点

然后其实是两个线段

现在大家看这个两个线段之间的距离

是不是比较接近两个凸包之间的距离

就从图上是可以看出来的

做这个操作还可以继续做一个操作

继续做一个操作呢

就是说求你求两个直线之间的最短距离

就是两个直线之间的最短距离可以讲一下

其实就是说你可以构建一个

就是说两个直线都所在的

平行的平面

简单的

直接的讲就是简单的直线

比如说

比如这是两根直线对吧

它们的位置可能是

就是说这种它不是这种平行的

是可能是

就是说一些交叉并且不相交

那其实我可以以构建构建出它们两

把一个直线的先平移一下

构建出个平面

那这两个平面之间的距离

其实就是这两个直线的那个距离对吧

记得刚才讲的

那就是说你不断的求

你可以也从两个点两点间的距离

变为两个直线的距离

也可以变为两个三角形的距离

也可以变成两个四面体的距离

基本上你求到大概两个三角形的距离

其实已经是比较就是说

就是说基本上误差已经就是说比较小了

那你还可以继续求那个四面体的那个距离

那就基本就比较精确

那这个呢

因为在计算机里面的我也讲过

就是说很多情况下

其实无法求得精确值的

只要近似值就行了

而且要考虑到算法

它的那个性能开销

绝对不会迭代太多的步骤

一般来说

在物理引擎的话

它求解的两个这种碰撞体积距离

基本上大概是这个迭代

也就是迭代到这个两个四面体之间的距离