3D中线与三角形之间的交点 [英] Intersection between line and triangle in 3D
问题描述
我在3D空间中的某处有一条直线和一个三角形.换句话说，我的三角形有3个点(每个[x，y，z])，直线有2个点(也有[x，y，z]).
I have a line and a triangle somewhere in 3D space. In other words, I have 3 points ([x,y,z] each) for the triangle, and two points (also [x,y,z]) for the line.
我需要找出一种方法，希望使用C ++来确定直线是否与三角形相交.平行于三角形且有多个共同点的直线应算作不相交".
I need to figure out a way, hopefully using C++, to figure out if the line ever crosses the triangle. A line parallel to the triangle, and with more than one point in common, should be counted as "does not intersect".
我已经编写了一些代码，但是它不起作用，即使视觉表示清楚地显示了相交点，我也总是会报错.
I already made some code, but it doesn't work, and I always get false even when a visual representation clearly shows an intersection.
ofVec3f P1, P2;
P1 = ray.s;
P2 = ray.s + ray.t;
ofVec3f p1, p2, p3;
p1 = face.getVertex(0);
p2 = face.getVertex(1);
p3 = face.getVertex(2);
ofVec3f v1 = p1 - p2;
ofVec3f v2 = p3 - p2;
float a, b, c, d;
a = v1.y * v2.z - v1.z * v2.y;
b = -(v1.x * v2.z - v1.z * v2.x);
c = v1.x * v2.y - v1.y * v2.x;
d = -(a * p1.x + b * p1.y + c * p1.z);
ofVec3f O = P1;
ofVec3f V = P2 - P1;
float t;
t = -(a * O.x + b * O.y + c * O.z + d) / (a * V.x + b * V.y + c * V.z);
ofVec3f p = O + V * t;
float xmin = std::min(P1.x, P2.x);
float ymin = std::min(P1.y, P2.y);
float zmin = std::min(P1.z, P2.z);
float xmax = std::max(P1.x, P2.x);
float ymax = std::max(P1.y, P2.y);
float zmax = std::max(P1.z, P2.z);
if (inside(p, xmin, xmax, ymin, ymax, zmin, zmax)) {
*result = p.length();
return true;
}
return false;
这是inside()的定义
And here is the definition of inside()
bool primitive3d::inside(ofVec3f p, float xmin, float xmax, float ymin, float ymax, float zmin, float zmax) const {
if (p.x >= xmin && p.x <= xmax && p.y >= ymin && p.y <= ymax && p.z >= zmin && p.z <= zmax)
return true;
return false;
}
推荐答案
1)如果您只想知道是否线与三角形相交(不需要实际的交点):
1) If you just want to know whether the line intersects the triangle (without needing the actual intersection point):
让p1,p2,p3表示您的三角形
在两个方向上相距很远的直线上选择两个点q1,q2.
Pick two points q1,q2 on the line very far away in both directions.
让SignedVolume(a,b,c,d)表示四面体a，b，c，d的有符号体积.
Let SignedVolume(a,b,c,d) denote the signed volume of the tetrahedron a,b,c,d.
如果SignedVolume(q1,p1,p2,p3)和SignedVolume(q2,p1,p2,p3)具有不同的符号并且
SignedVolume(q1,q2,p1,p2)，SignedVolume(q1,q2,p2,p3)和SignedVolume(q1,q2,p3,p1)具有相同的符号，然后有一个交集.
If SignedVolume(q1,p1,p2,p3) and SignedVolume(q2,p1,p2,p3) have different signs AND
SignedVolume(q1,q2,p1,p2), SignedVolume(q1,q2,p2,p3) and SignedVolume(q1,q2,p3,p1) have the same sign, then there is an intersection.
SignedVolume(a,b,c,d) = (1.0/6.0)*dot(cross(b-a,c-a),d-a)
2)现在，如果您想要相交，则当1)中的测试通过时
以参数形式编写直线方程:p(t) = q1 + t*(q2-q1)
write the equation of the line in parametric form: p(t) = q1 + t*(q2-q1)
写平面方程:dot(p-p1,N) = 0其中
N = cross(p2-p1, p3-p1)
将p(t)注入到平面方程中:dot(q1 + t*(q2-q1) - p1, N) = 0
Inject p(t) into the equation of the plane: dot(q1 + t*(q2-q1) - p1, N) = 0
展开:dot(q1-p1,N) + t dot(q2-q1,N) = 0
推导t = -dot(q1-p1,N)/dot(q2-q1,N)
交点为q1 + t*(q2-q1)
3)一种更高效的算法
我们现在在以下方面研究算法:
We now study the algorithm in:
Möller和Trumbore，快速，最小存储射线三角交叉点"， 图形工具杂志，第一卷. 2，1997年，第2页. 21–28
Möller and Trumbore, « Fast, Minimum Storage Ray-Triangle Intersection », Journal of Graphics Tools, vol. 2, 1997, p. 21–28
(另请参见:)
https://en.wikipedia.org/wiki /M％C3％B6ller％E2％8％93Trumbore_intersection_algorithm
最后，该算法更简单(比我们在1和2)中做的指令少)，但在理解上却要复杂得多.让我们一步一步地得出它.
The algorithm is in the end simpler (less instructions than what we did in 1) and 2)), but sightly more complicated to understand. Let us derive it step by step.
符号:
-
O=射线的起源，
D =射线的方向向量，
D = direction vector of the ray,
A,B,C =三角形的顶点
射线上的任意点P可以写为P = O + tD
An arbitrary point P on the ray can be written as P = O + tD
三角形上的任意点P可以写为P = A + uE1 + vE2，其中E1 = B-A和E2 = C-A, u>=0, v>=0和(u+v)<=1
An arbitrary point P on the triangle can be written as P = A + uE1 + vE2 where E1 = B-A and E2 = C-A, u>=0, v>=0 and (u+v)<=1
同时编写两个P表达式可得出:
Writing both expressions of P gives:
O + tD = A + uE1 + vE2
或:
uE1 + vE2 -tD = O-A
以矩阵形式:
[u]
[E1|E2|-D] [v] = O-A
[t]
(其中[E1 | E2 | -D]是以E1，E2，-D为列的3x3矩阵)
(where [E1|E2|-D] is the 3x3 matrix with E1,E2,-D as its columns)
使用Cramer公式解决以下问题:
Using Cramer's formula for the solution of:
[a11 a12 a13][x1] [b1]
[a12 a22 a23][x2] = [b2]
[a31 a32 a33][x3] [b3]
给予:
|b1 a12 a13| |a11 a12 a13|
x1 = |b2 a22 a23| / |a21 a22 a23|
|b3 a32 a33| |a31 a32 a33|
|a11 b1 a13| |a11 a12 a13|
x2 = |a21 b2 a23| / |a21 a22 a23|
|a31 b3 a33| |a31 a32 a33|
|a11 a12 b1| |a11 a12 a13|
x3 = |a21 a22 b2| / |a21 a22 a23|
|a31 a32 b3| |a31 a32 a33|
现在我们得到:
u = (O-A,E2,-D) / (E1,E2,-D)
v = (E1,O-A,-D) / (E1,E2,-D)
t = (E1,E2,O-A) / (E1,E2,-D)
其中(A，B，C)表示以A，B，C作为列向量的3x3矩阵的行列式.
where (A,B,C) denotes the determinant of the 3x3 matrix with A,B,C as its column vectors.
现在我们使用以下身份:
Now we use the following identities:
(A,B,C) = dot(A,cross(B,C)) (develop the determinant w.r.t. first column)
(B,A,C) = -(A,B,C) (swapping two vectors changes the sign)
(B,C,A) = (A,B,C) (circular permutation does not change the sign)
现在我们得到:
u = -(E2,O-A,D) / (D,E1,E2)
v = (E1,O-A,D) / (D,E1,E2)
t = -(O-A,E1,E2) / (D,E1,E2)
使用:
N=cross(E1,E2);
AO = O-A;
DAO = cross(D,AO)
我们最终获得以下代码(此处为GLSL，易于翻译为其他语言):
We obtain finally the following code (here in GLSL, easy to translate to other languages):
bool intersect_triangle(
in Ray R, in vec3 A, in vec3 B, in vec3 C, out float t,
out float u, out float v, out vec3 N
) {
vec3 E1 = B-A;
vec3 E2 = C-A;
N = cross(E1,E2);
float det = -dot(R.Dir, N);
float invdet = 1.0/det;
vec3 AO = R.Origin - A;
vec3 DAO = cross(AO, R.Dir);
u = dot(E2,DAO) * invdet;
v = -dot(E1,DAO) * invdet;
t = dot(AO,N) * invdet;
return (det >= 1e-6 && t >= 0.0 && u >= 0.0 && v >= 0.0 && (u+v) <= 1.0);
}
当函数返回true时，交点由R.Origin + t * R.Dir给出.三角形中交点的重心坐标为u，v，1-u-v(适用于Gouraud阴影或纹理映射).不错的是，您可以免费获得它们！
When the function returns true, the intersection point is given by R.Origin + t * R.Dir. The barycentric coordinates of the intersection in the triangle are u, v, 1-u-v (useful for Gouraud shading or texture mapping). The nice thing is that you get them for free !
请注意，该代码是无分支的. 我的一些着色器在ShaderToy上使用了它
Note that the code is branchless. It is used by some of my shaders on ShaderToy
- https://www.shadertoy.com/view/tl3XRN
- https://www.shadertoy.com/view/3ltSzM
这篇关于3D中线与三角形之间的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
