News: Support the forums via Fractalforums.com Online Store
 
*
Welcome, Guest. Please login or register. July 25, 2014, 08:16:01 PM


Login with username, password and session length



Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: local C∞ smooth interpolation in closed form  (Read 196 times)
0 Members and 1 Guest are viewing this topic.
kram1032
Fractal Senior
******
Posts: 1530


« on: February 03, 2012, 11:02:47 PM »

*Edit: This post is quite long and explains a couple of things but the second one shows a much simpler result that even performs better.*

A while ago, I found those papers about C-interpolation, by going into the limit of b-Splines, when you have an infinite amount of knots.
The resulting splines are called ERBS (Corresponding paper as PDF).
In that paper, they stated, that you basically need to solve an integral numerically, as else, you wont get all the traits to work.
So that meant, no closed-form expression is available.

The limit basically converged into an exponential of a rational function (as opposed to the rational function, found in NURBS)
So I wondered, whether I could combine Exponential-based rational functions (such as tan(x)) into something that has at least some of the traits but is closed form.

What I found, is this:




The blue graph is the function itself, and the purple and yellow ones are the first and second derivative, respectively.

If you use this function in a linear-interpolation-manner, e.g.

r(x) (1-f(x))+s(x) f(x)

You interpolate smoothly - PERFECTLY smoothly - between the (potentially vector-valued) functions r and s.
Outside of the interval [0,1], you'd just go on with the actual functions.
With the parameter k, I added, you can toggle, how "fast" you want this interpolation to happen.
All it needs to basically work just as well as the "default" Beziér-Interpolation, is a trivially add-able offset parameter, so you can use it multiple times for one big function.

The version, they did in the ERBS has a couple of other advantages, where I'm not sure, whether my found solution satisfy them.
If you look at the first derivative, the function could potentially be improved by making the middle portion flat as well. But I wasn't able to think of an easy "fix" for that...

Multidimensional interpolation should work just like multilinear interpolation., but instead of using the parameter t, as it's usually called, use the function given above.

Maybe, the "flat" section is too long to make this method overal useful, but in some cases it might be useful...

Here is an extreme case: Interpolating between tan(x) and cot(x) over two Intervals (0 - 2π), compared to simple linear interpolation. The function I'm using here fits the curves much closer...



As you can see, linear interpolation already fails due to the pole. At x=0, it returns a value of 1/(2π) instead of, as expected, 0.
Not very well visible is, that linear interpolation will add a break in the function, due to not being C2-smooth.
Bezier-Interpolation wouldn't have such a problem, but after a couple of derivatives, such a break would appear once again.
The function I'm using here will never have this problem. It's, as already mentioned, C.

So if you ever need REALLY smooth interpolation and you don't want to bother with the implementation of ERBS, use this.
There is only one major problem:
The nature of this interpolation function is by construction an exponential one. I'm exploiting a function that goes to 1 at ∞ and to 0 at -∞ and put in a function, that goes to exactly those places in finite time. Thus, beware of overflow and underflow...

(For maximum costumizablity, also check out GERBS(pdf) - the extension of ERBS that also allows deliberate breaks in the function and such...)
« Last Edit: February 04, 2012, 04:13:00 PM by kram1032 » Logged
kram1032
Fractal Senior
******
Posts: 1530


« Reply #1 on: February 04, 2012, 03:38:57 PM »

After a bit of randomly trying functions that work similar to cot in the desired range, I stumbled across a much simpler function that additionally has a nicer Derivative, both from viewing it in closed form and how the graph looks like.



The form that both is fully simplified and parametric, looks like this:

 [1+(1+k(m-x))-[2k(1+k(m-x))(m-x)]-1(k(x-m))[2k(1+k(m-x))(m-x)]-1]-1

with k being a quater of the tangent in the straight part and m being the point where it starts.
This could be parametrized slightly different to go from a to b... maybe more useful for adapting the approximation speed over multiple curve segments.

Setting k=1 and m=0 returns the equation, visible in the plot (though simplified).

The other parameter-set, with a being the point where the function becomes 0 and b being the point where the function becomes 1, looks like this:

[1+c1-dc2d]-1

where

c1 = (a-x)/(a-b)
c2 = (x-b)/(a-b)

d = (a-b)2/(2 (a-x)(x-b))

Nicely symmetric, fairly simple and very usable.
Also, a lot less likely than my previous function to result in overflows or underflows and faster to calculate.

I hope, this is useful for somebody.
« Last Edit: February 05, 2012, 11:40:48 AM by kram1032 » Logged
Pages: [1]   Go Down
  Print  
 
Jump to:  


Related Topics
Subject Started by Replies Views Last post
Bicubic interpolation Programming aluminumstudios 6 1751 Last post March 21, 2010, 11:47:08 AM
by aluminumstudios
interpolation for faster rendering of zoom movies Mandelbulb 3d paolo 2 368 Last post February 07, 2012, 12:47:27 AM
by panzerboy
chaostv #4 - interpolation sequence chaosTube - News cKleinhuis 0 238 Last post November 13, 2012, 05:32:45 AM
by cKleinhuis
GLSL vertex interpolation question/problem Programming cKleinhuis 4 317 Last post April 14, 2013, 04:00:23 PM
by cKleinhuis
Eyes closed Images Showcase (Rate My Fractal) Dinkydau 2 179 Last post April 23, 2013, 03:29:57 AM
by Dinkydau

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2013, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.32 seconds with 29 queries. (Pretty URLs adds 0.01s, 2q)