geometry - 鲁棒线性插值

Question

给定两个线段端点 A 和 B(二维)，我想根据值 t 执行线性插值，即:

C = A + t(B-A)

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

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

Answer 1

坏消息

无法满足请求。对于 A 和 B 的值，除了 0 和 1 之外，没有 t 值，其中 lerp(A, B, t) 是 float 。

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

(有点)好消息

然而，精确的插值可以表示为 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)的算术加法等于期望的结果；但是，不能保证这些量的浮点加法是准确的。

使用上面的示例， exact_lerp(12345678.f, 12345679.f, 0.300000011920928955078125f, &err1, &err2, &err3, &err4) 返回 12345678.f 和 err1 的结果， err2 、 err3 和 err4 分别是 0.0f 、 0.0f 、 0.300000011920928955078125f 和 0.0f 。事实上，正确的结果是 12345678.300000011920928955078125，它不能表示为单精度 float 。

一个更复杂的示例: 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，并且无法精确存储在单精度 float 中。

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

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

引用文献

• [1] Stef Graillat (2007)。 Accurate Floating Point Product and Exponentiation.
• [2] Enabling strict floating point mode in GCC
• [3] Semantics of Floating Point Math in GCC