Bezier-Kurven berechnen

[Phoenix]

Tja, ich sitz in einer Spassigen Vorlesung namens Computergrafik, und dort haben wir theoretisch mal Bezier-Kurven angesprochen.

Pierre Bézier beschreibt die nach ihm benannte Kurve mit folgender kubischen Formel:

X(u) = x0 * (1-u)hoch3 + x1 * 3 * u * (1-u)hoch2 + x2 * 3 * u hoch2 (1-u) + x3 * u hoch3

Y(u) = y0 * (1-u)hoch3 + y1 * 3 * u * (1-u)hoch2 + y2 * 3 * u hoch2 (1-u) + y3 * u hoch3

Dabei sind (x0,y0): Startpunkt; (x1,y1), (x2,y2): zwei Bezier-Kontrollpunkte (BCP's) ausserhalb der Kurve; und (x3,y3): Endpunkt der Kurve. Der Wert 0<=u<=1 ist der Parameter der Darstellung und wird entlang der Kurve ständig etwas erhöht.

Nun meine Frage: Wie groß muss ich die Schritte für u wählen, damit ich für einen bestimmten Pixelabstand zwischen x0 und y0 eine möglichst genaue Kurve erhalte?

Bzw. gibt es da eine Faustformel um diese Schrittweite optimal zu ermitteln?

[kalmi01]

Zitat:

Der Wert 0<=u<=1 ist der Parameter der Darstellung und wird entlang der Kurve ständig etwas erhöht.

Nun meine Frage: Wie groß muss ich die Schritte für u wählen, damit ich für einen bestimmten Pixelabstand zwischen x0 und y0 eine möglichst genaue Kurve erhalte?

Nach meiner Erfahrung sollte man 0.01 nehmen.
Viel mehr als 100 Schritte vermittelt das (trügerische) Gefühl von "mehr Genauigkeit", was sich in der Realität aber nicht belegen lässt.
Am auffälligsten ist dies bei Kreissegmenten, weshalb Adobe (und Andere) in den diversen Postscript-Treibern mächtig rum-Rundet und Glättet.

[Flocke]

Du kannst das ganze auch Rekursiv nach De Casteljau lösen und Teilsegmente als Linien zeichnen, sobald Anfangs- und Endpunkt nahe genug beieinander liegen.

Hintergrund: man kann mit relativ simpler Mathematik ein kubisches Spline in der Mitte (t=0,5) zerlegen und auch gleich noch die neuen Stützpunkte berechnen, so dass man dann zwei kleinere Teilkurven erhält.

// Nachtrag

Etwas ausführlicher.

Gehen wir davon aus, du hast die Punkte A0, B0, C0 und D0. A0 ist der Startpunkt, D0 der Endpunkt und B0/C0 sind die Stützpunkte.

Du möchtest die Kurve bei t aus ]0, 1[ zerlegen (0 entspricht A0, 1 entspricht D0).

Schritt 1: Teile die Strecken (A0 B0), (B0 C0) und (C0 D0) jeweils bei t.
A1 = (1-t) A0 + t B0
B1 = (1-t) B0 + t C0
C1 = (1-t) C0 + t D0

Schritt 2: Teile diese neuen Strecken (A1 B1) und (B1 C1) wiederum bei t.
A2 = (1-t) A1 + t B1
B2 = (1-t) B1 + t C1

Schritt 3: Teile die Strecke (A2 B2) noch einmal bei t.
A3 = (1-t) A2 + t B2

Ergebnis:
Den Pfad (A0 B0 C0 D0) kannst du jetzt zerlegen in die beiden Teilpfade (A0 A1 A2 A3) und (A3 B2 C1 D0).

[Khabarakh]

Ich würde ebenfalls zu De Casteljau raten, den ich auch hier eingesetzt habe (sogar ebenfalls C# :zwinker: ). Dessen Teilungsverfahren könntest du aber auch mit der Parameterfunktion selbst nachbauen:
Man wähle t = 0,5 und halbiere diesen Wert [1], bis der errechnete Punkt nah genug am Anfangspunkt liegt. Dann wird die Strecke gezeichnet und der nächste Teilabschnitt errechnet.

[1] Hier gäbe es wahrscheinlich noch Raum zur Optimierung, beispielsweise könnte man statt 0,5 den erwarteten Wert für eine lineare Bézierkurve wählen. Ist die Strecke zwischen Anfangs- und Endpunkt also 50 Pixel lang und es sollen maximal 5 Pixel-lange Linien gezeichnet werden, werde ich t = 0,1 wählen. Das kann zuviel oder zu wenig geschätzt sein, aber wohl immer noch besser als 0,5.

[dizzy]

Um mal auf die eigentliche Frage einzugehen: WIr haben (ebefalls in unserer aktuellen CG Vorlesung :)) auch nicht über optimale Schrittweiten gesprochen. Jedoch kam mir grad eine Idee, wie man u.U. etwas brauchbares herausbekommt.

Nimm die Pixelkoordinaten deiner Stützpunkte, und berechne die Gesamtlänge L des Polygonzugs. 1/L könnte dann für das Segment eine durchaus brauchbare Lösung sein, zumindest aber ein Ausgangswert der sich an einer Näherung der tatsächlichen Länge orientiert. Genau Pixelabstand wird man jedoch nicht, bzw. nicht trivial oder gar performant hinbekommen, da die Punktverteilung bei gleichschrittigem Erhöhen von t nicht linear ist. Ums Strecken Zeichnen wirst also nicht herum kommen ;)


Edit: Ich habe vorhin nochmal meinen Prof dazu befragt. Er gab bei o.g. Methode noch zu bedenken, dass das Vorgehen keineswegs optimal ist, und zwar dahingehend, dass auch wenn eine Teilstrecke der Kurve nicht stark gekrümmt ist, trotzdem mit hoher Auflösung die Punkte berechnet werden, obwohl für einen guten Bildeindruck weniger nötig wären. Auf der anderen Seite kann es noch passieren, dass zu starke Krümmungen zu kantig erscheinen, wobei das bei 1/L eher selten der Fall sein dürfte, da die Punkte damit schon sehr dicht werden.

Eine Möglichkeit der Optimierung wäre also nun, indem man ein Verfahren findet, dass die Krümmung der Kurve wiedergibt. U.U. lässt sich da mit numerischen Näherungsverfahren zur Ableitungsbildung was erreichen, aber konkrete Quellen habe ich da leider nicht parat. Zudem ist dann die Frage, ob es nicht performanter wäre, einfach ein paar Punkte zu viel zu zeichnen :D. (Je nach Anwendungsfall.)