Fast 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:
- 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()