Материал: Фрактальная компьютерная графика
Фрактальная компьютерная графика
Введение
Слово фрактал образовано от латинского "fractus" и в переводе означает состоящий из фрагментов. Оно было предложено Бенуа Мандельбротом в 1975 году. Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому". Одним из основных свойств фракталов является самоподобие. В самом простом случае небольшая часть фрактала содержит информацию о всем фрактале. Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов.
Фракталы широко применяются в компьютерной графике для построения изображений природных объектов, таких, как деревья, кусты, горные ландшафты, поверхности морей и т. д. Роль фракталов в машинной графике сегодня достаточно велика. Они приходят на помощь, например, когда требуется, получить линии и поверхности очень сложной формы. Фракталы используются для описания кривизны поверхностей. С точки зрения машинной графики, фрактальная геометрия незаменима при генерации искусственных облаков, объемных рельефных гор, поверхности моря. Фактически найден способ легкого представления сложных неевклидовых объектов, образы которых весьма похожи на природные. Фрактальная компьютерная графика широко используется при создании мультфильмов и фантастических художественных фильмов. Используются антенны, имеющие фрактальные формы, что сильно уменьшает их размеры и вес.
1. Теоретическая часть
1.1 Применение фракталов
· Компьютерные системы.
Наиболее полезным использованием фракталов в компьютерной науке является фрактальное сжатие данных. Достоинство фрактального сжатия изображений - очень маленький размер упакованного файла и малое время восстановления картинки. Фрактально упакованные картинки можно масштабировать без появления пикселизации. Но процесс сжатия занимает продолжительное время и иногда длится часами. Алгоритм фрактальной упаковки с потерей качества позволяет задать степень сжатия, аналогично формату jpeg.
В основе алгоритма лежит поиск больших кусков изображения подобных некоторым маленьким кусочкам. И в выходной файл записывается только какой кусочек какому подобен. При сжатии обычно используют квадратную сетку (кусочки - квадраты), что приводит к небольшой угловатости при восстановлении картинки, шестиугольная сетка лишена такого недостатка.
· Механика жидкостей.
Изучение турбулентности в потоках очень хорошо подстраивается под фракталы. Турбулентные потоки хаотичны и поэтому их сложно точно смоделировать.
При помощи фракталов также можно смоделировать языки пламени.
Пористые материалы хорошо представляются в фрактальной форме в связи с тем, что они имеют очень сложную геометрию. Это используется в нефтяной науке.
· Телекоммуникации.
В телекоммуникациях фракталы используются для создания фрактальных антенн. Фрактальные антенны - относительно новый класс электрически малых антенн (ЭМА), принципиально отличающийся своей геометрией от известных решений. По сути, традиционная эволюция антенн базировалась на евклидовой геометрии, оперирующей объектами целочисленной размерности (линия, круг, эллипс, параболоид и т. п.). Фрактальная антенны с удивительно компактным дизайном обеспечивает превосходную широкополосную производительность в маленьком форм-факторе. Достаточно компактны для установки или встраивания в различных местах, фрактальные антенны используются для морских, воздушных транспортных средств, или персональных устройств. На изображении выше пример фрактальной антенны.
Также в сфере сетевых технологий было проведено множество исследований
показывающих самоподобие траффика передаваемого по разного рода сетям. Особенно
это касается речевых, аудио и видео сервисов. Поэтому сейчас ведутся разработки
и исследования возможности фрактального сжатия траффика передаваемого по сетям,
с целью более эффективной передачи информации.
1.2 Классификация фракталов
Вообще фракталом называется предмет который обладает одним из указанных свойств:
v Обладает нетривиальной структурой на всех масштабах. В этом и есть отличие от регулярных фигур, таких как окружность или эллипс. Если мы рассмотрим небольшой фрагмент регулярной фигуры в крупном масштабе, то он будет похож на фрагмент прямой. Для фрактала увеличение масштаба не ведет к упрощению структуры, на всех шкалах мы увидим одинаково сложную картину.
v Является самоподобным или приближенно самоподобным.
v Обладает дробной метрической размерностью.
В основном фракталы классифицируют по трём видам:
. Алгебраические фракталы
. Геометрические фракталы
. Стохастические фракталы
Алгебраические фракталы
Алгебраические фракталы - это самая крупная группа фракталов, получившая название за использование алгебраических формул. Методов
получения алгебраических фракталов несколько. Один из методов
представляет собой многократный (итерационный) расчет функции Zn+1=f(Zn), где Z
- комплексное число, а f некая функция. Расчет данной функции продолжается до
выполнения определенного условия. И когда это условие выполнится - на экран
выводится точка. При этом функция для разных точек комплексной плоскости может
иметь разное поведение: с течением времени она может стремиться к
бесконечности; стремиться к 0; принимать несколько фиксированных значений и не
выходить за их пределы. Поведение хаотично, без каких-либо тенденций. Таким
образом было получено множество Мандельброта - фрактал, определённый, как
множество точек С на комплексной плоскости. Бенуа Мандельброт предложил модель
фрактала, которая стала классической и часто используется для демонстрации, как
типичного примера самого фрактала, так и для демонстрации красоты фракталов,
которая также привлекает исследователей, художников, просто интересующихся
людей.
Рис.1. Пример алгебраического фрактала.
Геометрические фракталы
Фракталы этого класса самые наглядные, потому что в них сразу видна самоподобность.
В двухмерном случае такие фракталы можно получить, задав некоторую ломаную,
называемую генератором. За один шаг алгоритма каждый из отрезков, составляющих
ломаную, заменяется на ломаную-генератор. В результате бесконечного повторения
этой процедуры (а, точнее, при переходе к пределу) получается фрактальная
кривая. При видимой сложности полученной кривой, её общий вид задается только
формой генератора. Примерами таких кривых служат: кривая Коха (снежинка Коха),
кривая Леви, кривая Минковского, кривая Пеано.
Рис.2. Пример геометрического фрактала.
Стохастические фракталы
Типичный представитель данного класса фракталов "Плазма". Для
ее построения возьмем прямоугольник и для каждого его угла определим цвет. Далее
находим центральную точку прямоугольника и раскрашиваем ее в цвет равный
среднему арифметическому цветов по углам прямоугольника плюс некоторое
случайное число. Чем больше случайное число - тем более "рваным"
будет рисунок. Если мы теперь скажем, что цвет точки это высота над уровнем
моря - получим вместо плазмы - горный массив. Именно на этом принципе
моделируются горы в большинстве программ.
1.3 Виды фракталов
Рассмотрим несколько распространённых видов фракталов.
Решётка Серпинского.
Это один из фракталов, с которыми экспериментировал Мандельброт, когда
разрабатывал концепции фрактальных размерностей и итераций. Треугольники,
сформированные соединением средних точек большего треугольника вырезаны из
главного треугольника, образовывая треугольник, с большим количеством дырочек.
В этом случае инициатор - большой треугольник а шаблон - операция вырезания
треугольников, подобных большему. Так же можно получить и трехмерную версию
треугольника, используя обыкновенный тетраэдр и вырезая маленькие тетраэдры.
Размерность такого фрактала ln3/ln2 = 1.584962501.
Рис.3. Решетка Серпинского.
Треугольник Серпинского.
Не перепутайте этот фрактал с решеткой Серпинского. Это два абсолютно
разных объекта. В этом фрактале, инициатор и генератор одинаковы. При каждой
итерации, добавляется уменьшенная копия инициатора к каждому углу генератора и
так далее. Если при создании этого фрактала произвести бесконечное число
итераций, он бы занял всю плоскость, не оставив ни одной дырочки. Поэтому его
фрактальная размерность ln9/ln3 = 2.0.
Рис.4. Треугольник Серпинского.
Кривая Коха.
Кривая Коха один из самых типичных детерминированных фракталов. Она была
изобретена в 1904 году шведским математиком по имени Хельге фон Кох, который,
изучая работы Георга Контора и Карла Вейерштрассе, натолкнулся на описания
некоторых странных кривых с необычным поведением. Инициатор - прямая линия.
Генератор - равносторонний треугольник, стороны которого равны трети длины большего
отрезка. Эти треугольники добавляются к середине каждого сегмента снова и
снова. В своем исследовании, Мандельброт много экспериментировал с кривыми
Коха, и получил фигуры такие как Острова Коха, Кресты Коха, Снежинки Коха и
даже трехмерные представления кривой Коха, используя тетраэдр и прибавляя
меньшие по размерам тетраэдры к каждой его грани. Кривая Коха имеет размерность
ln4/ln3 = 1.261859507.
Рис.5. Кривая Коха.
Фрактал Мандельброта.
Это НЕ множество Мандельброта, которое можно достаточно часто видеть.
Множество Мандельброта основано на нелинейных уравнениях и является комплексным
фракталом. Это тоже вариант кривой Коха несмотря на то, что этот объект не
похож на нее. Инициатор и генератор так же отличны от использованных для
создания фракталов, основанных на принципе кривой Коха, но идея остается той
же. Вместо того, чтобы присоединять равносторонние треугольники к отрезку
кривой, квадраты присоединяются к квадрату. Благодаря тому, что этот фрактал
занимает точно половину отведенного пространства при каждой итерации, он имеет
простую фрактальную размерность 3/2 = 1.5
Рис.6. Фрактал Мандельброта.
Кривая Дракона.
Изобретенная итальянским математиком Джузеппе Пеано, Кривая Дракона или
Взмах Дракона, как он назвал его, очень похож на колбасу Минковского.
Использован более простой инициатор, а генератор тот же самый. Мандельброт
назвал этот фрактал Река Двойного Дракона. Его фрактальная размерность
приблизительно равна 1.5236.
Рис.7. Дракон Джузеппе Пеано.
Множество Мандельброта.
Множества Мандельброта и Жюлиа, вероятно, два наиболее распространенных среди сложных фракталов. Их можно найти во многих научных журналах, обложках книг, открытках, и в компьютерных хранителях экрана. Множество Мандельброта, которое было построено Бенуа Мандельбротом, наверное первая ассоциация, возникающая у людей, когда они слышат слово фрактал. Этот фрактал, напоминающий чесальную машину с прикрепленными к ней пылающими древовидными и круглыми областями, генерируется простой формулой Zn+1=Zna+C, где Z и C - комплексные числа и а - положительное число.
Множество Мандельброта, которое чаще всего можно увидеть - это множество Мандельброта 2й степени, то есть а=2. Тот факт, что множество Мандельброта не только Zn+1=ZnІ+C, а фрактал, показатель в формуле которого может быть любым положительным числом ввел в заблуждение многих. На этой странице вы видите пример множества Мандельброта для различных значений показателя а.
Также популярен процесс Z=Z*tg (Z+C). Благодаря включению функции
тангенса, получается множество Мандельброта, окруженное областью, напоминающей
яблоко. При использовании функции косинуса, получаются эффекты воздушных
пузырьков. Короче говоря, существует бесконечное количество способов настройки
множества Мандельброта для получения различных красивых картинок.
Рис.8. Множество Мандельброта.
Модель Джулии
Модель фрактала Джулии имеет то же уравнение, что и модель Мандельброта: Z=Z2+c, только здесь переменным параметром является не c, a z.
Соответственно, меняется вся структура фрактала, так как теперь на
начальное положение не накладывается никаких ограничений. Между моделями
Мандельброта и Джулии существует такое различие: если модель Мандельброта
является статической ( так как z начальное
всегда равно нулю), то модель Джулии является динамической моделью фрактала.
Рис.9. Модель Джулии.
2. Постановка задачи
Необходимо спроектировать и разработать программный продукт, при помощи которого возможно наглядно посмотреть изображения фрактальной графики. Программа должна позволять раскрыть сущность фрактала - многократное самоповторение (всего изображения или определённой его части). Интерфейс должен быть максимально понятным. Скорость работы должна быть такой, чтобы сбалансировать производительность и качество, то есть при данной скорости прорисовывается достаточно наглядное изображение. Необходима так же возможность сохранения фрактального изображения. Программа должна быть интуитивно понятной и "не отталкивать при первом взгляде". Возможностями программы должны быть доступны прорисовки алгебраического и геометрического фракталов.
Программная структура представляет собой набор функций, каждая из которых
является "формулой" прорисовки одного фрактала. И процедуры самой
прорисовки.
Рис.10. Схема работы программы.
Работать мы будем в среде программирования PascalABC.NET, поговорим о ней подробнее. PascalABC.NET - это язык программирования Паскаль нового поколения, который включает в себя классический Паскаль, большинство возможностей языка Delphi <https://ru.wikipedia.org/wiki/Delphi_%28%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F%29>, а также ряд собственных расширений. Он реализован на платформе Microsoft.NET <https://ru.wikipedia.org/wiki/.NET_Framework> и содержит все современные языковые средства такие как: классы <https://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_%28%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%29>, перегрузку операций <https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D0%B3%D1%80%D1%83%D0%B7%D0%BA%D0%B0_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80%D0%BE%D0%B2>, интерфейсы <https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D1%84%D0%B5%D0%B9%D1%81_%28%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%BD%D0%BE-%D0%BE%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%29>, обработку исключений <https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B0_%D0%B8%D1%81%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D0%B9>, обобщенные классы и подпрограммы <https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D0%BE%D0%B1%D1%89%D1%91%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5>, сборку мусора <https://ru.wikipedia.org/wiki/%D0%A1%D0%B1%D0%BE%D1%80%D0%BA%D0%B0_%D0%BC%D1%83%D1%81%D0%BE%D1%80%D0%B0>, лямбда-выражения, средства параллельного программирования <https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5>..NET является мультипарадигменным языком: на нем можно программировать в структурном <https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5>, объектно-ориентированном <https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%BD%D0%BE-%D0%BE%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5> и функциональном <https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5> стилях. Также это простая и мощная интегрированная среда разработки, поддерживающая технологию IntelliSense <https://ru.wikipedia.org/wiki/IntelliSense>, содержащая средства автоформатирования, встроенный отладчик и встроенный дизайнер форм. Кроме того, консольный компилятор PascalABC.NET функционирует на Linux <https://ru.wikipedia.org/wiki/Linux> и MacOS <https://ru.wikipedia.org/wiki/MacOS> под Mono <https://ru.wikipedia.org/wiki/Mono>.