three deteccion colisión colisiones collision-detection

collision detection - deteccion - ¿Alguien puede explicar la detección de colisiones por píxel?



deteccion de colisiones en java (7)

Cuando hables de pros y contras también debes considerar la respuesta de colisión. ¿Qué quieres hacer cuando se detecta una colisión? Si está detectando un objeto que golpea a otro objeto donde el resultado es uno o ambos de los objetos que se destruyen, entonces la detección de colisión por píxel es buena y precisa. Si desea que el objeto reaccione de alguna otra manera, es decir, deslizándose contra una pared, rebotando, etc. ... entonces puede que desee trabajar con algún tipo de rectángulo delimitador / círculo / óvalo que hará que la respuesta de colisión parezca más suave y más consistente, con menos posibilidades de quedarse atascado.

¿Puede alguien explicar los pros y los contras de esto y cualquier matemática involucrada con esto?


Es más preciso que los vértices (o cajas de mensajes, etc.). Supongo que estás hablando de 2d aquí (3d sería modelo de caja vs. vértice). Por píxel le permitiría tener sprites detallados cuyas pequeñas cosas (misiles, por ejemplo) colisionarían de forma más realista.

Es más matemático y más lento que el método convencional, que sería dibujar una caja (o alguna otra forma matemática fácil como un círculo) y decir ''este es el actor, cualquier cosa aquí es él''. Sin embargo, es más preciso.


Para 2D: no necesita ninguna matemática para este problema, solo necesita una rutina bitblit personalizada. Enviará los candidatos a colisión a una superficie oculta pintando sus máscaras de colisión en esta superficie y comprobando si los píxeles que desea dibujar son (¡píxel! = 0). Entonces tendrás una colisión. Por supuesto, debe verificar previamente delimitando rectángulos si se produce una colisión.

Para 3D: ¡necesitarás matemáticas (mucho)!

básicamente, verificarás cada superficie de tu actor contra cada superficie de tu enemigo. Esto se hará calculando una intersección de rayos planos. Aquí hay mucha optimización posible, pero depende de su representación 3d. Esto tampoco es una colisión por píxel, sino colisión por vértice


Los profesionales ya se han mencionado: es perfecto y justo, no hay falsos positivos ni falsos negativos. La principal desventaja es que es costoso de calcular, pero si primero hace un simple cuadro delimitador, esto no debería ser un gran problema. En la era de OpenGL y DirectX, hay un problema más: los datos de sprites suelen ser texturas, lo que significa que están en la VRAM y no puede verificar fácilmente los valores de los píxeles. En OpenGL Puede usar la función glReadPixels para volver a la parte intersecada de dos sprites en la RAM y verificar la colisión, o puede usar la consulta de oclusión . El enfoque de consulta de oclusión debería tener un mejor rendimiento, ya que no está moviendo datos de la GPU, pero las consultas de oclusión no son compatibles en todas partes (es decir, no son compatibles con OpenGL ES, alguien corrija si estoy equivocado).


tomando OpenGL y el caso de textura: puede precalcular una matriz de bits para la imagen y probar si dos píxeles se superponen.


La detección de colisiones por píxel es una reliquia del pasado, cuando los gráficos eran simples y el hardware 2D incluía la comprobación de colisiones gratuitas entre los sprites y los fondos. Si bien los gráficos 2d de hoy son más complejos, rara vez se utilizan controles de colisión por píxel, especialmente porque la forma visible del objeto y la forma de colisión suelen ser diferentes. Círculos o cajas son suficientes para la mayoría de los casos. Además, dado que el hardware de gráficos basado en OpenGL ya no puede realizar la prueba de colisión, debe escribir código de renderizado adicional, utilizando la CPU para el único propósito de verificar colisiones, mientras mantiene datos de mapa de bits adicionales en la memoria del sistema, ya que no se puede acceder directamente a la memoria gráfica.


Comenzaré respondiendo los pros y los contras de la detección de colisiones por píxel, y luego consideraré los aspectos matemáticos más adelante.

La detección de colisiones por píxel, también conocida como detección de colisiones perfecta para píxeles, y tal vez una detección de colisiones basada en imágenes más precisa, es encontrar colisiones entre objetos de colisión que se representan como imágenes. Este método espacial se contrapone a los métodos más geométricos, donde los polígonos y otras formas geométricas se utilizan para representar los objetos de colisión.

Para 2D, generalmente hay 3 opciones diferentes:

  • Basado en imágenes
  • Formas geométricas simples (cajas delimitadoras alineadas a los ejes, círculos)
  • Formas geométricas complejas (polígonos convexos, polígonos de convalecencia, elipses, etc.)

La detección de colisiones basada en imágenes es precisa y fácil de usar y comprender. Con respecto a los juegos que usan imágenes para dibujar, el uso de la detección de colisiones basada en imágenes significa que cada vez que los sprites en la pantalla se superponen, también se superponen en el sistema de detección de colisiones. También son útiles para juegos en los que se necesitan objetos de colisión deformables, como en el caso de juegos destructibles vistos en el terreno, como Worms 2D, ya que generalmente hay poco precomputado. Su principal inconveniente es que son muy ineficientes en comparación con los otros métodos, especialmente al girar y escalar los objetos de colisión.

Las formas geométricas simples son simples de trabajar y muy eficientes. Si no se necesita alta precisión, o los objetos de colisión encajan bien con formas geométricas simples (por ejemplo, si los objetos de colisión son bolas, los círculos se ajustan perfectamente, a veces incluso mejor que las imágenes). Su principal inconveniente es su precisión. Para obtener una alta precisión donde las formas básicas no se ajustan, debe combinar las formas simples en formas más complejas o debe usar formas más generales y complejas. En cualquier caso, terminas en el tercer método.

Las formas geométricas complejas pueden ser algo precisas y relativamente eficientes o ineficientes, dependiendo de la complejidad de las formas usadas para representar un objeto de colisión. Un inconveniente importante es la facilidad de uso. Cuando los objetos de colisión no se ajustan a las formas geométricas disponibles, la precisión tendrá que sufrir, o varias formas posiblemente diferentes tendrán que usarse para representarlo, lo que lleva tiempo. Además, algunas de las formas son complejas y no fáciles de crear, a menos que pueda generarlas a partir de una imagen automáticamente. Una ventaja importante es que la rotación y la escala generalmente son eficientes y fáciles, especialmente en comparación con la detección de colisiones basada en imágenes.

La detección de colisiones basada en imágenes generalmente se considera una mala solución, porque con frecuencia es ineficiente, especialmente cuando se usa la rotación y la escala. Sin embargo, dado que es tan flexible, preciso y fácil de usar, decidí implementar una biblioteca que busca resolver el problema de la eficiencia. El resultado es PoxelColl , que utiliza cascos convexos precalculados automáticamente para acelerar la detección de colisiones basada en imágenes. Esto brinda facilidad de uso, flexibilidad, precisión y eficiencia, y admite rotación y escalado. Los principales inconvenientes son que no es eficiente en todos los casos en comparación con las soluciones geométricas puras, y usa precálculo, lo que significa que no es muy ineficiente para objetos de colisión deformables.

Para 3D, las opciones y ventajas son algo similares:

  • Basada en el volumen
  • Formas geométricas simples (cajas delimitadoras alineadas a los ejes, círculos)
  • Formas geométricas complejas (polígonos convexos, polígonos de convalecencia, elipses, etc.)

Cabe señalar que la respuesta de Peter Parker es incorrecta para 3D; Los píxeles (elementos de imagen) en 2D corresponden a los vóxeles (elementos de volumen) en 3D.

Algunas diferencias importantes son que el método espacial es mucho más raro para 3D que para 2D. Una posible razón es que, debido a que el 3D agrega una dimensión extra, la solución espacial se vuelve aún menos eficiente, mientras que las soluciones geométricas simples siguen siendo eficientes. Y en los juegos, la detección de colisiones generalmente es una operación en línea, que requiere cierto nivel de eficiencia, lo que hace que la eficiencia sea importante. Por lo tanto, los volúmenes se usan con mayor frecuencia en aplicaciones que no son de juegos, donde las colisiones no necesitan determinarse en línea.

Para ejemplos de detección de colisiones con detección de colisiones por volumen, ver por ejemplo detección de colisiones volumétricas para objetos deformables , donde el uso de volúmenes en lugar de formas geométricas significa que pueden manejar objetos de colisión deformables con superficies cerradas de forma arbitraria.

En cuanto a la segunda pregunta, la matemática involucrada en las colisiones basadas en imágenes puede variar de simple a compleja. El caso simple es básicamente el uso de recuadros delimitadores alineados con los ejes para las imágenes, encontrando su intersección, y luego solo verifica las imágenes en la intersección. Las soluciones más complejas incluyen la biblioteca que mencioné antes, donde se requiere una intersección poligonal convexa. Y para el caso 3D, las soluciones van de simples a muy complejas.