drc_cache_generator.cpp

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright The KiCad Developers.
 *
 * 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, see <https://www.gnu.org/licenses/>.
 */
 
#include <common.h>
#include <board_design_settings.h>
#include <pad.h>
#include <pcb_board_outline.h>
#include <footprint.h>
#include <thread_pool.h>
#include <zone.h>
#include <connectivity/connectivity_data.h>
#include <drc/drc_engine.h>
#include <drc/drc_rtree.h>
#include <drc/drc_cache_generator.h>
#include <mutex>
 
bool DRC_CACHE_GENERATOR::Run()
{
    m_board = m_drcEngine->GetBoard();
 
    // Everything below appends to the board's DRC caches rather than replacing them, so they
    // have to start out empty.
    m_board->IncrementTimeStamp();
 
    int&           largestClearance = m_board->m_DRCMaxClearance;
    int&           largestPhysicalClearance = m_board->m_DRCMaxPhysicalClearance;
    DRC_CONSTRAINT worstConstraint;
    LSET           boardCopperLayers = LSET::AllCuMask( m_board->GetCopperLayerCount() );
    thread_pool&   tp = GetKiCadThreadPool();
 
    largestClearance = std::max( largestClearance, m_board->GetMaxClearanceValue() );
 
    // Only consider unconditional constraints for the global maximum.  Conditional constraints
    // (like the barcode physical clearance default) apply only to specific item types and
    // should not inflate the R-tree query radius for all items on the board.
    if( m_drcEngine->QueryWorstConstraint( PHYSICAL_CLEARANCE_CONSTRAINT, worstConstraint, true ) )
        largestPhysicalClearance = worstConstraint.GetValue().Min();
 
    if( m_drcEngine->QueryWorstConstraint( PHYSICAL_HOLE_CLEARANCE_CONSTRAINT, worstConstraint, true ) )
        largestPhysicalClearance = std::max( largestPhysicalClearance, worstConstraint.GetValue().Min() );
 
    // If the unconditional max is 0, check for conditional constraints that may still apply.
    // User-defined conditional rules always need the test to run.  The implicit barcode rule
    // only needs the test if barcodes actually exist on the board.
    if( largestPhysicalClearance <= 0 )
    {
        int conditionalMax = 0;
 
        if( m_drcEngine->QueryWorstConstraint( PHYSICAL_CLEARANCE_CONSTRAINT, worstConstraint ) )
            conditionalMax = worstConstraint.GetValue().Min();
 
        if( m_drcEngine->QueryWorstConstraint( PHYSICAL_HOLE_CLEARANCE_CONSTRAINT, worstConstraint ) )
            conditionalMax = std::max( conditionalMax, worstConstraint.GetValue().Min() );
 
        if( conditionalMax > 0 )
        {
            if( m_drcEngine->HasUserDefinedPhysicalConstraint() )
            {
                largestPhysicalClearance = conditionalMax;
            }
            else
            {
                bool hasMatchingItems = false;
 
                forEachGeometryItem( { PCB_BARCODE_T }, LSET::AllLayersMask(),
                                     [&]( BOARD_ITEM* item ) -> bool
                                     {
                                         hasMatchingItems = true;
                                         return false;
                                     } );
 
                if( hasMatchingItems )
                    largestPhysicalClearance = conditionalMax;
            }
        }
    }
 
    // Ensure algorithmic safety
    largestClearance = std::min( largestClearance, INT_MAX / 3 );
    largestPhysicalClearance = std::min( largestPhysicalClearance, INT_MAX / 3 );
 
    std::set<ZONE*> allZones;
 
    auto cacheBBoxes =
            []( ZONE* zone, const LSET& copperLayers )
            {
                if( !zone->GetParentFootprint() )
                    zone->Outline()->BuildBBoxCaches();
 
                for( PCB_LAYER_ID layer : copperLayers )
                {
                    if( SHAPE_POLY_SET* fill = zone->GetFill( layer ) )
                        fill->BuildBBoxCaches();
                }
            };
 
    for( ZONE* zone : m_board->Zones() )
    {
        allZones.insert( zone );
 
        if( !zone->GetIsRuleArea() )
        {
            m_board->m_DRCZones.push_back( zone );
 
            LSET zoneCopperLayers = zone->GetLayerSet() & boardCopperLayers;
 
            if( zoneCopperLayers.any() )
            {
                cacheBBoxes( zone, zoneCopperLayers );
                m_board->m_DRCCopperZones.push_back( zone );
            }
        }
    }
 
    for( FOOTPRINT* footprint : m_board->Footprints() )
    {
        for( ZONE* zone : footprint->Zones() )
        {
            allZones.insert( zone );
 
            if( !zone->GetIsRuleArea() )
            {
                m_board->m_DRCZones.push_back( zone );
 
                LSET zoneCopperLayers = zone->GetLayerSet() & boardCopperLayers;
 
                if( zoneCopperLayers.any() )
                {
                    cacheBBoxes( zone, zoneCopperLayers );
                    m_board->m_DRCCopperZones.push_back( zone );
                }
            }
        }
    }
 
    for( ZONE* zone : m_board->m_DRCCopperZones )
    {
        LSET zoneCopperLayers = zone->GetLayerSet() & boardCopperLayers;
 
        for( PCB_LAYER_ID layer : zoneCopperLayers )
            m_board->m_DRCCopperZonesByLayer[layer].push_back( zone );
    }
 
    size_t              count = 0;
    std::atomic<size_t> done( 1 );
 
    auto countItems =
            [&]( BOARD_ITEM* item ) -> bool
            {
                ++count;
                return true;
            };
 
    auto addToCopperTree =
            [&]( BOARD_ITEM* item ) -> bool
            {
                if( m_drcEngine->IsCancelled() )
                    return false;
 
                LSET copperLayers = item->GetLayerSet() & boardCopperLayers;
 
                // Special-case pad holes which pierce all the copper layers
                if( item->Type() == PCB_PAD_T )
                {
                    PAD* pad = static_cast<PAD*>( item );
 
                    if( pad->HasHole() )
                        copperLayers = boardCopperLayers;
                }
 
                copperLayers.RunOnLayers(
                        [&]( PCB_LAYER_ID layer )
                        {
                            m_board->m_CopperItemRTreeCache->Insert( item, layer, CLEARANCE_CONSTRAINT,
                                                                     largestClearance );
                        } );
 
                done.fetch_add( 1 );
                return true;
            };
 
    if( !reportPhase( _( "Gathering copper items..." ) ) )
        return false;   // DRC cancelled
 
    static const std::vector<KICAD_T> itemTypes = {
        PCB_TRACE_T, PCB_ARC_T, PCB_VIA_T,
        PCB_PAD_T,
        PCB_SHAPE_T,
        PCB_FIELD_T, PCB_TEXT_T, PCB_TEXTBOX_T,
        PCB_TABLE_T, PCB_TABLECELL_T,
        PCB_DIMENSION_T,
        PCB_BARCODE_T
    };
 
    forEachGeometryItem( itemTypes, boardCopperLayers, countItems );
 
    std::future<void> retn = tp.submit_task(
            [&]()
            {
                std::unique_lock<std::shared_mutex> writeLock( m_board->m_CachesMutex );
 
                // Always start from an empty tree: the traversal below re-inserts every copper
                // item, and a DRC_RTREE stops accepting inserts once it has been built. 
                m_board->m_CopperItemRTreeCache = std::make_shared<DRC_RTREE>();
 
                forEachGeometryItem( itemTypes, boardCopperLayers, addToCopperTree );
                m_board->m_CopperItemRTreeCache->Build();
            } );
 
    std::future_status status = retn.wait_for( std::chrono::milliseconds( 250 ) );
 
    while( status != std::future_status::ready )
    {
        reportProgress( done, count );
        status = retn.wait_for( std::chrono::milliseconds( 250 ) );
    }
 
    if( !reportPhase( _( "Tessellating copper zones..." ) ) )
        return false;   // DRC cancelled
 
    // Cache zone bounding boxes, triangulation, copper zone rtrees, and footprint courtyards
    // before we start.
 
    for( FOOTPRINT* footprint : m_board->Footprints() )
    {
        footprint->BuildCourtyardCaches();
        footprint->BuildNetTieCache();
    }
 
    std::vector<std::future<size_t>> returns;
 
    returns.reserve( allZones.size() );
 
    auto cache_zones =
            [this, &done]( ZONE* aZone ) -> size_t
            {
                if( m_drcEngine->IsCancelled() )
                    return 0;
 
                aZone->CacheBoundingBox();
                aZone->CacheTriangulation();
 
                if( !aZone->GetIsRuleArea() && aZone->IsOnCopperLayer() )
                {
                   std::unique_ptr<DRC_RTREE> rtree = std::make_unique<DRC_RTREE>();
 
                   aZone->GetLayerSet().RunOnLayers(
                           [&]( PCB_LAYER_ID layer )
                           {
                               if( IsCopperLayer( layer ) )
                                   rtree->Insert( aZone, layer, CLEARANCE_CONSTRAINT );
                           } );
 
                   rtree->Build();
 
                   {
                       std::unique_lock<std::shared_mutex> writeLock( m_board->m_CachesMutex );
                       m_board->m_CopperZoneRTreeCache[ aZone ] = std::move( rtree );
                   }
 
                   done.fetch_add( 1 );
                }
 
                return 1;
            };
 
    for( ZONE* zone : allZones )
    {
        returns.emplace_back( tp.submit_task(
                [cache_zones, zone]
                {
                    return cache_zones( zone );
                } ) );
    }
 
    done.store( 1 );
 
    for( const std::future<size_t>& ret : returns )
    {
        status = ret.wait_for( std::chrono::milliseconds( 250 ) );
 
        while( status != std::future_status::ready )
        {
            reportProgress( done, allZones.size() );
            status = ret.wait_for( std::chrono::milliseconds( 250 ) );
        }
    }
 
    m_board->m_ZoneIsolatedIslandsMap.clear();
 
    for( ZONE* zone : m_board->Zones() )
    {
        if( !zone->GetIsRuleArea() && !zone->IsTeardropArea() && !zone->IsCopperThieving() )
        {
            zone->GetLayerSet().RunOnLayers(
                    [&]( PCB_LAYER_ID layer )
                    {
                        m_board->m_ZoneIsolatedIslandsMap[ zone ][ layer ] = ISOLATED_ISLANDS();
                    } );
        }
    }
 
    m_board->UpdateBoardOutline();
 
    if( m_board->BoardOutline() )
        m_board->BoardOutline()->GetOutline().BuildBBoxCaches();
 
    std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_board->GetConnectivity();
 
    connectivity->ClearRatsnest();
    connectivity->Build( m_board, m_drcEngine->GetProgressReporter() );
    connectivity->FillIsolatedIslandsMap( m_board->m_ZoneIsolatedIslandsMap, true );
 
    return !m_drcEngine->IsCancelled();
}