1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929
|
/*
* This program source code file is part of KiCad, a free EDA CAD application.
*
* Copyright (C) 2007-2014 Jean-Pierre Charras, jp.charras at wanadoo.fr
* 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 ratsnest.cpp
* @brief Ratsnets functions.
*/
#include <fctsys.h>
#include <gr_basic.h>
#include <common.h>
#include <class_drawpanel.h>
#include <colors_selection.h>
#include <wxBasePcbFrame.h>
#include <macros.h>
#include <class_board.h>
#include <class_module.h>
#include <class_track.h>
#include <pcbnew.h>
#include <minimun_spanning_tree.h>
/**
* @brief class MIN_SPAN_TREE_PADS (derived from MIN_SPAN_TREE) specializes
* the base class to calculate a minimum spanning tree from a list of pads,
* and to add this tree as ratsnest to the main ratsnest list.
*/
class MIN_SPAN_TREE_PADS: public MIN_SPAN_TREE
{
friend class MIN_SPAN_TREE;
public:
std::vector <D_PAD*>* m_PadsList; // list of pads:
/* these pads are the parents of nodes of the tree.
* Each node position is the corresponding pad position.
* This pad list is used to evaluate the weight of an edge in tree.
* -> edge = link between 2 nodes = links between 2 pads.
* -> weight of a link = rectilinear distance between the 2 pads
*/
public:
MIN_SPAN_TREE_PADS(): MIN_SPAN_TREE()
{
m_PadsList = NULL;
}
void MSP_Init( std::vector <D_PAD*>* aPadsList )
{
m_PadsList = aPadsList;
MIN_SPAN_TREE::MSP_Init( (int) m_PadsList->size() );
}
/**
* Function AddTreeToRatsnest
* Adds the current minimum spanning tree as ratsnest items
* to the main ratsnest list
* @param aRatsnestList = a ratsnest list to add to
*/
void AddTreeToRatsnest( std::vector<RATSNEST_ITEM>* aRatsnestList );
/**
* Function GetWeight
* calculates the weight between 2 items
* NOTE: The weight between a node and itself should be 0
* @param aItem1 = first item
* @param aItem2 = other item
* @return the weight between items ( the rectilinear distance )
*/
int GetWeight( int aItem1, int aItem2 );
};
void MIN_SPAN_TREE_PADS::AddTreeToRatsnest( std::vector<RATSNEST_ITEM>* aRatsnestList )
{
std::vector<D_PAD*>& padsBuffer = *m_PadsList;
if( padsBuffer.empty() )
return;
int netcode = padsBuffer[0]->GetNetCode();
// Note: to get edges in minimum spanning tree,
// the index value 0 is not used: it is just
// the entry point of the minimum spanning tree.
// The first edge (i.e. rastnest) starts at index 1
for( int ii = 1; ii < m_Size; ii++ )
{
// Create the new ratsnest
RATSNEST_ITEM net;
net.SetNet( netcode );
net.m_Status = CH_ACTIF | CH_VISIBLE;
net.m_Lenght = GetDist(ii);
net.m_PadStart = padsBuffer[ii];
net.m_PadEnd = padsBuffer[ GetWhoTo(ii) ];
aRatsnestList->push_back( net );
}
}
/* Function GetWeight
* calculates the weight between 2 items
* Here it calculate the rectilinear distance between 2 pads (2 items)
* NOTE: The weight between a node and itself should be <=0
* aItem1 and aItem2 are the 2 items
* return the rectilinear distance
*/
int MIN_SPAN_TREE_PADS::GetWeight( int aItem1, int aItem2 )
{
// NOTE: The distance (weight) between a node and itself should be 0
// so we add 1 to other distances to be sure we never have 0
// in cases other than a node and itself
D_PAD* pad1 = (*m_PadsList)[aItem1];
D_PAD* pad2 = (*m_PadsList)[aItem2];
if( pad1 == pad2 )
return 0;
int weight = abs( pad2->GetPosition().x - pad1->GetPosition().x ) +
abs( pad2->GetPosition().y - pad1->GetPosition().y );
return weight + 1;
}
/* Note about the ratsnest computation:
* Building the general ratsnest:
* For each net, the ratsnest is the set of lines connecting pads,
* using the shorter distance
* Therefore this problem is well known in graph therory, and sloved
* using the "minimum spanning tree".
* We use here an algorithm to build the minimum spanning tree known as Prim's algorithm
*/
/**
* Function Compile_Ratsnest
* Create the entire board ratsnest.
* Must be called after a board change (changes for
* pads, footprints or a read netlist ).
* @param aDC = the current device context (can be NULL)
* @param aDisplayStatus : if true, display the computation results
*/
void PCB_BASE_FRAME::Compile_Ratsnest( wxDC* aDC, bool aDisplayStatus )
{
wxString msg;
GetBoard()->m_Status_Pcb = 0; // we want a full ratsnest computation, from the scratch
ClearMsgPanel();
// Rebuild the full pads and net info list
RecalculateAllTracksNetcode();
if( aDisplayStatus )
{
msg.Printf( wxT( " %d" ), m_Pcb->GetPadCount() );
AppendMsgPanel( wxT( "Pads" ), msg, RED );
msg.Printf( wxT( " %d" ), m_Pcb->GetNetCount() );
AppendMsgPanel( wxT( "Nets" ), msg, CYAN );
}
/* Compute the full ratsnest
* which can be see like all the possible links or logical connections.
* some of them are active (no track connected) and others are inactive
* (when tracks connect pads)
* This full ratsnest is not modified by track editing.
* It changes only when a netlist is read, or footprints are modified
*/
Build_Board_Ratsnest();
// Compute the pad connections due to the existing tracks (physical connections)
TestConnections();
/* Compute the active ratsnest, i.e. the unconnected links
*/
TestForActiveLinksInRatsnest( 0 );
// Redraw the active ratsnest ( if enabled )
if( GetBoard()->IsElementVisible(RATSNEST_VISIBLE) && aDC )
DrawGeneralRatsnest( aDC, 0 );
if( aDisplayStatus )
SetMsgPanel( m_Pcb );
}
/* Sort function used by QSORT
* Sort pads by net code
*/
static bool sortByNetcode( const D_PAD* const & ref, const D_PAD* const & item )
{
return ref->GetNetCode() < item->GetNetCode();
}
/**
* Function to compute the full ratsnest
* This is the "basic" ratsnest depending only on pads.
*
* Create the sorted pad list (if necessary)
* The active pads (i.e included in a net ) are called nodes
* This pad list is sorted by net codes
* A ratsnest can be seen as a logical connection.
*
* Update :
* nb_nodes = Active pads count for the board
* nb_links = link count for the board (logical connection count)
* (there are n-1 links in a net which counting n active pads) .
*/
void PCB_BASE_FRAME::Build_Board_Ratsnest()
{
D_PAD* pad;
int noconn;
m_Pcb->SetUnconnectedNetCount( 0 );
m_Pcb->m_FullRatsnest.clear();
if( m_Pcb->GetPadCount() == 0 )
return;
// Created pad list and the net_codes if needed
if( (m_Pcb->m_Status_Pcb & NET_CODES_OK) == 0 )
m_Pcb->BuildListOfNets();
for( unsigned ii = 0; ii<m_Pcb->GetPadCount(); ++ii )
{
pad = m_Pcb->GetPad( ii );
pad->SetSubRatsnest( 0 );
}
if( m_Pcb->GetNodesCount() == 0 )
return; // No useful connections.
// Ratsnest computation
unsigned current_net_code = 1; // First net code is analyzed.
// (net_code = 0 -> no connect)
noconn = 0;
MIN_SPAN_TREE_PADS min_spanning_tree;
for( ; current_net_code < m_Pcb->GetNetCount(); current_net_code++ )
{
NETINFO_ITEM* net = m_Pcb->FindNet( current_net_code );
if( !net ) // Should not occur
{
UTF8 msg = StrPrintf( "%s: error, net %d not found", __func__, current_net_code );
wxMessageBox( msg ); // BTW, it does happen.
return;
}
net->m_RatsnestStartIdx = m_Pcb->GetRatsnestsCount();
min_spanning_tree.MSP_Init( &net->m_PadInNetList );
min_spanning_tree.BuildTree();
min_spanning_tree.AddTreeToRatsnest( &m_Pcb->m_FullRatsnest );
net->m_RatsnestEndIdx = m_Pcb->GetRatsnestsCount();
}
m_Pcb->SetUnconnectedNetCount( noconn );
m_Pcb->m_Status_Pcb |= LISTE_RATSNEST_ITEM_OK;
// Update the ratsnest display option (visible/invisible) flag
for( unsigned ii = 0; ii < m_Pcb->GetRatsnestsCount(); ii++ )
{
if( !GetBoard()->IsElementVisible( RATSNEST_VISIBLE ) ) // Clear VISIBLE flag
m_Pcb->m_FullRatsnest[ii].m_Status &= ~CH_VISIBLE;
}
}
/**
* function DrawGeneralRatsnest
* Only ratsnest items with the status bit CH_VISIBLE set are displayed
* @param aDC = the current device context (can be NULL)
* @param aNetcode: if > 0, Display only the ratsnest relative to the
* corresponding net_code
*/
void PCB_BASE_FRAME::DrawGeneralRatsnest( wxDC* aDC, int aNetcode )
{
if( ( m_Pcb->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK ) == 0 )
return;
if( ( m_Pcb->m_Status_Pcb & DO_NOT_SHOW_GENERAL_RASTNEST ) )
return;
if( aDC == NULL )
return;
const int state = CH_VISIBLE | CH_ACTIF;
for( unsigned ii = 0; ii < m_Pcb->GetRatsnestsCount(); ii++ )
{
RATSNEST_ITEM& item = m_Pcb->m_FullRatsnest[ii];
if( ( item.m_Status & state ) != state )
continue;
if( ( aNetcode <= 0 ) || ( aNetcode == item.GetNet() ) )
{
item.Draw( m_canvas, aDC, GR_XOR, wxPoint( 0, 0 ) );
}
}
}
/**
* Function used by TestForActiveLinksInRatsnest
* Function testing the ratsnest between 2 blocks ( of the same net )
* The search is made between pads in block 1 and the others blocks
* The block n ( n > 1 ) is merged with block 1 and linked by the smallest ratsnest
* between block 1 and the block n (activate the logical connection)
* @param aRatsnestBuffer = the buffer to store NETINFO_ITEM* items
* @param aNetinfo = the current NETINFO_ITEM for the current net
* output: .state member, bit CH_ACTIF of the ratsnest item
* @return last subratsnest id in use
*/
static int tst_links_between_blocks( NETINFO_ITEM* aNetinfo,
std::vector<RATSNEST_ITEM>& aRatsnestBuffer )
{
int subratsnest_id, min_id;
RATSNEST_ITEM* link, * best_link;
// Search a link from a block to another block
best_link = NULL;
for( unsigned ii = aNetinfo->m_RatsnestStartIdx; ii < aNetinfo->m_RatsnestEndIdx; ii++ )
{
link = &aRatsnestBuffer[ii];
// If this link joints 2 pads inside the same block, do nothing
// (these pads are already connected)
if( link->m_PadStart->GetSubRatsnest() == link->m_PadEnd->GetSubRatsnest() )
continue;
// This link joints 2 pads of different blocks: this is a candidate,
// but we want to select the shorter link, so use it only if it is shorter
// than the previous candidate:
if( best_link == NULL ) // no candidate
best_link = link;
else if( best_link->m_Lenght > link->m_Lenght ) // It is a better candidate.
best_link = link;
}
if( best_link == NULL )
return 1;
/* At this point we have found a link between 2 different blocks (subratsnest)
* we must set its status to ACTIVE and merge the 2 blocks
*/
best_link->m_Status |= CH_ACTIF;
subratsnest_id = best_link->m_PadStart->GetSubRatsnest();
min_id = best_link->m_PadEnd->GetSubRatsnest();
if( min_id > subratsnest_id )
std::swap( min_id, subratsnest_id );
// Merge the 2 blocks in one sub ratsnest:
for( unsigned ii = 0; ii < aNetinfo->m_PadInNetList.size(); ii++ )
{
if( aNetinfo->m_PadInNetList[ii]->GetSubRatsnest() == subratsnest_id )
{
aNetinfo->m_PadInNetList[ii]->SetSubRatsnest( min_id );
}
}
return subratsnest_id;
}
/**
* Function used by TestForActiveLinksInRatsnest_general
* The general ratsnest list must exists because this function explores this ratsnest
* Activates (i.e. set the CH_ACTIF flag) the ratsnest links between 2 pads when
* at least one pad not already connected (SubRatsnest = 0)
* and actives the corresponding link
*
* @param aFirstItem = starting address for the ratsnest list
* @param aLastItem = ending address for the ratsnest list
* @param aCurrSubRatsnestId = last sub ratsnest id in use (computed from the track
* analysis)
*
* output:
* ratsnest list (status member bit CH_ACTIF set)
* and pads linked (m_SubRatsnest value set)
*
* @return new block number
*/
static void tst_links_between_pads( int & aCurrSubRatsnestId,
RATSNEST_ITEM* aFirstItem,
RATSNEST_ITEM* aLastItem )
{
for( RATSNEST_ITEM* item = aFirstItem; item < aLastItem; item++ )
{
D_PAD* pad_start = item->m_PadStart;
D_PAD* pad_end = item->m_PadEnd;
/* Update the current SubRatsnest if the 2 pads are not connected :
* a new cluster is created and the link activated
*/
if( (pad_start->GetSubRatsnest() == 0) && (pad_end->GetSubRatsnest() == 0) )
{
aCurrSubRatsnestId++;
pad_start->SetSubRatsnest( aCurrSubRatsnestId );
pad_end->SetSubRatsnest( aCurrSubRatsnestId );
item->m_Status |= CH_ACTIF;
}
/* If a pad is already connected to a subratsnest: activate the link
* the pad other is merged in the existing subratsnest
*/
else if( pad_start->GetSubRatsnest() == 0 )
{
pad_start->SetSubRatsnest( pad_end->GetSubRatsnest() );
item->m_Status |= CH_ACTIF;
}
else if( pad_end->GetSubRatsnest() == 0 )
{
pad_end->SetSubRatsnest( pad_start->GetSubRatsnest() );
item->m_Status |= CH_ACTIF;
}
}
}
/* function TestForActiveLinksInRatsnest
* determine the active links inside the full ratsnest
*
* I used an algorithm inspired by the "Lee algorithm".
* The idea is all pads must be connected by a physical track or a logical track
* a physical track is the existing track on copper layers.
* a logical track is the link that must be activated (visible) if
* no track found between 2 pads.
* The algorithm explore the existing full ratnest
* This is a 2 steps algorithm (executed for each net).
* - First:
* Initialise for each pad the subratsnest id to its subnet value
* explore the full ratnest (relative to the net) and active a link each time at least one pad of
* the given link is not connected to another pad by a track ( subratsnest = 0)
* If the 2 pads linked have both the subratsnest id = 0, a new subratsnest value is created
* - Second:
* explore the full ratnest (relative to the net) and find a link that links
* 2 pads having different subratsnest values
* Active the link and merge the 2 subratsnest value.
*
* This is usually fast because the ratsnest is not built here: it is just explored
* to see what link must be activated
*/
void PCB_BASE_FRAME::TestForActiveLinksInRatsnest( int aNetCode )
{
RATSNEST_ITEM* rats;
D_PAD* pad;
NETINFO_ITEM* net;
if( m_Pcb->GetPadCount() == 0 )
return;
if( (m_Pcb->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK) == 0 )
Build_Board_Ratsnest();
for( int net_code = 1; net_code < (int) m_Pcb->GetNetCount(); net_code++ )
{
net = m_Pcb->FindNet( net_code );
wxCHECK_RET( net != NULL,
wxString::Format( wxT( "Net code %d not found!" ), net_code ) );
if( aNetCode && (net_code != aNetCode) )
continue;
// Create subratsnests id from subnets created by existing tracks:
int subratsnest = 0;
for( unsigned ip = 0; ip < net->m_PadInNetList.size(); ip++ )
{
pad = net->m_PadInNetList[ip];
int subnet = pad->GetSubNet();
pad->SetSubRatsnest( subnet );
subratsnest = std::max( subratsnest, subnet );
}
for( unsigned ii = net->m_RatsnestStartIdx; ii < net->m_RatsnestEndIdx; ii++ )
{
m_Pcb->m_FullRatsnest[ii].m_Status &= ~CH_ACTIF;
}
// First pass - activate links for not connected pads
rats = &m_Pcb->m_FullRatsnest[0];
tst_links_between_pads( subratsnest,
rats + net->m_RatsnestStartIdx,
rats + net->m_RatsnestEndIdx );
// Second pass activate links between blocks (Iteration)
while( subratsnest > 1 )
{
subratsnest = tst_links_between_blocks( net, m_Pcb->m_FullRatsnest );
}
}
m_Pcb->SetUnconnectedNetCount( 0 );
unsigned cnt = 0;
for( unsigned ii = 0; ii < m_Pcb->GetRatsnestsCount(); ii++ )
{
if( m_Pcb->m_FullRatsnest[ii].IsActive() )
cnt++;
}
m_Pcb->SetUnconnectedNetCount( cnt );
}
void PCB_BASE_FRAME::build_ratsnest_module( MODULE* aModule )
{
// for local ratsnest calculation when moving a footprint:
// list of pads to use for this local ratsnets:
// this is the list of connected pads of the current module,
// and all pads connected to these pads:
static std::vector <D_PAD*> localPadList;
static unsigned pads_module_count; // node count (node = pad with a net
// code) for the footprint being moved
static unsigned internalRatsCount; // number of internal links (links
// between pads of the module)
D_PAD* pad_ref;
D_PAD* pad_externe;
int current_net_code;
int distance;
wxPoint pad_pos; // True pad position according to the
// current footprint position
if( (GetBoard()->m_Status_Pcb & LISTE_PAD_OK) == 0 )
{
GetBoard()->m_Status_Pcb = 0;
GetBoard()->BuildListOfNets();
}
/* Compute the "local" ratsnest if needed (when this footprint starts move)
* and the list of external pads to consider, i.e pads in others
* footprints which are "connected" to
* a pad in the current footprint
*/
if( (m_Pcb->m_Status_Pcb & RATSNEST_ITEM_LOCAL_OK) == 0 )
{
// Compute the "internal" ratsnest, i.e the links between the current
// footprint pads
localPadList.clear();
m_Pcb->m_LocalRatsnest.clear();
// collect active pads of the module:
for( pad_ref = aModule->Pads(); pad_ref; pad_ref = pad_ref->Next() )
{
if( pad_ref->GetNetCode() == NETINFO_LIST::UNCONNECTED )
continue;
localPadList.push_back( pad_ref );
pad_ref->SetSubRatsnest( 0 );
pad_ref->SetSubNet( 0 );
}
pads_module_count = localPadList.size();
if( pads_module_count == 0 )
return; // no connection!
sort( localPadList.begin(), localPadList.end(), sortByNetcode );
// Build the list of pads linked to the current footprint pads
current_net_code = 0;
for( unsigned ii = 0; ii < pads_module_count; ii++ )
{
pad_ref = localPadList[ii];
if( pad_ref->GetNetCode() == current_net_code )
continue;
// A new net was found, load all pads of others modules members of this net:
NETINFO_ITEM* net = pad_ref->GetNet();
if( net == NULL ) //Should not occur
{
wxMessageBox( wxT( "build_ratsnest_module() error: net not found" ) );
return;
}
for( unsigned jj = 0; jj < net->m_PadInNetList.size(); jj++ )
{
pad_externe = net->m_PadInNetList[jj];
if( pad_externe->GetParent() == aModule )
continue;
pad_externe->SetSubRatsnest( 0 );
pad_externe->SetSubNet( 0 );
localPadList.push_back( pad_externe );
}
}
// Sort the pad list by net_code
sort( localPadList.begin() + pads_module_count, localPadList.end(),
sortByNetcode );
/* Compute the internal rats nest:
* this is the same as general ratsnest, but considers only the current
* footprint pads it is therefore not time consuming, and it is made only
* once
*/
current_net_code = localPadList[0]->GetNetCode();
MIN_SPAN_TREE_PADS min_spanning_tree;
std::vector<D_PAD*> padsBuffer; // contains pads of only one net
for( unsigned ii = 0; ii < pads_module_count; ii++ )
{
// Search the end of pad list relative to the current net
unsigned jj = ii + 1;
for( ; jj <= pads_module_count; jj++ )
{
if( jj >= pads_module_count )
break;
if( localPadList[jj]->GetNetCode() != current_net_code )
break;
}
for( unsigned kk = ii; kk < jj; kk++ )
padsBuffer.push_back( localPadList[kk] );
min_spanning_tree.MSP_Init( &padsBuffer );
min_spanning_tree.BuildTree();
min_spanning_tree.AddTreeToRatsnest( &m_Pcb->m_LocalRatsnest );
padsBuffer.clear();
ii = jj;
if( ii < localPadList.size() )
current_net_code = localPadList[ii]->GetNetCode();
}
internalRatsCount = m_Pcb->m_LocalRatsnest.size();
// set the flag LOCAL_RATSNEST_ITEM of the ratsnest status:
for( unsigned ii = 0; ii < m_Pcb->m_LocalRatsnest.size(); ii++ )
m_Pcb->m_LocalRatsnest[ii].m_Status = LOCAL_RATSNEST_ITEM;
m_Pcb->m_Status_Pcb |= RATSNEST_ITEM_LOCAL_OK;
} // End of internal ratsnest build
/* This section computes the "external" ratsnest: it is done when the
* footprint position changes
*
* This section search:
* for each current module pad the nearest neighbor external pad (of
* course for the same net code).
* For each current footprint cluster of pad (pads having the same net
* code),
* we search the smaller rats nest.
* so, for each net, only one rats nest item is created
*/
RATSNEST_ITEM local_rats;
local_rats.m_Lenght = INT_MAX;
local_rats.m_Status = 0;
bool addRats = false;
// Erase external ratsnest items:
if( internalRatsCount < m_Pcb->m_LocalRatsnest.size() )
m_Pcb->m_LocalRatsnest.erase( m_Pcb->m_LocalRatsnest.begin() + internalRatsCount,
m_Pcb->m_LocalRatsnest.end() );
current_net_code = localPadList[0]->GetNetCode();
for( unsigned ii = 0; ii < pads_module_count; ii++ )
{
pad_ref = localPadList[ii];
if( pad_ref->GetNetCode() != current_net_code )
{
// if needed, creates a new ratsnest for the old net
if( addRats )
{
m_Pcb->m_LocalRatsnest.push_back( local_rats );
}
addRats = false;
current_net_code = pad_ref->GetNetCode();
local_rats.m_Lenght = INT_MAX;
}
pad_pos = pad_ref->GetPosition() - g_Offset_Module;
// Search the nearest external pad of this current pad
for( unsigned jj = pads_module_count; jj < localPadList.size(); jj++ )
{
pad_externe = localPadList[jj];
// we search pads having the same net code
if( pad_externe->GetNetCode() < pad_ref->GetNetCode() )
continue;
if( pad_externe->GetNetCode() > pad_ref->GetNetCode() ) // pads are sorted by net code
break;
distance = abs( pad_externe->GetPosition().x - pad_pos.x ) +
abs( pad_externe->GetPosition().y - pad_pos.y );
if( distance < local_rats.m_Lenght )
{
local_rats.m_PadStart = pad_ref;
local_rats.m_PadEnd = pad_externe;
local_rats.SetNet( pad_ref->GetNetCode() );
local_rats.m_Lenght = distance;
local_rats.m_Status = 0;
addRats = true;
}
}
}
if( addRats ) // Ensure the last created rats nest item is stored in buffer
m_Pcb->m_LocalRatsnest.push_back( local_rats );
}
void PCB_BASE_FRAME::TraceModuleRatsNest( wxDC* DC )
{
if( DC == NULL )
return;
if( ( m_Pcb->m_Status_Pcb & RATSNEST_ITEM_LOCAL_OK ) == 0 )
return;
EDA_COLOR_T tmpcolor = g_ColorsSettings.GetItemColor(RATSNEST_VISIBLE);
for( unsigned ii = 0; ii < m_Pcb->m_LocalRatsnest.size(); ii++ )
{
RATSNEST_ITEM* rats = &m_Pcb->m_LocalRatsnest[ii];
if( rats->m_Status & LOCAL_RATSNEST_ITEM )
{
g_ColorsSettings.SetItemColor(RATSNEST_VISIBLE, YELLOW);
rats->Draw( m_canvas, DC, GR_XOR, g_Offset_Module );
}
else
{
g_ColorsSettings.SetItemColor(RATSNEST_VISIBLE, tmpcolor);
wxPoint tmp = rats->m_PadStart->GetPosition();
rats->m_PadStart->SetPosition( tmp - g_Offset_Module );
rats->Draw( m_canvas, DC, GR_XOR, wxPoint( 0, 0 ) );
rats->m_PadStart->SetPosition( tmp );
}
}
g_ColorsSettings.SetItemColor( RATSNEST_VISIBLE, tmpcolor );
}
/*
* PCB_BASE_FRAME::BuildAirWiresTargetsList and
* PCB_BASE_FRAME::TraceAirWiresToTargets
* are 2 function to show the near connecting points when
* a new track is created, by displaying g_MaxLinksShowed airwires
* between the on grid mouse cursor and these connecting points
* during the creation of a track
*/
/* Buffer to store pads coordinates when creating a track.
* these pads are members of the net
* and when the mouse is moved, the g_MaxLinksShowed links to neighbors are
* drawn
*/
static std::vector <wxPoint> s_TargetsLocations;
static wxPoint s_CursorPos; // Coordinate of the moving point (mouse cursor and
// end of current track segment)
/* Used by BuildAirWiresTargetsList(): sort function by link length
* (rectilinear distance between s_CursorPos and item pos)
*/
static bool sort_by_distance( const wxPoint& ref, const wxPoint& compare )
{
wxPoint deltaref = ref - s_CursorPos; // relative coordinate of ref
wxPoint deltacmp = compare - s_CursorPos; // relative coordinate of compare
// rectilinear distance between ref and s_CursorPos:
int lengthref = abs( deltaref.x ) + abs( deltaref.y );
// rectilinear distance between compare and s_CursorPos:
int lengthcmp = abs( deltacmp.x ) + abs( deltacmp.y );
return lengthref < lengthcmp;
}
static bool sort_by_point( const wxPoint& ref, const wxPoint& compare )
{
if( ref.x == compare.x )
return ref.y < compare.y;
return ref.x < compare.x;
}
/* Function BuildAirWiresTargetsList
* Build a list of candidates that can be a coonection point
* when a track is started.
* This functions prepares data to show airwires to nearest connecting points (pads)
* from the current new track to candidates during track creation
*/
void PCB_BASE_FRAME::BuildAirWiresTargetsList( BOARD_CONNECTED_ITEM* aItemRef,
const wxPoint& aPosition, bool aInit )
{
if( ( ( m_Pcb->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK ) == 0 )
|| ( ( m_Pcb->m_Status_Pcb & LISTE_PAD_OK ) == 0 )
|| ( ( m_Pcb->m_Status_Pcb & NET_CODES_OK ) == 0 ) )
{
s_TargetsLocations.clear();
return;
}
s_CursorPos = aPosition; // needed for sort_by_distance
if( aInit )
{
s_TargetsLocations.clear();
if( aItemRef == NULL )
return;
int net_code = aItemRef->GetNetCode();
int subnet = aItemRef->GetSubNet();
if( net_code <= 0 )
return;
NETINFO_ITEM* net = m_Pcb->FindNet( net_code );
if( net == NULL ) // Should not occur
{
wxMessageBox( wxT( "BuildAirWiresTargetsList() error: net not found" ) );
return;
}
// Create a list of pads candidates ( pads not already connected to the
// current track ):
for( unsigned ii = 0; ii < net->m_PadInNetList.size(); ii++ )
{
D_PAD* pad = net->m_PadInNetList[ii];
if( pad == aItemRef )
continue;
if( !pad->GetSubNet() || (pad->GetSubNet() != subnet) )
s_TargetsLocations.push_back( pad->GetPosition() );
}
// Create a list of tracks ends candidates, not already connected to the
// current track:
for( TRACK* track = m_Pcb->m_Track; track; track = track->Next() )
{
if( track->GetNetCode() < net_code )
continue;
if( track->GetNetCode() > net_code )
break;
if( !track->GetSubNet() || (track->GetSubNet() != subnet) )
{
if( aPosition != track->GetStart() )
s_TargetsLocations.push_back( track->GetStart() );
if( aPosition != track->GetEnd() && track->GetStart() != track->GetEnd() )
s_TargetsLocations.push_back( track->GetEnd() );
}
}
// Remove duplicate targets, using the C++ unique algorithm
sort( s_TargetsLocations.begin(), s_TargetsLocations.end(), sort_by_point );
std::vector< wxPoint >::iterator it = unique( s_TargetsLocations.begin(), s_TargetsLocations.end() );
// Using the C++ unique algorithm only moves the duplicate entries to the end of
// of the array. This removes the duplicate entries from the array.
s_TargetsLocations.resize( it - s_TargetsLocations.begin() );
} // end if Init
// in all cases, sort by distances:
sort( s_TargetsLocations.begin(), s_TargetsLocations.end(), sort_by_distance );
}
void PCB_BASE_FRAME::TraceAirWiresToTargets( wxDC* aDC )
{
if( aDC == NULL )
return;
if( s_TargetsLocations.size() == 0 )
return;
GRSetDrawMode( aDC, GR_XOR );
DISPLAY_OPTIONS* displ_opts = (DISPLAY_OPTIONS*)GetDisplayOptions();
for( int ii = 0; ii < (int) s_TargetsLocations.size(); ii++ )
{
if( ii >= displ_opts->m_MaxLinksShowed )
break;
GRLine( m_canvas->GetClipBox(), aDC, s_CursorPos, s_TargetsLocations[ii], 0, YELLOW );
}
}
|