Punkte, die gleichmäßig entlang einer Bezierkurve verteilt sind

10

Ich habe mich eine Weile umgesehen und kann keine Lösung für dieses Problem finden. Angenommen, ich habe eine kubische Bezierkurve (definiert durch 4 Punkte) und möchte eine Reihe von Punkten erhalten, die gleichmäßig entlang der Kurve verteilt sind. Stellen Sie sich zum Beispiel einen Text entlang einer Kurve vor.

Das Problem ist nun, dass bei einer Eingabe t(Interpolationswert von 0-1) mit einem konstanten Inkrement die Punkte nicht gleichmäßig verteilt sind. Der Abstand entlang der Kurve ist kleiner, wenn die Kurve eine Kurve macht, und länger, wenn die Kurve gerade ist.

Wie platziere ich Punkte gleichmäßig entlang einer Bezierkurve?

Foaly
quelle
4
Suchen Sie eine "rein mathematische" (oder besonders effiziente) Lösung? Andernfalls lautet der einfache Ansatz: Konvertieren Sie die Kurve in eine Polylinie, indem Sie entlang der Kurve gehen t, beispielsweise 100 Schritte erhöhen und die Abstände zwischen den resultierenden Punkten messen. Interpolieren Sie dann wie gewünscht entlang dieser Polylinie.
Marco13
Ich denke, Sie suchen nach dem Schlüsselwort "Bogenlängenparametrisierung", das zum Beispiel in dieser Frage beantwortet wurde .
Wondra
Was @ Marco13 gesagt hat!
David van Brink
Den Antworten / Kommentaren zufolge ist der von mir erwähnte Ansatz nicht nur einfach, sondern auch ziemlich verbreitet. Ist das für eine bestimmte Sprache? Vielleicht würde dann jemand ein paar Codezeilen
posten
1
Mögliches Duplikat der Bewegung
Ingenieur

Antworten:

3

Es ist eher eine mathematische Frage. Eine Bezierkurve hat also die folgende Formel , sowohl in der xals auch in der yKomponente.

B_x(t) = (1-t)^3 * P0_x + (1-t)^2 * t * P1_x + (1-t) * t^2 * P2_x + t^3 * P3_x
B_y(t) = (1-t)^3 * P0_y + (1-t)^2 * t * P1_y + (1-t) * t^2 * P2_x + t^3 * P3_y

Die tentlang einer Kurve zurückgelegte Länge gammaist gegeben durch:

length_gamma(t) = integration( sqrt( derivative(  gamma_x(s)  ) ^2 + derivative(  gamma_y(s)  ) ^2 ) )

Es gibt keine vom Menschen beschreibbare Lösung für das Integral, daher müssen Sie sich annähern.

Ersetzen der gamma(t)durch den Ausdruck B(t)der Länge zu erhalten length_Bdurch reiste tentlang der Bezier - Segment. Nehmen wir an, es reist von 0nach L.

Wählen Sie nun nWerte zwischen 0und L, die den gleichmäßig verteilten Punkten entsprechen. Zum Beispiel Längen des Formulars k*L/nfür kvon 0bis n.

Jetzt müssen Sie die Funktion umkehren length_B, damit Sie die tRückseite aus der Länge berechnen können l. Es ist ziemlich viel Mathe und ich bin verdammt faul, versuche es selbst. Wenn Sie nicht können, können Sie zum Mathe-Stapelaustausch gehen . Für eine vollständigere Antwort können Sie trotzdem dorthin gehen.

Sobald Sie diese Umkehrfunktion length_B(oder eine vernünftige Annäherung) haben, ist Ihre Verarbeitung recht einfach.

  • Erstellen Sie Längen l[k]mit einem bestimmten Pfadabstand vom Ursprung (P0_x,P1_x).
  • Berechnen Sie die entsprechende t[k]Verwendung length_B_inverse.
  • Positionieren Sie die Punkte mit (B_x(t[k]),B_y(t[k])).
Lærne
quelle
1
Vielen Dank! Es stellt sich heraus, dass die Mathematik, die Sie zur Integration des Bernstein-Polynoms benötigen, ein Albtraum ist. Ich konnte diese Lösung verwenden
Foaly
0

Um das zu erweitern, was Marco gesagt hat, besteht eine übliche Technik darin, die Kurve in viel kleineren Schritten als den Schritten fester Länge, die Sie ausführen möchten, entlangzugehen und den resultierenden Ausgabepunkt (und möglicherweise die Entfernung?) In einer Tabelle zu speichern.

Anschließend gehen Sie die Tabelle durch und verwerfen alle Einträge mit Ausnahme der Punkte, die den ganzzahligen Vielfachen der Entfernungen, die Sie zurücklegen möchten, am nächsten liegen.

Dann bleibt Ihnen eine Tabelle übrig, die Sie sehr schnell direkt zur Laufzeit indizieren können. Wenn Sie zu der Stelle gehen möchten, die fünfmal so groß ist wie Ihre Entfernung, sehen Sie in Ihrer Tabelle nach Index [5].

Beachten Sie, dass Sie die beiden Schritte in einem Schritt ausführen und die zusätzlichen Elemente zunächst nicht in der Tabelle speichern können. Es ist jedoch einfacher, sie in zwei Schritten zu visualisieren und zu verstehen.

Ich habe einmal eine Technik gesehen, mit der dies tatsächlich im laufenden Betrieb berechnet werden kann, ohne eine Tabelle vorab zu berechnen (es wurde auch keine Iteration / Wurzelfindung verwendet!), Aber leider kann ich mich überhaupt nicht an die Details erinnern):

Wenn ich mich daran erinnere oder es finde, werde ich die Infos posten!

Alan Wolfe
quelle
1
Dies könnte auch für Sie von Interesse sein: math.stackexchange.com/questions/15896/…
Alan Wolfe
0

Schritt 1 - Generieren Sie N + 1 Punkte, indem Sie die Kurve in Schritten von 1 / N interpolieren. N sollte groß genug für gute visuelle Ergebnisse sein, aber klein genug, um leicht berechnet zu werden. Ein Wert von 50 sollte in den meisten Situationen in Ordnung sein, sollte jedoch auf Ihren speziellen Fall abgestimmt sein. Ich werde dies die "interpolierten Punkte" nennen.

Alternativ können Sie eine kurze Liste von Segmenten erstellen und jedes Segment rekursiv aufteilen, das länger als die gewünschte maximale Segmentlänge ist (anfangs sollten Sie mindestens vier Segmente generieren, um S-Kurven zu berücksichtigen, bei denen der Anfang sehr nahe am Ende liegt).

Schritt 2 - "Gehen Sie die Linie" mit den interpolierten Punkten und dem gewünschten Abstand zwischen den einzelnen Punkten.

Ich lasse es hier meinen Unity-Code:

public static Vector2[] InterpolateBezier(Vector2 start, Vector2 startControlPoint,
    Vector2 end, Vector2 endControlPoint, int segments)
{
    Vector2[] interpolated = new Vector2[segments + 1];
    interpolated[0] = start;
    interpolated[segments] = end;

    float step = 1f / segments;
    for (int i = 1; i < segments; i++)
    {
        interpolated[i] = GetBezierPosition(start, startControlPoint, end,
            endControlPoint, i * step);
    }

    return interpolated;
}

public static Vector2 GetBezierPosition(Vector2 start, Vector2 startControlPoint,
    Vector2 end, Vector2 endControlPoint, float t)
{
    float omt = 1f - t;
    float omt2 = omt * omt;
    float t2 = t * t;

    return
        start * (omt2 * omt) +
        startControlPoint * (3f * omt2 * t) +
        endControlPoint * (3f * omt * t2) +
        end * (t2 * t);
}

public static List<Vector2> WalkLine(Vector2[] points, float spacing, float offset = 0)
{
    List<Vector2> result = new List<Vector2>();

    spacing = spacing > 0.00001f ? spacing : 0.00001f;

    float distanceNeeded = offset;
    while (distanceNeeded < 0)
    {
        distanceNeeded += spacing;
    }

    Vector2 current = points[0];
    Vector2 next = points[1];
    int i = 1;
    int last = points.Length - 1;
    while (true)
    {
        Vector2 diff = next - current;
        float dist = diff.magnitude;

        if (dist >= distanceNeeded)
        {
            current += diff * (distanceNeeded / dist);
            result.Add(current);
            distanceNeeded = spacing;
        }
        else if (i != last)
        {
            distanceNeeded -= dist;
            current = next;
            next = points[++i];
        }
        else
        {
            break;
        }
    }

    return result;
}
Jorge Galvão
quelle
-1

Hier ist ein Algorithmus, der ziemlich gute Ergebnisse liefert:

  Point Index(float pos) const
  {
    int count = p.NumPoints();
    Vector val(0.0,0.0,0.0);
    for(int i=0;i<count;i++)
      { 
        val += bin(pos,i,count-1)*Vector(p.Points(i));
      }
    return Point(val);
  }
  float bin(float pos, int i, int n) const
  { 
    return float(ni(n,i)) * pow(double(pos), double(i))*pow(double(1.0-pos), double(n-i));
  }
  int ni(int n, int i) const
  {
    if (i==0) { return 1; }
    if (n==i) { return 1; }
    return ni(n-1,i-1)+ni(n-1,i);
  }
tp1
quelle