Horizon
Loading...
Searching...
No Matches
pns_node.h
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 <tomasz.wlostowski@cern.ch>
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 <unordered_map>
30#include <core/minoptmax.h>
31
32#include <geometry/shape_line_chain.h>
33#include <geometry/shape_index.h>
34
35#include "pns_item.h"
36#include "pns_joint.h"
37#include "pns_itemset.h"
38
39namespace PNS {
40
41class ARC;
42class SEGMENT;
43class LINE;
44class SOLID;
45class VIA;
46class INDEX;
47class ROUTER;
48class NODE;
49
55enum class CONSTRAINT_TYPE
56{
57 CT_CLEARANCE = 1,
58 CT_DIFF_PAIR_GAP = 2,
59 CT_LENGTH = 3,
60 CT_WIDTH = 4,
61 CT_VIA_DIAMETER = 5,
62 CT_VIA_HOLE = 6,
63 CT_HOLE_CLEARANCE = 7,
64 CT_EDGE_CLEARANCE = 8,
65 CT_HOLE_TO_HOLE = 9
66};
67
69{
70 CONSTRAINT_TYPE m_Type;
71 MINOPTMAX<int> m_Value;
72 bool m_Allowed;
73 wxString m_RuleName;
74 wxString m_FromName;
75 wxString m_ToName;
76};
77
79{
80public:
81 virtual ~RULE_RESOLVER() {}
82
83 virtual int Clearance( const ITEM* aA, const ITEM* aB ) = 0;
84 virtual int HoleClearance( const ITEM* aA, const ITEM* aB ) = 0;
85 virtual int HoleToHoleClearance( const ITEM* aA, const ITEM* aB ) = 0;
86
87 virtual int DpCoupledNet( int aNet ) = 0;
88 virtual int DpNetPolarity( int aNet ) = 0;
89 virtual bool DpNetPair( const ITEM* aItem, int& aNetP, int& aNetN ) = 0;
90
91 virtual bool IsDiffPair( const ITEM* aA, const ITEM* aB ) = 0;
92
93 virtual bool QueryConstraint( CONSTRAINT_TYPE aType, const PNS::ITEM* aItemA,
94 const PNS::ITEM* aItemB, int aLayer,
95 PNS::CONSTRAINT* aConstraint ) = 0;
96
97 virtual wxString NetName( int aNet ) = 0;
98
99 virtual void ClearCacheForItem( const ITEM* aItem ) {}
100};
101
114
116{
117public:
118 OBSTACLE_VISITOR( const ITEM* aItem );
119
120 virtual ~OBSTACLE_VISITOR()
121 {
122 }
123
124 void SetWorld( const NODE* aNode, const NODE* aOverride = nullptr );
125
126 virtual bool operator()( ITEM* aCandidate ) = 0;
127
128protected:
129 bool visit( ITEM* aCandidate );
130
131protected:
132 const ITEM* m_item;
133
134 const NODE* m_node;
136};
137
147class NODE
148{
149public:
150 typedef std::optional<OBSTACLE> OPT_OBSTACLE;
151 typedef std::vector<ITEM*> ITEM_VECTOR;
152 typedef std::vector<OBSTACLE> OBSTACLES;
153
154 NODE();
155 ~NODE();
156
158 int GetClearance( const ITEM* aA, const ITEM* aB ) const;
159 int GetHoleClearance( const ITEM* aA, const ITEM* aB ) const;
160 int GetHoleToHoleClearance( const ITEM* aA, const ITEM* aB ) const;
161
163 int GetMaxClearance() const
164 {
165 return m_maxClearance;
166 }
167
169 void SetMaxClearance( int aClearance )
170 {
171 m_maxClearance = aClearance;
172 }
173
175 void SetRuleResolver( RULE_RESOLVER* aFunc )
176 {
177 m_ruleResolver = aFunc;
178 }
179
181 {
182 return m_ruleResolver;
183 }
184
186 int JointCount() const
187 {
188 return m_joints.size();
189 }
190
192 int Depth() const
193 {
194 return m_depth;
195 }
196
206 int QueryColliding( const ITEM* aItem, OBSTACLES& aObstacles, int aKindMask = ITEM::ANY_T,
207 int aLimitCount = -1, bool aDifferentNetsOnly = true );
208
209 int QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints,
210 LAYER_RANGE aLayerMask = LAYER_RANGE::All(), int aKindMask = ITEM::ANY_T );
211
220 OPT_OBSTACLE NearestObstacle( const LINE* aLine, int aKindMask = ITEM::ANY_T,
221 const std::set<ITEM*>* aRestrictedSet = nullptr );
222
231 OPT_OBSTACLE CheckColliding( const ITEM* aItem, int aKindMask = ITEM::ANY_T );
232
233
242 OPT_OBSTACLE CheckColliding( const ITEM_SET& aSet, int aKindMask = ITEM::ANY_T );
243
250 const ITEM_SET HitTest( const VECTOR2I& aPoint ) const;
251
260 bool Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant = false );
261 void Add( std::unique_ptr< SOLID > aSolid );
262 void Add( std::unique_ptr< VIA > aVia );
263 bool Add( std::unique_ptr< ARC > aArc, bool aAllowRedundant = false );
264
265 void Add( LINE& aLine, bool aAllowRedundant = false );
266
270 void Remove( ARC* aArc );
271 void Remove( SOLID* aSolid );
272 void Remove( VIA* aVia );
273 void Remove( SEGMENT* aSegment );
274 void Remove( ITEM* aItem );
275
281 void Remove( LINE& aLine );
282
289 void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
290 void Replace( LINE& aOldLine, LINE& aNewLine );
291
300 NODE* Branch();
301
313 const LINE AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex = nullptr,
314 bool aStopAtLockedJoints = false,
315 bool aFollowLockedSegments = false );
316
318 void Dump( bool aLong = false );
319
326 void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
327
336 void Commit( NODE* aNode );
337
343 JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, int aNet );
344
345 void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
346
352 JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem )
353 {
354 return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
355 }
356
358 int FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines );
359
361 void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
362
364 void KillChildren();
365
366 void AllItemsInNet( int aNet, std::set<ITEM*>& aItems, int aKindMask = -1 );
367
368 void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION | MK_HOLE );
369
370 void RemoveByMarker( int aMarker );
371
372 ITEM* FindItemByParent( const class PNS_HORIZON_PARENT_ITEM* aParent, int net);
373
374 bool HasChildren() const
375 {
376 return !m_children.empty();
377 }
378
380 {
381 return m_parent;
382 }
383
385 bool Overrides( ITEM* aItem ) const
386 {
387 return m_override.find( aItem ) != m_override.end();
388 }
389
390 void FixupVirtualVias();
391
392private:
393 void Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant = false );
394
396 NODE( const NODE& aB );
397 NODE& operator=( const NODE& aB );
398
400 JOINT& touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet );
401
403 void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
404
406 void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
407
409 void addSolid( SOLID* aSeg );
410 void addSegment( SEGMENT* aSeg );
411 void addVia( VIA* aVia );
412 void addArc( ARC* aVia );
413
414 void removeSolidIndex( SOLID* aSeg );
415 void removeSegmentIndex( SEGMENT* aSeg );
416 void removeViaIndex( VIA* aVia );
417 void removeArcIndex( ARC* aVia );
418
419 void doRemove( ITEM* aItem );
420 void unlinkParent();
421 void releaseChildren();
422 void releaseGarbage();
423 void rebuildJoint( JOINT* aJoint, ITEM* aItem );
424
425 bool isRoot() const
426 {
427 return m_parent == nullptr;
428 }
429
430 SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr,
431 int aNet );
432 SEGMENT* findRedundantSegment( SEGMENT* aSeg );
433
434 ARC* findRedundantArc( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr, int aNet );
435 ARC* findRedundantArc( ARC* aSeg );
436
438 void followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
439 VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
440 bool& aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments );
441
442private:
443 struct DEFAULT_OBSTACLE_VISITOR;
444 typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> JOINT_MAP;
445 typedef JOINT_MAP::value_type TagJointPair;
446
447 JOINT_MAP m_joints;
449
450 NODE* m_parent;
451 NODE* m_root;
452 std::set<NODE*> m_children;
453
454 std::unordered_set<ITEM*> m_override;
456
457 int m_maxClearance;
458 RULE_RESOLVER* m_ruleResolver;
459 INDEX* m_index;
460 int m_depth;
462
463 std::unordered_set<ITEM*> m_garbageItems;
464};
465
466}
467
468#endif
Represent a contiguous set of PCB layers.
Definition pns_layerset.h:32
Definition minoptmax.h:31
Base class for PNS router board items.
Definition pns_item.h:57
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:43
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:61
Keep the router "world" - i.e.
Definition pns_node.h:148
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition pns_node.cpp:138
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:1037
NODE * GetParent() const
Check if this branch contains an updated version of the m_item from the root branch.
Definition pns_node.h:379
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition pns_node.cpp:803
int GetMaxClearance() const
Set the worst-case clearance between any pair of items.
Definition pns_node.h:163
void SetMaxClearance(int aClearance)
Assign a clearance resolution function object.
Definition pns_node.h:169
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:1345
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:451
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:267
JOINT * FindJoint(const VECTOR2I &aPos, const ITEM *aItem)
Search for a joint at a given position, linked to given item.
Definition pns_node.h:352
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition pns_node.cpp:1030
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition pns_node.h:180
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:126
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition pns_node.cpp:639
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition pns_node.h:186
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:297
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:1142
void Remove(ARC *aArc)
Remove an item from this branch.
Definition pns_node.cpp:838
void Commit(NODE *aNode)
Apply the changes from a given branch (aNode) to the root branch.
Definition pns_node.cpp:1392
~NODE()
Return the expected clearance between items a and b.
Definition pns_node.cpp:69
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition pns_node.cpp:948
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition pns_node.cpp:518
Definition pns_node.h:116
const NODE * m_node
node we are searching in (either root or a branch)
Definition pns_node.h:134
const ITEM * m_item
the item we are looking for collisions with
Definition pns_node.h:132
const NODE * m_override
node that overrides root entries
Definition pns_node.h:135
Definition pns_horizon_iface.hpp:29
Definition pns_node.h:79
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Definition shape_line_chain.h:81
Definition wx_compat.h:13
Definition pns_node.h:69
Hold an object colliding with another object, along with some useful data about the collision.
Definition pns_node.h:106
int m_distFirst
... and the distance thereof
Definition pns_node.h:112
VECTOR2I m_ipFirst
First intersection between m_head and m_hull.
Definition pns_node.h:111
ITEM * m_item
Item found to be colliding with m_head.
Definition pns_node.h:109
const ITEM * m_head
Item we search collisions with.
Definition pns_node.h:107
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item.
Definition pns_node.h:110