如何在 3D 中检测两个面的交集
How to detect intersection of two faces in 3D
让我们说
struct myFace
{
3DPoint p0;
3DPoint p1;
3DPoint p2;
3DPoint p3;
3DPoint pNormal;
};
face1 和 face2 是 myFace 类型的面孔。
double ac = face1.pNormal * face2.pNormal;
if (!(ac<1.00000001 && ac>0.99999999) && !(ac>-1.00000001 && ac<-0.99999999))
那么面不平行。
但是如何检测它们是否相交?
糟糕,请忽略我的评论:想到了另一种方法。
- 第 1 步:
对于面 F1
和 F2
,将 F2
的点作为两个 三角形 ,例如(p0, p1, p2)
和 (p1, p2, p3)
分别。然后取 F1
的边,即 (p0, p1)
、(p1, p2)
、(p2, p3)
和 (p3, p0)
,然后将它们中的每一个与两个三角形相交。
我找到了一些代码来执行此操作:(改编自 http://geomalgorithms.com/a06-_intersect-2.html)
#define SMALL_NUM 0.00000001
/*
returns: 0 if no intersection
1 if parallel but disjoint
2 if coplanar
*/
int intersect3D_RayTriangle(Vector P0, Vector P1, Vector V0, Vector V1, Vector V2)
{
Vector u, v, n; // triangle vectors
Vector dir, w0, w; // ray vectors
float r, a, b; // params to calc ray-plane intersect
// get triangle edge vectors and plane normal
u = V1 - V0;
v = V2 - V0;
n = cross(u, v);
dir = P1 - P0; // ray direction vector
w0 = P0 - V0;
a = -dot(n, w0);
b = dot(n, dir);
if (fabs(b) < SMALL_NUM) // ray is parallel to triangle plane
return (fabs(a) < SMALL_NUM ? 2 : 0);
// get intersect point of ray with triangle plane
r = a / b;
if (r < 0.0 || r > 1.0)
return 0; // => no intersect
Vector I = R.P0 + r * dir; // intersect point of ray and plane
// is I inside T?
float uu, uv, vv, wu, wv, D;
uu = dot(u, u);
uv = dot(u, v);
vv = dot(v, v);
w = I - V0;
wu = dot(w, u);
wv = dot(w, v);
D = uv * uv - uu * vv;
// get and test parametric coords
float s, t;
s = (uv * wv - vv * wu) / D;
if (s < 0.0 || s > 1.0) // I is outside T
return 0;
t = (uv * wu - uu * wv) / D;
if (t < 0.0 || (s + t) > 1.0) // I is outside T
return 0;
return 1; // I is in T
}
P0
和 P1
形成 F1
的边之一,而 V0
、V1
和 V2
形成 F2
的三角形。
- 如果其中一个检查(应该有8个)returns 1,那么它们肯定相交(return真立即)。
- 如果全部个return0,则不相交
- 如果其中一项检查 returns 2(第一次检查可能会这样做)那么我们需要一种不同的方法。停止这些检查并立即进入第 2 步。
- 第 2 步:
这部分适用于多边形是否共面(即平行且在同一平面内)。这次,取 F1
的所有边和 F2
的所有边;对于 F1
的每条边,检查它是否与 F2
的任何边相交,如果一对相交则 return true 立即 .
做这样的边相交:(改编自https://gist.github.com/hanigamal/6556506)
A0
、A1
形成来自 F1
的边,以及 B0
、B1
来自 F2
.
int intersection(Vector A0, Vector A1, Vector B0, Vector B1)
{
Vector dA = A1 - A0;
Vector dB = B1 - B0;
Vector dC = B0 - A0;
double s = dot(cross(dC, dB), cross(dA, dB)) / norm2(cross(dA, dB));
return (s >= 0.0 && s <= 1.0);
}
让我们说
struct myFace
{
3DPoint p0;
3DPoint p1;
3DPoint p2;
3DPoint p3;
3DPoint pNormal;
};
face1 和 face2 是 myFace 类型的面孔。
double ac = face1.pNormal * face2.pNormal;
if (!(ac<1.00000001 && ac>0.99999999) && !(ac>-1.00000001 && ac<-0.99999999))
那么面不平行。
但是如何检测它们是否相交?
糟糕,请忽略我的评论:想到了另一种方法。
- 第 1 步:
对于面 F1
和 F2
,将 F2
的点作为两个 三角形 ,例如(p0, p1, p2)
和 (p1, p2, p3)
分别。然后取 F1
的边,即 (p0, p1)
、(p1, p2)
、(p2, p3)
和 (p3, p0)
,然后将它们中的每一个与两个三角形相交。
我找到了一些代码来执行此操作:(改编自 http://geomalgorithms.com/a06-_intersect-2.html)
#define SMALL_NUM 0.00000001
/*
returns: 0 if no intersection
1 if parallel but disjoint
2 if coplanar
*/
int intersect3D_RayTriangle(Vector P0, Vector P1, Vector V0, Vector V1, Vector V2)
{
Vector u, v, n; // triangle vectors
Vector dir, w0, w; // ray vectors
float r, a, b; // params to calc ray-plane intersect
// get triangle edge vectors and plane normal
u = V1 - V0;
v = V2 - V0;
n = cross(u, v);
dir = P1 - P0; // ray direction vector
w0 = P0 - V0;
a = -dot(n, w0);
b = dot(n, dir);
if (fabs(b) < SMALL_NUM) // ray is parallel to triangle plane
return (fabs(a) < SMALL_NUM ? 2 : 0);
// get intersect point of ray with triangle plane
r = a / b;
if (r < 0.0 || r > 1.0)
return 0; // => no intersect
Vector I = R.P0 + r * dir; // intersect point of ray and plane
// is I inside T?
float uu, uv, vv, wu, wv, D;
uu = dot(u, u);
uv = dot(u, v);
vv = dot(v, v);
w = I - V0;
wu = dot(w, u);
wv = dot(w, v);
D = uv * uv - uu * vv;
// get and test parametric coords
float s, t;
s = (uv * wv - vv * wu) / D;
if (s < 0.0 || s > 1.0) // I is outside T
return 0;
t = (uv * wu - uu * wv) / D;
if (t < 0.0 || (s + t) > 1.0) // I is outside T
return 0;
return 1; // I is in T
}
P0
和 P1
形成 F1
的边之一,而 V0
、V1
和 V2
形成 F2
的三角形。
- 如果其中一个检查(应该有8个)returns 1,那么它们肯定相交(return真立即)。
- 如果全部个return0,则不相交
- 如果其中一项检查 returns 2(第一次检查可能会这样做)那么我们需要一种不同的方法。停止这些检查并立即进入第 2 步。
- 第 2 步:
这部分适用于多边形是否共面(即平行且在同一平面内)。这次,取 F1
的所有边和 F2
的所有边;对于 F1
的每条边,检查它是否与 F2
的任何边相交,如果一对相交则 return true 立即 .
做这样的边相交:(改编自https://gist.github.com/hanigamal/6556506)
A0
、A1
形成来自 F1
的边,以及 B0
、B1
来自 F2
.
int intersection(Vector A0, Vector A1, Vector B0, Vector B1)
{
Vector dA = A1 - A0;
Vector dB = B1 - B0;
Vector dC = B0 - A0;
double s = dot(cross(dC, dB), cross(dA, dB)) / norm2(cross(dA, dB));
return (s >= 0.0 && s <= 1.0);
}