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

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

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

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

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

Какие я использую плагины для WordPress

Всем привет! Вот решил рассказать какие плагины я использую в WordPress и зачем. Поехали!

Akismet

Классика защиты от спама в комментариях. Проверяет новые комментарии по своей базе и отсеивает всякий мусор. Категорически рекомендуется к установке. Для затравки цитата из моей админки: «Akismet защитил ваш сайт от 3 522 спам-комментариев».

Executable PHP widget

Позволяет добавлять виджеты в тему с исполняемым PHP кодом. Установил специально для YoWindow.

Google Analytics for WordPress

Поддержка службы «Google Analytics». Благодаря ему можно смотреть подробную статистику посещений блога.

Google XML Sitemaps

Генерация файлика sitemap.xml, включая запакованную версию. Этот файл идет в нагрузку к robots.txt и используется поисковиками для более подробной индексации сайта. Рекомендую!

LiveJournal Crossposter

Автоматически создает копию поста в моем блоге в ЖЖ. В последнее время почему-то глючит и создает дубли при кросспостинге. Кандидат на удаление.

Mail From

Задает имя для робота, который шлет отчеты на почту. Согласитесь, что noreply@blog2k.ru намного лучше какого-нибудь ip141.32.31@blog2k.ru. Чисто декоративный плагин.

Pagination Rel Links

Задает значения аттрибута rel — «next|prev» для лучшего индексирования страниц. Подробности можно узнать в этой статье на хабре.

StatPress Reloaded

Статистика посещений моего блога в дополнение к службам «Google Analytics» и «Яндекс.Метрика». Чисто позырить — кто ходит по блогу и зачем.

Use Google Libraries

Загрузка стандартных библиотек (типа jQuery) с хостинга Google. Теоретически из-за этого блог грузится быстрее, потому что загрузка скриптов происходит с разных IP адресов. Честно говоря, не проверял. Поверил на слово.

WordPress Popular Posts

Список популярных постов, который вы видите справа. Можно выводить список популярных постов за сутки, неделю, месяц или за все время наблюдения. В плагине StatPress Reloaded есть похожий функционал, но он как-то совсем криво работает и сделан, видимо, для галочки.

WP-Syntax

Подсветка синтаксиса исходников. Поддержка C/C++/Python/Java/sh и еще куча других. Его работу можно увидеть воочию в разделе «Программирование».

WP LaTeX

Вставка математических формул в блог. Задаете формулу в формате LaTeX, а плагин вставляет картинку заместо нее. Ну очень полезный плагин. Поставил его сразу после Akismet для постов про матрицы и вектора так и остался он тут жить.

WP Super Cache

Кеширует страницы блога, избавляя сервер от лишней работы по разбору PHP скриптов. Реально ускоряет блог.

WP Ya.Share

Добавляет кнопку «Поделиться» от «Яндекса» для множества социальных сетей к каждому посту.

Яндекс.Метрика

Интеграция сервиса «Яндекс.Метрика». Учитывая, что «Яндекс.Метрика» «залипает» во время загрузки графиков — кандидат на удаление.

UPD: написал обновленную версию этого поста, часть вторую. Ознакомится можно по ссылке: «Какие я использую плагины для WordPress — 2».

Что такое матрица 4×4 в трехмерных играх?

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

Ну согласитесь — нормального человека нельзя заставить умножать и складывать 32 числа непонятно для какой цели.. Тупо делать это только ради оценки в журнале. Я так не умею, а Вы?

Итак, что же такое матрица 4×4? Какую роль она играет в трехмерных играх? Зачем эти 16 чисел складывать и умножать? СКАНДАЛЫ, ИНТРИГИ, РАССЛЕДОВАНИЯ.. Читайте дальше в моем журнале после короткой рекламы.

Рассмотрим абстрактную матрицу, в которой злой гений зашифровал положение объекта в трехмерном мире:

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

Начнем расшифровку.. В матрице присутствуют три вектора, вот они перед Вами:

\vec{X}=(A, B, C)
\vec{Y}=(E, F, G)
\vec{Z}=(I, J, K)

Как нетрудно догадаться, это вектора осей системы координат. Длина этих векторов — это масштаб объект вдоль каждого вектора.

Рассмотрим такую матрицу:

M=\begin{bmatrix}2&0&0&M\\0&3&0&N\\0&0&0.5&O\\D&H&L&P\end{bmatrix}

Что следует из этой матрицы? Во-первых, по X объект увеличен в два раза, по Y в три раза, по Z уменьшен в два раза.

Смотрим дальше. Числа M, N и O — это смещение объекта вдоль этих векторов (по X, Y и Z соответственно).

С остальными числами я пока не разобрался. Число P практически всегда равно единице, остальные — нулю. Есть подозрение, что они имеют отношение к проецированию трехмерного объекта на двухмерный экран.

Ссылка на подробный обзор матриц и операций на ними из комментариев: http://www.opengl-tutorial.org/ru/beginners-tutorials/tutorial-3-matrices/