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 <class_board.h>
34 
35 namespace PNS {
36 
38 {
39  if( !aLine->IsLinked() || !aLine->SegmentCount() )
40  return false;
41 
42  SEGMENT* 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 )
110  return false;
111 
112  if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 ) || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
113  {
114  end = jt->Pos();
115  }
116  else
117  {
118  int anchor;
119 
120  TOPOLOGY topo( tmpNode.get() );
121  ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
122 
123  if( !it )
124  return false;
125 
126  end = it->Anchor( anchor );
127  }
128 
129  aRatLine.Clear();
130  aRatLine.Append( track.CPoint( -1 ) );
131  aRatLine.Append( end );
132  return true;
133 }
134 
135 
136 ITEM* TOPOLOGY::NearestUnconnectedItem( JOINT* aStart, int* aAnchor, int aKindMask )
137 {
138  std::set<ITEM*> disconnected;
139 
140  m_world->AllItemsInNet( aStart->Net(), disconnected );
141 
142  for( const JOINT* jt : ConnectedJoints( aStart ) )
143  {
144  for( ITEM* link : jt->LinkList() )
145  {
146  if( disconnected.find( link ) != disconnected.end() )
147  disconnected.erase( link );
148  }
149  }
150 
151  int best_dist = INT_MAX;
152  ITEM* best = NULL;
153 
154  for( ITEM* item : disconnected )
155  {
156  if( item->OfKind( aKindMask ) )
157  {
158  for( int i = 0; i < item->AnchorCount(); i++ )
159  {
160  VECTOR2I p = item->Anchor( i );
161  int d = ( p - aStart->Pos() ).EuclideanNorm();
162 
163  if( d < best_dist )
164  {
165  best_dist = d;
166  best = item;
167 
168  if( aAnchor )
169  *aAnchor = i;
170  }
171  }
172  }
173  }
174 
175  return best;
176 }
177 
178 
179 bool TOPOLOGY::followTrivialPath( LINE* aLine, bool aLeft, ITEM_SET& aSet, std::set<ITEM*>& aVisited )
180 {
181  assert( aLine->IsLinked() );
182 
183  VECTOR2I anchor = aLeft ? aLine->CPoint( 0 ) : aLine->CPoint( -1 );
184  SEGMENT* last = aLeft ? aLine->LinkedSegments().front() : aLine->LinkedSegments().back();
185  JOINT* jt = m_world->FindJoint( anchor, aLine );
186 
187  assert( jt != NULL );
188 
189  aVisited.insert( last );
190 
191  if( jt->IsNonFanoutVia() || jt->IsTraceWidthChange() )
192  {
193  ITEM* via = NULL;
194  SEGMENT* next_seg = NULL;
195 
196  for( ITEM* link : jt->Links().Items() )
197  {
198  if( link->OfKind( ITEM::VIA_T ) )
199  via = link;
200  else if( aVisited.find( link ) == aVisited.end() )
201  next_seg = static_cast<SEGMENT*>( link );
202  }
203 
204  if( !next_seg )
205  return false;
206 
207  LINE l = m_world->AssembleLine( next_seg );
208 
209  VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
210 
211  if( nextAnchor != anchor )
212  {
213  l.Reverse();
214  }
215 
216  if( aLeft )
217  {
218  if( via )
219  aSet.Prepend( via );
220 
221  aSet.Prepend( l );
222  }
223  else
224  {
225  if( via )
226  aSet.Add( via );
227 
228  aSet.Add( l );
229  }
230 
231  return followTrivialPath( &l, aLeft, aSet, aVisited );
232  }
233 
234  return false;
235 }
236 
237 
239 {
240  ITEM_SET path;
241  std::set<ITEM*> visited;
242  SEGMENT* seg;
243  VIA* via;
244 
245  seg = dyn_cast<SEGMENT*> (aStart);
246 
247  if(!seg && (via = dyn_cast<VIA*>( aStart ) ) )
248  {
249  JOINT *jt = m_world->FindJoint( via->Pos(), via );
250 
251  if( !jt->IsNonFanoutVia() )
252  return ITEM_SET();
253 
254  for( auto entry : jt->Links().Items() )
255  if( ( seg = dyn_cast<SEGMENT*>( entry.item ) ) )
256  break;
257  }
258 
259  if( !seg )
260  return ITEM_SET();
261 
262  LINE l = m_world->AssembleLine( seg );
263 
264  path.Add( l );
265 
266  followTrivialPath( &l, false, path, visited );
267  followTrivialPath( &l, true, path, visited );
268 
269  return path;
270 }
271 
272 
273 const ITEM_SET TOPOLOGY::ConnectedItems( JOINT* aStart, int aKindMask )
274 {
275  return ITEM_SET();
276 }
277 
278 
279 const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
280 {
281  return ITEM_SET();
282 }
283 
284 
285 bool commonParallelProjection( SEG n, SEG p, SEG &pClip, SEG& nClip );
286 
287 
289 {
290  int refNet = aStart->Net();
291  int coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
292 
293  if( coupledNet < 0 )
294  return false;
295 
296  std::set<ITEM*> coupledItems;
297 
298  m_world->AllItemsInNet( coupledNet, coupledItems );
299 
300  SEGMENT* coupledSeg = NULL, *refSeg;
301  int minDist = std::numeric_limits<int>::max();
302 
303  if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) != NULL )
304  {
305  for( ITEM* item : coupledItems )
306  {
307  if( SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
308  {
309  if( s->Layers().Start() == refSeg->Layers().Start() && s->Width() == refSeg->Width() )
310  {
311  int dist = s->Seg().Distance( refSeg->Seg() );
312  bool isParallel = refSeg->Seg().ApproxParallel( s->Seg() );
313  SEG p_clip, n_clip;
314 
315  bool isCoupled = commonParallelProjection( refSeg->Seg(), s->Seg(), p_clip, n_clip );
316 
317  if( isParallel && isCoupled && dist < minDist )
318  {
319  minDist = dist;
320  coupledSeg = s;
321  }
322  }
323  }
324  }
325  }
326  else
327  {
328  return false;
329  }
330 
331  if( !coupledSeg )
332  return false;
333 
334  LINE lp = m_world->AssembleLine( refSeg );
335  LINE ln = m_world->AssembleLine( coupledSeg );
336 
337  if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
338  {
339  std::swap( lp, ln );
340  }
341 
342  int gap = -1;
343 
344  if( refSeg->Seg().ApproxParallel( coupledSeg->Seg() ) )
345  {
346  // Segments are parallel -> compute pair gap
347  const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
348  const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->Anchor( 1 );
349  gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
350  }
351 
352  aPair = DIFF_PAIR( lp, ln );
353  aPair.SetWidth( lp.Width() );
354  aPair.SetLayers( lp.Layers() );
355  aPair.SetGap( gap );
356 
357  return true;
358 }
359 
360 const std::set<ITEM*> TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer )
361 {
362  std::set<ITEM*> visited;
363  std::deque<ITEM*> pending;
364 
365  pending.push_back( aStart );
366 
367  while( !pending.empty() )
368  {
369  NODE::OBSTACLES obstacles;
370  ITEM* top = pending.front();
371 
372  pending.pop_front();
373 
374  visited.insert( top );
375 
376  m_world->QueryColliding( top, obstacles, ITEM::ANY_T, -1, false );
377 
378  for( OBSTACLE& obs : obstacles )
379  {
380  if( visited.find( obs.m_item ) == visited.end() && obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
381  {
382  visited.insert( obs.m_item );
383  pending.push_back( obs.m_item );
384  }
385  }
386  }
387 
388  return visited;
389 }
390 
391 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:104
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:123
const JOINT_SET ConnectedJoints(JOINT *aStart)
CITER next(CITER it)
Definition: ptree.cpp:130
Class ITEM.
Definition: pns_item.h:53
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:207
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited)
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
bool IsTraceWidthChange() const
Definition: pns_joint.h:108
Class BOARD to handle a board.
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:834
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
ENTRIES & Items()
Definition: pns_itemset.h:137
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems)
Definition: pns_node.cpp:1234
static const int dist[10][10]
Definition: dist.cpp:57
ITEM * NearestUnconnectedItem(JOINT *aStart, int *aAnchor=NULL, int aKindMask=ITEM::ANY_T)
const VECTOR2I & Pos() const
Definition: pns_via.h:88
SEGMENT * GetLink(int aIndex) const
Definition: pns_line.h:203
#define abs(a)
Definition: auxiliary.h:84
int Width() const
Returns line width
Definition: pns_line.h:159
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:109
Casted dyn_cast(From aObject)
Function dyn_cast()
Definition: typeinfo.h:73
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
int PointCount() const
Returns the number of points in the line
Definition: pns_line.h:135
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assigns a shape to the line (a polyline/line chain)
Definition: pns_line.h:105
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
ITEM_SET & Links()
Definition: pns_joint.h:187
Class JOINT.
Definition: pns_joint.h:44
void SetGap(int aGap)
const ITEM_SET AssembleTrivialPath(ITEM *aStart)
void Reverse()
Reverses the point/vertex order
Definition: pns_line.cpp:730
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:295
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
bool IsNonFanoutVia() const
Definition: pns_joint.h:100
virtual VECTOR2I Anchor(int n) const override
Definition: pns_segment.h:116
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:192
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:129
bool EndsWithVia() const
Definition: pns_line.h:248
NODE * m_world
Definition: pns_topology.h:71
void SetWidth(int aWidth)
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
void SetLayers(const LAYER_RANGE &aLayers)
Function SetLayers()
Definition: pns_item.h:187
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:968
bool SimplifyLine(LINE *aLine)
extended_type Cross(const VECTOR2< T > &aVector) const
Function Cross() computes cross product of self with aVector.
Definition: vector2d.h:480
Definition: seg.h:37
Class DIFF_PAIR.
SEGMENT_REFS & LinkedSegments()
Returns the list of segments from the owning node that constitute this line (or NULL if the line is n...
Definition: pns_line.h:181
RULE_RESOLVER * GetRuleResolver()
Definition: pns_node.h:168
#define max(a, b)
Definition: auxiliary.h:86
Class SHAPE_LINE_CHAIN.
const VECTOR2I & Pos() const
Definition: pns_joint.h:167
VECTOR2I A
Definition: seg.h:47
int Net() const
Function Net()
Definition: pns_item.h:177
void Clear()
Function Clear() Removes all points from the line chain.
virtual int DpNetPolarity(int aNet)=0
const SEG & Seg() const
Definition: pns_segment.h:93
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:177
int Net() const
Definition: pns_joint.h:172
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:142
Push and Shove diff pair dimensions (gap) settings dialog.
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aForceClearance=-1)
Function QueryColliding()
Definition: pns_node.cpp:278
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
bool commonParallelProjection(SEG n, SEG p, SEG &pClip, SEG &nClip)
std::set< JOINT * > JOINT_SET
Definition: pns_topology.h:42
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:141
bool IsLinked() const
Definition: pns_line.h:186
Struct OBSTACLE.
Definition: pns_node.h:76
VECTOR2I B
Definition: seg.h:48