collisione con una maglia di punti

Question

Voglio evitare che il mio giocatore possa stare all'interno delle mura. Ogni partita spunta il mio giocatore si muove di una piccola distanza e/o ruota.

TL; DR inserire una variante del classico line-segmento -> - algoritmo di intersezione triangolo che restituisce quasi incidenti troppo, o risolvere il problema in un altro modo Il segmento di linea interseca se passa all'interno di una data la distanza del triangolo. C'è un sacco di sottigliezza del problema, come angoli del luogo del triangolo arrotondati e se il segmento di linea è tangenziale al triangolo.

Ho il solito codice di intersezione raggio/triangolo.

Tuttavia, un raggio è un'approssimazione molto scarsa di un giocatore in movimento! Ho dei problemi con i bordi mancanti del centro del giocatore, ma la mesh del giocatore passa attraverso di loro.

Come determinare in modo efficace quando e dove un giocatore si scontra con muri e ostacoli in un ambiente 3D?

Un approccio generale sarebbe quello di avere codice triangolo quasi-miss, in cui il raggio è un cilindro con la sfera.

La soluzione generale che ho provato a fare è immaginare che il giocatore sia una sfera; capovolgendola, ho provato a creare una mesh che è più grande del raggio delle pareti reali e fare dei raggi di collisione su quello. Voglio calcolare una mesh che è una certa distanza fissa davanti a questa maglia, cioè un cubo si espanderebbe per essere un cubo leggermente più grande con bordi e angoli arrotondati. (Le mie maglie sono piuttosto meno regolari di un cubo. Immagina una rappresentazione a maglie all'interno di un locale caldaia, e immagina di provare a calcolare una maglia che è a 20 cm da tutte le pareti e caldaie e telai delle porte e così in quella stanza.) Ecco un semplice maglia intorno ad un barilotto:

Per ogni faccia posso calcolare la superficie normale; questo è il modo in cui so in che modo "fuori".

Il mio brainstorming mi fa immaginare moltiplicare la normale di ogni faccia per la distanza fissa e quindi emettere un triangolo con l'offset corrispondente.

Ciò tuttavia lascerebbe dei buchi ai bordi e forse (?) Causerebbe il passaggio di alcuni bordi attraverso angoli acuti molto stretti?

Posso anche immaginare di unire ciascun bordo come cilindri con estremità a sfera e così via.

L'approccio che ho usato per il barile sopra è quello di calcolare la media normale di tutte le facce che condividono un vertice e quindi moltiplicare quella per il raggio di collisione. Non affronta bene gli angoli acuti e cosa fare se un vertice è falsamente condiviso tra facce opposte?

Calcolo questa mesh e quindi eseguo le intersezioni di raggio in Javacsript. Quindi anche le prestazioni sono una considerazione. Una mesh troppo fine e dettagliata sarà costosa per eseguire il rilevamento delle collisioni.

Come è possibile calcolare efficacemente una mesh di loci sufficientemente buona? Oppure intersezione a triangolo fuzzy localizzato? O c'è un modo migliore per fare collisione, e può in qualche modo modellare che le cose si muovono in archi piuttosto che in linee rette?

Answer 1

(nessuno ha raccolto la taglia :(Nathan Reed on gamedev.stackexchange aiutato con la terminologia. Si chiama intersezione triangolo capsula triangolo.)

La sua matematica sorprendentemente complessa e googling non trova molto codice pronto da copiare.

A standard way A estrusione il triangolo dal raggio, aggiungere anche testare ciascuno dei tre bordi del triangolo come capsule.

Per estrudere il triangolo, basta moltiplicare la normale del triangolo per il raggio della capsula, sfalsare ciascun angolo del triangolo di tale valore e quindi eseguire il normale test del triangolo del segmento di linea su di esso.

Il test della capsula per ciascun bordo del triangolo è piuttosto più costoso in quanto è necessario farlo tre volte. È possibile che l'uso delle coordinate baricentriche dal test del triangolo aiuterà ad evitare alcuni dei test del bordo della capsula, ma non ci ho pensato. Puoi anche evitare il test della capsula sui bordi che sono condivisi con altri triangoli che sono abbastanza ottusi; puoi calcolarlo e segnare quei bordi. Non mi sono preoccupato (ancora).

Ho trovato che pre-calcolare la sfera di delimitazione di ogni faccia e fare un test di intersezione con la sfera di delimitazione della capsula era un modo super-economico per evitare questo costoso test per la maggior parte del tempo. Pre-computo anche le normali di ogni faccia, anche se è una vittoria più piccola.

Poiché il test è così costoso, la cosa migliore da fare è trattare il giocatore come una singola sfera e il codice di intersezione dare un elenco di incroci di volti. Puoi quindi modellare il giocatore come una serie di sfere più piccole che volano in formazione, e devi solo fare il codice di intersezione della faccia della capsula per i volti che il primo passaggio ha trovato con la sfera più grande.