Media mashup

I’ve been working on a bunch of small projects recently that I wanted to share. The first two are related to visualizing Newton fractals in the complex plane. One is a video showing what happens when you move around the three zeros of a cubic polynomial while coloring its corresponding Newton fractal, while the other shows the Newton fractal generated from the function $f(z) = \sin z$.

The next image is a basic implementation of diffusion-limited aggregation.

I also experimented a bit with an iterative edge detection procedure on MAT’s canonical bunny image, which yielded the following video.

In the audio world, I’m currently experimenting with ideas based on granular synthesis and the Doppler effect, so stay tuned for future content!

Fractal Colorings

Last time, we saw some fairly primitive images of the Mandelbrot set. In particular, the coloring scheme was somewhat gaudy — there were noticeable discrete bands in all the images. The reason for this was in the code, where I had set the value of each pixel to be whichever integer we escaped at, creating a discrete range of possibilities. Luckily, there are fancier methods of coloring which smooth out these discontinuities. While there are a ton of different implementations out there, I’m just going to mention two: Hubbard-Douady Potential, and the Normalized Iteration Count.

In the Hubbard-Douady method, we treat the Mandelbrot set as though it is an electric field and consider the corresponding electric potential that it induces. This function turns out to be $\phi(z) = \lim_{n \rightarrow \infty} \frac{\log|z_n|}{2^n}$, where $z_n$ is the value of z after iterations. So one option for smoother coloring is to assign to pixel z the value of $\phi(z)$, or an approximation for a large value of n. Here’s an example.

In the Normalized Iteration Count, we try to come up with a corresponding continuum to the different integer range that we had specified before. There are a few variants of this formula, but the simplest is given by mapping each point to the real number $r = n - \log_2(\frac{\log|z_n|}{\log R})$, where R is the bailout radius and $z_n$ is the first iteration value that escapes the disk of radius R centered at the origin. (One way to understand this is to see that this is equivalent to choosing a real value r which satisfies $\frac{\log R}{2^r} = \frac{\log|z_n|}{2^n}$.) This formula will give us real numbers r in the interval $[0, n)$ so that upon division by n we get a standard color mapping. Here are a couple examples.

Finally, here’s another spinning Julia video, but with a continuously modified smooth color scheme. I’ve mostly used my own variant of the Hubbard-Douady method in this particular piece.

The Mandelbrot set is a very well-known fractal discovered by Benoit Mandelbrot in the late 1970s. Despite its complex appearance, it is generated from an extremely simple iterative procedure. Consider any number $c$ in the complex plane. Write $c = c_0$. Now for any positive integer n, define $c_n = c_{n-1}^2 + c_0$. Then belongs to the Mandelbrot set provided that there is a real number r such that $c_n$ is inside the disk of radius r in the complex plane for every n. (It turns out that the Mandelbrot set lives entirely inside the closed disk of radius 2, so that in practice it suffices to check whether $|c_n| \le 2$ for every n.)

As a quick example to demonstrate, consider $c = c_0 = -i$. This has distance 1 from the origin. Now $c_1 = (-i)^2 + i = -1 + i$, which has distance $\sqrt 2$ from the origin. Next, $c_2 = (-1 + i)^2 + i = -2i + i = -i$, which is back to distance 1 from the origin. But since $c_2 = c_0$, the pattern will repeat forever, and we will clearly never escape the disk of radius 2. Thus, $c = -i$ belongs to the Mandelbrot set. (An example of a number which would not belong to the Mandelbrot set would be c = 1, which the reader can verify.)

When generating computer images of the Mandelbrot set, it is common to try the iterative procedure a set number of times, and then assume that if we haven’t escaped the disk of radius 2 yet, we never will. Of course this is a bit imprecise, but it is the best we can do with finite memory. Various colorings of the points outside the set also take into account how many iterations it takes before escaping the disk.

There are many fancy images of the Mandelbrot set on the web, but it’s always more fun to brew your own. Here are a couple I generated for my pattern formation class:

Another interesting set from the field of complex dynamics is the Julia set. Its formal definition is more complicated, but a special case of Julia sets arise from a procedure very similar to the one that generates the Mandelbrot set. If instead of adding back $c_0$ at each iteration, we add back some other pre-chosen complex parameter, $a$, then we generate a family of Julia sets for different choices of $a$. Here’s one with $a = \frac{1 + i}{2}$:

I also designed an interactive animation in which the user can cycle through a family of Julia sets. Here’s a video of it in action:

And another version of the same concept, zoomed in and colored:

As before, check out my course’s website for other interesting content generated by my fellow classmates.

Conway’s Game of Life

One of the early examples of cellular automata to be popularized was John Conway’s ‘Game of Life’. You start with an infinite two-dimensional grid of cells, each of which is in one of two states: ‘dead’ or ‘alive’. (In practice, this is usually implemented by coloring the dead pixels black and the live ones white, or vice versa.) Each cell has eight neighboring cells — the four orthogonally adjacent cells and the four diagonally adjacent cells. Based on the initial position of the live and dead cells, the arrangement ‘evolves’ according to a set of simple rules:

1. Any live cell with fewer than two live neighbors dies (underpopulation).
2. Any live cell with exactly two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies (overpopulation).
4. Any dead cell with exactly three live neighbours becomes a live cell (reproduction).

The ‘game’ was invented in 1970 and has been extensively analyzed and explored. Here’s a quick demonstration that I coded in my pattern formation course, taught by Prof. Ted Kim. The initial setup is an R-pentomino, which expands rapidly.

I also made a few modifications as an exploration. One of the major implementation concerns are boundary conditions — although the game in theory is played on an infinite grid, computers work with a finite amount of memory. One solution is to treat the boundary as a dead zone. Another is to use a ‘wrap-around’ effect, essentially mapping the grid to the fundamental polygon of a torus. I decided to try out a more exotic concept, mapping the grid to the fundamental polygon of the real projective plane. In addition, I relaxed the ‘birth’ rules to include having only two live neighbors. Here are the results.

My classmates are also producing interesting content, which you can view on our course blog.