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