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