Фрактал Мандельброта.
(c) Alone Coder
Тут некоторые знакомые меня достали во-
просами, что такое фрактал и зачем он ну-
жен. На второй вопрос ответить я не смогу,
но на первый отвечу прямо здесь и как мож-
но полнее! Хотя эти знакомые всё равно
спектрумовских журналов не читают!
1.
Фракталом называется фигура или узор,
сохраняющая(-ий) сложную структуру при ма-
сштабировании в произвольное количество
раз. Такие фракталы можно с успехом испо-
льзовать в демомейкинге.
Вот картинка:
Это общий вид фрактала Мандельброта при
минимальном увеличении. Фрактал Мандельб-
рота является двумерным узором, определён-
ным на комплексной числовой плоскости.
Свойства, проявляющиеся при масштабиро-
вании этого фрактала, можно понять по сле-
дующей картинке:
(На картинке изображён фрагмент фракта-
ла вокруг точки с координатами (.35703211;
.57944996) при увеличении в 1 млрд раз.)
Теперь понятно? Продолжим.
Фрактал Мандельброта (или просто "Ман-
дельброт") генерируют по одной точке. Ка-
ждой точке соответствует нижеследующие вы-
числения.
Пусть координаты точки равны (cx;cy).
Будем считать их компонентами комплекс-
ного числа C=cx+i*cy, где i=√(-1).
Инициализируем комплексное число Z=C.
Считаем Z=Z¤+C, пока |Z|<много либо по-
ка мы не накрутили больше сколько-то-там
проходов цикла. (Много - это,например,мил-
лиард;но можно и 10.Можно придумать и дру-
гие условия переполнения - результатом бу-
дет небольшое изменение рисунка фрактала.
Сколько-то-там должно быть как минимум
двухзначным, причём при очень сильном мас-
штабировании картинки это число желательно
увеличивать.)
Количество проходов цикла и будет соот-
ветствовать цвету точки. Некоторые точки
фигуры никогда не дают переполнения
q|Z|ЄЄмного, в этом случае выход из цикла
происходит по прохождении скольких-то-там
итераций цикла. Такие точки обычно изобра-
жают на рисунке чёрным цветом.
На следующем рисунке на примере четырёх
различных точек показано, как движутся Z.
Для некоторых из них процесс сходится, для
некоторых - наоборот.
Для читателей,не знакомых с комплексной
арифметикой,раскрою операцию Z=Z¤+C. Пусть
Z=x+i·y (описывается двумя действительными
числами: {x;y} ), а C=cx+i·cy, как выше.
Тогда Z¤+C={x¤-y¤+cx;2·x·y+cy}=(x¤-y¤+cx)+
+(2·x·y+cy)·i. То есть два возведения в
квадрат и одно умножение.
Модулем |Z| комплексного числа считает-
ся значение √(x¤+y¤) (корень суммы квад-
ратов. Поскольку вычислять такое выражение
на каждом шаге накладно,лучше использовать
другое условие окончания цикла Z=Z¤+C,
например, переполнение по одной координате
"пока |y|<много".
2.
Изложенной информации достаточно для
написания программы ныряния во фрактал на
каком-нибудь паскале для какого-нибудь IBM
PC ATHLON 2GHz. Только почему получается
так медленно???
Да, именно медленно. Мандельброт - один
из самых времяёмких двумерных эффектов в
демомейкинге. Без хитростей тут не обой-
тись. Какие же есть хитрости?
В первую очередь,если вы намерены имен-
но увеличивать фрактал (а не гонять по
нему трамваи), то совершенно незачем прос-
читывать каждую фазу целиком. Гораздо луч-
ше генерировать последовательно картинки,
отличающиеся по размеру в 2 раза,а переход
между ними совершать обычным zoom'ом (или
zoom rotator'ом). Оба процесса - генерация
и масштабирование - по логике вещей должны
происходить одновременно.Поэтому нужно два
буфера под генерируемые картинки - один
выводится,другой строится. Размер картинок
рекомендуется подбирать не сильно отличаю-
щимся от такого, при котором максимальное
увеличение проецирует пиксель картинки в
пиксель экрана. То есть, грубо говоря, по
линейным размерам - вдвое больше экрана.
Теперь заметим, что никто нам не мешает
задать условие окончания цикла просто-нап-
росто как |y|Є1. Область, занятая фракта-
лом, практически целиком помещается в этот
промежуток!
Далее, кто сказал, что для расчётов ну-
жны числа с плавающей точкой? Ха! Да будет
вам известно (я это открыл всего две неде-
ли назад &), что для масштабирования в сто
тысяч раз достаточно всего 16 бит после
запятой, а 24 бита после запятой дают при-
личное увеличение аж в 20 миллионов раз!
Хотя, может быть, я и не первый из тех,кто
это выяснил :)
В общем, поскольку у нас не ATHLON, а
Z80, берём 16 бит, а знак обсчитываем от-
дельно.На самом деле я пробовал писать та-
кую программу уже 3 раза (в разные годы),и
только с 3-го раза она, собственно,зарабо-
тала :)
В исходнике приведено 2 набора умножа-
лок и возводилок в квадрат - одни, более
точные, алгоритмические, я использовал для
отладки, а те,которые используются - менее
точные,но быстрые. Произведение двух чисел
рассматривается как квадрат полусуммы ми-
нус квадрат полуразности. А сами квадраты
считаются следующим образом:
1. Обнуляем младший бит числа (жалко,
конечно, но таблица не позволяет...)
2. Далее варианты:
2a) если число по модулю меньше 1/2, то
берём результат из таблицы;
2b) иначе результат равен "число из та-
блицы"+"исходное число"+1/4.
Таблица, очевидно, занимает 32k.
Теперь необходимо несколькими экспери-
ментами найти оптимальное значение макси-
мального числа проходов цикла. То есть, то
значение, при котором в максимальном дос-
тупном увеличении (то есть когда только-
только проявляется дискретность) завитушки
ещё видны.Оказывается,в разных местах фра-
ктала этот параметр для режима 16bit коле-
блется от 15 до 35. В прилагаемом исходни-
ке задан список координат нескольких то-
чек, можете добавить свои точки и посмот-
реть,что получится с разными пиковыми чис-
лами проходов.
Как можно уменьшить число обрабатывае-
мых точек фрактала из расчёта на каждый
выводимый кадр?
1) Уменьшить скорость масштабирования.
(На практике начиная с некоторой скорости
начинают происходить повторения кадров,то-
чнее,локальные заторможенности. Рекоменду-
ется иметь столько промежуточных фаз масш-
табирования, сколько пикселей укладывается
на половине одного из линейных размеров
экрана.)
2) Уменьшить размер генерируемых карти-
нок за счёт более некрасивого вида их в
максимальном увеличении. (Скорость,соотве-
тствено,возрастёт пропорционально квадрату
этой экономии.)
3) Разницу между размерами соседних фаз
взять не 2, а более. (Выигрыш сомнителен.)
4) Организовать "решето": те пикселы у
соседних фаз, которые точно не изменятся,
пересчитывать не стоит. Таких пикселов на
всей картинке ровно четверть.
5) Просчитывать края экрана грубее, чем
центр.
6) Не генерировать вообще, а иметь в
памяти кучу рассчитанных фаз :) Этот фокус
проделывается частенько, причём картинки
генерируют почему-то именно на IBM'ках.Тем
не менее, как видно из этой статьи,это во-
все не необходимое условие.
В результате всех этих подлостей я до-
бился того, что для каждого кадра прихо-
дится обсчитывать всего 8 (восемь!) точек
фрактала. На что и можете посмотреть :)
В приложении находится исходник прог-
раммы генерации фрактала на ALASM. Заодно
мы поместили в архив любопытный документ о
том,как Alone Coder поспорил с Vivid'ом на
тему фракталов, и что из этого вышло - и в
виде исходников тоже :)
