Algoritmos de detección de colisión de fase estrecha

10

Hay tres fases de detección de colisión.

  1. Broadphase : se repite entre todos los objetos que pueden interactuar, se permiten falsos positivos, si se acelera el ciclo.

  2. Narrowphase : determina si colisionan y, a veces, cómo, sin falsos positivos

  3. Resolución : resuelve la colisión.

La pregunta que hago es sobre la fase estrecha. Existen múltiples algoritmos, que difieren en complejidad y precisión.

  1. Intersección de Hitbox : este es un algoritmo a posteriori, que tiene la complejidad más baja, pero que tampoco es demasiado preciso,

  2. Intersección de color : intersección de Hitbox para cada píxel, a posteriori, perfecto de píxel, no precisa en cuanto al tiempo, mayor complejidad

  3. Teorema del eje de separación : se usa con más frecuencia, con precisión para los triángulos, sin embargo, a posteriori, ya que no puede encontrar el borde, cuando se tiene en cuenta el último fotograma, es más estable

  4. Radiodifusión lineal : el algoritmo A-priori, útil para la física de aspecto semi-realista, encuentra el punto de intersección, incluso más preciso que el SAT, pero con más complejidad

  5. Interpolación de spline : A-priori, incluso más precisa que los rayos lineales, incluso más coplexidad.

Probablemente hay muchos más que he olvidado. La pregunta es, ¿cuándo es mejor usar SAT, cuándo rayos, cuándo splines y si hay algo mejor?

Marian Ivanov
fuente

Respuestas:

6

Dos de los que te estás perdiendo y que inmediatamente me destacan son GJK y MPR.

GJK es un algoritmo para encontrar el punto más cercano de dos polígonos convexos. Con un poco de trabajo extra, puede usarlo para encontrar puntos de incidentes para objetos que se cruzan y, por lo tanto, calcular un múltiple de colisión. Esto se realiza mediante recorte de polígono, igual que si se usa SAT, pero GJK le ahorra algunos pasos (ya que ya tendrá los puntos más cercanos).

MPR (Minkowski Portal Refinement) es otro algoritmo, similar a GJK (ambos usan espacios de Minkowski). No puede encontrar el punto más cercano entre los objetos que no se cruzan como GJK, pero tiene muchas otras propiedades agradables para los juegos, y es una forma de usarlo para obtener un contacto múltiple.

MPR es uno de los más populares para juegos. Es muy eficiente, numéricamente estable y fácil de implementar.

Otras fases estrechas se utilizan más en juegos especializados. Los juegos de carreras usualmente usan rayos fundidos para modelar neumáticos reales y aún no es posible obtener un comportamiento realista (o incluso divertido) utilizando el modelado tradicional de forma y resolución de colisión. Los juegos de plataformas también suelen utilizar la colisión y la física altamente personalizadas, ya que la física preferida "similar a Mario" no está modelada con algoritmos de física tradicionales. También verá a menudo diferentes métodos de colisión y física para fluidos y demás, aunque sé menos sobre ellos.

Ver:

Sean Middleditch
fuente
3

Quería decir que es la prueba del eje de separación , no el teorema.

Usaría SAT en polígonos no móviles (2D), aunque puede extenderlo para hacer frente al movimiento lineal relativo.

http://elancev.name/oliver/2D%20polygon.htm#tut3

No use GJK en 2D, encontré que en realidad es más lento que simplemente el SAT de fuerza bruta.

Otra técnica que puede usar es la Diferencia de Minkowski, que reduce un objeto a un punto y 'hace crecer' al otro por la forma del primero. Luego prueba el objeto combinado contra el punto, que es mucho más fácil: esto le da una distancia de penetración normal. Creo que esta herramienta es conceptualmente muy útil para abordar nuevos problemas de detección de colisiones; más fácil de visualizar que SAT.

Para mover y rotar polígonos (y poliedros), puede utilizar el avance conservador para encontrar la hora exacta y el punto de contacto.

http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf

Puede leer más sobre estas técnicas en esta publicación de blog que escribí hace un tiempo:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

¡Espero que ayude!

Saludos, Paul.

salvaje
fuente
2
El teorema del eje de separación: existe un eje a lo largo del cual las proyecciones de dos objetos convexos son disjuntas si los objetos son disjuntos. Una prueba de eje de separación: supongo que pone en práctica el teorema mencionado anteriormente.
Eric
0

Esto realmente depende del tipo de juego que tengas. Cada método anterior tiene sus propias compensaciones.

Sin embargo, SAT es bastante estándar en mi experiencia para las bibliotecas de física genérica, ej. Box2D lo usa ampliamente (Angry Birds, y muchos otros juegos usan Box2D).

Las variaciones de intersección de color mezcladas con la intersección SAT o Hitbox se usan en juegos como Sonic, Megaman con buenos resultados.

Sin embargo, no sé mucho sobre los n. ° 4 y n. ° 5.

XiaoChuan Yu
fuente