Triangle Triangle Intersection in 3d-Space

Question

Sto lavorando con alcune geometrie 3d. Devo trovare l'intersezione del triangolo con un altro triangolo.

Quale algoritmo è possibile utilizzare?

Answer 1

Googling revelead this. Penso che lo spieghi in dettaglio!

Answer 2

Questo documento descrive un'implementazione:

http://knight.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf

Nota che ci sono tecniche diverse a seconda se si desidera conoscere il punto/segmento in cui si è verificato l'incrocio, o semplicemente dire se un Intersect accaduto. Questo documento ti darà il segmento di linea che rappresenta l'intersezione.

Answer 3

C'è una buona paper da Devillers et al con il titolo "più veloce test Triangolo-triangolo Intersezione" - (sì, ha fatto una ricerca su Google, ma le parole chiave di ricerca sono importanti ...)

In ogni caso, la loro punto (rispetto al documento Moeller nella risposta di MichaelM) è che dovresti davvero ottenere le tue informazioni combinatorie facendo determinanti di gruppi selezionati di 4 punti (il documento descrive come). Questo evita di calcolare valori intermedi che possono essere problematicamente incoerenti e che probabilmente non saranno in realtà più veloci ...

È possibile osservare questi fattori determinanti per capire se il tetraedro formato dai 4 punti è destrorso, mancino, o degenerato (cioè planare). Questo valore determina anche se uno dei 4 punti è su un lato o l'altro del piano formato dagli altri tre, e se la linea (diretta) formata da due qualsiasi dei 4 è su un lato o l'altro del linea formata dagli altri due.

Per farla breve, fare la cosa determinante rende la matematica più solida e, se si presta attenzione, di solito è possibile convertire algoritmi che inizialmente non hanno fatto la cosa determinante in quelli che lo fanno. Oppure potresti leggere il foglio.

Answer 4

Molte persone apparentemente si basano su un'implementazione (link to source code) del metodo descritto nel 2006 nel seguente articolo (link to PDF):

Tropp, Oren, Ayellet Tal, e Ilan Shimshoni. "Un triangolo veloce per il test di intersezione a triangolo per il rilevamento delle collisioni." Computer Animazione e mondi virtuali 17.5 (2006): 527-535.

V'è tuttavia un problema con quel codice (tranne che per l'adozione di un vecchio stile di programmazione, utilizzando notazioni non convenzionali e di sciogliere l'interpretazione geometrica sottostante): "cosa determinante" non necessariamente rendere la matematica più robusto, se fatto la strada sbagliata.

suggerisco usare sia il metodo di Moeller (link to PDF) oppure dare un'occhiata al giornale di Delliver (link to PDF), implementato nella libreria CGAL (link, "Triangle_3_Triangle_3_do_intersect.h").

Un esempio: la routine intersezione implementato precedente indica che i triangoli (p0, p1, p2) e (q0, q1, q2) definiti dai punti seguenti

p0 = (-21, -72, 63) 
p1 = (-78, 99, 40) 
p2 = (-19, -78, -83) 
q0 = (96, 77, -51) 
q1 = (-95, -1, -16) 
q2 = (9, 5, -21) 

non sono intersezione . Ecco una foto di triangoli:

E qui è il frammento di codice (aggiungere al codice originale):

#include <iostream> 

inline void setPoint(double p[3], const double x, const double y, const double z) 
{ 
    p[0] = x; p[1] = y; p[2] = z; 
} 

inline void computeEdges(double v0[3], double v1[3], const double p0[3], const double p1[3], const double p2[3]) 
{ 
    v0[0] = p1[0]-p0[0]; 
    v0[1] = p1[1]-p0[1]; 
    v0[2] = p1[2]-p0[2]; 
    v1[0] = p2[0]-p0[0]; 
    v1[1] = p2[1]-p0[1]; 
    v1[2] = p2[2]-p0[2]; 
} 

void main() 
{ 
    unsigned int numErrors(0), count(0); 
    double p0[3], p1[3], p2[3], q0[3], q1[3], q2[3]; 
    double v0[3], v1[3], w0[3], w1[3]; 
    bool res, answer; 
    int ret; 

    std::cout << "Testing the correctness of tr_tri_intersect3D" << std::endl; 

    { 
     // Non excluding triangles in generic positions, big determinants, intersecting 
     ++count; 
     setPoint(p0, -21, -72, 63); 
     setPoint(p1, -78, 99, 40); 
     setPoint(p2, -19, -78, -83); 
     setPoint(q0, 96, 77, -51); 
     setPoint(q1, -95, -1, -16); 
     setPoint(q2, 9, 5, -21); 
     answer = true; 

     computeEdges(v0, v1, p0, p1, p2); 
     computeEdges(w0, w1, q0, q1, q2); 
     int ret = tr_tri_intersect3D(p0, v0, v1, q0, w0, w1); 
     bool res = (ret != 0); 

     if(res != answer) 
     { 
      std::cout << "# wrong answer on test " << count << "!\n"; 
      ++numErrors; 
     } 
    } 

} 

Una nota finale sul numero di operazioni aritmetiche: poiché il metodo prende in input i vettori di bordo precompilati, 12 operazioni +/- devono essere aggiunte alla Tabella I. del foglio.

Ultimo ma non meno importante: si prega di verificare quello che sto scrivendo da solo e mi danno un feedback se pensate che ho frainteso qualcosa!