I made a visualizer for the limit set of Kleinian groups in OpenGL.
1. Indra's Pearls
Mumford, Series and Wright wrote a book describing how to visualize these amazing fractals:
The book is readily accessible with only high-school level math. It is written in a very non-formal and funny style, although they always point to ways of getting into the precise details if you want to.
2. Limit Set of Kleinian Groups
So what are these fractals as mathematical objects? Well they are the limit set of some Kleinian groups.
2.1. Kleinian groups
The orientation-preserving 2D Möbius transformation form a group. It's called a Kleinian group. You can see its elements as transformations acting on the complex plane.
2.2. Infinite words
If you take two elements of this group, that is two such transformations, you can generate a subgroup consisting of all their compositions. So if you start with the elements \(a,b\) you can generate new transformations like \(abbab\) or \(abABA\) for example, where \(A\) and \(B\) are the inverse transformations. These compositions are also called words.
2.3. Limit set
Now if you take all the infinite words of a the subgroup generated by two words and apply it to some point on the complex plane, you get what is called a limit set.
3. Visualizing the fractal
There are multiple ways to visualize the limit set.
- In the book, they use a depth-first search alogorithm.
- Some have used an escape-time algorithm, similar to what is used to visualize the Julia or Mandelbrot sets. It is basically a parallel algorithm in screen space, so the input is the screen position. I copied a lot of code from this implementation.
- I used a parallel algorithm on the space of words.
The advantage of parallel approaches is of course it efficiency, which allows to have real time animation.
3.1. Visualize a lot of words
To visualize the limit set of a Kleinian subgroup generated by \(a,b\), you just have to generate a lot of these infinite words and apply them to some point.
Sounds like a paralelizable task, right? So I wrote a vertex shader for it. The idea is simple: each kernel represents a word, it has an input ID and outputs a position on the complex plane.
One could just use the id to generate a random word, but there is a way to get an ordering on the words, so you can use the id as a 1-dimensional parameter and visualize the fractal as a curve (when it happens to be a curve).
3.2. Some pictures
Visualizing as lines look like this: Visualizing as point look like this:
3.3. TODOs
- Add a geometry shader to spawn more points where needed.
- Use a cumulative approach: Add new points each frame.
- Use random words. For some subgroups, it might be easier to just brutally generate as many words as possible.