Kubische Interpolation, wie bekomme ich den Y-Wert?

Hallo mycsharp Community,
ich entwickle gerade einen eigenen KeyFrame Player.

Soweit wie ich das sehe ist damit auch alles in Ordnung, ALLERDINGS habe ich ein Problem mit der KeyFrame-Interpolation.

Lineare Interpolation ist einfach, ich habe aber Probleme mit der Kubischen Interpolation.
Da ich mir schwer getan habe, den Algorithmus für eine Kubische Bezier-Kurve zu schreiben, hakte ich im Internet nach und bin auf diese Code-Schnipsel gestossen:

private double X(double t, double x0, double x1, double x2, double x3) {
    return (x0 * Math.Pow((1 - t), 3) + x1 * 3 * t * Math.Pow((1 - t), 2) + x2 * 3 * Math.Pow(t, 2) * (1 - t) + x3 * Math.Pow(t, 3));
}
private double Y(double t, double y0, double y1, double y2, double y3) {
    return (y0 * Math.Pow((1 - t), 3) + y1 * 3 * t * Math.Pow((1 - t), 2) + y2 * 3 * Math.Pow(t, 2) * (1 - t) + y3 * Math.Pow(t, 3));
}
private void CalculateCurve(double dt, Point pt0, Point pt1, Point pt2, Point pt3) {
    for (double t = 0.0f; t < 1.0; t += dt)
        points.Add(new Point(X(t, pt0.X, pt1.X, pt2.X, pt3.X), Y(t, pt0.Y, pt1.Y, pt2.Y, pt3.Y))); 
    points.Add(new Point(X(1.0f, pt0.X, pt1.X, pt2.X, pt3.X), Y(1.0f, pt0.Y, pt1.Y, pt2.Y, pt3.Y)));
}

Den Rest dafür habe ich Prima hinbekommen.
Punkt 0: x: 0, y: Wert vom vorherigen KeyFrame bzw. Standardtwert (wenn davor kein KeyFrame war)

Punkt 1 und 2: Kontrollpunkte.

Punkt 3: x: Die totalen Frames die der KeyFrame interpoliert, y: Der Wert den der KeyFrame erreichen soll.

Gut, meine Applikation zeichnet es auch richtig auf, allerdings:
Wenn ich versuche für den Frame, der zwischen den Werten P0|X und P3|X liegt, den Y-Wert
zu bekommen, dann treffe ich auf das Problem dass mit meiner Funktion der Wert zu Grob ist:

public double GetYFromX(int frame) {
    for(int i=0; i<points.Count; i++) {
        if (points[i].X >= frame) return points[i].Y;
    }
    return points[points.Count - 1].Y;
}

Das Liegt warscheinlich daran, dass einige Frames nicht in der Liste vertreten sind und er so einfach den nächsten höheren Wert nimmt.
Dadurch sieht es natürlich so aus, als würde die Animation kurz steckenbleiben, weil er einfach für mehrer Frames den gleichen Wert nimmt.

Wie also bekomme ich Werte, welche für jeden einzelnen Frame steigen bzw. sinken (je nachdem ob der KeyFrame Endwert mehr oder weniger werden soll)!

Ich danke schon einmal für eure Hilfe! 😄

LG Rexozz ^^

Hi Rexozz,

das Problem mit Bezierkurven ist, daß sie sich nicht ohne weiteres nach einer X- oder Y-Koordinate auflösen lassen, sondern nur nach "t", also bezogen auf die Länge der Kurve. Das führt dann dazu, daß mit dt=0.2 eine Kurve mit einer Länge von 2 Keyframes genauso in 5 Punkte zerlegt wird, wie eine Kurve über 200 Keyframes.

Da hast meines Erachtens folgende Möglichkeiten:

• Du kannst die betreffenden Keyframes zwischen den berechnete Punkten linear interpolieren
• Du kannst dt so klein wählen, daß die Kurve auch mit Sicherheit mindestens einen Punkt pro Keyframe hat.
• Du kannst dt rekursiv verkleinern, solange nicht für jeden Keyframe eine Koordinate berechnet wird
• Es gibt auch Wege, t für eine bestimmte Koordinate berechnen zu lassen (google mal nach 5th degree bezier splines)

Hallo MrSparkle
folgendes:

Möglichkeit 1 habe ich schon selbst in Betracht gezogen, nur bekomme ich einfach nicht den Algorithmus in den Kopf.

Möglichkeit 2 hat bei mir des öfteren eine OutOfMemoryException ausgelößt, ist ja auch klar bei 1000 frames dass der computer nicht mehr mitkommt!

Möglichkeit 3 verstehe ich nicht ganz!

Möglichkeit 4 werde ich mir einmal genauer ansehen!

Außerdem, ist das mit t nicht so das t einfach die Menge der Punkte angibt in denen die Kurve gleichmäßig aufgeteilt wird?
Also z.B. dt = 0.01 = 100 Punkte?

Ich danke dir, ich werde mal nachsehen was ich so rausbekomme! ^^

EDIT:
Ich bezweifle zwar das es so einfach ist, aber würde es so funktionieren?

public double GetYFromX(int frame)
{
    return Y((1/totalFrames)*frame, p0.Y, p1.Y, p2.Y, p3.Y);
}

Linear geht das ganz sicher, aber Kurvenmäßig?
Immerhin braucht man ja die X-Werte um zu wissen wann Y anfängt zu steigen oder?

Möglichkeit 1 habe ich schon selbst in Betracht gezogen, nur bekomme ich einfach nicht den Algorithmus in den Kopf.

Ist nur ein einfacher Dreisatz 😃

Möglichkeit 3 verstehe ich nicht ganz!

Das würde bedeuten, du nimmst zuerst einen höheren Wert für dt, und verringerst ihn dann bei Bedarf, also nur dann, wenn für einen Keyframe kein Punkt erzeugt wurde.

Du kannst dafür De Casteljau's algorithm verwenden, hier ein Beispiel: Casteljau's algorithm - practical example, hier eine ausführliche Erklärung: Finding a Point on a Bézier Curve: De Casteljau's Algorithm und hier ein Video: Computing Bézier curves using de Casteljau's algorithm.

ist das mit t nicht so das t einfach die Menge der Punkte angibt in denen die Kurve gleichmäßig aufgeteilt wird?

t ist einfach nur ein Parameter, mit dem man einen Punkt auf einer Kurve festlegt. Er bezieht sich auf die Länge der Kurve (die tatsächliche Länge, nicht der Abstand zwischen den Endpunkten), und die Gesamtlänge einer Kurve ist immer genau 1.0. Der Startpunkt einer Kurve wird also mit t=0 angegeben, der Endpunkt mit t=1.0, und die Mitte der Kurve ist t=0.5.

Wenn du also die Koordinaten alle t=0.5 berechnest, dann bekommst du zwei Punkte auf der Kurve, mit t=0.01 100 Punkte, usw.

Zu deinem Edit:

Nein, das funktioniert eben nicht, da sich der erste Parameter der Y-Methode nicht auf die X-Koordinate bezieht, sondern auf t.

So ähnlich sollte das aussehen wenn ich es grafisch darstellen wollte! (Anhang)

Das ist nur eine Skizze, also warscheinlich etwas ungenau! Und nur eine Beispiel-Interpolation! ^^

Wahrscheinlich nicht der performativste weg, aber es funktioniert endlich:

public double GetValueFromFrame(uint frame)
        {
            if (frame > 0)
            {
                if (points.ContainsKey(frame))
                {
                    return points[frame];
                }
                else
                {
                    double minVal, maxVal;
                    double valIncr;
                    uint frames;
                    uint currFrame;
                    int lastFrame = -1;
                    int nextFrame;

                    for (uint i = frame; i > 0; --i)
                    {
                        if (points.ContainsKey(i))
                        {
                            lastFrame = points.GetItemIndex(i);
                            break;
                        }
                    }

                    if (lastFrame < 0)
                        lastFrame = 0;

                    if (lastFrame + 1 < points.Count)
                        nextFrame = lastFrame + 1;
                    else
                        nextFrame = points.Count - 1;

                    frames = points[nextFrame].Key - points[lastFrame].Key;
                    currFrame = frame - points[lastFrame].Key;

                    minVal = points[lastFrame].Value;
                    maxVal = points[nextFrame].Value;

                    valIncr = (maxVal - minVal) / frames;
                    return minVal + valIncr * currFrame;
                }
            }
            return 0;
        }