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:
- Cardioid & periodicity 2 bulb checking
- Only compute top half of complex plane, copy top to bottom
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 and 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()