稳健的线性插值

Question

给定两个线段端点 A 和 B（在二维中），我想根据值 t 执行线性插值，即：

C = A + t(B-A)

在理想世界中，A、B 和 C 应该共线。但是，我们在这里使用有限的浮点运算，所以会有小的偏差。为了解决其他操作的数值问题，我使用了最初由 Jonathan Shewchuk 创建的强大的自适应例程。特别是，Shewchuk 实现了一个方向函数orient2d，该函数使用自适应精度来精确测试三个点的方向。

我的问题是：是否有一个已知的程序如何使用浮点数学计算插值，以便它正好位于 A 和 B 之间的线上？在这里，我不太关心插值本身的准确性，而更关心由此产生的共线性。换句话说，只要满足共线性，C 稍微移动一点就可以了。

Answer 1

坏消息

请求无法得到满足。A对于和的值，除了 0 和 1 之外，B没有其他值为浮点数的值。tlerp(A, B, t)

单精度的一个简单例子是x1 = 12345678.f和x2 = 12345679.f。y1无论和的值如何y2，所需的结果都必须具有和x之间的分量，并且这两者之间不存在单精度浮点数。12345678.f12345679.f

（有点）好消息

然而，精确的插值可以表示为 5 个浮点值（在 2D 情况下为向量）的总和：一个用于公式结果，一个用于每个运算 [1] 中的误差，另一个用于乘以误差经过t。我不确定这对你是否有用。为了简单起见，以下是单精度算法的 1D C 版本，它使用融合乘加来计算乘积误差：

#include <math.h>

float exact_sum(float a, float b, float *err)
{
    float sum = a + b;
    float z = sum - a;
    *err = a - (sum - z) + (b - z);
    return sum;
}

float exact_mul(float a, float b, float *err)
{
    float prod = a * b;
    *err = fmaf(a, b, -prod);
    return prod;
}

float exact_lerp(float A, float B, float t,
                 float *err1, float *err2, float *err3, float *err4)
{
    float diff = exact_sum(B, -A, err1);
    float prod = exact_mul(diff, t, err2);
    *err1 = exact_mul(*err1, t, err4);
    return exact_sum(A, prod, err3);
}

为了使该算法发挥作用，操作需要在舍入到最近模式下符合 IEEE-754 语义。C 标准不能保证这一点，但可以指示 GNU gcc编译器这样做，至少在支持 SSE2 的处理器中 [2][3]。

保证 的算术加法(result + err1 + err2 + err3 + err4)等于期望的结果；但是，不能保证这些量的浮点加法是准确的。

要使用上面的示例，分别返回and 、、are 、和的exact_lerp(12345678.f, 12345679.f, 0.300000011920928955078125f, &err1, &err2, &err3, &err4)结果。事实上，正确的结果是 12345678.300000011920928955078125，它不能表示为单精度浮点数。12345678.ferr1err2err3err40.0f0.0f0.300000011920928955078125f0.0f

一个更复杂的例子：exact_lerp(0.23456789553165435791015625f, 7.345678806304931640625f, 0.300000011920928955078125f, &err1, &err2, &err3, &err4)返回2.3679010868072509765625f和错误是6.7055225372314453125e-08f、8.4771045294473879039287567138671875e-08f和1.490116119384765625e-08f。2.66453525910037569701671600341796875e-15f这些数字加起来就是精确的结果，即 2.36790125353468550173374751466326415538787841796875，并且无法精确存储在单精度浮点数中。

上面示例中的所有数字都是使用其精确值而不是近似值来编写的。例如，0.3不能精确地表示为单精度浮点数；最接近的一个的精确值为 0.300000011920928955078125，这是我使用过的。

如果您计算（按该顺序），您可能err1 + err2 + err3 + err4 + result会得到在您的用例中被视为共线的近似值。也许值得一试。

参考

• [1] Stef Graillat (2007)。精确的浮点乘积和幂运算。
• [2]在GCC中启用严格浮点模式
• [3] GCC 中浮点数学的语义