Cubic Bézier sampling for animation easing

Showcase your libraries, tools and other projects that help your fellow love users.
Post Reply
RNavega
Party member
Posts: 235
Joined: Sun Aug 16, 2020 1:28 pm

Cubic Bézier sampling for animation easing

Post by RNavega »

Hi, this code implements the analytical solution for sampling a cubic Bézier curve with a vertical ray, in the same way that animation programs like Blender, Synfig, 3ds max, After Effects etc. do it when you're working with animation keyframes.
This means that you can export the curve keyframes and evaluate them in real-time in Lua, or create editors that offer such functionality.

You can grab the code in here: https://github.com/RNavega/CubicBezierE ... n/main.lua
(The relevant function is also inlined at the bottom of this post.)

Image

Interestingly, the (now discontinued) Spine runtime for Lua/Löve just flattens their cubic curves to a polyline and samples that, making it a ray to line-segment intersection. It's an approximation, but if you can get away with this it might be better for games with many many curves being evaluated since it's very fast. You can check their code in here: https://github.com/EsotericSoftware/spi ... #L220-L269

* Relevant function:

Code: Select all

-- Cubic Bézier curve sampling for use with animation easing.
--
-- Code by Rafael Navega (2022).
-- License: Public Domain.
--
-- === function findTFromTime ===
-- Parameters:
-- evalTime: the X coordinate of the vertical ray sampling the curve.
-- p0, p1, p2, p3: the X coordinates of the 4 control points of the cubic Bézier curve.
--
-- Returns:
-- The 't' parameter for the curve where the intersection happened, or returns
-- 'nil' in case the intersection doesn't happen or is outside the [0, 1] range.
function EasingCurve:findTFromTime(evalTime, p0, p1, p2, p3)
    -- Take the "power basis" form of the Cubic Bézier:
    -- P(t) = (1 - t)^3 * P0 + 3t(1-t)^2 * P1 + 3t² (1-t) * P2 + t³ * P3

    -- We find the 4 coefficients from the full cubic polynomial. To do that,
    -- you run the above form through WolframAlpha to get the expanded version,
    -- then combine what you can to bring it down to this cubic polynomial form...
    -- (a t³ + b t² + c t + d = 0)
    --
    -- These a,b,c,d coefficients are based on the control points:
    -- (p3-p0+3*(p1-p2)) * t³ + (3*(p2-2*p1+p0)) * t² + 3*(p1-p0) * t + p0
    --
    -- To place the vertical ray at 'evalTime', subtract this value from
    -- the coefficient (d), moving the whole curve backwards so the ray is
    -- at the origin (x=0).
    local c3 = p3 + 3.0 * (p1 - p2) - p0
    local c2 = 3.0 * (p2 - 2.0 * p1 + p0)
    local c1 = 3.0 * (p1 - p0)
    local c0 = p0 - evalTime

    -- The root finding formula uses a reduced cubic polynomial, which is the
    -- full polynomial (ax³ + bx² + cx + d = 0) as divided by (a), giving:
    -- (x³ + ax² + bx + c = 0)
    --
    -- So these a,b,c coefficients below are from the *reduced* polynomial.
    local a = c2 / c3
    local b = c1 / c3
    local c = c0 / c3

    -- Neat optimization from the Blender source code: if you precalculate (a/3), the
    -- expressions below can be simplified.
    local aDiv3 = a / 3.0

    -- From the book, find values Q and R.

    -- Starting with the original formula for Q:
    -- Q = (a² - 3b) / 9
    --
    -- You expand and replace any (a/3) with the precomputed value:
    -- a²/9 - 3b/9 =
    -- a²/9 - b/3 =
    -- (a/3)² - b/3 =
    -- x² - b/3
    local Q = (aDiv3*aDiv3) - b/3.0

    -- Starting with the original formula for R:
    -- R = (2a³ - 9ab + 27c) / 54
    --
    -- The alternative/rearranged formula of which is (thanks WolframAlpha):
    -- R = a³/27 - ab/6 + c/2
    --
    -- You expand and replace any (a/3) as well:
    -- R = a³/27  - ab/6      + c/2 =
    --     (a/3)³ - (a/3)*b/2 + c/2 =
    --     x³     - xb/2      + c/2 =
    --     (2*x³   - x*b       + c) / 2
    local R = ((2 * aDiv3 * aDiv3 * aDiv3) - (aDiv3 * b) + c) / 2.0

    local RR = R * R
    local QQQ = Q * Q * Q
    if RR < QQQ then
        -- This happens in case there's three distinct real roots (the ray
        -- crosses the curve at 3 different points).
        --do
        --    error('EasingCurve:findTFromTime() -> Multiple solutions for sampling the curve')
        --end
        -- Anyway, the code to get the three roots (if they're within the [0, 1] range) is this.
        -- To avoid this route, run the control points of your curve(s) through the "control-point
        -- fixing code" from Blender, mentioned in the references at the start of this file.
        local sqrt_Q = math.sqrt(Q)
        local theta = math.acos(R / math.sqrt(QQQ))
        local t1 = -2.0 * sqrt_Q * math.cos(theta / 3.0) - aDiv3
        local t2 = -2.0 * sqrt_Q * math.cos((theta + 2.0 * math.pi) / 3.0) - aDiv3
        local t3 = -2.0 * sqrt_Q * math.cos((theta - 2.0 * math.pi) / 3.0) - aDiv3
        return (t1 >= 0.0 and t1 <= 1.0) and t1 or nil,
               (t2 >= 0.0 and t2 <= 1.0) and t2 or nil,
               (t3 >= 0.0 and t3 <= 1.0) and t3 or nil
    else
        -- At least one real root, the other two are either complex numbers or the same
        -- real number.
        -- We only want the first real root (a single value) to be the result.
        local A = (
            (R > 0.0 and -mathPow(R + math.sqrt(RR-QQQ), 1.0/3.0)) or
             mathPow(-R + math.sqrt(RR-QQQ), 1.0/3.0)
        )
        local t1 = A + (A == 0.0 and 0.0 or Q/A) - aDiv3
        return ((t1 >= 0.0 and t1 <= 1.0) and t1 or nil), nil, nil
    end
end
Post Reply

Who is online

Users browsing this forum: No registered users and 24 guests