Зона кода

А давайте немного попрограммируем...

Пиксельный взрыв. Часть 1. Построение алгоритмов

C99Графические программы

Захотелось мне, развлечения ради, написать очередную программку на C99, генерирующую кадры анимации. На этот раз я решил анимировать "взрывы" произвольных изображений. Если говорить коротко, "взрыв" заключается в распаде изображения на отдельные пиксели, которые "разбегаются" по прямолинейным траекториям, удаляясь от заранее выбранной точки, которую мы назовём центральной точкой или центром взрыва, до тех пор, пока не выйдут за пределы прямоугольного холста, изначально содержащего  "взрываемое" изображение.

По аналогии с атомным взрывом, разрывающим объект на отдельные атомы, наш взрыв, в результате которого изображение распадается на пиксели, я решил назвать пиксельным взрывом. Пиксельный взрыв, в отличие от атомного, будет вполне себе мирным, и даже, надеюсь, забавным.

А для чего всё это нужно? Ну, во-первых, будет интересно построить алгоритм для решения поставленной задачи. Во-вторых, полученный результат можно использовать при создании простейших заставок к видеороликам или при реализации в роликах переходов между статичными кадрами (например, в слайд-шоу). А в-третьих, как уже было заявлено в статье, — для развлечения.

Замечу, что под "пикселем" в растровой графике чаще всего понимается наименьший неделимый элемент изображения, который фиксирован и своего положения не меняет. Так что корректнее, наверное, было бы говорить о распаде изображений на разбегающиеся точки, а не на пиксели. Но "пиксельный" взрыв звучит лучше, чем "точечный", поэтому я выбрал именно такой эпитет.

Но в дальнейшем мы будем, всё же, говорить о движении именно точек, а не пикселей, предполагая, что одна и та же точка может быть изображена любым пикселем, окрашенным в цвет этой точки.

А теперь давайте конкретизируем постановку задачи.

Постановка задачи

Будем предполагать, что у нас имеется некоторое исходное изображение. Будем считать, что во взрыве участвуют определённые принадлежащие ему точки. Возможны 2 варианта: либо участвуют все точки, либо только те, цвет которых отличен от заранее выбранного цвета, который назовём фоновым.

Первый вариант можно будет использовать для создания переходов между фотографиями, когда одна из них, распадаясь на точки, открывает находящуюся под ней другую. А с помощью второго можно будет, например, наблюдать за распадом контрастных фигур на белом фоне.

Выбирается центр взрыва. Для каждой точки (кроме центральной) строится прямая, соединяющая эту точку с центральной. Траектория движения точки представляет собой луч, принадлежащий этой прямой, начинающийся в данной точке (поскольку точки у нас — движущиеся, то здесь имеется в виду положение точки в начальный момент времени) и не содержащий центра взрыва.

Исходное изображение считается первым кадром анимации. При переходе от одного кадра к другому каждая из точек "перескакивает" на соседний пиксель так, чтобы двигаться максимально близко к построенной траектории. Каждый кадр строится посредством вычисления новых координат точек и нанесения их на заранее заданное фоновое изображение.

Что представляет собой фоновое изображение? Это зависит от наших задач. Если мы выполняем переход от одной фотографии к другой, то фоновое изображение — это вторая фотография. А если мы наблюдаем за распадом фигур на белом фоне, то фоновое изображение — это просто белый холст.

Как только точка "выходит" за пределы прямоугольного холста, так сразу же мы "забываем" о её существовании. Построение кадров заканчивается, когда на фоновом изображении не останется ни одной точки, принадлежащей исходному изображению. Таким образом, фоновое изображение будет являться последним кадром анимации.

И ещё. Если в центре взрыва находится точка, которая должна участвовать в распаде изображения, то мы её никуда перемещать не будем, а будем считать, что она "сгорает" в первый же момент взрыва. Это означает, что она будет присутствовать только в исходном изображении.

Подведём итоги. Итак, мы должны изначально располагать исходным и фоновым изображениями, фоновым цветом (если он нужен) и центром взрыва. В результате решения задачи мы должны получить анимацию, первый кадр который совпадает с исходным изображением, а последний — с фоновым. А сама анимация должна представлять собой демонстрацию "превращения" первого из них во второе по описанным выше правилам.

Построение траектории движения точки

Самым сложным этапом решения задачи является, пожалуй, построение траектории движения точки или, другими словами, разработка алгоритма, позволяющего определять, в какой именно соседний пиксель должна "перепрыгнуть" точка при переходе от одного кадра анимации к другому. Этот алгоритм мы и сформируем в данном разделе.

Вначале нужно выяснить, что означает понятие "соседний пиксель". Предположим, что холст для рисования изображений расчерчен на квадратные клетки со сторонами единичной длины, а система координат введена таким образом, что оси проходят через середины сторон клеток (см. рисунок). При этом центры клеток имеют целые координаты . Эти клетки и будем отождествлять с пикселями. Договоримся координатами пикселя (клетки) считать координаты центра клетки.

Холст для рисования, разбитый на клетки, с введённой системой координат

Моделирование пикселей квадратными клетками. Оси координат проходят через середины сторон клеток

Соседними клетками будем называть клетки, имеющие хотя бы одну общую вершину. Ясно, что каждая клетка, не лежащая на "краю" холста, соседствует с 8 клетками, 4 из которых имеют общие стороны с данной, а каждая из остальных 4-х — ровно по одной общей вершине. Таким образом, на каждом шаге (т. е. переходе от одного кадра к другому) точка, находящаяся в клетке, должна перейти в одну из 8 соседних клеток. А теперь сформулируем нашу задачу максимально строго.

Пусть С (xCyC) — это центральная точка, а M0 (x0y0) — начальное положение точки, движение которой мы рассматриваем. Предположим, что на некотором кадре наша точка совпала с точкой M1 (x1y1), а на следующим за ним — с точкой M2 (x2y2). Нам нужно научиться по известным координатам точек СM0 и M1 находить координаты точки M2.

Обозначим: Δx = x2 - x1, Δy = y2 - y1 — приращения координат в точке M1. В силу того, эта точка всегда переходит именно в соседнюю клетку, каждое из чисел Δx и Δy может равняться либо -1, либо 0, либо 1; однако одновременно оба они не могут быть нулевыми.

Для двух случаев (назовём их вырожденными) — когда траектория движения параллельна одной из осей координат и когда она наклонена к осям под углом 45°, мы сразу же можем найти Δx и Δy. Вырожденные случаи мы рассмотрим отдельно, а сейчас поговорим обо всех остальных.

Сразу же сделаем важное замечание. Из-за того, что наша точка удаляется от центра взрыва по прямой, проекция отрезка СM1 на любую из координатных осей не может превышать проекцию отрезка СM2 на эту же ось. Это означает, что Δx может быть равно 0 или sign(x0 - xC), а Δy — 0 или sign(y0 - yC), но оба они не могут одновременно быть нулевыми (sign означает знак числа, заключённого в скобках, т. е. 1, если число положительно, -1, если отрицательно и 0, если равно 0).

Таким образом, уже 5 соседних клеток "выходят из игры", т. е. точка в эти 5 клеток попасть заведомо не может. Остаются только 3 клетки, из которых нужно выбрать одну. Из этих трёх клеток одна имеет с исходной ровно одну общую вершину, а две другие — по одной общей стороне.

Одну из этих трёх клеток можно сразу же исключить из рассмотрения. Для того, чтобы понять, как это сделать, представим, что мы построили в графическом редакторе, предназначенном для работы с растровой графикой (например, в Paint'е), отрезок прямой минимально возможной толщины (не в математическом смысле, конечно; мы знаем, что в математике толщина отрезка равна 0). Пусть этот отрезок не параллелен ни одной из сторон холста и не наклонён к сторонам под углом 45°.

Построим на отрезке как на гипотенузе прямоугольный треугольник с катетами, параллельными сторонам холста. Заметим, что наш отрезок состоит из прямоугольников, соединённых "наискосок" (т. е. любые 2 соединённых прямоугольника имеют ровно одну общую вершину).Некоторые из этих прямоугольников, возможно, являются квадратами. А те, которые не являются, — всегда "вытянуты" вдоль большего катета. Другими словами, большая из сторон каждого прямоугольника всегда параллельна большему катету (см. рисунок).

Прямоугольный треугольник

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

Вернёмся к нашей задаче. Клетки, по которым перемещается наша точка, принадлежащие холсту, как раз и будут образовывать отрезок, описанный в предыдущем абзаце, а значит, мы можем воспользоваться сформулированным в нём наблюдением.

Возьмём какой-нибудь отрезок, лежащий на прямой, частью которой является наша траектория, например, СM0, и построим на нём, как на гипотенузе, прямоугольный треугольник. Теперь из трёх упомянутых выше соседних клеток мы можем исключить ту, которая образовывает с исходной клеткой прямоугольник, вытянутый вдоль меньшего из катетов. Длины катетов вычислить несложно: катет, параллельный оси абсцисс, равен |x0 - xC|, а параллельный оси ординат — |y0 - yC|.

Таким образом, мы получаем 2 возможных набора приращения координат. Приращения из первого набора вычисляются по формулам

Δx1 = sign(x0 - xC),
Δy1 = sign(y0 - yC).

Они соответствуют клетке, имеющей с исходной ровно одну общую вершину. А формулы для вычисления приращений из второго набора зависят от того, выполняется ли равенство

|x0 - xC| > |y0 - yC|.

Если да, то Δx2 = Δx1 и Δy2 = 0, а если нет, то Δx2 = 0 и Δy2 = Δy1.

Остаётся из двух возможных клеток выбрать одну. Как это сделать? Очень просто: нужно взять ту, которая ближе к нашей траектории.

Любую прямую на плоскости можно задать общим уравнением

a x + b y + c = 0.

Прямая, которой принадлежит наша траектория, проходит через точки С и M0. Для того, чтобы построить её уравнение, нужно коэффициенты a, b и c, фигурирующие в общем уравнении, выразить через координаты этих точек. Это сделать несложно:

a = y0 - yC,
b = xC - x0,
c = x0 yC - xC y0.

В итоге, искомое уравнение прямой будет иметь вид:

(y0 - yC) x + (xC - x0) y + (x0 yC - xC y0) = 0.

Расстояние ρ(N, α) от любой точки плоскости N(xN, yN) до прямой α, имеющей уравнение a x + b y + c = 0, вычисляется по формуле

ρN,α=axN+byN+ca2+b2.

Поскольку нас интересует только, какое из двух расстояний больше, а какое — меньше, то мы можем ограничиться вычислением и сравнением значений числителя дроби, стоящей в правой части равенства, а не самих расстояний, т .к. знаменатель не зависит от координат точки. Так что нам достаточно подставить в числитель дроби вместо координат точки N координаты двух соседних клеток, соответствующих приращением Δx1, Δy1 и Δx2, Δy2, после чего сравнить два найденных числа.

В итоге, мы получаем следующий способ нахождения Δx и Δy. Предварительно вычислив a, b и c по приведённым выше формулам, находим числа:

|a (x1 + Δx1) + b (y1 + Δy1) + c|,
|a (x1 + Δx2) + b (y1 + Δy2) + c|.

Если первое из них меньше второго, то полагаем: Δx = Δx1, Δy = Δy1. В противном случае имеем: Δx = Δx2, Δy = Δy2. А искомые координаты точки M2 находим по очевидным формулам

x2 = x1 + Δx,
y2 = y1 + Δy.

С вырожденными случаями всё просто. Приращения координат находятся однозначно:

Δx = sign(x0 - xC),
Δy = sign(y0 - yC).

Формулы для нахождения координат точки M2, разумеется, остаются теми же.

Заметим, что если траектория параллельна одной из координатных осей, то одно из приращений будет нулевым, так что одна из координат всегда будет неизменной. А если траектория наклонена к осям под углом 45°, то оба они будут ненулевыми, т. е. обе координаты будут изменяться на каждом шаге.

Кстати, как мы видим, в вырожденных случаях Δx и Δy постоянны, т. е. не зависят от координат точки M1. А в невырожденных они могут изменяться от шага к шагу. При этом, правда, существуют только 2 варианта их значений.

Давайте теперь соберём всю информацию, изложенную в этом разделе, в единый алгоритм получения координат точки M2.

Но для начала нам нужно предварительно вычислить ряд величин. Оформим их вычисление также в виде алгоритма:

  • Шаг 1. Вычисляем: Δx1 = sign(x0 - xC), Δy1 = sign(y0 - yC). Если Δx1 = 0 или Δy1 = 0, то заканчиваем работу.
  • Шаг 2. Если |x0 - xC| = |y0 - yC|, то полагаем: Δx2 = 0, Δy2 = 0 и заканчиваем работу.
  • Шаг 3. Если |x0 - xC| > |y0 - yC|, то полагаем: Δx2 = Δx1, Δy2 = 0 и переходим к шагу 5.
  • Шаг 4. Полагаем:  Δx2 = 0 и  Δy2 = Δy1.
  • Шаг 5. Вычисляем: a = y0 - yC, b = xC - x0, c = x0 yC - xC y0 и заканчиваем работу.

Обратите внимание на то, что на 2-м шаге мы положили Δx2 и Δy2  равными 0. Сделали мы это для того, чтобы в основном алгоритме, установив, что Δx2 = Δy2, мы могли бы сделать вывод о том, что траектория наклонена под углом 45° к осям.

А теперь приведём и сам алгоритм получения координат точки M2.

  • Шаг 1. Если Δx1 = 0 (траектория параллельна оси ординат), то полагаем: x2 = x1, y2 = y1 + Δy1 и заканчиваем работу.
  • Шаг 2. Если Δy1 = 0 (траектория параллельна оси абсцисс), то полагаем: x2 = x1 + Δx1, y2 = y1 и заканчиваем работу.
  • Шаг 3. Если Δx2 = Δy2 (траектория наклонена к осям под углом 45°), то полагаем: x2 = x1 + Δx1, y2 = y1 + Δy1 и заканчиваем работу.
  • Шаг 4. Полагаем: x21 = x1 + Δx1, y21 = y1 + Δy1, x22 = x1 + Δx2, y22 = y1 + Δy2.
  • Шаг 5. Если |a x21 + b y21 + c| < |a x22 + b y22 + c|, то полагаем: x2 = x21, y2 = y21 и заканчиваем работу.
  • Шаг 6. Полагаем: x2 = x22, y2 = y22 и заканчиваем работу.

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

Логично хранить все эти данные в переменной структурного типа (как видите, мы уже начали затрагивать тему реализации). Будем в дальнейшем называть каждую такую переменную переменной-точкой или объектом (когда понятно, что за объект имеется в виду).

Алгоритм построения кадров

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

В качестве исходных данных функция должна принимать набор переменных-точек и фоновое изображение. Она должна сгенерировать кадр и, возможно, удалить из набора те объекты, которые больше не нужны. Новый кадр и новый (возможно) набор объектов и будут являться результатом её работы. Полученный набор, в свою очередь, будет обрабатываться этой же функцией при её следующем вызове. Как только в результате работы функции набор станет пустым, так сразу же вызовы функций прекратятся.

Нам нужно решить, какую именно структуру данных использовать для хранения переменных-точек. Поскольку эта структура должна постоянно менять свой размер в сторону уменьшения, массив не подойдёт. Но вполне подойдут очередь или стек. Мы уже часто использовали стек, поэтому я на этот раз решил испытать "в боевых условиях" недавно созданную библиотеку для работы с кастомизированной очередью, описанную в прошлой статье.

И ещё. Разумным будет использовать сразу две очереди. В начале выполнения функции первая из них будет наполнена переменными-точками, а вторая будет пустой. По мере формирования кадра, объекты из первой очереди, будут "перетекать" из первой очереди во вторую (правда, не все; некоторые будут удаляться). К концу работы функции первая очередь опустеет, а все оставшиеся после удаления объекты окажутся во второй; именно из неё они будут "черпаться" при следующем вызове функции.

А вот и сам алгоритм работы функции, формирующей кадр (первой будем называть изначально полную очередь, а второй — пустую).

  • Шаг 1. Если первая очередь не пуста, извлекаем из неё переменную-точку. В противном случае завершаем работу.
  • Шаг 2. На основании информации, хранящейся в объекте, вычисляем новые координаты точки.
  • Шаг 3. Если новая точка находится за пределами фонового изображения, то переходим к шагу 1.
  • Шаг 4. Наносим точку на фоновое изображение (цвет точки получаем из извлечённого объекта).
  • Шаг 5. Записываем новые координаты в переменную-точку.
  • Шаг 6. Помещаем переменную-точку во вторую очередь и переходим к шагу 1.

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