La mejor manera / eficiente de implementar una colisión 3D

16

Ya he programado un sistema de colisión basado en 2D para un juego anterior. Fue mi primer sistema de colisión y fue feo. Estaba buscando una colisión entre objetos marcando todos los objetos con todos los objetos. Ya he oído hablar de un sistema de cuadrícula con celdas donde un objeto solo verá la colisión con otros objetos de sus celdas actuales. ¿Es realmente una buena manera de verificar la colisión?

Me gustaría tener una buena técnica para recorrer todos mis artículos en un mundo 3D.

Jean-Philippe Leclerc
fuente

Respuestas:

11

Necesitará un buen algoritmo de partición espacial, comúnmente utilizado en 3D son octrees .

Después de eso, puede rodear modelos, etc., con esferas delimitadoras en las que encajan perfectamente porque es muy fácil calcular una colisión entre esferas delimitadoras. Después de saber que dos esferas delimitadores colisionan, puede hacer iterativamente que las esferas delimitadores sean más pequeñas y agregar esferas de delimitación para mantener el objeto cubierto en ellas, o usar otro algoritmo inteligente para calcular colisiones entre dos objetos complejos.

Ver esta imagen: múltiples esferas delimitadoras

Roy T.
fuente
12

En última instancia, creo que la respuesta a su pregunta dependerá de las necesidades de su aplicación en particular, ya que no existe una solución única para todos. Aunque hay una cantidad de recursos decentes en la web, se ahorrará mucho tiempo y frustración al elegir la detección de colisiones en tiempo real de Christer Ericson , que presenta con gran detalle una amplia variedad de técnicas y algoritmos, por ejemplo Código C ++.

Me ayudó a dar pequeños pasos antes de saltar a tratar de construir un gran sistema. Escribir una función para determinar si un punto está en un plano, luego si un punto está en un triángulo, si un rayo está en un triángulo, etc. Luego pasar a pruebas estáticas de varios sólidos convexos: AABB vs. Triángulo, etc. Las cosas que parecían impenetrables (perdón por el juego de palabras) al principio se volvieron menos desalentadoras. Aquí hay una lista de un buen número de pruebas, con código de ejemplo:

http://www.realtimerendering.com/intersections.html

Mientras tanto, como sé que no todo el mundo puede desembolsar 70-80 $ por un libro a voluntad, aquí hay algunos términos que puede considerar:

  • Particionamiento espacial, octrees, quadtrees, árboles BSP
  • BIH árboles
  • Volúmenes delimitadores y jerarquías del volumen delimitador
  • Detección de colisión discreta versus continua
  • Teorema del eje de separación
  • Algoritmo GJK
user_123abc
fuente