Miglioramento della simulazione e delle prestazioni con un solutore fisico avanzato
Nel 2016 abbiamo aggiunto il supporto per una serie diversificata di nuovi vincoli fisici, incentivando gli sviluppatori a migrare al nuovo solutore ed estendendo le capacità creative del motore fisico. Tutti i nuovi luoghi utilizzavano il solutore PGS per impostazione predefinita, con la possibilità di tornare al solutore classico.
A metà del 2018 abbiamo risolto alcuni problemi di stabilità legati a grandi differenze di massa e meccanismi complessi introducendo il risolutore ibrido LDL-PGS. Questo ha reso obsoleto il vecchio risolutore, che è stato completamente disabilitato nel 2019, migrando automaticamente tutti i luoghi al PGS.
Nel 2019, le prestazioni sono state ulteriormente migliorate utilizzando il multi-threading che divide la simulazione in lavori costituiti da isole collegate di parti simulate. Avevamo ancora problemi di prestazioni relativi all'LDL che abbiamo finalmente risolto all'inizio del 2020.
Il motore fisico è ancora in fase di miglioramento e ottimizzazione delle prestazioni e prevediamo di aggiungere nuove funzionalità nel prossimo futuro.
Implementazione delle leggi della fisica
L'obiettivo principale di un motore fisico è simulare il movimento dei corpi in un ambiente virtuale. Nel nostro motore fisico, ci occupiamo di corpi rigidi, che entrano in collisione e hanno vincoli tra loro.
Un motore fisico è organizzato in due fasi: rilevamento delle collisioni e risoluzione. Il rilevamento delle collisioni individua le intersezioni tra le geometrie associate ai corpi rigidi, generando informazioni appropriate sulle collisioni, quali punti di collisione, normali e profondità di penetrazione. Successivamente, un risolutore aggiorna il movimento dei corpi rigidi sotto l'influenza delle collisioni rilevate e dei vincoli forniti dall'utente.
Il movimento è il risultato dell'interpretazione da parte del solutore delle leggi della fisica, come la conservazione dell'energia e della quantità di moto. Ma farlo con una precisione del 100% è proibitivamente costoso, e il trucco per simularlo in tempo reale consiste nell'effettuare approssimazioni per aumentare le prestazioni, purché il risultato sia fisicamente realistico. Finché le leggi fondamentali del moto vengono mantenute entro una tolleranza ragionevole, questo compromesso è del tutto accettabile per una simulazione in un videogioco.
Piccoli passi
L'idea principale del motore fisico è quella di discretizzare il movimento utilizzando il time-stepping. Le equazioni del moto dei corpi rigidi vincolati e non vincolati sono molto difficili da integrare direttamente e con precisione. La discretizzazione suddivide il movimento in piccoli incrementi di tempo, in cui le equazioni vengono semplificate e linearizzate, rendendo possibile risolverle in modo approssimativo. Ciò significa che durante ogni passo temporale il movimento delle parti rilevanti dei corpi rigidi coinvolti in un vincolo viene approssimato linearmente.
Sebbene un problema linearizzato sia più facile da risolvere, produce una deriva in una simulazione che contiene comportamenti non lineari, come il moto rotatorio. Più avanti vedremo metodi di mitigazione che aiutano a ridurre la deriva e rendono la simulazione più plausibile.
Risoluzione
Questa animazione mostra come un risolutore PGS modifichi le posizioni dei corpi ad ogni fase del processo di iterazione, con l'obiettivo di trovare le posizioni che rispettino i vincoli a snodo sferico preservando il centro di massa ad ogni fase (si tratta di un tipo di risolutore posizionale utilizzato dal dragger IK). Sebbene questo esempio abbia una soluzione analitica semplice, è una buona dimostrazione dell'idea alla base del PGS. Ad ogni passo, il risolutore fissa uno dei vincoli e lascia che l'altro venga violato. Dopo alcune iterazioni, i corpi sono molto vicini alle loro posizioni corrette. Una caratteristica di questo metodo è il modo in cui alcuni corpi rigidi sembrano vibrare attorno alla loro posizione finale, specialmente quando si accoppiano interazioni con corpi più pesanti. Se non si eseguono abbastanza iterazioni, la parte gialla potrebbe rimanere in uno stato visibilmente non valido in cui uno dei suoi due vincoli è drammaticamente violato. Questo è chiamato problema dell'alto rapporto di massa ed è stato la rovina dei motori fisici poiché causa instabilità ed esplosioni. Se si eseguono troppe iterazioni, il risolutore diventa troppo lento; se non se ne eseguono abbastanza, diventa instabile. Trovare un equilibrio tra i due aspetti è stato un processo lungo e doloroso.
Strategie di mitigazione
Un risolutore ha due principali fonti di imprecisioni: il time-stepping e la risoluzione iterativa (c'è anche la deriva in virgola mobile, ma è minore rispetto alle prime due). Queste imprecisioni introducono errori nella simulazione, facendola deviare dal percorso corretto. Alcune di queste deviazioni sono tollerabili, come velocità leggermente diverse o perdita di energia, ma altre non lo sono, come instabilità, grandi guadagni di energia o vincoli dislocati.
Pertanto, gran parte della complessità del risolutore deriva dall'implementazione di metodi volti a minimizzare l'impatto delle imprecisioni computazionali. La nostra implementazione finale utilizza alcune strategie di mitigazione tradizionali e alcune innovative:
- Avvio a caldo: si parte dalla soluzione di un passo temporale precedente per aumentare la velocità di convergenza del risolutore iterativo
- Post-stabilizzazione: riproiezione del sistema sul manifold dei vincoli per prevenire la deriva dei vincoli
- Regolarizzazione: aggiunta di conformità ai vincoli per garantire che esista una soluzione e che questa sia unica
- Precondizionamento: utilizzo di una soluzione esatta per un sottosistema lineare, migliorando la stabilità dei meccanismi complessi
Le strategie 1, 2 e 3 sono piuttosto tradizionali, ma la 3 è stata migliorata e perfezionata da noi. Inoltre, sebbene la 4 non sia del tutto sconosciuta, non ne abbiamo visto alcuna implementazione pratica. Utilizziamo un metodo di fattorizzazione originale per grandi matrici di vincoli sparse e un nuovo modo efficiente di combinarlo con il PGS. L'implementazione risultante è solo leggermente più lenta rispetto al PGS puro, ma garantisce che il sistema lineare derivante dai vincoli di uguaglianza venga risolto esattamente. Di conseguenza, i vincoli di uguaglianza subiscono solo la deriva derivante dalla discretizzazione temporale. I dettagli sui nostri metodi sono contenuti nella mia presentazione al GDC 2020. Attualmente, stiamo studiando metodi diretti applicati ai vincoli di disuguaglianza e alle collisioni.
Maggiori dettagli
Tradizionalmente esistono due modelli matematici per i meccanismi articolati: i metodi a coordinate ridotte, introdotti da Featherstone, che parametrizzano i gradi di libertà in ciascun giunto, e i metodi a coordinate complete che utilizzano una formulazione lagrangiana.
Noi utilizziamo la seconda formulazione poiché è meno restrittiva e richiede una matematica e un'implementazione molto più semplici.
Il motore Roblox utilizza metodi analitici per calcolare la risposta dinamica dei vincoli, al contrario dei metodi di penalità utilizzati in precedenza. I metodi analitici sono stati inizialmente introdotti da Baraff nel 1989, dove vengono utilizzati per trattare in modo coerente sia i vincoli di uguaglianza che quelli di disuguaglianza. Baraff ha osservato che il modello di contatto può essere formulato utilizzando la programmazione quadratica e ha fornito un metodo di soluzione euristico (che non è il metodo che utilizziamo nel nostro risolutore).
Invece di utilizzare una formulazione basata sulla forza, utilizziamo una formulazione basata sull'impulso nello spazio delle velocità, originariamente introdotta da Mirtich-Canny nel 1995 e ulteriormente migliorata da Stewart-Trinkle nel 1996, che unifica il trattamento dei diversi tipi di contatto e garantisce l'esistenza di una soluzione per i contatti con attrito. Ad ogni passo temporale, i vincoli e le collisioni vengono mantenuti applicando variazioni istantanee delle velocità dovute agli impulsi di vincolo. Un'eccellente spiegazione del perché la simulazione basata sugli impulsi sia superiore è contenuta nella presentazione GDC di Catto del 2014.
I contatti senza attrito sono modellati utilizzando un problema di complementarità lineare (LCP) come descritto in Baraff 1994. L'attrito viene aggiunto come proiezione non lineare sul cono di attrito, intercalata con le iterazioni del metodo di Gauss-Seidel proiettato.
La deriva numerica che introduce errori di posizione nei vincoli viene risolta utilizzando una tecnica di post-stabilizzazione che impiega pseudo-velocità introdotte da Cline-Pai 2003. Ciò comporta la risoluzione di un secondo LCP nello spazio delle posizioni, che proietta il sistema nuovamente sulla varietà dei vincoli.
Gli LCP vengono risolti utilizzando un PGS / Impulse Solver reso popolare da Catto 2005 (vedi anche Catto 2009). Questo metodo è iterativo e considera ogni singolo vincolo in sequenza, risolvendolo in modo indipendente. Dopo molte iterazioni, e in condizioni ideali, il sistema converge verso una soluzione globale.
Inoltre, i problemi legati all'elevato rapporto di massa nei vincoli di uguaglianza vengono risolti precondizionando il PGS utilizzando la decomposizione LDL sparsa della matrice dei vincoli di uguaglianza. Le sottomatrici dense della matrice dei vincoli vengono sparsificate utilizzando un metodo che chiamiamo Body Splitting. Questo è simile alla decomposizione LDL utilizzata in Baraff 1996, ma consente sistemi meccanici più generali e risolve il sistema nello spazio dei vincoli. Per ulteriori informazioni, potete consultare la mia presentazione al GDC 2020.
L'architettura del nostro risolutore segue l'idea di Guendelman-Bridson-Fedkiw, in cui gli incrementi di velocità e posizione sono separati dalla risoluzione dei vincoli. La nostra sequenza temporale è:
- Avanzamento delle velocità
- Risoluzione dei vincoli nello spazio delle velocità e nello spazio delle posizioni
- Avanzamento delle posizioni
Questo schema ha il vantaggio di integrare solo velocità valide e di limitare la latenza nell'applicazione della forza esterna, consentendo tuttavia una piccola quantità di violazione percepita dei vincoli dovuta alla deriva numerica.
Un ottimo riferimento per la simulazione di corpi rigidi è il libro Erleben 2005, recentemente reso disponibile gratuitamente. È possibile trovare lezioni online sull'animazione basata sulla fisica, un blog di Nilson Souto sulla creazione di un motore fisico, un'ottima presentazione GDC di Erin Catto sui moderni metodi di risoluzione e forum come il Bullet Physics Forum e GameDev, che sono ottimi luoghi dove porre domande.
In conclusione
Il campo della simulazione della fisica dei giochi presenta molti problemi interessanti che sono allo stesso tempo entusiasmanti e stimolanti. Ci sono opportunità per imparare una quantità sostanziale di matematica e fisica interessanti e per utilizzare moderne tecniche di ottimizzazione. È un'area dello sviluppo dei giochi che unisce strettamente matematica, fisica e ingegneria del software.
Anche se Roblox dispone di un buon motore fisico per i corpi rigidi, ci sono aree in cui può essere migliorato e ottimizzato. Inoltre, stiamo lavorando a nuovi progetti entusiasmanti come la fratturazione, la deformazione, i corpi morbidi, i tessuti, l'aerodinamica e la simulazione dell'acqua.
Né Roblox Corporation né questo blog promuovono o sostengono alcuna azienda o servizio. Inoltre, non vengono fornite garanzie o promesse riguardo all'accuratezza, all'affidabilità o alla completezza delle informazioni contenute in questo blog.
Questo post è stato originariamente pubblicato sul blog tecnico di Roblox.
