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

1K #линейная интерполяция#математика#формулы

Как-то после обеда прочитал статью на 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

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

Расстояние между точками, маленькая хитрость

50 #математика#формулы

Расстояние между точками считается довольно просто. Допустим, у нас есть две точки (x1, y1, z1) и (x2, y2, z2), тогда расстояние L между ними считается так:

L=\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2}

Если вам нужно определить меньше это расстояние или больше какого-то константного значения C, то вам нет нужны извлекать корень (довольно «дорогая» для процессора операция). Просто сравниваете значение L^2 со значением C^2.

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

L^2=(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2

Если у вас двумерное пространство — отбросьте координату z.

Определитель матрицы 3×3

43 #математика#матрица#формулы

Определитель матрицы 3×3 вычисляется следующим образом:

\Delta(A)=\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix}=a_{11}\begin{bmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{bmatrix}-a_{12}\begin{bmatrix}a_{21}&a_{23}\\a_{31}&a_{33}\end{bmatrix}+a_{13}\begin{bmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{bmatrix}=a_{11}(a_{22}a_{33}-a_{23}a_{32})-a_{12}(a_{23}a_{33}-a_{23}a_{31})+a_{13}(a_{21}a_{32}-a_{22}a_{31})

Операции над точками и векторами

151 #вектор#математика#формулы

Операции над точками:

  • расстояние между точками \sqrt{(x_a-x_b)^2+(y_a-y_b)^2+(z_a-z_b)^2}

Операции над векторами:

  • длина \left|\vec{v}\right|=\sqrt{x^2+y^2+z^2}
  • скалярное произведение n=(\vec{a}, \vec{b})=|\vec{a}|* |\vec{b}|*cos\angle(\vec{a},\vec{b}) = x_a x_b + y_a y_b + z_a z_b, где n длина проекции вектора \vec{a} на вектор \vec{b}
  • векторное произведение \vec{c}=(y_a z_b-z_a y_b;z_a x_b-x_a z_b;x_a y_b-y_a x_b), где \vec{c} перпендикуляр к плоскости, которую образуют \vec{a} и \vec{b}
  • сложение векторов \vec{a}+\vec{b}=(x_a+x_b;y_a+y_b;z_a+z_b)
  • вычитание векторов \vec{a}-\vec{b}=(x_a-x_b;y_a-y_b;z_a-z_b)
Личный блог Евгения Жирнова