Colisiones en una aplicación del mundo real

Question

Aquí está mi problema. Estoy creando un juego y me pregunto cómo hacer las colisiones. Tengo varios casos para analizar y para encontrar la mejor solución para.

Lo diré de antemano, no estoy usando ninguna biblioteca de física de un tercero, pero lo haré en casa. (Ya que este es un proyecto educativo, no tengo horarios y quiero aprender)

tengo 2 tipos de malla para la que tengo que hacer las colisiones para:

1) Las mallas estáticas (que desplazarse por la pantalla, pero no tiene ningún tipo de animación)

2) Skinned/Boned mallas (animado)

en realidad tengo esta solución (bastante hacky: |)

primero de todo, tienen una prueba contra un volumen delimitador que encierra la m completa esh (cápsula en mi caso), después:

1) Para las mallas estáticas, las divido manualmente en bloques (en el modelador) y para cada uno de estos bloques utilizo una prueba esfera/AABB. (funciona bien, pero es un poco desordenado cortar cada malla: P) (probé un sistema automático para dividir la malla entre planos, pero da malos resultados :()

2) Para la malla animada ATM i ' m dividiendo la malla en tiempo de ejecución en x bloques (donde x es el número de huesos). Cada bloque contiene el vértice para el cual ese hueso es el principal influencer. (A veces funciona, a veces da muy malos resultados: |.)

Tenga en cuenta que la brecha de la malla se realiza en tiempo de carga y no cada vez (de lo contrario se corre como una presentación de diapositivas: D)

Y esta es la pregunta:

¿Cuál es la idea más sensata para usar en esos 2 casos? ¿Algún material para mí para estudiar estos métodos? (con algunos códigos fuente y explicaciones sería aún mejor (el lenguaje no es importante, cuando entiendo el algoritmo, la implementación es fácil)) ¿Puede argumentar por qué esa solución es mejor que otras? He oído hablar mucho de kd-tree, octree, etc. Mientras entiendo su estructura, echo de menos su utilidad en un escenario de detección de colisiones.

¡Muchas gracias por las respuestas!

EDIT: tratando de encontrar un ejemplo de K-Dop con alguna explicación en la red. Todavía no he encontrado nada. :(¿Alguna pista? Me interesa saber CÓMO el K-Dop puede ser probado eficientemente con otro tipo de volúmenes delimitadores, etc. ... pero la documentación en la red parece muy deficiente. :(

Answer 1

Los enfoques más comunes utilizados en muchos juegos AAA actuales es la colisión simplificada "k-DOP" para StaticMeshes, y una representación simplificada del cuerpo físico para SkeletalMeshes.

Si busca en google "colisión kDOP" o "politopos de orientación discretos", debería encontrar suficientes referencias. Este es básicamente un volumen delimitador definido de varios planos que se mueven desde el exterior hacia la malla, hasta que se produce una colisión triangular. La "k" en kDOP define la cantidad de estos planos que se usan, y dependiendo de tu geometría y tu "k" obtendrás muy buenas aproximaciones con esto.

Para huesos esqueléticos la técnica más recomendable es definir la geometría simple que se une a huesos específicos. Esta geometría podría ser una caja o una esfera. Este modelo de colisión puede utilizarse para la detección de colisiones bastante precisa de mallas animadas.

Si necesita una colisión por triángulo, el "Teorema de eje separado" es el término de búsqueda de Google de su elección. Esto es útil para casos específicos, pero el 75% de las necesidades de detección de colisiones deben cubrirse con los métodos mencionados anteriormente.

Tenga en cuenta que probablemente necesite un mayor nivel de rechazo temprano de colisiones que un volumen delimitador. Tan pronto como tenga muchos objetos en el mundo, necesitará usar una "partición espacial" para rechazar grupos de objetos de pruebas posteriores tan pronto como sea posible.

Answer 2

Antes de hacer complejos detección de colisiones que debe realizar la detección básica.

el uso de esferas o rectángulos como volúmenes de selección es la mejor opción. Entonces, si este detecta una colisión, pasar a sus métodos más complejos.

lo que quiero llegar es sencillo a menudo es mejor y más rápido. Envolver volúmenes encuadernados y dividir mallas es costoso, por no mencionar complejo. Sin embargo, parece estar en el camino correcto.

Al igual que con la programación de juegos, existen múltiples formas de detección de colisiones. Mi consejo sería comenzar simple.Tome un cubo y perfeccione sus rutinas sobre eso, luego, en teoría, debería poder usar cualquier otro modelo. En cuanto a los ejemplos, verificaría gamedev.net ya que tienen algunos buenos artículos. Gran parte de mi detección de colisión casera es una combinación de muchos métodos, por lo que realmente no puedo recomendar el recurso definitivo.

Answer 3

La pregunta que responde se reduce a ¿con qué precisión necesita?

Claramente, los cuadros delimitadores de esfera son los más triviales. En el otro lado de la escala, tiene una detección de colisión de malla de malla triangular completa, que tiene que suceder cada vez que un objeto se mueve.

Motor de desarrollo de juegos basado en el arte de la aproximación (aceché en los foros de matemáticas y física de GameDev.net hace años).

Mi opinión es que necesitarás algún tipo de elipsoide delimitador asociado a cada objeto. Un objeto puede ser un objeto multimesh general, una malla o una malla de submalla. Esto debería proporcionar una cantidad de aproximación "decente".

Answer 4

Recoger Christer Ericson's libro, Real-Time Collision Detection. Él discute estos mismos problemas con gran detalle.

Al leer artículos, recuerde que en una aplicación de juego del mundo real trabajará bajo los límites de la memoria y el tiempo: ¡obtiene 16.6ms por cuadro y eso es todo! Por lo tanto, tenga cuidado con cualquier artículo o documento que no discuta seriamente la memoria y la huella de CPU de su algoritmo.