spread_footprints.cpp 12 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2013 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
 * Copyright (C) 2013 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
 * Copyright (C) 2013 Wayne Stambaugh <stambaughw@verizon.net>
 *
 * Copyright (C) 1992-2013 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
 */

/**
 * @file spread_footprints.cpp
 * @brief functions to spread footprints on free areas outside a board.
 * this is usefull after reading a netlist, when new footprints are loaded
 * and stacked at 0,0 coordinate.
 * Often, spread them on a free area near the board being edited make more easy
 * their selection.
 */

#include <algorithm>

#include <fctsys.h>
#include <convert_to_biu.h>
#include <class_drawpanel.h>
#include <confirm.h>
#include <pcbnew.h>
#include <wxPcbStruct.h>
#include <class_board.h>
#include <class_module.h>

#include <rect_placement/rect_placement.h>

struct TSubRect : public CRectPlacement::TRect
{
    int n;      // Original index of this subrect, before sorting

    TSubRect() { }
    TSubRect( int _w, int _h, int _n ) :
        TRect( 0, 0, _w, _h ), n( _n ) { }
};

typedef std::vector<TSubRect> CSubRectArray;

// Use 0.01 mm units to calculate placement, to avoid long calculation time
const int scale = (int)(0.01 * IU_PER_MM);

// Populates a list of rectangles, from a list of modules
void fillRectList( CSubRectArray& vecSubRects, std::vector <MODULE*>& aModuleList )
{
    vecSubRects.clear();

    for( unsigned ii = 0; ii < aModuleList.size(); ii++ )
    {
        EDA_RECT fpBox = aModuleList[ii]->GetBoundingBox();
        TSubRect fpRect( fpBox.GetWidth()/scale, fpBox.GetHeight()/scale, ii );
        vecSubRects.push_back( fpRect );
    }
}

// Populates a list of rectangles, from a list of EDA_RECT
void fillRectList( CSubRectArray& vecSubRects, std::vector <EDA_RECT>& aRectList )
{
    vecSubRects.clear();

    for( unsigned ii = 0; ii < aRectList.size(); ii++ )
    {
        EDA_RECT& rect = aRectList[ii];
        TSubRect fpRect( rect.GetWidth()/scale, rect.GetHeight()/scale, ii );
        vecSubRects.push_back( fpRect );
    }
}



// Spread a list of rectangles inside a placement area
void spreadRectangles( CRectPlacement& aPlacementArea,
                      CSubRectArray& vecSubRects,
                      int areaSizeX, int areaSizeY )
{
    areaSizeX/= scale;
    areaSizeY/= scale;

    // Sort the subRects based on dimensions, larger dimension goes first.
    std::sort( vecSubRects.begin(), vecSubRects.end(), CRectPlacement::TRect::Greater );

    // gives the initial size to the area
    aPlacementArea.Init( areaSizeX, areaSizeY );

    // Add all subrects
    CSubRectArray::iterator it;
    for( it = vecSubRects.begin(); it != vecSubRects.end(); )
    {
        CRectPlacement::TRect r( 0, 0, it->w, it->h );

        bool bPlaced = aPlacementArea.AddAtEmptySpotAutoGrow( &r, areaSizeX, areaSizeY );

        if( !bPlaced )   // No room to place the rectangle: enlarge area and retry
        {
            areaSizeX = ceil(areaSizeX * 1.1);
            areaSizeY = ceil(areaSizeY * 1.1);
            aPlacementArea.Init( areaSizeX, areaSizeY );
            it = vecSubRects.begin();
            continue;
        }

        // When correctly placed in a placement area, the coords are returned in r.x and r.y
        // Store them.
        it->x   = r.x;
        it->y   = r.y;

        it++;
    }
}


void moveFootprintsInArea( CRectPlacement& aPlacementArea,
                           std::vector <MODULE*>& aModuleList, EDA_RECT& aFreeArea,
                           bool aFindAreaOnly  )
{
    CSubRectArray   vecSubRects;

    fillRectList( vecSubRects, aModuleList );
    spreadRectangles( aPlacementArea, vecSubRects,
                      aFreeArea.GetWidth(), aFreeArea.GetHeight() );

    if( aFindAreaOnly )
        return;

    for( unsigned it = 0; it < vecSubRects.size(); ++it )
    {
        wxPoint pos( vecSubRects[it].x, vecSubRects[it].y );
        pos.x *= scale;
        pos.y *= scale;

        MODULE * module = aModuleList[vecSubRects[it].n];

        EDA_RECT fpBBox = module->GetBoundingBox();
        wxPoint mod_pos = pos + ( module->GetPosition() - fpBBox.GetOrigin() )
                          + aFreeArea.GetOrigin();

        module->Move( mod_pos - module->GetPosition() );
    }
}

static bool sortModulesbySheetPath( MODULE* ref, MODULE* compare );

/* Function to move components in a rectangular area format 4 / 3,
 * starting from the mouse cursor
 * The components with the FIXED status set are not moved
 */
void PCB_EDIT_FRAME::SpreadFootprints( bool aFootprintsOutsideBoardOnly )
{
    EDA_RECT bbox = GetBoard()->ComputeBoundingBox( true );
    bool     edgesExist = ( bbox.GetWidth() || bbox.GetHeight() );

    // no edges exist
    if( aFootprintsOutsideBoardOnly && !edgesExist )
    {
        DisplayError( this,
177
                      _( "Could not automatically place footprints. No board outlines detected." ) );
178 179 180 181 182 183 184 185 186
        return;
    }

    // if aFootprintsOutsideBoardOnly is true, and if board outline exists,
    // wue have to filter footprints to move:
    bool outsideBrdFilter = aFootprintsOutsideBoardOnly && edgesExist;

    // Build candidate list
    // calculate also the area needed by these footprints
187
    MODULE* module = GetBoard()->m_Modules;
188 189
    std::vector <MODULE*> moduleList;

190
    for( ; module != NULL; module = module->Next() )
191
    {
192
        module->CalculateBoundingBox();
193 194 195

        if( outsideBrdFilter )
        {
196
            if( bbox.Contains( module->GetPosition() ) )
197 198 199
                continue;
        }

200
        if( module->IsLocked() )
201 202
            continue;

203
        moduleList.push_back(module);
204 205 206 207 208 209 210 211 212 213 214 215 216 217 218
    }

    if( moduleList.size() == 0 )    // Nothing to do
        return;

    // sort footprints by sheet path. we group them later by sheet
    sort( moduleList.begin(), moduleList.end(), sortModulesbySheetPath );

    // Undo command: init undo list
    PICKED_ITEMS_LIST  undoList;
    undoList.m_Status = UR_CHANGED;
    ITEM_PICKER        picker( NULL, UR_CHANGED );

    for( unsigned ii = 0; ii < moduleList.size(); ii++ )
    {
219
        module = moduleList[ii];
220 221

        // Undo: add copy of module to undo list
222 223
        picker.SetItem( module );
        picker.SetLink( module->Clone() );
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
        undoList.PushItem( picker );
    }

    // Extract and place footprints by sheet
    std::vector <MODULE*> moduleListBySheet;
    std::vector <EDA_RECT> placementSheetAreas;
    double subsurface;
    double placementsurface = 0.0;

    wxPoint placementAreaPosition = GetCrossHairPosition();

    // We do not want to move footprints inside an existing board.
    // move the placement area position outside the board bounding box
    // to the left of the board
    if( edgesExist )
    {
        if( placementAreaPosition.x < bbox.GetEnd().x &&
            placementAreaPosition.y < bbox.GetEnd().y )
        {
            placementAreaPosition.x = bbox.GetEnd().x;
            placementAreaPosition.y = bbox.GetOrigin().y;
        }
    }

    // The placement uses 2 passes:
    // the first pass creates the rectangular areas to place footprints
    // each sheet in schematic creates one rectangular area.
    // the second pass moves footprints inside these areas
    for( int pass = 0; pass < 2; pass++ )
    {
        int subareaIdx = 0;
        moduleListBySheet.clear();
        subsurface = 0.0;

        for( unsigned ii = 0; ii < moduleList.size(); ii++ )
        {
260 261
            module = moduleList[ii];
            bool islastItem = false;
262

263 264 265 266 267 268 269
            if( ii == moduleList.size() - 1 ||
                ( moduleList[ii]->GetPath().BeforeLast( '/' ) !=
                  moduleList[ii+1]->GetPath().BeforeLast( '/' ) ) )
                islastItem = true;

            moduleListBySheet.push_back( module );
            subsurface += module->GetArea();
270

271
            if( islastItem )
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308
            {
                // end of the footprint sublist relative to the same sheet path
                // calculate placement of the current sublist
                EDA_RECT freeArea;
                int Xsize_allowed = (int) ( sqrt( subsurface ) * 4.0 / 3.0 );
                int Ysize_allowed = (int) ( subsurface / Xsize_allowed );

                freeArea.SetWidth( Xsize_allowed );
                freeArea.SetHeight( Ysize_allowed );
                CRectPlacement placementArea;

                if( pass == 1 )
                {
                    wxPoint areapos = placementSheetAreas[subareaIdx].GetOrigin()
                                      + placementAreaPosition;
                    freeArea.SetOrigin( areapos );
                }

                bool findAreaOnly = pass == 0;
                moveFootprintsInArea( placementArea, moduleListBySheet,
                                      freeArea, findAreaOnly );

                if( pass == 0 )
                {
                    // Populate sheet placement areas list
                    EDA_RECT sub_area;
                    sub_area.SetWidth( placementArea.GetW()*scale );
                    sub_area.SetHeight( placementArea.GetH()*scale );
                    // Add a margin around the sheet placement area:
                    sub_area.Inflate( Millimeter2iu( 1.5 ) );

                    placementSheetAreas.push_back( sub_area );

                    placementsurface += (double) sub_area.GetWidth()*
                                        sub_area.GetHeight();
                }

309
                // Prepare buffers for next sheet
310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347
                subsurface  = 0.0;
                moduleListBySheet.clear();
                subareaIdx++;
            }
        }

        // End of pass:
        // At the end of the first pass, we have to find position of each sheet
        // placement area
        if( pass == 0 )
        {
            int Xsize_allowed = (int) ( sqrt( placementsurface ) * 4.0 / 3.0 );
            int Ysize_allowed = (int) ( placementsurface / Xsize_allowed );
            CRectPlacement placementArea;
            CSubRectArray  vecSubRects;

            fillRectList( vecSubRects, placementSheetAreas );
            spreadRectangles( placementArea, vecSubRects, Xsize_allowed, Ysize_allowed );

            for( unsigned it = 0; it < vecSubRects.size(); ++it )
            {
                TSubRect& srect = vecSubRects[it];
                wxPoint pos( srect.x*scale, srect.y*scale );
                wxSize size( srect.w*scale, srect.h*scale );
                placementSheetAreas[srect.n].SetOrigin( pos );
                placementSheetAreas[srect.n].SetSize( size );
            }
        }
    }   // End pass

    // Undo: commit list
    SaveCopyInUndoList( undoList, UR_CHANGED );
    OnModify();

    m_canvas->Refresh();
}


348 349 350 351
// Sort function, used to group footprints by sheet.
// Footprints are sorted by their sheet path.
// (the full sheet path restricted to the time stamp of the sheet itself,
// without the time stamp of the footprint ).
352 353
static bool sortModulesbySheetPath( MODULE* ref, MODULE* compare )
{
354 355 356 357
    if( ref->GetPath().Length() == compare->GetPath().Length() )
        return ref->GetPath().BeforeLast( '/' ).Cmp( compare->GetPath().BeforeLast( '/' ) ) < 0;

    return ref->GetPath().Length() < compare->GetPath().Length();
358
}