Krzywa Beziera Krzywa: Maksymalne unikanie kolizji i kolizji?

Question

Używam krzywych Beziera jako ścieżek do poruszania się statkami kosmicznymi, kiedy zbliżają się do stacji dokującej. Mam prosty algorytm do obliczania gdzie statek powinien być w czasie t wzdłuż krzywej sześciennej Beziera:

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; 

    } 
} 

Krzywa punkt startu jest lokalizacja statek kosmiczny, a punkt końcowy znajduje się wejście do hangaru (czerwone kropki na schemacie). Statek kosmiczny ma znormalizowany wektor dla jego kierunku, a wnęka dokująca ma inny znormalizowany wektor, który wskazuje kierunek, w którym statek musi się przemieszczać, tak aby był wyrównany bezpośrednio do dokującej stacji, gdy nadejdzie (żółte linie na schemacie)

Zielona linia to możliwa ścieżka statku kosmicznego i fioletowy okrąg, promień statku kosmicznego. W końcu czarna skrzynka to ramka ograniczająca dla stacji.

mam dwa problemy:

1. kosmicznym ma tylko być w stanie obrócić w R radianach na sekundę
2. statek kosmiczny nie może latać przez stację

Zakładam, że przekłada się to na:

a). Znalezienie "współczynników krzywej" (długości punktów kontrolnych), które dadzą ścieżkę, w której statek nie musi zbyt mocno skręcić

b). Znalezienie lokalizacji/kierunku statku kosmicznego, z którego nie może uniknąć kolizji ze stacją (i utworzenie ścieżki do wyprowadzenia go z tego stanu, aby można było przejść do części a))

Jednak w przypadku obu tych , Nie miałem szczęścia znaleźć rozwiązania. Mam już kod do wykrywania przecięć między wektorami, ramkami, punktami i sferami, ale jeszcze nie krzywymi Beziera. Mam również funkcje pozwalające mi znaleźć odległość między dwoma punktami.

Każda pomoc będzie najbardziej cenionych

Dzięki James

Answer 1

Znalezienie dokładnych przecięcia Baziera Curve polega na rozwiązywaniu 5. lub 6. stopień wielomianu. Bardziej realistyczne rozwiązania są albo za pomocą metod numerycznych, albo dzieląc krzywą Beziera.

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 staje pierwszy segment. q3 .. q6 staje się drugim segmentem.

Podziel krzywa 2-5 razy i użyj punktów kontrolnych jako polilinii.

---

The curvature można obliczyć w punktach końcowych każdego segmentu:

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); 
} 

---

Aby rozwiązać Problem 1 podzielić ten krzywą kilka razy i oblicza krzywiznę z punkt końcowy każdego segmentu. To będzie tylko przybliżenie, ale możesz selektywnie dzielić segmenty o wysokiej krzywiźnie, aby uzyskać lepsze przybliżenie w tym regionie.

---

Aby rozwiązać problem , można podzielić trzy krzywe:

• Jeden z zerową prędkością w obu punktach końcowych (C0). To by wytworzyło linię prostą.
• Jeden z prędkością zero na pierwszym punkcie końcowym i jeden na drugim (C1).
• Jeden z prędkością 1 na pierwszym punkcie końcowym i zero na drugim (C2).

Jeśli podzielisz wszystkie krzywe w ten sam sposób, możesz szybko ocenić punkty kontrolne końcowej krzywej. Możesz połączyć odpowiednie kontrolno-punktów, parametryzowane przez prędkościami w końcowych punktach:

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

Można z tym znalezienie prawidłowych parametrów-zakresy, tak że żaden segment (oceniana jako prostej segmencie) przecina stacja. (v1 i v2 może przekroczyć 1,0).