2 * \file src/toporouter.h
4 * \brief Topological Autorouter for PCB.
8 * <h1><b>Copyright.</b></h1>\n
10 * Topological Autorouter for
11 * PCB, interactive printed circuit board design
13 * Copyright (C) 2009 Anthony Blake
15 * Copyright (C) 2009-2011 PCB Contributors (see ChangeLog for details)
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.
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.
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.
31 * Contact addresses for email:
32 * Anthony Blake, tonyb33@gmail.com
35 #ifndef PCB_TOPOROUTER_H
36 #define PCB_TOPOROUTER_H
41 #include "autoroute.h"
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)
76 #if TOPO_OUTPUT_ENABLED
80 #define EPSILON 0.0001f
82 //#define DEBUG_ROAR 1
84 #define tvdistance(a,b) hypot(vx(a)-vx(b),vy(a)-vy(b))
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))
91 #define tedge(v1,v2) TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v1), GTS_VERTEX(v2)))
93 #define edge_routing(e) (TOPOROUTER_IS_CONSTRAINT(e) ? TOPOROUTER_CONSTRAINT(e)->routing : e->routing)
94 #define vrouting(v) (edge_routing(v->routingedge))
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)))
99 #define vx(v) (GTS_POINT(v)->x)
100 #define vy(v) (GTS_POINT(v)->y)
101 #define vz(v) (GTS_POINT(v)->z)
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)
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))
112 #define tvertex_intersect(a,b,c,d) (TOPOROUTER_VERTEX(vertex_intersect(GTS_VERTEX(a),GTS_VERTEX(b),GTS_VERTEX(c),GTS_VERTEX(d))))
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 ())
132 struct _toporouter_bbox_t
{
135 toporouter_term_t type
;
140 GtsTriangle
*enclosing
;
146 // char *netlist, *style;
148 struct _toporouter_cluster_t
*cluster
;
152 struct _toporouter_bbox_class_t
{
153 GtsBBoxClass parent_class
;
156 typedef struct _toporouter_bbox_t toporouter_bbox_t
;
157 typedef struct _toporouter_bbox_class_t toporouter_bbox_class_t
;
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 ())
163 #define EDGE_FLAG_DIRECTCONNECTION (1<<0)
165 struct _toporouter_edge_t
{
167 //NetListType *netlist;
174 struct _toporouter_edge_class_t
{
175 GtsEdgeClass parent_class
;
178 typedef struct _toporouter_edge_t toporouter_edge_t
;
179 typedef struct _toporouter_edge_class_t toporouter_edge_class_t
;
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 ())
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)
196 struct _toporouter_vertex_t
{
199 struct _toporouter_bbox_t
*bbox
;
201 struct _toporouter_vertex_t
*parent
;
202 struct _toporouter_vertex_t
*child
;
204 toporouter_edge_t
*routingedge
;
208 gdouble gcost
, hcost
;
211 struct _toporouter_arc_t
*arc
;
213 struct _toporouter_oproute_t
*oproute
;
214 struct _toporouter_route_t
*route
;
220 struct _toporouter_vertex_class_t
{
221 GtsVertexClass parent_class
;
224 typedef struct _toporouter_vertex_t toporouter_vertex_t
;
225 typedef struct _toporouter_vertex_class_t toporouter_vertex_class_t
;
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 ())
231 struct _toporouter_constraint_t
{
233 toporouter_bbox_t
*box
;
237 struct _toporouter_constraint_class_t
{
238 GtsEdgeClass parent_class
;
243 } toporouter_spoint_t
;
245 typedef struct _toporouter_constraint_t toporouter_constraint_t
;
246 typedef struct _toporouter_constraint_class_t toporouter_constraint_class_t
;
251 // GtsVertex *v1, *v2, *v3;
257 } toporouter_layer_t
;
259 #define TOPOROUTER_VERTEX_REGION(x) ((toporouter_vertex_region_t *)x)
263 toporouter_vertex_t
*v1
, *v2
;
264 toporouter_vertex_t
*origin
;
266 } toporouter_vertex_region_t
;
268 struct _toporouter_rubberband_arc_t
{
269 toporouter_vertex_t
*pathv
, *arcv
;
275 typedef struct _toporouter_rubberband_arc_t toporouter_rubberband_arc_t
;
276 #define TOPOROUTER_RUBBERBAND_ARC(x) ((toporouter_rubberband_arc_t *)x)
278 struct _toporouter_route_t
{
280 struct _toporouter_netlist_t
*netlist
;
282 struct _toporouter_cluster_t
*src
, *dest
;
283 struct _toporouter_cluster_t
*psrc
, *pdest
;
285 gdouble score
, detourscore
;
287 toporouter_vertex_t
*curpoint
;
288 GHashTable
*alltemppoints
;
294 GList
*destvertices
, *srcvertices
;
304 typedef struct _toporouter_route_t toporouter_route_t
;
306 #define TOPOROUTER_ROUTE(x) ((toporouter_route_t *)x)
308 struct _toporouter_netlist_t
{
309 GPtrArray
*clusters
, *routes
;
310 char *netlist
, *style
;
313 struct _toporouter_netlist_t
*pair
;
316 typedef struct _toporouter_netlist_t toporouter_netlist_t
;
318 #define TOPOROUTER_NETLIST(x) ((toporouter_netlist_t *)x)
320 struct _toporouter_cluster_t
{
323 toporouter_netlist_t
*netlist
;
326 typedef struct _toporouter_cluster_t toporouter_cluster_t
;
328 #define TOPOROUTER_CLUSTER(x) ((toporouter_cluster_t *)x)
330 #define TOPOROUTER_OPROUTE(x) ((toporouter_oproute_t *)x)
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)
335 #define TOPOROUTER_SERPINTINE(x) ((toporouter_serpintine_t *)x)
337 struct _toporouter_serpintine_t
{
340 gdouble x0
, y0
, x1
, y1
;
343 gdouble halfa
, radius
;
347 typedef struct _toporouter_serpintine_t toporouter_serpintine_t
;
349 struct _toporouter_oproute_t
{
351 toporouter_vertex_t
*term1
, *term2
;
352 char *style
; char *netlist
;
357 toporouter_serpintine_t
*serp
;
360 typedef struct _toporouter_oproute_t toporouter_oproute_t
;
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())
367 struct _toporouter_arc_t
{
370 gdouble x0
, y0
, x1
, y1
;
371 toporouter_vertex_t
*centre
, *v
;
377 toporouter_oproute_t
*oproute
;
379 toporouter_vertex_t
*v1
, *v2
;
382 struct _toporouter_arc_class_t
{
383 GtsObjectClass parent_class
;
387 typedef struct _toporouter_arc_t toporouter_arc_t
;
388 typedef struct _toporouter_arc_class_t toporouter_arc_class_t
;
390 typedef struct _toporouter_t toporouter_t
;
397 guint
*pairwise_nodetour
;
398 gdouble pairwise_detour_sum
;
400 guint pairwise_fails
;
402 toporouter_route_t
*routedata
;
406 } toporouter_netscore_t
;
408 #define TOPOROUTER_NETSCORE(x) ((toporouter_netscore_t *)x)
410 struct _toporouter_t
{
414 toporouter_layer_t
*layers
;
418 GList
*keepoutlayers
;
422 GList
*destboxes
, *consumeddestboxes
;
427 gdouble wiring_score
;
432 GList
*routednets
, *failednets
;
434 gint (*netsort
)(toporouter_netscore_t
**, toporouter_netscore_t
**);
436 struct timeval starttime
;
441 typedef gint (*oproute_adjseg_func
)
446 gdouble
, gdouble
, gdouble
, gdouble
,
447 toporouter_oproute_t
*,
448 toporouter_oproute_t
*);
453 cairo_surface_t
*surface
;
456 double s
; /*!< scale factor. */
462 double iw
; /*!< image width dimensions. */
463 double ih
; /*!< image height dimensions. */
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;
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;
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;
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;
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;
486 #define FOREACH_END }} while(0)
488 #endif /* PCB_TOPOROUTER_H */