Report by B. Sc. Έλλεν Εμίλια Άννα Zscheile.

This was quite a bit involved in unexpected place.
For a bit of history, it is important to keep in mind that during the development of this, the underlying architecture was massively overhauled afaik twice or such.
Furthermore, I had to put some effort into handling dependency upgrades across a large amount of involved Rust crates, to make it possible that anyangle can be properly integrated into Topola later.

Architecture and implementation of the navigational mesh / Generating a multilayer navigation mesh

In anyangle, there exist two parallel infrastructures for this purpose:

(x).

flat ("squashed"), basically usually a single 2D triangulation of an PCB board, with each triangle being annotated with the layers on which there are no obstacles intersecting with that triangle, and the triangulation itself is computed from the set of obstacles (e.g. vias, pins, etc.), their polygonal boundary, and which layers it spans.

(y).

Remesh (navmesh.rs) + DelaunayNavmesh (delaunay.rs), which instead of having one triangulation for all layers, has separate triangulations per layer, and is supposed to also keep track of layer transitions, but that part is overall unfinished, and it should ultimately not be necessary to keep it around.

In terms of architecture, it should be kept in mind that for now, every insertion of an obstacle, and this includes newly inserted "etched" (i.e. finalized and integrated into the layout/geometry) (normally taut) paths, requires a retriangulation of at least the affected layer (for (y).), and in particularly thus a retriangulation of all layers and obstacles for (x).. This means that the originally pursued very aggressive caching done via Remesh probably won't last. For (x). steps were taken to ensure that retriangulation only affects the local area and their neighbors.

Subsequently, there are the relevant PRs for anyangle. and relevant issues (all tagged with the "navmesh" label).
In particular (x). PR #20 implements the newer flat variant, for which it was easier to come up with an easily realizable way to implement an multi-layer A* search. It takes the basic idea of how the Remesh implementation generates a triangulation using the iShape ecosystem, and generates a single triangulation for all layers, which is way easier to deal with both in the generation phase, and has more obvious behavior in the search phase.
Note that Mikolaj Wielgus wrote almost all of the code for (y).

Up-/downstream integration

One of those architectural overhauls was the dearcut crate in Topola, which was ripped out in Pull Request 297 and should be later replaced by the anyangle crate, on which most of the development here actually happened.

Some refactorings were necessary upstream in the polygon_unionfind crate:

• PR #1, PR #2, PR #3
• also downstream: Topola PR #298

Future outlook and planned integration

Find multilayer path (any-angle) with layer transitions

For pathing, there are the relevant PRs for anyangle (label "pathing").

• PR #4 implements the so called "Stupid Simple Funnel Algorithm", which is necessary to implement any algorithm that performs a search for taut paths on a triangulation (it probably also works on polygonal complexes in general). This part is also already tested and merged.
• PR #6 improves that algorithm to also keep track of additional metadata (e.g. the associated point index / vertex identifier) of the points where the path has to bend to stay in the funnel. (also already merged)
• [currently work in progress] PR #7 then leverages (x) and this funnel algorithm to implement an multi-layer A* search, which is norm / distance metric agnostic (for measuring the length of traces between two points), and has an input to vary the "penality" (in the LaTeX sense) for layer switching.
  This proof of concept compiles and works on a few simple examples, including across multiple layers, but isn't properly tested yet.
  It contains a demonstration program astar-demo which gets passed a configuration file that describes the routing problem to solve. See example configuration files demos/astar-demo/ex*.toml. That PR also contains some images of the results (where found paths are highlighted in red+magenta), repeated below.

Examples

astar result:
  - point [20, 20] on layer LayerId(0)
  - point [40, 20] on layer LayerId(0)
  - point [40, 40] on layer LayerId(0)

astar result:
  - point [20, 20] on layer LayerId(0)
  - layer transition from LayerId(0) to LayerId(1)
  - point [20, 20] on layer LayerId(1)
  - point [20, 40] on layer LayerId(1)
  - point [40, 40] on layer LayerId(1)

Implement pathfinding with 45° bends

For 45 degree pathing, there are the relevant PRs for anyangle (label "45 deg pathing")

• PR #8 with associated white paper / technical report introduces a norm (and subsequently a distance metric) that can be plugged into the norm-agnostic implementation of pathing. to find length-optimal paths in that case, too, without having to rely on computationally expensive route searching on a fine grid.
• PR #28 preserves the intermediate data to make it possible to compare exact results and not rounded ones (this is only possible because we're working in 2D). This is also necessary to later make it possible to expose a GUI to the user to adjust the result in the bounds admitted under invariant path lengths (see next bullet point).
• Properly integrating this into the GUI, optimally in a way that allows the user to choose where PCB to-be-etched "taut" path kinks should be inserted, in case of connections between points which don't lie on a grid axis-aligned or diagonal line (which is a choice that doesn't affect the resulting length of the path). Similarly to coming up with this mechanism and proving its correctness, this is probably going to be a bit more complicated.

Materialize the new traces with vias

Similarly for the last milestone, there should be some GUI integration to choose suitable places to insert vias along a line. Currently, testing and GUI integration is still missing, which was unfortunately stalled a bit by having to do some larger-scale dependency mangling to migrate a bunch of involved crates to current versions of the rstar, maplike, undoredo, polygon_unionfind crates.

Funding

This project is funded through NGI0 Commons Fund, a fund established by NLnet with financial support from the European Commission's Next Generation Internet program. Learn more at the NLnet project page.