diff options
Diffstat (limited to 'pcbnew/autorouter')
| -rw-r--r-- | pcbnew/autorouter/auto_place_footprints.cpp | 1299 | ||||
| -rw-r--r-- | pcbnew/autorouter/autorout.cpp | 277 | ||||
| -rw-r--r-- | pcbnew/autorouter/autorout.h | 236 | ||||
| -rw-r--r-- | pcbnew/autorouter/cell.h | 116 | ||||
| -rw-r--r-- | pcbnew/autorouter/dist.cpp | 171 | ||||
| -rw-r--r-- | pcbnew/autorouter/graphpcb.cpp | 843 | ||||
| -rw-r--r-- | pcbnew/autorouter/move_and_route_event_functions.cpp | 200 | ||||
| -rw-r--r-- | pcbnew/autorouter/queue.cpp | 220 | ||||
| -rw-r--r-- | pcbnew/autorouter/rect_placement/RectanglePlacement.txt | 38 | ||||
| -rw-r--r-- | pcbnew/autorouter/rect_placement/rect_placement.cpp | 259 | ||||
| -rw-r--r-- | pcbnew/autorouter/rect_placement/rect_placement.h | 104 | ||||
| -rw-r--r-- | pcbnew/autorouter/routing_matrix.cpp | 550 | ||||
| -rw-r--r-- | pcbnew/autorouter/solve.cpp | 1348 | ||||
| -rw-r--r-- | pcbnew/autorouter/spread_footprints.cpp | 362 | ||||
| -rw-r--r-- | pcbnew/autorouter/work.cpp | 164 |
15 files changed, 6187 insertions, 0 deletions
diff --git a/pcbnew/autorouter/auto_place_footprints.cpp b/pcbnew/autorouter/auto_place_footprints.cpp new file mode 100644 index 0000000..d6d25a1 --- /dev/null +++ b/pcbnew/autorouter/auto_place_footprints.cpp @@ -0,0 +1,1299 @@ +/** + * @file auto_place_footprints.cpp + * @brief Functions to automatically place Footprints on a board. + */ + +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2012 KiCad Developers, see change_log.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 <fctsys.h> +#include <class_drawpanel.h> +#include <confirm.h> +#include <pcbnew.h> +#include <wxPcbStruct.h> +#include <gr_basic.h> +#include <macros.h> +#include <msgpanel.h> + +#include <autorout.h> +#include <cell.h> +#include <colors_selection.h> + +#include <class_board.h> +#include <class_module.h> +#include <class_track.h> +#include <class_drawsegment.h> +#include <convert_to_biu.h> +#include <base_units.h> +#include <protos.h> + + +#define GAIN 16 +#define KEEP_OUT_MARGIN 500 + + +/* Penalty (cost) for CntRot90 and CntRot180: + * CntRot90 and CntRot180 are from 0 (rotation allowed) to 10 (rotation not allowed) + */ +static const double OrientPenality[11] = +{ + 2.0, // CntRot = 0 rotation prohibited + 1.9, // CntRot = 1 + 1.8, // CntRot = 2 + 1.7, // CntRot = 3 + 1.6, // CntRot = 4 + 1.5, // CntRot = 5 + 1.4, // CntRot = 5 + 1.3, // CntRot = 7 + 1.2, // CntRot = 8 + 1.1, // CntRot = 9 + 1.0 // CntRot = 10 rotation authorized, no penalty +}; + +// Cell states. +#define OUT_OF_BOARD -2 +#define OCCUPED_By_MODULE -1 +#define FREE_CELL 0 + + +static wxPoint CurrPosition; // Current position of the current module placement +double MinCout; + + +/* generates the Routing matrix, used to fing the best placement + * of a footprint. + * Allocate a "bitmap" which is an image of the real board + * the bitmap handles: + * - The free areas + * - penalties (cell not occupied, but near occupied areas) + * - cells occupied by footprints, board cutout ... + */ +int genPlacementRoutingMatrix( BOARD* aBrd, EDA_MSG_PANEL* messagePanel ); + +/* searches for the optimal position of aModule. + * return 1 if placement impossible or 0 if OK. + */ +static int getOptimalModulePlacement( PCB_EDIT_FRAME* aFrame, + MODULE* aModule, wxDC* aDC ); + +/* + * Function compute_Ratsnest_PlaceModule + * displays the module's ratsnest during displacement, and assess the "cost" + * of the position. + * + * The cost is the longest ratsnest distance with penalty for connections + * approaching 45 degrees. + */ +static double compute_Ratsnest_PlaceModule( BOARD* aBrd ); + +/* Place a footprint on the Routing matrix. + */ +void genModuleOnRoutingMatrix( MODULE* Module ); +/* + * Displays the Placement/Routing matrix on the screen + */ +static void drawPlacementRoutingMatrix( BOARD* aBrd, wxDC* DC ); + +static int TstModuleOnBoard( BOARD* Pcb, MODULE* Module, bool TstOtherSide ); + +static void CreateKeepOutRectangle( int ux0, int uy0, int ux1, int uy1, + int marge, int aKeepOut, LSET aLayerMask ); + +static MODULE* PickModule( PCB_EDIT_FRAME* pcbframe, wxDC* DC ); +static int propagate(); + +void PCB_EDIT_FRAME::AutoPlaceModule( MODULE* Module, int place_mode, wxDC* DC ) +{ + MODULE* currModule = NULL; + wxPoint PosOK; + wxPoint memopos; + int error; + LAYER_ID lay_tmp_TOP, lay_tmp_BOTTOM; + + // Undo: init list + PICKED_ITEMS_LIST newList; + + newList.m_Status = UR_CHANGED; + ITEM_PICKER picker( NULL, UR_CHANGED ); + + if( GetBoard()->m_Modules == NULL ) + return; + + m_canvas->SetAbortRequest( false ); + + switch( place_mode ) + { + case PLACE_1_MODULE: + currModule = Module; + + if( currModule == NULL ) + return; + + currModule->SetIsPlaced( false ); + currModule->SetNeedsPlaced( false ); + break; + + case PLACE_OUT_OF_BOARD: + break; + + case PLACE_ALL: + + if( !IsOK( this, _( "Footprints NOT LOCKED will be moved" ) ) ) + return; + + break; + + case PLACE_INCREMENTAL: + + if( !IsOK( this, _( "Footprints NOT PLACED will be moved" ) ) ) + return; + + break; + } + + memopos = CurrPosition; + lay_tmp_BOTTOM = g_Route_Layer_BOTTOM; + lay_tmp_TOP = g_Route_Layer_TOP; + + RoutingMatrix.m_GridRouting = (int) GetScreen()->GetGridSize().x; + + // Ensure Board.m_GridRouting has a reasonable value: + if( RoutingMatrix.m_GridRouting < Millimeter2iu( 0.25 ) ) + RoutingMatrix.m_GridRouting = Millimeter2iu( 0.25 ); + + // Compute module parameters used in auto place + if( genPlacementRoutingMatrix( GetBoard(), m_messagePanel ) == 0 ) + return; + + int moduleCount = 0; + Module = GetBoard()->m_Modules; + + for( ; Module != NULL; Module = Module->Next() ) + { + Module->SetNeedsPlaced( false ); + + switch( place_mode ) + { + case PLACE_1_MODULE: + + if( currModule == Module ) + { + // Module will be placed, add to undo. + picker.SetItem( currModule ); + newList.PushItem( picker ); + Module->SetNeedsPlaced( true ); + } + + break; + + case PLACE_OUT_OF_BOARD: + Module->SetIsPlaced( false ); + + if( Module->IsLocked() ) + break; + + if( !RoutingMatrix.m_BrdBox.Contains( Module->GetPosition() ) ) + { + // Module will be placed, add to undo. + picker.SetItem( Module ); + newList.PushItem( picker ); + Module->SetNeedsPlaced( true ); + } + + break; + + case PLACE_ALL: + Module->SetIsPlaced( false ); + + if( Module->IsLocked() ) + break; + + // Module will be placed, add to undo. + picker.SetItem( Module ); + newList.PushItem( picker ); + Module->SetNeedsPlaced( true ); + break; + + case PLACE_INCREMENTAL: + + if( Module->IsLocked() ) + { + Module->SetIsPlaced( false ); + break; + } + + if( !Module->NeedsPlaced() ) + { + // Module will be placed, add to undo. + picker.SetItem( Module ); + newList.PushItem( picker ); + Module->SetNeedsPlaced( true ); + } + + break; + } + + if( Module->NeedsPlaced() ) // Erase from screen + { + moduleCount++; + Module->Draw( m_canvas, DC, GR_XOR ); + } + else + { + genModuleOnRoutingMatrix( Module ); + } + } + + // Undo command: prepare list + if( newList.GetCount() ) + SaveCopyInUndoList( newList, UR_CHANGED ); + + int cnt = 0; + wxString msg; + + while( ( Module = PickModule( this, DC ) ) != NULL ) + { + // Display some info about activity, module placement can take a while: + msg.Printf( _( "Place footprint %d of %d" ), cnt, moduleCount ); + SetStatusText( msg ); + + double initialOrient = Module->GetOrientation(); + // Display fill area of interest, barriers, penalties. + drawPlacementRoutingMatrix( GetBoard(), DC ); + + error = getOptimalModulePlacement( this, Module, DC ); + double bestScore = MinCout; + double bestRotation = 0.0; + int rotAllowed; + PosOK = CurrPosition; + + if( error == ESC ) + goto end_of_tst; + + // Try orientations 90, 180, 270 degrees from initial orientation + rotAllowed = Module->GetPlacementCost180(); + + if( rotAllowed != 0 ) + { + Rotate_Module( DC, Module, 1800.0, true ); + error = getOptimalModulePlacement( this, Module, DC ); + MinCout *= OrientPenality[rotAllowed]; + + if( bestScore > MinCout ) // This orientation is better. + { + PosOK = CurrPosition; + bestScore = MinCout; + bestRotation = 1800.0; + } + else + { + Rotate_Module( DC, Module, initialOrient, false ); + } + + if( error == ESC ) + goto end_of_tst; + } + + // Determine if the best orientation of a module is 90. + rotAllowed = Module->GetPlacementCost90(); + + if( rotAllowed != 0 ) + { + Rotate_Module( DC, Module, 900.0, true ); + error = getOptimalModulePlacement( this, Module, DC ); + MinCout *= OrientPenality[rotAllowed]; + + if( bestScore > MinCout ) // This orientation is better. + { + PosOK = CurrPosition; + bestScore = MinCout; + bestRotation = 900.0; + } + else + { + Rotate_Module( DC, Module, initialOrient, false ); + } + + if( error == ESC ) + goto end_of_tst; + } + + // Determine if the best orientation of a module is -90. + if( rotAllowed != 0 ) + { + Rotate_Module( DC, Module, 2700.0, true ); + error = getOptimalModulePlacement( this, Module, DC ); + MinCout *= OrientPenality[rotAllowed]; + + if( bestScore > MinCout ) // This orientation is better. + { + PosOK = CurrPosition; + bestScore = MinCout; + bestRotation = 2700.0; + } + else + { + Rotate_Module( DC, Module, initialOrient, false ); + } + + if( error == ESC ) + goto end_of_tst; + } + +end_of_tst: + + if( error == ESC ) + break; + + // Place module. + CurrPosition = GetCrossHairPosition(); + SetCrossHairPosition( PosOK ); + + PlaceModule( Module, DC ); + + bestRotation += initialOrient; + + if( bestRotation != Module->GetOrientation() ) + Rotate_Module( DC, Module, bestRotation, false ); + + SetCrossHairPosition( CurrPosition ); + + Module->CalculateBoundingBox(); + + genModuleOnRoutingMatrix( Module ); + Module->SetIsPlaced( true ); + Module->SetNeedsPlaced( false ); + } + + CurrPosition = memopos; + + RoutingMatrix.UnInitRoutingMatrix(); + + g_Route_Layer_TOP = lay_tmp_TOP; + g_Route_Layer_BOTTOM = lay_tmp_BOTTOM; + + Module = GetBoard()->m_Modules; + + for( ; Module != NULL; Module = Module->Next() ) + { + Module->CalculateBoundingBox(); + } + + GetBoard()->m_Status_Pcb = 0; + Compile_Ratsnest( DC, true ); + m_canvas->ReDraw( DC, true ); +} + + +void drawPlacementRoutingMatrix( BOARD* aBrd, wxDC* DC ) +{ + int ii, jj; + EDA_COLOR_T color; + int ox, oy; + MATRIX_CELL top_state, bottom_state; + + GRSetDrawMode( DC, GR_COPY ); + + for( ii = 0; ii < RoutingMatrix.m_Nrows; ii++ ) + { + oy = RoutingMatrix.m_BrdBox.GetY() + ( ii * RoutingMatrix.m_GridRouting ); + + for( jj = 0; jj < RoutingMatrix.m_Ncols; jj++ ) + { + ox = RoutingMatrix.m_BrdBox.GetX() + (jj * RoutingMatrix.m_GridRouting); + color = BLACK; + + top_state = RoutingMatrix.GetCell( ii, jj, TOP ); + bottom_state = RoutingMatrix.GetCell( ii, jj, BOTTOM ); + + if( top_state & CELL_is_ZONE ) + color = BLUE; + + // obstacles + if( ( top_state & CELL_is_EDGE ) || ( bottom_state & CELL_is_EDGE ) ) + color = WHITE; + else if( top_state & ( HOLE | CELL_is_MODULE ) ) + color = LIGHTRED; + else if( bottom_state & (HOLE | CELL_is_MODULE) ) + color = LIGHTGREEN; + else // Display the filling and keep out regions. + { + if( RoutingMatrix.GetDist( ii, jj, TOP ) + || RoutingMatrix.GetDist( ii, jj, BOTTOM ) ) + color = DARKGRAY; + } + + GRPutPixel( NULL, DC, ox, oy, color ); + } + } +} + + +int genPlacementRoutingMatrix( BOARD* aBrd, EDA_MSG_PANEL* messagePanel ) +{ + wxString msg; + + RoutingMatrix.UnInitRoutingMatrix(); + + EDA_RECT bbox = aBrd->ComputeBoundingBox( true ); + + if( bbox.GetWidth() == 0 || bbox.GetHeight() == 0 ) + { + DisplayError( NULL, _( "No PCB edge found, unknown board size!" ) ); + return 0; + } + + RoutingMatrix.ComputeMatrixSize( aBrd, true ); + int nbCells = RoutingMatrix.m_Ncols * RoutingMatrix.m_Nrows; + + messagePanel->EraseMsgBox(); + msg.Printf( wxT( "%d" ), RoutingMatrix.m_Ncols ); + messagePanel->SetMessage( 1, _( "Cols" ), msg, GREEN ); + msg.Printf( wxT( "%d" ), RoutingMatrix.m_Nrows ); + messagePanel->SetMessage( 7, _( "Lines" ), msg, GREEN ); + msg.Printf( wxT( "%d" ), nbCells ); + messagePanel->SetMessage( 14, _( "Cells." ), msg, YELLOW ); + + // Choose the number of board sides. + RoutingMatrix.m_RoutingLayersCount = 2; + + RoutingMatrix.InitRoutingMatrix(); + + // Display memory usage. + msg.Printf( wxT( "%d" ), RoutingMatrix.m_MemSize / 1024 ); + messagePanel->SetMessage( 24, wxT( "Mem(Kb)" ), msg, CYAN ); + + g_Route_Layer_BOTTOM = F_Cu; + + if( RoutingMatrix.m_RoutingLayersCount > 1 ) + g_Route_Layer_BOTTOM = B_Cu; + + g_Route_Layer_TOP = F_Cu; + + // Place the edge layer segments + TRACK TmpSegm( NULL ); + + TmpSegm.SetLayer( UNDEFINED_LAYER ); + TmpSegm.SetNetCode( -1 ); + TmpSegm.SetWidth( RoutingMatrix.m_GridRouting / 2 ); + + EDA_ITEM* PtStruct = aBrd->m_Drawings; + + for( ; PtStruct != NULL; PtStruct = PtStruct->Next() ) + { + DRAWSEGMENT* DrawSegm; + + switch( PtStruct->Type() ) + { + case PCB_LINE_T: + DrawSegm = (DRAWSEGMENT*) PtStruct; + + if( DrawSegm->GetLayer() != Edge_Cuts ) + break; + + TraceSegmentPcb( DrawSegm, HOLE | CELL_is_EDGE, + RoutingMatrix.m_GridRouting, WRITE_CELL ); + break; + + case PCB_TEXT_T: + default: + break; + } + } + + // Mark cells of the routing matrix to CELL_is_ZONE + // (i.e. availlable cell to place a module ) + // Init a starting point of attachment to the area. + RoutingMatrix.OrCell( RoutingMatrix.m_Nrows / 2, RoutingMatrix.m_Ncols / 2, + BOTTOM, CELL_is_ZONE ); + + // find and mark all other availlable cells: + for( int ii = 1; ii != 0; ) + ii = propagate(); + + // Initialize top layer. to the same value as the bottom layer + if( RoutingMatrix.m_BoardSide[TOP] ) + memcpy( RoutingMatrix.m_BoardSide[TOP], RoutingMatrix.m_BoardSide[BOTTOM], + nbCells * sizeof(MATRIX_CELL) ); + + return 1; +} + + +/* Place module on Routing matrix. + */ +void genModuleOnRoutingMatrix( MODULE* Module ) +{ + int ox, oy, fx, fy; + LSET layerMask; + D_PAD* Pad; + + EDA_RECT fpBBox = Module->GetBoundingBox(); + + fpBBox.Inflate( RoutingMatrix.m_GridRouting / 2 ); + ox = fpBBox.GetX(); + fx = fpBBox.GetRight(); + oy = fpBBox.GetY(); + fy = fpBBox.GetBottom(); + + if( ox < RoutingMatrix.m_BrdBox.GetX() ) + ox = RoutingMatrix.m_BrdBox.GetX(); + + if( ox > RoutingMatrix.m_BrdBox.GetRight() ) + ox = RoutingMatrix.m_BrdBox.GetRight(); + + if( fx < RoutingMatrix.m_BrdBox.GetX() ) + fx = RoutingMatrix.m_BrdBox.GetX(); + + if( fx > RoutingMatrix.m_BrdBox.GetRight() ) + fx = RoutingMatrix.m_BrdBox.GetRight(); + + if( oy < RoutingMatrix.m_BrdBox.GetY() ) + oy = RoutingMatrix.m_BrdBox.GetY(); + + if( oy > RoutingMatrix.m_BrdBox.GetBottom() ) + oy = RoutingMatrix.m_BrdBox.GetBottom(); + + if( fy < RoutingMatrix.m_BrdBox.GetY() ) + fy = RoutingMatrix.m_BrdBox.GetY(); + + if( fy > RoutingMatrix.m_BrdBox.GetBottom() ) + fy = RoutingMatrix.m_BrdBox.GetBottom(); + + if( Module->GetLayer() == F_Cu ) + layerMask.set( F_Cu ); + + if( Module->GetLayer() == B_Cu ) + layerMask.set( B_Cu ); + + TraceFilledRectangle( ox, oy, fx, fy, layerMask, + CELL_is_MODULE, WRITE_OR_CELL ); + + // Trace pads + clearance areas. + for( Pad = Module->Pads(); Pad != NULL; Pad = Pad->Next() ) + { + int margin = (RoutingMatrix.m_GridRouting / 2) + Pad->GetClearance(); + ::PlacePad( Pad, CELL_is_MODULE, margin, WRITE_OR_CELL ); + } + + // Trace clearance. + int margin = ( RoutingMatrix.m_GridRouting * Module->GetPadCount() ) / GAIN; + CreateKeepOutRectangle( ox, oy, fx, fy, margin, KEEP_OUT_MARGIN, layerMask ); +} + +// A minor helper function to draw a bounding box: +inline void draw_FootprintRect(EDA_RECT * aClipBox, wxDC* aDC, EDA_RECT& fpBBox, EDA_COLOR_T aColor) +{ +#ifndef USE_WX_OVERLAY + GRRect( aClipBox, aDC, fpBBox, 0, aColor ); +#endif +} + +int getOptimalModulePlacement( PCB_EDIT_FRAME* aFrame, MODULE* aModule, wxDC* aDC ) +{ + int error = 1; + wxPoint LastPosOK; + double min_cost, curr_cost, Score; + bool TstOtherSide; + DISPLAY_OPTIONS* displ_opts = (DISPLAY_OPTIONS*)aFrame->GetDisplayOptions(); + BOARD* brd = aFrame->GetBoard(); + + aModule->CalculateBoundingBox(); + + bool showRats = displ_opts->m_Show_Module_Ratsnest; + displ_opts->m_Show_Module_Ratsnest = false; + + brd->m_Status_Pcb &= ~RATSNEST_ITEM_LOCAL_OK; + aFrame->SetMsgPanel( aModule ); + + LastPosOK = RoutingMatrix.m_BrdBox.GetOrigin(); + + wxPoint mod_pos = aModule->GetPosition(); + EDA_RECT fpBBox = aModule->GetFootprintRect(); + + // Move fpBBox to have the footprint position at (0,0) + fpBBox.Move( -mod_pos ); + wxPoint fpBBoxOrg = fpBBox.GetOrigin(); + + // Calculate the limit of the footprint position, relative + // to the routing matrix area + wxPoint xylimit = RoutingMatrix.m_BrdBox.GetEnd() - fpBBox.GetEnd(); + + wxPoint initialPos = RoutingMatrix.m_BrdBox.GetOrigin() - fpBBoxOrg; + + // Stay on grid. + initialPos.x -= initialPos.x % RoutingMatrix.m_GridRouting; + initialPos.y -= initialPos.y % RoutingMatrix.m_GridRouting; + + CurrPosition = initialPos; + + // Undraw the current footprint + aModule->DrawOutlinesWhenMoving( aFrame->GetCanvas(), aDC, wxPoint( 0, 0 ) ); + + g_Offset_Module = mod_pos - CurrPosition; + + /* Examine pads, and set TstOtherSide to true if a footprint + * has at least 1 pad through. + */ + TstOtherSide = false; + + if( RoutingMatrix.m_RoutingLayersCount > 1 ) + { + LSET other( aModule->GetLayer() == B_Cu ? F_Cu : B_Cu ); + + for( D_PAD* pad = aModule->Pads(); pad; pad = pad->Next() ) + { + if( !( pad->GetLayerSet() & other ).any() ) + continue; + + TstOtherSide = true; + break; + } + } + + // Draw the initial bounding box position + EDA_COLOR_T color = BROWN; + fpBBox.SetOrigin( fpBBoxOrg + CurrPosition ); + draw_FootprintRect(aFrame->GetCanvas()->GetClipBox(), aDC, fpBBox, color); + + min_cost = -1.0; + aFrame->SetStatusText( wxT( "Score ??, pos ??" ) ); + + for( ; CurrPosition.x < xylimit.x; CurrPosition.x += RoutingMatrix.m_GridRouting ) + { + wxYield(); + + if( aFrame->GetCanvas()->GetAbortRequest() ) + { + if( IsOK( aFrame, _( "OK to abort?" ) ) ) + { + displ_opts->m_Show_Module_Ratsnest = showRats; + return ESC; + } + else + aFrame->GetCanvas()->SetAbortRequest( false ); + } + + CurrPosition.y = initialPos.y; + + for( ; CurrPosition.y < xylimit.y; CurrPosition.y += RoutingMatrix.m_GridRouting ) + { + // Erase traces. + draw_FootprintRect( aFrame->GetCanvas()->GetClipBox(), aDC, fpBBox, color ); + + fpBBox.SetOrigin( fpBBoxOrg + CurrPosition ); + g_Offset_Module = mod_pos - CurrPosition; + int keepOutCost = TstModuleOnBoard( brd, aModule, TstOtherSide ); + + // Draw at new place + color = keepOutCost >= 0 ? BROWN : RED; + draw_FootprintRect( aFrame->GetCanvas()->GetClipBox(), aDC, fpBBox, color ); + + if( keepOutCost >= 0 ) // i.e. if the module can be put here + { + error = 0; + aFrame->build_ratsnest_module( aModule ); + curr_cost = compute_Ratsnest_PlaceModule( brd ); + Score = curr_cost + keepOutCost; + + if( (min_cost >= Score ) || (min_cost < 0 ) ) + { + LastPosOK = CurrPosition; + min_cost = Score; + wxString msg; + msg.Printf( wxT( "Score %g, pos %s, %s" ), + min_cost, + GetChars( ::CoordinateToString( LastPosOK.x ) ), + GetChars( ::CoordinateToString( LastPosOK.y ) ) ); + aFrame->SetStatusText( msg ); + } + } + } + } + + // erasing the last traces + GRRect( aFrame->GetCanvas()->GetClipBox(), aDC, fpBBox, 0, BROWN ); + + displ_opts->m_Show_Module_Ratsnest = showRats; + + // Regeneration of the modified variable. + CurrPosition = LastPosOK; + + brd->m_Status_Pcb &= ~( RATSNEST_ITEM_LOCAL_OK | LISTE_PAD_OK ); + + MinCout = min_cost; + return error; +} + + +/* Test if the rectangular area (ux, ux .. y0, y1): + * - is a free zone (except OCCUPED_By_MODULE returns) + * - is on the working surface of the board (otherwise returns OUT_OF_BOARD) + * + * Returns OUT_OF_BOARD, or OCCUPED_By_MODULE or FREE_CELL if OK + */ +int TstRectangle( BOARD* Pcb, const EDA_RECT& aRect, int side ) +{ + EDA_RECT rect = aRect; + + rect.Inflate( RoutingMatrix.m_GridRouting / 2 ); + + wxPoint start = rect.GetOrigin(); + wxPoint end = rect.GetEnd(); + + start -= RoutingMatrix.m_BrdBox.GetOrigin(); + end -= RoutingMatrix.m_BrdBox.GetOrigin(); + + int row_min = start.y / RoutingMatrix.m_GridRouting; + int row_max = end.y / RoutingMatrix.m_GridRouting; + int col_min = start.x / RoutingMatrix.m_GridRouting; + int col_max = end.x / RoutingMatrix.m_GridRouting; + + if( start.y > row_min * RoutingMatrix.m_GridRouting ) + row_min++; + + if( start.x > col_min * RoutingMatrix.m_GridRouting ) + col_min++; + + if( row_min < 0 ) + row_min = 0; + + if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) ) + row_max = RoutingMatrix.m_Nrows - 1; + + if( col_min < 0 ) + col_min = 0; + + if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) ) + col_max = RoutingMatrix.m_Ncols - 1; + + for( int row = row_min; row <= row_max; row++ ) + { + for( int col = col_min; col <= col_max; col++ ) + { + unsigned int data = RoutingMatrix.GetCell( row, col, side ); + + if( ( data & CELL_is_ZONE ) == 0 ) + return OUT_OF_BOARD; + + if( (data & CELL_is_MODULE) ) + return OCCUPED_By_MODULE; + } + } + + return FREE_CELL; +} + + +/* Calculates and returns the clearance area of the rectangular surface + * aRect): + * (Sum of cells in terms of distance) + */ +unsigned int CalculateKeepOutArea( const EDA_RECT& aRect, int side ) +{ + wxPoint start = aRect.GetOrigin(); + wxPoint end = aRect.GetEnd(); + + start -= RoutingMatrix.m_BrdBox.GetOrigin(); + end -= RoutingMatrix.m_BrdBox.GetOrigin(); + + int row_min = start.y / RoutingMatrix.m_GridRouting; + int row_max = end.y / RoutingMatrix.m_GridRouting; + int col_min = start.x / RoutingMatrix.m_GridRouting; + int col_max = end.x / RoutingMatrix.m_GridRouting; + + if( start.y > row_min * RoutingMatrix.m_GridRouting ) + row_min++; + + if( start.x > col_min * RoutingMatrix.m_GridRouting ) + col_min++; + + if( row_min < 0 ) + row_min = 0; + + if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) ) + row_max = RoutingMatrix.m_Nrows - 1; + + if( col_min < 0 ) + col_min = 0; + + if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) ) + col_max = RoutingMatrix.m_Ncols - 1; + + unsigned int keepOutCost = 0; + + for( int row = row_min; row <= row_max; row++ ) + { + for( int col = col_min; col <= col_max; col++ ) + { + // RoutingMatrix.GetDist returns the "cost" of the cell + // at position (row, col) + // in autoplace this is the cost of the cell, if it is + // inside aRect + keepOutCost += RoutingMatrix.GetDist( row, col, side ); + } + } + + return keepOutCost; +} + + +/* Test if the module can be placed on the board. + * Returns the value TstRectangle(). + * Module is known by its bounding box + */ +int TstModuleOnBoard( BOARD* Pcb, MODULE* aModule, bool TstOtherSide ) +{ + int side = TOP; + int otherside = BOTTOM; + + if( aModule->GetLayer() == B_Cu ) + { + side = BOTTOM; otherside = TOP; + } + + EDA_RECT fpBBox = aModule->GetFootprintRect(); + fpBBox.Move( -g_Offset_Module ); + + int diag = TstRectangle( Pcb, fpBBox, side ); + + if( diag != FREE_CELL ) + return diag; + + if( TstOtherSide ) + { + diag = TstRectangle( Pcb, fpBBox, otherside ); + + if( diag != FREE_CELL ) + return diag; + } + + int marge = ( RoutingMatrix.m_GridRouting * aModule->GetPadCount() ) / GAIN; + + fpBBox.Inflate( marge ); + return CalculateKeepOutArea( fpBBox, side ); +} + + +double compute_Ratsnest_PlaceModule( BOARD* aBrd ) +{ + double curr_cost; + wxPoint start; // start point of a ratsnest + wxPoint end; // end point of a ratsnest + int dx, dy; + + if( ( aBrd->m_Status_Pcb & RATSNEST_ITEM_LOCAL_OK ) == 0 ) + return -1; + + curr_cost = 0; + + for( unsigned ii = 0; ii < aBrd->m_LocalRatsnest.size(); ii++ ) + { + RATSNEST_ITEM* pt_local_rats_nest = &aBrd->m_LocalRatsnest[ii]; + + if( ( pt_local_rats_nest->m_Status & LOCAL_RATSNEST_ITEM ) ) + continue; // Skip ratsnest between 2 pads of the current module + + // Skip modules not inside the board area + MODULE* module = pt_local_rats_nest->m_PadEnd->GetParent(); + + if( !RoutingMatrix.m_BrdBox.Contains( module->GetPosition() ) ) + continue; + + start = pt_local_rats_nest->m_PadStart->GetPosition() - g_Offset_Module; + end = pt_local_rats_nest->m_PadEnd->GetPosition(); + + // Cost of the ratsnest. + dx = end.x - start.x; + dy = end.y - start.y; + + dx = abs( dx ); + dy = abs( dy ); + + // ttry to have always dx >= dy to calculate the cost of the rastsnet + if( dx < dy ) + std::swap( dx, dy ); + + // Cost of the connection = lenght + penalty due to the slope + // dx is the biggest lenght relative to the X or Y axis + // the penalty is max for 45 degrees ratsnests, + // and 0 for horizontal or vertical ratsnests. + // For Horizontal and Vertical ratsnests, dy = 0; + double conn_cost = hypot( dx, dy * 2.0 ); + curr_cost += conn_cost; // Total cost = sum of costs of each connection + } + + return curr_cost; +} + + +/** + * Function CreateKeepOutRectangle + * builds the cost map: + * Cells ( in Dist map ) inside the rect x0,y0 a x1,y1 are + * incremented by value aKeepOut + * Cell outside this rectangle, but inside the rectangle + * x0,y0 -marge to x1,y1 + marge are incremented by a decreasing value + * (aKeepOut ... 0). The decreasing value depends on the distance to the first rectangle + * Therefore the cost is high in rect x0,y0 to x1,y1, and decrease outside this rectangle + */ +void CreateKeepOutRectangle( int ux0, int uy0, int ux1, int uy1, + int marge, int aKeepOut, LSET aLayerMask ) +{ + int row, col; + int row_min, row_max, col_min, col_max, pmarge; + int trace = 0; + DIST_CELL data, LocalKeepOut; + int lgain, cgain; + + if( aLayerMask[g_Route_Layer_BOTTOM] ) + trace = 1; // Trace on bottom layer. + + if( aLayerMask[g_Route_Layer_TOP] && RoutingMatrix.m_RoutingLayersCount ) + trace |= 2; // Trace on top layer. + + if( trace == 0 ) + return; + + ux0 -= RoutingMatrix.m_BrdBox.GetX(); + uy0 -= RoutingMatrix.m_BrdBox.GetY(); + ux1 -= RoutingMatrix.m_BrdBox.GetX(); + uy1 -= RoutingMatrix.m_BrdBox.GetY(); + + ux0 -= marge; ux1 += marge; + uy0 -= marge; uy1 += marge; + + pmarge = marge / RoutingMatrix.m_GridRouting; + + if( pmarge < 1 ) + pmarge = 1; + + // Calculate the coordinate limits of the rectangle. + row_max = uy1 / RoutingMatrix.m_GridRouting; + col_max = ux1 / RoutingMatrix.m_GridRouting; + row_min = uy0 / RoutingMatrix.m_GridRouting; + + if( uy0 > row_min * RoutingMatrix.m_GridRouting ) + row_min++; + + col_min = ux0 / RoutingMatrix.m_GridRouting; + + if( ux0 > col_min * RoutingMatrix.m_GridRouting ) + col_min++; + + if( row_min < 0 ) + row_min = 0; + + if( row_max >= (RoutingMatrix.m_Nrows - 1) ) + row_max = RoutingMatrix.m_Nrows - 1; + + if( col_min < 0 ) + col_min = 0; + + if( col_max >= (RoutingMatrix.m_Ncols - 1) ) + col_max = RoutingMatrix.m_Ncols - 1; + + for( row = row_min; row <= row_max; row++ ) + { + lgain = 256; + + if( row < pmarge ) + lgain = ( 256 * row ) / pmarge; + else if( row > row_max - pmarge ) + lgain = ( 256 * ( row_max - row ) ) / pmarge; + + for( col = col_min; col <= col_max; col++ ) + { + // RoutingMatrix Dist map containt the "cost" of the cell + // at position (row, col) + // in autoplace this is the cost of the cell, when + // a footprint overlaps it, near a "master" footprint + // this cost is hight near the "master" footprint + // and decrease with the distance + cgain = 256; + LocalKeepOut = aKeepOut; + + if( col < pmarge ) + cgain = ( 256 * col ) / pmarge; + else if( col > col_max - pmarge ) + cgain = ( 256 * ( col_max - col ) ) / pmarge; + + cgain = ( cgain * lgain ) / 256; + + if( cgain != 256 ) + LocalKeepOut = ( LocalKeepOut * cgain ) / 256; + + if( trace & 1 ) + { + data = RoutingMatrix.GetDist( row, col, BOTTOM ) + LocalKeepOut; + RoutingMatrix.SetDist( row, col, BOTTOM, data ); + } + + if( trace & 2 ) + { + data = RoutingMatrix.GetDist( row, col, TOP ); + data = std::max( data, LocalKeepOut ); + RoutingMatrix.SetDist( row, col, TOP, data ); + } + } + } +} + + +// Sort routines +static bool Tri_PlaceModules( MODULE* ref, MODULE* compare ) +{ + double ff1, ff2; + + ff1 = ref->GetArea() * ref->GetPadCount(); + ff2 = compare->GetArea() * compare->GetPadCount(); + + return ff2 < ff1; +} + + +static bool sortFootprintsByRatsnestSize( MODULE* ref, MODULE* compare ) +{ + double ff1, ff2; + + ff1 = ref->GetArea() * ref->GetFlag(); + ff2 = compare->GetArea() * compare->GetFlag(); + return ff2 < ff1; +} + + +/** + * Function PickModule + * find the "best" module place + * The criteria are: + * - Maximum ratsnest with modules already placed + * - Max size, and number of pads max + */ +static MODULE* PickModule( PCB_EDIT_FRAME* pcbframe, wxDC* DC ) +{ + MODULE* Module; + std::vector <MODULE*> moduleList; + + // Build sorted footprints list (sort by decreasing size ) + Module = pcbframe->GetBoard()->m_Modules; + + for( ; Module != NULL; Module = Module->Next() ) + { + Module->CalculateBoundingBox(); + moduleList.push_back( Module ); + } + + sort( moduleList.begin(), moduleList.end(), Tri_PlaceModules ); + + for( unsigned ii = 0; ii < moduleList.size(); ii++ ) + { + Module = moduleList[ii]; + Module->SetFlag( 0 ); + + if( !Module->NeedsPlaced() ) + continue; + + pcbframe->GetBoard()->m_Status_Pcb &= ~RATSNEST_ITEM_LOCAL_OK; + pcbframe->SetMsgPanel( Module ); + pcbframe->build_ratsnest_module( Module ); + + // Calculate external ratsnest. + for( unsigned ii = 0; ii < pcbframe->GetBoard()->m_LocalRatsnest.size(); ii++ ) + { + if( ( pcbframe->GetBoard()->m_LocalRatsnest[ii].m_Status & + LOCAL_RATSNEST_ITEM ) == 0 ) + Module->IncrementFlag(); + } + } + + pcbframe->GetBoard()->m_Status_Pcb &= ~RATSNEST_ITEM_LOCAL_OK; + + sort( moduleList.begin(), moduleList.end(), sortFootprintsByRatsnestSize ); + + // Search for "best" module. + MODULE* bestModule = NULL; + MODULE* altModule = NULL; + + for( unsigned ii = 0; ii < moduleList.size(); ii++ ) + { + Module = moduleList[ii]; + + if( !Module->NeedsPlaced() ) + continue; + + altModule = Module; + + if( Module->GetFlag() == 0 ) + continue; + + bestModule = Module; + break; + } + + if( bestModule ) + return bestModule; + else + return altModule; +} + + +/** + * Function propagate + * Used only in autoplace calculations + * Uses the routing matrix to fill the cells within the zone + * Search and mark cells within the zone, and agree with DRC options. + * Requirements: + * Start from an initial point, to fill zone + * The zone must have no "copper island" + * Algorithm: + * If the current cell has a neighbor flagged as "cell in the zone", it + * become a cell in the zone + * The first point in the zone is the starting point + * 4 searches within the matrix are made: + * 1 - Left to right and top to bottom + * 2 - Right to left and top to bottom + * 3 - bottom to top and Right to left + * 4 - bottom to top and Left to right + * Given the current cell, for each search, we consider the 2 neighbor cells + * the previous cell on the same line and the previous cell on the same column. + * + * This function can request some iterations + * Iterations are made until no cell is added to the zone. + * @return added cells count (i.e. which the attribute CELL_is_ZONE is set) + */ +int propagate() +{ + int row, col; + long current_cell, old_cell_H; + std::vector<long> pt_cell_V; + int nbpoints = 0; + +#define NO_CELL_ZONE (HOLE | CELL_is_EDGE | CELL_is_ZONE) + + pt_cell_V.reserve( std::max( RoutingMatrix.m_Nrows, RoutingMatrix.m_Ncols ) ); + fill( pt_cell_V.begin(), pt_cell_V.end(), 0 ); + + // Search from left to right and top to bottom. + for( row = 0; row < RoutingMatrix.m_Nrows; row++ ) + { + old_cell_H = 0; + + for( col = 0; col < RoutingMatrix.m_Ncols; col++ ) + { + current_cell = RoutingMatrix.GetCell( row, col, BOTTOM ) & NO_CELL_ZONE; + + if( current_cell == 0 ) // a free cell is found + { + if( (old_cell_H & CELL_is_ZONE) || (pt_cell_V[col] & CELL_is_ZONE) ) + { + RoutingMatrix.OrCell( row, col, BOTTOM, CELL_is_ZONE ); + current_cell = CELL_is_ZONE; + nbpoints++; + } + } + + pt_cell_V[col] = old_cell_H = current_cell; + } + } + + // Search from right to left and top to bottom/ + fill( pt_cell_V.begin(), pt_cell_V.end(), 0 ); + + for( row = 0; row < RoutingMatrix.m_Nrows; row++ ) + { + old_cell_H = 0; + + for( col = RoutingMatrix.m_Ncols - 1; col >= 0; col-- ) + { + current_cell = RoutingMatrix.GetCell( row, col, BOTTOM ) & NO_CELL_ZONE; + + if( current_cell == 0 ) // a free cell is found + { + if( (old_cell_H & CELL_is_ZONE) || (pt_cell_V[col] & CELL_is_ZONE) ) + { + RoutingMatrix.OrCell( row, col, BOTTOM, CELL_is_ZONE ); + current_cell = CELL_is_ZONE; + nbpoints++; + } + } + + pt_cell_V[col] = old_cell_H = current_cell; + } + } + + // Search from bottom to top and right to left. + fill( pt_cell_V.begin(), pt_cell_V.end(), 0 ); + + for( col = RoutingMatrix.m_Ncols - 1; col >= 0; col-- ) + { + old_cell_H = 0; + + for( row = RoutingMatrix.m_Nrows - 1; row >= 0; row-- ) + { + current_cell = RoutingMatrix.GetCell( row, col, BOTTOM ) & NO_CELL_ZONE; + + if( current_cell == 0 ) // a free cell is found + { + if( (old_cell_H & CELL_is_ZONE) || (pt_cell_V[row] & CELL_is_ZONE) ) + { + RoutingMatrix.OrCell( row, col, BOTTOM, CELL_is_ZONE ); + current_cell = CELL_is_ZONE; + nbpoints++; + } + } + + pt_cell_V[row] = old_cell_H = current_cell; + } + } + + // Search from bottom to top and left to right. + fill( pt_cell_V.begin(), pt_cell_V.end(), 0 ); + + for( col = 0; col < RoutingMatrix.m_Ncols; col++ ) + { + old_cell_H = 0; + + for( row = RoutingMatrix.m_Nrows - 1; row >= 0; row-- ) + { + current_cell = RoutingMatrix.GetCell( row, col, BOTTOM ) & NO_CELL_ZONE; + + if( current_cell == 0 ) // a free cell is found + { + if( (old_cell_H & CELL_is_ZONE) || (pt_cell_V[row] & CELL_is_ZONE) ) + { + RoutingMatrix.OrCell( row, col, BOTTOM, CELL_is_ZONE ); + current_cell = CELL_is_ZONE; + nbpoints++; + } + } + + pt_cell_V[row] = old_cell_H = current_cell; + } + } + + return nbpoints; +} diff --git a/pcbnew/autorouter/autorout.cpp b/pcbnew/autorouter/autorout.cpp new file mode 100644 index 0000000..7c53f0e --- /dev/null +++ b/pcbnew/autorouter/autorout.cpp @@ -0,0 +1,277 @@ +/** + * @file autorout.cpp + * @brief Autorouting command and control. + */ + +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2012 KiCad Developers, see change_log.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 <fctsys.h> +#include <class_drawpanel.h> +#include <wxPcbStruct.h> +#include <gr_basic.h> +#include <msgpanel.h> + +#include <pcbnew.h> +#include <cell.h> +#include <zones.h> + +#include <class_board.h> +#include <class_module.h> +#include <class_track.h> +#include <convert_to_biu.h> + +#include <autorout.h> + + +MATRIX_ROUTING_HEAD RoutingMatrix; // routing matrix (grid) to route 2-sided boards + +/* init board, route traces*/ +void PCB_EDIT_FRAME::Autoroute( wxDC* DC, int mode ) +{ + int start, stop; + MODULE* Module = NULL; + D_PAD* Pad = NULL; + int autoroute_net_code = -1; + wxString msg; + + if( GetBoard()->GetCopperLayerCount() > 1 ) + { + g_Route_Layer_TOP = GetScreen()->m_Route_Layer_TOP; + g_Route_Layer_BOTTOM = GetScreen()->m_Route_Layer_BOTTOM; + } + else + { + g_Route_Layer_TOP = g_Route_Layer_BOTTOM = B_Cu; + } + + switch( mode ) + { + case ROUTE_NET: + if( GetScreen()->GetCurItem() ) + { + switch( GetScreen()->GetCurItem()->Type() ) + { + case PCB_PAD_T: + Pad = (D_PAD*) GetScreen()->GetCurItem(); + autoroute_net_code = Pad->GetNetCode(); + break; + + default: + break; + } + } + if( autoroute_net_code <= 0 ) + { + wxMessageBox( _( "Net not selected" ) ); return; + } + break; + + case ROUTE_MODULE: + Module = (MODULE*) GetScreen()->GetCurItem(); + if( (Module == NULL) || (Module->Type() != PCB_MODULE_T) ) + { + wxMessageBox( _( "Footprint not selected" ) ); + return; + } + break; + + case ROUTE_PAD: + Pad = (D_PAD*) GetScreen()->GetCurItem(); + + if( (Pad == NULL) || (Pad->Type() != PCB_PAD_T) ) + { + wxMessageBox( _( "Pad not selected" ) ); + return; + } + + break; + } + + if( (GetBoard()->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK ) == 0 ) + Compile_Ratsnest( DC, true ); + + /* Set the flag on the ratsnest to CH_ROUTE_REQ. */ + for( unsigned ii = 0; ii < GetBoard()->GetRatsnestsCount(); ii++ ) + { + RATSNEST_ITEM* ptmp = &GetBoard()->m_FullRatsnest[ii]; + ptmp->m_Status &= ~CH_ROUTE_REQ; + + switch( mode ) + { + case ROUTE_ALL: + ptmp->m_Status |= CH_ROUTE_REQ; + break; + + case ROUTE_NET: + if( autoroute_net_code == ptmp->GetNet() ) + ptmp->m_Status |= CH_ROUTE_REQ; + break; + + case ROUTE_MODULE: + { + D_PAD* pt_pad = (D_PAD*) Module->Pads(); + for( ; pt_pad != NULL; pt_pad = pt_pad->Next() ) + { + if( ptmp->m_PadStart == pt_pad ) + ptmp->m_Status |= CH_ROUTE_REQ; + + if( ptmp->m_PadEnd == pt_pad ) + ptmp->m_Status |= CH_ROUTE_REQ; + } + + break; + } + + case ROUTE_PAD: + if( ( ptmp->m_PadStart == Pad ) || ( ptmp->m_PadEnd == Pad ) ) + ptmp->m_Status |= CH_ROUTE_REQ; + + break; + } + } + + start = time( NULL ); + + /* Calculation of no fixed routing to 5 mils and more. */ + RoutingMatrix.m_GridRouting = (int)GetScreen()->GetGridSize().x; + + if( RoutingMatrix.m_GridRouting < (5*IU_PER_MILS) ) + RoutingMatrix.m_GridRouting = 5*IU_PER_MILS; + + + /* Calculated ncol and nrow, matrix size for routing. */ + RoutingMatrix.ComputeMatrixSize( GetBoard() ); + + m_messagePanel->EraseMsgBox(); + + /* Map the board */ + RoutingMatrix.m_RoutingLayersCount = 1; + + if( g_Route_Layer_TOP != g_Route_Layer_BOTTOM ) + RoutingMatrix.m_RoutingLayersCount = 2; + + if( RoutingMatrix.InitRoutingMatrix() < 0 ) + { + wxMessageBox( _( "No memory for autorouting" ) ); + RoutingMatrix.UnInitRoutingMatrix(); /* Free memory. */ + return; + } + + SetStatusText( _( "Place Cells" ) ); + PlaceCells( GetBoard(), -1, FORCE_PADS ); + + /* Construction of the track list for router. */ + RoutingMatrix.m_RouteCount = Build_Work( GetBoard() ); + + // DisplayRoutingMatrix( m_canvas, DC ); + + Solve( DC, RoutingMatrix.m_RoutingLayersCount ); + + /* Free memory. */ + FreeQueue(); + InitWork(); /* Free memory for the list of router connections. */ + RoutingMatrix.UnInitRoutingMatrix(); + stop = time( NULL ) - start; + msg.Printf( wxT( "time = %d second%s" ), stop, ( stop == 1 ) ? wxT( "" ) : wxT( "s" ) ); + SetStatusText( msg ); +} + + +/* Clear the flag CH_NOROUTABLE which is set to 1 by Solve(), + * when a track was not routed. + * (If this flag is 1 the corresponding track it is not rerouted) + */ +void PCB_EDIT_FRAME::Reset_Noroutable( wxDC* DC ) +{ + if( ( GetBoard()->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK )== 0 ) + Compile_Ratsnest( DC, true ); + + for( unsigned ii = 0; ii < GetBoard()->GetRatsnestsCount(); ii++ ) + { + GetBoard()->m_FullRatsnest[ii].m_Status &= ~CH_UNROUTABLE; + } +} + + +/* DEBUG Function: displays the routing matrix */ +void DisplayRoutingMatrix( EDA_DRAW_PANEL* panel, wxDC* DC ) +{ + int dcell0; + EDA_COLOR_T color; + + int maxi = 600 / RoutingMatrix.m_Ncols; + maxi = ( maxi * 3 ) / 4; + + if( !maxi ) + maxi = 1; + + GRSetDrawMode( DC, GR_COPY ); + + for( int col = 0; col < RoutingMatrix.m_Ncols; col++ ) + { + for( int row = 0; row < RoutingMatrix.m_Nrows; row++ ) + { + color = BLACK; + dcell0 = RoutingMatrix.GetCell( row, col, BOTTOM ); + + if( dcell0 & HOLE ) + color = GREEN; + +#if 0 + int dcell1 = 0; + + if( RoutingMatrix.m_RoutingLayersCount ) + dcell1 = GetCell( row, col, TOP ); + + if( dcell1 & HOLE ) + color = RED; + + dcell0 |= dcell1; +#endif + if( !color && ( dcell0 & VIA_IMPOSSIBLE ) ) + color = BLUE; + + if( dcell0 & CELL_is_EDGE ) + color = YELLOW; + else if( dcell0 & CELL_is_ZONE ) + color = YELLOW; + + #define DRAW_OFFSET_X -20 + #define DRAW_OFFSET_Y 20 +// if( color ) + { + for( int i = 0; i < maxi; i++ ) + for( int j = 0; j < maxi; j++ ) + GRPutPixel( panel->GetClipBox(), DC, + ( col * maxi ) + i + DRAW_OFFSET_X, + ( row * maxi ) + j + DRAW_OFFSET_Y, color ); + + } + } + } +} diff --git a/pcbnew/autorouter/autorout.h b/pcbnew/autorouter/autorout.h new file mode 100644 index 0000000..348191f --- /dev/null +++ b/pcbnew/autorouter/autorout.h @@ -0,0 +1,236 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2012 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2012 KiCad Developers, see change_log.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 autorout.h + */ + +#ifndef AUTOROUT_H +#define AUTOROUT_H + + +#include <base_struct.h> +#include <layers_id_colors_and_visibility.h> + + +class BOARD; +class DRAWSEGMENT; + + +#define TOP 0 +#define BOTTOM 1 +#define EMPTY 0 +#define ILLEGAL -1 + + +/* Autorouter commands. */ +enum AUTOPLACEROUTE_OPTIONS +{ + PLACE_ALL, + PLACE_OUT_OF_BOARD, + PLACE_INCREMENTAL, + PLACE_1_MODULE, + + ROUTE_ALL, + ROUTE_NET, + ROUTE_MODULE, + ROUTE_PAD +}; + +#define MAX_ROUTING_LAYERS_COUNT 2 + +#define FORCE_PADS 1 /* Force placement of pads for any Netcode */ + +/* search statistics */ +extern int OpenNodes; /* total number of nodes opened */ +extern int ClosNodes; /* total number of nodes closed */ +extern int MoveNodes; /* total number of nodes moved */ +extern int MaxNodes; /* maximum number of nodes opened at one time */ + + +/* Structures useful to the generation of board as bitmap. */ +typedef char MATRIX_CELL; +typedef int DIST_CELL; +typedef char DIR_CELL; + + +/** + * class MATRIX_ROUTING_HEAD + * handle the matrix routing that describes the actual board + */ +class MATRIX_ROUTING_HEAD +{ +public: + MATRIX_CELL* m_BoardSide[MAX_ROUTING_LAYERS_COUNT]; // the image map of 2 board sides + DIST_CELL* m_DistSide[MAX_ROUTING_LAYERS_COUNT]; // the image map of 2 board sides: + // distance to cells + DIR_CELL* m_DirSide[MAX_ROUTING_LAYERS_COUNT]; // the image map of 2 board sides: + // pointers back to source + bool m_InitMatrixDone; + int m_RoutingLayersCount; // Number of layers for autorouting (0 or 1) + int m_GridRouting; // Size of grid for autoplace/autoroute + EDA_RECT m_BrdBox; // Actual board bounding box + int m_Nrows, m_Ncols; // Matrix size + int m_MemSize; // Memory requirement, just for statistics + int m_RouteCount; // Number of routes + +private: + // a pointer to the current selected cell operation + void (MATRIX_ROUTING_HEAD::* m_opWriteCell)( int aRow, int aCol, + int aSide, MATRIX_CELL aCell); + +public: + MATRIX_ROUTING_HEAD(); + ~MATRIX_ROUTING_HEAD(); + + void WriteCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell) + { + (*this.*m_opWriteCell)( aRow, aCol, aSide, aCell ); + } + + /** + * function GetBrdCoordOrigin + * @return the board coordinate corresponding to the + * routing matrix origin ( board coordinate offset ) + */ + wxPoint GetBrdCoordOrigin() + { + return m_BrdBox.GetOrigin(); + } + + /** + * Function ComputeMatrixSize + * calculates the number of rows and columns of dimensions of \a aPcb for routing and + * automatic calculation of area. + * @param aPcb = the physical board + * @param aUseBoardEdgesOnly = true to use board edges only, + * = false to use the full board bounding box (default) + */ + bool ComputeMatrixSize( BOARD* aPcb, bool aUseBoardEdgesOnly = false ); + + /** + * Function InitBoard + * initializes the data structures. + * + * @return the amount of memory used or -1 if default. + */ + int InitRoutingMatrix(); + + void UnInitRoutingMatrix(); + + // Initialize WriteCell to make the aLogicOp + void SetCellOperation( int aLogicOp ); + + // functions to read/write one cell ( point on grid routing matrix: + MATRIX_CELL GetCell( int aRow, int aCol, int aSide); + void SetCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell); + void OrCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell); + void XorCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell); + void AndCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell); + void AddCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell); + DIST_CELL GetDist( int aRow, int aCol, int aSide ); + void SetDist( int aRow, int aCol, int aSide, DIST_CELL ); + int GetDir( int aRow, int aCol, int aSide ); + void SetDir( int aRow, int aCol, int aSide, int aDir); + + // calculate distance (with penalty) of a trace through a cell + int CalcDist(int x,int y,int z ,int side ); + + // calculate approximate distance (manhattan distance) + int GetApxDist( int r1, int c1, int r2, int c2 ); +}; + +extern MATRIX_ROUTING_HEAD RoutingMatrix; /* 2-sided board */ + + +/* Constants used to trace the cells on the BOARD */ +#define WRITE_CELL 0 +#define WRITE_OR_CELL 1 +#define WRITE_XOR_CELL 2 +#define WRITE_AND_CELL 3 +#define WRITE_ADD_CELL 4 + +// Functions: + +class PCB_EDIT_FRAME; +class BOARD; +class D_PAD; +class RATSNEST_ITEM; +class TRACK; + + +/* Initialize a color value, the cells included in the board edge of the + * pad surface by pt_pad, with the margin reserved for isolation and the + * half width of the runway + * Parameters: + * Pt_pad: pointer to the description of the pad + * color: mask write in cells + * margin: add a value to the radius or half the score pad + * op_logic: type of writing in the cell (WRITE, OR) + */ +void PlacePad( D_PAD* pt_pad, int type, int marge, int op_logic ); + +/* Draws a segment of track on the board. */ +void TraceSegmentPcb( TRACK* pt_segm, int type, int marge, int op_logic ); +void TraceSegmentPcb( DRAWSEGMENT* pt_segm, int type, int marge, int op_logic ); + +/* Uses the color value of all cells included in the board + * coord of the rectangle ux0, uy0 (top right corner) + * a ux1, uy1 (lower left corner) (coord PCB) + * the rectangle is horizontal (or vertical) + * masque_layer = mask layers; + * op_logic = WRITE_CELL, WRITE_OR_CELL, WRITE_XOR_CELL, WRITE_AND_CELL + */ +void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1, + LSET side, int color, int op_logic); + + +/* Same as above, but the rectangle is inclined angle angle. */ +void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1, + double angle, LSET masque_layer, + int color, int op_logic ); + +/* QUEUE.CPP */ +void FreeQueue(); +void InitQueue(); +void GetQueue( int *, int *, int *, int *, int * ); +bool SetQueue( int, int, int, int, int, int, int ); +void ReSetQueue( int, int, int, int, int, int, int ); + +/* WORK.CPP */ +void InitWork(); +void ReInitWork(); +int SetWork( int, int, int , int, int, RATSNEST_ITEM *, int ); +void GetWork( int *, int *, int *, int *, int *, RATSNEST_ITEM ** ); +void SortWork(); /* order the work items; shortest first */ + +/* routing_matrix.cpp */ +int Build_Work( BOARD * Pcb ); +void PlaceCells( BOARD * Pcb, int net_code, int flag = 0 ); + + +#endif // AUTOROUT_H diff --git a/pcbnew/autorouter/cell.h b/pcbnew/autorouter/cell.h new file mode 100644 index 0000000..63b76ae --- /dev/null +++ b/pcbnew/autorouter/cell.h @@ -0,0 +1,116 @@ +/** + * @file cell.h + */ + +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors. + * + * First copyright (C) Randy Nevin, 1989 (see PCBCA package) + * + * 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 + */ + + +#ifndef _CELL_H_ +#define _CELL_H_ + + +/* Bits characterizing cell */ +#define HOLE 0x01 /* a conducting hole or obstacle */ +#define CELL_is_MODULE 0x02 /* auto placement occupied by a module */ +#define CELL_is_EDGE 0x20 /* Area and auto-placement: limiting cell contour (Board, Zone) */ +#define CELL_is_FRIEND 0x40 /* Area and auto-placement: cell part of the net */ +#define CELL_is_ZONE 0x80 /* Area and auto-placement: cell available */ + +/* Bit masks for presence of obstacles to autorouting */ +#define OCCUPE 1 /* Autorouting: obstacle tracks and vias. */ +#define VIA_IMPOSSIBLE 2 /* Autorouting: obstacle for vias. */ +#define CURRENT_PAD 4 + + +/* traces radiating outward from a hole to a side or corner */ +#define HOLE_NORTH 0x00000002L /* upward */ +#define HOLE_NORTHEAST 0x00000004L /* upward and right */ +#define HOLE_EAST 0x00000008L /* to the right */ +#define HOLE_SOUTHEAST 0x00000010L /* downward and right */ +#define HOLE_SOUTH 0x00000020L /* downward */ +#define HOLE_SOUTHWEST 0x00000040L /* downward and left */ +#define HOLE_WEST 0x00000080L /* to the left */ +#define HOLE_NORTHWEST 0x00000100L /* upward and left */ + +/* straight lines through the center */ +#define LINE_HORIZONTAL 0x00000002L /* left-to-right line */ +#define LINE_VERTICAL 0x00000004L /* top-to-bottom line */ + +/* lines cutting across a corner, connecting adjacent sides */ +#define CORNER_NORTHEAST 0x00000008L /* upper right corner */ +#define CORNER_SOUTHEAST 0x00000010L /* lower right corner */ +#define CORNER_SOUTHWEST 0x00000020L /* lower left corner */ +#define CORNER_NORTHWEST 0x00000040L /* upper left corner */ + +/* diagonal lines through the center */ +#define DIAG_NEtoSW 0x00000080L /* northeast to southwest */ +#define DIAG_SEtoNW 0x00000100L /* southeast to northwest */ + +/* 135 degree angle side-to-far-corner lines */ +#define BENT_NtoSE 0x00000200L /* north to southeast */ +#define BENT_NtoSW 0x00000400L /* north to southwest */ +#define BENT_EtoSW 0x00000800L /* east to southwest */ +#define BENT_EtoNW 0x00001000L /* east to northwest */ +#define BENT_StoNW 0x00002000L /* south to northwest */ +#define BENT_StoNE 0x00004000L /* south to northeast */ +#define BENT_WtoNE 0x00008000L /* west to northeast */ +#define BENT_WtoSE 0x00010000L /* west to southeast */ + +/* 90 degree corner-to-adjacent-corner lines */ +#define ANGLE_NEtoSE 0x00020000L /* northeast to southeast */ +#define ANGLE_SEtoSW 0x00040000L /* southeast to southwest */ +#define ANGLE_SWtoNW 0x00080000L /* southwest to northwest */ +#define ANGLE_NWtoNE 0x00100000L /* northwest to northeast */ + +/* 45 degree angle side-to-near-corner lines */ +#define SHARP_NtoNE 0x00200000L /* north to northeast */ +#define SHARP_EtoNE 0x00400000L /* east to northeast */ +#define SHARP_EtoSE 0x00800000L /* east to southeast */ +#define SHARP_StoSE 0x01000000L /* south to southeast */ +#define SHARP_StoSW 0x02000000L /* south to southwest */ +#define SHARP_WtoSW 0x04000000L /* west to southwest */ +#define SHARP_WtoNW 0x08000000L /* west to northwest */ +#define SHARP_NtoNW 0x10000000L /* north to northwest */ + +/* directions the cell can be reached from (point to previous cell) */ +#define FROM_NOWHERE 0 +#define FROM_NORTH 1 +#define FROM_NORTHEAST 2 +#define FROM_EAST 3 +#define FROM_SOUTHEAST 4 +#define FROM_SOUTH 5 +#define FROM_SOUTHWEST 6 +#define FROM_WEST 7 +#define FROM_NORTHWEST 8 +#define FROM_OTHERSIDE 9 + + +#endif // _CELL_H_ + diff --git a/pcbnew/autorouter/dist.cpp b/pcbnew/autorouter/dist.cpp new file mode 100644 index 0000000..5841073 --- /dev/null +++ b/pcbnew/autorouter/dist.cpp @@ -0,0 +1,171 @@ +/** + * @file dist.cpp + * @brief Routines to calculate PCB editor auto routing distances. + */ + +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 1992-2012 KiCad Developers, see AUTHORS.txt for contributors. + * + * First copyright (C) Randy Nevin, 1989 (see PCBCA package) + * + * 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 <autorout.h> +#include <cell.h> + + +/* The tables of distances and keep out areas are established on the basis of a + * 50 units grid size (the pitch between the cells is 50 units). + * The actual distance could be computed by a scaling factor, but this is + * not needed, we can use only reduced values + */ + + /* calculate approximate distance (manhattan distance) + */ +int MATRIX_ROUTING_HEAD::GetApxDist( int r1, int c1, int r2, int c2 ) +{ + int d1, d2; /* row and column deltas */ + + if( ( d1 = r1 - r2 ) < 0 ) /* get absolute row delta */ + d1 = -d1; + + if( ( d2 = c1 - c2 ) < 0 ) /* get absolute column delta */ + d2 = -d2; + + return ( d1+d2 ) * 50; +} + + +/* distance to go thru a cell (en mils) */ +static const int dist[10][10] = +{ /* OT=Otherside, OR=Origin (source) cell */ +/*..........N, NE, E, SE, S, SW, W, NW, OT, OR */ +/* N */ { 50, 60, 35, 60, 99, 60, 35, 60, 12, 12 }, +/* NE */ { 60, 71, 60, 71, 60, 99, 60, 71, 23, 23 }, +/* E */ { 35, 60, 50, 60, 35, 60, 99, 60, 12, 12 }, +/* SE */ { 60, 71, 60, 71, 60, 71, 60, 99, 23, 23 }, +/* S */ { 99, 60, 35, 60, 50, 60, 35, 60, 12, 12 }, +/* SW */ { 60, 99, 60, 71, 60, 71, 60, 71, 23, 23 }, +/* W */ { 35, 60, 99, 60, 35, 60, 50, 60, 12, 12 }, +/* NW */ { 60, 71, 60, 99, 60, 71, 60, 71, 23, 23 }, + +/* OT */ { 12, 23, 12, 23, 12, 23, 12, 23, 99, 99 }, +/* OR */ { 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 } +}; + +/* penalty for extraneous holes and corners, scaled by sharpness of turn */ +static const int penalty[10][10] = +{ /* OT=Otherside, OR=Origin (source) cell */ +/*......... N, NE, E, SE, S, SW, W, NW, OT, OR */ +/* N */ { 0, 5, 10, 15, 20, 15, 10, 5, 50, 0 }, +/* NE */ { 5, 0, 5, 10, 15, 20, 15, 10, 50, 0 }, +/* E */ { 10, 5, 0, 5, 10, 15, 20, 15, 50, 0 }, +/* SE */ { 15, 10, 5, 0, 5, 10, 15, 20, 50, 0 }, +/* S */ { 20, 15, 10, 5, 0, 5, 10, 15, 50, 0 }, +/* SW */ { 15, 20, 15, 10, 5, 0, 5, 10, 50, 0 }, +/* W */ { 10, 15, 20, 15, 10, 5, 0, 5, 50, 0 }, +/* NW */ { 5, 10, 15, 20, 15, 10, 5, 0, 50, 0 }, + +/* OT */ { 50, 50, 50, 50, 50, 50, 50, 50, 100, 0 }, +/* OR */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } +}; + +/* penalty pour directions preferencielles */ +#define PN 20 +static const int dir_penalty_TOP[10][10] = +{ +/* OT=Otherside, OR=Origin (source) cell */ +/*......... N, NE, E, SE, S, SW, W, NW, OT, OR */ +/* N */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, +/* NE */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, +/* E */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, +/* SE */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, +/* S */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, +/* SW */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, +/* W */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, +/* NW */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, + +/* OT */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }, +/* OR */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 } +}; + +static int dir_penalty_BOTTOM[10][10] = +{ +/* OT=Otherside, OR=Origin (source) cell */ +/*......... N, NE, E, SE, S, SW, W, NW, OT, OR */ +/* N */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, +/* NE */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, +/* E */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, +/* SE */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, +/* S */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, +/* SW */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, +/* W */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, +/* NW */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, + +/* OT */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }, +/* OR */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 } +}; + +/* +** x is the direction to enter the cell of interest. +** y is the direction to exit the cell of interest. +** z is the direction to really exit the cell, if y=FROM_OTHERSIDE. +** +** return the distance of the trace through the cell of interest. +** the calculation is driven by the tables above. +*/ + + +/* calculate distance (with penalty) of a trace through a cell +*/ +int MATRIX_ROUTING_HEAD::CalcDist(int x,int y,int z ,int side ) +{ + int adjust, ldist; + + adjust = 0; /* set if hole is encountered */ + + if( x == EMPTY ) + x = 10; + + if( y == EMPTY ) + { + y = 10; + } + else if( y == FROM_OTHERSIDE ) + { + if( z == EMPTY ) + z = 10; + + adjust = penalty[x-1][z-1]; + } + + ldist = dist[x-1][y-1] + penalty[x-1][y-1] + adjust; + + if( m_RouteCount > 1 ) + { + if( side == BOTTOM ) + ldist += dir_penalty_TOP[x-1][y-1]; + + if( side == TOP ) + ldist += dir_penalty_BOTTOM[x-1][y-1]; + } + + return ldist * 10; +} diff --git a/pcbnew/autorouter/graphpcb.cpp b/pcbnew/autorouter/graphpcb.cpp new file mode 100644 index 0000000..840bfcb --- /dev/null +++ b/pcbnew/autorouter/graphpcb.cpp @@ -0,0 +1,843 @@ +/** + * @file graphpcb.cpp + * @brief PCB editor autorouting and "graphics" routines. + */ + +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2012 KiCad Developers, see change_log.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 <fctsys.h> +#include <common.h> +#include <macros.h> +#include <trigo.h> +#include <math_for_graphics.h> +#include <class_board.h> +#include <class_track.h> +#include <class_drawsegment.h> + +#include <pcbnew.h> +#include <autorout.h> +#include <cell.h> + +void TracePcbLine( int x0, int y0, int x1, int y1, LAYER_NUM layer, int color ); + +void TraceArc( int ux0, int uy0, + int ux1, int uy1, + double ArcAngle, + int lg, LAYER_NUM layer, int color, + int op_logic ); + + +static void DrawSegmentQcq( int ux0, int uy0, + int ux1, int uy1, + int lg, LAYER_NUM layer, int color, + int op_logic ); + +static void TraceFilledCircle( int cx, int cy, int radius, + LSET aLayerMask, + int color, + int op_logic ); + +static void TraceCircle( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer, + int color, int op_logic ); + +// Macro call to update cell. +#define OP_CELL( layer, dy, dx ) \ + { \ + if( layer == UNDEFINED_LAYER ) \ + { \ + RoutingMatrix.WriteCell( dy, dx, BOTTOM, color ); \ + if( RoutingMatrix.m_RoutingLayersCount > 1 ) \ + RoutingMatrix.WriteCell( dy, dx, TOP, color ); \ + } \ + else \ + { \ + if( layer == g_Route_Layer_BOTTOM ) \ + RoutingMatrix.WriteCell( dy, dx, BOTTOM, color ); \ + if( RoutingMatrix.m_RoutingLayersCount > 1 ) \ + if( layer == g_Route_Layer_TOP ) \ + RoutingMatrix.WriteCell( dy, dx, TOP, color ); \ + } \ + } + +void PlacePad( D_PAD* aPad, int color, int marge, int op_logic ) +{ + int dx, dy; + wxPoint shape_pos = aPad->ShapePos(); + + dx = aPad->GetSize().x / 2; + dx += marge; + + if( aPad->GetShape() == PAD_SHAPE_CIRCLE ) + { + TraceFilledCircle( shape_pos.x, shape_pos.y, dx, + aPad->GetLayerSet(), color, op_logic ); + return; + } + + dy = aPad->GetSize().y / 2; + dy += marge; + + if( aPad->GetShape() == PAD_SHAPE_TRAPEZOID ) + { + dx += abs( aPad->GetDelta().y ) / 2; + dy += abs( aPad->GetDelta().x ) / 2; + } + + // The pad is a rectangle ( horizontal or vertical ) + if( int( aPad->GetOrientation() ) % 900 == 0 ) + { + // Orientation turned 90 deg. + if( aPad->GetOrientation() == 900 || aPad->GetOrientation() == 2700 ) + { + std::swap( dx, dy ); + } + + TraceFilledRectangle( shape_pos.x - dx, shape_pos.y - dy, + shape_pos.x + dx, shape_pos.y + dy, + aPad->GetLayerSet(), color, op_logic ); + } + else + { + TraceFilledRectangle( shape_pos.x - dx, shape_pos.y - dy, + shape_pos.x + dx, shape_pos.y + dy, + aPad->GetOrientation(), + aPad->GetLayerSet(), color, op_logic ); + } +} + + +/* Set to color the cells included in the circle + * Parameters: + * center: cx, cy. + * radius: a value add to the radius or half the score pad + * aLayerMask: layer occupied + * color: mask write in cells + * op_logic: type of writing in the cell (WRITE, OR) + */ +void TraceFilledCircle( int cx, int cy, int radius, + LSET aLayerMask, int color, int op_logic ) +{ + int row, col; + int ux0, uy0, ux1, uy1; + int row_max, col_max, row_min, col_min; + int trace = 0; + double fdistmin, fdistx, fdisty; + int tstwrite = 0; + int distmin; + + if( aLayerMask[g_Route_Layer_BOTTOM] ) + trace = 1; // Trace on BOTTOM + + if( aLayerMask[g_Route_Layer_TOP] ) + if( RoutingMatrix.m_RoutingLayersCount > 1 ) + trace |= 2; // Trace on TOP + + if( trace == 0 ) + return; + + RoutingMatrix.SetCellOperation( op_logic ); + + cx -= RoutingMatrix.GetBrdCoordOrigin().x; + cy -= RoutingMatrix.GetBrdCoordOrigin().y; + + distmin = radius; + + // Calculate the bounding rectangle of the circle. + ux0 = cx - radius; + uy0 = cy - radius; + ux1 = cx + radius; + uy1 = cy + radius; + + // Calculate limit coordinates of cells belonging to the rectangle. + row_max = uy1 / RoutingMatrix.m_GridRouting; + col_max = ux1 / RoutingMatrix.m_GridRouting; + row_min = uy0 / RoutingMatrix.m_GridRouting; // if (uy0 > row_min*Board.m_GridRouting) row_min++; + col_min = ux0 / RoutingMatrix.m_GridRouting; // if (ux0 > col_min*Board.m_GridRouting) col_min++; + + if( row_min < 0 ) + row_min = 0; + + if( row_max >= (RoutingMatrix.m_Nrows - 1) ) + row_max = RoutingMatrix.m_Nrows - 1; + + if( col_min < 0 ) + col_min = 0; + + if( col_max >= (RoutingMatrix.m_Ncols - 1) ) + col_max = RoutingMatrix.m_Ncols - 1; + + // Calculate coordinate limits of cell belonging to the rectangle. + if( row_min > row_max ) + row_max = row_min; + + if( col_min > col_max ) + col_max = col_min; + + fdistmin = (double) distmin * distmin; + + for( row = row_min; row <= row_max; row++ ) + { + fdisty = (double) ( cy - ( row * RoutingMatrix.m_GridRouting ) ); + fdisty *= fdisty; + + for( col = col_min; col <= col_max; col++ ) + { + fdistx = (double) ( cx - ( col * RoutingMatrix.m_GridRouting ) ); + fdistx *= fdistx; + + if( fdistmin <= ( fdistx + fdisty ) ) + continue; + + if( trace & 1 ) + RoutingMatrix.WriteCell( row, col, BOTTOM, color ); + + if( trace & 2 ) + RoutingMatrix.WriteCell( row, col, TOP, color ); + + tstwrite = 1; + } + } + + if( tstwrite ) + return; + + /* If no cell has been written, it affects the 4 neighboring diagonal + * (Adverse event: pad off grid in the center of the 4 neighboring + * diagonal) */ + distmin = RoutingMatrix.m_GridRouting / 2 + 1; + fdistmin = ( (double) distmin * distmin ) * 2; // Distance to center point diagonally + + for( row = row_min; row <= row_max; row++ ) + { + fdisty = (double) ( cy - ( row * RoutingMatrix.m_GridRouting ) ); + fdisty *= fdisty; + + for( col = col_min; col <= col_max; col++ ) + { + fdistx = (double) ( cx - ( col * RoutingMatrix.m_GridRouting ) ); + fdistx *= fdistx; + + if( fdistmin <= ( fdistx + fdisty ) ) + continue; + + if( trace & 1 ) + RoutingMatrix.WriteCell( row, col, BOTTOM, color ); + + if( trace & 2 ) + RoutingMatrix.WriteCell( row, col, TOP, color ); + } + } +} + +void TraceSegmentPcb( DRAWSEGMENT* pt_segm, int color, int marge, int op_logic ) +{ + int half_width = ( pt_segm->GetWidth() / 2 ) + marge; + + // Calculate the bounding rectangle of the segment (if H, V or Via) + int ux0 = pt_segm->GetStart().x - RoutingMatrix.GetBrdCoordOrigin().x; + int uy0 = pt_segm->GetStart().y - RoutingMatrix.GetBrdCoordOrigin().y; + int ux1 = pt_segm->GetEnd().x - RoutingMatrix.GetBrdCoordOrigin().x; + int uy1 = pt_segm->GetEnd().y - RoutingMatrix.GetBrdCoordOrigin().y; + + LAYER_NUM layer = pt_segm->GetLayer(); + + if( color == VIA_IMPOSSIBLE ) + layer = UNDEFINED_LAYER; + + switch( pt_segm->GetShape() ) + { + // The segment is here a straight line or a circle or an arc.: + case S_CIRCLE: + TraceCircle( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic ); + break; + + case S_ARC: + TraceArc( ux0, uy0, ux1, uy1, pt_segm->GetAngle(), half_width, layer, color, op_logic ); + break; + + // The segment is here a line segment. + default: + DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic ); + break; + } +} + +void TraceSegmentPcb( TRACK* aTrack, int color, int marge, int op_logic ) +{ + int half_width = ( aTrack->GetWidth() / 2 ) + marge; + + // Test if VIA (filled circle need to be drawn) + if( aTrack->Type() == PCB_VIA_T ) + { + LSET layer_mask; + + if( aTrack->IsOnLayer( g_Route_Layer_BOTTOM ) ) + layer_mask.set( g_Route_Layer_BOTTOM ); + + if( aTrack->IsOnLayer( g_Route_Layer_TOP ) ) + { + if( !layer_mask.any() ) + layer_mask = LSET( g_Route_Layer_TOP ); + else + layer_mask.set(); + } + + if( color == VIA_IMPOSSIBLE ) + layer_mask.set(); + + if( layer_mask.any() ) + TraceFilledCircle( aTrack->GetStart().x, aTrack->GetStart().y, + half_width, layer_mask, color, op_logic ); + } + else + { + // Calculate the bounding rectangle of the segment + int ux0 = aTrack->GetStart().x - RoutingMatrix.GetBrdCoordOrigin().x; + int uy0 = aTrack->GetStart().y - RoutingMatrix.GetBrdCoordOrigin().y; + int ux1 = aTrack->GetEnd().x - RoutingMatrix.GetBrdCoordOrigin().x; + int uy1 = aTrack->GetEnd().y - RoutingMatrix.GetBrdCoordOrigin().y; + + // Ordinary track + LAYER_ID layer = aTrack->GetLayer(); + + if( color == VIA_IMPOSSIBLE ) + layer = UNDEFINED_LAYER; + + DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic ); + } +} + + +/* Draws a line, if layer = -1 on all layers + */ +void TracePcbLine( int x0, int y0, int x1, int y1, LAYER_NUM layer, int color, int op_logic ) +{ + int dx, dy, lim; + int cumul, inc, il, delta; + + RoutingMatrix.SetCellOperation( op_logic ); + + if( x0 == x1 ) // Vertical. + { + if( y1 < y0 ) + std::swap( y0, y1 ); + + dy = y0 / RoutingMatrix.m_GridRouting; + lim = y1 / RoutingMatrix.m_GridRouting; + dx = x0 / RoutingMatrix.m_GridRouting; + + // Clipping limits of board. + if( ( dx < 0 ) || ( dx >= RoutingMatrix.m_Ncols ) ) + return; + + if( dy < 0 ) + dy = 0; + + if( lim >= RoutingMatrix.m_Nrows ) + lim = RoutingMatrix.m_Nrows - 1; + + for( ; dy <= lim; dy++ ) + { + OP_CELL( layer, dy, dx ); + } + + return; + } + + if( y0 == y1 ) // Horizontal + { + if( x1 < x0 ) + std::swap( x0, x1 ); + + dx = x0 / RoutingMatrix.m_GridRouting; + lim = x1 / RoutingMatrix.m_GridRouting; + dy = y0 / RoutingMatrix.m_GridRouting; + + // Clipping limits of board. + if( ( dy < 0 ) || ( dy >= RoutingMatrix.m_Nrows ) ) + return; + + if( dx < 0 ) + dx = 0; + + if( lim >= RoutingMatrix.m_Ncols ) + lim = RoutingMatrix.m_Ncols - 1; + + for( ; dx <= lim; dx++ ) + { + OP_CELL( layer, dy, dx ); + } + + return; + } + + // Here is some perspective: using the algorithm LUCAS. + if( abs( x1 - x0 ) >= abs( y1 - y0 ) ) // segment slightly inclined/ + { + if( x1 < x0 ) + { + std::swap( x1, x0 ); + std::swap( y1, y0 ); + } + + dx = x0 / RoutingMatrix.m_GridRouting; + lim = x1 / RoutingMatrix.m_GridRouting; + dy = y0 / RoutingMatrix.m_GridRouting; + inc = 1; + + if( y1 < y0 ) + inc = -1; + + il = lim - dx; cumul = il / 2; + delta = abs( y1 - y0 ) / RoutingMatrix.m_GridRouting; + + for( ; dx <= lim; ) + { + if( ( dx >= 0 ) && ( dy >= 0 ) && + ( dx < RoutingMatrix.m_Ncols ) && + ( dy < RoutingMatrix.m_Nrows ) ) + { + OP_CELL( layer, dy, dx ); + } + + dx++; + cumul += delta; + + if( cumul > il ) + { + cumul -= il; + dy += inc; + } + } + } + else + { + if( y1 < y0 ) + { + std::swap( x1, x0 ); + std::swap( y1, y0 ); + } + + dy = y0 / RoutingMatrix.m_GridRouting; + lim = y1 / RoutingMatrix.m_GridRouting; + dx = x0 / RoutingMatrix.m_GridRouting; + inc = 1; + + if( x1 < x0 ) + inc = -1; + + il = lim - dy; + cumul = il / 2; + delta = abs( x1 - x0 ) / RoutingMatrix.m_GridRouting; + + for( ; dy <= lim; ) + { + if( ( dx >= 0 ) && ( dy >= 0 ) && ( dx < RoutingMatrix.m_Ncols ) && ( dy < RoutingMatrix.m_Nrows ) ) + { + OP_CELL( layer, dy, dx ); + } + + dy++; + cumul += delta; + + if( cumul > il ) + { + cumul -= il; + dx += inc; + } + } + } +} + + +void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1, + LSET aLayerMask, int color, int op_logic ) +{ + int row, col; + int row_min, row_max, col_min, col_max; + int trace = 0; + + if( aLayerMask[g_Route_Layer_BOTTOM] ) + trace = 1; // Trace on BOTTOM + + if( aLayerMask[g_Route_Layer_TOP] && RoutingMatrix.m_RoutingLayersCount > 1 ) + trace |= 2; // Trace on TOP + + if( trace == 0 ) + return; + + RoutingMatrix.SetCellOperation( op_logic ); + + ux0 -= RoutingMatrix.GetBrdCoordOrigin().x; + uy0 -= RoutingMatrix.GetBrdCoordOrigin().y; + ux1 -= RoutingMatrix.GetBrdCoordOrigin().x; + uy1 -= RoutingMatrix.GetBrdCoordOrigin().y; + + // Calculating limits coord cells belonging to the rectangle. + row_max = uy1 / RoutingMatrix.m_GridRouting; + col_max = ux1 / RoutingMatrix.m_GridRouting; + row_min = uy0 / RoutingMatrix.m_GridRouting; + + if( uy0 > row_min * RoutingMatrix.m_GridRouting ) + row_min++; + + col_min = ux0 / RoutingMatrix.m_GridRouting; + + if( ux0 > col_min * RoutingMatrix.m_GridRouting ) + col_min++; + + if( row_min < 0 ) + row_min = 0; + + if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) ) + row_max = RoutingMatrix.m_Nrows - 1; + + if( col_min < 0 ) + col_min = 0; + + if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) ) + col_max = RoutingMatrix.m_Ncols - 1; + + for( row = row_min; row <= row_max; row++ ) + { + for( col = col_min; col <= col_max; col++ ) + { + if( trace & 1 ) + RoutingMatrix.WriteCell( row, col, BOTTOM, color ); + + if( trace & 2 ) + RoutingMatrix.WriteCell( row, col, TOP, color ); + } + } +} + + +void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1, + double angle, LSET aLayerMask, int color, int op_logic ) +{ + int row, col; + int cx, cy; // Center of rectangle + int radius; // Radius of the circle + int row_min, row_max, col_min, col_max; + int rotrow, rotcol; + int trace = 0; + + if( aLayerMask[g_Route_Layer_BOTTOM] ) + trace = 1; // Trace on BOTTOM + + if( aLayerMask[g_Route_Layer_TOP] ) + { + if( RoutingMatrix.m_RoutingLayersCount > 1 ) + trace |= 2; // Trace on TOP + } + + if( trace == 0 ) + return; + + RoutingMatrix.SetCellOperation( op_logic ); + + ux0 -= RoutingMatrix.GetBrdCoordOrigin().x; + uy0 -= RoutingMatrix.GetBrdCoordOrigin().y; + ux1 -= RoutingMatrix.GetBrdCoordOrigin().x; + uy1 -= RoutingMatrix.GetBrdCoordOrigin().y; + + cx = (ux0 + ux1) / 2; + cy = (uy0 + uy1) / 2; + radius = KiROUND( Distance( ux0, uy0, cx, cy ) ); + + // Calculating coordinate limits belonging to the rectangle. + row_max = ( cy + radius ) / RoutingMatrix.m_GridRouting; + col_max = ( cx + radius ) / RoutingMatrix.m_GridRouting; + row_min = ( cy - radius ) / RoutingMatrix.m_GridRouting; + + if( uy0 > row_min * RoutingMatrix.m_GridRouting ) + row_min++; + + col_min = ( cx - radius ) / RoutingMatrix.m_GridRouting; + + if( ux0 > col_min * RoutingMatrix.m_GridRouting ) + col_min++; + + if( row_min < 0 ) + row_min = 0; + + if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) ) + row_max = RoutingMatrix.m_Nrows - 1; + + if( col_min < 0 ) + col_min = 0; + + if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) ) + col_max = RoutingMatrix.m_Ncols - 1; + + for( row = row_min; row <= row_max; row++ ) + { + for( col = col_min; col <= col_max; col++ ) + { + rotrow = row * RoutingMatrix.m_GridRouting; + rotcol = col * RoutingMatrix.m_GridRouting; + RotatePoint( &rotcol, &rotrow, cx, cy, -angle ); + + if( rotrow <= uy0 ) + continue; + + if( rotrow >= uy1 ) + continue; + + if( rotcol <= ux0 ) + continue; + + if( rotcol >= ux1 ) + continue; + + if( trace & 1 ) + RoutingMatrix.WriteCell( row, col, BOTTOM, color ); + + if( trace & 2 ) + RoutingMatrix.WriteCell( row, col, TOP, color ); + } + } +} + + +/* Fills all cells inside a segment + * half-width = lg, org = ux0,uy0 end = ux1,uy1 + * coordinates are in PCB units + */ +void DrawSegmentQcq( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer, + int color, int op_logic ) +{ + int row, col; + int inc; + int row_max, col_max, row_min, col_min; + int demi_pas; + + int cx, cy, dx, dy; + + RoutingMatrix.SetCellOperation( op_logic ); + + // Make coordinate ux1 tj > ux0 to simplify calculations + if( ux1 < ux0 ) + { + std::swap( ux1, ux0 ); + std::swap( uy1, uy0 ); + } + + // Calculating the incrementing the Y axis + inc = 1; + + if( uy1 < uy0 ) + inc = -1; + + demi_pas = RoutingMatrix.m_GridRouting / 2; + + col_min = ( ux0 - lg ) / RoutingMatrix.m_GridRouting; + + if( col_min < 0 ) + col_min = 0; + + col_max = ( ux1 + lg + demi_pas ) / RoutingMatrix.m_GridRouting; + + if( col_max > ( RoutingMatrix.m_Ncols - 1 ) ) + col_max = RoutingMatrix.m_Ncols - 1; + + if( inc > 0 ) + { + row_min = ( uy0 - lg ) / RoutingMatrix.m_GridRouting; + row_max = ( uy1 + lg + demi_pas ) / RoutingMatrix.m_GridRouting; + } + else + { + row_min = ( uy1 - lg ) / RoutingMatrix.m_GridRouting; + row_max = ( uy0 + lg + demi_pas ) / RoutingMatrix.m_GridRouting; + } + + if( row_min < 0 ) + row_min = 0; + + if( row_min > ( RoutingMatrix.m_Nrows - 1 ) ) + row_min = RoutingMatrix.m_Nrows - 1; + + if( row_max < 0 ) + row_max = 0; + + if( row_max > ( RoutingMatrix.m_Nrows - 1 ) ) + row_max = RoutingMatrix.m_Nrows - 1; + + dx = ux1 - ux0; + dy = uy1 - uy0; + + double angle; + if( dx ) + { + angle = ArcTangente( dy, dx ); + } + else + { + angle = 900; + + if( dy < 0 ) + angle = -900; + } + + RotatePoint( &dx, &dy, angle ); // dx = length, dy = 0 + + for( col = col_min; col <= col_max; col++ ) + { + int cxr; + cxr = ( col * RoutingMatrix.m_GridRouting ) - ux0; + + for( row = row_min; row <= row_max; row++ ) + { + cy = (row * RoutingMatrix.m_GridRouting) - uy0; + cx = cxr; + RotatePoint( &cx, &cy, angle ); + + if( abs( cy ) > lg ) + continue; // The point is too far on the Y axis. + + /* This point a test is close to the segment: the position + * along the X axis must be tested. + */ + if( ( cx >= 0 ) && ( cx <= dx ) ) + { + OP_CELL( layer, row, col ); + continue; + } + + // Examination of extremities are rounded. + if( ( cx < 0 ) && ( cx >= -lg ) ) + { + if( ( ( cx * cx ) + ( cy * cy ) ) <= ( lg * lg ) ) + OP_CELL( layer, row, col ); + + continue; + } + + if( ( cx > dx ) && ( cx <= ( dx + lg ) ) ) + { + if( ( ( ( cx - dx ) * ( cx - dx ) ) + ( cy * cy ) ) <= ( lg * lg ) ) + OP_CELL( layer, row, col ); + + continue; + } + } + } +} + + +/* Fills all cells of the routing matrix contained in the circle + * half-width = lg, center = ux0, uy0, ux1,uy1 is a point on the circle. + * coord are in PCB units. + */ +void TraceCircle( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer, + int color, int op_logic ) +{ + int radius, nb_segm; + int x0, y0, // Starting point of the current segment trace. + x1, y1; // End point. + int ii; + int angle; + + radius = KiROUND( Distance( ux0, uy0, ux1, uy1 ) ); + + x0 = x1 = radius; + y0 = y1 = 0; + + if( lg < 1 ) + lg = 1; + + nb_segm = ( 2 * radius ) / lg; + + if( nb_segm < 5 ) + nb_segm = 5; + + if( nb_segm > 100 ) + nb_segm = 100; + + for( ii = 1; ii < nb_segm; ii++ ) + { + angle = (3600 * ii) / nb_segm; + x1 = KiROUND( cosdecideg( radius, angle ) ); + y1 = KiROUND( sindecideg( radius, angle ) ); + DrawSegmentQcq( x0 + ux0, y0 + uy0, x1 + ux0, y1 + uy0, lg, layer, color, op_logic ); + x0 = x1; + y0 = y1; + } + + DrawSegmentQcq( x1 + ux0, y1 + uy0, ux0 + radius, uy0, lg, layer, color, op_logic ); +} + + +/* Fills all routing matrix cells contained in the arc + * angle = ArcAngle, half-width lg + * center = ux0,uy0, starting at ux1, uy1. Coordinates are in + * PCB units. + */ +void TraceArc( int ux0, int uy0, int ux1, int uy1, double ArcAngle, int lg, + LAYER_NUM layer, int color, int op_logic ) +{ + int radius, nb_segm; + int x0, y0, // Starting point of the current segment trace + x1, y1; // End point + int ii; + double angle, StAngle; + + + radius = KiROUND( Distance( ux0, uy0, ux1, uy1 ) ); + + x0 = ux1 - ux0; + y0 = uy1 - uy0; + StAngle = ArcTangente( uy1 - uy0, ux1 - ux0 ); + + if( lg < 1 ) + lg = 1; + + nb_segm = ( 2 * radius ) / lg; + nb_segm = ( nb_segm * std::abs( ArcAngle ) ) / 3600; + + if( nb_segm < 5 ) + nb_segm = 5; + + if( nb_segm > 100 ) + nb_segm = 100; + + for( ii = 1; ii <= nb_segm; ii++ ) + { + angle = ( ArcAngle * ii ) / nb_segm; + angle += StAngle; + + NORMALIZE_ANGLE_POS( angle ); + + x1 = KiROUND( cosdecideg( radius, angle ) ); + y1 = KiROUND( cosdecideg( radius, angle ) ); + DrawSegmentQcq( x0 + ux0, y0 + uy0, x1 + ux0, y1 + uy0, lg, layer, color, op_logic ); + x0 = x1; + y0 = y1; + } +} diff --git a/pcbnew/autorouter/move_and_route_event_functions.cpp b/pcbnew/autorouter/move_and_route_event_functions.cpp new file mode 100644 index 0000000..5e9f319 --- /dev/null +++ b/pcbnew/autorouter/move_and_route_event_functions.cpp @@ -0,0 +1,200 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2012 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 move_and_route_event_functions.cpp + * @brief Routines for automatic displacement and rotation of modules. + */ + +#include <algorithm> + +#include <fctsys.h> +#include <class_drawpanel.h> +#include <confirm.h> +#include <kicad_string.h> +#include <pcbnew.h> +#include <wxPcbStruct.h> +#include <kicad_device_context.h> + +#include <autorout.h> +#include <cell.h> +#include <pcbnew_id.h> +#include <class_board.h> +#include <class_module.h> + + +typedef enum { + FIXE_MODULE, + FREE_MODULE, + FIXE_ALL_MODULES, + FREE_ALL_MODULES +} SelectFixeFct; + + + +wxString ModulesMaskSelection = wxT( "*" ); + + +/* Called on events (popup menus) relative to automove and autoplace footprints + */ +void PCB_EDIT_FRAME::OnPlaceOrRouteFootprints( wxCommandEvent& event ) +{ + int id = event.GetId(); + + if( m_mainToolBar == NULL ) + return; + + INSTALL_UNBUFFERED_DC( dc, m_canvas ); + + switch( id ) + { + case ID_POPUP_PCB_AUTOROUTE_SELECT_LAYERS: + return; + + case ID_POPUP_PCB_AUTOPLACE_FIXE_MODULE: + LockModule( (MODULE*) GetScreen()->GetCurItem(), true ); + return; + + case ID_POPUP_PCB_AUTOPLACE_FREE_MODULE: + LockModule( (MODULE*) GetScreen()->GetCurItem(), false ); + return; + + case ID_POPUP_PCB_AUTOPLACE_FREE_ALL_MODULES: + LockModule( NULL, false ); + return; + + case ID_POPUP_PCB_AUTOPLACE_FIXE_ALL_MODULES: + LockModule( NULL, true ); + return; + + case ID_POPUP_CANCEL_CURRENT_COMMAND: + if( m_canvas->IsMouseCaptured() ) + { + m_canvas->CallEndMouseCapture( &dc ); + } + + break; + + default: // Abort a current command (if any) + m_canvas->EndMouseCapture( ID_NO_TOOL_SELECTED, m_canvas->GetDefaultCursor() ); + break; + } + + // Erase ratsnest if needed + if( GetBoard()->IsElementVisible(RATSNEST_VISIBLE) ) + DrawGeneralRatsnest( &dc ); + + GetBoard()->m_Status_Pcb |= DO_NOT_SHOW_GENERAL_RASTNEST; + + switch( id ) + { + case ID_POPUP_PCB_AUTOPLACE_CURRENT_MODULE: + AutoPlaceModule( (MODULE*) GetScreen()->GetCurItem(), PLACE_1_MODULE, &dc ); + break; + + case ID_POPUP_PCB_AUTOPLACE_ALL_MODULES: + AutoPlaceModule( NULL, PLACE_ALL, &dc ); + break; + + case ID_POPUP_PCB_AUTOPLACE_NEW_MODULES: + AutoPlaceModule( NULL, PLACE_OUT_OF_BOARD, &dc ); + break; + + case ID_POPUP_PCB_AUTOPLACE_NEXT_MODULE: + AutoPlaceModule( NULL, PLACE_INCREMENTAL, &dc ); + break; + + case ID_POPUP_PCB_SPREAD_ALL_MODULES: + if( !IsOK( this, + _("Not locked footprints inside the board will be moved. OK?") ) ) + break; + // Fall through + case ID_POPUP_PCB_SPREAD_NEW_MODULES: + if( GetBoard()->m_Modules == NULL ) + { + DisplayError( this, _( "No footprint found!" ) ); + return; + } + + SpreadFootprints( id == ID_POPUP_PCB_SPREAD_NEW_MODULES ); + break; + + case ID_POPUP_PCB_AUTOROUTE_ALL_MODULES: + Autoroute( &dc, ROUTE_ALL ); + break; + + case ID_POPUP_PCB_AUTOROUTE_MODULE: + Autoroute( &dc, ROUTE_MODULE ); + break; + + case ID_POPUP_PCB_AUTOROUTE_PAD: + Autoroute( &dc, ROUTE_PAD ); + break; + + case ID_POPUP_PCB_AUTOROUTE_NET: + Autoroute( &dc, ROUTE_NET ); + break; + + case ID_POPUP_PCB_AUTOROUTE_RESET_UNROUTED: + Reset_Noroutable( &dc ); + break; + + default: + wxMessageBox( wxT( "OnPlaceOrRouteFootprints command error" ) ); + break; + } + + GetBoard()->m_Status_Pcb &= ~DO_NOT_SHOW_GENERAL_RASTNEST; + Compile_Ratsnest( &dc, true ); +} + + +/* Set or reset (true or false) Lock attribute of aModule or all modules if aModule == NULL + */ +void PCB_EDIT_FRAME::LockModule( MODULE* aModule, bool aLocked ) +{ + if( aModule ) + { + aModule->SetLocked( aLocked ); + SetMsgPanel( aModule ); + OnModify(); + } + else + { + aModule = GetBoard()->m_Modules; + + for( ; aModule != NULL; aModule = aModule->Next() ) + { + if( WildCompareString( ModulesMaskSelection, aModule->GetReference() ) ) + { + aModule->SetLocked( aLocked ); + OnModify(); + } + } + } +} + diff --git a/pcbnew/autorouter/queue.cpp b/pcbnew/autorouter/queue.cpp new file mode 100644 index 0000000..0cf1977 --- /dev/null +++ b/pcbnew/autorouter/queue.cpp @@ -0,0 +1,220 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2015 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2015 KiCad Developers, see change_log.txt for contributors. + * + * First copyright (C) Randy Nevin, 1989 (see PCBCA package) + * + * 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 queue.cpp + */ + +#include <fctsys.h> +#include <common.h> + +#include <pcbnew.h> +#include <autorout.h> +#include <cell.h> + + +struct PcbQueue /* search queue structure */ +{ + struct PcbQueue* Next; + int Row; /* current row */ + int Col; /* current column */ + int Side; /* 0=top, 1=bottom */ + int Dist; /* path distance to this cell so far */ + int ApxDist; /* approximate distance to target from here */ +}; + +static long qlen = 0; /* current queue length */ +static struct PcbQueue* Head = NULL; +static struct PcbQueue* Tail = NULL; +static struct PcbQueue* Save = NULL; /* hold empty queue structs */ + + +/* Free the memory used for storing all the queue */ +void FreeQueue() +{ + struct PcbQueue* p; + + InitQueue(); + + while( (p = Save) != NULL ) + { + Save = p->Next; + delete p; + } +} + + +/* initialize the search queue */ +void InitQueue() +{ + struct PcbQueue* p; + + while( (p = Head) != NULL ) + { + Head = p->Next; + p->Next = Save; Save = p; + } + + Tail = NULL; + OpenNodes = ClosNodes = MoveNodes = MaxNodes = qlen = 0; +} + + +/* get search queue item from list */ +void GetQueue( int* r, int* c, int* s, int* d, int* a ) +{ + struct PcbQueue* p; + + if( (p = Head) != NULL ) /* return first item in list */ + { + *r = p->Row; *c = p->Col; + *s = p->Side; + *d = p->Dist; *a = p->ApxDist; + + if( (Head = p->Next) == NULL ) + Tail = NULL; + + /* put node on free list */ + p->Next = Save; Save = p; + ClosNodes++; qlen--; + } + else /* empty list */ + { + *r = *c = *s = *d = *a = ILLEGAL; + } +} + + +/* add a search node to the list + * : + * 1 - OK + * 0 - Failed to allocate memory. + */ +bool SetQueue( int r, int c, int side, int d, int a, int r2, int c2 ) +{ + struct PcbQueue* p, * q, * t; + int i, j; + + j = 0; // gcc warning fix + + if( (p = Save) != NULL ) /* try free list first */ + { + Save = p->Next; + } + else if( ( p = (PcbQueue*) operator new( sizeof( PcbQueue ), std::nothrow ) ) == NULL ) + { + return 0; + } + + p->Row = r; + p->Col = c; + p->Side = side; + i = (p->Dist = d) + (p->ApxDist = a); + p->Next = NULL; + + if( (q = Head) != NULL ) /* insert in proper position in list */ + { + if( q->Dist + q->ApxDist > i ) /* insert at head */ + { + p->Next = q; Head = p; + } + else /* search for proper position */ + { + for( t = q, q = q->Next; q && i > ( j = q->Dist + q->ApxDist ); t = q, q = q->Next ) + ; + + if( q && i == j && q->Row == r2 && q->Col == c2 ) + { + /* insert after q, which is a goal node */ + if( ( p->Next = q->Next ) == NULL ) + Tail = p; + + q->Next = p; + } + else /* insert in front of q */ + { + if( ( p->Next = q ) == NULL ) + Tail = p; + + t->Next = p; + } + } + } + else /* empty search list */ + { + Head = Tail = p; + } + + OpenNodes++; + + if( ++qlen > MaxNodes ) + MaxNodes = qlen; + + return 1; +} + + +/* reposition node in list */ +void ReSetQueue( int r, int c, int s, int d, int a, int r2, int c2 ) +{ + struct PcbQueue* p, * q; + + /* first, see if it is already in the list */ + for( q = NULL, p = Head; p; q = p, p = p->Next ) + { + if( p->Row == r && p->Col == c && p->Side == s ) + { + /* old one to remove */ + if( q ) + { + if( ( q->Next = p->Next ) == NULL ) + Tail = q; + } + else if( ( Head = p->Next ) == NULL ) + { + Tail = NULL; + } + + p->Next = Save; + Save = p; + OpenNodes--; + MoveNodes++; + qlen--; + break; + } + } + + if( !p ) /* not found, it has already been closed once */ + ClosNodes--; /* we will close it again, but just count once */ + + /* if it was there, it's gone now; insert it at the proper position */ + bool res = SetQueue( r, c, s, d, a, r2, c2 ); + (void) res; +} diff --git a/pcbnew/autorouter/rect_placement/RectanglePlacement.txt b/pcbnew/autorouter/rect_placement/RectanglePlacement.txt new file mode 100644 index 0000000..cecbf2e --- /dev/null +++ b/pcbnew/autorouter/rect_placement/RectanglePlacement.txt @@ -0,0 +1,38 @@ +A class that fits subrectangles into a power-of-2 rectangle + +(C) Copyright 2000-2002 by Javier Arevalo +This code is free to use and modify for all purposes + +You have a bunch of rectangular pieces. You need to arrange them in a +rectangular surface so that they don't overlap, keeping the total area of the +rectangle as small as possible. This is fairly common when arranging characters +in a bitmapped font, lightmaps for a 3D engine, and I guess other situations as +well. + +The idea of this algorithm is that, as we add rectangles, we can pre-select +"interesting" places where we can try to add the next rectangles. For optimal +results, the rectangles should be added in order. I initially tried using area +as a sorting criteria, but it didn't work well with very tall or very flat +rectangles. I then tried using the longest dimension as a selector, and it +worked much better. So much for intuition... + +These "interesting" places are just to the right and just below the currently +added rectangle. The first rectangle, obviously, goes at the top left, the next +one would go either to the right or below this one, and so on. It is a weird way +to do it, but it seems to work very nicely. + +The way we search here is fairly brute-force, the fact being that for most off- +line purposes the performance seems more than adequate. I have generated a +japanese font with around 8500 characters and all the time was spent generating +the bitmaps. + +Also, for all we care, we could grow the parent rectangle in a different way +than power of two. It just happens that power of 2 is very convenient for +graphics hardware textures. + +I'd be interested in hearing of other approaches to this problem. Make sure +to post them on http://www.flipcode.com + +See also +http://www.flipcode.com/archives/Rectangle_Placement.shtml +http://kossovsky.net/index.php/2009/07/cshar-rectangle-packing diff --git a/pcbnew/autorouter/rect_placement/rect_placement.cpp b/pcbnew/autorouter/rect_placement/rect_placement.cpp new file mode 100644 index 0000000..f562c2b --- /dev/null +++ b/pcbnew/autorouter/rect_placement/rect_placement.cpp @@ -0,0 +1,259 @@ +// ---------------------------------------------------------------------------------------- +// Name : rect_placement.cpp +// Description : A class that fits subrectangles into a power-of-2 rectangle +// (C) Copyright 2000-2002 by Javier Arevalo +// This code is free to use and modify for all purposes +// ---------------------------------------------------------------------------------------- + +/* + * You have a bunch of rectangular pieces. You need to arrange them in a + * rectangular surface so that they don't overlap, keeping the total area of the + * rectangle as small as possible. This is fairly common when arranging characters + * in a bitmapped font, lightmaps for a 3D engine, and I guess other situations as + * well. + * + * The idea of this algorithm is that, as we add rectangles, we can pre-select + * "interesting" places where we can try to add the next rectangles. For optimal + * results, the rectangles should be added in order. I initially tried using area + * as a sorting criteria, but it didn't work well with very tall or very flat + * rectangles. I then tried using the longest dimension as a selector, and it + * worked much better. So much for intuition... + * + * These "interesting" places are just to the right and just below the currently + * added rectangle. The first rectangle, obviously, goes at the top left, the next + * one would go either to the right or below this one, and so on. It is a weird way + * to do it, but it seems to work very nicely. + * + * The way we search here is fairly brute-force, the fact being that for most off- + * line purposes the performance seems more than adequate. I have generated a + * japanese font with around 8500 characters and all the time was spent generating + * the bitmaps. + * + * Also, for all we care, we could grow the parent rectangle. + * + * I'd be interested in hearing of other approaches to this problem. Make sure + * to post them on http://www.flipcode.com + */ + +#include "rect_placement.h" + +// -------------------------------------------------------------------------------- +// Name : +// Description : +// -------------------------------------------------------------------------------- +void CRectPlacement::Init( int w, int h ) +{ + End(); + m_size = TRect( 0, 0, w, h ); + m_vPositions.push_back( TPos( 0, 0 ) ); + m_area = 0; +} + + +// -------------------------------------------------------------------------------- +// Name : +// Description : +// -------------------------------------------------------------------------------- +void CRectPlacement::End() +{ + m_vPositions.clear(); + m_vRects.clear(); + m_size.w = 0; +} + + +// -------------------------------------------------------------------------------- +// Name : IsFree +// Description : Check if the given rectangle is partially or totally used +// -------------------------------------------------------------------------------- +bool CRectPlacement::IsFree( const TRect& r ) const +{ + if( !m_size.Contains( r ) ) + return false; + + for( CRectArray::const_iterator it = m_vRects.begin(); + it != m_vRects.end(); ++it ) + { + if( it->Intersects( r ) ) + return false; + } + + return true; +} + + +// -------------------------------------------------------------------------------- +// Name : AddPosition +// Description : Add new anchor point +// -------------------------------------------------------------------------------- +void CRectPlacement::AddPosition( const TPos& p ) +{ + // Try to insert anchor as close as possible to the top left corner + // So it will be tried first + bool bFound = false; + CPosArray::iterator it; + + for( it = m_vPositions.begin(); + !bFound && it != m_vPositions.end(); + ++it ) + { + if( p.x + p.y < it->x + it->y ) + bFound = true; + } + + if( bFound ) + m_vPositions.insert( it, p ); + else + m_vPositions.push_back( p ); +} + + +// -------------------------------------------------------------------------------- +// Name : AddRect +// Description : Add the given rect and updates anchor points +// -------------------------------------------------------------------------------- +void CRectPlacement::AddRect( const TRect& r ) +{ + m_vRects.push_back( r ); + m_area += r.w * r.h; + + // Add two new anchor points + AddPosition( TPos( r.x, r.y + r.h ) ); + AddPosition( TPos( r.x + r.w, r.y ) ); +} + + +// -------------------------------------------------------------------------------- +// Name : AddAtEmptySpot +// Description : Add the given rectangle +// -------------------------------------------------------------------------------- +bool CRectPlacement::AddAtEmptySpot( TRect& r ) +{ + // Find a valid spot among available anchors. + bool bFound = false; + CPosArray::iterator it; + + for( it = m_vPositions.begin(); + !bFound && it != m_vPositions.end(); + ++it ) + { + TRect Rect( it->x, it->y, r.w, r.h ); + + if( IsFree( Rect ) ) + { + r = Rect; + bFound = true; + break; // Don't let the loop increase the iterator. + } + } + + if( bFound ) + { + int x, y; + + // Remove the used anchor point + m_vPositions.erase( it ); + + // Sometimes, anchors end up displaced from the optimal position + // due to irregular sizes of the subrects. + // So, try to adjut it up & left as much as possible. + for( x = 1; x <= r.x; x++ ) + { + if( !IsFree( TRect( r.x - x, r.y, r.w, r.h ) ) ) + break; + } + + for( y = 1; y <= r.y; y++ ) + { + if( !IsFree( TRect( r.x, r.y - y, r.w, r.h ) ) ) + break; + } + + if( y > x ) + r.y -= y - 1; + else + r.x -= x - 1; + + AddRect( r ); + } + + return bFound; +} + +#include <stdio.h> +// -------------------------------------------------------------------------------- +// Name : AddAtEmptySpotAutoGrow +// Description : Add a rectangle of the given size, growing our area if needed +// Area grows only until the max given. +// Returns the placement of the rect in the rect's x,y coords +// -------------------------------------------------------------------------------- +bool CRectPlacement::AddAtEmptySpotAutoGrow( TRect* pRect, int maxW, int maxH ) +{ + double growing_factor = 1.2; // Must be > 1.0, and event > 1.1 for fast optimization + + #define GROW(x) ((x * growing_factor) + 1) + + if( pRect->w <= 0 ) + return true; + + int orgW = m_size.w; + int orgH = m_size.h; + + // Try to add it in the existing space + while( !AddAtEmptySpot( *pRect ) ) + { + int pw = m_size.w; + int ph = m_size.h; + + // Sanity check - if area is complete. + if( pw >= maxW && ph >= maxH ) + { + m_size.w = orgW; + m_size.h = orgH; + return false; + } + + // Try growing the smallest dim + if( pw < maxW && ( pw < ph || ( (pw == ph) && (pRect->w >= pRect->h) ) ) ) + m_size.w = GROW( pw ); + else + m_size.h = GROW( ph ); + + if( AddAtEmptySpot( *pRect ) ) + break; + + // Try growing the other dim instead + if( pw != m_size.w ) + { + m_size.w = pw; + + if( ph < maxW ) + m_size.h = GROW( ph ); + } + else + { + m_size.h = ph; + + if( pw < maxW ) + m_size.w = GROW( pw ); + } + + if( pw != m_size.w || ph != m_size.h ) + if( AddAtEmptySpot( *pRect ) ) + break; + + + + // Grow both if possible, and reloop. + m_size.w = pw; + m_size.h = ph; + + if( pw < maxW ) + m_size.w = GROW( pw ); + + if( ph < maxH ) + m_size.h = GROW( ph ); + } + + return true; +} diff --git a/pcbnew/autorouter/rect_placement/rect_placement.h b/pcbnew/autorouter/rect_placement/rect_placement.h new file mode 100644 index 0000000..b89b538 --- /dev/null +++ b/pcbnew/autorouter/rect_placement/rect_placement.h @@ -0,0 +1,104 @@ +// -------------------------------------------------------------------------------- +// Name : rect_placement.h +// Description : A class that allocates subrectangles into power-of-2 rectangles +// (C) Copyright 2000-2002 by Javier Arevalo +// This code is free to use and modify for all purposes +// -------------------------------------------------------------------------------- + +/** + * @file rect_placement.h + */ + +#ifndef _RECT_PLACEMENT_H_ +#define _RECT_PLACEMENT_H_ + +#include <vector> + +// -------------------------------------------------------------------------------- +// -------------------------------------------------------------------------------- + +class CRectPlacement +{ +public: + + // Helper classes + struct TPos + { + int x, y; + + TPos() : x( 0 ), y( 0 ) { } + TPos( int _x, int _y ) : x( _x ), y( _y ) { } + + bool operator ==( const TPos& p ) const { return x == p.x && y == p.y; } + }; + + struct TRect : public TPos + { + int w, h; + + TRect() : w( 0 ), h( 0 ) { } + TRect( int _x, int _y, int _w, int _h ) : TPos( _x, _y ), w( _w > 0 ? _w : 0 ), h( + _h > 0 ? _h : 0 ) { } + + bool Contains( const TPos& p ) const + { + return p.x >= x && p.y >= y && p.x < (x + w) && p.y < (y + h); + } + bool Contains( const TRect& r ) const + { + return r.x >= x && r.y >= y && + (r.x + r.w) <= (x + w) && (r.y + r.h) <= (y + h); + } + bool Intersects( const TRect& r ) const + { + return w > 0 && h > 0 && r.w > 0 && r.h > 0 + && ( (r.x + r.w) > x && r.x < (x + w) && (r.y + r.h) > y && r.y < (y + h) ); + } + + // static bool Greater(const TRect &a, const TRect &b) + // { return a.w*a.h > b.w*b.h; } + // Greater rect area. Not as good as the next heuristic: + // Greater size in at least one dim. + static bool Greater( const TRect& a, const TRect& b ) + { + return (a.w > b.w && a.w > b.h) || (a.h > b.w && a.h > b.h); + } + }; + + // --------------------- + + typedef std::vector<TPos> CPosArray; + typedef std::vector<TRect> CRectArray; + + // --------------------- + + CRectPlacement() { Init(); } + ~CRectPlacement() { End(); } + + void Init( int w = 1, int h = 1 ); + void End(); + + bool IsOk() const { return m_size.w > 0; } + + int GetW() const { return m_size.w; } + int GetH() const { return m_size.h; } + double GetArea() const { return m_area; } + double GetTotalArea() const { return (double)m_size.w * m_size.h; } + + bool AddAtEmptySpotAutoGrow( TRect* pRect, int maxW, int maxH ); + +private: + TRect m_size; + CRectArray m_vRects; + CPosArray m_vPositions; + double m_area; + + // --------------------- + + bool IsFree( const TRect& r ) const; + void AddPosition( const TPos& p ); + void AddRect( const TRect& r ); + bool AddAtEmptySpot( TRect& r ); +}; + +#endif // _RECT_PLACEMENT_H_ diff --git a/pcbnew/autorouter/routing_matrix.cpp b/pcbnew/autorouter/routing_matrix.cpp new file mode 100644 index 0000000..2c97f0d --- /dev/null +++ b/pcbnew/autorouter/routing_matrix.cpp @@ -0,0 +1,550 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2015 KiCad Developers, see change_log.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 routing_matrix.cpp + * @brief Functions to create autorouting maps + */ + +#include <fctsys.h> +#include <common.h> + +#include <pcbnew.h> +#include <cell.h> +#include <autorout.h> + +#include <class_board.h> +#include <class_module.h> +#include <class_track.h> +#include <class_drawsegment.h> +#include <class_edge_mod.h> +#include <class_pcb_text.h> + + +MATRIX_ROUTING_HEAD::MATRIX_ROUTING_HEAD() +{ + m_BoardSide[0] = m_BoardSide[1] = NULL; + m_DistSide[0] = m_DistSide[1] = NULL; + m_DirSide[0] = m_DirSide[1] = NULL; + m_opWriteCell = NULL; + m_InitMatrixDone = false; + m_Nrows = 0; + m_Ncols = 0; + m_MemSize = 0; + m_RoutingLayersCount = 1; + m_GridRouting = 0; + m_RouteCount = 0; +} + + +MATRIX_ROUTING_HEAD::~MATRIX_ROUTING_HEAD() +{ +} + + +bool MATRIX_ROUTING_HEAD::ComputeMatrixSize( BOARD* aPcb, bool aUseBoardEdgesOnly ) +{ + aPcb->ComputeBoundingBox( aUseBoardEdgesOnly ); + + // The boundary box must have its start point on routing grid: + m_BrdBox = aPcb->GetBoundingBox(); + + m_BrdBox.SetX( m_BrdBox.GetX() - ( m_BrdBox.GetX() % m_GridRouting ) ); + m_BrdBox.SetY( m_BrdBox.GetY() - ( m_BrdBox.GetY() % m_GridRouting ) ); + + // The boundary box must have its end point on routing grid: + wxPoint end = m_BrdBox.GetEnd(); + + end.x -= end.x % m_GridRouting; + end.x += m_GridRouting; + + end.y -= end.y % m_GridRouting; + end.y += m_GridRouting; + + m_BrdBox.SetEnd( end ); + + aPcb->SetBoundingBox( m_BrdBox ); + + m_Nrows = m_BrdBox.GetHeight() / m_GridRouting; + m_Ncols = m_BrdBox.GetWidth() / m_GridRouting; + + // gives a small margin + m_Ncols += 1; + m_Nrows += 1; + + return true; +} + + +int MATRIX_ROUTING_HEAD::InitRoutingMatrix() +{ + if( m_Nrows <= 0 || m_Ncols <= 0 ) + return 0; + + m_InitMatrixDone = true; // we have been called + + // give a small margin for memory allocation: + int ii = (RoutingMatrix.m_Nrows + 1) * (RoutingMatrix.m_Ncols + 1); + + int side = BOTTOM; + for( int jj = 0; jj < m_RoutingLayersCount; jj++ ) // m_RoutingLayersCount = 1 or 2 + { + m_BoardSide[side] = NULL; + m_DistSide[side] = NULL; + m_DirSide[side] = NULL; + + // allocate matrix & initialize everything to empty + m_BoardSide[side] = (MATRIX_CELL*) operator new( ii * sizeof(MATRIX_CELL) ); + memset( m_BoardSide[side], 0, ii * sizeof(MATRIX_CELL) ); + + if( m_BoardSide[side] == NULL ) + return -1; + + // allocate Distances + m_DistSide[side] = (DIST_CELL*) operator new( ii * sizeof(DIST_CELL) ); + memset( m_DistSide[side], 0, ii * sizeof(DIST_CELL) ); + + if( m_DistSide[side] == NULL ) + return -1; + + // allocate Dir (chars) + m_DirSide[side] = (char*) operator new( ii ); + memset( m_DirSide[side], 0, ii ); + + if( m_DirSide[side] == NULL ) + return -1; + + side = TOP; + } + + m_MemSize = m_RouteCount * ii * ( sizeof(MATRIX_CELL) + + sizeof(DIST_CELL) + sizeof(char) ); + + return m_MemSize; +} + + +void MATRIX_ROUTING_HEAD::UnInitRoutingMatrix() +{ + int ii; + + m_InitMatrixDone = false; + + for( ii = 0; ii < MAX_ROUTING_LAYERS_COUNT; ii++ ) + { + // de-allocate Dir matrix + if( m_DirSide[ii] ) + { + delete m_DirSide[ii]; + m_DirSide[ii] = NULL; + } + + // de-allocate Distances matrix + if( m_DistSide[ii] ) + { + delete m_DistSide[ii]; + m_DistSide[ii] = NULL; + } + + // de-allocate cells matrix + if( m_BoardSide[ii] ) + { + delete m_BoardSide[ii]; + m_BoardSide[ii] = NULL; + } + } + + m_Nrows = m_Ncols = 0; +} + + +/** + * Function PlaceCells + * Initialize the matrix routing by setting obstacles for each occupied cell + * a cell set to HOLE is an obstacle for tracks and vias + * a cell set to VIA_IMPOSSIBLE is an obstacle for vias only. + * a cell set to CELL_is_EDGE is a frontier. + * Tracks and vias having the same net code as net_code are skipped + * (htey do not are obstacles) + * + * For single-sided Routing 1: + * BOTTOM side is used, and Route_Layer_BOTTOM = Route_Layer_TOP + * + * If flag == FORCE_PADS: all pads will be put in matrix as obstacles. + */ +void PlaceCells( BOARD* aPcb, int net_code, int flag ) +{ + int ux0 = 0, uy0 = 0, ux1, uy1, dx, dy; + int marge, via_marge; + LSET layerMask; + + // use the default NETCLASS? + NETCLASSPTR nc = aPcb->GetDesignSettings().GetDefault(); + + int trackWidth = nc->GetTrackWidth(); + int clearance = nc->GetClearance(); + int viaSize = nc->GetViaDiameter(); + + marge = clearance + (trackWidth / 2); + via_marge = clearance + (viaSize / 2); + + // Place PADS on matrix routing: + for( unsigned i = 0; i < aPcb->GetPadCount(); ++i ) + { + D_PAD* pad = aPcb->GetPad( i ); + + if( net_code != pad->GetNetCode() || (flag & FORCE_PADS) ) + { + ::PlacePad( pad, HOLE, marge, WRITE_CELL ); + } + + ::PlacePad( pad, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL ); + } + + // Place outlines of modules on matrix routing, if they are on a copper layer + // or on the edge layer + + for( MODULE* module = aPcb->m_Modules; module; module = module->Next() ) + { + for( BOARD_ITEM* item = module->GraphicalItems(); item; item = item->Next() ) + { + switch( item->Type() ) + { + case PCB_MODULE_EDGE_T: + { + EDGE_MODULE* edge = (EDGE_MODULE*) item; + EDGE_MODULE tmpEdge( *edge ); + + if( tmpEdge.GetLayer() == Edge_Cuts ) + tmpEdge.SetLayer( UNDEFINED_LAYER ); + + TraceSegmentPcb( &tmpEdge, HOLE, marge, WRITE_CELL ); + TraceSegmentPcb( &tmpEdge, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL ); + } + break; + + default: + break; + } + } + } + + // Place board outlines and texts on copper layers: + for( BOARD_ITEM* item = aPcb->m_Drawings; item; item = item->Next() ) + { + switch( item->Type() ) + { + case PCB_LINE_T: + { + DRAWSEGMENT* DrawSegm; + + int type_cell = HOLE; + DrawSegm = (DRAWSEGMENT*) item; + DRAWSEGMENT tmpSegm( DrawSegm ); + + if( DrawSegm->GetLayer() == Edge_Cuts ) + { + tmpSegm.SetLayer( UNDEFINED_LAYER ); + type_cell |= CELL_is_EDGE; + } + + TraceSegmentPcb( &tmpSegm, type_cell, marge, WRITE_CELL ); + } + break; + + case PCB_TEXT_T: + { + TEXTE_PCB* PtText = (TEXTE_PCB*) item; + + if( PtText->GetText().Length() == 0 ) + break; + + EDA_RECT textbox = PtText->GetTextBox( -1 ); + ux0 = textbox.GetX(); + uy0 = textbox.GetY(); + dx = textbox.GetWidth(); + dy = textbox.GetHeight(); + + // Put bounding box (rectangle) on matrix + dx /= 2; + dy /= 2; + + ux1 = ux0 + dx; + uy1 = uy0 + dy; + + ux0 -= dx; + uy0 -= dy; + + layerMask = LSET( PtText->GetLayer() ); + + TraceFilledRectangle( ux0 - marge, uy0 - marge, ux1 + marge, + uy1 + marge, PtText->GetOrientation(), + layerMask, HOLE, WRITE_CELL ); + + TraceFilledRectangle( ux0 - via_marge, uy0 - via_marge, + ux1 + via_marge, uy1 + via_marge, + PtText->GetOrientation(), + layerMask, VIA_IMPOSSIBLE, WRITE_OR_CELL ); + } + break; + + default: + break; + } + } + + // Put tracks and vias on matrix + for( TRACK* track = aPcb->m_Track; track; track = track->Next() ) + { + if( net_code == track->GetNetCode() ) + continue; + + TraceSegmentPcb( track, HOLE, marge, WRITE_CELL ); + TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL ); + } +} + + +int Build_Work( BOARD* Pcb ) +{ + RATSNEST_ITEM* pt_rats; + D_PAD* pt_pad; + int r1, r2, c1, c2, current_net_code; + RATSNEST_ITEM* pt_ch; + int demi_pas = RoutingMatrix.m_GridRouting / 2; + wxString msg; + + InitWork(); // clear work list + int cellCount = 0; + + for( unsigned ii = 0; ii < Pcb->GetRatsnestsCount(); ii++ ) + { + pt_rats = &Pcb->m_FullRatsnest[ii]; + + /* We consider here only ratsnest that are active ( obviously not yet routed) + * and routables (that are not yet attempt to be routed and fail + */ + if( (pt_rats->m_Status & CH_ACTIF) == 0 ) + continue; + + if( pt_rats->m_Status & CH_UNROUTABLE ) + continue; + + if( (pt_rats->m_Status & CH_ROUTE_REQ) == 0 ) + continue; + + pt_pad = pt_rats->m_PadStart; + + current_net_code = pt_pad->GetNetCode(); + pt_ch = pt_rats; + + r1 = ( pt_pad->GetPosition().y - RoutingMatrix.m_BrdBox.GetY() + demi_pas ) + / RoutingMatrix.m_GridRouting; + + if( r1 < 0 || r1 >= RoutingMatrix.m_Nrows ) + { + msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r1, + pt_pad->GetPosition().y, RoutingMatrix.m_BrdBox.GetY() ); + wxMessageBox( msg ); + return 0; + } + + c1 = ( pt_pad->GetPosition().x - RoutingMatrix.m_BrdBox.GetX() + demi_pas ) / RoutingMatrix.m_GridRouting; + + if( c1 < 0 || c1 >= RoutingMatrix.m_Ncols ) + { + msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c1, + pt_pad->GetPosition().x, RoutingMatrix.m_BrdBox.GetX() ); + wxMessageBox( msg ); + return 0; + } + + pt_pad = pt_rats->m_PadEnd; + + r2 = ( pt_pad->GetPosition().y - RoutingMatrix.m_BrdBox.GetY() + + demi_pas ) / RoutingMatrix.m_GridRouting; + + if( r2 < 0 || r2 >= RoutingMatrix.m_Nrows ) + { + msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r2, + pt_pad->GetPosition().y, RoutingMatrix.m_BrdBox.GetY() ); + wxMessageBox( msg ); + return 0; + } + + c2 = ( pt_pad->GetPosition().x - RoutingMatrix.m_BrdBox.GetX() + demi_pas ) + / RoutingMatrix.m_GridRouting; + + if( c2 < 0 || c2 >= RoutingMatrix.m_Ncols ) + { + msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c2, + pt_pad->GetPosition().x, RoutingMatrix.m_BrdBox.GetX() ); + wxMessageBox( msg ); + return 0; + } + + SetWork( r1, c1, current_net_code, r2, c2, pt_ch, 0 ); + cellCount++; + } + + SortWork(); + return cellCount; +} + +// Initialize m_opWriteCell member to make the aLogicOp +void MATRIX_ROUTING_HEAD::SetCellOperation( int aLogicOp ) +{ + switch( aLogicOp ) + { + default: + case WRITE_CELL: + m_opWriteCell = &MATRIX_ROUTING_HEAD::SetCell; + break; + + case WRITE_OR_CELL: + m_opWriteCell = &MATRIX_ROUTING_HEAD::OrCell; + break; + + case WRITE_XOR_CELL: + m_opWriteCell = &MATRIX_ROUTING_HEAD::XorCell; + break; + + case WRITE_AND_CELL: + m_opWriteCell = &MATRIX_ROUTING_HEAD::AndCell; + break; + + case WRITE_ADD_CELL: + m_opWriteCell = &MATRIX_ROUTING_HEAD::AddCell; + break; + } +} + + +/* return the value stored in a cell + */ +MATRIX_CELL MATRIX_ROUTING_HEAD::GetCell( int aRow, int aCol, int aSide ) +{ + MATRIX_CELL* p; + + p = RoutingMatrix.m_BoardSide[aSide]; + return p[aRow * m_Ncols + aCol]; +} + + +/* basic cell operation : WRITE operation + */ +void MATRIX_ROUTING_HEAD::SetCell( int aRow, int aCol, int aSide, MATRIX_CELL x ) +{ + MATRIX_CELL* p; + + p = RoutingMatrix.m_BoardSide[aSide]; + p[aRow * m_Ncols + aCol] = x; +} + + +/* basic cell operation : OR operation + */ +void MATRIX_ROUTING_HEAD::OrCell( int aRow, int aCol, int aSide, MATRIX_CELL x ) +{ + MATRIX_CELL* p; + + p = RoutingMatrix.m_BoardSide[aSide]; + p[aRow * m_Ncols + aCol] |= x; +} + + +/* basic cell operation : XOR operation + */ +void MATRIX_ROUTING_HEAD::XorCell( int aRow, int aCol, int aSide, MATRIX_CELL x ) +{ + MATRIX_CELL* p; + + p = RoutingMatrix.m_BoardSide[aSide]; + p[aRow * m_Ncols + aCol] ^= x; +} + + +/* basic cell operation : AND operation + */ +void MATRIX_ROUTING_HEAD::AndCell( int aRow, int aCol, int aSide, MATRIX_CELL x ) +{ + MATRIX_CELL* p; + + p = RoutingMatrix.m_BoardSide[aSide]; + p[aRow * m_Ncols + aCol] &= x; +} + + +/* basic cell operation : ADD operation + */ +void MATRIX_ROUTING_HEAD::AddCell( int aRow, int aCol, int aSide, MATRIX_CELL x ) +{ + MATRIX_CELL* p; + + p = RoutingMatrix.m_BoardSide[aSide]; + p[aRow * m_Ncols + aCol] += x; +} + + +// fetch distance cell +DIST_CELL MATRIX_ROUTING_HEAD::GetDist( int aRow, int aCol, int aSide ) // fetch distance cell +{ + DIST_CELL* p; + + p = RoutingMatrix.m_DistSide[aSide]; + return p[aRow * m_Ncols + aCol]; +} + + +// store distance cell +void MATRIX_ROUTING_HEAD::SetDist( int aRow, int aCol, int aSide, DIST_CELL x ) +{ + DIST_CELL* p; + + p = RoutingMatrix.m_DistSide[aSide]; + p[aRow * m_Ncols + aCol] = x; +} + + +// fetch direction cell +int MATRIX_ROUTING_HEAD::GetDir( int aRow, int aCol, int aSide ) +{ + DIR_CELL* p; + + p = RoutingMatrix.m_DirSide[aSide]; + return (int) (p[aRow * m_Ncols + aCol]); +} + + +// store direction cell +void MATRIX_ROUTING_HEAD::SetDir( int aRow, int aCol, int aSide, int x ) +{ + DIR_CELL* p; + + p = RoutingMatrix.m_DirSide[aSide]; + p[aRow * m_Ncols + aCol] = (char) x; +} diff --git a/pcbnew/autorouter/solve.cpp b/pcbnew/autorouter/solve.cpp new file mode 100644 index 0000000..c10e57f --- /dev/null +++ b/pcbnew/autorouter/solve.cpp @@ -0,0 +1,1348 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * + * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors. + * + * First copyright (C) Randy Nevin, 1989 (see PCBCA package) + * + * 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 + */ + +/* see "Autorouting With the A* Algorithm" (Dr.Dobbs journal) +*/ + +/** + * @file solve.cpp + */ + +#include <fctsys.h> +#include <class_drawpanel.h> +#include <confirm.h> +#include <wxPcbStruct.h> +#include <gr_basic.h> +#include <macros.h> + +#include <class_board.h> +#include <class_track.h> + +#include <pcbnew.h> +#include <protos.h> +#include <autorout.h> +#include <cell.h> + + +static int Autoroute_One_Track( PCB_EDIT_FRAME* pcbframe, + wxDC* DC, + int two_sides, + int row_source, + int col_source, + int row_target, + int col_target, + RATSNEST_ITEM* pt_rat ); + +static int Retrace( PCB_EDIT_FRAME* pcbframe, + wxDC* DC, + int, + int, + int, + int, + int, + int net_code ); + +static void OrCell_Trace( BOARD* pcb, + int col, + int row, + int side, + int orient, + int current_net_code ); + +static void AddNewTrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC ); + + +static int segm_oX, segm_oY; +static int segm_fX, segm_fY; /* Origin and position of the current + * trace segment. */ +static RATSNEST_ITEM* pt_cur_ch; +static int s_Clearance; // Clearance value used in autorouter + +static PICKED_ITEMS_LIST s_ItemsListPicker; + +int OpenNodes; // total number of nodes opened +int ClosNodes; // total number of nodes closed +int MoveNodes; // total number of nodes moved +int MaxNodes; // maximum number of nodes opened at one time + +#define NOSUCCESS 0 +#define STOP_FROM_ESC -1 +#define ERR_MEMORY -2 +#define SUCCESS 1 +#define TRIVIAL_SUCCESS 2 + +/* +** visit neighboring cells like this (where [9] is on the other side): +** +** +---+---+---+ +** | 1 | 2 | 3 | +** +---+---+---+ +** | 4 |[9]| 5 | +** +---+---+---+ +** | 6 | 7 | 8 | +** +---+---+---+ +*/ + +/* for visiting neighbors on the same side: increments/decrements coord of + * [] [0] = row [] (1] = col was added to the coord of the midpoint for + * Get the coord of the 8 neighboring points. + */ +static const int delta[8][2] = +{ + { 1, -1 }, // northwest + { 1, 0 }, // north + { 1, 1 }, // northeast + { 0, -1 }, // west + { 0, 1 }, // east + { -1, -1 }, // southwest + { -1, 0 }, // south + { -1, 1 } // southeast +}; + +static const int ndir[8] = +{ + // for building paths back to source + FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST, + FROM_EAST, FROM_WEST, + FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST +}; + +// blocking masks for neighboring cells +#define BLOCK_NORTHEAST ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \ + | ANGLE_NEtoSE | ANGLE_NWtoNE \ + | SHARP_NtoNE | SHARP_EtoNE | HOLE ) +#define BLOCK_SOUTHEAST ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \ + | ANGLE_NEtoSE | ANGLE_SEtoSW \ + | SHARP_EtoSE | SHARP_StoSE | HOLE ) +#define BLOCK_SOUTHWEST ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \ + | ANGLE_SEtoSW | ANGLE_SWtoNW \ + | SHARP_StoSW | SHARP_WtoSW | HOLE ) +#define BLOCK_NORTHWEST ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \ + | ANGLE_SWtoNW | ANGLE_NWtoNE \ + | SHARP_WtoNW | SHARP_NtoNW | HOLE ) +#define BLOCK_NORTH ( LINE_VERTICAL | BENT_NtoSE | BENT_NtoSW \ + | BENT_EtoNW | BENT_WtoNE \ + | BENT_StoNE | BENT_StoNW \ + | CORNER_NORTHEAST | CORNER_NORTHWEST \ + | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_NWtoNE \ + | DIAG_NEtoSW | DIAG_SEtoNW \ + | SHARP_NtoNE | SHARP_NtoNW \ + | SHARP_EtoNE | SHARP_WtoNW | HOLE ) +#define BLOCK_EAST ( LINE_HORIZONTAL | BENT_EtoSW | BENT_EtoNW \ + | BENT_NtoSE | BENT_StoNE \ + | BENT_WtoNE | BENT_WtoSE \ + | CORNER_NORTHEAST | CORNER_SOUTHEAST \ + | ANGLE_NEtoSE | ANGLE_SEtoSW | ANGLE_NWtoNE \ + | DIAG_NEtoSW | DIAG_SEtoNW \ + | SHARP_EtoNE | SHARP_EtoSE \ + | SHARP_NtoNE | SHARP_StoSE | HOLE ) +#define BLOCK_SOUTH ( LINE_VERTICAL | BENT_StoNE | BENT_StoNW \ + | BENT_EtoSW | BENT_WtoSE \ + | BENT_NtoSE | BENT_NtoSW \ + | CORNER_SOUTHEAST | CORNER_SOUTHWEST \ + | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_SEtoSW \ + | DIAG_NEtoSW | DIAG_SEtoNW \ + | SHARP_StoSE | SHARP_StoSW \ + | SHARP_EtoSE | SHARP_WtoSW | HOLE ) +#define BLOCK_WEST ( LINE_HORIZONTAL | BENT_WtoNE | BENT_WtoSE \ + | BENT_NtoSW | BENT_StoNW \ + | BENT_EtoSW | BENT_EtoNW \ + | CORNER_SOUTHWEST | CORNER_NORTHWEST \ + | ANGLE_SWtoNW | ANGLE_SEtoSW | ANGLE_NWtoNE \ + | DIAG_NEtoSW | DIAG_SEtoNW \ + | SHARP_WtoSW | SHARP_WtoNW \ + | SHARP_NtoNW | SHARP_StoSW | HOLE ) + +struct block +{ + int r1, c1; + long b1; + int r2, c2; + long b2; +}; + +// blocking masks for diagonal traces +static struct block blocking[8] = +{ { + 0, -1, + BLOCK_NORTHEAST, + 1, 0, + BLOCK_SOUTHWEST + }, + { + 0, 0, 0, + 0, 0, 0 + }, + { + 1, 0, + BLOCK_SOUTHEAST, + 0, 1, + BLOCK_NORTHWEST + }, + { + 0, 0, 0, + 0, 0, 0 + }, + { + 0, 0, 0, + 0, 0, 0 + }, + { + 0, -1, + BLOCK_SOUTHEAST, + -1, 0, + BLOCK_NORTHWEST + }, + { + 0, 0, 0, + 0, 0, 0 + }, + { + -1, 0, + BLOCK_NORTHEAST, + 0, 1, + BLOCK_SOUTHWEST + } }; + +// mask for hole-related blocking effects +static struct +{ + long trace; + int present; +} selfok2[8] = +{ + { HOLE_NORTHWEST, 0 }, + { HOLE_NORTH, 0 }, + { HOLE_NORTHEAST, 0 }, + { HOLE_WEST, 0 }, + { HOLE_EAST, 0 }, + { HOLE_SOUTHWEST, 0 }, + { HOLE_SOUTH, 0 }, + { HOLE_SOUTHEAST, 0 } +}; + +static long newmask[8] = +{ + // patterns to mask out in neighbor cells + 0, + CORNER_NORTHWEST | CORNER_NORTHEAST, + 0, + CORNER_NORTHWEST | CORNER_SOUTHWEST, + CORNER_NORTHEAST | CORNER_SOUTHEAST, + 0, + CORNER_SOUTHWEST | CORNER_SOUTHEAST, + 0 +}; + + +/* Route all traces + * : + * 1 if OK + * -1 if escape (stop being routed) request + * -2 if default memory allocation + */ +int PCB_EDIT_FRAME::Solve( wxDC* DC, int aLayersCount ) +{ + int current_net_code; + int row_source, col_source, row_target, col_target; + int success, nbsucces = 0, nbunsucces = 0; + NETINFO_ITEM* net; + bool stop = false; + wxString msg; + int routedCount = 0; // routed ratsnest count + bool two_sides = aLayersCount == 2; + + m_canvas->SetAbortRequest( false ); + + s_Clearance = GetBoard()->GetDesignSettings().GetDefault()->GetClearance(); + + // Prepare the undo command info + s_ItemsListPicker.ClearListAndDeleteItems(); // Should not be necessary, but... + + // go until no more work to do + GetWork( &row_source, &col_source, ¤t_net_code, + &row_target, &col_target, &pt_cur_ch ); // First net to route. + + for( ; row_source != ILLEGAL; GetWork( &row_source, &col_source, + ¤t_net_code, &row_target, + &col_target, + &pt_cur_ch ) ) + { + // Test to stop routing ( escape key pressed ) + wxYield(); + + if( m_canvas->GetAbortRequest() ) + { + if( IsOK( this, _( "Abort routing?" ) ) ) + { + success = STOP_FROM_ESC; + stop = true; + break; + } + else + { + m_canvas->SetAbortRequest( false ); + } + } + + EraseMsgBox(); + + routedCount++; + net = GetBoard()->FindNet( current_net_code ); + + if( net ) + { + msg.Printf( wxT( "[%8.8s]" ), GetChars( net->GetNetname() ) ); + AppendMsgPanel( wxT( "Net route" ), msg, BROWN ); + msg.Printf( wxT( "%d / %d" ), routedCount, RoutingMatrix.m_RouteCount ); + AppendMsgPanel( wxT( "Activity" ), msg, BROWN ); + } + + segm_oX = GetBoard()->GetBoundingBox().GetX() + (RoutingMatrix.m_GridRouting * col_source); + segm_oY = GetBoard()->GetBoundingBox().GetY() + (RoutingMatrix.m_GridRouting * row_source); + segm_fX = GetBoard()->GetBoundingBox().GetX() + (RoutingMatrix.m_GridRouting * col_target); + segm_fY = GetBoard()->GetBoundingBox().GetY() + (RoutingMatrix.m_GridRouting * row_target); + + // Draw segment. + GRLine( m_canvas->GetClipBox(), DC, + segm_oX, segm_oY, segm_fX, segm_fY, + 0, WHITE ); + pt_cur_ch->m_PadStart->Draw( m_canvas, DC, GR_OR | GR_HIGHLIGHT ); + pt_cur_ch->m_PadEnd->Draw( m_canvas, DC, GR_OR | GR_HIGHLIGHT ); + + success = Autoroute_One_Track( this, DC, + two_sides, row_source, col_source, + row_target, col_target, pt_cur_ch ); + + switch( success ) + { + case NOSUCCESS: + pt_cur_ch->m_Status |= CH_UNROUTABLE; + nbunsucces++; + break; + + case STOP_FROM_ESC: + stop = true; + break; + + case ERR_MEMORY: + stop = true; + break; + + default: + nbsucces++; + break; + } + + msg.Printf( wxT( "%d" ), nbsucces ); + AppendMsgPanel( wxT( "OK" ), msg, GREEN ); + msg.Printf( wxT( "%d" ), nbunsucces ); + AppendMsgPanel( wxT( "Fail" ), msg, RED ); + msg.Printf( wxT( " %d" ), GetBoard()->GetUnconnectedNetCount() ); + AppendMsgPanel( wxT( "Not Connected" ), msg, CYAN ); + + // Delete routing from display. + pt_cur_ch->m_PadStart->Draw( m_canvas, DC, GR_AND ); + pt_cur_ch->m_PadEnd->Draw( m_canvas, DC, GR_AND ); + + if( stop ) + break; + } + + SaveCopyInUndoList( s_ItemsListPicker, UR_UNSPECIFIED ); + s_ItemsListPicker.ClearItemsList(); // s_ItemsListPicker is no more owner of picked items + + return SUCCESS; +} + + +/* Route a trace on the BOARD. + * Parameters: + * 1 side / 2 sides (0 / 1) + * Coord source (row, col) + * Coord destination (row, col) + * Net_code + * Pointer to the ratsnest reference + * + * Returns: + * SUCCESS if routed + * TRIVIAL_SUCCESS if pads are connected by overlay (no track needed) + * If failure NOSUCCESS + * Escape STOP_FROM_ESC if demand + * ERR_MEMORY if memory allocation failed. + */ +static int Autoroute_One_Track( PCB_EDIT_FRAME* pcbframe, + wxDC* DC, + int two_sides, + int row_source, + int col_source, + int row_target, + int col_target, + RATSNEST_ITEM* pt_rat ) +{ + int r, c, side, d, apx_dist, nr, nc; + int result, skip; + int i; + long curcell, newcell, buddy, lastopen, lastclos, lastmove; + int newdist, olddir, _self; + int current_net_code; + int marge; + LSET padLayerMaskStart; // Mask layers belonging to the starting pad. + LSET padLayerMaskEnd; // Mask layers belonging to the ending pad. + + LSET topLayerMask( g_Route_Layer_TOP ); + + LSET bottomLayerMask( g_Route_Layer_BOTTOM ); + + LSET routeLayerMask; // Mask two layers for routing. + + LSET tab_mask[2]; // Enables the calculation of the mask layer being + // tested. (side = TOP or BOTTOM) + int start_mask_layer = 0; + wxString msg; + + // @todo this could be a bottle neck + LSET all_cu = LSET::AllCuMask( pcbframe->GetBoard()->GetCopperLayerCount() ); + + wxBusyCursor dummy_cursor; // Set an hourglass cursor while routing a + // track + + result = NOSUCCESS; + + marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 ); + + // clear direction flags + i = RoutingMatrix.m_Nrows * RoutingMatrix.m_Ncols * sizeof(DIR_CELL); + + if( two_sides ) + memset( RoutingMatrix.m_DirSide[TOP], FROM_NOWHERE, i ); + memset( RoutingMatrix.m_DirSide[BOTTOM], FROM_NOWHERE, i ); + + lastopen = lastclos = lastmove = 0; + + // Set tab_masque[side] for final test of routing. + if( two_sides ) + tab_mask[TOP] = topLayerMask; + tab_mask[BOTTOM] = bottomLayerMask; + + // Set active layers mask. + routeLayerMask = topLayerMask | bottomLayerMask; + + pt_cur_ch = pt_rat; + + current_net_code = pt_rat->GetNet(); + padLayerMaskStart = pt_cur_ch->m_PadStart->GetLayerSet(); + + padLayerMaskEnd = pt_cur_ch->m_PadEnd->GetLayerSet(); + + + /* First Test if routing possible ie if the pads are accessible + * on the routing layers. + */ + if( ( routeLayerMask & padLayerMaskStart ) == 0 ) + goto end_of_route; + + if( ( routeLayerMask & padLayerMaskEnd ) == 0 ) + goto end_of_route; + + /* Then test if routing possible ie if the pads are accessible + * On the routing grid (1 grid point must be in the pad) + */ + { + int cX = ( RoutingMatrix.m_GridRouting * col_source ) + + pcbframe->GetBoard()->GetBoundingBox().GetX(); + int cY = ( RoutingMatrix.m_GridRouting * row_source ) + + pcbframe->GetBoard()->GetBoundingBox().GetY(); + int dx = pt_cur_ch->m_PadStart->GetSize().x / 2; + int dy = pt_cur_ch->m_PadStart->GetSize().y / 2; + int px = pt_cur_ch->m_PadStart->GetPosition().x; + int py = pt_cur_ch->m_PadStart->GetPosition().y; + + if( ( ( int( pt_cur_ch->m_PadStart->GetOrientation() ) / 900 ) & 1 ) != 0 ) + std::swap( dx, dy ); + + if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) ) + goto end_of_route; + + cX = ( RoutingMatrix.m_GridRouting * col_target ) + + pcbframe->GetBoard()->GetBoundingBox().GetX(); + cY = ( RoutingMatrix.m_GridRouting * row_target ) + + pcbframe->GetBoard()->GetBoundingBox().GetY(); + dx = pt_cur_ch->m_PadEnd->GetSize().x / 2; + dy = pt_cur_ch->m_PadEnd->GetSize().y / 2; + px = pt_cur_ch->m_PadEnd->GetPosition().x; + py = pt_cur_ch->m_PadEnd->GetPosition().y; + + if( ( ( int( pt_cur_ch->m_PadEnd->GetOrientation() ) / 900) & 1 ) != 0 ) + std::swap( dx, dy ); + + if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) ) + goto end_of_route; + } + + // Test the trivial case: direct connection overlay pads. + if( row_source == row_target && col_source == col_target && + ( padLayerMaskEnd & padLayerMaskStart & all_cu ).any() ) + { + result = TRIVIAL_SUCCESS; + goto end_of_route; + } + + // Placing the bit to remove obstacles on 2 pads to a link. + pcbframe->SetStatusText( wxT( "Gen Cells" ) ); + + PlacePad( pt_cur_ch->m_PadStart, CURRENT_PAD, marge, WRITE_OR_CELL ); + PlacePad( pt_cur_ch->m_PadEnd, CURRENT_PAD, marge, WRITE_OR_CELL ); + + // Regenerates the remaining barriers (which may encroach on the + // placement bits precedent) + i = pcbframe->GetBoard()->GetPadCount(); + + for( unsigned ii = 0; ii < pcbframe->GetBoard()->GetPadCount(); ii++ ) + { + D_PAD* ptr = pcbframe->GetBoard()->GetPad( ii ); + + if( ( pt_cur_ch->m_PadStart != ptr ) && ( pt_cur_ch->m_PadEnd != ptr ) ) + { + PlacePad( ptr, ~CURRENT_PAD, marge, WRITE_AND_CELL ); + } + } + + InitQueue(); // initialize the search queue + apx_dist = RoutingMatrix.GetApxDist( row_source, col_source, row_target, col_target ); + + // Initialize first search. + if( two_sides ) // Preferred orientation. + { + if( abs( row_target - row_source ) > abs( col_target - col_source ) ) + { + if( ( padLayerMaskStart & topLayerMask ).any() ) + { + start_mask_layer = 2; + + if( SetQueue( row_source, col_source, TOP, 0, apx_dist, + row_target, col_target ) == 0 ) + { + return ERR_MEMORY; + } + } + + if( ( padLayerMaskStart & bottomLayerMask ).any() ) + { + start_mask_layer |= 1; + + if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist, + row_target, col_target ) == 0 ) + { + return ERR_MEMORY; + } + } + } + else + { + if( ( padLayerMaskStart & bottomLayerMask ).any() ) + { + start_mask_layer = 1; + + if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist, + row_target, col_target ) == 0 ) + { + return ERR_MEMORY; + } + } + + if( ( padLayerMaskStart & topLayerMask ).any() ) + { + start_mask_layer |= 2; + + if( SetQueue( row_source, col_source, TOP, 0, apx_dist, + row_target, col_target ) == 0 ) + { + return ERR_MEMORY; + } + } + } + } + else if( ( padLayerMaskStart & bottomLayerMask ).any() ) + { + start_mask_layer = 1; + + if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist, row_target, col_target ) == 0 ) + { + return ERR_MEMORY; + } + } + + // search until success or we exhaust all possibilities + GetQueue( &r, &c, &side, &d, &apx_dist ); + + for( ; r != ILLEGAL; GetQueue( &r, &c, &side, &d, &apx_dist ) ) + { + curcell = RoutingMatrix.GetCell( r, c, side ); + + if( curcell & CURRENT_PAD ) + curcell &= ~HOLE; + + if( (r == row_target) && (c == col_target) // success if layer OK + && (tab_mask[side] & padLayerMaskEnd).any() ) + { + // Remove link. + GRSetDrawMode( DC, GR_XOR ); + GRLine( pcbframe->GetCanvas()->GetClipBox(), + DC, + segm_oX, + segm_oY, + segm_fX, + segm_fY, + 0, + WHITE ); + + // Generate trace. + if( Retrace( pcbframe, DC, row_source, col_source, + row_target, col_target, side, current_net_code ) ) + { + result = SUCCESS; // Success : Route OK + } + + break; // Routing complete. + } + + if( pcbframe->GetCanvas()->GetAbortRequest() ) + { + result = STOP_FROM_ESC; + break; + } + + // report every COUNT new nodes or so + #define COUNT 20000 + + if( ( OpenNodes - lastopen > COUNT ) + || ( ClosNodes - lastclos > COUNT ) + || ( MoveNodes - lastmove > COUNT ) ) + { + lastopen = OpenNodes; + lastclos = ClosNodes; + lastmove = MoveNodes; + msg.Printf( wxT( "Activity: Open %d Closed %d Moved %d" ), + OpenNodes, ClosNodes, MoveNodes ); + pcbframe->SetStatusText( msg ); + } + + _self = 0; + + if( curcell & HOLE ) + { + _self = 5; + + // set 'present' bits + for( i = 0; i < 8; i++ ) + { + selfok2[i].present = 0; + + if( curcell & selfok2[i].trace ) + selfok2[i].present = 1; + } + } + + for( i = 0; i < 8; i++ ) // consider neighbors + { + nr = r + delta[i][0]; + nc = c + delta[i][1]; + + // off the edge? + if( nr < 0 || nr >= RoutingMatrix.m_Nrows || + nc < 0 || nc >= RoutingMatrix.m_Ncols ) + continue; // off the edge + + if( _self == 5 && selfok2[i].present ) + continue; + + newcell = RoutingMatrix.GetCell( nr, nc, side ); + + if( newcell & CURRENT_PAD ) + newcell &= ~HOLE; + + // check for non-target hole + if( newcell & HOLE ) + { + if( nr != row_target || nc != col_target ) + continue; + } + // check for traces + else if( newcell & HOLE & ~(newmask[i]) ) + { + continue; + } + + // check blocking on corner neighbors + if( delta[i][0] && delta[i][1] ) + { + // check first buddy + buddy = RoutingMatrix.GetCell( r + blocking[i].r1, c + blocking[i].c1, side ); + + if( buddy & CURRENT_PAD ) + buddy &= ~HOLE; + + if( buddy & HOLE ) + continue; + +// if (buddy & (blocking[i].b1)) continue; + // check second buddy + buddy = RoutingMatrix.GetCell( r + blocking[i].r2, c + blocking[i].c2, side ); + + if( buddy & CURRENT_PAD ) + buddy &= ~HOLE; + + if( buddy & HOLE ) + continue; + +// if (buddy & (blocking[i].b2)) continue; + } + + olddir = RoutingMatrix.GetDir( r, c, side ); + newdist = d + RoutingMatrix.CalcDist( ndir[i], olddir, + ( olddir == FROM_OTHERSIDE ) ? + RoutingMatrix.GetDir( r, c, 1 - side ) : 0, side ); + + // if (a) not visited yet, or (b) we have + // found a better path, add it to queue + if( !RoutingMatrix.GetDir( nr, nc, side ) ) + { + RoutingMatrix.SetDir( nr, nc, side, ndir[i] ); + RoutingMatrix.SetDist( nr, nc, side, newdist ); + + if( SetQueue( nr, nc, side, newdist, + RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ), + row_target, col_target ) == 0 ) + { + return ERR_MEMORY; + } + } + else if( newdist < RoutingMatrix.GetDist( nr, nc, side ) ) + { + RoutingMatrix.SetDir( nr, nc, side, ndir[i] ); + RoutingMatrix.SetDist( nr, nc, side, newdist ); + ReSetQueue( nr, nc, side, newdist, + RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ), + row_target, col_target ); + } + } + + //* Test the other layer. * + if( two_sides ) + { + olddir = RoutingMatrix.GetDir( r, c, side ); + + if( olddir == FROM_OTHERSIDE ) + continue; // useless move, so don't bother + + if( curcell ) // can't drill via if anything here + continue; + + // check for holes or traces on other side + if( ( newcell = RoutingMatrix.GetCell( r, c, 1 - side ) ) != 0 ) + continue; + + // check for nearby holes or traces on both sides + for( skip = 0, i = 0; i < 8; i++ ) + { + nr = r + delta[i][0]; nc = c + delta[i][1]; + + if( nr < 0 || nr >= RoutingMatrix.m_Nrows || + nc < 0 || nc >= RoutingMatrix.m_Ncols ) + continue; // off the edge !! + + if( RoutingMatrix.GetCell( nr, nc, side ) /* & blocking2[i] */ ) + { + skip = 1; // can't drill via here + break; + } + + if( RoutingMatrix.GetCell( nr, nc, 1 - side ) /* & blocking2[i] */ ) + { + skip = 1; // can't drill via here + break; + } + } + + if( skip ) // neighboring hole or trace? + continue; // yes, can't drill via here + + newdist = d + RoutingMatrix.CalcDist( FROM_OTHERSIDE, olddir, 0, side ); + + /* if (a) not visited yet, + * or (b) we have found a better path, + * add it to queue */ + if( !RoutingMatrix.GetDir( r, c, 1 - side ) ) + { + RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE ); + RoutingMatrix.SetDist( r, c, 1 - side, newdist ); + + if( SetQueue( r, c, 1 - side, newdist, apx_dist, row_target, col_target ) == 0 ) + { + return ERR_MEMORY; + } + } + else if( newdist < RoutingMatrix.GetDist( r, c, 1 - side ) ) + { + RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE ); + RoutingMatrix.SetDist( r, c, 1 - side, newdist ); + ReSetQueue( r, c, + 1 - side, + newdist, + apx_dist, + row_target, + col_target ); + } + } // Finished attempt to route on other layer. + } + +end_of_route: + PlacePad( pt_cur_ch->m_PadStart, ~CURRENT_PAD, marge, WRITE_AND_CELL ); + PlacePad( pt_cur_ch->m_PadEnd, ~CURRENT_PAD, marge, WRITE_AND_CELL ); + + msg.Printf( wxT( "Activity: Open %d Closed %d Moved %d"), + OpenNodes, ClosNodes, MoveNodes ); + pcbframe->SetStatusText( msg ); + + return result; +} + + +static long bit[8][9] = +{ + // OT=Otherside + // N, NE, E, SE, S, SW, W, NW, OT +// N + { LINE_VERTICAL, + BENT_StoNE, + CORNER_SOUTHEAST, + SHARP_StoSE, + 0, + SHARP_StoSW, + CORNER_SOUTHWEST, + BENT_StoNW, + ( HOLE | HOLE_SOUTH ) + }, +// NE + { + BENT_NtoSW, + DIAG_NEtoSW, + BENT_EtoSW, + ANGLE_SEtoSW, + SHARP_StoSW, + 0, + SHARP_WtoSW, + ANGLE_SWtoNW, + ( HOLE | HOLE_SOUTHWEST ) + }, +// E + { + CORNER_NORTHWEST, + BENT_WtoNE, + LINE_HORIZONTAL, + BENT_WtoSE, + CORNER_SOUTHWEST, + SHARP_WtoSW, + 0, + SHARP_WtoNW, + ( HOLE | HOLE_WEST ) + }, +// SE + { + SHARP_NtoNW, + ANGLE_NWtoNE, + BENT_EtoNW, + DIAG_SEtoNW, + BENT_StoNW, + ANGLE_SWtoNW, + SHARP_WtoNW, + 0, + ( HOLE | HOLE_NORTHWEST ) + }, +// S + { + 0, + SHARP_NtoNE, + CORNER_NORTHEAST, + BENT_NtoSE, + LINE_VERTICAL, + BENT_NtoSW, + CORNER_NORTHWEST, + SHARP_NtoNW, + ( HOLE | HOLE_NORTH ) + }, +// SW + { + SHARP_NtoNE, + 0, + SHARP_EtoNE, + ANGLE_NEtoSE, + BENT_StoNE, + DIAG_NEtoSW, + BENT_WtoNE, + ANGLE_NWtoNE, + ( HOLE | HOLE_NORTHEAST ) + }, +// W + { + CORNER_NORTHEAST, + SHARP_EtoNE, + 0, + SHARP_EtoSE, + CORNER_SOUTHEAST, + BENT_EtoSW, + LINE_HORIZONTAL, + BENT_EtoNW, + ( HOLE | HOLE_EAST ) + }, +// NW + { + BENT_NtoSE, + ANGLE_NEtoSE, + SHARP_EtoSE, + 0, + SHARP_StoSE, + ANGLE_SEtoSW, + BENT_WtoSE, + DIAG_SEtoNW, + ( HOLE | HOLE_SOUTHEAST ) + } +}; + + +/* work from target back to source, actually laying the traces + * Parameters: + * start on side target_side, of coordinates row_target, col_target. + * arrive on side masque_layer_start, coordinate row_source, col_source + * The search is done in reverse routing, the point of arrival (target) to + * the starting point (source) + * The router. + * + * Target_side = symbol (TOP / BOTTOM) of departure + * = Mask_layer_source mask layers Arrival + * + * Returns: + * 0 if error + * > 0 if Ok + */ +static int Retrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC, + int row_source, int col_source, + int row_target, int col_target, int target_side, + int current_net_code ) +{ + int r0, c0, s0; + int r1, c1, s1; // row, col, starting side. + int r2, c2, s2; // row, col, ending side. + int x, y = -1; + long b; + + r1 = row_target; + c1 = col_target; // start point is target ( end point is source ) + s1 = target_side; + r0 = c0 = s0 = ILLEGAL; + + wxASSERT( g_CurrentTrackList.GetCount() == 0 ); + + do + { + // find where we came from to get here + r2 = r1; c2 = c1; s2 = s1; + x = RoutingMatrix.GetDir( r1, c1, s1 ); + + switch( x ) + { + case FROM_NORTH: + r2++; + break; + + case FROM_EAST: + c2++; + break; + + case FROM_SOUTH: + r2--; + break; + + case FROM_WEST: + c2--; + break; + + case FROM_NORTHEAST: + r2++; + c2++; + break; + + case FROM_SOUTHEAST: + r2--; + c2++; + break; + + case FROM_SOUTHWEST: + r2--; + c2--; + break; + + case FROM_NORTHWEST: + r2++; + c2--; + break; + + case FROM_OTHERSIDE: + s2 = 1 - s2; + break; + + default: + wxMessageBox( wxT( "Retrace: internal error: no way back" ) ); + return 0; + } + + if( r0 != ILLEGAL ) + y = RoutingMatrix.GetDir( r0, c0, s0 ); + + // see if target or hole + if( ( ( r1 == row_target ) && ( c1 == col_target ) ) || ( s1 != s0 ) ) + { + int p_dir; + + switch( x ) + { + case FROM_NORTH: + p_dir = HOLE_NORTH; + break; + + case FROM_EAST: + p_dir = HOLE_EAST; + break; + + case FROM_SOUTH: + p_dir = HOLE_SOUTH; + break; + + case FROM_WEST: + p_dir = HOLE_WEST; + break; + + case FROM_NORTHEAST: + p_dir = HOLE_NORTHEAST; + break; + + case FROM_SOUTHEAST: + p_dir = HOLE_SOUTHEAST; + break; + + case FROM_SOUTHWEST: + p_dir = HOLE_SOUTHWEST; + break; + + case FROM_NORTHWEST: + p_dir = HOLE_NORTHWEST; + break; + + case FROM_OTHERSIDE: + default: + DisplayError( pcbframe, wxT( "Retrace: error 1" ) ); + return 0; + } + + OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, p_dir, current_net_code ); + } + else + { + if( ( y == FROM_NORTH || y == FROM_NORTHEAST + || y == FROM_EAST || y == FROM_SOUTHEAST + || y == FROM_SOUTH || y == FROM_SOUTHWEST + || y == FROM_WEST || y == FROM_NORTHWEST ) + && ( x == FROM_NORTH || x == FROM_NORTHEAST + || x == FROM_EAST || x == FROM_SOUTHEAST + || x == FROM_SOUTH || x == FROM_SOUTHWEST + || x == FROM_WEST || x == FROM_NORTHWEST + || x == FROM_OTHERSIDE ) + && ( ( b = bit[y - 1][x - 1] ) != 0 ) ) + { + OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, b, current_net_code ); + + if( b & HOLE ) + OrCell_Trace( pcbframe->GetBoard(), r2, c2, s2, HOLE, current_net_code ); + } + else + { + wxMessageBox( wxT( "Retrace: error 2" ) ); + return 0; + } + } + + if( ( r2 == row_source ) && ( c2 == col_source ) ) // see if source + { + int p_dir; + + switch( x ) + { + case FROM_NORTH: + p_dir = HOLE_SOUTH; + break; + + case FROM_EAST: + p_dir = HOLE_WEST; + break; + + case FROM_SOUTH: + p_dir = HOLE_NORTH; + break; + + case FROM_WEST: + p_dir = HOLE_EAST; + break; + + case FROM_NORTHEAST: + p_dir = HOLE_SOUTHWEST; + break; + + case FROM_SOUTHEAST: + p_dir = HOLE_NORTHWEST; + break; + + case FROM_SOUTHWEST: + p_dir = HOLE_NORTHEAST; + break; + + case FROM_NORTHWEST: + p_dir = HOLE_SOUTHEAST; + break; + + case FROM_OTHERSIDE: + default: + wxMessageBox( wxT( "Retrace: error 3" ) ); + return 0; + } + + OrCell_Trace( pcbframe->GetBoard(), r2, c2, s2, p_dir, current_net_code ); + } + + // move to next cell + r0 = r1; + c0 = c1; + s0 = s1; + r1 = r2; + c1 = c2; + s1 = s2; + } while( !( ( r2 == row_source ) && ( c2 == col_source ) ) ); + + AddNewTrace( pcbframe, DC ); + return 1; +} + + +/* This function is used by Retrace and read the autorouting matrix data cells to create + * the real track on the physical board + */ +static void OrCell_Trace( BOARD* pcb, int col, int row, + int side, int orient, int current_net_code ) +{ + if( orient == HOLE ) // placement of a via + { + VIA *newVia = new VIA( pcb ); + + g_CurrentTrackList.PushBack( newVia ); + + g_CurrentTrackSegment->SetState( TRACK_AR, true ); + g_CurrentTrackSegment->SetLayer( F_Cu ); + + g_CurrentTrackSegment->SetStart(wxPoint( pcb->GetBoundingBox().GetX() + + ( RoutingMatrix.m_GridRouting * row ), + pcb->GetBoundingBox().GetY() + + ( RoutingMatrix.m_GridRouting * col ))); + g_CurrentTrackSegment->SetEnd( g_CurrentTrackSegment->GetStart() ); + + g_CurrentTrackSegment->SetWidth( pcb->GetDesignSettings().GetCurrentViaSize() ); + newVia->SetViaType( pcb->GetDesignSettings().m_CurrentViaType ); + + g_CurrentTrackSegment->SetNetCode( current_net_code ); + } + else // placement of a standard segment + { + TRACK *newTrack = new TRACK( pcb ); + int dx0, dy0, dx1, dy1; + + + g_CurrentTrackList.PushBack( newTrack ); + + g_CurrentTrackSegment->SetLayer( g_Route_Layer_BOTTOM ); + + if( side == TOP ) + g_CurrentTrackSegment->SetLayer( g_Route_Layer_TOP ); + + g_CurrentTrackSegment->SetState( TRACK_AR, true ); + g_CurrentTrackSegment->SetEnd( wxPoint( pcb->GetBoundingBox().GetX() + + ( RoutingMatrix.m_GridRouting * row ), + pcb->GetBoundingBox().GetY() + + ( RoutingMatrix.m_GridRouting * col ))); + g_CurrentTrackSegment->SetNetCode( current_net_code ); + + if( g_CurrentTrackSegment->Back() == NULL ) // Start trace. + { + g_CurrentTrackSegment->SetStart( wxPoint( segm_fX, segm_fY ) ); + + // Placement on the center of the pad if outside grid. + dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x; + dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y; + + dx0 = pt_cur_ch->m_PadEnd->GetPosition().x - g_CurrentTrackSegment->GetStart().x; + dy0 = pt_cur_ch->m_PadEnd->GetPosition().y - g_CurrentTrackSegment->GetStart().y; + + // If aligned, change the origin point. + if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) ) + { + g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() ); + } + else // Creation of a supplemental segment + { + g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() ); + + newTrack = (TRACK*)g_CurrentTrackSegment->Clone(); + newTrack->SetStart( g_CurrentTrackSegment->GetEnd()); + + g_CurrentTrackList.PushBack( newTrack ); + } + } + else + { + if( g_CurrentTrackSegment->Back() ) + { + g_CurrentTrackSegment->SetStart( g_CurrentTrackSegment->Back()->GetEnd() ); + } + } + + g_CurrentTrackSegment->SetWidth( pcb->GetDesignSettings().GetCurrentTrackWidth() ); + + if( g_CurrentTrackSegment->GetStart() != g_CurrentTrackSegment->GetEnd() ) + { + // Reduce aligned segments by one. + TRACK* oldTrack = g_CurrentTrackSegment->Back(); + + if( oldTrack && oldTrack->Type() != PCB_VIA_T ) + { + dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x; + dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y; + + dx0 = oldTrack->GetEnd().x - oldTrack->GetStart().x; + dy0 = oldTrack->GetEnd().y - oldTrack->GetStart().y; + + if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) ) + { + oldTrack->SetEnd( g_CurrentTrackSegment->GetEnd() ); + + delete g_CurrentTrackList.PopBack(); + } + } + } + } +} + + +/* Insert the new track created in the list of tracks. + * amend the points of beginning and end of the track so that they are + * connected + * Center on pads even if they are off grid. + */ +static void AddNewTrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC ) +{ + if( g_FirstTrackSegment == NULL ) + return; + + int dx0, dy0, dx1, dy1; + int marge, via_marge; + EDA_DRAW_PANEL* panel = pcbframe->GetCanvas(); + PCB_SCREEN* screen = pcbframe->GetScreen(); + + marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 ); + via_marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentViaSize() / 2 ); + + dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x; + dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y; + + // Place on center of pad if off grid. + dx0 = pt_cur_ch->m_PadStart->GetPosition().x - g_CurrentTrackSegment->GetStart().x; + dy0 = pt_cur_ch->m_PadStart->GetPosition().y - g_CurrentTrackSegment->GetStart().y; + + // If aligned, change the origin point. + if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) ) + { + g_CurrentTrackSegment->SetEnd( pt_cur_ch->m_PadStart->GetPosition() ); + } + else + { + TRACK* newTrack = (TRACK*)g_CurrentTrackSegment->Clone(); + + newTrack->SetEnd( pt_cur_ch->m_PadStart->GetPosition() ); + newTrack->SetStart( g_CurrentTrackSegment->GetEnd() ); + + g_CurrentTrackList.PushBack( newTrack ); + } + + g_FirstTrackSegment->start = pcbframe->GetBoard()->GetPad( g_FirstTrackSegment, + ENDPOINT_START ); + + if( g_FirstTrackSegment->start ) + g_FirstTrackSegment->SetState( BEGIN_ONPAD, true ); + + g_CurrentTrackSegment->end = pcbframe->GetBoard()->GetPad( g_CurrentTrackSegment, + ENDPOINT_END ); + + if( g_CurrentTrackSegment->end ) + g_CurrentTrackSegment->SetState( END_ONPAD, true ); + + // Out the new track on the matrix board + for( TRACK* track = g_FirstTrackSegment; track; track = track->Next() ) + { + TraceSegmentPcb( track, HOLE, marge, WRITE_CELL ); + TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL ); + } + + // Insert new segments in real board + int netcode = g_FirstTrackSegment->GetNetCode(); + TRACK* firstTrack = g_FirstTrackSegment; + int newCount = g_CurrentTrackList.GetCount(); + + // Put entire new current segment list in BOARD + TRACK* track; + TRACK* insertBeforeMe = g_CurrentTrackSegment->GetBestInsertPoint( pcbframe->GetBoard() ); + + while( ( track = g_CurrentTrackList.PopFront() ) != NULL ) + { + ITEM_PICKER picker( track, UR_NEW ); + s_ItemsListPicker.PushItem( picker ); + pcbframe->GetBoard()->m_Track.Insert( track, insertBeforeMe ); + } + + DrawTraces( panel, DC, firstTrack, newCount, GR_OR ); + + pcbframe->TestNetConnection( DC, netcode ); + + screen->SetModify(); +} diff --git a/pcbnew/autorouter/spread_footprints.cpp b/pcbnew/autorouter/spread_footprints.cpp new file mode 100644 index 0000000..52b7106 --- /dev/null +++ b/pcbnew/autorouter/spread_footprints.cpp @@ -0,0 +1,362 @@ +/* + * 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-2015 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() : TRect(), + n( 0 ) + { + } + + 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, + _( "Could not automatically place footprints. No board outlines detected." ) ); + 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 + MODULE* module = GetBoard()->m_Modules; + std::vector <MODULE*> moduleList; + + for( ; module != NULL; module = module->Next() ) + { + module->CalculateBoundingBox(); + + if( outsideBrdFilter ) + { + if( bbox.Contains( module->GetPosition() ) ) + continue; + } + + if( module->IsLocked() ) + continue; + + moduleList.push_back(module); + } + + 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++ ) + { + module = moduleList[ii]; + + // Undo: add copy of module to undo list + picker.SetItem( module ); + picker.SetLink( module->Clone() ); + 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++ ) + { + module = moduleList[ii]; + bool islastItem = false; + + if( ii == moduleList.size() - 1 || + ( moduleList[ii]->GetPath().BeforeLast( '/' ) != + moduleList[ii+1]->GetPath().BeforeLast( '/' ) ) ) + islastItem = true; + + moduleListBySheet.push_back( module ); + subsurface += module->GetArea(); + + if( islastItem ) + { + // 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(); + } + + // Prepare buffers for next sheet + 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(); +} + + +// 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 ). +static bool sortModulesbySheetPath( MODULE* ref, MODULE* compare ) +{ + if( ref->GetPath().Length() == compare->GetPath().Length() ) + return ref->GetPath().BeforeLast( '/' ).Cmp( compare->GetPath().BeforeLast( '/' ) ) < 0; + + return ref->GetPath().Length() < compare->GetPath().Length(); +} diff --git a/pcbnew/autorouter/work.cpp b/pcbnew/autorouter/work.cpp new file mode 100644 index 0000000..68aa48c --- /dev/null +++ b/pcbnew/autorouter/work.cpp @@ -0,0 +1,164 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr + * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com> + * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net> + * + * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors. + * + * First copyright (C) Randy Nevin, 1989 (see PCBCA package) + * + * 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 work.cpp + * @brief Automatic routing routines + */ + +#include <fctsys.h> +#include <common.h> + +#include <pcbnew.h> +#include <autorout.h> +#include <cell.h> + + +struct CWORK // a unit of work is a source-target to connect + // this is a ratsnest item in the routing matrix world +{ + int m_FromRow; // source row + int m_FromCol; // source column + int m_ToRow; // target row + int m_ToCol; // target column + RATSNEST_ITEM* m_Ratsnest; // Corresponding ratsnest + int m_NetCode; // m_NetCode + int m_ApxDist; // approximate distance + int m_Cost; // cost for sort by length + int m_Priority; // route priority + + // the function that calculates the cost of this ratsnest: + void CalculateCost(); +}; + + +// the list of ratsnests +static std::vector <CWORK> WorkList; +static unsigned Current = 0; + + +// initialize the work list +void InitWork() +{ + WorkList.clear(); + Current = 0; +} + + +/* add a unit of work to the work list + * : + * 1 if OK + * 0 if memory allocation failed + */ + +int SetWork( int r1, int c1, + int n_c, + int r2, int c2, + RATSNEST_ITEM* pt_ch, int pri ) +{ + CWORK item; + item.m_FromRow = r1; + item.m_FromCol = c1; + item.m_NetCode = n_c; + item.m_ToRow = r2; + item.m_ToCol = c2; + item.m_Ratsnest = pt_ch; + item.m_ApxDist = RoutingMatrix.GetApxDist( r1, c1, r2, c2 ); + item.CalculateCost(); + item.m_Priority = pri; + WorkList.push_back( item ); + return 1; +} + + +/* fetch a unit of work from the work list */ +void GetWork( int* r1, int* c1, + int* n_c, + int* r2, int* c2, + RATSNEST_ITEM** pt_ch ) +{ + if( Current < WorkList.size() ) + { + *r1 = WorkList[Current].m_FromRow; + *c1 = WorkList[Current].m_FromCol; + *n_c = WorkList[Current].m_NetCode; + *r2 = WorkList[Current].m_ToRow; + *c2 = WorkList[Current].m_ToCol; + *pt_ch = WorkList[Current].m_Ratsnest; + Current++; + } + else /* none left */ + { + *r1 = *c1 = *r2 = *c2 = ILLEGAL; + *n_c = 0; + *pt_ch = NULL; + } +} + + +// order the work items; shortest (low cost) first: +bool sort_by_cost( const CWORK& ref, const CWORK& item ) +{ + if( ref.m_Priority == item.m_Priority ) + return ref.m_Cost < item.m_Cost; + + return ref.m_Priority >= item.m_Priority; +} + +void SortWork() +{ + sort( WorkList.begin(), WorkList.end(), sort_by_cost ); +} + + +/* Calculate the cost of a ratsnest: + * cost = (| dx | + | dy |) * disability + * disability = 1 if dx or dy = 0, max if | dx | # | dy | + */ +void CWORK::CalculateCost() +{ + int dx, dy, mx, my; + double incl = 1.0; + + dx = abs( m_ToCol - m_FromCol ); + dy = abs( m_ToRow - m_FromRow ); + mx = dx; + my = dy; + + if( mx < my ) + { + mx = dy; my = dx; + } + + if( mx ) + incl += (2 * (double) my / mx); + + m_Cost = (int) ( ( dx + dy ) * incl ); +} |