Diagram Lines: Path Grid Selection

Freehand is an infinite canvas for multi-player collaboration. With our diagramming lines feature, users can select a source object and a destination object, and Freehand will draw a line between them — as shown in the picture above.

We recently improved this feature by allowing users to pick the edge of an object they want their diagramming line to connect to. Because Freehand’s canvas is infinite, there is no underlying fixed grid of points that we can route a diagramming line through. This is equivalent to having an open field between your home and your office, as opposed to a network of roads. Without a candidate set of roads to navigate over, it is possible to take almost any path through that open field for your commute.

Users can also elect to allow Freehand to dynamically determine the best edge of an object to anchor the diagramming lines to (as opposed to endpoints that are affixed to a specific edge of an object). In our commute analogy, this is equivalent to having multiple doors to your house and office. Which of the many possible doors do you depart from; which door do you enter? Again, an almost infinite set of paths is possible.

These improved diagramming features presented a technical challenge: provided with only the end points, how can we route an intuitive and efficient path between the two objects?

This blog post series will be broken into three parts. Throughout the series we’ll walk through how the Freehand engineering team solved these problems and released diagramming lines that are dynamic, intuitive, and fun! In this first post, we’ll tackle grid selection. Before we talk about pathing algorithms we need some sort of candidate set of points through which we can route a diagramming line. How do we even go about picking candidate points on an infinite canvas?

Problems with an Almost Infinite Grid

What if we didn’t pick a grid of candidate points? Or what if we threw a ton of evenly spaced points on the canvas? Would either of these approaches work?

One issue with an almost infinite grid is that the objects can move fluidly relative to one another. As you can see in the gif above, the diagramming lines remain attached to center points on the edges of the objects. But those center points move relative to one another. Which means our grid, to account for all possible center points, must become almost pixel perfect.

Let’s assume our grid is 1:1 with pixels, then. This is probably not a good idea because users can have different screen resolutions. But let’s assume we could overlay a grid that was reasonably centered for the objects in question. The issue with such a grid is that our route search space becomes very large, and the grid becomes costly to generate and navigate.

We aim to render Freehand 60 times per second. For a single diagramming line this might not seem like a challenging computation. Even ignoring all other canvas interactions/animations, it’s possible for a single user to force many diagramming line recalculations with a single drag operation.

We need to be efficient in our grid selection. If we were mapping GPS directions between locations in two separate cities, we might not consider every single side-street in our computation. We would probably only consider highways or thoroughfares first. The goal of grid selection is to craft a small grid of highways and thoroughfares. We effectively want to eliminate all of those small side-streets that we won’t reasonably navigate. The smaller the grid, the better, because, that way, we’ll be able to cram more routing calculations into a single frame.

Points of Interest

Let’s try constructing a grid based on points of interest. That is, points that we might reasonably navigate through on our path from home to work. For example, we might pick a highway exit closest to our source and destination and connect those points in the grid. We might also pick a few thoroughfares that lead from our home to the source highway point. And so on.

In Freehand we can apply these same principles. We can simplify our task by ensuring that all of the points of interest we select are connected vertically and horizontally in straight lines only. We know that we don’t want to have diagonal lines in our resulting path. Which means we can pick points of interest based on two-dimensional cartesian coordinates (x,y) and then create a strict vertical/horizontal grid of candidate path legs over those points.

In the commute example above, I used a simple heuristic of convenience or common-sense to pick highway entrances and exits. We can do the same for Freehand based on our visual understanding of diagramming lines. For instance, we know that diagramming lines need to have some space between them and the objects they are navigating to. In the example below, we would never navigate along the bottom of the purple rectangle because that line would not be easy for users to see or distinguish from the object’s border. We should instead always jump away from the edge by some padding before proceeding.

This means we can pick points of interest along the padded boundaries of our objects. For example, we can construct a list of x-axis coordinates based on the padded left edge of each object, and the padded right edge of each object. And we can construct a list of y-axis coordinates based on the padded top edge of each object, and the padded bottom edge of each object. If we then perform a product over these two lists, we end up with a grid that looks something like this.

When we navigate over the top of an object, for example, we’ll end up using some of these points along the path. These are great points!

You’ll notice that we are still missing some points along the way — our grid is not complete. It’s going to be easier to visualize this next part without dynamic endpoints. With dynamic endpoints we are effectively telling Freehand to pick which edge of the object we should connect our diagramming line to, based on the relative position and distance between two objects. We’ll come back to these dynamic lines in a future post because they are an application of a more generalized version of what I’ll explain next.

With static endpoints, we restrict Freehand to one edge of an object. This means that as the objects move around each other, the diagramming endpoints remain fixed to one edge of the object even if there is a more efficient path from some other edge of the same object. In our commute analogy, this is like telling Freehand that all but one door out of the building is locked. In the following gif we’ve bound the source endpoint to the right edge of the purple rectangle and we’ve bound the destination endpoint to the top of the green rectangle.

If we simplify our problem to static endpoints, we can extend our x-axis coordinates list and y-axis coordinates list with those new positions. The resulting grid looks like this.

The first thing you might notice is that the grid is not evenly distributed. That’s okay. We have all the points we need. And we are guaranteed to only need a 6x6 grid for all of our pathing. There are some unnecessary points that we can prune, but the grid is already quite small and of constant size, so I won’t delve into any additional optimizations. It’s not trivial to prune points because there are edge cases with overlapping shapes that make all of the points we have selected viable path candidates under some circumstances.

Hopefully this gives you a good sense of how grid selection works.

What’s Next?

That’s grid selection. We’ve divided an infinite space based on points of interest. And we’ve defined how those points of interest connect to one another (vertically and horizontally) in order to get a set of candidate path legs. In the next two blog posts in this series we’ll look at navigating this grid, and then how we evaluate candidate paths.