math - 间隔之间的插值，按照贝塞尔曲线插值

Question

为了实现 2D 动画，我正在寻找两个关键帧之间的插值，其变化速度由贝塞尔曲线定义。问题是贝塞尔曲线以参数形式表示，而要求是能够评估特定时间的值。

详细地说，假设 10 和 40 的值将在 4 秒内插值，该值不是不断变化的，而是由表示为 0,0 0.2,0.3 0.5,0.5 1,1 的贝塞尔曲线定义的。
现在，如果我以每秒 24 帧的速度绘图，我需要评估每一帧的值。我怎样才能做到这一点 ？我查看了 De Casteljau 算法，并认为将曲线分成 24*4 段 4 秒可以解决我的问题，但这听起来是错误的，因为时间是沿着“x”轴而不是沿着曲线。

为了进一步简化
如果我在平面上绘制曲线，x 轴代表时间，y 轴代表我要查找的值。我真正需要的是能够找出对应于“x”的“y”。然后我可以将 x 分成 24 等份并知道每一帧的值

Answer 1

我面临着同样的问题:似乎每个动画包都使用贝塞尔曲线来控制随时间变化的值，但没有关于如何将贝塞尔曲线实现为 y(x) 函数的信息。所以这就是我想出的。

二维空间中的标准三次贝塞尔曲线可以由四个点 定义P0=(x0, y0) .. P3=(x3, y3) .
P0 和 P3 是曲线的端点，而 P1 和 P2 是影响其形状的 handle 。使用参数 t ϵ [0, 1]，然后可以使用等式确定曲线上任何给定点的 x 和 y 坐标
A) x = (1-t)3x0 + 3t(1-t)2x1 + 3t2(1-t)x2 + t3x3 和
B) y = (1-t)3y0 + 3t(1-t)2y1 + 3t2(1-t)y2 + t3y3 .

我们想要的是一个函数 y(x)，给定一个 x 坐标，它将返回曲线的相应 y 坐标。为此，曲线必须从左到右单调移动，以便它不会在不同的 y 位置多次占据相同的 x 坐标。确保这一点的最简单方法是限制输入点，以便 x0 < x3 和 x1, x2 ϵ [x0, x3] .换句话说，P0 必须在 P3 的左侧，并且它们之间有两个 handle 。

为了计算给定 x 的 y，我们必须首先从 x 确定 t。从 t 得到 y 就是将 t 应用于方程 B 的简单问题。

我看到两种确定给定 y 的方法。

首先，您可以尝试对 t 进行二分搜索。从 0 的下限和 1 的上限开始，并通过等式 A 为 t 计算这些值的 x。继续平分区间，直到获得合理接近的近似值。虽然这应该可以正常工作，但它既不会特别快也不会非常精确(至少不是同时)。

第二种方法是实际求解方程 A 的 t。这有点难以实现，因为方程是三次方程。另一方面，计算变得非常快并产生精确的结果。

方程 A 可以改写为
(-x0+3x1-3x2+x3)t3 + (3x0-6x1+3x2)t2 + (-3x0+3x1)t + (x0-x) = 0 .
插入 x0..x3 的实际值，我们得到形式为 的三次方程at3 + bt2 + c*t + d = 0 我们知道在 [0, 1] 内只有一个解。我们现在可以使用类似 this Stack Overflow answer 中发布的算法来求解这个方程。 .

下面是一个演示这种方法的小 C# 类。将其转换为您选择的语言应该足够简单。

using System;

public class Point {
    public Point(double x, double y) {
        X = x;
        Y = y;
    }
    public double X { get; private set; }
    public double Y { get; private set; }
}

public class BezierCurve {
    public BezierCurve(Point p0, Point p1, Point p2, Point p3) {
        P0 = p0;
        P1 = p1;
        P2 = p2;
        P3 = p3;
    }

    public Point P0 { get; private set; }
    public Point P1 { get; private set; }
    public Point P2 { get; private set; }
    public Point P3 { get; private set; }

    public double? GetY(double x) {
        // Determine t
        double t;
        if (x == P0.X) {
            // Handle corner cases explicitly to prevent rounding errors
            t = 0;
        } else if (x == P3.X) {
            t = 1;
        } else {
            // Calculate t
            double a = -P0.X + 3 * P1.X - 3 * P2.X + P3.X;
            double b = 3 * P0.X - 6 * P1.X + 3 * P2.X;
            double c = -3 * P0.X + 3 * P1.X;
            double d = P0.X - x;
            double? tTemp = SolveCubic(a, b, c, d);
            if (tTemp == null) return null;
            t = tTemp.Value;
        }

        // Calculate y from t
        return Cubed(1 - t) * P0.Y
            + 3 * t * Squared(1 - t) * P1.Y
            + 3 * Squared(t) * (1 - t) * P2.Y
            + Cubed(t) * P3.Y;
    }

    // Solves the equation ax³+bx²+cx+d = 0 for x ϵ ℝ
    // and returns the first result in [0, 1] or null.
    private static double? SolveCubic(double a, double b, double c, double d) {
        if (a == 0) return SolveQuadratic(b, c, d);
        if (d == 0) return 0;

        b /= a;
        c /= a;
        d /= a;
        double q = (3.0 * c - Squared(b)) / 9.0;
        double r = (-27.0 * d + b * (9.0 * c - 2.0 * Squared(b))) / 54.0;
        double disc = Cubed(q) + Squared(r);
        double term1 = b / 3.0;

        if (disc > 0) {
            double s = r + Math.Sqrt(disc);
            s = (s < 0) ? -CubicRoot(-s) : CubicRoot(s);
            double t = r - Math.Sqrt(disc);
            t = (t < 0) ? -CubicRoot(-t) : CubicRoot(t);

            double result = -term1 + s + t;
            if (result >= 0 && result <= 1) return result;
        } else if (disc == 0) {
            double r13 = (r < 0) ? -CubicRoot(-r) : CubicRoot(r);

            double result = -term1 + 2.0 * r13;
            if (result >= 0 && result <= 1) return result;

            result = -(r13 + term1);
            if (result >= 0 && result <= 1) return result;
        } else {
            q = -q;
            double dum1 = q * q * q;
            dum1 = Math.Acos(r / Math.Sqrt(dum1));
            double r13 = 2.0 * Math.Sqrt(q);

            double result = -term1 + r13 * Math.Cos(dum1 / 3.0);
            if (result >= 0 && result <= 1) return result;

            result = -term1 + r13 * Math.Cos((dum1 + 2.0 * Math.PI) / 3.0);
            if (result >= 0 && result <= 1) return result;

            result = -term1 + r13 * Math.Cos((dum1 + 4.0 * Math.PI) / 3.0);
            if (result >= 0 && result <= 1) return result;
        }

        return null;
    }

    // Solves the equation ax² + bx + c = 0 for x ϵ ℝ
    // and returns the first result in [0, 1] or null.
    private static double? SolveQuadratic(double a, double b, double c) {
        double result = (-b + Math.Sqrt(Squared(b) - 4 * a * c)) / (2 * a);
        if (result >= 0 && result <= 1) return result;

        result = (-b - Math.Sqrt(Squared(b) - 4 * a * c)) / (2 * a);
        if (result >= 0 && result <= 1) return result;

        return null;
    }

    private static double Squared(double f) { return f * f; }

    private static double Cubed(double f) { return f * f * f; }

    private static double CubicRoot(double f) { return Math.Pow(f, 1.0 / 3.0); }
}