# Fast Interpolation given Left, Right, Intermediate and a shift value.

2 views

### Skybuck Flying

Jun 4, 2022, 5:55:55 PMJun 4
to
Hello,

Original function in Delph is:

function Linear_Interpolate(a, b, x : double ) : double;
begin
result := a*(1-x) + b*x;
end;

I would like some integer version of this:

function Linear_InterpolateFast( Left, Right, Intermediate, Shift : Integer ) : integer;
begin

end;

(
Where the intermediate value lies between left and right.
So far example Left is 0 and Right is 32. The intermediate value can ran from 1 to 31.
The shift value is related to the maximum intermediate value in the following way:
MaximumIntermediateValue = (1 shl Shift)-1;
So basically what I am currently looking for is an integer function like above for shift = 5
but a general version which shift values around would be nice too...

Intermediate + Shift kind of replaces the x parameter in the original function, computing x is kind of expensive
it needs to lie between 0 and 1 and thus intermediate value would have to be divided by 32 or 31 or in other words / (1 shl (shift=5))
So I was like... hmmm maybe try and multiple by 32 and then divide by 32 ? see below at this attempt:
)

My idea was to multiple by 32 and then divide by 32 but somehow this failed because I suck at math:

This is what I wrote down:

To interpolate between let's say [0] and [1]

we want to do something like

[0] x ?*1/1 + [1] x (1 - ?)*1/1

this becomes

[0] x ?*32/32 + [1] x (1 - ?)*32/32

this becomes

[0] x ?*32/32 + [1] x (32 - ?*32)/32

*this becomes

([0] * ? * 32) / 32 + ([1] * 32 - [1] * ? * 32) / 32

**since same fraction this becomes

( ([0] * ? * 32) + ([1] * 32 - [1] * ? * 32) ) / 32

*this becomes

[0] * (? shl 5) shr 5 + ([1] shl 5 - [1] * (? shl 5)) shr 5

**since same fraction this becomes

([0] * (? shl 5) + ([1] shl 5 - [1] * (? shl 5))) shr 5

and this is how the final function became to be:

function Linear_InterpolateFast( Left, Right, Intermediate, Shift : Integer ) : integer;
begin
result := ((Left * (Intermediate shl Shift)) + ((Right shl Shift) - (Right * (Intermediate shl Shift)))) shr Shift;
end;

But it doesn't work... it produces wrong output...

Can you do better ?

Bye for now,
Skybuck.

P.S.: Ultimately this will be used for converting 8 bit r,g,b palette colors to 13 bit r,g,b palette colors for OpenXcom game. So the idea is to increase the 16x16=256 vga palette to something larger to benefit from true color displays, 7200 palette to be exact = 16x450 =
16 rows, each 450 colors, each row has start and end color and 14 intermediate colors which are used to compute 31 intermediate interpolated colors for a total of (2+14 +14x31=450) per row, so x16 = 7200 entries for new palette)

Though if it makes sense to use another palette size for fast interpolation and calculations/instructions that is possible to... though the number of original colors is 16 per row, and the final palette should have roughly between 300 to 500 interpolated colors to make sure it covers every step from left to right.

Visualized:

[ ] = original colors
IP = interpolated colors

advanced palette (index) situation (per row, colors: 16 + IP X 14):
[0] IP1 [1] IP2 [2] IP3 [3] IP4 [4] IP5 [5] IP6 [6] IP7 [7] IP8 [8] IP9 [9] IP10 [10] IP11 [11] IP12 [12] IP13 [13] [14] IP14 [15=?]

original palette (index) situation (per row, 16 colors):

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

Any index from advanced palette should be converted to original palette index.

### Skybuck Flying

Jun 4, 2022, 6:44:21 PMJun 4
to
Well first of all the parameters inside the formula would have to be swapped.

With a little bit of help from this link and code I came to the following routine/solution which is very close, but "ofcourse" not 100% the same.

https://www.gamedev.net/forums/topic/337531-integer-interpolation/3198110/

and the code from DavW:

// slow division example:
inline int interpolate(int a, int b, int percentage) { return (a*percentage)/100+(b*(100-percentage)/100);}

// fast shifting example:
// Revised version (position is between 0 and 256):
inline int interpolate(int a, int b, int position) { return (a * position) >> 8 + (b * (256-position)) >> 8;}

Converted to Delphi and modified/adjusted/swapped around for my purposes:

function Linear_InterpolateFast( Left, Right, Intermediate, Shift : Integer ) : integer;
var
check_x,
check_a,
check_b,
check_compare : double;
begin
// good:
result :=
// (left * ( (1 shl shift)-Intermediate)) shr shift +
// (right * Intermediate) shr shift;

// can be written as and is also more accurate:

(
(left * ( (1 shl shift)-Intermediate)) +
(right * Intermediate)
)
shr shift;

// but still not as accurate as this, some combinations are not the same:
check_x := Intermediate / (1 shl shift);
check_a := left;
check_b := right;
check_compare := check_a*(1-check_x) + check_b*check_x;

if round(check_compare) <> result then
begin
result := 0; // error detected
end;
end;

Question is can you do better, speed-wise, or accuracy-wise maintaining the speed of this function ?

Have not benchmarked anything, but my main concern is avoiding the expensive division: Intermediate/31 which is now avoided with this routine above.

The check stuff is to compared against doubles.

Bye for now,
Skybuck.

P.S.: Sorry for sloppy Delphi code, could have written it a bit better, but I've been busy all day.

### Skybuck Flying

Jun 4, 2022, 7:00:10 PMJun 4
to
Unfortunately this does not yet solve the division problem, I am guessing for my purposes the "usage code" would still need a division, which cannot be shifted out currently:

because the columncount is not a power of 2 ?! BLEH !

// untested code, but I think it's a correct usage example for going from 7200 palette to 256 palette:

Left := LargerPaletteIndex div mColumnCount; // painfull div still necessary... ColumnCount would be 450 for mShift = 5
Right := Left + 1;
Intermediate := LargerPaletteIndex mod mColumnCount; // could be down with a single divmod instruction combine with above.
Shift := 5;

function Linear_InterpolateFast( Left, Right, Intermediate, Shift : Integer ) : integer;

So a different larger palette would need to be constructed where column count is a power of 2 but also the multiplier is a power of 2.... the 1 shl Shift in the routine, but I am not sure if such a combination exists for shift range 1 to 9 or so.... anything beyond shifting by 9 would probably be unreasonable, then again 16 bits per R,G,B,A is what adobe uses and maybe future 48 bit displays with 16 bit alpha channel for total of 64 bits... So a shift value would be 16-8 = 8.... so yes... shift value can range from 1 to 8... even 9 would probably be unreasonable ! ;)

Bye for now,
Skybuck.