Molaskes: Paving and Leading the Way

‌ ‌ In 1994 I took a 2-hour train ride to visit some relatives of mine. I decided to use this ride to solve the task of finding the perfect interpolation formula, and I successfully did so, as described below, within the 2 hours, using nothing but a pencil and four sheets of A4 writing paper. First let's take a look at a schematic sketch: ‌ We know that on the left side (s=s₁), the value shall be v₁ and the gradient shall be m₁. On the right side (s=s₂) the value shall be v₂ and the gradient shall be m₂. In between there shall be a natural curve v(s) — which means continuous (no breaks or irregularities). To get the math a bit more handy, let's push our curve-to-be with the point (s₁,v₁) to (0,0). This doesn't hurt much, because it is just a simple vector subtraction (new s = old s - s₁, and new v = old v - v₁), which we can reverse at any point, but it helps us much to get more readable formulas below. For the final formula, we will simply add s₁ to our s and v₁ to our v, and the curve will be where it should be. So, instead of v(s1)=v1 and v(s2)=v2‌ we will work with v(0)=0 and v(s2-s1)=v2-v1. And to make it even handier, we will define Δs=s2-s1 and Δv=v2-v1‌ and therefore write for short v(0)=0 and v(Δs)=Δv. 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 m₁ to m₂ in v'(s). That means we look for a way to do v'(s)=m1·F1(s)+m2·F2(s)‌ with F1(0)=1 to F1(Δs)=0 and F2(0)=0 to F2(Δs)=1. For the second F, that fades in m₂, this is absolutely trivial: F2(s)=s/Δs: ‌ And the first F, that fades out m₁, is not hard to find either: F1(s)=1-s/Δs: ‌ So we now have v'(s)=m1·(1-s/Δs)+m2·s/Δs. (Just set s to 0 vs Δs to see that indeed v'(0)=m₁ and v'(Δs)=m₂.) 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 m₁‌ and/or v'(Δs) would become different from m₂. 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 s₁ and s₂, the curve bends in some relation to m₁ and m₂ and Δv/Δs: ‌ Let's therefore work with a virtual mid-point gradient m_M, which describes the gradient of the curve right between our two points: v'(Δs/2)=mM. We now need to add this m_M 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 and FM(Δs/2)=1 and FM(Δs)=0. The following 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.) Using this we finally can set: v'(s)=m1·(1-s/Δs)+m2·(s/Δs)+mM·(1-(2s/Δs-1)²). If you verify this formula, you will find that v'(0) is m₁ and v'(Δs) is m₂ — which is exactly what we wanted — but v'(Δs/2) is not m_M but mM+(m1+m2)/2 instead. That, however, is no problem at all, really. The m_M 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), it is rather the "magic delta" that must be added to the mean value of m₁ and m₂. 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): ‌ Now we will eventually integrate v'(s). If you do not remember it anymore: the integral of xⁿ 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: ‌ Prepare for the last steps, which will include getting rid of the m_M! If we set m_M to any value independent from s, the formula stays the same, and thus our m₁ at the beginning and m₂ at the end remain intact. So we now can find the proper value for m_M 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: ‌ And this shall equal Δv! So: v(Δs)=Δv=Δs⋅(m1/2+m2/2+2mM/3). Now we can finally solve m_M, and get: mM=3(2Δv/Δs-m1-m2)/4. Which we can use in our v(s): 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: ‌

---

‌ ‌ For time-critical applications, we want to be able to iteratively refine data chains by smoothing them out, such as in 2D or 3D graphics, or in audio processing such as digital special effects. ‌ ‌ First we need to assign the correct curve gradient to every sample point. The best algorithm (in computer programming) is to first do this with all the middle points, and only then with the leftmost (starting) and the rightmost (ending) point. The number of sample points is here written as c ("count"). The example is for a 3D space interpolation, and you can easily remove dimensions, or add further ones: ‌ Next we need to spread the curve's data: ‌ Finally we can calculate the new, interpolated values for each gap (every odd n): ‌ The new c for the next iteration will be: cnew=(cold-1)⋅2+1. ‌ The gradient formulas are quite straightforward solutions when you make some sketches: The gradient in any non-end point is equal to the gradient formed by its neighboring points: ‌ For the end points, it is a little trickier, but it actually just ensures that the gradient of the adjacent point is mirrored symmetically over the straight line that connects it to the end point: ‌ The IMIP interpolation formula we get when we solve the EMIP formula for s=Δs/2: ‌ Here is a simple animated 3D example, with the golden balls being the original data set, and the blue balls showing four IMIP iteration steps in decreasing opacity (increasing transparency): ‌ ‌ IMIP might be used not only for 2D and 3D graphics and audio processing, but for example also in artificial intelligence applications, where multidimensional experience clusters shall be read out to generate an appropriate response to sensoric input from the environment. The iterativeness should be a fair equivalent to how our own brains work: When the AI has time to "think", it will be much more accurate, but under "stress", its responses will be less refined.

Esc Search / Table of Contents

 

Tab ›