KiCad PCB EDA Suite
pns_node.h
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-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Tomasz Wlostowski <[email protected]>
8  *
9  * This program is free software: you can redistribute it and/or modify it
10  * under the terms of the GNU General Public License as published by the
11  * Free Software Foundation, either version 3 of the License, or (at your
12  * option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful, but
15  * WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  * General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License along
20  * with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #ifndef __PNS_NODE_H
24 #define __PNS_NODE_H
25 
26 #include <vector>
27 #include <list>
28 #include <unordered_set>
29 #include <core/minoptmax.h>
30 
32 #include <geometry/shape_index.h>
33 
34 #include "pns_item.h"
35 #include "pns_joint.h"
36 #include "pns_itemset.h"
37 
38 namespace PNS {
39 
40 class ARC;
41 class SEGMENT;
42 class LINE;
43 class SOLID;
44 class VIA;
45 class INDEX;
46 class ROUTER;
47 class NODE;
48 
54 enum class CONSTRAINT_TYPE
55 {
56  CT_CLEARANCE = 1,
57  CT_DIFF_PAIR_GAP = 2,
58  CT_LENGTH = 3,
59  CT_WIDTH = 4,
60  CT_VIA_DIAMETER = 5,
61  CT_VIA_HOLE = 6,
64  CT_HOLE_TO_HOLE = 9
65 };
66 
67 struct CONSTRAINT
68 {
71  bool m_Allowed;
72  wxString m_RuleName;
73  wxString m_FromName;
74  wxString m_ToName;
75 };
76 
78 {
79 public:
80  virtual ~RULE_RESOLVER() {}
81 
82  virtual int Clearance( const ITEM* aA, const ITEM* aB ) = 0;
83  virtual int HoleClearance( const ITEM* aA, const ITEM* aB ) = 0;
84  virtual int HoleToHoleClearance( const ITEM* aA, const ITEM* aB ) = 0;
85 
86  virtual int DpCoupledNet( int aNet ) = 0;
87  virtual int DpNetPolarity( int aNet ) = 0;
88  virtual bool DpNetPair( const ITEM* aItem, int& aNetP, int& aNetN ) = 0;
89 
90  virtual bool IsDiffPair( const ITEM* aA, const ITEM* aB ) = 0;
91 
92  virtual bool QueryConstraint( CONSTRAINT_TYPE aType, const PNS::ITEM* aItemA,
93  const PNS::ITEM* aItemB, int aLayer,
94  PNS::CONSTRAINT* aConstraint ) = 0;
95 
96  virtual wxString NetName( int aNet ) = 0;
97 };
98 
102 struct OBSTACLE
103 {
104  const ITEM* m_head;
105 
110 };
111 
113 {
114 public:
115  OBSTACLE_VISITOR( const ITEM* aItem );
116 
118  {
119  }
120 
121  void SetWorld( const NODE* aNode, const NODE* aOverride = nullptr );
122 
123  virtual bool operator()( ITEM* aCandidate ) = 0;
124 
125 protected:
126  bool visit( ITEM* aCandidate );
127 
128 protected:
129  const ITEM* m_item;
130 
131  const NODE* m_node;
132  const NODE* m_override;
133 };
134 
144 class NODE
145 {
146 public:
148  typedef std::vector<ITEM*> ITEM_VECTOR;
149  typedef std::vector<OBSTACLE> OBSTACLES;
150 
151  NODE();
152  ~NODE();
153 
155  int GetClearance( const ITEM* aA, const ITEM* aB ) const;
156  int GetHoleClearance( const ITEM* aA, const ITEM* aB ) const;
157  int GetHoleToHoleClearance( const ITEM* aA, const ITEM* aB ) const;
158 
160  int GetMaxClearance() const
161  {
162  return m_maxClearance;
163  }
164 
166  void SetMaxClearance( int aClearance )
167  {
168  m_maxClearance = aClearance;
169  }
170 
173  {
174  m_ruleResolver = aFunc;
175  }
176 
178  {
179  return m_ruleResolver;
180  }
181 
183  int JointCount() const
184  {
185  return m_joints.size();
186  }
187 
189  int Depth() const
190  {
191  return m_depth;
192  }
193 
203  int QueryColliding( const ITEM* aItem, OBSTACLES& aObstacles, int aKindMask = ITEM::ANY_T,
204  int aLimitCount = -1, bool aDifferentNetsOnly = true );
205 
206  int QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints,
207  LAYER_RANGE aLayerMask = LAYER_RANGE::All(), int aKindMask = ITEM::ANY_T );
208 
217  OPT_OBSTACLE NearestObstacle( const LINE* aLine, int aKindMask = ITEM::ANY_T,
218  const std::set<ITEM*>* aRestrictedSet = nullptr );
219 
228  OPT_OBSTACLE CheckColliding( const ITEM* aItem, int aKindMask = ITEM::ANY_T );
229 
230 
239  OPT_OBSTACLE CheckColliding( const ITEM_SET& aSet, int aKindMask = ITEM::ANY_T );
240 
247  const ITEM_SET HitTest( const VECTOR2I& aPoint ) const;
248 
257  bool Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant = false );
258  void Add( std::unique_ptr< SOLID > aSolid );
259  void Add( std::unique_ptr< VIA > aVia );
260  bool Add( std::unique_ptr< ARC > aArc, bool aAllowRedundant = false );
261 
262  void Add( LINE& aLine, bool aAllowRedundant = false );
263 
267  void Remove( ARC* aArc );
268  void Remove( SOLID* aSolid );
269  void Remove( VIA* aVia );
270  void Remove( SEGMENT* aSegment );
271  void Remove( ITEM* aItem );
272 
278  void Remove( LINE& aLine );
279 
286  void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
287  void Replace( LINE& aOldLine, LINE& aNewLine );
288 
297  NODE* Branch();
298 
307  const LINE AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex = nullptr,
308  bool aStopAtLockedJoints = false );
309 
311  void Dump( bool aLong = false );
312 
319  void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
320 
329  void Commit( NODE* aNode );
330 
336  JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, int aNet );
337 
338  void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
339 
345  JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem )
346  {
347  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
348  }
349 
351  int FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines );
352 
354  void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
355 
357  void KillChildren();
358 
359  void AllItemsInNet( int aNet, std::set<ITEM*>& aItems, int aKindMask = -1 );
360 
361  void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION | MK_HOLE );
362 
363  void RemoveByMarker( int aMarker );
364 
365  ITEM* FindItemByParent( const BOARD_ITEM* aParent );
366 
367  bool HasChildren() const
368  {
369  return !m_children.empty();
370  }
371 
372  NODE* GetParent() const
373  {
374  return m_parent;
375  }
376 
378  bool Overrides( ITEM* aItem ) const
379  {
380  return m_override.find( aItem ) != m_override.end();
381  }
382 
383  void FixupVirtualVias();
384 
385 private:
386  void Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant = false );
387 
389  NODE( const NODE& aB );
390  NODE& operator=( const NODE& aB );
391 
393  JOINT& touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet );
394 
396  void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
397 
399  void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
400 
402  void addSolid( SOLID* aSeg );
403  void addSegment( SEGMENT* aSeg );
404  void addVia( VIA* aVia );
405  void addArc( ARC* aVia );
406 
407  void removeSolidIndex( SOLID* aSeg );
408  void removeSegmentIndex( SEGMENT* aSeg );
409  void removeViaIndex( VIA* aVia );
410  void removeArcIndex( ARC* aVia );
411 
412  void doRemove( ITEM* aItem );
413  void unlinkParent();
414  void releaseChildren();
415  void releaseGarbage();
416  void rebuildJoint( JOINT* aJoint, ITEM* aItem );
417 
418  bool isRoot() const
419  {
420  return m_parent == nullptr;
421  }
422 
423  SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr,
424  int aNet );
426 
427  ARC* findRedundantArc( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr, int aNet );
428  ARC* findRedundantArc( ARC* aSeg );
429 
431  void followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
432  VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
433  bool& aGuardHit, bool aStopAtLockedJoints );
434 
435 private:
437  typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> JOINT_MAP;
438  typedef JOINT_MAP::value_type TagJointPair;
439 
441 
445  std::set<NODE*> m_children;
446 
447  std::unordered_set<ITEM*> m_override;
448 
453  int m_depth;
454 
456  std::unordered_set<ITEM*> m_garbageItems;
457 };
458 
459 }
460 
461 #endif
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1440
Base class for PNS router board items.
Definition: pns_item.h:55
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:445
ITEM * m_item
Item found to be colliding with m_head.
Definition: pns_node.h:106
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:131
Keep the router "world" - i.e.
Definition: pns_node.h:144
virtual ~RULE_RESOLVER()
Definition: pns_node.h:80
int GetHoleToHoleClearance(const ITEM *aA, const ITEM *aB) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:125
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:49
void releaseChildren()
Definition: pns_node.cpp:1357
virtual bool QueryConstraint(CONSTRAINT_TYPE aType, const PNS::ITEM *aItemA, const PNS::ITEM *aItemB, int aLayer, PNS::CONSTRAINT *aConstraint)=0
virtual int DpCoupledNet(int aNet)=0
void unlinkParent()
Definition: pns_node.cpp:173
int m_distFirst
... and the distance thereof
Definition: pns_node.h:109
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1028
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:701
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:722
bool HasChildren() const
Definition: pns_node.h:367
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:183
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
Definition: pns_node.cpp:1035
wxString m_RuleName
Definition: pns_node.h:72
virtual int Clearance(const ITEM *aA, const ITEM *aB)=0
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
int Depth() const
Definition: pns_node.h:189
bool Overrides(ITEM *aItem) const
Definition: pns_node.h:378
virtual bool operator()(ITEM *aCandidate)=0
void SetRuleResolver(RULE_RESOLVER *aFunc)
Definition: pns_node.h:172
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1239
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:113
void Commit(NODE *aNode)
Apply the changes from a given branch (aNode) to the root branch.
Definition: pns_node.cpp:1385
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1247
bool isRoot() const
Definition: pns_node.h:418
virtual ~OBSTACLE_VISITOR()
Definition: pns_node.h:117
static LAYER_RANGE All()
Definition: pns_layerset.h:109
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
int Start() const
Definition: pns_layerset.h:82
void SetMaxClearance(int aClearance)
Assign a clearance resolution function object.
Definition: pns_node.h:166
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:629
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:453
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:42
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:451
void addSolid(SOLID *aSeg)
Definition: pns_node.cpp:546
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:101
void KillChildren()
Definition: pns_node.cpp:1405
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:736
std::unordered_multimap< JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH > JOINT_MAP
Definition: pns_node.h:436
ITEM * FindItemByParent(const BOARD_ITEM *aParent)
Definition: pns_node.cpp:1573
int Net() const
Definition: pns_item.h:150
JOINT * FindJoint(const VECTOR2I &aPos, const ITEM *aItem)
Search for a joint at a given position, linked to given item.
Definition: pns_node.h:345
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1465
virtual int HoleClearance(const ITEM *aA, const ITEM *aB)=0
OBSTACLE_VISITOR(const ITEM *aItem)
Definition: pns_node.cpp:182
void FixupVirtualVias()
Definition: pns_node.cpp:1069
bool visit(ITEM *aCandidate)
Definition: pns_node.cpp:197
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:447
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1535
wxString m_FromName
Definition: pns_node.h:73
virtual int HoleToHoleClearance(const ITEM *aA, const ITEM *aB)=0
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:129
void releaseGarbage()
Definition: pns_node.cpp:1370
void addVia(VIA *aVia)
Definition: pns_node.cpp:562
void SetWorld(const NODE *aNode, const NODE *aOverride=nullptr)
Definition: pns_node.cpp:190
~NODE()
Return the expected clearance between items a and b.
Definition: pns_node.cpp:68
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1500
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition: pns_node.cpp:517
void addArc(ARC *aVia)
Definition: pns_node.cpp:656
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true)
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:266
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:296
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item.
Definition: pns_node.h:107
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1140
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:177
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:801
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1450
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:789
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:438
void Dump(bool aLong=false)
Definition: pns_node.cpp:1256
NODE * GetParent() const
Check if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:372
Represent a polyline (an zero-thickness chain of connected line segments).
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1411
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:450
int GetMaxClearance() const
Set the worst-case clearance between any pair of items.
Definition: pns_node.h:160
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
Touch a joint and links it to an m_item.
Definition: pns_node.cpp:1177
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:456
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:781
void followLine(LINKED_ITEM *aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool *aArcReversed, bool &aGuardHit, bool aStopAtLockedJoints)
Definition: pns_node.cpp:897
const ITEM * m_head
Item we search collisions with.
Definition: pns_node.h:104
boost::optional< T > OPT
Definition: optional.h:7
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1338
void removeArcIndex(ARC *aVia)
Definition: pns_node.cpp:729
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
virtual int DpNetPolarity(int aNet)=0
virtual wxString NetName(int aNet)=0
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:450
MINOPTMAX< int > m_Value
Definition: pns_node.h:70
virtual bool DpNetPair(const ITEM *aItem, int &aNetP, int &aNetN)=0
wxString m_ToName
Definition: pns_node.h:74
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:440
VECTOR2I m_ipFirst
First intersection between m_head and m_hull.
Definition: pns_node.h:108
virtual bool IsDiffPair(const ITEM *aA, const ITEM *aB)=0
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:149
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:132
Push and Shove diff pair dimensions (gap) settings dialog.
NODE * m_parent
node this node was branched from
Definition: pns_node.h:443
NODE & operator=(const NODE &aB)
Try to find matching joint and creates a new one if not found.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
CONSTRAINT_TYPE m_Type
Definition: pns_node.h:69
INDEX.
Definition: pns_index.h:45
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:31
const LAYER_RANGE & Layers() const
Definition: pns_item.h:152
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1170
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:148
CONSTRAINT_TYPE
An abstract function object, returning a design rule (clearance, diff pair gap, etc) required between...
Definition: pns_node.h:54
bool m_Allowed
Definition: pns_node.h:71
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:102