ASSIGNMENT 4
Assignment 4.1 Задача – Аппроксимировать изображение набором полупрозрачных многоугольников
Как это работает? Исходная картинка
Как это работает? Аппроксимированная картинка
Степень схожести картинок Будем обозначать F(Img1, Img2) Сумма квадратов разностей R, G и B между пикселями двух картинок Img1 и Img2, суммируем по всем пикселям Одна из картинок – исходная, задается извне, подгружается в виде файла Вторая из картинок – некоторый растеризованный набор многоугольников
Представление набора многоугольников Многоугольник: – Число точек N, !!! 4 N 10 !!! – Координаты точек (x[1], y[1]) … (x[N], y[N]) – Цвет R,G,B (0 R, G, B 255) – Прозрачность A (0 A 255) Набор многоугольников: – Число многоугольников – Массив многоугольников
Как растеризовать набор многоугольников? По аналогии с Assignment 3 CUDA ядро – Синхронизация (индексы многоугольников лежат в shared памяти) – Цикл (по размеру блока) Каждый поток читает многоугольник из глобальной памяти (если надо) Проверяет, пересекает ли данный многоугольник тот пиксел, которому соответствует поток
Как растеризовать набор многоугольников? Растеризация многоугольников проводится последовательно согласно порядку следования многоугольников в наборе
Многоугольники Число точек в многоугольниках 4 N 10 Нет, только треугольники нельзя Уметь рендерить невыпуклые многоугольники (и с самопересечениями) Алгоритм проверки принадлежности точки многоугольнику: – Гуглить «point inside polygon» – Книга Шикина и Борескова «Компьютерная графика. Полигональные модели», раздел 8.5. – Википедия Координаты точек многоугольника лежат в пределах границ исходной картинки
Как все это работает? Разгрузить исходное изображение Img Пусть A – набор многоугольников, с которым мы работаем, изначально A – пуст Растеризовать A в ImgA, пусть best=F(Img, ImgA) Цикл: – Скопировать A в новый набор многоугольников B – «Немножко поменять» B – Растеризовать B в ImgB, пусть check=F(Img, ImgB) – Если check < best, то best = check A = B
«Немножко поменять» Извне задается вероятность p выполнения операций (по умолчанию, p=0.001) С вероятностью p выполняется каждая из следующих операций над многоугольниками набора: – Добавить случайный многоугольник в набор – Удалить случайный многоугольник из набора – Случайно изменить порядок отрисовки одного из многоугольников (т.е. передвинуть элемент массива) – Добавить точку в середину случайного ребра в случайный многоугольник (если позволяет число точек) – Удалить случайную точку случайного многоугольника (если позволяет число точек)
«Немножко поменять» С вероятностью p выполняется каждая из следующих операций над многоугольниками набора (продолжение): – Изменить каждую из координат случайной точки случайного многоугольника (ненамного, в районе 1-20 пикселей) – Изменить каждую из координат случайной точки случайного многоугольника (выбрать случайно в пределах границ исходной картинки) – Изменить R, G, B или A случайно выбранного многоугольника (т.е. rnd() * 255) – Сдвинуть все точки случайного многоугольника разом (ненамного, в районе 1-20 пикселей по каждой коорд-те) – Если не лень, то придумать что-нибудь свое (… PROFIT)
Если все работает правильно Как все эволюционирует (если нет глюков)
Исходная картинка Любое более-менее приличное изображение
Assignment 4.2 Задача – Аппроксимировать изображение набором полупрозрачных многоугольников (4.1) – Использовать CUDA + openMP (или MPI) на Tesla сервере Входное изображение разбивается на куски, и каждый кусок обрабатывается на своем GPU
Общие правила по оформлению программ Если сдаете по – ДОЛЖЕН быть с темой CUDA ASSIGNEMENT 2011.N (N - номер задания, в данном случае 4) Задание сложное – Срок – 17 Мая – Не откладывайте с вопросами Недвусмыслен ный намек от кэпа
Общие правила по оформлению прорамм – Программа должна делать проверки на ошибки: Наличие девайса? Выделилась память? И т.д. – Программа должна компилироваться с CUDA Toolkit 3.2 Если писали на windows то vcproj для VS2005 / VS2008 либо (makefile +.bat) Если писали на *nix то make
Общие правила по оформлению программ Если вы используете любые другие инклюды кроме стандартных – не расчитывайте, что они прописаны на проверяющей машине. Пример того, чего не будет на машине: – cutil.h (требует установки CUDA SDK) Пример того, что будет на машине: – cudart.h (ставиться вместе с CUDA toolkit) – stdio.h (стандартная C библиотека) – thrust – cufft