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'ом на тему фракталов, и что из этого вышло - и в виде исходников тоже :)
Другие статьи номера:
Похожие статьи:
В этот день... 12 декабря