Ratsnest for the GAL blueprints
Maciej Sumiński/CERN <maciej.suminski@cern.ch>, 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).
Illustration 1: 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).
Illustration 2: 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.
Illustration 3: The first algorithm step.
# 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 3, 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.
As the algorithm is likely to allocate a big number of small objects (structures describing nodes & edges), it is a good idea to use a memory pool scheme to reduce the overhead caused by memory (de)allocations. An easy solution may be provided by the Boost Pool [2] library.
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”.
Possible upgrades
Dynamic ratsnest algorithm selection
The ratsnest algorithm used with the GAL displays only one ratsnest line
for items that are currently modified (e.g. dragged). It is the result
of having some of nets (mostly power nets) too heavy to compute every
rendered frame, so it is displayed in a simplified way. Still, the full
dynamic ratsnest looks much better then the simple one.
However most of the nets are quite simple – consisting of pad to pad
connection, with some tracks and parallel parts (capacitors/resistors)
making a net just a several nodes to compute. For such cases there could
be the whole ratsnest recomputed and still retain the expected
smoothness of the tool.
It gets complicated if one is dragging a module that is connected to
many nets at the same time. Even if there are no big, complicated power
nets attached (a rare case), still a big number of such simple nets may
slow it down to an unacceptable level. It also depends on the hardware
that is used for running KiCad. I have already seen cases, where
ratsnest for a power net requires around 200 ms, resulting in 5 fps
framerate.
To solve the problem, a single frame computation time (or a mean value
for a few last frames) could be used to determine if full ratsnest
recomputation takes too long.
By default it could start with the full algorithm and if it takes more
than 20 ms (50 fps) and then switch to the simple algorithm. It should
leave some time margin for other computations that may take time at the
same time and for the simple algorithm.
The single frame computation time could be easily obtained by adding
profiling timers (profile.h) in the void EDA_DRAWPANEL_GAL::onPaint()
function. For the ratsnest algorithm selection, there could be a common
wxTimer (or any other timer that uses callbacks) to measure current
computation time. If the full ratsnest algorithm is finished, then the
timer is off and further computations are done using the full algorithm.
If it did not fit in the time slot, then it switches to the simple
algorithm and uses it until the dataset is changed (i.e. movement
operation is finished and another one is started).
Pool allocators
The algorithm performs a lot of memory (de)allocations. First, it
processes a board and creates nodes and connections (edges), basing on
the contents (one pad/via = one node, one track = two nodes & connection
between them). Then it maps the created model to the processed
BOARD_ITEMs, so the ratsnest model could be updated using BOARD_ITEMs
as parameters.
To simplify the node management, they are stored as shared pointers (to
give an example: quite common case is a single node that is used
simultaneously by a few tracks and a pad – and all of them should share
the same node object). The shared pointers are emplaced in containers,
but the data they point is created in the default way. Proper usage of
pool allocators should boost the speed of items (de)allocations.
Parallelization
NOTE: The RN_DATA::Recalculate() part is already there, thanks to
Carl Poirier.*
The ratsnest is computed on per net basis in a loop, it means that in
theory it could be easily parallelized, as two different nets ratsnests
are completely unrelated. The loop is in the RN_DATA::Recalculate()
function. Another good place for the multithreaded approach is the
RN_POLY::HitTest() function. It tests if a point is located inside or
outside a polygon and to do so it compares the point location against
every polygon line (that does require knowledge of previous results).
I have already tried applying the OpenMP library, as it is multiplatform
and easy to use, but it did not give me the expected outcome. I suspect
that the thread management overhead could be too significant to gain any
real speed. This probably could be resolved by using some more pragmas
(e.g. to make a single thread compute a few loop iterations or move only
the biggest nets to separate threads) and requires tests.
Note that before commiting, it has to be checked if in fact it works
flawlessly on all supported platforms, especially if it builds with
KicadOSXBuilder [3] and Kicad-Winbuilder [4].
Context menu
There could be a few options available in the context menu for single net items, like pads, vias & tracks (so there is no disambiguation which net should be affected by changes):
- Show ratsnest
- Hide ratsnest
- Show all
- Hide all
These options can be controlled by the RN_NET::SetVisible() function.
There could be an extra accessor in the RN_DATA class (e.g. void
RN_DATA::SetVisible( int aNet )), as the RN_DATA is publicly available
in the BOARD class.
References
[1] Boost Graph Library:
http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/index.html
[2] Boost Pool:
http://www.boost.org/doc/libs/1_54_0/libs/pool/doc/html/boost_pool/pool.html
[3] KicadOSXBuilder: https://github.com/mangelajo/KicadOSXBuilder
[4] Kicad-Winbuilder: https://launchpad.net/kicad-winbuilder