The Mandelwat Set
If you’ve never seen the Mandelbrot set, do me and also yourself a favor and watch some amount of time of one or two of these videos real quick.
I know, right? Wtf is that thing?!
I wanted to learn about the Mandelbrot set. I thought, that’s a neat thing! I wonder how I could make one. Turns out it’s not that hard, really, but you have to understand the math and also what it is, and those things were pretty hard, at least for me, because I am not great at math even though I love it and also the Mandelbrot set is a fractal and fractals are bonkers.
I thought, “Hey, I’m a Web Developer™! I should use JavaScript for this because JavaScript is the best lol!” And so here we are.
I’m going to jump right in and try to explain it practically, but if you feel a little lost or want something reinforced, jump down to the references at the bottom for some good resources and videos to watch!
One more note: This article was originally published on my blog, here. There are some inline interactive examples there that have been screen grabbed as images below. Also, all the example images here are part of the Mandelbrot set and were generated with the end result of this project that now lives at mandelbrot.jfo.click. Go ahead a click around that if you want to see where this is headed! It’s pretty beta, but should work on most browsers and operating systems to some degree. Mobile isn’t great.
Oh, and here’s a bunch of hi-res backgrounds for downloadin’ from which the illustrations in this post are drawn.
Anyway, on to the set!
So before I can draw a Mandelbrot set, I have to have something to draw on! In html5 land, that thing is a <canvas>
and it looks like this:
Here, let me put a border on it so you can see where it is:
By default, the dimensions of a canvas element will be 150 pixels tall by 300 pixels wide. This is a funny size, and I’m not sure why it’s the default, but in any case you’re almost always going to want to set the width and height yourself. You can do this with either with CSS, programatically in JS land, or as attributes directly on the canvas element. Since there are issues with using CSS for this, and because I don’t intend to resize the canvas dynamically in the JS code, I’ll just set the attributes directly.
Now we just need to slap an id
in there and we can grab it from the JavaScriptville.
That’s it from the HTML side. All the rest of the canvases will look the same except with incrementing ids!
You can do many wonderful things on a canvas! First you need to grab a reference to the thing:
And then instantiate a context for drawing on it. For now, we’re just going to stick with a basic CanvasRenderingContext2D
, which can be fetched with a call like this:
From there, there are a lot of methods you can call on the context to affect the canvas itself. In the following example, notice that we access the canvases width
and height
attributes to know how big a rectangle to draw! This is a common pattern, and it will be important later on. Right now I’m just drawing a rectangle to fill the whole canvas though. Also I’m using a random color function I found for another post.
You can also do other things! Like drawing lines:
So, let’s look a little closer at those lines.
Those numbers that I’m passing to moveTo
and lineTo
are x and y values, sort of, but they’re indexed from the upper left corner. If they exceed the width or height of the canvas, they’ll just go straight off the side!
So, clearly, I have to account for the size of the canvas myself- it’s not really designed to do that for me. Just keep that in mind!
It seems like that’s really how you’re ‘supposed’ to interact with the canvas… it’s definitely hinted at by the name, you draw strokes and shapes on it to achieve a final result.
I am interested in a lower level API than these drawn lines and shapes, though. How can I achieve granular control over each pixel? We can interact directly with the pixels in a canvas by using a representation called ImageData
.
Calling createImageData(height, width)
on a CanvasRenderingContext2d
will return an ImageData object that contains three things:
There is the width
and height
that I expected to see. What is the other thing? It’s just a 1-dimensional array of bytes! 10 x 10 = 100, it seems like a 10 x 10 ImageData should contain 100 items since it represents 100 pixels, but it contains 400, because each pixel is represented by 4 bytes, one each for red, green, blue, and alpha (transparency) channels.Uint8ClampedArray
ensures that any value inside of itself is an integer between 0 and 255, simulating the hard type of a single byte. This is important because javascript doesn’t otherwise have any sense of integer types, and internally represents all numerical values as 64 bit floats.
You might expect a 2d array here, like this:
Where p
is a some sort of pixel object that can be addressed by attribute, like:
But the ImageData.data array is actually even lower level than that. It is literally just a one dimensional array with no real API to speak of! Let’s play with it though. This example simply fills all the channels for all the pixels with a random value. You’ll notice that it looks a little pastel, since on average there will be some transparency applied to each pixel.
Of course, to be useful we need to look at each pixel’s 4 values as a chunk and change them accordingly. Here’s a simple little for loop that will do that! This example simply turns every pixel blue with no transparency.
Here’s a small exercise I just thought of. How would one make a widget that uses the ImageData technique above to create a randomly colored background? How about one that allows user input for the RGBA values? A canvas that maps mouse position to the color of the canvas and changes it as you move it around? These are just some ideas. You wouldn’t have to use ImageData exclusively, of course, there are easier ways to simply change the background color.
It is an inconvenience to have to address the pixel values linearly like this, what I’d really like to be able to do is address coordinates inside the canvas. I can remedy this problem with a little bit of math and a helper function!
So I can write a function, indexToCoord
, that takes an index value and then computes the x and y pixel offsets for that index in that imageData object. Note that canvas
must be in scope and a valid canvas for this to work! I will address that more thoroughly later.
So now, let’s say I have a 10x10 canvas, (that’s a very small canvas, but lol I guess) and I want to address the pixel marked below with an #
An ImageData object for this size of 10x10 would contain 400 byte values, and the 4 bytes associated with that pixel would be at indices 132–136. This is pretty straight forward, but if I put it through the indexToCoord()
function, I get something a little more palatable!
This tells me a lot more about that pixel’s location.
We’re almost there. I want to be able to use coordinates on a coordinate plane, this is still 0
indexed from the top and left. Also, I want to decouple the coordinate from the pixels themselves and simply be able to scale it to whatever range I want. That scaling value is going to be an “r” value.
Let’s say that I want the coordinate plane to go from -2 to 2 on both axes. (Just, you know, for example.)
Let’s also assume we have a much larger canvas! 10 x 10 is not very interesting. 200 x 200, as before, gives us an ImageData object that has 160,000 bytes in it! Again, that’s 200 * 200 = 40,000 * 4 = 160,000. Quite a lot.
So here is a way to turn an index into a coordinate that can be scaled according to what you’re trying to see! Given a canvas of 200 x 200, and a scale of -2 to 2, then, yields something very close to what you’d expect:
This is just begging to be abstracted, so that’s what I’m going to do.
First, the constructor will take one thing, a string that represents the canvas id in the dom! It will assign both canvas
and context
as private variables. We’re also going to go ahead and allocate an ImageData
object for this graph that we can reuse.
Next we’ll add that indexToCoord
method. I’ve put the r
value and the center
value as attributes on the object so that I can manipulate them from outside, and I’ve added an aspect ratio to scale the coordinates correctly in case the canvas is not 1:1.
If I were writing a real graphing library or something, I would want that to be settable as well, but this is a stepping stone to the Mandelbrot rendering, which will always be 1:1, so I’m going to ignore that.
I’ve also added the rgb noise example as the render function for this object.
Now I can interact with a canvas something like this:
Each pixel, now, can be viewed as a single discrete coordinate on a plane that can be centered anywhere in the two dimensional plane and scaled up or down depending on what you want to see!
Before packing away this abstraction and explaining sets, I want to add one more thing.
This render function above just randomly sets all the pixel values, but of course I want more control than that. I will change the render()
method to accept a predicate function, instead:
Now, for every pixel on a given Graph, the predicate is called on its scaled coordinate and returns whether or not it should be filled in with black or not. The first three values per pixel are RGB values, and the last one is the alpha
channel, which sets the transparency of the pixel. The higher it is, the more opaque, so by setting it to its maximum value of 255
, we make the pixel black. If we set it to 0
, it is completely transparent and looks like the background.
From now on I’m going to interact with a Graph object for each canvas in the next section, like this!
Ok let’s play with it!
Above we see a predicate function that basically says: “if the current pixel is on the line described by one of these equations, fill it in. If not, don’t!”
You’ll notice that some of the lines are not totally smooth, and instead are made up of dots or dashes. What you’re seeing is kind of sort of a version of the “screen door effect”. For each individual pixel in, say, this equation:
x * 2 = y
The pixel’s coordinate must match exactly with the output of the equation in order to qualify and be filled in. This means that when it’s even with a multiple of the size of the canvas, it’s much more likely to be filled!
Again, if I were building a fully functional graphing library, I would have to deal with this issue (and many more!). But I’m not, so I won’t! This is adequate for now. Let’s talk about sets!
Sets wtf is a set
I’m not really going to get into set theory because I don’t know anything about it tbqh, but maybe it’s worth a mention? Wonder what would be a really good succinct but not wrong explanation of set theory…
Let’s say a set is pretty much what you think it is, then. How can we describe a set? We can have a set that is completely enumerated.
{ 1, 4, 397376, 89, 44 }
These are just some numbers. They don’t really have anything in common with each other, I just typed some numbers. And so for any number x
that you can dream up, x
will either be in this set, or not.
Is 2 in the set? No.
Is 20 in the set? No.
is 397376 in the set? Yes!
Hey actually, JavaScript has a syntax for exactly this! (Well, strictly speaking, ES6 does.)
Will this work??
Hmm, no it will not. Because of JavaScript’s equality rules, objects are not compared to each other by value. To whit, these are falsy:
Objects instead are equal if they are actually the same object, meaning the two sides of the double or triple equals refer to the same memory.
You get the idea. Now, I could write a deep checking set class for these coordinates, or build the coordinates into a real object that has a function that can do that, but I don’t really want to. Instead I’m going to talk about sets more generally!
So, you can have a set that is just a defined set of whatever, and write all the whatevers out, like the example above.. That works great! But what about something like this:
Obviously, I can’t write that out! But I can check if an arbitrary number is a member of that set with a simple function.
Hey cool! This is like, a programaticalized way to test for set membership in that particular set of numbers.
Now we’re getting somewhere! What about this one:
This is cool, then, I have a way of “graphing” sets! These sets are pretty boring though. But you know what’s not boring??
The Mandelbrot Set
…is defined as:
The set of all complex numbers that remain bounded when iterated on the equation f(z) = z²+ c
Okay so real talk, there are like 3 or 4 things in that definition that I totally did not understand at all when I started this project. But I do now, and I’m going to explain them to you, one by one!
Let’s start with the equation.
f(z) = z²+ c
This part’s pretty easy. I have a function, and I feed it a number, and I get a number back.
This is, of course, borked.
thinger(2);ReferenceError: c is not defined
at thinger (/private/tmp/thinger.js:2:29)
at Object.<anonymous> (/private/tmp/thinger.js:5:13)
at Module._compile (module.js:570:32)
at Object.Module._extensions..js (module.js:579:10)
at Module.load (module.js:487:32)
at tryModuleLoad (module.js:446:12)
at Function.Module._load (module.js:438:3)
at Module.runMain (module.js:604:10)
at run (bootstrap_node.js:394:7)
at startup (bootstrap_node.js:149:9)
c
here must be defined. I will define it then!
Cool cool. I can plug whatever in there now great.
thinger(4, 2);
thinger(40, 3);
thinger(4000, 3.32);
Yields, respectively:
18
1603
16000003.32
Ok so now, what does ‘iterated on’ mean?
It means that I take the output of the function and feed it back into the same function. The initial z
input is always 0.
Obviously, this is also borked.
RangeError: Maximum call stack size exceeded
at Object.pow (native)
...
This is a recursive function with no base case. This is where the “bounded” part comes in. For a given input, this equation exhibits one of two behaviors under iteration. It can either stay bounded Or it can explode to infinity. This makes a little more sense if we see some output. I’ll add a counter that I’ll increment on each call just to give us a way to get out of the recursive loop.
Now, we can see some interesting stuff
thinger(0, 2, 0);
will print:
2
6
38
1446
2090918
4371938082726
1.9113842599189892e+25
3.653389789066062e+50
1.3347256950852164e+101
1.781492681120714e+202
Infinity
Exponents are no joke, and 2 decidedly does not remain bounded.
What about this one?
thinger(0, -1, 0);
Hmm…
-1
0
-1
0
-1
0
-1
0
-1
0
-1
But this one does! -1 is thus in the Mandelbrot set, and 2 is not.
Wait, though, we were talking about complex numbers. And the numbers -1 and 2 are not coordinates, they are integers. How do you make a 2 dimensional graph with one number?
These two questions answer each other!
The Mandelbrot set is not plotted on a Cartesian plane, where each point is represented as a pair of numbers <x, y>
. It’s plotted on the complex plane. Where each point is represented by a single complex number.
A complex number is an expression of the form x + yi
where x
and y
are real numbers and i
is the unit imaginary number. Though y
alone is a real number, it is here the coefficient of i
, and so cannot be combined with x
. On the complex plane, we plot x
(the “real” part of the complex number) on the x axis and y
(the “imaginary” part of the complex number) on the y axis. This took me a while to understand but it’s pretty simple really! Here’s a Khan Academy video that explains it in more detail.
So the cartesian coordinate (1, 2)
would be represented on the complex plane as the complex number 1 + 2i
.
So, remember, we wanted to feed complex numbers into that function, but we can’t because javascript doesn’t have a complex number type. There are, of course, 36 packages on npm that probably can do this, but I’m not going to use any of them, because reasons!
No but seriously. It’s just one application and I can do it by hand and that’s how we learn new things.
So, a complex number is made up of a real part and an imaginary part. Never the two shall meet. What if I wanted to add two complex numbers together?
(1 + 2i) + (3 + 5i) = 4 + 7i
Alright. But in JS, I could just keep track of these two parts separately.
Prints [4, 7]
, which is representing the imaginary number4 + 7i
.
I’m returning this as a tuple of two values. I could use objects, if I wanted…
Do you see it? Do you see how this is just dying to be made into a prototype that implements basic math over itself and stuff? Oh man, it really wants me to do that, but I’m not going to do that.
We also need to be able to multiply complex numbers, in order to square them. What does that look like? It looks like algebra. Remember FOIL
? “First, outer, inner, last.”
(1 + 2i) * (3 + 5i)
(1 * 3) + (1 * 5i) + (2i * 3) + (2i * 5i)
3 + 5i + 6i + 10i²
3 + 11i + 10i²
3 + 11i + 10(i * i)
3 + 11i + 10(-1)
3 + 11i — 10
-7 + 11i
Recall that i
is actually the square root of -1, so i² is… -1
!
So… let’s go back to our testing function from before! All I need to do is replace z
and c
with “complex numbers” made up of zr
(z real), zi
(z imaginary), cr
(c real), and ci
(c imaginary). I’ll keep that index var i
around for now, as well, but I’m going to change it to iterations
for a little more clarity.
Those nextr
and nexti
expressions look pretty wonky but they are just what you get when you factor out the real and imaginary operations from the FOIL
procedure from above.
So here’s the trick. Right now I’m sort of just, winging it with those iteration counts. But how do I really know if a point is not in the set?
If the sum of the squares of the real and imaginary parts of the complex number ever exceed 4, then that complex number is not in the Mandelbrot set.
That’s a little more useful!
So what we have here… this is getting there. If the condition stated above is met, then the number is not in the set. BUT if we’ve reached some maximum iteration count, then as far as we know, the number is in the set. That’s going to be important later on!
It’s cute to have this be recursive and all, but it’s unnecessary. The formula looks cleaner as a loop and is less computationally expensive. We can let that state be internal and leave it out of the function signature. And as a matter of fact, dropping the recursion means we don’t have to pass in the inital zr
and zi
, either. And what the hell, why don’t I change that name fromthinger
to something a little more descriptive.
Ok so, remember those predicate functions from before? They took in a coord
with an x
value and a y
value? Doesn’t that look… suspiciously similar to what we’ve got above?
There it is. Our old friend. The Mandelbrot set.
Lol that looks like a fuzzy potato why is this cool
Yeah, it might look boring from where we’re sitting, but it’s totally not.
Remember when I built that “Graph” object, I made both r
(the zoom factor) and center
accessible.
We can totally change where we’re looking at the graph!
x= -0.7463
y = 0.1102
r = 0.005
x = -0.7453
y = 0.1127
r = 0.00065
x = -1.25066
y = 0.02012
r = 0.0005
x = -0.16
y = 1.0405
r = 0.046
Small refactor
So at this point I am going to drop the more general Graph
abstraction and just hardcode that object’s predicate as the Mandelbrot test. That… pretty much looks like you would expect.
Now, I can do something like this:
There’s one important change here! In the Mandelbrot
object above, you can see that I’ve exposed another attribute. this.iterations
, and used it as a maximum value in the for loop in the Mandelbrot function.
Why are iterations important? Well, the more iterations we use the more fine grained the Mandlebrot can be displayed. Play around with the widget to see what I mean!
As the iterations cycle back and forth, you can see that the edges of the set get more definition. That could go on infinitely, though what you see there is about as high fidelity as we can get at that zoom level, since pixels have a definite size, small as they may seem.
Colors come out of the speakers
Let’s talk about those trippy ass colors you see on all the zooms on youtube.
Right now we’ve got a pretty simple true false test that tells us if a pixel is not in the set or if, as far as we know, it is. Every extra iteration increases the fidelity of that second category, as you can see in the doodad above. The thing is, we’re throwing away some information here. We’re throwing away how many iterations it took us to figure out that a point was not in the set. This is really interesting information!
Currently, the render function uses the boolean value returned by isMandlebrot
to decide whether or not to set the opacity
‘byte’ to either 255, or 0.
We can change isMandlebrot
to return a tuple instead, of two things: the original boolean value and the iterations required to divine it.
Now, back in the render function, we can use that information to color the pixel according to it’s iteration score!
set
here is a value that I’m first normalizing between 0 and 1, then scaling to be between 0 and 16777215. Then I’m extracting RGB values in kind from it with some bit twiddling. Sorry I’m not explaining that more/better, I’m turning the iteration count into a color value is all!
This is dramatically cooler looking.
Remember those little thingers from before? Look what one of them looks like in color!
Alright! This totally works and is beautiful! But, it’s slow. On the one hand of course it is, this is a lot of computation. But on the other hand… I can do better.
So, I’ve made a little doodad that computes Mandelbrots on the gpu using WebGL. It lives here:
All of the illustrations above that aren’t example canvases were made with this tool. I’ve really enjoyed playing with it! You can even resize the canvas to download high resolution backgrounds as large as you want! Though of course the bigger they go, the slower they’ll run, but just give it a try and see what you can find.
I am not going to explain the code in the webgl widget just yet for a few reasons. First, I’m really happy with how the final product turned out, but the code is a wreck, organizationally! And anyway, most of it is boilerplate to get the webgl connected and up and running, and the parts that aren’t boilerplate aren’t substantially different from the code I’ve shown in vanilla javascript over the course of this post.
I hacked together this widget using:
The author, Greggman, also maintains a library called twgl.js for making the WebGL api less verbose and I am definitely going to use it next time.
Íñigo Quílez, who created shadertoy, also practically has the market cornered on Mandelbrot renders. That link served as both inspiration for this whole thing (wait… we can compute in real time now?) and model while porting my js code over to webgl. I have that shader to thank for that incredible coloring function that I used as the base of mine; I’m still not entirely sure how it works.
A few caveats- this isn’t really designed for mobile. UX wise it’s definitely not, but more importantly mobile platforms don’t seem to have the same caliber of graphics processing as a lap or desktop. This isn’t really a huge surprise; you might be able to get it to render something, but no promises.
Also, unfortunately, current GLSL only natively supports 32 bit floats for use on the gpu, so we run out of precision relatively quickly on the widget. You can barely see where the pixels become blockish at the highest zooms, but don’t be mistaken- this is not the end of the set- the set goes on forever. There are techniques to work around this and achieve a higher precision, but my mandelbrot shed doesn’t need another coat of paint before shipping. I’ll likely try to get around to that sometime, or just put it off until 64 bit floats are native to the platform!
References
Here are some things I found really helpful while working on this project.
- Holly Krieger’s explanation of the set on Numberphile
- This documentary excerpt featuring Benoit Mandelbrot
- Mandelbrot’s Ted talk about roughness from 2010
- This deep zoom video accompanied by Jonathan Coulton’s song “Mandelbrot Set”
- This JavaScript Mandelbrot generator
- This wikihow.com page (I know right? But it was helpful early on!)
- This collection of interesting coordinates I used for testing.
- Fractals: an animated discussion
Unfortunately the last one is probably the best but I haven’t been able to find it online anywhere. The one I saw was loaned to me by fellow fractal enthusiast and Etsian Paul-Jean Letourneau. Thanks Paul-Jean!
Also thanks to Julia Evans for talking me through some of the math early on and helping me with my complex number algebra that I kept messing up and which produced weird blobs on the canvas.
I hope this was interesting. I’m going to shut off my computer for the rest of the day now. I’ve been thinking of picking one day a week and not looking at any screens, or at least not staring at the computer screen for the whole day.