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 #define TOPOROUTER_FLAG_DETOUR        (1<<9)
  67
  68 #if TOPO_OUTPUT_ENABLED
  69   #include <cairo.h>
  70 #endif
  71
  72 #define EPSILON 0.0001f
  73
  74 //#define DEBUG_ROAR 1
  75
  76 #define coord_distance(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
  77 #define coord_distance2(a,b,c,d) (pow(a-c,2)+pow(b-d,2))
  78
  79 #define tvdistance(a,b) sqrt(pow(vx(a)-vx(b),2)+pow(vy(a)-vy(b),2))
  80 #define tvdistance2(a,b) (pow(vx(a)-vx(b),2)+pow(vy(a)-vy(b),2))
  81
  82 #define edge_v1(e) (GTS_SEGMENT(e)->v1)
  83 #define edge_v2(e) (GTS_SEGMENT(e)->v2)
  84 #define tedge_v1(e) (TOPOROUTER_VERTEX(GTS_SEGMENT(e)->v1))
  85 #define tedge_v2(e) (TOPOROUTER_VERTEX(GTS_SEGMENT(e)->v2))
  86
  87 #define tedge(v1,v2) TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v1), GTS_VERTEX(v2)))
  88
  89 #define edge_routing(e) (TOPOROUTER_IS_CONSTRAINT(e) ? TOPOROUTER_CONSTRAINT(e)->routing : e->routing)
  90 #define vrouting(v) (edge_routing(v->routingedge))
  91
  92 #define edge_routing_next(e,list) ((list->next) ? TOPOROUTER_VERTEX(list->next->data) : TOPOROUTER_VERTEX(edge_v2(e)))
  93 #define edge_routing_prev(e,list) ((list->prev) ? TOPOROUTER_VERTEX(list->prev->data) : TOPOROUTER_VERTEX(edge_v1(e)))
  94
  95 #define vx(v) (GTS_POINT(v)->x)
  96 #define vy(v) (GTS_POINT(v)->y)
  97 #define vz(v) (GTS_POINT(v)->z)
  98
  99 #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)
 100
 101 #define tev1x(e) (vx(tedge_v1(e))
 102 #define tev1y(e) (vy(tedge_v1(e))
 103 #define tev1z(e) (vz(tedge_v1(e))
 104 #define tev2x(e) (vx(tedge_v2(e))
 105 #define tev2y(e) (vy(tedge_v2(e))
 106 #define tev2z(e) (vz(tedge_v2(e))
 107
 108 #define tvertex_intersect(a,b,c,d) (TOPOROUTER_VERTEX(vertex_intersect(GTS_VERTEX(a),GTS_VERTEX(b),GTS_VERTEX(c),GTS_VERTEX(d))))
 109
 110 #define TOPOROUTER_IS_BBOX(obj)      (gts_object_is_from_class (obj, toporouter_bbox_class ()))
 111 #define TOPOROUTER_BBOX(obj)          GTS_OBJECT_CAST (obj, toporouter_bbox_t, toporouter_bbox_class ())
 112 #define TOPOROUTER_BBOX_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_bbox_class_t, toporouter_bbox_class ())
 113
 114 typedef enum {
 115   PAD,
 116   PIN,
 117   VIA,
 118   ARC,
 119   VIA_SHADOW,
 120   LINE,
 121   OTHER,
 122   BOARD,
 123   EXPANSION_AREA,
 124   POLYGON,
 125   TEMP
 126 } toporouter_term_t;
 127
 128 struct _toporouter_bbox_t {
 129   GtsBBox b;
 130
 131   toporouter_term_t type;
 132   void *data;
 133   int layer;
 134
 135   GtsSurface *surface;
 136   GtsTriangle *enclosing;
 137
 138   GList *constraints;
 139   GtsPoint *point,
 140            *realpoint;
 141
 142 //  char *netlist, *style;
 143
 144   struct _toporouter_cluster_t *cluster;
 145
 146 };
 147
 148 struct _toporouter_bbox_class_t {
 149   GtsBBoxClass parent_class;
 150 };
 151
 152 typedef struct _toporouter_bbox_t toporouter_bbox_t;
 153 typedef struct _toporouter_bbox_class_t toporouter_bbox_class_t;
 154
 155 #define TOPOROUTER_IS_EDGE(obj)      (gts_object_is_from_class (obj, toporouter_edge_class ()))
 156 #define TOPOROUTER_EDGE(obj)          GTS_OBJECT_CAST (obj, toporouter_edge_t, toporouter_edge_class ())
 157 #define TOPOROUTER_EDGE_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_edge_class_t, toporouter_edge_class ())
 158
 159 #define EDGE_FLAG_DIRECTCONNECTION (1<<0)
 160
 161 struct _toporouter_edge_t {
 162   GtsEdge e;
 163   //NetListType *netlist;
 164
 165   guint flags;
 166
 167   GList *routing;
 168 };
 169
 170 struct _toporouter_edge_class_t {
 171   GtsEdgeClass parent_class;
 172 };
 173
 174 typedef struct _toporouter_edge_t toporouter_edge_t;
 175 typedef struct _toporouter_edge_class_t toporouter_edge_class_t;
 176
 177 #define TOPOROUTER_IS_VERTEX(obj)      (gts_object_is_from_class (obj, toporouter_vertex_class ()))
 178 #define TOPOROUTER_VERTEX(obj)          GTS_OBJECT_CAST (obj, toporouter_vertex_t, toporouter_vertex_class ())
 179 #define TOPOROUTER_VERTEX_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_vertex_class_t, toporouter_vertex_class ())
 180
 181 #define VERTEX_FLAG_VIZ      (1<<1)
 182 #define VERTEX_FLAG_CCW      (1<<2)
 183 #define VERTEX_FLAG_CW       (1<<3)
 184 #define VERTEX_FLAG_RED      (1<<4)
 185 #define VERTEX_FLAG_GREEN    (1<<5)
 186 #define VERTEX_FLAG_BLUE     (1<<6)
 187 #define VERTEX_FLAG_TEMP     (1<<7)
 188 #define VERTEX_FLAG_ROUTE    (1<<8)
 189 #define VERTEX_FLAG_FAKE     (1<<10)
 190 #define VERTEX_FLAG_SPECCUT  (1<<11)
 191
 192 struct _toporouter_vertex_t {
 193   GtsVertex v;
 194   //GList *boxes;
 195   struct _toporouter_bbox_t *bbox;
 196
 197   struct _toporouter_vertex_t *parent;
 198   struct _toporouter_vertex_t *child;
 199
 200   toporouter_edge_t *routingedge;
 201
 202   guint flags;
 203
 204   gdouble gcost, hcost;
 205   guint gn;
 206
 207   struct _toporouter_arc_t *arc;
 208
 209   struct _toporouter_oproute_t *oproute;
 210   struct _toporouter_route_t *route;
 211
 212   gdouble thickness;
 213
 214 };
 215
 216 struct _toporouter_vertex_class_t {
 217   GtsVertexClass parent_class;
 218 };
 219
 220 typedef struct _toporouter_vertex_t toporouter_vertex_t;
 221 typedef struct _toporouter_vertex_class_t toporouter_vertex_class_t;
 222
 223 #define TOPOROUTER_IS_CONSTRAINT(obj)      (gts_object_is_from_class (obj, toporouter_constraint_class ()))
 224 #define TOPOROUTER_CONSTRAINT(obj)          GTS_OBJECT_CAST (obj, toporouter_constraint_t, toporouter_constraint_class ())
 225 #define TOPOROUTER_CONSTRAINT_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_constraint_class_t, toporouter_constraint_class ())
 226
 227 struct _toporouter_constraint_t {
 228   GtsConstraint c;
 229   toporouter_bbox_t *box;
 230   GList *routing;
 231 };
 232
 233 struct _toporouter_constraint_class_t {
 234   GtsConstraintClass parent_class;
 235 };
 236
 237 typedef struct {
 238   gdouble x, y;
 239 } toporouter_spoint_t;
 240
 241 typedef struct _toporouter_constraint_t toporouter_constraint_t;
 242 typedef struct _toporouter_constraint_class_t toporouter_constraint_class_t;
 243
 244 typedef struct {
 245   GtsSurface *surface;
 246 //  GtsTriangle *t;
 247 //  GtsVertex *v1, *v2, *v3;
 248
 249   GList *vertices;
 250   GList *constraints;
 251   GList *edges;
 252
 253 } toporouter_layer_t;
 254
 255 #define TOPOROUTER_VERTEX_REGION(x) ((toporouter_vertex_region_t *)x)
 256 typedef struct {
 257
 258   GList *points;
 259   toporouter_vertex_t *v1, *v2;
 260   toporouter_vertex_t *origin;
 261
 262 } toporouter_vertex_region_t;
 263
 264 struct _toporouter_rubberband_arc_t {
 265   toporouter_vertex_t *pathv, *arcv;
 266   gdouble r, d;
 267   gint wind;
 268   GList *list;
 269 };
 270
 271 typedef struct _toporouter_rubberband_arc_t toporouter_rubberband_arc_t;
 272 #define TOPOROUTER_RUBBERBAND_ARC(x) ((toporouter_rubberband_arc_t *)x)
 273
 274 struct _toporouter_route_t {
 275
 276   struct _toporouter_netlist_t *netlist;
 277
 278   struct _toporouter_cluster_t *src, *dest;
 279   struct _toporouter_cluster_t *psrc, *pdest;
 280
 281   gdouble score, detourscore;
 282
 283   toporouter_vertex_t *curpoint;
 284   GHashTable *alltemppoints;
 285
 286   GList *path;
 287
 288   guint flags;
 289
 290   GList *destvertices, *srcvertices;
 291
 292   GList *topopath;
 293
 294   gdouble pscore;
 295   GList *ppath;
 296
 297   gint *ppathindices;
 298 };
 299
 300 typedef struct _toporouter_route_t toporouter_route_t;
 301
 302 #define TOPOROUTER_ROUTE(x) ((toporouter_route_t *)x)
 303
 304 struct _toporouter_netlist_t {
 305   GPtrArray *clusters, *routes;
 306   char *netlist, *style;
 307   GList *routed;
 308
 309   struct _toporouter_netlist_t *pair;
 310 };
 311
 312 typedef struct _toporouter_netlist_t toporouter_netlist_t;
 313
 314 #define TOPOROUTER_NETLIST(x) ((toporouter_netlist_t *)x)
 315
 316 struct _toporouter_cluster_t {
 317   gint c, pc;
 318   GPtrArray *boxes;
 319   toporouter_netlist_t *netlist;
 320 };
 321
 322 typedef struct _toporouter_cluster_t toporouter_cluster_t;
 323
 324 #define TOPOROUTER_CLUSTER(x) ((toporouter_cluster_t *)x)
 325
 326 #define TOPOROUTER_OPROUTE(x) ((toporouter_oproute_t *)x)
 327
 328 #define oproute_next(a,b) (b->next ? TOPOROUTER_ARC(b->next->data) : a->term2)
 329 #define oproute_prev(a,b) (b->prev ? TOPOROUTER_ARC(b->prev->data) : a->term1)
 330
 331 #define TOPOROUTER_SERPINTINE(x) ((toporouter_serpintine_t *)x)
 332
 333 struct _toporouter_serpintine_t {
 334   GList *arcs;
 335   gdouble x, y;
 336   gdouble x0, y0, x1, y1;
 337
 338   gpointer start;
 339   gdouble halfa, radius;
 340   guint nhalfcycles;
 341
 342 };
 343 typedef struct _toporouter_serpintine_t toporouter_serpintine_t;
 344
 345 struct _toporouter_oproute_t {
 346   GList *arcs;
 347   toporouter_vertex_t *term1, *term2;
 348   char *style; char *netlist;
 349   guint layergroup;
 350   gdouble tof;
 351   GList *path;
 352
 353   toporouter_serpintine_t *serp;
 354 };
 355
 356 typedef struct _toporouter_oproute_t toporouter_oproute_t;
 357
 358
 359 #define TOPOROUTER_IS_ARC(obj)           (gts_object_is_from_class (obj, toporouter_arc_class()))
 360 #define TOPOROUTER_ARC(obj)              GTS_OBJECT_CAST (obj, toporouter_arc_t, toporouter_arc_class())
 361 #define TOPOROUTER_ARC_CLASS(klass)      GTS_OBJECT_CLASS_CAST (klass, toporouter_arc_class_t, toporouter_arc_class())
 362
 363 struct _toporouter_arc_t {
 364   GtsObject object;
 365
 366   gdouble x0, y0, x1, y1;
 367   toporouter_vertex_t *centre, *v;
 368   gdouble r;
 369   gint dir;
 370
 371   GList *clearance;
 372
 373   toporouter_oproute_t *oproute;
 374
 375   toporouter_vertex_t *v1, *v2;
 376 };
 377
 378 struct _toporouter_arc_class_t {
 379   GtsObjectClass parent_class;
 380   gboolean binary;
 381 };
 382
 383 typedef struct _toporouter_arc_t toporouter_arc_t;
 384 typedef struct _toporouter_arc_class_t toporouter_arc_class_t;
 385
 386 typedef struct _toporouter_t toporouter_t;
 387
 388
 389
 390 typedef struct {
 391   guint id;
 392
 393   guint *pairwise_nodetour;
 394   gdouble pairwise_detour_sum;
 395   gdouble score;
 396   guint pairwise_fails;
 397
 398   toporouter_route_t *routedata;
 399
 400   toporouter_t *r;
 401
 402 } toporouter_netscore_t;
 403
 404 #define TOPOROUTER_NETSCORE(x) ((toporouter_netscore_t *)x)
 405
 406 struct _toporouter_t {
 407   GSList *bboxes;
 408   GNode *bboxtree;
 409
 410   toporouter_layer_t *layers;
 411
 412   GList *paths;
 413
 414   GList *keepoutlayers;
 415
 416   guint flags;
 417
 418   GList *destboxes, *consumeddestboxes;
 419
 420   /* settings: */
 421   guint viamax;
 422   gdouble viacost;
 423   gdouble stublength;
 424   gdouble serpintine_half_amplitude;
 425
 426   gdouble wiring_score;
 427
 428   GPtrArray *routes;
 429   GPtrArray *netlists;
 430
 431   GList *routednets, *failednets;
 432
 433   gint (*netsort)(toporouter_netscore_t **, toporouter_netscore_t **);
 434
 435   struct timeval starttime;
 436
 437   FILE *debug;
 438 };
 439
 440 typedef gint (*oproute_adjseg_func)
 441   (toporouter_t *,
 442    GList **,
 443    GList **,
 444    guint *,
 445    gdouble, gdouble, gdouble, gdouble,
 446    toporouter_oproute_t *,
 447    toporouter_oproute_t *);
 448
 449 typedef struct {
 450 #ifdef CAIRO_H
 451   cairo_t *cr;
 452   cairo_surface_t *surface;
 453 #endif
 454
 455   double s; /* scale factor */
 456
 457   int mode;
 458   void *data;
 459
 460   char *filename;
 461   double iw, ih; /* image dimensions */
 462 } drawing_context_t;
 463
 464 #define FOREACH_CLUSTER(clusters) do { \
 465   for(toporouter_cluster_t **i = ((toporouter_cluster_t **)clusters->pdata) + clusters->len - 1; i >= (toporouter_cluster_t **)clusters->pdata && clusters->len > 0; --i) { \
 466     toporouter_cluster_t *cluster = *i;
 467
 468 #define FOREACH_BBOX(boxes) do { \
 469   for(toporouter_bbox_t **i = ((toporouter_bbox_t **)boxes->pdata) + boxes->len - 1; i >= (toporouter_bbox_t **)boxes->pdata && boxes->len > 0; --i) { \
 470     toporouter_bbox_t *box = *i;
 471
 472 #define FOREACH_ROUTE(routes) do { \
 473   for(toporouter_route_t **i = ((toporouter_route_t **)routes->pdata) + routes->len - 1; i >= (toporouter_route_t **)routes->pdata && routes->len > 0; --i) { \
 474     toporouter_route_t *routedata = *i;
 475
 476 #define FOREACH_NETSCORE(netscores) do { \
 477   for(toporouter_netscore_t **i = ((toporouter_netscore_t **)netscores->pdata) + netscores->len - 1; i >= (toporouter_netscore_t **)netscores->pdata && netscores->len > 0; --i) { \
 478     toporouter_netscore_t *netscore = *i;
 479
 480 #define FOREACH_NETLIST(netlists) do { \
 481   for(toporouter_netlist_t **i = ((toporouter_netlist_t **)netlists->pdata) + netlists->len - 1; i >= (toporouter_netlist_t **)netlists->pdata && netlists->len > 0; --i) { \
 482     toporouter_netlist_t *netlist = *i;
 483
 484 #define FOREACH_END }} while(0)
 485
 486 #endif /* __TOPOROUTER_INCLUDED__ */