lerp.py

def lerp(a,b,x):
    """
    0.0 <= a,b <= 1.0
    0.0 <= x <= 1.0

    v  x
    ----
    a (0)
    b (1)

    .--x

    a--b
    """
    return a*x + b*(1.0-x)

def bilerp(a,b,c,d,x,y):
    """
    0.0 <= a,b,c,d <= 1.0
    0.0 <= x,y <= 1.0

    v  x  y
    --------
    a (0, 0)
    b (1, 0)
    c (0, 1)
    d (1, 1)

    .--x
    |
    y

    a--b
    |  |
    c--d
    """
    return 1/2.0 * sum((
        lerp(lerp(a,b, x), lerp(c,d, x), y),
        lerp(lerp(a,c, y), lerp(b,d, y), x),
    ))

def trilerp(a,b,c,d,e,f,g,h,x,y,z):
    """
    0.0 <= a,b,c,d,e,f,g,h <= 1.0
    0.0 <= x,y,z <= 1.0

    v  x  y  z
    -----------
    a (0, 0, 0)
    b (1, 0, 0)
    c (0, 1, 0)
    d (1, 1, 0)
    e (0, 0, 1)
    f (1, 0, 1)
    g (0, 1, 1)
    h (1, 1, 1)

      z
     /
    .--x
    |
    y

      e----f
     /:   /|
    a----b |
    | g..|.h
    |/   |/
    c----d
    """
    return 1/3.0 * sum((
        lerp(bilerp(a,b,c,d, x, y), bilerp(e,f,g,h, x, y), z),
        lerp(bilerp(a,e,c,g, z, y), bilerp(b,f,d,h, z, y), x),
        lerp(bilerp(a,b,e,f, x, z), bilerp(c,d,g,h, x, z), y),
    ))

def bezerp(a,b,c,d, t):
    return lerp(lerp(lerp(a,b,t), lerp(b,c,t), t), lerp(lerp(b,c,t), lerp(c,d,t), t), t)
    
def bezeval(v, x):
    if x <= v[0]:
        return v[1]
    x = min(max(v[0], x), v[-2])
    i = 0
    while i < len(v) and v[i+6] < x:
        i += 6
    left = 0.0
    right = 1.0
    t = 0.5
    for n in range(15):
        on_left = (bezerp(v[i],v[i+2],v[i+4],v[i+6],left) < x) != (bezerp(v[i],v[i+2],v[i+4],v[i+6],t) < x)
        right = t if on_left else right
        left = left if on_left else t
        t = (right - left) / 2.0 + left
    return bezerp(v[i + 1], v[i + 3], v[i + 5], v[i + 7], t)
    
def add_knot(v, x):
    """
    Take a curve and add a new knot at x such that the curve is not changed
    """
    v = list(v)
    x = min(max(v[0], x), v[-2])
    i = 0
    while i < len(v) and v[i+6] < x:
        i += 6
    left = 0.0
    right = 1.0
    t = 0.5
    for n in range(15):
        on_left = (bezerp(v[i],v[i+2],v[i+4],v[i+6],left) < x) != (bezerp(v[i],v[i+2],v[i+4],v[i+6],t) < x)
        right = t if on_left else right
        left = left if on_left else t
        t = (right - left) / 2.0 + left
    h1x, h1y = lerp(v[i], v[i+2], t), lerp(v[i+1], v[i+3], t)
    h2x, h2y = lerp(v[i+4], v[i+6], t), lerp(v[i+5], v[i+7], t)
    mx, my = lerp(v[i+2], v[i+4], t), lerp(v[i+3], v[i+5], t)
    h1y_my = lerp(h1y, my, t)
    my_h2y = lerp(my, h2y, t)
    for p in v[:i]:
        yield p
    yield v[i]; yield v[i+1]
    yield h1x; yield h1y
    yield lerp(h1x, mx, t); yield h1y_my
    yield x; yield lerp(h1y_my, my_h2y, t)
    yield lerp(mx, h2x, t); yield my_h2y
    yield h2x; yield h2y
    yield v[i+6]; yield v[i+7]

    for p in v[i+8:]:
        yield p