Interpolation

[Ludis Langens]

<thormj at iname.com> wrote:
> Solution #2:
> Can anyone provide me with a *quick* 2 point linear interpolation
> (1d map)... and a quick 4 point interpolation (2d map)?
>
> My current code looks like:
> return (x-curve[i-1].x)*(curve[i].y - curve[i-1].y)/
>          (curve[i].x - curve[i-1].x) + curve[i-1].y;
>
> This is for a 68hc11 uC, so the less math the better. :-/

What is that code fragment trying to do?  And why do you have both an x
and a y in each array element?

Here's what GM uses (on a 68xx) to interpolate in a one dimensional
array.  "scale" is usually 16 which means that a 17 byte table maps all
input byte values.  "scale" of 8 allows a 9 byte table.  Other values
are also possible.

typedef unsigned char uchar;

uchar Interpolate(uchar *table, uchar input, uchar scale)
  {
  unsigned int temp;
  uchar whole, fract;

  temp = input * scale;
  whole = temp >> 8;
  fract = temp & 0xff;

  table += whole;

  if (table[0] <= table[1])
    return table[0] + (((table[1] - table[0]) * fract + 0x80) >> 8);
  else
    return table[0] - (((table[0] - table[1]) * fract + 0x80) >> 8);
  }

For a two dimensional array, the above algorithm gets used three times:
once in row n, once in row n + 1, and once more on the previous two
results.


To interpolate or not to interpolate:  The main reason to interpolate is
likely not the increased accuracy.  Instead, interpolating gets rid of a
step function in the output value.  Control algorithms won't work good
when a table lookup doesn't produce a smooth output.

               unsigned long BinToBCD(unsigned long i) {unsigned long t;
Ludis Langens     return i ? (t = BinToBCD(i >> 1), (t << 1) + (i & 1) + 
ludis at cruzers.com            (t + 858993459 >> 2 & 572662306) * 3) : 0;}