- 4INT -------------------------------------------- It's interesting -
Msg : 152 of 200 Addr Date
From : Lout Roman 2:463/586.20 23.11.97
Subj : Морфинг
----------------------------------------------------------------------
---> Hi Dmitry! <---
[Втp Hоя 18 1997, 22:26], Dmitry Sorvachev нашкрябал All:
DS> Кто может помочь с алгоpитмом 2D моpфинга (плавный пеpеход одной
DS> каpтинки в дpугую)? У кого-нибудь есть инфоpмация по этому вопpосу
DS> на _pусском_ языке?
Статья писалась для жуpнала, так что извиняюсь за некотоpое
"pазжевывание" понятных вопpосов.
Sincerely Yours, ++AX
---
* Origin: ћДа мне за это шнобелевскую премию должны были дать !
{> Cut here. FileName= MORPHING.TXT }
MORPHING
В наши дни по телевидению в рекламе, фильмах, просто заставках
можно увидеть эффект "переливания" одного изображения в другое
- "морфирование изображений". Будь то превращение человекаобо-
ротня в волка, галлерея лиц в клипе Майкла Джексона, трансфор-
мация Терминатора 2 - действие происходит так плавно, что даже
трудно уловить, на каком мгновении предмет потерял все признаки
предыдущей формы и приобрёл новые. Как же это делается ?
Морфинг - это плавное "превращение" одного изображения
в другое, во время которого конкретный элемент первого изобра-
жения "перетекает" в элемент второго изображения. Hапример, при
морфировании одного автомобиля в другой, колесо первого превра-
щается в колесо второго. Компьютер не может выполнить морфинг
двух изображений самостоятельно - сначала художнику требуется
задать соответствие элементов первого изображения элементам
второго а также другие параметры, пользуясь специальным редак-
тором. Способ задания соответствия зависит от редактора - это
могут быть точки, линии, полигоны. Сам морфинг можно разбить на
три части: warping, tweening и dissolving.
Warping (коробить, искривлять) - преобразование изобра-
жения, при котором оно в отдельных областях сжимается и растя-
гивается - как буд-то изображение нанесено на резину. Расчёт
каждой точки этого изображения осуществляется по математическим
формулам в зависимости от соответствия элементов изображения,
которое задал художник. Во время warping'а элеметны изображения
пытаются принять положение и форму элементов второго изображе-
ния.
Tweening (построение промежуточных кадров) - интерполя-
ция двух изображений для получения плавной анимации. апример,
если соответствие элементов изображений задано точками, то ин-
терполяцией положений точек можно получить промежуточные соот-
ветствия.
Dissolving (растворять, в кино cross-dissolving - за-
темнение одной сцены и осветление другой) - слияние двух изоб-
ражений, при котором в качестве цвета каждой точки нового изоб-
ражения берётся смесь цветов соответствующих точек двух исход-
ных изображений в заданной пропорци.
Рассмотрим как пример морфирование авто мобилей:
[skiped]
Рис. 1.
При warping'е один автомобиль пытается принять форму другого
(в результате, конечно, ничего хорошего не получается):
[skiped]
Рис. 2.
Tweening применяет warping для интерполированных точек, то есть
позволяет получить промежуточные фазы (вверху показаны конечные
кадры). Dissolving обьединяет два полученных изображения в од-
но. В целом при морфинге первый атомобиль плавно пытается при-
нять форму второго, а второй, приняв форму первого, пытается
вернуться к нормальной форме. Dissolving смешивает изображения,
при этом изображение первого автомобиля постепенно затухает, а
второго - появляется.
АЛГОРИТМЫ
Алгоритм зависит от требуемого качества, скорости и
способа задания соответствия элементов изображений. Удобно за-
давать соответствие пользуюясь сеткой (mesh), например:
[skiped]
[Фотогpафия, накотоpую наложена сетка из четыpёхугольников]
Рис. 3.
Плотность сетки влияет на скорость вычислений, требования к па-
мяти, качество получаемого изображения. Редактор, предоставляю-
щий другие способы задания соответствий, дожен привести их к
сетке. Художник, работая с редактором, может вообще не подозре-
вать о том, что в конечном счёте всё задаётся таким образом
(вообще говоря, чем лучше редактор этот факт скрывает, тем он
удобнее).
Сетка задаётся узлами, и именно эти узлы (точки) при
tweenig'е плавно движутся от своего первого положения во вто-
рое, то есть tweening морфирует сетку. Warping осуществляется в
соответствии с начальной сеткой и сеткой, полученной для данно-
го кадра. Для узловых точек это легко: мы знаем, что в исходной
сетке узел находился в точке (x,y) с цветом с. Значит в требуе-
мой картинке точка, в которой теперь находится узел, имеет цвет
c. Для остальных точек несколько сложнее: тут применяется били-
нейная или бикубическая интерполяция.
В алгоритме, предоженном Douglas Smithe для создания
спецэффектов к фильму "Willow" (1988), применятся двух проход-
ное преобразование изображения: в начале изображение деформиру-
ется по x, а затем по y. Объясню на примере :
[описание алгоpитма skiped. Без pисунков все pавно не понять,
да и не нужен он тебе - используй описанный ниже]
Hа деформацию сетки действуют ограничения:
её ячейки не должны накладываться друг на друга, и боковые узлы
не должны двигаться, иначе нельзя будет построить однозначную
сплайн-функцию. В более сложных алгоритмах в узлах сетки можно
задавать дополнительные параметры - например, скорость
dissolving'а, таким образом регулируя нежелательное быстрое по-
явление светлых частей второго изображения и т.п. Реализацию
этого алгоритма можно найти в интернете - файл morfsrc.zip. К
сожалению использовать исходные тексты на PC не удаётся из-за
различия расположения старших/младших байт на PC и sun SPARC
workstation, для которой они написаны.
В РЕАЛЬHОМ ВРЕМЕHИ ?
"Я смотрел демку Heart-Quake/Iguana (ftp.cdrom.com
pub/demos/demos/1994/heartq.zip) - они делают морфинг в реаль-
ном времени. Вышеописанный алгоритм слишком медленный для это-
го. Как у них это получается, причём быстро даже на 486DX33 ?".
Как точно сделано с демке, я не могу сказать. Однако идея, ко-
торую я покажу в исходных текстах, будет визуально именно тем,
что нам показала Iguana.
Прежде всего - только линейная интерполяция. Это значи-
тельно снижает объём вычислений, в тоже время не сильно влияя
на качество изображения при удачно заданном соответствии точек.
Далее - работа в 256 оттенках серого. В связи с такими ограниче-
ниями можно применить некоторую хитрость: работать не с точками
изображения, а с целыми ячейками сетки. Действительно: доста-
точно четырёхугольник изображения, являющийся ячейкой первой
сетки, преобразовать в четырёхугольник, которым он стал в теку-
шей сетке - и мы автоматически получаем нужное деформированное
изображение. С процедурой, выполняющей такое преобразование,
знаком каждый, кто занимается программированием трёхмерной гра-
фики. Это так называемый линейный маппинг изображения. Hа вход
процедуре даются вершины исходного четырёхугольника на текстуре
(картинке, ниже - s_polybmp), указатель на саму картинку, коор-
динаты вершин требуемого четырёхугольника на экране (s_poly2d).
Сама процедура здесь не описывается - это тема отдельной
статьи.
С dissolving'ом всё просто: цвет точки определяется по
формуле c=c1+(c2-c1)*t, 0<t<1, где с1 и c2 - цвета точки первой
и второй картинки, t - фаза морфинга. Ксати, для цветного изоб-
ражения выполняется тоже самое для составляющих RGB. Что каса-
ется Heart-Quake, там нахождение цвета точки (индекса в палит-
ре) выполняется, судя по всему, по заранее просчитанной таблице
c=ColTable[c1,c2,t] размер которой для t=0..20 составляет
256*256*20=1310720 байт (!). Однако размеры таблицы можно зна-
чительно уменьшить, если заставить оба изображения использовать
не все цвета палитры, а, например, - 64. Это требует таблицу
всего 81Кб (при этом остальные цвета палитры используются для
представления промежуточных цветов). Вы заметили, какой сильный
dithering на фотографиях в Heart-Quake ?
Исходные тексты для Borland Pascal 7.0 for DPMI. Расс-
читаны на работу с картинками 256x256 и сеткой 9x9. Из-за боль-
ших размеров текст некоторорых процедур не приводится - в этом
месте ставится соответствующий комментарий. Все процедуры моду-
ля myvesa и описание редактора сеток не приводится.
Ссылки.
1. morphscr.zip "MESHWARPING ALGORITHM FOR MORPHING IMPLEMENTED IN C
by George Wolberg".
2. DEMO.DESIGN.* Frequently Asked Questions, Release 9
(С) Peter Sobolev, 2:5030/84@fidonet.
3. Demo Heart-Quake/Iguana
(ftp.cdrom.com pub/demos/demos/1994/heartq.zip)
4. Demo Stars/Noon (ftp.cdrom.com pub/demos/demos/1995/n/nooon_st.zip)
|
Roman Lout
