- 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
d y se encuentra el primer punto p.
- Búsqueda de punto: se calcula el producto punto de
d y p; 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
Algoritmo GJK: En los años 90, me costó un año entender el algoritmo GJK. Es útil para detección de colisiones y para encontrar los puntos más cercanos. La idea básica es fácil de entender. Se empieza con dos sólidos convexos, se elige un punto aleatorio y se intenta mejorar la distancia entre cada punto. Se eligen los puntos más cercanos y se repite. Cuando el punto más cercano deja de ser un vértice, hace falta el concepto de "símplex". Se trata de analizar varios casos. En motores físicos surgen problemas cuando los objetos se estabilizan en contacto cara a cara. En teoría es una solución 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. En el caso general es O(log N), y cuando está cerca de la posición anterior es O(1). El fallecido profesor Stephen Cameron, de Oxford, investigó mucho para implementar GJK correctamente. A fines de los 90, se usó GJK en el sistema comercial de ragdolls 3D "Falling Bodies".
Redacción de una explicación de GJK: Como no encontré una explicación intuitiva del algoritmo de detección de colisiones GJK, escribí una yo mismo. Pido que me digan si hay una forma de hacerlo más claro y eficiente. Como es una explicación matemática hecha por un estudiante de secundaria, conviene tomarla con un nivel adecuado de escepticismo.
Video del algoritmo GJK: Comparto un enlace a una presentación en video sobre el mismo algoritmo. Enlace al video
Elogio al artículo: Es un artículo excelente. Muy claro e interesante.
Comparación con optimización convexa: Otra forma de comprobar la intersección entre dos conjuntos convexos es resolver un problema de optimización convexa que minimiza la norma de la diferencia entre dos puntos. Si el valor óptimo es 0, entonces los conjuntos tienen un punto de intersección. Me gustaría ver una comparación entre el algoritmo GJK y el método de optimización convexa. No estoy seguro de cuál es mejor.
Elogio al artículo y malentendido: Es un gran artículo. Sin embargo, la primera imagen muestra una intersección de formas no convexas, pero más adelante se aclara que el algoritmo solo funciona con formas convexas.
Primera vez que escucho sobre el algoritmo GJK: Es la primera vez que oigo hablar del algoritmo GJK.
Post de blog relacionado: Escribí un post de blog relacionado con la geometría de Minkowski. Enlace al blog
Sitio web personal: Como inesperadamente está recibiendo mucha atención, menciono que mi sitio web personal está lleno de bromas. Si quieren contactarme, avísenme en una respuesta.
Uso de la función Minkowski: He usado la función Minkowski en openSCAD, y me alegra saber qué es realmente.
Elogio al algoritmo: Es un algoritmo increíble.