Mandelbrot Set by QuadTree

Fast Mandelbrot Set by QuadTree

By Monty, 27th May 2015

Mandelbrot Set by QuadTree

Mandelbrot Set by QuadTree

Most Mandelbrot Set programs proceed along the display area, pixel by pixel horizontally, row by row from top to bottom. This one doesn’t. It divides up the screen into 6 horizontal squares in 2 rows, then for each one, checks the value of the escape time for the pixel at each corner. If they’re all the same then probably there’s nothing happening in this square, so go on to the next one. Otherwise sub-divide it into 4 new squares and check them the same way.

The assumption that if the square’s corners all have the same iteration count from the escape function then there’s no internal detail to render is almost always OK, but I’ve seen it break down in rare cases. It can happen that the M-set sneaks in  bit from one or more sides. This is (almost) fixed  by adding 4 more checks, each at the sides’ mid points.

I think that my technique is called ‘quad tree’ (QT) in computer sciencese. The QT algorithm consist of subdividing an area (square in my case) into 4 equal sub-squares, and then processing and evaluating them somehow, before potentially repeating the process recursively on each sub-square, if necessary. Except that recursion wasn’t ideal as it’s depth-first and I wanted breadth-first so that the image revealed top-down. So I used a FIFO queue instead.

The program is much faster than the usual raster-scanning ones. It has a couple more optimisations:

There’s another version over at FractalArt.Gallery that does a couple more things: it plays fractal music from the M-set, and it does ‘art’, not entirely unlike Mondrian’s paintings (so I call it Mandrian).

There are some parameters you might like to experiment with:

  • side of square in pixels, must be a power of 2
  • maxit = maximum iterations per point; smaller => faster but lower resolution
  • randCol shows the squares chosen, as does
  • line = width of a line bordering each square; 0 = none
  • sqrtCol = non-linear colour scale, makes colours show better
  • colOff = colour offset, 0-360 – varies the background colour range
  • xmin, xmax, ymax in the complex plane if you want to select a smaller area
#!/usr/bin/python3
'''
    MandelbrotQuadTree.py
    Alan Richmond, Python3.codes
'''
import pygame, random
from collections import deque
from math import sqrt

side = height = 2**10           # must be a power of 2
width = int(1.5*side)
maxit = 1440                    # maximum iterations per point
csc = 360.0/maxit
randCol = False                 # random not continuous colours
sqrtCol = True                  # square root colour scale
colOff = 9                      # colour offset in range 0-360 (in HSV)
line = 0                        # thickness of square's border lines

#   Complex plane
xmin = -2.0
xmax = 1.0
xd = xmax - xmin
ymax = xd/3.0
ymin = -ymax
yd = ymax - ymin
xscale = xd / float(width)
yscale = yd / float(height)

def inCardioidOrBulb(x, y):
    '''
    http://en.wikipedia.org/wiki/Mandelbrot_set#Cardioid_.2F_bulb_checking
    '''
    y2 = y*y
    q = (x-0.25)**2+y2
    return (q*(q+(x-0.25))<y2/4.0 or (x+1.0)**2 + y2 <0.0625)

def mandel(ix, iy):
    ''' Is this pixel in the Mandelbrot Set; return escape time '''

    x =  xscale * ix + xmin     # Scale pixel coordinate to complex plane
    y = -yscale * iy + ymax

    if inCardioidOrBulb(x,y):   return maxit + 1
    c = complex(x, y)
    z = complex(0, 0)
    for it in range(maxit):
        z *= z
        z += c
        if abs(z) > 2:  break
    else:    it = maxit
    return   it               # in set

sfm = sqrt(float(maxit))
fg = pygame.Color(0, 0, 0, 0)

def col(it):
    ''' Make a colour palette '''
    if it >=  maxit: return pygame.Color(0, 0, 0, 0)
    if (randCol):
        it = random.randint(0, maxit - 1)
    elif (sqrtCol):
        it = int(sqrt(float(it)) * sfm)
    fg.hsva = ((it * csc + colOff) % 360, 100, 100, 0)
    return fg

def Mandelbrot():
#   Add 3 squares to queue, in a line on top of the real axis
    squares = deque([(0, 0, side / 2), (side / 2, 0, side / 2), (side,0,side/2)])
    c = (0,0,0)
#   Pop squares off the queue
    while squares:
        ix, iy, l = squares.popleft()
        l2 = l / 2
#       Determine colour
        if l ==  1:      # down to 1 pixel
            itav = mandel(ix, iy)
        elif l ==  2:
#        else:
#           Get iteration counts at 4 corners.
            it = [mandel(ix, iy),
                  mandel(ix + l - 1, iy),
                  mandel(ix + l - 1, iy + l - 1),
                  mandel(ix, iy + l - 1)]
            di = max(it) - min(it)
            itav = sum(it) / 4
        else:
#           Get iteration counts at 4 corners & midpoints
            it = [mandel(ix, iy),                   # top left
                  mandel(ix + l2 - 1, iy),          # top mid
                  mandel(ix + l - 1, iy),           # top right
                  mandel(ix + l - 1, iy+l2-1),      # mid right
                  mandel(ix + l2 - 1, iy+l2-1),     # mid
                  mandel(ix + l - 1, iy + l-1),     # bot right
                  mandel(ix + l2 - 1, iy + l-1),    # bot mid
                  mandel(ix, iy + l - 1),           # bot left
                  mandel(ix, iy + l2 - 1)           # mid left
            ]
            di = max(it) - min(it)
            itav = sum(it) / 9

        c = col(itav)
#       Draw square
        yn = side - iy - l

        if (line > 0):
#           Clunky way to add borders -
#               just shrink the square exposing colour behind!
            b = l - line
            d.fill(c, pygame.Rect(ix + 1, iy + 1, b, b))
            d.fill(c, pygame.Rect(ix + 1, yn + 1, b, b))
        else:
            d.fill(c, pygame.Rect(ix, iy, l, l))
            d.fill(c, pygame.Rect(ix, yn, l, l))

        pygame.display.update([(ix, iy, l, l), (ix, yn, l, l)])

#       Subdivide square; midpoints
        ixn = ix + l2
        iyn = iy + l2

#       If squares are more than 1 pixel,
#           and there's a variation of iteration counts
        if l > 1 and di > 0:
#           Add sub-squares to queue
            squares.append((ix, iy, l2))
            squares.append((ixn, iy, l2))
            squares.append((ixn, iyn, l2))
            squares.append((ix, iyn, l2))

d = pygame.display.set_mode((width, height))
pygame.display.set_caption("Mandelbrot Set by Quad Tree from Python3.codes")

Mandelbrot()
%d bloggers like this: