Teilkurven von Bezier-Splines

Written by Stephan Michels on 8. Januar 2012. Posted in Cocoa, Computergrafik

 

Ich hatte folgendes Problem: Ich hatte eine Kurve, dargestellt durch ein Bezier-Spline, an deren Enden jeweils ein Pfeil angezeigt werden sollte. Nun sollte aber die Kurve nicht jeweils um die Länge der Pfeilspitzen verlängert werden, sondern die Kurve sollte um die Länge der Spitzen verkürzt werden.

 

Als Beispiel wurde hier ein Bezier-Spline mit den beiden Knotenpunkten p1 und p4, sowie mit den Kontrollpunkten p2 und p3 dargestellt. Die Idee ist nun eine Teilkurve zu finden, welche von Start bis End geht.

Nun lassen sich Teile von Splines nicht einfach berechnen wie z.B. bei geraden Linien, weil Splines parametrisierte Kurven sind. Selbst die Länge von Bezier-Splines lässt sich nicht ohne weiteres berechnen. Bei der Suche nach einer Lösung bin auf den wundervollen Artikel „Adaptive Subdivision of Bezier Curves“ von Maxim Shemanarev gestoßen.

Dieser Artikel handelt hauptsächlich von der Berechnung der Länge von Bezier-Splines. Seine Lösung benutzt eine ganze besondere Eigenschaft von Bezier-Splines, bei der von Bezier-Splines zwei Bruchstücke einfach über Trigonometrie berechnen werden können.

In der Darstellung wird gezeigt, dass wir zwei neue Kurven erhalten mit jeweils p1 und p1234 bzw. p1234 und p4 als Knotenpunkte, sowie p12 und p123 bzw. p234 und p34 als Kontrollpunkte.

Mit Hilfe von Intervallschachtelung lassen sich nun die Bruchstücke immer weiter verkleinern. Dabei werden die Bruchstücke dahingehend unterschieden, ob sich die Bruchstücke in dem gewünschten Intervall befinden oder nicht.

Auch hier hab ich ein kleines Demo-Programm geschrieben, um den Algorithmus auszuprobieren. Der Algorithmus ist als Kategorie von NSBezierPath wegen der einfachen Wiederverwendbarkeit implementiert. Auch um die Kategorie universell zu gestalten, habe ich darauf geachtet, dass der Algorithmus mit Linien-Segmenten und auch mit unterbrochen Segmenten umgehen kann. Der Code ist wieder zu finden auf Github.

Trackback from your site.

Leave a comment

Current month ye@r day *