我在3D空间中的某处有一条直线和一个三角形。换句话说，我的三角形有3个点(每个[x，y，z])，直线有2个点(也有[x，y，z])。
我需要找出一种方法(希望使用C++)来确定直线是否与三角形相交。平行于三角形且有多个共同点的线应被视为“不相交”。
我已经编写了一些代码，但是它不起作用，即使视觉表示清楚地显示了相交点，我也总是会出错。
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()的定义
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)如果只想知道直线是否与三角形相交(不需要实际的交点):
让p1,p2,p3表示您的三角形
在两个方向上都很远的线上选择两个点q1,q2。
令SignedVolume(a,b,c,d)表示四面体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)具有相同的符号，然后有一个交集。
SignedVolume(a,b,c,d) = (1.0/6.0)*dot(cross(b-a,c-a),d-a)
以参数形式编写直线方程:
p(t) = q1 + t*(q2-q1)编写平面方程:dot(p-p1,N) = 0其中N = cross(p2-p1, p3-p1)
p(t)注入(inject)平面方程: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)更有效的算法现在，我们在以下方面研究该算法:
Möller和Trumbore，《快速，最小存储射线三角交叉点》，
图形工具杂志，第一卷。 2，1997年，第2页。 21–28
(也可以看看:)
https://en.wikipedia.org/wiki/M%C3%B6ller%E2%8%93Trumbore_intersection_algorithm
最终，该算法更简单(比我们在1和2)中做的指令少)，但在理解上却要复杂得多。让我们一步一步地得出它。
符号:
O =射线的起源，D =射线的方向 vector ，A,B,C =三角形的顶点射线上的任意点P可以写成
P = O + tD三角形上的任意点P可以写为P = A + uE1 + vE2，其中E1 = B-A和E2 = C-A, u>=0, v>=0和(u+v)<=1编写P的两个表达式可得出:O + tD = A + uE1 + vE2
uE1 + vE2 -tD = O-A
[u]
[E1|E2|-D] [v] = O-A
[t]
使用Cramer公式解决以下问题:
[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) = 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)
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底纹或纹理映射)。不错的是，您可以免费获得它们!请注意，该代码是无分支的。
我的一些着色器在ShaderToy上使用了它
关于c++ - 3D中线与三角形之间的交点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42740765/