Билинейная фильтрация — это способ масштабирования изображения с относительно хорошим качеством. Для каждого пикселя нового изображения выбирается четыре пикселя из старого и хитрым образом интерполируются между собой. Подробнее можно прочитать в википедии.
Давно хочу написать длинную и подробную статью про билинейную фильтрацию с помощью NEON, но как-то все не нахожу времени и желания. Поэтому решил начать с малого — реализация алгоритма на JavaScript.
В продолжение темы кватерниона…
Итак, есть матрица 4×4, где три оси ортогональны друг другу (по-нашенски, по-деревенски — это означает, что три оси перпендикулярны каждая с каждой, представьте оси прямоугольной системы координат, так вот это оно и есть).
Выглядит матрица вот так:
[latex]M=\begin{bmatrix}A&E&I&M\\B&F&J&N\\C&G&K&O\\D&H&L&P\end{bmatrix}[/latex]
В ней, как я уже рассказывал, «живут» три вектора ABC (ось X), EFG (ось Y), IJK (ось Z). Также есть три смещения вдоль XYZ — это M, N и O соответственно.
Для того, чтобы извлечь вектор и угол из этой матрицы я использую вот такую конструкцию (псевдокод):
def getAngleAxis(m): xx = m[A] yy = m[F] zz = m[K] # Сумма элементов главной диагонали traceR = xx + yy + zz # Угол поворота theta = acos((traceR - 1) * 0.5) # Упростим вычисление каждого элемента вектора omegaPreCalc = 1.0 / (2 * sin(theta)) # Вычисляем вектор w.x = omegaPreCalc * (m[J] - m[G]) w.y = omegaPreCalc * (m[C] - m[I]) w.z = omegaPreCalc * (m[E] - m[B]) # Получаем угол поворота и ось, # относительно которой был поворот return (theta, w) |
Мне довелось применять этот метод на матрице, где вектора ABC, EFG и IJK нормализованы. Масштаб хранится отдельно. Если вы храните масштаб внутри матрицы, то перед применением формулы надо нормализовать вектора ABC, EFG и IJK).
И снова в эфире наша рубрика: «Банальности программирования в массы»…
В этот раз хочу поделиться с народом штукой под названием «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, а потом в комментариях к статье нашел другую и неожиданно обрел знание: как работают кривая Безье и в чем собственно суть. И чтобы не забыть, сделал эту запись в блоге.
Вообще я сразу теряюсь, когда в статье наталкиваюсь на математические формулы и сразу пытаюсь их пролистать, а тут решил вникнуть и внезапно осенило!
Самая простая кривая Безье называется «линейная кривая», хотя она не кривая, а очень даже прямая. Это банальная линейная интерполяция от точки [latex]P_0[/latex] до [latex]P_1[/latex]. Формула этой кривой вот такая: [latex]P=(1-t)*P_0+t*P_1[/latex]
Параметр [latex]t[/latex] у нас живет в пределах от нуля до единицы, заместо [latex]P[/latex] подставляем [latex]X[/latex] или [latex]Y[/latex] и получаем искомое значение.
Программистами используется та же самая формула, только в профиль (убирается лишнее умножение): [latex]P=P_0+t*(P_1-P_0)[/latex]
Следующая по сложности идет «квадратичная кривая». Она строится по трем точкам [latex]P_0[/latex], [latex]P_1[/latex] и [latex]P_2[/latex]. Оказывается, она представляет собой линейную интерполяцию двух простых кривых Безье по точками P0, P1 и P1, P2 соответственно. На мой взгляд звучит ужасно сложно, в голове рисуются страшные формулы, но на деле выходит довольно просто.
Формула первой кривой: [latex]A=(1-t)*P_0+t*P_1[/latex]
Формула второй кривой: [latex]B=(1-t)*P_1+t*P_2[/latex]
Линейная интерполяция: [latex]P=(1-t)*A+t*B[/latex]
После замены A и B получается такой монстр: [latex](1-t)*((1-t)*P_0+t*P_1)+t*((1-t)*P_1+t*P_2)[/latex]
Раскрываем, сокращаем, упрощаем: [latex]P=P_0*(1-t)^2+2*t*P_1*(1-t)+t^2*P_2[/latex]
Если записать по науке, то формула выше такая: [latex]f(t)=P_0*(1-t)^2+2*t*P_1*(1-t)+t^2*P_2[/latex]
Чтобы найти касательную к кривой Безье в любой точке t, надо вычислить производную этой функции (подсмотрено в википедии): [latex]f'(t)=2*(1-t)*(P_1-P_0)+2*t*(P_2-P_1)[/latex]
Для чего может пригодится касательная:
Если я ничего не напутал, то формула для вычисления длины выглядит вот так:
[latex]\sum\limits_{t=0}^1=|f'(t)|*\Delta t[/latex]
Затем можно рассмотреть «кубическую кривую», но это уж как-нибудь сами. Вот собственно и все, чем хотел поделиться… Не судите строго.
[latexpage]
Расстояние между точками считается довольно просто. Допустим, у нас есть две точки $(x1, y1, z1)$ и $(x2, y2, z2)$, тогда расстояние $L$ между ними считается так:
\begin{equation*}
L=\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2}
\end{equation*}
Если вам нужно определить меньше это расстояние или больше какого-то константного значения $C$, то вам нет нужны извлекать корень (довольно «дорогая» для процессора операция). Просто сравниваете значение $L^2$ со значением $C^2$.
Формула расстояния в таком случае примет вид:
\begin{equation*}
L^2=(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2
\end{equation*}
Если у вас двумерное пространство — отбросьте координату $z$.