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 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 
35 namespace PNS {
36 
38 {
39  if( !aLine->IsLinked() || !aLine->SegmentCount() )
40  return false;
41 
42  LINKED_ITEM* root = aLine->GetLink( 0 );
43  LINE l = m_world->AssembleLine( root );
44  SHAPE_LINE_CHAIN simplified( l.CLine() );
45 
46  simplified.Simplify();
47 
48  if( simplified.PointCount() != l.PointCount() )
49  {
50  m_world->Remove( l );
51  LINE lnew( l );
52  lnew.SetShape( simplified );
53  m_world->Add( lnew );
54  return true;
55  }
56 
57  return false;
58 }
59 
60 
62 {
63  std::deque<JOINT*> searchQueue;
64  JOINT_SET processed;
65 
66  searchQueue.push_back( aStart );
67  processed.insert( aStart );
68 
69  while( !searchQueue.empty() )
70  {
71  JOINT* current = searchQueue.front();
72  searchQueue.pop_front();
73 
74  for( ITEM* item : current->LinkList() )
75  {
76  if( item->OfKind( ITEM::SEGMENT_T ) )
77  {
78  SEGMENT* seg = static_cast<SEGMENT*>( item );
79  JOINT* a = m_world->FindJoint( seg->Seg().A, seg );
80  JOINT* b = m_world->FindJoint( seg->Seg().B, seg );
81  JOINT* next = ( *a == *current ) ? b : a;
82 
83  if( processed.find( next ) == processed.end() )
84  {
85  processed.insert( next );
86  searchQueue.push_back( next );
87  }
88  }
89  }
90  }
91 
92  return processed;
93 }
94 
95 
96 bool TOPOLOGY::LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine )
97 {
98  LINE track( *aTrack );
99  VECTOR2I end;
100 
101  if( !track.PointCount() )
102  return false;
103 
104  std::unique_ptr<NODE> tmpNode( m_world->Branch() );
105  tmpNode->Add( track );
106 
107  JOINT* jt = tmpNode->FindJoint( track.CPoint( -1 ), &track );
108 
109  if( !jt || jt->Net() <= 0 )
110  return false;
111 
112  if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 )
113  || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
114  {
115  end = jt->Pos();
116  }
117  else
118  {
119  int anchor;
120 
121  TOPOLOGY topo( tmpNode.get() );
122  ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
123 
124  if( !it )
125  return false;
126 
127  end = it->Anchor( anchor );
128  }
129 
130  aRatLine.Clear();
131  aRatLine.Append( track.CPoint( -1 ) );
132  aRatLine.Append( end );
133  return true;
134 }
135 
136 
137 ITEM* TOPOLOGY::NearestUnconnectedItem( JOINT* aStart, int* aAnchor, int aKindMask )
138 {
139  std::set<ITEM*> disconnected;
140 
141  m_world->AllItemsInNet( aStart->Net(), disconnected );
142 
143  for( const JOINT* jt : ConnectedJoints( aStart ) )
144  {
145  for( ITEM* link : jt->LinkList() )
146  {
147  if( disconnected.find( link ) != disconnected.end() )
148  disconnected.erase( link );
149  }
150  }
151 
152  int best_dist = INT_MAX;
153  ITEM* best = NULL;
154 
155  for( ITEM* item : disconnected )
156  {
157  if( item->OfKind( aKindMask ) )
158  {
159  for( int i = 0; i < item->AnchorCount(); i++ )
160  {
161  VECTOR2I p = item->Anchor( i );
162  int d = ( p - aStart->Pos() ).EuclideanNorm();
163 
164  if( d < best_dist )
165  {
166  best_dist = d;
167  best = item;
168 
169  if( aAnchor )
170  *aAnchor = i;
171  }
172  }
173  }
174  }
175 
176  return best;
177 }
178 
179 
180 bool TOPOLOGY::followTrivialPath( LINE* aLine, bool aLeft, ITEM_SET& aSet,
181  std::set<ITEM*>& aVisited, JOINT** aTerminalJoint )
182 {
183  assert( aLine->IsLinked() );
184 
185  VECTOR2I anchor = aLeft ? aLine->CPoint( 0 ) : aLine->CPoint( -1 );
186  LINKED_ITEM* last = aLeft ? aLine->Links().front() : aLine->Links().back();
187  JOINT* jt = m_world->FindJoint( anchor, aLine );
188 
189  assert( jt != NULL );
190 
191  aVisited.insert( last );
192 
193  if( jt->IsNonFanoutVia() || jt->IsTraceWidthChange() )
194  {
195  ITEM* via = NULL;
196  SEGMENT* next_seg = NULL;
197 
198  for( ITEM* link : jt->Links().Items() )
199  {
200  if( link->OfKind( ITEM::VIA_T ) )
201  via = link;
202  else if( aVisited.find( link ) == aVisited.end() )
203  next_seg = static_cast<SEGMENT*>( link );
204  }
205 
206  if( !next_seg )
207  {
208  if( aTerminalJoint )
209  *aTerminalJoint = jt;
210 
211  return false;
212  }
213 
214  LINE l = m_world->AssembleLine( next_seg );
215 
216  VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
217 
218  if( nextAnchor != anchor )
219  {
220  l.Reverse();
221  }
222 
223  if( aLeft )
224  {
225  if( via )
226  aSet.Prepend( via );
227 
228  aSet.Prepend( l );
229  }
230  else
231  {
232  if( via )
233  aSet.Add( via );
234 
235  aSet.Add( l );
236  }
237 
238  return followTrivialPath( &l, aLeft, aSet, aVisited, aTerminalJoint );
239  }
240 
241  if( aTerminalJoint )
242  *aTerminalJoint = jt;
243 
244  return false;
245 }
246 
247 
249  std::pair<JOINT*, JOINT*>* aTerminalJoints )
250 {
251  ITEM_SET path;
252  std::set<ITEM*> visited;
253  LINKED_ITEM* seg = nullptr;
254 
255  if( aStart->Kind() == ITEM::VIA_T )
256  {
257  VIA* via = static_cast<VIA*>( aStart );
258  JOINT* jt = m_world->FindJoint( via->Pos(), via );
259 
260  if( !jt->IsNonFanoutVia() )
261  return ITEM_SET();
262 
263  for( const ITEM_SET::ENTRY& entry : jt->Links().Items() )
264  {
265  if( entry.item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
266  {
267  seg = static_cast<LINKED_ITEM*>( entry.item );
268  break;
269  }
270  }
271  }
272  else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
273  {
274  seg = static_cast<LINKED_ITEM*>( aStart );
275  }
276 
277  if( !seg )
278  return ITEM_SET();
279 
280  LINE l = m_world->AssembleLine( seg );
281 
282  path.Add( l );
283 
284  JOINT* jointA = nullptr;
285  JOINT* jointB = nullptr;
286 
287  followTrivialPath( &l, false, path, visited, &jointA );
288  followTrivialPath( &l, true, path, visited, &jointB );
289 
290  if( aTerminalJoints )
291  {
292  wxASSERT( jointA && jointB );
293  *aTerminalJoints = std::make_pair( jointA, jointB );
294  }
295 
296  return path;
297 }
298 
299 
300 const ITEM_SET TOPOLOGY::AssembleTuningPath( ITEM* aStart, SOLID** aStartPad, SOLID** aEndPad )
301 {
302  std::pair<JOINT*, JOINT*> joints;
303  ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints );
304 
305  PAD* padA = nullptr;
306  PAD* padB = nullptr;
307 
308  auto getPadFromJoint =
309  []( JOINT* aJoint, PAD** aTargetPad, SOLID** aTargetSolid )
310  {
311  for( ITEM* item : aJoint->LinkList() )
312  {
313  if( item->OfKind( ITEM::SOLID_T ) )
314  {
315  BOARD_ITEM* bi = static_cast<SOLID*>( item )->Parent();
316 
317  if( bi->Type() == PCB_PAD_T )
318  {
319  *aTargetPad = static_cast<PAD*>( bi );
320 
321  if( aTargetSolid )
322  *aTargetSolid = static_cast<SOLID*>( item );
323  }
324 
325  break;
326  }
327  }
328  };
329 
330  if( joints.first )
331  getPadFromJoint( joints.first, &padA, aStartPad );
332 
333  if( joints.second )
334  getPadFromJoint( joints.second, &padB, aEndPad );
335 
336  if( !padA && !padB )
337  return initialPath;
338 
339  auto clipLineToPad =
340  []( SHAPE_LINE_CHAIN& aLine, PAD* aPad, bool aForward = true )
341  {
342  const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
343 
344  int start = aForward ? 0 : aLine.PointCount() - 1;
345  int delta = aForward ? 1 : -1;
346 
347  // Skip the "first" (or last) vertex, we already know it's contained in the pad
348  int clip = start;
349 
350  for( int vertex = start + delta;
351  aForward ? vertex < aLine.PointCount() : vertex >= 0;
352  vertex += delta )
353  {
354  SEG seg( aLine.GetPoint( vertex ), aLine.GetPoint( vertex - delta ) );
355 
356  bool containsA = shape->Contains( seg.A );
357  bool containsB = shape->Contains( seg.B );
358 
359  if( containsA && containsB )
360  {
361  // Whole segment is inside: clip out this segment
362  clip = vertex;
363  }
364  else if( containsB &&
365  ( aForward ? vertex < aLine.PointCount() - 1 : vertex > 0 ) )
366  {
367  // Only one point inside: Find the intersection
368  VECTOR2I loc;
369 
370  if( shape->Collide( seg, 0, nullptr, &loc ) )
371  {
372  aLine.Replace( vertex - delta, vertex - delta, loc );
373  }
374  }
375  }
376 
377  if( !aForward && clip < start )
378  aLine.Remove( clip + 1, start );
379  else if( clip > start )
380  aLine.Remove( start, clip - 1 );
381 
382  // Now connect the dots
383  aLine.Insert( aForward ? 0 : aLine.PointCount(), aPad->GetPosition() );
384  };
385 
386  auto processPad =
387  [&]( PAD* aPad )
388  {
389  const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
390 
391  for( int idx = 0; idx < initialPath.Size(); idx++ )
392  {
393  if( initialPath[idx]->Kind() != ITEM::LINE_T )
394  continue;
395 
396  LINE* line = static_cast<LINE*>( initialPath[idx] );
397 
398  SHAPE_LINE_CHAIN& slc = line->Line();
399 
400  if( shape->Contains( slc.CPoint( 0 ) ) )
401  clipLineToPad( slc, aPad, true );
402  else if( shape->Contains( slc.CPoint( -1 ) ) )
403  clipLineToPad( slc, aPad, false );
404  }
405  };
406 
407  if( padA )
408  processPad( padA );
409 
410  if( padB )
411  processPad( padB );
412 
413  return initialPath;
414 }
415 
416 
417 const ITEM_SET TOPOLOGY::ConnectedItems( JOINT* aStart, int aKindMask )
418 {
419  return ITEM_SET();
420 }
421 
422 
423 const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
424 {
425  return ITEM_SET();
426 }
427 
428 
429 bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
430 
431 
433 {
434  int refNet = aStart->Net();
435  int coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
436 
437  if( coupledNet < 0 )
438  return false;
439 
440  std::set<ITEM*> coupledItems;
441 
442  m_world->AllItemsInNet( coupledNet, coupledItems );
443 
444  SEGMENT* coupledSeg = NULL, *refSeg;
445  int minDist = std::numeric_limits<int>::max();
446 
447  if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) != NULL )
448  {
449  for( ITEM* item : coupledItems )
450  {
451  if( SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
452  {
453  if( s->Layers().Start() == refSeg->Layers().Start() && s->Width() == refSeg->Width() )
454  {
455  int dist = s->Seg().Distance( refSeg->Seg() );
456  bool isParallel = refSeg->Seg().ApproxParallel( s->Seg() );
457  SEG p_clip, n_clip;
458 
459  bool isCoupled = commonParallelProjection( refSeg->Seg(), s->Seg(), p_clip, n_clip );
460 
461  if( isParallel && isCoupled && dist < minDist )
462  {
463  minDist = dist;
464  coupledSeg = s;
465  }
466  }
467  }
468  }
469  }
470  else
471  {
472  return false;
473  }
474 
475  if( !coupledSeg )
476  return false;
477 
478  LINE lp = m_world->AssembleLine( refSeg );
479  LINE ln = m_world->AssembleLine( coupledSeg );
480 
481  if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
482  {
483  std::swap( lp, ln );
484  }
485 
486  int gap = -1;
487 
488  if( refSeg->Seg().ApproxParallel( coupledSeg->Seg() ) )
489  {
490  // Segments are parallel -> compute pair gap
491  const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
492  const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->Anchor( 1 );
493  gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
494  }
495 
496  aPair = DIFF_PAIR( lp, ln );
497  aPair.SetWidth( lp.Width() );
498  aPair.SetLayers( lp.Layers() );
499  aPair.SetGap( gap );
500 
501  return true;
502 }
503 
504 const std::set<ITEM*> TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer )
505 {
506  std::set<ITEM*> visited;
507  std::deque<ITEM*> pending;
508 
509  pending.push_back( aStart );
510 
511  while( !pending.empty() )
512  {
513  NODE::OBSTACLES obstacles;
514  ITEM* top = pending.front();
515 
516  pending.pop_front();
517 
518  visited.insert( top );
519 
520  m_world->QueryColliding( top, obstacles, ITEM::ANY_T, -1, false );
521 
522  for( OBSTACLE& obs : obstacles )
523  {
524  if( visited.find( obs.m_item ) == visited.end() && obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
525  {
526  visited.insert( obs.m_item );
527  pending.push_back( obs.m_item );
528  }
529  }
530  }
531 
532  return visited;
533 }
534 
535 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
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)
Assembles 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
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:82
int SegmentCount() const
Definition: pns_line.h:139
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
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:138
ITEM * NearestUnconnectedItem(JOINT *aStart, int *aAnchor=NULL, int aKindMask=ITEM::ANY_T)
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:163
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
Function PointCount()
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:124
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)
Function Append()
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:797
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
Function Point()
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
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:907
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:907
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, JOINT **aTerminalJoint=nullptr)
#define NULL
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
virtual VECTOR2I Anchor(int n) const override
Definition: pns_segment.h:107
int Net() const
Definition: pns_item.h:148
NODE * m_world
Definition: pns_topology.h:92
void SetWidth(int aWidth)
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
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:151
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:252
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:1041
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:41
DIFF_PAIR.
SHAPE_LINE_CHAIN.
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:1312
VECTOR2I A
Definition: seg.h:49
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:134
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:126
void Clear()
Function Clear() Removes all points from the line chain.
virtual int DpNetPolarity(int aNet)=0
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)
Function Replace()
Definition: pad.h:60
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:608
const LAYER_RANGE & Layers() const
Definition: pns_item.h:150
std::set< JOINT * > JOINT_SET
Definition: pns_topology.h:42
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:163
bool Contains(const SEG &aSeg) const
Definition: seg.h:336
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:50