Rilevamento collisioni punto-triangolo in 3D

Question

Come posso correggere l'errore in virgola mobile nella seguente simulazione fisica:

• Punto originale (x, y, z),
• Punto desiderato (x', y', z') dopo l'applicazione delle forze.
• Due triangoli (A, B, C) e (B, C, D), che condividono il bordo BC

Sto usando questo metodo per il rilevamento delle collisioni:

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

Il problema che sto riscontrando è che a volte il punto cade nell'area grigia della matematica in virgola mobile dove è così vicino alla linea BC che non riesce a scontrarsi con nessuno dei triangoli, anche se tecnicamente dovrebbe sempre scontrarsi con l'uno o l'altro poiché condividono un vantaggio.Quando ciò accade, il punto passa proprio tra i due triangoli che condividono i bordi.Ho contrassegnato una riga del codice con (!) perché credo che sia lì che dovrei fare un cambiamento.

Un'idea che funziona in situazioni molto limitate è saltare il test dei bordi.Trasformando efficacemente i triangoli in piani.Funziona solo quando le mie mesh sono scafi convessi, ma ho intenzione di creare forme convesse.

Sto utilizzando specificamente il prodotto scalare e le normali triangolari per tutti i miei test fronte-retro.

Answer 1

Questo è un problema inevitabile quando si riprende un singolo raggio contro una geometria con bordi e vertici.È sorprendente come le simulazioni fisiche sembrino cercare la più piccola imprecisione numerica!

Alcune delle spiegazioni e soluzioni proposte da altri intervistati non funzioneranno.In particolare:

• L'imprecisione numerica può davvero far sì che un raggio "cada attraverso il vuoto".Il problema è che intersechiamo il raggio con il piano ABC (ottenendo il punto P, per esempio) prima di fare il test con la linea BC.Quindi intersechiamo il raggio con il piano BCD (ottenendo il punto Q, diciamo) prima di testarlo rispetto alla linea BC.P e Q sono entrambi rappresentati dall'approssimazione in virgola mobile più vicina;non c'è motivo di aspettarsi che questi si trovino esattamente sui piani su cui dovrebbero giacere, e quindi ogni possibilità che tu possa avere sia P a sinistra di BC che Q a destra di BC.

• L'uso del test minore o uguale non aiuta;il problema è l'imprecisione nell'intersezione tra il raggio e il piano.

• Il problema non sono le radici quadrate;puoi eseguire tutti i calcoli necessari utilizzando i prodotti scalari e la divisione in virgola mobile.

Ecco alcune soluzioni reali:

• Per le mesh convesse, puoi semplicemente testare tutti i piani e ignorare i bordi e i vertici, come dici tu (evitando così del tutto il problema).

• Non intersecare il raggio con ciascun triangolo a turno.Utilizzare invece il file prodotto triplo scalare.(Questo metodo esegue la stessa identica sequenza di calcoli per il raggio e il bordo BC quando si considera ciascun triangolo, garantendo che qualsiasi imprecisione numerica sia almeno coerente tra i due triangoli.)

• Per le mesh non convesse, dare una certa larghezza ai bordi e ai vertici.Cioè, posiziona una piccola sfera su ciascun vertice della mesh e posiziona un cilindro sottile lungo ciascun bordo della mesh.Interseca il raggio con queste sfere e cilindri nonché con i triangoli.Queste figure geometriche aggiuntive fermano il raggio che passa attraverso i bordi e i vertici della mesh.

Permettetemi di consigliare vivamente il libro Rilevamento delle collisioni in tempo reale di Christer Ericson.C'è una discussione di questo problema esatto alle pagine 446–448 e una spiegazione dell'approccio del triplo prodotto scalare per intersecare un raggio con un triangolo alle pagine 184–188.

Answer 2

Sembra che tu non includa i test se è SUL bordo (stai scrivendo "Bordi interni del triangolo").Prova a modificare il codice in "minore o uguale" (interno o sovrapposto).

Answer 3

Trovo alquanto improbabile che il tuo raggio cada esattamente tra i triangoli in modo tale che la precisione in virgola mobile abbia effetto.Sei assolutamente certo che questo sia davvero il problema?

In ogni caso, una soluzione possibile è invece di sparare un solo raggio per spararne tre molto vicini tra loro.Se uno cade esattamente nel mezzo, almeno uno degli altri due cadrà sicuramente su un triangolo.

Ciò ti consentirà almeno di verificare se il problema è davvero l'errore in virgola mobile o qualcosa di più probabile.

Answer 4

@Dichiarazione:In effetti sto già utilizzando un confronto "maggiore o uguale a" nel mio codice, grazie per il suggerimento.+1

La mia soluzione attuale è aggiungere una piccola quantità di spinta al test dei bordi.Fondamentalmente quando viene testato ciascun triangolo, i suoi bordi vengono spostati di una quantità molto piccola per contrastare l'errore in virgola mobile.Un po' come testare se il risultato di un calcolo in virgola mobile è inferiore a 0,01 invece di testare l'uguaglianza con zero.

È una soluzione ragionevole?

Answer 5

Se stai misurando la distanza, fai attenzione alle radici quadrate.Hanno la brutta abitudine di buttare via metà della tua precisione.Se accumuli alcuni di questi calcoli, puoi finire velocemente in grossi guai.Ecco una funzione di distanza che ho usato.

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

Poiché l'ultima operazione non è una radice quadrata, non si perde più la precisione.

L'ho scoperto in un progetto a cui stavo lavorando.Dopo averlo studiato e aver capito cosa faceva, ho rintracciato il programmatore che pensavo fosse incaricato di congratularsi con lui, ma non aveva idea di cosa stavo parlando.