Problem Description:

Problembeschreibung:

We want to know the formula v(s) which accurately describes the natural curve between two points v(s1) = v1 and v(s2) = v2 with the known/given gradients v´(s1) = m1 and v´(s2) = m2.

Wir suchen die Formel v(s) welche den natürlichen Kurvenverlauf wiedergibt zwischen zwei Punkten v(s1) = v1 und v(s2) = v2 mit den bekannten/gegebenen Anstiegen v´(s1) = m1 und v´(s2) = m2.

We use v(s) instead of the more common y(x) here to better illustrate the fact, that the problem can be applied to any dimension. For instance, for a three-dimensional interpolation, you would apply the solution described here on a vector R(s) where s is the distance between the two points and R is a vector (x, y, z).

Wir verwenden hier v(s) anstelle des gebräuchlicheren y(x), um besser zu illustrieren, daß das Problem auf jede beliebige Dimension angewandt werden kann. Für eine dreidimensionale Interpolation etwa würde man die hier beschriebene Lösung auf eine Vektorform R(s) anwenden, wo s die Distanz zwischen beiden Punkten ist und R ein Vektor der Form (x, y, z).

Solution:

Lösung:

v(s) = v1 + s·m1 + s²(3Δv/Δs - 2m1 - m2)/Δs - s³(2Δv/Δs - m1 - m2)/Δs² Δv = v2 - v1 Δs = s2 - s1

Optimal form for computer algorithms:

Für Computeralgorithmik optimierte Form:

dv := v2 - v1; dsi := 1/(s2 - s1); A := v1; B := m1; C := (3*dv*dsi - 2*m1 - m2)*dsi; D := (m1 + m2 - 2*dv*dsi)*dsi*dsi; v := A + s*(B + s*(C + s*D));

Derivation:

Herleitung:

First let´s take a look again at the sketch. We know that on the left side (s = s1) the value shall be v1 and the gradient shall be m1. On the right side (s = s2) the value shall be v2 and the gradient shall be m2. In between there shall be a natural curve - which means continuous (no breaks or irregularities).

Schauen wir uns zuerst noch einmal die Skizze an. Wir wissen, daß links (s = s1) der Wert v1 sein soll und der Anstieg m1. Und rechts (s = s2) soll der Wert v2 sein und der Anstieg m2. Dazwischen soll eine natürliche Kurve verlaufen - in anderen Worten: sie soll stetig sein (keine Knicke oder sonstigen Unregelmäßigkeiten aufweisen).

To get the math a bit more handy, let´s push our curve-to-be with the point (s1,v1) to (0,0). This doesn´t hurt much, because it is just a simple vector subtraction (new s = old s - s1, and new v = old v - v1) which we can reverse at any point, but it helps us much to get more readable formulas below. For the final formula, just add s1 to your s and v1 to your v, and the curve is where it originally should be.

Um eine bessere Übersichtlichkeit zu gewährleisten, normieren wir zunächst die Kurve ein wenig, und schieben sie mit ihrem Punkt (s1,v1) nach (0,0). Das tut auch nicht weiter weh, denn es ist ja nur eine einfache, jederzeit rückgängig machbare Vektorsubtraktion (neues s = altes s - s1, und neues v = altes v - v1), hilft uns aber viel dabei, die kommenden Formeln besser lesbar zu machen. Ganz zum Schluß braucht man nur s1 zum gewünschten s addieren und v1 zum erhaltenen v, und die Kurve ist wieder dort, wo sie ursprünglich sein sollte.

So, instead of v(s1) = v1 v(s2) = v2 we will work with v(0) = 0 v(s2 - s1) = v2 - v1. And to make it even handier, we will define Δs = s2 - s1 Δv = v2 - v1 and therefore write for short v(0) = 0 v(Δs) = Δv. And remember: our s will now move only from 0 to Δs!

Anstelle von v(s1) = v1 v(s2) = v2 werden wir also arbeiten mit v(0) = 0 v(s2 - s1) = v2 - v1. Und um das Ganze noch etwas handlicher zu machen, definieren wir Δs = s2 - s1 Δv = v2 - v1 und können damit kürzer schreiben v(0) = 0 v(Δs) = Δv. Bitte merken: unser s wird sich nun nur von 0 nach Δs bewegen!

Now how are we gonna solve the actual problem? We will start with a simple ("linear") fade — but not of v(s)! No, we will fade from m1 to m2 in v´(s). That means we look for a way to do v´(s) = m1·F1(s) + m2·F2(s) with F1(0) = 1 F1(Δs) = 0 F2(0) = 0 F2(Δs) = 1

So, wie lösen wir denn nun die gestellte Aufgabe? Wir beginnen mit einer einfachen linearen Interpolation — aber nicht über v(s)! Nein, wir interpolieren von m1 bis m2 in v´(s). Das heißt, wir suchen nach einer Möglichkeit, Folgendes zu tun: v´(s) = m1·F1(s) + m2·F2(s) wobei gelten muß F1(0) = 1 F1(Δs) = 0 F2(0) = 0 F2(Δs) = 1

For the second F this is easiest: F2(s) = s/Δs

Für das zweite F ist das unglaublich einfach: F2(s) = s/Δs

And the first F now is not hard to find either: F1(s) = 1 - s/Δs (Just set s to 0 vs Δs to see what happens to either F.)

Und das erste F ist damit nun auch nicht mehr schwer zu finden: F1(s) = 1 - s/Δs (Setze einfach für s einmal 0 und einmal Δs ein, um zu sehen, was mit den Fs dann passiert.)

So we now have v´(s) = m1·(1 - s/Δs) + m2·s/Δs.

Wir haben bis hierhin also v´(s) = m1·(1 - s/Δs) + m2·s/Δs.

We could integrate this to get v(s). But how could we be able to meet the condition v(Δs) = Δv? We can hardly manipulate v(s) without destroying our so well constructed formula so far: v´(0) would become different from m1 and v´(Δs) would become different from m2.

Wir könnten dies integrieren, um v(s) zu bekommen. Aber wie befolgen wir dann die Bedingung v(Δs) = Δv? Wir können v(s) kaum manipulieren, ohne unsere bis jetzt so schön konstruierte Formel zu zerstören: v´(0) würde nicht mehr m1 ergeben, und v´(Δs) nicht mehr m2.

So, for the sake of safety, let´s stay with v´(s) for one more step. And now here comes the key trick for the whole solution. Let´s take a look at the sketch once again! Between s1 and s2, the curve bends in some relation to m1 and m2 and Δv/Δs. Let´s therefore work with a virtual middle-gradient mm, which describes the gradient of the curve right between our two points: v´(Δs/2) = mm

Aus Sicherheitsgründen verweilen wir also lieber noch einen weiteren Schritt beim v´(s). Und wir kommen nun zum wichtigsten Trick in der ganzen Lösung. Schauen wir uns noch einmal die Skizze an! Zwischen s1 und s2 biegt sich die Kurve irgendwie in Abhängigkeit von m1 und m2 und Δv/Δs. Wir werden deswegen mit einem virtuellen Mittel-Anstieg mm arbeiten, der den Anstieg der Kurve genau zwischen unseren beiden Punkten angibt: v´(Δs/2) = mm

We now need to add this mm into our formula: v´(s) = m1·F1(s) + m2·F2(s) + mm·Fm(s) And in order not to destroy our conditions for s = 0 and s = Δs it follows that Fm(0) = 0 Fm(Δs/2) = 1 Fm(Δs) = 0

Dieses mm müssen wir nun zu unserer Formel hinzufügen: v´(s) = m1·F1(s) + m2·F2(s) + mm·Fm(s) Und damit wir unsere Bedingungen für s = 0 und s = Δs nicht kaputtmachen, folgt Fm(0) = 0 Fm(Δs/2) = 1 Fm(Δs) = 0

The sketch shows the simplemost function´s graph for this task. It is the square function. We only need to flip it upside down and scale it right to fit. We then get Fm(s) = 1 - (2s/Δs - 1)² (Test it again with s = 0, s = Δs/2 and s = Δs.)

Die Skizze zeigt den Graphen der einfachsten Funktion für diese Aufgabe. Es ist die Quadratfunktion. Wir müssen sie nur auf den Kopf stellen und richtig skalieren. Dann erhalten wir Fm(s) = 1 - (2s/Δs - 1)² (Mache wieder die Probe mit s = 0, s = Δs/2 und s = Δs.)

Using this we finally can set:

Damit können wir endlich setzen:

v´(s) = m1·(1 - s/Δs) + m2·(s/Δs) + mm·(1 - (2s/Δs - 1)²)

In the next step we will integrate v´(s) to get v(s). So it would be a pretty good idea to rearrange the formula around the variable s. This leads to our final formula for v´(s):

Im nächsten Schritt werden wird v´(s) integrieren, um v(s) zu erhalten. Es ist daher angebracht, die Formel jetzt nach der Variable s umzustellen. Das führt zu unserer endgültigen Formel für v´(s):

v´(s) = m1 + s(m2 - m1 + 4mm)/Δs - s²4mm/Δs²

If you verify this formula, you will find that v´(0) is m1 and v´(Δs) is m2 — which is exactly what we wanted. But v´(Δs/2) is not mm — but that is no problem at all, really. The mm is just a virtual variable which will be dropped towards the end of the solution anyway. It is not the actual gradient at v´(Δs/2).

Wenn man für diese Formel die Probe macht, stellt man fest, daß v´(0) = m1 ist und v´(Δs) = m2 — also genau was wir wollten. Aber v´(Δs/2) ist ungleich mm — dies jedoch ist wirklich kein Problem. Das mm ist eben nur eine virtuelle Variable, die gegen Ende der Lösung ohnehin rausfliegen wird. Sie stellt nicht den tatsächlichen Anstieg in v´(Δs/2) dar.

Now we will eventually integrate v´(s). If you do not remember it anymore: the integral of xn is ∫xnδ/δx = x(n+1)/(n+1) + C Since we defined that v(s) = 0, we can integrate v´(s) and just drop the offset C (because there is none). This results in the following formula:

Nun werden wir v´(s) endlich integrieren. Wer es schon vergessen hat: das Integral von xn lautet ∫xnδ/δx = x(n+1)/(n+1) + C Da wir definiert haben, daß gelten soll v(s) = 0, können wir v´(s) integrieren und die Verschiebung C einfach weglassen (es gibt ja keine). Dies ergibt dann folgende Formel:

v(s) = s·m1 + s²(m2 - m1 + 4mm)/2Δs - s³4mm/3Δs²

Prepare for the last steps, which will include getting rid of the mm! If we set mm to any value independent from s, the formula stays the same, and thus our m1 at the beginning and m2 at the end remain intact. So we now can find the proper value for mm to make the graph fit the last remaining condition v(Δs) = Δv. (That we already keep the condition v(0) = 0 should be obvious.) Let´s see where our v(Δs) points currently:

Kommen wir zu den letzten Schritten, bei denen wir uns auch endlich vom mm verabschieden werden! Wenn wir mm auf irgendeinen von s unabhängigen Wert setzen, bleibt die Formel erhalten, und unser m1 am Anfang bleibt genauso intakt wie das m2 am Ende. Wir können nun also den richtigen Wert für mm ermitteln, der unseren Graph so skalieren wird, daß er die letzte verbleibende Bedingung v(Δs) = Δv erfüllt. (Daß wir die Bedingung v(0) = 0 bereits erfüllen, dürfte aus der obigen Formel ersichtlich sein.) Schauen wir doch einmal, was unser v(Δs) derzeit ergibt:

v(Δs) = Δs·m1 + Δs²(m2 - m1 + 4mm)/2Δs - Δs³4mm/3Δs² v(Δs) = Δs(m1 + (m2 - m1 + 4mm)/2 - s4mm/3)

And this shall equal Δv! With the formula of above slightly rearranged, we put:

Und dies soll gleich Δv sein! Die Formel von eben leicht umgestellt, können wir setzen:

Δv = Δs(m1/2 + m2/2 + 2mm/3)

Now we can finally solve mm, and get:

Nun können wir nach mm umstellen, und erhalten:

mm = 3(2Δv/Δs - m1 - m2)/4

Which we can use in our v(s):

Und das können wir in unser v(s) einsetzen:

v(s) = s·m1 + s²(m2 - m1 + 3(2Δv/Δs - m1 - m2))/2Δs - s³(2Δv/Δs - m1 - m2)/Δs²

This formula now contains only the parameters which are given with the problem. Hooray! As a last step we just need to clean up the formula to see the final result:

Diese Formel enthält nun nur noch die Parameter, die mit der Aufgabenstellung gegeben sind. Hipp, hipp, hurra! Als letztes müssen wir die Formel nur noch ein wenig aufräumen, um das Endergebnis zu sehen:

v(s) = s·m1 + s²(3Δv/Δs - 2m1 - m2)/Δs - s³(2Δv/Δs - m1 - m2)/Δs²

Commentary:

Kommentar:

I found this solution already back in early 1999 (at age 21) on a train ride from Dresden to Berlin, using only a pencil, four A4 pages of paper and of course my brain. :)

Diese Lösung fand ich bereits Anfang 1999 (also 21jährig), auf einer Zugfahrt von Dresden nach Berlin, wobei ich nichts weiter verwendete als einen Bleistift, vier A4-Seiten Papier und natürlich mein Gehirn. :)