Do any of the other maintainers have a good understanding of the splines feature and its associated code? If you search “splines” we have 73 open issues that match, and there seems a near-constant stream of new issues coming in that could be summarized as “this splines directive doesn’t work.”
I bring this up, because I think it would be really impactful to users for someone to dive into this code and resolve these issues. Many of them probably have the same root cause.
The spline router was mainly written by Eleftherios Koutsofios (still in AT&T Labs) and David Dobkin (Princeton CS), though Emden Gansner may have worked on it, and definitely on the code that calls it.
Implementing a General-Purpose Edge Router describes the algorithm. There was a video made around but it was on analog video so maybe did not make it to digital but if it would be really helpful l’ll search my archives.
There are two main parts to the spline fitter.
There’s a top level, that knows about the graph layout. It computes a “feasible region” or constraint polygon for the spline, which is a simple polygon that must contain the endpoints. In dot, the polygon is obtained by first computing a “box path” (a list of boxes that touch sequentially on sides but the direction can change) because it is easy to generate boxes from the levels of the ranked graph. Then there is a phase to walk the boxes and make them into a simple polygon.
It calls a lower level, the routesplines library, to get a piecewise cubic Bezier curve that connects the endpoints and must stay within the constraint polygon. Routesplines applies an iterative divide-and-conquer approach. For example first it tries a straight line. If that does not stay within the constraint polygon, I think it tries to bend the spline by adjusting the endpoint slopes. If that doesn’t work then somehow it chooses a third point between the other two that is within the constraint polygon, divides the problem and recurses.
When the top level gets the result spline back, it does some more graph layout bookkeeping to keep track of the actual space used by the spline (for example moving virtual nodes to reflect the spline) so unused space is available for splines that are routed afterward. This makes the spline routing phase seem not trivially parallelizable (not that we tried to do that, but people have asked).
FYI/FYA in code like this one always has to watch out for numerical issues and especially textbook algorithms that assume points in general position (no duplicate or collinear points or degeneracy, like boxes with 0 height).
Thanks, Stephen. Seems you’re far and away the most knowledgeable person right now. If you have bandwidth, I think you’re best placed to resolve the spline issues. Otherwise one of us minions will have to take a crack and lean heavily on you for clues.