Curva de Curva cúbica: ¿Reducción máxima de gradiente y colisión?

Question

Estoy usando curvas de bezier como caminos para que mis naves espaciales viajen cuando llegan al muelle en una estación. Tengo un simple algoritmo para calcular donde el barco debe estar en el tiempo t a lo largo de una curva de Bezier:

public class BezierMovement{ 
    public BezierMovement(){ 
     // start docking straight away in this test version 
     initDocking(); 
    } 

    private Vector3 p0; 
    private Vector3 p1; 
    private Vector3 p2; 
    private Vector3 p3; 

    private double tInc = 0.001d; 
    private double t = tInc; 

    protected void initDocking(){ 

     // get current location 
     Vector3 location = getCurrentLocation(); 

     // get docking point 
     Vector3 dockingPoint = getDockingPoint(); 

     // ship's normalised direction vector 
     Vector3 direction = getDirection(); 

     // docking point's normalised direction vector 
     Vector3 dockingDirection = getDockingDirection(); 

     // scalars to multiply normalised vectors by 
     // The higher the number, the "curvier" the curve 
     float curveFactorShip = 10000.0f; 
     float curveFactorDock = 2000.0f; 

     p0 = new Vector3(location.x,location.y,location.z); 

     p1 = new Vector3(location.x + (direction.x * curveFactorShip), 
         location.y + (direction.y * curveFactorShip), 
         location.z + (direction.z * curveFactorShip)); 

     p2 = new Vector3(dockingPoint.x + (dockingDirection.x * curveFactorDock), 
         dockingPoint.y + (dockingDirection.y * curveFactorDock), 
         dockingPoint.z + (dockingDirection.z * curveFactorDock)); 

     p3 = new Vector3(dockingPoint.x, dockingPoint.y, dockingPoint.z); 


    } 

    public void incrementPosition() { 

     bezier(p0, p1, p2, p3, t, getCurrentLocation()); 

     // make ship go back and forth along curve for testing    
     t += tInc; 

     if(t>=1){ 
      tInc = 0-tInc; 
     } else if(t<0){ 
      tInc = 0-tInc; 
     } 

    } 

    protected void bezier(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, double t, Vector3 outputVector){ 

     double a = (1-t)*(1-t)*(1-t); 
     double b = 3*((1-t)*(1-t))*t; 
     double c = 3*(1-t)*(t*t); 
     double d = t*t*t; 

     outputVector.x = a*p0.x + b*p1.x + c*p2.x + d*p3.x; 
     outputVector.y = a*p0.y + b*p1.y + c*p2.y + d*p3.y; 
     outputVector.z = a*p0.z + b*p1.z + c*p2.z + d*p3.z; 

    } 
} 

La curva de punto de partida es la ubicación de la nave espacial, y el punto final es la entrada a la bahía de acoplamiento (puntos rojos en el diagrama). La nave espacial tiene un vector normalizado para su dirección, y la bahía de acoplamiento tiene otro vector normalizado para indicar la dirección en la que la nave debe viajar para alinearse directamente con la bahía de acoplamiento cuando llega (las líneas amarillas en el diagrama)

La línea verde es una ruta posible de la nave espacial, y el círculo púrpura, el radio de la nave espacial. Finalmente, la caja negra es el cuadro delimitador de la estación.

que tienen dos problemas:

1. La nave espacial se supone que sólo es capaz de convertir en radianes por segundo r
2. La nave espacial no puede volar a través de la estación de

Supongo que esto se traduce en:

a). Encontrar los "factores de curva" (longitudes de punto de control) que darán un camino donde el barco no tiene que girar demasiado apretado

b). Encontrar la ubicación/dirección de la nave espacial desde la que no puede evitar colisionar con la estación (y crear una ruta para guiarla fuera de ese estado, para que pueda avanzar con la parte a))

Sin embargo, con ambos No he tenido mucha suerte para encontrar una solución. Ya tengo un código para detectar intersecciones entre vectores, cuadros, puntos y esferas, pero aún no hay curvas más curvas. También tengo funciones que me permiten encontrar la distancia entre dos puntos.

Cualquier ayuda sería muy apreciada

Gracias, James

Answer 1

Encontrar las intersecciones exactos de una curva Bézier cúbica implica la solución de un polinomio de 5º o 6º grado. Las soluciones más factibles son utilizar métodos numéricos o subdividir la curva de Bezier.

protected void subdivide(
     Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, 
     Vector3 q0, Vector3 q1, Vector3 q2, Vector3 q3, 
     Vector3 q4, Vector3 q5, Vector3 q6) { 

    q0.x = p0.x; q0.y = p0.y; q0.z = p0.z; 
    q6.x = p3.x; q6.y = p3.y; q6.z = p3.z; 

    q1.x = (p0.x + p1.x) * 0.5; 
    q1.y = (p0.y + p1.y) * 0.5; 
    q1.z = (p0.z + p1.z) * 0.5; 

    q5.x = (p2.x + p3.x) * 0.5; 
    q5.y = (p2.y + p3.y) * 0.5; 
    q5.z = (p2.z + p3.z) * 0.5; 

    double x3 = (p1.x + p2.x) * 0.5; 
    double y3 = (p1.y + p2.y) * 0.5; 
    double z3 = (p1.z + p2.z) * 0.5; 

    q2.x = (q1.x + x3) * 0.5; 
    q2.y = (q1.y + y3) * 0.5; 
    q2.z = (q1.z + z3) * 0.5; 

    q4.x = (x3 + q1.x) * 0.5; 
    q4.y = (y3 + q1.y) * 0.5; 
    q4.z = (z3 + q1.z) * 0.5; 

    q3.x = (q2.x + q4.x) * 0.5; 
    q3.y = (q2.y + q4.y) * 0.5; 
    q3.z = (q2.z + q4.z) * 0.5; 
} 

q1 .. q3 se convierte en el primer segmento. q3 .. q6 se convierte en el segundo segmento.

Subdividir la curva 2-5 veces, y usar los puntos de control como una polilínea.

---

El curvature se pudo calcular en los puntos finales de cada segmento:

protected double curvatureAtStart(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3) { 
    double dx1 = p1.x - p0.x; 
    double dy1 = p1.y - p0.y; 
    double dz1 = p1.z - p0.z; 

    double A = dx1 * dx1 + dy1 * dy1 + dz1 * dz1; 

    double dx2 = p0.x - 2*p1.x + p2.x; 
    double dy2 = p0.y - 2*p1.y + p2.y; 
    double dz2 = p0.z - 2*p1.z + p2.z; 

    double B = dx1 * dx2 + dy1 * dy2 + dz1 * dz2; 

    double Rx = (dx2 - dx1*B/A)/A*2/3; 
    double Ry = (dy2 - dy1*B/A)/A*2/3; 
    double Rz = (dz2 - dz1*B/A)/A*2/3; 

    return Math.sqrt(Rx * Rx + Ry * Ry + Rz * Rz); 
} 

---

Para resolver Problema 1, subdividir la curva de un par de veces, y calcular la curvatura en el punto final de cada segmento Esto solo será una aproximación, pero podría subdividir selectivamente los segmentos con una curvatura alta para obtener una mejor aproximación en esa región.

---

Para resolver el problema 2 , se podría subdividir tres curvas:

• Uno con velocidad cero en ambos extremos (C0). Esto produciría una línea recta.
• Uno con velocidad cero en el primer punto final y uno en el segundo (C1).
• Uno con velocidad uno en el primer punto final y cero en el segundo (C2).

Si subdivide todas las curvas de la misma manera, podría evaluar rápidamente los puntos de control de la curva final. Se mezclan el control en puntos correspondientes, parametrizada por las velocidades en los puntos finales:

C[i] = C0[i] + (C1[i] - C0[i])*v1 + (C2[i] - C0[i])*v2 

Se podía con este encontrar parámetros-rangos válidos, de modo que ningún segmento (evaluado como una línea-segmento recto) se cruza con el estación. (v1 y v2 puede ir por encima de 1.0).