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

Question

позволяет говорить

struct myFace 
{ 
    3DPoint p0; 
    3DPoint p1; 
    3DPoint p2; 
    3DPoint p3; 
    3DPoint pNormal; 

}; 

face1 и face2 это лицо, которые типа myFace.

double ac = face1.pNormal * face2.pNormal; 

если (! (Ас < 1,00000001 & & переменного тока> 0.99999999) & &! (С> -1.00000001 & & ас < -0.99999999))

то грани не параллельны друг другу.

но как определить, пересекаются ли они или нет?

Answer 1

Упс игнорировать мой комментарий: подумал о другом способе сделать это.

---

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

---

• Шаг 2:

Эта часть предназначена для если многоугольники лежат в одной плоскости (т.е. параллельно и в одной и той же плоскости) , На этот раз возьмите все края F1 и все края F2; для каждого из краев F1, проверьте, пересекается ли он с любым из краев F2, и если одна пара пересекается, то сразу возвращается значение .

Чтобы сделать такое ребро пересечения: (адаптировано из 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); 
}