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 
38 #include "pns_node.h"
39 #include "pns_line_placer.h"
40 #include "pns_line.h"
41 #include "pns_solid.h"
42 #include "pns_utils.h"
43 #include "pns_router.h"
44 #include "pns_shove.h"
45 #include "pns_dragger.h"
46 #include "pns_topology.h"
47 #include "pns_diff_pair_placer.h"
48 #include "pns_meander_placer.h"
50 #include "pns_dp_meander_placer.h"
51 
53 
54 #include <class_board.h>
56 #include <class_module.h>
57 #include <class_track.h>
58 #include <ratsnest_data.h>
60 #include <geometry/convex_hull.h>
61 
62 namespace PNS {
63 
64 // an ugly singleton for drawing debug items within the router context.
65 // To be fixed sometime in the future.
66 static ROUTER* theRouter;
67 
69 {
70  theRouter = this;
71 
72  m_state = IDLE;
74 
75  // Initialize all other variables:
76  m_lastNode = nullptr;
77  m_iterLimit = 0;
78  m_showInterSteps = false;
79  m_snapshotIter = 0;
80  m_violation = false;
81  m_iface = nullptr;
82 }
83 
84 
86 {
87  return theRouter;
88 }
89 
90 
92 {
93  ClearWorld();
94  theRouter = nullptr;
95 }
96 
97 
99 {
100  ClearWorld();
101 
102  m_world = std::unique_ptr<NODE>( new NODE );
103  m_iface->SyncWorld( m_world.get() );
104 
105 }
106 
108 {
109  if( m_world )
110  {
111  m_world->KillChildren();
112  m_world.reset();
113  }
114 
115  m_placer.reset();
116 }
117 
118 
120 {
121  return m_state != IDLE;
122 }
123 
124 
126 {
127  if( m_state == IDLE )
128  return m_world->HitTest( aP );
129  else
130  return m_placer->CurrentNode()->HitTest( aP );
131 }
132 
133 
134 bool ROUTER::StartDragging( const VECTOR2I& aP, ITEM* aStartItem )
135 {
136  if( !aStartItem || aStartItem->OfKind( ITEM::SOLID_T ) )
137  return false;
138 
139  m_dragger.reset( new DRAGGER( this ) );
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  switch( m_mode )
159  {
161  m_placer.reset( new LINE_PLACER( this ) );
162  break;
164  m_placer.reset( new DIFF_PAIR_PLACER( this ) );
165  break;
167  m_placer.reset( new MEANDER_PLACER( this ) );
168  break;
170  m_placer.reset( new DP_MEANDER_PLACER( this ) );
171  break;
173  m_placer.reset( new MEANDER_SKEW_PLACER( this ) );
174  break;
175 
176  default:
177  return false;
178  }
179 
180  m_placer->UpdateSizes ( m_sizes );
181  m_placer->SetLayer( aLayer );
182  m_placer->SetDebugDecorator ( m_iface->GetDebugDecorator () );
183 
184  bool rv = m_placer->Start( aP, aStartItem );
185 
186  if( !rv )
187  return false;
188 
189  m_currentEnd = aP;
191  return rv;
192 }
193 
194 
195 void ROUTER::DisplayItems( const ITEM_SET& aItems )
196 {
197  for( const ITEM* item : aItems.CItems() )
198  m_iface->DisplayItem( item );
199 }
200 
201 
202 void ROUTER::Move( const VECTOR2I& aP, ITEM* endItem )
203 {
204  m_currentEnd = aP;
205 
206  switch( m_state )
207  {
208  case ROUTE_TRACK:
209  movePlacing( aP, endItem );
210  break;
211 
212  case DRAG_SEGMENT:
213  moveDragging( aP, endItem );
214  break;
215 
216  default:
217  break;
218  }
219 }
220 
221 
222 void ROUTER::moveDragging( const VECTOR2I& aP, ITEM* aEndItem )
223 {
224  m_iface->EraseView();
225 
226  m_dragger->Drag( aP );
227  ITEM_SET dragged = m_dragger->Traces();
228 
229  updateView( m_dragger->CurrentNode(), dragged );
230 }
231 
232 
233 void ROUTER::markViolations( NODE* aNode, ITEM_SET& aCurrent, NODE::ITEM_VECTOR& aRemoved )
234 {
235  for( ITEM* item : aCurrent.Items() )
236  {
237  NODE::OBSTACLES obstacles;
238 
239  aNode->QueryColliding( item, obstacles, ITEM::ANY_T );
240 
241  if( item->OfKind( ITEM::LINE_T ) )
242  {
243  LINE* l = static_cast<LINE*>( item );
244 
245  if( l->EndsWithVia() )
246  {
247  VIA v( l->Via() );
248  aNode->QueryColliding( &v, obstacles, ITEM::ANY_T );
249  }
250  }
251 
252  for( OBSTACLE& obs : obstacles )
253  {
254  int clearance = aNode->GetClearance( item, obs.m_item );
255  std::unique_ptr<ITEM> tmp( obs.m_item->Clone() );
256  tmp->Mark( MK_VIOLATION );
257  m_iface->DisplayItem( tmp.get(), -1, clearance );
258  aRemoved.push_back( obs.m_item );
259  }
260  }
261 }
262 
263 
264 void ROUTER::updateView( NODE* aNode, ITEM_SET& aCurrent )
265 {
266  NODE::ITEM_VECTOR removed, added;
267  NODE::OBSTACLES obstacles;
268 
269  if( !aNode )
270  return;
271 
272  if( Settings().Mode() == RM_MarkObstacles )
273  markViolations( aNode, aCurrent, removed );
274 
275  aNode->GetUpdatedItems( removed, added );
276 
277  for( auto item : added )
278  m_iface->DisplayItem( item );
279 
280  for( auto item : removed )
281  m_iface->HideItem( item );
282 }
283 
284 
285 void ROUTER::UpdateSizes( const SIZES_SETTINGS& aSizes )
286 {
287  m_sizes = aSizes;
288 
289  // Change track/via size settings
290  if( m_state == ROUTE_TRACK)
291  {
292  m_placer->UpdateSizes( m_sizes );
293  }
294 }
295 
296 
297 void ROUTER::movePlacing( const VECTOR2I& aP, ITEM* aEndItem )
298 {
299  m_iface->EraseView();
300 
301  m_placer->Move( aP, aEndItem );
302  ITEM_SET current = m_placer->Traces();
303 
304  for( const ITEM* item : current.CItems() )
305  {
306  if( !item->OfKind( ITEM::LINE_T ) )
307  continue;
308 
309  const LINE* l = static_cast<const LINE*>( item );
310  int clearance = GetRuleResolver()->Clearance( item->Net() );
311 
312  m_iface->DisplayItem( l, -1, clearance );
313 
314  if( l->EndsWithVia() )
315  m_iface->DisplayItem( &l->Via(), -1, clearance );
316  }
317 
318  //ITEM_SET tmp( &current );
319 
320  updateView( m_placer->CurrentNode( true ), current );
321 }
322 
323 
325 {
326  NODE::ITEM_VECTOR removed, added;
327 
328  aNode->GetUpdatedItems( removed, added );
329 
330  for( auto item : removed )
331  m_iface->RemoveItem( item );
332 
333  for( auto item : added )
334  m_iface->AddItem( item );
335 
336  m_iface->Commit();
337  m_world->Commit( aNode );
338 }
339 
340 
341 bool ROUTER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
342 {
343  bool rv = false;
344 
345  switch( m_state )
346  {
347  case ROUTE_TRACK:
348  rv = m_placer->FixRoute( aP, aEndItem );
349  break;
350 
351  case DRAG_SEGMENT:
352  rv = m_dragger->FixRoute();
353  break;
354 
355  default:
356  break;
357  }
358 
359  if( rv )
360  StopRouting();
361 
362  return rv;
363 }
364 
365 
367 {
368  // Update the ratsnest with new changes
369 
370  if( m_placer )
371  {
372  std::vector<int> nets;
373  m_placer->GetModifiedNets( nets );
374 
375  // Update the ratsnest with new changes
376  for ( auto n : nets )
377  m_iface->UpdateNet( n );
378  }
379 
380  if( !RoutingInProgress() )
381  return;
382 
383  m_placer.reset();
384  m_dragger.reset();
385 
386  m_iface->EraseView();
387 
388  m_state = IDLE;
389  m_world->KillChildren();
390  m_world->ClearRanks();
391 }
392 
393 
395 {
396  if( m_state == ROUTE_TRACK )
397  {
398  m_placer->FlipPosture();
399  }
400 }
401 
402 
403 void ROUTER::SwitchLayer( int aLayer )
404 {
405  switch( m_state )
406  {
407  case ROUTE_TRACK:
408  m_placer->SetLayer( aLayer );
409  break;
410  default:
411  break;
412  }
413 }
414 
415 
417 {
418  if( m_state == ROUTE_TRACK )
419  {
420  bool toggle = !m_placer->IsPlacingVia();
421  m_placer->ToggleVia( toggle );
422  }
423 }
424 
425 
426 const std::vector<int> ROUTER::GetCurrentNets() const
427 {
428  if( m_placer )
429  return m_placer->CurrentNets();
430 
431  return std::vector<int>();
432 }
433 
434 
436 {
437  if( m_placer )
438  return m_placer->CurrentLayer();
439  return -1;
440 }
441 
442 
444 {
445  LOGGER* logger = nullptr;
446 
447  switch( m_state )
448  {
449  case DRAG_SEGMENT:
450  logger = m_dragger->Logger();
451  break;
452 
453  case ROUTE_TRACK:
454  logger = m_placer->Logger();
455  break;
456 
457  default:
458  break;
459  }
460 
461  if( logger )
462  logger->Save( "/tmp/shove.log" );
463 }
464 
465 
467 {
468  if( !m_placer )
469  return false;
470 
471  return m_placer->IsPlacingVia();
472 }
473 
474 
475 void ROUTER::SetOrthoMode( bool aEnable )
476 {
477  if( !m_placer )
478  return;
479 
480  m_placer->SetOrthoMode( aEnable );
481 }
482 
483 
485 {
486  m_mode = aMode;
487 }
488 
489 
491 {
492  m_iface = aIface;
493  m_iface->SetRouter( this );
494 }
495 
496 }
Class ITEM.
Definition: pns_item.h:53
Class BOARD_CONNECTED_ITEM.
void moveDragging(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:222
const VIA & Via() const
Definition: pns_line.h:253
int m_snapshotIter
Definition: pns_router.h:254
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:264
const ITEM_SET QueryHoverItems(const VECTOR2I &aP)
Definition: pns_router.cpp:125
Class BOARD to handle a board.
bool StartDragging(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:134
Class that computes missing connections on a PCB.
ENTRIES & Items()
Definition: pns_itemset.h:137
Class LINE_PLACER.
virtual void HideItem(ITEM *aItem)=0
void SyncWorld()
Definition: pns_router.cpp:98
Class ROUTER.
Definition: pns_router.h:78
VECTOR2I m_currentEnd
Definition: pns_router.h:240
int m_iterLimit
Definition: pns_router.h:252
void DisplayItems(const ITEM_SET &aItems)
Definition: pns_router.cpp:195
bool IsPlacingVia() const
Definition: pns_router.cpp:466
virtual void AddItem(ITEM *aItem)=0
const std::vector< int > GetCurrentNets() const
Definition: pns_router.cpp:426
void SwitchLayer(int layer)
Definition: pns_router.cpp:403
void SetOrthoMode(bool aEnable)
Definition: pns_router.cpp:475
Functions relatives to tracks, vias and segments used to fill zones.
void ToggleViaPlacement()
Definition: pns_router.cpp:416
void ClearWorld()
Definition: pns_router.cpp:107
bool RoutingInProgress() const
Definition: pns_router.cpp:119
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:130
std::unique_ptr< NODE > m_world
Definition: pns_router.h:243
virtual void SyncWorld(NODE *aNode)=0
virtual void UpdateNet(int aNetCode)=0
VIEW_ITEM class definition.
bool m_showInterSteps
Definition: pns_router.h:253
NODE * m_lastNode
Definition: pns_router.h:244
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0
std::unique_ptr< PLACEMENT_ALGO > m_placer
Definition: pns_router.h:246
bool EndsWithVia() const
Definition: pns_line.h:248
bool FixRoute(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:341
RouterState m_state
Definition: pns_router.h:241
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:250
virtual void SetRouter(ROUTER *aRouter)=0
Class DRAGGER.
Definition: pns_dragger.h:44
void movePlacing(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:297
void Move(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:202
bool StartRouting(const VECTOR2I &aP, ITEM *aItem, int aLayer)
Definition: pns_router.cpp:156
void SetInterface(ROUTER_IFACE *aIface)
Definition: pns_router.cpp:490
Class MEANDER_SKEW_PLACER.
std::unique_ptr< DRAGGER > m_dragger
Definition: pns_router.h:247
void StopRouting()
Definition: pns_router.cpp:366
virtual void EraseView()=0
Class LINE_PLACER.
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_router.h:154
static ROUTER * theRouter
Definition: pns_router.cpp:66
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:285
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:100
void SetMode(ROUTER_MODE aMode)
Definition: pns_router.cpp:484
Board layer functions and definitions.
void CommitRouting(NODE *aNode)
Definition: pns_router.cpp:324
ROUTER_MODE Mode() const
Definition: pns_router.h:116
virtual void DisplayItem(const ITEM *aItem, int aColor=-1, int aClearance=-1)=0
SIZES_SETTINGS m_sizes
Definition: pns_router.h:258
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:255
virtual void RemoveItem(ITEM *aItem)=0
int GetCurrentLayer() const
Definition: pns_router.cpp:435
ROUTER_MODE m_mode
Definition: pns_router.h:259
void DumpLog()
Definition: pns_router.cpp:443
Module description (excepted pads)
void FlipPosture()
Definition: pns_router.cpp:394
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:278
ROUTING_SETTINGS & Settings()
Definition: pns_router.h:178
static ROUTER * GetInstance()
Definition: pns_router.cpp:85
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:233
Struct OBSTACLE.
Definition: pns_node.h:76