Свой Flash на HTML5: объединение векторных изображений (ч.1)

Давным-давно, в далёкой-далёкой галактике (т.е. больше года назад и за пределами дефолт-сити) один web программист решил написать свой Flash ^[1] (был он не без мании величия, конечно). Задача тогда казалась непростой и очень интересной. В данной статье пойдёт речь об одной из проблем, которые встали у него на пути.
Те, кто рисовал во Flash знают, что в нём фигуры (закрашенные области) в пределах одного слоя никогда не перекрываются, а линии всегда рисуются поверх закрашенных фигур. У такого подхода есть, на мой взгляд, хороший плюс — ты имеешь на изображении то, что видишь. Однако, при написании векторного редактора это приводит к необходимости решения задачи корректного наложения рисуемых объектов (линий и закрашенных фигур) на уже существующие. Ниже я попытаюсь поэтапно показать, как это можно сделать.

Для простоты, далее я буду называть полигонами закрашенные области, ограниченные прямыми отрезками и квадратичными кривыми Безье. Как правило, при упоминании рёбер, я буду иметь в виду видимые нарисованные прямые или кривые отрезки (stroke lines).

Исходные данные

Итак, у нас есть два изображения, которые мы хотим объединить. Каждое задано набором рёбер и полигонов.

Вот что мы знаем о рёбрах:

• могут быть прямыми отрезками;
• могут быть кривыми Безье;

  Квадратичная кривая Безье — простейший случай, когда кривая имеет одну контрольную точку и, по сути, рисуется внутри треугольника, заданного тремя своими вершинами. Отличная иллюстрация с Википедии:
• каждое ребро имеет свой цвет;
• никакие два ребра не пересекаются (но могут, конечно, иметь общую начальную или конечную точку);
• никакие два ребра не совпадают.

Так, на рисунке справа можно увидеть 5 рёбер: два голубых и три тёмно-жёлтых.

А вот что мы знаем о полигонах:

• ограничены прямыми или кривыми отрезками;
• никогда не пересекаются;
• могут примыкать друг к другу, т.е. иметь общую границу (в этом случае, цвета полигонов должны различаться, либо граница должна быть явно выделена рёбрами; таким образом, не должно быть полигонов, которым ничто не мешает объединиться в один);
• имеют свой вариант заливки (в простейшем случае — цвет);
• могут быть полупрозрачными (цвет можно задать с указанием alpha-канала);
• могут быть невыпуклыми;
• могут иметь «дырки» (т.е. области, заданные прямыми/кривыми отрезками, где заливка отсутствует).

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

Подзадачи

Понятно, что нахождение объединения двух векторных изображений является сложной задачей, а потому стоит разбить её на несколько подзадач. Вот что у меня получилось:

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

В результате всех этих действий в исходном изображении мы должны получить искомый результат объединения.

Думаю понятно, что каждая из подзадач представляет из себя, порой, нетривиальную проблему. Поэтому рассмотрим их отдельно.

Поиск пересечения двух отрезков

Отрезки у нас бывают разные, так что рассмотрим три возможных случая отдельно.

Оба отрезка прямые

Как известно, найти пересечение двух прямых отрезков не представляет особой сложности, стоит лишь помнить, что при вычислениях удобно представлять их в параметрическом виде (формулы вида y=kx+b имеют фатальный недостаток: быстро теряют точность при приближении отрезка к вертикальному положению, а для вертикальных отрезков требуют отдельного рассмотрения):

// M - точка на отрезке, S - начало отрезка, D - конец отрезка, t - значение из диапазона [0; 1]
M1 = S1 + (D1-S1) * t1 // параметрическое представление первого отрезка
M2 = S2 + (D2-S2) * t2 // параметрическое представление второго отрезка

// Пересечение - это когда M1 = M2 - получаем систему уравнений,
// из которой мы добудем значение t1:
Xs1 + (Xd1-Xs1) * t1 = Xs2 + (Xd2-Xs2) * t2
Ys1 + (Yd1-Ys1) * t1 = Ys2 + (Yd2-Ys2) * t2

Не буду описывать вывод t1 (думаю, здесь без особого труда справится каждый). После получения значения t1 нужно убедиться, что оно лежит в интервале [0; 1] (в противном случае отрезки не пересекаются), после чего можно подставить его в формулу, задающую первый отрезок, получив таким образом координаты точки пересечения:

Xm = Xs1 + (Xd1-Xs1) * t1
Ym = Ys1 + (Yd1-Ys1) * t1

Кривая Безье и прямой отрезок

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

// P0, P1, P2 - точки, задающие кривую; t - значение из диапазона [0; 1]
M1 = (1-t1)^2 * P0 + 2*t1*(1-t1) * P1 + t1^2 * P2 // параметрическое представление кривой

// S - начало отрезка, D - конец
M2 = S + (D-S) * t2 // параметрическое представление прямого отрезка

// поворачиваем точки P0, P1, P2, S и D на угол a = -atan2(Yd-Ys, Xd-Xs);
// ниже расположены известные формулы для такого поворота
// (точка, заданная координатами (X, Y) переходит в точку (Xn, Yn))
Xn = X*cos(a) - Y*sin(a) 
Yn = X*sin(a) + Y*cos(a)

// формула кривой не изменилась (изменились только значения P0, P1 и P2)
Xm1 = (1-t1)^2 * Xp0 + 2*t1*(1-t1) * Xp1 + t1^2 * Xp2
Ym1 = (1-t1)^2 * Yp0 + 2*t1*(1-t1) * Yp1 + t1^2 * Yp2

// формула прямого отрезка упростилась для координаты Y:
Xm2 = Xs + (Xd-Xs) * t2
Ym2 = Ys // т.к. после поворота у нас Ys = Yd

// M1 = M2, т.е.
Xm1 = Xm2
Ym1 = Ym2

// достаточно рассмотреть только формулу для Y, т.к. именно там имеется упрощение:
(1-t1)^2*Yp0 + 2*t1*(1-t1)*Yp1 + t1^2*Yp2 = Ys

Решив это квадратное уравнение, мы найдём значения t1 (а их может быть два). Для каждого значения t1, как и в случае с прямыми отрезками, стоит убедиться, что оно лежит в пределах [0; 1]. Подставив значения t1 в исходную (до поворота) формулу кривой, получим координаты искомых точек пересечения.

Две кривые Безье

Аналитически вычислить точки пересечения двух квадратичных кривых Безье (а таких точек может быть до 4-х штук) очень не просто: сложность настолько высока, что в негодование приходит даже MathCAD, выдавая сообщения о слишком длинных формулах. Также, на сколько я понимаю ситуацию, в этом случае придётся поработать с комплексными числами. К счастью, существуют численные итеративные методы получения точек пересечения произвольных кривых с заданной точностью. Тут всё просто:

1. если рассматриваемые отрезки имеют размер меньше заданной точности — аппроксимируем их прямыми и считаем их пересечение;
2. если хотя бы один из отрезков больше точности — бьём его на две (более-менее равные) части и рекурсивно применяем алгоритм для полученных отрезков.

Здесь можно ввести оптимизацию: предварительно проверять могут ли отрезки в принципе пересекаться (например, используя ограничивающие прямоугольники) и если нет, то прекращать текущую ветвь рекурсии.

Момент, который может вызвать затруднение — разбиение кривой Безье на две части (т.е. вычисление новых контрольных точек; определить конечную точку первой кривой, совпадающую с начальной точкой второй кривой, легко, подставив в формулу кривой t=0.5). Как оказалось, для этого достаточно вычислить координаты центров отрезков, задающих опорный треугольник — полученные точки и будут контрольными точками для новых кривых. Рисунок слева иллюстрирует решение: кривая (P0, P1, P2) разбивается на две кривых, опорный треугольник первой из них (P0, P1', P2') выделен синим. Контрольная точка второй кривой (P2', ..., P2) вычисляется совершенно аналогично.

Продолжение следует…

Автор: yar3333

Источник ^[2]