docs/wiki/pcb-connection_lookup.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   2  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   3 <html>
   4 <head>
   5   <link rel="stylesheet" media="screen" type="text/css" href="./style.css" />
   6   <link rel="stylesheet" media="screen" type="text/css" href="./design.css" />
   7   <link rel="stylesheet" media="print" type="text/css" href="./print.css" />
   8
   9   <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  10 </head>
  11 <body>
  12
  13 <h2 class="sectionedit1" id="connection_lookup">Connection Lookup</h2>
  14 <div class="level2">
  15
  16 <p>
  17 The connection lookup algorithm starts at an object and looks for any objects that touch the starting object or any object touching the starting object. This code is implemented in find.c and used throughout the code base for a variety of purposes.
  18 </p>
  19
  20 <p>
  21 The connection lookup process starts at an object (pins/pads only?) and searches for intersecting objects. For each object it finds, it sets a specified flag. (todo: eventually this should build a list of objects instead). These flags are used in a convoluted way to identify things that have already been found, and if the algorithm should continue looking for more objects.
  22 </p>
  23
  24 <p>
  25 One of the tricks that the algorithm uses to restore the state of the flags in some cases is to use ClearFlagOnAllObjects to wipe out a flag (an undoable operation), then do everything without adding operations to the Undo stack, run ClearFlagsOnAllObjects a second time (without undo), and then Undo the first one. I guess the point of this is to prevent the undo system from sucking up resources during these operations? This has led to a global variable “User” which has the effect of causing flag change operations to be added to the undo list. I think this is absolutely horrid. This variable needs to die. I think a better way of accomplishing this goal is by locking the undo system.
  26 </p>
  27
  28 <p>
  29 In a number of places, the “andRats” parameter is used. This indicates that rat lines should be considered when looking for overlaps. This way, you can highlight an entire net, even if all the pieces aren&#039;t connected with copper. It&#039;s important to preserve this functionality.
  30 </p>
  31
  32 <p>
  33 Objects are broken into two categories, “layer objects” (LO) and pins and vias (PV). The tests then get split into four categories, PV to PV, LO to PV, LO to LO, and PV to LO.
  34 </p>
  35
  36 </div>
  37 <!-- EDIT1 SECTION "Connection Lookup" [1-1803] -->
  38 <h2 class="sectionedit2" id="detailed_algorithm">Detailed Algorithm</h2>
  39 <div class="level2">
  40 <ol>
  41 <li class="level1"><div class="li"> Initialize the lists</div>
  42 </li>
  43 <li class="level1"><div class="li"> Add seed object</div>
  44 </li>
  45 <li class="level1"><div class="li"> Initialize global variables</div>
  46 </li>
  47 <li class="level1 node"><div class="li"> Search lists for new connections</div>
  48 <ol>
  49 <li class="level2 node"><div class="li"> Check the PV list for new PV connections (LookupPVConnectionsToPVList)</div>
  50 <ol>
  51 <li class="level3"><div class="li"> rsearch the pin tree calling pv_pv_callback</div>
  52 </li>
  53 <li class="level3 node"><div class="li"> rsearch the via tree calling pv_pv_callback</div>
  54 <ol>
  55 <li class="level4"><div class="li"> check that the pvs are on intersecting layers</div>
  56 </li>
  57 <li class="level4"><div class="li"> check that it&#039;s not already in the list</div>
  58 </li>
  59 <li class="level4"><div class="li"> check that they touch</div>
  60 </li>
  61 <li class="level4"><div class="li"> check that neither is just a hole</div>
  62 </li>
  63 <li class="level4"><div class="li"> add the new pv to the list</div>
  64 </li>
  65 </ol>
  66 </li>
  67 </ol>
  68 </li>
  69 <li class="level2 node"><div class="li"> Check the PV list for new LO connections</div>
  70 <ol>
  71 <li class="level3"><div class="li"> rsearch the pad tree calling LOCtoPVpad_callback</div>
  72 </li>
  73 <li class="level3 node"><div class="li"> For each copper layer</div>
  74 <ol>
  75 <li class="level4"><div class="li"> rsearch the line tree calling LOCtoPVline_callback</div>
  76 </li>
  77 <li class="level4"><div class="li"> rsearch the arc tree calling LOCtoPVarc_callback</div>
  78 </li>
  79 <li class="level4"><div class="li"> rsearch the polygon tree calling LOCtoPVpoly_callback</div>
  80 </li>
  81 </ol>
  82 </li>
  83 </ol>
  84 </li>
  85 </ol>
  86 </li>
  87 </ol>
  88 <ol>
  89 <li class="level1 node"><div class="li"> InitConnectionLookup()</div>
  90 <ol>
  91 <li class="level2 node"><div class="li"> InitComponentLookup()</div>
  92 <ol>
  93 <li class="level3"><div class="li"> Compute the number of pads on each side of the pcb</div>
  94 </li>
  95 <li class="level3"><div class="li"> Allocate enough memory for the PadLists to hold pointers to all of them, and initialize the list structures.</div>
  96 </li>
  97 </ol>
  98 </li>
  99 <li class="level2 node"><div class="li"> InitLayoutLookup()</div>
 100 <ol>
 101 <li class="level3"><div class="li"> For each copper layer, allocate enough memory for each list (lines, arcs, polygons) to hold pointers to all of the objects on the layer, and initialize the list structures.</div>
 102 </li>
 103 <li class="level3"><div class="li"> Allocate enough memory for the pin and via combined list, and initialize it.</div>
 104 </li>
 105 <li class="level3"><div class="li"> Allocate enough memory for the rats list to hold all of the rats.</div>
 106 </li>
 107 </ol>
 108 </li>
 109 </ol>
 110 </li>
 111 <li class="level1 node"><div class="li"> ListStart(type, ptr1, ptr2, ptr3)</div>
 112 <ol>
 113 <li class="level2"><div class="li"> Add the seed object to the lists.</div>
 114 </li>
 115 </ol>
 116 </li>
 117 <li class="level1 node"><div class="li"> DoIt(flag, bloat, AndRats, AndDraw, is_drc)</div>
 118 <ol>
 119 <li class="level2"><div class="li"> Set the global drc flag and bloat value</div>
 120 </li>
 121 <li class="level2"><div class="li"> Update layer “no_drc” flags</div>
 122 </li>
 123 <li class="level2 node"><div class="li"> Lookup connection loop:</div>
 124 <ol>
 125 <li class="level3"><div class="li"> Note that if any of the four lookup functions returns true, it will likely short-circuit the rest of the tests.</div>
 126 </li>
 127 <li class="level3 node"><div class="li"> LookupPVConnectionsToPVList(flag)</div>
 128 <ol>
 129 <li class="level4"><div class="li"> Save our current position in the PV list</div>
 130 </li>
 131 <li class="level4 node"><div class="li"> If our current position is not the last item in the list:</div>
 132 <ol>
 133 <li class="level5"><div class="li"> Get the current list item</div>
 134 </li>
 135 <li class="level5"><div class="li"> Expand the bounding box by the global bloat for the search</div>
 136 </li>
 137 <li class="level5 node"><div class="li"> Set a jump point, and do an r_search on the via tree around the current PV (pv_pv_callback)</div>
 138 <ol>
 139 <li class="level6"><div class="li"> If the vias are buried and the layers don&#039;t intersect, return and continue the search.</div>
 140 </li>
 141 <li class="level6 node"><div class="li"> If the new PV hasn&#039;t been marked yet, and the new one overlaps with the current one,</div>
 142 <ol>
 143 <li class="level7"><div class="li"> If it&#039;s just a hole (no copper annulus), throw a warning and continue the search</div>
 144 </li>
 145 <li class="level7 node"><div class="li"> Otherwise, add the new PV to the list (add_object_to_list)</div>
 146 <ol>
 147 <li class="level8"><div class="li"> If this is a DRC and the selected flag wasn&#039;t set, long jump back to LookupPVConnectionsToPVList</div>
 148 </li>
 149 <li class="level8"><div class="li"> Otherwise, continue the search</div>
 150 </li>
 151 </ol>
 152 </li>
 153 </ol>
 154 </li>
 155 </ol>
 156 </li>
 157 <li class="level5"><div class="li"> If we returned via a long jump, return true (found something/want to stop lookup up objects)</div>
 158 </li>
 159 <li class="level5"><div class="li"> Otherwise check the pin tree (repeat via tree steps)</div>
 160 </li>
 161 <li class="level5"><div class="li"> If we returned via a long jump, return true (found something/want to stop lookup up objects)</div>
 162 </li>
 163 <li class="level5"><div class="li"> Otherwise, keep looking through the PV list until we get to the end.</div>
 164 </li>
 165 </ol>
 166 </li>
 167 <li class="level4"><div class="li"> Restore the list position (why? Probably so that LookupLOConnectionsToPVList can iterate over the same group of objects)</div>
 168 </li>
 169 <li class="level4"><div class="li"> Return false (no new objects/we want to keep looking up objects)</div>
 170 </li>
 171 </ol>
 172 </li>
 173 <li class="level3 node"><div class="li"> LookupLOConnectionsToPVList(flag, AndRats)</div>
 174 <ol>
 175 <li class="level4 node"><div class="li"> If our current position is not the last item in the list:</div>
 176 <ol>
 177 <li class="level5"><div class="li"> Get the current list item</div>
 178 </li>
 179 <li class="level5"><div class="li"> Expand the bounding box by the global bloat for the search</div>
 180 </li>
 181 <li class="level5 node"><div class="li"> Set a jump point, and do an r_search on the pad tree around the current PV (LOCtoPVpad_callback)</div>
 182 <ol>
 183 <li class="level6"><div class="li"> If the PV doesn&#039;t intersect the pad layer (top or bottom), return false (keep looking for objects)</div>
 184 </li>
 185 <li class="level6"><div class="li"> If we haven&#039;t already flagged the pad, the PV and pad intersect, and the PV isn&#039;t just a hole, add the pad to the list, and longjmp back to LookupLOConnectionToPVList</div>
 186 </li>
 187 <li class="level6"><div class="li"> Otherwise, return 0 (keep looking for objects)</div>
 188 </li>
 189 </ol>
 190 </li>
 191 <li class="level5 node"><div class="li"> For each layer:</div>
 192 <ol>
 193 <li class="level6"><div class="li"> if the no_drc flag is set, skip this layer</div>
 194 </li>
 195 <li class="level6 node"><div class="li"> Set a jump point, and do an r_search on the layer&#039;s line tree around the via (LOCtoPVline_callback)</div>
 196 <ol>
 197 <li class="level7"><div class="li"> Repeat the pad procedure here</div>
 198 </li>
 199 </ol>
 200 </li>
 201 <li class="level6"><div class="li"> If we returned via long jump, return true (abort search)</div>
 202 </li>
 203 <li class="level6 node"><div class="li"> Otherwise, set a jump point and do an r_search on the layer&#039;s arc tree around the via (LOCtoPVarc_callback)</div>
 204 <ol>
 205 <li class="level7"><div class="li"> Repeat the pad procedure here</div>
 206 </li>
 207 </ol>
 208 </li>
 209 <li class="level6"><div class="li"> If we returned via long jump, return true (abort search)</div>
 210 </li>
 211 <li class="level6 node"><div class="li"> Otherwise, set a jump point and do an r_search on the layer&#039;s polygon tree around the via (LOCtoPVpoly_callback)</div>
 212 <ol>
 213 <li class="level7"><div class="li"> If the PV doesn&#039;t intersect the polygon layer, return 0 (continue search)</div>
 214 </li>
 215 <li class="level7 node"><div class="li"> If we haven&#039;t yet flagged the polygon and the PV isn&#039;t just a hole…</div>
 216 <ol>
 217 <li class="level8"><div class="li"> If there&#039;s no thermal and the polygon is clearing, return 0 (continue search)</div>
 218 </li>
 219 <li class="level8 node"><div class="li"> Otherwise…</div>
 220 <ol>
 221 <li class="level9"><div class="li"> compute the width of the search box</div>
 222 </li>
 223 <li class="level9 node"><div class="li"> if the pv has the square flag set,</div>
 224 <ol>
 225 <li class="level10"><div class="li"> compute the corner points</div>
 226 </li>
 227 <li class="level10"><div class="li"> if the rectangle is in the polygon (IsRectangleInPolygon) add it to the list (… ends up in add_object_to_list)</div>
 228 </li>
 229 <li class="level10"><div class="li"> if we&#039;re doing the drc and the object didn&#039;t have the selected flag set, long jump back to to LookupLOConnectionToPVList</div>
 230 </li>
 231 <li class="level10"><div class="li"> otherwise return 0 (continue search)</div>
 232 </li>
 233 </ol>
 234 </li>
 235 <li class="level9 node"><div class="li"> otherwise, if the pv has the octagon flag set…</div>
 236 <ol>
 237 <li class="level10"><div class="li"> create a dummy octagon polygon</div>
 238 </li>
 239 <li class="level10"><div class="li"> if the dummy octagon and the polygon intersect (isects), add it to the list</div>
 240 </li>
 241 <li class="level10"><div class="li"> if we&#039;re doing the drc and the object didn&#039;t have the selected flag set, long jump back to to LookupLOConnectionToPVList</div>
 242 </li>
 243 </ol>
 244 </li>
 245 <li class="level9 node"><div class="li"> otherwise, pv is round, and if intersects the polygon (IsPointInPolygon)</div>
 246 <ol>
 247 <li class="level10"><div class="li"> add it to the list</div>
 248 </li>
 249 <li class="level10"><div class="li"> if we&#039;re doing the drc and the object didn&#039;t have the selected flag set, long jump back to LookupLOConnectionToPVList</div>
 250 </li>
 251 </ol>
 252 </li>
 253 </ol>
 254 </li>
 255 </ol>
 256 </li>
 257 <li class="level7"><div class="li"> return 0 (continue search)</div>
 258 </li>
 259 </ol>
 260 </li>
 261 <li class="level6"><div class="li"> Move on to the next layer</div>
 262 </li>
 263 </ol>
 264 </li>
 265 <li class="level5 node"><div class="li"> If we&#039;re following rats, set a jump point and do an r_search on the rat tree (LOCtoPVrat_callback)</div>
 266 <ol>
 267 <li class="level6"><div class="li"> If we haven&#039;t already found the rat, add it to the list, and long jump back to LookupLOConnectionToPVList</div>
 268 </li>
 269 </ol>
 270 </li>
 271 <li class="level5"><div class="li"> Increment the position in the list and check the next PV</div>
 272 </li>
 273 </ol>
 274 </li>
 275 <li class="level4"><div class="li"> Return false (continue search)</div>
 276 </li>
 277 </ol>
 278 </li>
 279 <li class="level3"><div class="li"> LookupLOConnectionsToLOList(flag, AndRats)</div>
 280 </li>
 281 </ol>
 282 </li>
 283 </ol>
 284 </li>
 285 </ol>
 286
 287 </div>
 288 <!-- EDIT2 SECTION "Detailed Algorithm" [1804-8382] -->
 289 <h3 class="sectionedit3" id="uses_of_the_connection_lookup_algorithm">Uses of the Connection Lookup Algorithm</h3>
 290 <div class="level3">
 291
 292 </div>
 293
 294 <h4 id="drc">DRC</h4>
 295 <div class="level4">
 296
 297 <p>
 298 The DRC uses the connection lookup code in combination with the “Bloat” and “Shrink” settings to detect places with insufficient spacing and overlap.
 299 </p>
 300
 301 </div>
 302
 303 <h4 id="notifyline">NotifyLine</h4>
 304 <div class="level4">
 305
 306 <p>
 307 action.c
 308 </p>
 309
 310 </div>
 311
 312 <h4 id="notifymode">NotifyMode</h4>
 313 <div class="level4">
 314
 315 <p>
 316 action.c
 317 </p>
 318
 319 </div>
 320
 321 <h4 id="actionconnection">ActionConnection</h4>
 322 <div class="level4">
 323
 324 <p>
 325 action.c
 326 </p>
 327
 328 </div>
 329
 330 <h4 id="actiondisplay">ActionDisplay</h4>
 331 <div class="level4">
 332
 333 <p>
 334 action.c
 335 </p>
 336
 337 </div>
 338
 339 <h4 id="actionsaveto">ActionSaveTo</h4>
 340 <div class="level4">
 341
 342 <p>
 343 action.c
 344 </p>
 345
 346 </div>
 347
 348 <h4 id="ipcd_hid">IPCD HID</h4>
 349 <div class="level4">
 350
 351 </div>
 352
 353 <h4 id="gtk_hid">GTK HID</h4>
 354 <div class="level4">
 355
 356 <p>
 357 netlist window
 358 </p>
 359
 360 </div>
 361
 362 <h4 id="netlistc">netlist.c</h4>
 363 <div class="level4">
 364
 365 </div>
 366
 367 <h4 id="reportc">report.c</h4>
 368 <div class="level4">
 369
 370 </div>
 371
 372 <h4 id="places_that_call_doit">Places that call DoIt</h4>
 373 <div class="level4">
 374
 375 </div>
 376
 377 <h5 id="notes_from_20180810">Notes from 20180810</h5>
 378 <div class="level5">
 379
 380 <p>
 381 Saves list of unused pins and pads:
 382 ActionSaveTo:action.c:5752
 383 LookupUnusedPins:find.c:2464
 384 PrintAndSelectUnusedPinsAndPadsOfElement:find.c:1982
 385 DoIt:find.c:2000, 2044
 386 </p>
 387
 388 <p>
 389 Saves list of element connections
 390 ActionSaveTo:action.c:5752
 391 LookupElementConnections:find.c:2255
 392 PrintElementConnections:find.c:2120
 393 DoIt:find.c:2136, 2161
 394 </p>
 395
 396 <p>
 397 There are quite a few of these.
 398 (action.c: 905, 906, 1366, 2314, 2315, 2789, 2792) LookupConnection:find.c:2376
 399 (netlist.c: 171, 180) LookupConnection:find.c:2376
 400 (report.c: 598) LookupConnection:find.c:2376
 401 DoIt:find.c:2417
 402 </p>
 403
 404 <p>
 405 (ipcd356.c: 493, 514, 538) LookupConnectionByPin:find.c:2431
 406 DoIt:find.c:2439
 407 </p>
 408
 409 <p>
 410 (gsvit.c:433) RatFindHook:find.c:2450
 411 (lesstif/netlist.c:140) RatFindHook:find.c:2450
 412 (gtk/gui-netlist-window.c:543) RatFindHook:find.c:2450
 413 (rats.c:474) RatFindHook:find.c:2450
 414 (select.c:996) RatFindHook:find.c:2450
 415 DoIt:find.c:2456
 416 </p>
 417
 418 <p>
 419 start_do_it_and_dump:find.c:2681
 420 DoIt:find.c:2689
 421 </p>
 422
 423 </div>
 424 <!-- EDIT3 SECTION "Uses of the Connection Lookup Algorithm" [8383-] --></body>
 425 </html>