Ratsnest for GAL blueprints
Maciej Sumiński/CERN, October 2013
Ratsnest is an option for marking to user currently unconnected parts to make easier to connect them together. Usually, it is shown as straight lines drawn between nodes within the same net that need to be connected.
Rationale
KiCad currently contains routines for computing ratsnest, but these can be improved. For example, although pins 4 & 5 of the vacuum tube (shown on the illustration 1) belong to the same net and could be connected together – the ratsnest suggests longer connection through the pin 1 of the connector (CONN_2).
An example of nonoptimal ratsnest.
Another reason is the fact that currently when computing ratsnest, only pads are taken into account, despite of possibility of having tracks that could be closer than any other pad. Example of such situation is shown on the illustration 2 – red tracks are literally touching the pads, but the ratsnest still shows only pad to pad missing connection. But it has to be remarked, that while a track is routed, the currently routed track is taken into account and shown in the correct way (ie. it shows the missing connection between track and pad or even other tracks belonging to the same net).
Ratsnest is computed basing only on pads.
As far as I could see, the current implementation recomputes the whole
ratsnest even when only a single item has changed, which is rather
unnecessary and could be changed.
Another reason for the refactorization of the ratsnest code is
introduction of the GAL. All items that are shown in the view, should be
written as VIEW_ITEMs, so is the ratsnest. Ideally to preserve the MVC
model, the ratsnest code should be split to 3 parts:
- algorithm that gets list of BOARD_CONNECTED_ITEMs as an input and outputs list of missing connections that makes the ratsnest
- data structure that holds the output of the above algorithm
- routines that use the data structure and paints them into the view
Proposal
Ratsnest could be computed using undirected graph algorithms, where
vertices are connection points (ie. vias & pads) and edges are
connections (ie. tracks & vias as they are connecting different layers
together). There are a few issues that have to be solved in order to
compute a ratsnest.
Identification of connection points
Connection points (aka nodes) should be identified by coordinates (x, y)
and layer. This will allow to treat eg. pad and beginning of a track
located in the same place as the same node. It should not be possible to
add two nodes that have the same coordinates and layer and treat them as
two different nodes in the graph.
Solution: Usage of std::set/boost::unordered_set as a container for
connections points. It requires hashing function to be prepared (eg.
using boost::hash), possibly not very demanding on CPU cycles. Nodes
should store an unique id, so they can be quickly compared if they are
the same or different.
In case of trial of adding a node that is already stored in the set, it
should has the same node identifier assigned, to show that it is exactly
the same node.
The algorithm
There is the Boost Graph Library [1] that allows to quickly use and adapt graph based data structures and algorithms. The presented algorithm computes ratsnest for a single net, it has to be run for every net in the board.
- Iterate through all the BOARD_CONNECTED_ITEMs for a given board.
Add pads as nodes, vias as connections between nodes (the same
coordinates, but different layers) and tracks as connections between
nodes (the same layer, but different coordinates). At this time,
nodes are assigned their unique numbers.
The connections should be treated as graph edges with zero weight, it is explained later in the text.
This step is shown on the illustration 3. Pads circled in red belong to the same net, they are assigned unique numbers (1-9). Please note that track endings have also nodes and identifiers assigned (1,2 and 3, 4, 5, 6). Zero-weight edges made by tracks are drawn in blue color.
# Create subgraphs (connected groups of items). Probably, some of items
are already connected together (directly by a single track or indirectly
by a few tracks and vias) – they should use the same subgraph
identifier. The assignment is done using the depth-first search
algorithm contained in the boost library.
In the example situation (shown on the illustration 3), 5 subgraphs are
created:
- nodes 1, 2 (let's name it subgraph A)
- nodes 3, 4, 5, 6 (let's name it subgraph B)
- node 7 (let's name it subgraph C)
- node 8 (let's name it subgraph D)
- node 9 (let's name it subgraph E)
- Determine the missing edges.
Variant A. There is no point in adding edges within the same subgraph, as those nodes are already connected. In order to obtain the ratsnest, we need to consider only edges between different subgraphs.
We add all the possible combinations of edges between different subgraphs:
for subgraph A: 1-3, 1-4, 1-5, 1-6, 1-7, 1-8, 1-9, 2-3, 2-4, 2-5, 2-6, 2-7, 2-8, 2-9 (there is no 1-2, as both nodes belong to the same subgraph)
for subgraph B: 3-7, 3-8, 3-9, 4-7, 4-8, 4-9, 5-7, 5-8, 5-9, 6-7, 6-8, 6-9 (there is no 3-1, 3-2, 4-1, 4-2, etc. as they are already added for subgraph A and the graph is undirected)
for subgraph C: 7-8, 7-9
for subgraph D: 8-9
Weight of those edges, should be the distance between the connected nodes. Remember that edges between already connected nodes have zero weight.
Probably there could be an optimization introduced that blocks adding edges for a given subgraph if there is already lighter (shorter) edge added. For example: as the weight (distance) of the edge 1-3 is smaller than the weight of the edge 1-7, we can skip adding the edge 1-7.
Variant B. Apply the Delaunay triangulation, so it generates the missing edges. The weight of the generated edges should be equal to the distance between two nodes connected by that edge. All edges connecting nodes that have the same subgraph identifier (ie. connected directly or indirectly) – should be zero weight. - Apply the minimum spanning tree algorithm. In the beginning of this step we already have a graph containing both edges between already connected nodes (with zero weight) and all the possible combinations of edges between not connected nodes belonging to different subgraphs (with >0 weight). The minimum spanning tree algorithm results in the subgraph that contains all the vertices connected together using the lightest (the shortest) edges. In our case, it will surely contain edges between already connected nodes (as they have zero weight, so they are granted for free) and the shortest edges that could link unconnected nodes.
- Remove edges with zero weight. The last step is to remove zero weight edges (as they are already connected). The remaining edges make the ratsnest. This step could be integrated with the step 4, as 0-weight edges could be filtered out with an application of a custom inserter, that is required by the Prim's minimum spanning tree algorithm offered by the BGL.
Updating single nodes/connections
There should be a possibility to recompute the ratsnest for a single
node/edge, instead of recalculating the whole ratsnest from scratch. It
will be used eg. when routing tracks or dragging items, where usually a
few items coordinates change, but the rest remains the same.
In this case, one could remove all the edges connected to the modified
node, update its coordinates & layer and then look for the lightest (the
shortest) edge. It may happen that the node has ended up with
coordinats/layer that is shared by another node – if so, then they
should have the same node & subgraph identifiers.
Filled zones
We have to check all nodes on the given layer against all filled zones
on that layer. This may solve the problem of checking if a zone contains
a point:
http://www.codeproject.com/Tips/84226/Is-a-Point-inside-a-Polygon. For
all nodes connected by a zone, there should be appropriate edges
added.
After a node was found to be contained by a zone, it may be excluded
from further tests against other zones.
Other remarks
Usually, there is a lot of nets that contain only a few nodes – most of
connections are simply pad to pad, sometimes with a parallel capacitor
or a pull-up/down resistor attached. In case of partially connected
nets, there can be also a few other connection points resulting from
having tracks (each track contains two connections points – the origin
and the end). The exception to above are power nets (eg. GND, VCC and so
on) that usually connect a lot of components.
This makes the algorithm has to deal with a big number of small graphs
and just a few bigger graphs. It is worth to remember when choosing some
of solutions.
In the particular case of just two nodes remaining in the net, the
algorithm could be skipped and those two nodes could be directly added
to the ratsnest.
There should be also a possibility to control the list of nets for which
the ratsnest is displayed. At a particular moment, one may be not
interested in seeing the whole ratsnest, but only a subset of it, eg. a
single bus or a power net. This could be added using a list of nets,
where user can choose the subset or by right-click context menu
available for every BOARD_CONNECTED_ITEM, containing an option:
“Toggle ratsnest”.
References
[1] Boost Graph Library: http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/index.html