Генерация фракталов с помощью SSE/SSE2
ОГЛАВЛЕНИЕ
В статье описывается способ генерации фракталов с помощью SSE/SSE2
Введение
Вероятно, вы раньше слышали о фракталах. Это красивые изображения, подобные показанному выше. Любой фрактал можно описать с помощью итерационных формул. Фрактал генерируется путем вычисления этих формул и нахождения цвета каждого пикселя. Это тяжелая вычислительная задача, и рисование фрактала требует быстрого процессора и тщательно оптимизированной программы.
Фракталы и их свойства изучаются в нелинейной динамике. Помимо ученых, некоторым людям нравится изучать фракталы, потому что изображения изящные и причудливые.
В этой статье опущены математические основы. Необходимые объяснения есть тут:
• Наборы Джулии и Мандельброта, автор – Дэвид Е. Джойс.
• Что такое набор Мандельброта и другие статьи о фракталах, автор –Фабио Цесари.
• Ваш фрактал, сэр. - Спасибо, Джеймс, автор – q123456789.
• Наборы Джулии и Мандельброта. Теория, автор – Мартин Фингстл.
• Теория фракталов, автор – Cygnus Software.
Последние три статьи также дают некоторый код C для генерации фракталов. Если вы впервые знакомитесь с фракталами, прочтите статьи Фабио Цесари. Его объяснения просты и понятны, с таблицами и картинками, стоящими тысячи слов.
Цели и обзор нескольких генераторов фракталов
Надо найти или разработать учебную программу для изучения фракталов и их свойств. Программа будет применяться для демонстрации ученикам, что такое наборы Мандельброта и Джулии, и будет давать им некоторые упражнения. Ожидается, что ученики будут работать с программой всего один урок, поэтому она должна быть простой и интуитивно понятной.
Главные особенности следующие:
• генерация наборов Джулии и Мандельброта с помощью быстрого алгоритма под управлением SSE;
• просмотр орбиты функции (т.е., последовательности итераций) в виде графика и в виде таблицы;
• демонстрация осей и координат любой точки;
• легкое масштабирование (щелчок левой кнопкой мыши – для увеличения, щелчок правой кнопкой мыши – для уменьшения или нечто подобное);
• генерация набора Джулии с параметром C, соответствующим точке набора Мандельброта.
Последний пункт значит, что можно выбрать значение C для набора Джулии из изображения набора Мандельброта. Вы просто держите кнопку мыши, перемещаете курсор над набором Мандельброта, и набор Джулии меняется, в то время как вы делаете это:
Это называется режимом PnP (изображение в изображении) для краткости.
И несколько слов о тех целях, которые не будут реализованы:
• яркие цвета и палитры (если это сделать, то ученики сосредоточатся на схемах окраски, а не на математике);
• любые типы фракталов, отличные от Джулии и Мандельброта;
• поддержка для 3DNow (расширения SIMD, имеющиеся в старых процессорах AMD; современный Athlon XP использует SSE);
• перенос на другие операционные системы и процессоры (x86 и Win9x/XP было достаточно);
• поддержка нескольких процессоров.
Первой попыткой был Chaos Pro. Это сложное бесплатное приложение, способное генерировать наборы Джулии и Мандельброта и много других фракталов. Можно добавлять собственные формулы фракталов с помощью встроенного языка программирования. Несмотря на то, что программа может создавать превосходные трехмерные изображения и анимации, использовать разные палитры и т.д., в ней нет некоторых важных возможностей. Во-первых, нельзя просмотреть орбиту и оси. Во-вторых, набор Мандельброта генерируется за 1.6 секунды на ноутбуке с процессором Pentium M 1.5 ГГц, а рисование набора Джулии с C = -0.12+0.74i занимает 1.4 секунды. Chaos Pro поддерживает режим PnP, но его неудобно использовать из-за медленной отрисовки. Фракталы нельзя полностью отрисовать в реальном времени (нельзя заставить изображение меняться мгновенно при перемещении курсора). В-третьих (главная причина), в Chaos Pro часто возникает ошибка "нарушение доступа" или другие глюки. Это нормально для бесплатного приложения, написанного любителем, но нужно нечто более надежное.
Также есть FracInt, старая добрая программа DOS для рисования фракталов. Она была разработана несколько лет назад, и сейчас доступна 20.0 версия этого приложения. Программа весьма развитая и мощная, с множеством интересных особенностей, таких как возможность просматривать несколько дюжин типов фракталов, воспроизводить музыку фрактала, использовать режим PnP и создавать стереоскопические изображения. Ее основной недостаток – устаревший пользовательский интерфейс. Масштабирование занимает много времени: вы перетаскиваете мышь, чтобы установить нужный размер прямоугольника, затем перемещаете мышь в точку и, наконец, щелкаете дважды (левой кнопкой – для увеличения, правой кнопкой – для уменьшения). Это было неприемлемо, потому что обычный ученик потратит пол-урока на понимание, как использовать интерфейс масштабирования. Доступны видеорежимы до 1600x1200 (1024x768 VESA должен работать с большинством видеоплат), но при запуске FracInt в Windows XP и нажатии Alt+Tab видеодрайвер дал сбой. Вывод на звуковую плату не работал, и пришлось использовать встроенный динамик. Стоит ли говорить, что это старое приложение не поддерживает MMX и SSE.
После нескольких часов навигации по интернету было найдено «Быстрое плавающее фрактальное веселье», или FFFF. Это очень быстрый генератор набора Мандельброта, поддерживающий SSE, SSE2, 3DNow и программы вершин графического процессора. Если бы он был известен раньше, не была бы начата разработка собственного механизма отрисовки фракталов. Однако у FFFF немного функций помимо масштабирования и переключения между разными механизмами расчета, поэтому если вы решите использовать его, то вам придется добавить генератор набора Джулии и разработать более продуманный графический пользовательский интерфейс.