KiCad PCB EDA Suite
pns_topology.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2015 CERN
5  * Copyright (C) 2016-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software: you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
10  * Free Software Foundation, either version 3 of the License, or (at your
11  * option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #include "pns_line.h"
23 #include "pns_segment.h"
24 #include "pns_node.h"
25 #include "pns_joint.h"
26 #include "pns_solid.h"
27 #include "pns_router.h"
28 #include "pns_utils.h"
29 
30 #include "pns_diff_pair.h"
31 #include "pns_topology.h"
32 
33 #include <board.h>
34 #include <pad.h>
35 
36 namespace PNS {
37 
39 {
40  if( !aLine->IsLinked() || !aLine->SegmentCount() )
41  return false;
42 
43  LINKED_ITEM* root = aLine->GetLink( 0 );
44  LINE l = m_world->AssembleLine( root );
45  SHAPE_LINE_CHAIN simplified( l.CLine() );
46 
47  simplified.Simplify();
48 
49  if( simplified.PointCount() != l.PointCount() )
50  {
51  m_world->Remove( l );
52  LINE lnew( l );
53  lnew.SetShape( simplified );
54  m_world->Add( lnew );
55  return true;
56  }
57 
58  return false;
59 }
60 
61 
63 {
64  std::deque<JOINT*> searchQueue;
65  JOINT_SET processed;
66 
67  searchQueue.push_back( aStart );
68  processed.insert( aStart );
69 
70  while( !searchQueue.empty() )
71  {
72  JOINT* current = searchQueue.front();
73  searchQueue.pop_front();
74 
75  for( ITEM* item : current->LinkList() )
76  {
77  if( item->OfKind( ITEM::SEGMENT_T ) )
78  {
79  SEGMENT* seg = static_cast<SEGMENT*>( item );
80  JOINT* a = m_world->FindJoint( seg->Seg().A, seg );
81  JOINT* b = m_world->FindJoint( seg->Seg().B, seg );
82  JOINT* next = ( *a == *current ) ? b : a;
83 
84  if( processed.find( next ) == processed.end() )
85  {
86  processed.insert( next );
87  searchQueue.push_back( next );
88  }
89  }
90  }
91  }
92 
93  return processed;
94 }
95 
96 
97 bool TOPOLOGY::LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine )
98 {
99  LINE track( *aTrack );
100  VECTOR2I end;
101 
102  if( !track.PointCount() )
103  return false;
104 
105  std::unique_ptr<NODE> tmpNode( m_world->Branch() );
106  tmpNode->Add( track );
107 
108  JOINT* jt = tmpNode->FindJoint( track.CPoint( -1 ), &track );
109 
110  if( !jt || jt->Net() <= 0 )
111  return false;
112 
113  if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 )
114  || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
115  {
116  end = jt->Pos();
117  }
118  else
119  {
120  int anchor;
121 
122  TOPOLOGY topo( tmpNode.get() );
123  ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
124 
125  if( !it )
126  return false;
127 
128  end = it->Anchor( anchor );
129  }
130 
131  aRatLine.Clear();
132  aRatLine.Append( track.CPoint( -1 ) );
133  aRatLine.Append( end );
134  return true;
135 }
136 
137 
138 ITEM* TOPOLOGY::NearestUnconnectedItem( JOINT* aStart, int* aAnchor, int aKindMask )
139 {
140  std::set<ITEM*> disconnected;
141 
142  m_world->AllItemsInNet( aStart->Net(), disconnected );
143 
144  for( const JOINT* jt : ConnectedJoints( aStart ) )
145  {
146  for( ITEM* link : jt->LinkList() )
147  {
148  if( disconnected.find( link ) != disconnected.end() )
149  disconnected.erase( link );
150  }
151  }
152 
153  int best_dist = INT_MAX;
154  ITEM* best = nullptr;
155 
156  for( ITEM* item : disconnected )
157  {
158  if( item->OfKind( aKindMask ) )
159  {
160  for( int i = 0; i < item->AnchorCount(); i++ )
161  {
162  VECTOR2I p = item->Anchor( i );
163  int d = ( p - aStart->Pos() ).EuclideanNorm();
164 
165  if( d < best_dist )
166  {
167  best_dist = d;
168  best = item;
169 
170  if( aAnchor )
171  *aAnchor = i;
172  }
173  }
174  }
175  }
176 
177  return best;
178 }
179 
180 
181 bool TOPOLOGY::followTrivialPath( LINE* aLine, bool aLeft, ITEM_SET& aSet,
182  std::set<ITEM*>& aVisited, JOINT** aTerminalJoint )
183 {
184  assert( aLine->IsLinked() );
185 
186  VECTOR2I anchor = aLeft ? aLine->CPoint( 0 ) : aLine->CPoint( -1 );
187  LINKED_ITEM* last = aLeft ? aLine->Links().front() : aLine->Links().back();
188  JOINT* jt = m_world->FindJoint( anchor, aLine );
189 
190  assert( jt != nullptr );
191 
192  aVisited.insert( last );
193 
194  if( jt->IsNonFanoutVia() || jt->IsTraceWidthChange() )
195  {
196  ITEM* via = nullptr;
197  SEGMENT* next_seg = nullptr;
198 
199  for( ITEM* link : jt->Links().Items() )
200  {
201  if( link->OfKind( ITEM::VIA_T ) )
202  via = link;
203  else if( aVisited.find( link ) == aVisited.end() )
204  next_seg = static_cast<SEGMENT*>( link );
205  }
206 
207  if( !next_seg )
208  {
209  if( aTerminalJoint )
210  *aTerminalJoint = jt;
211 
212  return false;
213  }
214 
215  LINE l = m_world->AssembleLine( next_seg );
216 
217  VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
218 
219  if( nextAnchor != anchor )
220  {
221  l.Reverse();
222  }
223 
224  if( aLeft )
225  {
226  if( via )
227  aSet.Prepend( via );
228 
229  aSet.Prepend( l );
230  }
231  else
232  {
233  if( via )
234  aSet.Add( via );
235 
236  aSet.Add( l );
237  }
238 
239  return followTrivialPath( &l, aLeft, aSet, aVisited, aTerminalJoint );
240  }
241 
242  if( aTerminalJoint )
243  *aTerminalJoint = jt;
244 
245  return false;
246 }
247 
248 
250  std::pair<JOINT*, JOINT*>* aTerminalJoints )
251 {
252  ITEM_SET path;
253  std::set<ITEM*> visited;
254  LINKED_ITEM* seg = nullptr;
255 
256  if( aStart->Kind() == ITEM::VIA_T )
257  {
258  VIA* via = static_cast<VIA*>( aStart );
259  JOINT* jt = m_world->FindJoint( via->Pos(), via );
260 
261  if( !jt->IsNonFanoutVia() )
262  return ITEM_SET();
263 
264  for( const ITEM_SET::ENTRY& entry : jt->Links().Items() )
265  {
266  if( entry.item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
267  {
268  seg = static_cast<LINKED_ITEM*>( entry.item );
269  break;
270  }
271  }
272  }
273  else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
274  {
275  seg = static_cast<LINKED_ITEM*>( aStart );
276  }
277 
278  if( !seg )
279  return ITEM_SET();
280 
281  LINE l = m_world->AssembleLine( seg );
282 
283  path.Add( l );
284 
285  JOINT* jointA = nullptr;
286  JOINT* jointB = nullptr;
287 
288  followTrivialPath( &l, false, path, visited, &jointA );
289  followTrivialPath( &l, true, path, visited, &jointB );
290 
291  if( aTerminalJoints )
292  {
293  wxASSERT( jointA && jointB );
294  *aTerminalJoints = std::make_pair( jointA, jointB );
295  }
296 
297  return path;
298 }
299 
300 
301 const ITEM_SET TOPOLOGY::AssembleTuningPath( ITEM* aStart, SOLID** aStartPad, SOLID** aEndPad )
302 {
303  std::pair<JOINT*, JOINT*> joints;
304  ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints );
305 
306  PAD* padA = nullptr;
307  PAD* padB = nullptr;
308 
309  auto getPadFromJoint =
310  []( JOINT* aJoint, PAD** aTargetPad, SOLID** aTargetSolid )
311  {
312  for( ITEM* item : aJoint->LinkList() )
313  {
314  if( item->OfKind( ITEM::SOLID_T ) )
315  {
316  BOARD_ITEM* bi = static_cast<SOLID*>( item )->Parent();
317 
318  if( bi->Type() == PCB_PAD_T )
319  {
320  *aTargetPad = static_cast<PAD*>( bi );
321 
322  if( aTargetSolid )
323  *aTargetSolid = static_cast<SOLID*>( item );
324  }
325 
326  break;
327  }
328  }
329  };
330 
331  if( joints.first )
332  getPadFromJoint( joints.first, &padA, aStartPad );
333 
334  if( joints.second )
335  getPadFromJoint( joints.second, &padB, aEndPad );
336 
337  if( !padA && !padB )
338  return initialPath;
339 
340  auto clipLineToPad =
341  []( SHAPE_LINE_CHAIN& aLine, PAD* aPad, bool aForward = true )
342  {
343  const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
344 
345  int start = aForward ? 0 : aLine.PointCount() - 1;
346  int delta = aForward ? 1 : -1;
347 
348  // Skip the "first" (or last) vertex, we already know it's contained in the pad
349  int clip = start;
350 
351  for( int vertex = start + delta;
352  aForward ? vertex < aLine.PointCount() : vertex >= 0;
353  vertex += delta )
354  {
355  SEG seg( aLine.GetPoint( vertex ), aLine.GetPoint( vertex - delta ) );
356 
357  bool containsA = shape->Contains( seg.A );
358  bool containsB = shape->Contains( seg.B );
359 
360  if( containsA && containsB )
361  {
362  // Whole segment is inside: clip out this segment
363  clip = vertex;
364  }
365  else if( containsB &&
366  ( aForward ? vertex < aLine.PointCount() - 1 : vertex > 0 ) )
367  {
368  // Only one point inside: Find the intersection
369  VECTOR2I loc;
370 
371  if( shape->Collide( seg, 0, nullptr, &loc ) )
372  {
373  aLine.Replace( vertex - delta, vertex - delta, loc );
374  }
375  }
376  }
377 
378  if( !aForward && clip < start )
379  aLine.Remove( clip + 1, start );
380  else if( clip > start )
381  aLine.Remove( start, clip - 1 );
382 
383  // Now connect the dots
384  aLine.Insert( aForward ? 0 : aLine.PointCount(), aPad->GetPosition() );
385  };
386 
387  auto processPad =
388  [&]( JOINT* aJoint, PAD* aPad )
389  {
390  const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
391 
392  for( int idx = 0; idx < initialPath.Size(); idx++ )
393  {
394  if( initialPath[idx]->Kind() != ITEM::LINE_T )
395  continue;
396 
397  LINE* line = static_cast<LINE*>( initialPath[idx] );
398 
399  if( !aPad->FlashLayer( line->Layer() ) )
400  continue;
401 
402  const std::vector<VECTOR2I>& points = line->CLine().CPoints();
403 
404  if( points.front() != aJoint->Pos() && points.back() != aJoint->Pos() )
405  continue;
406 
407  SHAPE_LINE_CHAIN& slc = line->Line();
408 
409  if( shape->Contains( slc.CPoint( 0 ) ) )
410  clipLineToPad( slc, aPad, true );
411  else if( shape->Contains( slc.CPoint( -1 ) ) )
412  clipLineToPad( slc, aPad, false );
413  }
414  };
415 
416  if( padA )
417  processPad( joints.first, padA );
418 
419  if( padB )
420  processPad( joints.second, padB );
421 
422  return initialPath;
423 }
424 
425 
426 const ITEM_SET TOPOLOGY::ConnectedItems( JOINT* aStart, int aKindMask )
427 {
428  return ITEM_SET();
429 }
430 
431 
432 const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
433 {
434  return ITEM_SET();
435 }
436 
437 
438 bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
439 
440 
442 {
443  int refNet = aStart->Net();
444  int coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
445 
446  if( coupledNet < 0 )
447  return false;
448 
449  std::set<ITEM*> coupledItems;
450 
451  m_world->AllItemsInNet( coupledNet, coupledItems );
452 
453  SEGMENT* coupledSeg = nullptr, *refSeg;
454  int minDist = std::numeric_limits<int>::max();
455 
456  if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) != nullptr )
457  {
458  for( ITEM* item : coupledItems )
459  {
460  if( SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
461  {
462  if( s->Layers().Start() == refSeg->Layers().Start() &&
463  s->Width() == refSeg->Width() )
464  {
465  int dist = s->Seg().Distance( refSeg->Seg() );
466  bool isParallel = refSeg->Seg().ApproxParallel( s->Seg() );
467  SEG p_clip, n_clip;
468 
469  bool isCoupled = commonParallelProjection( refSeg->Seg(), s->Seg(), p_clip,
470  n_clip );
471 
472  if( isParallel && isCoupled && dist < minDist )
473  {
474  minDist = dist;
475  coupledSeg = s;
476  }
477  }
478  }
479  }
480  }
481  else
482  {
483  return false;
484  }
485 
486  if( !coupledSeg )
487  return false;
488 
489  LINE lp = m_world->AssembleLine( refSeg );
490  LINE ln = m_world->AssembleLine( coupledSeg );
491 
492  if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
493  {
494  std::swap( lp, ln );
495  }
496 
497  int gap = -1;
498 
499  if( refSeg->Seg().ApproxParallel( coupledSeg->Seg() ) )
500  {
501  // Segments are parallel -> compute pair gap
502  const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
503  const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->Anchor( 1 );
504  gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
505  }
506 
507  aPair = DIFF_PAIR( lp, ln );
508  aPair.SetWidth( lp.Width() );
509  aPair.SetLayers( lp.Layers() );
510  aPair.SetGap( gap );
511 
512  return true;
513 }
514 
515 const std::set<ITEM*> TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer )
516 {
517  std::set<ITEM*> visited;
518  std::deque<ITEM*> pending;
519 
520  pending.push_back( aStart );
521 
522  while( !pending.empty() )
523  {
524  NODE::OBSTACLES obstacles;
525  ITEM* top = pending.front();
526 
527  pending.pop_front();
528 
529  visited.insert( top );
530 
531  m_world->QueryColliding( top, obstacles, ITEM::ANY_T, -1, false );
532 
533  for( OBSTACLE& obs : obstacles )
534  {
535  if( visited.find( obs.m_item ) == visited.end() &&
536  obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
537  {
538  visited.insert( obs.m_item );
539  pending.push_back( obs.m_item );
540  }
541  }
542  }
543 
544  return visited;
545 }
546 
547 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
const JOINT_SET ConnectedJoints(JOINT *aStart)
CITER next(CITER it)
Definition: ptree.cpp:126
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:513
Base class for PNS router board items.
Definition: pns_item.h:55
const ITEM_SET AssembleTrivialPath(ITEM *aStart, std::pair< JOINT *, JOINT * > *aTerminalJoints=nullptr)
Assemble a trivial path between two joints given a starting item.
bool IsTraceWidthChange() const
Link the joint to a given board item (when it's added to the NODE).
Definition: pns_joint.h:126
virtual int Layer() const
Definition: pns_item.h:156
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:49
int SegmentCount() const
Definition: pns_line.h:139
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
const ITEM_SET ConnectedItems(JOINT *aStart, int aKindMask=ITEM::ANY_T)
void Prepend(const LINE &aLine)
Definition: pns_itemset.cpp:39
virtual int DpCoupledNet(int aNet)=0
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
ENTRIES & Items()
Definition: pns_itemset.h:135
class PAD, a pad in a footprint
Definition: typeinfo.h:89
const ITEM_SET AssembleTuningPath(ITEM *aStart, SOLID **aStartPad=nullptr, SOLID **aEndPad=nullptr)
Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fu...
int Size() const
Definition: pns_itemset.h:160
const SEG & Seg() const
Definition: pns_segment.h:84
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
int Net() const
Definition: pns_joint.h:190
int PointCount() const
Return the number of points (vertices) in this line chain.
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
int PointCount() const
Definition: pns_line.h:140
bool EndsWithVia() const
Definition: pns_line.h:191
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
ITEM * NearestUnconnectedItem(JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
void Insert(size_t aVertex, const VECTOR2I &aP)
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
ITEM_SET & Links()
Definition: pns_joint.h:205
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:42
void SetGap(int aGap)
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:1022
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, JOINT **aTerminalJoint=nullptr)
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
const std::vector< VECTOR2I > & CPoints() const
virtual VECTOR2I Anchor(int n) const override
Definition: pns_segment.h:107
int Net() const
Definition: pns_item.h:150
NODE * m_world
Definition: pns_topology.h:94
void SetWidth(int aWidth)
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:195
virtual const VECTOR2I GetPoint(int aIndex) const override
void SetLayers(const LAYER_RANGE &aLayers)
Definition: pns_item.h:153
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true)
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:266
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1140
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
bool SimplifyLine(LINE *aLine)
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:177
Definition: seg.h:40
Basic class for a differential pair.
Represent a polyline (an zero-thickness chain of connected line segments).
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1411
VECTOR2I A
Definition: seg.h:48
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:136
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:128
void Clear()
Remove all points from the line chain.
virtual int DpNetPolarity(int aNet)=0
constexpr int delta
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:210
const VECTOR2I & Pos() const
Definition: pns_joint.h:185
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
Definition: pad.h:57
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:149
Push and Shove diff pair dimensions (gap) settings dialog.
bool IsNonFanoutVia() const
Definition: pns_joint.h:112
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
const LAYER_RANGE & Layers() const
Definition: pns_item.h:152
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946
std::set< JOINT * > JOINT_SET
Definition: pns_topology.h:42
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:113
bool Contains(const SEG &aSeg) const
Definition: seg.h:331
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:102
VECTOR2I B
Definition: seg.h:49