¿Cuál es un buen algoritmo para detectar colisiones entre esferas en movimiento?

27

Si (con el fin de detectar colisiones) los objetos 3D están representados en un juego por esferas, ¿cuál es un buen algoritmo para detectar una colisión entre esferas?

Si cada objeto tiene una posición a partir del último cuadro y una nueva posición (deseada), ¿cuál es un buen algoritmo que identificará las colisiones donde las esferas no se cruzan en el cuadro anterior, y pueden no cruzarse en el segundo cuadro, pero se cruzaron en algún punto intermedio?

collision-detection kevin42
fuente

Respuestas:

18

Básicamente estás buscando un rastro.

Esta página probablemente lo ayudará: http://www.realtimerendering.com/intersections.html

Esfera móvil / Esfera: (ubicación) Agregue el radio de la esfera móvil a la esfera estática y trate la esfera móvil como un rayo. Use este rayo para realizar la intersección rayo / esfera. Ver Gómez; Schroeder para el código (el artículo tiene error en la derivación, el código está bien); y RTR2, p. 622.

Tétrada
fuente
1
Eso no funciona si ambas esferas se mueven (ni siquiera si lo haces dos veces). Me parece que primero debería hacer una verificación de distancia entre las líneas que abarcan el movimiento a y el movimiento de expansión b, y si eso es menor que el radio a + radio b, es posible que se produzca una colisión. Después de eso, haría una comprobación para ver dónde está ese punto en el tiempo para la esfera a y dónde para la esfera b para ver si los tiempos están cerca. Si es así, comprobaría la velocidad contra la distancia en el tiempo para ese punto, si todavía es una posible colisión, haría un refinamiento gradual.
Kaj
15
En realidad lo hace, solo tienes que hacer el movimiento relativo. Entonces, si ambas esferas se mueven, simplemente resta la velocidad de una de las esferas de ambas para tener una esfera "en movimiento" y una esfera "estacionaria". Entonces puedes usar lo anterior.
Tetrad el
8

Use una prueba de barrido como se demuestra en este artículo de Gamasutra.

Firas Assaad
fuente
4

La parte superior de mi cabeza:

  1. Cree dos segmentos de línea desde el centro de cada círculo desde donde comenzó hasta donde se movió en ese paso de tiempo.
  2. Encuentre la distancia mínima entre esos dos segmentos de línea; como se explica aquí .
  3. Si esa distancia es menor o igual al radio del primer círculo más el segundo, entonces colisionaron; de lo contrario no lo hicieron.

Y eso es todo, hay que esperar que sea bastante rápido.

Robert Massaioli
fuente
1

Aquí hay otro buen artículo de Gamasatura .

Mateen Ulhaq
fuente
1
Me doy cuenta de que esto es 7 años después, pero esta respuesta es solo un enlace. Afortunadamente, el enlace todavía está vivo, pero si no fuera así, su respuesta ... no sería una respuesta.
Draco18s
0

Hablando como alguien que ha hecho esto: no vale la pena . A menos que el diseño de su juego lo necesite absolutamente, y casi seguro que no, gastará mucho más esfuerzo trabajando de lo que realmente espera. Y será más lento de lo que querías que fuera.

ZorbaTHut
fuente
Podría estar haciendo un juego de billar por todo lo que sabes.
Kaj
Si estaba haciendo un juego de billar, su "diseño de juego lo necesita absolutamente" .
deft_code
Tienes razón, no reinventes la rueda . Pero solo por ejercicio puede valer la pena.
user712092
44
No estoy de acuerdo con el desánimo directo como respuesta .
bobobobo
Estoy de acuerdo con @bobobobo, la pregunta no es si vale la pena o no, un futuro usuario que vea este hilo podría necesitar la respuesta sin importar el costo. Esto sería mejor como comentario.
TomTsagk
0

La detección de colisión para objetos en movimiento generalmente se denomina "Cálculo de volumen barrido", aquí hay algunos códigos / artículos sobre este tema.

http://www.gpu-voxels.org/demos/ (Demo)

Bibliotecas de código fuente:

https://github.com/fzi-forschungszentrum-informatik/gpu-voxels

https://libigl.github.io/tutorial/#swept-volume

https://github.com/gradientspace/geometry3Sharp

Artículos:

http://gamma.cs.unc.edu/SV/sm03.pdf

https://www.cs.columbia.edu/~allen/PAPERS/abrams.swept.pdf (Desafortunadamente no hay código fuente)

http://www.realtimerendering.com/intersections.html (Colección bastante pesada de enlaces)

TarmoPikaro
fuente
1
Las respuestas que contienen solo un enlace (o en este caso, varios) no contienen una respuesta real. Debes incluir la información relevante en tu publicación para que si esos enlaces se cortan, tu publicación aún sea comprensible.
Draco18s
La información detrás de los enlaces explica un poco mejor que yo en este momento. También hay videos de demostración detrás de los enlaces, que dan una idea de lo que sucede en tiempo real.
TarmoPikaro el
1
meta.stackexchange.com/a/8259/313685
Draco18s el