Simulación en 2D de choques 2D (Detección rápida de colisión para gran cantidad de bolas)

Question

Quiero escribir un programa para simular un movimiento de alto número (N = 1000 - 10^5 y más) de cuerpos (círculos) en 2D avión. Todos los cuerpos tienen el mismo tamaño y la única interacción entre ellos es la colisión elástica.

Quiero obtener algo como pero en una escala más grande, con más bolas y un relleno más denso del avión (no es un modelo de gas como aquí, pero es muy parecido al modelo de agua hirviendo).

Así que quiero un método rápido de detección que el número de bola i tenga cualquier otra bola en su trayectoria dentro de un radio de 2 * + V * delta_t de distancia. No quiero hacer una búsqueda completa de colisión con N bolas para cada bola i. (Esta búsqueda será N^2).

PD Lo siento por el GIF animado por bucle. Solo presiona Esc para detenerlo. (No funcionará en Chrome).

Answer 1

Este primer paso en la simulación física es la detección de colisiones en fase amplia. Hay varios enfoques descritos aquí http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html pero los dos elementos básicos son la partición espacial, que divide los objetos en una cuadrícula, o clasificación y barrido, que consiste en ordenar todos los objetos a lo largo de dos ejes.

Answer 2

Obviamente, desea evitar (N1 -) * N comprueba las colisiones con cada iteración. Un enfoque simple sería dividir el área en una cuadrícula 2D de celdas y luego hacer un solo pase para determinar qué celdas atraviesa cada bola en la iteración actual. Entonces, cada bola solo verifica las colisiones con las bolas que pasan a través de las celdas por las que pasa.

Estoy seguro de que hay enfoques más sofisticados, pero este podría ser un buen comienzo.

Answer 3

El ancho/largo de la malla debe ser mayor o igual que el radio de ellos y la búsqueda debe realizarse en los primeros vecinos (8 + centro = 9 cuadrículas). Con un tamaño de cuadrícula mínimo, es de diez a quince veces el número de cálculos de partículas.