src/toporouter.h

   1 /*!
   2  * \file src/toporouter.h
   3  *
   4  * \brief Topological Autorouter for PCB.
   5  *
   6  * <hr>
   7  *
   8  * <h1><b>Copyright.</b></h1>\n
   9  *
  10  * Topological Autorouter for
  11  * PCB, interactive printed circuit board design
  12  *
  13  * Copyright (C) 2009 Anthony Blake
  14  *
  15  * Copyright (C) 2009-2011 PCB Contributors (see ChangeLog for details)
  16  *
  17  * This program is free software; you can redistribute it and/or modify
  18  * it under the terms of the GNU General Public License as published by
  19  * the Free Software Foundation; either version 2 of the License, or
  20  * (at your option) any later version.
  21  *
  22  * This program is distributed in the hope that it will be useful,
  23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  25  * GNU General Public License for more details.
  26  *
  27  * You should have received a copy of the GNU General Public License
  28  * along with this program; if not, write to the Free Software
  29  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  30  *
  31  * Contact addresses for email:
  32  * Anthony Blake, tonyb33@gmail.com
  33  */
  34
  35 #ifndef PCB_TOPOROUTER_H
  36 #define PCB_TOPOROUTER_H
  37
  38 #include <assert.h>
  39 #include "data.h"
  40 #include "macro.h"
  41 #include "autoroute.h"
  42 #include "box.h"
  43 #include "create.h"
  44 #include "draw.h"
  45 #include "error.h"
  46 #include "find.h"
  47 #include "heap.h"
  48 #include "rtree.h"
  49 #include "misc.h"
  50 #include "mymem.h"
  51 #include "polygon.h"
  52 #include "rats.h"
  53 #include "remove.h"
  54 #include "thermal.h"
  55 #include "undo.h"
  56 #include "global.h"
  57
  58 #include "gts.h"
  59
  60 #include <stdlib.h>
  61 #include <getopt.h>
  62
  63 #include <sys/time.h>
  64
  65 #define TOPOROUTER_FLAG_VERBOSE       (1<<0)
  66 #define TOPOROUTER_FLAG_HARDDEST      (1<<1)
  67 #define TOPOROUTER_FLAG_HARDSRC       (1<<2)
  68 #define TOPOROUTER_FLAG_MATCH         (1<<3)
  69 #define TOPOROUTER_FLAG_LAYERHINT     (1<<4)
  70 #define TOPOROUTER_FLAG_LEASTINVALID  (1<<5)
  71 #define TOPOROUTER_FLAG_AFTERORDER    (1<<6)
  72 #define TOPOROUTER_FLAG_AFTERRUBIX    (1<<7)
  73 #define TOPOROUTER_FLAG_GOFAR         (1<<8)
  74 #define TOPOROUTER_FLAG_DETOUR        (1<<9)
  75
  76 #if TOPO_OUTPUT_ENABLED
  77   #include <cairo.h>
  78 #endif
  79
  80 #define EPSILON 0.0001f
  81
  82 //#define DEBUG_ROAR 1
  83
  84 #define tvdistance(a,b) hypot(vx(a)-vx(b),vy(a)-vy(b))
  85
  86 #define edge_v1(e) (GTS_SEGMENT(e)->v1)
  87 #define edge_v2(e) (GTS_SEGMENT(e)->v2)
  88 #define tedge_v1(e) (TOPOROUTER_VERTEX(GTS_SEGMENT(e)->v1))
  89 #define tedge_v2(e) (TOPOROUTER_VERTEX(GTS_SEGMENT(e)->v2))
  90
  91 #define tedge(v1,v2) TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v1), GTS_VERTEX(v2)))
  92
  93 #define edge_routing(e) (TOPOROUTER_IS_CONSTRAINT(e) ? TOPOROUTER_CONSTRAINT(e)->routing : e->routing)
  94 #define vrouting(v) (edge_routing(v->routingedge))
  95
  96 #define edge_routing_next(e,list) ((list->next) ? TOPOROUTER_VERTEX(list->next->data) : TOPOROUTER_VERTEX(edge_v2(e)))
  97 #define edge_routing_prev(e,list) ((list->prev) ? TOPOROUTER_VERTEX(list->prev->data) : TOPOROUTER_VERTEX(edge_v1(e)))
  98
  99 #define vx(v) (GTS_POINT(v)->x)
 100 #define vy(v) (GTS_POINT(v)->y)
 101 #define vz(v) (GTS_POINT(v)->z)
 102
 103 #define close_enough_xy(a,b) (vx(a) > vx(b) - EPSILON && vx(a) < vx(b) + EPSILON && vy(a) > vy(b) - EPSILON && vy(a) < vy(b) + EPSILON)
 104
 105 #define tev1x(e) (vx(tedge_v1(e))
 106 #define tev1y(e) (vy(tedge_v1(e))
 107 #define tev1z(e) (vz(tedge_v1(e))
 108 #define tev2x(e) (vx(tedge_v2(e))
 109 #define tev2y(e) (vy(tedge_v2(e))
 110 #define tev2z(e) (vz(tedge_v2(e))
 111
 112 #define tvertex_intersect(a,b,c,d) (TOPOROUTER_VERTEX(vertex_intersect(GTS_VERTEX(a),GTS_VERTEX(b),GTS_VERTEX(c),GTS_VERTEX(d))))
 113
 114 #define TOPOROUTER_IS_BBOX(obj)      (gts_object_is_from_class (obj, toporouter_bbox_class ()))
 115 #define TOPOROUTER_BBOX(obj)          GTS_OBJECT_CAST (obj, toporouter_bbox_t, toporouter_bbox_class ())
 116 #define TOPOROUTER_BBOX_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_bbox_class_t, toporouter_bbox_class ())
 117
 118 typedef enum {
 119   PAD,
 120   PIN,
 121   VIA,
 122   ARC,
 123   VIA_SHADOW,
 124   LINE,
 125   OTHER,
 126   BOARD,
 127   EXPANSION_AREA,
 128   POLYGON,
 129   TEMP
 130 } toporouter_term_t;
 131
 132 struct _toporouter_bbox_t {
 133   GtsBBox b;
 134
 135   toporouter_term_t type;
 136   void *data;
 137   int layer;
 138
 139   GtsSurface *surface;
 140   GtsTriangle *enclosing;
 141
 142   GList *constraints;
 143   GtsPoint *point,
 144            *realpoint;
 145
 146 //  char *netlist, *style;
 147
 148   struct _toporouter_cluster_t *cluster;
 149
 150 };
 151
 152 struct _toporouter_bbox_class_t {
 153   GtsBBoxClass parent_class;
 154 };
 155
 156 typedef struct _toporouter_bbox_t toporouter_bbox_t;
 157 typedef struct _toporouter_bbox_class_t toporouter_bbox_class_t;
 158
 159 #define TOPOROUTER_IS_EDGE(obj)      (gts_object_is_from_class (obj, toporouter_edge_class ()))
 160 #define TOPOROUTER_EDGE(obj)          GTS_OBJECT_CAST (obj, toporouter_edge_t, toporouter_edge_class ())
 161 #define TOPOROUTER_EDGE_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_edge_class_t, toporouter_edge_class ())
 162
 163 #define EDGE_FLAG_DIRECTCONNECTION (1<<0)
 164
 165 struct _toporouter_edge_t {
 166   GtsEdge e;
 167   //NetListType *netlist;
 168
 169   guint flags;
 170
 171   GList *routing;
 172 };
 173
 174 struct _toporouter_edge_class_t {
 175   GtsEdgeClass parent_class;
 176 };
 177
 178 typedef struct _toporouter_edge_t toporouter_edge_t;
 179 typedef struct _toporouter_edge_class_t toporouter_edge_class_t;
 180
 181 #define TOPOROUTER_IS_VERTEX(obj)      (gts_object_is_from_class (obj, toporouter_vertex_class ()))
 182 #define TOPOROUTER_VERTEX(obj)          GTS_OBJECT_CAST (obj, toporouter_vertex_t, toporouter_vertex_class ())
 183 #define TOPOROUTER_VERTEX_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_vertex_class_t, toporouter_vertex_class ())
 184
 185 #define VERTEX_FLAG_VIZ      (1<<1)
 186 #define VERTEX_FLAG_CCW      (1<<2)
 187 #define VERTEX_FLAG_CW       (1<<3)
 188 #define VERTEX_FLAG_RED      (1<<4)
 189 #define VERTEX_FLAG_GREEN    (1<<5)
 190 #define VERTEX_FLAG_BLUE     (1<<6)
 191 #define VERTEX_FLAG_TEMP     (1<<7)
 192 #define VERTEX_FLAG_ROUTE    (1<<8)
 193 #define VERTEX_FLAG_FAKE     (1<<10)
 194 #define VERTEX_FLAG_SPECCUT  (1<<11)
 195
 196 struct _toporouter_vertex_t {
 197   GtsVertex v;
 198   //GList *boxes;
 199   struct _toporouter_bbox_t *bbox;
 200
 201   struct _toporouter_vertex_t *parent;
 202   struct _toporouter_vertex_t *child;
 203
 204   toporouter_edge_t *routingedge;
 205
 206   guint flags;
 207
 208   gdouble gcost, hcost;
 209   guint gn;
 210
 211   struct _toporouter_arc_t *arc;
 212
 213   struct _toporouter_oproute_t *oproute;
 214   struct _toporouter_route_t *route;
 215
 216   gdouble thickness;
 217
 218 };
 219
 220 struct _toporouter_vertex_class_t {
 221   GtsVertexClass parent_class;
 222 };
 223
 224 typedef struct _toporouter_vertex_t toporouter_vertex_t;
 225 typedef struct _toporouter_vertex_class_t toporouter_vertex_class_t;
 226
 227 #define TOPOROUTER_IS_CONSTRAINT(obj)      (gts_object_is_from_class (obj, toporouter_constraint_class ()))
 228 #define TOPOROUTER_CONSTRAINT(obj)          GTS_OBJECT_CAST (obj, toporouter_constraint_t, toporouter_constraint_class ())
 229 #define TOPOROUTER_CONSTRAINT_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_constraint_class_t, toporouter_constraint_class ())
 230
 231 struct _toporouter_constraint_t {
 232   GtsConstraint c;
 233   toporouter_bbox_t *box;
 234   GList *routing;
 235 };
 236
 237 struct _toporouter_constraint_class_t {
 238   GtsConstraintClass parent_class;
 239 };
 240
 241 typedef struct {
 242   gdouble x, y;
 243 } toporouter_spoint_t;
 244
 245 typedef struct _toporouter_constraint_t toporouter_constraint_t;
 246 typedef struct _toporouter_constraint_class_t toporouter_constraint_class_t;
 247
 248 typedef struct {
 249   GtsSurface *surface;
 250 //  GtsTriangle *t;
 251 //  GtsVertex *v1, *v2, *v3;
 252
 253   GList *vertices;
 254   GList *constraints;
 255   GList *edges;
 256
 257 } toporouter_layer_t;
 258
 259 #define TOPOROUTER_VERTEX_REGION(x) ((toporouter_vertex_region_t *)x)
 260 typedef struct {
 261
 262   GList *points;
 263   toporouter_vertex_t *v1, *v2;
 264   toporouter_vertex_t *origin;
 265
 266 } toporouter_vertex_region_t;
 267
 268 struct _toporouter_rubberband_arc_t {
 269   toporouter_vertex_t *pathv, *arcv;
 270   gdouble r, d;
 271   gint wind;
 272   GList *list;
 273 };
 274
 275 typedef struct _toporouter_rubberband_arc_t toporouter_rubberband_arc_t;
 276 #define TOPOROUTER_RUBBERBAND_ARC(x) ((toporouter_rubberband_arc_t *)x)
 277
 278 struct _toporouter_route_t {
 279
 280   struct _toporouter_netlist_t *netlist;
 281
 282   struct _toporouter_cluster_t *src, *dest;
 283   struct _toporouter_cluster_t *psrc, *pdest;
 284
 285   gdouble score, detourscore;
 286
 287   toporouter_vertex_t *curpoint;
 288   GHashTable *alltemppoints;
 289
 290   GList *path;
 291
 292   guint flags;
 293
 294   GList *destvertices, *srcvertices;
 295
 296   GList *topopath;
 297
 298   gdouble pscore;
 299   GList *ppath;
 300
 301   gint *ppathindices;
 302 };
 303
 304 typedef struct _toporouter_route_t toporouter_route_t;
 305
 306 #define TOPOROUTER_ROUTE(x) ((toporouter_route_t *)x)
 307
 308 struct _toporouter_netlist_t {
 309   GPtrArray *clusters, *routes;
 310   char *netlist, *style;
 311   GList *routed;
 312
 313   struct _toporouter_netlist_t *pair;
 314 };
 315
 316 typedef struct _toporouter_netlist_t toporouter_netlist_t;
 317
 318 #define TOPOROUTER_NETLIST(x) ((toporouter_netlist_t *)x)
 319
 320 struct _toporouter_cluster_t {
 321   gint c, pc;
 322   GPtrArray *boxes;
 323   toporouter_netlist_t *netlist;
 324 };
 325
 326 typedef struct _toporouter_cluster_t toporouter_cluster_t;
 327
 328 #define TOPOROUTER_CLUSTER(x) ((toporouter_cluster_t *)x)
 329
 330 #define TOPOROUTER_OPROUTE(x) ((toporouter_oproute_t *)x)
 331
 332 #define oproute_next(a,b) (b->next ? TOPOROUTER_ARC(b->next->data) : a->term2)
 333 #define oproute_prev(a,b) (b->prev ? TOPOROUTER_ARC(b->prev->data) : a->term1)
 334
 335 #define TOPOROUTER_SERPINTINE(x) ((toporouter_serpintine_t *)x)
 336
 337 struct _toporouter_serpintine_t {
 338   GList *arcs;
 339   gdouble x, y;
 340   gdouble x0, y0, x1, y1;
 341
 342   gpointer start;
 343   gdouble halfa, radius;
 344   guint nhalfcycles;
 345
 346 };
 347 typedef struct _toporouter_serpintine_t toporouter_serpintine_t;
 348
 349 struct _toporouter_oproute_t {
 350   GList *arcs;
 351   toporouter_vertex_t *term1, *term2;
 352   char *style; char *netlist;
 353   guint layergroup;
 354   gdouble tof;
 355   GList *path;
 356
 357   toporouter_serpintine_t *serp;
 358 };
 359
 360 typedef struct _toporouter_oproute_t toporouter_oproute_t;
 361
 362
 363 #define TOPOROUTER_IS_ARC(obj)           (gts_object_is_from_class (obj, toporouter_arc_class()))
 364 #define TOPOROUTER_ARC(obj)              GTS_OBJECT_CAST (obj, toporouter_arc_t, toporouter_arc_class())
 365 #define TOPOROUTER_ARC_CLASS(klass)      GTS_OBJECT_CLASS_CAST (klass, toporouter_arc_class_t, toporouter_arc_class())
 366
 367 struct _toporouter_arc_t {
 368   GtsObject object;
 369
 370   gdouble x0, y0, x1, y1;
 371   toporouter_vertex_t *centre, *v;
 372   gdouble r;
 373   gint dir;
 374
 375   GList *clearance;
 376
 377   toporouter_oproute_t *oproute;
 378
 379   toporouter_vertex_t *v1, *v2;
 380 };
 381
 382 struct _toporouter_arc_class_t {
 383   GtsObjectClass parent_class;
 384   gboolean binary;
 385 };
 386
 387 typedef struct _toporouter_arc_t toporouter_arc_t;
 388 typedef struct _toporouter_arc_class_t toporouter_arc_class_t;
 389
 390 typedef struct _toporouter_t toporouter_t;
 391
 392
 393
 394 typedef struct {
 395   guint id;
 396
 397   guint *pairwise_nodetour;
 398   gdouble pairwise_detour_sum;
 399   gdouble score;
 400   guint pairwise_fails;
 401
 402   toporouter_route_t *routedata;
 403
 404   toporouter_t *r;
 405
 406 } toporouter_netscore_t;
 407
 408 #define TOPOROUTER_NETSCORE(x) ((toporouter_netscore_t *)x)
 409
 410 struct _toporouter_t {
 411   GSList *bboxes;
 412   GNode *bboxtree;
 413
 414   toporouter_layer_t *layers;
 415
 416   GList *paths;
 417
 418   GList *keepoutlayers;
 419
 420   guint flags;
 421
 422   GList *destboxes, *consumeddestboxes;
 423
 424   /* settings: */
 425   gdouble viacost;
 426
 427   gdouble wiring_score;
 428
 429   GPtrArray *routes;
 430   GPtrArray *netlists;
 431
 432   GList *routednets, *failednets;
 433
 434   gint (*netsort)(toporouter_netscore_t **, toporouter_netscore_t **);
 435
 436   struct timeval starttime;
 437
 438   FILE *debug;
 439 };
 440
 441 typedef gint (*oproute_adjseg_func)
 442   (toporouter_t *,
 443    GList **,
 444    GList **,
 445    guint *,
 446    gdouble, gdouble, gdouble, gdouble,
 447    toporouter_oproute_t *,
 448    toporouter_oproute_t *);
 449
 450 typedef struct {
 451 #ifdef CAIRO_H
 452   cairo_t *cr;
 453   cairo_surface_t *surface;
 454 #endif
 455
 456   double s; /*!< scale factor. */
 457
 458   int mode;
 459   void *data;
 460
 461   char *filename;
 462   double iw; /*!< image width dimensions. */
 463   double ih; /*!< image height dimensions. */
 464 } drawing_context_t;
 465
 466 #define FOREACH_CLUSTER(clusters) do { \
 467   for(toporouter_cluster_t **i = ((toporouter_cluster_t **)clusters->pdata) + clusters->len - 1; i >= (toporouter_cluster_t **)clusters->pdata && clusters->len > 0; --i) { \
 468     toporouter_cluster_t *cluster = *i;
 469
 470 #define FOREACH_BBOX(boxes) do { \
 471   for(toporouter_bbox_t **i = ((toporouter_bbox_t **)boxes->pdata) + boxes->len - 1; i >= (toporouter_bbox_t **)boxes->pdata && boxes->len > 0; --i) { \
 472     toporouter_bbox_t *box = *i;
 473
 474 #define FOREACH_ROUTE(routes) do { \
 475   for(toporouter_route_t **i = ((toporouter_route_t **)routes->pdata) + routes->len - 1; i >= (toporouter_route_t **)routes->pdata && routes->len > 0; --i) { \
 476     toporouter_route_t *routedata = *i;
 477
 478 #define FOREACH_NETSCORE(netscores) do { \
 479   for(toporouter_netscore_t **i = ((toporouter_netscore_t **)netscores->pdata) + netscores->len - 1; i >= (toporouter_netscore_t **)netscores->pdata && netscores->len > 0; --i) { \
 480     toporouter_netscore_t *netscore = *i;
 481
 482 #define FOREACH_NETLIST(netlists) do { \
 483   for(toporouter_netlist_t **i = ((toporouter_netlist_t **)netlists->pdata) + netlists->len - 1; i >= (toporouter_netlist_t **)netlists->pdata && netlists->len > 0; --i) { \
 484     toporouter_netlist_t *netlist = *i;
 485
 486 #define FOREACH_END }} while(0)
 487
 488 #endif /* PCB_TOPOROUTER_H */