In honor of Halloween, I thought I’d post some spooky pictures and discuss how they were made. But first, please take a minute to check out my newly redesigned website, which is up and running at http://davidbachmandesign.com. A special thank you goes out to my friend, Ben Benjamin, for his advice on the design.
Anyone who is interested in 3D printing, art, design, and mathematics has most likely come across the work of Jessica Rosekrantz and Jesse Louis-Rosenberg at their company, Nervous System. Many of their designs for lamps, clothing, furniture, etc are generated with biologically inspired algorithms. One of my favorites is a series of lamps they call “Hyphae”. (Photo shown here with permission.)
As they explain here on their website, these lamps were made from their implementation of an algorithm to simulate the veins in a leaf, detailed in the paper “Modeling and visualization of leaf venation patterns” by Adam Runions & co. (available here). For anyone interested in understanding this algorithm, I highly recommend watching the animation of it on the Nervous System website.
After spending some time understanding this algorithm myself, I decided to try my own implementation. I was interested in growing veins on a meshed surface of arbitrary topology, which turned out to require some significant modification of the original algorithm. After a month or so of fiddling, I finally started to get some results I was happy with, like the veins on this skull:
And this “eyeball”:
My algorithm is mostly implemented in a Python box of a larger Grasshopper script. Before the algorithm is run the user selects a vertex of the mesh to be the “root,” and a collection of vertices to be the “sources.” These selections are accomplished with the “Select Mesh Vertices” component of the Grasshopper Mesh+ plugin. (As an aside, my Grasshopper textbook is well underway. Look for an announcement in the next few months!)
Here’s a brief description of my algorithm, with a few simplifications at each step to (hopefully) make it understandable. Feel free to contact me for more details. My apologies for any incomprehensible technical jargon. If you get bored, just scroll down to the end for one more picture! In each iteration of the algorithm we decide how to grow a tree (initially the root vertex) toward the sources.
- Compute the shortest path from each source to the tree. Each vertex of the tree at the endpoint of at least one such path is a “growth site.” In the next steps, we determine in which direction to grow from each growth site.
- Weight the edges adjacent to each growth site so that an edge picks up one unit of weight if it is the initial edge of a shortest path between the tree and some source.
- Find the edge emanating from the growth site closest to the “weighted center” of all of the edges adjacent to it.
- “Grow” the tree in the direction of this edge by adding it to the tree.
- If the new edge touches a source, remove that source from the collection of sources.
- Repeat until all sources are gone.
The above algorithm creates a polygonal tree through the mesh edges. To get a nice veiny structure, only the vertices of each branch are kept track of, together with the total of the edge weights at each. Those vertices are used to construct NURBS curves, and a tapered pipe is made around each curve with radii proportional to the weights.
Unfortunately, the algorithm is very time consuming. The detail of the resulting vein system is limited by how fine of a mesh is used, but in a finer mesh the shortest-path computations, which have to get re-run with every iteration, take much longer. This is why the vein systems I show here are nowhere near as intricate as the one in the Nervous System photo above.
There’s been a lot of beautiful work creating tree structures in Grasshopper. For example, there are really nice forum discussions featuring an algorithm of Daniel Gonzales Abalde and various experiments with it, primarily by Nik Wilmore. While these algorithms produce some amazing results in 2 and 3 dimensions, the kinds of trees they produce are structurally different than the ones I’ve shared here. Shortly I will post my own implementation of that algorithm to arbitrary meshes and compare the results.