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

就是现在我下一章要讲的三维距离

比如说在物理引擎和游戏里面很多时候

那你要去计算

你离它的一个距离

就是那这个距离就是这么

比如说一个物体

它可能是一个点

可能是一个球也可能是个包围体

甚至是一个一棵树

一个非常复杂的这种由三角网格

构成的一个Mesh

那在这里边的这种就是它是怎么来的

然后呢

我会从最简单最基础的

这种就是说

几何运算的开

然后呢

来就是来告诉大家

就是说整个如何去做这种

就是这种算法求解的

或者这种方法的就是从简单到复杂

到最终解决我们的那个问题

从最简单的那个开始

就是一个点到一个直线的最近点

这个在那个线性线性代数里面

其实是可以通过

就是你去给列一些

就是把它转化成方程

通过求解方程的机制

发生的机制来来求得

但求得那个就是说点到直线那个最近距离

然后在游戏这里面呢

或者在计算机里面

就是有一种非常简单的方法

这种简单的方法就是这里的是一个点

这里是一个射线的一个起点

就是这个是射线的方向

我们可以先找那个点的

做一个垂线

一个虚拟的垂线

这个垂线的相交点换一条这个呢

就应该是最近的点

不是应该是肯定

我们在连接这个P点和那个射线的起点

其实是可以构建出一个就是直角三角形的

直角三角形的

然后我们我们可以通过

就是说通过这个Lpoint到那个P

这个向量跟这个直线的那个向量

做一个点击

点击大家应该知道是一个什么操作吧

点击就是我简单讲下点击

点击就是求一个

应该是求他们两个就是两个向量

再在另外一个向量

一个向量在另外一个向量投影的一个长度

当然

其中要求其中一个向量是一个单位长度

所以这个射线的那个方向

它也是一个单位长度这样的求出来了

大概就是这一段的长度

这一段长度

我把它标明为T

刚才之前也讲到了

就是说一个直线的话

你可以通过它的那个参数化的方式

就是通过它的参数方式求出

你给定的参数然后呢

那个求得在那个直线上那个给定的那个点

就是对于那个参数录的那个那一点所以呢

这个整个的公式或者说这个方法呢

就是非常比较简单的

其实就是拿一个你的那个

那个目标点到

你那个射线起点的跟一个法线

就是跟那个直线的那个射线做一次点击

点击求的这个长度

然后再把这个长度呢

带入那个直线的那个参数和公式中

然后那就能直接的求到那个Npoint

然后在那边这边的那个运算的

其实都是这个是这个点击操作

很像Lpoint

LDir

然后呢

它们都是这里面那个向量

就是说做的一个三维向量操作

这个大家有没有疑问

这个应该是比较那个比较简单的

就是现在讲的是那个点到直线的距离

那点到线段的距离怎么算呢

其实跟刚才那个方法很类似

我们还是可以其实做一个虚拟的那个垂线

到这个直线上这个点

如果说

如果说这个点的是位于那个

位于两个直线两端的话

那肯定也就直接求出来

但是呢

有可能它并不落在那个那个线段的两端

这时候做一个什么样的操作呢

就是刚才讲到那个求道的那个T

我们把这个T的长

截取到那个PA就是个线段的长了一边

就让它不超过这个线段

在这张图里面

它这个T这个点了就会被挪到这个P点

然后再在通过刚才讲的就是那个直线的就是直线的参数化

那个公式的话

把这个就是截取

把T截取后的这个点的

截取后的这个参数就是参数代入方程式

就能求出这个比它线段上的这一点

就是我也做了一个简单的demo

就是来展示一下

就是用应用刚才这个公式的那个效果

我现在移动的这个呢

其实就是我刚才那个起点

然后呢

下面白色的这个呢

是一个线段

我现在就是说

每一帧都会去计算它们那个最近点距离

然后做一个连线

现在的是可以

看到就是说不管我怎么移动

上下移动

最后呢

目测这个这个结果是对的

回到刚才那个讲的点到线段的最近点

所以呢

其实像这种最基础的这个距离求解呢

其实也是应该是比较简单的

那如何求一个点

到一个就是一个AABB

就或者说一个轴对齐的一个Box

一个距离了

在这里面

其实这个操作的跟刚才

讲那个点到线段间的距离的操作

也很也有一定的类似

就是说我们可以直接把这个

就是Box外面的那个点的

把它截取到Box

比如说先在水平方向做也做一次截取

这时候的那个P点的就落于

这个落在这个位置

然后呢

再在对它进行纵坐标的一个截取

就落到了这个位置

然后呢

这个P应该是说最后截取的这个点

那就是其实就是离P点最近的

并且这个点是位于这个

Box那个表面上

刚才讲到了这个点到Box的那个距离

现在讲的就是说

在加一个维度就是我们

比如说如何求一个点到一个平面的最近点

其实这个呢

在现实生活中

或者说游戏里面其实是非常常用的

比如说做一些那种投影

的一些计算

就是基于之前的那个知识呢

我们其实就是说可以简单的理解的

就是说那个平面的是那个直线

在那个三维上的一种扩张

扩张那其实求一个刚才这个同学也讲到过

就是说像这个求解这种

就是那个矩阵的秩呢

就是说其实是一种广义上的一种体积

其实我那在那在这里面的

那个图给画出来了就是

其实我们是可以把这个平面

就是说

如果说

假设你的眼睛是刚好落在平面上

你在这个角度去看这个平面

说它其实是不是一条直线

在这里面就是说

我想表达的一个就是说一个一种做法呢

其实就是你可以把他这个平面的

就是说变成一条直线

但是呢

这个其实是要通过逐步的

就是说去降维去去做

这个只是一种思路

然后再在这里面在这个方法里面呢

其实也是非常简单的

就是对这个平面来说呢

跟那个射线其实是一样的

就说已知你平面的以上的任意一点

然后呢

并且已知它这个平面的那个方向

那你可以能通过求解这个点

在这个平面上的一个投影

然后再通过刚才讲的这个就是参数化方法

也可以把这个点给求出来

在这个方法里面的实际上

是通过求出这个就是这个point

到这个它假设的那个最近的那个点的向量

这个向量的那个具体的求法呢

就是

就是那个起点和平面上的一点去相减

所求得的一个向量的

跟这个平面的做一次那个点击

其实也是个得到的

会得到一个它的一个投影的长度

因为你已知这个平面的那个方向

那你也可以通过这个长度

去乘上这个平面的那个normal或者平面的方向

最后能得出这个向量

因为我们已知那个point

并且已经得出它们两相点的向量

然后呢

将它们那个point加上那个相减的向量的话

就能得出我平面上最近的一点

其实我们的整个事件呢

就是通常是刚才提到的一些简单的几何体

还有一些是一些模型比如说

比如说你用3Dmax或者玛雅来构建的

那些不管是模型什么的

基本上都是三角网格

那比如说我很多时候要求解

比如说某个点到这个叫什么这个模型的

最近的三角变或最近的点的话

那怎么求呢

其实它的那个基础算法呢

其实通过便利每一个三角形

最简单就是不考虑优化情况下

便利每个三角形

求出这个三角形到你的那个点的最近的点

最后不但都比较找到了

最后最终找到最近点

所以呢

这个算法的其实是和这个方法呢

它是其实是依赖于这个点

到三角形的那个最近点

这里面的我就做了一张图

就是ABC它是一个三角形

然后这个我们要求的是个P点

到那个三角形ABC最近的一个Q点

那这个怎么求呢

我们其实先可以考虑二维的情况

我们在二维情况的就是说

可以考虑把这个三角形的就是划分成

划分成七个区域

就是三角形的内部F区域

然后呢

三角形ABC

那个顶点的那个顶点区域

以及它的人的几个区域

就是如果说我们要求它那个

就是说那个起点的话

它可能会落在这七个区域中其中一个

那其实这个顶点区域

和它人区域以及它内部

那就需要用不同的那个算法那第一步呢

就是其实是求解

求解这个就是说

你这个点到底是在哪个区域

其实这个呢

也这个方法

其实我真的没有想详细的那个就是画出来

但是它的方法

大家可以聊

就是说了解就好了

就是说它其实是通过把这个你的那个顶点

在这个三条棱上做的次投影

做次投影

做一次投影的话

那你那个投影的值呢

如果是刚好是位于两个端点

两个三角形的端点之间的话

那它就属于一个人的区域

然后如果他是处于这个人的外面的话

处于人外面的话

它其实就是那个顶点那个区域

因为我们有两条能量条会相交

如果说它都是在那个两条人的

就是说的那个顶点区域的话

那它肯定就是位于这个就是顶点区域

这个顶点区域的话

也意味着就是说这个点

它离三角形最近的就是这个点

那就是如果它位于这个区的话呢

那你可以直接给出他那个最近的那个点了

其实就是三角形的顶点

这里的就是说写出了这个判断它

就是处于这个人这个区域的一个

这个表达式可以了解下就好了

如果一个点

它刚好落F区域话其实就是它自己

也就是说

其实像这种算法中

随着就是说你的几何体的

不断的复杂的

就是要通过各种不同的判断条件

走不同的程序分支来得到这个结果

就不是让最开始讲的

就是通过一个公式就可以

直接将它的那个最近的那个距离点

直接求出来

在这里呢

就是

我们可以有了这个点

到三角形的那个最近的距离呢

算法呢

那我们可以构建出点到四面体的最近距离

就是一下子就从这个就是一个平面的二D

来到一个三D

刚才忘讲了一个就是

就是这在3D里面

就是说这个刚才讲的呢

其实是一个二维平面的结果

如果那在让在3D情况下怎么解决呢

其实很简单

就是你做一次投影

就是把你那个起点投影

到那个三角形所在的平面

做一次这种那些降维

降维的操作就可以解决

那在这个3D空间中呢

比如对于现在3D空间中就是一些几何体

你像这个就是由三角形构成的

最简单的那个几何实体

3D实体其实就是一个四面体

四面体的话

那点到四面体的距离

其实你可以

结果就是讲之前讲的方法

就是便利这个四面体上

表面的所有的那个三角形就便利四次

那你就可以求出这个点

到这个四面体最近的那个距离了

顶点这里面

其实我是就是给出的

是一个就是说四面体相比较更复杂的

比如像人体

以及我们的那个就是在3D模型

比如说像房子

包括岩石

他们都是一个个的三角形去组合而成的

通过这个方法呢

就是你可以求得任意复杂吧

就是任意复杂东西

你都可以把它三角化三角化之后呢

然后你求的这个三角形

就是这个三角网格里面的点了

与它这个点这个你要求的点

那个最近的距离

也就可以通过这种方式来求出来