Determinar si dos objetos que se mueven rápidamente se deben enviar para una verificación de colisión

8

Tengo un motor de física 2D básico en funcionamiento. Es más o menos un motor de partículas, solo usa formas básicas como AABB y círculos, por lo que no es posible la rotación. Tengo un CCD implementado que puede proporcionar un TOI preciso para dos objetos que se mueven rápidamente y todo funciona sin problemas.

Mi problema ahora es que no puedo determinar cómo determinar si dos objetos que se mueven rápidamente deberían ser comparados entre sí en primer lugar. Estoy usando un árbol cuádruple para la partición espacial y para cada objeto que se mueve rápidamente, lo compruebo contra los objetos en cada celda que pasa. Esto funciona bien para determinar la colisión con la geometría estática, pero significa que cualquier otro objeto de movimiento rápido que pueda chocar con él, pero que no esté en ninguna de las celdas que se verifican, nunca se considera.

La única solución a esto que se me ocurre es tener las celdas lo suficientemente grandes y cruzar los dedos para que sea suficiente, o implementar algún tipo de algoritmo de fuerza bruta. ¿Hay una manera adecuada de lidiar con esto? Quizás alguien resolvió este problema de manera eficiente. ¿O tal vez hay una mejor manera de particionar el espacio que explica esto?

Aquí hay un diagrama:

ingrese la descripción de la imagen aquí

Las "áreas de efecto" del objeto A y B se cruzan, deben verificarse entre sí. Pero con la forma en que actualmente estoy comprobando las colisiones no se tiene en cuenta esto. Nuevamente, puedo pensar en algunas soluciones para esto, como verificar si los caminos de los objetos se cruzan una vez que su velocidad es mayor que x, o algo así, pero eso se siente como un truco y es un desastre tratar de implementarlo.

collision-detection physics dreta
fuente
¿Podría dar un escenario de ejemplo en el que su método falla?
Anko
1
Creo que sería así: el objeto A y B están en esta configuración: [A] [] [B]. A va hacia la derecha y B hacia la izquierda. Ellos van rápido La verificación de colisión es así: ¿la siguiente celda está vacía para A? Sí, bcs no hay nada en la celda del medio. ¿La siguiente celda está vacía para B? Si. Entonces no hay colisión. Pero la física real mostraría que es probable que A y B choquen (especialmente en este juego de una dimensión que describo;)
Cystack
@Cystack Tengo CCD implementado. La situación que describiste no es un problema. Los dos objetos van directamente el uno al otro, la implementación que describí va a recoger eso y resolverlo.
dreta
La física de la situación es clara. Digamos que puede identificar un objeto como 'rápido' antes de tiempo. Luego, cuando realiza una verificación de colisión, debe verificar no solo la celda en la que se encuentra actualmente el objeto, sino todas las celdas por las que pasó en el último paso de tiempo. Por lo tanto, cada objeto de movimiento rápido en realidad tiene múltiples ubicaciones, como toda la franja verde que dibujó en la imagen de arriba.
theJollySin
@theJollySin Ya describí la solución que está dando, es un truco, un caso especial, estoy buscando una solución general si hay una.
dreta

Respuestas:

5

El problema del que está hablando a menudo se llama 'detección de colisión de fase amplia' y su solución es un 'volumen barrido', no realmente un truco, solo cómo se hace (simplemente tome el AABB del objeto, incluidos el inicio y el final del movimiento y úselo para colisión, aunque las cosas se ponen un poco difíciles con las rotaciones).

Luego, el algoritmo de detección de colisión de fase ancha que hace que esto sea rápido se llama 'Barrer y podar'.

Jeff Gates
fuente
Descarté SAP antes de que surgiera este problema. Estoy haciendo esto en JavaScript, lo que hace que la sobrecarga de las listas sea notable, también las matrices pueden volverse poco confiables en lo que respecta al rendimiento. Supongo que tendré que reconsiderar las cosas. Gracias, el algoritmo realmente resuelve el problema.
dreta