Математика - Фрактал Мандельброта.

<b>Математика</b> - Фрактал Мандельброта.

          Фрактал Мандельброта.

(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'ом на
тему фракталов, и что из этого вышло - и в
виде исходников тоже :)