GSoC project: Topological Autorouter

[Anthony Blake]

Hi Everyone,

As some of you know I've been developing a topological autorouter for
PCB as part of the google summer of code. The summer of code is now
finished, and although the autorouter isn't really ready for users, it
is routing some simple boards, and is already demonstrating advantages
over PCB's current maze router.

Please see http://www.wand.net.nz/~amb33/toporouter/ for more
information, and a couple of screenshots of output.

A few limitations which prevent it being used on real boards:

- It currently only supports through-hole tech, because it isn't yet
importing the geometry of pads etc from PCB as constraints for the
autorouter;
- It doesn't yet support planes and polygons;
- Designs incorporating high-density packages such as BGA's really
require a heuristic;
- Results would be greatly enhanced through the use of topologies other
than euclidean minimum spanning tree (EMST), such as a force-driven
constrained steiner-tree.

As well as fixing bugs, I will be tackling these issues in the coming weeks.

Any comments would be appreciated!!

Cheers,
Anthony Blake

[Peter TB Brett]

Post by Anthony Blake
Any comments would be appreciated!!

I am very impressed. Well done!

Peter

[Peter Clifton]

Post by Anthony Blake
Hi Everyone,
As some of you know I've been developing a topological autorouter for
PCB as part of the google summer of code. The summer of code is now
finished, and although the autorouter isn't really ready for users, it
is routing some simple boards, and is already demonstrating advantages
over PCB's current maze router.
Please see http://www.wand.net.nz/~amb33/toporouter/ for more
information, and a couple of screenshots of output.

That is superb work there, and a great write-up on the project. I really
look forward to trying it out. I wish I could understand the algorithms
behind it a little better - my brain hurts when subject that kind of
thing!
--
Peter Clifton

Electrical Engineering Division,
Engineering Department,
University of Cambridge,
9, JJ Thomson Avenue,
Cambridge
CB3 0FA

Tel: [phone] - (No signal in the lab!)

[Kai-Martin Knaak]

The summer of code is now finished,
and although the autorouter isn't really ready for users, it is routing
some simple boards, and is already demonstrating advantages over PCB's
current maze router.

You have obviously come a long way!

Please see http://www.wand.net.nz/~amb33/toporouter/ for more
information, and a couple of screenshots of output.

Hmm. I don't see any two sided routes in the screenshorts. Is this one of
the limitations?

---<(kaimartin)>---

[DJ Delorie]

Hmm. I don't see any two sided routes in the screenshots. Is this
one of the limitations?

I've routed 2-sided with it. The interesting problems are all on
1-layer boards, that's all.

[John Griessen]

Post by Anthony Blake
Hi Everyone,
As some of you know I've been developing a topological autorouter for
PCB as part of the google summer of code.
- It currently only supports through-hole tech, because it isn't yet
importing the geometry of pads etc from PCB as constraints for the
autorouter;
- It doesn't yet support planes and polygons;
- Designs incorporating high-density packages such as BGA's really
require a heuristic;
- Results would be greatly enhanced through the use of topologies other
than euclidean minimum spanning tree (EMST), such as a force-driven
constrained steiner-tree.
As well as fixing bugs, I will be tackling these issues in the coming weeks.
Any comments would be appreciated!!

Your write up and before/after examples seem fabulous! Congrats on
condensing the info from past research papers in your biblio into
working code. That's no small feat.

What have you got in mind for heuristic rules to deal with BGA-like
packages? Will you have a user input file for specifying zones to
route, such as quadrants, when the package is a square arrangement?
How about user definitions of what is "good layout" to use as starting
point for next autoroute run?

Thanks for your GPL'd work. I'll spend soem time trying it out to
generate more comments.

John Griessen