Морфинг

При решении задачи главной частью алгоритма было перенесение изображения из одного треугольника в другой треугольник(сводится к задаче интерполяции параметра в треугольнике). Задача заключается в нахождении значения параметра в любой точке внутри треугольника,зная значения этого параметра в вершинах треугольника и координаты этой точки. Пусть дан треугольник с координатами вершин (x1,y1),(x2,y2),(x3,y3) и интерполируемыми параметрами c1, c2 и c3 соответственно для вершин треугольника. Найдем функцию F(c1,c2,c3,x,y),которая для точки с координатами x,y возвращает значение интерполируемого параметра.Представим,что есть плоскость,проходящая через точки (x1,y1,c1),(x2,y2,c2) и (x3,y3,c3) в пространстве и c1,c2,c3 это Z-координата вершин треугольника.Можем записать уравнение этой плоскости Ax+By+Cc+D=0,где A,B и C это координаты вектора нормали к этой плоскости.
A = (y2-y1)*(c3-c1)-(y3-y1)*(c2-c1);
B = -(x2-x1)*(c3-c1)+(x3-x1)*(c2-c1);
C = (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
Зная уравнение плоскости и то,что точки (x,y,c) и (x1,y1,c1) принадлежат этой плоскости вычтем из уравнения Ax+By+Cc+D=0 уравнение Ax1+By1+Cc1+D=0, чтобы избавиться от коэффициента D. Получим уравнение A(x-x1)+B(y-y1)+C(c-c1)=0 из него получим c=c1-(A/C)(x-x1)-(B/C)(y-y1); Вот,собственно,задача интерполирования параметра и решена. Для того,чтобы пройти по всем точкам треугольника(а это нужно сделать для переноса изображения) я использую следующий алгоритм.
Пусть вершинами треугольника являются точки с координатами (i1,j1),(i2,j2),(i3,j3) и нам нужно перебрать все точки внутри треугольника по одному разу.Для этого вычислим Minj=min(j1,j2,j3) и Maxj=max(j1,j2,j3),заведем массивы Mini[j] и Maxi[j] и заполним их при помощи какого-нибудь алгоритма рисования растрового отрезка(я использовал целочисленный алгоритм Брезенхейма).Затем мы можем пройти двойным циклом :
for j := minj to maxj do
for i := mini[j] to maxi[j] do something(i,j)
при этом процедуре something(i,j) будут подвергнуты все точки треугольника. Для перенесения закраски я использовал следующий алгоритм: перебираю все точки второго треугольника(пусть его координаты равны (i1,j1),(i2,j2),(i3,j3) и для каждой из них определяю точку ,которая соответствует ей в первом треугольнике. Для этого использую функцию F,выведенную ранее. Где для определения X-координаты в качестве параметров c1,c2 и c3 подставляю i1,i2,i3, то есть xnew = F(i,j,i1,i2,i3); так же найдем и Y-координату ynew = F(i,j,j1,j2,j3); после определения этих координат остается только "взять" точку с координатами (xnew,ynew) и нарисовать ее как точку с координатами (i,j).
Для того чтобы делать плавный переход от одной картинки к другой нужно еще знать какие треугольники в какие нужно "двигать"(нужно построить триангуляцию).В моей программе пользователь работает не с треугольниками,а с четырехугольниками. Пользователь может создавать вертикальные и горизонтальные линии сетки и затем двигать точки их пересечения,задавая участки первой картинки(ограниченные сторонами четырехугольника),которые должны будут переводится в соответствующие им участки второй картинки. Все четырехугольники сетки разбиваются на треугольники по диагонали(по этому к пользователю есть одно правило построения сетки для корректного морфирования "Четырехугольники должны быть выпуклыми и, по возможности, близкими к квадрату" иначе могут получаться нежелательные эффекты). При морфировании нужно знать количество кадров создаваемого мультика и должны быть известны треангуляции. Если все это известно, то построение N-го кадра мультика состоит из следующих шагов:

Построить промежуточную триангуляцию(это я сделал при помощи линейной интерполяции параметра.Если известны два числа,например x1 и x2 и нужно перейти от x1 к x2 за K шагов ,то на K1 шаге (1
Создать промежуточную картинку путем сдвига первой картинки при помощи построенной триангуляции и триангуляции,заданной пользователем.
Проделываем ту же работу,но уже со второй картинкой
Подсчитываем цвета путем линейной интерполяции номеров цветов.

После этого получаем готовый N-й кадр мультика. Этот алгоритм используется, если нужно сделать мультик путем перевода различных картинок(MORFING). Если нужно просто исказить одну картинку и сделать несколько промежуточных кадров, то применяется другой алгоритм (warping).
Он состоит только из первого и второго пунктов предыдущего алгоритма.Для warping'а в программе предусмотрен режим просмотра изображения(введен по двум причинам:

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

Пример реализации можно посмотреть в проекте "Морфинг".

[Назад]

Reklama