-
Notifications
You must be signed in to change notification settings - Fork 0
/
quadtree_fastrender.py
112 lines (76 loc) · 2.81 KB
/
quadtree_fastrender.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import math, random, timeit
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.colors import ListedColormap
from turbo_colormap import turbo_colormap_data
def makeQuad():
return [
[None, None],
[None, None]
]
def getPixel(quadTree, x, y, mapSize):
u = x / mapSize
v = y / mapSize
cell = quadTree
while type(cell) is list:
if u < 0.5:
cellX = 0
else:
cellX = 1
if v < 0.5:
cellY = 0
else:
cellY = 1
cell = cell[cellX][cellY]
u = 2 * (u - cellX / 2)
v = 2 * (v - cellY / 2)
return cell
def mandelbrot(x, y, maxIterations):
z0 = np.complex(x, y)
z = 0
for n in range(maxIterations):
if abs(z) > 2:
return 1 + n - math.log(math.log(abs(z)) / math.log(2)) / math.log(2)
z = z * z + z0
return 0
def randSamp(x, y, boxSize):
return (i + random.random() * boxSize for i in (x, y))
def transformCoords(x, y, resolution, zoomWindow, centerPoint):
real = ((x / resolution - 0.5) * zoomWindow + centerPoint[0])
imaginary = (-(y / resolution - 0.5) * zoomWindow + centerPoint[1])
return real, imaginary
def renderQuad(grid, resolution, maxBlockSize, sampleCount, maxIterations, zoomWindow, centerPoint, rangeThreshold, stdThreshold, x=0, y=0, subResolution=0):
if subResolution == 0: subResolution = resolution
boxSize = subResolution / 2
for cellX, col in enumerate(grid):
for cellY, cell in enumerate(col):
x2 = x + cellX * boxSize
y2 = y + cellY * boxSize
sampledValues = [mandelbrot(*transformCoords(*randSamp(x2, y2, boxSize), resolution, zoomWindow, centerPoint), maxIterations) for s in range(min(sampleCount[1], max(int(sampleCount[1] * boxSize / maxBlockSize), sampleCount[0])))]
if ((np.std(sampledValues) >= stdThreshold or np.ptp(sampledValues) >= rangeThreshold) and boxSize >= 2) or boxSize >= maxBlockSize:
subdivision = makeQuad()
grid[cellX][cellY] = subdivision
renderQuad(subdivision, resolution, maxBlockSize, sampleCount, maxIterations, zoomWindow, centerPoint, rangeThreshold, stdThreshold, x2, y2, subResolution / 2)
else:
grid[cellX][cellY] = np.mean(sampledValues)
#print('Solved ' + str(int(x2)) + ',' + str(int(y2)))
mandelbrotGrid = makeQuad()
MAX_ITERATIONS = 1024
RESOLUTION = 1024
SAMPLES = (2, 32)
ZOOM_WINDOW = 4 / 300
CENTER_POINT = (-.79, .15)
RANGE_THRESHOLD = 1
STD_THRESHOLD = 0.1
MAX_BLOCK_SIZE = 64
def execute():
renderQuad(mandelbrotGrid, RESOLUTION, MAX_BLOCK_SIZE, SAMPLES, MAX_ITERATIONS, ZOOM_WINDOW, CENTER_POINT, RANGE_THRESHOLD, STD_THRESHOLD)
print(timeit.timeit(execute, number=1))
img = np.full((RESOLUTION, RESOLUTION), 0)
for y in range(img.shape[0]):
for x in range(img.shape[1]):
img[y, x] = getPixel(mandelbrotGrid, x, y, RESOLUTION)
if not y % 10:
print(y / RESOLUTION)
plt.imshow(img, interpolation="bicubic", cmap=ListedColormap(turbo_colormap_data))
plt.show(block=True)