Skybuck Flying
2022-06-04 21:55:54 UTC
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.
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.