algoritmo de distancia de Gilbert-Johnson-Keerthi

El algoritmo de distancia de Gilbert-Johnson-Keerthi es un método para determinar la distancia mínima entre dos conjuntos convexos , publicado por primera vez por Elmer G. Gilbert , Daniel W. Johnson y S. Sathiya Keerthi en 1988. A diferencia de muchos otros algoritmos de distancia, no requiere que los datos geométricos se almacenen en ningún formato específico, sino que se basa únicamente en una función de soporte para generar iterativamente símplices más cercanos a la respuesta correcta utilizando el obstáculo del espacio de configuración (CSO) de dos formas convexas, más conocido como la diferencia de Minkowski .

Los algoritmos "GJK mejorados" utilizan información de los bordes para acelerar el algoritmo siguiendo los bordes al buscar el siguiente simplex. Esto mejora sustancialmente el rendimiento para politopos con un gran número de vértices.

GJK utiliza el subalgoritmo de distancia de Johnson, que calcula en el caso general el punto de un tetraedro más cercano al origen, pero se sabe que sufre problemas de robustez numérica. En 2017, Montanari, Petrinic y Barbieri propusieron un nuevo subalgoritmo basado en volúmenes con signo que evita la multiplicación de cantidades potencialmente pequeñas y reduce el tiempo total de CPU del algoritmo GJK en un promedio del 10 %, con mejoras que van del 5 % al 25 % en escenarios donde los objetos están en contacto. ^{[ 1 ]}

Los algoritmos GJK se utilizan frecuentemente de forma incremental en sistemas de simulación y videojuegos. En este modo, el símplex final de una solución anterior se utiliza como estimación inicial en la siguiente iteración, o "fotograma". Si las posiciones en el nuevo fotograma son similares a las del fotograma anterior, el algoritmo convergerá en una o dos iteraciones. Esto da como resultado sistemas de detección de colisiones que operan en un tiempo prácticamente constante.

La estabilidad, la velocidad y el reducido consumo de almacenamiento del algoritmo lo hacen popular para la detección de colisiones en tiempo real , especialmente en los motores de física para videojuegos .

GJK se basa en dos funciones:

• ${\displaystyle \mathrm {Soporte} (\mathrm {forma} ,{\vec {d}})}$, que devuelve el punto en la forma que tiene el producto escalar más alto con${\displaystyle {\vec {d}}}$.
• ${\displaystyle \mathrm {NearestSimplex} (s)}$, que toma un simplex s y devuelve el simplex en s más cercano al origen, y una dirección hacia el origen normal al nuevo simplex. Si s contiene el origen, NearestSimplex acepta s y se determina que las dos figuras se intersecan.

Los símplices que maneja NearestSimplex pueden ser cualquier subespacio símplice de R ⁿ . Por ejemplo, en 3D, pueden ser un punto, un segmento de línea, un triángulo o un tetraedro ; cada uno definido por 1, 2, 3 o 4 puntos respectivamente.

función GJK_intersection(forma p, forma q, vector initial_axis): vector A = Soporte(p, eje_inicial) − Soporte(q, −eje_inicial) simplex s = {A} vector D = −A bucle : A = Soporte(p, D) − Soporte(q, −D) Si dot(A, D) < 0: rechazar s = s ∪ {A} s, D, contiene_origen := Simplex más cercano(s) si contiene_origen: aceptar

• Refinamiento del portal de Minkowski
• Teorema de separación de hiperplanos

• "Un procedimiento rápido para calcular la distancia entre objetos complejos en el espacio tridimensional", Gilbert, Johnson y Keerthi - la publicación inicial
• "Cálculo de la distancia entre objetos", la implementación del algoritmo GJK del profesor de Oxford Stephen Cameron.
• "Un enfoque extraño pero elegante para un problema sorprendentemente difícil (algoritmo GJK)"
• Una videoconferencia de 52 minutos sobre la implementación de Gilbert-Johnson-Keerthi
• "Mejora del algoritmo GJK para consultas de distancia más rápidas y fiables entre objetos convexos" , Montanari, Petrinic y Barbieri.
• "Detección de colisiones acelerada: una perspectiva de optimización" , Montaut, Le Lidec, Petrik, Sivic y Carpentier. Este artículo de investigación muestra cómo el algoritmo GJK original puede acelerarse mediante estrategias de aceleración de tipo Nesterov, lo que contribuye a reducir la complejidad computacional general de GJK.