游戏思考19：游戏多维计算相关：点乘、叉乘、点线面距离计算

最近刷leecode遇到了这个问题，所以顺便记录下

一、点乘

1）公式

对于向量a和向量b：

a和b的点积公式为：

2）要求

要求一维向量a和向量b的行列数相同。

3）几何意义

表征或计算两个向量之间的夹角，以及在b向量在a向量方向上的投影，有公式：

推导过程如下，首先看一下向量组成：

定义向量c：

根据三角形余弦定理有：

根据关系c=a-b（a、b、c均为向量）有：

向量a，b的长度都是可以计算的已知量，从而有a和b间的夹角θ：

根据这个公式就可以计算向量a和向量b之间的夹角。从而就可以进一步判断这两个向量是否是同一方向，是否正交(也就是垂直)等方向关系，具体对应关系为：

1） a·b>0    方向基本相同，夹角在0°到90°之间
2）a·b=0    正交，相互垂直  
3） a·b<0    方向基本相反，夹角在90°到180°之间 
1
2
3

二、叉乘

1）叉乘公式

• 概念
  两个向量的叉乘，又叫向量积、外积、叉积，叉乘的运算结果是一个向量而不是一个标量。并且两个向量的叉积与这两个向量组成的坐标平面垂直。

对于向量a和向量b：

a和b的叉乘公式为：

其中：

根据i、j、k间关系，有：

2）几何意义（1、构建法向量，2、计算平行四边形面积）

1）在三维几何中，向量a和向量b的叉乘结果是一个向量，更为熟知的叫法是法向量，该向量垂直于a和b向量构成的平面。
（在3D图像学中，叉乘的概念非常有用，可以通过两个向量的叉乘，生成第三个垂直于a，b的法向量，从而构建X、Y、Z坐标系。如下图所示： ）


那么这个时候的a，b向量的叉乘结果

c=a×b=(a.x,a.y,a.z)×(b.x,b.y,b.z)=(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * 
b.x)=(0,0,a.x * b.y - a.y * b.x)
即 c.z=a.x * b.y - a.y * b.x
1
2
3

关于向量的叉乘右手定则判方向
如果k>0时，那么a正旋转到b的角度为<180°，
如果k<0，那么a正旋转到b的角度为>180°,
如果k=0 那么a，b向量平行。
1）a×b的方向：四指由a开始，指向b，拇指的指向就是a×b的方向，垂直于a和b所在的平面
2）b×a的方向：四指由b开始，指向a，拇指的指向就是b×a的方向，垂直于b和a所在的平面；
3）a×b的方向与b×a的方向是相反的，且有：a×b=-b×a。

2）在二维空间中，叉乘还有另外一个几何意义就是：aXb等于由向量a和向量b构成的平行四边形的面积。

3）以leetcode题举例（这里没有z轴，故z轴坐标计算的值都为0）

• 469.凸多边形

• 输入

输入: points = [[0,0],[0,5],[5,5],[5,0]]
输出: true
1
2

• 思路：
  ①设点0为A点，A点坐标(0,5)；点B点为(0,5);点C为(5,0);点D为(0,0);
  ②算出AB、BC的法向量

int tmp = x1*y2 - x2*y1;
1

③算出BC和CD的法向量，与AB、BC的对比，小于0说明法向量相反，不是凸多边形

            if (tmp != 0)               
            {
                if ((long long)pre * tmp < 0)  //与上一次的法向量的方向相反
                    return false;
                pre = tmp; //保存上次结果   
            }
1
2
3
4
5
6

三、计算点线面举例问题

1）点到线段的最短距离

• 相关代码如下：

static float distancePtSeg2d(const float* pt, const float* p, const float* q)
{
	float pqx = q[0] - p[0];
	float pqz = q[2] - p[2];
	float dx = pt[0] - p[0];
	float dz = pt[2] - p[2];
	float d = pqx*pqx + pqz*pqz;
	float t = pqx*dx + pqz*dz;
	if (d > 0)
		t /= d;
	if (t < 0)
		t = 0;
	else if (t > 1)
		t = 1;
	
	dx = p[0] + t*pqx - pt[0];
	dz = p[2] + t*pqz - pt[2];
	
	return dx*dx + dz*dz;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2）点到多边形的最短距离

先计算点到多边形所有边的距离，取最小值。如果点在多边形内，则取负数。可以利用射线法判断点是否在多边形内，如果射线与多边形的奇数条边相交，则表示点在多边形内部。

• 相关代码如下：

static float distToPoly(int nvert, const float* verts, const float* p)
{
	
	float dmin = FLT_MAX;
	int i, j, c = 0;
	for (i = 0, j = nvert-1; i < nvert; j = i++)
	{
		const float* vi = &verts[i*3];
		const float* vj = &verts[j*3];
		if (((vi[2] > p[2]) != (vj[2] > p[2])) &&
			(p[0] < (vj[0]-vi[0]) * (p[2]-vi[2]) / (vj[2]-vi[2]) + vi[0]) )
			c = !c;
		dmin = rcMin(dmin, distancePtSeg2d(p, vj, vi));
	}
	return c ? -dmin : dmin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3）点到三角面的距离

当投影点P1在三角形外时，距离取FLT_MAX；当投影点P1在三角形内时，距离为点P与点P1的y坐标之差的绝对值。投影点P1在三角形内需要满足的条件为：

• 相关代码如下：

static float distPtTri(const float* p, const float* a, const float* b, const float* c)
{
	float v0[3], v1[3], v2[3];
	rcVsub(v0, c,a);
	rcVsub(v1, b,a);
	rcVsub(v2, p,a);
	
	const float dot00 = vdot2(v0, v0);
	const float dot01 = vdot2(v0, v1);
	const float dot02 = vdot2(v0, v2);
	const float dot11 = vdot2(v1, v1);
	const float dot12 = vdot2(v1, v2);
	
	// Compute barycentric coordinates
	const float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
	const float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
	float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
	
	// If point lies inside the triangle, return interpolated y-coord.
	static const float EPS = 1e-4f;
	if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS)
	{
		const float y = a[1] + v0[1]*u + v1[1]*v;
		return fabsf(y-p[1]);
	}
	return FLT_MAX;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27