浮点线性插值

Question

要在两个变量之间进行线性插值a并b给出一个分数f,我目前正在使用此代码:

float lerp(float a, float b, float f) 
{
    return (a * (1.0 - f)) + (b * f);
}

我认为这可能是一种更有效的方法.我正在使用没有FPU的微控制器,因此浮点运算是在软件中完成的.它们相当快,但它仍然可以添加或增加100个周期.

有什么建议？

为了清楚起见,在上面的代码中,我们可以省略指定1.0为显式浮点文字.

Answer 1

忽略精度差异,表达式相当于

float lerp(float a, float b, float f)
{
    return a + f * (b - a);
}

这是2次加法/减法和1次乘法,而不是2次加法/减法和2次乘法.

Answer 2

如果您使用的是没有FPU的微控制器,那么浮点将非常昂贵.对于浮点运算,可能容易慢20倍.最快的解决方案是使用整数进行所有数学运算.

固定二进制点之后的位数(http://blog.credland.net/2013/09/binary-fixed-point-explanation.html?q=fixed+binary+point)为:XY_TABLE_FRAC_BITS.

这是我使用的一个功能:

inline uint16_t unsignedInterpolate(uint16_t a, uint16_t b, uint16_t position) {
    uint32_t r1;
    uint16_t r2;

    /* 
     * Only one multiply, and one divide/shift right.  Shame about having to
     * cast to long int and back again.
     */

    r1 = (uint32_t) position * (b-a);
    r2 = (r1 >> XY_TABLE_FRAC_BITS) + a;
    return r2;    
}

内联功能应该是约.10-20个周期.

如果你有一个32位微控制器,你将能够使用更大的整数,在不影响性能的情况下获得更大的数字或更高的精度.该功能用于16位系统.

Answer 3

假定浮点数学是可行的,OP的算法是一个很好的算法,并且a + f * (b - a)由于精度损失a而且b在幅度上有很大差异,因此总是优于替代算法.

例如:

// OP's algorithm
float lint1 (float a, float b, float f) {
    return (a * (1.0f - f)) + (b * f);
}

// Algebraically simplified algorithm
float lint2 (float a, float b, float f) {
    return a + f * (b - a);
}

在该示例中,假设32位浮点数lint1(1.0e20, 1.0, 1.0)将正确返回1.0,而lint2将错误地返回0.0.

当操作数的大小差别很大时,大多数精度损失在加法和减法运算符中.在上面的例子中,罪魁祸首是减法b - a和加法a + f * (b - a).由于组件在加法之前完全相乘,因此OP的算法不会受此影响.

对于a = 1e20,b = 1的情况,这里是不同结果的示例.测试程序:

#include <stdio.h>
#include <math.h>

float lint1 (float a, float b, float f) {
    return (a * (1.0f - f)) + (b * f);
}

float lint2 (float a, float b, float f) {
    return a + f * (b - a);
}

int main () {
    const float a = 1.0e20;
    const float b = 1.0;
    int n;
    for (n = 0; n <= 1024; ++ n) {
        float f = (float)n / 1024.0f;
        float p1 = lint1(a, b, f);
        float p2 = lint2(a, b, f);
        if (p1 != p2) {
            printf("%i %.6f %f %f %.6e\n", n, f, p1, p2, p2 - p1);
        }
    }
    return 0;
}

输出,略微调整格式:

    f            lint1               lint2             lint2-lint1
0.828125  17187500894208393216  17187499794696765440  -1.099512e+12
0.890625  10937500768952909824  10937499669441282048  -1.099512e+12
0.914062   8593750447104196608   8593749897348382720  -5.497558e+11
0.945312   5468750384476454912   5468749834720641024  -5.497558e+11
0.957031   4296875223552098304   4296874948674191360  -2.748779e+11
0.972656   2734375192238227456   2734374917360320512  -2.748779e+11
0.978516   2148437611776049152   2148437474337095680  -1.374390e+11
0.986328   1367187596119113728   1367187458680160256  -1.374390e+11
0.989258   1074218805888024576   1074218737168547840  -6.871948e+10
0.993164    683593798059556864    683593729340080128  -6.871948e+10
1.000000                     1                     0  -1.000000e+00

Answer 4

值得注意的是，标准线性插值公式 f1(t)=a+t(ba)、f2(t)=b-(ba)(1-t) 和 f3(t)=a(1- t)+bt 不保证在使用浮点运算时表现良好。也就是说，如果 a != b，则不保证 f1(1.0) == b 或 f2(0.0) == a，而对于 a == b，则不保证 f3(t) 等于 a ，当 0 < t < 1 时。

当我需要结果表现良好并准确到达端点时，此函数在支持 IEEE754 浮点的处理器上对我有用（我以双精度使用它，但 float 也应该工作）：

double lerp(double a, double b, double t) 
{
    if (t <= 0.5)
        return a+(b-a)*t;
    else
        return b-(b-a)*(1.0-t);
}