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