./exe/mandelbrot/readme.txt
It's a strange miracle that this thing exists at all, and perhaps still stranger that anyone found it, but here it is, for us to enjoy. Click anywhere on the picture to zoom in, and you will see that you can somehow ... just keep zooming. Really, try it!
I say it is a miracle because its discovery is rooted in the unlikely answer of "what is the square root of negative one?" Even after a suitable answer to that question was formalized in mathematics, it still took hundreds of years of human development to get to the point that we can display this image and explore it. It could technically be drawn with a box of crayons and A LOT of time, but it really took the development of an electronic computer in order to render it in any reasonable amount of time.
This object is called the Mandelbrot set, named after the famous fractal mathematician Benoit B. Mandelbrot (if you asked him what the B. stands for, he would answer: "Benoit B. Mandelbrot", and if you aksed him what THAT B stood for... well... what do you think?) This picture behaves in just the same way, no matter how far you zoom into it, you keep seeing more copies of the same thing. Well, not the same thing, but rather, variations on several themes: depending on where you look, you will find spirals, structures that look like trees, flowers, rivers, galaxies, bad hair days... all sorts of natural-looking formations of seemingly infinite variety.
You would think that a graph of such complexity would be the result of an equally complicated looking equation, but in fact it is produced by the rather tame quadratic equation of a complex variable:
f(z) = z² + c
Only nine symbols...
How does it work? Every point c on the complex plane is colored based on how quickly the sequence produced by the recursive iteration of this function diverges when starting at z = 0. I refer you to the excellent wikipedia article about it if you would like a more detailed description. The mathematics required is accessible to the modern high-schooler, and even younger, if you are ambitious! (Algebra2 standard, topics: complex numbers, function composition).
As a math teacher, a question you are frequently asked is "but when will I ever use this in real life?" The most honest answer I can give them is "maybe never"... but... "not everything you learn in school is meant to be useful. Some of it is just interesting and beautiful and makes you enjoy your life a little more. And that's okay." Some of the most important things in life have no particular use. What is the use of music, for example, or of a soccer game? These are just things we enjoy, without bothering much about their use. Wouldn't a person be missing the point if they said that the use of a soccer game is "to exercise" or "to fulfill some evolutionary goal"? It would take all the magic out. And this graph seems to me like magic. This graph is one of my favorite examples of something in math that need not be useful in order to be interesting. People all over the world have marveled at the detail of it, the dazzling colors and shapes.
The code for this current interface is largely based on that provided in the O'Reilly book, but is pretty heavily modified in order to unwrap the mandelbrot object class into a set of global parameters, so as to be more easily spoken to by the html buttons, which are here implemented as simple <div>'s with click-listeners. The same book is where I got the technique of dividing the work among web-workers in order to invoke multiple threads simultaneously and speed up the work.
./exe/mandelbrot/main.html
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Ѭ</title>
<link rel="stylesheet" href="style.css"></link>
</head>
<body>
<div class="control_bar">
<div id="left">[←]:left</div>
<div id="up">[↑]:up</div>
<div id="down">[↓]:down</div>
<div id="right">[→]:right</div>
<div id="out">[o]:out</div>
<div id="reset">[esc]:reset</div>
</div>
<div class="canvas_holder">
<canvas id="canvas"></canvas>
</div>
<script src="mandelbrot.js"></script>
</body>
</html>
./exe/mandelbrot/style.css
body {
background-color : #123;
}
div.control_bar{
margin: auto;
width: 95vw;
position: sticky;
top: 0;
display: flex;
flex-direction: row;
align-content: stretch;
}
.control_bar div {
text-align : center;
background-color: rgb(35,40,50);
flex : 1;
color: #678;
color: coral;
font-family: Courier new;
padding-bottom: 10px;
padding-top: 10px;
-webkit-touch-callout: none;
-webkit-user-select: none;
-khtml-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
opacity: 0.8;
}
.control_bar div:active {
background-color: #358;
}
.control_bar div:hover {
background-color: #245;
}
.control_bar div:first-child{
border-top-left-radius: 20px;
border-bottom-left-radius: 20px;
}
.control_bar div:last-child{
border-top-right-radius: 20px;
border-bottom-right-radius: 20px;
}
.canvas_holder {
display: flex;
justify-content: center;
padding: 20px;
border-radius: 30px;
background-color: #013;
}
canvas {
width: 90vw;
height: 90vh;
}
./exe/mandelbrot/mandelbrot.js
class Tile {
constructor(x, y, width, height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
static *tiles(width, height, numRows, numCols) {
let columnWidth = Math.ceil(width/numCols);
let rowHeight = Math.ceil(height/numRows);
for (let row = 0; row < numRows; row++) {
let tileHeight = (row < numRows-1)
? rowHeight
:height - rowHeight * (numRows-1);
for (let col = 0; col < numCols; col++) {
let tileWidth = (col < numCols-1)
? columnWidth
: width - columnWidth * (numCols-1);
yield new Tile(col*columnWidth, row*rowHeight,
tileWidth, tileHeight);
}
}
}
}
class WorkerPool {
constructor(numWorkers, workerSource) {
this.idleWorkers = [];
this.workQueue = [];
this.workerMap = new Map(); // map workers to res/rej
for (let i = 0; i < numWorkers; i++) {
let worker = new Worker(workerSource);
worker.onmessage = message => {
this._workerDone(worker, null, message.data);
};
worker.onerror = error => {
this._workerDone(worker, error, null);
};
this.idleWorkers[i] = worker;
}
}
// internal method called when a worker finishes
_workerDone(worker, error, response) {
let [resolver, rejector] = this.workerMap.get(worker);
this.workerMap.delete(worker);
// if there is no work to do, put idle
// otherwise assign work
if (this.workQueue.length === 0) {
this.idleWorkers.push(worker);
} else {
let [work, resolver, rejector] = this.workQueue.shift()
this.workerMap.set(worker, [resolver, rejector]);
worker.postMessage(work);
}
error === null ? resolver(response) : rejector(error);
}
addWork(work) {
return new Promise( (resolve, reject) => {
if (this.idleWorkers.length > 0) {
let worker = this.idleWorkers.pop();
this.workerMap.set(worker, [resolve, reject]);
worker.postMessage(work);
} else {
this.workQueue.push([work, resolve, reject]);
}
});
}
}
class PageState {
static initializeState() {
let s = new PageState();
s.cx = -0.5;
s.cy = 0;
s.perPixel = 3/window.innerHeight*2;
s.magnification = 0;
s.maxIterations = 500;
return s;
}
static fromURL(url) {
let s = new PageState();
let u = new URL(url);
s.cx = parseFloat(u.searchParams.get("cx"));
s.magnification = parseFloat(u.searchParams.get("mag"));
s.cy = parseFloat(u.searchParams.get("cy"));
s.perPixel = parseFloat(u.searchParams.get("pp"));
s.maxIterations = parseInt(u.searchParams.get("it"));
return (isNaN(s.cx)) || (isNaN(s.cy)) || (isNaN(s.perPixel))
|| (isNaN(s.maxIterations))
? null
: s;
}
toURL() {
let u = new URL(window.location);
u.searchParams.set("mag", this.magnification);
u.searchParams.set("it", this.maxIterations);
u.searchParams.set("cx", this.cx);
u.searchParams.set("cy", this.cy);
u.searchParams.set("pp", this.perPixel);
return u.href;
}
}
// these control the parallelism
const ROWS = 3;
const COLS = 4;
const NUMWORKERS = navigator.hardwareConcurrency || 2;
// initialization (used to be constructor)
const canvas = document.querySelector("#canvas");
const context = canvas.getContext("2d");
let workerPool = new WorkerPool(NUMWORKERS, "worker.js");
let tiles = null;
let pendingRender = null;
let wantsRerender = false;
let resizeTimer = null;
let colorTable = null;
let width = canvas.width = window.innerWidth;
let height = canvas.height = window.innerHeight;
window.addEventListener("keydown", e => handleKey(e));
window.addEventListener("resize", e => handleResize(e));
window.addEventListener("popstate", e => setState( e.state, false));
let state = PageState.fromURL(window.location) || PageState.initializeState();
history.replaceState(state, "", state.toURL()); // probably don't want this
function setSize(){
width = canvas.width;
height = canvas.height;
tiles = [...Tile.tiles(width, height, ROWS, COLS)]
}
function setState(f, save=true) {
if (typeof f === "function") {
f(state);
} else {
for(let property in f) {
state[property] = f[property];
}
}
render();
document.body.style.cursor = "wait";
/*
if i == 0 {
history.pushState(state, "", state.toURL());
}
*/
}
function color(iterations) {
let alpha = 255;
let blue = Math.round(75*Math.sin(iterations**0.4 + 2*Math.PI/3) + 175)
let green = Math.round(75*Math.sin(iterations**0.4 - 2*Math.PI/3) + 75)
let red = Math.round(-125*Math.sin(iterations**0.4 ) + 125)
//scale values to 0-255 range and return like this:
return ((alpha<<24) + (blue<<16) + (green<<8) + (red));
}
colorTable = new Uint32Array(13000)
for (let i = 0; i < colorTable.length; i++){
colorTable[i] = color(i);
}
function render(){
if (pendingRender) {
wantsRerender = true;
return;
}
let {cx, cy, perPixel, maxIterations} = state;
let x0 = cx - perPixel*width/2;
let y0 = cy - perPixel*height/2;
let promises = tiles.map( tile => workerPool.addWork({
tile: tile,
x0: x0 + tile.x * perPixel,
y0: y0 + tile.y * perPixel,
perPixel: perPixel,
maxIterations: maxIterations
}));
pendingRender = Promise.all(promises).then(responses => {
let min = maxIterations;
let max = 0;
for (let r of responses) {
if (r.min < min) min = r.min;
if (r.max > max) max = r.max;
}
/*
// every iteration count from 0-maxIterations has its own color
if (!colorTable || colorTable.length !== maxIterations+1){
colorTable = new Uint32Array(maxIterations+1);
}
if (min === max) { //
if (min === maxIterations) {
colorTable[min] = 0xFF000000;
} else {
colorTable[min] = 0xFF000000;
}
} else { //TODO change this! transparency is slow and it looks bad too
for (let i = min; i < max; i++) {
colorTable[i] = color(i);
}
}
*/
for (let r of responses) {
let iterations = new Uint32Array(r.imageData.data.buffer);
for (let i= 0; i < iterations.length; i++) {
if (iterations[i] === max){
iterations[i] = 0xFF000000;
continue;
}
iterations[i] = colorTable[iterations[i]%colorTable.length];
}
}
canvas.style.transform = "";
document.body.style.cursor = "crosshair";
for (let r of responses) {
context.putImageData(r.imageData, r.tile.x, r.tile.y);
}
})
.catch((reason) => {
console.error("promise rejected in render():", reason);
})
.finally(() => {
pendingRender = null;
if (wantsRerender) {
wantsRerender = false;
render();
}
});
}
function handleResize(event) {
if (resizeTimer) clearTimeout(resizeTimer);
resizeTimer = setTimeout(() => {
resizeTimer = null;
setSize();
render();
}, 1);
}
function handleKey(event) {
switch (event.key) {
case "Escape":
reset();
break;
case "+":
iter_up();
break;
case "-":
iter_down();
break;
case "o":
out();
break;
case "ArrowUp":
event.preventDefault();
up();
break;
case "ArrowDown":
event.preventDefault();
down();
break;
case "ArrowLeft":
left();
break;
case "ArrowRight":
right();
break;
}
}
const reset_button = document.querySelector("#reset");
function reset() {
setState(PageState.initializeState());
}
reset_button.onclick = reset;
function iter_down() {
setState(s => {
s.maxIterations = Math.round(s.maxIterations/1.5);
if( s.maxIterations < 1) s.maxIterations = 1;
});
}
function iter_up() {
setState(s => {
s.maxIterations = Math.round(s.maxIterations *1.5);
});
}
const up_button = document.querySelector("#up");
const down_button = document.querySelector("#down");
const left_button = document.querySelector("#left");
const right_button = document.querySelector("#right");
const out_button = document.querySelector("#out");
function up(){
setState(s => s.cy -= height/10 * s.perPixel);
}
up_button.onclick = up;
function down() {
setState(s => s.cy += height/10 * s.perPixel);
}
down_button.onclick = down;
function left() {
setState(s => s.cx -= width/10 * s.perPixel);
}
left_button.onclick = left;
function right() {
setState(s => s.cx += width/10 * s.perPixel);
}
right_button.onclick = right;
function out() {
setState(s => s.perPixel *= 2);
}
out_button.onclick = out;
canvas.addEventListener("pointerdown", event => {
bb = canvas.getBoundingClientRect();
let x0 = (event.clientX-bb.left)*(canvas.width/bb.width);
let y0 = (event.clientY-bb.top)*(canvas.height/bb.height);
t0 = Date.now();
let {cx, cy, perPixel} = state;
let cdx = x0 - width/2;
let cdy = y0 - height/2;
canvas.style.transform = 'translate(${-cdx*2}px, ${-cdy*2}px) scale(2)';
setState(s => {
s.cx += cdx*s.perPixel;
s.cy += cdy*s.perPixel;
s.perPixel /= 2;
s.magnification += 1;
s.maxIterations = Math.round(500*(1.5)**(s.magnification/5));
});
});
setSize();
render();
./exe/mandelbrot/worker.js
onmessage = function(message) {
const {tile, x0, y0, perPixel, maxIterations} = message.data;
const {width, height} = tile;
const imageData = new ImageData(width, height);
const iterations = new Uint32Array(imageData.data.buffer);
// typed array treats each pixel as a single integer instead of
// 4 separate bytes. These will be mapped to colors in parent thread
let index = 0; // to go pixel by pixel in the iterations array
let max = 0;
let min = maxIterations;
// stepping throught the image and the graph in same loop.
// row and col are the pixel coordinates
// x and y are the actual complex number
for (let row = 0, y = y0; row < height ;row++, y+= perPixel){
for (let col = 0, x = x0; col < width; col++, x += perPixel) {
let n;
let r = x, i = y; // real and imaginary
// inner loop iterates over each pixel to see if it escapes
for (n = 0; n < maxIterations; n++){
let rr = r*r, ii = i*i;
if (rr + ii > 8){
break;
}
i = 2*r*i + y;
r = rr - ii + x;
}
iterations[index++] = n; // remember # iterations per pixel
if (n > max) max = n;
if (n < min) min = n;
}
}
postMessage({tile, imageData, min, max}, [imageData.data.buffer]);
}
