The Engineering behind Figma's Vector Networks
Adobe Illustrator introduced the pen tool back in 1987 as a tool for creating and modifying paths. Since then the pen tool has become incredibly widespread, so much so that is has become the de facto icon of the graphic design industry.
The pen tool's functionality hasn't changed significantly in the 30 years since its introduction. Just click and drag to create smooth curves. Designers have learned to work with it, and around its idiosyncrasies.
The pen tool
But Figma felt like they could improve some aspects of how the pen tool worked, so they had a go at redesigning it. Instead of it being used to work with traditional paths, they improved the pen tool by creating what they call Vector Networks.
In this post we will go through what Vector Networks are and what problems they try to solve. After we've defined what Vector Networks are, we will take a look at some of the engineering challenges you would face if you were to take a stab at implementing them.
This post can be thought of as an introduction to a really interesting problem space, and as a resource for people interesting in making use of some aspects of Vector Networks for future applications. I hope it succeeds in providing value to both developers being introduced to new concepts and ideas, and to designers interesting in learning more about the tool they know and love.
I will start off by laying out the core concepts behind the pen tool, and from there we will move onto Figma's Vector Networks.
Paths
The pen tool is used to create and manipulate paths.
If you've every worked with graphics software like Illustrator before, you've worked with paths. Paths are a series of lines and curves that may or may not form a loop.
Some paths
The path to the left loops, while the path to the right doesn't. Both of these are valid paths.
The main characteristic of paths is that they form a single continuous unbroken chain. This means that each node can only be connected to one or two other nodes.
Not valid paths
However, you could construct these shapes from multiple paths if you position them correctly together.
Multiple paths are used to create more complex shapes
From a combination of paths, you can create any shape imaginable.
This beer glass, for example, is just a combination of five different paths positioned and scaled a certain way.
The building blocks of paths
A path is made up of two things, points and lines.
Points and lines
The points are known as nodes (or vertices) and the lines are called edges.
Together, they make a path
Any path can be described as a list of nodes and edges.
This path can be described as the series of nodes (0, 1, 2, 3, 4). It could also be thought of as the series of the edges that composed it. That list of edges would be (0, 1), (1, 2), (2, 3), (3, 4), (4, 0).
You can think of this like the dot to dot puzzles that you used to do as a kid: Draw the edges of the path in the order that the points lay out.
But instead of a kid drawing lines between numbered points on a paper, a cold calculating machine does it along the cartesian coordinate system.
Edges
An edge is a connection between a pair of nodes. Visually, edges are a line from node a to node b.
But that line can be drawn in a lot of different ways. How do you describe those different types of lines?
Edges fall into two categories, straight and curvy.
Straight edges are as simple as they seem, just a line from a to b. But how are those curvy edges defined?
Bezier curves
Curvy edges are bezier curves. Bezier curves are a special type of curve defined by four points.
The positions of the two nodes in our edge make up the start and end points of the curve. Each of the two nodes has a control point.
In most applications, these control points are shown as handles that extend from their respective node. These handles are used to control the shape of the curve.
Bezier curves can be chained to make more complex shapes that a single curve can't draw on its own. They can also be combined with straight lines to make some cool designs.
But what exactly are the handles doing? How do the handles tell the computer to draw the curve like it does?
Computers draw curves by splitting them into straight lines and drawing the individual lines.
The more lines you split a curve into, the smoother the curve becomes.
So to draw the curve we need to know how to get the different points that make up the curve. If we compute enough of them, we get a smooth curve.
Computing a point on a bezier curve
Let's compute the point at 25% point of the curve. We can start by connecting the control points with a third blue line.
Then for each blue line, we draw a blue dot at the 25% point of the line.
Next, draw two green lines between the three blue dots.
And we repeat the same step as we did with the blue dots. Draw green points at the 25% points of the green lines.
And then one more red line between the newly created green points.
Then we add a red point at the 25% point of the red line.
And just like that, we've computed the point at the 25% point of the curve.
From now on we'll refer to points on curves through a t value, where t is a number from 0 to 1. In the above example, the point would be at t=0.25 (25%).
t=0.25, t=0.5 and t=0.75
This way of computing the point at t is called De Casteljau's algorithm and can also be used to subdivide a bezier curve. Using the points we created along the way, we can also subdivide the bezier curve into two smaller bezier curves.
Bezier curves are pretty amazing things. Shaping the curve by adjusting the handles feels surprisingly natural, and chaining them together allows you to create detailed and complex shapes.
And for computers, they're stable and inexpensive to compute. For this reason they're used for everything from vector graphics to animation curves and automobile bodies.
You can see an interactive demo of bezier curves at Jason Davies' site. It's fascinating to watch a series of straight lines trace out a smooth curve.
From https://jasondavies.com/animated-bezier
The creative constraints of paths
Earlier in this post, paths were defined as a continuous series of lines and curves that may or may not form a loop.
The fact that paths are a single continuous chain is a pretty big limitation.
It means three way intersections are not possible using a single path. To create a three way intersection, two or more paths will have to be used. This means dealing with positioning and grouping different paths together. It also means that changes to a single path can lead to changes to multiple other paths.
But that's simply the routine. Seasoned designers know how paths behave, they can plan around it without really thinking about it. For a static design it doesn't really matter how many paths and layers you have to create if the piece is planned properly upfront.
But for some situations the constraints that paths impose cause a lot of friction.
Vector Networks
In 2016, Figma introduced Vector Networks. They lift the “single continuous” limitation by allowing any two nodes to be joined together without restrictions.
“A vector network improves on the path model by allowing lines and curves between any two points instead of requiring that they all join up to form a single chain.”
Source: https://www.figma.com/blog/introducing-vector-networks/
The cube is the quintessential example for demonstrating Vector Networks.
Via traditional paths, you would have to create at minimum 3 different paths to describe this shape.
This creates a lot of friction for a seemingly simple and common shape. To modify the cube, you would have to modify two or three different paths. But with Vector Networks you can simply grab an edge and move it around, and the shape behaves like you would expect.
So if you would want to increase the extrusion of the cube, you could just grab the two appropriate edges and move them together.
This is the big selling point for Figma's Vector Networks. Ease of use.
Vector Networks don't enable you to create something that you couldn't create with other tools, but it does remove a lot of the friction in the process of creating things.
And you can take this even further. Say you want to add a hole to the side of the cube.
Just start off by selecting and copying the sides of the cube. You can then duplicate those edges and scale them to the size you want them to be.
And just like that, you have a cube with a hole.
And to make this hole believable, you just need the inner edge.
Again, Vector Networks may not allow you to create something you couldn't otherwise. Instead, they enable workflows that weren't previously possible.
Creating Vector Networks
With an understanding of what Vector Networks are, we can now take a look at how we would go about implementing them.
Graph
The main data structure behind Vector Networks is a graph. A graph can be thought of as a collection of nodes and edges.
A graph
Nodes
A graph may have any number of nodes. For our purposes nodes have two properties, a unique id and a position.
Edges
Edges are the connection between two nodes. Each edge is a composed of two edge parts. An edge part contains a node's id and an optional control point.
The labels n0 and n1 will be used to refer to the nodes at the start and end of an edge, respectively. The control points will be labeled cp0 and cp1.
If the control points of the edge are omitted, the edge becomes a straight line.
Filling the holes
Source: https://www.figma.com/blog/introducing-vector-networks/
When working with vector networks, the Fill tool allows you to “toggle” the fill of different “areas” of the graph.
These areas can be defined as a sequence of node ids that go in a circle, a loop, if you will.
This loopy sequence is referred to as a cycle. In the above example, the cycle would consist of the nodes n0, n1, n3, n4, n5, n6 and n7. These cycles will be written like (0, 1, 3, 4, 5, 6, 7).
If you were to count the different visually distinct “areas” of the cycle your answer would probably be three, but you could easily find more than three cycles.
What makes this correct or incorrect?
The sequence (0, 1, 2, 3, 4, 5, 6, 7) is a cycle and it loops, but it is not what we're looking for. The problem can be illustrated with the “how many triangles” puzzle you might have seen on Facebook.
How many triangles are in this image?
You should be able to count 24 different triangles depending on which areas you choose to include.
But that's not what we want. What we need to find are the 16 small areas.
We need a way to find the “small cycles” in the graph.
Minimal cycle basis
This paper on Minimal Cycle Basis is a bit less dense than most others academic papers (and it has pictures!). Its goal is:
…to compute a minimal number of cycles that form a cycle basis for the graph.
What does “Minimal Cycle Basis” mean?
It's just a fancy way to refer to all of the “small areas” of a graph. You can think of these as the “visually distinct” areas of a graph. Enclosed areas.
Left or right?
The main tool for finding the “minimal cycle basis” will be determining which edge to choose based on left- or rightness.
Should we go to a or b?
We'll think of this in terms of clockwise and counter clockwise.
curr for current, prev for previous
When traveling left, we choose the counter clockwise most edge (CCW) relative to the previous one.
CCW
When traveling right, we choose the clockwise most edge (CW) relative to the previous one.
CW
The algorithm
We will be finding the minimal cycle basis for the graph we saw earlier.
The first step is choosing the leftmost node in the graph.
When traveling from the first node, we want to go clockwise (CW). But relative to which edge?
For the first node, we imagine that the previous edge is “below” the current one. We then pick the CW edge relative to that.
In this case a is more CW relative to prev than b, so we'll walk to a.
After the first walk, we start picking the CCW edge.
In this case, that's b. We repeat the previous step and keep selecting the CCW edge until we reach the original node.
When we reach the original node again, a cycle is found.
We now have the first small cycle in the graph.
When a cycle has been found, the first edge of the cycle is then removed from the graph.
The first edge, (n0 n1), is removed
Then, the filaments of the first two nodes in the cycle are removed.
In this case, we only have a single filament
Filaments are nodes that only have one adjacent edge. Think of these as dead ends. When a filament is found, we also check whether or not the single adjacent node is a filament. This ensures that the first node of the next cycle has two adjacent nodes. We'll see an example of this later.
Now we pick the first node in the next cycle. In our graph, there are two equally left most nodes.
When this happens, we pick the bottom node, n1 in this case.
We then repeat the process from before. CW from the bottom for the first node, then CCW from the previous node until we find the first node.
We find the cycle (1, 2, 3).
Now we have the cycles (0, 1, 3, 4, 5, 6, 7) and (1, 2, 3).
Then we remove the first edge of the cycle and filaments like before. We start by removing the filaments connected to the first two nodes of the cycle.
We keep going until there aren't any filaments left.
Finding the next cycle is pretty obvious.
CW then CCW
We now have all the cycles of the graph.
This is the minimal cycle basis of our graph! Now we can toggle the fills of these cycles as we please.
The math
I want to dig into how the clockwise-ness of an edge relative to another edge is determined.
The only prerequisite for understanding this section are vectors; arrows pointing from one point of a 2D coordinate system to another.
i = (1, 0), j = (0, 1)
With two vectors sitting at the origin, i and j, we can create a square like so.
For the unit vectors (1, 0) and (0, 1) the square has an area of 1.
We can do this with any two vectors.
This shape is called a parallelogram. Parallelograms have one property that we care about, which is that their area is equal to the absolute value of their determinant.
That may sound like jargon, but the determinant happens to be really useful for us. Take a look at what happens when we move the vectors of the one-by-one square closer together.
When the vectors get closer, their area gets smaller. And when the vectors are parallel, the determinant and area become 0.
At this point the natural question to ask is what happens when we keep going and the blue arrow is to the right of the green arrow?
The determinant becomes negative!
When the blue vector j is to the left of the green vector i the determinant of the parallelogram becomes negative. When the opposite is true it becomes positive.
The implication for our use case is that we can check whether the determinant of two vectors is positive or negative to determine whether or not a vector is to the left or right of another vector.
And we can do this no matter the direction because the area of a parallelogram does not change depending on the orientation of the vectors that create it.
The determinant changes when the orientation of the vectors change relative to each other.
With this knowledge as our weapon, we can create a function, det(i, j), that takes in two vectors and returns the determinant.
The function will return a positive value when j is to the left (CCW) of i.
Applying the math
Say we're in the middle of the finding a cycle and we're deciding whether or not to move to n0 or n1.
Let's move this into the coordinate system.
We'll start off with a.
We want to get the vector from curr to a, which we do by subtracting curr from a. We'll call this new vector da.
We can do the same for curr using prev.
Now we can determine whether a is left of curr by computing the determinant of the parallelogram that da and dcurr form.
Note that the order is important. If we use da as i the area is negative. If we use it as j it becomes positive.
We can do the same with b.
With this information as our weapon, we know whether or not a, b and curr are left or right of each other.
What do we do with this information?
The green zone
We will be focusing on determining whether da is more CCW than db relative to curr. Simply put, is da left of db?
If da is more CCW than db relative to dcurr, da can be said to be better than db.
The first step is to determine whether the angle between dcurr and db is convex.
This “convexity” can more easily visualized by shifting dcurr back and imagining an arc like so:
The angle is convex
If the angle is convex, we we use the following expression to check whether da is better than db.
The ∨ symbol represents the logical OR operator in math.
Let's take a look at the individual parts of this expression.
Is da CCW of dcurr?
Is da CCW of db?
I find that it's pretty hard to visualize this mentally, so I think of the two different expressions creating a “green zone” where da is better than db.
For the first part of the expression (is da left of dcurr), the green area looks like so.
The second part of the expression asks if da is left of db. The green area look looks like so.
And since it's an OR expression, either of these sub-expressions being true would result in a being better than b. Thus, the green area looks like this:
Is a better than b?
We use this to determine the better-ness of a when the angle is convex.
But what if the angle from dcurr to db is concave?
Then the expression looks like so:
The only thing that changed here is that the logical OR operator (∨) changed to the logical AND operator (∧).
Let's take a look at what happens with the green zones using this expression.
Is da left of dcurr?
Is da left of db?
And since these sub-expressions are joined by logical AND, the green zone looks like so:
Using this method, we can always get the CCW or CW most node. And the great thing is that this method is independent of rotation and really cheap to compute.
Computing the determinant
Given two vectors, the determinant can be computed with this formula:
Intersections in the graph
Let's go back to our graph for a bit.
This graph is the simplest, most optimistic case. This graph only has straight lines, and no two lines cross each other.
This box shape has an intersection. The edge (0, 2) crosses the edge (1, 3).
With the intersection, the above area looks fillable. But defining the “filled area” is pretty difficult.
What makes defining this area so difficult? Consider this rectangle and line.
There are two intersections with the edge (4, 5) intersecting (0, 1) and (2, 3).
Say the area left of the line is filled. What happens if we move the line left?
Obviously the area shrinks, but what if we keep going and move the line outside of the rectangle? Which of these outcomes below should be the result, and why?
In this case kinda feels like the rectangle should be empty. But what if we move the line right?
Should it then be filled? Sure, but what if we move the line up or down instead? Should the rectangle fill or empty when the line is no longer separating the two sections?
Expanding the graph
This is how I believe Figma solves this problem. I call it “expanding the graph”, but the engineers at Figma probably use a different vocabulary to describe it.
Expanding the graph means taking each intersection, creating a node at the point of the intersections, and then splitting the edges that intersected each other at that point.
This is the original graph:
The edge (0, 2) intersects the edge (1, 3). When expanded, the graph would look like so:
A new node, 5 would be added at the point of the intersection.
The edges (0, 2) and (1, 3) have been removed and replaced by the edges (0, 5), (5, 2), (1, 5), and (5, 3).
The structure of the graph has been changed
Here's a graphic that should illustrate this a bit more clearly.
Expanding an intersection
Multiple intersections
These steps are pretty simple for line edges with a single intersections. But each edge can have multiple other edges intersecting it, and two cubic bezier curves can create 9 intersections.
This complicates things a bit. Let's take a look at a bezier-line intersection.
The best way to go about this is to treat the intersections for an edge as separate from the edge that intersected it.
The t values go from 0 at the start of the curve to 1 at the end of it
The line has two intersections at t = 0.3 and t = 0.7. The bezier has two intersections, but at t = 0.25 and t = 0.75.
Before we move on with this example, I want to introduce a different way of thinking about edges since I believe it will help with the overall understanding of the problem.
Duplicate edges
Two nodes may be connected multiple times by different edges.
In this graph, an edge represented by the node pair (2, 3) could represent either of the two edges that connect n2 and n3.
To get around this problem, we will give each edge a unique id.
For most future examples, I will still refer to edges by the nodes they connect since I feel it's easier to think about. But for the next example it's better to separate nodes and edges.
Intersection map
We can structure the data for the intersections of the edges like so:
Creating nodes at the intersection points of edges
When we encounter an intersection, we create a node whose position is at the intersection. We then add intersections to an intersection map that will contain the intersections for each edge with a corresponding t value and a nodeId. These intersections are sorted by the t value.
For the intersection with the lowest t value, we create an edge with the first edge part having the nodeId of the first edge part of the original edge. The second edge part should contain the nodeId of the intersection. This creates the edge (2, 4).
Subsequent edges will have the first edge part's nodeId be the nodeId of the previous intersection and the second nodeId be the nodeId of the current intersection. In this example, that edge is (4, 5).
One additional edge will be created for each edge with any intersections.
The first edge part's nodeId will be the nodeId of the last intersection and the second edge part's nodeId will be the nodeId of the second edge part of the original edge.
This was a bit of a mouthful, so hopefully this graphic helps a bit with understanding that alphabet soup.
Separating the intersections of an edge from the edges that created those intersections makes it easier to think about. It alleviates some of the complexity that might arise from multiple edges intersecting with each other.
Self-intersection
Cubic beziers can self-intersect.
This, unfortunately, means that every single cubic bezier edge has to be checked for self-intersection. It's an interesting problem that involves finding the two different t values that the bezier intersects itself at, but I won't be covering how to find those values here.
Once you have the t values, a self-intersecting bezier can be expanded like so:
The blue node should be invisible to the user
We insert n3 since having a node with an edge that has itself on both ends of the edge is problematic, but it should be hidden from the user.
Intersecting the loop of a self-intersecting bezier
Removing n3 at the first opportunity
Curvy edges
Earlier we covered the CW - CCW graph traversal algorithm to find the minimal cycle basis (small areas).
Finding the better (counter clockwise most) point adjacent to curr
But the algorithm described in the paper was designed to work with nodes connected by straight lines that don't intersect. Introducing edges defined by cubic beziers introduces significant complexity.
Which edge to choose, blue or green?
In the example above, we can find out that the blue edge is better than the green one by using the determinant. We are stilling defining better to mean the CCW most edge.
When working with cubic bezier curves, the naive solution would be to just convert the bezier to a line defined by the points at the start and end of the curve.
But that idea breaks down as soon as one edge curves over the other.
Oops
Let's take a fresh look at a bezier curves and try to work from there.
Looking at this, we notice that the tangent at the start of the curve, n0, is parallel to the line from n0 to cp0. So to get the direction at the start of the edge we can use the line (n0, cp0).
For clarity, the start of our edge, n0, is the same node as curr.
So by converting edges defined by cubic beziers into a line defined by (n0, cp0), we get the initial angle of the curve.
This seems like a good solution when looking at the “curve around” case.
Looks like we've solved the problem. Right?
No intersections
Before we move on to further edge cases, it helps to understand that any solutions assume that no two edges may intersect when deciding which edge to travel.
This is not allowed
The edges of the graph we're traversing must not have any intersections when we compute the cycles (minimal cycle basis) of the graph.
We can only operate on an expanded graph.
Like we covered earlier, an expanded graph is a graph that has replaced all intersections with new nodes and edges. So if the original, user-defined graph has any intersections, they would have to be expanded before we can find the graph's cycles.
The same edges as above, but expanded
Parallel edges
The next edge case is two edges being parallel (pointing in the same direction).
If the lines go in the same direction, determining which is better is impossible without more information.
Here are a few possible solutions for the cases where the control points of the curves are parallel.
Point at t
What if we just take the point on the curve at, for example, t = 0.1?
This produces the correct result for curves of a similar length, but we can easily break this with one curve being significantly bigger than the other.
This is effectively the same problem as the “curve around” case we saw earlier.
Point at length
Instead of taking a point at a fixed t value, we could take a point at some length along the curve. The length would be determined by some point on the smaller curve, e.g. at t=0.1.
I have not tried implementing this since I have another working solution, but this could possibly be a viable and performant solution if it works for all edge cases.
Lasers!
The next solution is a bit esoteric but produces the correct result. This is the solution I'm currently using.
We begin by splitting each bezier at t = 0.05 (image above is exaggerated). We then tesselate each part into n points.
Then, for each point of the tesselated bezier, we check whether a line from n0 to that point intersects the other edge.
It's pretty hard to see what's going on at this scale, so let's zoom in a bit.
When a point intersects the other edge, we use the point before it.
Found an intersection
Let's zoom in a bit.
The intersection close up
For the other edge, we have no intersection.
In that case, we just use the end of the edge as the direction line.
With this method we've produced lines that seem to represent their respective curves.
And this also works for the “curve around” case.
But it fails for a “curve behind” case.
This would produce the green edge as the more CCW edge, which is wrong.
My solution to this problem is to shoot an infinite laser in the direction of the previous edge.
We then check whether the points of the tesselated bezier intersect this laser.
But a line from n0 to the points would never intersect the laser.
Passes right through
Instead, we can create a line from the current point to the previous point and use that for the intersection test.
When we intersect the laser, we use the previous point. The previous point will always be on the correct side of the laser.
The point we use
And like that, we have a solution.
Parallel, but in reverse!
It could also be the case that the blue or green edges, a and b respectively, could be parallel to the edge from curr to prev.
a is parallel to prev
The process for finding the better edge follows a process similar to the one described above so we will cover this very quickly.
There are two cases:
A or B are parallel to Prev , but not both
If either a or b, but not both, are parallel to prev, we can simply compare the parallel edge to prev.
If the parallel edge is CW of prev, the parallel edge is better.
If the parallel edge is CCW of prev, the other edge is better.
Think a bit about why this is true.
If one edge is parallel to prev and curves CW, and the other is not parallel to prev, then the parallel edge is as CCW as can be. This means that the green zone for the other edge is completely empty.
The reverse is true if the parallel edge curves CCW, since it would be as CW as possible. This means that the green zone for the other edge is the whole circle.
Both A and B are parallel to Prev
Using the same laser solution as before, this case is covered.
Cycles inside of cycles
Now we're going to look at fills for a bit.
Let's take a look at a basic example of a graph with a cycle inside of another cycle.
You would expect the graph's areas to be defined like so:
But as it stands, if you hover over the outer area you get a different, unsatisfactory result.
But this makes sense. Let's take a look at the nodes of the graph.
The cycle (0, 1, 2, 3) describes the outer boundary of the area we want, but we aren't describing the “inner boundary” of the area yet.
Let's take a look at how we can do that.
Even-odd rule
Telling a computer to draw the outline of a 2D shape is simple enough. But if you want to fill that shape, how do you tell the computer what is “inside” and what is “outside”?
One way of finding out whether a point is inside a shape or not is by shooting an infinite laser in any direction from that point and counting how many “walls” it passes through.
If the laser intersects an odd number of walls, it's inside of the shape. Otherwise it is outside of the shape.
Intersects 1 wall, we're inside of the shape
Intersects 4 walls, we're outside of the shape
This works for any 2D shape, no matter which point you choose and which direction you shoot the laser in.
This also helps in the case of nested paths.
This gives us an idea for how we can define the “inner boundary” of a shape.
Reducing closed walks
Let's look at a graph with a cycle nested inside of another cycle, but with an edge connecting two nodes of the cycles.
This will lead back to how we can think about nested cycles and give us a deeper understanding on how to think about them.
Let's find the cycles. We use the same CW-CCW method as usual.
With this method, we go on what looks like a small detour around the inner cycle.
When we reach the node we started at, this is what the cycle looks like.
This is the first cycle we've seen where we cross a node twice (both n3 and n4). Something interesting appears when we take a look at the direction that the cycle takes throughout the graph.
We start off traveling CCW, but when we cross the edge from the outer cycle to the inner cycle the orientation we travel seems to flip.
I will state for now that we want to separate the outer cycle from the inner cycle and treat the edge between them as if it didn't exist. I will go into the why later and explain the how here.
We take all repeated nodes, in this case n3, and remove them from the cycle. We also remove any nodes that are between the two repeated nodes.
You might notice that n4 is also repeated, but since it's “inside” of the part of the cycle that n3 removes, we can ignore it.
We leave one instance of the repeated node, and then we have the cycle that would have been found if the crossing didn't exist.
We then mark the edge that connected the outer cycle from the inner cycle. I call these marked edges crossings.
It could also be the case that an outer-inner cycle combo has multiple crossings.
In that case, we mark all edges adjacent to the node connected to the outer cycle as a crossing.
And after all this is done, our cycles look like so:
Subcycles
Instead of referring to “inner” and “outer” cycles, I will refer to subcycles and parent cycles. This will make it easier to think about multiple cycles relative to each other.
Having said that, let's introduce a third cycle.
When we hover over the outermost cycle, what do you expect to happen?
Because of the even-odd rule, the innermost cycle is filled too!
To fix this, we can introduce the concept of direct subcycles.
Parent cycles (blue) and their direct subcycles (green)
A parent cycle may have multiple direct subcycles. But due to the non-intersection rule, a subcycle may only have a single parent cycle.
Let's take a look at how this works.
This graph has a a rectangle, our outermost cycle, which has two direct subcycles: a diamond and an hourglass. The diamond has two direct subcycles of its own, and the hourglass has three direct subcycles.
We will begin with the rectangle and its direct subcycles. We will name them, c0, c1 and c2.
The user has decided to fill some of these cycles, and leave some of them empty.
c0 and c1 are filled, and c2 is empty
Let's draw the graph without a stroke and with a gray fill. When drawing this graph we start with the outermost cycle, c0.
The graph to the left with the render to the right
Since c0 is filled, we draw it. If it were not filled we could skip drawing it. We can shoot a laser out of the rectangle and see that it intersects the walls of the rectangle once, so we can expect it to be filled considering the even-odd rule.
This may seem really obvious, but it's good to have the rules of the game laid out clearly before we move on.
Next we want to draw c1, the diamond in our graph. It was filled, just like the rectangle so we should draw it as well. But if we try to draw the diamond as well, we get the wrong result.
Our laser is intersecting two walls as a result of drawing both of the shapes when the have the same fill setting.
We intersect an even number of walls, so we're “outside” of the shape
So to draw the image the user wanted we can simply skip drawing the diamond since the parent cycle implicitly draws direct subcycles with the same fill setting.
The hourglass, c2, is supposed to be empty. With that being the case, just not drawing it seems like a reasonable conclusion. But since the parent cycle (rectangle) has already drawn the hourglass as if it were filled we need to “flip” the fill by drawing the hourglass.
And again, if we try to use the laser intersection method we see that the number of intersections is 2, an even number. And with the even-odd rule, an even number of walls means you're “outside” of the shape.
Now that we've drawn the rectangle and its direct subcycles, we can move onto the direct subcycles of those.
When working with c3 and c4, the direct subcycles of c1, we can treat them as if they're direct subcycles of c0 since c1 had the same fill setting.
For c3, we want to “flip” the fill setting so we draw it. But c4 has the same fill setting as its parent cycle so we don't draw it.
Even number of intersections so we're outside of the shape
And we can think of c5, c6 and c7 in the same way. We don't care whether they're filled or empty when rendering them. We care whether or not they have the same fill as their parent cycle.
We only need to draw cycles if their parent cycle has the opposite “fill setting” as themselves. If they have the same fill setting, we don't have to draw them.
This means that when drawing cycles, start by drawing the outermost “filled” cycle and then look at that cycle's subcycles. If a subcycle has the same fill setting as its parent cycle, it should not be drawn.
Contiguous cycles
A graph may have multiple “clusters” of cycles.
I use the phrase contiguous cycles to describe the “togetherness” of the cycles, if you will. I often think of these contiguous groups of cycles as being in different colors.
Finding these contiguous cycles can be done with a depth-first traversal:
Start at the first node of the cycle
Color each node you find
But remember the crossings? In the search, you may not crawl to adjacent nodes by edges marked as crossings.
So in the end, our colors actually look like this:
Take this group of contiguous cycles nested inside another group of contiguous cycles:
Because of the non-intersection rule we know that if one of the nodes in a group of contiguous cycles is inside of a cycle not in the group, all of them are.
This “contiguous cycles” idea is maybe not the most interesting part of this post on the surface, but I've found it to be useful when working on Vector Networks.
Partial expansion
When hovering an area defined by intersections, we are showing a cycle of the expanded graph.
Take this triangle as an example.
If we hover over one of its areas, we see an area defined by nodes that don't exist yet.
What the blue striped area represents is the area whose fill state would be “toggled” if the user clicks the left mouse button. This area does not exist on the graph as the user defined it. It exists as a cycle on the expanded version of the original graph.
The expanded graph
When the user clicks to toggle the fill state of the area, we would first have to expand the graph for the nodes and edges that make up that area to exist.
The expanded graph
But by doing that we've expanded two intersections that we didn't need to expand to be able to describe the area. These expansions are destructive in nature and should be avoided when possible.
Instead, we can partially expand the graph by only expanding the intersections that define the selected cycle.
Partially expanded graph
This allows us to maintain as much of the original graph as possible while still being able to define the fill.
Implementing partial expansions
The basic implementation is reasonably simple. When you create the expanded graph, just add a little metadata to each expanded node that tells you which two edges of the original graph were used to create it and at what t values those intersections occurred.
Then when the cycle is clicked, iterate over each node. If the node exists in the expanded graph but not the original graph, add it to a new partially expanded graph.
There are edge cases, but I will not be covering them here.
Omitted topics
Here are some of the topics that I decided to omit for this post. Go have a stab at them yourself!
Joins
Figma offers three types of joins. Round, pointy and square. How could these different types of joins be implemented?
Stroke align
Figma also offers three ways to align the stroke of a graph: center, inside and outside.
How do you determine inside- or outside-ness and what happens when the graph has no cycles?
Boolean operations
Figma, like most vector graphics tools, offers boolean operations. How could those be implemented?
Paper.js is open source and has boolean operations for paths, maybe you can start there?
Future topics
These are some of the more open-ended features and ideas I want to explore in the future.
A different way of working with fills
There are alternatives to how Figma allows the user to work with fills.
One possible solution I'm interested in exploring is multiple different “fill layers” that use one vector object as a reference. This would solve the “one graph, multiple colors” problem without having to duplicate the layer and keep multiple vector objects in sync if you want to make changes later on.
Animating the graph
Given an expression and reference based system similar to After Effects, what could you achieve when you combine it with Vector Networks?
Or maybe we could make use of a node editor similar to Blender's shader editor or Fusion's node based workflow?
There's a lot of exploration to be done here and I'm really excited to dive into this topic.
In closing
Thanks for reading this post! I hope it served as a good introduction to what I think is a really interesting problem space. I've been working on this problem alongside school and work for a good while. It's part of an animation editor plus runtime for the web I'm working on. I intend for a modified version of Vector Networks to be the core of a few features.
I've been working on implementing Vector Networks for a bit over half a year now. The vector editor is pretty robust when it comes to creating, modifying and expanding the graph. But the edge cases when modifying the fill state have been stumping me for quite a while now.
I wanted to have a fully working demo before publishing this post, but it's going to be a few months until it's stable enough for it to be usable for people that are not me.
The big idea behind the project is to be a piece of animation software that's tailor-made for creating and running dynamic animations on the web. I'll share more about this project at a later date.
I also just think that Figma's Vector Networks are super cool and it's really hard to find material about it online. I hope this post helps fix the lack of information that I encountered when attempting to find information about Vector Networks.