All my series of “Learning to Develop KiCad” posts are listed in FAQ
Index:
- Use cases in regexp filter used during DDR4 routing
- Add a Dialog
- Add Netlist in the Dialog
- Add two levels data items
Following is a translation of my Chinese article
commit revision: 9db1dd5ec5f20d301af076301b8853b7a133eed5
Calling Traces
When activated Length Tuning Tool, via the calling to Go inside DRAWING_TOOL::setTransitions (pcbnew/tools/drawing_tool.cpp), bound to DRAWING_TOOL::PlaceTuningPattern, in which there is an event loop handler.
When a cursor hovers over a track, Length Tuning Tool shows the length of the whole track, the source code goes here ( still inside DRAWING_TOOL::PlaceTuningPattern):
if( evt->IsMotion ) {
// omitted code ...
updateHoverStatus();
} // omitted more code
Inside updateHoverStatus(), by calling PCB_TUNING_PATTERN::Update(), the code goes into
router->StartRouting()
it will go (for single traces) inside pcbnew/router/pns_meander_placer.cpp
MEANDER_PLACER::Start
Now, it goes into the core algorithm of length calculation.
Analysis of algorithm of length calculation
The core code is here in pcbnew/router/pns_meander_placer.cpp
TOPOLOGY topo( m_world );
m_tunedPath = topo.AssembleTuningPath( m_initialSegment, &m_startPad_n, &m_endPad_n );
Inheritance Relationships
In source code, by calling:
PNS::ITEM::Kind()
to determine the actual object type of current PNS::ITEM * pointer.
PNS::ITEM
Base class for PNS router board items.
Implements the shared properties of all PCB items net, spanned layers, geometric shape and reference to owning model.
PNS::NODE
pcbnew/router/pns_node.h
Keep the router “world” - i.e. all the tracks, vias, solids in a hierarchical and indexed way.
PNS::JOINT
A 2D point on a given set of layers and belonging to a certain net, that links together a number of board items. A hash table of joints is used by the router to follow connectivity between the items.
VIAs, PADs, junction of two segments all can be a JOINT. It defines multiple methods which can determine the type of this JOINT.
96 /**
97 * Checks if a joint connects two segments of the same net, layer, and width.
98 * @param aAllowLockedSegs will consider joints between locked and unlocked segments as trivial
99 * @return true if the joint is a trivial line corner
100 */
101 bool IsLineCorner( bool aAllowLockedSegs = false ) const;
150 bool IsNonFanoutVia() const;
172 bool IsStitchingVia() const;
177 bool IsTraceWidthChange() const;
PNS::LINE
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads, junctions between multiple traces or two traces different widths and combinations of these). PNS_LINEs are NOT stored in the model (NODE). Instead, they are assembled on-the-fly, based on a via/pad/segment that belongs to/starts/ends them.
A LINE may have a VIA attached at its end (i.e. the last point) - this is used by via dragging/force propagation stuff.
PNS::TOPOLOGY
TOPOLOGY is used to calculate topology properties of a NODE (world).
PNS::TOPOLOGY::AssembleTrivialPath
Assemble a trivial path between two joints given a starting item
Analysis
Sample PCB
Simplified content of the PCB file
(net 0 "")
(footprint "TestPoint:TestPoint_Pad_D4.0mm"
(at 113.34 54.19)
(pad "1" smd circle
(at 0 0)
(size 4 4)
(layers "F.Cu" "F.Mask")
(uuid "6baca6a6-e3ec-422e-8255-1ec74843a0d0")
)
)
(footprint "TestPoint:TestPoint_Pad_D4.0mm"
(layer "F.Cu")
(uuid "a1b08514-55a3-404d-8cf1-e425fa312934")
(at 129.07 54.21)
(pad "1" smd circle
(at 0 0)
(size 4 4)
(layers "F.Cu" "F.Mask")
(uuid "efe3ecd5-3fc1-4341-b837-57f85992cbfe")
)
)
(segment
(start 124.14 54.21)
(end 129.07 54.21)
(width 0.2)
(layer "F.Cu")
(net 0)
(uuid "14e13181-32a3-4a99-92ee-58914e592582")
)
(segment
(start 113.34 54.19)
(end 117.7 54.19)
(width 0.2)
(layer "F.Cu")
(net 0)
(uuid "7e88cb31-5757-4ba5-8a5f-ddf7daf03ebf")
)
(segment
(start 117.7 54.19)
(end 117.71 54.2)
(width 0.2)
(layer "F.Cu")
(net 0)
(uuid "98dd8262-83c0-425a-9f5d-b12bb95a1462")
)
(via
(at 117.71 54.2)
(size 0.6)
(drill 0.3)
(layers "F.Cu" "B.Cu")
(net 0)
(uuid "40af5aa0-cd97-40bd-94fe-1d4d088d00be")
)
(via
(at 124.14 54.21)
(size 0.6)
(drill 0.3)
(layers "F.Cu" "B.Cu")
(net 0)
(uuid "674e89f5-457e-46a1-86c6-b68c22d485b1")
)
(segment
(start 117.71 54.2)
(end 124.13 54.2)
(width 0.2)
(layer "B.Cu")
(net 0)
(uuid "4140aa44-32a2-49f1-a53c-69d33340e76c")
)
(segment
(start 124.13 54.2)
(end 124.14 54.21)
(width 0.2)
(layer "B.Cu")
(net 0)
(uuid "7df491dc-65ca-42dc-bb4c-245e1d145486")
)
The details of the file format see this doc.
Starting pcbnew by GDB, and set a breakpoint at TOPOLOGY::AssembleTuningPath
Then activated Length Tuning Tool, hover the cursor over the center track like this:
It will break at the breakpoint:
(gdb) list 332
327
328 return path;
329 }
330
331
332 const ITEM_SET TOPOLOGY::AssembleTuningPath( ITEM* aStart, SOLID** aStartPad, SOLID** aEndPad )
333 {
334 std::pair<const JOINT*, const JOINT*> joints;
335 ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints, true );
336
(gdb) p *aStart
$2 = {<PNS::OWNABLE_ITEM> = {m_owner = 0x5555579ff000}, <PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead8ef80 <vtable for PNS::SEGMENT+16>},
m_kind = PNS::ITEM::SEGMENT_T, m_parent = 0x555556932280, m_layers = {m_start = 31, m_end = 31}, m_movable = true, m_net = 0x55555694e980, m_marker = 0,
m_rank = -1, m_routable = true, m_isVirtual = false, m_isFreePad = false, m_isCompoundShapePrimitive = false}
(gdb) p *(SEGMENT *)aStart
$3 = {<PNS::LINKED_ITEM> = {<PNS::ITEM> = {<PNS::OWNABLE_ITEM> = {m_owner = 0x5555579ff000}, <PNS::ITEM_OWNER> = {
_vptr.ITEM_OWNER = 0x7fffead8ef80 <vtable for PNS::SEGMENT+16>}, m_kind = PNS::ITEM::SEGMENT_T, m_parent = 0x555556932280, m_layers = {m_start = 31,
m_end = 31}, m_movable = true, m_net = 0x55555694e980, m_marker = 0, m_rank = -1, m_routable = true, m_isVirtual = false, m_isFreePad = false,
m_isCompoundShapePrimitive = false}, <No data fields>}, m_seg = {<SHAPE> = {<SHAPE_BASE> = {
_vptr.SHAPE_BASE = 0x7fffeadec950 <vtable for SHAPE_SEGMENT+16>, m_type = SH_SEGMENT}, static MIN_PRECISION_IU = 4}, m_seg = {A = {x = 117710000,
y = 54200000}, B = {x = 124130000, y = 54200000}, m_index = -1}, m_width = 200000}}
According to the value of m_seg, we can match inside data in kicad pcb file
(segment
(start 117.71 54.2)
(end 124.13 54.2)
(width 0.2)
(layer "B.Cu")
(net 0)
(uuid "4140aa44-32a2-49f1-a53c-69d33340e76c")
)
Step over statement, goes into TOPOLOGY::AssembleTrivialPath
(gdb) list
275
276 const ITEM_SET TOPOLOGY::AssembleTrivialPath( ITEM* aStart,
277 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
278 bool aFollowLockedSegments )
279 {
280 ITEM_SET path;
281 LINKED_ITEM* seg = nullptr;
282
283 if( aStart->Kind() == ITEM::VIA_T )
284 {
(gdb) n
281 LINKED_ITEM* seg = nullptr;
(gdb)
283 if( aStart->Kind() == ITEM::VIA_T )
(gdb)
302 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
(gdb)
304 seg = static_cast<LINKED_ITEM*>( aStart );
(gdb)
307 if( !seg )
Now it is the simplest situation of Length Tuning Tool, which selected one segment.
Next, goes into NODE::AssembleLine
PNS::NODE::AssembleLine
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
It first definesMaxVerts, which limits the max vertex which the algorithm can handle.
int i_start = MaxVerts / 2;
int i_end = i_start + 1;
It shows, the algorithm constructs an array of a PNS::LINE, starts at the center of the array. The array defines left is from the i_start to 0, right is from i_end.
PNS::NODE::followLine
Scan the joint map, forming a line starting from segment (current)
(gdb) list
958
959 void NODE::followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
960 VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
961 bool& aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments )
962 {
963 bool prevReversed = false;
964
965 const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
966
967 for( int count = 0 ; ; ++count )
Here the algorithm starts at one point of the segment, scans from the center of the array, along with one direction.
Before we see PNS::SEGMENT has two points: A, B, here aCurrent is one PNS::SEGMENT, aCurrent->Anchor() calls implementation defines in pns_segment.h, ie, when aScanDirector == false, returns A, else returns B:
107 virtual VECTOR2I Anchor( int n ) const override 52 b.refs|1 ref
108 {
109 if( n == 0 )
110 return m_seg.GetSeg().A;
111 else
112 return m_seg.GetSeg().B;
113 }
Next is the actual algorithm of construction of the scan.
(gdb) l 974
967 for( int count = 0 ; ; ++count )
968 {
969 const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
970 const JOINT* jt = FindJoint( p, aCurrent );
971
972 wxCHECK( jt, /* void */ );
973
974 aCorners[aPos] = jt->Pos();
975 aSegments[aPos] = aCurrent;
976 aArcReversed[aPos] = false;
977
978 if( aCurrent->Kind() == ITEM::ARC_T )
979 {
980 if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) )
981 || ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
NODE::JOINT
1206 const JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, NET_HANDLE aNet ) const
1207 {
1208 JOINT::HASH_TAG tag;
1209
1210 tag.net = aNet;
1211 tag.pos = aPos;
1212
1213 JOINT_MAP::const_iterator f = m_joints.find( tag ), end = m_joints.end();
1214
1215 if( f == end && !isRoot() )
1216 {
1217 end = m_root->m_joints.end();
1218 f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1219 }
1220
1221 if( f == end )
1222 return nullptr;
1223
1224 while( f != end )
1225 {
1226 if( f->second.Layers().Overlaps( aLayer ) )
1227 return &f->second;
1228
1229 ++f;
1230 }
1231
1232 return nullptr;
1233 }
I didn’t research how m_joints constructed.
When executed at line number 1221, the result of f is:
(gdb) p f->first
$21 = {pos = {x = 117710000, y = 54200000}, net = 0x55555694e980}
(gdb) p (JOINT)f->second
$50 = {<PNS::ITEM> = {<PNS::OWNABLE_ITEM> = {m_owner = 0x0}, <PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead8f258 <vtable for PNS::JOINT+16>},
m_kind = PNS::ITEM::JOINT_T, m_parent = 0x0, m_layers = {m_start = 0, m_end = 31}, m_movable = true, m_net = 0x0, m_marker = 0, m_rank = -1,
m_routable = true, m_isVirtual = false, m_isFreePad = false, m_isCompoundShapePrimitive = false}, m_tag = {pos = {x = 117710000, y = 54200000},
net = 0x55555694e980}, m_linkedItems = {<PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead8eef0 <vtable for PNS::ITEM_SET+16>},
m_items = std::vector of length 3, capacity 4 = {0x55555f2502d0, 0x555555c55900, 0x55555f1ee550}}, m_locked = false}
(gdb) p *(((JOINT)f->second).m_linkedItems.m_items[0])
$42 = {<PNS::OWNABLE_ITEM> = {m_owner = 0x5555579ff000}, <PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead8ef80 <vtable for PNS::SEGMENT+16>},
m_kind = PNS::ITEM::SEGMENT_T, m_parent = 0x55555f1c7de0, m_layers = {m_start = 0, m_end = 0}, m_movable = true, m_net = 0x55555694e980, m_marker = 0,
m_rank = -1, m_routable = true, m_isVirtual = false, m_isFreePad = false, m_isCompoundShapePrimitive = false}
(gdb) p *(((JOINT)f->second).m_linkedItems.m_items[1])
$43 = {<PNS::OWNABLE_ITEM> = {m_owner = 0x5555579ff000}, <PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead90258 <vtable for PNS::VIA+16>},
m_kind = PNS::ITEM::VIA_T, m_parent = 0x55555f085f50, m_layers = {m_start = 0, m_end = 31}, m_movable = true, m_net = 0x55555694e980, m_marker = 0,
m_rank = -1, m_routable = true, m_isVirtual = false, m_isFreePad = false, m_isCompoundShapePrimitive = false}
(gdb) p *(((JOINT)f->second).m_linkedItems.m_items[2])
$44 = {<PNS::OWNABLE_ITEM> = {m_owner = 0x5555579ff000}, <PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead8ef80 <vtable for PNS::SEGMENT+16>},
m_kind = PNS::ITEM::SEGMENT_T, m_parent = 0x555556932280, m_layers = {m_start = 31, m_end = 31}, m_movable = true, m_net = 0x55555694e980, m_marker = 0,
m_rank = -1, m_routable = true, m_isVirtual = false, m_isFreePad = false, m_isCompoundShapePrimitive = false}
Print again after type conversion:
(gdb) p *(((JOINT)f->second).m_linkedItems.m_items[0])
$42 = {<PNS::OWNABLE_ITEM> = {m_owner = 0x5555579ff000}, <PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead8ef80 <vtable for PNS::SEGMENT+16>},
m_kind = PNS::ITEM::SEGMENT_T, m_parent = 0x55555f1c7de0, m_layers = {m_start = 0, m_end = 0}, m_movable = true, m_net = 0x55555694e980, m_marker = 0,
m_rank = -1, m_routable = true, m_isVirtual = false, m_isFreePad = false, m_isCompoundShapePrimitive = false}
(gdb) p *(((JOINT)f->second).m_linkedItems.m_items[1])
$43 = {<PNS::OWNABLE_ITEM> = {m_owner = 0x5555579ff000}, <PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead90258 <vtable for PNS::VIA+16>},
m_kind = PNS::ITEM::VIA_T, m_parent = 0x55555f085f50, m_layers = {m_start = 0, m_end = 31}, m_movable = true, m_net = 0x55555694e980, m_marker = 0,
m_rank = -1, m_routable = true, m_isVirtual = false, m_isFreePad = false, m_isCompoundShapePrimitive = false}
(gdb) p *(((JOINT)f->second).m_linkedItems.m_items[2])
$44 = {<PNS::OWNABLE_ITEM> = {m_owner = 0x5555579ff000}, <PNS::ITEM_OWNER> = {_vptr.ITEM_OWNER = 0x7fffead8ef80 <vtable for PNS::SEGMENT+16>},
m_kind = PNS::ITEM::SEGMENT_T, m_parent = 0x555556932280, m_layers = {m_start = 31, m_end = 31}, m_movable = true, m_net = 0x55555694e980, m_marker = 0,
m_rank = -1, m_routable = true, m_isVirtual = false, m_isFreePad = false, m_isCompoundShapePrimitive = false}
Now we match kicad pcb file, the three items are:
(segment
(start 117.7 54.19)
(end 117.71 54.2)
(width 0.2)
(layer "F.Cu")
(net 0)
(uuid "98dd8262-83c0-425a-9f5d-b12bb95a1462")
)
(via
(at 117.71 54.2)
(size 0.6)
(drill 0.3)
(layers "F.Cu" "B.Cu")
(net 0)
(uuid "40af5aa0-cd97-40bd-94fe-1d4d088d00be")
)
(segment
(start 117.71 54.2)
(end 124.13 54.2)
(width 0.2)
(layer "B.Cu")
(net 0)
(uuid "4140aa44-32a2-49f1-a53c-69d33340e76c")
)
Matching to PCB here
Save current JOINT information, and advanced one position ( forward +1, backward -1 ):
974 aCorners[aPos] = jt->Pos();
975 aSegments[aPos] = aCurrent;
976 aArcReversed[aPos] = false;
985 aPos += ( aScanDirection ? 1 : -1 );
998 if( locked || !jt->IsLineCorner( aFollowLockedSegments ) || aPos < 0 || aPos == aLimit )
999 break;
Here it checks jt is not LineCorner, then break ( because PNS::LINE is a line which connected two ‘non trivial’ line).
And here because IsLineCorener, the algorithm stops constructing more lines when more than two traces conntected to one JOINT
1028 followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1029 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1030
1031 if( !guardHit )
1032 {
1033 followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1034 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1035 }
Because guardHit is not set to true, now execute second followLine to find the other end (JOINT) of the LINE.
In the end, these ITEMs are selected
After two executions of followLine, then the algorithm will construct the final LINE (variable named pl) by returned corners and segments.
1044 for( int i = i_start + 1; i < i_end; i++ ) 5 refs
1045 {
1046 const VECTOR2I& p = corners[i]; 1 ref
1047 LINKED_ITEM* li = segs[i]; 11 refs
1048
1049 if( !li || li->Kind() != ITEM::ARC_T )
1050 line.Append( p );
1051
1052 if( li && prev_seg != li )
The code later also process special cases of ARCs.
Notice, the i starts from i_start + 1, so it will skip first position, so when there is a third segments connected to one JOINT which causes algorithm ( construction ) stops, the LINE in the right side will not include this VIA ( or JOINT ).
back to pcbnew/router/pns_topology.cpp
312 LINE l = m_world->AssembleLine( seg, nullptr, false, aFollowLockedSegments );
314 path.Add( l );
The path ( which is returned as m_tunedPath ) will append the first LINE.
Then from this LINE l, the algorithm continues to construct to left and right ( the LEFT and RIGHT is logical, not in the drawing ):
319 followTrivialPath( &l, false, path, &jointB, aFollowLockedSegments );
320 followTrivialPath( &l, true, path, &jointA, aFollowLockedSegments );
PNS::TOPOLOGY::followTrivialPath
This logic is similar to followLine, it executes multiple times of NODE::AssembleLine.
The condition check:
216 if( !visited.insert( last ).second
217 || ( !jt->IsNonFanoutVia() && !jt->IsTraceWidthChange() ) )
218 {
219 if( aTerminalJoint )
220 *aTerminalJoint = jt;
221
222 return false;
223 }
When a JOINT is NonFanoutVia, which is a VIA connected by two trivial SEGMENTs, the alglrithm stops construction.
Next is calculation of the length
PNS::MEANDER_PLACER::origPathLength
94 long long int MEANDER_PLACER::origPathLength() const 2 refs|2 derived
95 {
96 return m_padToDieLength + lineLength( m_tunedPath, m_startPad_n, m_endPad_n );
97 }
PNS::MEANDER_PLACER_BASE::lineLength
335 /**
336 * If there is a start pad but the pad's layers do not overlap the first track layer, then there must be a
337 * fanout via on the line. If there isn't, we still need to have the via back to the pad, so count the distance
338 * in the line tuning
339 */
340 start_via = aStartPad && ( !aStartPad->LayersOverlap( start_item ) );
341 end_via = aEndPad && ( !aEndPad->LayersOverlap( end_item ) );
Here, start_via is set only when aStartPad and start_item is not in same layer; end_via is set only when aEndPad and end_item is not in same layer. and the stackup height is added according to start_via and end_via is set or not.
At last, it is the calculation of sum up all LINEs
343 for( int idx = 0; idx < aLine.Size(); idx++ ) 7 refs
344 {
345 const ITEM* item = aLine[idx]; 2 refs
346
347 if( const LINE* l = dyn_cast<const LINE*>( item ) ) 2 refs
348 {
349 total += l->CLine().Length();
350 }
351 else if( item->OfKind( ITEM::VIA_T ) && idx > 0 && idx < aLine.Size() - 1 )
352 {
353 int layerPrev = aLine[idx - 1]->Layer(); 2 refs
354 int layerNext = aLine[idx + 1]->Layer(); 2 refs
355
356 if( layerPrev != layerNext )
357 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
358 }
359 }
Notice here, it will add a height between two layers when it finds a VIA.