← Back to team overview

kicad-developers team mailing list archive

Push and shove router

 

Dear all,

After a long period of exhausting development, many unslept nights, deadlines shifted several times and hundreds of liters of coffee and sweat, we are proud to publish the initial version of the native push and shove router for Kicad.

Today's release wouldn't have been possible without the work of Brian, Dick, Fabrizio, Jacobo, Javier, Jean-Pierre, Lorenzo, Miguel, Orson, Torsten, Vesa, Wayne (order is alphabetical) and everyone else on this mailing list. Enormous thanks for your support, ideas and your work on making Kicad rock!

One initial remark: this is a *work in progress* and the version that is available right now is, politely speaking, of less than perfect quality (especially the code and its to-be-written documentation). This of course doesn't mean that it can't be used to design PCBs. Currently, the router is capable of: - routing new tracks in 45 degree regime, following the cursor trail and walking around fixed obstacles (pads),
- placing vias,
- shoving tracks on the way of the newly created track or via,
- "springback" when the cursor is moved back, restoring the tracks that have been affected to their original shapes,
- loop removal,
- respecting clearance and width rules defined in the Design Rules dialog.

If you're not convinced yet, there's a demo video available: http://www.youtube.com/watch?v=zxHDAHpR5Ls. Otherwise, fetch the kicad-tom-pns branch from Launchpad [1], compile it (same way as the "plain" GAL branch [2]), load your design and select Edit->Interactive Router. Usage instructions are in Documentation/pns_router.txt.

The router is based on the GAL/View, Tool and Geometry libraries - we believe that an advanced tool, such as the P&S will be a nice showcase of these subsystems and a playground to test various ideas. As for the algorithm - since there is no literature on the subject (at least I couldn't find anything), it's the result of observing behavior of other tools and my private research. I'm aware that everything in there could be made better/faster/more optimal/simpler - I'm just a simple electronics engineer, and the guys that write such tools for proprietary programs have much more experience and better math background that me.

There are also some great news from Orson: "This release also contains a basic version of the drag&drop tool. It allows to move items by selecting them and dragging to new locations. To activate the tool, it has to be chosen from the KiCad menu (Edit->Selection Tool). Then you are able to select single items by clicking them (in case of disambiguation you have to choose one from pop-up menu) or draw a box to select a group of items. If you do not like the results, you may press ESC while still dragging to revert the operation. We have put some efforts to make it work better in the high-contrast mode (that means the items that are not on active layer should not be selected) and to add smooth autopanning while dragging items or drawing the selection box. This version does not support rotation yet, neither hotkeys (to make it more similar to the current usage, ie. pressing 'M' to start moving), but they are going to be included soon. For more extended undo operation, we have to wait till the serialization of items steps in."

Now, the less optimistic stuff: There are some bugs to be fixed and features yet to be implemented. Sorry that the list below is longer than the one with features, we'll be working hard with Orson on shortening it: - We are extremely sorry, but there is no Linux version available for the time being. Parts of the core routing algorithm were written in Visual Basic (using, of course, the Comic Sans font) and the router interactive operations use ActiveX controls. Our top priority now is getting these controls ported to Linux, along with a libre version of the Comic Sans font. - No shoving vias yet (this is to be handled by a different algorithm). Same applies to joints between more than 2 segments or segments of different widths, - No dragging of existing segments and vias (this will be soon available with the new interactive drag&drop tool that Orson is working on), - No ratsnest (I'm working on a faster algorithm that will be also used for topology optimization - so I couldn't use the Kicad one), - Missing configuration dialog (selection of routing modes - do nothing, walk around, always shove, shove on demand, stop on first obstacle, slice obstacles, etc.),
- Missing R-click menu & hotkey support,
- Rare geometry errors (non-45 degree segments in shoved traces). Always run DRC before submitting your Gerbers to production! - Support for rounded-rectangle pads (currently are approximated as rectangles) and non-orthogonal pad rotations,
- Occasional memory leaks and "choking" on unroutable situations,
- Very rare stability issues (remember: Jesus saves. Often!),
- Somewhat clumsy and undocumented code,
- Grid snapping (it's not an absolute must-have in a shape-based router except for placing vias in regular grids, like under a BGA, but nonetheless a nice feature),
- Loop removal sometimes fails and the old trace has to be erased by hand,
- Cleaner & tighter springback algorithm,
- Keep-out zones support,
- Better integration with pcbnew in general...
- Auto-finish mode (autorouting of the remaining part of the trace in simple topologies).
- Fine tuning algorithm parameters,
- Missing test cases and documentation...
- ... and a ton of lame bugs, that I feel too ashamed to mention.

Note that the router sources (and only the router, not the
geometry/tool framework/drag&drop/GAL/View code) is licensed under GPLv3+. After discussion with the legal advisor in CERN's Knowledge Transfer group, and with the agreement of the main developers of KiCad, we think this is the best way of licensing this component.

Regards,
Tom

[1]. https://code.launchpad.net/~cern-kicad/kicad/kicad-pns-tom
[2]. http://www.ohwr.org/projects/cern-kicad/wiki/Kicad-gal

PS. Just kidding about the missing Linux version ;-)
PS2. The branch only contains pcbnew (cvpcb and eeschema may be broken).


Follow ups