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