Darstellung von Splines

14/06/2013 - 09:10 von Hans-Peter Diettrich | Report spam
Ein Bekannter möchte eine stückweise durch parametrierte kubische
Splines definierte Kurve zeichnen (lassen). Er hat also für jeden Abschnitt:
x(t)=at^3+bt^2+ct+d
y(t) entsprechend

Wie làßt sich das effizient in ein Polygon (oder Punktefolge) umwandeln?

Gibt es dafür ein Verfahren à la Bresenham, d.h. unter Verwendung einer
(oder 2) Fehlerfunktion(en)?

Bislang ist mir nur folgendes eingefallen:

Die Anfangs- und Endkoordinaten der Segmente sind bekannt, lassen sich
in ganzzahlige (Pixel)Koordinaten umrechnen. Ggf. können die Segmente
weiter unterteilt werden, um Überschwinger zu eliminieren, so daß jede
Teilkurve vollstàndig in einem Rechteck (zwischen Anfangs- zum Endpunkt)
liegt - entsprechend Bresenham für Kreis-Oktanten. Auch kann davon
ausgegangen werden, daß die Stützstellen (Meßpunkte) in X (Zeit) und Y
(Meßwert) monoton sind, so daß Überschwinger in den Segmenten eigentlich
nicht auftreten dürfen, jedoch als Artefakte der Umwandlung in Splines
nicht ganz auszuschließen sind.

Aber wie bekomme ich brauchbare Werte für t?

Ist es vielleicht zielführender, t durch Interpolation/Extrapolation zu
variieren, bis sich zwischen zwei Werten eine Abweichung von max. 1
Pixel ergibt?

DoDi
 

Lesen sie die antworten

#1 Christian Gollwitzer
15/06/2013 - 09:51 | Warnen spam
Hallo Hans-Peter,

Am 14.06.13 09:10, schrieb Hans-Peter Diettrich:
Ein Bekannter möchte eine stückweise durch parametrierte kubische
Splines definierte Kurve zeichnen (lassen). Er hat also für jeden
Abschnitt:
x(t)=at^3+bt^2+ct+d
y(t) entsprechend



Hat er sie wirklich in dieser Form gegeben? Oder hat er sie dahin
ausmultipliziert?

Üblicherweise werden in der Computergrafik nàmlich eher Bezier-Splines
benutzt, also eine Darstellung in Form der Bernstein-Polynome. Das sind
die Koeffizenten, die man aus der binomischen Formel für (t+(1-t)^n
erhàlt. Siehe z.B.

http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Der große Vorteil davon ist die geometrische Bedeutung der Koeffizenten:
Die Kurve geht für t aus (0..1) vom ersten zum letzten Punkt, die
Tangenten an den Stützpunkten sind die Verbindungslinien zu den inneren
Kontrollpunkten.

Die Konvertierung aus Deinem Polynom in Standardbasis sollte durch eine
simple Matrixinversion möglich sein.

Wie làßt sich das effizient in ein Polygon (oder Punktefolge) umwandeln?



De-Casteljau-Algorithmus (aus Bezier-Spline)

Gibt es dafür ein Verfahren à la Bresenham, d.h. unter Verwendung einer
(oder 2) Fehlerfunktion(en)?



Keine Ahnung. Ich weiß auch nicht, wie das heute in Grafikbibliotheken
üblicherweise gemacht wird, der Fachbegriff zum Googlen heißt
"Rasterization".

Abgesehen davon: Wenn es nur ums Zeichnen geht, dann sollte man
versuchen, die Kurve in kubische Bezier-Splines zu konvertieren. Die
kann man nàmlich in jede halbwegs aktuelle Grafikschnittstelle direkt
eingeben und erhàlt die bestmögliche Darstellung inklusive Antialiasing.
PostScript enthàlt etwa curveto, PDF den "c" Operator, SVG das
"C"-Element in der Pfadbeschreibung, und auch die APIs für Windows etc.
haben Bezierbefehle.

Christian

Ähnliche fragen