I recently read an article that Roger Penrose won a nobel prize for his theoretical work on Black Holes, which I’m sure is well deserved. Another creation of Roger Penrose, ‘Penrose tilings’ are also very interesting, being his solution for tiling an infinite plane aperiodically with only two tiles. Penrose tilings have an Escheresque quality to them (Escher and Penrose famously were both inspired by one-another during their respective careers) which I find fascinating.
Having just moved into a new (tragically empty) flat, I’ve been inspired to try decorating it with some self created art, and Penrose tiling’s beauty in conjunction with their relative ease of computability make them an ideal candidate. The idea I have is to write a program to generate some basic Penrose tilings, where I can then play around with the colour scheme, print out a frame, and paint them by hand in an Escher like style. How is that going to work? Let’s find out.
The rules for constructing penrose tilings are well documented, this link in particular explains the rules in better detail than I ever could.
Starting with a decagon is probably the easiest method, though there are other seeds that can be used. To construct one procedurally, draw a line of length 1 and rotate the end point by π/5 radians with respect to the origin; repeat the process nine more times, fill in the lines and you have a decagon.
Conveniently, (0, 0) is the middle of the screen when it comes to computer graphics so arranging the triangles around the center of the screen is trivial.
The simplest method of division is to take each triangle and divide it into three sub triangles; you can find the sub-triangle geometry by from the two new vertices along the perimeter of the parent triangle via the golden ratio (again, check out the link above for more detail).
Doing this correctly you can fit two t123’s and one t124 perfectly into a parent t123 triangle, and in a similar manner the rules for dividing t124 triangles is to fit one t123 and one t124. Boom, infinite Penrose tilings. Simple right? Check out the first split to the left.
I have used the sfml library in the past as a wrapper for GLSL shading, but it turned out to be a pain to use for this project. I admit my knowledge of the library is poor, but in a marginally more complex project I found a few too many things to be restrictive, for example managing vertex buffers (how do I handle my own element buffer objects?); in the end I’d rather just call the OpenGL functions myself, so I scrapped the library in favour of glfw. A little more work required in exchange for a little more control turned out to be the right balance.
Once I had sufficiently bashed myself over the head trying to remember how the OpenGL rendering pipeline works, most of the implementation was a modest cycle of tinkering/ refactoring. The only tricky part was that I had to look up was how to find a point on a line (thank you based math stack exchange), something I’m sure I learned in school and immediately forgot.
For reference, the formula for calculating a point between two points is:
- (xt, yt) = (((1 − t) * x0 + (t * x1)), ((1 − t) * y0 + (t * y1)))
- where ratio t = dt / d
- and distance d = √((x1 − x0)² + (y1 − y0)²)
That looks like a bit of a pain, but for our use case it simplifies nicely since sub-triangles are always a ratio of… the golden ratio. That is to say:
- dt = φ * d
- ∴ t = φ
- ∴ no need to calculate d at all (nice.).
Once that was solved I ended up with an interesting pattern, from which the Penrose tiling can be carved out.
Despite the above picture being formed from only two different triangles, it is not a valid Penrose tiling. Some of the lines need to be removed, and at the time I was rendering whole triangles instead of individual lines which wasn’t flexible enough in terms of design. Once I figured out which lines needed to be removed and how, I ended up with the following:
Voila! That qualifies as a valid Penrose tiling, and with some careful tinkering I was able to generate the P3 tiling also. Next, using the triangle index data for shading (one element buffer for the t123 triangles, and one for t124):
Then trying to be clever by using a six colour palette (including the lines and background). This was achieved by looking at the parent type of any given triangle giving us 2² colour options for the triangles. I think it turned out nicely:
I know there are better and more elegant ways of shading Penrose tilings but I feel happy that I’ve done what I set out to do, the hard part is waiting for divine inspiration to kick in before I try and paint one for real.
You can find the code used to generate the images above on github here. If you want to compile the program yourself you’ll have install the dependencies manually for now; I may take the time to package it with a more modern build tool in the future.
Peace out.