Zeichnen Sie Splines mit Direct2D

Wenn Sie nicht bereits über funktionierenden Code für grundlegende NURBS-Operationen verfügen oder ein NURBS-Experte sind, rate ich Ihnen, eine NURBS-Bibliothek zu verwenden. Im Allgemeinen sind die für Ihr Problem relevanten Operationen: Punktauswertung , Knoteneinfügung , Aufspaltung und vielleicht Gradhöhe .

Für die Allgemeinheit werde ich drei mögliche Lösungen beschreiben.

Aufgeteilt nach Knoten

Angenommen, Ihre Eingabe-NURBS-Kurven sind nicht-rational (keine Gewichte = Einheitsgewichte) und ihr Grad kann den maximal zulässigen Grad der resultierenden Bezier-Kurven nicht überschreiten. Dann ist jede Spanne des Splines eine Polynomkurve, so dass sie als Bezier-Kurve extrahiert werden kann.

Abhängig von der verwendeten Bibliothek kann die Beschreibung des Algorithmus unterschiedlich sein. Hier sind mögliche Varianten:

1. Wenn es eine Funktion gibt, um eine NURBS-Kurve in Bezier-Kurven aufzuteilen, rufen Sie sie einfach auf.
2. Angenommen, es gibt eine Funktion zum Aufteilen einer Kurve in zwei Subkurven bei einem gegebenen Parameter. Dann teilen Sie Ihre Kurve in jedem internen Knoten (d. H. Nicht gleich Min / Max-Knoten). Tun Sie dasselbe für jede der Subkurven, bis keine internen Knoten mehr vorhanden sind, was bedeutet, dass alle Kurven Bezier sind.
3. Jede NURBS-Bibliothek muss Knoten einfügen Funktion haben. Für jeden Knoten Ki mit einer Multiplizität kleiner als D (Grad), rufen Sie die Knoteneinfügung mit param = Ki auf. Sie können verschiedene Knoten in beliebiger Reihenfolge einfügen. Die Bibliothek kann auch "Mehrfachknoten einfügen" enthalten, wodurch alle Einfügungen zu einem Aufruf kombiniert werden können. Am Ende müssen Min / Max-Knoten die Multiplizität D + 1 haben, alle internen Knoten müssen die Multiplizität D haben. In diesem Moment beschreiben die Kontrollpunkte die von Ihnen benötigten Bezier-Kurven vollständig: Kontrollpunkte [0..D] definieren die 0- th Bezier, [D.2D] definieren die 1-ten Bezier, ..., [q D .. (q + 1) D] Kontrollpunkte definieren die q-te Bezier.

Wenn der Grad der eingegebenen NURBS-Kurve niedriger ist als der erforderliche Grad an Bezier-Kurven, können Sie auch die Grad-Höhe entweder für die ursprüngliche NURBS-Kurve oder für die resultierenden Bezier-Kurven aufrufen. Apropos ID2D1GeometrySink, akzeptiert alle Bezier-Kurven mit Grad & lt; = 3 (lineare Bezier-Kurve ist einfach ein Liniensegment), also ist es nicht notwendig.

Wenn Ihre NURBS-Kurve einen inakzeptabel hohen Grad hat oder rational sein kann, dann müssen Sie die Kurve entweder mit kubischem Spline (härter und schneller) oder mit Polylinie (einfacher, aber langsamer) approximieren.

Garantierte Polylinienapproximation

Hier ist ein ziemlich einfacher rekursiver Algorithmus, der eine Polylinienapproximation einer NURBS-Kurve mit garantiertem Fehler & lt; = MaxErr.

1. Zeichnen Sie ein Liniensegment vom ersten bis zum letzten Kontrollpunkt der Kurve.
2. Überprüfen Sie, ob sich alle Kontrollpunkte innerhalb der MaxErr-Entfernung vom Segment befinden.
3. Wenn dies der Fall ist, fügen Sie der Ausgabe das Liniensegment hinzu.
4. Andernfalls teilen Sie die Kurve in der Mitte in zwei Unterkurven und approximieren Sie sie rekursiv.

Um es zu implementieren, benötigen Sie die NURBS-Kurvenaufteilung (die durch Einfügen von Knoten implementiert werden kann).

Heuristische Polylinienapproximation

Wenn keine NURBS-Bibliothek zur Hand ist, kann das Einsetzen des Knotens eine Menge Schmerzen verursachen. Deshalb beschreibe ich eine weitere Lösung, die nur Punktauswertung von NURBS-Kurven verwendet. Sie können die Punktbewertung entweder über den de Boor-Algorithmus oder per Definition implementieren (siehe Basisfunktionen und NURBS Kurve Definitionen)

Der Algorithmus ist rekursiv, er akzeptiert ein parametrisches Intervall auf der ursprünglichen Kurve als Eingabe.

1. Werten Sie den Start- und den Endpunkt des parametrischen Intervalls aus.
2. Zeichnen Sie ein Liniensegment durch sie.
3. Werten Sie einige Punkte auf der Kurve innerhalb des parametrischen Intervalls aus.
4. Überprüfen Sie, ob diese internen Punkte innerhalb der MaxErr-Entfernung des Liniensegments liegen.
5. Wenn dies der Fall ist, fügen Sie der Ausgabe das Liniensegment hinzu.
6. Andernfalls teilen Sie das parametrische Intervall in zwei Hälften und rufen Sie die Annäherung rekursiv auf.

Dieser Algorithmus ist adaptiv und kann in seltenen Fällen eine schlechte Approximation in der Praxis erzeugen. Die Prüfpunkte können innerhalb des parametrischen Intervalls einheitlich gewählt werden. Für mehr Zuverlässigkeit ist es besser, auch die Kurve an allen Knoten der Eingangskurve auszuwerten, die innerhalb des parametrischen Intervalls liegen.

Third-Party-Bibliothek

Wenn Sie nicht viel mit NURBS arbeiten, empfehle ich, die tinyspline Bibliothek zu nehmen. Es ist sehr klein von Design, hat keine Abhängigkeiten und hat MIT-Lizenz. Außerdem scheint es aktiv entwickelt zu sein, so dass Sie dem Autor im Falle von Problemen kommunizieren können.

Es scheint, dass die erste Lösung für den Themenstarter ausreicht, also hier ist der Code zum Aufteilen von NURBS in Bezier-Kurven mit tinyspline:

Schlussnotiz

Der Großteil des obigen Textes geht davon aus, dass Ihre NURBS-Kurven geklammert sind, was bedeutet, dass Min- und Max-Knoten die Multiplizität D + 1 haben. Nicht geklemmte NURBS-Kurven werden manchmal auch verwendet. Wenn Sie eines treffen, müssen Sie es möglicherweise auch mithilfe der entsprechenden Funktion der Bibliothek einspannen. Methode toBeziers von tinyspline verwendet knapp über Klammern NURBS automatisch, müssen Sie nicht manuell klemmen.

Direct2D, klarer ID2D1GeometrySink , unterstützt keine Splines, sondern kubische Bezier-Kurven, die zu einem Spline zusammengesetzt werden können. Im Gegenteil, Sie können B-Kurven aus Ihren Spline-Daten erhalten und diese einfach zu Ihrer Geometrie hinzufügen.

Der Algorithmus wird einfach durch dieses Bild erklärt: .

Einen Artikel für kurze und gute Erklärungen finden Sie hier . Sie können Ihren Spline teilen, bis sich die Kontrollpunkte überlappen und der Grad gesenkt werden kann, sogar bis alle Kurven flach genug sind, um Linien zu sein. Die letzte Sache ist keine schlechte Idee, da Ihre Hardware keine Kurven kennt, also werden Ihre übergebenen Kurven sowieso später in Zeilen umgewandelt. Wenn Sie diese Konvertierung durchführen, können Sie die Toleranz für die Ebenheit bestimmen und unschöne Kanten vermeiden.