## Faster Cubic Interpolation

Zamaster
Posts: 1025
Joined: Jun 20, 2005 21:40
Contact:

### Faster Cubic Interpolation

For scaling images cleanly and stuff. Usually, a pure implementation of cubic interpolation requires at least 7 multiplies in the inner loop, heres a method that (with pretty good accuracy too! though some tiny gaps at the endpoints) requires only one.

The trick treats the interpolation as a second order ODE integrated with a fudged midpoint method (the actual tracker for the input x is just assumed to be shifted by one half the step size). Of course a lot more pre-calcs have to be done but assuming there is a large enough distance to cover this shouldn't matter
(mine are currently uncoptomized anyway ; ] )

Code: Select all

`#define SCRX 640    #define SCRY 480#define MaxPoints 5screenres SCRX, SCRY, 32randomize timerDim as double Points(MaxPoints-1)Dim as double pt(3), term(3), lTerm, termA, termB, nStep=1, acc, n,x, acc2Dim as integer i, q, ptIndex(3)'compute the step sizes and mid point shiftDim as double xPos=0, xSep = SCRX/MaxPoints, xSepDiv = 1/xSep, xSepDivHalf=xSepDiv*0.5For i = 0 to MaxPoints-1: Points(i)=rnd*SCRY:Next iptIndex(0)=MaxPoints-3ptIndex(1)=MaxPoints-2ptIndex(2)=MaxPoints-1     ptIndex(3)=0For i = 1 to MaxPoints    For q = 0 to 3        ptIndex(q)=((ptIndex(q)+1) Mod MaxPoints)        pt(q) = Points(ptIndex(q))    Next q        'this only has to happen once every interval... so the larger the interval the    'better the performance (duh)    term(0) = pt(3)-pt(2)-pt(0)+pt(1)    term(1) = (pt(0)-pt(1)-term(0))*2*xSepDiv*xSepDiv    term(0) = term(0)*3*xSepDiv*(xSepDiv*2)    term(2) = (pt(2)-pt(0))*xSepDiv    term(3) = pt(1)       acc = term(3)    acc2 = term(2)    'heres the trick!    x = xSepDivHalf      Circle (i*xSep,Points(i-1)),4, &HFF0000,,,,F    For q = 0 to xSep-1                               'and this it it! This is all the math to compute the cubic interpolation... so no exponent garbage        acc2 += term(0)*x+term(1)        acc += acc2                                x += xSepDiv        pset(xPos+q,acc)        sleep 10        Next q    xPos += xSepNext isleep`
Zamaster
Posts: 1025
Joined: Jun 20, 2005 21:40
Contact:
man o man... this suuurree is cooooollll...
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:
screenshots will make people interested!
Zamaster
Posts: 1025
Joined: Jun 20, 2005 21:40
Contact:
its a math thing... the screen shot is just a curvy line!
duke4e
Posts: 717
Joined: Dec 04, 2005 0:16
Location: Varazdin, Croatia, Europe
Contact:
could this be used for bicubic interpolation of images?
Zamaster
Posts: 1025
Joined: Jun 20, 2005 21:40
Contact:
YES! Thats the idea, you dont have to evaluate 7 multiplications every pixel, just one. And for endpoints you only need two more multiplications than you would for full cubic interpolation, so pretty much its faster if the scale factor for a bicubic image is greater than or equal to two.