Bezier, Hermite & Spline Interpolation

Hier entsteht ein Tutorial

Der Text wird in den kommenden Stunden (und Tagen) formatiert!

................... Teil 1

Spline-Interpolation

Die Spline-Interpolation ist ein Begriff, der in den letzten Jahren zunehmend an Bedeutung gewinnt – und vor 30 bis 40 Jahren noch weitgehend unbekannt war. Und dies obwohl sie schon seit 100erten von Jahren genutzt wird. Paradox?

Zunächst einmal, der Begriff "Spline" kommt aus dem englischen, er bedeutet zu deutsch "Straklatte", was sicher auch nicht unbedingt für jedermann eingänglich ist; trotzdem: Sie hatten so was wahrscheinlich aber schon mal in der Hand!!!

Ich spreche von einem federnden etwas, das sich biegt aber nicht bricht und gerne in seine Ausgangsform zurückkehrt, z. B. ein Lineal. Unter Einwirkung einer äußeren Kraft läßt sich das Lineal im kleinen, die Straklatte im großen, oftmals sehr großen Maß verbiegen: Dem Schiffbau bis hin zur Titanic!

Das Geheimnis ist gelüftet: Will man mehrere Punkte (für den Rumpf eines Schiffes) elegant verbinden, so kommt die Straklatte seit einigen 100 Jahren zum Einsatz. Auf den Werften der Welt wurde sie auf dem Dach-Boden "1 zu 1" ausgelegt, geformt, mit Hammer & Nagel fixiert, gezeichnet und danach die Spanten geschnitten. Wird die Latte an nur wenigen Punkten fixiert, so tritt eine innere Spannung auf, die sie in eine weiche, stetige "elegante" Verformung führt. Was die Schiffbauer schon lange konnten, konnte nur kein Mensch berechnen.

Inzwischen überhäufen sich mathematische Lösungs-Ansätze hierzu, deren Ver-ständnis mehrerer Semester höherer Mathematik bedarf. Als ich das studiert habe, gab es die Dinger noch nicht – bzw. die Mathematik stand auf dem Index militäri-scher Staatsgeheimnisse – konnte man hiermit doch "Frei-Formen" berechnen und fertigen, die eine geräuschlose U-Boot Fahrt ermöglichte!

Ich gebe unumwunden zu, die Mathematik hierfür nicht nachvollziehen geschweige denn aufstellen zu können. Aber Einsetzen kann ich sie. Diese Ausarbeitung fokus-siert daher auf Kurvendiskussion und angewandte Mathematik in Hinblick auf die Steuerung von Robotern und hochachsigen CNC Bearbeitungscentren.

•In Teil 2 dieser Ausarbeitung finden Sie den Zugang zu einer praxisorientier-ten Excel®-Studie. Vieles von dem, was ich hier schreibe habe ich mit dieser Studie erarbeitet! - Einiges in diesem Tutorial nimmt hierauf Bezug.

Interpolation

beschreibt die Aufgabe einen oder mehrere nicht bekannte Punkte zwischen bekann-ten zu bestimmen, dies kann sehr einfach sein, wenn wir wissen, welcher Funktion die bekannten Punkte folgen: Es ist kein Problem einen beliebigen Sinuswert oder Parabelpunkt zu interpolieren – denn wir kennen die Funktion die die Ortskurve be-schreibt. Haben wir jedoch eine Vielzahl von Punkten – aber keine Ahnung, wie sie entstanden sind – dann wird die Sache interessant.

Letztendlich können wir unendlich viele Kurven durch diese Punkte legen, - welche die richtige ist, wissen die Götter. Wir können die Aufgabe etwas eingrenzen, indem wir die Verbindung der Punkte mit Geraden (lineare Interpolation) ausschließen und wir können evtl. sagen, die Verbindungslinie solle nicht allzu wellig sein. Eine wachsweiche Definition – die dem Spline recht nahe kommt.

Spline und Polynom

Das klassische Polynom verbindet eine beliebige Anzahl von Stützpunkten (K) mit einem Kurvenzug der Ordnung (K-1). 5 Stützstellen erfordern also eine Kurve 4-ter Ordnung, die exakt diese Stützstellen verbinden wird. Allerdings schwingt diese Kur-ve zwischen den Stützstellen erheblich (oszilliert), so daß der Polynomzug extrem wellig wird. Verantwortlich hierfür ist, daß die Kurve mit einer einzigen Funktion be-schrieben wird. Im Gegenteil hierzu verbindet ein Spline die Punkte mit mehreren Kurvenabschnitten, die nicht einer einheitlichen mathematischen Funktion folgen, sondern aus "polynomen Bruchstücken" zusammengesetzt werden.

Die Spline-Kurve verbindet alle Punkte – nicht etwa linear durch Geraden, sondern Parabeln. Grundelemente sind kubische Parabeln (hoch 3), quadratische Parabeln (hoch 2) und lineare Glieder, die mit geeigneten Koeffizienten gestreckt, gestaucht und verschoben werden. Das Ergebnis nennt sich in seiner Grundform "Kubischer Spline". Mehrere dieser Parabeln bilden Teilstücke des Splines, wobei die Übergän-ge an den Knotenstellen die gleiche Tangente aufweisen – dies macht den weichen Übergang. Im mathematischen Sinne handelt es sich um "glatte Kurven":

Zitat:

"Glatte Kurve" bedeutet dabei im mathematischen Sinne, daß die Kurve zweimal stetig differen-zierbar sein soll. Alle gegebenen Punkte stellen als Stützstellen der Kurve sozusagen auch Naht-stellen zwischen den Teilkurven dar, in denen jeweils beide Funktionswerte, beide erste und auch zweite Ableitungen der zusammentreffenden Teilkurven übereinstimmen. Diese Naht- oder Stütz-stellen werden auch Knoten genannt. http://www.arndt-bruenner.de/mathe/scripts/kubspline.htm

Aber bitte glauben Sie nicht, daß diese Splines nicht schwingen würden, Vielleicht nicht ganz so extrem wie ein Polynom, trotzdem: Ich habe es in der Analyse ge-schafft, die Scheitelpunkte eines Splines um das 25.000-fache über seine y-Stützwerte hinauszutreiben!

2 Charakteristika haben diese Kurven.

•Sie verbinden die Punkte, aber nicht auf dem kürzesten Weg (das wäre eine Ge-rade), sondern schwingen vor und hinter den Stützstellen ein bzw. (mehr oder weniger) über, sie oszillieren. Je näher sich die x-Werte kommen, je weiter die Y–Werte auseinander liegen, je stärker wird die Neigung zum Oszillieren.

•Verschiebt man einen Stützpunkt auf der y-Achse, so folgt der Spline, verschiebt man ihn auf der x-Achse so folgt der Spline, solange sich der Stütz-punkt zwischen 2 anderen Stützstellen befindet. Verschiebt man einen Stützpunkt über einen anderen hinaus, so tauschen die Stützpunkte ihre x-Achsen Wertigkeit – und der Spline ggf. seine y-Ausrichtung!

Interpoliert man eine zeitlich kontinuierlich forschreitende Meßreihe so ist dies un-problematisch. Findet man eine Vielzahl von Punkten, die es zu verbinden gilt, so wird man diese in einem Koordinaten System erfassen. Nach Murphys Gesetz der größten Gemeinheit hängt die Schwingneigung davon ab, wie das xy-Koordinaten System die Punkte erfaßt:

Denk-Experiment:

Man nehme die Eckpunkte einer symmetrischen Trapez-Kurve: •Liegt die Kurve parallel zur x-Achse, so wird der Spline Sinus-ähnlich über-schwingen. •Dreht man die Kurve im Koordinatensystem, so verändern sich die x-Achsen Ab-stände. - Paarweise verkürzt sich der Abstand, paarweise verlängert er sich. - Der Spline oszilliert extrem unsymmetrisch, - parasitäre Schwingungen mit zusätzlichen min/max Punkten kommen hinzu. - Ich habe so den 25.000-fachen Überschwinger erzeugt!

Wer also glaubt, zur Steuerung von Robotern und CNC Systemen könne man "ein paar Eckpunkte" einfach per Spline-Interpolation verbinden, kann Überraschungen erleben!

Aus all dem geht hervor:

•Der Kubische Spline ist eine stetig fortschreitende Kurve, sie kann stetige Verän-derungen recht gut interpolieren, Sprung-Funktionen provozieren hingegen star-kes Überschwingen. •Der Kubische Spline kann nicht geschlossen werden. Um die Verwirrung etwas voran zutreiben, kann man natürlich mit einem, nein zwei Kubischen-Splines schon etwas kreisförmiges bewirken. Ähnlich wie die ste-tig fortschreitende sin/cos Überlagerung in der klassischen CNC einen Kreis plot-tet, können stetig fortschreitende Splines aus der Überlagerung natürlich eben-falls "das Werkzeug zurückführen".

Die Spline-Mathematik schaut bei jeder Interpolation des Kurvenverlaufes nach links und rechts, also wo die Kurve herkommt (vorheriger Stützpunkt) und wo sie hin soll, wenn der Stützpunkt verlassen wird (nächster Stützpunkt). Im mittleren Kurverbe-reich ist dies unproblematisch, für die Start- und Endpunkte schon – denn es gibt keine Stützpunkte außerhalb der Kurve.

Natürlicher Splin

Per Definition stellt "natürlich" einen Spline dar, der außerhalb seines mathematisch definierten Kurverbereiches gradlinig verläuft – ob dies bei einer echten Kurve natür-lich ist, sei dahingestellt. Für die Robotik ist dies optimal, verbindet ein natürlicher Spline doch Geraden miteinander "ohne Knick".

Als Pendent zu den Natürlichen Splines mit linearem Verlauf außerhalb der Kurve werden Splines definiert, die an Stelle des linearen Verlaufes "glauben", in eine Pa-rabel überzugehen.

Noch mal zum mittleren Kurvenbereich: Hier schaut der Spline nach links und rechts, das ist nicht unproblematisch: Denn die Änderung eines einzelnen Spline Stützpunk-tes hat globale Auswirkungen auf die Kurve weit über andere Stützpunktbereiche hinaus.

B-Spline

Anders verhalten sich die B-Splines, hier hat die Änderung eines Stützpunktes kaum globale Auswirkung, sondern schwerpunktmäßig lokalen Einfluß auf die Kurvenform. Allerdings geht der B-Spline im mittleren Bereich nicht mehr durch die Stützpunkte, sondern an ihnen vorbei. Die Kurve wird von den Stützpunkten "gewichtet beein-flußt", lediglich Start- und Zielpunkt des B-Spliens liegt auf der jeweiligen Stützstelle.

Anders als der Kubische Spline kann der B-Spline zu einer geschlossenen Kurve geformt werden; bei einem Kreis ähnlichen B-Spline liegen die mittleren Stützstellen außerhalb der Kurve – aber in deren Nähe!

Constrained Cubic Spline

Ist ein Spline, der nicht überschwingt! Der "gebändigte" Spline kommt der Straklatte recht nahe. Per Definition spannen jeweils 2 benachbarte Knotenpunkte ein Rechteck parallel zur xy-Achse und begren-zen, "bändigen" den Spline. •Stetige Kurven laufen "diagonal weich" durch die Rechtecke, ohne die Begren-zung zu berühren. •Sprung-Funktionen "schlagen an", manchmal wirkt er im Knotenbereich etwas "eckig".

In unserem Trapezbeispiel läuft der Constrained Spline bei x-Achsen paralleler Aus-richtung horizontal als Gerade, die Schrägen werden verrundet. Dreht man die sym-metrische Trapez-Kurve im Koordinatensystem, so ergibt sich ein unsymmetrischer, ggf. eckiger Spline.

Überschwingen, was ist das?

Vielleicht mehr philosophisch: Auch Überschwingen ist eine Frage der Definition und des Meßaufbaus.

Nehmen wir einen ganz normalen Kreis im xy-Koordinatensystem. •Fallen die Mittelpunkte von Kreis und Koordinatensystem zusammen, so wird kein Mensch auf die Idee des Überschwingens kommen. •Legen wir den Kreis so, daß er x- und y- Achse tangiert, so werden wir die Punkte im Bereich von 0 bis 90 Grad, 90 bis 180 etc. ebenfalls nicht als überschwingend erachten. Liegen die zu verbindenden Punkte bei 0 und 180 Grad, so kann man vortrefflich streiten, ob es sich um einen Überschwinger gegenüber der doch par-allel zur x-Achse laufenden Sehne handelt!

Die Spline-Inflation

Während in der Mitte des letzten Jahrhunderts einigen Wissenschaftlern gewiß die Grundlagen der Spline-Mathematik bekannt waren (Schönberg soll hieran bereits 1945 geforscht haben), gab es hierfür zunächst keine Anwendung; Impulse setzte die Automobil und Flugzeugindustrie in den 1960-igern. Nunmehr überschlagen sich die Entwicklungen mit dem "Nachnamen" Spline; Hermitischer Spline / Catmull-Rom Spline / Cardinal Spline / Kochanek-Bartels Spline etc.

Mehr oder minder sind diese Splines miteinander verwandt, gemeinsam ist ihnen, daß eine Einflußmöglichkeit auf die Kurvenform zwischen den Knotenpunkten be-steht. Ein Überschwingen wie beim "Natürlichen, kubischen Spline" oder Anschlagen wie beim "Constrained Spline" ist so vermeidbar. Die Problematik der Kurvenform-Änderung in Abhängigkeit der relativen Lage im Koordinatensystem (vgl. "Denk-Experiment") besteht nicht.

Urvater dieser Spline-Familie ist der Hermitische Spline, genannt nach Charles Her-mite - der ihn aber nicht kannte! Zwei französische Mathematiker müssen wohl als Pionier der angewandten Mathematik gesehen werden; die Spline-Inflation folgte und ist leichter zu verstehen, wenn wir uns zunächst dieser Pionierarbeit zuwenden:

Bézier- und Casteljau

Recht ähnlich in ihrem Aussehen – in ihrem Verhalten jedoch völlig anders als "Na-türliche, kubische Splines" – sind Bézier- und Casteljau-Kurven. Beide Herren haben in den frühen 60igern des vorigen Jahrhunderts von einander (vermutlich) unabhän-gig – weil für die Konkurrenzfirmen Citroen und Renault tätig, eine deckungsgleiche Kurve entwickelt. Bézier suchte den Ansatz in der numerischen Mathematik mit Computern der späten 50iger (bitte mal in Erinnerung rufen; es gab keine Computer-Grafik, sondern IBM-Kettendrucker & Co; was der Mann leistete ist phänomenal; so entwickelte er eigens eins der ersten CAD Systeme, UNISURF).

Casteljau suchte den Ansatz in der darstellenden Geometrie und technischen Me-chanik. Seine Lösung baut auf Getriebelehre auf. Vorteil dieser Lösung: Modelle / Werkzeuge konnten - ohne Umweg über eine Zeichnung - direkt "aus dem Vollen geschnitzt" werden (auch CNC-Fräsen waren noch nicht erfunden).

Ob nun Bézier oder Casteljau: Die Kurve und ihre Konstruktion kann man (nachdem man's weiß) verhältnismäßig leicht nachempfinden:

Man nehme: 2 stabile (unverwindbare) Tragschienen, am Ende jeder Tragschiene niete man eine (nicht allzu steife) Straklatte an. Und zwar so, daß die Straklatte an der Tragschiene parallel zurück läuft – und das bei beiden Tragschienen. Die Trag-schienen sind also Tangente. Im Ergebnis sieht dies wie der Buchstabe "M" aus, wo-bei die Mitte des "M" nicht spitz zuläuft, sondern sich U-förmig formt - weil die Straklatte das so will !!!

Verschiebt man jetzt die beiden Tragschienen winklig oder parallel gegeneinander, so formt sich die Straklatte.

Bei den echten Bézier Kurven kommt hinzu, daß der Abstand der "Niet-Punkte" so-wie die Länge der Tragschienen Einfluß auf die Länge der Kurve haben. Da dies so ist, wird bei Bézier und Casteljau die Kurve nie außerhalb des durch die 4 Punkte gebildeten Gevierts liegen, - wird auf dieses Geviert bezogen nie überschwingen!

Unterschieden werden Bézier- und Casteljau-Kurven 1ten, 2ten und höheren Grades.

Die Kurve 1ten Grades

ist eine Gerade mit 2 Kontrollpunkten (wie jede andere Gerade auch).

Die Kurve 2ten Grades

(quadratische Bézier-Kurve)

hat 3 Kontrollpunkte. Man kann sich das so vorstellen, daß unsere beiden Trag-schienen in deren freiem Ende auf einen Punkt fallen. Anders ausgedrückt: Sie formen einen offenen Winkel und die darin eingespannte Straklatte eine Parabel. Der Scheitelpunkt jeder Bézier Kurve 2ten Grades liegt auf halber Lot-Höhe des äußeren Kontrollpunktes zu der die beiden anderen Punkte verbindenden Sehne.

Die Kurve 3ten Grades

(kubische Bézier-Kurve)

arbeitet mit 4 Kontrollpunkten und hat wohl die wesentliche Bedeutung. 2 Kontrollpunkte liegen auf der Kurve (Anfang / Ende), die beiden anderen bestimmen die Kurvenform (dies ist unser Tragschienen-Beispiel).

Das eigentliche Ergebnis, die Form liegt innerhalb dieser 4 Kontrollpunkte, - aber das Ergebnis ist meist eher zufällig, wenngleich exakt reproduzierbar, - schließen läßt sich die Kurve 3ten Grades nicht! Der Scheitelpunkt einer Bézier Kurve 3ten Grades liegt auf 3/4 Höhe der äußeren Kontrollpunkte, so beide die selbe Lot-Höhe zur Sehne haben. Bei unterschiedli-cher Höhe wächst die Scheitelpunkt-Höhe auf max. 88,9% der beiden arithme-tisch gemittelten Lot-Höhen.

Kubische Bézier-Kurve

Nennen wir die Kontrollpunkte auf der einen Tragschiene 0 und 1, die auf der ande-ren 2 und 3 (die Straklatte sei zwischen 0 und 3 angenietet). Bewegen wir 0 und 3 aufeinander zu, 1 und 2 voneinander fort, so lassen sich schöne , hufeisenähnliche asymmetrische "Freiformen" erzeugen, solange die Punkte 0 bis 3 nicht auf einer Geraden liegen. Ist dies der Fall, so wird auch die Freiform zur Geraden!

Vollständig schließen läßt sich eine einzelne Bézier Kurve 3ten Grades noch nicht, jedoch können mehrere Kurven (zu einem Bézier-Spline) cascadiert werden. Der Punkt 0 der folgenden Kurve fällt dann auf den Punkt 3 des Vorgängers, die Punkte 2 und 1 bilden eine gemeinsame Tangenten-Gerade. Die beiden Bézier Abschnitte lassen sich dann zu zwei hufeisenähnlichen Halbkreisen schließen.

Wesentlicher Unterschied: Beim B-Spline liegen die mittleren Stützpunkte in der Nä-he der Kurve, bei Bézier- und Casteljau-Kurven gibt es per Definition keine Stütz-punkte, sondern Kontrollpunkte. Zwei dieser Kontrollpunkte (0 und 3) können als Stützstelle erachtet werden, die beiden anderen (1 und 2) liegen bei Bézier- Kurven (auch denen höherer Ordnung) völlig außerhalb der Kurve.

Der im deutschen gebräuchliche Begriff "Kontrollpunkt" geht wohl auf eine Fehlüber-setzung zurück. Die englische Begrifflichkeit "control" steht eher für steuern als für kontrollieren. "Steuerpunkt" wäre wohl besser gewesen. Etwas anschaulich werden die Punkte 1 und 2 auch als "Handgriff" bezeichnet. Es bedarf einiger Übung, mit diesen Handgriffen / Steuerpunkten die gewünschte Kurve zu erzeugen.

Wechselt die Position 2 und 3 gegenseitig (die Tragschiene wird umgedreht), so ent-steht eine S-förmige Bézier- bzw. Casteljau- Kurve.

Es mag eine gewisse Tragik sein, daß Paul de Faget de Casteljau die Kurve und deren Konstruktion einige Jahre vor Pierre Bézier entdeckte. Citroen hielt die Ent-deckung lange, sehr lange geheim, Bézier durfte eher veröffentlichen – die Kurve trägt seinen Namen.

Einen exzellenten Zusammenhang zeigt http://en.wikipedia.org/wiki/B%C3%A9zier_curve

In der von Bézier entwickelten Mathematik wird die Kurve mit zwei Stützpunkten und 2 Steuerpunkten vollständig beschrieben. Die Genialität Pierre Béziers greift dabei auf das Bernsteinpolynom zurück, das Sergei Natanovich Bernstein 1911 entdeckte.

Vom Ansatz multipliziert Bézier "die xy-Koordinaten seiner 4 Kontrollpunkte" mit den 4 Grafen des Bernsteinpolynoms 3ten Grades "matrixförmig" und addiert die jeweils 4 Produkte je Kurvenpunkt zu dessen X bzw. Y Wert. Die Berechnung erfolgt para-metriert von t = 0 bis t =1, wobei diese extrem-Werte zugleich die Tangenten-Vektoren der Handgriffe repräsentieren.

•Das hört sich kompliziert an und ist es auch; hilfreich zum Verständnis ist die Excel® Studie (s.u.). Vieles von dem, was ich hier schreibe habe ich mit dieser Studie erarbeitet!

Das Geniale ist, das die einmal berechneten Bernsteinpolynome als Festwert-Tabelle (ähnlich der Logarithmentafel) hinterlegt werden können und die eigentliche Kurven-Berechnung sich auf simple Multiplikation und Addition beschränkt. Was naturgemäß wenig Rechenaufwand erfordert.

Noch einmal:

Bézier- & Casteljau-Kurven sind schön –wie die Autos der 50iger und 60iger-, sie können Punkt-symmetrisch, Achsen-symmetrisch oder unsymmetrisch sein. Zwei Geraden verbinden sie wunderbar, einen oder mehrere dazwischen liegende Punkte interpolieren sie hingegen eher zufällig; es sei denn, man cascadiert.

Auch hier gilt:

Die sich aus der Cascadierung ergebende Kurve selbst, also ihre Funktion sowie de-ren 1te und 2te Ableitung müssen an den Knotenpunkten (t = 0 bzw. t =1) stetig sein, um den "weichen Übergang" zu gewährleisten.

•Die 1. Ableitung

gekennzeichnet durch: F-Strich f ' gibt die Änderung des Funktionswertes an, d.h. die Steigung des Funktionsgra-phen an einer bestimmten Stelle (Knotenpunkt).

•Die 2. Ableitung

gekennzeichnet durch F-Doppel-Strich f gibt die Änderung der Steigung an. Sie gibt also Auskunft über die Krümmung des Graphen.

Zur 2. Ableitung eine tragische Berühmtheit: Die Todesspirale, Looping-Attraktion großer Achterbahnen zum Anfang des vorigen Jahrhunderts. Eine schräg abfal-lende Gerade geht in einen tangentialen Kreis mit Überschlag über und steigt da-nach in einer schrägen Gerade wieder an. Obwohl Gerade und Kreis tangential ineinander übergehen, kam es zu Genickbrüchen!

Die Geschwindigkeit wird durch die Steigung des Graphen beschrieben, die Be-schleunigung durch deren Änderung (2. Ableitung) und diese ist bei Übergang von Gerade in Kreis schlagartig - will heißen unendlich!

Moderne Achterbahnen-Konstruktionen beachten dies und werden als Spline be-rechnet.

Bézier und die Handgriffe

Es gibt eine Vielzahl von Applets zu diesem Thema im Internet. Man kann die Hand-griffe / Anfasser mit der Maus verschieben und sich freuen; verstanden habe ich die Mechanik, will sagen, Mathematik mit diesen Applets nicht. Hilfreich war hingegen eine Arbeit von Klaus Kühnlein, auf deren Basis ich eine Experimental-Studie entwik-kelt habe.

Excel® Studie Bézier-Cascade & Hermite Sie finden die Studie im Download-Bereich meiner Web-Site.

Um Bézier & Hermite zu untersuchen werden in einem Excel® Sheet diverse Kurven sowie ihre Ableitungen berechnet. Die Anfasser werden jedoch nicht mit der Maus verschoben, sondern deren Position per Schieber reproduzierbar eingestellt – nicht als xy-Koordinate, sondern ähnlich einer Polarkoordinate nach Betrag und Winkel. Der Anfasser kann also um P0 bzw. P3 kreisen ohne seine Länge zu ändern oder seine Länge ändern ohne den Winkel zu ändern. Im xy-Koordinaten System wäre dies schwierig.

Die Studie (vgl. Teil 2) untersucht für Bezier die Nachbildung eines Kreissegmentes sowie einen Spline aus 3 Bézier- bzw. Hermite Kurven. Diese sind "koppelbar" oder auch nicht. Sie können hiermit die wildesten Splines erzeugen.

Bahnkurve & Ableitungen Die im Hauptdiagramm gezeigte Kurvenform wird in CNC- und Robotersystemen letztendlich aus mehreren Achsen, im einfachsten Fall der x- und y-Achse erzeugt. Die Studie zeigt zur weiteren Analyse daher das Weg-Zeit Diagramm nach x- und y Achse, die beiden anderen Diagramme die jeweilige Achsengeschwindigkeit und de-ren Beschleunigung/Verzögerung – also die erste und zweite Ableitung.

Für Bezier macht die Studie deutlich:

Der Winkel des Anfassers bestimmt den Winkel, mit dem die Bézier-Kurve den Punkt P0 bzw. P3 trifft, die Länge des Anfassers bestimmt die Krümmung. Je länger der Anfasser, je länger schmiegt sich die Kurve an ihn an, je bauchiger wird sie – und die Länge bietet noch eine Überraschung! Und diese bezieht sich unter CNC und Robo-ter-Gesichtspunkten nicht auf die Form der Bahnkurve, sondern deren Dynamik!

Ergänzend untersucht die Excel-Studie Hermite im Vergleich zu Bézier. Wesentliche Erkenntnis: Bezier und Hermite können gegenseitig ineinander abgebildet werden. Vorteil: Die Bezier-Anfasser sind kürzer und in ihrer Wirkung besser vorhersehbar.

Zunächst die Bézier Betrachtungen, danach Erkenntnisse zu Hermite.

Vieles hiervon ist theoretisch, abstrakt. Die Studie gibt Erkenntnisse aus der Praxis für die Praxis, Sie finden die Excel® "Studie Bézier-Cascade & Hermite" im Downlo-ad-Bereich meiner Web-Site "studieren Sie mit"!

Bézier und der Kreisbogen

Einigkeit besteht in den Veröffentlichungen, daß man mit Bézier einen Viertel-Kreis recht gut approximieren könne. Angegeben und auch bewiesen wird ein Faktor

Der Radius eines Kreises multipliziert mit diesem Faktor, (meist "Kappa" genannt) ergibt die Länge des Anfassers; um eine Ellipse zu bilden wird die Länge der beiden Halb-Achsen jeweils als Radius gesetzt.

Beim 90-Grad Kreissegment weicht die Bézier-Kurve mit diesem Näherungs-Wert im 1/10 Promillebereich "nach außen" ab. Diese hervorragende Näherung ist sogar noch zu verbessern, wenn sich die Kurve von "innen und außen" an das Kreissegment anschmiegt.

Zu anderen Winkeln war meine Recherche ergebnislos; mit o.g. Experimental-Studie habe ich Näherungen für Tangentenwinkel im Bereich 0 bis 180 Grad ermittelt. Defi-niert ist der Tangentenöffnungswinkel als der, der einen Kreis tangential von außen berührt, (der Winkel des korrespondierenden Kreissegmentes ergibt sich aus "180 - Tangentenöffnungswinkel). Die Faktoren für die Stützstellen 0 bis 180 Grad wurden im 30er Raster iterativ genähert, die Zwischenwerte im 1,8 Grad Raster aus dem arithmetischem Mittel von kubischem- und constrained Spline interpoliert.

Die angegebenen Näherungs-Faktoren liegen im Bereich "0" (für einen Tangenten-öffnungswinkel von 180 Grad, das ist ein Punkt) bis ca. "1,32" für einen Tangenten-öffnungswinkel von 0-Grad (die Tangenten liegen dann parallel) - wegen des Nähe-rungsfehlers jedoch nur bedingt verwendbar.

Der Näherungsfehler "Bézier zu Kreis"

liegt für Tangentenöffnungswinkel zwischen 180 bis 90 Grad im 1/10 Promillebereich, im Bereich 60 bis 30 Grad im einstelligen Promillebereich, danach nimmt er deutlich bis in den Prozentbereich zu!

In der Studie sind Radiusschwankung und Näherungsfehler nach Mittelwert, min/max sowie Standardabweichung ausgewiesen. Der Näherungsalgorithmus bewertet die Anschmiegung als geometrisches Mittel aus Ziel-Radius und Standardabweichung. Im Ergebnis touchiert die Bézier-Kurve das Kreissegment durchgängig von 0 bis 180 Grad "innen und außen". Für das 90-Grad Kreissegment ermittelt die Studie einen Kappa-Faktor von 0.551784859. Dies verbessert (zumindest rein rechnerisch) die mit dem Klassiker ohnehin schon hervorragende Näherung.

Die Analyse macht deutlich: Die "richtige" Näherung gibt es nicht, da die Werte nicht korrelieren. Je nach Wichtung führt der Algorithmus zu Ergebnissen, die sich ab der 4ten Kommastelle unterscheiden. Der Näherungsalgorithmus wichtet (empirisch ermittelt) unter Berücksichtigung des Öffnungswinkels.

Kurven 4-ten und höheren Grades

ermöglichen extrem komplexe & elegante Formgebung. Das mit 5 und mehr Kontrollpunkten erreichbare Ergebnis ist (ohne PC-Grafik) kaum intuitiv vorherzubestimmen. Bézier- Kurven 4ten Grades lassen sich bereits schließen.

Der Hermitische Spline

unterscheidet sich bereits auf den ersten Blick in den Anfassern. Bei Hermite startet die Kurve wie bei Bézier von Kontrollpunkt 0 in Richtung 1, jedoch liegt der Kontroll-punkt 2 in der gedachten Verlängerung der Kurve (bei Bézier hatten wir diesen Ziel-Punkt P3 genannt). Auf den zweiten Blick wird man feststellen, daß die Kurve ge-genüber Bézier "weitgehend" außerhalb des Kontrollpunkt-Gevierts liegt.

Hermite reagiert auf die Bewegung der Anfasser deutlich komplexer. Während der Start-Anfasser zu einer recht Bézier ähnlichen Verformung führt, stellt der Ziel-Anfasser alle Erwartungen auf den Kopf: Zieht man ihn (bei unverändertem Winkel), so weicht die Kurve entgegen der Zug-Richtung nach hinten aus. Meist nimmt sie eine "S-förmige" Kontur an. Der Anfasser ist Flucht-Tangente im Ziel-Punkt.

Der Hermitische Spline läßt sich wie Bézier ebenfalls cascadieren. Um die Glattheit im Knotenpunkt zu garantieren ist per Definition der Start-Anfasser der Folge-Stufe gleich dem Ziel-Anfasser der Vor-Stufe. Bewegt man also diesen Kombi-Anfasser, so reagiert das Ganze recht eigenwillig und unvorhersehbar - mit Kanten, Schlingen und Schleifen. Auffällig ist, daß gegenüber Bézier wesentlich längere Anfasser erforder-lich werden, um die Kurve zu formen. Oftmals liegen sie weit außerhalb der eigentli-chen Kurve – und außerhalb des Bildschirmes! All dies macht die (interaktive) Hand-habung des Hermitischen Splines deutlich ungelenker als Bézier.

Die Hermite-Mathematik

ist der von Bézier ähnlich. 4 Anfasser werden mit 4 Polynomen parametrisch für 0<=t<=1 multipliziert. Dem in der Studie verwendeten Algorithmus beider Kurven (Bézier / Hermite) liegt dementsprechend der gleiche Matritzen-Ansatz zu Grunde; Excel® stellt hierfür die mächtige Formel "Summenprodukt" zur Verfügung. Es liegt nun nahe, einfach die Matrix des Bernstein-Polynoms gegen die Matrix des Hermite-Polynoms zu tauschen. Nur, so einfach ist das nicht!

•Das Bernstein-Polynom addiert für alle Parametrierungen 0<=t<=1 zu jeweils 1; •beim Hermite-Polynom gilt dies nur für die Parametrierungen t = 0 / t = 0,5 / t = 1. Die Summe steigt in der Mitte der ersten Hälfte über 1 sie fällt in der 2. Hälfte un-ter 1. Dies führt zu einer Verzerrung der Kurvenform in Abhängigkeit ihrer xy-Koordinaten: Was nahe dem Koordinaten Nullpunkt noch glatt ist, wirft Schleifen je weiter es sich vom Nullpunkt entfernt; verantwortlich hierfür sind die Matritzen-produkte aus den Anfasserkoordinaten.

Die Lösung:

Werden die Anfasserkoordinaten "1 zu 1" aus Bézier übernommen, so ergibt sich der beschriebene Fehler. Bei Hermite bezieht sich der Koordinatenwert der An-fasser nicht (wie bei Bézier) auf den Nullpunkt, sondern ihren Offset zum eignen Tangentenpunkt. Von der Absolut-Koordinate des Anfassers ist also die Koordi-nate seines Tangentenpunktes (P0 bzw. P3) abzuziehen. Mit dieser Modifikation der Kontrollpunkte errechnet sich die Kurve wie zu erwarten aus der Matrizen-Multiplikation von Hermite-Polynom & Hermite-Kontrollpunkten. Aus gleichen Koordinaten erzeugen Bézier und Hermite völlig unterschiedliche Kur-ven, da ist es gewiß erstaunlich, daß mit Bernstein eine zu Hermite deckungsgleiche Kurve gebildet werden kann. Die Endpunkte der Kurve sind identisch, die Anfasser stehen in einer schlichten Beziehung:

Um Hermite-Kurven mit Bézier zu erzeugen verkürzen sich die Anfasser auf 1/3. Für den Start-Anfasser wird dieses Drittel zum Start-Punkt addiert, für den Ziel-Anfasser vom Ziel-Punkt subtrahiert – wie man in einigen Veröffentlichungen liest.

Man erhält den bereits bekannten Fehler deckungsgleich: Verzerrung der Kurven-form in Abhängigkeit ihrer xy-Koordinaten. Auch hier gilt: Das Drittel bezieht sich nicht auf den XY-Absolutwert der Anfasserkoordinaten, sondern ihre relative Posi-tion zum eigenen Tangentenpunkt.

Wesentliche Erkenntnis: Bezier und Hermite können gegenseitig ineinander abgebil-det werden. Vorteil: Die Bezier-Anfasser sind kürzer, die Ziel-Anfasser in ihrer Wir-kung besser vorhersehbar. Bei der Kascadierung geht dieser Vorteil verloren.

•In der Studie kann zum Kurvenvergleich zwischen beiden Algorithmen umge-schaltet werden; lediglich die Anfasser unterscheiden sich! Der Vollständigkeit halber besteht die Möglichkeit eine "echte" Bézier-Kurve aus denselben Kontrollpunkten zu bilden. In allen 3 Analysen bleiben die Schieber-werte konstant, die Grafik zeigt die transformierten Anfasser entsprechend ihrer Wirkung.

Hermite-Variante Der Vollständigkeit halber – im Moment ohne erkennbaren Vorteil – hier ein Lösungs¬ansatz für eine recht Hermite-ähnliche Kurve:

Der weiter oben beschriebene Fehler führte in eine Verzerrung der Kurvenform in Abhängigkeit ihrer xy-Koordinaten. Dividiert man die so erhaltenen, fehlerhaften xy-Koordinaten durch den parametrierten Summenwert aller 4 Hermite-Polynome für 0<=t<=1, so kompensiert dies die Verzerrung. Interessanter Weise gilt dies für die Berechnungen mit Bernstein- und Hermite-Polynom gleichermaßen, beide Kurven sind deckungsgleich.

Qualitativ ähneln diese Kurven den "echten", sind hiermit jedoch nicht deckungs-gleich. Erhebliche Unterschiede zeigt ein Vergleich der Ableitungen.

Catmull-Rom Spline / Cardinal Spline / Kochanek-Bartels Spline etc.

gehen auf den Hermitischen Spline zurück. Die Namensgeber entwickelten Algorith-men, den Winkel und die Länge der Anfasser zu berechnen, um markante Kontroll-punkte per Cascadierung automatisch zu interpolieren. Der Bogen schließt sich zum Kubischen Spline, der genau dies tut.

Teil 2

Excel® Studie Bézier-Cascade & Hermite

Es empfiehlt sich zuvor / begleitend Teil 1 dieses Tutorials durchzuarbeiten. Hier, in Teil 2 finden Sie einige "Bedien-Hinweise" zur Studie - und die Auflösung der Bézier- Überraschung! •Diese Studie ist kein professionelles Programm; sie dient lediglich dazu, ma-thematische Zusammenhänge und deren Einfluß und Abhängigkeit in Hinblick auf "Roboter-Mathematik" sowie mathematische Ansätze zur Interpolation ei-ner Bahnkurve aus Stützstellen zu untersuchen. Es gibt eine Vielzahl von Möglichkeiten Kurven zu gestallten – nicht alle sind dokumentiert! Die Mög-lichkeit der freien Parameterwahl über Schieber und Werteingabe wird ergänzt durch mehrere Makrofamilien.

•Im Sinne einer Studie sind die verwendeten Formeln nicht gegen Fehleinga-ben geschützt; verwenden Sie für Ihre Experimente eine Kopie. Die Studie ist getestet, wird aber ohne jegliche Gewährleistung für irgendwelche Fehler "so wie sie ist" veröffentlicht. Ansprüche jeglicher Art aus der Nutzung sind ausge-schlossen.

•Die Experimental-Studie untersucht die Bézier- Nachbildung eines Kreisseg-mentes sowie jeweils einen Spline aus 3 Bézier- bzw. 3 Hermite Segmenten. Diese sind "koppelbar" oder auch nicht. Die eingestellten Schieberwerte wer-den nach Winkel und Betrag angezeigt.

Hier zunächst die Bézier Betrachtungen. Um die Bézier Mechanik zu untersuchen werden in einem Excel® Sheet Kurven so-wie ihre Ableitungen berechnet. Die Anfasser werden jedoch nicht mit der Maus ver-schoben, sondern deren Position per Schieber reproduzierbar eingestellt – nicht als xy-Koordinate, sondern ähnlich einer Polarkoordinate nach Betrag und Winkel. Die Schieberwerte werden nach Betrag und Winkel angezeigt, alternativ sind die Werte direkt eingebbar. Der Anfasser kann also um P0 bzw. P3 kreisen ohne seine Länge zu ändern oder seine Länge ändern ohne den Winkel zu ändern. Im xy-Koordinaten System wäre dies schwierig.

Die Studie macht deutlich: Der Winkel des Anfassers bestimmt den Winkel, mit dem die Bézier-Kurve den Punkt P0 bzw. P3 trifft, die Länge des Anfassers bestimmt die Krümmung. Je länger der Anfasser, je länger schmiegt sich die Kurve an ihn an, je bauchiger wird sie – und die Länge bietet noch eine Überraschung!

Bézier-Kreissegment

Zur Theorie s. Teil 1 dieses Tutorials. Mit dem Makro "Winkel_tang…" wird für beispielhaft hinterlegte Winkel iterativ eine Kappa-Näherung errechnet. Im rechten Bildschirmbereich befindet sich eine "Kappa-Tabelle" für weitere Tangenten-Winkel in feinerer Auflösung, Bézier-cascadiert ver-wendet diese Tabelle.

Bézier-cascadiert

Sie können aus 2 Makro-Familen kombinieren oder rein manuell untersuchen.

Makro "Copy_..."

Beispielhaft sind Koordinaten mehrerer unterschiedlicher Punkt-Konstellationen (Quadrat/Trapez/Winkel) für die 3 cascadierbaren Bezier-Kurven hinterlegt. Das Ma-kro kopiert deren Koordinaten in den aktiven Bereich.

Makro "Auto_Spline_..."

Parallel hierzu läuft im Hintergrund ein Algorithmus, der für 4 unterschiedliche "An-fasser-Philosophien" mögliche Schieberwerte errechnet. Die Anfasser-Werte dieser 4 Philosophien werden unter den aktiven Schieberwerten angezeigt und per Makro "Auto_Spline_..." aktiviert.

•Tangenten-Ellipse & Tangenten-Oval die beiden äußeren Bézier-Kurven bilden jeweils eine Gerade – bestimmt durch deren Punkte P0/P3; die mittlere Bézier Kurve formt sich "kreisähnlich" und läuft in die Geraden tangential ein:

Beträgt der Öffnungswinkel 90 Grad und liegen die beiden Tangenten-Endpunkte gleichweit vom theoretischen Schnittpunkt entfernt, so bildet sich bei beiden Vari-anten ein deckungsgleiches, nahezu exaktes Kreisbogensegment.

Liegen die Geraden unsymmetrisch, so wird an Stelle des Kreisbogens eine Ellip-se bzw. ein Oval gebildet; das Ergebnis wird durch die Länge der Anfasser be-stimmt (vgl. Bézier und der Kreisbogen). Bei der Ellipse wird der Radius aus dem Schnittpunkt der beiden Tangentenlote im Knotenpunkt, beim Oval aus den bei-den Schnittpunkten mit dem Mittelpunktslot der Sehne errechnet.

•Kurve1 Die Punkte P0 und P3 jedes Anfassers bilden mit ihren beiden Nachbarpunkten je ein Dreieck, das in einen äußeren Kreis eingeschlossen ist. Der Winkel des An-fassers steht senkrecht auf der Geraden, die "seinen" Punkt mit dem Mittelpunkt "seines" Kreises verbindet. Im Diagramm sind diese Mittelpunkte markiert. Die Länge der Anfasser errechnet sich aus dem Öffnungswinkel der Kreissegmente.

•Kurve2 Für jeden Punkt P0/P3 werden die beiden Nachbarpunkte jeweils mit einer Sehne verbunden. Der Winkel des Anfassers entspricht dem der Sehne im Koordinaten-system, er liegt also der Sehne parallel. Die Länge errechnet sich (recht komplex) aus einem Netzwerk der gewichteten Sehnen.

•Für die Kurven 1&2 ist im Bereich der "Anfasser-Berechnung" ein "Bauch-Faktor" wählbar, der per Makro "Auto_Spline_...." aktiviert wird.

Das Makro "Auto_Spline_...." überträgt lediglich die errechneten Schieberwerte in den "Parameter"-Bereich; ggf. werden Schlingen & Schleifen durch 180 Grad Kom-pensation der Anfasser entwirrt. Es wird so möglich, die errechneten Werte per MausClick mit den Schiebern manuell zu modifizieren.

Übung: •Wählen Sie für die Anfasser der Start- und Endpunkte (Kurven 1&2) manuell die Flucht- und Einlaufwinkel, mit denen der Punkt getroffen werden soll. •Kopieren Sie "Quadrat" und rufen Sie nacheinander "TangenteOval / Kurve1" auf. Verstellen Sie den Richtungssschieber A1.1 auf 90, den Schieber A3.2 auf 360 Grad. Ein ¾ Kreis erscheint.

Bézier Ableitungen

Die im Hauptdiagramm gezeigte Kurvenform wird in CNC- und Robotersystemen letztendlich aus mehreren Achsen, im einfachsten Fall der x- und y-Achse erzeugt. Die Studie zeigt zur weiteren Analyse daher das Weg-Zeit Diagramm nach x- und y Achse, die beiden anderen Diagramme die jeweilige Achsengeschwindigkeit und de-ren Beschleunigung/Verzögerung – also die erste und zweite Ableitung.

Die Ableitungen werden nicht als Differentialquotient, sondern als Differenzenquo-tient ermittelt. Dieser vereinfachte Ansatz wird möglich, da die Kurve über die Poly-nome parametriert für t = 0 bis t = 1 errechnet wird; diese t-Parameter können als Zeitraster aufgefaßt werden. Das Zeitraster ist konstant, es muß daher nicht einmal dividiert werden: Die Differenz der Nachbarn ergibt bereits die Ableitung nach Delta t! Für t = 1 ist die Differenzbildung etwas "tricky", um senkrechte Sprünge im Diagram besser darzustellen.

Weg-Zeit Diagramm der xy-Achsen

Betrachten wir den soeben erstellten ¾ Kreis: Klassisch wäre er auf die Überlage-rung von Sinus und Cosinus zurückzuführen. Die Ableitung des sin bringt cos, die Ableitung des cos bringt sin. Nicht aber hier!

Das Weg-Zeit Diagramm ist zwar sin/cos-ähnlich; die erste Ableitung zeigt jedoch bereits, daß die Geschwindigkeit alles andere als sinus-förmig zu- bzw. abnimmt, die zweite Ableitung offenbart die ganze Wahrheit: Die Ableitung einer Parabel führt letztendlich in eine Gerade!

Während bei einer kontinuierlich durchfahrenen Kreisbahn die Winkelgeschwindigkeit konstant ist, verändert sich die Bahn-Geschwindigkeit zwischen P0/P3. Sie liegt bei einer Standardabweichung von knapp 2% in Start- und End-Punkt der 90 Grad Seg-mente etwa 7% über der Geschwindigkeit im mittleren Kurvenbereich.

Die Bézier Überraschung

• Die Länge der Anfasser beeinflußt also nicht nur die Form der Kurve, sondern unter CNC und Roboter Gesichtspunkten auch die Bahn-Geschwindigkeit, mit der die Kurve durchfahren wird!

Werden beide Anfasser eines Knotenpunktes gleich lang, so werden die Ge-schwindigkeiten mit der der Knotenpunkt erreicht und wieder verlassen wird ebenfalls gleich, die Änderung der Beschleunigung / Verzögerung, der "Ruck" wird minimiert.

Auffällig ist ebenfalls, daß als Bezier Kurve erzeugte Geraden im Weg-Zeit Dia-gramm nicht unbedingt als Gerade erscheinen. Verändern Sie die Länge der An-fasser für die Geraden: Die Gerade selbst verändert sich hierbei nicht, wohl aber Ihre Weg-Zeit -Funktion, sie verläuft bogenförmig, manchmal als S-Bogen – also mit unterschiedlicher Geschwindigkeit. Dieser Bogen formt sich zur Geraden, wenn die Längenwerte beider Anfasser zu exakt 1/3 des Abstandes von P0/P3 werden. Die Bahn-Geschwindigkeit ist dann kontinuierlich.

Werden die Anfasser zu 0, so werden P0/P3 mit 10 % der max-Geschwindigkeit des mittleren Kurvenbereiches angefahren, liegen die Anfasser auf den Gegen-punkten so fällt die Geschwindigkeit in der Mitte der Geraden auf nahezu 0, die Geschwindigkeit im Start und Endpunkt steigt zum Ausgleich extrem.

Bezier und Hermite

Aufbau und Bedienung der Hermite-Studie ähneln der beschriebenen Bézier Studie • In der Studie kann zum Kurvenvergleich zwischen beiden Algorithmen umge-schaltet werden; lediglich die Anfasser unterscheiden sich! Der Vollständigkeit halber besteht die Möglichkeit eine "echte" Bézier-Kurve aus denselben Kontrollpunkten zu bilden. In allen 3 Analysen bleiben die Schieber-werte konstant, die Grafik zeigt die transformierten Anfasser entsprechend ihrer Wirkung.

Hinweis

Die Schieber können Werte erzeugen, deren Koordinaten außerhalb des Diagramms liegen. Ein Excel®-Diagramm paßt sich standardmäßig den max-Koordinaten an. Diese Funktion ist abgeschaltet, da eine permanente Maßstab Veränderung ausge-sprochen störend ist. Mit den Buttons "AutoScala/AutoScala linear" wird der Maßstab gezielt aktualisiert.