KiCad PCB EDA Suite
pns_dragger.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-2019 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 "pns_arc.h"
23 
24 #include "pns_dragger.h"
25 #include "pns_shove.h"
26 #include "pns_router.h"
27 #include "pns_debug_decorator.h"
28 #include "pns_walkaround.h"
29 
30 namespace PNS {
31 
32 DRAGGER::DRAGGER( ROUTER* aRouter ) :
33  DRAG_ALGO( aRouter )
34 {
35  m_world = NULL;
36  m_lastNode = NULL;
39  m_dragStatus = false;
41  m_freeAngleMode = false;
42 }
43 
44 
46 {
47 }
48 
49 
50 bool DRAGGER::startDragSegment( const VECTOR2D& aP, SEGMENT* aSeg )
51 {
52  int w2 = aSeg->Width() / 2;
53 
55 
56  if( m_shove )
57  {
58  m_shove->SetInitialLine( m_draggedLine );
59  }
60 
61  auto distA = ( aP - aSeg->Seg().A ).EuclideanNorm();
62  auto distB = ( aP - aSeg->Seg().B ).EuclideanNorm();
63 
64  if( distA <= w2 )
65  {
66  m_mode = DM_CORNER;
67  }
68  else if( distB <= w2 )
69  {
70  //todo (snh) Adjust segment for arcs
72  m_mode = DM_CORNER;
73  }
74  else if ( m_freeAngleMode )
75  {
76  if( distB < distA )
77  {
79  }
80  m_mode = DM_CORNER;
81  }
82  else
83  {
85  }
86 
87  return true;
88 }
89 
90 
91 
92 bool DRAGGER::startDragArc( const VECTOR2D& aP, ARC* aArc )
93 {
95  m_shove->SetInitialLine( m_draggedLine );
96  m_mode = DM_ARC;
97 
98  return true;
99 }
100 
101 
103 {
104  m_initialVia = aVia->MakeHandle();
106 
107  m_mode = DM_VIA;
108 
109  return true;
110 }
111 
113 {
114  ITEM_SET rv;
115 
116  JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
117 
118  if( !jt )
119  return rv;
120 
121  for( ITEM* item : jt->LinkList() )
122  {
123  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
124  {
125  int segIndex;
126  LINKED_ITEM* seg = ( LINKED_ITEM*) item;
127  LINE l = aNode->AssembleLine( seg, &segIndex );
128 
129  if( segIndex != 0 )
130  l.Reverse();
131 
132  rv.Add( l );
133  } else if ( item->OfKind( ITEM::VIA_T ))
134  {
135  rv.Add( item );
136  }
137  }
138 
139  return rv;
140 }
141 
142 bool DRAGGER::Start( const VECTOR2I& aP, ITEM_SET& aPrimitives )
143 {
144  if( aPrimitives.Empty() )
145  return false;
146 
147  ITEM* startItem = aPrimitives[0];
148 
149  m_lastNode = NULL;
153 
155  {
156  m_shove = std::make_unique<SHOVE>( m_world, Router() );
157  m_shove->SetLogger( Logger() );
158  m_shove->SetDebugDecorator( Dbg() );
159  }
160 
161  startItem->Unmark( MK_LOCKED );
162 
163  wxLogTrace( "PNS", "StartDragging: item %p [kind %d]", startItem, (int) startItem->Kind() );
164 
165  switch( startItem->Kind() )
166  {
167  case ITEM::SEGMENT_T:
168  return startDragSegment( aP, static_cast<SEGMENT*>( startItem ) );
169 
170  case ITEM::VIA_T:
171  return startDragVia( static_cast<VIA*>( startItem ) );
172 
173  case ITEM::ARC_T:
174  return startDragArc( aP, static_cast<ARC*>( startItem ) );
175 
176  default:
177  return false;
178  }
179 }
180 
181 
182 void DRAGGER::SetMode( int aMode )
183 {
184  m_mode = aMode;
185 }
186 
187 
189 {
190  // fixme: rewrite using shared_ptr...
191  if( m_lastNode )
192  {
193  delete m_lastNode;
194  m_lastNode = nullptr;
195  }
196 
198 
199  switch( m_mode )
200  {
201  case DM_SEGMENT:
202  case DM_CORNER:
203  {
204  //TODO: Make threshhold configurable
205  int thresh = Settings().SmoothDraggedSegments() ? m_draggedLine.Width() / 4 : 0;
206  LINE origLine( m_draggedLine );
207  LINE dragged( m_draggedLine );
208  dragged.SetSnapThreshhold( thresh );
209  dragged.ClearSegmentLinks();
210 
211  if( m_mode == DM_SEGMENT )
212  dragged.DragSegment( aP, m_draggedSegmentIndex );
213  else
215 
216  m_lastNode->Remove( origLine );
217  m_lastNode->Add( dragged );
218 
220  m_draggedItems.Add( dragged );
221 
222  break;
223  }
224 
225  case DM_VIA: // fixme...
226  {
228 
229  break;
230  }
231  }
232 
233  if( Settings().CanViolateDRC() )
234  m_dragStatus = true;
235  else
237 
238  return true;
239 }
240 
241 
242 void DRAGGER::dragViaMarkObstacles( const VIA_HANDLE& aHandle, NODE* aNode, const VECTOR2I& aP )
243 {
245 
246  ITEM_SET fanout = findViaFanoutByHandle( aNode, aHandle );
247 
248  if( fanout.Empty() )
249  {
250  return;
251  }
252 
253  for( ITEM* item : fanout.Items() )
254  {
255  if( const LINE* l = dyn_cast<const LINE*>( item ) )
256  {
257  LINE origLine( *l );
258  LINE draggedLine( *l );
259 
260  draggedLine.DragCorner( aP, origLine.CLine().Find( aHandle.pos ), m_freeAngleMode );
261  draggedLine.ClearSegmentLinks();
262 
263  m_draggedItems.Add( draggedLine );
264 
265  m_lastNode->Remove( origLine );
266  m_lastNode->Add( draggedLine );
267  }
268  else if ( VIA *via = dyn_cast<VIA*>( item ) )
269  {
270  auto nvia = Clone( *via );
271 
272  nvia->SetPos( aP );
273  m_draggedItems.Add( nvia.get() );
274 
275  m_lastNode->Remove( via );
276  m_lastNode->Add( std::move( nvia ) );
277  }
278  }
279 }
280 
281 
282 void DRAGGER::dragViaWalkaround( const VIA_HANDLE& aHandle, NODE* aNode, const VECTOR2I& aP )
283 {
285 
286  ITEM_SET fanout = findViaFanoutByHandle( aNode, aHandle );
287 
288  if( fanout.Empty() )
289  {
290  return;
291  }
292 
293  for( ITEM* item : fanout.Items() )
294  {
295  if( const LINE* l = dyn_cast<const LINE*>( item ) )
296  {
297  LINE origLine( *l );
298  LINE draggedLine( *l );
299 
300  draggedLine.DragCorner( aP, origLine.CLine().Find( aHandle.pos ), m_freeAngleMode );
301  draggedLine.ClearSegmentLinks();
302 
303  m_draggedItems.Add( draggedLine );
304 
305  m_lastNode->Remove( origLine );
306  m_lastNode->Add( draggedLine );
307  }
308  else if ( VIA *via = dyn_cast<VIA*>( item ) )
309  {
310  auto nvia = Clone( *via );
311 
312  nvia->SetPos( aP );
313  m_draggedItems.Add( nvia.get() );
314 
315  m_lastNode->Remove( via );
316  m_lastNode->Add( std::move( nvia ) );
317  }
318  }
319 }
320 
321 
323 {
324  VECTOR2D lockV;
325  dragged.ClearSegmentLinks();
326  dragged.Unmark();
327 
328  lockV = dragged.CLine().NearestPoint( aP );
329 
330  if( Settings().GetOptimizeDraggedTrack() )
331  {
332  OPTIMIZER::Optimize( &dragged,
334  m_lastNode, lockV );
335  }
336 
337  m_lastNode->Add( dragged );
339  m_draggedItems.Add( dragged );
340 }
341 
342 
344 {
345  bool ok = false;
346 // fixme: rewrite using shared_ptr...
347  if( m_lastNode )
348  {
349  delete m_lastNode;
350  m_lastNode = nullptr;
351  }
352 
354 
355  switch( m_mode )
356  {
357  case DM_SEGMENT:
358  case DM_CORNER:
359  {
360  int thresh = Settings().SmoothDraggedSegments() ? m_draggedLine.Width() / 4 : 0;
361  LINE dragged( m_draggedLine );
362  LINE origLine( m_draggedLine );
363 
364  if( m_mode == DM_SEGMENT )
365  dragged.DragSegment( aP, m_draggedSegmentIndex, false );
366  else
367  dragged.DragCorner( aP, m_draggedSegmentIndex, thresh );
368 
369  if ( m_world->CheckColliding( &dragged ) )
370  {
371  WALKAROUND walkaround( m_lastNode, Router() );
372 
373  walkaround.SetSolidsOnly( false );
374  walkaround.SetDebugDecorator( Dbg() );
375  walkaround.SetLogger( Logger() );
376  walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
377 
378  WALKAROUND::RESULT wr = walkaround.Route( dragged );
379 
380  //Dbg()->AddLine( wr.lineCw.CLine(), 3, 200000 );
381  //Dbg()->AddLine( wr.lineCcw.CLine(), 2, 200000 );
382 
384  {
385  dragged = ( wr.lineCw.CLine().Length() < wr.lineCcw.CLine().Length() ? wr.lineCw : wr.lineCcw );
386  ok = true;
387  }
388  else if ( wr.statusCw == WALKAROUND::DONE )
389  {
390  dragged = wr.lineCw;
391  ok = true;
392  }
393  else if ( wr.statusCcw == WALKAROUND::DONE )
394  {
395  dragged = wr.lineCcw;
396  ok = true;
397  }
398 
399  }
400  else
401  {
402  ok = true;
403  }
404 
405  if(ok)
406  {
407  m_lastNode->Remove( origLine );
408  optimizeAndUpdateDraggedLine( dragged, aP );
409  }
410  break;
411  }
412  case DM_VIA: // fixme...
413  {
415 
416  break;
417  }
418  }
419 
420  m_dragStatus = ok;
421 
422  return true;
423 }
424 
425 bool DRAGGER::dragShove( const VECTOR2I& aP )
426 {
427  bool ok = false;
428 
429  if( m_lastNode )
430  {
431  delete m_lastNode;
432  m_lastNode = NULL;
433  }
434 
435  switch( m_mode )
436  {
437  case DM_SEGMENT:
438  case DM_CORNER:
439  {
440  //TODO: Make threshhold configurable
441  int thresh = Settings().SmoothDraggedSegments() ? m_draggedLine.Width() / 2 : 0;
442  LINE dragged( m_draggedLine );
443  dragged.SetSnapThreshhold( thresh );
444 
445  if( m_mode == DM_SEGMENT )
446  dragged.DragSegment( aP, m_draggedSegmentIndex );
447  else
448  dragged.DragCorner( aP, m_draggedSegmentIndex );
449 
450  SHOVE::SHOVE_STATUS st = m_shove->ShoveLines( dragged );
451 
452  if( st == SHOVE::SH_OK )
453  ok = true;
454  else if( st == SHOVE::SH_HEAD_MODIFIED )
455  {
456  dragged = m_shove->NewHead();
457  ok = true;
458  }
459 
460  m_lastNode = m_shove->CurrentNode()->Branch();
461 
462  if( ok )
463  {
464  VECTOR2D lockV;
465  dragged.ClearSegmentLinks();
466  dragged.Unmark();
467 
468  lockV = dragged.CLine().NearestPoint( aP );
469 
470  if( Settings().GetOptimizeDraggedTrack() )
471  {
475  }
476 
477  m_lastNode->Add( dragged );
479  m_draggedItems.Add( dragged );
480  }
481 
482  break;
483  }
484 
485  case DM_VIA:
486  {
487  VIA_HANDLE newVia;
488 
489  SHOVE::SHOVE_STATUS st = m_shove->ShoveDraggingVia( m_draggedVia, aP, newVia );
490 
491  if( st == SHOVE::SH_OK || st == SHOVE::SH_HEAD_MODIFIED )
492  ok = true;
493 
494  m_lastNode = m_shove->CurrentNode()->Branch();
495 
496  if( newVia.valid )
497  m_draggedVia = newVia;
498 
500  break;
501  }
502  }
503 
504  m_dragStatus = ok;
505 
506  return ok;
507 }
508 
509 
511 {
512  NODE* node = CurrentNode();
513 
514  if( node )
515  {
516  // Collisions still prevent fixing unless "Allow DRC violations" is checked
517  if( !m_dragStatus )
518  return false;
519 
520  Router()->CommitRouting( node );
521  return true;
522  }
523 
524  return false;
525 }
526 
527 
528 bool DRAGGER::Drag( const VECTOR2I& aP )
529 {
530  if( m_freeAngleMode )
531  return dragMarkObstacles( aP );
532 
533  switch( m_currentMode )
534  {
535  case RM_MarkObstacles:
536  return dragMarkObstacles( aP );
537 
538  case RM_Shove:
539  case RM_Smart:
540  return dragShove( aP );
541 
542  case RM_Walkaround:
543  return dragWalkaround( aP );
544 
545  default:
546  return false;
547  }
548 }
549 
550 
552 {
553  return m_lastNode;
554 }
555 
556 
558 {
559  return m_draggedItems;
560 }
561 
562 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
int Find(const VECTOR2I &aP) const
Function Find()
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:144
ITEM.
Definition: pns_item.h:53
ITEM_SET m_draggedItems
If true, moves the connection lines without maintaining 45° corners.
Definition: pns_dragger.h:124
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:51
long long int Length() const
Function Length()
bool Drag(const VECTOR2I &aP) override
Function Drag()
bool Empty() const
Definition: pns_itemset.h:135
NODE.
Definition: pns_node.h:145
void DragSegment(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:595
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:116
DRAGGER(ROUTER *aRouter)
Definition: pns_dragger.cpp:32
void CommitRouting()
Definition: pns_router.cpp:422
std::unique_ptr< SHOVE > m_shove
Definition: pns_dragger.h:117
DRAG_ALGO.
Definition: pns_drag_algo.h:42
Ignore collisions, mark obstacles
int Width() const override
Definition: pns_segment.h:78
WALKAROUND_STATUS statusCw
ENTRIES & Items()
Definition: pns_itemset.h:140
bool m_dragStatus
Definition: pns_dragger.h:119
virtual void Unmark(int aMarker=-1)
Definition: pns_item.h:220
virtual LOGGER * Logger()
Returns the logger object, allowing to dump geometry to a file.
bool startDragSegment(const VECTOR2D &aP, SEGMENT *aSeg)
Definition: pns_dragger.cpp:50
VIA_HANDLE m_draggedVia
Definition: pns_dragger.h:110
virtual bool Start(const VECTOR2I &aP, ITEM_SET &aPrimitives) override
Function Start()
LINE m_draggedLine
Definition: pns_dragger.h:114
const ITEM_SET Traces() override
Function Traces()
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
NODE * CurrentNode() const override
Function CurrentNode()
bool startDragArc(const VECTOR2D &aP, ARC *aArc)
Definition: pns_dragger.cpp:92
const SEG & Seg() const
Definition: pns_segment.h:83
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
bool startDragVia(VIA *aVia)
void dragViaWalkaround(const VIA_HANDLE &aHandle, NODE *aNode, const VECTOR2I &aP)
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
int Start() const
Definition: pns_layerset.h:83
ROUTING_SETTINGS & Settings() const
Returns current router settings
void optimizeAndUpdateDraggedLine(LINE &dragged, const VECTOR2I &aP)
JOINT.
Definition: pns_joint.h:43
void Reverse()
Reverses the point/vertex order
Definition: pns_line.cpp:851
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
#define NULL
int m_draggedSegmentIndex
Definition: pns_dragger.h:118
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
a quick shortcut to optmize a line without creating and setting up an optimizer
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:77
bool SmoothDraggedSegments() const
Returns true if smoothing segments durign dragging is enabled.
PNS_MODE Mode() const
Returns the routing mode.
void SetSolidsOnly(bool aSolidsOnly)
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:196
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
NODE * m_lastNode
Definition: pns_dragger.h:112
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:583
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:271
void dragViaMarkObstacles(const VIA_HANDLE &aHandle, NODE *aNode, const VECTOR2I &aP)
bool FixRoute() override
Function FixRoute()
Only walkaround
const ITEM_SET findViaFanoutByHandle(NODE *aNode, const VIA_HANDLE &handle)
bool dragWalkaround(const VECTOR2I &aP)
void ClearSegmentLinks()
Erases the linking information. Used to detach the line from the owning node.
Definition: pns_line.cpp:936
bool dragShove(const VECTOR2I &aP)
PNS_MODE m_currentMode
Definition: pns_dragger.h:120
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
WALKAROUND_STATUS statusCcw
LAYER_RANGE layers
Definition: pns_via.h:44
VECTOR2I A
Definition: seg.h:47
VIA_HANDLE m_initialVia
Definition: pns_dragger.h:109
int Width() const
Returns line width
Definition: pns_line.h:187
bool dragMarkObstacles(const VECTOR2I &aP)
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Function SetDebugDecorator.
Definition: pns_algo_base.h:72
VECTOR2I pos
Definition: pns_via.h:43
PnsKind Kind() const
Function Kind()
Definition: pns_item.h:123
bool m_freeAngleMode
Definition: pns_dragger.h:127
Push and Shove diff pair dimensions (gap) settings dialog.
void SetLogger(LOGGER *aLogger)
Definition: pns_algo_base.h:62
void SetMode(int aDragMode) override
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
virtual void Unmark(int aMarker=-1) override
Definition: pns_line.cpp:98
void SetIterationLimit(const int aIterLimit)
void SetSnapThreshhold(int aThreshhold)
Definition: pns_line.h:301
VECTOR2I B
Definition: seg.h:48