Schnelles Berechnen von kubischen Bezierkurven

[Senior Sanchez]

Hallo,

ich möchte gerne eine kubische Bezierkurve berechnen. Die Kontrollpunkte sind alle bekannt und die Konstruktion der Kurve klappt auch.

Die Schwierigkeit ist nun, dass ich die Kurve nicht über ihren normalen Parameter t, der quasi den relativen Abstand der aktuellen Position auf der Kurve zum Kurvenanfang beschreibt, berechnen möchte. Stattdessen möchte ich die Kurve gerne als Funktion interpretieren und suche daher für gegebene Parameter x die passenden y-Werte.

Derzeit mache ich das so, dass ich die Kurve mit einer hohen Auflösung des Parameters t sample, damit dann x und y-Koordinaten berechne und anschließend über meine gegebenen x-Werte iteriere und die gesampleten Punkte der Kurve finde, die am nächsten zu diesen x-Werten liegen. Erhöhe ich die Auflösung des Parameters t, umso exakter wird meine Kurve beschrieben, d.h. die Zuordnung der gegebenen x-Werte zur Kurve funktioniert besser. Aber das macht es natürlich auch langsam.

Gibt es einen Weg, das ganze zu beschleunigen? Der oftmals zitierte De Casteljau-Algorithmus ist da glaube ich nicht der richtige Weg, da durch die vielen Rekursionen das ganze nicht schneller sein sollte.

[rudl]

schon mal den chaikin algorithm ausprobiert?

[Senior Sanchez]

schon mal den chaikin algorithm ausprobiert?

Hab ich noch nie von gehört, aber ich habe mal nachgeschaut.

So wie ich das sehe, ist das ja eine eigene Kurvendefinition, wobei gezeigt wurde, dass das zu quadratischen B-Splines äquivalent sein soll. Aber das hilft mir ja nicht weiter für eine kubische Bezierkurve. Zudem sehe ich das Problem, dass dieser sehr ähnlich zum De Casteljau Algorithmus ist und somit auch sehr stark auf Rekursionen setzt. Ich müsste dort dann wahrscheinlich auch wieder eine gewisse Rekursionstiefe erreichen, um eine gewisse Güte zu erreichen. Und das ganze wiederhole ich dann für jeden Punkt. Ich bin mir unsicher, ob das wirklich schneller ist als mein Überabtasten.

[rudl]

dann gibts noch "lane riesenfeld" die sollte kubisch sein

[Senior Sanchez]

Hmm, ich weiß nicht. Das ist wieder so eine rekursive Geschichte.

Hast du den schon mal ausprobiert?

[Spasstiger]

Ich würde mal stark davon ausgehen, dass die rekursiven Algorithmen bei gleicher Genauigkeit schneller sind als dein Bruteforce-Ansatz, sonst würden diese Algorithmen nicht so oft zitiert werden. Probier es doch einfach aus für verschiedene Bezierkurven und einen Satz von Referenzpunkten, welcher Algorithmus im Mittel am Schnellsten ist. Die Abbruchbedingung kannst du ja für den "Benchmark" über eine gewünschte Genauigkeit festlegen, wenn du vorher die Referenzpunkte berechnet hast.
Du kannst als Abbruchbedingung auch festlegen, dass von einem Rekursionsschritt zum nächsten die Änderung kleiner als ein bestimmter Wert ist.

Deinen Ansatz kannst du natürlich auch effizienter gestalten. Z.B. fängst du an mit t=0, t=0,5 und t=1. Dann schaust du, für welches t dein x am Besten approximiert wird und rechnest um dieses t herum mit einer kleineren Schrittweite weiter.
Z.B. ergibt sich im ersten Schritt t=0,5, dann berechnest du t=0,25 und t=0,75 und überprüfst wieder dein x. Wenn sowohl t=0,25 als auch t=0,75 dein x besser approximieren als t=0,5, musst du einen neuen Rechenzweig aufspannen und beide Zweige getrennt berechnen. Für jeden neuen Zweig speicherst du das t und den Schritt, damit du in der nächsten Iteration mit der passenden kleineren Schrittweite weiterrechnen kannst. Jeden Zweig berechnest du solange bis die Änderung von x klein genug ist.

Wieviele verschiedene y kann es eigentlich für ein x bei einer kubischen Bezierkurve geben? Zwei oder drei?

[Senior Sanchez]

Da hast du natürlich Recht.

Wobei ich das bisher so verstanden habe, dass man De Casteljau eigentlich hauptsächlich einsetzt, um eine Kurve durch Linearisierung überhaupt zeichnen zu können. Das der besonders schnell sein soll, habe ich glaube ich noch nicht gelesen.

[Spasstiger]

Ja, ich hab mir den De Casteljau gerade auch angeschaut und festgestellt, dass er dein Problem nicht 100% abbildet. Deshalb noch mein Posting um einen Alternativ-Vorschlag ergänzt.

[Senior Sanchez]

Deinen Ansatz kannst du natürlich auch effizienter gestalten. Z.B. fängst du an mit t=0, t=0,5 und t=1. Dann schaust du, für welches t dein x am Besten approximiert wird und rechnest um dieses t herum mit einer kleineren Schrittweite weiter.
Z.B. ergibt sich im ersten Schritt t=0,5, dann berechnest du t=0,25 und t=0,75 und überprüfst wieder dein x. Wenn sowohl t=0,25 als auch t=0,75 dein x besser approximieren als t=0,5, musst du einen neuen Rechenzweig aufspannen und beide Zweige getrennt berechnen. Für jeden neuen Zweig speicherst du das t und den Schritt, damit du in der nächsten Iteration mit der passenden kleineren Schrittweite weiterrechnen kannst. Jeden Zweig berechnest du solange bis die Änderung von x klein genug ist.

Wieviele verschiedene y kann es eigentlich für ein x bei einer kubischen Bezierkurve geben? Zwei oder drei?

An die Variante habe ich auch schon mal gedacht. Es geht ja schon etwas in Richtung Nullstellenberechnung, wobei es mich auch an den Douglas-Peucker-Algorithmus erinnert. Ich muss das wohl mal ausprobieren.

Also da eine Bezierkurve ja nicht auf dem X/Y-Raum definiert wird, sondern über t muss eine Bezierkurve keine Funktion im X/Y-Raum sein. Sie kann ja auch Schleifen drehen. Gehen wir von unendlicher Genauigkeit aus, müsste eine kubische Bezierkurve glaube ich maximal zwei y-Werte für einen x-Wert haben können. Aber ich weiß das jetzt nicht mit Sicherheit. Für mein Problem dagegen könnte es durchaus vorkommen (wenn ich es mit der Abtastfrequenz übertreibe), dass es pro x-Wert noch mehr y-Werte gibt, was daran liegt, dass man eigentlich unterschiedliche x-Werte aufgrund der Gleitkommaungenauigkeit nicht mehr voneinander unterscheiden kann.

Ich habe übrigens schon versucht, als Alternative, mal x und y durch t zu beschreiben, was ja durch ein Umstellen der Gleichung zur Berechnung der Bezierkurve machbar ist. Mathematica hat mir dabei aber so lange Terme ausgespuckt, dass ich die praktisch nicht einsetzen kann. :D

[Spasstiger]

Ich habe übrigens schon versucht, als Alternative, mal x und y durch t zu beschreiben, was ja durch ein Umstellen der Gleichung zur Berechnung der Bezierkurve machbar ist. Mathematica hat mir dabei aber so lange Terme ausgespuckt, dass ich die praktisch nicht einsetzen kann. :D
Das hab ich jetzt auch mal getestet und es klappt imo relativ gut.
Wenn die Stützpunkte definiert sind als
P_0 = (x_0, y_0), P_1 = (x_1, y_1), P_2 = (x_2, y_2) und P_3 = (x_3, y_3),
dann sind die möglichen y zu jedem Punkt x reellle Lösungen der drei folgenden Funktionen:


y_a(x) = y_0 - ((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) + ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) - ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3))^3*(y_0 - 3*y_1 + 3*y_2 - y_3) - (3*y_0 - 3*y_1)*((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) + ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) - ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)) + ((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) + ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) - ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3))^2*(3*y_0 - 6*y_1 + 3*y_2);


y_b(x) = y_0 - (y_0 - 3*y_1 + 3*y_2 - y_3)*((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)/2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/(2*((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)) - (3^(1/2)*(((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3))*i)/2)^3 - (3*y_0 - 3*y_1)*((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)/2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/(2*((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)) - (3^(1/2)*(((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3))*i)/2) + (3*y_0 - 6*y_1 + 3*y_2)*((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)/2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/(2*((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)) - (3^(1/2)*(((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3))*i)/2)^2


y_c(x) = y_0 - (y_0 - 3*y_1 + 3*y_2 - y_3)*((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)/2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/(2*((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)) + (3^(1/2)*(((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3))*i)/2)^3 - (3*y_0 - 3*y_1)*((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)/2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/(2*((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)) + (3^(1/2)*(((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3))*i)/2) + (3*y_0 - 6*y_1 + 3*y_2)*((3*x_0 - 6*x_1 + 3*x_2)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)/2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/(2*((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3)) + (3^(1/2)*(((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3) + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))/((((x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) + ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^2 + ((3*x_0 - 3*x_1)/(3*(x_0 - 3*x_1 + 3*x_2 - x_3)) - (3*x_0 - 6*x_1 + 3*x_2)^2/(9*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^3)^(1/2) + (3*x_0 - 6*x_1 + 3*x_2)^3/(27*(x_0 - 3*x_1 + 3*x_2 - x_3)^3) - (x - x_0)/(2*(x_0 - 3*x_1 + 3*x_2 - x_3)) - ((3*x_0 - 3*x_1)*(3*x_0 - 6*x_1 + 3*x_2))/(6*(x_0 - 3*x_1 + 3*x_2 - x_3)^2))^(1/3))*i)/2)^2

Problematisch ist die Rechengenauigkeit, weil sich zumindest mit Matlab komplexe Lösungen auch dort ergeben, wo man reelle Lösungen erwartet. Die Kurve nimmt natürlich nur reelle Lösungen an. Deshalb hab ich einen Schwellwert für den Imaginärteil definiert (Betrag des Imaginärteils < 1e-10), um die gültigen Lösungen zu filtern.
So sieht das dann beispielsweise aus:

http://www.forum-3dcenter.org/vbulletin/attachment.php?attachmentid=46343&stc=1&d=1375631641 http://www.forum-3dcenter.org/vbulletin/attachment.php?attachmentid=46344&stc=1&d=1375632498

Eventuell willst du dann auch noch den Lösungbereich auf den beschränken, in dem t zwischen 0 und 1 liegt.
Matlab erzeugt die obigen Graphen mit 1000 berechneten Punkten ohne merkliche Verzögerung auf einem Core i3-2310M. Ich weiß ja nicht, wieviele Punkte du in welcher Zeit berechnen willst, aber mir scheint der Lösungsweg schnell genug zu sein. Sind ja auch nur ein paar Additionen, Multiplikationen und Divisionen und am Schluss noch für jeden y-Wert eine Prüfung des Imaginärteils. Der große Vorteil ist, dass man eine exakte Lösung bekommt im Rahmen der Rechengenauigkeit.

[Senior Sanchez]

Wow, danke für deine Mühe!

Also vor den Termen schrecke ich etwas zurück. Das ist mir doch zu undurchsichtig.

Derzeitig braucht meine Implementierung auf einem Core i5 etwa 4,9 ms für die Berechnung einer Bezierkurve. Okay, stimmt nicht exakt. Ich arbeite hier gerade mit B-Splines aber die sind ja verwandt. 4,9 ms ist jedenfalls noch zu lang.

EDIT: Achja, 3.000 Punkte pro Kurve, Überabtastung mit Faktor 10. Also ich erzeuge 30.000 Punkte pro Kurve per gleichmäßigem Sampling.

[del_4901]

Rechnest du in Matrix Form? Da kannst du naemlich ganz viel wiederverwenden: http://and-what-happened.blogspot.se/2012/03/assorted-uniform-splines-in-matrix-form.html Fuer 30k Punkte lohnt es sich ja schon fast das auf die GPU hochzuladen, der HLSL code dafuer ist auch schoener.

[Spasstiger]

Wow, danke für deine Mühe!

Also vor den Termen schrecke ich etwas zurück. Das ist mir doch zu undurchsichtig.

Derzeitig braucht meine Implementierung auf einem Core i5 etwa 4,9 ms für die Berechnung einer Bezierkurve. Okay, stimmt nicht exakt. Ich arbeite hier gerade mit B-Splines aber die sind ja verwandt. 4,9 ms ist jedenfalls noch zu lang.

EDIT: Achja, 3.000 Punkte pro Kurve, Überabtastung mit Faktor 10. Also ich erzeuge 30.000 Punkte pro Kurve per gleichmäßigem Sampling.
Bei mir dauert es im Schnitt 0,7 ms in Matlab, um die y-Werte für ein einzelnes x zu berechnen.
Die Terme habe ich übrigens auch von Matlab berechnen lassen, mit der Symbolic Toolbox. Man muss die Terme halt komplexwertig lösen, sonst kommt man nicht weit. Bei gültigen Lösungen ist der Imaginärteil theoretisch null, aber da macht einem wie gesagt die begrenzte Rechengenauigkeit einen Strich durch die Rechnung, weshalb ich mit einem Schwellwert für den Imaginärteil arbeite.

[Senior Sanchez]

Rechnest du in Matrix Form? Da kannst du naemlich ganz viel wiederverwenden: http://and-what-happened.blogspot.se/2012/03/assorted-uniform-splines-in-matrix-form.html Fuer 30k Punkte lohnt es sich ja schon fast das auf die GPU hochzuladen, der HLSL code dafuer ist auch schoener.

Ist keine Option, da das in Zukunft mal auf einem Mikrocontroller laufen soll - und das auf etwas seeeehr einfachem. ;)

Bei mir dauert es im Schnitt 0,7 ms in Matlab, um die y-Werte für ein einzelnes x zu berechnen.
Die Terme habe ich übrigens auch von Matlab berechnen lassen, mit der Symbolic Toolbox. Man muss die Terme halt komplexwertig lösen, sonst kommt man nicht weit. Bei gültigen Lösungen ist der Imaginärteil theoretisch null, aber da macht einem wie gesagt die begrenzte Rechengenauigkeit einen Strich durch die Rechnung, weshalb ich mit einem Schwellwert für den Imaginärteil arbeite.

Also ist meine Variante schneller, weil ich eben in 4,9 ms für 3.000 x-Werte die Lösung finde.

[Spasstiger]

Wirklich 3000 x-Werte oder nur 3000 t-Werte?

[Senior Sanchez]

Wirklich 3000 x-Werte oder nur 3000 t-Werte?

3.000 x-Werte, 30.000 t-Werte.
Das ganze in Java, btw.

[del_4901]

Ist keine Option, da das in Zukunft mal auf einem Mikrocontroller laufen soll - und das auf etwas seeeehr einfachem. ;)
Wenn du mehrere Werte auf einmal brauchst ist Matrixform trozdem schneller, der code ist nur haesslicher.

[Senior Sanchez]

3.000 x-Werte, 30.000 t-Werte.
Das ganze in Java, btw.

Ich muss meine Aussage etwas revidieren.
Die 3.000 x-Werte sind häufig nicht durch eine Bezierkurve vollständig abgedeckt, sondern teilweise nur 1.200 Werte. Der Rest ist dann ein linearer Verlauf, der aber auch mit in die Zeitberechnung einging. Ich habe noch ein paar Testreihen gemacht und meine ursprüngliche Implementierung war dann bei etwa 5,5 ms im Durchschnitt.

Ich habe jetzt den Algorithmus etwas getunt, einige Schleifendurchläufe gespart und dadurch eine etwas andere Approximation erhalten (Abweichungen so ab der 7. Nachkommastelle - in meinem Fall verschmerzbar). Ich taste immer noch mit einem Faktor von 10 ab und bin jetzt bei etwa 4,2 ms für die gesamte Funktion mit ihren 3.000 x-Werten.

EDIT: Ich werde mal über meine ganzen Daten einen kleinen Benchmark machen. Mal schauen, wie lang es dauert. Damit habe ich dann verlässlichere Angaben für die Berechnungsdauer.

[Senior Sanchez]

So, ich habe noch mal durchgemessen.

Die ursprüngliche Version braucht 5,2 ms. Jetzt sind es 4,8 ms. Da die Ergebnisse auch leicht abweichen schaue ich jetzt, welche Variante da die besseren Ergebnisse liefert. Für nur 0,4 ms verzichte ich dann nicht auf die bessere Qualität.

[Spasstiger]

Kannst du den direkten Weg mit den Formel für y(x) nicht austesten? Matlab ist nicht gerade für Schnelligkeit bekannt, deshalb muss meine Referenzzeit von 0,7 ms pro x nichts bedeuten (zumal gemessen auf einem langsamen mobilen i3). Für was brauchst du das Zeug eigentlich auf einem Microcontroller, für Echtzeit-Bildverarbeitung im PKW o.ä.?

/EDIT: Auszug aus dem Matlab-Profiler:

http://abload.de/img/matlab7yucx.png

Sind ja 6,5 ms pro x-Wert, nicht rund 0,7 ms. :redface:
0,65 ms pro x-Wert. :up:

[Senior Sanchez]

Kannst du den direkten Weg mit den Formel für y(x) nicht austesten? Matlab ist nicht gerade für Schnelligkeit bekannt, deshalb muss meine Referenzzeit von 0,7 ms pro x nichts bedeuten (zumal gemessen auf einem langsamen mobilen i3). Für was brauchst du das Zeug eigentlich auf einem Microcontroller, für Echtzeit-Bildverarbeitung im PKW o.ä.?

Ich probiere erstmal noch eine Erweiterung, aber dann schaue ich mir vermutlich mal deine Variante mit der Formel an. Matlab basiert aber größtenteils auf Java und von daher gehe ich jetzt mal davon aus, dass die sich von der Performance her nicht so sehr unterscheiden. Ich habe übrigens auf einem mobilen i5-2520M gemessen, natürlich nur auf einem Kern.

Ich brauche es nicht für Echtzeit-Bildverarbeitung. ;) Ich benutze solche Kurven für eine andere Anwendung, wo man sie bisher nicht einsetzte. Es ist aber auch im Automobilbereich angesiedelt, aber zuviel darf ich noch nicht verraten.

EDIT: Woher weiß ich eigentlich, welches y der drei Lösungen das richtige ist?

[Spasstiger]

EDIT: Woher weiß ich eigentlich, welches y der drei Lösungen das richtige ist?
Es können alle drei y richtig sein, da die Kurve ja dritter Ordnung ist und sich somit für einen x-Wert bis zu drei y-Werte ergeben. Ein richtiges y hat nur einen Realteil, keinen Imaginärteil. Wegen der begrenzten Rechengenauigkeit gehen aber viele eigentliche Lösungen unter, wenn man so hart filtert. Ich hab in den Grafiken oben als Schwellwert für den Imaginärteil 1E-10 angesetzt. Wenn man einfach alle y nimmt und deren Realteil darstellt, kommt sowas Lustiges raus:

http://www.forum-3dcenter.org/vbulletin/attachment.php?attachmentid=46376&stc=1&d=1375797262

P.S.: Ich hab mich bei der Performance um eine Zehnerpotenz vertan, siehe das EDIT im vorigen Posting. ;)

[Senior Sanchez]

/EDIT: Auszug aus dem Matlab-Profiler:

http://abload.de/img/matlab7yucx.png

Sind ja 6,5 ms pro x-Wert, nicht rund 0,7 ms. :redface:

Also 65 Sekunden aka 65.000 Millisekunden bei 100.000 calls sind für mich immer noch 0,65 ms pro x-Wert. :uroll:

[Spasstiger]

Arg, das Wetter, dann noch sich mit nem Kollegen unterhalten und nebenher Ausarbeitung schreiben, da verknotet sich offenbar mein Gehirn. :freak:

[Senior Sanchez]

Ich geh gleich erstmal auf die Terrasse und probiere noch eine Idee aus. Mal schauen, was die bringt.

[Senior Sanchez]

Ich habe mal folgendes gemacht.
Ich habe alle meine Kurven genommen und die mal hochgenau abgetastet. Hier mit einem Faktor von 10.000, dass heißt wenn ich 3.000 Datenpunkte habe, tastet er die Kurve mit 30 Mio Punkten ab. Das ist meine Referenz.

Anschließend habe ich dann dieselben Kurven mal mit einer niedrigeren Abtastung gesampled und dabei sowohl die Berechnungsdauer als auch die Ähnlichkeit zur Referenz ausgegeben. Wie man sieht gewährleistet eigentlich schon Faktor 2 eine sehr hohe Ähnlichkeit, braucht dafür aber viel weniger Rechenzeit.

Auswertezeit (ms) der Referenzen (Faktor = 10000): 829948.551631 Durchschnittliche Zeit (ms): 4585.351113983425
Faktor: 500 Durchschnittliche Güte: 0.9999999999995342 Auswertezeit (ms): 41432.972191 Durchschnittliche Zeit (ms): 228.91144856906078
Faktor: 250 Durchschnittliche Güte: 0.9999999999981318 Auswertezeit (ms): 20654.010342 Durchschnittliche Zeit (ms): 114.11055437569061
Faktor: 200 Durchschnittliche Güte: 0.999999999997081 Auswertezeit (ms): 16323.227165 Durchschnittliche Zeit (ms): 90.18357549723757
Faktor: 150 Durchschnittliche Güte: 0.9999999999948049 Auswertezeit (ms): 12246.084771 Durchschnittliche Zeit (ms): 67.6579269116022
Faktor: 100 Durchschnittliche Güte: 0.9999999999883188 Auswertezeit (ms): 8167.149235 Durchschnittliche Zeit (ms): 45.122371464088395
Faktor: 50 Durchschnittliche Güte: 0.9999999999531725 Auswertezeit (ms): 4090.56023 Durchschnittliche Zeit (ms): 22.599780276243095
Faktor: 40 Durchschnittliche Güte: 0.9999999999268706 Auswertezeit (ms): 3547.598719 Durchschnittliche Zeit (ms): 19.599992922651936
Faktor: 30 Durchschnittliche Güte: 0.9999999998701322 Auswertezeit (ms): 2547.756775 Durchschnittliche Zeit (ms): 14.076004281767954
Faktor: 20 Durchschnittliche Güte: 0.9999999997074379 Auswertezeit (ms): 1654.408135 Durchschnittliche Zeit (ms): 9.140376436464088
Faktor: 10 Durchschnittliche Güte: 0.999999998831801 Auswertezeit (ms): 832.409452 Durchschnittliche Zeit (ms): 4.598947248618784
Faktor: 9 Durchschnittliche Güte: 0.9999999985540818 Auswertezeit (ms): 743.918246 Durchschnittliche Zeit (ms): 4.110045558011049
Faktor: 8 Durchschnittliche Güte: 0.99999999817346 Auswertezeit (ms): 703.584296 Durchschnittliche Zeit (ms): 3.887206055248619
Faktor: 7 Durchschnittliche Güte: 0.9999999976145122 Auswertezeit (ms): 636.575182 Durchschnittliche Zeit (ms): 3.516989955801105
Faktor: 6 Durchschnittliche Güte: 0.9999999967536959 Auswertezeit (ms): 516.527319 Durchschnittliche Zeit (ms): 2.8537420939226523
Faktor: 5 Durchschnittliche Güte: 0.9999999953196382 Auswertezeit (ms): 412.072237 Durchschnittliche Zeit (ms): 2.2766421933701655
Faktor: 4 Durchschnittliche Güte: 0.9999999927014301 Auswertezeit (ms): 331.885846 Durchschnittliche Zeit (ms): 1.833623458563536
Faktor: 3 Durchschnittliche Güte: 0.999999987007864 Auswertezeit (ms): 255.586241 Durchschnittliche Zeit (ms): 1.4120786795580111
Faktor: 2 Durchschnittliche Güte: 0.9999999707774264 Auswertezeit (ms): 171.590236 Durchschnittliche Zeit (ms): 0.9480123535911602
Faktor: 1 Durchschnittliche Güte: 0.9781537925528359 Auswertezeit (ms): 88.024043 Durchschnittliche Zeit (ms): 0.48632067955801106

[Spasstiger]

Was ist denn deine Güte? Der Korrelationskoeffizient?
Der Faktor 2 täuscht ein bischen darüber hinweg, dass du ja letztlich doch 6000 Punkte berechnen musst, um auf irgendein beliebiges x schließen zu können. Für die Berechnung eines einzelnen x musst du 6000-mal die Parameterformel (in Abhängigkeit von t) auswerten. Soviele Terme hat der direkte Rechenweg y(x) definitiv nicht. ;)

Was du vermutlich in deinem Vergleich auch nicht berücksichtigst ist, dass die Genauigkeit bei deinem Ansatz nicht für alle x gleich ist, sondern von der Krümmung der Kurve abhängt. Im Worst-Case-Fall kann der Näherungswert deutlich abweichen oder es werden Lösungen "übersprungen".

[Senior Sanchez]

Was ist denn deine Güte? Der Korrelationskoeffizient?

Die Güte basiert auf einer relativ komplexen Ähnlichkeitsfunktion (die stelle ich auch noch in einem Paper vor :D). Es ist grundsätzlich eine gewichtete Funktion mehrerer Gütekriterien und sie kann feinste Nuancen sehr genau auflösen, berücksichtigt aber auch die Charakteristik der Kurven.


Der Faktor 2 täuscht ein bischen darüber hinweg, dass du ja letztlich doch 6000 Punkte berechnen musst, um auf irgendein beliebiges x schließen zu können. Für die Berechnung eines einzelnen x musst du 6000-mal die Parameterformel (in Abhängigkeit von t) auswerten. Soviele Terme hat der direkte Rechenweg y(x) definitiv nicht. ;)

Ehm, nee, du hast das ganze falsch verstanden. :D
Ich habe hier meine Kurve beschrieben durch 8 Parameter - bei 2 Koordinaten pro Punkt ergibt das 4 Kontrollpunkte, die die Kurve definieren. Weiterhin habe ich meine x-Werte, für die ich die y-Werte auf der Kurve wissen will.

Nun mache ich folgendes: im Extremfall liegen 3.000 x-Werte auf der Kurve. Ich sample die Kurve in äquidistanten Schritten über den Parameter t, der ja zwischen 0 und 1 liegt. Die Schrittweite bestimme ich dabei durch 1/(3.000*Abtastungsfaktor). Wähle ich den Faktor hoch, erhalte ich sehr kleine Schrittweiten und t wird somit sehr hoch aufgelöst. Wähle ich den Faktor niedrig, erhalte ich kleinere Schrittweiten. Mit dem Faktor 2 erhalte ich somit 6000 Punkte für die ganze (!) Kurve, nicht pro x-Wert.


Was du vermutlich in deinem Vergleich auch nicht berücksichtigst ist, dass die Genauigkeit bei deinem Ansatz nicht für alle x gleich ist, sondern von der Krümmung der Kurve abhängt. Im Worst-Case-Fall kann der Näherungswert deutlich abweichen oder es werden Lösungen "übersprungen".

Aus diesem Grund nutze ich als Faktor auch nicht 2, sondern 4. Wie man anhand der gemittelten Güte über ~130 Kurven sieht, funktioniert das ausgezeichnet, spart aber einiges an Rechenzeit ein. Das heißt nicht, dass das immer so sein muss, aber die Kurven, die ich hier betrachte sind in dieser Hinsicht recht gutmütig.

[Spasstiger]

Ich hab dich schon richtig verstanden. Ich meinte den Fall, dass du nur einen x-Wert samplen möchtest. Dann bräuchtest du für die gleiche Güte wie bei den 3000 x-Samples mit Faktor 2 Überabtastung trotzdem 6000 t-Samples.

[Senior Sanchez]

Ich hab dich schon richtig verstanden. Ich meinte den Fall, dass du nur einen x-Wert samplen möchtest. Dann bräuchtest du für die gleiche Güte wie bei den 3000 x-Samples mit Faktor 2 Überabtastung trotzdem 6000 t-Samples.

Achso, jetzt weiß ich was du meinst.
Das kommt aber in meiner Anwendung nicht vor. Außerdem könnte man das über eine binäre Suche schneller machen. Dann brauch ich auch nicht 6.000 mal zu samplen.

[Senior Sanchez]

Spasstiger, mach dich bereit mit den Ohren zu schlackern! ;D

Ich habe ja mal oben erwähnt, dass ich derzeitig keine Bezierkurven sondern B-Splinekurven berechne. Im Grunde ist es dasselbe, außer das man anstatt eines Bernsteinpolynoms ein Basispolynom berechnet, was rekursiv definiert ist. Ich habe bisher immer so getan, als sei es quasi das selbe, denn so ein großer Unterschied in der Performance sollte das eigentlich nicht sein. Aber ich habe meinen Test von oben jetzt trotzdem mal mit Bezierkurven wiederholt.

Nach einem ersten Test erhielt ich dieses Ergebnis:
Auswertezeit (ms) der Referenzen (Faktor = 10000): 5039584.111987 Durchschnittliche Zeit (ms): 27843.00614357459
Faktor: 500 Durchschnittliche Güte: 0.9999999999994126 Auswertezeit (ms): 252454.467418 Durchschnittliche Zeit (ms): 1394.776063082873
Faktor: 250 Durchschnittliche Güte: 0.9999999999976436 Auswertezeit (ms): 125673.535892 Durchschnittliche Zeit (ms): 694.3289275801105
Faktor: 200 Durchschnittliche Güte: 0.9999999999963153 Auswertezeit (ms): 100412.957309 Durchschnittliche Zeit (ms): 554.7677199392266
Faktor: 150 Durchschnittliche Güte: 0.9999999999934476 Auswertezeit (ms): 75811.142078 Durchschnittliche Zeit (ms): 418.8460888287293
Faktor: 100 Durchschnittliche Güte: 0.9999999999852999 Auswertezeit (ms): 50538.424432 Durchschnittliche Zeit (ms): 279.21781454143644
Faktor: 50 Durchschnittliche Güte: 0.9999999999410935 Auswertezeit (ms): 25493.258645 Durchschnittliche Zeit (ms): 140.84673284530388
Faktor: 40 Durchschnittliche Güte: 0.9999999999079473 Auswertezeit (ms): 20080.318574 Durchschnittliche Zeit (ms): 110.9409865966851
Faktor: 30 Durchschnittliche Güte: 0.9999999998362853 Auswertezeit (ms): 15212.728818 Durchschnittliche Zeit (ms): 84.04822551381216
Faktor: 20 Durchschnittliche Güte: 0.9999999996326309 Auswertezeit (ms): 10072.479705 Durchschnittliche Zeit (ms): 55.649059143646404
Faktor: 10 Durchschnittliche Güte: 0.9999999985276872 Auswertezeit (ms): 5091.337335 Durchschnittliche Zeit (ms): 28.12893555248619
Faktor: 9 Durchschnittliche Güte: 0.9999999981843716 Auswertezeit (ms): 4768.429561 Durchschnittliche Zeit (ms): 26.34491470165746
Faktor: 8 Durchschnittliche Güte: 0.9999999977020524 Auswertezeit (ms): 4075.090619 Durchschnittliche Zeit (ms): 22.514312812154696
Faktor: 7 Durchschnittliche Güte: 0.9999999969936405 Auswertezeit (ms): 3546.376197 Durchschnittliche Zeit (ms): 19.593238657458564
Faktor: 6 Durchschnittliche Güte: 0.9999999959198499 Auswertezeit (ms): 3047.282828 Durchschnittliche Zeit (ms): 16.835816729281767
Faktor: 5 Durchschnittliche Güte: 0.9999999941260952 Auswertezeit (ms): 2561.080592 Durchschnittliche Zeit (ms): 14.149616530386739
Faktor: 4 Durchschnittliche Güte: 0.9999999908008945 Auswertezeit (ms): 2023.048216 Durchschnittliche Zeit (ms): 11.177061966850829
Faktor: 3 Durchschnittliche Güte: 0.9999999836050888 Auswertezeit (ms): 1513.813778 Durchschnittliche Zeit (ms): 8.36361203314917
Faktor: 2 Durchschnittliche Güte: 0.9953482750827576 Auswertezeit (ms): 1004.541165 Durchschnittliche Zeit (ms): 5.549951187845304
Faktor: 1 Durchschnittliche Güte: 0.8344876168773036 Auswertezeit (ms): 511.598211 Durchschnittliche Zeit (ms): 2.826509453038674

Ich dachte mir nur so: Häh? WTF? Warum dauert das so viel länger als die B-Splinekurven? Hat der Spasstiger da etwa doch eine sehr schnelle Lösung für ein schwieriges Problem gefunden? Meine Standardvariante mit 10-facher Überabtastung braucht da 28,13 ms pro Kurve, was 6-7 mal langsamer als die B-Splines ist. Und das obwohl die B-Splines auf rekursive Methodenaufrufe setzen, die eigentlich Rechenzeit kosten?!

Aufgrund dieser Ergebnisse habe ich mir mal die Berechnung des Bernsteinpolynoms angeschaut. Nun ja, ich hatte es programmiertechnisch elegant gemacht, indem ich das eigentliche Polynom in eine extra Methode ausgelagert habe und diese jeweils für die x- und die y-Koordinate eines Kurvenpunktes gecalled habe. Zudem habe ich Math.pow() eingesetzt, wo es dann aber irgendwo klingelte, dass das bei ganzzahligen Exponenten nicht gerade effizient ist.

Also habe ich folgende Änderungen vollzogen:
- Bernsteinpolynomberechnung direkt in die aufrufende Methode integriert
- Faktoren des Polynoms nur einmal berechnet, sodass ich für x- und y-Koordinaten bloß einfache Multiplikationen mit bereits berechneten Größen habe
- pow() durch ausgerollte Multiplikationen ersetzt
- Zudem habe ich noch ein paar Zwischenberechnungen manuell gecached, um ein paar Multiplikationen zu sparen

Ein kurzer Test ergab, dass die berechneten Kurven immer noch korrekt sind, sodass mir kein Fehler unterlaufen sein sollte. Also ging es ans Performance messen. Ich startete die Berechnung und ging Zähne putzen, weil er ja eine Weile rechnen würde. Ich komme wieder und sehe das:

Auswertezeit (ms) der Referenzen (Faktor = 10000): 110196.679547 Durchschnittliche Zeit (ms): 608.821433961326
Faktor: 500 Durchschnittliche Güte: 0.9999999999994126 Auswertezeit (ms): 5471.791341 Durchschnittliche Zeit (ms): 30.230891386740332
Faktor: 250 Durchschnittliche Güte: 0.9999999999976433 Auswertezeit (ms): 2697.765158 Durchschnittliche Zeit (ms): 14.90477987845304
Faktor: 200 Durchschnittliche Güte: 0.9999999999963154 Auswertezeit (ms): 2160.800956 Durchschnittliche Zeit (ms): 11.938126828729281
Faktor: 150 Durchschnittliche Güte: 0.9999999999934476 Auswertezeit (ms): 1623.471784 Durchschnittliche Zeit (ms): 8.969457370165745
Faktor: 100 Durchschnittliche Güte: 0.9999999999852999 Auswertezeit (ms): 1087.072448 Durchschnittliche Zeit (ms): 6.005925127071823
Faktor: 50 Durchschnittliche Güte: 0.9999999999410935 Auswertezeit (ms): 549.223159 Durchschnittliche Zeit (ms): 3.034382093922652
Faktor: 40 Durchschnittliche Güte: 0.9999999999079473 Auswertezeit (ms): 440.651379 Durchschnittliche Zeit (ms): 2.4345380055248618
Faktor: 30 Durchschnittliche Güte: 0.9999999998362854 Auswertezeit (ms): 331.193705 Durchschnittliche Zeit (ms): 1.8297994751381217
Faktor: 20 Durchschnittliche Güte: 0.9999999996326309 Auswertezeit (ms): 223.072693 Durchschnittliche Zeit (ms): 1.2324458176795579
Faktor: 10 Durchschnittliche Güte: 0.9999999985276872 Auswertezeit (ms): 115.375722 Durchschnittliche Zeit (ms): 0.6374349281767956
Faktor: 9 Durchschnittliche Güte: 0.9999999981843717 Auswertezeit (ms): 104.304017 Durchschnittliche Zeit (ms): 0.5762652872928177
Faktor: 8 Durchschnittliche Güte: 0.9999999977020524 Auswertezeit (ms): 93.162104 Durchschnittliche Zeit (ms): 0.5147077569060774
Faktor: 7 Durchschnittliche Güte: 0.9999999969936405 Auswertezeit (ms): 81.599818 Durchschnittliche Zeit (ms): 0.45082772375690605
Faktor: 6 Durchschnittliche Güte: 0.9999999959198499 Auswertezeit (ms): 71.582304 Durchschnittliche Zeit (ms): 0.39548234254143644
Faktor: 5 Durchschnittliche Güte: 0.9999999941260952 Auswertezeit (ms): 59.762634 Durchschnittliche Zeit (ms): 0.3301802983425414
Faktor: 4 Durchschnittliche Güte: 0.9999999908008945 Auswertezeit (ms): 48.734426 Durchschnittliche Zeit (ms): 0.2692509723756906
Faktor: 3 Durchschnittliche Güte: 0.9999999836050888 Auswertezeit (ms): 39.02276 Durchschnittliche Zeit (ms): 0.2155953591160221
Faktor: 2 Durchschnittliche Güte: 0.9953482750827576 Auswertezeit (ms): 27.861552 Durchschnittliche Zeit (ms): 0.15393122651933702
Faktor: 1 Durchschnittliche Güte: 0.8344876168773036 Auswertezeit (ms): 16.059528 Durchschnittliche Zeit (ms): 0.08872667403314917

:eek::eek::eek: :O :uwoot:
:ucatch::ucatch::ucatch:

Faktor 10 haut der jetzt in 0,64 ms pro Kurve durch. Mit Faktor 4, den ich auch für B-Splinekurven verwende, berechnet er die komplette Kurve in 0,269 ms!
Ich werd bekloppt!

[Spasstiger]

Respekt, mit meiner Lösung bin ich davon zeitlich um Größenordnungen entfernt! Interessant wäre noch die Güte bei meiner Lösung.

[Senior Sanchez]

Ich probiere deine Lösung die Tage mal aus. Gerade rechnet er etwas, wofür er die Kurven braucht und das dauert ein paar Stunden/Tage. ;)

Die Frage ist aber: was nehmen wir bei deiner Variante zur Ermittlung der Güte als Referenz? Wenn man es genau nimmt, müsste, sofern keine numerischen Ungenauigkeiten entstehen, deine Lösung ja die genaueste sein. Wenn wir die jetzt aber als Referenz nehmen sind die Güten ja nicht mehr vergleichbar. Vergleiche ich es dagegen mit der 10.000-fachen Abtastung ergeben sich vermutlich kleine Unterschiede - wir wissen dann aber noch nicht, welche Lösung genauer ist.

[Spasstiger]

Stimmt, ohne Referenz bringt der Vergleich nicht so viel. Ich weiß gar nicht, ob ich bisher mit doppelter Genauigkeit gerechnet habe, muss ich mal überprüfen.

[Senior Sanchez]

Wobei, mir fällt ein, dass ich eine Referenz habe. ;)

Die Bezier- und B-Spline-Kurven wurden über ein Curve Fitting erzeugt. Und die Originalkurve habe ich ja. Ich könnte diese also als Referenz nehmen! Das ich da nicht früher drauf gekommen bin. Wobei, das lag daran, dass ich den relativen Unterschied zwischen verschiedenen Abtastungen ermitteln wollte.