- El algoritmo GJK es una forma de verificar si dos figuras se superponen.
- Para comprobar si la figura A y la figura B se superponen, basta con verificar si хотя бы uno de los puntos de ambas figuras coincide.
Diferencia de Minkowski
- Se crea un nuevo conjunto restando todos los puntos de las dos figuras.
- Si este nuevo conjunto contiene el origen, significa que las dos figuras se superponen.
- A esto se le llama diferencia de Minkowski.
Idea básica del algoritmo
- Se verifica si la diferencia de Minkowski de A y B contiene el origen.
- Si la diferencia contiene el origen, las figuras se superponen.
Pasos del algoritmo
- Inicialización: se establece un vector de dirección arbitrario
dy se encuentra el primer puntop. - Búsqueda de punto: se calcula el producto punto de
dyp; si es positivo, se continúa, y si es negativo, se termina. - Agregar nuevo punto: desde
p, se busca un nuevo punto en dirección al origen. - Simplificación: se agrega un nuevo punto tomando como base los dos primeros puntos para simplificar.
- Verificación de inclusión del origen: se comprueba si la figura simplificada contiene el origen.
- Repetición: se repite hasta que contenga el origen o hasta encontrar evidencia de que no lo contiene.
Opinión de GN⁺
- Punto interesante: el algoritmo GJK es un buen ejemplo de cómo resolver un problema complejo mediante una transformación matemática simple.
- Por qué ayuda: se usa de forma muy útil en gráficos en tiempo real, como en la detección de colisiones.
- Mirada crítica: la implementación del algoritmo puede ser compleja y requiere una comprensión precisa.
- Tecnologías relacionadas: entre otros algoritmos de detección de colisiones está SAT (Separating Axis Theorem).
- Aspectos a considerar: al usar el algoritmo GJK, hay que considerar la complejidad de las figuras y el costo computacional.
1 comentarios
Comentarios de Hacker News
En los años 90 sufrí casi un año por culpa de GJK
Es útil para detección de colisiones 3D y también se puede usar como algoritmo de punto más cercano. La idea básica es fácil de entender. Si tienes dos sólidos convexos, tomas un punto arbitrario de cada uno, calculas la distancia entre esos dos puntos, luego intentas mejorar esa distancia moviéndote por cada arista desde la posición actual y eligiendo el nuevo punto más cercano, repitiendo el proceso
Pero este enfoque deja de funcionar cuando el punto más cercano ya no es un vértice, y ahí hace falta el concepto de símplex. Las combinaciones del punto más cercano se dividen en vértice-vértice, vértice-arista, vértice-cara, arista-arista, arista-cara (sin solución única), cara-cara (sin solución única), y en la práctica manejar el símplex es casi lo mismo que analizar estos casos
En la práctica surgen muchos problemas. En los motores físicos es común que los objetos se estabilicen en contacto cara-cara, y un modelo de colisión de punto único puede producir vibraciones o movimientos incorrectos. Además, cuando la posición converge a un contacto cara-cara, GJK termina manejando diferencias pequeñas entre valores grandes y puede perder por completo los dígitos significativos de punto flotante. La condición de terminación también puede provocar bucles infinitos
En teoría es elegante, pero en la práctica es un problema difícil de análisis numérico. Aun así, probablemente sea el enfoque más rápido para este problema. En el caso general es O(log N), y si usas la última solución como punto de partida cuando la situación anterior era la más cercana, puede acercarse a O(1)
El difunto profesor Steven Cameron de Oxford trabajó mucho para hacer que GJK funcionara correctamente, y usó GJK en "Falling Bodies", el primer sistema comercial de ragdolls 3D de finales de los 90
Obtener eso es todavía peor numéricamente. Empiezas desde el símplex que produjo GJK y lo expandes hacia afuera, y en el proceso hay que triangular. Implementarlo con buen rendimiento es casi una pesadilla total
Me pregunto si la patente ya expiró y si hay intención de publicar el código. Tiene valor histórico y podría ser un material interesante, como leer el código fuente de Doom
Como no encontraba un texto que explicara de forma intuitiva el algoritmo de detección de colisiones GJK, dediqué la tarde a organizarlo yo mismo
Si hay alguna forma de hacerlo más claro o más eficiente, me gustaría saberlo. Claro, tengan en cuenta que es un texto donde un estudiante de penúltimo año de preparatoria explica contenido matemático
Ya está muy bien, pero para dejarlo aún más redondo quizá podrías añadir algunas cosas. Una explicación breve de la complejidad temporal en el peor caso, una sección aparte sobre la condición de terminación, y algo de seudocódigo intercalado en la explicación
La forma de explicarlo desde una perspectiva matemática, como ahora, funciona bien y vale la pena conservarla. Pero sería aún mejor si, después de cada paso, añadieras un breve seudocódigo que muestre hasta dónde ha avanzado el algoritmo mientras defines funciones auxiliares como
S(•)El texto sobre el modelo oculto de OpenAI también estuvo bueno. Casi siempre vale la pena dedicar tiempo a ver qué más ha hecho alguien que produjo algo tan impresionante
El título debería ser "as simply as possible". No conocía el algoritmo GJK, pero si estuviera enseñando Cálculo III ahora mismo, buscaría la forma de meter este contenido en clase. Así de buena es la explicación
En el ejemplo del rectángulo suavemente redondeado al final del texto, no veo qué impide que solo se acerque cada vez más a la respuesta sin llegar realmente a alcanzarla. Claro, sé que en computación real no hay motivo para seguir después de cierto límite práctico de precisión
Al principio lo interpreté como si se aplicara alguna transformación a A y B para producir la forma A-B. Después de releer varias veces, me parece que A-B representa la intersección de otros A y B, no los dos conjuntos de la izquierda, y que lo importante es que esa intersección coincida con el origen o con 0,0. Quisiera saber si entendí bien
Presentación en video sobre el mismo algoritmo: https://www.youtube.com/watch?v=ajv46BSqcK4
Al final hay una demo interactiva que muestra la diferencia de Minkowski
El texto es muy claro e interesante
Otra forma de comprobar si dos conjuntos convexos se intersectan es resolver un problema de optimización convexa que minimice la norma de la diferencia entre un punto perteneciente al primer conjunto convexo y otro perteneciente al segundo. Si el valor óptimo es 0, entonces los dos conjuntos se intersectan
Sería interesante comparar el algoritmo GJK con la optimización convexa. No tengo claro cuál de los dos sale mejor parado
La primera imagen muestra la intersección de figuras no convexas, pero el hecho de que el algoritmo solo funciona con figuras convexas aparece bastante después, así que puede prestarse un poco a confusión
Llevo un tiempo usando la función Minkowski en openSCAD, y estuvo bueno enterarme de qué era realmente
Como esto terminó atrayendo más atención de la que esperaba, quizá debería aclarar que mi sitio personal es básicamente una colección elaborada de bromas internas
Si alguien quiere contactarme o tiene algo para mí, puede decírmelo en una respuesta
Hace casi 10 años implementé GJK basándome en la excelente explicación de Casey: https://www.youtube.com/watch?v=Qupqu1xe7Io
Una vez escribí un texto relacionado con la geometría de Minkowski: https://nickp.svbtle.com/asteroid-intersections