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