ASSIGNMENT 4. Assignment 4.1 Задача – Аппроксимировать изображение набором полупрозрачных многоугольников. - презентация

1 ASSIGNMENT 4

2 Assignment 4.1 Задача – Аппроксимировать изображение набором полупрозрачных многоугольников

3 Как это работает? Исходная картинка

4 Как это работает? Аппроксимированная картинка

5 Степень схожести картинок Будем обозначать F(Img1, Img2) Сумма квадратов разностей R, G и B между пикселями двух картинок Img1 и Img2, суммируем по всем пикселям Одна из картинок – исходная, задается извне, подгружается в виде файла Вторая из картинок – некоторый растеризованный набор многоугольников

6 Представление набора многоугольников Многоугольник: – Число точек N, !!! 4 N 10 !!! – Координаты точек (x[1], y[1]) … (x[N], y[N]) – Цвет R,G,B (0 R, G, B 255) – Прозрачность A (0 A 255) Набор многоугольников: – Число многоугольников – Массив многоугольников

7 Как растеризовать набор многоугольников? По аналогии с Assignment 3 CUDA ядро – Синхронизация (индексы многоугольников лежат в shared памяти) – Цикл (по размеру блока) Каждый поток читает многоугольник из глобальной памяти (если надо) Проверяет, пересекает ли данный многоугольник тот пиксел, которому соответствует поток

8 Как растеризовать набор многоугольников? Растеризация многоугольников проводится последовательно согласно порядку следования многоугольников в наборе

9 Многоугольники Число точек в многоугольниках 4 N 10 Нет, только треугольники нельзя Уметь рендерить невыпуклые многоугольники (и с самопересечениями) Алгоритм проверки принадлежности точки многоугольнику: – Гуглить «point inside polygon» – Книга Шикина и Борескова «Компьютерная графика. Полигональные модели», раздел 8.5. – Википедия Координаты точек многоугольника лежат в пределах границ исходной картинки

10 Как все это работает? Разгрузить исходное изображение Img Пусть A – набор многоугольников, с которым мы работаем, изначально A – пуст Растеризовать A в ImgA, пусть best=F(Img, ImgA) Цикл: – Скопировать A в новый набор многоугольников B – «Немножко поменять» B – Растеризовать B в ImgB, пусть check=F(Img, ImgB) – Если check < best, то best = check A = B

11 «Немножко поменять» Извне задается вероятность p выполнения операций (по умолчанию, p=0.001) С вероятностью p выполняется каждая из следующих операций над многоугольниками набора: – Добавить случайный многоугольник в набор – Удалить случайный многоугольник из набора – Случайно изменить порядок отрисовки одного из многоугольников (т.е. передвинуть элемент массива) – Добавить точку в середину случайного ребра в случайный многоугольник (если позволяет число точек) – Удалить случайную точку случайного многоугольника (если позволяет число точек)

12 «Немножко поменять» С вероятностью p выполняется каждая из следующих операций над многоугольниками набора (продолжение): – Изменить каждую из координат случайной точки случайного многоугольника (ненамного, в районе 1-20 пикселей) – Изменить каждую из координат случайной точки случайного многоугольника (выбрать случайно в пределах границ исходной картинки) – Изменить R, G, B или A случайно выбранного многоугольника (т.е. rnd() * 255) – Сдвинуть все точки случайного многоугольника разом (ненамного, в районе 1-20 пикселей по каждой коорд-те) – Если не лень, то придумать что-нибудь свое (… PROFIT)

13 Если все работает правильно Как все эволюционирует (если нет глюков)

14 Исходная картинка Любое более-менее приличное изображение

15 Assignment 4.2 Задача – Аппроксимировать изображение набором полупрозрачных многоугольников (4.1) – Использовать CUDA + openMP (или MPI) на Tesla сервере Входное изображение разбивается на куски, и каждый кусок обрабатывается на своем GPU

16 Общие правила по оформлению программ Если сдаете по – ДОЛЖЕН быть с темой CUDA ASSIGNEMENT 2011.N (N - номер задания, в данном случае 4) Задание сложное – Срок – 17 Мая – Не откладывайте с вопросами Недвусмыслен ный намек от кэпа

17 Общие правила по оформлению прорамм – Программа должна делать проверки на ошибки: Наличие девайса? Выделилась память? И т.д. – Программа должна компилироваться с CUDA Toolkit 3.2 Если писали на windows то vcproj для VS2005 / VS2008 либо (makefile +.bat) Если писали на *nix то make

18 Общие правила по оформлению программ Если вы используете любые другие инклюды кроме стандартных – не расчитывайте, что они прописаны на проверяющей машине. Пример того, чего не будет на машине: – cutil.h (требует установки CUDA SDK) Пример того, что будет на машине: – cudart.h (ставиться вместе с CUDA toolkit) – stdio.h (стандартная C библиотека) – thrust – cufft

19