Graphics & Media Lab. >> Курсы >> Курс Ю.М.Баяковского 2001

Компьютерная графика
О курсе
О курсе
Лекции
Лекции
Практикум
Практикум
FAQs
FAQs
Оценки
Оценки
Глоссарий
Глоссарий
Литература
Литература
 
HW1: Множество Мандельброта 
Начало: 14 февраля 2001 года
Конец:     1 марта 2001 года

1.1. Множества Жюлиа

Будем рассматривать последовательности комплексных чисел {Zn}. Возьмем произвольное комплексное число c. Теперь для любого комплексного числа k рассмотрим последовательность {Zn(k)}:

    Z0 = k,
    Zi+1= Zi2 + c

Зададим себе вопрос: сходится ли Zn к нулю или стремится к бесконечности при n стремящемся к бесконечности? Пусть J – множество всех комплексных чисел {k}, таких что {Zn(k)}стремится к 0, при n стремящемся к бесконечности.  Если теперь мы возьмем все такие k и отобразим их на комплексной плоскости, то получим множество Жюлиа. Меняя c, мы получим бесконечный набор фантастических само подобных образов – множеств Жюлиа.

1.2. Множество Мандельброта

Рассмотрим набор множеств Жюлиа и зададимся вопросом: связно ли данное конкретное множество Жюлиа? Пусть M – множество всех множеств Жюлиа, которые связны. Это множество и называется множеством Мандельброта.

Теперь возьмем любое множество Жюлиа J, и комплексное число c, которое его породило. Если J содержится в M, то изобразим точку черным на комплексной плоскости, в противном случае белым. Это и дает нам того “своеобразного снеговика“, которого вы уже наверное видели миллион раз. Его - то мы и будем генерировать.

К счастью, есть более легкий путь изображения множества Мандельброта, чем рисование каждого множества Жюлия и выяснения, связно ли оно. Наш метод будет очень близок к построению множеств Жюлиа. Опять рассмотрим итерационную последовательность для любого k, и выясним, сходится ли она к нулю.

Zi+1= Zi2 + c

Заметим, что c здесь уже не константа.Для любой точки комплексной плоскости мы c присваиваем значение kи выполняем итерации. Этот метод, как ни странно, дает нам то же изображение множества Мандельброта. Итак, алгоритм:

For each point k on the complex plane do:
    let x=0.
    repeat infinite times:
        x = x2 + k.
    end repeat
    if x goes to infinity,
        k is not in the set. Color is white.
    else
        k is in the set. Color is black.

Понятно, что бесконечных циклов быть не должно. Поэтому возьмем некоторое большое число I и проитерируем I раз. Чем большее I мы взяли, тем, разумеется, точнее ответ мы получим. Из практики, число 4000 дает довольно хороший результат. Да, но 4000 раз “крутить“ цикл для каждого пиксела изображения, это многовато. К счастью, мы можем воспользоваться результатами многолетней работы математиков в этой области. Оказывается, если в любой конкретный момент вычислений, для k расстояние от zi(k) до начала координат больше 2, то мы можем принять, что данная {Zn(k)} уйдет в бесконечность. (При сравнении: расстояние < 2, поэтому его квадрат меньше 4 и корень извлекать не нужно.) Итак, теперь наш алгоритм выглядит так:

For each point k in the complex plane do:
    let x=0.
    repeat 4000 times
        let x=x2+k
        if x2 > 4 then
            Color it white
            Break
    end repeat
    if we reached 4000 then
        Color is black.

Этот метод дает нам черно-белое изображение множества Мандельброта. Теперь надо подумать о том, как сделать его разноцветным.

1.3. Цветное изображение

Если точка принадлежит множеству Мандельброта, то с ней все ясно – рисуем ее черным. Но как быть с точками, не принадлежащими множеству? Общепринятый способ выбора цвета для них – это выбирать цвет в соответствии с тем, как быстро {Zn(k)} стремится к бесконечности (на какой итерации мы ее исключаем из рассмотрения). Например, точка, для которой расстояние до начала координат больше 2 уже на третьей итерации, должна быть почти белой, а та точка, которая “продержалась“ до 3995 итерации – почти черной. Перепишем алгоритм для изображения в градациях серого:

For each point k in the complex plane do:
    let x:=0.
    for i:=0 to 4000
        let x=x2+k
        if ( |x|2> 4) then
            Color point k color i
            Break;
        end if
    end for
    if (i=4000)
        Color of point k is black.
    end if

Конечно, просто рисовать точку цветом i мы не можем. Считая, что у нас есть только 256 градаций серого, а i меняется до 4000. Нам надо как-то отображать i на доступный нам диапазон цветов. Эту проблему мы оставляем вам. После того, как мы получили приличное изображение в градациях серого, очень легко чуть изменить алгоритм для получения цветного изображения. Например, в изображении в градациях серого, если точка вышла из области на n-ой итерации, вы можете рисовать ее цветом (n, n, n). Можете попробовать и что-нибудь поинтереснее типа (n, 255 – n, 50 mod n * 3). Оставляем простор для вашей фантазии. И последнее: обычно, все множество Мандельброта расположено от -2 до 0.5 по действительной оси и от –1.25 до 1.25 по мнимой оси. Ваша программа не должна тестировать точки далеко за пределами этой области. Теперь можно посмотреть пример. Надеемся, что вам удастся сделать что-нибудь поинтереснее.

Требования

Итак, ваша программа должна генерировать цветное изображение множества Мандельброта с приемлемой точностью (где цвет должен отражать то, как быстро расходится итерационная последовательность для данной точки). Полностью выполненная и вовремя представленна работа оценивается 7-ю баллами. 

Как дополнение, вы можете сделать следующее: позволить пользователю увеличивать любые части изображения, щелкая на них мышкой соответствующую прямоугольную область на картинке (за это будут даваться поощрительные баллы). Можно также расчитывать на дополнительные баллы, если  картинка сохраняется в BMP-файле. Если ваша программа работает долго, выводите на дисплей какого-либо вида индикатор, показывающий как продвигается работа и сколько еще ждать до ее окончания. Попытайтесь организовать циклическую смену цветов в палитре и, таким образом, создать своего рода "анимацию". Каждой точке в множестве Мандельброта соответсвует множество Жюлиа. При указании на некоторую точку в множестве Мандельброта, покажите какое множество Жюлиа ей соответствует. За счет этих дополнительных возможностей  оценка может увеличиться до 10 - 12 баллов. 

Сдача

Дата сдачи: 1 марта.

Присылать задания по e-mail: assign1@graphicon.ru в следующем виде: .zip файл с именем, построенным следующим образом: 
имя начинается с цифры - это последняя цифра в номере вашей группы (например, если у вас 206 группа, то название файла будет начинаться с цифры 6), дальше- первые три буквы вашей фамилии (латинским шрифтом), далее - знак подчеркивания и три первые буквы имени (латинским шрифтом). 
Пример: Иванов Андрей из 202 группы должен прислать нам .zip файл с именем: 2iva_and.zip. 
Теперь о том, какие файлы должен содержать ваш .zip - файл: 
первое - исходники
второе - *.exe - файл 
третье !!! - файл readme (что работает, что не работает, что дополнительно реализовано, какая операционная система использовалась, и т.п.)
Внимание: номер задания и его название, фамилия и  имя автора, номер группы, дата - суть обязательные атрибуты READ.ME. Та же информация должна как комментарий содержаться в исходных текстах программы.

Если у вас нет возможности воспользоваться электронной почтой, вы можете записать ваш .ZIP файл на дискету и принести ее в комн. 703 после лекции 2-го марта в 16:15.

На основную
На главную
 
Graphics & Media Lab. >> Библиотека | Курсы | Графикон
 
Hosted by Graphics & Media Lab
http://graphics.cs.msu.su
lab_logo
Дизайн: Алексей Игнатенко
Поддержка: Ольга Соловьева