src/toporouter.h

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