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