Как обнаружить пересечение двух лиц в 3D

К сожалению, игнорируйте мой комментарий: подумал о другом способе сделать это.

• Шаг 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) возвращает 1, то они определенно пересекаются (возвращают true немедленно).
• Если все из них возвращают 0, тогда они не пересекаются.
• Если одна из проверок возвращает 2 (первая проверка, вероятно, сделает это), тогда нам нужен другой метод. Остановите эти проверки и немедленно перейти к шагу 2.

• Шаг 2:

Эта часть предназначена для того, если полигоны копланарны (т.е. параллельны и находятся в одной плоскости). На этот раз взять все F1Края и все F2краешки; для каждого из F1края, проверьте, пересекается ли он с любым из F2ребра, и если одна пара пересекается, вернуть 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);
}