Практическое применение B-сплайна (B-Spline) в программировании

Полтора дня разбирался в работе B-сплайна и как это применяется на практике. Хочу поделиться с вами результатами моих изысканий.

Немного теории

Допустим, у вас есть некий массив точек размером n. Что вам потребуется для работы B-сплайна:

  • определить количество интерполируемых точек (от этого зависит скорость работы, гладкость получившейся кривой и размер формулы для вычисления, количество точек равно k+1)
  • избавится от рекурсии формулы для вычисления

Общая формула для расчета коэффициентов:

    \begin{equation*}N_{i,k}(x)=\frac{x-t_i}{t_{i+k-1}-t_i}N_{i,k-1}(x)+\frac{t_{i+k}-x}{t_{i+k}-t_{i+1}}N_{i+1,k-1}(x)\end{equation*}

Формула рекурсивная и заканчивается на k равном единице:

    \begin{equation*}   N_{i,1}(x)=\left\{\begin{array}{cr}1&\text{if }t_i\leq x\textless t_{i+1}\\0&\mathrm{otherwise}\quad\end{array}\right.\end{equation*}

Пояснения к формуле:

  • если делитель получается равным или близким по значению к нулю, значит вся дробь равна нулю
  • параметр i — это индекс текущей точки
  • x — значение от i до i + 1 с нужным вам шагом (например, i равно 7, и нам нужно создать 3 точки для интерполяции, значит берем x равным 7.0, 7.5, 8.0)
  • t — неубывающий массив индексов

Вычисление элементов массива t:

    \begin{equation*}   t=\left\{\begin{array}{ll}0,&\mathrm{if}\ i<k\\i-k+1,&\mathrm{if}\ k\leq{i}\leq{n}\\n-k+2,&\mathrm{if}\ i>n\end{array}\right. \end{equation*}

Практика

Мне нужно было интерполировать по четырем точкам, поэтому я заранее на бумажке вычислил формулу без рекурсии:

    \begin{equation*}   N_{i,3}(x)=\left\{\begin{array}{ll}0,&\mathrm{if}\ x\textless t_{i}\\\frac{x-t_i}{t_{i+2}-t_i}*\frac{x-ti}{t_{i+1}-ti},&\mathrm{if}\ t_i\leq x\textless t_{i+1}\\\frac{x-ti}{t_{i+2}-ti}*\frac{t_{i+2}-x}{t_{i+2}-t_{i+1}}+\frac{t_{i+3}-x}{t_{i+3}-t_{i+1}}*\frac{x-ti}{t_{i+2}-t_{i+1}},&\mathrm{if}\ t_{i+1}\leq x\textless t_{i+2}\\\frac{t_{i+3}-x}{t_{i+3}-t_{i+1}}*\frac{t_{i+3}-x}{t_{i+3}-t_{i+2}},&\mathrm{if}\ t_{i+2}\leq x\textless t_{i+3}\\0,&\mathrm{if}\ x\geq t_{i+3}\end{array}\right. \end{equation*}

Про бумажку я, конечно, соврал, мне было удобнее сделать функцию на питоне вот такого вида:

def div(a, b):
    try:
        return a / float(b)
    except ZeroDivisionError:
        return 0
 
def N(i, k, x, t):
    if 1 == k:
        if t[i] <= x < t[i + 1]:
            return 1.0
        return 0.0
    a = div(x - t[i], t[i + k - 1] - t[i]) * N(i, k - 1, x, t)
    b = div(t[i + k] - x, x[i + k] - x[i + 1]) * N(i + 1, k - 1, x, t)
    return a + b

После этого добавил условие k==2 и все возможные возвращаемые значения в зависимости от x, затем условие k==3, значения которого зависят от k==2. Может вам будет удобнее все это сделать на бумажке.

Наконец можно приступать к интерполяции. Формула такая:

    \begin{equation*}   \sum\limits_{i}^{i+k}=\vec{p_{i}}N_{i,k}(x) \end{equation*}

Если индекс точки меньше нуля, берем нулевую точку, если индекс точки больше размера массива, то берем последнюю точку в массиве.

Небольшой пример

У нас есть некий массив точек, нам надо интерполировать с пятой по шестую точки с шагом 0.25, при этом $k$ равно 3 (значит для интерполяции нужно взять четыре точки).

     \begin{equation*}   p_0=p_5*N_{0,3}(0.0)+p_6*N_{1,3}(0.0)+p_7*N_{2,3}(0.0)+p_8*N_{3,3}(0.0) \end{equation*}

     \begin{equation*}   p_1=p_5*N_{0,3}(0.25)+p_6*N_{1,3}(0.25)+p_7*N_{2,3}(0.25)+p_8*N_{3,3}(0.25) \end{equation*}

     \begin{equation*}   p_2=p_5*N_{0,3}(0.5)+p_6*N_{1,3}(0.5)+p_7*N_{2,3}(0.5)+p_8*N_{3,3}(0.5) \end{equation*}

     \begin{equation*}   p_3=p_5*N_{0,3}(1.0)+p_6*N_{1,3}(1.0)+p_7*N_{2,3}(1.0)+p_8*N_{3,3}(1.0) \end{equation*}

Итого четыре новых точки вместо двух.

Спасибо за внимание, надеюсь нигде не ошибся. На несложные вопросы по теме могу ответить в комментариях.

Линейная интерполяция между углами

Иногда бывает необходимо выполнить линейную интерполяцию между углами. Ситуация осложняется тем, что углы в градусах бывают равны при совершенно разных значениях (например угол -360, 360 и 0 на самом деле одно и тоже). Делюсь методом правильной интерполяции между углами (подсмотрено в исходниках Quake).

float lerpAngle(float a1, float a2, float t)
{
    if (a1 - a2 > 180) 
    {
        a1 -= 360;
    }
    if (a1 - a2 < -180)
    {
        a1 += 360;
    }
    return a1 + t * (a2 - a1);
}

Если вам необходимо вычислить расстояние в градусах между углами, то можно переписать код так:

float distAngle(float a1, float a2)
{
    if (a1 - a2 > 180) 
    {
        a1 -= 360;
    }
    if (a1 - a2 < -180)
    {
        a1 += 360;
    }
    return abs(a2 - a1);
}
Билинейная фильтрация на JavaScript

Билинейная фильтрация — это способ масштабирования изображения с относительно хорошим качеством. Для каждого пикселя нового изображения выбирается четыре пикселя из старого и хитрым образом интерполируются между собой. Подробнее можно прочитать в википедии.

Давно хочу написать длинную и подробную статью про билинейную фильтрацию с помощью NEON, но как-то все не нахожу времени и желания. Поэтому решил начать с малого — реализация алгоритма на JavaScript.

(далее…)

Убираем резкие перепады входных данных

И снова в эфире наша рубрика: «Банальности программирования в массы»…

В этот раз хочу поделиться с народом штукой под названием «Low-pass filter».

«Ну что ты, в самом деле, опять про то, что все уже давным-давно знают» — скажут опытные программисты. «А вот ничего подобного» — отвечу им, лично я узнал об этом совсем недавно. И очень жалею, что не знал этого раньше.

Итак, вот функция для сглаживания входных данных:

def filter(a, b, dt, RC):
    t = dt / (RC + dt)
    return a + t * (b - a)

где a — текущее значение переменной, b — следующее значение, dt — время в миллисекундах между кадрами, RC — некий коэффициент (чем больше значение, тем больше сглаживание).

Соответственно, если вам надо сгладить какое-то значение (например, позицию камеры по Y в зависимости от позиции Y главного героя), то можно применить эту функцию следующим образом (значение RC подбирается опытным путем):

def update(dt):
    camPosY = filter(camPosY, heroPosY, dt, 0.85)

Кстати, тут используется линейная интерполяция, которая вкратце описана в этой заметке: «Линейная интерполяция и кривая Безье».

Линейная интерполяция и кривая Безье

Как-то после обеда прочитал статью на gamedev.ru, а потом в комментариях к статье нашел другую и неожиданно обрел знание: как работают кривая Безье и в чем собственно суть. И чтобы не забыть, сделал эту запись в блоге.

Вообще я сразу теряюсь, когда в статье наталкиваюсь на математические формулы и сразу пытаюсь их пролистать, а тут решил вникнуть и внезапно осенило!

Линейная кривая

Самая простая кривая Безье называется «линейная кривая», хотя она не кривая, а очень даже прямая. Это банальная линейная интерполяция от точки P_0 до P_1. Формула этой кривой вот такая: P=(1-t)*P_0+t*P_1
Параметр t у нас живет в пределах от нуля до единицы, заместо P подставляем X или Y и получаем искомое значение.

Программистами используется та же самая формула, только в профиль (убирается лишнее умножение): P=P_0+t*(P_1-P_0)

Квадратичная кривая

Следующая по сложности идет «квадратичная кривая». Она строится по трем точкам P_0, P_1 и P_2. Оказывается, она представляет собой линейную интерполяцию двух простых кривых Безье по точками P0, P1 и P1, P2 соответственно. На мой взгляд звучит ужасно сложно, в голове рисуются страшные формулы, но на деле выходит довольно просто.

Формула первой кривой: A=(1-t)*P_0+t*P_1
Формула второй кривой: B=(1-t)*P_1+t*P_2
Линейная интерполяция: P=(1-t)*A+t*B

После замены A и B получается такой монстр: (1-t)*((1-t)*P_0+t*P_1)+t*((1-t)*P_1+t*P_2)

Раскрываем, сокращаем, упрощаем: P=P_0*(1-t)^2+2*t*P_1*(1-t)+t^2*P_2

Касательная к квадратичной кривой

Если записать по науке, то формула выше такая: f(t)=P_0*(1-t)^2+2*t*P_1*(1-t)+t^2*P_2

Чтобы найти касательную к кривой Безье в любой точке t, надо вычислить производную этой функции (подсмотрено в википедии): f'(t)=2*(1-t)*(P_1-P_0)+2*t*(P_2-P_1)

Для чего может пригодится касательная:

  • поворачиваем касательную на 90 градусов, делим на длину и получаем нормаль к кривой Безье в точке t
  • берем некий шаг \Delta t, вычисляем касательную для каждой t от нуля до единицы с шагом \Delta t, суммируем длину этих касательных, умноженную на \Delta t, получаем общую длину кривой Безье, точность которой зависит от \Delta t

Если я ничего не напутал, то формула для вычисления длины выглядит вот так:

\sum\limits_{t=0}^1=|f'(t)|*\Delta t

Затем можно рассмотреть «кубическую кривую», но это уж как-нибудь сами. Вот собственно и все, чем хотел поделиться… Не судите строго.

Блог Евгения Жирнова