Algoritmos de representación gráfica del conjunto de Mandelbrot

Algoritmos y métodos para representar gráficamente el conjunto de Mandelbrot en un dispositivo informático

Imagen fija de una película de aumento creciente en 0,001643721971153 − 0,822467633298876 i

Imagen fija de una animación de aumento creciente

Existen muchos programas y algoritmos que se utilizan para representar gráficamente el conjunto de Mandelbrot y otros fractales , algunos de los cuales se describen en software de generación de fractales . Estos programas utilizan una variedad de algoritmos para determinar el color de los píxeles individuales de manera eficiente.

Algoritmo de tiempo de escape

El algoritmo más simple para generar una representación del conjunto de Mandelbrot se conoce como algoritmo de "tiempo de escape". Se realiza un cálculo repetitivo para cada punto x , y en el área del gráfico y, en función del comportamiento de ese cálculo, se elige un color para ese píxel.

Algoritmo de tiempo de escape ingenuo no optimizado

En los algoritmos de tiempo de escape optimizados y no optimizados, las posiciones x e y de cada punto se utilizan como valores iniciales en un cálculo repetitivo o iterativo (descrito en detalle a continuación). El resultado de cada iteración se utiliza como valores iniciales para la siguiente. Los valores se comprueban durante cada iteración para ver si han alcanzado una condición crítica de "escape" o "rescate". Si se alcanza esa condición, se detiene el cálculo, se dibuja el píxel y se examina el siguiente punto x , y . Para algunos valores iniciales, el escape se produce rápidamente, después de solo una pequeña cantidad de iteraciones. Para valores iniciales muy cercanos pero que no están en el conjunto, pueden necesitarse cientos o miles de iteraciones para escapar. Para valores dentro del conjunto de Mandelbrot, el escape nunca se producirá. El programador o usuario debe elegir cuántas iteraciones (o cuánta "profundidad") desea examinar. Cuanto mayor sea el número máximo de iteraciones, más detalles y sutilezas surgirán en la imagen final, pero más tiempo llevará calcular la imagen fractal.

Las condiciones de escape pueden ser simples o complejas. Debido a que ningún número complejo con una parte real o imaginaria mayor que 2 puede ser parte del conjunto, una solución común es escapar cuando cualquiera de los coeficientes excede 2. Un método computacionalmente más complejo que detecta los escapes antes, es calcular la distancia desde el origen utilizando el teorema de Pitágoras , es decir, determinar el valor absoluto , o módulo , del número complejo. Si este valor excede 2, o equivalentemente, cuando la suma de los cuadrados de las partes real e imaginaria excede 4, el punto ha alcanzado el escape. Las variaciones de representación más intensivas computacionalmente incluyen el método Buddhabrot , que encuentra puntos de escape y traza sus coordenadas iteradas.

El color de cada punto representa la rapidez con la que los valores alcanzaron el punto de escape. A menudo, se utiliza el negro para mostrar los valores que no logran escapar antes del límite de iteración y se utilizan colores gradualmente más brillantes para los puntos que escapan. Esto proporciona una representación visual de cuántos ciclos se necesitaron antes de alcanzar la condición de escape.

Para representar una imagen de este tipo, la región del plano complejo que estamos considerando se subdivide en una cierta cantidad de píxeles . Para colorear cualquiera de esos píxeles, sea el punto medio de ese píxel. Ahora iteramos el punto crítico 0 bajo , verificando en cada paso si el punto de la órbita tiene un módulo mayor que 2. Cuando este es el caso, sabemos que no pertenece al conjunto de Mandelbrot y coloreamos nuestro píxel de acuerdo con la cantidad de iteraciones utilizadas para averiguarlo. De lo contrario, seguimos iterando hasta una cantidad fija de pasos, después de lo cual decidimos que nuestro parámetro está "probablemente" en el conjunto de Mandelbrot, o al menos muy cerca de él, y coloreamos el píxel de negro. ${\displaystyle c}$ ${\displaystyle P_{c}}$ ${\displaystyle c}$

En pseudocódigo , este algoritmo se vería de la siguiente manera. El algoritmo no utiliza números complejos y simula manualmente operaciones con números complejos utilizando dos números reales, para aquellos que no tienen un tipo de datos complejo . El programa se puede simplificar si el lenguaje de programación incluye operaciones con tipos de datos complejos.

Para cada píxel (Px, Py) de la pantalla, haga lo siguiente: x0 := coordenada x escalada del píxel (escalada para estar en la escala X de Mandelbrot (-2,00, 0,47)) y0 := coordenada y escalada del píxel (escalada para ubicarse en la escala Y de Mandelbrot (-1,12, 1,12)) x := 0.0 y := 0.0 iteración := 0 iteración máxima := 1000 mientras (x*x + y*y ≤ 2*2 Y iteración < máx_iteración) hacer xtemp := x*x - y*y + x0 y := 2*x*y + y0 x := xtemp iteración := iteración + 1  color := paleta[iteración] trama(Px, Py, color)

Aquí, relacionando el pseudocódigo con , y : ${\displaystyle c}$ ${\displaystyle z}$ ${\displaystyle P_{c}}$

• ${\displaystyle z=x+iy\ }$
• ${\displaystyle z^{2}=x^{2}+2ixy}$- ${\displaystyle y^{2}\ }$
• ${\displaystyle c=x_{0}+iy_{0}\ }$

y así, como se puede ver en el pseudocódigo en el cálculo de x e y :

• ${\displaystyle x=\mathop {\mathrm {Re} } (z^{2}+c)=x^{2}-y^{2}+x_{0}}$y ${\displaystyle y=\mathop {\mathrm {Im} } (z^{2}+c)=2xy+y_{0}.\ }$

Para obtener imágenes coloridas del conjunto, la asignación de un color a cada valor del número de iteraciones ejecutadas se puede realizar utilizando una de varias funciones (lineal, exponencial, etc.). Una forma práctica, sin ralentizar los cálculos, es utilizar el número de iteraciones ejecutadas como una entrada a una paleta inicializada al inicio. Si la tabla de colores tiene, por ejemplo, 500 entradas, entonces la selección de colores es n  mod 500, donde n es el número de iteraciones.

Algoritmos de tiempo de escape optimizados

El código de la sección anterior utiliza un bucle while interno no optimizado para mayor claridad. En la versión no optimizada, se deben realizar cinco multiplicaciones por iteración. Para reducir la cantidad de multiplicaciones, se puede utilizar el siguiente código para el bucle while interno:

x2:= 0y2:= 0en:= 0mientras (x2 + y2 ≤ 4 y iteración < max_iteration) hacer x:= x2 - y2 + x0 y:= w - x2 - y2 + y0 x2:= x * x y2:= y * y w:= (x + y) * (x + y) iteración:= iteración + 1

El código anterior funciona mediante una simplificación algebraica de la multiplicación compleja:

${\displaystyle {\begin{aligned}(iy+x)^{2}&=-y^{2}+2iyx+x^{2}\\&=x^{2}-y^{2}+2iyx\end{aligned}}}$

Utilizando la identidad anterior, el número de multiplicaciones se puede reducir a tres en lugar de cinco.

El bucle while interno anterior se puede optimizar aún más expandiendo w a

${\displaystyle w=x^{2}+2xy+y^{2}}$

Sustituir w en los rendimientos y, por lo tanto, calcular w ya no es necesario. ${\displaystyle y=w-x^{2}-y^{2}+y_{0}}$ ${\displaystyle y=2xy+y_{0}}$

El pseudocódigo optimizado adicional para lo anterior es:

x2:= 0y2:= 0mientras (x2 + y2 ≤ 4 y iteración < max_iteration) hacer y:= 2 * x * y + y0 x:= x2 - y2 + x0 x2:= x * x y2:= y * y iteración:= iteración + 1

Tenga en cuenta que en el pseudocódigo anterior, parece aumentar el número de multiplicaciones en 1, pero como 2 es el multiplicador, el código se puede optimizar mediante . ${\displaystyle 2xy}$ ${\displaystyle (x+x)y}$

Rescate de derivados o "derbail"

Un ejemplo del fino detalle que se puede lograr con el uso de derbail, generado con 1024 muestras

Es común verificar la magnitud de z después de cada iteración, pero hay otro método que podemos usar que puede converger más rápido y revelar la estructura dentro de los conjuntos de Julia .

En lugar de verificar si la magnitud de z después de cada iteración es mayor que un valor dado, podemos verificar si la suma de cada derivada de z hasta el paso de iteración actual es mayor que un valor de rescate dado ^{[ cita requerida ]} :

${\displaystyle z_{n}^{\prime }:=(2*z_{n-1}^{\prime }*z_{n-1})+1}$

El tamaño del valor dbail puede mejorar el detalle de las estructuras reveladas dentro del método dbail con valores muy grandes.

Es posible encontrar derivadas automáticamente aprovechando la diferenciación automática y calculando las iteraciones utilizando números duales ^{[ cita requerida ]} .

Agujero causado por problemas de precisión

La representación de fractales con la técnica derbail a menudo puede requerir una gran cantidad de muestras por píxel, ya que puede haber problemas de precisión que generan detalles finos y pueden dar como resultado imágenes ruidosas incluso con muestras de cientos o miles. ^{[ cita requerida ]}

Código Python:

Derbail utilizado en un set de Julia del barco en llamas

def  mand_der ( c0 :  complejo ,  límite :  int = 1024 ): def  abs_square ( c :  complejo ): devuelve  c . real ** 2  +  c . imag ** 2 dfianza  =  1e6 c  =  c0 corriente continua  =  1  +  0 j suma_dc  =  0  +  0 j para  n  en  el rango ( 1 ,  límite ): c  =  c ** 2  +  c0 cc =  2 * cc * c  +  1 suma_dc  +=  dc si  abs_cuadrado ( dc_suma )  >=  dbail : volver  n devuelve  0

Algoritmos de coloración

Además de representar gráficamente el conjunto, se han desarrollado diversos algoritmos para

• Colorear eficientemente el conjunto de una manera estéticamente agradable.
• Mostrar estructuras de datos (visualización científica)

Coloración del histograma

Un método de coloración más complejo implica el uso de un histograma que empareja cada píxel con el número máximo de iteraciones de dicho píxel antes del escape/rescate. Este método distribuirá los colores de manera uniforme en la misma área general y, lo que es importante, es independiente del número máximo de iteraciones elegido. ^[1]

Este algoritmo consta de cuatro pasos. El primer paso implica el cálculo de los recuentos de iteraciones asociados a cada píxel (pero sin que se grafica ningún píxel). Estos se almacenan en una matriz: IterationCounts[x][y], donde x e y son las coordenadas x e y de dicho píxel en la pantalla respectivamente.

El primer paso del segundo paso es crear una matriz de tamaño n , que es el recuento máximo de iteraciones: NumIterationsPerPixel. A continuación, se debe iterar sobre la matriz de pares de recuento de iteraciones-píxeles, IterationCounts[][], y recuperar el recuento de iteraciones guardado de cada píxel, i , mediante, por ejemplo, i = IterationCounts[x][y]. Después de recuperar el recuento de iteraciones i de cada píxel , es necesario indexar NumIterationsPerPixel por i e incrementar el valor indexado (que inicialmente es cero), por ejemplo, NumIterationsPerPixel[ i ] = NumIterationsPerPixel[ i ] + 1 .

para (x = 0; x < ancho; x++) hacer  para (y = 0; y < alto; y++) hacer i:= IteracionesConteos[x][y] Número de iteraciones por píxel[i]++

El tercer paso itera a través de la matriz NumIterationsPerPixel y suma todos los valores almacenados, guardándolos en total . El índice de la matriz representa la cantidad de píxeles que alcanzaron ese recuento de iteraciones antes del rescate.

total: = 0 para (i = 0; i < máx_iteraciones; i++) hacer total += NúmIteracionesPorPíxel[i]

Después de esto, comienza el cuarto paso y se indexan todos los valores de la matriz IterationCounts y, para cada recuento de iteración i asociado con cada píxel, el recuento se agrega a una suma global de todos los recuentos de iteración de 1 a i en la matriz NumIterationsPerPixel. Luego, este valor se normaliza dividiendo la suma por el valor total calculado anteriormente.

hue[][]:= 0.0 para (x = 0; x < ancho; x++) hacer  para (y = 0; y < alto; y++) hacer iteración:= IterationCounts[x][y] para (i = 0; i <= iteración; i++) hacer hue[x][y] += NumIterationsPerPixel[i] / total /* Debe ser una división de punto flotante. */...color = paleta[tono[m, n]]...

Finalmente, el valor calculado se utiliza, por ejemplo, como índice de una paleta de colores.

Este método se puede combinar con el método de coloración suave que se muestra a continuación para obtener imágenes estéticamente más agradables.

Coloración continua (suave)

El algoritmo de tiempo de escape es popular por su simplicidad. Sin embargo, crea bandas de color que, como un tipo de aliasing , pueden restar valor estético a una imagen. Esto se puede mejorar utilizando un algoritmo conocido como "recuento de iteraciones normalizado", ^{[2] [3]} que proporciona una transición suave de colores entre iteraciones. El algoritmo asocia un número real con cada valor de z utilizando la conexión del número de iteración con la función potencial . Esta función está dada por ${\displaystyle \nu }$

${\displaystyle \phi (z)=\lim _{n\to \infty }(\log |z_{n}|/P^{n}),}$

donde z _n es el valor después de n iteraciones y P es la potencia a la que z se eleva en la ecuación del conjunto de Mandelbrot ( z _{n +1}  =  z _n ^P  +  c , P es generalmente 2).

Si elegimos un radio de rescate grande N (por ejemplo, 10 ¹⁰⁰ ), tenemos que

${\displaystyle \log |z_{n}|/P^{n}=\log(N)/P^{\nu (z)}}$

para algún número real , y este es ${\displaystyle \nu (z)}$

${\displaystyle \nu (z)=n-\log _{P}(\log |z_{n}|/\log(N)),}$

y como n es el primer número de iteración tal que | z _n | > N , el número que restamos de n está en el intervalo [0, 1).

Para la coloración debemos tener una escala cíclica de colores (construida matemáticamente, por ejemplo) y que contenga H colores numerados de 0 a H  − 1 ( H = 500, por ejemplo). Multiplicamos el número real por un número real fijo que determine la densidad de colores en la imagen, tomamos la parte integral de este número módulo  H y lo usamos para buscar el color correspondiente en la tabla de colores. ${\displaystyle \nu (z)}$

Por ejemplo, modificando el pseudocódigo anterior y también utilizando el concepto de interpolación lineal obtendríamos

Para cada píxel (Px, Py) de la pantalla, haga lo siguiente: x0:= coordenada x escalada del píxel (escalada para estar en la escala X de Mandelbrot (-2,5, 1)) y0:= coordenada y escalada del píxel (escalada para estar en la escala Y de Mandelbrot (-1, 1)) x:= 0.0 y:= 0.0 iteración:= 0 iteración máxima:= 1000 // Aquí se elige N = 2^8 como un radio de rescate razonable. mientras x*x + y*y ≤ (1 << 16) y iteración < max_iteration hacer xtemp:= x*x - y*y + x0 y:= 2*x*y + y0 x:= xtemp iteración:= iteración + 1 // Se utiliza para evitar problemas de punto flotante con puntos dentro del conjunto.  si iteración < max_iteration entonces  // se elimina la raíz cuadrada del término interno utilizando reglas de simplificación logarítmica. log_zn:= log(x*x + y*y) / 2 nu:= iniciar sesión(log_zn / iniciar sesión(2)) / iniciar sesión(2) // Reorganizar la función potencial.  // Dividir log_zn por log(2) en lugar de log(N = 1<<8)  // porque queremos que toda la paleta vaya desde el  centro hasta el radio 2, NO nuestro radio de rescate. iteración:= iteración + 1 - nu color1:= paleta[piso(iteración)] color2:= paleta[piso(iteración) + 1] // iteración % 1 = parte fraccionaria de la iteración. color:= interpolación_lineal(color1, color2, iteración % 1) trama(Px, Py, color)

Iteraciones cíclicas y mapeadas exponencialmente

Coloración cíclica exponencial en el espacio de color LCH con sombreado

Normalmente, cuando renderizamos un fractal, el rango en el que aparecen los colores de una paleta determinada a lo largo del fractal es estático. Si deseamos desplazar la ubicación con respecto al borde del fractal o ajustar su paleta para que se repita de una manera específica, hay algunos cambios simples que podemos hacer al tomar el recuento de iteraciones final antes de pasarlo para elegir un elemento de nuestra paleta.

Cuando hayamos obtenido el recuento de iteraciones, podemos hacer que el rango de colores sea no lineal. Al elevar un valor normalizado al rango [0,1] a una potencia n , se convierte un rango lineal en un rango exponencial, lo que en nuestro caso puede hacer que los colores aparezcan en el exterior del fractal y permitirnos resaltar otros colores o acercar toda la paleta al borde.

${\displaystyle v=((\mathbf {i} /max_{i})^{\mathbf {S} }\mathbf {N} )^{1.5}{\bmod {\mathbf {N} }}}$

donde i es nuestro recuento de iteraciones después del rescate, max_i es nuestro límite de iteraciones, S es el exponente al que elevamos los iteradores y N es la cantidad de elementos en nuestra paleta. Esto escala el recuento de iteradores de manera no lineal y escala la paleta para que realice ciclos aproximadamente proporcionales al zoom.

Luego podemos conectar v a cualquier algoritmo que deseemos para generar un color.

Pasar iteraciones a un color directamente

Ejemplo de coloración LCH cíclica mapeada exponencialmente sin sombreado

Una cosa que podemos considerar es evitar tener que lidiar con una paleta o con la combinación de colores. En realidad, hay varios métodos que podemos aprovechar para generar una coloración uniforme y uniforme creando el color en el momento.

v se refiere a un recuento de iteradores cíclicos mapeados exponencialmente y normalizados

f(v) se refiere a laFunción de transferencia sRGB

Un método ingenuo para generar un color de esta manera es escalar directamente v a 255 y pasarlo a RGB como tal.

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

Una falla de esto es que el RGB no es lineal debido a la gamma; considere en cambio el sRGB lineal. Pasar de RGB a sRGB utiliza una función de compresión inversa en los canales. Esto hace que la gamma sea lineal y nos permite sumar correctamente los colores para el muestreo.

srgb = [v * 255, v * 255, v * 255]

Gradiente HSV

Coloración HSV

La coloración HSV se puede lograr asignando el recuento de iteradores de [0,max_iter) a [0,360), llevándolo a la potencia de 1,5 y luego al módulo 360.Luego podemos simplemente tomar el recuento de iteradores mapeado exponencialmente en el valor y devolverlo.

hsv = [potencial de potencia ((i / máx) * 360, 1,5) % 360, 100, (i / máx) * 100]

Este método también se aplica a HSL, excepto que en su lugar pasamos una saturación del 50%.

hsl = [potencial de potencia ((i / máx) * 360, 1,5) % 360, 50, (i / máx) * 100]

Gradiente LCH

Coloración LCH

Uno de los métodos de coloración más uniformes desde el punto de vista perceptual consiste en pasar el recuento de iteraciones procesado a LCH. Si utilizamos el método cíclico y de mapeo exponencial mencionado anteriormente, podemos tomar el resultado de eso en los canales Luma y Chroma. También podemos mapear exponencialmente el recuento de iteraciones y escalarlo a 360, y pasar este módulo 360 al tono.

${\textstyle {\begin{array}{lcl}x&\in &\mathbb {Q+} \\s_{i}&=&(i/max_{i})^{\mathbf {x} }\\v&=&1.0-cos^{2}(\pi s_{i})\\L&=&75-(75v)\\C&=&28+(75-75v)\\H&=&(360s_{i})^{1.5}{\bmod {3}}60\end{array}}}$

Un problema que queremos evitar aquí son los colores fuera de gama. Esto se puede lograr con un pequeño truco basado en el cambio de los colores dentro de la gama en relación con la luminancia y el croma. A medida que aumentamos la luminancia, debemos disminuir el croma para permanecer dentro de la gama.

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];

Algoritmos de trazado avanzados

Además de los algoritmos de tiempo de escape simples y lentos ya analizados, hay muchos otros algoritmos más avanzados que se pueden utilizar para acelerar el proceso de trazado.

Estimaciones de distancia

Se puede calcular la distancia desde el punto c (en el exterior o en el interior ) hasta el punto más cercano en el límite del conjunto de Mandelbrot. ^{[4] [5]}

Estimación de la distancia exterior

La prueba de la conexidad del conjunto de Mandelbrot proporciona de hecho una fórmula para la función uniformizadora del complemento de (y la derivada de esta función). Mediante el teorema del cuarto de Koebe , se puede estimar la distancia entre el punto medio de nuestro píxel y el conjunto de Mandelbrot hasta un factor de 4. ${\displaystyle M}$

En otras palabras, siempre que el número máximo de iteraciones sea suficientemente alto, se obtiene una imagen del conjunto de Mandelbrot con las siguientes propiedades:

1. Cada píxel que contiene un punto del conjunto de Mandelbrot está coloreado de negro.
2. Cada píxel coloreado de negro está cerca del conjunto de Mandelbrot.

La estimación de la distancia exterior se puede utilizar para colorear todo el complemento del conjunto de Mandelbrot

El límite superior b para la estimación de la distancia de un píxel c (un número complejo) del conjunto de Mandelbrot está dado por ^{[6] [7] [8]}

${\displaystyle b=\lim _{n\to \infty }{\frac {2\cdot |{P_{c}^{n}(c)|\cdot \ln |{P_{c}^{n}(c)}}|}{|{\frac {\partial }{\partial {c}}}P_{c}^{n}(c)|}},}$

dónde

• ${\displaystyle P_{c}(z)\,}$significa polinomio cuadrático complejo
• ${\displaystyle P_{c}^{n}(c)}$representa n iteraciones de o , comenzando con : , ; ${\displaystyle P_{c}(z)\to z}$ ${\displaystyle z^{2}+c\to z}$ ${\displaystyle z=c}$ ${\displaystyle P_{c}^{0}(c)=c}$ ${\displaystyle P_{c}^{n+1}(c)=P_{c}^{n}(c)^{2}+c}$
• ${\displaystyle {\frac {\partial }{\partial {c}}}P_{c}^{n}(c)}$es la derivada de con respecto a c. Esta derivada se puede hallar comenzando con y luego . Esto se puede verificar fácilmente utilizando la regla de la cadena para la derivada. ${\displaystyle P_{c}^{n}(c)}$ ${\displaystyle {\frac {\partial }{\partial {c}}}P_{c}^{0}(c)=1}$ ${\displaystyle {\frac {\partial }{\partial {c}}}P_{c}^{n+1}(c)=2\cdot {}P_{c}^{n}(c)\cdot {\frac {\partial }{\partial {c}}}P_{c}^{n}(c)+1}$

La idea detrás de esta fórmula es simple: cuando las líneas equipotenciales para la función potencial están cerca, el número es grande y, por lo tanto, a la inversa, las líneas equipotenciales para la función deberían estar aproximadamente regulares. ${\displaystyle \phi (z)}$ ${\displaystyle |\phi '(z)|}$ ${\displaystyle \phi (z)/|\phi '(z)|}$

Desde el punto de vista de un matemático, esta fórmula sólo funciona en el límite donde n tiende a infinito, pero se pueden encontrar estimaciones muy razonables con sólo unas pocas iteraciones adicionales después de que sale el bucle principal.

Una vez que se encuentra b , por el teorema 1/4 de Koebe, sabemos que no hay ningún punto del conjunto de Mandelbrot con distancia a c menor que b/4 .

La estimación de la distancia se puede utilizar para dibujar el límite del conjunto de Mandelbrot, véase el artículo Conjunto de Julia . En este enfoque, los píxeles que están suficientemente cerca de M se dibujan utilizando un color diferente. Esto crea dibujos donde los "filamentos" delgados del conjunto de Mandelbrot se pueden ver fácilmente. Esta técnica se utiliza con buenos resultados en las imágenes en blanco y negro de los conjuntos de Mandelbrot en los libros "La belleza de los fractales " ^[9] y "La ciencia de las imágenes fractales". ^[10]

A continuación se muestra una muestra de una imagen en blanco y negro generada mediante estimaciones de distancia:

Esta es una imagen en blanco y negro de una parte del conjunto de Mandelbrot generada mediante estimaciones de distancia (DE)

La estimación de distancia también se puede utilizar para representar imágenes 3D de los conjuntos de Mandelbrot y Julia.

Estimación de la distancia interior

Píxeles coloreados según la distancia interior estimada

También es posible estimar la distancia de un punto con periodicidad límite (es decir, hiperbólico ) al límite del conjunto de Mandelbrot. El límite superior b para la estimación de la distancia se da mediante ^[4]

${\displaystyle b={\frac {1-\left|{{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}\right|^{2}}{\left|{{\frac {\partial }{\partial {c}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})+{\frac {\partial }{\partial {z}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0}){\frac {{\frac {\partial }{\partial {c}}}P_{c}^{p}(z_{0})}{1-{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}}}\right|}},}$

dónde

• ${\displaystyle p}$es el periodo,
• ${\displaystyle c}$es el punto a estimar,
• ${\displaystyle P_{c}(z)}$es el polinomio cuadrático complejo ${\displaystyle P_{c}(z)=z^{2}+c}$
• ${\displaystyle P_{c}^{p}(z_{0})}$es la iteración -fold de , comenzando con ${\displaystyle p}$ ${\displaystyle P_{c}(z)\to z}$ ${\displaystyle P_{c}^{0}(z)=z_{0}}$
• ${\displaystyle z_{0}}$es cualquiera de los puntos que forman el atractor de las iteraciones de comenzando con ; satisface , ${\displaystyle p}$ ${\displaystyle P_{c}(z)\to z}$ ${\displaystyle P_{c}^{0}(z)=c}$ ${\displaystyle z_{0}}$ ${\displaystyle z_{0}=P_{c}^{p}(z_{0})}$
• ${\displaystyle {\frac {\partial }{\partial {c}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}$, , y son varios derivados de , evaluados en . ${\displaystyle {\frac {\partial }{\partial {z}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}$ ${\displaystyle {\frac {\partial }{\partial {c}}}P_{c}^{p}(z_{0})}$ ${\displaystyle {\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}$ ${\displaystyle P_{c}^{p}(z)}$ ${\displaystyle z_{0}}$

De manera análoga al caso exterior, una vez que se encuentra b , sabemos que todos los puntos dentro de la distancia de b /4 desde c están dentro del conjunto de Mandelbrot.

Existen dos problemas prácticos con la estimación de la distancia interior: primero, necesitamos encontrar con precisión, y segundo, necesitamos encontrar con precisión. El problema con es que la convergencia a mediante iteración requiere, teóricamente, un número infinito de operaciones. El problema con cualquier dato es que, a veces, debido a errores de redondeo, un período se identifica falsamente como un múltiplo entero del período real (por ejemplo, se detecta un período de 86, mientras que el período real es solo 43=86/2). En tal caso, la distancia se sobreestima, es decir, el radio informado podría contener puntos fuera del conjunto de Mandelbrot. ${\displaystyle z_{0}}$ ${\displaystyle p}$ ${\displaystyle z_{0}}$ ${\displaystyle z_{0}}$ ${\displaystyle P_{c}(z)}$ ${\displaystyle p}$

Vista 3D: valor absoluto más pequeño de la órbita de los puntos interiores del conjunto de Mandelbrot

Comprobación de cardioide/bulbo

Una forma de mejorar los cálculos es averiguar de antemano si el punto dado se encuentra dentro del cardioide o en el bulbo de período 2. Antes de pasar el valor complejo por el algoritmo de tiempo de escape, primero verifique que:

${\displaystyle p={\sqrt {\left(x-{\frac {1}{4}}\right)^{2}+y^{2}}}}$,

${\displaystyle x\leq p-2p^{2}+{\frac {1}{4}}}$,

${\displaystyle (x+1)^{2}+y^{2}\leq {\frac {1}{16}}}$,

donde x representa el valor real del punto e y el valor imaginario. Las dos primeras ecuaciones determinan que el punto está dentro del cardioide, la última el bulbo de periodo 2.

La prueba cardioide se puede realizar de manera equivalente sin la raíz cuadrada:

${\displaystyle q=\left(x-{\frac {1}{4}}\right)^{2}+y^{2},}$

${\displaystyle q\left(q+\left(x-{\frac {1}{4}}\right)\right)\leq {\frac {1}{4}}y^{2}.}$

Los brotes de tercer orden y superiores no tienen pruebas equivalentes, porque no son perfectamente circulares. ^[11] Sin embargo, es posible encontrar si los puntos están dentro de círculos inscritos dentro de estos bulbos de orden superior, lo que evita que se iteren muchos, aunque no todos, los puntos del bulbo.

Comprobación de periodicidad

Para evitar tener que hacer una gran cantidad de iteraciones para los puntos dentro del conjunto, se puede realizar una comprobación de periodicidad, que comprueba si se ha alcanzado antes un punto al iterar un píxel. Si es así, el píxel no puede divergir y debe estar en el conjunto. La comprobación de periodicidad es una compensación, ya que la necesidad de recordar puntos consume instrucciones de gestión de datos y memoria, pero ahorra instrucciones computacionales. Sin embargo, la comprobación con una sola iteración anterior puede detectar muchos períodos con poca sobrecarga de rendimiento. Por ejemplo, dentro del bucle while del pseudocódigo anterior, realice las siguientes modificaciones:

xantiguo := 0yold := 0periodo := 0mientras (x*x + y*y ≤ 2*2 y iteración < max_iteration) hacer xtemp := x*x - y*y + x0 y := 2*x*y + y0 x := xtemp iteración := iteración + 1  Si x ≈ xold e y ≈ yold entonces iteración := max_iteration /* Establecer en máximo para el trazado de color */ break /*Estamos dentro del conjunto de Mandelbrot, salgamos del bucle while*/  periodo:= periodo + 1 Si el periodo > 20 entonces periodo := 0 xviejo := x yold := y

El código anterior almacena un nuevo valor x e y cada 20 iteraciones, por lo que puede detectar períodos de hasta 20 puntos de longitud.

Rastreo de fronteras / control de bordes

Detección de bordes mediante el filtro Sobel de componentes hiperbólicos del conjunto de Mandelbrot

Como el conjunto de Mandelbrot es completo , ^[12] cualquier punto encerrado por una forma cerrada cuyos bordes se encuentren completamente dentro del conjunto de Mandelbrot debe estar en el conjunto de Mandelbrot. El rastreo de bordes funciona siguiendo las lemniscatas de los diversos niveles de iteración (bandas de colores) alrededor del conjunto y luego llenando toda la banda de una sola vez. Esto también proporciona un aumento de velocidad porque ahora se pueden omitir grandes cantidades de puntos. ^[13]

Animación del trazado de fronteras

En la animación mostrada, los puntos fuera del conjunto se colorean con un algoritmo de tiempo de escape de 1000 iteraciones. Trazar el borde del conjunto y rellenarlo, en lugar de iterar los puntos interiores, reduce el número total de iteraciones en un 93,16 %. Con un límite de iteración más alto, el beneficio sería aún mayor.

Comprobación de rectángulo

La comprobación de rectángulos es un método más antiguo y simple para trazar el conjunto de Mandelbrot. La idea básica de la comprobación de rectángulos es que si cada píxel en el borde de un rectángulo comparte la misma cantidad de iteraciones, entonces el rectángulo se puede rellenar de forma segura utilizando esa cantidad de iteraciones. Hay varias variaciones del método de comprobación de rectángulos, sin embargo, todas ellas son más lentas que el método de trazado de bordes porque terminan calculando más píxeles. Una variante solo calcula los píxeles de las esquinas de cada rectángulo, sin embargo, esto causa imágenes dañadas con más frecuencia que calcular el borde completo, por lo que solo funciona razonablemente bien si solo se utilizan pequeños cuadros de alrededor de 6x6 píxeles y no se recurre a partir de cuadros más grandes. ( Método Fractint ).

El método más simple de verificación de rectángulos consiste en verificar los bordes de rectángulos de igual tamaño, de forma que se asemeje a un patrón de cuadrícula (algoritmo de Mariani). ^[14]

Una variante más rápida y ligeramente más avanzada es calcular primero un cuadro más grande, digamos de 25x25 píxeles. Si todo el borde del cuadro tiene el mismo color, entonces simplemente rellene el cuadro con el mismo color. Si no, divida el cuadro en cuatro cuadros de 13x13 píxeles, reutilizando los píxeles ya calculados como borde exterior y compartiendo los píxeles "cruzados" internos entre los cuadros interiores. Nuevamente, rellene los cuadros que tengan un solo color de borde. Y divida los cuadros que no lo tengan, ahora en cuatro cuadros de 7x7 píxeles. Y luego los que "fallen" en cuadros de 4x4. (Algoritmo de Mariani-Silver).

Una forma aún más rápida de dividir las cajas por la mitad en lugar de en cuatro cajas es utilizar cajas con una relación de aspecto de 1,4:1 , de modo que se puedan dividir de la misma manera que se doblan los papeles A3 en papeles A4 y A5 (el método DIN).

Al igual que con el trazado de bordes, la comprobación de rectángulos solo funciona en áreas con un color discreto. Pero incluso si el área exterior utiliza un coloreado suave/continuo, la comprobación de rectángulos seguirá acelerando el costoso área interior del conjunto de Mandelbrot. A menos que el área interior también utilice algún método de coloreado suave, por ejemplo, la estimación de la distancia interior.

Utilización de la simetría

La simetría horizontal del conjunto de Mandelbrot permite omitir partes del proceso de renderizado cuando el eje real está presente en la imagen final. Sin embargo, independientemente de la parte que se refleje, se renderizará la misma cantidad de puntos.

Los conjuntos de Julia tienen simetría en torno al origen. Esto significa que los cuadrantes 1 y 3 son simétricos, y los cuadrantes 2 y 4 son simétricos. Para admitir la simetría tanto para los conjuntos de Mandelbrot como para los de Julia es necesario manejar la simetría de forma diferente para los dos tipos de gráficos.

Multiprocesamiento

La representación en tiempo de escape de los conjuntos de Mandelbrot y Julia se presta muy bien al procesamiento en paralelo. En máquinas de múltiples núcleos, el área que se va a representar gráficamente se puede dividir en una serie de áreas rectangulares que luego se pueden proporcionar como un conjunto de tareas que se van a representar mediante un grupo de subprocesos de representación. Este es un problema de computación vergonzosamente paralelo ^[15] . (Obsérvese que se obtiene la mejor aceleración excluyendo primero las áreas simétricas del gráfico y luego dividiendo las regiones únicas restantes en áreas rectangulares). ^[16]

Aquí hay un video corto que muestra el conjunto de Mandelbrot que se representa utilizando subprocesos múltiples y simetría, pero sin seguimiento de límites:

Este es un video corto que muestra la representación de un conjunto de Mandelbrot usando subprocesos múltiples y simetría, pero con el seguimiento de límites desactivado.

Finalmente, aquí hay un video que muestra la misma imagen del conjunto de Mandelbrot renderizada usando subprocesamiento múltiple, simetría y seguimiento de límites:

Este es un video corto que muestra la representación de un conjunto de Mandelbrot utilizando seguimiento de límites, subprocesos múltiples y simetría.

Teoría de perturbaciones y aproximación de series

Las imágenes muy ampliadas requieren más que los 64–128 bits de precisión estándar que proporcionan la mayoría de las unidades de punto flotante de hardware , lo que obliga a los renderizadores a utilizar bibliotecas matemáticas lentas "BigNum" o de " precisión arbitraria " para realizar los cálculos. Sin embargo, esto se puede acelerar mediante la explotación de la teoría de perturbaciones .

${\displaystyle z_{n+1}=z_{n}^{2}+c}$

como la iteración, y un pequeño épsilon y delta, es el caso que

${\displaystyle (z_{n}+\epsilon )^{2}+(c+\delta )=z_{n}^{2}+2z_{n}\epsilon +\epsilon ^{2}+c+\delta ,}$

o

${\displaystyle =z_{n+1}+2z_{n}\epsilon +\epsilon ^{2}+\delta ,}$

Así que si uno define

${\displaystyle \epsilon _{n+1}=2z_{n}\epsilon _{n}+\epsilon _{n}^{2}+\delta ,}$

se puede calcular un único punto (por ejemplo, el centro de una imagen) utilizando aritmética de alta precisión ( z ), dando una órbita de referencia , y luego calcular muchos puntos a su alrededor en términos de varios desplazamientos iniciales delta más la iteración anterior para epsilon, donde epsilon-zero se establece en 0. Para la mayoría de las iteraciones, epsilon no necesita más de 16 cifras significativas y, en consecuencia, se puede utilizar el punto flotante de hardware para obtener una imagen mayormente precisa. ^[17] A menudo habrá algunas áreas donde las órbitas de los puntos divergen lo suficiente de la órbita de referencia como para que se necesite precisión adicional en esos puntos, o bien se necesitan órbitas de referencia locales adicionales calculadas con alta precisión. Al medir la distancia de la órbita entre el punto de referencia y el punto calculado con baja precisión, se puede detectar que no es posible calcular el punto correctamente y se puede detener el cálculo. Estos puntos incorrectos se pueden volver a calcular más tarde, por ejemplo, desde otro punto de referencia más cercano.

Además, es posible aproximar los valores iniciales para los puntos de baja precisión con una serie de Taylor truncada , lo que a menudo permite omitir una cantidad significativa de iteraciones. ^[18] Los renderizadores que implementan estas técnicas están disponibles públicamente y ofrecen aceleraciones para imágenes muy magnificadas de alrededor de dos órdenes de magnitud. ^[19]

Una explicación alternativa de lo anterior:

Para el punto central en el disco y sus iteraciones , y un punto arbitrario en el disco y sus iteraciones , es posible definir la siguiente relación iterativa: ${\displaystyle c}$ ${\displaystyle z_{n}}$ ${\displaystyle c+\delta }$ ${\displaystyle z'_{n}}$

${\displaystyle z'_{n}=z_{n}+\epsilon _{n}}$

Con . Las iteraciones sucesivas de se pueden encontrar utilizando lo siguiente: ${\displaystyle \epsilon _{1}=\delta }$ ${\displaystyle \epsilon _{n}}$

${\displaystyle z'_{n+1}={z'_{n}}^{2}+(c+\delta )}$

${\displaystyle z'_{n+1}=(z_{n}+\epsilon _{n})^{2}+c+\delta }$

${\displaystyle z'_{n+1}={z_{n}}^{2}+c+2z_{n}\epsilon _{n}+{\epsilon _{n}}^{2}+\delta }$

${\displaystyle z'_{n+1}=z_{n+1}+2z_{n}\epsilon _{n}+{\epsilon _{n}}^{2}+\delta }$

Ahora, de la definición original:

${\displaystyle z'_{n+1}=z_{n+1}+\epsilon _{n+1}}$,

Resulta que:

${\displaystyle \epsilon _{n+1}=2z_{n}\epsilon _{n}+{\epsilon _{n}}^{2}+\delta }$

Como la relación iterativa relaciona un punto arbitrario con el punto central mediante un cambio muy pequeño , entonces la mayoría de las iteraciones de también son pequeñas y se pueden calcular utilizando hardware de punto flotante. ${\displaystyle \delta }$ ${\displaystyle \epsilon _{n}}$

Sin embargo, para cada punto arbitrario en el disco es posible calcular un valor para un dado sin tener que iterar a través de la secuencia de , expresándose como una serie de potencias de . ${\displaystyle \epsilon _{n}}$ ${\displaystyle \epsilon _{0}}$ ${\displaystyle \epsilon _{n}}$ ${\displaystyle \delta }$

${\displaystyle \epsilon _{n}=A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc }$

Con . ${\displaystyle A_{1}=1,B_{1}=0,C_{1}=0,\dotsc }$

Ahora, dada la ecuación de iteración de , es posible calcular los coeficientes de la serie de potencias para cada : ${\displaystyle \epsilon }$ ${\displaystyle \epsilon _{n}}$

${\displaystyle \epsilon _{n+1}=2z_{n}\epsilon _{n}+{\epsilon _{n}}^{2}+\delta }$

${\displaystyle \epsilon _{n+1}=2z_{n}(A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc )+(A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc )^{2}+\delta }$

${\displaystyle \epsilon _{n+1}=(2z_{n}A_{n}+1)\delta +(2z_{n}B_{n}+{A_{n}}^{2})\delta ^{2}+(2z_{n}C_{n}+2A_{n}B_{n})\delta ^{3}+\dotsc }$

Por tanto, se deduce que:

${\displaystyle A_{n+1}=2z_{n}A_{n}+1}$

${\displaystyle B_{n+1}=2z_{n}B_{n}+{A_{n}}^{2}}$

${\displaystyle C_{n+1}=2z_{n}C_{n}+2A_{n}B_{n}}$

${\displaystyle \vdots }$

Los coeficientes de la serie de potencias se pueden calcular como series iterativas utilizando únicamente valores de las iteraciones del punto central y no cambian para ningún punto arbitrario en el disco. Si es muy pequeño, debería ser calculable con suficiente precisión utilizando únicamente unos pocos términos de la serie de potencias. Como los contornos de escape de Mandelbrot son "continuos" sobre el plano complejo, si se ha calculado el tiempo de escape de un punto, entonces el tiempo de escape de los puntos vecinos de ese punto debería ser similar. La interpolación de los puntos vecinos debería proporcionar una buena estimación de dónde comenzar en la serie. ${\displaystyle z}$ ${\displaystyle \delta }$ ${\displaystyle \epsilon _{n}}$ ${\displaystyle \epsilon _{n}}$

Además, la interpolación separada de los puntos de los ejes reales y de los puntos de los ejes imaginarios debería proporcionar un límite superior e inferior para el punto que se está calculando. Si ambos resultados son iguales (es decir, ambos escapan o no escapan), entonces la diferencia se puede utilizar para recusar hasta que se pueda establecer un límite superior e inferior. Si se puede utilizar hardware de punto flotante para iterar la serie, entonces existe una relación entre la cantidad de iteraciones que se pueden lograr en el tiempo que lleva utilizar el software BigNum para calcular un determinado . Si la diferencia entre los límites es mayor que el número de iteraciones, es posible realizar una búsqueda binaria utilizando el software BigNum, reduciendo sucesivamente a la mitad la brecha hasta que se vuelva más eficiente en términos de tiempo encontrar el valor de escape utilizando hardware de punto flotante. ${\displaystyle \Delta n}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon _{n}}$

Referencias

1. "Novato: ¿Cómo mapear colores en el conjunto de Mandelbrot?". www.fractalforums.com . Mayo de 2007. Archivado desde el original el 9 de septiembre de 2022 . Consultado el 11 de febrero de 2020 .
2. García, Francisco; Ángel Fernández; Javier Barrallo; Luis Martín. "Colorear sistemas dinámicos en el plano complejo" (PDF) . Archivado (PDF) desde el original el 30 de noviembre de 2019 . Consultado el 21 de enero de 2008 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
3. Linas Vepstas. «Renormalizando el escape de Mandelbrot». Archivado desde el original el 14 de febrero de 2020. Consultado el 11 de febrero de 2020 .
4. Albert Lobo. «Límites de distancia interior y exterior para el conjunto de Mandelbrot». Archivado desde el original el 9 de septiembre de 2022. Consultado el 29 de abril de 2021 .
5. Wilson, Dr. Lindsay Robert (2012). "Método de estimación de distancias para dibujar conjuntos de Mandelbrot y Julia" (PDF) . Archivado (PDF) del original el 3 de mayo de 2021 . Consultado el 3 de mayo de 2021 .
6. Chéritat, Arnaud (2016). «Métodos de detección de límites mediante estimadores de distancia». Archivado desde el original el 18 de diciembre de 2022. Consultado el 2 de enero de 2023 .
7. Christensen, Mikael Hvidtfeldt (2011). «Distancia estimada de fractales 3D (V): el bulbo de Mandel y diferentes aproximaciones DE». Archivado desde el original el 13 de mayo de 2021. Consultado el 10 de mayo de 2021 .
8. Dang, Yumei; Louis Kauffman ; Daniel Sandin (2002). «Capítulo 3.3: La fórmula de estimación de distancia». Iteraciones hipercomplejas: estimación de distancia y fractales de mayor dimensión (PDF) . World Scientific. págs. 17–18. Archivado (PDF) del original el 23 de marzo de 2021 . Consultado el 29 de abril de 2021 .
9. Peitgen, Heinz-Otto; Richter Peter (1986). La belleza de los fractales . Heidelberg: Springer-Verlag. ISBN 0-387-15851-0.
10. Peitgen, Heinz-Otto; Saupe Dietmar (1988). La ciencia de las imágenes fractales . Nueva York: Springer-Verlag. pag. 202.ISBN​ 0-387-96608-0.
11. "Mandelbrot Bud Maths". Archivado desde el original el 14 de febrero de 2020. Consultado el 11 de febrero de 2020 .
12. Douady, Adrien; Hubbard, John (2009). "Explorando el conjunto de Mandelbrot. Explorando el conjunto de Mandelbrot. Las notas de Orsay" . Consultado el 9 de abril de 2023 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
13. "Método de trazado de límites". Archivado desde el original el 20 de febrero de 2015.
14. Dewdney, AK (1989). "Recreaciones por computadora, febrero de 1989; un recorrido por el conjunto de Mandelbrot a bordo del Mandelbus". Scientific American . pág. 111. JSTOR  24987149. (se requiere suscripción)
15. http://courses.cecs.anu.edu.au/courses/COMP4300/lectures/embParallel.4u.pdf Archivado el 27 de enero de 2020 en Wayback Machine ^{[ URL básica PDF ]}
16. http://cseweb.ucsd.edu/groups/csag/html/teaching/cse160s05/lectures/Lecture14.pdf Archivado el 26 de enero de 2020 en Wayback Machine ^{[ URL básica PDF ]}
17. "Superfractalthing - Representación de conjuntos de Mandelbrot con precisión arbitraria en Java". Archivado desde el original el 30 de junio de 2020. Consultado el 11 de febrero de 2020 .
18. KI Martin. «Superfractalthing Maths» (PDF) . Archivado desde el original (PDF) el 28 de junio de 2014. Consultado el 11 de febrero de 2020 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
19. "Kalles Fraktaler 2". Archivado desde el original el 24 de febrero de 2020. Consultado el 11 de febrero de 2020 .