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