El algoritmo de distancia de Gilbert-Johnson-Keerthi es un método para determinar la distancia mínima entre dos conjuntos convexos . A diferencia de muchos otros algoritmos de distancia, no requiere que los datos de geometría se almacenen en ningún formato específico, sino que se basa únicamente en una función de soporte para generar iterativamente simples más cercanos a la respuesta correcta utilizando la configuración del obstáculo espacial (CSO) de dos formas convexas. , más comúnmente conocida como la diferencia de Minkowski .
Los algoritmos "GJK mejorados" utilizan información de borde para acelerar el algoritmo siguiendo los bordes cuando se busca el siguiente símplex. Esto mejora sustancialmente el rendimiento de los politopos con un gran número de vértices.
GJK hace uso del 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 logró una aceleración del 15% al 30%.
Los algoritmos GJK se utilizan a menudo 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 conjetura inicial en la siguiente iteración o "marco". Si las posiciones en el nuevo fotograma están cerca de las del antiguo, el algoritmo convergerá en una o dos iteraciones. Esto produce sistemas de detección de colisiones que operan en un tiempo casi constante.
La estabilidad, la velocidad y el pequeño espacio de almacenamiento del algoritmo lo hacen popular para la detección de colisiones en tiempo real , especialmente en motores de física para videojuegos .
Descripción general
GJK se basa en dos funciones:
- , que devuelve el punto en la forma que tiene el producto escalar más alto con.
- , que toma un simplex sy devuelve el simplex en s más cercano al origen, y una dirección hacia el origen normal al nuevo simplex. Si s mismo contiene el origen, NertherSimplex acepta s y se determina que las dos formas se intersecan.
Los simples manejados por NehestSimplex pueden ser cada uno de los subespacios símplex de R n . 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.
Pseudocódigo
función GJK_intersection (forma p, forma q, vector eje_inicial): vector A = Soporte (p, eje_inicial) - Soporte (q, −axis_inicial) simplex s = {A} vector D = −A bucle : A = Soporte (p, D) - Soporte (q, −D) si el punto (A, D) <0: rechazar s = s ∪ A s, D, contains_origin: = Simplex más cercano (s) si contiene_origen: aceptar
Ilustración
Ver también
enlaces externos
- "Un procedimiento rápido para calcular la distancia entre objetos complejos en un espacio tridimensional", Gilbert, Johnson y Keerthi - la publicación inicial
- "Calcular la distancia entre objetos", implementación de GJK del profesor de Oxford Stephen Cameron
- "Un enfoque extraño pero elegante para un problema sorprendentemente difícil (algoritmo GJK)"
- Una conferencia en video 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.