Mail Archives: geda-user/2015/10/28/08:32:04
On Sun, 2015-10-11 at 20:58 +0200, Stefan Salewski wrote:
> On Sun, 2015-10-11 at 20:37 +0200, Kai-Martin Knaak wrote:
> > Thank you. This link worked nicely.
> >
> > I will try to get a grasp how the algorithm works. Don't expect me to
> > come up with ideas for improvement. All the simple routes have
> > probably
> > already been thoroughly explored.
>
> There is much room for improvements, as I already said. One reason is,
> that Tal Dayan's thesis is less concerned with PCB and the space
> restrictions. For example when you read about layer assignment, it is
> clear that that algorithm is nice, but it assumes that only traces build
> barriers for other traces. But on PCB dense spaced pin rows can built
> barriers too. That is only one point, which I can currently remember and
> I have not tried to improve. Another point is, that I used a lot of
> hashes to mark blocked paths. I was not really happy with that, it
> works, but is a simple minded way. The thesis told us only about the
> region idea, but not how they really did it unfortunately. (But they
> have 14k lines of code as they told, we have only 2k.)
OK, since some people asked about it in the last weeks:
I have made a tar archive containing all the Ruby glue code for CGAL and
BOOST library, so you can play with it when you really want.
AND: I spent the whole last weekend fixing the ugly usage of hashes for
some blocked path. At the same time I was able to relax routing to allow
also outer convex paths. Both is not really an improvement for actual
routing -- hashes worked fine, but consumed much memory and it was
really not a smart solution. And convex outer path -- well generally the
inner path give better traces, maybe with very few exceptions. But I
always had the feeling that outer paths should be usable too, and now
that is done. We have to tune weighing of outer/inner path, without that
too many outer ones are used.
I had not the time to clean up the code yet :-(
If you want to play with it: You need Ruby interpreter, preferable
latest version 2.2, ruby-gnome2 for cairo picture drawing, and CGAL and
BOOST library. Maybe developer packages for some of that. And a Linux
box with a working C compiler.
Download Router20151028.tar from http://ssalewski.de/Router.html.en and
extract it in an arbitrary named directory. You get directories Router,
RAPOLLONIUS, RCGAL, RTREE_2D_POINT, RTREE_2D_RECT and RBOOST. Cd into
Router, and type "bash gen_bindings". That will generate .so files for
the CGAL and BOOST bindings. Now you can start testing with "ruby
router.rb". Result should be an test routing generated with random
numbers. Or type "ruby pcbtr.rb" to generate pics for that example pcb.
Of course that all is only playing -- next would be cleaning up the
code, then improving the layer assignment. For that we may route each
subpath in advance to detect barriers and get a lower bound for the
detour. After that we may tune the real routing process -- a very simple
way may be to reorder the routing sequence, moving failed traces further
to the start. And we should add some GUI support of course...
- Raw text -