速度提升 - 优化

对称

曼德勃罗集合关于平面中的 x 轴对称

colour(x,y) = colour(x,-y)

它与 x 轴的交点（曼德勃罗集合的实切片）是一个区间

<-2 ; 1/4>

它可以用来加速计算（最高 2 倍）^[1]

逃逸测试

而不是检查幅度（半径 = abs(z)）是否大于逃逸半径（ER）

 ${\sqrt {Z_{x}^{2}+Z_{y}^{2}}}<ER$

计算 ER 的平方

 ER2 = ER*ER

一次，并检查

 $Z_{x}^{2}+Z_{y}^{2}<ER^{2}$

它给出相同的结果，并且更快。

内部检测

内部检测方法^[2]

使用检测和不使用检测的时间分别为：0.383 秒和 8.692 秒，因此快了 23 倍 !!!!

// gives last iterate = escape time
// output 0< i < iMax
 int iterate(double complex C , int iMax)
  {
   int i=0;
   double complex Z= C; // initial value for iteration Z0
   complex double D = 1.0; // derivative with respect to z 
   
   for(i=0;i<iMax;i++)
    { if(cabs(Z)>EscapeRadius) break; // exterior
      if(cabs(D)<eps) break; // interior
      D = 2.0*D*Z;
      Z=Z*Z+C; // complex quadratic polynomial
      
    }
   return i; 
 }

周期检测

复二次映射的周期 - 主要文章

"在渲染曼德勃罗集合或朱利亚集合时，图像中最耗时的部分是“黑色区域”。在这些区域中，迭代永远不会逃逸到无穷大，因此每个像素必须迭代到最大限制。因此，可以通过使用算法提前检测这些区域来节省大量时间，以便它们可以立即被涂成黑色，而不是像像素一样逐像素地渲染它们。FractalNet 使用递归算法将图像分割成块，并测试每个块以查看它是否位于“黑色区域”内。这样，图像的大片区域可以快速被涂成黑色，通常可以节省大量渲染时间。 ...（一些）块被检测为“黑色区域”并立即被涂成黑色，而无需渲染。（其他）块以通常的方式逐像素渲染。" Michael Hogg ^[3]

 // cpp code by Geek3 
// http://commons.wikimedia.org/wiki/File:Mandelbrot_set_rainbow_colors.png
bool outcircle(double center_x, double center_y, double r, double x, double y)
{ // checks if (x,y) is outside the circle around (center_x,center_y) with radius r
        x -= center_x;
        y -= center_y;
        if (x * x + y * y > r * r)
                return(true);
        return(false);

 // skip values we know they are inside
                        if ((outcircle(-0.11, 0.0, 0.63, x0, y0) || x0 > 0.1)
                                && outcircle(-1.0, 0.0, 0.25, x0, y0)
                                && outcircle(-0.125, 0.744, 0.092, x0, y0)
                                && outcircle(-1.308, 0.0, 0.058, x0, y0)
                                && outcircle(0.0, 0.25, 0.35, x0, y0))
                        {
                          // code for iteration
                         }

心形和周期-2检查

改进计算的一种方法是提前找出给定点是否位于心形内或周期-2瓣内。在将复数值传递给逃逸时间算法之前，首先检查是否

(x+1)^{2}+y^{2}<{\frac {1}{16}}

以确定该点是否位于周期-2瓣内，以及

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

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

以确定该点是否位于主心形内。

另一个描述 ^[4]

// http://www.fractalforums.com/new-theories-and-research/quick-(non-iterative)-rejection-filter-for-mandelbrotbuddhabrot-with-benchmark/
         public static void quickRejectionFilter(BlockingCollection<Complex> input, BlockingCollection<Complex> output)
         {
            foreach(var item in input.GetConsumingEnumerable())
            {
                if ((Complex.Abs(1.0 - Complex.Sqrt(Complex.One - (4 * item))) < 1.0)) continue;
                if (((Complex.Abs(item - new Complex(-1, 0))) < 0.25)) continue;
                if ((((item.Real + 1.309) * (item.Real + 1.309)) + item.Imaginary * item.Imaginary) < 0.00345) continue;
                if ((((item.Real + 0.125) * (item.Real + 0.125)) + (item.Imaginary - 0.744) * (item.Imaginary - 0.744)) < 0.0088) continue;
                if ((((item.Real + 0.125) * (item.Real + 0.125)) + (item.Imaginary + 0.744) * (item.Imaginary + 0.744)) < 0.0088) continue;

                //We tried every known quick filter and didn't reject the item, adding it to next queue.
                output.Add(item);
            }
         }

另见

Claude Heiland-Allen 的心形和瓣检查

周期性检查

曼德勃罗集合内部的大多数点在固定的轨道内振荡。它们之间可能有十个到数万个点，但如果一个轨道到达一个它曾经到达过的点，那么它将不断地遵循这条路径，永远不会趋向于无穷大，因此在曼德勃罗集合内。

此曼德勃罗处理器包括

周期性检查
周期-2瓣和心形检查

在具有高最大迭代值的深度缩放动画中，可以极大地加快速度。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Mandelbrot2
{
    public struct MandelbrotData
    {
        private double px;
        private double py;

        private double zx;
        private double zy;

        private long iteration;
        private bool inSet;
        private HowFound found;

        public MandelbrotData(double px, double py)
        {
            this.px = px;
            this.py = py;
            this.zx = 0.0;
            this.zy = 0.0;
            this.iteration = 0L;
            this.inSet = false;
            this.found = HowFound.Not;
        }

        public MandelbrotData(double px, double py,
                              double zx, double zy,
                              long iteration,
                              bool inSet,
                              HowFound found)
        {
            this.px = px;
            this.py = py;
            this.zx = zx;
            this.zy = zy;
            this.iteration = iteration;
            this.inSet = inSet;
            this.found = found;
        }

        public double PX
        {
            get { return this.px; }
        }

        public double PY
        {
            get { return this.py; }
        }

        public double ZX
        {
            get { return this.zx; }
        }

        public double ZY
        {
            get { return this.zy; }
        }

        public long Iteration
        {
            get { return this.iteration; }
        }

        public bool InSet
        {
            get { return this.inSet; }
        }

        public HowFound Found
        {
            get { return this.found; }
        }
    }

    public enum HowFound { Max, Period, Cardioid, Bulb, Not }

    class MandelbrotProcess
    {
        private long maxIteration;
        private double bailout;

        public MandelbrotProcess(long maxIteration, double bailout)
        {
            this.maxIteration = maxIteration;
            this.bailout = bailout;
        }

        public MandelbrotData Process(MandelbrotData data)
        {
            double zx;
            double zy;
            double xx;
            double yy;

            double px = data.PX;
            double py = data.PY;
            yy = py * py;

            #region Cardioid check

            //Cardioid
            double temp = px - 0.25;
            double q = temp * temp + yy;
            double a = q * (q + temp);
            double b = 0.25 * yy;
            if (a < b)
                return new MandelbrotData(px, py, px, py, this.maxIteration, true, HowFound.Cardioid);

            #endregion

            #region Period-2 bulb check

            //Period-2 bulb
            temp = px + 1.0;
            temp = temp * temp + yy;
            if (temp < 0.0625)
                return new MandelbrotData(px, py, px, py, this.maxIteration, true, HowFound.Bulb);

            #endregion

            zx = px;
            zy = py;

            int check = 3;
            int checkCounter = 0;

            int update = 10;
            int updateCounter = 0;

            double hx = 0.0;
            double hy = 0.0;

            for (long i = 1; i <= this.maxIteration; i++)
            {
                //Calculate squares
                xx = zx * zx;
                yy = zy * zy;

                #region Bailout check

                //Check bailout
                if (xx + yy > this.bailout)
                    return new MandelbrotData(px, py, zx, zy, i, false, HowFound.Not);

                #endregion

                //Iterate
                zy = 2.0 * zx * zy + py;
                zx = xx - yy + px;

                #region Periodicity check

                //Check for period
                double xDiff = Math.Abs(zx - hx);
                if (xDiff < this.ZERO)
                {
                    double yDiff = Math.Abs(zy - hy);
                    if (yDiff < this.ZERO)
                        return new MandelbrotData(px, py, zx, zy, i, true, HowFound.Period);
                } //End of on zero tests

                //Update history
                if (check == checkCounter)
                {
                    checkCounter = 0;

                    //Double the value of check
                    if (update == updateCounter)
                    {
                        updateCounter = 0;
                        check *= 2;
                    }
                    updateCounter++;

                    hx = zx;
                    hy = zy;
                } //End of update history
                checkCounter++;

                #endregion
            } //End of iterate for

            #region Max iteration

            return new MandelbrotData(px, py, zx, zy, this.maxIteration, true, HowFound.Max);

            #endregion
        }

        private double ZERO = 1e-17;
    }
}

参考文献

T Myers：关于扰动的介绍...
拓扑优化解释
导数外推来自曼德勃罗集合词汇表和百科全书，作者 Robert Munafo，(c) 1987-2023。

[1] 如何使用集合的对称性

[2] A Cheritat 维基：Mandelbrot_set#Interior_detection_methods

[3] Michael Hogg 的 FractalNet

[4] 分形论坛：快速（非迭代）Mandelbrot-Buddhabrot 排斥滤波器，含基准测试

[1]

[2]

[3]

[4]