In December our team was allowed two weeks to pursue a “passion project”. It didn’t have be work-related, just something you truly wanted to work on. I chose to design tread patterns on the soles of shoes.
I had never given a thought about shoe treads until, a week earlier, a woman on the NodeBox forum asked for help creating organic shoe patterns. I asked her to elaborate on what she meant by “organic” and she sent me a photograph that looked like a school of hexagon fish swimming in the shape of a shoe, with bigger fish in the center and smaller fish near the edges.
An organic-looking shoe tread design
I looked into it and discovered a vast art form that had been right under my feet the whole time. There are entire schools which teach shoe tread design and thousands of designs hitting the pavement every day, each one unique. If you doubt me, go to this Pinterest page and start scrolling. Scroll some more. Getting tired yet? Keep scrolling. Amazing, isn’t it?
Redrawing a particular pattern wouldn’t be too hard; you could just trace over a photograph. But generating new vector-based patterns from scratch is not as easy. You would need to develop a whole language of core concepts (nodes) that could follow the sinuous curve of an arch, adapt to edges, grow and shrink based on position, soften sharp edges, etc. These are things which children can do instinctively, but which require significant math for computers.
That is the problem which hooked me. It’s a problem I’ve run into before. Visualizations are powerful because the human visual system is powerful. Resolving a scene into component shapes, tracing edges, comparing areas, etc. is effortless for us – we do most of it subconsciously. I often get ideas for rendering data as shapes or lines that are easy to sketch on paper, but hard to codify into algorithms.
To illustrate this, I have identified six simple visual tasks that are easy for children but surprisingly tricky to do in NodeBox. Over the course of my two-week passion project I was able to develop a “node” for each one – and then used them to draw a few simple tread designs.
1. Finding the outside
Visual Task Number 1
Given a set of objects (shapes, words, dots) arranged on a 2D canvas, it is often useful to draw a border that efficiency encloses the objects. Uses include highlighting one clump of related points in a larger scattergram, drawing “word clouds” that surround a set of words, etc. To do this you have to figure out which positions are the outside of the clump and which are inside. A child can do this just by looking, but how does a computer do it?
The mathematical term for this is convex hull. It is considered one of the fundamental problems of computational geometry. The difficulty of finding a convex hull increases with the number of points to be enclosed. There are a number of known algorithms, each with its own tradeoffs. I used Andrew’s Monotone Chain.
I now have a “wrap” node. Feed it a list of points and it returns the subset of exterior points arranged in clockwise order. You can feed that output into a connect node to draw a line that wraps all the objects and then into a scale node to create some breathing room.
2. Softening Corners
Visual Task Numbe 2
A key requirement in making “organic” shapes is the ability to soften corners. You need to replace sharp corners with gentle curves and control the amount of “curviness”. This turns out to be a hard problem. The shapes I want to deal with are “Bsplines”, sequences of bezier curves. In order to turn a pointy shape into a rounded shape, you need to replace line segments with Bsplines and find the control points of each bezier curve in the sequence.
Fortunately, I found an algorithm by Bernhard R. Fischer that does exactly that. It involves finding the tangent of each corner and extending control points along that tangent (the farther you go, the curvier it gets). I created a NodeBox node (subnetwork) called fit_curve that does all this. It’s not perfect, but it works well enough, and has become one of the most useful tools in my toolbox.
3. Finding Areas
Visual Task Number 3
A persistent problem I ran into when I began trying to draw shoe soles was dust. (I encountered the same phenomenon when working with maps.) “Dust” refers to shapes created during complex intersection operations that are often too tiny to see with the naked eye. Dust particles can be so small that they cannot be softened and so screw up my calculations. To get rid of them I needed to delete all shapes below a certain area.
But how do you calculate the area of random curvy shapes? Even calculus does not help much with this. The solution I came up with was to reduce the shape to a polygon and apply a centuries-old surveyor’s method called the shoelace formula. It involves taking cross-products of alternating X and Y positions in a back-and-forth way like tying a shoelace. Problem solved.
4. Tracing Edges
Visual Task Number 4
Children love tracing edges. Start with a few simple shapes and draw outlines around each one. Then draw outlines around the outlines until they start to intersect. The result is psychedelic. A similar process is useful in creating topographic maps and sea-charts.
By now you will not be surprised to hear that this is another hard problem for computers. A popular library for doing curve offsets requires more than three thousand lines of code. In fact, it is mathematically impossible to offset one bezier curve from another. The solution is to break the curve down into tiny line segments, calculate the tangent of each one, and use that information (plus my fit_curve node) to create a new curve. I can now trace the inside of a shoe sole with ease.
5. Magnifying a Grid
Visual Task Number 5
A basic component of shoe tread patterns is intersecting lines or curves. But for that organic bigger-in-the-center, smaller-near-the-edges look, I needed a way to magnify these grids so that the center cell is enlarged, the grid cells around that are proportionally smaller, the grid cells around those are smaller still, and so forth.
The effect looks simple and natural, but calculating the exact positions of each intersecting line in a way that shrinks distances around the center in a consistently proportional way while at the same time conserving the number of lines and maintaining a fixed outer boundary is, well, tricky. I derived a nasty-looking formula to represent this, but my calculus skills were too rusty to integrate it. I finally had to turn to a messy numerical method.
There may be a simpler way of doing this that I could not see, but my accordion node works well enough for now. It’s also handy for creating natural-looking animations like a fan folding and unfolding.
6. Seeing Shapes
Visual Task Number 6
The final challenge was the most fundamental and goes to the heart of what makes our human visual system so magical. When presented with an array of intersecting lines, circles, etc. people instantly and effortlessly perceive the intersections as independent shapes. They can point to them, number them, and color them without a second thought.
But to a computer there are no shapes there. It takes a lot of extra work to calculate all the positions lines or circles intersect and figure out which subsets of those intersections could form the outline of new shapes.
This is what my fragment node now does. Feed it a boundary and a pattern of intersecting lines or curves and it returns a list of all the independent shapes formed as a result (minus the dust). If I feed it the three intersecting circles of a Venn diagram it will return all eight intersection shapes (including the shape outside the three circles).
With the toolbox I developed over the course of my two-week “passion project” I can now trace the inside of the sole to define a canvas, apply a grid of curves to it, magnify that grid, pull out the resulting shapes, and soften them. I was only able to create a few simple proof of concept tread designs in the allotted time, but am now confident I could produce many more. Perhaps this will be a retirement project for me some day. In the meantime, I have already used some of these tools to create new visualizations at work.
NodeBox screenshot showing some of my tread designs
Passion projects like this may seem frivolous, but I’ve always found them an essential part of innovation. I have my own name for them: PONARVs: Projects Of No Apparent Redeeming Value.
Stone Soup
In the classic Grimm Brothers tale, returning soldiers convince selfish villagers to share their food by telling them they are making “stone soup”. They place a stone in a pot of water and start it boiling. One by one they get each suspicious villager to add an apparently inconsequential ingredient until a flavorful soup comes together that is more than the sum of its parts.
My shoe soles project was like making stone soup. The shoe problem was the stone that defined the soup. But in the process of making it, I was forced to add one tasty node “ingredient” after another. In the end I created something much more wonderful – and useful – than shoe treads.
