Non-Periodic Tiling in Blender, Chapter 2

A few months ago, I made a post about Penrose Tiling in Blender. Remember how I mentioned that Penrose Tiling is a kind of non-periodic tiling? Well, I'd now like to show you another Blender script I made. This one is able to generate hundreds of kinds of non-periodic tilings (including Penrose Tiling).

You see, I've stumbled across an excellent website, one Tiling Encyclopedia which archives almost two-hundred non-periodic patterns. I was delighted to discover that most (if not all) of the listed patterns can be generated using simple substitution algorithms. What's a substitution algorithm? Well, allow me to explain myself with an example: the Kite-Domino (discovered by D.Frettlöh and M. Baake). There's only two kinds of tiles: "Kites" and "Dominos".

These are the substitution rules which generate the Kite-Domino. As you can see, the algorithm is simple enough to summarize in a single image.

Any place you have a Kite prototile, replace it with the designated configuration of kite and domino prototiles. Likewise, the domino prototile has it's own substitution rule.

After several iterations of substitution, you can turn a single domino into an extremely complicated pattern.

Here's another one: the Goodman-Strauss 7-Fold Rhomb, named after it's discoverer, C. Goodman-Strauss.

I found this one particularly beautiful, and it's the one which initially motivated me to code my tiling script.

This time, there's three rhombus prototiles. I had to do a bit of math to figure out how to model them: it turns out that each rhombus has an angle 180/7.0 times 1, 2 and 3 respectively (hence "7-Fold Rhomb" I suppose?).

As you can see, this pattern uses the same kind of substitution rule. The only difference is that this time, you need to be a little more careful when building your substitutions because the orientation of the tile is important. Notice that little arrow markings were added to the shapes - these indicate the orientation of the tiles.

Most, if not all of the patterns documented in the Tiling Encyclopedia can be generated from a substitution rule. Naturally, I decided to find a way to build a set of substitution rules into Blender and use them to generate patterns. Read on to find out how this works.

Tutorial

My script is available at the end of this post.

Let's pick an interesting pattern to build ... say, the Pinwheel (discovered by J. Conway and C. Radin) ... it's apparently famous enough to have a wikipedia article. The prototile substitution rules are given on the right.

We need to:

• Model the prototiles
• Define the substitution rules
• Set the initial conditions
• Run the script

Build the Prototiles

If an object has a name of the form [shapeName].###, my script will treat them as an ordinary prototile of type [shapeName].

In building the Pinwheel, I used two prototile types: Triangle and TriangleRev. Both are triangles with side lengths 1:2:√5, and mirror images of one another.

It should be possible to build the Pinwheel with only one prototile, but my script seems unable to properly mirror tiles (i.e. work with objects that have negative scale on one axis). Until this gets fixed, we can workaround by using a second prototile as the mirrored shape.
  
Build the triangle and it's mirror image as separate objects. I suggest you name them Triangle.000 and TriangleRev.000. The former is depicted above.

Model the triangles however you like, but make sure that the width of their base is double their height. I chose to model them aligned with the x-z plane, and with a height of 1. I also chose to build the narrow corner of both prototiles at their respective object's origin/center.

Define the substitution rules
 

A substitution rule will be represented by an object (named SubRule_[shapeName]) and the tiling of objects parented to it. The children, (named Sub_[shapeName].###) will inform my script where to put the new tiles when substituting the old one. We do this by scaling down the "Sub" tiles, and fitting them over top the "SubRule" object, filling its area. We basically are going to reconstruct the substitution rule diagrams, one for each prototile.

To build the SubRule objects, I duplicated the Triangle and TriangleRev prototiles, and re-named them as SubRule_Triangle and SubRule_TriangleRev respectively. If you like, you can store different SubRule objects on separate layers. When my script finds these two objects, it will understand that these objects are involved in defining substitution rules for tiles of type Triangle and TriangleRev. Save yourself the headache, and clear any scaling or rotation from these objects.

I built the Sub objects from more duplicates of the prototiles. These objects were named Sub_Triangle.000, Sub_Triangle.001 ... Sub_TriangleRev.000, Sub_TriangleRev.001 etc. I then scaled them down and started tiling them according to the substitution rule diagram. When positioning these tiles, make sure you're transforming the objects themselves (don't edit the mesh in any way), and make sure these objects are parented to the "SubRule" object.

On the right, I assembled the Triangle substitution rule. The red, dark orange, and green triangles are named Sub_TriangleRev.### and the yellow and light orange triangles are named Sub_Triangle.###.

You might be asking yourself, how do I transform the Sub tiles into place? 

• Translation

Positioning the Sub tiles is easy if you translate them with vertex snapping on. Snap tiles into place on the edges, and work inwards towards the middle.

• Scale

Glancing at the Triangle substitution rule, we can see that the hypotenuse of the red Sub_TriangleRev.### replacement tile should be scaled down from a length of √5 to a length of 1. Blender lets you enter python expressions into an object's transform channels, so, set the scale x, y, and z of all your replacement tiles to 1/sqrt(5).

• Rotation

If you're looking at the tiles from front view (like I am), rotate the objects on their y-axis only. Key to solving this problem is using some basic trigonometry to find the acute angles of the triangular prototiles: atan(1/2)*180°/pi and atan(2)*180°/pi. By adding or subtracting 90° to one of these two values, you can find the values you need. For example, the red triangle's rotation is atan(2)*180/pi (copy paste it into the y-channel). You can find the green triangle's rotation by adding 90° to atan(2)*180/pi.


SubRule_TriangleRev was built in a similar manner.

Set the Initial Conditions

 
The hardest is over. Now we only need to place a few tiles so that we can subdivide them. I duplicated the Triangle object twice and arranged them into a square. The tiles are red and green in my picture just so that you can tell them apart. Once they're substituted by my script, the new tiles will inherit the colours designated in the substitution rules.

Run the Script

My script will try to subdivide whatever objects you have selected. Open up the script in the text editor, and click the "Run Script" button. You might have noticed that the script starts getting pretty slow after two or three subdivisions.

The slowdown is another one of my script's shortcomings. I suspect the scene.update() command is the bottleneck, but I'm not sure yet. I have some ideas for optimization/speed-up, but if anyone has any suggestions, I would be delighted to hear from you.

Result

This is roughly what the result should look like. If you merge the tiles into a single mesh and mark all the edges as Freestyle edges, you can outline each triangle.  I prefer this pattern without outlines however - it causes multiple triangles to get lumped into interesting shapes.

So that's it! Venture onwards! Endow your 3D artwork with the manifold bounties of non-periodic tiling! Try out my script. Show me cool stuff that you made! If you have any problems, please don't hesitate to send me questions.

import bpy
import bmesh
from math import *
from mathutils import Vector

# Some borrowed code (Apparently from Nick Keeline's "Cloud Generator") which I again borrowed.
def duplicateObject(scene, name, copyobj):

    # Create new mesh
    mesh = bpy.data.meshes.new(name)

    # Create new object associated with the mesh
    ob_new = bpy.data.objects.new(name, mesh)

    # Copy data block from the old object into the new object
    ob_new.data = copyobj.data.copy()
    ob_new.scale = copyobj.scale
    ob_new.rotation_euler = copyobj.rotation_euler
    ob_new.location = copyobj.location

    # Link new object to the given scene and select it
    scene.objects.link(ob_new)
    ob_new.select = False

    return ob_new


############
### MAIN ###
############

# Number of times to iterate substitution rules. Advice: it often gets very slow after 2-3 iterations.
numIterations = 1

currScene = bpy.data.scenes["Scene"]

# Get list of objects to substitute (from selection)
l_objToBeSubbed = bpy.context.selected_objects
# Initialize a list of objects that will substitute the above objects
l_objWhichSubbed = []

# Get the list of objects which contain the substitution rules.
l_subRuleObj = [item for item in bpy.data.objects if item.name.split("_")[0] == "SubRule"]
# Generate a list of the types of shapes that will be substituted.
l_shapeType = [item.name.split("_")[1] for item in bpy.data.objects if item.name.split("_")[0] == "SubRule"]


for iteration in range(numIterations):
    # Iterate over each object that needs to be subdivided
    for obj in l_objToBeSubbed:
        # Determine the kind of substitution needed for the current tile
        shapeType = obj.name.split(".")[0]
        i_type = l_shapeType.index(shapeType)
        # Get the object which contains the needed substitution rule
        subRuleObj = l_subRuleObj[i_type]
        print("Subbing "+obj.name+" using SubRule "+subRuleObj.name)

        # Get the list of template tiles that will determine where to put the new tiles 
        l_objSubstitutes = subRuleObj.children
        # Initialize a list of new shapes to be duplicated from the teplates.
        l_newShapes = []

        for subst in l_objSubstitutes:
            print("Substitute object: "+subst.name)
            newShapeType = subst.name.split("_")[1].split(".")[0]
            newShape = duplicateObject(currScene,newShapeType,subst)
            l_newShapes.append(newShape)
        # Do this here to speed things up.
        currScene.update()
        # Duplicate the templated pattern of tile objects and place them into the tesselation
        # according to the arrangement of templates stored in the substitution rule.
        for newShape in l_newShapes:
            # Find transforms if parented
            # To optimize, try to use currScene.update() less frequently.

            tMat = obj.matrix_world*newShape.matrix_world
            newShape.location = tMat.to_translation()
            newShape.rotation_euler = tMat.to_euler('XYZ')
            newShape.scale = tMat.to_scale()           
#            # A different way ... it seems just as slow.
#            newShape.parent = obj
#            currScene.update()  # update the matrix_world data
#            loc = newShape.matrix_world.to_translation()
#            rot = newShape.matrix_world.to_euler('XYZ')
#            scl = newShape.matrix_world.to_scale()
#            newShape.parent = None
#            # Set transforms as though parented
#            newShape.location = loc
#            newShape.rotation_euler = rot
#            newShape.scale = scl
           
            # Track the new substitute objects
            l_objWhichSubbed.append(newShape)
           
    # Delete the objects I substituted
    for obj in l_objToBeSubbed:
        obj.select = True
    bpy.ops.object.delete(use_global=False)
    # If we are iterating again, we need to designate the newly created tiles
    # as the objects we want to swap.
    l_objToBeSubbed = l_objWhichSubbed
    l_objWhichSubbed = []
# Select the newly created objects
for obj in l_objToBeSubbed:
    obj.select = True
   

- CG From Space