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