KiCad PCB EDA Suite
Loading...
Searching...
No Matches
drc_test_provider_sliver_checker.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2021-2024 KiCad Developers.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, you may find one here:
18 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
19 * or you may search the http://www.gnu.org website for the version 2 license,
20 * or you may write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22 */
23
24#include <atomic>
25#include <board.h>
27#include <zone.h>
28#include <footprint.h>
29#include <pcb_shape.h>
31#include <drc/drc_rule.h>
32#include <drc/drc_item.h>
34#include <advanced_config.h>
35#include <progress_reporter.h>
36#include <core/thread_pool.h>
37
38/*
39 Checks for slivers in copper layers
40
41 Errors generated:
42 - DRCE_COPPER_SLIVER
43*/
44
46{
47public:
49 {
50 }
51
53 {
54 }
55
56 virtual bool Run() override;
57
58 virtual const wxString GetName() const override
59 {
60 return wxT( "sliver checker" );
61 };
62
63 virtual const wxString GetDescription() const override
64 {
65 return wxT( "Checks copper layers for slivers" );
66 }
67
68private:
69 wxString layerDesc( PCB_LAYER_ID aLayer );
70};
71
72
74{
75 return wxString::Format( wxT( "(%s)" ), m_drcEngine->GetBoard()->GetLayerName( aLayer ) );
76}
77
78
80{
82 return true; // Continue with other tests
83
84 if( !reportPhase( _( "Running sliver detection on copper layers..." ) ) )
85 return false; // DRC cancelled
86
87 int64_t widthTolerance = pcbIUScale.mmToIU( ADVANCED_CFG::GetCfg().m_SliverWidthTolerance );
88 int64_t squared_width = widthTolerance * widthTolerance;
89
90 double angleTolerance = ADVANCED_CFG::GetCfg().m_SliverAngleTolerance;
91 double cosangleTol = 2.0 * cos( DEG2RAD( angleTolerance ) );
92 LSET copperLayerSet = m_drcEngine->GetBoard()->GetEnabledLayers() & LSET::AllCuMask();
93 LSEQ copperLayers = copperLayerSet.Seq();
94 int layerCount = copperLayers.size();
95
96 // Report progress on board zones only. Everything else is in the noise.
97 int zoneLayerCount = 0;
98 std::atomic<size_t> done( 1 );
99
100 for( PCB_LAYER_ID layer : copperLayers )
101 {
102 for( ZONE* zone : m_drcEngine->GetBoard()->Zones() )
103 {
104 if( !zone->GetIsRuleArea() && zone->IsOnLayer( layer ) )
105 zoneLayerCount++;
106 }
107 }
108
110
111 if( reporter && reporter->IsCancelled() )
112 return false; // DRC cancelled
113
114 std::vector<SHAPE_POLY_SET> layerPolys( layerCount );
115
116 auto build_layer_polys =
117 [&]( int layerIdx ) -> size_t
118 {
119 PCB_LAYER_ID layer = copperLayers[layerIdx];
120 SHAPE_POLY_SET& poly = layerPolys[layerIdx];
121
122 if( m_drcEngine->IsCancelled() )
123 return 0;
124
125 SHAPE_POLY_SET fill;
126
128 [&]( BOARD_ITEM* item ) -> bool
129 {
130 if( ZONE* zone = dynamic_cast<ZONE*>( item) )
131 {
132 if( !zone->GetIsRuleArea() )
133 {
134 fill = zone->GetFill( layer )->CloneDropTriangulation();
135 poly.Append( fill );
136
137 // Report progress on board zones only. Everything else is
138 // in the noise.
139 done.fetch_add( 1 );
140 }
141 }
142 else
143 {
144 item->TransformShapeToPolygon( poly, layer, 0, ARC_LOW_DEF,
145 ERROR_INSIDE );
146 }
147
148 if( m_drcEngine->IsCancelled() )
149 return false;
150
151 return true;
152 } );
153
154
155 if( m_drcEngine->IsCancelled() )
156 return 0;
157
159
160 return 1;
161 };
162
164 std::vector<std::future<size_t>> returns;
165
166 returns.reserve( copperLayers.size() );
167
168 for( size_t ii = 0; ii < copperLayers.size(); ++ii )
169 returns.emplace_back( tp.submit( build_layer_polys, ii ) );
170
171 for( const std::future<size_t>& ret : returns )
172 {
173 std::future_status status = ret.wait_for( std::chrono::milliseconds( 250 ) );
174
175 while( status != std::future_status::ready )
176 {
177 reportProgress( zoneLayerCount, done );
178 status = ret.wait_for( std::chrono::milliseconds( 250 ) );
179 }
180 }
181
182 for( int ii = 0; ii < layerCount; ++ii )
183 {
184 PCB_LAYER_ID layer = copperLayers[ii];
185 SHAPE_POLY_SET& poly = layerPolys[ii];
186
188 continue;
189
190 // Frequently, in filled areas, some points of the polygons are very near (dist is only
191 // a few internal units, like 2 or 3 units.
192 // We skip very small vertices: one cannot really compute a valid orientation of
193 // such a vertex
194 // So skip points near than min_len (in internal units).
195 const int min_len = pcbIUScale.mmToIU( ADVANCED_CFG::GetCfg().m_SliverMinimumLength );
196
197 for( int jj = 0; jj < poly.OutlineCount(); ++jj )
198 {
199 const std::vector<VECTOR2I>& pts = poly.Outline( jj ).CPoints();
200 int ptCount = pts.size();
201 int offset = 0;
202
203 auto area = [&]( const VECTOR2I& p, const VECTOR2I& q, const VECTOR2I& r ) -> VECTOR2I::extended_type
204 {
205 return static_cast<VECTOR2I::extended_type>( q.y - p.y ) * ( r.x - q.x ) -
206 static_cast<VECTOR2I::extended_type>( q.x - p.x ) * ( r.y - q.y );
207 };
208
209 auto isLocallyInside = [&]( int aA, int aB ) -> bool
210 {
211 int prev = ( ptCount + aA - 1 ) % ptCount;
212 int next = ( aA + 1 ) % ptCount;
213
214 if( area( pts[prev], pts[aA], pts[next] ) < 0 )
215 return area( pts[aA], pts[aB], pts[next] ) >= 0 && area( pts[aA], pts[prev], pts[aB] ) >= 0;
216 else
217 return area( pts[aA], pts[aB], pts[prev] ) < 0 || area( pts[aA], pts[next], pts[aB] ) < 0;
218 };
219
220 if( ptCount <= 5 )
221 continue;
222
223 for( int kk = 0; kk < ptCount; kk += offset )
224 {
225 int prior_index = ( ptCount + kk - 1 ) % ptCount;
226 int next_index = ( kk + 1 ) % ptCount;
227 VECTOR2I pt = pts[ kk ];
228 VECTOR2I ptPrior = pts[ prior_index ];
229 VECTOR2I vPrior = ( ptPrior - pt );
230 int forward_offset = 1;
231
232 offset = 1;
233
234 while( std::abs( vPrior.x ) < min_len && std::abs( vPrior.y ) < min_len
235 && offset < ptCount )
236 {
237 pt = pts[ ( kk + offset++ ) % ptCount ];
238 vPrior = ( ptPrior - pt );
239 }
240
241 if( offset >= ptCount )
242 break;
243
244 VECTOR2I ptAfter = pts[ next_index ];
245 VECTOR2I vAfter = ( ptAfter - pt );
246
247 while( std::abs( vAfter.x ) < min_len && std::abs( vAfter.y ) < min_len
248 && forward_offset < ptCount )
249 {
250 next_index = ( kk + forward_offset++ ) % ptCount;
251 ptAfter = pts[ next_index ];
252 vAfter = ( ptAfter - pt );
253 }
254
255 if( offset >= ptCount )
256 break;
257
258 // Negative dot product means that the angle is > 90°
259 if( vPrior.Dot( vAfter ) <= 0 )
260 continue;
261
262 if( !isLocallyInside( prior_index, next_index ) )
263 continue;
264
265 VECTOR2I vIncluded = ptAfter - ptPrior;
266 double arm1 = vPrior.SquaredEuclideanNorm();
267 double arm2 = vAfter.SquaredEuclideanNorm();
268 double opp = vIncluded.SquaredEuclideanNorm();
269
270 double cos_ang = std::abs( ( opp - arm1 - arm2 ) / ( std::sqrt( arm1 ) * std::sqrt( arm2 ) ) );
271
272 if( cos_ang > cosangleTol && 2.0 - cos_ang > std::numeric_limits<float>::epsilon() && opp > squared_width )
273 {
274 std::shared_ptr<DRC_ITEM> drce = DRC_ITEM::Create( DRCE_COPPER_SLIVER );
275 drce->SetErrorMessage( drce->GetErrorText() + wxS( " " ) + layerDesc( layer ) );
276 reportViolation( drce, pt, layer );
277 }
278 }
279 }
280 }
281
282 return true;
283}
284
285
286namespace detail
287{
289}
@ ERROR_INSIDE
Definition: approximation.h:34
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:108
constexpr int ARC_LOW_DEF
Definition: base_units.h:119
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:79
virtual void TransformShapeToPolygon(SHAPE_POLY_SET &aBuffer, PCB_LAYER_ID aLayer, int aClearance, int aError, ERROR_LOC aErrorLoc, bool ignoreLineWidth=false) const
Convert the item shape to a closed polygon.
Definition: board_item.cpp:255
LSET GetEnabledLayers() const
A proxy function that calls the corresponding function in m_BoardSettings.
Definition: board.cpp:775
const ZONES & Zones() const
Definition: board.h:335
const wxString GetLayerName(PCB_LAYER_ID aLayer) const
Return the name of a aLayer.
Definition: board.cpp:579
BOARD * GetBoard() const
Definition: drc_engine.h:99
bool IsErrorLimitExceeded(int error_code)
PROGRESS_REPORTER * GetProgressReporter() const
Definition: drc_engine.h:151
bool IsCancelled() const
static std::shared_ptr< DRC_ITEM > Create(int aErrorCode)
Constructs a DRC_ITEM for the given error code.
Definition: drc_item.cpp:372
virtual const wxString GetDescription() const override
virtual const wxString GetName() const override
virtual bool Run() override
Run this provider against the given PCB with configured options (if any).
Represent a DRC "provider" which runs some DRC functions over a BOARD and spits out DRC_ITEM and posi...
virtual bool reportPhase(const wxString &aStageName)
int forEachGeometryItem(const std::vector< KICAD_T > &aTypes, LSET aLayers, const std::function< bool(BOARD_ITEM *)> &aFunc)
virtual void reportViolation(std::shared_ptr< DRC_ITEM > &item, const VECTOR2I &aMarkerPos, int aMarkerLayer)
static std::vector< KICAD_T > s_allBasicItems
DRC_ENGINE * m_drcEngine
virtual bool reportProgress(size_t aCount, size_t aSize, size_t aDelta=1)
LSEQ is a sequence (and therefore also a set) of PCB_LAYER_IDs.
Definition: lseq.h:47
LSET is a set of PCB_LAYER_IDs.
Definition: lset.h:36
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Return a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:676
LSEQ Seq(const LSEQ &aSequence) const
Return an LSEQ from the union of this LSET and a desired sequence.
Definition: lset.cpp:410
A progress reporter interface for use in multi-threaded environments.
virtual bool IsCancelled() const =0
const std::vector< VECTOR2I > & CPoints() const
Represent a set of closed polygons.
void Simplify(POLYGON_MODE aFastMode)
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
SHAPE_LINE_CHAIN & Outline(int aIndex)
Return the reference to aIndex-th outline in the set.
int OutlineCount() const
Return the number of outlines in the set.
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:307
VECTOR2_TRAITS< int32_t >::extended_type extended_type
Definition: vector2d.h:73
constexpr extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:550
Handle a list of polygons defining a copper zone.
Definition: zone.h:73
@ DRCE_COPPER_SLIVER
Definition: drc_item.h:92
#define _(s)
double m_SliverAngleTolerance
Sliver angle to tolerance for DRC.
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:60
static DRC_REGISTER_TEST_PROVIDER< DRC_TEST_PROVIDER_ANNULAR_WIDTH > dummy
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:390
CITER next(CITER it)
Definition: ptree.cpp:126
constexpr int mmToIU(double mm) const
Definition: base_units.h:88
static thread_pool * tp
Definition: thread_pool.cpp:30
BS::thread_pool thread_pool
Definition: thread_pool.h:30
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
Definition: thread_pool.cpp:32
double DEG2RAD(double deg)
Definition: trigo.h:166