X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f X-Recipient: geda-user AT delorie DOT com Message-ID: <1446037932.3188.42.camel@ssalewski.de> Subject: [geda-user] Some update for Ruby toporouter From: Stefan Salewski To: geda-user AT delorie DOT com Date: Wed, 28 Oct 2015 14:12:12 +0100 Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.16.5 Mime-Version: 1.0 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by delorie.com id t9SDM4jp020009 Reply-To: geda-user AT delorie DOT com 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...