Mail Archives: geda-user/2013/10/28/12:36:55
On Sun, 2013-10-27 at 19:18 -0500, John Griessen wrote:
> > http://www.ssalewski.de/tmp/routerfun.png
>
> How do we interpret that image Stefan?
Colored traces are the result of a modified version of
"Dijkstra's shortest path search" from a start pin/pad to a destination
pin/pad -- each one of these traces is then collapsed to a black curved
copper trace. Of course these black traces should not touch each other
or even cross -- for a few cases they still do. The small rectangular
areas with thin inner lines are the pads in original size, rounded by
pins at the corners. The small gray discs are pins or vias, some vias
are inserted by the layer assignment process. (The layer assignment
process takes multi-terminal nets, generates a minimum spanning tree (a
steiner tree would be even better, but it's generation is more
difficult, I have still not found a good description.) out of these
getting 2 terminal nets, and splits these 2 terminal nets into multiple
segments, which are assigned to the available layers trying to archive
minimal crossings. This process is described in detail in Tal Dayans's
thesis, so implementing that took me less than 100 hours. Unfortunately
the rubberband routing is not described in such a detailed way.) Pins
are shown at a fixed too small size yet. The colored traces can overlap,
but should not cross -- I did use a transparent color to see them better
when overlapping. All other colors, i.e. the red arcs, are only helpful
to debugging.
Generally it is a trivial task to convert the black curved traces to
real copper arcs and lines in PCB format -- so basically we have a "real
useful router"! But of course still a lot of work is necessary -- for
non trivial dense layouts the router crashes often or gives invalid
results. But I think fixing these bugs should be not too difficult --
for most bugs I already know the reasons. Most bugs should simple
disappear when I clean up the code -- this cleaning is what I really
should do in the next months. For me this simple "real board routing"
was an important milestone, because it is a big difference if we route a
set of random points, or a real boards. One difficulty of real boards
are the straight lines build from pads and pins of multi-pin devices --
thats makes traveling along triangulation edges some sort of difficult,
i.e. there is no clear left or right turn when you walk from pin to pin.
But I found solutions for these problems, and it seems to work.
I still wonder how Anthony B. has solved all these for his topological
router, in the short period of a "Google Summer of Code 2008". He must
have been an really smart guy -- sad that he fully retired. Of course
his code is still available, 8 k lines of plain C. For me it should be
nearly impossible to understand or even extend that, but maybe in future
a really smart guy with some hundreds hours of free time may continue
Anthony's work.
Best regards,
Stefan Salewski
- Raw text -