Simulazione di n corpi in collisione 2D (rilevamento rapido di collisioni per un gran numero di sfere)

Question

Voglio scrivere un programma per simulare un movimento di numero elevato (N = 1000 - 10^5 e più) di corpi (cerchi) su 2D aereo. Tutti i corpi hanno le stesse dimensioni e l'unica interazione tra loro è la collisione elastica.

Voglio ottenere qualcosa come ma in scala maggiore, con più palle e riempimento più denso dell'aereo (non un modello di gas come qui, ma smth come modello di acqua bollente).

Quindi voglio un metodo veloce di rilevamento che il numero di palla i ha qualsiasi altra palla sul suo percorso entro 2 * raggio + V * delta_t distanza. Non voglio fare una ricerca completa di collisione con palle N per ciascuna sfera i. (Questa ricerca sarà N^2.)

PS Ci scusiamo per GIF animate in loop. Basta premere Esc per fermarlo. (Non funzionerà in Chrome).

Answer 1

Questo primo passo nella simulazione fisica è il rilevamento di collisione in fase ampia. Esistono diversi approcci descritti qui http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html ma i due elementi di base sono il partizionamento spaziale, che divide gli oggetti in una griglia, o sort-and-sweep, che consiste nell'ordinare tutti gli oggetti lungo due assi.

Answer 2

Ovviamente si desidera evitare (N1 -) * N controlla le collisioni con ciascuna iterazione. Un approccio semplice sarebbe quello di dividere l'area in una griglia 2D di celle e quindi fare un singolo passaggio per capire quali celle attraversano ciascuna delle sfere nell'iterazione corrente. Ogni palla quindi controlla solo le collisioni con le palle che passano attraverso le celle che attraversa.

Sono sicuro che ci sono approcci più sofisticati, ma questo potrebbe essere un buon inizio.

Answer 3

La larghezza/lunghezza della griglia deve essere maggiore o uguale al raggio di essi e la ricerca deve essere sui primi vicini (8 + centro = 9 griglie). Con una dimensione minima della griglia, è dieci a quindici volte il numero di calcoli di particelle.