KiCad PCB EDA Suite
pns_router.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 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 <cstdio>
23 #include <vector>
24 
25 #include <view/view.h>
26 #include <view/view_item.h>
27 #include <view/view_group.h>
29 #include <gal/color4d.h>
30 
31 #include <pcb_painter.h>
32 
33 #include <geometry/shape.h>
35 #include <geometry/shape_rect.h>
36 #include <geometry/shape_circle.h>
37 #include <geometry/convex_hull.h>
38 
39 #include "pns_node.h"
40 #include "pns_line_placer.h"
41 #include "pns_line.h"
42 #include "pns_solid.h"
43 #include "pns_utils.h"
44 #include "pns_router.h"
45 #include "pns_shove.h"
46 #include "pns_dragger.h"
47 #include "pns_topology.h"
48 #include "pns_diff_pair_placer.h"
49 #include "pns_meander_placer.h"
51 #include "pns_dp_meander_placer.h"
52 
53 namespace PNS {
54 
55 // an ugly singleton for drawing debug items within the router context.
56 // To be fixed sometime in the future.
57 static ROUTER* theRouter;
58 
60 {
61  theRouter = this;
62 
63  m_state = IDLE;
65 
66  // Initialize all other variables:
67  m_lastNode = nullptr;
68  m_iterLimit = 0;
69  m_showInterSteps = false;
70  m_snapshotIter = 0;
71  m_violation = false;
72  m_iface = nullptr;
73 }
74 
75 
77 {
78  return theRouter;
79 }
80 
81 
83 {
84  ClearWorld();
85  theRouter = nullptr;
86 }
87 
88 
90 {
91  ClearWorld();
92 
93  m_world = std::unique_ptr<NODE>( new NODE );
94  m_iface->SyncWorld( m_world.get() );
95 
96 }
97 
99 {
100  if( m_world )
101  {
102  m_world->KillChildren();
103  m_world.reset();
104  }
105 
106  m_placer.reset();
107 }
108 
109 
111 {
112  return m_state != IDLE;
113 }
114 
115 
117 {
118  if( m_state == IDLE || m_placer == nullptr )
119  return m_world->HitTest( aP );
120  else
121  return m_placer->CurrentNode()->HitTest( aP );
122 }
123 
124 
125 bool ROUTER::StartDragging( const VECTOR2I& aP, ITEM* aStartItem, int aDragMode )
126 {
127 
128  if( aDragMode & DM_FREE_ANGLE )
130  else
131  m_forceMarkObstaclesMode = false;
132 
133  if( !aStartItem || aStartItem->OfKind( ITEM::SOLID_T ) )
134  return false;
135 
136  m_placer.reset( new LINE_PLACER( this ) );
137  m_placer->Start( aP, aStartItem );
138 
139  m_dragger.reset( new DRAGGER( this ) );
140  m_dragger->SetMode( aDragMode );
141  m_dragger->SetWorld( m_world.get() );
142  m_dragger->SetDebugDecorator ( m_iface->GetDebugDecorator () );
143 
144  if( m_dragger->Start ( aP, aStartItem ) )
146  else
147  {
148  m_dragger.reset();
149  m_state = IDLE;
150  return false;
151  }
152 
153  return true;
154 }
155 
156 bool ROUTER::isStartingPointRoutable( const VECTOR2I& aWhere, int aLayer )
157 {
158  if( Settings().CanViolateDRC() && Settings().Mode() == RM_MarkObstacles )
159  return true;
160 
161  auto candidates = QueryHoverItems( aWhere );
162 
163  for( ITEM* item : candidates.Items() )
164  {
165  if( ! item->IsRoutable() && item->Layers().Overlaps( aLayer ) )
166  {
167  return false;
168  }
169  }
170 
171  return true;
172 }
173 
174 bool ROUTER::StartRouting( const VECTOR2I& aP, ITEM* aStartItem, int aLayer )
175 {
176 
177  if( ! isStartingPointRoutable( aP, aLayer ) )
178  {
179  SetFailureReason( _("Cannot start routing inside a keepout area or board outline." ) );
180  return false;
181  }
182 
183  m_forceMarkObstaclesMode = false;
184 
185  switch( m_mode )
186  {
188  m_placer.reset( new LINE_PLACER( this ) );
189  break;
191  m_placer.reset( new DIFF_PAIR_PLACER( this ) );
192  break;
194  m_placer.reset( new MEANDER_PLACER( this ) );
195  break;
197  m_placer.reset( new DP_MEANDER_PLACER( this ) );
198  break;
200  m_placer.reset( new MEANDER_SKEW_PLACER( this ) );
201  break;
202 
203  default:
204  return false;
205  }
206 
207  m_placer->UpdateSizes ( m_sizes );
208  m_placer->SetLayer( aLayer );
209  m_placer->SetDebugDecorator ( m_iface->GetDebugDecorator () );
210 
211  bool rv = m_placer->Start( aP, aStartItem );
212 
213  if( !rv )
214  return false;
215 
216  m_currentEnd = aP;
218  return rv;
219 }
220 
221 
222 void ROUTER::DisplayItems( const ITEM_SET& aItems )
223 {
224  for( const ITEM* item : aItems.CItems() )
225  m_iface->DisplayItem( item );
226 }
227 
228 
229 void ROUTER::Move( const VECTOR2I& aP, ITEM* endItem )
230 {
231  m_currentEnd = aP;
232 
233  switch( m_state )
234  {
235  case ROUTE_TRACK:
236  movePlacing( aP, endItem );
237  break;
238 
239  case DRAG_SEGMENT:
240  moveDragging( aP, endItem );
241  break;
242 
243  default:
244  break;
245  }
246 }
247 
248 
249 void ROUTER::moveDragging( const VECTOR2I& aP, ITEM* aEndItem )
250 {
251  m_iface->EraseView();
252 
253  m_dragger->Drag( aP );
254  ITEM_SET dragged = m_dragger->Traces();
255 
256  updateView( m_dragger->CurrentNode(), dragged, true );
257 }
258 
259 
260 void ROUTER::markViolations( NODE* aNode, ITEM_SET& aCurrent, NODE::ITEM_VECTOR& aRemoved )
261 {
262  for( ITEM* item : aCurrent.Items() )
263  {
264  NODE::OBSTACLES obstacles;
265 
266  aNode->QueryColliding( item, obstacles, ITEM::ANY_T );
267 
268  if( item->OfKind( ITEM::LINE_T ) )
269  {
270  LINE* l = static_cast<LINE*>( item );
271 
272  if( l->EndsWithVia() )
273  {
274  VIA v( l->Via() );
275  aNode->QueryColliding( &v, obstacles, ITEM::ANY_T );
276  }
277  }
278 
279  for( OBSTACLE& obs : obstacles )
280  {
281  int clearance = aNode->GetClearance( item, obs.m_item );
282  std::unique_ptr<ITEM> tmp( obs.m_item->Clone() );
283  tmp->Mark( MK_VIOLATION );
284  m_iface->DisplayItem( tmp.get(), -1, clearance );
285  aRemoved.push_back( obs.m_item );
286  }
287  }
288 }
289 
290 
291 void ROUTER::updateView( NODE* aNode, ITEM_SET& aCurrent, bool aDragging )
292 {
293  NODE::ITEM_VECTOR removed, added;
294  NODE::OBSTACLES obstacles;
295 
296  if( !aNode )
297  return;
298 
300  markViolations( aNode, aCurrent, removed );
301 
302  aNode->GetUpdatedItems( removed, added );
303 
304  for( auto item : added )
305  {
306  int clearance = GetRuleResolver()->Clearance( item->Net() );
307 
308  m_iface->DisplayItem( item, -1, clearance, aDragging );
309  }
310 
311  for( auto item : removed )
312  m_iface->HideItem( item );
313 }
314 
315 
316 void ROUTER::UpdateSizes( const SIZES_SETTINGS& aSizes )
317 {
318  m_sizes = aSizes;
319 
320  // Change track/via size settings
321  if( m_state == ROUTE_TRACK)
322  {
323  m_placer->UpdateSizes( m_sizes );
324  }
325 }
326 
327 
328 void ROUTER::movePlacing( const VECTOR2I& aP, ITEM* aEndItem )
329 {
330  m_iface->EraseView();
331 
332  m_placer->Move( aP, aEndItem );
333  ITEM_SET current = m_placer->Traces();
334 
335  for( const ITEM* item : current.CItems() )
336  {
337  if( !item->OfKind( ITEM::LINE_T ) )
338  continue;
339 
340  const LINE* l = static_cast<const LINE*>( item );
341  int clearance = GetRuleResolver()->Clearance( item->Net() );
342 
343  m_iface->DisplayItem( l, -1, clearance );
344 
345  if( l->EndsWithVia() )
346  m_iface->DisplayItem( &l->Via(), -1, clearance );
347  }
348 
349  //ITEM_SET tmp( &current );
350 
351  updateView( m_placer->CurrentNode( true ), current );
352 }
353 
354 
356 {
357  NODE::ITEM_VECTOR removed, added;
358 
359  aNode->GetUpdatedItems( removed, added );
360 
361  for( auto item : removed )
362  m_iface->RemoveItem( item );
363 
364  for( auto item : added )
365  m_iface->AddItem( item );
366 
367  m_iface->Commit();
368  m_world->Commit( aNode );
369 }
370 
371 
372 bool ROUTER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
373 {
374  bool rv = false;
375 
376  switch( m_state )
377  {
378  case ROUTE_TRACK:
379  rv = m_placer->FixRoute( aP, aEndItem, aForceFinish );
380  break;
381 
382  case DRAG_SEGMENT:
383  rv = m_dragger->FixRoute();
384  break;
385 
386  default:
387  break;
388  }
389 
390  if( rv )
391  StopRouting();
392 
393  return rv;
394 }
395 
396 
398 {
399  // Update the ratsnest with new changes
400 
401  if( m_placer )
402  {
403  std::vector<int> nets;
404  m_placer->GetModifiedNets( nets );
405 
406  // Update the ratsnest with new changes
407  for ( auto n : nets )
408  m_iface->UpdateNet( n );
409  }
410 
411  if( !RoutingInProgress() )
412  return;
413 
414  m_placer.reset();
415  m_dragger.reset();
416 
417  m_iface->EraseView();
418 
419  m_state = IDLE;
420  m_world->KillChildren();
421  m_world->ClearRanks();
422 }
423 
424 
426 {
427  if( m_state == ROUTE_TRACK )
428  {
429  m_placer->FlipPosture();
430  }
431 }
432 
433 
434 void ROUTER::SwitchLayer( int aLayer )
435 {
436  switch( m_state )
437  {
438  case ROUTE_TRACK:
439  m_placer->SetLayer( aLayer );
440  break;
441  default:
442  break;
443  }
444 }
445 
446 
448 {
449  if( m_state == ROUTE_TRACK )
450  {
451  bool toggle = !m_placer->IsPlacingVia();
452  m_placer->ToggleVia( toggle );
453  }
454 }
455 
456 
457 const std::vector<int> ROUTER::GetCurrentNets() const
458 {
459  if( m_placer )
460  return m_placer->CurrentNets();
461 
462  return std::vector<int>();
463 }
464 
465 
467 {
468  if( m_placer )
469  return m_placer->CurrentLayer();
470  return -1;
471 }
472 
473 
475 {
476  LOGGER* logger = nullptr;
477 
478  switch( m_state )
479  {
480  case DRAG_SEGMENT:
481  logger = m_dragger->Logger();
482  break;
483 
484  case ROUTE_TRACK:
485  logger = m_placer->Logger();
486  break;
487 
488  default:
489  break;
490  }
491 
492  if( logger )
493  logger->Save( "/tmp/shove.log" );
494 }
495 
496 
498 {
499  if( !m_placer )
500  return false;
501 
502  return m_placer->IsPlacingVia();
503 }
504 
505 
506 void ROUTER::SetOrthoMode( bool aEnable )
507 {
508  if( !m_placer )
509  return;
510 
511  m_placer->SetOrthoMode( aEnable );
512 }
513 
514 
516 {
517  m_mode = aMode;
518 }
519 
520 
522 {
523  m_iface = aIface;
524  m_iface->SetRouter( this );
525 }
526 
527 void ROUTER::BreakSegment( ITEM *aItem, const VECTOR2I& aP )
528 {
529  NODE *node = m_world->Branch();
530 
531  LINE_PLACER placer( this );
532 
533  if ( placer.SplitAdjacentSegments( node, aItem, aP ) )
534  {
535  CommitRouting( node );
536  }
537  else
538  {
539  delete node;
540  }
541 
542 }
543 
544 }
bool isStartingPointRoutable(const VECTOR2I &aWhere, int aLayer)
Definition: pns_router.cpp:156
Class ITEM.
Definition: pns_item.h:53
void moveDragging(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:249
int m_snapshotIter
Definition: pns_router.h:266
Class NODE.
Definition: pns_node.h:140
const ITEM_SET QueryHoverItems(const VECTOR2I &aP)
Definition: pns_router.cpp:116
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_router.h:165
ENTRIES & Items()
Definition: pns_itemset.h:140
Class LINE_PLACER.
virtual void HideItem(ITEM *aItem)=0
void SyncWorld()
Definition: pns_router.cpp:89
Class ROUTER.
Definition: pns_router.h:87
bool IsPlacingVia() const
Definition: pns_router.cpp:497
const std::vector< int > GetCurrentNets() const
Definition: pns_router.cpp:457
VECTOR2I m_currentEnd
Definition: pns_router.h:252
int m_iterLimit
Definition: pns_router.h:264
void DisplayItems(const ITEM_SET &aItems)
Definition: pns_router.cpp:222
virtual void AddItem(ITEM *aItem)=0
void SwitchLayer(int layer)
Definition: pns_router.cpp:434
void SetOrthoMode(bool aEnable)
Definition: pns_router.cpp:506
bool EndsWithVia() const
Definition: pns_line.h:264
void ToggleViaPlacement()
Definition: pns_router.cpp:447
void ClearWorld()
Definition: pns_router.cpp:98
std::unique_ptr< NODE > m_world
Definition: pns_router.h:255
virtual void SyncWorld(NODE *aNode)=0
virtual void UpdateNet(int aNetCode)=0
VIEW_ITEM class definition.
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:95
bool m_showInterSteps
Definition: pns_router.h:265
void BreakSegment(ITEM *aItem, const VECTOR2I &aP)
Definition: pns_router.cpp:527
void updateView(NODE *aNode, ITEM_SET &aCurrent, bool aDragging=false)
Definition: pns_router.cpp:291
NODE * m_lastNode
Definition: pns_router.h:256
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Function SplitAdjacentSegments()
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0
std::unique_ptr< PLACEMENT_ALGO > m_placer
Definition: pns_router.h:258
bool FixRoute(const VECTOR2I &aP, ITEM *aItem, bool aForceFinish=false)
Definition: pns_router.cpp:372
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:215
RouterState m_state
Definition: pns_router.h:253
virtual void DisplayItem(const ITEM *aItem, int aColor=-1, int aClearance=-1, bool aEdit=false)=0
Class MEANDER_PLACER.
VIEW_GROUP extends VIEW_ITEM by possibility of grouping items into a single object.
ROUTER_IFACE * m_iface
Definition: pns_router.h:262
virtual void SetRouter(ROUTER *aRouter)=0
Class DRAGGER.
Definition: pns_dragger.h:47
void movePlacing(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:328
void Move(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:229
#define _(s)
bool StartRouting(const VECTOR2I &aP, ITEM *aItem, int aLayer)
Definition: pns_router.cpp:174
void SetInterface(ROUTER_IFACE *aIface)
Definition: pns_router.cpp:521
Class MEANDER_SKEW_PLACER.
std::unique_ptr< DRAGGER > m_dragger
Definition: pns_router.h:259
void StopRouting()
Definition: pns_router.cpp:397
virtual void EraseView()=0
static ROUTER * theRouter
Definition: pns_router.cpp:57
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
void Save(const std::string &aFilename)
Definition: pns_logger.cpp:197
ROUTER_MODE
Definition: pns_router.h:65
void UpdateSizes(const SIZES_SETTINGS &aSizes)
Applies stored settings.
Definition: pns_router.cpp:316
void SetMode(ROUTER_MODE aMode)
Definition: pns_router.cpp:515
void CommitRouting(NODE *aNode)
Definition: pns_router.cpp:355
bool StartDragging(const VECTOR2I &aP, ITEM *aItem, int aDragMode=DM_ANY)
Definition: pns_router.cpp:125
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:132
SIZES_SETTINGS m_sizes
Definition: pns_router.h:271
Class DP_MEANDER_PLACER.
virtual void Commit()=0
const ENTRIES & CItems() const
Definition: pns_itemset.h:141
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Function GetUpdatedItems()
Definition: pns_node.cpp:1149
bool m_violation
Definition: pns_router.h:267
virtual void RemoveItem(ITEM *aItem)=0
ROUTER_MODE m_mode
Definition: pns_router.h:272
void DumpLog()
Definition: pns_router.cpp:474
void FlipPosture()
Definition: pns_router.cpp:425
bool RoutingInProgress() const
Definition: pns_router.cpp:110
const VIA & Via() const
Definition: pns_line.h:269
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:145
ROUTER_MODE Mode() const
Definition: pns_router.h:126
Push and Shove diff pair dimensions (gap) settings dialog.
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:272
ROUTING_SETTINGS & Settings()
Definition: pns_router.h:189
static ROUTER * GetInstance()
Definition: pns_router.cpp:76
bool m_forceMarkObstaclesMode
Definition: pns_router.h:268
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:144
void markViolations(NODE *aNode, ITEM_SET &aCurrent, NODE::ITEM_VECTOR &aRemoved)
Definition: pns_router.cpp:260
Struct OBSTACLE.
Definition: pns_node.h:79
int GetCurrentLayer() const
Definition: pns_router.cpp:466