Monday 30 December 2013

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 

16 comments:

  1. Hey, Robin! Thank you for a very useful and detailed article. Also, stumbled across Penrose Tiling on your blog, which contains some dark magic with patterns. Have you considered writing an addon?

    ReplyDelete
    Replies
    1. Thanks for your feedback :-)

      I was thinking about making an add-on too.
      However, I'm not totally sure I can imagine an appropriate way of integrating this tool into Blender.

      Right now, my script relies on naming conventions and parenting to distinguish "tiles" from "subrule-defining tiles". I doubt that would be a very tidy implementation of an addon. Maybe there's a way of doing it using the GUI where for each tile you pick out its subrule (using a dropdown menu of objects), and for each subrule, you pick the small substitution tiles from a list as well... and the substitution tiles would have to have their own subrule picked too. Maybe that just makes it too complicated?

      Would you have any suggestions on how to set it up?

      Delete
    2. You're right, this hierarchy of dropdown menus is perhaps too complicated. But for some users (including me,heh) any dropdown is slightly comprehensible than code. There should be the way of simplifying this stuff in GUI, but I can't find sound solution right now :).

      Maybe it's possible to make a dropdown menu with some presets, like Penrose, Pinwheel, Goodman-Strauss and Custom tiles ? And in "custom" make another dropdown menu (4 steps) which you've proposed?

      Delete
    3. Some more thoughts:
      Maybe it could be set up this way:
      * Prototiles: Tiles that are swapped in and out of the work space during pattern generation. Use a drop-down menu to point them at a "Shape-type" object to set their type.
      * Shape Type: An object that is the parent of "substitution rule" objects.
      * Substitution rule: Object(s) to replace prototiles of a given "shape type" according to their position and orientation in the parent shape-type-object's space. These objects also point to their own shape type.

      Any object involved in the tiling could have a modifier, and on it you check off either "prototile", "shape type" or "substitution rule". You'd also set the object pointers on the modifier panel.

      The user would only need to know that the "substitution rule" objects need to be parented to the "shape type" objects, and naming conventions would be irrelevant.

      Delete
    4. Pretty interesting way of describing it all. I think it could work. Not quite getting, how it'll look in the interface. I suppose that you have a better picture of it.

      Delete
  2. Hello! This looks like a great technique but I'm having problems following along to the end. I can get to your second-last screenshot OK, but I can't seem get an outcome like the final screenshot. The script replaces the selected object with the relevant SubRule at the same scale. I suspect there's some leap of intuition I'm failing to make in how the script is actually used to create the pattern you've made. Further hand-holding would be appreciated because getting the hang of this would make my life thousands of times easier on a project I'm currently doing...

    ReplyDelete
    Replies
    1. Oh ... I might not have been clear that you run the script more than once.

      When you select the initial tile(s) and run the script, the smaller tiles will be substituted. I set it up so that the new tiles are already selected. If you just run the script again, you can subdivide it again.

      Was this the problem? If so, I'll edit and try to make this more clear.

      Delete
    2. Figured out what I'd done wrong - rotation and scale have to be left unapplied on the Sub_X pieces. Also it would be good to note that you have to parent the Sub_Xes to the relevant SubRule_X - the script didn't work for me otherwise.

      Great script though! Thanks for posting it and thanks for the tutorial. :)

      Delete
    3. Yes, you're right in both cases. I'll try and make those points a little more clear.

      Delete
    4. By the way, I'm very curious about what sort of tiling project you're working on.

      Delete
  3. I have to say: this looks very promising. For the lack of the better description I just love tiles, I try to use them as much as possible in my work. However the problem here is creating initial prototiles in precisely the right dimensions. The one that you showed is straight forward enough, but other ones are really poorly explained in the Tilings Encyclopedia. It would be so grate to provide some kind of database of tiles. This is important for me as a designer. Maybe we can create blender files or obj or precise vectors. I don't know. I'm willing to help. What do you think, how can we approach this? O and thank you for this :D

    ReplyDelete
    Replies
    1. Yes, that is definitely a problem! I usually have to sit down and do a bunch of math to figure it out, and I realize that this isn't something every artist is capable of.

      For example, try and figure this one out:
      http://tilings.math.uni-bielefeld.de/substitution_rules/cyclotomic_trapezoids_7_fold

      I really liked that one, and so I was very determined to do it, but it took me a good chunk of the afternoon.

      Maybe a .blend file on blendswap could archive different patterns in different scenes... but it would be better if there were a way for several collaborators to update the file. GitHub has been suggested to me for distributing code ... I wonder if it works for .blend files too.

      Delete
  4. This comment has been removed by a blog administrator.

    ReplyDelete
  5. This comment has been removed by a blog administrator.

    ReplyDelete
  6. I agree with Stravamir. Having a database of shapes sounds like an excellent opportunity for artists. It could be a Blender add-on, and /or a web based tool that generates a .svg file with the shapes. Would be super handy!

    ReplyDelete