再论向量在游戏中的应用(3) Point In Triangle (PIT)

问题概述

如何判断一个给定的P点是否在一个三角形中. 解法有两种,两种方式也都在这篇著名的文章中提到了

同边解法

这个解法最好理解,但是计算速度不是最优. 用到的核心算法就是 使用向量叉积判断是否在一个向量的同一侧. (原理在 再论向量在游戏中的应用-1 )中有描述.

所以 首先 构建判断是否在同一侧的函数

1
2
3
4
5
function SameSide(p1,p2, a,b)
cp1 = CrossProduct(b-a, p1-a)
cp2 = CrossProduct(b-a, p2-a)
if DotProduct(cp1, cp2) >= 0 then return true
else return false

因为 p点 一定在 a,b 所在的平面 所以 cp1 和 cp2 两个向量 就是垂直于 该平面的, 无非是同方向 或者异方向.

如果这个平面正好是2D x-y平面的话 那可以直接用 cp1.z * cp2.z >=0 去比较正负即可. 但是如果 ABC构成的三角形是 三维内 任意一三角形. 此时cp1.z * cp2.z 就没有任何几何意义了.

cp1 点乘 cp2 :

因为 cp1 和 cp2的 关系 无非就是 0度或者180度 所以 cp1 点乘 cp2 的结果 也 无非就是 正/负 cp1 在 cp2 上的投影长度.

不关心长度问题,所以只取得 正负号 就可以判断 两个向量的夹角是 0度 还是 180度了. 从而判断出 p1 和 p2 是同侧 还是 异侧.

当可以判断出 同侧还是异侧以后,后续的逻辑就很简单了. 直接

1
2
3
function PointInTriangle(p, a,b,c)
if SameSide(p,a, b,c) and SameSide(p,b, a,c and SameSide(p,c, a,b) then return true
else return false

重心坐标(Barycentric Coordinates) 解法

Barycentric Coordinates 也是一个很重要的概念,其用处也非常广泛. 具体如何理解 还是继续从 这篇著名的文章的 第二种解法谈起

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v < 1)

这个解法理解起来有几个难点

为何任意一点P 可以表述为:

P = A + u (C - A) + v (B - A)

为何 u,v 满足如下三个条件时候 点P会才在三角形内

(u >= 0) && (v >= 0) && (u + v < 1

为何 u,v 可以表述为:

u = (dot11 dot02 - dot01 dot12) x invDenom
v = (dot00 dot12 - dot01 dot02) x invDenom

重心坐标的理解

先说前两个问题, 在解释 三角形的 P = A + u * (C - A) + v * (B - A) 之前 ,首先来看

对于线段AB上的一点P的重心坐标表示法.

首先 在 再论向量在游戏中的应用(2) 中 我已经说过 直线的参数式表达法. 所以对于 线段AB,上的一点P 可以表述为

摘自 Realtime Collision Detection,3.4 Barycentric Coordinates

As a simple example of barycentric coordinates, consider two points, A and B. A point P on the line between them can be expressed as P = A + t(B − A) = (1 − t)A + tB or simply as P = uA + vB, where u + v = 1. P is on the segment AB if and only if 0 ≤ u ≤ 1 and 0 ≤ v ≤ 1. Written in the latter way, (u, v) are the barycentric coordinates of P with respect to A and B. The barycentric coordinates of A are (1, 0), and for B they are (0, 1).

u,v 也就是 P点 对于 向量A,B的 barycentric coordinates描述, 并且 注意一点的是 u,v的取值空间都是[0,1], 超过这个范围的u,v所描述的P点 不在AB上

u + v = 1 - t + t = 1

按照Realtime Collision Detection后续的介绍

A typical application of barycentric coordinates is to parameterize triangles (or the planes of the triangles). Consider a triangle ABC specified by three noncollinear points A, B, and C. Any point P in the plane of the points can then be uniquely expressed as P = uA + vB + wC for some constants u, v, and w, where u + v + w = 1. The triplet (u, v, w) corresponds to the barycentric coordinates of the point. For the

对于由A,B,C三点构成的三角形,其内部的P点 也可以描述为

P = uA + vB + wC

并且满足 u + v + w =1 ,u,v,w的取值空间都在[0,1]之间

又因为u = 1 - v + w

P = (1 − v − w)A + vB + wC
= A - vA -wA + vB + wC
= A + vB - vA + wC - wA
= A + v(B-A) + w(C-A)

u,v 求解推算

前两个问题搞定以后就差最后一个 u,v的求解.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Compute barycentric coordinates (u, v, w) for
// point p with respect to triangle (a, b, c)
void Barycentric(Point a, Point b, Point c, Point p, float &u, float &v, float &w) {
Vector v0 = b - a, v1 = c - a, v2 = p - a;
float d00 = Dot(v0, v0);
float d01 = Dot(v0, v1);
float d11 = Dot(v1, v1);
float d20 = Dot(v2, v0);
float d21 = Dot(v2, v1);
float denom = d00 * d11 - d01 * d01;
v = (d11 * d20 - d01 * d21) / denom;
w = (d00 * d21 - d01 * d20) / denom;
u = 1.0f - v - w;
}

其实比较晕的是 为何 两边是 点乘 v0 和 v1 最后联立两个方程组 求解, 为何不可以直接 叉乘 v0,v1 这样直接就把v0和v1个消除了.

因为PIP问题求解里面就是这么搞的. 后来我又大概查了一下. 可能是因为 向量无法做除法. 向量除向量 应该就已经失去 数学意义了.

但是PIP里面 判断线段相交问题时候的确做了 向量除法. 可能向量除法只是在2D平面内有意义吧. 暂且先这么理解好了.

坚持原创技术分享,您的支持将鼓励我继续创作!