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 )
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, std::set<ITEM*>& aVisited )
181 {
182  assert( aLine->IsLinked() );
183 
184  VECTOR2I anchor = aLeft ? aLine->CPoint( 0 ) : aLine->CPoint( -1 );
185  LINKED_ITEM* last =
186  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  return false;
208 
209  LINE l = m_world->AssembleLine( next_seg );
210 
211  VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
212 
213  if( nextAnchor != anchor )
214  {
215  l.Reverse();
216  }
217 
218  if( aLeft )
219  {
220  if( via )
221  aSet.Prepend( via );
222 
223  aSet.Prepend( l );
224  }
225  else
226  {
227  if( via )
228  aSet.Add( via );
229 
230  aSet.Add( l );
231  }
232 
233  return followTrivialPath( &l, aLeft, aSet, aVisited );
234  }
235 
236  return false;
237 }
238 
239 
241 {
242  ITEM_SET path;
243  std::set<ITEM*> visited;
244  SEGMENT* seg;
245  VIA* via;
246 
247  seg = dyn_cast<SEGMENT*> (aStart);
248 
249  if(!seg && (via = dyn_cast<VIA*>( aStart ) ) )
250  {
251  JOINT *jt = m_world->FindJoint( via->Pos(), via );
252 
253  if( !jt->IsNonFanoutVia() )
254  return ITEM_SET();
255 
256  for( const auto& entry : jt->Links().Items() )
257  if( ( seg = dyn_cast<SEGMENT*>( entry.item ) ) )
258  break;
259  }
260 
261  if( !seg )
262  return ITEM_SET();
263 
264  LINE l = m_world->AssembleLine( seg );
265 
266  path.Add( l );
267 
268  followTrivialPath( &l, false, path, visited );
269  followTrivialPath( &l, true, path, visited );
270 
271  return path;
272 }
273 
274 
275 const ITEM_SET TOPOLOGY::ConnectedItems( JOINT* aStart, int aKindMask )
276 {
277  return ITEM_SET();
278 }
279 
280 
281 const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
282 {
283  return ITEM_SET();
284 }
285 
286 
287 bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
288 
289 
291 {
292  int refNet = aStart->Net();
293  int coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
294 
295  if( coupledNet < 0 )
296  return false;
297 
298  std::set<ITEM*> coupledItems;
299 
300  m_world->AllItemsInNet( coupledNet, coupledItems );
301 
302  SEGMENT* coupledSeg = NULL, *refSeg;
303  int minDist = std::numeric_limits<int>::max();
304 
305  if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) != NULL )
306  {
307  for( ITEM* item : coupledItems )
308  {
309  if( SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
310  {
311  if( s->Layers().Start() == refSeg->Layers().Start() && s->Width() == refSeg->Width() )
312  {
313  int dist = s->Seg().Distance( refSeg->Seg() );
314  bool isParallel = refSeg->Seg().ApproxParallel( s->Seg() );
315  SEG p_clip, n_clip;
316 
317  bool isCoupled = commonParallelProjection( refSeg->Seg(), s->Seg(), p_clip, n_clip );
318 
319  if( isParallel && isCoupled && dist < minDist )
320  {
321  minDist = dist;
322  coupledSeg = s;
323  }
324  }
325  }
326  }
327  }
328  else
329  {
330  return false;
331  }
332 
333  if( !coupledSeg )
334  return false;
335 
336  LINE lp = m_world->AssembleLine( refSeg );
337  LINE ln = m_world->AssembleLine( coupledSeg );
338 
339  if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
340  {
341  std::swap( lp, ln );
342  }
343 
344  int gap = -1;
345 
346  if( refSeg->Seg().ApproxParallel( coupledSeg->Seg() ) )
347  {
348  // Segments are parallel -> compute pair gap
349  const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
350  const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->Anchor( 1 );
351  gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
352  }
353 
354  aPair = DIFF_PAIR( lp, ln );
355  aPair.SetWidth( lp.Width() );
356  aPair.SetLayers( lp.Layers() );
357  aPair.SetGap( gap );
358 
359  return true;
360 }
361 
362 const std::set<ITEM*> TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer )
363 {
364  std::set<ITEM*> visited;
365  std::deque<ITEM*> pending;
366 
367  pending.push_back( aStart );
368 
369  while( !pending.empty() )
370  {
371  NODE::OBSTACLES obstacles;
372  ITEM* top = pending.front();
373 
374  pending.pop_front();
375 
376  visited.insert( top );
377 
378  m_world->QueryColliding( top, obstacles, ITEM::ANY_T, -1, false );
379 
380  for( OBSTACLE& obs : obstacles )
381  {
382  if( visited.find( obs.m_item ) == visited.end() && obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
383  {
384  visited.insert( obs.m_item );
385  pending.push_back( obs.m_item );
386  }
387  }
388  }
389 
390  return visited;
391 }
392 
393 }
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
bool IsTraceWidthChange() const
Link the joint to a given board item (when it's added to the NODE).
Definition: pns_joint.h:126
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited)
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)
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
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
const VECTOR2I & Pos() const
Definition: pns_via.h:96
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:804
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
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)
const ITEM_SET AssembleTrivialPath(ITEM *aStart)
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:862
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:912
#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:68
void SetWidth(int aWidth)
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:195
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:259
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:1027
bool SimplifyLine(LINE *aLine)
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:182
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:1298
VECTOR2I A
Definition: seg.h:49
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
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
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:154
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:615
const LAYER_RANGE & Layers() const
Definition: pns_item.h:150
std::set< JOINT * > JOINT_SET
Definition: pns_topology.h:42
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:106
VECTOR2I B
Definition: seg.h:50