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.
In anyangle, there exist two parallel infrastructures for this purpose:
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.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).
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:
For pathing, there are the relevant PRs for anyangle
(label "pathing").
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.
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)
For 45 degree pathing, there are the relevant PRs for anyangle
(label "45 deg pathing")
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.
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.
