判断空间点在三角形内部_迈克老狼

http://blog.sina.com.cn/u/1644101601

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

判断空间点在三角形内部

(2010-11-29 21:49:38)

分类：物理引擎

前面转了一个觉得不错的帖子，讲述3种判断空间点在三角形内部（在三角形平面内）的方法。

在Real-Time Collision Detection检测一书中，作者还介绍了同向法的另一种实施方式，并通过拉格朗日恒等式把同向法和重心法统一起来了。

下面看下作者是如何做的：

原理：给定三角形ABC, 如何判断一个空间点P在三角形ABC内呢？首先我们对点P和三角形做平移操作，把P点移到原点位置，现在问题就转化为：判断原点是否包含在平移后的三角形内。当且仅当三角形PAB、PBC、PCA同是顺时针或逆时针方向时，P才位于三角形ABC内（如图1所示）。现在我们可以通过求叉积u = B × C, v = C × A, w = A × B, 当u, v, w在同一方向，即u﹒v >= 0, u﹒w >= 0时，PAB, PBC, PCA 方向一致，即P位于三角形内部。

http://s12/middle/61feffe1496315792a10b&690

图1

实现代码如下：

1 
// Test if point P lies inside the counterclockwise triangle ABC

2 
int PointInTriangle(Point p, Point a, Point b, Point c)

3 
{

4 
// Translate point and triangle so that point lies at origin

5 
a-=p;b-=p;c-=p;

6 
// Compute normal vectors for triangles pab and pbc

7 
Vector u = Cross(b, c);

8 
Vector v = Cross(c, a);

9 
// Make sure they are both pointing in the same direction

10 
if (Dot(u, v) < 0.0f) return 0;

11 
// Compute normal vector for triangle pca

12 
Vector w = Cross(a, b);

13 
// Make sure it points in the same direction as the first two

14 
if (Dot(u, w) < 0.0f) return 0;

15 
// Otherwise P must be in (or on) the triangle

16 
return 1;

17 
}

18 
 

根据拉格朗日恒等式:

http://s16/middle/61feffe14963157b51a7f&690

则上面的代码可以转化为下面的形式，可以看到这个代码和重心法的实施代码很相似。

1 
// Test if point P lies inside the counterclockwise 3D triangle ABC

2 
int PointInTriangle(Point p, Point a, Point b, Point c)

3 
{

4 
// Translate point and triangle so that point lies at origin

5 
a-=p;b-=p;c-=p;

6 
float ab = Dot(a, b);

7 
float ac = Dot(a, c);

8 
float bc = Dot(b, c);

9 
float cc = Dot(c, c);

10 
// Make sure plane normals for pab and pbc point in the same direction

11 
if (bc * ac – cc * ab < 0.0f) return 0;

12 
// Make sure plane normals for pab and pca point in the same direction

13 
float bb = Dot(b, b);

14 
if (ab * bc – ac * bb < 0.0f) return 0;

15 
// Otherwise P must be in (or on) the triangle

16 
return 1;

17 
}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：判断点是否在三角形内(转帖)

后一篇：如何判定一个空间点在四面体内部？

新浪BLOG意见反馈留言板　欢迎批评指正

1	// Test if point P lies inside the counterclockwise triangle ABC
2	int PointInTriangle(Point p, Point a, Point b, Point c)
3	{
4	// Translate point and triangle so that point lies at origin
5	a-=p;b-=p;c-=p;
6	// Compute normal vectors for triangles pab and pbc
7	Vector u = Cross(b, c);
8	Vector v = Cross(c, a);
9	// Make sure they are both pointing in the same direction
10	if (Dot(u, v) < 0.0f) return 0;
11	// Compute normal vector for triangle pca
12	Vector w = Cross(a, b);
13	// Make sure it points in the same direction as the first two
14	if (Dot(u, w) < 0.0f) return 0;
15	// Otherwise P must be in (or on) the triangle
16	return 1;
17	}
18