kicad-developers team mailing list archive
Mailing list archive
Push and shove router
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 , compile it (same way as the
"plain" GAL branch ), 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
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
- 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
- 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.
PS. Just kidding about the missing Linux version ;-)
PS2. The branch only contains pcbnew (cvpcb and eeschema may be broken).