/* * This program source code file is part of KiCad, a free EDA CAD application. * * Copyright (C) 2017 Jean-Pierre Charras, jp.charras at wanadoo.fr * Copyright (C) 2015 SoftPLC Corporation, Dick Hollenbeck * Copyright The KiCad Developers, see AUTHORS.txt for contributors. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, you may find one here: * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html * or you may search the http://www.gnu.org website for the version 2 license, * or you may write to the Free Software Foundation, Inc., * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /** * Flag to enable debug tracing for the board outline creation * * Use "KICAD_BOARD_OUTLINE" to enable. * * @ingroup trace_env_vars */ const wxChar* traceBoardOutline = wxT( "KICAD_BOARD_OUTLINE" ); class SCOPED_FLAGS_CLEANER : public std::unordered_set { EDA_ITEM_FLAGS m_flagsToClear; public: SCOPED_FLAGS_CLEANER( const EDA_ITEM_FLAGS& aFlagsToClear ) : m_flagsToClear( aFlagsToClear ) {} ~SCOPED_FLAGS_CLEANER() { for( EDA_ITEM* item : *this ) item->ClearFlags( m_flagsToClear ); } }; /** * Local and tunable method of qualifying the proximity of two points. * * @param aLeft is the first point. * @param aRight is the second point. * @param aLimit is a measure of proximity that the caller knows about. * @return true if the two points are close enough, else false. */ static bool close_enough( VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit ) { return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit ); } /** * Local method which qualifies whether the start or end point of a segment is closest to a point. * * @param aRef is the reference point * @param aFirst is the first point * @param aSecond is the second point * @return true if the first point is closest to the reference, otherwise false. */ static bool closer_to_first( VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond ) { return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm(); } /** * Search for a #PCB_SHAPE matching a given end point or start point in a list. * * @param aShape The starting shape. * @param aPoint The starting or ending point to search for. * @param aList The list to remove from. * @param aLimit is the distance from \a aPoint that still constitutes a valid find. * @return The first #PCB_SHAPE that has a start or end point matching aPoint, otherwise nullptr. */ static PCB_SHAPE* findNext( PCB_SHAPE* aShape, const VECTOR2I& aPoint, const std::vector& aList, unsigned aLimit ) { // Look for an unused, exact hit for( PCB_SHAPE* graphic : aList ) { if( graphic == aShape || ( graphic->GetFlags() & SKIP_STRUCT ) != 0 ) continue; if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() ) return graphic; } // Search again for anything that's close, even something already used. (The latter is // important for error reporting.) VECTOR2I pt( aPoint ); SEG::ecoord closest_dist_sq = SEG::Square( aLimit ); PCB_SHAPE* closest_graphic = nullptr; SEG::ecoord d_sq; for( PCB_SHAPE* graphic : aList ) { if( graphic == aShape ) continue; d_sq = ( pt - graphic->GetStart() ).SquaredEuclideanNorm(); if( d_sq < closest_dist_sq ) { closest_dist_sq = d_sq; closest_graphic = graphic; } d_sq = ( pt - graphic->GetEnd() ).SquaredEuclideanNorm(); if( d_sq < closest_dist_sq ) { closest_dist_sq = d_sq; closest_graphic = graphic; } } return closest_graphic; // Note: will be nullptr if nothing within aLimit } static bool isCopperOutside( const FOOTPRINT* aFootprint, SHAPE_POLY_SET& aShape ) { bool padOutside = false; for( PAD* pad : aFootprint->Pads() ) { pad->Padstack().ForEachUniqueLayer( [&]( PCB_LAYER_ID aLayer ) { SHAPE_POLY_SET poly = aShape.CloneDropTriangulation(); poly.ClearArcs(); poly.BooleanIntersection( *pad->GetEffectivePolygon( aLayer, ERROR_INSIDE ) ); if( poly.OutlineCount() == 0 ) { VECTOR2I padPos = pad->GetPosition(); wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): outside" ), padPos.x, padPos.y ); padOutside = true; } } ); if( padOutside ) break; VECTOR2I padPos = pad->GetPosition(); wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): not outside" ), padPos.x, padPos.y ); } return padOutside; } bool doConvertOutlineToPolygon( std::vector& aShapeList, SHAPE_POLY_SET& aPolygons, int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint, OUTLINE_ERROR_HANDLER* aErrorHandler, bool aAllowUseArcsInPolygons, SCOPED_FLAGS_CLEANER& aCleaner ) { if( aShapeList.size() == 0 ) return true; bool selfIntersecting = false; wxString msg; PCB_SHAPE* graphic = nullptr; std::set startCandidates( aShapeList.begin(), aShapeList.end() ); // Keep a list of where the various shapes came from so after doing our combined-polygon // tests we can still report errors against the individual graphic items. std::map, PCB_SHAPE*> shapeOwners; auto fetchOwner = [&]( const SEG& seg ) -> PCB_SHAPE* { auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) ); return it == shapeOwners.end() ? nullptr : it->second; }; PCB_SHAPE* prevGraphic = nullptr; VECTOR2I prevPt; std::vector contours; for( PCB_SHAPE* shape : startCandidates ) shape->ClearFlags( SKIP_STRUCT ); while( startCandidates.size() ) { graphic = (PCB_SHAPE*) *startCandidates.begin(); graphic->SetFlags( SKIP_STRUCT ); aCleaner.insert( graphic ); startCandidates.erase( startCandidates.begin() ); contours.emplace_back(); SHAPE_LINE_CHAIN& currContour = contours.back(); currContour.SetWidth( graphic->GetWidth() ); bool firstPt = true; // Circles, rects and polygons are closed shapes unto themselves (and do not combine // with other shapes), so process them separately. if( graphic->GetShape() == SHAPE_T::POLY ) { for( auto it = graphic->GetPolyShape().CIterate(); it; it++ ) { VECTOR2I pt = *it; currContour.Append( pt ); if( firstPt ) firstPt = false; else shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic; prevPt = pt; } currContour.SetClosed( true ); } else if( graphic->GetShape() == SHAPE_T::CIRCLE ) { VECTOR2I center = graphic->GetCenter(); int radius = graphic->GetRadius(); VECTOR2I start = center; start.x += radius; // Add 360 deg Arc in currContour SHAPE_ARC arc360( center, start, ANGLE_360, 0 ); currContour.Append( arc360, aErrorMax ); currContour.SetClosed( true ); // set shapeOwners for currContour points created by appending the arc360: for( int ii = 1; ii < currContour.PointCount(); ++ii ) { shapeOwners[ std::make_pair( currContour.CPoint( ii-1 ), currContour.CPoint( ii ) ) ] = graphic; } if( !aAllowUseArcsInPolygons ) currContour.ClearArcs(); } else if( graphic->GetShape() == SHAPE_T::RECTANGLE ) { std::vector pts = graphic->GetRectCorners(); for( const VECTOR2I& pt : pts ) { currContour.Append( pt ); if( firstPt ) firstPt = false; else shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic; prevPt = pt; } currContour.SetClosed( true ); } else { // Polygon start point. Arbitrarily chosen end of the segment and build the poly // from here. VECTOR2I startPt = graphic->GetEnd(); prevPt = startPt; currContour.Append( prevPt ); // do not append the other end point yet, this first 'graphic' might be an arc for(;;) { switch( graphic->GetShape() ) { case SHAPE_T::RECTANGLE: case SHAPE_T::CIRCLE: { // As a non-first item, closed shapes can't be anything but self-intersecting if( aErrorHandler ) { wxASSERT( prevGraphic ); (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic, prevPt ); } selfIntersecting = true; // A closed shape will finish where it started, so no point in updating prevPt break; } case SHAPE_T::SEGMENT: { VECTOR2I nextPt; // Use the line segment end point furthest away from prevPt as we assume // the other end to be ON prevPt or very close to it. if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) ) nextPt = graphic->GetEnd(); else nextPt = graphic->GetStart(); currContour.Append( nextPt ); shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic; prevPt = nextPt; } break; case SHAPE_T::ARC: { VECTOR2I pstart = graphic->GetStart(); VECTOR2I pmid = graphic->GetArcMid(); VECTOR2I pend = graphic->GetEnd(); if( !close_enough( prevPt, pstart, aChainingEpsilon ) ) { wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) ); std::swap( pstart, pend ); } // Snap the arc start point to avoid potential self-intersections pstart = prevPt; SHAPE_ARC sarc( pstart, pmid, pend, 0 ); SHAPE_LINE_CHAIN arcChain; arcChain.Append( sarc, aErrorMax ); if( !aAllowUseArcsInPolygons ) arcChain.ClearArcs(); // set shapeOwners for arcChain points created by appending the sarc: for( int ii = 1; ii < arcChain.PointCount(); ++ii ) { shapeOwners[std::make_pair( arcChain.CPoint( ii - 1 ), arcChain.CPoint( ii ) )] = graphic; } currContour.Append( arcChain ); prevPt = pend; } break; case SHAPE_T::BEZIER: { // We do not support Bezier curves in polygons, so approximate with a series // of short lines and put those line segments into the !same! PATH. VECTOR2I nextPt; bool reverse = false; // Use the end point furthest away from prevPt as we assume the other // end to be ON prevPt or very close to it. if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) ) { nextPt = graphic->GetEnd(); } else { nextPt = graphic->GetStart(); reverse = true; } // Ensure the approximated Bezier shape is built graphic->RebuildBezierToSegmentsPointsList( aErrorMax ); if( reverse ) { for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- ) { const VECTOR2I& pt = graphic->GetBezierPoints()[jj]; if( close_enough( prevPt, pt, aChainingEpsilon ) ) continue; currContour.Append( pt ); shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic; prevPt = pt; } } else { for( const VECTOR2I& pt : graphic->GetBezierPoints() ) { if( close_enough( prevPt, pt, aChainingEpsilon ) ) continue; currContour.Append( pt ); shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic; prevPt = pt; } } prevPt = nextPt; } break; default: UNIMPLEMENTED_FOR( graphic->SHAPE_T_asString() ); return false; } // Get next closest segment. PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aShapeList, aChainingEpsilon ); if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) ) { prevGraphic = graphic; graphic = nextGraphic; graphic->SetFlags( SKIP_STRUCT ); aCleaner.insert( graphic ); startCandidates.erase( graphic ); continue; } // Finished, or ran into trouble... if( close_enough( startPt, prevPt, aChainingEpsilon ) ) { if( startPt != prevPt && currContour.PointCount() > 2 ) { // Snap the last shape's endpoint to the outline startpoint PCB_SHAPE* owner = fetchOwner( currContour.CSegment( -1 ) ); if( currContour.IsArcEnd( currContour.PointCount() - 1 ) ) { SHAPE_ARC arc = currContour.Arc( currContour.ArcIndex( currContour.PointCount() - 1 ) ); // Snap the arc endpoint SHAPE_ARC sarc( arc.GetP0(), arc.GetArcMid(), startPt, 0 ); SHAPE_LINE_CHAIN arcChain; arcChain.Append( sarc, aErrorMax ); if( !aAllowUseArcsInPolygons ) arcChain.ClearArcs(); // Set shapeOwners for arcChain points created by appending the sarc: for( int ii = 1; ii < arcChain.PointCount(); ++ii ) { shapeOwners[std::make_pair( arcChain.CPoint( ii - 1 ), arcChain.CPoint( ii ) )] = owner; } currContour.RemoveShape( currContour.PointCount() - 1 ); currContour.Append( arcChain ); } else { // Snap the segment endpoint currContour.SetPoint( -1, startPt ); shapeOwners[std::make_pair( currContour.CPoint( -2 ), currContour.CPoint( -1 ) )] = owner; } prevPt = startPt; } currContour.SetClosed( true ); break; } else if( nextGraphic ) // encountered already-used segment, but not at the start { if( aErrorHandler ) (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt ); break; } else // encountered discontinuity { if( aErrorHandler ) (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt ); break; } } } } for( const SHAPE_LINE_CHAIN& contour : contours ) { if( !contour.IsClosed() ) return false; } // First, collect the parents of each contour std::map> contourToParentIndexesMap; for( size_t ii = 0; ii < contours.size(); ++ii ) { VECTOR2I firstPt = contours[ii].GetPoint( 0 ); std::vector parents; for( size_t jj = 0; jj < contours.size(); ++jj ) { if( jj == ii ) continue; const SHAPE_LINE_CHAIN& parentCandidate = contours[jj]; if( parentCandidate.PointInside( firstPt ) ) parents.push_back( jj ); } contourToParentIndexesMap[ii] = std::move( parents ); } // Next add those that are top-level outlines to the SHAPE_POLY_SET std::map contourToOutlineIdxMap; for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap ) { if( parentIndexes.size() %2 == 0 ) { // Even number of parents; top-level outline if( !aAllowDisjoint && !aPolygons.IsEmpty() ) { if( aErrorHandler ) { BOARD_ITEM* a = fetchOwner( aPolygons.Outline( 0 ).GetSegment( 0 ) ); BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) ); if( a && b ) { (*aErrorHandler)( _( "(multiple board outlines not supported)" ), a, b, contours[ contourIndex ].GetPoint( 0 ) ); return false; } } } aPolygons.AddOutline( contours[ contourIndex ] ); contourToOutlineIdxMap[ contourIndex ] = aPolygons.OutlineCount() - 1; } } // And finally add the holes for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap ) { if( parentIndexes.size() %2 == 1 ) { // Odd number of parents; we're a hole in the parent which has one fewer parents // than we have. const SHAPE_LINE_CHAIN& hole = contours[ contourIndex ]; for( int parentContourIdx : parentIndexes ) { if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 ) { int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ]; aPolygons.AddHole( hole, outlineIdx ); break; } } } } // All of the silliness that follows is to work around the segment iterator while checking // for collisions. // TODO: Implement proper segment and point iterators that follow std std::vector segments; size_t total = 0; for( int ii = 0; ii < aPolygons.OutlineCount(); ++ii ) { const SHAPE_LINE_CHAIN& contour = aPolygons.Outline( ii ); total += contour.SegmentCount(); for( int jj = 0; jj < aPolygons.HoleCount( ii ); ++jj ) { const SHAPE_LINE_CHAIN& hole = aPolygons.Hole( ii, jj ); total += hole.SegmentCount(); } } segments.reserve( total ); for( auto seg = aPolygons.IterateSegmentsWithHoles(); seg; seg++ ) { if( LexicographicalCompare( ( *seg ).A, ( *seg ).B ) > 0 ) { // Ensure segments are always ordered A < B VECTOR2I tmp = ( *seg ).A; ( *seg ).A = ( *seg ).B; ( *seg ).B = tmp; } segments.push_back( *seg ); } std::sort( segments.begin(), segments.end(), []( const SEG& a, const SEG& b ) { if( a.A != b.A ) return LexicographicalCompare( a.A, b.A ) < 0; return LexicographicalCompare( a.B, b.B ) < 0; } ); for( auto seg1 = segments.begin(); seg1 != segments.end(); seg1++ ) { auto seg2 = seg1; for( ++seg2; seg2 != segments.end(); seg2++ ) { if( ( *seg2 ).A > ( *seg1 ).B ) { // No more segments to check, as they are sorted by A and B. break; } // Check for exact overlapping segments. if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) ) { if( aErrorHandler ) { BOARD_ITEM* a = fetchOwner( *seg1 ); BOARD_ITEM* b = fetchOwner( *seg2 ); (*aErrorHandler)( _( "(self-intersecting)" ), a, b, ( *seg1 ).A ); } selfIntersecting = true; } if( OPT_VECTOR2I pt = seg1->Intersect( *seg2, true ) ) { if( aErrorHandler ) { BOARD_ITEM* a = fetchOwner( *seg1 ); BOARD_ITEM* b = fetchOwner( *seg2 ); (*aErrorHandler)( _( "(self-intersecting)" ), a, b, *pt ); } selfIntersecting = true; } } } return !selfIntersecting; } bool ConvertOutlineToPolygon( std::vector& aShapeList, SHAPE_POLY_SET& aPolygons, int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint, OUTLINE_ERROR_HANDLER* aErrorHandler, bool aAllowUseArcsInPolygons ) { SCOPED_FLAGS_CLEANER cleaner( SKIP_STRUCT ); return doConvertOutlineToPolygon( aShapeList, aPolygons, aErrorMax, aChainingEpsilon, aAllowDisjoint, aErrorHandler, aAllowUseArcsInPolygons, cleaner ); } bool TestBoardOutlinesGraphicItems( BOARD* aBoard, int aMinDist, OUTLINE_ERROR_HANDLER* aErrorHandler ) { bool success = true; PCB_TYPE_COLLECTOR items; int min_dist = std::max( 0, aMinDist ); // Get all the shapes into 'items', then keep only those on layer == Edge_Cuts. items.Collect( aBoard, { PCB_SHAPE_T } ); std::vector shapeList; for( int ii = 0; ii < items.GetCount(); ii++ ) { PCB_SHAPE* seg = static_cast( items[ii] ); if( seg->GetLayer() == Edge_Cuts ) shapeList.push_back( seg ); } // Now Test validity of collected items for( PCB_SHAPE* shape : shapeList ) { switch( shape->GetShape() ) { case SHAPE_T::RECTANGLE: { VECTOR2I seg = shape->GetEnd() - shape->GetStart(); int dim = seg.EuclideanNorm(); if( dim <= min_dist ) { success = false; if( aErrorHandler ) { (*aErrorHandler)( wxString::Format( _( "(rectangle has null or very small " "size: %d nm)" ), dim ), shape, nullptr, shape->GetStart() ); } } break; } case SHAPE_T::CIRCLE: { int r = shape->GetRadius(); if( r <= min_dist ) { success = false; if( aErrorHandler ) { (*aErrorHandler)( wxString::Format( _( "(circle has null or very small " "radius: %d nm)" ), r ), shape, nullptr, shape->GetStart() ); } } break; } case SHAPE_T::SEGMENT: { VECTOR2I seg = shape->GetEnd() - shape->GetStart(); int dim = seg.EuclideanNorm(); if( dim <= min_dist ) { success = false; if( aErrorHandler ) { (*aErrorHandler)( wxString::Format( _( "(segment has null or very small " "length: %d nm)" ), dim ), shape, nullptr, shape->GetStart() ); } } break; } case SHAPE_T::ARC: { // Arc size can be evaluated from the distance between arc middle point and arc ends // We do not need a precise value, just an idea of its size VECTOR2I arcMiddle = shape->GetArcMid(); VECTOR2I seg1 = arcMiddle - shape->GetStart(); VECTOR2I seg2 = shape->GetEnd() - arcMiddle; int dim = seg1.EuclideanNorm() + seg2.EuclideanNorm(); if( dim <= min_dist ) { success = false; if( aErrorHandler ) { (*aErrorHandler)( wxString::Format( _( "(arc has null or very small size: " "%d nm)" ), dim ), shape, nullptr, shape->GetStart() ); } } break; } case SHAPE_T::POLY: break; case SHAPE_T::BEZIER: break; default: UNIMPLEMENTED_FOR( shape->SHAPE_T_asString() ); return false; } } return success; } bool BuildBoardPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler, bool aAllowUseArcsInPolygons ) { PCB_TYPE_COLLECTOR items; SHAPE_POLY_SET fpHoles; bool success = false; SCOPED_FLAGS_CLEANER cleaner( SKIP_STRUCT ); // Get all the shapes into 'items', then keep only those on layer == Edge_Cuts. items.Collect( aBoard, { PCB_SHAPE_T } ); for( int ii = 0; ii < items.GetCount(); ++ii ) items[ii]->ClearFlags( SKIP_STRUCT ); for( FOOTPRINT* fp : aBoard->Footprints() ) { PCB_TYPE_COLLECTOR fpItems; fpItems.Collect( fp, { PCB_SHAPE_T } ); std::vector fpSegList; for( int ii = 0; ii < fpItems.GetCount(); ii++ ) { PCB_SHAPE* fpSeg = static_cast( fpItems[ii] ); if( fpSeg->GetLayer() == Edge_Cuts ) fpSegList.push_back( fpSeg ); } if( !fpSegList.empty() ) { SHAPE_POLY_SET fpOutlines; success = doConvertOutlineToPolygon( fpSegList, fpOutlines, aErrorMax, aChainingEpsilon, false, // don't report errors here; the second pass also // gets an opportunity to use these segments nullptr, aAllowUseArcsInPolygons, cleaner ); // Test to see if we should make holes or outlines. Holes are made if the footprint // has copper outside of a single, closed outline. If there are multiple outlines, // we assume that the footprint edges represent holes as we do not support multiple // boards. Similarly, if any of the footprint pads are located outside of the edges, // then the edges are holes if( success && ( isCopperOutside( fp, fpOutlines ) || fpOutlines.OutlineCount() > 1 ) ) { fpHoles.Append( fpOutlines ); } else { // If it wasn't a closed area, or wasn't a hole, the we want to keep the fpSegs // in contention for the board outline builds. for( int ii = 0; ii < fpItems.GetCount(); ++ii ) fpItems[ii]->ClearFlags( SKIP_STRUCT ); } } } // Make a working copy of aSegList, because the list is modified during calculations std::vector segList; for( int ii = 0; ii < items.GetCount(); ii++ ) { PCB_SHAPE* seg = static_cast( items[ii] ); // Skip anything already used to generate footprint holes (above) if( seg->GetFlags() & SKIP_STRUCT ) continue; if( seg->GetLayer() == Edge_Cuts ) segList.push_back( seg ); } if( segList.size() ) { success = doConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon, true, aErrorHandler, aAllowUseArcsInPolygons, cleaner ); } if( !success || !aOutlines.OutlineCount() ) { // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to // create a rectangular outline, or, failing that, the bounding box of the items on // the board. BOX2I bbbox = aBoard->GetBoardEdgesBoundingBox(); // If null area, uses the global bounding box. if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) ) bbbox = aBoard->ComputeBoundingBox( false ); // Ensure non null area. If happen, gives a minimal size. if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) ) bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) ); aOutlines.RemoveAllContours(); aOutlines.NewOutline(); VECTOR2I corner; aOutlines.Append( bbbox.GetOrigin() ); corner.x = bbbox.GetOrigin().x; corner.y = bbbox.GetEnd().y; aOutlines.Append( corner ); aOutlines.Append( bbbox.GetEnd() ); corner.x = bbbox.GetEnd().x; corner.y = bbbox.GetOrigin().y; aOutlines.Append( corner ); } aOutlines.BooleanSubtract( fpHoles ); return success; } /** * Get the complete bounding box of the board (including all items). * * The vertex numbers and segment numbers of the rectangle returned. * 1 * *---------------* * |1 2| * 0| |2 * |0 3| * *---------------* * 3 */ void buildBoardBoundingBoxPoly( const BOARD* aBoard, SHAPE_POLY_SET& aOutline ) { BOX2I bbbox = aBoard->GetBoundingBox(); SHAPE_LINE_CHAIN chain; // If null area, uses the global bounding box. if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) ) bbbox = aBoard->ComputeBoundingBox( false ); // Ensure non null area. If happen, gives a minimal size. if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) ) bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) ); // Inflate slightly (by 1/10th the size of the box) bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 ); chain.Append( bbbox.GetOrigin() ); chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y ); chain.Append( bbbox.GetEnd() ); chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y ); chain.SetClosed( true ); aOutline.RemoveAllContours(); aOutline.AddOutline( chain ); } VECTOR2I projectPointOnSegment( const VECTOR2I& aEndPoint, const SHAPE_POLY_SET& aOutline, int aOutlineNum = 0 ) { int minDistance = -1; VECTOR2I projPoint; for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ ) { auto seg = it.Get(); int dis = seg.Distance( aEndPoint ); if( minDistance < 0 || ( dis < minDistance ) ) { minDistance = dis; projPoint = seg.NearestPoint( aEndPoint ); } } return projPoint; } int findEndSegments( SHAPE_LINE_CHAIN& aChain, SEG& aStartSeg, SEG& aEndSeg ) { int foundSegs = 0; for( int i = 0; i < aChain.SegmentCount(); i++ ) { SEG seg = aChain.Segment( i ); bool foundA = false; bool foundB = false; for( int j = 0; j < aChain.SegmentCount(); j++ ) { // Don't test the segment against itself if( i == j ) continue; SEG testSeg = aChain.Segment( j ); if( testSeg.Contains( seg.A ) ) foundA = true; if( testSeg.Contains( seg.B ) ) foundB = true; } // This segment isn't a start or end if( foundA && foundB ) continue; if( foundSegs == 0 ) { // The first segment we encounter is the "start" segment wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ), seg.A.x, seg.A.y, seg.B.x, seg.B.y ); aStartSeg = seg; foundSegs++; } else { // Once we find both start and end, we can stop wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ), seg.A.x, seg.A.y, seg.B.x, seg.B.y ); aEndSeg = seg; foundSegs++; break; } } return foundSegs; } bool BuildFootprintPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler ) { FOOTPRINT* footprint = aBoard->GetFirstFootprint(); // No footprint loaded if( !footprint ) { wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) ); return false; } PCB_TYPE_COLLECTOR items; SHAPE_POLY_SET outlines; bool success = false; SCOPED_FLAGS_CLEANER cleaner( SKIP_STRUCT ); // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts. items.Collect( aBoard, { PCB_SHAPE_T } ); // Make a working copy of aSegList, because the list is modified during calculations std::vector segList; for( int ii = 0; ii < items.GetCount(); ii++ ) { if( items[ii]->GetLayer() == Edge_Cuts ) segList.push_back( static_cast( items[ii] ) ); } if( !segList.empty() ) { success = doConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon, true, aErrorHandler, false, cleaner ); } // A closed outline was found on Edge_Cuts if( success ) { wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) ); // If copper is outside a closed polygon, treat it as a hole // If there are multiple outlines in the footprint, they are also holes if( isCopperOutside( footprint, outlines ) || outlines.OutlineCount() > 1 ) { wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) ); buildBoardBoundingBoxPoly( aBoard, aOutlines ); // Copy all outlines from the conversion as holes into the new outline for( int i = 0; i < outlines.OutlineCount(); i++ ) { SHAPE_LINE_CHAIN& out = outlines.Outline( i ); if( out.IsClosed() ) aOutlines.AddHole( out, -1 ); for( int j = 0; j < outlines.HoleCount( i ); j++ ) { SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j ); if( hole.IsClosed() ) aOutlines.AddHole( hole, -1 ); } } } // If all copper is inside, then the computed outline is the board outline else { wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) ); aOutlines = outlines; } return true; } // No board outlines were found, so use the bounding box else if( outlines.OutlineCount() == 0 ) { wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) ); buildBoardBoundingBoxPoly( aBoard, aOutlines ); return true; } // There is an outline present, but it is not closed else { wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) ); std::vector closedChains; std::vector openChains; // The ConvertOutlineToPolygon function returns only one main outline and the rest as // holes, so we promote the holes and process them openChains.push_back( outlines.Outline( 0 ) ); for( int j = 0; j < outlines.HoleCount( 0 ); j++ ) { SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j ); if( hole.IsClosed() ) { wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) ); closedChains.push_back( hole ); } else { wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) ); openChains.push_back( hole ); } } SHAPE_POLY_SET bbox; buildBoardBoundingBoxPoly( aBoard, bbox ); // Treat the open polys as the board edge SHAPE_LINE_CHAIN chain = openChains[0]; SHAPE_LINE_CHAIN rect = bbox.Outline( 0 ); // We know the outline chain is open, so set to non-closed to get better segment count chain.SetClosed( false ); SEG startSeg; SEG endSeg; // The two possible board outlines SHAPE_LINE_CHAIN upper; SHAPE_LINE_CHAIN lower; findEndSegments( chain, startSeg, endSeg ); if( chain.SegmentCount() == 0 ) { // Something is wrong, bail out with the overall footprint bounding box wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) ); aOutlines = bbox; return true; } else if( chain.SegmentCount() == 1 ) { // This case means there is only 1 line segment making up the edge cuts of the // footprint, so we just need to use it to cut the bounding box in half. wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) ); startSeg = chain.Segment( 0 ); // Intersect with all the sides of the rectangle OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) ); OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) ); OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) ); OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) ); if( inter0 && inter2 && !inter1 && !inter3 ) { // Intersects the vertical rectangle sides only wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox " "sides" ) ); // The upper half upper.Append( *inter0 ); upper.Append( rect.GetPoint( 1 ) ); upper.Append( rect.GetPoint( 2 ) ); upper.Append( *inter2 ); upper.SetClosed( true ); // The lower half lower.Append( *inter0 ); lower.Append( rect.GetPoint( 0 ) ); lower.Append( rect.GetPoint( 3 ) ); lower.Append( *inter2 ); lower.SetClosed( true ); } else if( inter1 && inter3 && !inter0 && !inter2 ) { // Intersects the horizontal rectangle sides only wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox " "sides" ) ); // The left half upper.Append( *inter1 ); upper.Append( rect.GetPoint( 1 ) ); upper.Append( rect.GetPoint( 0 ) ); upper.Append( *inter3 ); upper.SetClosed( true ); // The right half lower.Append( *inter1 ); lower.Append( rect.GetPoint( 2 ) ); lower.Append( rect.GetPoint( 3 ) ); lower.Append( *inter3 ); lower.SetClosed( true ); } else { // Angled line segment that cuts across a corner wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox " "sides" ) ); // Figure out which actual lines are intersected, since IntersectLines assumes // an infinite line bool hit0 = rect.Segment( 0 ).Contains( *inter0 ); bool hit1 = rect.Segment( 1 ).Contains( *inter1 ); bool hit2 = rect.Segment( 2 ).Contains( *inter2 ); bool hit3 = rect.Segment( 3 ).Contains( *inter3 ); if( hit0 && hit1 ) { // Cut across the upper left corner wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) ); // The upper half upper.Append( *inter0 ); upper.Append( rect.GetPoint( 1 ) ); upper.Append( *inter1 ); upper.SetClosed( true ); // The lower half lower.Append( *inter0 ); lower.Append( rect.GetPoint( 0 ) ); lower.Append( rect.GetPoint( 3 ) ); lower.Append( rect.GetPoint( 2 ) ); lower.Append( *inter1 ); lower.SetClosed( true ); } else if( hit1 && hit2 ) { // Cut across the upper right corner wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) ); // The upper half upper.Append( *inter1 ); upper.Append( rect.GetPoint( 2 ) ); upper.Append( *inter2 ); upper.SetClosed( true ); // The lower half lower.Append( *inter1 ); lower.Append( rect.GetPoint( 1 ) ); lower.Append( rect.GetPoint( 0 ) ); lower.Append( rect.GetPoint( 3 ) ); lower.Append( *inter2 ); lower.SetClosed( true ); } else if( hit2 && hit3 ) { // Cut across the lower right corner wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) ); // The upper half upper.Append( *inter2 ); upper.Append( rect.GetPoint( 2 ) ); upper.Append( rect.GetPoint( 1 ) ); upper.Append( rect.GetPoint( 0 ) ); upper.Append( *inter3 ); upper.SetClosed( true ); // The bottom half lower.Append( *inter2 ); lower.Append( rect.GetPoint( 3 ) ); lower.Append( *inter3 ); lower.SetClosed( true ); } else { // Cut across the lower left corner wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) ); // The upper half upper.Append( *inter0 ); upper.Append( rect.GetPoint( 1 ) ); upper.Append( rect.GetPoint( 2 ) ); upper.Append( rect.GetPoint( 3 ) ); upper.Append( *inter3 ); upper.SetClosed( true ); // The bottom half lower.Append( *inter0 ); lower.Append( rect.GetPoint( 0 ) ); lower.Append( *inter3 ); lower.SetClosed( true ); } } } else { // More than 1 segment wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) ); // Just a temporary thing aOutlines = bbox; return true; } // Figure out which is the correct outline SHAPE_POLY_SET poly1; SHAPE_POLY_SET poly2; poly1.NewOutline(); poly1.Append( upper ); poly2.NewOutline(); poly2.Append( lower ); if( isCopperOutside( footprint, poly1 ) ) { wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) ); aOutlines = poly2; } else { wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) ); aOutlines = poly1; } // Add all closed polys as holes to the main outline for( SHAPE_LINE_CHAIN& closedChain : closedChains ) { wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) ); aOutlines.AddHole( closedChain, -1 ); } return true; } // We really shouldn't reach this point return false; }