Страница 2 | Категория "Математика"

4 июля 2013 138 #javascript,#интерактив,#линейная интерполяция,#математика

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

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

(далее…)

Извлекаем вектор и угол из матрицы поворота

26 февраля 2013 1K #python,#вектор,#математика,#матрица

В продолжение темы кватерниона…

Итак, есть матрица 4×4, где три оси ортогональны друг другу (по-нашенски, по-деревенски — это означает, что три оси перпендикулярны каждая с каждой, представьте оси прямоугольной системы координат, так вот это оно и есть).

Выглядит матрица вот так:

$M=\begin{bmatrix}A&E&I&M\\B&F&J&N\\C&G&K&O\\D&H&L&P\end{bmatrix}$

В ней, как я уже рассказывал, «живут» три вектора 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).

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

5 февраля 2013 12 #python,#линейная интерполяция,#математика

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

В этот раз хочу поделиться с народом штукой под названием «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)

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

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

29 января 2013 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$

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

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

8 января 2013 46 #математика

Расстояние между точками считается довольно просто. Допустим, у нас есть две точки $(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$ .

Список постов в категории "Математика"

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

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

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