Jump to content

Алгоритмы построения множества Мандельброта

Неподвижное изображение видеоролика с увеличивающимся увеличением на 0,001643721971153 − 0,822467633298876 i
Неподвижное изображение анимации с увеличивающимся увеличением

Существует множество программ и алгоритмов, используемых для построения множества Мандельброта и других фракталов , некоторые из которых описаны в программном обеспечении, генерирующем фракталы . Эти программы используют различные алгоритмы для эффективного определения цвета отдельных пикселей .

Алгоритм времени выхода

[ редактировать ]

Самый простой алгоритм создания представления множества Мандельброта известен как алгоритм «времени выхода». Повторяющийся расчет выполняется для каждой точки x , y в области графика, и на основе поведения этого расчета для этого пикселя выбирается цвет.

Неоптимизированный наивный алгоритм времени выхода

[ редактировать ]

Как в неоптимизированном, так и в оптимизированном алгоритмах времени ухода координаты x и y каждой точки используются в качестве начальных значений в повторяющихся или итерирующих вычислениях (подробно описано ниже). Результат каждой итерации используется в качестве начального значения для следующей. Значения проверяются во время каждой итерации, чтобы увидеть, достигли ли они критического состояния «выхода» или «катастрофы». Если это условие достигнуто, расчет останавливается, пиксель рисуется и x , y исследуется следующая точка . Для некоторых начальных значений выход происходит быстро, после небольшого количества итераций. Для начальных значений, очень близких к множеству, но не входящих в него, для выхода могут потребоваться сотни или тысячи итераций. Для значений из множества Мандельброта экранирование никогда не произойдет. Программист или пользователь должен выбрать, сколько итераций – или какую «глубину» – они хотят изучить. Чем выше максимальное количество итераций, тем больше деталей и тонкостей появляется в конечном изображении, но тем больше времени потребуется для расчета фрактального изображения.

Условия побега могут быть простыми и сложными. Поскольку никакое комплексное число с действительной или мнимой частью больше 2 не может быть частью набора, обычным выходом является побег, когда любой из коэффициентов превышает 2. Более сложный в вычислительном отношении метод, который обнаруживает побеги раньше, заключается в вычислении расстояния от начала координат с помощью теорему Пифагора , т.е. для определения абсолютного значения или модуля комплексного числа. Если это значение превышает 2 или, что то же самое, когда сумма квадратов действительной и мнимой частей превышает 4, точка достигла выхода. Более ресурсоемкие варианты рендеринга включают метод Буддхаброта , который находит ускользающие точки и строит график их повторяющихся координат.

Цвет каждой точки показывает, насколько быстро значения достигли точки выхода. Часто черный цвет используется для отображения значений, которые не могут выйти за пределы итерации, а для точек, которые выходят за рамки, постепенно используются более яркие цвета. Это дает визуальное представление о том, сколько циклов потребовалось для достижения условия выхода.

Для визуализации такого изображения рассматриваемую нами область комплексной плоскости разбивают на определенное количество пикселей . Чтобы раскрасить любой такой пиксель, пусть быть серединой этого пикселя. Теперь мы повторяем критическую точку 0 под , проверяя на каждом шаге, имеет ли точка орбиты модуль больше 2. В этом случае мы знаем, что не принадлежит множеству Мандельброта, и мы раскрашиваем наш пиксель в соответствии с количеством итераций, использованных для его определения. В противном случае мы продолжаем итерацию до фиксированного количества шагов, после чего решаем, что наш параметр «вероятно» принадлежит множеству Мандельброта или, по крайней мере, очень близок к нему, и окрашиваем пиксель в черный цвет.

В псевдокоде этот алгоритм будет выглядеть следующим образом. Алгоритм не использует комплексные числа и вручную моделирует операции с комплексными числами, используя два действительных числа, для тех, у кого нет сложного типа данных . Программа может быть упрощена, если язык программирования включает операции со сложными типами данных.

for each pixel (Px, Py) on the screen do
    x0 := scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.00, 0.47))
    y0 := scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1.12, 1.12))
    x := 0.0
    y := 0.0
    iteration := 0
    max_iteration := 1000
    while (x*x + y*y ≤ 2*2 AND iteration < max_iteration) do
        xtemp := x*x - y*y + x0
        y := 2*x*y + y0
        x := xtemp
        iteration := iteration + 1
 
    color := palette[iteration]
    plot(Px, Py, color)

Здесь, связывая псевдокод с , и :

  • -

и так, как видно из псевдокода при вычислении x и y :

  • и

Чтобы получить красочные изображения множества, присвоение цвета каждому значению числа выполненных итераций может быть произведено с помощью одной из множества функций (линейной, экспоненциальной и т. д.). Одним из практических способов, не замедляющих расчеты, является использование количества выполненных итераций в качестве записи в палитре, инициализируемой при запуске. Если таблица цветов содержит, например, 500 записей, то выбор цвета равен n mod 500, где n — количество итераций.

Оптимизированные алгоритмы времени выхода

[ редактировать ]

В коде предыдущего раздела для ясности используется неоптимизированный внутренний цикл while. В неоптимизированной версии за итерацию необходимо выполнить пять умножений. Чтобы уменьшить количество умножений, вместо этого можно использовать следующий код для внутреннего цикла while:

x2:= 0
y2:= 0
w:= 0

while (x2 + y2 ≤ 4 and iteration < max_iteration) do
    x:= x2 - y2 + x0
    y:= w - x2 - y2 + y0
    x2:= x * x
    y2:= y * y
    w:= (x + y) * (x + y)
    iteration:= iteration + 1

Приведенный выше код работает посредством некоторого алгебраического упрощения комплексного умножения:

Используя приведенное выше тождество, количество умножений можно сократить до трех вместо пяти.

Вышеупомянутый внутренний цикл while можно дополнительно оптимизировать, расширив w до

Подставив w в урожайность и, следовательно, вычисление w больше не требуется.

Дальнейший оптимизированный псевдокод для вышеизложенного:

x2:= 0
y2:= 0

while (x2 + y2 ≤ 4 and iteration < max_iteration) do
    y:= 2 * x * y + y0
    x:= x2 - y2 + x0
    x2:= x * x
    y2:= y * y
    iteration:= iteration + 1

Обратите внимание, что в приведенном выше псевдокоде кажется, увеличивает количество умножений на 1, но поскольку 2 — это множитель, код можно оптимизировать с помощью .

Производная помощь или «дербайл»

[ редактировать ]
Пример мельчайших деталей, возможных с использованием derbail, визуализированный с использованием 1024 семплов.

Обычно величину z проверяют после каждой итерации, но мы можем использовать другой метод, который может сходиться быстрее и выявить структуру в наборах julia .

Вместо того, чтобы проверять, ли величина z превышает после каждой итерации заданное значение, мы можем вместо этого проверить, превышает ли сумма каждой производной z до текущего шага итерации заданное значение спасения:

Размер значения dbail может улучшить детализацию структур, выявленных с помощью метода dbail при очень больших значениях.

Производные можно найти автоматически, используя автоматическое дифференцирование и вычисляя итерации с использованием двойных чисел .

Отверстие, вызванное проблемами с точностью

Рендеринг фракталов с помощью метода derbail часто может требовать большого количества выборок на пиксель, поскольку могут возникнуть проблемы с точностью , которые приводят к появлению мелких деталей и могут привести к зашумленным изображениям даже с выборками в сотни или тысячи.

Код Python:

Дербейл использовался на съемках горящего корабля Джулии.
def pixel(x: int, y: int, w: int, h: int) -> int:
    def magn(a, b):
        return a * a + b * b

    dbail = 1e6
    ratio = w / h

    x0 = (((2 * x) / w) - 1) * ratio
    y0 = ((2 * y) / h) - 1

    dx_sum = 0
    dy_sum = 0

    iters = 0
    limit = 1024

    while magn(dx_sum, dy_sum) < dbail and iters < limit:
        xtemp = x * x - y * y + x0
        y = 2 * x * y + y0
        x = xtemp

        dx_sum += (dx * x - dy * y) * 2 + 1
        dy_sum += (dy * x + dx * y) * 2

        iters += 1

    return iters

Алгоритмы окраски

[ редактировать ]

Помимо построения набора, были разработаны различные алгоритмы для

  • эффективно раскрасить комплект эстетически приятным способом
  • показать структуры данных (научная визуализация)

Раскраска гистограммы

[ редактировать ]

Более сложный метод раскраски включает использование гистограммы , которая связывает каждый пиксель с максимальным количеством итераций этого пикселя перед выходом/выходом из строя. Этот метод будет одинаково распределять цвета по одной и той же общей площади и, что важно, не зависит от выбранного максимального количества итераций. [1]

Этот алгоритм имеет четыре прохода. Первый проход включает в себя вычисление количества итераций, связанных с каждым пикселем (но без построения графика пикселей). Они сохраняются в массиве: IterationCounts[x][y], где x и y — координаты x и y указанного пикселя на экране соответственно.

Верхний ряд представляет собой серию графиков с использованием алгоритма времени выхода для 10000, 1000 и 100 максимальных итераций на пиксель соответственно. В нижней строке используются те же максимальные значения итерации, но используется метод раскраски гистограммы. Обратите внимание, как мало меняется окраска в зависимости от максимального количества итераций для графиков метода раскраски гистограммы.

Первым шагом второго прохода является создание массива размера n , который соответствует максимальному количеству итераций: NumIterationsPerPixel. Затем необходимо перебрать массив пар счетчиков пикселей и итераций IterationCounts[][] и получить сохраненное количество итераций каждого пикселя i , например, i = IterationCounts[x][y]. каждого пикселя После получения количества итераций i необходимо проиндексировать NumIterationsPerPixel на i и увеличить индексированное значение (которое изначально равно нулю) — например, NumIterationsPerPixel[ i ] = NumIterationsPerPixel[ i ] + 1 .

for (x = 0; x < width; x++) do
    for (y = 0; y < height; y++) do
        i:= IterationCounts[x][y]
        NumIterationsPerPixel[i]++

Третий проход перебирает массив NumIterationsPerPixel и суммирует все сохраненные значения, сохраняя их в общей сложности . Индекс массива представляет количество пикселей, достигших этого количества итераций до аварийного восстановления.

total: = 0
for (i = 0; i < max_iterations; i++) do
    total += NumIterationsPerPixel[i]

После этого начинается четвертый проход, и все значения в массиве IterationCounts индексируются, и для каждого счетчика итераций i , связанного с каждым пикселем, этот счетчик добавляется к глобальной сумме всех счетчиков итераций от 1 до i в массиве. Массив NumIterationsPerPixel. Затем это значение нормализуется путем деления суммы на общее значение, вычисленное ранее.

hue[][]:= 0.0
for (x = 0; x < width; x++) do
    for (y = 0; y < height; y++) do
        iteration:= IterationCounts[x][y]
        for (i = 0; i <= iteration; i++) do
            hue[x][y] += NumIterationsPerPixel[i] / total /* Must be floating-point division. */

...

color = palette[hue[m, n]]

...

Наконец, вычисленное значение используется, например, как индекс цветовой палитры.

Этот метод можно комбинировать с приведенным ниже методом плавной окраски для получения более эстетичных изображений.

Непрерывное (плавное) окрашивание

[ редактировать ]
Это изображение было визуализировано с помощью алгоритма времени выхода. Есть очень очевидные цветные «полосы».
Это изображение было визуализировано с помощью алгоритма нормализованного подсчета итераций. Цветные полосы заменены плавным градиентом. Кроме того, цвета принимают тот же рисунок, который наблюдался бы при использовании алгоритма времени выхода.

Алгоритм времени выхода популярен благодаря своей простоте. Однако он создает цветные полосы, которые, как тип сглаживания , могут умалять эстетическую ценность изображения. Это можно улучшить с помощью алгоритма, известного как «нормализованное количество итераций». [2] [3] что обеспечивает плавный переход цветов между итерациями. Алгоритм связывает действительное число с каждым значением z , используя связь номера итерации с потенциальной функцией . Эта функция определяется выражением

где z n — значение после n итераций, а P — степень, до которой z возводится в уравнении множества Мандельброта ( z n +1 = z n П + c , P обычно 2).

Если мы выберем большой радиус спасения N (например, 10 100 ), у нас такое есть

для некоторого действительного числа , и это

и поскольку n — номер первой итерации такой, что | з п | > N , число, которое мы вычитаем из n, находится в интервале [0, 1).

Для раскраски нам необходима циклическая шкала цветов (построенная, например, математически) и содержащая H цветов с номерами от 0 до H - 1 ( H например, = 500). Умножаем действительное число по фиксированному вещественному числу, определяющему плотность цветов на изображении, возьмите целую часть этого числа по модулю H и используйте его для поиска соответствующего цвета в таблице цветов.

Например, изменение приведенного выше псевдокода, а также использование концепции линейной интерполяции даст

for each pixel (Px, Py) on the screen do
    x0:= scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.5, 1))
    y0:= scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1, 1))
    x:= 0.0
    y:= 0.0
    iteration:= 0
    max_iteration:= 1000
    // Here N = 2^8 is chosen as a reasonable bailout radius.

    while x*x + y*y ≤ (1 << 16) and iteration < max_iteration do
        xtemp:= x*x - y*y + x0
        y:= 2*x*y + y0
        x:= xtemp
        iteration:= iteration + 1

    // Used to avoid floating point issues with points inside the set.
    if iteration < max_iteration then
        // sqrt of inner term removed using log simplification rules.
        log_zn:= log(x*x + y*y) / 2
        nu:= log(log_zn / log(2)) / log(2)
        // Rearranging the potential function.
        // Dividing log_zn by log(2) instead of log(N = 1<<8)
        // because we want the entire palette to range from the
        // center to radius 2, NOT our bailout radius.
        iteration:= iteration + 1 - nu

    color1:= palette[floor(iteration)]
    color2:= palette[floor(iteration) + 1]
    // iteration % 1 = fractional part of iteration.
    color:= linear_interpolate(color1, color2, iteration % 1)
    plot(Px, Py, color)


Экспоненциально отображаемые и циклические итерации

[ редактировать ]
Экспоненциальная циклическая раскраска в цветовом пространстве LCH с затенением

Обычно, когда мы визуализируем фрактал, диапазон появления цветов из заданной палитры вдоль фрактала является статическим. Если мы хотим сместить местоположение от границы фрактала или настроить их палитру для цикличности определенным образом, есть несколько простых изменений, которые мы можем сделать, беря окончательный счетчик итераций, прежде чем передавать его для выбора элемента из нашего списка. палитра.


Когда мы получили количество итераций, мы можем сделать диапазон цветов нелинейным. Возведение значения, нормализованного к диапазону [0,1] в степень n , отображает линейный диапазон в экспоненциальный диапазон, что в нашем случае может подтолкнуть появление цветов вдоль внешней стороны фрактала и позволить нам выявить другие цвета или переместите всю палитру ближе к границе.

где i — количество итераций после спасения, max_i — наш лимит итераций, S — показатель степени, до которого мы повышаем итерации, а N — количество элементов в нашей палитре. При этом количество итеров масштабируется нелинейно, а палитра циклически масштабируется примерно пропорционально масштабу.

Затем мы можем подключить v к любому желаемому алгоритму генерации цвета.

Передача итераций в цвет напрямую

[ редактировать ]
Пример экспоненциально отображаемой циклической окраски LCH без затенения

Одна вещь, которую мы, возможно, захотим рассмотреть, — это вообще избегать необходимости иметь дело с палитрой или смешиванием цветов. На самом деле существует несколько методов, которые мы можем использовать для создания плавной и последовательной окраски, создавая цвет на месте.

v относится к нормализованному экспоненциально отображенному счетчику циклических итераций.

[ редактировать ]

Наивный метод генерации цвета таким способом — напрямую масштабировать v до 255 и передавать его в RGB как таковой.

rgb = [v * 255, v * 255, v * 255]

Один из недостатков заключается в том, что RGB нелинейен из-за гаммы; Вместо этого рассмотрите линейный sRGB. При переходе от RGB к sRGB на каналах используется функция обратного компандирования. Это делает гамму линейной и позволяет нам правильно суммировать цвета для выборки.

srgb = [v * 255, v * 255, v * 255]
ВПГ-градиент

Окраска ВПГ

[ редактировать ]

Раскраску HSV можно выполнить путем сопоставления количества итеров с [0,max_iter) на [0,360), возведя его в степень 1,5, а затем по модулю 360. Затем мы можем просто взять экспоненциально отображенное количество итеров в значение и вернуть

hsv = [powf((i / max) * 360, 1.5) % 360, 100, (i / max) * 100]

Этот метод применим и к HSL, за исключением того, что вместо этого мы передаем насыщенность 50%.

hsl = [powf((i / max) * 360, 1.5) % 360, 50, (i / max) * 100]
LCH Градиент

ЛЧ раскраска

[ редактировать ]

Один из наиболее единообразных методов раскраски предполагает передачу обработанного количества итеров в LCH. Если мы используем экспоненциально отображенный и циклический метод, описанный выше, мы можем перенести его результат в каналы яркости и цветности. Мы также можем экспоненциально отобразить количество итеров, масштабировать его до 360 и передать это значение по модулю 360 в оттенок.

Одной из проблем, которых мы хотим здесь избежать, являются цвета, выходящие за пределы гаммы. Этого можно добиться с помощью небольшого трюка, основанного на изменении цветов внутри гаммы относительно яркости и цветности. По мере увеличения яркости нам необходимо уменьшать цветность, чтобы оставаться в пределах гаммы.

s = iters/max_i;
v = 1.0 - powf(cos(pi * s), 2.0);
LCH = [75 - (75 * v), 28 + (75 - (75 * v)), powf(360 * s, 1.5) % 360];

Расширенные алгоритмы построения графиков

[ редактировать ]

В дополнение к уже рассмотренным простым и медленным алгоритмам времени выхода существует множество других, более продвинутых алгоритмов, которые можно использовать для ускорения процесса построения графиков.

Оценка расстояния

[ редактировать ]

Можно вычислить расстояние от точки c ( внешней или внутренней ) до ближайшей точки на границе множества Мандельброта. [4] [5]

Оценка внешнего расстояния

[ редактировать ]

Доказательство связности множества Мандельброта фактически дает формулу униформизирующего дополнения для отображения производная от этой карты). По теореме Кебе о четверти можно затем оценить расстояние между серединой нашего пикселя и набором Мандельброта с коэффициентом 4.

Другими словами, при условии, что максимальное число итераций достаточно велико, получается картина множества Мандельброта со следующими свойствами:

  1. Каждый пиксель, содержащий точку множества Мандельброта, окрашен в черный цвет.
  2. Каждый пиксель, окрашенный в черный цвет, близок к множеству Мандельброта.
Оценку внешнего расстояния можно использовать для раскрашивания всего набора Мандельброта.

Верхняя граница b для оценки расстояния пикселя c (комплексного числа) из множества Мандельброта определяется выражением [6] [7] [8]

где

  • означает комплексный квадратичный полином
  • означает n итераций или , начиная с : , ;
  • является производной от относительно ц. Эту производную можно найти, начав с а потом . В этом легко убедиться, воспользовавшись цепным правилом для производной.

Идея этой формулы проста: когда эквипотенциальные линии потенциальной функции лежи рядом, число велика, и, наоборот, поэтому эквипотенциальные линии для функции должно лежать примерно регулярно.

С точки зрения математика, эта формула работает только в пределе, когда n стремится к бесконечности, но очень разумные оценки можно получить всего за несколько дополнительных итераций после выхода из основного цикла.

Как только b найдено по теореме Кебе 1/4, мы знаем, что не существует точки множества Мандельброта с расстоянием от c меньшим, чем b/4 .

Оценку расстояния можно использовать для рисования границы множества Мандельброта, см. статью Множество Юлии . В этом подходе пиксели, достаточно близкие к M, рисуются другим цветом. Это создает рисунки, на которых легко увидеть тонкие «нити» множества Мандельброта. Этот прием с успехом используется в черно-белых изображениях множеств Мандельброта в книгах «Красота фракталов». [9] и «Наука о фрактальных изображениях». [10]

Вот пример черно-белого изображения, отрендеренного с использованием оценки расстояния:

Это черно-белое изображение части множества Мандельброта, визуализированное с использованием оценки расстояния (DE).

Оценку расстояния также можно использовать для рендеринга 3D-изображений множеств Мандельброта и Жюлиа.

Оценка внутреннего расстояния

[ редактировать ]
Пиксели окрашены в соответствии с предполагаемым внутренним расстоянием.

Также возможно оценить расстояние предельно периодической (т. е. гиперболической ) точки до границы множества Мандельброта. Верхняя граница b для оценки расстояния определяется выражением [4]

где

  • это период,
  • это точка, которую нужно оценить,
  • - комплексный квадратичный многочлен
  • это -кратная итерация , начиная с
  • это что-то из точки, которые составляют аттрактор итераций начиная с ; удовлетворяет ,
  • , , и представляют собой различные производные от , оцененный в .

Аналогично внешнему случаю: как только b найдено, мы знаем, что все точки на расстоянии b /4 от c находятся внутри множества Мандельброта.

С оценкой внутреннего расстояния возникают две практические проблемы: во-первых, нам нужно найти именно, а во-вторых, нам нужно найти именно так. Проблема с заключается в том, что сходимость к путем итерации теоретически требует бесконечного числа операций. Проблема с любым данным заключается в том, что иногда из-за ошибок округления период ошибочно идентифицируется как целое число, кратное реальному периоду (например, обнаруживается период 86, тогда как действительный период равен только 43=86/2). В таком случае расстояние завышено, т. е. заявленный радиус может содержать точки вне множества Мандельброта.

3D-вид: наименьшее абсолютное значение орбиты внутренних точек множества Мандельброта.

Проверка кардиоиды/лампочки

[ редактировать ]

Один из способов улучшить расчеты — заранее выяснить, лежит ли данная точка внутри кардиоиды или в колбе периода 2. Прежде чем передавать комплексное значение через алгоритм времени выхода, сначала убедитесь, что:

,
,
,

где x представляет собой реальное значение точки, а y — мнимое значение. Первые два уравнения определяют, что точка находится внутри кардиоиды, последнее — лампочки периода 2.

Кардиоидный тест можно эквивалентно выполнить без квадратного корня:

Почки 3-го и более высокого порядка не имеют эквивалентных раковин, поскольку они не являются идеально круглыми. [11] Однако можно определить, находятся ли точки внутри кругов, вписанных в эти луковицы более высокого порядка, что предотвращает повторение многих, хотя и не всех, точек в луковице.

Проверка периодичности

[ редактировать ]

Чтобы избежать необходимости выполнять огромное количество итераций для точек внутри набора, можно выполнить проверку периодичности, которая проверяет, была ли достигнута точка, достигнутая при итерации пикселя, ранее. Если это так, пиксель не может расходиться и должен находиться в наборе. Проверка периодичности является компромиссом, поскольку необходимость запоминать точки требует затрат на инструкции по управлению данными и память, но экономит вычислительные инструкции. Однако проверка только одной предыдущей итерации может обнаружить множество периодов с небольшими затратами на производительность. Например, в цикле while приведенного выше псевдокода внесите следующие изменения:

xold := 0
yold := 0
period := 0
while (x*x + y*y ≤ 2*2 and iteration < max_iteration) do
    xtemp := x*x - y*y + x0
    y := 2*x*y + y0
    x := xtemp
    iteration := iteration + 1 
 
    if x ≈ xold and y ≈ yold then
        iteration := max_iteration  /* Set to max for the color plotting */
        break        /* We are inside the Mandelbrot set, leave the while loop */
 
    period:= period + 1
    if period > 20 then
        period := 0
        xold := x
        yold := y

Приведенный выше код сохраняет новое значение x и y каждые 20. й итерации, поэтому он может обнаруживать периоды длиной до 20 пунктов.

Отслеживание границ / проверка краев

[ редактировать ]
Обнаружение краев с использованием фильтра Собеля гиперболических компонент множества Мандельброта

Поскольку множество Мандельброта полно , [12] любая точка, заключенная в замкнутую фигуру, границы которой полностью лежат в пределах множества Мандельброта, сама должна принадлежать множеству Мандельброта. Трассировка границ работает, отслеживая лемнискаты различных уровней итерации (цветные полосы) по всему набору, а затем сразу заполняя всю полосу. Это также обеспечивает увеличение скорости, поскольку теперь можно пропустить большое количество точек. [13]

Продолжительность: 7 секунд.
Анимация отслеживания границы

В показанной анимации точки вне набора окрашены с помощью алгоритма времени выхода с 1000 итераций. Отслеживание установленной границы и ее заполнение вместо повторения внутренних точек сокращает общее количество итераций на 93,16%. При более высоком лимите итераций выгода будет еще больше.

Проверка прямоугольника

[ редактировать ]

Проверка прямоугольника — более старый и простой метод построения множества Мандельброта. Основная идея проверки прямоугольника заключается в том, что если каждый пиксель на границе прямоугольника имеет одинаковое количество итераций, то прямоугольник можно безопасно заполнить, используя это количество итераций. Существует несколько вариантов метода проверки прямоугольников, однако все они медленнее, чем метод трассировки границ, поскольку в конечном итоге они вычисляют больше пикселей. Один вариант просто вычисляет угловые пиксели каждого прямоугольника, однако это приводит к повреждению изображений чаще, чем вычисление всей границы, поэтому он работает достаточно хорошо только в том случае, если используются только маленькие прямоугольники размером около 6x6 пикселей и без рекурсии из больших блоков. ( Метод фрактинта .)

Самый простой метод проверки прямоугольников заключается в проверке границ прямоугольников одинакового размера, напоминающих сетку. (Алгоритм Мариани.) [14]

Более быстрый и немного более продвинутый вариант — сначала рассчитать блок большего размера, скажем, 25x25 пикселей. Если вся граница поля имеет один и тот же цвет, просто заполните его тем же цветом. Если нет, то разделите блок на четыре блока размером 13x13 пикселей, повторно используя уже вычисленные пиксели в качестве внешней границы и разделив внутренние «перекрестные» пиксели между внутренними блоками. Снова заполните те поля, у которых есть только один цвет границы. А те блоки, которые этого не делают, разделите теперь на четыре блока размером 7x7 пикселей. А потом те, что "проваливаются" в коробки 4х4. (Алгоритм Мариани-Сильвера.)

Еще быстрее — разделить коробки пополам, а не на четыре. Тогда может быть оптимальным использовать коробки с соотношением сторон 1,4:1 , чтобы их можно было разделить так же, как листы формата А3 складываются в листы формата А4 и А5. (Подход DIN.)

Как и при трассировке границ, проверка прямоугольников работает только в областях с одним дискретным цветом. Но даже если внешняя область использует плавную/непрерывную окраску, проверка прямоугольников все равно ускорит дорогостоящую внутреннюю область множества Мандельброта. Если только внутренняя область не использует какой-либо метод плавной окраски, например, оценку внутреннего расстояния .

Использование симметрии

[ редактировать ]

Горизонтальная симметрия множества Мандельброта позволяет пропускать части процесса рендеринга при наличии реальной оси в конечном изображении. Однако независимо от того, какая часть зеркально отображается, будет отображено одинаковое количество точек.

Множества Джулии имеют симметрию относительно начала координат. Это означает, что квадрант 1 и квадрант 3 симметричны, а квадрант 2 и квадрант 4 симметричны. Поддержка симметрии для множеств Мандельброта и Жюлиа требует разного подхода к симметрии для двух разных типов графов.

Многопоточность

[ редактировать ]

Рендеринг множеств Мандельброта и Джулии в режиме Escape-Time чрезвычайно хорошо подходит для параллельной обработки. На многоядерных машинах область, подлежащая построению, может быть разделена на ряд прямоугольных областей, которые затем могут быть предоставлены как набор задач для обработки пулом потоков рендеринга. Это досадная параллель [15] вычислительная проблема. (Обратите внимание, что наилучшего ускорения можно добиться, если сначала исключить симметричные области графика, а затем разделить оставшиеся уникальные области на прямоугольные области.) [16]

Вот короткое видео, показывающее, как множество Мандельброта визуализируется с использованием многопоточности и симметрии, но без отслеживания границ:

Продолжительность: 11 секунд.
Это короткое видео, показывающее рендеринг множества Мандельброта с использованием многопоточности и симметрии, но с отключенным следованием границам.

Наконец, вот видео, показывающее то же изображение множества Мандельброта, визуализируемое с использованием многопоточности, симметрии и следования границам:

Продолжительность: 3 секунды.
Это короткое видео, показывающее рендеринг множества Мандельброта с использованием следования границам, многопоточности и симметрии.


Теория возмущений и рядовая аппроксимация

[ редактировать ]

Очень сильно увеличенные изображения требуют большей точности, чем стандартные 64–128 бит или около того, которые обеспечивают большинство аппаратных модулей с плавающей запятой , что требует от рендереров использовать медленные «BigNum» или « произвольной точности математические библиотеки » для вычислений. Однако этот процесс можно ускорить, используя теорию возмущений . Данный

как итерация, так и небольшой эпсилон и дельта, это тот случай, когда

или

поэтому, если кто-то определяет

можно вычислить одну точку (например, центр изображения) с помощью высокоточной арифметики ( z ), дав опорную орбиту , а затем вычислить множество точек вокруг нее с точки зрения различных начальных смещений дельта плюс вышеуказанная итерация для эпсилон, где epsilon-zero установлен в 0. Для большинства итераций epsilon не требуется более 16 значащих цифр, и, следовательно, для получения наиболее точного изображения можно использовать аппаратные средства с плавающей запятой. [17] Часто встречаются области, где орбиты точек настолько расходятся с опорной орбитой, что требуется дополнительная точность в этих точках или же требуются дополнительные локальные, рассчитанные с высокой точностью опорные орбиты. Измеряя расстояние по орбите между опорной точкой и точкой, рассчитанной с низкой точностью, можно обнаружить, что правильно вычислить точку невозможно, и расчет можно остановить. Эти неправильные точки впоследствии могут быть пересчитаны, например, из другой более близкой контрольной точки.

Далее можно аппроксимировать стартовые значения для точек низкой точности усеченным рядом Тейлора , что часто позволяет пропустить значительное количество итераций. [18] Рендереры, реализующие эти методы, общедоступны и обеспечивают ускорение обработки сильно увеличенных изображений примерно на два порядка. [19]

Альтернативное объяснение вышесказанного:

Для центральной точки диска и его итерации , и произвольная точка диска и его итерации , можно определить следующие итерационные отношения:

С . Последовательные итерации можно найти, используя следующее:

Теперь из исходного определения:

,

Отсюда следует, что:

Поскольку итеративные отношения связывают произвольную точку с центральной точкой с помощью очень небольшого изменения , то большая часть итераций также малы и могут быть рассчитаны с использованием аппаратных средств с плавающей запятой.

Однако для каждой произвольной точки диска можно вычислить значение для заданного значения. без необходимости перебирать последовательность из , выражая как степенной ряд .

С .

Теперь, учитывая итерационное уравнение , можно вычислить коэффициенты степенного ряда для каждого :

Следовательно, отсюда следует, что:

Коэффициенты в степенном ряду можно рассчитать как итеративный ряд, используя только значения из итераций центральной точки. , и не меняться ни для какой произвольной точки диска. Если очень маленький, должна быть вычислена с достаточной точностью, используя лишь несколько членов степенного ряда. Поскольку контуры выхода Мандельброта «непрерывны» на комплексной плоскости, если время ухода точки было рассчитано, то время ухода соседних точек должно быть одинаковым. Интерполяция соседних точек должна дать хорошую оценку того, с чего начать ряд.

Кроме того, отдельная интерполяция точек реальной оси и точек мнимой оси должна обеспечить как верхнюю, так и нижнюю границу вычисляемой точки. Если оба результата одинаковы (т.е. оба ускользают или не ускользают), то разница может использоваться для отказа до тех пор, пока не будут установлены верхняя и нижняя границы. Если аппаратное обеспечение с плавающей запятой может использоваться для итерации серии, то существует связь между тем, сколько итераций может быть выполнено за время, необходимое для использования программного обеспечения BigNum для вычисления заданного числа. . Если разница между границами превышает количество итераций, можно выполнить двоичный поиск с помощью программного обеспечения BigNum, последовательно сокращая разрыв вдвое, пока не станет более эффективным по времени поиск управляющего значения с использованием оборудования с плавающей запятой.

  1. ^ «Новичок: как сопоставить цвета в множестве Мандельброта?» . www.fractalforums.com . Май 2007 г. Архивировано из оригинала 9 сентября 2022 г. Проверено 11 февраля 2020 г.
  2. ^ Гарсия, Фрэнсис; Анхель Фернандес; Хавьер Барралло; Луис Мартин. «Раскраска динамических систем в комплексной плоскости» (PDF ) Архивировано (PDF) 30 ноября. из оригинала Получено 21 января. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  3. ^ Линас Вепстас. «Перенормировка выхода Мандельброта» . Архивировано из оригинала 14 февраля 2020 года . Проверено 11 февраля 2020 г.
  4. ^ Перейти обратно: а б Альберт Лобо. «Внутренние и внешние границы расстояний множества Мандельброта» . Архивировано из оригинала 9 сентября 2022 года . Проверено 29 апреля 2021 г.
  5. ^ Уилсон, доктор Линдси Роберт (2012). «Метод оценки расстояния для рисования множеств Мандельброта и Жюлиа» (PDF) . Архивировано (PDF) из оригинала 3 мая 2021 года . Проверено 3 мая 2021 г.
  6. ^ Шерита, Арно (2016). «Методы обнаружения границ с помощью оценщиков расстояний» . Архивировано из оригинала 18 декабря 2022 года . Проверено 2 января 2023 г.
  7. ^ Кристенсен, Микаэль Хвидтфельдт (2011). «Трехмерные фракталы с оценкой расстояния (V): лампочка Мандельбулбы и различные приближения DE» . Архивировано из оригинала 13 мая 2021 года . Проверено 10 мая 2021 г.
  8. ^ Данг, Юмей; Луи Кауфман ; Дэниел Сандин (2002). «Глава 3.3: Формула оценки расстояния». Гиперкомплексные итерации: оценка расстояния и фракталы более высоких измерений (PDF) . Всемирная научная. стр. 17–18. Архивировано (PDF) из оригинала 23 марта 2021 года . Проверено 29 апреля 2021 г.
  9. ^ Пейтген, Хайнц-Отто; Рихтер Питер (1986). Красота фракталов . Гейдельберг: Springer-Verlag. ISBN  0-387-15851-0 .
  10. ^ Пейтген, Хайнц-Отто; Саупе Дитмар (1988). Наука фрактальных изображений . Нью-Йорк: Springer Verlag. стр. 202. ИСБН  0-387-96608-0 .
  11. ^ «Математика почек Мандельброта» . Архивировано из оригинала 14 февраля 2020 года . Проверено 11 февраля 2020 г.
  12. ^ Дуади, Адриан; Хаббард, Джон (2009). «Исследование множества Мандельброта. Исследование множества Мандельброта. Записки Орсе» . Проверено 9 апреля 2023 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  13. ^ «Метод отслеживания границ» . Архивировано из оригинала 20 февраля 2015 года.
  14. ^ Дьюдни, АК (1989). «Компьютерные развлечения, февраль 1989 года; Экскурсия по Мандельброту, расположенному на борту Мандельбуса». Научный американец . п. 111. JSTOR   24987149 . (требуется подписка)
  15. ^ http://courses.cecs.anu.edu.au/courses/COMP4300/lectures/embParallel.4u.pdf. Архивировано 27 января 2020 г. в Wayback Machine. [ только URL-адрес PDF ]
  16. ^ http://cseweb.ucsd.edu/groups/csag/html/teaching/cse160s05/lectures/Lecture14.pdf. Архивировано 26 января 2020 г. в Wayback Machine. [ только URL-адрес PDF ]
  17. ^ «Суперфрактальная вещь — рендеринг множества Мандельброта произвольной точности на Java» . Архивировано из оригинала 30 июня 2020 года . Проверено 11 февраля 2020 г.
  18. ^ КИ Мартин. «Суперфрактальная математика» (PDF) . Архивировано из оригинала (PDF) 28 июня 2014 года . Проверено 11 февраля 2020 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  19. ^ «Каллес Фракталер 2» . Архивировано из оригинала 24 февраля 2020 года . Проверено 11 февраля 2020 г.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e5e08ab2e98fb9c0bc308123302bd3cd__1714614480
URL1:https://arc.ask3.ru/arc/aa/e5/cd/e5e08ab2e98fb9c0bc308123302bd3cd.html
Заголовок, (Title) документа по адресу, URL1:
Plotting algorithms for the Mandelbrot set - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)