pcb 4.1.1
An interactive printed circuit board layout editor.

toporouter.h

Go to the documentation of this file.
00001 
00035 #ifndef PCB_TOPOROUTER_H
00036 #define PCB_TOPOROUTER_H
00037 
00038 #include <assert.h>
00039 #include "data.h"
00040 #include "macro.h"
00041 #include "autoroute.h"
00042 #include "box.h"
00043 #include "create.h"
00044 #include "draw.h"
00045 #include "error.h"
00046 #include "find.h"
00047 #include "heap.h"
00048 #include "rtree.h"
00049 #include "misc.h"
00050 #include "mymem.h"
00051 #include "polygon.h"
00052 #include "rats.h"
00053 #include "remove.h"
00054 #include "thermal.h"
00055 #include "undo.h"
00056 #include "global.h"
00057 
00058 #include "gts.h"
00059 
00060 #include <stdlib.h>
00061 #include <getopt.h>
00062 
00063 #include <sys/time.h>
00064 
00065 #define TOPOROUTER_FLAG_VERBOSE       (1<<0)
00066 #define TOPOROUTER_FLAG_HARDDEST      (1<<1)
00067 #define TOPOROUTER_FLAG_HARDSRC       (1<<2)
00068 #define TOPOROUTER_FLAG_MATCH         (1<<3)
00069 #define TOPOROUTER_FLAG_LAYERHINT     (1<<4)
00070 #define TOPOROUTER_FLAG_LEASTINVALID  (1<<5)
00071 #define TOPOROUTER_FLAG_AFTERORDER    (1<<6)
00072 #define TOPOROUTER_FLAG_AFTERRUBIX    (1<<7)
00073 #define TOPOROUTER_FLAG_GOFAR         (1<<8)
00074 #define TOPOROUTER_FLAG_DETOUR        (1<<9)
00075 
00076 #if TOPO_OUTPUT_ENABLED
00077   #include <cairo.h>
00078 #endif
00079 
00080 #define EPSILON 0.0001f
00081 
00082 //#define DEBUG_ROAR 1
00083 
00084 #define tvdistance(a,b) hypot(vx(a)-vx(b),vy(a)-vy(b))
00085 
00086 #define edge_v1(e) (GTS_SEGMENT(e)->v1)
00087 #define edge_v2(e) (GTS_SEGMENT(e)->v2)
00088 #define tedge_v1(e) (TOPOROUTER_VERTEX(GTS_SEGMENT(e)->v1))
00089 #define tedge_v2(e) (TOPOROUTER_VERTEX(GTS_SEGMENT(e)->v2))
00090 
00091 #define tedge(v1,v2) TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v1), GTS_VERTEX(v2)))
00092 
00093 #define edge_routing(e) (TOPOROUTER_IS_CONSTRAINT(e) ? TOPOROUTER_CONSTRAINT(e)->routing : e->routing)
00094 #define vrouting(v) (edge_routing(v->routingedge))
00095 
00096 #define edge_routing_next(e,list) ((list->next) ? TOPOROUTER_VERTEX(list->next->data) : TOPOROUTER_VERTEX(edge_v2(e)))
00097 #define edge_routing_prev(e,list) ((list->prev) ? TOPOROUTER_VERTEX(list->prev->data) : TOPOROUTER_VERTEX(edge_v1(e)))
00098 
00099 #define vx(v) (GTS_POINT(v)->x)
00100 #define vy(v) (GTS_POINT(v)->y)
00101 #define vz(v) (GTS_POINT(v)->z)
00102 
00103 #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)
00104 
00105 #define tev1x(e) (vx(tedge_v1(e))
00106 #define tev1y(e) (vy(tedge_v1(e))
00107 #define tev1z(e) (vz(tedge_v1(e))
00108 #define tev2x(e) (vx(tedge_v2(e))
00109 #define tev2y(e) (vy(tedge_v2(e))
00110 #define tev2z(e) (vz(tedge_v2(e))
00111 
00112 #define tvertex_intersect(a,b,c,d) (TOPOROUTER_VERTEX(vertex_intersect(GTS_VERTEX(a),GTS_VERTEX(b),GTS_VERTEX(c),GTS_VERTEX(d))))
00113 
00114 #define TOPOROUTER_IS_BBOX(obj)      (gts_object_is_from_class (obj, toporouter_bbox_class ()))
00115 #define TOPOROUTER_BBOX(obj)          GTS_OBJECT_CAST (obj, toporouter_bbox_t, toporouter_bbox_class ())
00116 #define TOPOROUTER_BBOX_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_bbox_class_t, toporouter_bbox_class ())
00117 
00118 typedef enum {
00119   PAD, 
00120   PIN, 
00121   VIA, 
00122   ARC, 
00123   VIA_SHADOW, 
00124   LINE, 
00125   OTHER, 
00126   BOARD, 
00127   EXPANSION_AREA, 
00128   POLYGON, 
00129   TEMP
00130 } toporouter_term_t;
00131 
00132 struct _toporouter_bbox_t {
00133   GtsBBox b;
00134 
00135   toporouter_term_t type;
00136   void *data;
00137   int layer;
00138 
00139   GtsSurface *surface;
00140   GtsTriangle *enclosing;
00141 
00142   GList *constraints;
00143   GtsPoint *point,
00144            *realpoint;
00145 
00146 //  char *netlist, *style;
00147 
00148   struct _toporouter_cluster_t *cluster;
00149 
00150 };
00151 
00152 struct _toporouter_bbox_class_t {
00153   GtsBBoxClass parent_class;
00154 };
00155 
00156 typedef struct _toporouter_bbox_t toporouter_bbox_t;
00157 typedef struct _toporouter_bbox_class_t toporouter_bbox_class_t;
00158 
00159 #define TOPOROUTER_IS_EDGE(obj)      (gts_object_is_from_class (obj, toporouter_edge_class ()))
00160 #define TOPOROUTER_EDGE(obj)          GTS_OBJECT_CAST (obj, toporouter_edge_t, toporouter_edge_class ())
00161 #define TOPOROUTER_EDGE_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_edge_class_t, toporouter_edge_class ())
00162 
00163 #define EDGE_FLAG_DIRECTCONNECTION (1<<0)
00164 
00165 struct _toporouter_edge_t {
00166   GtsEdge e;
00167   //NetListType *netlist;
00168 
00169   guint flags;
00170 
00171   GList *routing;
00172 };
00173 
00174 struct _toporouter_edge_class_t {
00175   GtsEdgeClass parent_class;
00176 };
00177 
00178 typedef struct _toporouter_edge_t toporouter_edge_t;
00179 typedef struct _toporouter_edge_class_t toporouter_edge_class_t;
00180 
00181 #define TOPOROUTER_IS_VERTEX(obj)      (gts_object_is_from_class (obj, toporouter_vertex_class ()))
00182 #define TOPOROUTER_VERTEX(obj)          GTS_OBJECT_CAST (obj, toporouter_vertex_t, toporouter_vertex_class ())
00183 #define TOPOROUTER_VERTEX_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_vertex_class_t, toporouter_vertex_class ())
00184 
00185 #define VERTEX_FLAG_VIZ      (1<<1)
00186 #define VERTEX_FLAG_CCW      (1<<2)
00187 #define VERTEX_FLAG_CW       (1<<3)
00188 #define VERTEX_FLAG_RED      (1<<4)
00189 #define VERTEX_FLAG_GREEN    (1<<5)
00190 #define VERTEX_FLAG_BLUE     (1<<6)
00191 #define VERTEX_FLAG_TEMP     (1<<7)
00192 #define VERTEX_FLAG_ROUTE    (1<<8)
00193 #define VERTEX_FLAG_FAKE     (1<<10)
00194 #define VERTEX_FLAG_SPECCUT  (1<<11)
00195 
00196 struct _toporouter_vertex_t {
00197   GtsVertex v;
00198   //GList *boxes;
00199   struct _toporouter_bbox_t *bbox;
00200 
00201   struct _toporouter_vertex_t *parent;
00202   struct _toporouter_vertex_t *child;
00203 
00204   toporouter_edge_t *routingedge;
00205 
00206   guint flags;
00207 
00208   gdouble gcost, hcost;
00209   guint gn;
00210 
00211   struct _toporouter_arc_t *arc;
00212 
00213   struct _toporouter_oproute_t *oproute;
00214   struct _toporouter_route_t *route;
00215 
00216   gdouble thickness;
00217 
00218 };
00219 
00220 struct _toporouter_vertex_class_t {
00221   GtsVertexClass parent_class;
00222 };
00223 
00224 typedef struct _toporouter_vertex_t toporouter_vertex_t;
00225 typedef struct _toporouter_vertex_class_t toporouter_vertex_class_t;
00226 
00227 #define TOPOROUTER_IS_CONSTRAINT(obj)      (gts_object_is_from_class (obj, toporouter_constraint_class ()))
00228 #define TOPOROUTER_CONSTRAINT(obj)          GTS_OBJECT_CAST (obj, toporouter_constraint_t, toporouter_constraint_class ())
00229 #define TOPOROUTER_CONSTRAINT_CLASS(klass)  GTS_OBJECT_CLASS_CAST (klass, toporouter_constraint_class_t, toporouter_constraint_class ())
00230 
00231 struct _toporouter_constraint_t {
00232   GtsConstraint c;
00233   toporouter_bbox_t *box;
00234   GList *routing;
00235 };
00236 
00237 struct _toporouter_constraint_class_t {
00238   GtsConstraintClass parent_class;
00239 };
00240 
00241 typedef struct {
00242   gdouble x, y;
00243 } toporouter_spoint_t;
00244 
00245 typedef struct _toporouter_constraint_t toporouter_constraint_t;
00246 typedef struct _toporouter_constraint_class_t toporouter_constraint_class_t;
00247 
00248 typedef struct {
00249   GtsSurface *surface;
00250 //  GtsTriangle *t;
00251 //  GtsVertex *v1, *v2, *v3;
00252   
00253   GList *vertices;
00254   GList *constraints; 
00255   GList *edges;
00256 
00257 } toporouter_layer_t;
00258 
00259 #define TOPOROUTER_VERTEX_REGION(x) ((toporouter_vertex_region_t *)x)
00260 typedef struct {
00261 
00262   GList *points;
00263   toporouter_vertex_t *v1, *v2;
00264   toporouter_vertex_t *origin;
00265 
00266 } toporouter_vertex_region_t;
00267 
00268 struct _toporouter_rubberband_arc_t {
00269   toporouter_vertex_t *pathv, *arcv;
00270   gdouble r, d;
00271   gint wind;
00272   GList *list;
00273 };
00274 
00275 typedef struct _toporouter_rubberband_arc_t toporouter_rubberband_arc_t;
00276 #define TOPOROUTER_RUBBERBAND_ARC(x) ((toporouter_rubberband_arc_t *)x)
00277 
00278 struct _toporouter_route_t {
00279 
00280   struct _toporouter_netlist_t *netlist;
00281 
00282   struct _toporouter_cluster_t *src, *dest;
00283   struct _toporouter_cluster_t *psrc, *pdest;
00284 
00285   gdouble score, detourscore;
00286 
00287   toporouter_vertex_t *curpoint;
00288   GHashTable *alltemppoints; 
00289   
00290   GList *path;
00291   
00292   guint flags;
00293 
00294   GList *destvertices, *srcvertices;
00295 
00296   GList *topopath;
00297 
00298   gdouble pscore;
00299   GList *ppath;
00300 
00301   gint *ppathindices;
00302 };
00303 
00304 typedef struct _toporouter_route_t toporouter_route_t;
00305 
00306 #define TOPOROUTER_ROUTE(x) ((toporouter_route_t *)x)
00307 
00308 struct _toporouter_netlist_t {
00309   GPtrArray *clusters, *routes;
00310   char *netlist, *style;
00311   GList *routed;
00312 
00313   struct _toporouter_netlist_t *pair;
00314 };
00315 
00316 typedef struct _toporouter_netlist_t toporouter_netlist_t;
00317 
00318 #define TOPOROUTER_NETLIST(x) ((toporouter_netlist_t *)x)
00319 
00320 struct _toporouter_cluster_t {
00321   gint c, pc;
00322   GPtrArray *boxes;
00323   toporouter_netlist_t *netlist;
00324 };
00325 
00326 typedef struct _toporouter_cluster_t toporouter_cluster_t;
00327 
00328 #define TOPOROUTER_CLUSTER(x) ((toporouter_cluster_t *)x)
00329 
00330 #define TOPOROUTER_OPROUTE(x) ((toporouter_oproute_t *)x)
00331 
00332 #define oproute_next(a,b) (b->next ? TOPOROUTER_ARC(b->next->data) : a->term2)
00333 #define oproute_prev(a,b) (b->prev ? TOPOROUTER_ARC(b->prev->data) : a->term1)
00334 
00335 #define TOPOROUTER_SERPINTINE(x) ((toporouter_serpintine_t *)x)
00336 
00337 struct _toporouter_serpintine_t {
00338   GList *arcs;
00339   gdouble x, y;
00340   gdouble x0, y0, x1, y1;
00341 
00342   gpointer start;
00343   gdouble halfa, radius;
00344   guint nhalfcycles;
00345 
00346 };
00347 typedef struct _toporouter_serpintine_t toporouter_serpintine_t;
00348 
00349 struct _toporouter_oproute_t {
00350   GList *arcs;
00351   toporouter_vertex_t *term1, *term2;
00352   char *style; char *netlist;
00353   guint layergroup;
00354   gdouble tof;
00355   GList *path;
00356   
00357   toporouter_serpintine_t *serp;
00358 };
00359 
00360 typedef struct _toporouter_oproute_t toporouter_oproute_t;
00361 
00362 
00363 #define TOPOROUTER_IS_ARC(obj)           (gts_object_is_from_class (obj, toporouter_arc_class()))
00364 #define TOPOROUTER_ARC(obj)              GTS_OBJECT_CAST (obj, toporouter_arc_t, toporouter_arc_class())
00365 #define TOPOROUTER_ARC_CLASS(klass)      GTS_OBJECT_CLASS_CAST (klass, toporouter_arc_class_t, toporouter_arc_class())
00366 
00367 struct _toporouter_arc_t {
00368   GtsObject object;
00369   
00370   gdouble x0, y0, x1, y1;
00371   toporouter_vertex_t *centre, *v;
00372   gdouble r;
00373   gint dir;
00374 
00375   GList *clearance;
00376 
00377   toporouter_oproute_t *oproute;
00378 
00379   toporouter_vertex_t *v1, *v2;
00380 };
00381 
00382 struct _toporouter_arc_class_t {
00383   GtsObjectClass parent_class;
00384   gboolean binary;
00385 };
00386 
00387 typedef struct _toporouter_arc_t toporouter_arc_t;
00388 typedef struct _toporouter_arc_class_t toporouter_arc_class_t;
00389 
00390 typedef struct _toporouter_t toporouter_t;
00391 
00392 
00393 
00394 typedef struct {
00395   guint id;
00396 
00397   guint *pairwise_nodetour;
00398   gdouble pairwise_detour_sum;
00399   gdouble score;
00400   guint pairwise_fails;
00401 
00402   toporouter_route_t *routedata;
00403 
00404   toporouter_t *r;
00405 
00406 } toporouter_netscore_t;
00407 
00408 #define TOPOROUTER_NETSCORE(x) ((toporouter_netscore_t *)x)
00409 
00410 struct _toporouter_t {
00411   GSList *bboxes;
00412   GNode *bboxtree;
00413 
00414   toporouter_layer_t *layers;
00415   
00416   GList *paths;
00417 
00418   GList *keepoutlayers;
00419 
00420   guint flags;
00421 
00422   GList *destboxes, *consumeddestboxes;
00423 
00424   /* settings: */
00425   gdouble viacost;
00426 
00427   gdouble wiring_score;
00428 
00429   GPtrArray *routes;
00430   GPtrArray *netlists;
00431 
00432   GList *routednets, *failednets;
00433 
00434   gint (*netsort)(toporouter_netscore_t **, toporouter_netscore_t **);
00435 
00436   struct timeval starttime;  
00437 
00438   FILE *debug;
00439 };
00440 
00441 typedef gint (*oproute_adjseg_func)
00442   (toporouter_t *,
00443    GList **,
00444    GList **,
00445    guint *,
00446    gdouble, gdouble, gdouble, gdouble,
00447    toporouter_oproute_t *,
00448    toporouter_oproute_t *);
00449 
00450 typedef struct {
00451 #ifdef CAIRO_H
00452   cairo_t *cr;
00453   cairo_surface_t *surface;
00454 #endif  
00455   
00456   double s; 
00458   int mode;
00459   void *data;
00460 
00461   char *filename;
00462   double iw; 
00463   double ih; 
00464 } drawing_context_t;
00465 
00466 #define FOREACH_CLUSTER(clusters) do { \
00467   for(toporouter_cluster_t **i = ((toporouter_cluster_t **)clusters->pdata) + clusters->len - 1; i >= (toporouter_cluster_t **)clusters->pdata && clusters->len > 0; --i) { \
00468     toporouter_cluster_t *cluster = *i; 
00469 
00470 #define FOREACH_BBOX(boxes) do { \
00471   for(toporouter_bbox_t **i = ((toporouter_bbox_t **)boxes->pdata) + boxes->len - 1; i >= (toporouter_bbox_t **)boxes->pdata && boxes->len > 0; --i) { \
00472     toporouter_bbox_t *box = *i;
00473 
00474 #define FOREACH_ROUTE(routes) do { \
00475   for(toporouter_route_t **i = ((toporouter_route_t **)routes->pdata) + routes->len - 1; i >= (toporouter_route_t **)routes->pdata && routes->len > 0; --i) { \
00476     toporouter_route_t *routedata = *i;
00477 
00478 #define FOREACH_NETSCORE(netscores) do { \
00479   for(toporouter_netscore_t **i = ((toporouter_netscore_t **)netscores->pdata) + netscores->len - 1; i >= (toporouter_netscore_t **)netscores->pdata && netscores->len > 0; --i) { \
00480     toporouter_netscore_t *netscore = *i;
00481 
00482 #define FOREACH_NETLIST(netlists) do { \
00483   for(toporouter_netlist_t **i = ((toporouter_netlist_t **)netlists->pdata) + netlists->len - 1; i >= (toporouter_netlist_t **)netlists->pdata && netlists->len > 0; --i) { \
00484     toporouter_netlist_t *netlist = *i;
00485 
00486 #define FOREACH_END }} while(0)
00487 
00488 #endif /* PCB_TOPOROUTER_H */