Inferno #04
22 июня 2003

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

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

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




Другие статьи номера:

События - Об окончании первой части виртуального музыкального пати The Compo.

Sofтинка - Об операционных системах для спектрума ChAOS и ZXVGS.

Inferno - Авторы журнала.

Pentagon - Инструкция по активации незадействованной (нулевой) банки пзу в компьютере Пентагон.

Pentagon - Инструкция по переделке Пентагона-128 для выхода по Reset'у в 0-ю банку ПЗУ 27512.

Gameland - Прохождение игры Черный Ворон: Неизвестные Отгрузки. Диск 1.

Gameland - Прохождение игры Черный Ворон: Неизвестные Отгрузки. Диск 2.

Sofтинка - Описание графической оболочки для дисковой системы TR-DOS - ChAOS.

Inferno - Об оболочке.

Sofтинка - Редактор двухэкранной графики DouBleScreen Editor v0.4.

Sofтинка - Операционная система ZXVGS. Состав версий, софт.

Inferno - Вступление от редакторов.

Железо - Итоги освоения кодеров RGB - PAL/NTSC, на конец 2002 года.

Gameland - Об играх King's Bounty 3, Чёрный Ворон: Неизвестные Отгрузки.

Others - Об анкетировании.

For Coderz - Макросы под ассемблер Alasm v4.4x.

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

Sofтинка - Музыкальный редактор Pro Tracker v3.71. Особенности программы.

Sofтинка - Формат RAR 2.x. Техническая информация.

Others - Зарегистрированные пользователи ZXVGS и CPM22QED.

Sofтинка - Типы файлов, определённые в ОС ZXVGS.

Sofтинка - Функции операционной системы ZXVGS.

Sofтинка - Внешний вид операционной системы ZXVGS.

Sofтинка - IDEDOS - доступ к жёстким дискам в ОС ZXVGS.

Sofтинка - Описание операционной системы ZXVGS.

Sofтинка - MEMDISK - файловая система для хранения файлов в областях памяти.

Sofтинка - Релизы ОС ZXVGS и их различия.

Sofтинка - Резидентные Расширения Системы (RSX) в ZXVGS.

Sofтинка - Список версий новой операционной системы для спектрума ZXVGS.

Железо - Расширенная клавиатура для sinclair-совместимых персональных компьютеров.

For Coderz - Алгоритм нахождения целой части квадратного корня.

События - Номинанты виртуального музыкального пати The Compo.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Система - обращении непосредственно к ПЗУ DOS и о прямом программировании ВГ 93.
Мнение - кругом попса!!
События - Объявления результатов CC'000.

В этот день...   18 декабря