Detección de colisión con curvas.

12

Estoy trabajando en un juego en 2D en el que me gustaría hacer una detección de colisión entre un círculo en movimiento y algún tipo de curvas estáticas (quizás curvas de Bezier).

Actualmente, mi juego presenta solo líneas rectas como la geometría estática y estoy haciendo la detección de colisión calculando la distancia del círculo a las líneas y proyectando el círculo fuera de la línea en caso de que la distancia sea menor que el radio de los círculos.

¿Cómo puedo hacer este tipo de detección de colisión de una manera relativamente directa? Sé, por ejemplo, que Box2D presenta detección de colisión con curvas de Bezier. No necesito un mecanismo de detección de colisión con todas las funciones, solo algo que pueda hacer lo que he descrito.


ACTUALIZACIÓN: ¡Muchas gracias por las excelentes respuestas! Tendré que leer sobre las curvas de Bezier para comprender completamente el método que ha descrito. Entonces me pondré en contacto contigo.

paldepind
fuente

Respuestas:

6

29/09/2012 - 23:20

Creé un repositorio git aquí: https://github.com/ArthurWulfWhite/Bezier-Distance/

Puede descargar los archivos de origen como un archivo zip desde allí. También incluye una demostración que puede compilar con FlashDevelop. Para usar la demostración, abra el proyecto en Flash Develop y haga clic en 'Probar proyecto'. Mientras ejecuta la demostración, haga clic en el LMB para aleatorizar una nueva curva de Bezier y un nuevo círculo.

¡Buena suerte!

El enlace zip es difícil de ver, solo use Ctrl + F y escriba zip. Esta fuente representa un par de semanas de investigación y programación, espero que lo disfruten.


Si planea dividir el bezier de forma recursiva en segmentos y buscar colisiones con ellos, sugiero hacer una matriz de 100.100 (cuadrícula) y colocar cada segmento en los cuatro cuadrados más cercanos, por lo que solo tiene que verificar las colisiones con 4 / 10,000 de los segmenta cada cuadro.

Creo que te beneficiarás de box2d como programador y como creador de juegos, ya que hay muchos pequeños obstáculos ocultos para hacer un motor de física 'simple' que haga que el movimiento parezca un poco irregular y menos fluido de lo que podría ser.

Antigua respuesta: El camino puro.

En realidad, puede ver si un círculo colisiona con una curva de Bezier, verificando la distancia entre la distancia entre el centro del círculo y el punto más cercano en la curva.

La ecuación para la distancia (en general)

explicado:

Ecuación de Bezier:

q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Esto se puede resumir en (con algo de álgebra): omitiré (x, y) para facilitar la lectura (siguen siendo puntos, no un número)

q(t) = (start -2 * cont + end) t^2 + (-2 * start + 2 * control) + start

La distancia desde el punto (x, y) es:

sqrt ((q(t).x - point.x)^2 + (q(t).y - point.y)^2)

Para encontrar el punto más cercano en el bezier a la pelota, necesitas derivar y encontrar todos los puntos donde la derivada es igual a cero (las raíces). Es un polinomio de tercer grado, por lo que podría usar una fórmula cerrada, pero podría no ser confiable ya que la precisión de las fracciones representadas por coma flotante de la computadora puede no ser suficiente. Es mucho mejor usar Newton o algo así.

La derivada que necesita para encontrar las raíces es:

Suponiendo: a = inicio b = control c = final d = punto central del círculo

Derivado usando wolfram alpha

La parte difícil es multiplicar estos puntos, tienes que usar el producto punto.

Si lo desea, tengo el código para esto y puedo compartirlo aquí en forma de una función que simplemente devuelve un valor booleano si hay una colisión o no y un ángulo de colisión. Algunos problemas podrían aparecer en la implementación ingenua de un motor de colisión como este, por ejemplo, una bola en movimiento rápido podría quedar atrapada entre dos curvas.

Recomiendo evitarlo por ahora, solo sume los coeficientes para el eje x y para el eje y y sumelos.

Utilice cualquier método confiable que pueda elegir, como Newton, para encontrar las raíces, verifique la distancia desde los puntos raíz en el bezier, 0 <= t <= 1 al centro del círculo y verifique la distancia para los dos extremos del bezier (comience y final) al centro del círculo, el que esté más cerca, le dirá si hay una colisión.

Si el radio es más pequeño que la distancia mínima, hay una colisión.

El ángulo es aproximadamente el que está entre el centro del círculo y el punto más cercano en el bezier.

Dicho esto, si realmente deseas hacer un juego con física de colisión, te sugiero que solo repitas el juego.

    q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Divida cada pieza en el medio de forma recursiva hasta que sea lo suficientemente pequeña, digamos 10 píxeles o menos, luego construya el bezier más o menos a partir de cajas y use Box2d para la física porque es posible que escribir todo este código de detección de colisión resulte ser excelente sumidero de tiempo que no mejora mucho la jugabilidad. Usar Box2d ha demostrado su valía en innumerables proyectos en el pasado.

AturSams
fuente
El método que describe para calcular el punto más corto de la curva es exactamente el que estoy usando actualmente con líneas en lugar de curvas. Pero hacer lo mismo para las curvas con el método que explicas suena demasiado complicado. Lo cual, según tengo entendido, es también lo que piensas. Y con respecto a Box2D. Estoy seguro de que es un gran trabajo. Pero la física en mi juego es sinceramente muy simple y, por lo tanto, he decidido que un motor de física completo es excesivo.
paldepind
¿Cuántos objetos hay en tu juego? ¿Cuántos pueden chocar entre sí? A veces, usar un motor de Física puede generar grandes beneficios, como calcular con precisión el tiempo de colisión. (porque los marcos son discretos y las colisiones son reales (no suceden precisamente cuando se
procesa
A menudo, los desafíos inesperados al implementar algo nuevo y la belleza de usar una API de física 2D es que es como usar cualquier lenguaje de programación, no requiere un esfuerzo especial de su parte que no sea invertir un par de horas para aprenderlo y Los resultados son muy satisfactorios.
AturSams
Agregué algunos detalles más ahora mismo, buena suerte. :)
AturSams
Estoy creando un juego simple como Elasto Mania. Solo tres círculos móviles y geometría estática. Todo el motor está terminado y funciona muy bien. Lo único que queda es permitir curvas que estoy a punto de resolver atm gracias a la ayuda en esta respuesta :) Siéntase libre de publicar el código que mencionó. ¿Qué tan apropiado crees que sería usar en la vida real? ¿Mejor que convertir el bezier en pequeñas líneas?
paldepind
7

Para hacer esto, yo haría:

  • Divide la curva bezier en varios segmentos de línea y guárdalos.

  • Coloque todos estos segmentos en un cuadro delimitador alineado con el eje para toda la curva.

Detección de colisiones :

1) verifique si la esfera está dentro del cuadro delimitador principal. si no, no hay colisión.

2) de lo contrario, verifique si alguno de los segmentos individuales calculados arriba choca con la esfera. Vea el artículo de intersección línea-esfera de Wikipedia .

EDITAR: si necesita alta precisión y desea un buen rendimiento, también puede crear un cuadro delimitador principal para toda la curva, luego subdividir la curva en dos segmentos (por ejemplo: [0.0 - 0.5]y [0.5 - 1.0]). Cree un cuadro de bouding para cada uno de ellos, luego subdivida nuevamente cada uno de estos segmentos en dos segmentos (dando así [0 - 0.25], [0.25 - 0.5]y [0.5 - 0.75], [0.75 - 1.0]). Continúa así hasta que alcances la precisión suficiente. al final tendrá un binary treecuadro de límite con el cuadro de límite de la curva principal en los segmentos de raíz y línea en las hojas. buscar en el árbol le dará en O(log n)lugar de O(n)(donde n= número de segmentos de línea para la curva)

tigrou
fuente
Esta solución tiene sentido para mí y es definitivamente la más fácil de entender y podría resolverla. Pero tengo curiosidad si existe una opción más "pura".
paldepind
5

La intersección entre una línea y una curva de Bézier se logra matemáticamente subdividiendo la curva. Esto significa confiar en la propiedad del casco convexo de la curva y dividirla en arcos más pequeños con diferentes polígonos de control de una manera similar a dividir e imperar.

Este artículo lo cubre hasta cierto punto: http://students.cs.byu.edu/~tom/557/text/cic.pdf .

Lo bueno es que el algoritmo funciona con cualquier línea, solo tiene que aplicar una transformación rígida a la curva para que pueda considerar su línea objetivo como paralela al eje Ox.

De manera similar, puede verificar el círculo y el polígono de cada uno de estos arcos de Bezier cuando subdivide un arco de Bezier en dos subarcos. El círculo debe intersecar el polígono de control de un arco para que una prueba de curva a círculo tenga sentido.

Gabriel Conrad
fuente
Aún no he leído el artículo. Pero, ¿cómo llego desde la intersección entre una línea y una curva de Bézier hasta la intersección entre un círculo y un Bézier? Verificar la colisión contra un círculo y un polígono me parece demasiado complicado.
paldepind