geometry - 稳健的线性插值

给定两个线段端点A和B(在二维中)，我想基于值t进行线性插值，即:

C = A + t(B-A)

在理想世界中，A，B和C应该是共线的。但是，我们在此处使用的浮点数有限，因此会有很小的偏差。为了解决其他运算的数值问题，我使用了最初由Jonathan Shewchuk创建的健壮的自适应例程。特别是，Shewchuk实现了方位函数orient2d，该函数使用自适应精度来精确测试三个点的方位。

这是我的问题:是否有一个已知的过程如何使用浮点数学计算插值，以使其恰好位于A和B之间的直线上？在这里，我不太关心插值本身的准确性，而更多地关注所得的共线性。换句话说，只要满足共线性，C会稍微移位一下就可以了。

最佳答案

坏消息

该请求无法满足。存在A和B的值，其中t的值不为0和1，而lerp(A, B, t)的值是浮点型。

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

(sorta)好消息

但是，精确的插值可以表示为5个浮点值的总和(在2D情况下为矢量):一个用于公式的结果，一个用于每个操作中的错误[1]，以及一个用于乘以误差的值通过t。我不确定这对您是否有用。为简单起见，这是单精度算法的一维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标准所不能保证的，但是至少在支持SSE2 [2] [3]的处理器中，可以指示GNU gcc编译器这样做。

可以保证(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，它不能表示为单精度浮点数。

一个更复杂的示例:

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.36790125353468468173173751466326415538787841796875，不能精确地存储在单精度浮点数中。

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

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

引用

[1] Graillat，Stef(2007)。 Accurate Floating Point Product and Exponentiation.

[2] Enabling strict floating point mode in GCC

[3] Semantics of Floating Point Math in GCC

Err1

geometry - 稳健的线性插值