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)
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.
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.
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.
23 * Contact addresses for email:
24 * Anthony Blake, tonyb33@gmail.com
28 * This is *EXPERIMENTAL* code.
30 * As the code is experimental, the algorithms and code
31 * are likely to change. Which means it isn't documented
32 * or optimized. If you would like to learn about Topological
33 * Autorouters, the following papers are good starting points:
35 * This file implements a topological autorouter, and uses techniques from the
36 * following publications:
38 * Dayan, T. and Dai, W.W.M., "Layer Assignment for a Rubber Band Router" Tech
39 * Report UCSC-CRL-92-50, Univ. of California, Santa Cruz, 1992.
41 * Dai, W.W.M and Dayan, T. and Staepelaere, D., "Topological Routing in SURF:
42 * Generating a Rubber-Band Sketch" Proc. 28th ACM/IEEE Design Automation
43 * Conference, 1991, pp. 39-44.
45 * David Staepelaere, Jeffrey Jue, Tal Dayan, Wayne Wei-Ming Dai, "SURF:
46 * Rubber-Band Routing System for Multichip Modules," IEEE Design and Test of
47 * Computers ,vol. 10, no. 4, pp. 18-26, October/December, 1993.
49 * Dayan, T., "Rubber-band based topological router" PhD Thesis, Univ. of
50 * California, Santa Cruz, 1997.
52 * David Staepelaere, "Geometric transformations for a rubber-band sketch"
53 * Master's thesis, Univ. of California, Santa Cruz, September 1992.
58 #include "toporouter.h"
59 #include "pcb-printf.h"
61 #define BOARD_EDGE_RESOLUTION MIL_TO_COORD (100.)
62 #define VIA_COST_AS_DISTANCE MIL_TO_COORD (100.)
63 #define ROAR_DETOUR_THRESHOLD MIL_TO_COORD (10.)
67 toporouter_edge_init (toporouter_edge_t
*edge
)
73 toporouter_edge_class_t
*
74 toporouter_edge_class(void)
76 static toporouter_edge_class_t
*klass
= NULL
;
79 GtsObjectClassInfo constraint_info
= {
81 sizeof (toporouter_edge_t
),
82 sizeof (toporouter_edge_class_t
),
83 (GtsObjectClassInitFunc
) NULL
,
84 (GtsObjectInitFunc
) toporouter_edge_init
,
88 klass
= (toporouter_edge_class_t
*)gts_object_class_new (GTS_OBJECT_CLASS (gts_edge_class ()), &constraint_info
);
95 toporouter_bbox_init (toporouter_bbox_t
*box
)
99 box
->constraints
= NULL
;
103 toporouter_bbox_class_t
*
104 toporouter_bbox_class(void)
106 static toporouter_bbox_class_t
*klass
= NULL
;
109 GtsObjectClassInfo constraint_info
= {
111 sizeof (toporouter_bbox_t
),
112 sizeof (toporouter_bbox_class_t
),
113 (GtsObjectClassInitFunc
) NULL
,
114 (GtsObjectInitFunc
) toporouter_bbox_init
,
115 (GtsArgSetFunc
) NULL
,
118 klass
= (toporouter_bbox_class_t
*)gts_object_class_new (GTS_OBJECT_CLASS (gts_bbox_class ()), &constraint_info
);
125 toporouter_vertex_class_init (toporouter_vertex_class_t
*klass
)
131 toporouter_vertex_init (toporouter_vertex_t
*vertex
)
134 vertex
->parent
= NULL
;
135 vertex
->child
= NULL
;
137 vertex
->routingedge
= NULL
;
139 vertex
->oproute
= NULL
;
140 vertex
->route
= NULL
;
147 toporouter_vertex_class_t
*
148 toporouter_vertex_class(void)
150 static toporouter_vertex_class_t
*klass
= NULL
;
153 GtsObjectClassInfo constraint_info
= {
154 "toporouter_vertex_t",
155 sizeof (toporouter_vertex_t
),
156 sizeof (toporouter_vertex_class_t
),
157 (GtsObjectClassInitFunc
) toporouter_vertex_class_init
,
158 (GtsObjectInitFunc
) toporouter_vertex_init
,
159 (GtsArgSetFunc
) NULL
,
162 klass
= (toporouter_vertex_class_t
*)gts_object_class_new (GTS_OBJECT_CLASS (gts_vertex_class ()), &constraint_info
);
169 toporouter_constraint_class_init (toporouter_constraint_class_t
*klass
)
175 toporouter_constraint_init (toporouter_constraint_t
*constraint
)
177 constraint
->box
= NULL
;
178 constraint
->routing
= NULL
;
181 toporouter_constraint_class_t
*
182 toporouter_constraint_class(void)
184 static toporouter_constraint_class_t
*klass
= NULL
;
187 GtsObjectClassInfo constraint_info
= {
188 "toporouter_constraint_t",
189 sizeof (toporouter_constraint_t
),
190 sizeof (toporouter_constraint_class_t
),
191 (GtsObjectClassInitFunc
) toporouter_constraint_class_init
,
192 (GtsObjectInitFunc
) toporouter_constraint_init
,
193 (GtsArgSetFunc
) NULL
,
196 klass
= (toporouter_constraint_class_t
*)gts_object_class_new (GTS_OBJECT_CLASS (gts_constraint_class ()), &constraint_info
);
203 toporouter_arc_init (toporouter_arc_t
*arc
)
215 arc
->clearance
= NULL
;
219 toporouter_arc_class_t
*
220 toporouter_arc_class(void)
222 static toporouter_arc_class_t
*klass
= NULL
;
225 GtsObjectClassInfo constraint_info
= {
227 sizeof (toporouter_arc_t
),
228 sizeof (toporouter_arc_class_t
),
229 (GtsObjectClassInitFunc
) NULL
,
230 (GtsObjectInitFunc
) toporouter_arc_init
,
231 (GtsArgSetFunc
) NULL
,
234 klass
= (toporouter_arc_class_t
*)gts_object_class_new (GTS_OBJECT_CLASS (gts_constraint_class ()), &constraint_info
);
243 toporouter_output_init(int w
, int h
, char *filename
)
245 drawing_context_t
*dc
;
247 dc
= (drawing_context_t
*)malloc(sizeof(drawing_context_t
));
251 dc
->filename
= filename
;
253 /* Calculate scaling to maintain aspect ratio */
254 if(PCB
->MaxWidth
> PCB
->MaxHeight
) {
255 /* Scale board width to match image width minus 2xMARGIN */
256 dc
->s
= ((double)dc
->iw
- (2 * MARGIN
)) / (double)PCB
->MaxWidth
;
257 dc
->ih
= (double)PCB
->MaxHeight
* dc
->s
+ (2 * MARGIN
);
259 /* Scale board height to match image height minus 2xMARGIN */
260 dc
->s
= ((double)dc
->ih
- (2 * MARGIN
)) / (double)PCB
->MaxHeight
;
261 dc
->iw
= (double)PCB
->MaxWidth
* dc
->s
+ (2 * MARGIN
);
264 #if TOPO_OUTPUT_ENABLED
265 dc
->surface
= cairo_image_surface_create(CAIRO_FORMAT_ARGB32
, dc
->iw
, dc
->ih
);
266 dc
->cr
= cairo_create (dc
->surface
);
268 cairo_rectangle (dc
->cr
, 0, 0, dc
->iw
, dc
->ih
);
269 cairo_set_source_rgb (dc
->cr
, 0, 0, 0);
278 toporouter_output_close(drawing_context_t
*dc
)
280 #if TOPO_OUTPUT_ENABLED
281 cairo_surface_write_to_png (dc
->surface
, dc
->filename
);
282 cairo_destroy (dc
->cr
);
283 cairo_surface_destroy (dc
->surface
);
288 lookup_keepaway(char *name
)
293 // if(!strcmp(style->Name, name)) return style->Keepaway + 1.;
294 if(!strcmp(style
->Name
, name
)) return style
->Keepaway
;
297 // return Settings.Keepaway + 1.;
298 return Settings
.Keepaway
;
302 lookup_thickness(char *name
)
307 if(!strcmp(style
->Name
, name
)) return style
->Thick
;
310 return Settings
.LineThickness
;
313 static inline gdouble
314 cluster_keepaway(toporouter_cluster_t
*cluster
)
316 if(cluster
) return lookup_keepaway(cluster
->netlist
->style
);
317 return lookup_keepaway(NULL
);
320 static inline gdouble
321 cluster_thickness(toporouter_cluster_t
*cluster
)
323 if(cluster
) return lookup_thickness(cluster
->netlist
->style
);
324 return lookup_thickness(NULL
);
328 toporouter_draw_vertex(gpointer item
, gpointer data
)
330 #if TOPO_OUTPUT_ENABLED
331 drawing_context_t
*dc
= (drawing_context_t
*) data
;
332 toporouter_vertex_t
*tv
;
337 if(TOPOROUTER_IS_VERTEX((GtsObject
*)item
)) {
338 tv
= TOPOROUTER_VERTEX((GtsObject
*)item
);
340 if(tv
->flags
& VERTEX_FLAG_RED
) {
341 cairo_set_source_rgba(dc
->cr
, 1., 0., 0., 0.8f
);
343 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
344 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
345 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
348 }else if(tv
->flags
& VERTEX_FLAG_GREEN
) {
349 cairo_set_source_rgba(dc
->cr
, 0., 1., 0., 0.8f
);
351 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
352 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
353 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
356 }else if(tv
->flags
& VERTEX_FLAG_BLUE
) {
357 cairo_set_source_rgba(dc
->cr
, 0., 0., 1., 0.8f
);
359 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
360 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
361 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
366 //printf("tv->type = %d\n", tv->type);
369 pin
= (PinType
*) tv
->bbox
->data
;
370 pad
= (PadType
*) tv
->bbox
->data
;
373 switch(tv
->bbox
->type
) {
375 cairo_set_source_rgba(dc
->cr
, 1.0f
, 0., 0.0f
, 0.2f
);
377 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
378 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
379 (((gdouble
)pin
->Thickness
/ 2.0f
) + (gdouble
)lookup_keepaway(pin
->Name
) ) * dc
->s
, 0, 2 * M_PI
);
382 cairo_set_source_rgba(dc
->cr
, 1.0f
, 0., 0., 0.4f
);
384 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
385 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
386 (gdouble
)(pin
->Thickness
) / 2.0f
* dc
->s
,
392 cairo_set_source_rgba(dc
->cr
, 0.0f
, 0., 1., 0.2f
);
394 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
395 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
396 (((gdouble
)pin
->Thickness
/ 2.0f
) + (gdouble
)lookup_keepaway(pin
->Name
) ) * dc
->s
, 0, 2 * M_PI
);
399 cairo_set_source_rgba(dc
->cr
, 0.0f
, 0., 1., 0.4f
);
401 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
402 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
403 (gdouble
)(pin
->Thickness
) / 2.0f
* dc
->s
,
409 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1., 0., 0.5f
);
411 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
412 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
413 MIL_TO_COORD (4.) * dc
->s
, 0, 2 * M_PI
);
422 if(tv
->flags
& VERTEX_FLAG_BLUE
) {
423 cairo_set_source_rgba(dc
->cr
, 0., 0., 1., 0.8f
);
425 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
426 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
427 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
429 }else if(tv
->flags
& VERTEX_FLAG_RED
) {
430 cairo_set_source_rgba(dc
->cr
, 1., 0., 0., 0.8f
);
432 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
433 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
434 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
437 }else if(tv
->flags
& VERTEX_FLAG_GREEN
) {
438 cairo_set_source_rgba(dc
->cr
, 0., 1., 0., 0.8f
);
440 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
441 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
442 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
448 fprintf(stderr
, "Unknown data passed to toporouter_draw_vertex, aborting foreach\n");
458 toporouter_draw_edge(gpointer item
, gpointer data
)
460 #if TOPO_OUTPUT_ENABLED
461 drawing_context_t
*dc
= (drawing_context_t
*) data
;
462 toporouter_edge_t
*te
;
463 toporouter_constraint_t
*tc
;
465 if(TOPOROUTER_IS_EDGE((GtsObject
*)item
)) {
466 te
= TOPOROUTER_EDGE((GtsObject
*)item
);
467 cairo_set_source_rgba(dc
->cr
, 1.0f
, 1.0f
, 1.0f
, 0.5f
);
468 cairo_move_to(dc
->cr
,
469 te
->e
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
470 te
->e
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
471 cairo_line_to(dc
->cr
,
472 te
->e
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
473 te
->e
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
474 cairo_stroke(dc
->cr
);
475 }else if(TOPOROUTER_IS_CONSTRAINT((GtsObject
*)item
)) {
476 tc
= TOPOROUTER_CONSTRAINT((GtsObject
*)item
);
478 switch(tc
->box
->type
) {
480 cairo_set_source_rgba(dc
->cr
, 1.0f
, 0.0f
, 1.0f
, 0.9f
);
481 cairo_move_to(dc
->cr
,
482 tc
->c
.edge
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
483 tc
->c
.edge
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
484 cairo_line_to(dc
->cr
,
485 tc
->c
.edge
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
486 tc
->c
.edge
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
487 cairo_stroke(dc
->cr
);
491 cairo_set_source_rgba(dc
->cr
, 1.0f
, 0.0f
, 0.0f
, 0.9f
);
492 cairo_move_to(dc
->cr
,
493 tc
->c
.edge
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
494 tc
->c
.edge
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
495 cairo_line_to(dc
->cr
,
496 tc
->c
.edge
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
497 tc
->c
.edge
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
498 cairo_stroke(dc
->cr
);
501 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1.0f
, 0.0f
, 0.9f
);
502 cairo_move_to(dc
->cr
,
503 tc
->c
.edge
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
504 tc
->c
.edge
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
505 cairo_line_to(dc
->cr
,
506 tc
->c
.edge
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
507 tc
->c
.edge
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
508 cairo_stroke(dc
->cr
);
512 cairo_set_source_rgba(dc
->cr
, 1.0f
, 1.0f
, 0.0f
, 0.9f
);
513 cairo_move_to(dc
->cr
,
514 tc
->c
.edge
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
515 tc
->c
.edge
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
516 cairo_line_to(dc
->cr
,
517 tc
->c
.edge
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
518 tc
->c
.edge
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
519 cairo_stroke(dc
->cr
);
523 printf("CONSTRAINT without box\n");
527 fprintf(stderr
, "Unknown data passed to toporouter_draw_edge, aborting foreach\n");
537 //#define vertex_bbox(v) (v->bbox)
540 vertex_bbox(toporouter_vertex_t
*v
)
542 return v
? v
->bbox
: NULL
;
546 vertex_netlist(toporouter_vertex_t
*v
)
548 toporouter_bbox_t
*box
= vertex_bbox(v
);
550 if(box
&& box
->cluster
) return box
->cluster
->netlist
->netlist
;
556 constraint_netlist(toporouter_constraint_t
*c
)
558 toporouter_bbox_t
*box
= c
->box
;
560 if(box
&& box
->cluster
) return box
->cluster
->netlist
->netlist
;
566 epsilon_equals(gdouble a
, gdouble b
)
568 if(a
> b
- EPSILON
&& a
< b
+ EPSILON
) return 1;
573 print_bbox(toporouter_bbox_t
*box
)
578 printf("PAD "); break;
580 printf("PIN "); break;
582 printf("VIA "); break;
584 printf("LINE "); break;
586 printf("BOARD "); break;
588 printf("POLYGON "); break;
590 printf("UNKNOWN "); break;
594 printf("P: %f,%f,%f ", vx(box
->point
), vy(box
->point
), vz(box
->point
));
598 printf("LAYER: %d ", box
->layer
);
599 printf("CLUSTER: %d]\n", box
->cluster
? box
->cluster
->c
: -1);
604 print_vertex(toporouter_vertex_t
*v
)
607 printf("[V %f,%f,%f ", vx(v
), vy(v
), vz(v
));
609 printf("[V (null) ");
611 printf("%s ", vertex_netlist(v
));
612 if(v
->route
&& v
->route
->netlist
)
613 printf("%s ", v
->route
->netlist
->netlist
);
616 guint n
= g_list_length(edge_routing(v
->routingedge
));
617 guint pos
= g_list_index(edge_routing(v
->routingedge
), v
);
619 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
624 printf("%d/%d] ", pos
, n
);
629 if(v
->flags
& VERTEX_FLAG_TEMP
) printf("TEMP ");
630 if(v
->flags
& VERTEX_FLAG_ROUTE
) printf("ROUTE ");
631 if(v
->flags
& VERTEX_FLAG_SPECCUT
) printf("SPECCUT ");
632 if(v
->flags
& VERTEX_FLAG_FAKE
) printf("FAKE ");
639 vertex_net_thickness(toporouter_vertex_t
*v
)
641 toporouter_bbox_t
*box
= vertex_bbox(v
);
645 while(v
&& (v
->flags
& VERTEX_FLAG_TEMP
|| v
->flags
& VERTEX_FLAG_ROUTE
)) {
649 box
= vertex_bbox(v
);
652 if(box
->type
== PIN
|| box
->type
== VIA
) {
653 PinType
*pin
= (PinType
*)box
->data
;
654 if(TEST_FLAG(SQUAREFLAG
, pin
) || TEST_FLAG(OCTAGONFLAG
, pin
)) {
657 // return ((PinType *)box->data)->Thickness + 1.;
658 return ((PinType
*)box
->data
)->Thickness
;
659 }else if(box
->type
== PAD
) {
660 PadType
*pad
= (PadType
*)box
->data
;
661 if(pad
->Point1
.X
== pad
->Point2
.X
&& pad
->Point1
.Y
== pad
->Point2
.Y
&& !TEST_FLAG(SQUAREFLAG
, pad
)) {
662 return pad
->Thickness
;
665 }else if(box
->type
== BOARD
) {
667 }else if(box
->type
== LINE
) {
668 LineType
*line
= (LineType
*) box
->data
;
669 return line
->Thickness
;
670 }else if(box
->type
== POLYGON
) {
674 printf("Unrecognized type in thickness lookup..\n");
677 // if(!box || !box->cluster) return Settings.LineThickness + 1.;
678 if(!box
|| !box
->cluster
) return Settings
.LineThickness
;
680 return cluster_thickness(box
->cluster
);
684 vertex_net_keepaway(toporouter_vertex_t
*v
)
686 toporouter_bbox_t
*box
= vertex_bbox(v
);
689 while(v
&& (v
->flags
& VERTEX_FLAG_TEMP
|| v
->flags
& VERTEX_FLAG_ROUTE
)) {
692 box
= vertex_bbox(v
);
695 // if(box->type == PIN || box->type == VIA)
696 // return ((PinType *)box->data)->Clearance;
697 // else if(box->type == PAD)
698 // return ((PadType *)box->data)->Clearance;
702 // if(!box || !box->cluster) return Settings.Keepaway + 1.;
703 if(!box
|| !box
->cluster
) return Settings
.Keepaway
;
704 return cluster_keepaway(box
->cluster
);
707 /* fills in x and y with coordinates of point from a towards b of distance d */
709 point_from_point_to_point (toporouter_vertex_t
*a
,
710 toporouter_vertex_t
*b
,
712 double *x
, double *y
)
714 double theta
= atan2 (vy(b
) - vy(a
), vx(b
) - vx(a
));
716 *x
= vx(a
) + d
* cos (theta
);
717 *y
= vy(a
) + d
* sin (theta
);
721 coord_wind(gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
, gdouble cx
, gdouble cy
)
723 gdouble rval
, dx1
, dx2
, dy1
, dy2
;
724 dx1
= bx
- ax
; dy1
= by
- ay
;
725 dx2
= cx
- bx
; dy2
= cy
- by
;
726 rval
= (dx1
*dy2
)-(dy1
*dx2
);
727 return (rval
> EPSILON
) ? 1 : ((rval
< -EPSILON
) ? -1 : 0);
731 * returns 1,0,-1 for counterclockwise, collinear or clockwise, respectively.
734 point_wind(GtsPoint
*a
, GtsPoint
*b
, GtsPoint
*c
)
736 gdouble rval
, dx1
, dx2
, dy1
, dy2
;
737 dx1
= b
->x
- a
->x
; dy1
= b
->y
- a
->y
;
738 dx2
= c
->x
- b
->x
; dy2
= c
->y
- b
->y
;
739 rval
= (dx1
*dy2
)-(dy1
*dx2
);
740 return (rval
> EPSILON
) ? 1 : ((rval
< -EPSILON
) ? -1 : 0);
744 vertex_wind(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
)
746 return point_wind(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
));
750 tvertex_wind(toporouter_vertex_t
*a
, toporouter_vertex_t
*b
, toporouter_vertex_t
*c
)
752 return point_wind(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
));
755 /* moves vertex v d units in the direction of vertex p */
757 coord_move_towards_coord_values (double ax
, double ay
,
758 double px
, double py
,
760 double *x
, double *y
)
762 double theta
= atan2 (py
- ay
, px
- ax
);
764 *x
= ax
+ d
* cos (theta
);
765 *y
= ay
+ d
* sin (theta
);
768 /* moves vertex v d units in the direction of vertex p */
770 vertex_move_towards_vertex_values (GtsVertex
*v
,
773 double *x
, double *y
)
775 double theta
= atan2 (GTS_POINT(p
)->y
- GTS_POINT(v
)->y
,
776 GTS_POINT(p
)->x
- GTS_POINT(v
)->x
);
778 *x
= GTS_POINT(v
)->x
+ d
* cos (theta
);
779 *y
= GTS_POINT(v
)->y
+ d
* sin (theta
);
782 #define tv_on_layer(v,l) (l == TOPOROUTER_BBOX(TOPOROUTER_VERTEX(v)->boxes->data)->layer)
784 static inline gdouble
785 min_spacing(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
788 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
789 // toporouter_edge_t *e = v1->routingedge;
791 v1halfthick
= vertex_net_thickness(TOPOROUTER_VERTEX(v1
)) / 2.;
792 v2halfthick
= vertex_net_thickness(TOPOROUTER_VERTEX(v2
)) / 2.;
794 v1keepaway
= vertex_net_keepaway(TOPOROUTER_VERTEX(v1
));
795 v2keepaway
= vertex_net_keepaway(TOPOROUTER_VERTEX(v2
));
797 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
800 printf("v1halfthick = %f v2halfthick = %f v1keepaway = %f v2keepaway = %f ms = %f\n",
801 v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
);
807 // v1 is a vertex in the CDT, and v2 is a net... other way around?
808 static inline gdouble
809 min_vertex_net_spacing(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
812 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
814 v1halfthick
= vertex_net_thickness(TOPOROUTER_VERTEX(v1
)) / 2.;
815 v2halfthick
= cluster_thickness(vertex_bbox(v2
)->cluster
) / 2.;
817 v1keepaway
= vertex_net_keepaway(TOPOROUTER_VERTEX(v1
));
818 v2keepaway
= cluster_keepaway(vertex_bbox(v2
)->cluster
);
820 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
825 static inline gdouble
826 min_oproute_vertex_spacing(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v2
)
829 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
831 v1halfthick
= lookup_thickness(oproute
->style
) / 2.;
832 v2halfthick
= vertex_net_thickness(v2
) / 2.;
834 v1keepaway
= lookup_keepaway(oproute
->style
);
835 v2keepaway
= vertex_net_keepaway(v2
);
837 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
843 min_oproute_net_spacing(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v2
)
846 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
848 v1halfthick
= lookup_thickness(oproute
->style
) / 2.;
849 v2halfthick
= cluster_thickness(v2
->route
->src
) / 2.;
851 v1keepaway
= lookup_keepaway(oproute
->style
);
852 v2keepaway
= cluster_keepaway(v2
->route
->src
);
854 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
860 min_net_net_spacing(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
863 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
865 v1halfthick
= cluster_thickness(v1
->route
->src
) / 2.;
866 v2halfthick
= cluster_thickness(v2
->route
->src
) / 2.;
868 v1keepaway
= cluster_keepaway(v1
->route
->src
);
869 v2keepaway
= cluster_keepaway(v2
->route
->src
);
871 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
877 toporouter_draw_cluster(toporouter_t
*r
, drawing_context_t
*dc
, toporouter_cluster_t
*cluster
, gdouble red
, gdouble green
, gdouble blue
, guint layer
)
879 #if TOPO_OUTPUT_ENABLED
880 //GList *i = cluster->i;
883 // toporouter_bbox_t *box = TOPOROUTER_BBOX(i->data);
885 // if(box->point && vz(box->point) == layer) {
886 // cairo_set_source_rgba(dc->cr, red, green, blue, 0.8f);
887 // cairo_arc(dc->cr, vx(box->point) * dc->s + MARGIN, vy(box->point) * dc->s + MARGIN, MIL_TO_COORD (5.) * dc->s, 0, 2 * M_PI);
888 // cairo_fill(dc->cr);
897 toporouter_draw_surface(toporouter_t
*r
, GtsSurface
*s
, char *filename
, int w
, int h
, int mode
, GList
*datas
, int layer
, GList
*candidatepoints
)
899 #if TOPO_OUTPUT_ENABLED
900 drawing_context_t
*dc
;
902 toporouter_vertex_t
*tv
, *tv2
= NULL
;
904 dc
= toporouter_output_init(w
, h
, filename
);
908 gts_surface_foreach_edge(s
, toporouter_draw_edge
, dc
);
909 gts_surface_foreach_vertex(s
, toporouter_draw_vertex
, dc
);
913 GList
*j
= TOPOROUTER_ROUTE(i
->data
)->path
;
916 tv
= TOPOROUTER_VERTEX(j
->data
);
917 if(GTS_POINT(tv
)->z
== layer
) {
919 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1.0f
, 0.0f
, 0.8f
);
920 cairo_move_to(dc
->cr
,
921 GTS_POINT(tv
)->x
* dc
->s
+ MARGIN
,
922 GTS_POINT(tv
)->y
* dc
->s
+ MARGIN
);
923 cairo_line_to(dc
->cr
,
924 GTS_POINT(tv2
)->x
* dc
->s
+ MARGIN
,
925 GTS_POINT(tv2
)->y
* dc
->s
+ MARGIN
);
926 cairo_stroke(dc
->cr
);
929 if(tv
->flags
& VERTEX_FLAG_RED
) {
930 cairo_set_source_rgba(dc
->cr
, 1., 0., 0., 0.8f
);
932 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
933 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
934 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
937 }else if(tv
->flags
& VERTEX_FLAG_GREEN
) {
938 cairo_set_source_rgba(dc
->cr
, 0., 1., 0., 0.8f
);
940 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
941 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
942 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
945 }else if(tv
->flags
& VERTEX_FLAG_BLUE
) {
946 cairo_set_source_rgba(dc
->cr
, 0., 0., 1., 0.8f
);
948 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
949 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
950 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
956 cairo_set_source_rgba(dc
->cr
, 1., 1., 1., 0.8f
);
958 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
959 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
960 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
966 if(tv
->routingedge
&& !TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
)) {
967 gdouble tempx
, tempy
, nms
, pms
;
968 GList
*i
= g_list_find(edge_routing(tv
->routingedge
), tv
);
969 toporouter_vertex_t
*nextv
, *prevv
;
971 nextv
= edge_routing_next(tv
->routingedge
,i
);
972 prevv
= edge_routing_prev(tv
->routingedge
,i
);
974 nms
= min_spacing(tv
,nextv
);
975 pms
= min_spacing(tv
,prevv
);
977 g_assert(finite(nms
)); g_assert(finite(pms
));
979 point_from_point_to_point(tv
, nextv
, nms
, &tempx
, &tempy
);
981 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1.0f
, 1.0f
, 0.8f
);
982 cairo_move_to(dc
->cr
, vx(tv
) * dc
->s
+ MARGIN
, vy(tv
) * dc
->s
+ MARGIN
);
983 cairo_line_to(dc
->cr
, tempx
* dc
->s
+ MARGIN
, tempy
* dc
->s
+ MARGIN
);
984 cairo_stroke(dc
->cr
);
986 point_from_point_to_point(tv
, prevv
, pms
, &tempx
, &tempy
);
988 cairo_move_to(dc
->cr
, vx(tv
) * dc
->s
+ MARGIN
, vy(tv
) * dc
->s
+ MARGIN
);
989 cairo_line_to(dc
->cr
, tempx
* dc
->s
+ MARGIN
, tempy
* dc
->s
+ MARGIN
);
990 cairo_stroke(dc
->cr
);
1006 toporouter_route_t
*routedata
= (toporouter_route_t
*) datas
->data
;
1010 toporouter_draw_cluster(r
, dc
, routedata
->src
, 1., 0., 0., layer
);
1011 toporouter_draw_cluster(r
, dc
, routedata
->dest
, 0., 0., 1., layer
);
1014 i
= routedata
->path
;
1016 tv
= TOPOROUTER_VERTEX(i
->data
);
1017 if(GTS_POINT(tv
)->z
== layer
) {
1019 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1.0f
, 0.0f
, 0.8f
);
1020 cairo_move_to(dc
->cr
,
1021 GTS_POINT(tv
)->x
* dc
->s
+ MARGIN
,
1022 GTS_POINT(tv
)->y
* dc
->s
+ MARGIN
);
1023 cairo_line_to(dc
->cr
,
1024 GTS_POINT(tv2
)->x
* dc
->s
+ MARGIN
,
1025 GTS_POINT(tv2
)->y
* dc
->s
+ MARGIN
);
1026 cairo_stroke(dc
->cr
);
1034 if(routedata
->alltemppoints
) {
1036 i
= j
= g_hash_table_get_keys (routedata
->alltemppoints
);
1038 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
1040 if(GTS_POINT(tv
)->z
!= layer
) {
1044 if(tv
->flags
& VERTEX_FLAG_BLUE
) {
1045 cairo_set_source_rgba(dc
->cr
, 0., 0., 1., 0.8f
);
1047 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1048 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1049 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
1051 }else if(tv
->flags
& VERTEX_FLAG_RED
) {
1052 cairo_set_source_rgba(dc
->cr
, 1., 0., 0., 0.8f
);
1054 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1055 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1056 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
1059 }else if(tv
->flags
& VERTEX_FLAG_GREEN
) {
1060 cairo_set_source_rgba(dc
->cr
, 0., 1., 0., 0.8f
);
1062 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1063 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1064 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
1067 cairo_set_source_rgba(dc
->cr
, 1., 1., 1., 0.8f
);
1069 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1070 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1071 MIL_TO_COORD (5.) * dc
->s
, 0, 2 * M_PI
);
1078 datas
= datas
->next
;
1080 toporouter_output_close(dc
);
1086 toporouter_layer_free(toporouter_layer_t
*l
)
1088 g_list_free(l
->vertices
);
1089 g_list_free(l
->constraints
);
1099 for (group
= 0; group
< max_group
; group
++) {
1100 if(PCB
->LayerGroups
.Number
[group
] > 0) count
++;
1107 toporouter_free(toporouter_t
*r
)
1109 struct timeval endtime
;
1113 for(i
=0;i
<groupcount();i
++) {
1114 toporouter_layer_free(&r
->layers
[i
]);
1117 gettimeofday (&endtime
, NULL
);
1118 time_delta
= endtime
.tv_sec
- r
->starttime
.tv_sec
+
1119 (endtime
.tv_usec
- r
->starttime
.tv_usec
) / 1000000.;
1121 Message(_("Elapsed time: %.2f seconds\n"), time_delta
);
1128 * returns 1,0,-1 for counterclockwise, collinear or clockwise, respectively.
1131 wind(toporouter_spoint_t
*p1
, toporouter_spoint_t
*p2
, toporouter_spoint_t
*p3
)
1133 double rval
, dx1
, dx2
, dy1
, dy2
;
1134 dx1
= p2
->x
- p1
->x
; dy1
= p2
->y
- p1
->y
;
1135 dx2
= p3
->x
- p2
->x
; dy2
= p3
->y
- p2
->y
;
1136 rval
= (dx1
*dy2
)-(dy1
*dx2
);
1137 return (rval
> 0.0001) ? 1 : ((rval
< -0.0001) ? -1 : 0); /* XXX: Depends on PCB coordinate scaling */
1141 print_toporouter_constraint(toporouter_constraint_t
*tc
)
1143 printf("%f,%f -> %f,%f ",
1144 tc
->c
.edge
.segment
.v1
->p
.x
,
1145 tc
->c
.edge
.segment
.v1
->p
.y
,
1146 tc
->c
.edge
.segment
.v2
->p
.x
,
1147 tc
->c
.edge
.segment
.v2
->p
.y
);
1151 print_toporouter_vertex(toporouter_vertex_t
*tv
)
1153 printf("%f,%f ", tv
->v
.p
.x
, tv
->v
.p
.y
);
1159 * Given vertex a, gradient m, and radius r:
1161 * Return vertices on line of a & m at r from a
1164 vertices_on_line (toporouter_spoint_t
*a
,
1167 toporouter_spoint_t
*b0
,
1168 toporouter_spoint_t
*b1
)
1173 if (m
== INFINITY
|| m
== -INFINITY
) {
1184 c
= a
->y
- m
* a
->x
;
1185 dx
= r
/ sqrt (1 + pow (m
, 2));
1188 b0
->y
= m
* b0
->x
+ c
;
1191 b1
->y
= m
* b1
->x
+ c
;
1196 * Given coordinates ax, ay, gradient m, and radius r:
1198 * Return coordinates on line of a & m at r from a
1201 coords_on_line (double ax
, gdouble ay
,
1204 double *b0x
, double *b0y
,
1205 double *b1x
, double *b1y
)
1209 if (m
== INFINITY
|| m
== -INFINITY
) {
1221 dx
= r
/ sqrt (1 + pow (m
, 2));
1224 *b0y
= m
* *b0x
+ c
;
1227 *b1y
= m
* *b1x
+ c
;
1231 * Returns gradient of segment given by a & b
1234 vertex_gradient(toporouter_spoint_t
*a
, toporouter_spoint_t
*b
)
1236 if(a
->x
== b
->x
) return INFINITY
;
1238 return ((b
->y
- a
->y
) / (b
->x
- a
->x
));
1242 * Returns gradient of segment given by (x0,y0) & (x1,y1)
1244 static inline gdouble
1245 cartesian_gradient(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
)
1247 if(epsilon_equals(x0
,x1
)) return INFINITY
;
1249 return ((y1
- y0
) / (x1
- x0
));
1253 * Returns gradient of segment given by (x0,y0) & (x1,y1)
1255 static inline gdouble
1256 point_gradient(GtsPoint
*a
, GtsPoint
*b
)
1258 return cartesian_gradient(a
->x
, a
->y
, b
->x
, b
->y
);
1262 segment_gradient(GtsSegment
*s
)
1264 return cartesian_gradient(
1265 GTS_POINT(s
->v1
)->x
,
1266 GTS_POINT(s
->v1
)->y
,
1267 GTS_POINT(s
->v2
)->x
,
1268 GTS_POINT(s
->v2
)->y
);
1272 * Returns gradient perpendicular to m
1275 perpendicular_gradient(gdouble m
)
1277 if(isinf(m
)) return 0.0f
;
1278 if(m
< EPSILON
&& m
> -EPSILON
) return INFINITY
;
1283 * Returns the distance between two vertices in the x-y plane
1286 vertices_plane_distance(toporouter_spoint_t
*a
, toporouter_spoint_t
*b
) {
1287 return sqrt( pow(a
->x
- b
->x
, 2) + pow(a
->y
- b
->y
, 2) );
1291 * Finds the point p distance r away from a on the line segment of a & b
1294 vertex_outside_segment(toporouter_spoint_t
*a
, toporouter_spoint_t
*b
, gdouble r
, toporouter_spoint_t
*p
)
1296 toporouter_spoint_t temp
[2];
1298 vertices_on_line(a
, vertex_gradient(a
,b
), r
, &temp
[0], &temp
[1]);
1300 if(vertices_plane_distance(&temp
[0], b
) > vertices_plane_distance(&temp
[1], b
)) {
1310 /* proper intersection:
1311 * AB and CD must share a point interior to both segments.
1312 * returns TRUE if AB properly intersects CD.
1315 coord_intersect_prop (double ax
, double ay
,
1316 double bx
, double by
,
1317 double cx
, double cy
,
1318 double dx
, double dy
)
1320 int wind_abc
= coord_wind (ax
, ay
, bx
, by
, cx
, cy
);
1321 int wind_abd
= coord_wind (ax
, ay
, bx
, by
, dx
, dy
);
1322 int wind_cda
= coord_wind (cx
, cy
, dx
, dy
, ax
, ay
);
1323 int wind_cdb
= coord_wind (cx
, cy
, dx
, dy
, bx
, by
);
1325 /* If any of the line end-points are colinear with the other line, return false */
1326 if (wind_abc
== 0 || wind_abd
== 0 || wind_cda
== 0 || wind_cdb
== 0)
1329 return (wind_abc
!= wind_abd
) && (wind_cda
!= wind_cdb
);
1332 /* proper intersection:
1333 * AB and CD must share a point interior to both segments.
1334 * returns TRUE if AB properly intersects CD.
1337 point_intersect_prop (GtsPoint
*a
, GtsPoint
*b
, GtsPoint
*c
, GtsPoint
*d
)
1339 int wind_abc
= point_wind (a
, b
, c
);
1340 int wind_abd
= point_wind (a
, b
, d
);
1341 int wind_cda
= point_wind (c
, d
, a
);
1342 int wind_cdb
= point_wind (c
, d
, b
);
1344 /* If any of the line end-points are colinear with the other line, return false */
1345 if (wind_abc
== 0 || wind_abd
== 0 || wind_cda
== 0 || wind_cdb
== 0)
1348 return (wind_abc
!= wind_abd
) && (wind_cda
!= wind_cdb
);
1352 vertex_intersect_prop(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
, GtsVertex
*d
)
1354 return point_intersect_prop(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
), GTS_POINT(d
));
1357 /* intersection vertex:
1358 * AB and CD must share a point interior to both segments.
1359 * returns vertex at intersection of AB and CD.
1362 vertex_intersect(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
, GtsVertex
*d
)
1364 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1366 gdouble ua_top
, ua_bot
, ua
, rx
, ry
;
1368 /* TODO: this could be done more efficiently without duplicating computation */
1369 if(!vertex_intersect_prop(a
, b
, c
, d
)) return NULL
;
1371 ua_top
= ((d
->p
.x
- c
->p
.x
) * (a
->p
.y
- c
->p
.y
)) -
1372 ((d
->p
.y
- c
->p
.y
) * (a
->p
.x
- c
->p
.x
));
1373 ua_bot
= ((d
->p
.y
- c
->p
.y
) * (b
->p
.x
- a
->p
.x
)) -
1374 ((d
->p
.x
- c
->p
.x
) * (b
->p
.y
- a
->p
.y
));
1375 ua
= ua_top
/ ua_bot
;
1376 rx
= a
->p
.x
+ (ua
* (b
->p
.x
- a
->p
.x
));
1377 ry
= a
->p
.y
+ (ua
* (b
->p
.y
- a
->p
.y
));
1379 rval
= gts_vertex_new (vertex_class
, rx
, ry
, 0.0f
);
1384 /* intersection vertex:
1385 * AB and CD must share a point interior to both segments.
1386 * returns vertex at intersection of AB and CD.
1389 coord_intersect(gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
, gdouble cx
, gdouble cy
, gdouble dx
, gdouble dy
, gdouble
*rx
, gdouble
*ry
)
1391 gdouble ua_top
, ua_bot
, ua
;
1393 ua_top
= ((dx
- cx
) * (ay
- cy
)) - ((dy
- cy
) * (ax
- cx
));
1394 ua_bot
= ((dy
- cy
) * (bx
- ax
)) - ((dx
- cx
) * (by
- ay
));
1395 ua
= ua_top
/ ua_bot
;
1396 *rx
= ax
+ (ua
* (bx
- ax
));
1397 *ry
= ay
+ (ua
* (by
- ay
));
1403 * returns true if c is between a and b
1406 point_between(GtsPoint
*a
, GtsPoint
*b
, GtsPoint
*c
)
1408 if( point_wind(a
, b
, c
) != 0 ) return 0;
1410 if( a
->x
!= b
->x
) {
1411 return ((a
->x
<= c
->x
) &&
1416 return ((a
->y
<= c
->y
) &&
1423 vertex_between(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
)
1425 return point_between(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
));
1429 delaunay_create_from_vertices(GList
*vertices
, GtsSurface
**surface
, GtsTriangle
**t
)
1431 GList
*i
= vertices
;
1432 GtsVertex
*v1
, *v2
, *v3
;
1433 GSList
*vertices_slist
= NULL
;
1436 vertices_slist
= g_slist_prepend(vertices_slist
, i
->data
);
1440 // TODO: just work this out from the board outline
1441 *t
= gts_triangle_enclosing (gts_triangle_class (), vertices_slist
, 100000.0f
);
1442 gts_triangle_vertices (*t
, &v1
, &v2
, &v3
);
1444 *surface
= gts_surface_new (gts_surface_class (), gts_face_class (),
1445 GTS_EDGE_CLASS(toporouter_edge_class ()), GTS_VERTEX_CLASS(toporouter_vertex_class ()) );
1447 gts_surface_add_face (*surface
, gts_face_new (gts_face_class (), (*t
)->e1
, (*t
)->e2
, (*t
)->e3
));
1451 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(gts_delaunay_add_vertex (*surface
, (GtsVertex
*)i
->data
, NULL
));
1454 printf("ERROR: vertex could not be added to CDT ");
1461 gts_allow_floating_vertices
= TRUE
;
1462 gts_object_destroy (GTS_OBJECT (v1
));
1463 gts_object_destroy (GTS_OBJECT (v2
));
1464 gts_object_destroy (GTS_OBJECT (v3
));
1465 gts_allow_floating_vertices
= FALSE
;
1467 g_slist_free(vertices_slist
);
1472 list_to_slist(GList
*i
)
1474 GSList
*rval
= NULL
;
1476 rval
= g_slist_prepend(rval
, i
->data
);
1483 toporouter_bbox_create_from_points(int layer
, GList
*vertices
, toporouter_term_t type
, gpointer data
)
1485 toporouter_bbox_t
*bbox
;
1486 GSList
*vertices_slist
= list_to_slist(vertices
);
1488 // delaunay_create_from_vertices(vertices, &s, &t);
1489 bbox
= TOPOROUTER_BBOX( gts_bbox_points(GTS_BBOX_CLASS(toporouter_bbox_class()), vertices_slist
) );
1493 bbox
->surface
= NULL
;
1494 bbox
->enclosing
= NULL
;
1496 bbox
->layer
= layer
;
1499 bbox
->realpoint
= NULL
;
1501 g_slist_free(vertices_slist
);
1506 toporouter_bbox_create(int layer
, GList
*vertices
, toporouter_term_t type
, gpointer data
)
1508 toporouter_bbox_t
*bbox
;
1512 delaunay_create_from_vertices(vertices
, &s
, &t
);
1513 bbox
= TOPOROUTER_BBOX( gts_bbox_surface(GTS_BBOX_CLASS(toporouter_bbox_class()), s
) );
1518 bbox
->enclosing
= t
;
1520 bbox
->layer
= layer
;
1526 insert_vertex(toporouter_t
*r
, toporouter_layer_t
*l
, gdouble x
, gdouble y
, toporouter_bbox_t
*box
)
1528 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1534 v
= (GtsVertex
*)i
->data
;
1535 if(v
->p
.x
== x
&& v
->p
.y
== y
) {
1536 TOPOROUTER_VERTEX(v
)->bbox
= box
;
1542 v
= gts_vertex_new (vertex_class
, x
, y
, l
- r
->layers
);
1543 TOPOROUTER_VERTEX(v
)->bbox
= box
;
1544 l
->vertices
= g_list_prepend(l
->vertices
, v
);
1550 insert_constraint_edge(toporouter_t
*r
, toporouter_layer_t
*l
, gdouble x1
, gdouble y1
, guint flags1
,
1551 gdouble x2
, gdouble y2
, guint flags2
, toporouter_bbox_t
*box
)
1553 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1554 GtsEdgeClass
*edge_class
= GTS_EDGE_CLASS (toporouter_constraint_class ());
1562 /* insert or find points */
1566 v
= (GtsVertex
*)i
->data
;
1567 if(v
->p
.x
== x1
&& v
->p
.y
== y1
)
1569 if(v
->p
.x
== x2
&& v
->p
.y
== y2
)
1575 p
[0] = gts_vertex_new (vertex_class
, x1
, y1
, l
- r
->layers
);
1576 TOPOROUTER_VERTEX(p
[0])->bbox
= box
;
1577 l
->vertices
= g_list_prepend(l
->vertices
, p
[0]);
1580 p
[1] = gts_vertex_new (vertex_class
, x2
, y2
, l
- r
->layers
);
1581 TOPOROUTER_VERTEX(p
[1])->bbox
= box
;
1582 l
->vertices
= g_list_prepend(l
->vertices
, p
[1]);
1585 TOPOROUTER_VERTEX(p
[0])->flags
= flags1
;
1586 TOPOROUTER_VERTEX(p
[1])->flags
= flags2
;
1588 e
= gts_edge_new (edge_class
, p
[0], p
[1]);
1589 TOPOROUTER_CONSTRAINT(e
)->box
= box
;
1590 l
->constraints
= g_list_prepend (l
->constraints
, e
);
1591 // return insert_constraint_edge_rec(r, l, p, box);
1592 return g_list_prepend(NULL
, e
);
1597 insert_constraints_from_list(toporouter_t
*r
, toporouter_layer_t
*l
, GList
*vlist
, toporouter_bbox_t
*box
)
1600 toporouter_vertex_t
*pv
= NULL
, *v
;
1603 v
= TOPOROUTER_VERTEX(i
->data
);
1607 g_list_concat(box
->constraints
, insert_constraint_edge(r
, l
, vx(v
), vy(v
), v
->flags
, vx(pv
), vy(pv
), pv
->flags
, box
));
1614 v
= TOPOROUTER_VERTEX(vlist
->data
);
1616 g_list_concat(box
->constraints
, insert_constraint_edge(r
, l
, vx(v
), vy(v
), v
->flags
, vx(pv
), vy(pv
), pv
->flags
, box
));
1621 insert_centre_point(toporouter_t
*r
, toporouter_layer_t
*l
, gdouble x
, gdouble y
)
1624 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1628 GtsPoint
*p
= GTS_POINT(i
->data
);
1629 if(p
->x
== x
&& p
->y
== y
)
1634 l
->vertices
= g_list_prepend(l
->vertices
, gts_vertex_new(vertex_class
, x
, y
, 0.0f
));
1638 midpoint(GtsPoint
*a
, GtsPoint
*b
)
1640 return gts_point_new(gts_point_class(), (a
->x
+ b
->x
) / 2., (a
->y
+ b
->y
) / 2., 0.);
1643 static inline gdouble
1644 pad_rad(PadType
*pad
)
1646 return (lookup_thickness(pad
->Name
) / 2.) + lookup_keepaway(pad
->Name
);
1649 static inline gdouble
1650 pin_rad(PinType
*pin
)
1652 return (lookup_thickness(pin
->Name
) / 2.) + lookup_keepaway(pin
->Name
);
1656 rect_with_attachments(gdouble rad
,
1657 gdouble x0
, gdouble y0
,
1658 gdouble x1
, gdouble y1
,
1659 gdouble x2
, gdouble y2
,
1660 gdouble x3
, gdouble y3
,
1663 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1664 GList
*r
= NULL
, *rr
= NULL
, *i
;
1665 toporouter_vertex_t
*curpoint
, *temppoint
;
1668 curpoint
= TOPOROUTER_VERTEX(gts_vertex_new (vertex_class
, x0
, y0
, z
));
1670 r
= g_list_prepend(NULL
, curpoint
);
1671 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x1
, y1
, z
));
1672 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x2
, y2
, z
));
1673 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x3
, y3
, z
));
1677 temppoint
= TOPOROUTER_VERTEX(i
->data
);
1678 rr
= g_list_prepend(rr
, curpoint
);
1680 curpoint
= temppoint
;
1689 #define VERTEX_CENTRE(x) TOPOROUTER_VERTEX( vertex_bbox(x)->point )
1692 * Read pad data from layer into toporouter_layer_t struct
1694 * Inserts points and constraints into GLists
1697 read_pads(toporouter_t
*r
, toporouter_layer_t
*l
, guint layer
)
1699 toporouter_spoint_t p
[2], rv
[5];
1700 gdouble x
[2], y
[2], t
, m
;
1702 GList
*vlist
= NULL
;
1703 toporouter_bbox_t
*bbox
= NULL
;
1705 guint front
= GetLayerGroupNumberByNumber (component_silk_layer
);
1706 guint back
= GetLayerGroupNumberByNumber (solder_silk_layer
);
1708 // printf("read_pads: front = %d back = %d layer = %d\n",
1709 // front, back, layer);
1711 /* If its not the top or bottom layer, there are no pads to read */
1712 if(l
- r
->layers
!= front
&& l
- r
->layers
!= back
) return 0;
1714 ELEMENT_LOOP(PCB
->Data
);
1718 if( (l
- r
->layers
== back
&& TEST_FLAG(ONSOLDERFLAG
, pad
)) ||
1719 (l
- r
->layers
== front
&& !TEST_FLAG(ONSOLDERFLAG
, pad
)) ) {
1721 t
= (gdouble
)pad
->Thickness
/ 2.0f
;
1722 x
[0] = pad
->Point1
.X
;
1723 x
[1] = pad
->Point2
.X
;
1724 y
[0] = pad
->Point1
.Y
;
1725 y
[1] = pad
->Point2
.Y
;
1728 if(TEST_FLAG(SQUAREFLAG
, pad
)) {
1729 /* Square or oblong pad. Four points and four constraint edges are
1732 if(x
[0] == x
[1] && y
[0] == y
[1]) {
1735 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, x[0]-t, y[0]-t, 0.));
1736 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]-t, y[0]+t, 0.));
1737 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]+t, y[0]+t, 0.));
1738 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]+t, y[0]-t, 0.));
1739 vlist
= rect_with_attachments(pad_rad(pad
),
1745 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
1746 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1747 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1750 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, x[0], y[0], 0.) );
1751 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
[0], y
[0], bbox
) );
1752 g_assert(TOPOROUTER_VERTEX(bbox
->point
)->bbox
== bbox
);
1754 /* Pad is diagonal oblong or othogonal oblong */
1756 m
= cartesian_gradient(x
[0], y
[0], x
[1], y
[1]);
1758 p
[0].x
= x
[0]; p
[0].y
= y
[0];
1759 p
[1].x
= x
[1]; p
[1].y
= y
[1];
1761 vertex_outside_segment(&p
[0], &p
[1], t
, &rv
[0]);
1762 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[1], &rv
[2]);
1764 vertex_outside_segment(&p
[1], &p
[0], t
, &rv
[0]);
1765 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[3], &rv
[4]);
1767 if(wind(&rv
[1], &rv
[2], &rv
[3]) != wind(&rv
[2], &rv
[3], &rv
[4])) {
1768 rv
[0].x
= rv
[3].x
; rv
[0].y
= rv
[3].y
;
1769 rv
[3].x
= rv
[4].x
; rv
[3].y
= rv
[4].y
;
1770 rv
[4].x
= rv
[0].x
; rv
[4].y
= rv
[0].y
;
1773 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, rv[1].x, rv[1].y, 0.));
1774 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[2].x, rv[2].y, 0.));
1775 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[3].x, rv[3].y, 0.));
1776 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[4].x, rv[4].y, 0.));
1777 vlist
= rect_with_attachments(pad_rad(pad
),
1783 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
1784 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1785 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1788 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., 0.) );
1789 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, (x
[0] + x
[1]) / 2., (y
[0] + y
[1]) / 2., bbox
) );
1790 g_assert(TOPOROUTER_VERTEX(bbox
->point
)->bbox
== bbox
);
1795 /* Either round pad or pad with curved edges */
1797 if(x
[0] == x
[1] && y
[0] == y
[1]) {
1800 /* bounding box same as square pad */
1801 vlist
= rect_with_attachments(pad_rad(pad
),
1807 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
1808 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1811 //bbox->point = GTS_POINT( insert_vertex(r, l, x[0], y[0], bbox) );
1812 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
[0], y
[0], bbox
) );
1815 /* Two points and one constraint edge */
1817 /* the rest is just for bounding box */
1818 m
= cartesian_gradient(x
[0], y
[0], x
[1], y
[1]);
1820 p
[0].x
= x
[0]; p
[0].y
= y
[0];
1821 p
[1].x
= x
[1]; p
[1].y
= y
[1];
1823 vertex_outside_segment(&p
[0], &p
[1], t
, &rv
[0]);
1824 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[1], &rv
[2]);
1826 vertex_outside_segment(&p
[1], &p
[0], t
, &rv
[0]);
1827 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[3], &rv
[4]);
1829 if(wind(&rv
[1], &rv
[2], &rv
[3]) != wind(&rv
[2], &rv
[3], &rv
[4])) {
1830 rv
[0].x
= rv
[3].x
; rv
[0].y
= rv
[3].y
;
1831 rv
[3].x
= rv
[4].x
; rv
[3].y
= rv
[4].y
;
1832 rv
[4].x
= rv
[0].x
; rv
[4].y
= rv
[0].y
;
1835 vlist
= rect_with_attachments(pad_rad(pad
),
1841 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
1842 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1843 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1846 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., 0.) );
1847 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, (x
[0] + x
[1]) / 2., (y
[0] + y
[1]) / 2., bbox
) );
1849 //bbox->constraints = g_list_concat(bbox->constraints, insert_constraint_edge(r, l, x[0], y[0], x[1], y[1], bbox));
1866 * Read points data (all layers) into GList
1868 * Inserts pin and via points
1871 read_points(toporouter_t
*r
, toporouter_layer_t
*l
, int layer
)
1875 GList
*vlist
= NULL
;
1876 toporouter_bbox_t
*bbox
= NULL
;
1878 ELEMENT_LOOP(PCB
->Data
);
1883 t
= (gdouble
)pin
->Thickness
/ 2.0f
;
1887 if(TEST_FLAG (SQUAREFLAG
, pin
)) {
1889 vlist
= rect_with_attachments(pin_rad(pin
),
1895 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PIN
, pin
);
1896 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1897 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1899 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
1901 }else if(TEST_FLAG(OCTAGONFLAG
, pin
)){
1902 /* TODO: Handle octagon pins */
1903 fprintf(stderr
, "No support for octagon pins yet\n");
1905 vlist
= rect_with_attachments(pin_rad(pin
),
1911 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PIN
, pin
);
1912 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1914 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
1921 VIA_LOOP(PCB
->Data
);
1924 t
= (gdouble
)via
->Thickness
/ 2.0f
;
1928 if(TEST_FLAG (SQUAREFLAG
, via
)) {
1930 vlist
= rect_with_attachments(pin_rad((PinType
*)via
),
1936 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, VIA
, via
);
1937 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1938 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1940 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
1942 }else if(TEST_FLAG(OCTAGONFLAG
, via
)){
1943 /* TODO: Handle octagon vias */
1944 fprintf(stderr
, "No support for octagon vias yet\n");
1947 vlist
= rect_with_attachments(pin_rad((PinType
*)via
),
1953 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, VIA
, via
);
1954 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1957 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
1966 * Read line data from layer into toporouter_layer_t struct
1968 * Inserts points and constraints into GLists
1971 read_lines(toporouter_t
*r
, toporouter_layer_t
*l
, LayerType
*layer
, int ln
)
1973 gdouble xs
[2], ys
[2];
1975 GList
*vlist
= NULL
;
1976 toporouter_bbox_t
*bbox
= NULL
;
1978 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1982 xs
[0] = line
->Point1
.X
;
1983 xs
[1] = line
->Point2
.X
;
1984 ys
[0] = line
->Point1
.Y
;
1985 ys
[1] = line
->Point2
.Y
;
1986 if(!(xs
[0] == xs
[1] && ys
[0] == ys
[1])) {
1987 vlist
= g_list_prepend(NULL
, gts_vertex_new (vertex_class
, xs
[0], ys
[0], l
- r
->layers
));
1988 vlist
= g_list_prepend(vlist
, gts_vertex_new (vertex_class
, xs
[1], ys
[1], l
- r
->layers
));
1989 // TODO: replace this with surface version
1990 bbox
= toporouter_bbox_create_from_points(GetLayerGroupNumberByNumber(ln
), vlist
, LINE
, line
);
1991 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1993 //insert_constraints_from_list(r, l, vlist, bbox);
1995 // bbox->point = GTS_POINT( insert_vertex(r, l, (xs[0]+xs[1])/2., (ys[0]+ys[1])/2., bbox) );
1997 bbox
->constraints
= g_list_concat(bbox
->constraints
, insert_constraint_edge(r
, l
, xs
[0], ys
[0], 0, xs
[1], ys
[1], 0, bbox
));
2006 create_board_edge (double x0
, double y0
,
2007 double x1
, double y1
,
2011 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
2012 double edge_length
= sqrt (pow (x0
- x1
, 2) + pow (y0
- y1
, 2));
2013 unsigned int vertices_per_edge
= MIN (1, edge_length
/ BOARD_EDGE_RESOLUTION
);
2015 double inc
= edge_length
/ vertices_per_edge
;
2016 double x
= x0
, y
= y0
;
2018 *vlist
= g_list_prepend (*vlist
, gts_vertex_new (vertex_class
, x
, y
, layer
));
2020 for (count
= 1; count
< vertices_per_edge
; count
++) {
2021 coord_move_towards_coord_values (x
, y
, x1
, y1
, inc
, &x
, &y
);
2022 *vlist
= g_list_prepend (*vlist
, gts_vertex_new (vertex_class
, x
, y
, layer
));
2028 read_board_constraints (toporouter_t
*r
, toporouter_layer_t
*l
, int layer
)
2030 GList
*vlist
= NULL
;
2031 toporouter_bbox_t
*bbox
;
2033 /* Create points for the board edges and constrain those edges */
2034 create_board_edge (0., 0., PCB
->MaxWidth
, 0., layer
, &vlist
);
2035 create_board_edge (PCB
->MaxWidth
, 0., PCB
->MaxWidth
, PCB
->MaxHeight
, layer
, &vlist
);
2036 create_board_edge (PCB
->MaxWidth
, PCB
->MaxHeight
, 0., PCB
->MaxHeight
, layer
, &vlist
);
2037 create_board_edge (0., PCB
->MaxHeight
, 0., 0., layer
, &vlist
);
2039 bbox
= toporouter_bbox_create (layer
, vlist
, BOARD
, NULL
);
2040 r
->bboxes
= g_slist_prepend (r
->bboxes
, bbox
);
2041 insert_constraints_from_list (r
, l
, vlist
, bbox
);
2042 g_list_free (vlist
);
2046 triangle_cost(GtsTriangle
*t
, gpointer
*data
){
2048 gdouble
*min_quality
= (gdouble
*)data
[0];
2049 gdouble
*max_area
= (gdouble
*)data
[1];
2050 gdouble quality
= gts_triangle_quality(t
);
2051 gdouble area
= gts_triangle_area(t
);
2053 if (quality
< *min_quality
|| area
> *max_area
)
2060 print_constraint(toporouter_constraint_t
*e
)
2062 printf("CONSTRAINT:\n");
2063 print_vertex(tedge_v1(e
));
2064 print_vertex(tedge_v2(e
));
2068 print_edge(toporouter_edge_t
*e
)
2070 GList
*i
= edge_routing(e
);
2074 print_vertex(tedge_v1(e
));
2077 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
2082 print_vertex(tedge_v2(e
));
2084 static void pick_first_face (GtsFace
* f
, GtsFace
** first
)
2091 unconstrain(toporouter_layer_t
*l
, toporouter_constraint_t
*c
)
2093 toporouter_edge_t
*e
;
2095 gts_allow_floating_vertices
= TRUE
;
2096 e
= TOPOROUTER_EDGE(gts_edge_new (GTS_EDGE_CLASS (toporouter_edge_class ()), GTS_SEGMENT(c
)->v1
, GTS_SEGMENT(c
)->v2
));
2097 gts_edge_replace(GTS_EDGE(c
), GTS_EDGE(e
));
2098 l
->constraints
= g_list_remove(l
->constraints
, c
);
2099 c
->box
->constraints
= g_list_remove(c
->box
->constraints
, c
);
2101 gts_object_destroy (GTS_OBJECT (c
));
2102 gts_allow_floating_vertices
= FALSE
;
2106 build_cdt(toporouter_t
*r
, toporouter_layer_t
*l
)
2108 /* TODO: generalize into surface *cdt_create(vertices, constraints) */
2113 GtsVertex
*v1
, *v2
, *v3
;
2114 GSList
*vertices_slist
;
2116 vertices_slist
= list_to_slist(l
->vertices
);
2119 GtsFace
* first
= NULL
;
2120 gts_surface_foreach_face (l
->surface
, (GtsFunc
) pick_first_face
, &first
);
2121 gts_surface_traverse_destroy(gts_surface_traverse_new (l
->surface
, first
));
2124 t
= gts_triangle_enclosing (gts_triangle_class (), vertices_slist
, 1000.0f
);
2125 gts_triangle_vertices (t
, &v1
, &v2
, &v3
);
2127 g_slist_free(vertices_slist
);
2129 l
->surface
= gts_surface_new (gts_surface_class (), gts_face_class (),
2130 GTS_EDGE_CLASS(toporouter_edge_class ()), GTS_VERTEX_CLASS(toporouter_vertex_class ()) );
2132 gts_surface_add_face (l
->surface
, gts_face_new (gts_face_class (), t
->e1
, t
->e2
, t
->e3
));
2135 // fprintf(stderr, "ADDED VERTICES\n");
2139 if((debugface = gts_delaunay_check(l->surface))) {
2140 fprintf(stderr, "WARNING: Delaunay check failed\n");
2141 fprintf(stderr, "\tViolating triangle:\n");
2142 fprintf(stderr, "\t%f,%f %f,%f\n",
2143 debugface->triangle.e1->segment.v1->p.x,
2144 debugface->triangle.e1->segment.v1->p.y,
2145 debugface->triangle.e1->segment.v2->p.x,
2146 debugface->triangle.e1->segment.v2->p.y
2148 fprintf(stderr, "\t%f,%f %f,%f\n",
2149 debugface->triangle.e2->segment.v1->p.x,
2150 debugface->triangle.e2->segment.v1->p.y,
2151 debugface->triangle.e2->segment.v2->p.x,
2152 debugface->triangle.e2->segment.v2->p.y
2154 fprintf(stderr, "\t%f,%f %f,%f\n",
2155 debugface->triangle.e3->segment.v1->p.x,
2156 debugface->triangle.e3->segment.v1->p.y,
2157 debugface->triangle.e3->segment.v2->p.x,
2158 debugface->triangle.e3->segment.v2->p.y
2160 // toporouter_draw_surface(r, l->surface, "debug.png", 4096, 4096);
2163 for(i=0;i<groupcount();i++) {
2165 sprintf(buffer, "debug-%d.png", i);
2166 toporouter_draw_surface(r, r->layers[i].surface, buffer, 2048, 2048, 2, NULL, i, NULL);
2172 check_cons_continuation
:
2175 toporouter_constraint_t
*c1
= TOPOROUTER_CONSTRAINT(i
->data
);
2177 // printf("adding cons: "); print_constraint(c1);
2180 toporouter_constraint_t
*c2
= TOPOROUTER_CONSTRAINT(j
->data
);
2184 // printf("\tconflict: "); print_constraint(c2);
2185 toporouter_bbox_t
*c1box
= c1
->box
, *c2box
= c2
->box
;
2186 toporouter_vertex_t
*c1v1
= tedge_v1(c1
);
2187 toporouter_vertex_t
*c1v2
= tedge_v2(c1
);
2188 toporouter_vertex_t
*c2v1
= tedge_v1(c2
);
2189 toporouter_vertex_t
*c2v2
= tedge_v2(c2
);
2191 if(gts_segments_are_intersecting(GTS_SEGMENT(c1
), GTS_SEGMENT(c2
)) == GTS_IN
) {
2192 toporouter_vertex_t
*v
;
2193 unconstrain(l
, c1
); unconstrain(l
, c2
);
2195 // proper intersection
2196 v
= TOPOROUTER_VERTEX(vertex_intersect(
2202 // remove both constraints
2203 // replace with 4x constraints
2204 // insert new intersection vertex
2205 GTS_POINT(v
)->z
= vz(c1v1
);
2207 l
->vertices
= g_list_prepend(l
->vertices
, v
);
2208 // gts_delaunay_add_vertex (l->surface, GTS_VERTEX(v), NULL);
2212 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(v
), vy(v
), 0, c1box
);
2213 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2215 temp
= insert_constraint_edge(r
, l
, vx(c1v2
), vy(c1v2
), 0, vx(v
), vy(v
), 0, c1box
);
2216 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2218 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(v
), vy(v
), 0, c2box
);
2219 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2221 temp
= insert_constraint_edge(r
, l
, vx(c2v2
), vy(c2v2
), 0, vx(v
), vy(v
), 0, c2box
);
2222 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2224 }else if(gts_segments_are_intersecting(GTS_SEGMENT(c1
), GTS_SEGMENT(c2
)) == GTS_ON
||
2225 gts_segments_are_intersecting(GTS_SEGMENT(c2
), GTS_SEGMENT(c1
)) == GTS_ON
) {
2227 if(vertex_between(edge_v1(c2
), edge_v2(c2
), edge_v1(c1
)) && vertex_between(edge_v1(c2
), edge_v2(c2
), edge_v2(c1
))) {
2228 unconstrain(l
, c1
); unconstrain(l
, c2
);
2231 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c2v2
), vy(c2v2
), 0, c2box
);
2232 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2234 }else if(vertex_between(edge_v1(c1
), edge_v2(c1
), edge_v1(c2
)) && vertex_between(edge_v1(c1
), edge_v2(c1
), edge_v2(c2
))) {
2235 unconstrain(l
, c1
); unconstrain(l
, c2
);
2238 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c1v2
), vy(c1v2
), 0, c1box
);
2239 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2241 //}else if(!vertex_wind(edge_v1(c1), edge_v2(c1), edge_v1(c2)) && !vertex_wind(edge_v1(c1), edge_v2(c1), edge_v2(c2))) {
2242 /* }else if(vertex_between(edge_v1(c1), edge_v2(c1), edge_v1(c2)) || vertex_between(edge_v1(c1), edge_v2(c1), edge_v2(c2))) {
2243 unconstrain(l, c1); unconstrain(l, c2);
2245 printf("all colinear\n");
2247 temp = insert_constraint_edge(r, l, vx(c1v1), vy(c1v1), 0, vx(c1v2), vy(c1v2), 0, c1box);
2248 c1box->constraints = g_list_concat(c1box->constraints, temp);
2250 if(vertex_between(GTS_VERTEX(c1v1), GTS_VERTEX(c1v2), GTS_VERTEX(c2v2))) {
2251 // v2 of c2 is inner
2252 if(vertex_between(GTS_VERTEX(c2v1), GTS_VERTEX(c2v2), GTS_VERTEX(c1v2))) {
2253 // v2 of c1 is inner
2254 // c2 = c1.v2 -> c2.v1
2255 temp = insert_constraint_edge(r, l, vx(c1v2), vy(c1v2), 0, vx(c2v1), vy(c2v1), 0, c2box);
2256 c2box->constraints = g_list_concat(c2box->constraints, temp);
2258 // v1 of c1 is inner
2259 // c2 = c1.v1 -> c2.v1
2260 temp = insert_constraint_edge(r, l, vx(c1v1), vy(c1v1), 0, vx(c2v1), vy(c2v1), 0, c2box);
2261 c2box->constraints = g_list_concat(c2box->constraints, temp);
2264 // v1 of c2 is inner
2265 if(vertex_between(GTS_VERTEX(c2v1), GTS_VERTEX(c2v2), GTS_VERTEX(c1v2))) {
2266 // v2 of c1 is inner
2267 // c2 = c1.v2 -> c2.v2
2268 temp = insert_constraint_edge(r, l, vx(c1v2), vy(c1v2), 0, vx(c2v2), vy(c2v2), 0, c2box);
2269 c2box->constraints = g_list_concat(c2box->constraints, temp);
2271 // v1 of c1 is inner
2272 // c2 = c1.v1 -> c2.v2
2273 temp = insert_constraint_edge(r, l, vx(c1v1), vy(c1v1), 0, vx(c2v2), vy(c2v2), 0, c2box);
2274 c2box->constraints = g_list_concat(c2box->constraints, temp);
2277 }else if(vertex_between(edge_v1(c2
), edge_v2(c2
), edge_v1(c1
)) && c1v1
!= c2v1
&& c1v1
!= c2v2
) {
2278 unconstrain(l
, c1
); unconstrain(l
, c2
);
2281 printf("v1 of c1 on c2\n");
2283 // replace with 2x constraints
2284 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c1v1
), vy(c1v1
), 0, c2box
);
2285 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2286 temp
= insert_constraint_edge(r
, l
, vx(c2v2
), vy(c2v2
), 0, vx(c1v1
), vy(c1v1
), 0, c2box
);
2287 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2289 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c1v2
), vy(c1v2
), 0, c1box
);
2290 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2293 //temp = insert_constraint_edge(r, l, vx(tedge_v2(c1)), vy(tedge_v2(c1)), 0, vx(tedge_v1(c1)), vy(tedge_v1(c1)), 0, c1->box);
2294 //c2->box->constraints = g_list_concat(c2->box->constraints, temp);
2296 }else if(vertex_between(edge_v1(c2
), edge_v2(c2
), edge_v2(c1
)) && c1v2
!= c2v1
&& c1v2
!= c2v2
) {
2297 unconstrain(l
, c1
); unconstrain(l
, c2
);
2300 printf("v2 of c1 on c2\n");
2302 // replace with 2x constraints
2303 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c1v2
), vy(c1v2
), 0, c2box
);
2304 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2305 temp
= insert_constraint_edge(r
, l
, vx(c2v2
), vy(c2v2
), 0, vx(c1v2
), vy(c1v2
), 0, c2box
);
2306 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2308 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c1v2
), vy(c1v2
), 0, c1box
);
2309 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2311 }else if(vertex_between(edge_v1(c1
), edge_v2(c1
), edge_v1(c2
)) && c2v1
!= c1v1
&& c2v1
!= c1v2
) {
2312 unconstrain(l
, c1
); unconstrain(l
, c2
);
2315 printf("v1 of c2 on c1\n");
2317 // replace with 2x constraints
2318 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c2v1
), vy(c2v1
), 0, c1box
);
2319 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2320 temp
= insert_constraint_edge(r
, l
, vx(c1v2
), vy(c1v2
), 0, vx(c2v1
), vy(c2v1
), 0, c1box
);
2321 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2323 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c2v2
), vy(c2v2
), 0, c2box
);
2324 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2325 }else if(vertex_between(edge_v1(c1
), edge_v2(c1
), edge_v2(c2
)) && c2v2
!= c1v1
&& c2v2
!= c1v2
) {
2326 unconstrain(l
, c1
); unconstrain(l
, c2
);
2329 printf("v2 of c2 on c1\n");
2331 // replace with 2x constraints
2332 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c2v2
), vy(c2v2
), 0, c1box
);
2333 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2334 temp
= insert_constraint_edge(r
, l
, vx(c1v2
), vy(c1v2
), 0, vx(c2v2
), vy(c2v2
), 0, c1box
);
2335 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2337 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c2v2
), vy(c2v2
), 0, c2box
);
2338 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2341 if(rem
) goto check_cons_continuation
;
2352 //if(r->flags & TOPOROUTER_FLAG_DEBUG_CDTS)
2353 // fprintf(stderr, "\tadding vertex %f,%f\n", v->p.x, v->p.y);
2354 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(gts_delaunay_add_vertex (l
->surface
, (GtsVertex
*)i
->data
, NULL
));
2356 printf("conflict: "); print_vertex(v
);
2364 // toporouter_constraint_t *c1 = TOPOROUTER_CONSTRAINT(i->data);
2365 // printf("adding cons: "); print_constraint(c1);
2367 GSList
*conflicts
= gts_delaunay_add_constraint (l
->surface
, (GtsConstraint
*)i
->data
);
2368 GSList
*j
= conflicts
;
2370 if(TOPOROUTER_IS_CONSTRAINT(j
->data
)) {
2371 toporouter_constraint_t
*c2
= TOPOROUTER_CONSTRAINT(j
->data
);
2373 printf("\tconflict: "); print_constraint(c2
);
2378 g_slist_free(conflicts
);
2384 // goto build_cdt_continuation;
2385 // fprintf(stderr, "ADDED CONSTRAINTS\n");
2386 gts_allow_floating_vertices
= TRUE
;
2387 gts_object_destroy (GTS_OBJECT (v1
));
2388 gts_object_destroy (GTS_OBJECT (v2
));
2389 gts_object_destroy (GTS_OBJECT (v3
));
2390 gts_allow_floating_vertices
= FALSE
;
2395 gdouble quality = 0.50, area = G_MAXDOUBLE;
2396 guint num = gts_delaunay_conform(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL);
2401 num = gts_delaunay_refine(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL, (GtsKeyFunc) triangle_cost, data);
2406 gts_surface_print_stats(l
->surface
, stderr
);
2413 sprintf(buffer
, "surface%d.gts", l
- r
->layers
);
2414 fout2
= fopen(buffer
, "w");
2415 gts_surface_write(l
->surface
, fout2
);
2422 visited_cmp(gconstpointer a
, gconstpointer b
)
2430 coord_angle (double ax
, double ay
, double bx
, double by
)
2432 return atan2 (by
- ay
, bx
- ax
);
2436 cluster_vertices(toporouter_t
*r
, toporouter_cluster_t
*c
)
2442 FOREACH_CLUSTER(c
->netlist
->clusters
) {
2443 if((r
->flags
& TOPOROUTER_FLAG_AFTERRUBIX
&& cluster
->c
== c
->c
) || (!(r
->flags
& TOPOROUTER_FLAG_AFTERRUBIX
) && cluster
== c
)) {
2444 FOREACH_BBOX(cluster
->boxes
) {
2445 if(box
->type
== LINE
) {
2446 g_assert(box
->constraints
->data
);
2447 rval
= g_list_prepend(rval
, tedge_v1(box
->constraints
->data
));
2448 rval
= g_list_prepend(rval
, tedge_v2(box
->constraints
->data
));
2449 }else if(box
->point
) {
2450 rval
= g_list_prepend(rval
, TOPOROUTER_VERTEX(box
->point
));
2451 //g_assert(vertex_bbox(TOPOROUTER_VERTEX(box->point)) == box);
2453 printf("WARNING: cluster_vertices: unhandled bbox type\n");
2467 print_cluster(toporouter_cluster_t
*c
)
2471 printf("[CLUSTER (NULL)]\n");
2475 printf("CLUSTER %d: NETLIST = %s STYLE = %s\n", c
->c
, c
->netlist
->netlist
, c
->netlist
->style
);
2477 FOREACH_BBOX(c
->boxes
) {
2483 toporouter_cluster_t
*
2484 cluster_create(toporouter_t
*r
, toporouter_netlist_t
*netlist
)
2486 toporouter_cluster_t
*c
= (toporouter_cluster_t
*)malloc(sizeof(toporouter_cluster_t
));
2488 c
->c
= c
->pc
= netlist
->clusters
->len
;
2489 g_ptr_array_add(netlist
->clusters
, c
);
2490 c
->netlist
= netlist
;
2491 c
->boxes
= g_ptr_array_new();
2497 toporouter_bbox_locate(toporouter_t
*r
, toporouter_term_t type
, void *data
, gdouble x
, gdouble y
, guint layergroup
)
2499 GtsPoint
*p
= gts_point_new(gts_point_class(), x
, y
, layergroup
);
2500 GSList
*boxes
= gts_bb_tree_stabbed(r
->bboxtree
, p
), *i
= boxes
;
2502 gts_object_destroy(GTS_OBJECT(p
));
2505 toporouter_bbox_t
*box
= TOPOROUTER_BBOX(i
->data
);
2507 if(box
->type
== type
&& box
->data
== data
) {
2508 g_slist_free(boxes
);
2515 g_slist_free(boxes
);
2520 cluster_join_bbox(toporouter_cluster_t
*cluster
, toporouter_bbox_t
*box
)
2523 g_ptr_array_add(cluster
->boxes
, box
);
2524 box
->cluster
= cluster
;
2528 toporouter_netlist_t
*
2529 netlist_create(toporouter_t
*r
, char *netlist
, char *style
)
2531 toporouter_netlist_t
*nl
= (toporouter_netlist_t
*)malloc(sizeof(toporouter_netlist_t
));
2532 nl
->netlist
= netlist
;
2534 nl
->clusters
= g_ptr_array_new();
2535 nl
->routes
= g_ptr_array_new();
2538 g_ptr_array_add(r
->netlists
, nl
);
2543 import_clusters(toporouter_t
*r
)
2545 NetListListType nets
;
2546 nets
= CollectSubnets(false);
2547 NETLIST_LOOP(&nets
);
2549 if(netlist
->NetN
> 0) {
2550 toporouter_netlist_t
*nl
= netlist_create(r
, netlist
->Net
->Connection
->menu
->Name
, netlist
->Net
->Connection
->menu
->Style
);
2555 toporouter_cluster_t
*cluster
= cluster_create(r
, nl
);
2556 #ifdef DEBUG_MERGING
2559 CONNECTION_LOOP (net
);
2562 if(connection
->type
== LINE_TYPE
) {
2563 LineType
*line
= (LineType
*) connection
->ptr2
;
2564 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, LINE
, line
, connection
->X
, connection
->Y
, connection
->group
);
2565 cluster_join_bbox(cluster
, box
);
2567 #ifdef DEBUG_MERGING
2568 pcb_printf("\tLINE %#mD\n", connection
->X
, connection
->Y
);
2570 }else if(connection
->type
== PAD_TYPE
) {
2571 PadType
*pad
= (PadType
*) connection
->ptr2
;
2572 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, PAD
, pad
, connection
->X
, connection
->Y
, connection
->group
);
2573 cluster_join_bbox(cluster
, box
);
2575 #ifdef DEBUG_MERGING
2576 pcb_printf("\tPAD %#mD\n", connection
->X
, connection
->Y
);
2578 }else if(connection
->type
== PIN_TYPE
) {
2580 for(guint m
=0;m
<groupcount();m
++) {
2581 PinType
*pin
= (PinType
*) connection
->ptr2
;
2582 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, PIN
, pin
, connection
->X
, connection
->Y
, m
);
2583 cluster_join_bbox(cluster
, box
);
2586 #ifdef DEBUG_MERGING
2587 pcb_printf("\tPIN %#mD\n", connection
->X
, connection
->Y
);
2589 }else if(connection
->type
== VIA_TYPE
) {
2591 for(guint m
=0;m
<groupcount();m
++) {
2592 PinType
*pin
= (PinType
*) connection
->ptr2
;
2593 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, VIA
, pin
, connection
->X
, connection
->Y
, m
);
2594 cluster_join_bbox(cluster
, box
);
2597 #ifdef DEBUG_MERGING
2598 pcb_printf("\tVIA %#mD\n", connection
->X
, connection
->Y
);
2600 }else if(connection
->type
== POLYGON_TYPE
) {
2601 PolygonType
*polygon
= (PolygonType
*) connection
->ptr2
;
2602 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, POLYGON
, polygon
, connection
->X
, connection
->Y
, connection
->group
);
2603 cluster_join_bbox(cluster
, box
);
2605 #ifdef DEBUG_MERGING
2606 pcb_printf("\tPOLYGON %#mD\n", connection
->X
, connection
->Y
);
2612 #ifdef DEBUG_MERGING
2621 FreeNetListListMemory(&nets
);
2625 import_geometry(toporouter_t
*r
)
2627 toporouter_layer_t
*cur_layer
;
2632 for (group
= 0; group
< max_group
; group
++) {
2633 printf("Group %d: Number %d:\n", group
, PCB
->LayerGroups
.Number
[group
]);
2635 for (int entry
= 0; entry
< PCB
->LayerGroups
.Number
[group
]; entry
++) {
2636 printf("\tEntry %d\n", PCB
->LayerGroups
.Entries
[group
][entry
]);
2640 /* Allocate space for per layer struct */
2641 cur_layer
= r
->layers
= (toporouter_layer_t
*)malloc(groupcount() * sizeof(toporouter_layer_t
));
2643 /* Foreach layer, read in pad vertices and constraints, and build CDT */
2644 for (group
= 0; group
< max_group
; group
++) {
2646 printf("*** LAYER GROUP %d ***\n", group
);
2648 if(PCB
->LayerGroups
.Number
[group
] > 0){
2649 cur_layer
->vertices
= NULL
;
2650 cur_layer
->constraints
= NULL
;
2653 printf("reading board constraints from layer %d into group %d\n", PCB
->LayerGroups
.Entries
[group
][0], group
);
2655 read_board_constraints(r
, cur_layer
, PCB
->LayerGroups
.Entries
[group
][0]);
2657 printf("reading points from layer %d into group %d \n",PCB
->LayerGroups
.Entries
[group
][0], group
);
2659 read_points(r
, cur_layer
, PCB
->LayerGroups
.Entries
[group
][0]);
2661 //#ifdef DEBUG_IMPORT
2662 // printf("reading pads from layer %d into group %d\n", number, group);
2664 read_pads(r
, cur_layer
, group
);
2666 GROUP_LOOP(PCB
->Data
, group
)
2670 printf("reading lines from layer %d into group %d\n", number
, group
);
2672 read_lines(r
, cur_layer
, layer
, number
);
2680 printf("building CDT\n");
2682 build_cdt(r
, cur_layer
);
2683 printf("finished\n");
2686 for(i=0;i<groupcount();i++) {
2688 sprintf(buffer, "build%d.png", i);
2689 toporouter_draw_surface(r, r->layers[i].surface, buffer, 2048, 2048, 2, NULL, i, NULL);
2693 printf("finished building CDT\n");
2699 r
->bboxtree
= gts_bb_tree_new(r
->bboxes
);
2704 printf("finished import!\n");
2710 compare_points(gconstpointer a
, gconstpointer b
)
2712 GtsPoint
*i
= GTS_POINT(a
);
2713 GtsPoint
*j
= GTS_POINT(b
);
2716 if(i
->y
== j
->y
) return 0;
2717 if(i
->y
< j
->y
) return -1;
2720 if(i
->x
< j
->x
) return -1;
2725 compare_segments(gconstpointer a
, gconstpointer b
)
2727 if(a
== b
) return 0;
2728 if(a
< b
) return -1;
2731 #define DEBUG_CLUSTER_FIND 1
2732 toporouter_cluster_t
*
2733 cluster_find(toporouter_t
*r
, gdouble x
, gdouble y
, gdouble z
)
2735 GtsPoint
*p
= gts_point_new(gts_point_class(), x
, y
, z
);
2736 GSList
*hits
= gts_bb_tree_stabbed(r
->bboxtree
, p
);
2737 toporouter_cluster_t
*rval
= NULL
;
2739 #ifdef DEBUG_CLUSTER_FIND
2740 printf("FINDING %f,%f,%f\n\n", x
, y
, z
);
2744 toporouter_bbox_t
*box
= TOPOROUTER_BBOX(hits
->data
);
2746 #ifdef DEBUG_CLUSTER_FIND
2747 printf("HIT BOX: "); print_bbox(box
);
2750 if(box
->layer
== (int)z
) {
2751 if(box
->type
!= BOARD
) {
2752 if(box
->type
== LINE
) {
2753 LineType
*line
= (LineType
*)box
->data
;
2754 gint linewind
= coord_wind(line
->Point1
.X
, line
->Point1
.Y
, x
, y
, line
->Point2
.X
, line
->Point2
.Y
);
2756 if(line
->Point1
.X
> x
- EPSILON
&& line
->Point1
.X
< x
+ EPSILON
&&
2757 line
->Point1
.Y
> y
- EPSILON
&& line
->Point1
.Y
< y
+ EPSILON
) {
2758 rval
= box
->cluster
;
2761 if(line
->Point2
.X
> x
- EPSILON
&& line
->Point2
.X
< x
+ EPSILON
&&
2762 line
->Point2
.Y
> y
- EPSILON
&& line
->Point2
.Y
< y
+ EPSILON
) {
2763 rval
= box
->cluster
;
2767 rval
= box
->cluster
;
2771 }else if(box
->surface
) {
2773 if(gts_point_locate(p
, box
->surface
, NULL
)) {
2774 rval
= box
->cluster
;
2784 gts_object_destroy(GTS_OBJECT(p
));
2787 #ifdef DEBUG_CLUSTER_FIND
2788 printf("cluster_find: %f,%f,%f: ", x
, y
, z
);
2789 print_cluster(rval
);
2796 simple_h_cost(toporouter_t
*r
, toporouter_vertex_t
*curpoint
, toporouter_vertex_t
*destpoint
)
2798 gdouble layerpenalty
= (vz(curpoint
) == vz(destpoint
)) ? 0. : r
->viacost
;
2800 return gts_point_distance(GTS_POINT(curpoint
), GTS_POINT(destpoint
)) + layerpenalty
;
2803 #define FCOST(x) (x->gcost + x->hcost)
2805 route_heap_cmp(gpointer item
, gpointer data
)
2807 return FCOST(TOPOROUTER_VERTEX(item
));
2810 #define closelist_insert(p) closelist = g_list_prepend(closelist, p)
2813 toporouter_vertex_t
*key
;
2814 toporouter_vertex_t
*result
;
2815 }toporouter_heap_search_data_t
;
2818 toporouter_heap_search(gpointer data
, gpointer user_data
)
2820 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(data
);
2821 toporouter_heap_search_data_t
*heap_search_data
= (toporouter_heap_search_data_t
*)user_data
;
2822 if(v
== heap_search_data
->key
) heap_search_data
->result
= v
;
2826 toporouter_heap_color(gpointer data, gpointer user_data)
2828 toporouter_vertex_t *v = TOPOROUTER_VERTEX(data);
2829 v->flags |= (guint) user_data;
2832 static inline gdouble
2833 angle_span(gdouble a1
, gdouble a2
)
2836 return ((2*M_PI
)-a1
+ a2
);
2841 edge_capacity(toporouter_edge_t
*e
)
2843 return gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
)));
2847 edge_flow(toporouter_edge_t
*e
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*dest
)
2849 GList
*i
= edge_routing(e
);
2850 toporouter_vertex_t
*pv
= tedge_v1(e
), *v
= NULL
;
2854 if((pv
== v1
|| pv
== v2
) && waiting
) {
2855 flow
+= min_vertex_net_spacing(pv
, dest
);
2863 v
= TOPOROUTER_VERTEX(i
->data
);
2867 flow
+= min_vertex_net_spacing(v
, pv
);
2869 flow
+= min_spacing(v
, pv
);
2871 if((v
== v1
|| v
== v2
) && waiting
) {
2872 flow
+= min_vertex_net_spacing(v
, dest
);
2882 flow
+= min_vertex_net_spacing(tedge_v2(e
), pv
);
2884 flow
+= min_spacing(tedge_v2(e
), pv
);
2890 print_path(GList
*path
)
2896 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
2897 // printf("[V %f,%f,%f]\n", vx(v), vy(v), vz(v));
2900 if(v
->child
&& !g_list_find(path
, v
->child
))
2901 printf("\t CHILD NOT IN LIST\n");
2902 if(v
->parent
&& !g_list_find(path
, v
->parent
))
2903 printf("\t parent NOT IN LIST\n");
2911 split_path(GList
*path
)
2913 toporouter_vertex_t
*pv
= NULL
;
2914 GList
*curpath
= NULL
, *i
, *paths
= NULL
;
2920 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
2923 printf("v = %f,%f ", vx(v
), vy(v
));
2924 if(v
->parent
) printf("parent = %f,%f ", vx(v
->parent
), vy(v
->parent
));
2925 if(v
->child
) printf("child = %f,%f ", vx(v
->child
), vy(v
->child
));
2929 // if(v) printf("v = %f,%f\n", GTS_POINT(v)->x, GTS_POINT(v)->y);
2930 // if(pv) printf("pv = %f,%f\n", GTS_POINT(pv)->x, GTS_POINT(pv)->y);
2934 if(GTS_POINT(v
)->x
== GTS_POINT(pv
)->x
&& GTS_POINT(v
)->y
== GTS_POINT(pv
)->y
) {
2935 if(g_list_length(curpath
) > 1) paths
= g_list_prepend(paths
, curpath
);
2942 curpath
= g_list_append(curpath
, v
);
2948 if(g_list_length(curpath
) > 1)
2949 paths
= g_list_prepend(paths
, curpath
);
2956 #define edge_gradient(e) (cartesian_gradient(GTS_POINT(GTS_SEGMENT(e)->v1)->x, GTS_POINT(GTS_SEGMENT(e)->v1)->y, \
2957 GTS_POINT(GTS_SEGMENT(e)->v2)->x, GTS_POINT(GTS_SEGMENT(e)->v2)->y))
2960 /* sorting into ascending distance from v1 */
2962 routing_edge_insert(gconstpointer a
, gconstpointer b
, gpointer user_data
)
2964 GtsPoint
*v1
= GTS_POINT(edge_v1(user_data
));
2966 if(gts_point_distance2(v1
, GTS_POINT(a
)) < gts_point_distance2(v1
, GTS_POINT(b
)) - EPSILON
)
2968 if(gts_point_distance2(v1
, GTS_POINT(a
)) > gts_point_distance2(v1
, GTS_POINT(b
)) + EPSILON
)
2971 printf("a = %x b = %x\n", (int) a, (int) b);
2973 printf("WARNING: routing_edge_insert() with same points..\n \
2980 printf("A: "); print_vertex(TOPOROUTER_VERTEX(a));
2981 printf("B: "); print_vertex(TOPOROUTER_VERTEX(b));
2983 TOPOROUTER_VERTEX(a)->flags |= VERTEX_FLAG_RED;
2984 TOPOROUTER_VERTEX(b)->flags |= VERTEX_FLAG_RED;
2990 toporouter_vertex_t
*
2991 new_temp_toporoutervertex(gdouble x
, gdouble y
, toporouter_edge_t
*e
)
2993 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
2994 GList
*i
= edge_routing(e
);
2995 toporouter_vertex_t
*r
;
2998 r
= TOPOROUTER_VERTEX(i
->data
);
2999 if(epsilon_equals(vx(r
),x
) && epsilon_equals(vy(r
),y
)) {
3000 if(r
->flags
& VERTEX_FLAG_TEMP
) return r
;
3005 r
= TOPOROUTER_VERTEX( gts_vertex_new (vertex_class
, x
, y
, vz(edge_v1(e
))) );
3006 r
->flags
|= VERTEX_FLAG_TEMP
;
3009 if(TOPOROUTER_IS_CONSTRAINT(e
))
3010 TOPOROUTER_CONSTRAINT(e
)->routing
= g_list_insert_sorted_with_data(edge_routing(e
), r
, routing_edge_insert
, e
);
3012 e
->routing
= g_list_insert_sorted_with_data(edge_routing(e
), r
, routing_edge_insert
, e
);
3018 /* create vertex on edge e at radius r from v, closest to ref */
3019 toporouter_vertex_t
*
3020 new_temp_toporoutervertex_in_segment(toporouter_edge_t
*e
, toporouter_vertex_t
*v
, gdouble r
, toporouter_vertex_t
*ref
)
3022 gdouble m
= edge_gradient(e
);
3023 toporouter_spoint_t p
, np1
, np2
;
3024 // toporouter_vertex_t *b = TOPOROUTER_VERTEX((GTS_VERTEX(v) == edge_v1(e)) ? edge_v2(e) : edge_v1(e));
3025 toporouter_vertex_t
*rval
= NULL
;
3026 p
.x
= vx(v
); p
.y
= vy(v
);
3028 vertices_on_line(&p
, m
, r
, &np1
, &np2
);
3030 if( (pow(np1
.x
- vx(ref
), 2) + pow(np1
.y
- vy(ref
), 2)) < (pow(np2
.x
- vx(ref
), 2) + pow(np2
.y
- vy(ref
), 2)) )
3031 rval
= new_temp_toporoutervertex(np1
.x
, np1
.y
, e
);
3033 rval
= new_temp_toporoutervertex(np2
.x
, np2
.y
, e
);
3039 vertex_keepout_test(toporouter_t
*r
, toporouter_vertex_t
*v
)
3041 GList
*i
= r
->keepoutlayers
;
3043 gdouble keepout
= *((double *) i
->data
);
3044 if(vz(v
) == keepout
) return 1;
3051 closest_cluster_pair(toporouter_t
*r
, GList
*src_vertices
, GList
*dest_vertices
, toporouter_vertex_t
**a
, toporouter_vertex_t
**b
)
3053 GList
*i
= src_vertices
, *j
= dest_vertices
;
3056 *a
= NULL
; *b
= NULL
;
3060 toporouter_vertex_t
*v1
= TOPOROUTER_VERTEX(i
->data
);
3062 if(vertex_keepout_test(r
, v1
)) { i
= i
->next
; continue; }
3066 toporouter_vertex_t
*v2
= TOPOROUTER_VERTEX(j
->data
);
3067 if(vertex_keepout_test(r
, v2
) || vz(v2
) != vz(v1
)) { j
= j
->next
; continue; }
3070 *a
= v1
; *b
= v2
; min
= simple_h_cost(r
, *a
, *b
);
3072 gdouble tempd
= simple_h_cost(r
, v1
, v2
);
3073 if(r
->flags
& TOPOROUTER_FLAG_GOFAR
&& tempd
> min
) {
3074 *a
= v1
; *b
= v2
; min
= tempd
;
3077 *a
= v1
; *b
= v2
; min
= tempd
;
3087 // g_list_free(src_vertices);
3088 // g_list_free(dest_vertices);
3092 toporouter_vertex_t
*
3093 closest_dest_vertex(toporouter_t
*r
, toporouter_vertex_t
*v
, toporouter_route_t
*routedata
)
3095 GList
//*vertices = cluster_vertices(r, routedata->dest),
3096 *i
= routedata
->destvertices
;
3097 toporouter_vertex_t
*closest
= NULL
;
3098 gdouble closest_distance
= 0.;
3100 // if(routedata->flags & TOPOROUTER_FLAG_FLEX) i = r->destboxes;
3103 toporouter_vertex_t
*cv
= TOPOROUTER_VERTEX(i
->data
);
3105 if(vz(cv
) != vz(v
)) { i
= i
->next
; continue; }
3108 closest
= cv
; closest_distance
= simple_h_cost(r
, v
, closest
);
3110 gdouble tempd
= simple_h_cost(r
, v
, cv
);
3111 if(r
->flags
& TOPOROUTER_FLAG_GOFAR
&& tempd
> closest_distance
) {
3112 closest
= cv
; closest_distance
= tempd
;
3114 if(tempd
< closest_distance
) {
3115 closest
= cv
; closest_distance
= tempd
;
3121 // g_list_free(vertices);
3124 printf("CLOSEST = %f,%f,%f\n", vx(closest
), vy(closest
), vz(closest
));
3129 #define toporouter_edge_gradient(e) (cartesian_gradient(vx(edge_v1(e)), vy(edge_v1(e)), vx(edge_v2(e)), vy(edge_v2(e))))
3132 /* returns the capacity of the triangle cut through v */
3134 triangle_interior_capacity(GtsTriangle
*t
, toporouter_vertex_t
*v
)
3136 toporouter_edge_t
*e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3137 gdouble x
, y
, m1
, m2
, c2
, c1
;
3144 m1
= toporouter_edge_gradient(e
);
3145 m2
= perpendicular_gradient(m1
);
3146 c2
= (isinf(m2
)) ? vx(v
) : vy(v
) - (m2
* vx(v
));
3147 c1
= (isinf(m1
)) ? vx(edge_v1(e
)) : vy(edge_v1(e
)) - (m1
* vx(edge_v1(e
)));
3154 x
= (c2
- c1
) / (m1
- m2
);
3156 y
= (isinf(m2
)) ? vy(edge_v1(e
)) : (m2
* x
) + c2
;
3159 len
= gts_point_distance2(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
)));
3160 printf("%f,%f len = %f v = %f,%f\n", x
, y
, len
, vx(v
), vy(v
));
3163 if(epsilon_equals(x
,vx(edge_v1(e
))) && epsilon_equals(y
,vy(edge_v1(e
)))) return INFINITY
;
3164 if(epsilon_equals(x
,vx(edge_v2(e
))) && epsilon_equals(y
,vy(edge_v2(e
)))) return INFINITY
;
3166 if(x
>= MIN(vx(edge_v1(e
)),vx(edge_v2(e
))) &&
3167 x
<= MAX(vx(edge_v1(e
)),vx(edge_v2(e
))) &&
3168 y
>= MIN(vy(edge_v1(e
)),vy(edge_v2(e
))) &&
3169 y
<= MAX(vy(edge_v1(e
)),vy(edge_v2(e
))))
3171 // if( (pow(vx(edge_v1(e)) - x, 2) + pow(vy(edge_v1(e)) - y, 2)) < len && (pow(vx(edge_v2(e)) - x, 2) + pow(vy(edge_v2(e)) - y, 2)) < len )
3172 return sqrt(pow(vx(v
) - x
, 2) + pow(vy(v
) - y
, 2));
3177 static inline toporouter_vertex_t
*
3178 segment_common_vertex(GtsSegment
*s1
, GtsSegment
*s2
)
3180 if(!s1
|| !s2
) return NULL
;
3181 if(s1
->v1
== s2
->v1
) return TOPOROUTER_VERTEX(s1
->v1
);
3182 if(s1
->v2
== s2
->v1
) return TOPOROUTER_VERTEX(s1
->v2
);
3183 if(s1
->v1
== s2
->v2
) return TOPOROUTER_VERTEX(s1
->v1
);
3184 if(s1
->v2
== s2
->v2
) return TOPOROUTER_VERTEX(s1
->v2
);
3188 static inline toporouter_vertex_t
*
3189 route_vertices_common_vertex(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
3191 return segment_common_vertex(GTS_SEGMENT(v1
->routingedge
), GTS_SEGMENT(v2
->routingedge
));
3196 edges_third_edge(GtsSegment
*s1
, GtsSegment
*s2
, toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
3198 if(!s1
|| !s2
) return 0;
3199 if(s1
->v1
== s2
->v1
) {
3200 *v1
= TOPOROUTER_VERTEX(s1
->v2
);
3201 *v2
= TOPOROUTER_VERTEX(s2
->v2
);
3204 if(s1
->v2
== s2
->v1
) {
3205 *v1
= TOPOROUTER_VERTEX(s1
->v1
);
3206 *v2
= TOPOROUTER_VERTEX(s2
->v2
);
3209 if(s1
->v1
== s2
->v2
) {
3210 *v1
= TOPOROUTER_VERTEX(s1
->v2
);
3211 *v2
= TOPOROUTER_VERTEX(s2
->v1
);
3214 if(s1
->v2
== s2
->v2
) {
3215 *v1
= TOPOROUTER_VERTEX(s1
->v1
);
3216 *v2
= TOPOROUTER_VERTEX(s2
->v1
);
3222 /* returns the flow from e1 to e2, and the flow from the vertex oppisate e1 to
3223 * e1 and the vertex oppisate e2 to e2 */
3225 flow_from_edge_to_edge(GtsTriangle
*t
, toporouter_edge_t
*e1
, toporouter_edge_t
*e2
,
3226 toporouter_vertex_t
*common_v
, toporouter_vertex_t
*curpoint
)
3229 toporouter_vertex_t
*pv
= common_v
, *v
;
3230 toporouter_edge_t
*op_edge
;
3232 GList
*i
= edge_routing(e1
);
3234 v
= TOPOROUTER_VERTEX(i
->data
);
3237 r
+= min_spacing(v
, pv
);
3239 i
= i
->next
; continue;
3241 // if(!(v->flags & VERTEX_FLAG_TEMP)) {
3242 if((v
->flags
& VERTEX_FLAG_ROUTE
)) {
3244 if(v
->parent
->routingedge
== e2
) {
3245 r
+= min_spacing(v
, pv
);
3247 i
= i
->next
; continue;
3251 if(v
->child
->routingedge
== e2
) {
3252 r
+= min_spacing(v
, pv
);
3254 i
= i
->next
; continue;
3260 op_edge
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(common_v
)));
3266 v
= segment_common_vertex(GTS_SEGMENT(e2
), GTS_SEGMENT(op_edge
));
3269 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e1)));
3270 if(v
->flags
& VERTEX_FLAG_ROUTE
&& v
->parent
&& v
->parent
->routingedge
) {
3271 if(v
->parent
->routingedge
== e1
)
3272 r
+= min_spacing(v
, pv
);
3275 v
= segment_common_vertex(GTS_SEGMENT(e1
), GTS_SEGMENT(op_edge
));
3278 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e2)));
3279 if(v
->flags
& VERTEX_FLAG_ROUTE
&& v
->parent
&& v
->parent
->routingedge
) {
3280 if(v
->parent
->routingedge
== e1
)
3281 r
+= min_spacing(v
, pv
);
3284 if(TOPOROUTER_IS_CONSTRAINT(op_edge
)) {
3285 toporouter_bbox_t
*box
= vertex_bbox(TOPOROUTER_VERTEX(edge_v1(op_edge
)));
3286 r
+= vertex_net_thickness(v
) / 2.;
3288 r
+= MAX(vertex_net_keepaway(v
), cluster_keepaway(box
->cluster
));
3289 r
+= cluster_thickness(box
->cluster
) / 2.;
3291 r
+= vertex_net_keepaway(v
);
3302 check_triangle_interior_capacity(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_vertex_t
*curpoint
,
3303 toporouter_edge_t
*op_edge
, toporouter_edge_t
*adj_edge1
, toporouter_edge_t
*adj_edge2
)
3305 gdouble ic
= triangle_interior_capacity(t
, v
);
3306 gdouble flow
= flow_from_edge_to_edge(t
, adj_edge1
, adj_edge2
, v
, curpoint
);
3308 if(TOPOROUTER_IS_CONSTRAINT(adj_edge1
) || TOPOROUTER_IS_CONSTRAINT(adj_edge2
)) return 1;
3313 printf("fail interior capacity flow = %f ic = %f\n", flow
, ic
);
3321 toporouter_vertex_t
*
3322 edge_routing_next_not_temp(toporouter_edge_t
*e
, GList
*list
)
3324 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3326 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(list
->data
);
3327 if(!(v
->flags
& VERTEX_FLAG_TEMP
))
3336 toporouter_vertex_t
*
3337 edge_routing_prev_not_temp(toporouter_edge_t
*e
, GList
*list
)
3339 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3341 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(list
->data
);
3342 if(!(v
->flags
& VERTEX_FLAG_TEMP
))
3352 edge_adjacent_vertices(toporouter_edge_t
*e
, toporouter_vertex_t
*v
, toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
3354 GList
*r
= g_list_find(edge_routing(e
), v
);
3356 if(v
== tedge_v1(e
)) {
3358 *v2
= edge_routing_next_not_temp(e
, edge_routing(e
));
3359 }else if(v
== tedge_v2(e
)) {
3360 *v1
= edge_routing_prev_not_temp(e
, g_list_last(edge_routing(e
)));
3363 // r = g_list_find(r, v);
3364 *v1
= edge_routing_prev_not_temp(e
, r
);
3365 *v2
= edge_routing_next_not_temp(e
, r
);
3373 candidate_vertices(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*dest
, toporouter_edge_t
*e
)
3375 gdouble totald
, v1ms
, v2ms
, flow
, capacity
, ms
;
3382 g_assert(!(v1
->flags
& VERTEX_FLAG_TEMP
));
3383 g_assert(!(v2
->flags
& VERTEX_FLAG_TEMP
));
3385 printf("starting candidate vertices\n");
3386 printf("v1 = %f,%f v2 = %f,%f dest = %f,%f\n", vx(v1
), vy(v1
), vx(v2
), vy(v2
), vx(dest
), vy(dest
));
3388 totald
= gts_point_distance(GTS_POINT(v1
), GTS_POINT(v2
));
3389 v1ms
= min_spacing(v1
, dest
);
3390 v2ms
= min_spacing(v2
, dest
);
3391 ms
= min_spacing(dest
, dest
);
3392 flow
= TOPOROUTER_IS_CONSTRAINT(e
) ? 0. : edge_flow(e
, v1
, v2
, dest
);
3393 capacity
= edge_capacity(e
);
3396 g_assert(totald
> 0);
3398 printf("v1ms = %f v2ms = %f totald = %f ms = %f capacity = %f flow = %f\n", v1ms
, v2ms
, totald
, ms
, capacity
, flow
);
3401 if(flow
>= capacity
) return NULL
;
3404 if(v1ms
+ v2ms
+ ms
>= totald
) {
3405 vs
= g_list_prepend(vs
, new_temp_toporoutervertex((vx(v1
)+vx(v2
)) / 2., (vy(v1
)+vy(v2
)) / 2., e
));
3407 gdouble x0
, y0
, x1
, y1
, d
;
3409 vertex_move_towards_vertex_values(GTS_VERTEX(v1
), GTS_VERTEX(v2
), v1ms
, &x0
, &y0
);
3411 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x0
, y0
, e
));
3413 vertex_move_towards_vertex_values(GTS_VERTEX(v2
), GTS_VERTEX(v1
), v2ms
, &x1
, &y1
);
3415 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x1
, y1
, e
));
3417 d
= sqrt(pow(x0
-x1
,2) + pow(y0
-y1
,2));
3420 // guint nint = d / ms;
3421 // gdouble dif = d / (nint + 1);
3422 gdouble dif
= d
/ 2;
3424 // for(guint j=0;j<nint;j++) {
3427 // coord_move_towards_coord_values(x0, y0, x1, y1, dif * j, &x, &y);
3428 coord_move_towards_coord_values(x0
, y0
, x1
, y1
, dif
, &x
, &y
);
3430 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x
, y
, e
));
3438 printf("candidate vertices returning %d\n", g_list_length(vs
));
3444 edge_routing_first_not_temp(toporouter_edge_t
*e
)
3446 GList
*i
= edge_routing(e
);
3447 toporouter_vertex_t
*v
;
3450 v
= TOPOROUTER_VERTEX(i
->data
);
3451 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) return i
;
3460 edge_routing_last_not_temp(toporouter_edge_t
*e
)
3462 GList
*i
= edge_routing(e
), *last
= NULL
;
3463 toporouter_vertex_t
*v
;
3466 v
= TOPOROUTER_VERTEX(i
->data
);
3467 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) last
= i
;
3476 delete_vertex(toporouter_vertex_t
*v
)
3479 if(v
->flags
& VERTEX_FLAG_TEMP
) {
3480 if(v
->routingedge
) {
3481 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
3482 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
);
3484 v
->routingedge
->routing
= g_list_remove(v
->routingedge
->routing
, v
);
3487 gts_object_destroy ( GTS_OBJECT(v
) );
3491 #define edge_is_blocked(e) (TOPOROUTER_IS_EDGE(e) ? (e->flags & EDGE_FLAG_DIRECTCONNECTION) : 0)
3494 triangle_candidate_points_from_vertex(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_vertex_t
*dest
, toporouter_route_t
*routedata
)
3496 toporouter_edge_t
*op_e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3497 toporouter_vertex_t
*vv1
, *vv2
, *constraintv
= NULL
;
3498 toporouter_edge_t
*e1
, *e2
;
3503 printf("\tTRIANGLE CAND POINT FROM VERTEX\n");
3508 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), edge_v1(op_e
)));
3509 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), edge_v2(op_e
)));
3512 if(TOPOROUTER_IS_CONSTRAINT(op_e
)) {
3513 if(TOPOROUTER_CONSTRAINT(op_e
)->box
->type
== BOARD
) {
3515 printf("BOARD constraint\n");
3519 if(constraint_netlist(TOPOROUTER_CONSTRAINT(op_e
)) != vertex_netlist(dest
)) { // || TOPOROUTER_CONSTRAINT(op_e)->routing) {
3521 printf("op_e routing:\n");
3527 printf("RETURNING CONSTRAINT POING\n");
3529 constraintv
= new_temp_toporoutervertex_in_segment(op_e
, TOPOROUTER_VERTEX(edge_v1(op_e
)),
3530 gts_point_distance(GTS_POINT(edge_v1(op_e
)), GTS_POINT(edge_v2(op_e
))) / 2., TOPOROUTER_VERTEX(edge_v2(op_e
)));
3531 // return g_list_prepend(NULL, vv1);
3536 if(edge_is_blocked(op_e
)) {
3537 goto triangle_candidate_points_from_vertex_exit
;
3539 // v1 = tedge_v1(op_e);
3540 // v2 = tedge_v2(op_e);
3542 if(v
== tedge_v1(e1
)) {
3543 i
= edge_routing_first_not_temp(e1
);
3545 i
= edge_routing_last_not_temp(e1
);
3549 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3551 if(temp
->parent
== tedge_v2(op_e
) || temp
->child
== tedge_v2(op_e
)) {
3553 printf("temp -> op_e->v2\n");
3555 goto triangle_candidate_points_from_vertex_exit
;
3557 if(temp
->parent
->routingedge
== op_e
) {
3560 printf("vv1->parent\n");
3563 }else if(temp
->child
->routingedge
== op_e
) {
3566 printf("vv1->child\n");
3572 printf("temp -> e2?\n");
3573 printf("op_e = %f,%f\t\t%f,%f\n", vx(edge_v1(op_e
)), vy(edge_v1(op_e
)), vx(edge_v2(op_e
)), vy(edge_v2(op_e
)) );
3574 if(temp
->parent
->routingedge
)
3575 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3576 vx(edge_v1(temp
->parent
->routingedge
)), vy(edge_v1(temp
->parent
->routingedge
)),
3577 vx(edge_v2(temp
->parent
->routingedge
)), vy(edge_v2(temp
->parent
->routingedge
))
3580 printf("temp->parent->routingedge = NULL\n");
3582 if(temp
->child
->routingedge
)
3583 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3584 vx(edge_v1(temp
->child
->routingedge
)), vy(edge_v1(temp
->child
->routingedge
)),
3585 vx(edge_v2(temp
->child
->routingedge
)), vy(edge_v2(temp
->child
->routingedge
))
3588 printf("temp->child->routingedge = NULL\n");
3590 goto triangle_candidate_points_from_vertex_exit
;
3594 vv1
= tedge_v1(op_e
);
3596 printf("nothing on e1\n");
3600 if(v
== tedge_v1(e2
)) {
3601 i
= edge_routing_first_not_temp(e2
);
3603 i
= edge_routing_last_not_temp(e2
);
3607 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3609 if(temp
->parent
== tedge_v1(op_e
) || temp
->child
== tedge_v1(op_e
)) {
3611 printf("temp -> op_e->v2\n");
3613 goto triangle_candidate_points_from_vertex_exit
;
3616 if(temp
->parent
->routingedge
== op_e
) {
3619 printf("vv2->parent\n");
3621 }else if(temp
->child
->routingedge
== op_e
) {
3624 printf("vv2->child\n");
3630 printf("temp -> e1?\n");
3631 printf("op_e = %f,%f\t\t%f,%f\n", vx(edge_v1(op_e
)), vy(edge_v1(op_e
)), vx(edge_v2(op_e
)), vy(edge_v2(op_e
)) );
3632 if(temp
->parent
->routingedge
)
3633 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3634 vx(edge_v1(temp
->parent
->routingedge
)), vy(edge_v1(temp
->parent
->routingedge
)),
3635 vx(edge_v2(temp
->parent
->routingedge
)), vy(edge_v2(temp
->parent
->routingedge
))
3638 printf("temp->parent->routingedge = NULL\n");
3640 if(temp
->child
->routingedge
)
3641 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3642 vx(edge_v1(temp
->child
->routingedge
)), vy(edge_v1(temp
->child
->routingedge
)),
3643 vx(edge_v2(temp
->child
->routingedge
)), vy(edge_v2(temp
->child
->routingedge
))
3646 printf("temp->child->routingedge = NULL\n");
3648 goto triangle_candidate_points_from_vertex_exit
;
3652 vv2
= tedge_v2(op_e
);
3654 printf("nothing on e2\n");
3659 printf("size of e1 routing = %d e2 routing = %d op_e routing = %d\n",
3660 g_list_length(edge_routing(e1
)), g_list_length(edge_routing(e2
)), g_list_length(edge_routing(op_e
)));
3665 print_vertex(constraintv
);
3666 printf("constraintv %f,%f returning\n", vx(constraintv
), vy(constraintv
));
3668 return g_list_prepend(NULL
, constraintv
);
3671 i
= edge_routing(op_e
);
3673 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3675 if(temp
->parent
== v
|| temp
->child
== v
) {
3676 rval
= g_list_concat(rval
, candidate_vertices(vv1
, temp
, dest
, op_e
));
3683 rval
= g_list_concat(rval
, candidate_vertices(vv1
, vv2
, dest
, op_e
));
3689 triangle_candidate_points_from_vertex_exit
:
3690 if(constraintv
) //delete_vertex(constraintv);
3691 g_hash_table_insert(routedata
->alltemppoints
, constraintv
, constraintv
);
3699 routedata_insert_temppoints(toporouter_route_t
*data
, GList
*temppoints
) {
3700 GList
*j
= temppoints
;
3702 g_hash_table_insert(data
->alltemppoints
, j
->data
, j
->data
);
3709 constraint_route_test(toporouter_constraint_t
*c
, toporouter_route_t
*routedata
)
3711 if(c
->box
->cluster
&& c
->box
->cluster
->netlist
== routedata
->src
->netlist
) {
3712 if(c
->box
->cluster
->c
== routedata
->dest
->c
|| c
->box
->cluster
->c
== routedata
->src
->c
) return 1;
3718 all_candidates_on_edge(toporouter_edge_t
*e
, toporouter_route_t
*routedata
)
3721 if(edge_is_blocked(e
)) return NULL
;
3723 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3724 GList
*i
= edge_routing(e
);
3725 toporouter_vertex_t
*pv
= tedge_v1(e
);
3728 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3729 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) {
3730 rval
= g_list_concat(rval
, candidate_vertices(pv
, v
, TOPOROUTER_VERTEX(routedata
->destvertices
->data
), e
));
3736 rval
= g_list_concat(rval
, candidate_vertices(pv
, tedge_v2(e
), TOPOROUTER_VERTEX(routedata
->destvertices
->data
), e
));
3737 }else if(TOPOROUTER_CONSTRAINT(e
)->box
->type
== BOARD
) {
3739 }else if(constraint_route_test(TOPOROUTER_CONSTRAINT(e
), routedata
)) {
3740 toporouter_vertex_t
*consv
= new_temp_toporoutervertex_in_segment(e
, tedge_v1(e
), tvdistance(tedge_v1(e
), tedge_v2(e
)) / 2., tedge_v2(e
));
3741 rval
= g_list_prepend(rval
, consv
);
3742 // g_hash_table_insert(routedata->alltemppoints, consv, consv);
3749 triangle_all_candidate_points_from_vertex(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_route_t
*routedata
)
3751 toporouter_edge_t
*op_e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3752 return all_candidates_on_edge(op_e
, routedata
);
3756 triangle_all_candidate_points_from_edge(toporouter_t
*r
, GtsTriangle
*t
, toporouter_edge_t
*e
, toporouter_route_t
*routedata
,
3757 toporouter_vertex_t
**dest
, toporouter_vertex_t
*curpoint
)
3759 toporouter_vertex_t
*op_v
;
3760 toporouter_edge_t
*e1
, *e2
;
3761 GList
*i
, *rval
= NULL
, *rval2
= NULL
;
3762 toporouter_vertex_t
*boxpoint
= NULL
;
3763 guint e1intcap
, e2intcap
;
3765 op_v
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t
, GTS_EDGE(e
)));
3768 if(vertex_bbox(op_v
)) boxpoint
= TOPOROUTER_VERTEX(vertex_bbox(op_v
)->point
);
3770 if(g_list_find(routedata
->destvertices
, op_v
)) {
3771 rval
= g_list_prepend(rval
, op_v
);
3774 }else if(g_list_find(routedata
->destvertices
, boxpoint
)) {
3776 }else if(g_list_find(routedata
->srcvertices
, op_v
)) {
3777 rval
= g_list_prepend(rval
, op_v
);
3780 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v1(e
)));
3781 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v2(e
)));
3783 rval
= g_list_concat(rval
, all_candidates_on_edge(e1
, routedata
));
3784 rval
= g_list_concat(rval
, all_candidates_on_edge(e2
, routedata
));
3786 e1intcap
= check_triangle_interior_capacity(t
, tedge_v1(e
), curpoint
, e2
, e
, e1
);
3787 e2intcap
= check_triangle_interior_capacity(t
, tedge_v2(e
), curpoint
, e1
, e
, e2
);
3791 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3794 rval2
= g_list_prepend(rval2
, v
);
3795 else if(v
->routingedge
== e1
&& !(!TOPOROUTER_IS_CONSTRAINT(e1
) && !e1intcap
))
3796 rval2
= g_list_prepend(rval2
, v
);
3797 else if(v
->routingedge
== e2
&& !(!TOPOROUTER_IS_CONSTRAINT(e2
) && !e2intcap
))
3798 rval2
= g_list_prepend(rval2
, v
);
3808 triangle_candidate_points_from_edge(toporouter_t
*r
, GtsTriangle
*t
, toporouter_edge_t
*e
, toporouter_vertex_t
*v
, toporouter_vertex_t
**dest
,
3809 toporouter_route_t
*routedata
)
3811 toporouter_vertex_t
*v1
, *v2
, *op_v
, *vv
= NULL
, *e1constraintv
= NULL
, *e2constraintv
= NULL
;
3812 toporouter_edge_t
*e1
, *e2
;
3813 GList
*e1cands
= NULL
, *e2cands
= NULL
, *rval
= NULL
;
3814 guint noe1
= 0, noe2
= 0;
3816 op_v
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t
, GTS_EDGE(e
)));
3818 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v1(e
)));
3819 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v2(e
)));
3823 // v1 is prev dir, v2 is next dir
3824 edge_adjacent_vertices(e
, v
, &v1
, &v2
);
3826 if(TOPOROUTER_IS_CONSTRAINT(e1
)) {
3827 GList
*i
= edge_routing(e1
);
3829 if(TOPOROUTER_CONSTRAINT(e1
)->box
->type
== BOARD
) {
3831 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e1
), routedata
)) {
3834 printf("noe1 netlist\n");
3838 if(v1
== tedge_v1(e
) ||
3839 (v1
->parent
->routingedge
&& v1
->parent
->routingedge
== e1
) ||
3840 (v1
->child
->routingedge
&& v1
->child
->routingedge
== e1
)) {
3841 e1constraintv
= new_temp_toporoutervertex_in_segment(e1
, tedge_v1(e1
), gts_point_distance(GTS_POINT(edge_v1(e1
)), GTS_POINT(edge_v2(e1
))) / 2., tedge_v2(e1
));
3845 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3847 if((temp
->child
== tedge_v2(e
) || temp
->parent
== tedge_v2(e
)) && !(temp
->flags
& VERTEX_FLAG_TEMP
)) noe2
= 1;
3852 goto triangle_candidate_points_e2
;
3855 if(edge_is_blocked(e1
)) {
3857 goto triangle_candidate_points_e2
;
3860 if(v1
== tedge_v1(e
)) {
3862 toporouter_vertex_t
*vv1
, *vv2
;
3863 edge_adjacent_vertices(e1
, v1
, &vv1
, &vv2
);
3866 printf("v1 == e->v1\n");
3870 // candidates from v1 until vv1
3873 // candidates from v1 until vv2
3877 if(!e1constraintv
) e1cands
= candidate_vertices(v1
, vv
, *dest
, e1
);
3880 if(vv
->parent
== tedge_v2(e
) || vv
->child
== tedge_v2(e
)) {
3888 }else if(v1
->parent
!= op_v
&& v1
->child
!= op_v
) {
3889 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
3892 printf("v1 != e->v1\n");
3895 if(v1
->parent
->routingedge
== e1
) {
3898 printf("v1 parent = e1\n");
3900 if(op_v
== tedge_v1(e1
)) {
3901 // candidates from v1->parent until prev vertex
3902 vv2
= edge_routing_prev_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->parent
)->prev
);
3904 // candidates from v1->parent until next vertex
3905 vv2
= edge_routing_next_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->parent
)->next
);
3908 }else if(v1
->child
->routingedge
== e1
) {
3911 printf("v1 child = e1\n");
3913 if(op_v
== tedge_v1(e1
)) {
3914 // candidates from v1->child until prev vertex
3915 vv2
= edge_routing_prev_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->child
)->prev
);
3917 // candidates from v1->child until next vertex
3918 vv2
= edge_routing_next_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->child
)->next
);
3925 goto triangle_candidate_points_e2
;
3929 if(vv2
->parent
== tedge_v2(e
) || vv2
->child
== tedge_v2(e
)) {
3936 if(!e1constraintv
) e1cands
= candidate_vertices(vv1
, vv2
, *dest
, e1
);
3942 if(vv
&& vv
== op_v
) {
3943 toporouter_vertex_t
*boxpoint
= NULL
;
3945 if(vertex_bbox(op_v
)) boxpoint
= TOPOROUTER_VERTEX(vertex_bbox(op_v
)->point
);
3947 if(g_list_find(routedata
->destvertices
, op_v
)) {
3948 rval
= g_list_prepend(rval
, op_v
);
3950 }else if(g_list_find(routedata
->destvertices
, boxpoint
)) {
3952 }else if(g_list_find(routedata
->srcvertices
, op_v
)) {
3953 rval
= g_list_prepend(rval
, op_v
);
3957 triangle_candidate_points_e2
:
3960 // printf("noe2\n");
3961 goto triangle_candidate_points_finish
;
3964 if(TOPOROUTER_IS_CONSTRAINT(e2
)) {
3965 GList
*i
= edge_routing(e2
);
3967 if(TOPOROUTER_CONSTRAINT(e2
)->box
->type
== BOARD
) {
3969 // goto triangle_candidate_points_finish;
3970 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e2
), routedata
)) {
3972 printf("noe2 netlist\n");
3975 // goto triangle_candidate_points_finish;
3976 }else if(v2
== tedge_v2(e
) ||
3977 (v2
->parent
->routingedge
&& v2
->parent
->routingedge
== e2
) ||
3978 (v2
->child
->routingedge
&& v2
->child
->routingedge
== e2
)) {
3980 e2constraintv
= new_temp_toporoutervertex_in_segment(e2
, tedge_v1(e2
), gts_point_distance(GTS_POINT(edge_v1(e2
)), GTS_POINT(edge_v2(e2
))) / 2., tedge_v2(e2
));
3985 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3987 if((temp
->child
== tedge_v1(e
) || temp
->parent
== tedge_v1(e
)) && !(temp
->flags
& VERTEX_FLAG_TEMP
))
3995 goto triangle_candidate_points_finish
;
3998 if(edge_is_blocked(e2
)) {
4000 goto triangle_candidate_points_finish
;
4003 if(v2
== tedge_v2(e
)) {
4005 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4006 edge_adjacent_vertices(e2
, v2
, &vv1
, &vv2
);
4009 printf("v2 == e->v2\n");
4013 // candidates from v2 until vv1
4016 // candidates from v2 until vv2
4020 if(!e2constraintv
) e2cands
= candidate_vertices(v2
, vv
, *dest
, e2
);
4023 if(vv
->parent
== tedge_v1(e
) || vv
->child
== tedge_v1(e
)) {
4031 }else if(v2
->parent
!= op_v
&& v2
->child
!= op_v
) {
4032 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4035 printf("v2 == e->v2\n");
4038 if(v2
->parent
->routingedge
== e2
) {
4040 if(op_v
== tedge_v1(e2
)) {
4041 // candidates from v2->parent until prev vertex
4042 vv2
= edge_routing_prev_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->prev
);
4044 // candidates from v2->parent until next vertex
4045 vv2
= edge_routing_next_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->next
);
4048 }else if(v2
->child
->routingedge
== e2
) {
4050 if(op_v
== tedge_v1(e2
)) {
4051 // candidates from v2->child until prev vertex
4052 vv2
= edge_routing_prev_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->prev
);
4054 // candidates from v2->child until next vertex
4055 vv2
= edge_routing_next_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->next
);
4059 goto triangle_candidate_points_finish
;
4063 if(vv2
->parent
== tedge_v1(e
) || vv2
->child
== tedge_v1(e
)) {
4070 if(!e2constraintv
) e2cands
= candidate_vertices(vv1
, vv2
, *dest
, e2
);
4074 triangle_candidate_points_finish
:
4076 v1
= segment_common_vertex(GTS_SEGMENT(e
), GTS_SEGMENT(e1
));
4077 v2
= segment_common_vertex(GTS_SEGMENT(e
), GTS_SEGMENT(e2
));
4079 if(noe1
|| !check_triangle_interior_capacity(t
, v1
, v
, e2
, e
, e1
)) {
4081 printf("freeing e1cands\n");
4083 routedata_insert_temppoints(routedata
, e1cands
);
4084 g_list_free(e1cands
);
4088 if(noe2
|| !check_triangle_interior_capacity(t
, v2
, v
, e1
, e
, e2
)) {
4090 printf("freeing e2cands\n");
4092 routedata_insert_temppoints(routedata
, e2cands
);
4093 g_list_free(e2cands
);
4097 if(!noe1
&& e1constraintv
) {
4098 e1cands
= g_list_prepend(e1cands
, e1constraintv
);
4099 }else if(e1constraintv
) {
4100 g_hash_table_insert(routedata
->alltemppoints
, e1constraintv
, e1constraintv
);
4101 // delete_vertex(e1constraintv);
4104 if(!noe2
&& e2constraintv
) {
4105 e2cands
= g_list_prepend(e2cands
, e2constraintv
);
4106 }else if(e2constraintv
) {
4107 g_hash_table_insert(routedata
->alltemppoints
, e2constraintv
, e2constraintv
);
4108 // delete_vertex(e2constraintv);
4111 if(!noe1
&& !noe2
) return g_list_concat(rval
, g_list_concat(e1cands
, e2cands
));
4113 return g_list_concat(e1cands
, e2cands
);
4117 compute_candidate_points(toporouter_t
*tr
, toporouter_layer_t
*l
, toporouter_vertex_t
*curpoint
, toporouter_route_t
*data
,
4118 toporouter_vertex_t
**closestdest
)
4120 GList
*r
= NULL
, *j
;
4121 toporouter_edge_t
*edge
= curpoint
->routingedge
, *tempedge
;
4123 if(vertex_keepout_test(tr
, curpoint
)) goto compute_candidate_points_finish
;
4125 /* direct connection */
4126 // if(curpoint == TOPOROUTER_VERTEX(data->src->point))
4127 if((tempedge
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(curpoint
), GTS_VERTEX(*closestdest
))))) {
4129 if(TOPOROUTER_IS_CONSTRAINT(tempedge
)) {
4130 goto compute_candidate_points_finish
;
4132 if(!tempedge
->routing
) {
4133 r
= g_list_prepend(NULL
, *closestdest
);
4134 tempedge
->flags
|= EDGE_FLAG_DIRECTCONNECTION
;
4135 goto compute_candidate_points_finish
;
4138 printf("Direct connection, but has routing\n");
4143 /* if we get to here, there is routing blocking the direct connection,
4144 * continue as per normal */
4147 /* a real point origin */
4148 if(!(curpoint
->flags
& VERTEX_FLAG_TEMP
)) {
4149 GSList
*triangles
, *i
;
4150 i
= triangles
= gts_vertex_triangles(GTS_VERTEX(curpoint
), NULL
);
4152 printf("triangle count = %d\n", g_slist_length(triangles
));
4155 GtsTriangle
*t
= GTS_TRIANGLE(i
->data
);
4158 if(tr
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) temppoints
= triangle_all_candidate_points_from_vertex(t
, curpoint
, data
);
4159 else temppoints
= triangle_candidate_points_from_vertex(t
, curpoint
, *closestdest
, data
);
4162 printf("\treturned %d points\n", g_list_length(temppoints
));
4164 routedata_insert_temppoints(data
, temppoints
);
4166 r
= g_list_concat(r
, temppoints
);
4169 g_slist_free(triangles
);
4170 }else /* a temp point */ {
4171 int prevwind
= vertex_wind(GTS_SEGMENT(edge
)->v1
, GTS_SEGMENT(edge
)->v2
, GTS_VERTEX(curpoint
->parent
));
4172 // printf("tempoint\n");
4174 GSList
*i
= GTS_EDGE(edge
)->triangles
;
4177 GtsVertex
*oppv
= gts_triangle_vertex_opposite(GTS_TRIANGLE(i
->data
), GTS_EDGE(edge
));
4178 if(prevwind
!= vertex_wind(GTS_SEGMENT(edge
)->v1
, GTS_SEGMENT(edge
)->v2
, oppv
)) {
4181 if(tr
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) temppoints
= triangle_all_candidate_points_from_edge(tr
, GTS_TRIANGLE(i
->data
), edge
,
4182 data
, closestdest
, curpoint
);
4183 else temppoints
= triangle_candidate_points_from_edge(tr
, GTS_TRIANGLE(i
->data
), edge
, curpoint
, closestdest
, data
);
4187 toporouter_vertex_t
*tempj
= TOPOROUTER_VERTEX(j
->data
);
4188 if(tempj
->flags
& VERTEX_FLAG_TEMP
)
4189 g_hash_table_insert(data
->alltemppoints
, j
->data
, j
->data
);
4192 printf("got cand not a temp\n");
4196 r
= g_list_concat(r
, temppoints
);
4204 compute_candidate_points_finish
:
4206 if(vertex_bbox(curpoint
) && vertex_bbox(curpoint
)->cluster
) {
4207 if(vertex_bbox(curpoint
)->cluster
->c
== data
->src
->c
) {
4208 r
= g_list_concat(r
, g_list_copy(data
->srcvertices
));
4216 temp_point_clean(gpointer key
, gpointer value
, gpointer user_data
)
4218 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(value
);
4219 if(tv
->flags
& VERTEX_FLAG_TEMP
) {
4220 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
4221 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
4223 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
4224 gts_object_destroy ( GTS_OBJECT(tv
) );
4230 clean_routing_edges(toporouter_t
*r
, toporouter_route_t
*data
)
4232 g_hash_table_foreach_remove(data
->alltemppoints
, temp_point_clean
, NULL
);
4233 g_hash_table_destroy(data
->alltemppoints
);
4234 data
->alltemppoints
= NULL
;
4238 path_score(toporouter_t
*r
, GList
*path
)
4241 toporouter_vertex_t
*pv
= NULL
;
4242 toporouter_vertex_t
*v0
= NULL
;
4244 if(!path
) return INFINITY
;
4246 v0
= TOPOROUTER_VERTEX(path
->data
);
4249 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(path
->data
);
4252 score
+= gts_point_distance(GTS_POINT(pv
), GTS_POINT(v
));
4253 if(pv
!= v0
&& vz(pv
) != vz(v
))
4255 score
+= r
->viacost
;
4267 print_vertices(GList
*vertices
)
4270 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(vertices
->data
);
4272 print_bbox(vertex_bbox(v
));
4273 if(vertex_bbox(v
)) {
4274 printf("has bbox\n");
4275 if(vertex_bbox(v
)->cluster
)
4276 printf("has cluster\n");
4278 printf("no cluster\n");
4279 }else printf("no bbox\n");
4280 vertices
= vertices
->next
;
4285 space_edge(gpointer item
, gpointer data
)
4287 toporouter_edge_t
*e
= TOPOROUTER_EDGE(item
);
4291 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
4293 if(!edge_routing(e
) || !g_list_length(edge_routing(e
))) return 0;
4295 forces
= (gdouble
*)malloc(sizeof(double) * g_list_length(edge_routing(e
)));
4297 for(guint j
=0;j
<100;j
++) {
4299 guint equilibrium
= 1;
4301 i
= edge_routing(e
);
4303 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4307 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->prev->data), v);
4308 ms
= min_spacing(TOPOROUTER_VERTEX(i
->prev
->data
), v
);
4309 d
= gts_point_distance(GTS_POINT(i
->prev
->data
), GTS_POINT(v
));
4311 // ms = min_vertex_net_spacing(v, tedge_v1(e));
4312 ms
= min_spacing(v
, tedge_v1(e
));
4313 d
= gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(v
));
4316 if(d
< ms
) forces
[k
] = ms
- d
;
4317 else forces
[k
] = 0.;
4320 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->next->data), v);
4321 ms
= min_spacing(TOPOROUTER_VERTEX(i
->next
->data
), v
);
4322 d
= gts_point_distance(GTS_POINT(i
->next
->data
), GTS_POINT(v
));
4324 // ms = min_vertex_net_spacing(v, tedge_v2(e));
4325 ms
= min_spacing(v
, tedge_v2(e
));
4326 d
= gts_point_distance(GTS_POINT(edge_v2(e
)), GTS_POINT(v
));
4329 if(d
< ms
) forces
[k
] += d
- ms
;
4335 i
= edge_routing(e
);
4337 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4338 if(forces
[k
] > EPSILON
|| forces
[k
] < -EPSILON
) equilibrium
= 0;
4339 vertex_move_towards_vertex_values(GTS_VERTEX(v
), edge_v2(e
), forces
[k
] * 0.1, &(GTS_POINT(v
)->x
), &(GTS_POINT(v
)->y
));
4344 // printf("reached equilibriium at %d\n", j);
4355 swap_vertices(toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
4357 toporouter_vertex_t
*tempv
= *v1
;
4363 split_edge_routing(toporouter_vertex_t
*v
, GList
**l1
, GList
**l2
)
4368 g_assert(v
->routingedge
);
4370 base
= g_list_find(vrouting(v
), v
);
4372 *l1
= g_list_prepend(*l1
, tedge_v1(v
->routingedge
));
4373 *l2
= g_list_prepend(*l2
, tedge_v2(v
->routingedge
));
4379 if(!(TOPOROUTER_VERTEX(i
->data
)->flags
& VERTEX_FLAG_TEMP
)) *l2
= g_list_prepend(*l2
, i
->data
);
4385 if(!(TOPOROUTER_VERTEX(i
->data
)->flags
& VERTEX_FLAG_TEMP
)) *l1
= g_list_prepend(*l1
, i
->data
);
4391 vertices_routing_conflicts(toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
)
4393 toporouter_edge_t
*e
;
4394 GList
*rval
= NULL
, *l1
= NULL
, *l2
= NULL
, *i
;
4396 if(vz(v
) != vz(pv
)) return NULL
;
4399 if(!v
->routingedge
&& !pv
->routingedge
) {
4400 e
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), GTS_VERTEX(pv
)));
4402 i
= edge_routing(e
);
4404 rval
= g_list_prepend(rval
, TOPOROUTER_VERTEX(i
->data
)->route
);
4410 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
) && TOPOROUTER_IS_CONSTRAINT(pv
->routingedge
))
4413 if(TOPOROUTER_IS_CONSTRAINT(pv
->routingedge
)) swap_vertices(&pv
, &v
);
4415 if(!v
->routingedge
) swap_vertices(&pv
, &v
);
4419 split_edge_routing(v
, &l1
, &l2
);
4423 if(!pv
->routingedge
) {
4424 toporouter_edge_t
*e1
, *e2
;
4425 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv
), edge_v1(e
)));
4426 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv
), edge_v2(e
)));
4428 l1
= g_list_concat(l1
, g_list_copy(edge_routing(e1
)));
4429 l2
= g_list_concat(l2
, g_list_copy(edge_routing(e2
)));
4432 GList
*pvlist1
= NULL
, *pvlist2
= NULL
;
4433 toporouter_vertex_t
*commonv
= route_vertices_common_vertex(v
, pv
);
4437 split_edge_routing(pv
, &pvlist1
, &pvlist2
);
4439 if(commonv
== tedge_v1(e
)) {
4440 toporouter_edge_t
*ope
;
4442 if(commonv
== tedge_v1(pv
->routingedge
)) {
4443 l1
= g_list_concat(l1
, pvlist1
);
4444 l2
= g_list_concat(l2
, pvlist2
);
4445 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e
), edge_v2(pv
->routingedge
)));
4447 l1
= g_list_concat(l1
, pvlist2
);
4448 l2
= g_list_concat(l2
, pvlist1
);
4449 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e
), edge_v1(pv
->routingedge
)));
4452 l2
= g_list_concat(l2
, g_list_copy(edge_routing(ope
)));
4455 toporouter_edge_t
*ope
;
4456 if(commonv
== tedge_v1(pv
->routingedge
)) {
4457 l1
= g_list_concat(l1
, pvlist2
);
4458 l2
= g_list_concat(l2
, pvlist1
);
4459 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e
), edge_v2(pv
->routingedge
)));
4461 l1
= g_list_concat(l1
, pvlist1
);
4462 l2
= g_list_concat(l2
, pvlist2
);
4463 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e
), edge_v1(pv
->routingedge
)));
4466 l1
= g_list_concat(l1
, g_list_copy(edge_routing(ope
)));
4472 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
4474 if(curv
->flags
& VERTEX_FLAG_ROUTE
&& (g_list_find(l2
, curv
->parent
) || g_list_find(l2
, curv
->child
))) {
4475 if(!g_list_find(rval
, curv
->route
)) rval
= g_list_prepend(rval
, curv
->route
);
4481 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
4483 if(curv
->flags
& VERTEX_FLAG_ROUTE
&& (g_list_find(l1
, curv
->parent
) || g_list_find(l1
, curv
->child
))) {
4484 if(!g_list_find(rval
, curv
->route
)) rval
= g_list_prepend(rval
, curv
->route
);
4496 vertices_routing_conflict_cost(toporouter_t
*r
, toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
, guint
*n
)
4498 GList
*conflicts
= vertices_routing_conflicts(v
, pv
), *i
;
4499 gdouble penalty
= 0.;
4504 penalty
+= TOPOROUTER_ROUTE(i
->data
)->score
;
4507 g_list_free(conflicts
);
4508 // if(penalty > 0.) printf("conflict penalty of %f with %f,%f %f,%f\n", penalty, vx(v), vy(v), vx(pv), vy(pv));
4513 gcost(toporouter_t
*r
, toporouter_route_t
*data
, toporouter_vertex_t
*srcv
, toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
, guint
*n
,
4514 toporouter_netlist_t
*pair
)
4516 gdouble cost
= 0., segcost
;
4520 if(g_list_find(data
->srcvertices
, v
)) return 0.;
4522 segcost
= tvdistance(pv
, v
);
4524 if(pair
&& !TOPOROUTER_IS_CONSTRAINT(v
->routingedge
) && v
->routingedge
) {
4525 GList
*list
= g_list_find(v
->routingedge
->routing
, v
);
4526 toporouter_vertex_t
*pv
= edge_routing_prev_not_temp(v
->routingedge
, list
);
4527 toporouter_vertex_t
*nv
= edge_routing_next_not_temp(v
->routingedge
, list
);
4529 if(pv
->route
&& pv
->route
->netlist
== pair
) {
4530 }else if(nv
->route
&& nv
->route
->netlist
== pair
) {
4536 cost
= pv
->gcost
+ segcost
;
4538 if(r
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) {
4539 gdouble conflictcost
= 0.;
4541 if(pv
&& v
!= pv
&& vz(v
) == vz(pv
)) conflictcost
= vertices_routing_conflict_cost(r
, v
, pv
, n
);
4543 if(!(r
->flags
& TOPOROUTER_FLAG_DETOUR
&& *n
== 1)) {
4544 cost
+= conflictcost
* (pow(*n
,2));
4551 #define vlayer(x) (&r->layers[(int)vz(x)])
4554 candidate_is_available(toporouter_vertex_t
*pv
, toporouter_vertex_t
*v
)
4556 // TODO: still needed?
4558 if(pv
== v
) return 0;
4566 route(toporouter_t
*r
, toporouter_route_t
*data
, guint debug
)
4568 GtsEHeap
*openlist
= gts_eheap_new(route_heap_cmp
, NULL
);
4569 GList
*closelist
= NULL
;
4570 GList
*i
, *rval
= NULL
;
4571 toporouter_netlist_t
*pair
= NULL
;
4574 toporouter_vertex_t
*srcv
= NULL
, *destv
= NULL
, *curpoint
= NULL
;
4575 toporouter_layer_t
*cur_layer
; //, *dest_layer;
4577 g_assert(data
->src
->c
!= data
->dest
->c
);
4579 if(data
->destvertices
) g_list_free(data
->destvertices
);
4580 if(data
->srcvertices
) g_list_free(data
->srcvertices
);
4582 data
->destvertices
= cluster_vertices(r
, data
->dest
);
4583 data
->srcvertices
= cluster_vertices(r
, data
->src
);
4585 closest_cluster_pair(r
, data
->srcvertices
, data
->destvertices
, &curpoint
, &destv
);
4587 if(!curpoint
|| !destv
) goto routing_return
;
4590 cur_layer
= vlayer(curpoint
);
4591 //dest_layer = vlayer(destv);
4595 data
->alltemppoints
= g_hash_table_new(g_direct_hash
, g_direct_equal
);
4597 curpoint
->parent
= NULL
;
4598 curpoint
->child
= NULL
;
4599 curpoint
->gcost
= 0.;
4601 curpoint
->hcost
= simple_h_cost(r
, curpoint
, destv
);
4603 if(data
->netlist
&& data
->netlist
->pair
) {
4604 GList
*i
= r
->routednets
;
4606 toporouter_route_t
*curroute
= TOPOROUTER_ROUTE(i
->data
);
4607 if(curroute
->netlist
== data
->netlist
->pair
) {
4608 pair
= data
->netlist
->pair
;
4615 gts_eheap_insert(openlist
, curpoint
);
4617 while(gts_eheap_size(openlist
) > 0) {
4618 GList
*candidatepoints
;
4619 data
->curpoint
= curpoint
;
4620 //draw_route_status(r, closelist, openlist, curpoint, data, count++);
4622 curpoint
= TOPOROUTER_VERTEX( gts_eheap_remove_top(openlist
, NULL
) );
4623 if(curpoint
->parent
&& !(curpoint
->flags
& VERTEX_FLAG_TEMP
)) {
4624 if(vz(curpoint
) != vz(destv
)) {
4625 toporouter_vertex_t
*tempv
;
4626 cur_layer
= vlayer(curpoint
);//&r->layers[(int)vz(curpoint)];
4627 tempv
= closest_dest_vertex(r
, curpoint
, data
);
4630 //dest_layer = vlayer(destv);//&r->layers[(int)vz(destv)];
4636 // destpoint = closest_dest_vertex(r, curpoint, data);
4637 // dest_layer = &r->layers[(int)vz(destpoint)];
4639 if(g_list_find(data
->destvertices
, curpoint
)) {
4640 toporouter_vertex_t
*temppoint
= curpoint
;
4647 data
->path
= g_list_prepend(data
->path
, temppoint
);
4648 if(g_list_find(data
->srcvertices
, temppoint
)) {
4650 if(r
->flags
& TOPOROUTER_FLAG_AFTERORDER
) break;
4652 temppoint
= temppoint
->parent
;
4655 data
->score
= path_score(r
, data
->path
);
4657 printf("ROUTE: path score = %f computation cost = %d\n", data
->score
, count
);
4660 if(srcv
->bbox
->cluster
!= data
->src
) {
4661 data
->src
= srcv
->bbox
->cluster
;
4664 if(destv
->bbox
->cluster
!= data
->dest
) {
4665 data
->dest
= destv
->bbox
->cluster
;
4669 closelist_insert(curpoint
);
4671 printf("\n\n\n*** ROUTE COUNT = %d\n", count
);
4673 candidatepoints
= compute_candidate_points(r
, cur_layer
, curpoint
, data
, &destv
);
4675 //#ifdef DEBUG_ROUTE
4676 /*********************
4677 if(debug && !strcmp(data->dest->netlist, " unnamed_net2"))
4679 unsigned int mask = ~(VERTEX_FLAG_RED | VERTEX_FLAG_GREEN | VERTEX_FLAG_BLUE);
4683 for(j=0;j<groupcount();j++) {
4684 i = r->layers[j].vertices;
4686 TOPOROUTER_VERTEX(i->data)->flags &= mask;
4691 i = candidatepoints;
4693 TOPOROUTER_VERTEX(i->data)->flags |= VERTEX_FLAG_GREEN;
4694 // printf("flagged a candpoint @ %f,%f\n",
4695 // vx(i->data), vy(i->data));
4699 curpoint->flags |= VERTEX_FLAG_BLUE;
4700 if(curpoint->parent)
4701 curpoint->parent->flags |= VERTEX_FLAG_RED;
4704 for(j=0;j<groupcount();j++) {
4705 GList *datas = g_list_prepend(NULL, data);
4706 sprintf(buffer, "route-%d-%05d.png", j, count);
4707 toporouter_draw_surface(r, r->layers[j].surface, buffer, 1024, 1024, 2, datas, j, candidatepoints);
4712 *********************/
4714 // if(count > 100) exit(0);
4715 i
= candidatepoints
;
4717 toporouter_vertex_t
*temppoint
= TOPOROUTER_VERTEX(i
->data
);
4718 if(!g_list_find(closelist
, temppoint
) && candidate_is_available(curpoint
, temppoint
)) { //&& temppoint != curpoint) {
4719 toporouter_heap_search_data_t heap_search_data
= { temppoint
, NULL
};
4722 gdouble temp_g_cost
= gcost(r
, data
, srcv
, temppoint
, curpoint
, &temp_gn
, pair
);
4725 gts_eheap_foreach(openlist
,toporouter_heap_search
, &heap_search_data
);
4727 if(heap_search_data
.result
) {
4728 if(temp_g_cost
< temppoint
->gcost
) {
4730 temppoint
->gcost
= temp_g_cost
;
4731 temppoint
->gn
= temp_gn
;
4733 temppoint
->parent
= curpoint
;
4734 curpoint
->child
= temppoint
;
4736 gts_eheap_update(openlist
);
4739 temppoint
->parent
= curpoint
;
4740 curpoint
->child
= temppoint
;
4742 temppoint
->gcost
= temp_g_cost
;
4743 temppoint
->gn
= temp_gn
;
4745 temppoint
->hcost
= simple_h_cost(r
, temppoint
, destv
);
4746 // if(cur_layer != dest_layer) temppoint->hcost += r->viacost;
4747 gts_eheap_insert(openlist
, temppoint
);
4753 g_list_free(candidatepoints
);
4757 printf("ROUTE: could not find path!\n");
4760 data
->score
= INFINITY
;
4761 clean_routing_edges(r
, data
);
4764 //TOPOROUTER_VERTEX(data->src->point)->parent = NULL;
4765 //TOPOROUTER_VERTEX(data->src->point)->child = NULL;
4766 goto routing_return
;
4771 for(i=0;i<groupcount();i++) {
4773 sprintf(buffer, "route-error-%d-%d.png", r->routecount, i);
4774 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1280, 1280, 2, data, i, NULL);
4781 // printf(" * finished a*\n");
4785 for(i=0;i<groupcount();i++) {
4787 sprintf(buffer, "route-preclean-%d-%d.png", i, r->routecount);
4788 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, data, i, NULL);
4796 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
4798 if(tv->routingedge) {
4799 GList *list = g_list_find(edge_routing(tv->routingedge), tv);
4800 toporouter_vertex_t *restartv = NULL, *boxpoint;
4805 if(vertex_bbox(tedge_v2(tv->routingedge)))
4806 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v2(tv->routingedge))->point);
4810 if(tedge_v2(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v2(tv->routingedge)))
4811 restartv = tedge_v2(tv->routingedge);
4812 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
4813 restartv = boxpoint;
4817 if(vertex_bbox(tedge_v1(tv->routingedge)))
4818 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v1(tv->routingedge))->point);
4822 if(tedge_v1(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v1(tv->routingedge)))
4823 restartv = tedge_v1(tv->routingedge);
4824 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
4825 restartv = boxpoint;
4830 clean_routing_edges(r, data);
4831 gts_eheap_destroy(openlist);
4832 g_list_free(closelist);
4833 openlist = gts_eheap_new(route_heap_cmp, NULL);
4835 g_list_free(data->path);
4836 printf("ROUTING RESTARTING with new src %f,%f,%f\n", vx(restartv), vy(restartv), vz(restartv));
4837 curpoint = restartv;
4847 toporouter_vertex_t
*pv
= NULL
;
4848 GList
*i
= data
->path
;
4850 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
4852 if(pv
&& g_list_find(data
->srcvertices
, tv
)) {
4853 GList
*temp
= g_list_copy(i
);
4854 g_list_free(data
->path
);
4864 toporouter_vertex_t
*pv
= NULL
;
4865 GList
*i
= data
->path
;
4867 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
4868 if(tv
->flags
& VERTEX_FLAG_TEMP
) {
4869 tv
->flags
^= VERTEX_FLAG_TEMP
;
4870 tv
->flags
|= VERTEX_FLAG_ROUTE
;
4872 if(pv
) pv
->child
= tv
;
4874 if(tv
->routingedge
) tv
->route
= data
;
4876 // if(tv->routingedge && !TOPOROUTER_IS_CONSTRAINT(tv->routingedge)) space_edge(tv->routingedge, NULL);
4884 toporouter_vertex_t
*pv
= NULL
, *v
= NULL
;
4886 GList
*i
= data
->path
;
4888 v
= TOPOROUTER_VERTEX(i
->data
);
4901 if(v
) v
->child
= NULL
;
4904 clean_routing_edges(r
, data
);
4907 GList
*i
= data
->path
;
4909 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4911 if(v
->routingedge
&& !TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
4912 space_edge(v
->routingedge
, NULL
);
4919 g_list_free(data
->destvertices
);
4920 g_list_free(data
->srcvertices
);
4921 data
->destvertices
= NULL
;
4922 data
->srcvertices
= NULL
;
4923 gts_eheap_destroy(openlist
);
4924 g_list_free(closelist
);
4926 data
->alltemppoints
= NULL
;
4931 /* moves vertex v d units in the direction of vertex p */
4933 vertex_move_towards_vertex (GtsVertex
*v
,
4937 double theta
= atan2 (GTS_POINT(p
)->y
- GTS_POINT(v
)->y
,
4938 GTS_POINT(p
)->x
- GTS_POINT(v
)->x
);
4940 GTS_POINT(v
)->x
+= d
* cos (theta
);
4941 GTS_POINT(v
)->y
+= d
* sin (theta
);
4946 pathvertex_arcing_through_constraint(toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
)
4948 toporouter_vertex_t
*v
= pathv
->child
;
4950 if(!v
|| !v
->routingedge
) return 0.;
4952 while(v
->flags
& VERTEX_FLAG_ROUTE
&& (tedge_v1(v
->routingedge
) == arcv
|| tedge_v2(v
->routingedge
) == arcv
)) {
4953 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
4954 return gts_point_distance(GTS_POINT(tedge_v1(v
->routingedge
)), GTS_POINT(tedge_v2(v
->routingedge
)));
4959 while(v
->flags
& VERTEX_FLAG_ROUTE
&& (tedge_v1(v
->routingedge
) == arcv
|| tedge_v2(v
->routingedge
) == arcv
)) {
4960 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
4961 return gts_point_distance(GTS_POINT(tedge_v1(v
->routingedge
)), GTS_POINT(tedge_v2(v
->routingedge
)));
4969 vertices_connected(toporouter_vertex_t
*a
, toporouter_vertex_t
*b
)
4971 return ((a
->route
->netlist
== b
->route
->netlist
&& a
->route
->src
->c
== b
->route
->src
->c
) ? 1 : 0);
4975 edge_min_spacing(GList
*list
, toporouter_edge_t
*e
, toporouter_vertex_t
*v
, guint debug
)
4977 toporouter_vertex_t
*origin
;
4980 toporouter_vertex_t
*nextv
, *prevv
;
4981 //toporouter_vertex_t *edgev;
4982 //gdouble constraint_spacing;
4984 if(!list
) return INFINITY
;
4986 // printf("\t CMS %f,%f - %f,%f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), vx(tedge_v2(e)), vy(tedge_v2(e)));
4988 prevv
= origin
= TOPOROUTER_VERTEX(list
->data
);
4993 if(gts_point_distance2(GTS_POINT(origin
), GTS_POINT(edge_v1(e
))) < gts_point_distance2(GTS_POINT(v
), GTS_POINT(edge_v1(e
)))) {
4997 nextv
= edge_routing_next(e
, i
);
4998 if(nextv
->route
&& vertices_connected(nextv
, prevv
)) { i
= i
->next
; continue; }
4999 if(!(nextv
->flags
& VERTEX_FLAG_TEMP
)) {
5000 gdouble ms
= min_spacing(prevv
, nextv
);
5001 if(nextv
== tedge_v2(e
)) {
5002 gdouble cms
= pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i
->data
), tedge_v2(e
));
5003 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v2(e)), vy(tedge_v2(e)), cms, ms);
5004 // if(vx(tedge_v2(e)) > -EPSILON && vx(tedge_v2(e)) < EPSILON) {
5005 // printf("\t\tPROB: ");
5006 // print_vertex(tedge_v2(e));
5008 if(cms
> EPSILON
) space
+= MIN(ms
, cms
/ 2.);
5015 // printf("%f ", space);
5022 nextv
= edge_routing_prev(e
, i
);
5023 if(nextv
->route
&& vertices_connected(nextv
, prevv
)) { i
= i
->prev
; continue; }
5024 if(!(nextv
->flags
& VERTEX_FLAG_TEMP
)) {
5025 gdouble ms
= min_spacing(prevv
, nextv
);
5026 if(nextv
== tedge_v1(e
)) {
5027 gdouble cms
= pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i
->data
), tedge_v1(e
));
5028 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), cms, ms);
5029 // if(vx(tedge_v1(e)) > -EPSILON && vx(tedge_v1(e)) < EPSILON) {
5030 // printf("\t\tPROB: ");
5031 // print_vertex(tedge_v1(e));
5033 if(cms
> EPSILON
) space
+= MIN(ms
, cms
/ 2.);
5040 // printf("%f ", space);
5045 if(TOPOROUTER_IS_CONSTRAINT(e
) && space
> gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) / 2.)
5046 space
= gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) / 2.;
5048 // if(debug) printf("\tedge_min_spacing: %f\n", space);
5052 /* line segment is 1 & 2, point is 3
5053 returns 0 if v3 is outside seg
5056 vertex_line_normal_intersection(gdouble x1
, gdouble y1
, gdouble x2
, gdouble y2
, gdouble x3
, gdouble y3
, gdouble
*x
, gdouble
*y
)
5058 gdouble m1
= cartesian_gradient(x1
,y1
,x2
,y2
);
5059 gdouble m2
= perpendicular_gradient(m1
);
5060 gdouble c2
= (isinf(m2
)) ? x3
: y3
- (m2
* x3
);
5061 gdouble c1
= (isinf(m1
)) ? x1
: y1
- (m1
* x1
);
5068 *x
= (c2
- c1
) / (m1
- m2
);
5070 *y
= (isinf(m2
)) ? y1
: (m2
* (*x
)) + c2
;
5072 if(*x
>= MIN(x1
,x2
) - EPSILON
&& *x
<= MAX(x1
,x2
) + EPSILON
&& *y
>= MIN(y1
,y2
) - EPSILON
&& *y
<= MAX(y1
,y2
) + EPSILON
)
5078 print_toporouter_arc(toporouter_arc_t
*arc
)
5080 // GList *i = arc->vs;
5082 printf("ARC CENTRE: %f,%f ", vx(arc
->centre
), vy(arc
->centre
));// print_vertex(arc->centre);
5083 printf("RADIUS: %f", arc
->r
);
5085 if(arc
->dir
>0) printf(" COUNTERCLOCKWISE ");
5086 else if(arc
->dir
<0) printf(" CLOCKWISE ");
5087 else printf(" COLINEAR(ERROR) ");
5092 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
5093 printf("%f,%f ", vx(v), vy(v));
5101 toporouter_arc_remove(toporouter_oproute_t
*oproute
, toporouter_arc_t
*arc
)
5103 oproute
->arcs
= g_list_remove(oproute
->arcs
, arc
);
5105 if(arc
->v
) arc
->v
->arc
= NULL
;
5109 toporouter_arc_new(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*centre
, gdouble r
, gint dir
)
5111 toporouter_arc_t
*arc
= TOPOROUTER_ARC(gts_object_new(GTS_OBJECT_CLASS(toporouter_arc_class())));
5112 arc
->centre
= centre
;
5119 if(v1
) v1
->arc
= arc
;
5120 arc
->oproute
= oproute
;
5122 arc
->clearance
= NULL
;
5128 path_set_oproute(GList
*path
, toporouter_oproute_t
*oproute
)
5131 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(path
->data
);
5133 if(v
->flags
& VERTEX_FLAG_ROUTE
)
5134 v
->oproute
= oproute
;
5141 print_oproute(toporouter_oproute_t
*oproute
)
5143 GList
*i
= oproute
->arcs
;
5145 printf("Optimized Route:\n");
5146 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", oproute
->netlist
, oproute
->style
);
5147 // printf("%s\n", oproute->netlist);
5149 i = oproute->term1->zlink;
5151 toporouter_vertex_t *thisv = TOPOROUTER_VERTEX(i->data);
5152 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", vertex_bbox(thisv)->netlist, vertex_bbox(thisv)->style);
5156 printf("\t"); print_vertex(oproute
->term1
); printf("\n");
5159 toporouter_arc_t
*arc
= (toporouter_arc_t
*)i
->data
;
5160 printf("\t"); print_toporouter_arc(arc
); printf("\n");
5163 printf("\t"); print_vertex(oproute
->term2
); printf("\n");
5167 export_pcb_drawline(guint layer
, guint x0
, guint y0
, guint x1
, guint y1
, guint thickness
, guint keepaway
)
5171 line
= CreateDrawnLineOnLayer( LAYER_PTR(layer
), x0
, y0
, x1
, y1
,
5172 thickness
, keepaway
,
5173 MakeFlags (AUTOFLAG
| (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
: 0)));
5176 AddObjectToCreateUndoList (LINE_TYPE
, LAYER_PTR(layer
), line
, line
);
5177 d
= coord_distance((double)x0
, (double)y0
, (double)x1
, (double)y1
);
5183 arc_angle(toporouter_arc_t
*arc
)
5185 gdouble x0
, x1
, y0
, y1
;
5187 x0
= arc
->x0
- vx(arc
->centre
);
5188 x1
= arc
->x1
- vx(arc
->centre
);
5189 y0
= arc
->y0
- vy(arc
->centre
);
5190 y1
= arc
->y1
- vy(arc
->centre
);
5192 return fabs(acos(((x0
*x1
)+(y0
*y1
))/(sqrt(pow(x0
,2)+pow(y0
,2))*sqrt(pow(x1
,2)+pow(y1
,2)))));
5196 export_pcb_drawarc(guint layer
, toporouter_arc_t
*a
, guint thickness
, guint keepaway
)
5198 gdouble sa
, da
, theta
;
5203 wind
= coord_wind(a
->x0
, a
->y0
, a
->x1
, a
->y1
, vx(a
->centre
), vy(a
->centre
));
5205 /* NB: PCB's arcs have a funny coorindate system, with 0 degrees as the -ve X axis (left),
5206 * continuing clockwise, with +90 degrees being along the +ve Y axis (bottom). Because
5207 * Y+ points down, our internal angles increase clockwise from the +ve X axis.
5209 sa
= (M_PI
- coord_angle (vx (a
->centre
), vy (a
->centre
), a
->x0
, a
->y0
)) * 180. / M_PI
;
5211 theta
= arc_angle(a
);
5213 if(!a
->dir
|| !wind
) return 0.;
5215 if(a
->dir
!= wind
) theta
= 2. * M_PI
- theta
;
5217 da
= -a
->dir
* theta
* 180. / M_PI
;
5219 if(da
< 1. && da
> -1.) return 0.;
5220 if(da
> 359. || da
< -359.) return 0.;
5222 arc
= CreateNewArcOnLayer(LAYER_PTR(layer
), vx(a
->centre
), vy(a
->centre
), a
->r
, a
->r
,
5223 sa
, da
, thickness
, keepaway
,
5224 MakeFlags( AUTOFLAG
| (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
: 0)));
5227 AddObjectToCreateUndoList( ARC_TYPE
, LAYER_PTR(layer
), arc
, arc
);
5235 calculate_term_to_arc(toporouter_vertex_t
*v
, toporouter_arc_t
*arc
, guint dir
)
5237 gdouble theta
, a
, b
, bx
, by
, a0x
, a0y
, a1x
, a1y
;
5240 theta
= acos(arc
->r
/ gts_point_distance(GTS_POINT(v
), GTS_POINT(arc
->centre
)));
5241 a
= arc
->r
* sin(theta
);
5242 b
= arc
->r
* cos(theta
);
5244 printf("drawing arc with r %f theta %f d %f centre = %f,%f\n", arc
->r
, theta
, gts_point_distance(GTS_POINT(v
), GTS_POINT(arc
->centre
)), vx(arc
->centre
), vy(arc
->centre
));
5246 point_from_point_to_point(arc
->centre
, v
, b
, &bx
, &by
);
5248 coords_on_line(bx
, by
, perpendicular_gradient(point_gradient(GTS_POINT(v
), GTS_POINT(arc
->centre
))), a
, &a0x
, &a0y
, &a1x
, &a1y
);
5250 winddir
= coord_wind(vx(v
), vy(v
), a0x
, a0y
, vx(arc
->centre
), vy(arc
->centre
));
5253 printf("!winddir @ v %f,%f arc->centre %f,%f\n", vx(v
), vy(v
), vx(arc
->centre
), vy(arc
->centre
));
5254 //TODO: fix hack: this shouldn't happen
5264 if(dir
) winddir
= -winddir
;
5266 if(winddir
== arc
->dir
) {
5267 if(!dir
) { arc
->x0
= a0x
; arc
->y0
= a0y
; }
5268 else{ arc
->x1
= a0x
; arc
->y1
= a0y
; }
5270 if(!dir
) { arc
->x0
= a1x
; arc
->y0
= a1y
; }
5271 else{ arc
->x1
= a1x
; arc
->y1
= a1y
; }
5278 // b1 is the projection in the direction of narc, while b2 is the perpendicular projection
5280 arc_ortho_projections(toporouter_arc_t
*arc
, toporouter_arc_t
*narc
, gdouble
*b1
, gdouble
*b2
)
5282 gdouble nax
, nay
, ax
, ay
, alen2
, c
;
5283 gdouble b1x
, b1y
, b2x
, b2y
;
5286 printf("arc c = %f,%f narc c = %f,%f arc->0 = %f,%f\n",
5287 vx(arc
->centre
), vy(arc
->centre
),
5288 vx(narc
->centre
), vy(narc
->centre
),
5292 nax
= vx(narc
->centre
) - vx(arc
->centre
);
5293 nay
= vy(narc
->centre
) - vy(arc
->centre
);
5294 alen2
= pow(nax
,2) + pow(nay
,2);
5297 ax
= arc
->x0
- vx(arc
->centre
);
5298 ay
= arc
->y0
- vy(arc
->centre
);
5301 printf("norm narc = %f,%f - %f\tA=%f,%f\n", nax
, nay
, sqrt(alen2
), ax
, ay
);
5304 c
= ((ax
*nax
)+(ay
*nay
)) / alen2
;
5312 printf("proj = %f,%f perp proj = %f,%f\n", b1x
, b1y
, b2x
, b2y
);
5315 *b1
= sqrt(pow(b1x
,2) + pow(b1y
,2));
5316 *b2
= sqrt(pow(b2x
,2) + pow(b2y
,2));
5321 calculate_arc_to_arc(toporouter_t
*ar
, toporouter_arc_t
*parc
, toporouter_arc_t
*arc
)
5323 gdouble theta
, a
, b
, bx
, by
, a0x
, a0y
, a1x
, a1y
, m
, preva
, prevb
;
5325 toporouter_arc_t
*bigr
, *smallr
;
5327 if(parc
->r
> arc
->r
) {
5328 bigr
= parc
; smallr
= arc
;
5330 bigr
= arc
; smallr
= parc
;
5333 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr
->centre
), vy(bigr
->centre
),
5334 vx(smallr
->centre
), vy(smallr
->centre
));
5337 m
= perpendicular_gradient(point_gradient(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5339 if(bigr
->centre
== smallr
->centre
) {
5341 printf("bigr->centre == smallr->centre @ %f,%f\n", vx(smallr
->centre
), vy(smallr
->centre
));
5344 g_assert(bigr
->centre
!= smallr
->centre
);
5346 if(parc
->dir
== arc
->dir
) {
5347 //export_arc_straight:
5349 theta
= acos((bigr
->r
- smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5350 a
= bigr
->r
* sin(theta
);
5351 b
= bigr
->r
* cos(theta
);
5353 point_from_point_to_point(bigr
->centre
, smallr
->centre
, b
, &bx
, &by
);
5355 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5357 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5359 arc_ortho_projections(parc
, arc
, &prevb
, &preva
);
5360 //#ifdef DEBUG_EXPORT
5363 printf("STRAIGHT:\n");
5364 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr
->centre
), vy(bigr
->centre
),
5365 vx(smallr
->centre
), vy(smallr
->centre
));
5366 printf("theta = %f a = %f b = %f bigrr = %f d = %f po = %f\n", theta
, a
, b
, bigr
->r
,
5367 gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)),
5368 bigr
->r
/ gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5369 printf("bigr-r = %f smallr-r = %f ratio = %f\n",
5370 bigr
->r
, smallr
->r
, (bigr
->r
- smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5371 printf("preva = %f prevb = %f\n\n", preva
, prevb
);
5377 if(bigr
==parc
) winddir
= -winddir
;
5379 if(winddir
== bigr
->dir
) {
5397 a
= smallr
->r
* sin(theta
);
5398 b
= smallr
->r
* cos(theta
);
5401 printf("a = %f b = %f\n", a
, b
);
5403 point_from_point_to_point(smallr
->centre
, bigr
->centre
, -b
, &bx
, &by
);
5405 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5407 if(winddir
== bigr
->dir
) {
5429 theta
= acos((bigr
->r
+ smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5430 a
= bigr
->r
* sin(theta
);
5431 b
= bigr
->r
* cos(theta
);
5433 point_from_point_to_point(bigr
->centre
, smallr
->centre
, b
, &bx
, &by
);
5435 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5437 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5438 //#ifdef DEBUG_EXPORT
5441 printf("theta = %f a = %f b = %f r = %f d = %f po = %f\n", theta
, a
, b
, bigr
->r
+ smallr
->r
,
5442 gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)),
5443 (bigr
->r
+smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5445 printf("bigr centre = %f,%f smallr centre = %f,%f\n\n", vx(bigr
->centre
), vy(bigr
->centre
),
5446 vx(smallr
->centre
), vy(smallr
->centre
));
5448 printf("big wind = %d small wind = %d\n", bigr
->dir
, smallr
->dir
);
5453 smallr->centre->flags |= VERTEX_FLAG_RED;
5454 bigr->centre->flags |= VERTEX_FLAG_GREEN;
5455 //bigr->centre->flags |= VERTEX_FLAG_RED;
5458 for(i=0;i<groupcount();i++) {
5460 sprintf(buffer, "wind%d.png", i);
5461 toporouter_draw_surface(ar, ar->layers[i].surface, buffer, 2096, 2096, 2, NULL, i, NULL);
5469 if(bigr
==parc
) winddir
= -winddir
;
5471 if(winddir
== bigr
->dir
) {
5489 a
= smallr
->r
* sin(theta
);
5490 b
= smallr
->r
* cos(theta
);
5492 point_from_point_to_point(smallr
->centre
, bigr
->centre
, b
, &bx
, &by
);
5494 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5496 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5500 if(bigr
==parc
) winddir
= -winddir
;
5502 if(winddir
== smallr
->dir
) {
5526 export_oproutes(toporouter_t
*ar
, toporouter_oproute_t
*oproute
)
5528 guint layer
= PCB
->LayerGroups
.Entries
[oproute
->layergroup
][0];
5529 guint thickness
= lookup_thickness(oproute
->style
);
5530 guint keepaway
= lookup_keepaway(oproute
->style
);
5531 GList
*arcs
= oproute
->arcs
;
5532 toporouter_arc_t
*arc
, *parc
= NULL
;
5535 ar
->wiring_score
+= export_pcb_drawline(layer
, vx(oproute
->term1
), vy(oproute
->term1
), vx(oproute
->term2
), vy(oproute
->term2
), thickness
, keepaway
);
5540 // calculate_term_to_arc(oproute->term1, TOPOROUTER_ARC(arcs->data), 0, layer);
5543 arc
= TOPOROUTER_ARC(arcs
->data
);
5546 ar
->wiring_score
+= export_pcb_drawarc(layer
, parc
, thickness
, keepaway
);
5547 ar
->wiring_score
+= export_pcb_drawline(layer
, parc
->x1
, parc
->y1
, arc
->x0
, arc
->y0
, thickness
, keepaway
);
5549 ar
->wiring_score
+= export_pcb_drawline(layer
, vx(oproute
->term1
), vy(oproute
->term1
), arc
->x0
, arc
->y0
, thickness
, keepaway
);
5555 ar
->wiring_score
+= export_pcb_drawarc(layer
, arc
, thickness
, keepaway
);
5556 ar
->wiring_score
+= export_pcb_drawline(layer
, arc
->x1
, arc
->y1
, vx(oproute
->term2
), vy(oproute
->term2
), thickness
, keepaway
);
5563 oproute_free(toporouter_oproute_t
*oproute
)
5565 GList
*i
= oproute
->arcs
;
5567 toporouter_arc_t
*arc
= (toporouter_arc_t
*) i
->data
;
5568 if(arc
->centre
->flags
& VERTEX_FLAG_TEMP
)
5569 gts_object_destroy(GTS_OBJECT(arc
->centre
));
5574 g_list_free(oproute
->arcs
);
5579 oproute_calculate_tof(toporouter_oproute_t
*oproute
)
5581 GList
*arcs
= oproute
->arcs
;
5582 toporouter_arc_t
*parc
= NULL
, *arc
;
5587 oproute
->tof
= gts_point_distance(GTS_POINT(oproute
->term1
), GTS_POINT(oproute
->term2
));
5592 arc
= TOPOROUTER_ARC(arcs
->data
);
5595 oproute
->tof
+= arc_angle(parc
) * parc
->r
;
5596 oproute
->tof
+= sqrt(pow(parc
->x1
-arc
->x0
,2)+pow(parc
->y1
-arc
->y0
,2));
5598 oproute
->tof
+= sqrt(pow(arc
->x0
-vx(oproute
->term1
),2)+pow(arc
->y0
-vy(oproute
->term1
),2));
5605 oproute
->tof
+= arc_angle(parc
) * parc
->r
;
5606 oproute
->tof
+= sqrt(pow(arc
->x1
-vx(oproute
->term2
),2)+pow(arc
->y1
-vy(oproute
->term2
),2));
5611 line_line_distance_at_normal(
5612 gdouble line1_x1
, gdouble line1_y1
,
5613 gdouble line1_x2
, gdouble line1_y2
,
5614 gdouble line2_x1
, gdouble line2_y1
,
5615 gdouble line2_x2
, gdouble line2_y2
,
5616 gdouble x
, gdouble y
)
5618 gdouble m1
= perpendicular_gradient(cartesian_gradient(line1_x1
, line1_y1
, line1_x2
, line1_y2
));
5619 gdouble m2
= cartesian_gradient(line2_x1
, line2_y1
, line2_x2
, line2_y2
);
5620 gdouble c1
= (isinf(m1
)) ? x
: y
- (m1
* x
);
5621 gdouble c2
= (isinf(m2
)) ? line2_x1
: line2_y1
- (m2
* line2_x1
);
5625 if(isinf(m2
)) intx
= line2_x1
;
5626 else if(isinf(m1
)) intx
= x
;
5627 else intx
= (c2
- c1
) / (m1
- m2
);
5629 inty
= (isinf(m2
)) ? (m1
* intx
) + c1
: (m2
* intx
) + c2
;
5631 return sqrt(pow(x
-intx
,2)+pow(y
-inty
,2));
5635 calculate_serpintine(gdouble delta
, gdouble r
, gdouble initiala
, gdouble
*a
, guint
*nhalfcycles
)
5637 gdouble lhalfcycle
= 2.*(initiala
-r
)+(M_PI
*r
);
5640 printf("lhalfcycle = %f r = %f\n", lhalfcycle
, r
);
5642 n
= (delta
- M_PI
*r
) / (lhalfcycle
- 2.*r
) + 1;
5643 *a
= (delta
+ 4.*n
*r
- n
*M_PI
*r
+ 4.*r
- M_PI
*r
)/(2.*n
);
5648 oproute_min_spacing(toporouter_oproute_t
*a
, toporouter_oproute_t
*b
)
5650 return lookup_thickness(a
->style
) / 2. + lookup_thickness(b
->style
) / 2. + MAX(lookup_keepaway(a
->style
), lookup_keepaway(b
->style
));
5654 vector_angle(gdouble ox
, gdouble oy
, gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
)
5656 gdouble alen
= sqrt(pow(ax
-ox
,2)+pow(ay
-oy
,2));
5657 gdouble blen
= sqrt(pow(bx
-ox
,2)+pow(by
-oy
,2));
5658 return acos( ((ax
-ox
)*(bx
-ox
)+(ay
-oy
)*(by
-oy
)) / (alen
* blen
) );
5661 toporouter_serpintine_t
*
5662 toporouter_serpintine_new(gdouble x
, gdouble y
, gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, gpointer start
, gdouble halfa
, gdouble
5663 radius
, guint nhalfcycles
)
5665 toporouter_serpintine_t
*serp
= (toporouter_serpintine_t
*)malloc(sizeof(toporouter_serpintine_t
));
5672 serp
->start
= start
;
5673 serp
->halfa
= halfa
;
5674 serp
->radius
= radius
;
5675 serp
->nhalfcycles
= nhalfcycles
;
5680 //#define DEBUG_RUBBERBAND 1
5683 check_non_intersect_vertex(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
,
5684 toporouter_vertex_t
*opv
, gint wind
, gint
*arcwind
, gdouble
*arcr
, guint debug
)
5686 gdouble ms
, line_int_x
, line_int_y
, x
, y
, d
= 0., m
;
5687 gdouble tx0
, ty0
, tx1
, ty1
;
5690 g_assert(pathv
->routingedge
);
5692 if(TOPOROUTER_IS_CONSTRAINT(pathv
->routingedge
)) {
5693 gdouble d
= tvdistance(tedge_v1(pathv
->routingedge
), tedge_v2(pathv
->routingedge
)) / 2.;
5694 ms
= min_spacing(pathv
, arcv
);
5697 ms
= edge_min_spacing(g_list_find(edge_routing(pathv
->routingedge
), pathv
), pathv
->routingedge
, arcv
, debug
);
5701 if(!vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(arcv
), vy(arcv
), &line_int_x
, &line_int_y
)) {
5703 if(coord_distance2(x0
, y0
, line_int_x
, line_int_y
) < coord_distance2(x1
, y1
, line_int_x
, line_int_y
))
5704 { line_int_x
= x0
; line_int_y
= y0
; }else{ line_int_x
= x1
; line_int_y
= y1
; }
5706 m
= perpendicular_gradient(cartesian_gradient(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
));
5708 m
= cartesian_gradient(x0
, y0
, x1
, y1
);
5711 coords_on_line(vx(arcv
), vy(arcv
), m
, MIL_TO_COORD (1.), &tx0
, &ty0
, &tx1
, &ty1
);
5713 wind1
= coord_wind(tx0
, ty0
, tx1
, ty1
, line_int_x
, line_int_y
);
5714 wind2
= coord_wind(tx0
, ty0
, tx1
, ty1
, vx(opv
), vy(opv
));
5716 if(!wind2
|| wind1
== wind2
) return -1.;
5719 coords_on_line(line_int_x
, line_int_y
, perpendicular_gradient(m
), ms
, &tx0
, &ty0
, &tx1
, &ty1
);
5720 if(coord_distance2(tx0
, ty0
, vx(opv
), vy(opv
)) < coord_distance2(tx1
, ty1
, vx(opv
), vy(opv
)))
5721 { x
= tx0
; y
= ty0
; }else{ x
= tx1
; y
= ty1
; }
5723 toporouter_vertex_t
*parent
= pathv
->parent
, *child
= pathv
->child
;
5724 guint windtests
= 0;
5726 d
= coord_distance(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
);
5727 coord_move_towards_coord_values(line_int_x
, line_int_y
, vx(arcv
), vy(arcv
), ms
+ d
, &x
, &y
);
5729 wind1
= coord_wind(line_int_x
, line_int_y
, x
, y
, vx(parent
), vy(parent
));
5730 wind2
= coord_wind(line_int_x
, line_int_y
, x
, y
, vx(child
), vy(child
));
5731 if(wind1
&& wind2
&& wind1
== wind2
) {
5733 if(windtests
++ == 2) return -1.;
5735 if(parent
->flags
& VERTEX_FLAG_ROUTE
) parent
= parent
->parent
;
5736 if(child
->flags
& VERTEX_FLAG_ROUTE
) child
= child
->child
;
5743 *arcwind
= tvertex_wind(pathv
->parent
, pathv
, arcv
);
5745 #ifdef DEBUG_RUBBERBAND
5747 // printf("non-int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, d + ms,
5748 // vx(arcv), vy(arcv), vx(opv), vy(opv));
5755 check_intersect_vertex(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
,
5756 toporouter_vertex_t
*opv
, gint wind
, gint
*arcwind
, gdouble
*arcr
, guint debug
)
5758 gdouble ms
, line_int_x
, line_int_y
, x
, y
, d
= 0.;
5760 if(TOPOROUTER_IS_CONSTRAINT(pathv
->routingedge
)) {
5761 gdouble d
= tvdistance(tedge_v1(pathv
->routingedge
), tedge_v2(pathv
->routingedge
)) / 2.;
5762 ms
= min_spacing(pathv
, arcv
);
5765 ms
= edge_min_spacing(g_list_find(edge_routing(pathv
->routingedge
), pathv
), pathv
->routingedge
, arcv
, debug
);
5768 if(!vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(arcv
), vy(arcv
), &line_int_x
, &line_int_y
))
5771 d
= coord_distance(line_int_x
, line_int_y
, vx(arcv
), vy(arcv
));
5774 if(d
> ms
- EPSILON
)
5777 coord_move_towards_coord_values(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
, ms
, &x
, &y
);
5780 *arcwind
= tvertex_wind(pathv
->parent
, pathv
, arcv
);
5781 // *arcwind = coord_wind(x0, y0, x, y, x1, y1);
5782 #ifdef DEBUG_RUBBERBAND
5784 // printf("int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, ms - d,
5785 // vx(arcv), vy(arcv), vx(opv), vy(opv));
5791 /* returns non-zero if arc has loops */
5793 check_arc_for_loops(gpointer t1
, toporouter_arc_t
*arc
, gpointer t2
)
5795 gdouble x0
, y0
, x1
, y1
;
5797 if(TOPOROUTER_IS_VERTEX(t1
)) { x0
= vx(TOPOROUTER_VERTEX(t1
)); y0
= vy(TOPOROUTER_VERTEX(t1
)); }
5798 else { x0
= TOPOROUTER_ARC(t1
)->x1
; y0
= TOPOROUTER_ARC(t1
)->y1
; }
5800 if(TOPOROUTER_IS_VERTEX(t2
)) { x1
= vx(TOPOROUTER_VERTEX(t2
)); y1
= vy(TOPOROUTER_VERTEX(t2
)); }
5801 else { x1
= TOPOROUTER_ARC(t2
)->x0
; y1
= TOPOROUTER_ARC(t2
)->y0
; }
5803 if(coord_intersect_prop(x0
, y0
, arc
->x0
, arc
->y0
, arc
->x1
, arc
->y1
, x1
, y1
) ) {
5805 // (arc->x0 > arc->x1 - EPSILON && arc->x0 < arc->x1 + EPSILON &&
5806 // arc->y0 > arc->y1 - EPSILON && arc->y0 < arc->y1 + EPSILON)
5808 #ifdef DEBUG_RUBBERBAND
5809 printf("LOOPS %f %f -> %f %f & %f %f -> %f %f\n", x0
, y0
, arc
->x0
, arc
->y0
, arc
->x1
, arc
->y1
, x1
, y1
);
5816 toporouter_rubberband_arc_t
*
5817 new_rubberband_arc(toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
, gdouble r
, gdouble d
, gint wind
, GList
*list
)
5819 toporouter_rubberband_arc_t
*rba
= (toporouter_rubberband_arc_t
*)malloc(sizeof(toporouter_rubberband_arc_t
));
5830 compare_rubberband_arcs(toporouter_rubberband_arc_t
*a
, toporouter_rubberband_arc_t
*b
)
5831 { return b
->d
- a
->d
; }
5834 free_list_elements(gpointer data
, gpointer user_data
)
5838 /* returns the edge opposite v from the triangle facing (x,y), or NULL if v is colinear with an edge between v and a neighbor */
5841 vertex_edge_facing_vertex(GtsVertex *v, gdouble x, gdouble y)
5843 GSList *ts = gts_vertex_triangles(GTS_VERTEX(n), NULL);
5847 GtsTriangle *t = GTS_TRIANGLE(i->data);
5848 GtsEdge *e = gts_triangle_edge_opposite(t, v);
5850 if(coord_wind(vx(edge_v1(e)), vy(edge_v1(e)), vx(v), vy(v), x, y) == vertex_wind(edge_v1(e), v, edge_v2(e)) &&
5851 coord_wind(vx(edge_v2(e)), vy(edge_v2(e)), vx(v), vy(v), x, y) == vertex_wind(edge_v2(e), v, edge_v1(e))
5866 check_adj_pushing_vertex(toporouter_oproute_t
*oproute
, gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*v
, gdouble
*arcr
, gint
*arcwind
, toporouter_vertex_t
**arc
)
5868 GSList
*ns
= gts_vertex_neighbors(GTS_VERTEX(v
), NULL
, NULL
);
5873 toporouter_vertex_t
*n
= TOPOROUTER_VERTEX(i
->data
);
5874 gdouble segintx
, seginty
;
5875 if(vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(n
), vy(n
), &segintx
, &seginty
)) {
5876 toporouter_edge_t
*e
= tedge(n
, v
);
5877 gdouble ms
= 0., d
= coord_distance(segintx
, seginty
, vx(n
), vy(n
));
5878 //toporouter_vertex_t *a;
5879 toporouter_vertex_t
*b
;
5880 GList
*closestnet
= NULL
;
5884 if(v
== tedge_v1(e
)) {
5887 closestnet
= edge_routing(e
);
5891 closestnet
= g_list_last(edge_routing(e
));
5895 ms
= edge_min_spacing(closestnet
, e
, b
, 0);
5896 ms
+= min_oproute_net_spacing(oproute
, TOPOROUTER_VERTEX(closestnet
->data
));
5898 ms
= min_oproute_vertex_spacing(oproute
, b
);
5905 if(vx(v
) == x0
&& vy(v
) == y0
) {
5906 *arcwind
= coord_wind(x0
, y0
, vx(n
), vy(n
), x1
, y1
);
5907 }else if(vx(v
) == x1
&& vy(v
) == y1
) {
5908 *arcwind
= coord_wind(x1
, y1
, vx(n
), vy(n
), x0
, y0
);
5910 fprintf(stderr
, "ERROR: check_adj_pushing_vertex encountered bad vertex v (coordinates don't match)\n");
5925 oproute_rubberband_segment(toporouter_t
*r
, toporouter_oproute_t
*oproute
, GList
*path
, gpointer t1
, gpointer t2
, guint debug
)
5927 gdouble x0
, y0
, x1
, y1
;
5928 toporouter_vertex_t
*v1
, *v2
, *av1
, *av2
; /* v{1,2} are the vertex terminals of the segment, or arc terminal centres */
5929 toporouter_arc_t
*arc1
= NULL
, *arc2
= NULL
, *newarc
= NULL
; /* arc{1,2} are the arc terminals of the segment, if they exist */
5931 GList
*list1
, *list2
;
5934 toporouter_rubberband_arc_t
*max
= NULL
;
5937 gint v1wind
, v2wind
, arcwind
;
5939 if(TOPOROUTER_IS_VERTEX(t1
)) {
5940 v1
= TOPOROUTER_VERTEX(t1
);
5941 x0
= vx(v1
); y0
= vy(v1
);
5943 g_assert(TOPOROUTER_IS_ARC(t1
));
5944 arc1
= TOPOROUTER_ARC(t1
);
5945 v1
= TOPOROUTER_VERTEX(arc1
->v1
);
5950 if(TOPOROUTER_IS_VERTEX(t2
)) {
5951 v2
= TOPOROUTER_VERTEX(t2
);
5952 x1
= vx(v2
); y1
= vy(v2
);
5954 g_assert(TOPOROUTER_IS_ARC(t2
));
5955 arc2
= TOPOROUTER_ARC(t2
);
5956 v2
= TOPOROUTER_VERTEX(arc2
->v2
);
5961 #define TEST_AND_INSERT(z) if(d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v, z, arcr, d, arcwind, i));
5962 #define ARC_CHECKS(z) (!(arc1 && arc1->centre == z) && !(arc2 && arc2->centre == z) && \
5963 !(TOPOROUTER_IS_VERTEX(t1) && z == v1) && !(TOPOROUTER_IS_VERTEX(t2) && z == v2))
5965 if(v1
== v2
|| !i
->next
|| TOPOROUTER_VERTEX(i
->data
) == v2
) return NULL
;
5967 //#ifdef DEBUG_RUBBERBAND
5969 printf("\nRB: line %f,%f %f,%f v1 = %f,%f v2 = %f,%f \n ", x0
, y0
, x1
, y1
, vx(v1
), vy(v1
), vx(v2
), vy(v2
));
5970 // if(v1->routingedge) print_edge(v1->routingedge);
5971 // if(v2->routingedge) print_edge(v2->routingedge);
5976 /* check the vectices adjacent to the terminal vectices for push against the segment */
5977 //if(TOPOROUTER_IS_VERTEX(t1)) {
5978 // toporouter_vertex_t *arcc = NULL;
5979 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v1, &arcr, &arcwind, &arcc);
5980 // g_assert(arcc != v1);
5981 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v1, arcc, arcr, d, arcwind, path->next));
5984 //if(TOPOROUTER_IS_VERTEX(t2)) {
5985 // toporouter_vertex_t *arcc = NULL;
5986 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v2, &arcr, &arcwind, &arcc);
5987 // g_assert(arcc != v2);
5988 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v2, arcc, arcr, d, arcwind, g_list_last(path)->prev));
5993 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
5995 if(v
== v2
|| v
== v1
|| !v
->routingedge
) break;
5997 #ifdef DEBUG_RUBBERBAND
5999 // printf("current v %f,%f - edge %f,%f %f,%f\n", vx(v), vy(v),
6000 // vx(tedge_v1(v->routingedge)), vy(tedge_v1(v->routingedge)),
6001 // vx(tedge_v2(v->routingedge)), vy(tedge_v2(v->routingedge))
6004 g_assert(v
->routingedge
);
6006 v1wind
= coord_wind(x0
, y0
, x1
, y1
, vx(tedge_v1(v
->routingedge
)), vy(tedge_v1(v
->routingedge
)));
6007 v2wind
= coord_wind(x0
, y0
, x1
, y1
, vx(tedge_v2(v
->routingedge
)), vy(tedge_v2(v
->routingedge
)));
6008 // if(debug) printf("\twinds: %d %d\n", v1wind, v2wind);
6009 if(!v1wind
&& !v2wind
) { i
= i
->next
; continue; }
6012 if(v1wind
&& v2wind
&& v1wind
!= v2wind
) { /* edge is cutting through the current segment */
6014 if(ARC_CHECKS(tedge_v1(v
->routingedge
)) ){ /* edge v1 is not the centre of an arc terminal */
6015 d
= check_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v1(v
->routingedge
), tedge_v2(v
->routingedge
), v1wind
, &arcwind
, &arcr
, debug
);
6016 TEST_AND_INSERT(tedge_v1(v
->routingedge
));
6019 if(ARC_CHECKS(tedge_v2(v
->routingedge
)) ){ /* edge v2 is not the centre of an arc terminal */
6020 d
= check_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v2(v
->routingedge
), tedge_v1(v
->routingedge
), v2wind
, &arcwind
, &arcr
, debug
);
6021 TEST_AND_INSERT(tedge_v2(v
->routingedge
));
6023 }else{ /* edge is on one side of the segment */
6025 if(ARC_CHECKS(tedge_v1(v
->routingedge
)) ){ /* edge v1 is not the centre of an arc terminal */
6026 d
= check_non_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v1(v
->routingedge
), tedge_v2(v
->routingedge
), v1wind
, &arcwind
, &arcr
, debug
);
6027 TEST_AND_INSERT(tedge_v1(v
->routingedge
));
6030 if(ARC_CHECKS(tedge_v2(v
->routingedge
)) ){ /* edge v2 is not the centre of an arc terminal */
6031 d
= check_non_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v2(v
->routingedge
), tedge_v1(v
->routingedge
), v2wind
, &arcwind
, &arcr
, debug
);
6032 TEST_AND_INSERT(tedge_v2(v
->routingedge
));
6039 arcs
= g_list_sort(arcs
, (GCompareFunc
) compare_rubberband_arcs
);
6040 //rubberband_insert_maxarc:
6041 if(!arcs
) return NULL
;
6042 max
= TOPOROUTER_RUBBERBAND_ARC(arcs
->data
);
6044 av2
= max
->pathv
; i
= max
->list
->next
;
6046 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6047 if(v
->routingedge
&& (tedge_v1(v
->routingedge
) == max
->arcv
|| tedge_v2(v
->routingedge
) == max
->arcv
)) {
6048 av2
= v
; i
= i
->next
; continue;
6053 av1
= max
->pathv
; i
= max
->list
->prev
;
6055 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6056 if(v
->routingedge
&& (tedge_v1(v
->routingedge
) == max
->arcv
|| tedge_v2(v
->routingedge
) == max
->arcv
)) {
6057 av1
= v
; i
= i
->prev
; continue;
6061 //#ifdef DEBUG_RUBBERBAND
6063 printf("newarc @ %f,%f \t v1 = %f,%f v2 = %f,%f r = %f\n", vx(max
->arcv
), vy(max
->arcv
), vx(av1
), vy(av1
), vx(av2
), vy(av2
), max
->r
);
6065 newarc
= toporouter_arc_new(oproute
, av1
, av2
, max
->arcv
, max
->r
, max
->wind
);
6067 if(TOPOROUTER_IS_VERTEX(t1
))
6068 calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), newarc
, 0);
6069 else if(calculate_arc_to_arc(r
, TOPOROUTER_ARC(t1
), newarc
)) {
6070 printf("\tERROR: best: r = %f d = %f\n", max
->r
, max
->d
);
6071 printf("\tOPROUTE: %s\n", oproute
->netlist
);
6072 print_vertex(oproute
->term1
);
6073 print_vertex(oproute
->term2
);
6077 if(TOPOROUTER_IS_VERTEX(t2
))
6078 calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), newarc
, 1);
6079 else if(calculate_arc_to_arc(r
, newarc
, TOPOROUTER_ARC(t2
))) {
6080 printf("\tERROR: best: r = %f d = %f\n", max
->r
, max
->d
);
6081 printf("\tOPROUTE: %s\n", oproute
->netlist
);
6082 print_vertex(oproute
->term1
);
6083 print_vertex(oproute
->term2
);
6087 //if(check_arc_for_loops(t1, newarc, t2)) {
6088 // if(arc1 && arc2) calculate_arc_to_arc(r, arc1, arc2);
6089 // else if(arc1) calculate_term_to_arc(TOPOROUTER_VERTEX(t2), arc1, 1);
6090 // else if(arc2) calculate_term_to_arc(TOPOROUTER_VERTEX(t1), arc2, 0);
6092 //#ifdef DEBUG_RUBBERBAND
6093 // printf("REMOVING NEW ARC @ %f,%f\n", vx(newarc->centre), vy(newarc->centre));
6094 // //TODO: properly remove newarc
6097 // arcs = g_list_remove(arcs, max);
6099 // goto rubberband_insert_maxarc;
6103 list1
= oproute_rubberband_segment(r
, oproute
, path
, t1
, newarc
, debug
);
6104 list2
= oproute_rubberband_segment(r
, oproute
, i
->next
, newarc
, t2
, debug
);
6107 GList
*list
= g_list_last(list1
);
6108 toporouter_arc_t
*testarc
= TOPOROUTER_ARC(list
->data
);
6109 toporouter_arc_t
*parc
= list
->prev
? TOPOROUTER_ARC(list
->prev
->data
) : arc1
;
6110 gdouble px
= parc
? parc
->x1
: vx(TOPOROUTER_VERTEX(t1
)), py
= parc
? parc
->y1
: vy(TOPOROUTER_VERTEX(t1
));
6112 if(coord_intersect_prop(px
, py
, testarc
->x0
, testarc
->y0
, testarc
->x1
, testarc
->y1
, newarc
->x0
, newarc
->y0
)) {
6113 list1
= g_list_remove(list1
, testarc
);
6114 if(parc
) calculate_arc_to_arc(r
, parc
, newarc
);
6115 else calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), newarc
, 0);
6116 //#ifdef DEBUG_RUBBERBAND
6118 printf("REMOVING ARC @ %f,%f\n", vx(testarc
->centre
), vy(testarc
->centre
));
6123 toporouter_arc_t
*testarc
= TOPOROUTER_ARC(list2
->data
);
6124 toporouter_arc_t
*narc
= list2
->next
? TOPOROUTER_ARC(list2
->next
->data
) : arc2
;
6125 gdouble nx
= narc
? narc
->x0
: vx(TOPOROUTER_VERTEX(t2
)), ny
= narc
? narc
->y0
: vy(TOPOROUTER_VERTEX(t2
));
6127 if(coord_intersect_prop(newarc
->x1
, newarc
->y1
, testarc
->x0
, testarc
->y0
, testarc
->x1
, testarc
->y1
, nx
, ny
)) {
6128 list2
= g_list_remove(list2
, testarc
);
6129 if(narc
) calculate_arc_to_arc(r
, newarc
, narc
);
6130 else calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), newarc
, 1);
6132 //#ifdef DEBUG_RUBBERBAND
6134 printf("REMOVING ARC @ %f,%f\n", vx(testarc
->centre
), vy(testarc
->centre
));
6139 g_list_foreach(arcs
, free_list_elements
, NULL
);
6142 return g_list_concat(list1
, g_list_prepend(list2
, newarc
));
6146 oproute_check_all_loops(toporouter_t
*r
, toporouter_oproute_t
*oproute
)
6152 t1
= oproute
->term1
;
6155 toporouter_arc_t
*arc
= TOPOROUTER_ARC(i
->data
);
6156 gpointer t2
= i
->next
? i
->next
->data
: oproute
->term2
;
6158 if(check_arc_for_loops(t1
, arc
, t2
)) {
6160 if(TOPOROUTER_IS_ARC(t1
) && TOPOROUTER_IS_ARC(t2
))
6161 calculate_arc_to_arc(r
, TOPOROUTER_ARC(t1
), TOPOROUTER_ARC(t2
));
6162 else if(TOPOROUTER_IS_ARC(t1
))
6163 calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), TOPOROUTER_ARC(t1
), 1);
6164 else if(TOPOROUTER_IS_ARC(t2
))
6165 calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), TOPOROUTER_ARC(t2
), 0);
6167 oproute
->arcs
= g_list_remove(oproute
->arcs
, arc
);
6168 goto loopcheck_restart
;
6179 opposite_triangle(GtsTriangle
*t
, toporouter_edge_t
*e
)
6181 GSList
*i
= GTS_EDGE(e
)->triangles
;
6186 if(GTS_TRIANGLE(i
->data
) != t
) return GTS_TRIANGLE(i
->data
);
6195 speccut_edge_routing_from_edge(GList
*i
, toporouter_edge_t
*e
)
6197 g_assert(TOPOROUTER_IS_EDGE(e
));
6199 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
6201 if(!(curv
->flags
& VERTEX_FLAG_TEMP
)) {
6202 toporouter_vertex_t
*newv
= tvertex_intersect(curv
, curv
->parent
, tedge_v1(e
), tedge_v2(e
));
6204 // printf("\nCURV:\n");
6205 // print_vertex(curv);
6207 // printf("CURV child:\n");
6209 // print_vertex(curv->child);
6211 // printf("NULL\n");
6213 // printf("CURV parent:\n");
6215 // print_vertex(curv->parent);
6217 // printf("NULL\n");
6221 newv
->flags
|= VERTEX_FLAG_ROUTE
;
6222 newv
->flags
|= VERTEX_FLAG_SPECCUT
;
6223 e
->routing
= g_list_insert_sorted_with_data(e
->routing
, newv
, routing_edge_insert
, e
);
6224 newv
->route
= curv
->route
;
6225 newv
->oproute
= curv
->oproute
;
6226 newv
->routingedge
= e
;
6227 GTS_POINT(newv
)->z
= vz(curv
);
6229 newv
->parent
= curv
->parent
;
6232 // curv->parent = newv;
6234 index
= g_list_index(newv
->route
->path
, curv
);
6236 newv
->route
->path
= g_list_insert(newv
->route
->path
, newv
, index
);
6239 if(newv
->oproute
) newv
->oproute
->path
= newv
->route
->path
;
6242 if(!(curv
->child
->routingedge
)) {
6243 newv
= tvertex_intersect(curv
, curv
->child
, tedge_v1(e
), tedge_v2(e
));
6247 newv
->flags
|= VERTEX_FLAG_ROUTE
;
6248 newv
->flags
|= VERTEX_FLAG_SPECCUT
;
6249 e
->routing
= g_list_insert_sorted_with_data(e
->routing
, newv
, routing_edge_insert
, e
);
6250 newv
->route
= curv
->route
;
6251 newv
->oproute
= curv
->oproute
;
6252 newv
->routingedge
= e
;
6253 GTS_POINT(newv
)->z
= vz(curv
);
6255 newv
->parent
= curv
;
6256 newv
->child
= curv
->child
;
6258 // curv->child = newv;
6260 index
= g_list_index(newv
->route
->path
, curv
);
6262 newv
->route
->path
= g_list_insert(newv
->route
->path
, newv
, index
+1);
6265 if(newv
->oproute
) newv
->oproute
->path
= newv
->route
->path
;
6277 speccut_edge_patch_links(toporouter_edge_t
*e
)
6279 GList
*i
= e
->routing
;
6280 g_assert(TOPOROUTER_IS_EDGE(e
));
6282 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6283 v
->parent
->child
= v
;
6284 v
->child
->parent
= v
;
6290 check_speccut(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_edge_t
*e
, toporouter_edge_t
*e1
, toporouter_edge_t
*e2
)
6292 GtsTriangle
*t
, *opt
;
6293 toporouter_vertex_t
*opv
, *opv2
;
6294 toporouter_edge_t
*ope1
, *ope2
;
6295 gdouble cap
, flow
, line_int_x
, line_int_y
;
6297 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
6299 if(!(t
= gts_triangle_use_edges(GTS_EDGE(e
), GTS_EDGE(e1
), GTS_EDGE(e2
)))) {
6300 printf("check_speccut: NULL t\n");
6304 if(!(opt
= opposite_triangle(t
, e
))) {
6305 // printf("check_speccut: NULL opt\n");
6309 if(!(opv
= segment_common_vertex(GTS_SEGMENT(e1
), GTS_SEGMENT(e2
)))) {
6310 printf("check_speccut: NULL opv\n");
6314 if(!(opv2
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(opt
, GTS_EDGE(e
))))) {
6315 printf("check_speccut: NULL opv2\n");
6319 //TODO: shifting it out of the way would be better
6321 GList
*i
= e
->routing
;
6323 toporouter_vertex_t
*ev
= TOPOROUTER_VERTEX(i
->data
);
6324 if(!tvertex_wind(opv
, ev
, opv2
)) return 0;
6330 ope1
= tedge(opv2
, tedge_v1(e
));
6331 ope2
= tedge(opv2
, tedge_v2(e
));
6333 //this fixes the weird pad exits in r8c board
6334 // if(TOPOROUTER_IS_CONSTRAINT(ope1)) return 0;
6335 if(TOPOROUTER_IS_CONSTRAINT(ope2
)) return 0;
6337 if(!tvertex_wind(opv2
, tedge_v1(e
), opv
)) return 0;
6338 if(!tvertex_wind(opv2
, tedge_v2(e
), opv
)) return 0;
6340 if(!vertex_line_normal_intersection(
6341 vx(tedge_v1(e
)), vy(tedge_v1(e
)),
6342 vx(tedge_v2(e
)), vy(tedge_v2(e
)),
6344 &line_int_x
, &line_int_y
)) return 0;
6348 //if(vertex_line_normal_intersection(tev1x(e), tev1y(e), tev2x(e), tev2y(e), vx(opv), vy(opv), &line_int_x, &line_int_y))
6351 g_assert(opt
&& opv2
);
6353 /* this is just temp, for the purposes of determining flow */
6354 if(tedge_v1(ope1
) == opv2
) {
6355 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6356 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_append(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6358 ope1
->routing
= g_list_append(ope1
->routing
, v1
);
6360 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6361 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_prepend(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6363 ope1
->routing
= g_list_prepend(ope1
->routing
, v1
);
6366 cap
= triangle_interior_capacity(opt
, opv2
);
6367 flow
= flow_from_edge_to_edge(opt
, tedge(opv2
, tedge_v1(e
)), tedge(opv2
, tedge_v2(e
)), opv2
, v1
);
6369 /* temp v1 removed */
6370 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6371 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6373 ope1
->routing
= g_list_remove(ope1
->routing
, v1
);
6376 toporouter_edge_t
*newe
= TOPOROUTER_EDGE(gts_edge_new(GTS_EDGE_CLASS(toporouter_edge_class()), GTS_VERTEX(opv
), GTS_VERTEX(opv2
)));
6378 speccut_edge_routing_from_edge(edge_routing(e1
), newe
);
6379 speccut_edge_routing_from_edge(edge_routing(e2
), newe
);
6380 speccut_edge_routing_from_edge(edge_routing(ope1
), newe
);
6381 speccut_edge_routing_from_edge(edge_routing(ope2
), newe
);
6383 speccut_edge_patch_links(newe
);
6385 printf("SPECCUT WITH v %f,%f for seg %f,%f %f,%f detected\n", vx(opv2), vy(opv2),
6388 printf("\tflow %f cap %f\n", flow, cap);
6391 if(newe
->routing
) return 1;
6400 oproute_path_speccut(toporouter_oproute_t
*oproute
)
6403 toporouter_vertex_t
*pv
;
6404 path_speccut_restart
:
6408 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6411 if(pv
&& (v
->routingedge
|| pv
->routingedge
) && !(pv
->flags
& VERTEX_FLAG_SPECCUT
) && !(v
->flags
& VERTEX_FLAG_SPECCUT
)) {
6413 if(!v
->routingedge
) {
6414 if(check_speccut(oproute
, pv
, v
, tedge(tedge_v1(pv
->routingedge
), v
), pv
->routingedge
, tedge(tedge_v2(pv
->routingedge
), v
)))
6415 goto path_speccut_restart
;
6416 if(check_speccut(oproute
, pv
, v
, tedge(tedge_v2(pv
->routingedge
), v
), pv
->routingedge
, tedge(tedge_v1(pv
->routingedge
), v
)))
6417 goto path_speccut_restart
;
6418 }else if(!pv
->routingedge
) {
6419 if(check_speccut(oproute
, v
, pv
, tedge(tedge_v1(v
->routingedge
), pv
), v
->routingedge
, tedge(tedge_v2(v
->routingedge
), pv
)))
6420 goto path_speccut_restart
;
6421 if(check_speccut(oproute
, v
, pv
, tedge(tedge_v2(v
->routingedge
), pv
), v
->routingedge
, tedge(tedge_v1(v
->routingedge
), pv
)))
6422 goto path_speccut_restart
;
6424 toporouter_vertex_t
*v1
= NULL
, *v2
= NULL
;
6425 edges_third_edge(GTS_SEGMENT(v
->routingedge
), GTS_SEGMENT(pv
->routingedge
), &v1
, &v2
);
6426 if(check_speccut(oproute
, v
, pv
, tedge(v1
, v2
), v
->routingedge
, pv
->routingedge
))
6427 goto path_speccut_restart
;
6439 toporouter_oproute_t
*
6440 oproute_rubberband(toporouter_t
*r
, GList
*path
)
6442 toporouter_oproute_t
*oproute
= (toporouter_oproute_t
*)malloc(sizeof(toporouter_oproute_t
));
6446 oproute
->term1
= TOPOROUTER_VERTEX(path
->data
);
6447 oproute
->term2
= TOPOROUTER_VERTEX(g_list_last(path
)->data
);
6448 oproute
->arcs
= NULL
;
6449 oproute
->style
= vertex_bbox(oproute
->term1
)->cluster
->netlist
->style
;
6450 oproute
->netlist
= vertex_bbox(oproute
->term1
)->cluster
->netlist
->netlist
;
6451 oproute
->layergroup
= vz(oproute
->term1
);
6452 oproute
->path
= path
;
6453 oproute
->serp
= NULL
;
6455 oproute
->term1
->parent
= NULL
;
6456 oproute
->term2
->child
= NULL
;
6458 path_set_oproute(path
, oproute
);
6460 // if(!strcmp(oproute->netlist, " unnamed_net1"))
6461 oproute_path_speccut(oproute
);
6463 #ifdef DEBUG_RUBBERBAND
6464 if(strcmp(oproute
->netlist
, " VCC3V3" == 0) &&
6465 vx(oproute
->term1
) == MIL_TO_COORD (957.) &&
6466 vy(oproute
->term1
) == MIL_TO_COORD (708.) &&
6467 vx(oproute
->term2
) == MIL_TO_COORD (1967.) &&
6468 vy(oproute
->term2
) == MIL_TO_COORD (673.))
6470 // printf("OPROUTE %s - %f,%f %f,%f\n", oproute->netlist, vx(oproute->term1), vy(oproute->term1), vx(oproute->term2), vy(oproute->term2));
6471 // print_path(path);
6472 oproute
->arcs
= oproute_rubberband_segment(r
, oproute
, path
, oproute
->term1
, oproute
->term2
, 1);
6475 oproute
->arcs
= oproute_rubberband_segment(r
, oproute
, path
, oproute
->term1
, oproute
->term2
, 0);
6477 oproute_check_all_loops(r
, oproute
);
6483 toporouter_export(toporouter_t
*r
)
6485 GList
*i
= r
->routednets
;
6486 GList
*oproutes
= NULL
;
6489 toporouter_route_t
*routedata
= TOPOROUTER_ROUTE(i
->data
);
6490 toporouter_oproute_t
*oproute
= oproute_rubberband(r
, routedata
->path
);
6491 oproutes
= g_list_prepend(oproutes
, oproute
);
6497 toporouter_oproute_t
*oproute
= (toporouter_oproute_t
*) i
->data
;
6498 export_oproutes(r
, oproute
);
6499 oproute_free(oproute
);
6503 Message (_("Reticulating splines... successful\n\n"));
6504 /* NB: We could use the %$mS specifier to print these distances, but we would
6505 * have to cast to Coord, which might overflow for complex routing when
6506 * PCB is built with Coord as a 32-bit integer.
6508 Message (_("Wiring cost: %f inches\n"), COORD_TO_INCH (r
->wiring_score
));
6509 printf ("Wiring cost: %f inches\n", COORD_TO_INCH (r
->wiring_score
));
6511 g_list_free(oproutes
);
6515 toporouter_route_t
*
6516 routedata_create(void)
6518 toporouter_route_t
*routedata
= (toporouter_route_t
*)malloc(sizeof(toporouter_route_t
));
6519 routedata
->netlist
= NULL
;
6520 routedata
->alltemppoints
= NULL
;
6521 routedata
->path
= NULL
;
6522 routedata
->curpoint
= NULL
;
6523 routedata
->pscore
= routedata
->score
= 0.;
6524 routedata
->flags
= 0;
6525 routedata
->src
= routedata
->dest
= NULL
;
6526 routedata
->psrc
= routedata
->pdest
= NULL
;
6527 routedata
->ppath
= routedata
->topopath
= NULL
;
6529 routedata
->ppathindices
= NULL
;
6531 routedata
->destvertices
= routedata
->srcvertices
= NULL
;
6536 print_routedata(toporouter_route_t *routedata)
6538 GList *srcvertices = cluster_vertices(routedata->src);
6539 GList *destvertices = cluster_vertices(routedata->dest);
6541 printf("ROUTEDATA:\n");
6542 printf("SRCVERTICES:\n");
6543 print_vertices(srcvertices);
6544 printf("DESTVERTICES:\n");
6545 print_vertices(destvertices);
6547 g_list_free(srcvertices);
6548 g_list_free(destvertices);
6551 toporouter_route_t
*
6552 import_route(toporouter_t
*r
, RatType
*line
)
6554 toporouter_route_t
*routedata
= routedata_create();
6556 routedata
->src
= cluster_find(r
, line
->Point1
.X
, line
->Point1
.Y
, line
->group1
);
6557 routedata
->dest
= cluster_find(r
, line
->Point2
.X
, line
->Point2
.Y
, line
->group2
);
6559 if(!routedata
->src
) printf("couldn't locate src\n");
6560 if(!routedata
->dest
) printf("couldn't locate dest\n");
6562 if(!routedata
->src
|| !routedata
->dest
) {
6563 pcb_printf("PROBLEM: couldn't locate rat src or dest for rat %#mD, %d -> %#mD, %d\n",
6564 line
->Point1
.X
, line
->Point1
.Y
, line
->group1
, line
->Point2
.X
, line
->Point2
.Y
, line
->group2
);
6569 routedata
->netlist
= routedata
->src
->netlist
;
6571 g_assert(routedata
->src
->netlist
== routedata
->dest
->netlist
);
6573 g_ptr_array_add(r
->routes
, routedata
);
6574 g_ptr_array_add(routedata
->netlist
->routes
, routedata
);
6576 r
->failednets
= g_list_prepend(r
->failednets
, routedata
);
6582 delete_route(toporouter_route_t
*routedata
, guint destroy
)
6584 GList
*i
= routedata
->path
;
6585 toporouter_vertex_t
*pv
= NULL
;
6588 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6592 if(tv
&& pv
&& !(tv
->flags
& VERTEX_FLAG_ROUTE
) && !(pv
->flags
& VERTEX_FLAG_ROUTE
)) {
6593 toporouter_edge_t
*e
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(tv
), GTS_VERTEX(pv
)));
6595 if(e
&& (e
->flags
& EDGE_FLAG_DIRECTCONNECTION
)) {
6596 e
->flags
^= EDGE_FLAG_DIRECTCONNECTION
;
6603 i
= routedata
->path
;
6605 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6610 if(tv
->routingedge
) {
6611 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6612 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
6614 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
6615 if(destroy
) gts_object_destroy ( GTS_OBJECT(tv
) );
6621 if(routedata
->path
) g_list_free(routedata
->path
);
6622 routedata
->path
= NULL
;
6623 routedata
->curpoint
= NULL
;
6624 routedata
->score
= INFINITY
;
6625 routedata
->alltemppoints
= NULL
;
6628 /* remove route can be later reapplied */
6630 remove_route(GList
*path
)
6635 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6640 // if(tv->flags & VERTEX_FLAG_ROUTE) g_assert(tv->route == routedata);
6642 if(tv
->routingedge
) {
6644 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6645 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
6647 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
6655 apply_route(GList
*path
, toporouter_route_t
*routedata
)
6658 toporouter_vertex_t
*pv
= NULL
;
6665 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6667 if(tv
->routingedge
) {
6668 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6669 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_insert_sorted_with_data(
6670 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
,
6672 routing_edge_insert
,
6675 tv
->routingedge
->routing
= g_list_insert_sorted_with_data(
6676 tv
->routingedge
->routing
,
6678 routing_edge_insert
,
6689 if(tv
->flags
& VERTEX_FLAG_ROUTE
) g_assert(tv
->route
== routedata
);
6695 TOPOROUTER_VERTEX(path
->data
)->parent
= NULL
;
6703 compare_routedata_ascending(gconstpointer a
, gconstpointer b
)
6705 toporouter_route_t
*ra
= (toporouter_route_t
*)a
;
6706 toporouter_route_t
*rb
= (toporouter_route_t
*)b
;
6707 return ra
->score
- rb
->score
;
6711 print_costmatrix(gdouble
*m
, guint n
)
6713 printf("COST MATRIX:\n");
6714 for(guint i
= 0;i
<n
;i
++) {
6715 for(guint j
= 0;j
<n
;j
++) {
6716 printf("%f ", m
[(i
*n
)+j
]);
6724 init_cost_matrix(gdouble
*m
, guint n
)
6726 for(guint i
=0;i
<n
;i
++) {
6727 for(guint j
=0;j
<n
;j
++) {
6728 m
[(i
*n
)+j
] = INFINITY
;
6734 toporouter_netscore_t
*
6735 netscore_create(toporouter_t
*r
, toporouter_route_t
*routedata
, guint n
, guint id
)
6737 toporouter_netscore_t
*netscore
= (toporouter_netscore_t
*)malloc(sizeof(toporouter_netscore_t
));
6738 GList
*path
= route(r
, routedata
, 0);
6742 netscore
->routedata
= routedata
;
6743 routedata
->detourscore
= netscore
->score
= routedata
->score
;
6745 if(!finite(routedata
->detourscore
)) {
6746 printf("WARNING: !finite(detourscore)\n");
6747 print_cluster(routedata
->src
);
6748 print_cluster(routedata
->dest
);
6752 netscore
->pairwise_nodetour
= (guint
*)malloc(n
* sizeof(guint
));
6754 for(guint i
=0;i
<n
;i
++) {
6755 netscore
->pairwise_nodetour
[i
] = 0;
6758 netscore
->pairwise_detour_sum
= 0.;
6759 netscore
->pairwise_fails
= 0;
6764 routedata
->topopath
= g_list_copy(routedata
->path
);
6765 delete_route(routedata
, 0);
6772 netscore_destroy(toporouter_netscore_t
*netscore
)
6774 free(netscore
->pairwise_nodetour
);
6779 print_netscores(GPtrArray
* netscores
)
6781 printf("NETSCORES: \n\n");
6782 printf(" %15s %15s %15s\n----------------------------------------------------\n", "Score", "Detour Sum", "Pairwise Fails");
6784 for(toporouter_netscore_t
**i
= (toporouter_netscore_t
**) netscores
->pdata
; i
< (toporouter_netscore_t
**) netscores
->pdata
+ netscores
->len
; i
++) {
6785 #ifdef DEBUG_NETSCORES
6786 printf("%4d %15f %15f %15d %15x\n", (*i
)->id
, (*i
)->score
, (*i
)->pairwise_detour_sum
, (*i
)->pairwise_fails
, (guint
)*i
);
6794 netscore_pairwise_calculation(toporouter_netscore_t
*netscore
, GPtrArray
*netscores
)
6796 toporouter_netscore_t
**netscores_base
= (toporouter_netscore_t
**) (netscores
->pdata
);
6797 toporouter_route_t
*temproutedata
= routedata_create();
6799 //route(netscore->r, netscore->routedata, 0);
6800 apply_route(netscore
->routedata
->topopath
, netscore
->routedata
);
6802 for(toporouter_netscore_t
**i
= netscores_base
; i
< netscores_base
+ netscores
->len
; i
++) {
6804 if(!netscore
->pairwise_nodetour
[i
-netscores_base
] && *i
!= netscore
&& (*i
)->routedata
->netlist
!= netscore
->routedata
->netlist
) {
6806 temproutedata
->src
= (*i
)->routedata
->src
;
6807 temproutedata
->dest
= (*i
)->routedata
->dest
;
6809 route(netscore
->r
, temproutedata
, 0);
6811 if(temproutedata
->score
== (*i
)->score
) {
6812 netscore
->pairwise_nodetour
[i
-netscores_base
] = 1;
6813 (*i
)->pairwise_nodetour
[netscore
->id
] = 1;
6815 if(!finite(temproutedata
->score
)) {
6816 netscore
->pairwise_fails
+= 1;
6818 netscore
->pairwise_detour_sum
+= temproutedata
->score
- (*i
)->score
;
6821 delete_route(temproutedata
, 1);
6826 // delete_route(netscore->routedata, 1);
6827 remove_route(netscore
->routedata
->topopath
);
6829 free(temproutedata
);
6833 netscore_pairwise_size_compare(toporouter_netscore_t
**a
, toporouter_netscore_t
**b
)
6835 // infinite scores are last
6836 if(!finite((*a
)->score
) && !finite((*b
)->score
)) return 0;
6837 if(finite((*a
)->score
) && !finite((*b
)->score
)) return -1;
6838 if(finite((*b
)->score
) && !finite((*a
)->score
)) return 1;
6840 // order by pairwise fails
6841 if((*a
)->pairwise_fails
< (*b
)->pairwise_fails
) return -1;
6842 if((*b
)->pairwise_fails
< (*a
)->pairwise_fails
) return 1;
6844 // order by pairwise detour
6845 if((*a
)->pairwise_detour_sum
< (*b
)->pairwise_detour_sum
) return -1;
6846 if((*b
)->pairwise_detour_sum
< (*a
)->pairwise_detour_sum
) return 1;
6849 if((*a
)->score
< (*b
)->score
) return -1;
6850 if((*b
)->score
< (*a
)->score
) return 1;
6856 netscore_pairwise_compare(toporouter_netscore_t
**a
, toporouter_netscore_t
**b
)
6858 // infinite scores are last
6859 if(!finite((*a
)->score
) && !finite((*b
)->score
)) return 0;
6860 if(finite((*a
)->score
) && !finite((*b
)->score
)) return -1;
6861 if(finite((*b
)->score
) && !finite((*a
)->score
)) return 1;
6863 // order by pairwise fails
6864 if((*a
)->pairwise_fails
< (*b
)->pairwise_fails
) return -1;
6865 if((*b
)->pairwise_fails
< (*a
)->pairwise_fails
) return 1;
6867 // order by pairwise detour
6868 if((*a
)->pairwise_detour_sum
< (*b
)->pairwise_detour_sum
) return -1;
6869 if((*b
)->pairwise_detour_sum
< (*a
)->pairwise_detour_sum
) return 1;
6875 order_nets_preroute_greedy(toporouter_t
*r
, GList
*nets
, GList
**rnets
)
6877 gint len
= g_list_length(nets
);
6878 GPtrArray
* netscores
= g_ptr_array_sized_new(len
);
6879 guint failcount
= 0;
6882 toporouter_netscore_t
*ns
= netscore_create(r
, TOPOROUTER_ROUTE(nets
->data
), len
, failcount
++);
6883 if(ns
) g_ptr_array_add(netscores
, ns
);
6889 g_ptr_array_foreach(netscores
, (GFunc
) netscore_pairwise_calculation
, netscores
);
6891 g_ptr_array_sort(netscores
, (GCompareFunc
) r
->netsort
);
6893 #ifdef DEBUG_ORDERING
6894 print_netscores(netscores
);
6898 FOREACH_NETSCORE(netscores
) {
6899 *rnets
= g_list_prepend(*rnets
, netscore
->routedata
);
6900 if(!finite(netscore
->score
)) failcount
++;
6901 netscore_destroy(netscore
);
6904 g_ptr_array_free(netscores
, TRUE
);
6909 toporouter_vertex_t
*
6910 edge_closest_vertex(toporouter_edge_t
*e
, toporouter_vertex_t
*v
)
6912 GList
*i
= v
->routingedge
? edge_routing(v
->routingedge
) : NULL
;
6913 gdouble closestd
= 0.;
6914 toporouter_vertex_t
*closestv
= NULL
;
6917 toporouter_vertex_t
*ev
= TOPOROUTER_VERTEX(i
->data
);
6918 gdouble tempd
= gts_point_distance2(GTS_POINT(ev
), GTS_POINT(v
));
6920 if(!closestv
|| (tempd
< closestd
)) {
6932 snapshot(toporouter_t
*r
, char *name
, GList
*datas
)
6937 for(i
=0;i
<groupcount();i
++) {
6939 sprintf(buffer
, "route-%s-%d.png", name
, i
);
6940 toporouter_draw_surface(r
, r
->layers
[i
].surface
, buffer
, 2048, 2048, 2, datas
, i
, NULL
);
6948 route_conflict(toporouter_t *r, toporouter_route_t *route, guint *n)
6950 GList *i = route->path;
6951 toporouter_vertex_t *pv = NULL;
6955 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
6956 if(pv && vz(v) == vz(pv))
6957 cost += vertices_routing_conflict_cost(r, v, pv, n);
6966 route_conflicts(toporouter_route_t
*route
)
6968 GList
*conflicts
= NULL
, *i
= route
->path
;
6969 toporouter_vertex_t
*pv
= NULL
;
6972 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6974 if(pv
&& vz(pv
) == vz(v
)) {
6975 GList
*temp
= vertices_routing_conflicts(pv
, v
), *j
;
6979 toporouter_route_t
*conroute
= TOPOROUTER_ROUTE(j
->data
);
6980 if(!g_list_find(conflicts
, conroute
))
6981 conflicts
= g_list_prepend(conflicts
, conroute
);
6985 if(temp
) g_list_free(temp
);
6995 spread_edge(gpointer item
, gpointer data
)
6997 toporouter_edge_t
*e
= TOPOROUTER_EDGE(item
);
6998 toporouter_vertex_t
*v
;
7002 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
7004 i
= edge_routing(e
);
7006 if(!g_list_length(i
)) return 0;
7008 if(g_list_length(i
) == 1) {
7009 v
= TOPOROUTER_VERTEX(i
->data
);
7010 GTS_POINT(v
)->x
= (vx(edge_v1(e
)) + vx(edge_v2(e
))) / 2.;
7011 GTS_POINT(v
)->y
= (vy(edge_v1(e
)) + vy(edge_v2(e
))) / 2.;
7015 s
= spacing
= (gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) ) / (g_list_length(i
) + 1);
7018 v
= TOPOROUTER_VERTEX(i
->data
);
7019 vertex_move_towards_vertex_values(edge_v1(e
), edge_v2(e
), s
, &(GTS_POINT(v
)->x
), &(GTS_POINT(v
)->y
));
7029 route_checkpoint(toporouter_route_t
*route
, toporouter_route_t
*temproute
)
7031 GList
*i
= g_list_last(route
->path
);
7032 gint n
= g_list_length(route
->path
);
7034 if(route
->ppathindices
) free(route
->ppathindices
);
7035 route
->ppathindices
= (gint
*)malloc(sizeof(gint
)*n
);
7039 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7042 if(v
->routingedge
) {
7043 GList
*j
= g_list_find(edge_routing(v
->routingedge
), v
)->prev
;
7044 gint tempindex
= g_list_index(edge_routing(v
->routingedge
), v
);
7047 if(TOPOROUTER_VERTEX(j
->data
)->route
== temproute
) tempindex
--;
7051 route
->ppathindices
[n
] = tempindex
;
7053 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
7054 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
);
7056 v
->routingedge
->routing
= g_list_remove(v
->routingedge
->routing
, v
);
7062 route
->pscore
= route
->score
;
7063 route
->ppath
= route
->path
;
7064 remove_route(route
->path
);
7066 route
->psrc
= route
->src
;
7067 route
->pdest
= route
->dest
;
7068 //route->src->pc = route->src->c;
7069 //route->dest->pc = route->dest->c;
7073 route_restore(toporouter_route_t
*route
)
7076 toporouter_vertex_t
*pv
= NULL
;
7079 g_assert(route
->ppath
);
7080 g_assert(route
->ppathindices
);
7082 route
->path
= route
->ppath
;
7085 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7087 if(v
->routingedge
) {
7088 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
7089 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_insert(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
, route
->ppathindices
[n
]);
7091 v
->routingedge
->routing
= g_list_insert(v
->routingedge
->routing
, v
, route
->ppathindices
[n
]);
7093 // space_edge(v->routingedge, NULL);
7106 route
->score
= route
->pscore
;
7107 route
->src
= route
->psrc
;
7108 route
->dest
= route
->pdest
;
7109 //route->src->c = route->src->pc;
7110 //route->dest->c = route->dest->pc;
7115 cluster_merge(toporouter_route_t
*routedata
)
7117 gint oldc
= routedata
->dest
->c
, newc
= routedata
->src
->c
;
7119 FOREACH_CLUSTER(routedata
->netlist
->clusters
) {
7120 if(cluster
->c
== oldc
)
7127 netlist_recalculate(toporouter_netlist_t
*netlist
, GList
*ignore
)
7129 GList
*i
= g_list_last(netlist
->routed
);
7130 gint n
= netlist
->clusters
->len
-1;
7132 FOREACH_CLUSTER(netlist
->clusters
) {
7137 if(!ignore
|| !g_list_find(ignore
, i
->data
)) cluster_merge(TOPOROUTER_ROUTE(i
->data
));
7144 netlists_recalculate(GList
*netlists
, GList
*ignore
)
7146 GList
*i
= netlists
;
7148 netlist_recalculate(TOPOROUTER_NETLIST(i
->data
), ignore
);
7154 netlists_rollback(GList
*netlists
)
7156 // netlists_recalculate(netlists, NULL);
7158 toporouter_netlist_t
*netlist
= TOPOROUTER_NETLIST(netlists
->data
);
7160 FOREACH_CLUSTER(netlist
->clusters
) {
7161 cluster
->c
= cluster
->pc
;
7164 netlists
= netlists
->next
;
7169 print_netlist(toporouter_netlist_t
*netlist
)
7172 printf("NETLIST %s: ", netlist
->netlist
);
7174 FOREACH_CLUSTER(netlist
->clusters
) {
7175 printf("%d ", cluster
->c
);
7181 #define REMOVE_ROUTING(x) x->netlist->routed = g_list_remove(x->netlist->routed, x); \
7182 r->routednets = g_list_remove(r->routednets, x); \
7183 r->failednets = g_list_prepend(r->failednets, x)
7185 #define INSERT_ROUTING(x) x->netlist->routed = g_list_prepend(x->netlist->routed, x); \
7186 r->routednets = g_list_prepend(r->routednets, x); \
7187 r->failednets = g_list_remove(r->failednets, x)
7190 roar_route(toporouter_t
*r
, toporouter_route_t
*routedata
, gint threshold
)
7193 GList
*netlists
= NULL
, *routed
= NULL
;
7195 g_assert(!routedata
->path
);
7197 if(routedata
->src
->c
== routedata
->dest
->c
) {
7198 printf("ERROR: attempt to route already complete route\n");
7199 g_assert(routedata
->src
->c
!= routedata
->dest
->c
);
7202 routedata
->src
->pc
= routedata
->src
->c
;
7203 routedata
->dest
->pc
= routedata
->dest
->c
;
7204 routedata
->psrc
= routedata
->src
;
7205 routedata
->pdest
= routedata
->dest
;
7207 r
->flags
|= TOPOROUTER_FLAG_LEASTINVALID
;
7208 if(route(r
, routedata
, 0)) {
7209 GList
*conflicts
, *j
;
7211 INSERT_ROUTING(routedata
);
7213 conflicts
= route_conflicts(routedata
);
7214 cluster_merge(routedata
);
7216 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7220 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7221 if(!g_list_find(netlists
, conflict
->netlist
))
7222 netlists
= g_list_prepend(netlists
, conflict
->netlist
);
7224 route_checkpoint(conflict
, routedata
);
7226 REMOVE_ROUTING(conflict
);
7230 netlists
= g_list_prepend(netlists
, routedata
->netlist
);
7231 netlists_recalculate(netlists
, NULL
);
7235 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7236 g_assert(conflict
->src
->c
!= conflict
->dest
->c
);
7237 if(route(r
, conflict
, 0)) {
7238 cluster_merge(conflict
);
7240 routed
= g_list_prepend(routed
, conflict
);
7242 INSERT_ROUTING(conflict
);
7244 netlist_recalculate(conflict
->netlist
, NULL
);
7247 if(++intfails
>= threshold
) {
7250 toporouter_route_t
*intconflict
= TOPOROUTER_ROUTE(i
->data
);
7251 REMOVE_ROUTING(intconflict
);
7252 delete_route(intconflict
, 1);
7255 delete_route(routedata
, 1);
7256 i
= g_list_last(conflicts
);
7258 toporouter_route_t
*intconflict
= TOPOROUTER_ROUTE(i
->data
);
7260 route_restore(intconflict
);
7261 INSERT_ROUTING(intconflict
);
7265 REMOVE_ROUTING(routedata
);
7267 netlists_recalculate(netlists
, NULL
);
7268 goto roar_route_end
;
7276 netlists_recalculate(netlists
, NULL
);
7280 g_list_free(conflicts
);
7281 g_list_free(netlists
);
7284 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7287 g_list_free(routed
);
7292 roar_router(toporouter_t
*r
, gint failcount
, gint threshold
)
7294 gint pfailcount
= failcount
+1;
7296 Message(_("ROAR router: "));
7297 for(guint j
=0;j
<6;j
++) {
7298 GList
*failed
= g_list_copy(r
->failednets
), *k
= failed
;
7302 failcount
+= roar_route(r
, TOPOROUTER_ROUTE(k
->data
), threshold
);
7305 g_list_free(failed
);
7307 printf("\tROAR pass %d - %d routed - %d failed\n", j
, g_list_length(r
->routednets
), g_list_length(r
->failednets
));
7309 if(!failcount
|| failcount
>= pfailcount
) {
7310 Message(_("%d nets remaining\n"), failcount
);
7313 Message(_("%d -> "), failcount
);
7314 pfailcount
= failcount
;
7321 route_detour_compare(toporouter_route_t
**a
, toporouter_route_t
**b
)
7322 { return ((*b
)->score
- (*b
)->detourscore
) - ((*a
)->score
- (*a
)->detourscore
); }
7327 roar_detour_route(toporouter_t
*r
, toporouter_route_t
*data
)
7329 gdouble pscore
= data
->score
, nscore
= 0.;
7330 GList
*netlists
= NULL
;
7332 route_checkpoint(data
, NULL
);
7334 REMOVE_ROUTING(data
);
7336 netlists
= g_list_prepend(NULL
, data
->netlist
);
7337 netlists_recalculate(netlists
, NULL
);
7339 r
->flags
|= TOPOROUTER_FLAG_LEASTINVALID
;
7340 if(route(r
, data
, 0)) {
7341 GList
*conflicts
, *j
;
7343 nscore
= data
->score
;
7344 conflicts
= route_conflicts(data
);
7346 INSERT_ROUTING(data
);
7348 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7352 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7354 if(!g_list_find(netlists
, conflict
->netlist
))
7355 netlists
= g_list_prepend(netlists
, conflict
->netlist
);
7356 pscore
+= conflict
->score
;
7358 route_checkpoint(conflict
, NULL
);
7359 REMOVE_ROUTING(conflict
);
7363 netlists_recalculate(netlists
, NULL
);
7367 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7369 if(route(r
, conflict
, 0)) {
7370 cluster_merge(conflict
);
7371 INSERT_ROUTING(conflict
);
7372 nscore
+= conflict
->score
;
7375 goto roar_detour_route_rollback_int
;
7380 if(nscore
> pscore
) {
7381 j
= g_list_last(conflicts
);
7382 roar_detour_route_rollback_int
:
7383 REMOVE_ROUTING(data
);
7386 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7387 REMOVE_ROUTING(conflict
);
7388 delete_route(conflict
, 1);
7392 j
= g_list_last(conflicts
);
7394 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7395 route_restore(conflict
);
7396 INSERT_ROUTING(conflict
);
7399 delete_route(data
, 1);
7401 goto roar_detour_route_rollback_exit
;
7405 g_list_free(conflicts
);
7407 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7408 roar_detour_route_rollback_exit
:
7409 route_restore(data
);
7410 INSERT_ROUTING(data
);
7412 netlists_recalculate(netlists
, NULL
);
7414 g_list_free(netlists
);
7418 detour_router(toporouter_t
*r
)
7420 GList
*i
= r
->routednets
;
7421 guint n
= g_list_length(r
->routednets
);
7422 GPtrArray
* scores
= g_ptr_array_sized_new(n
);
7425 toporouter_route_t
*curroute
= TOPOROUTER_ROUTE(i
->data
);
7426 curroute
->score
= path_score(r
, curroute
->path
);
7427 g_ptr_array_add(scores
, i
->data
);
7431 g_ptr_array_sort(scores
, (GCompareFunc
) route_detour_compare
);
7433 r
->flags
|= TOPOROUTER_FLAG_DETOUR
;
7435 for(toporouter_route_t
**i
= (toporouter_route_t
**) scores
->pdata
; i
< (toporouter_route_t
**) scores
->pdata
+ scores
->len
; i
++) {
7436 toporouter_route_t
*curroute
= (*i
);
7438 if(finite(curroute
->score
) && finite(curroute
->detourscore
)) {
7439 // printf("%15s %15f \t %8f,%8f - %8f,%8f\n", (*i)->src->netlist + 2, (*i)->score - (*i)->detourscore,
7440 // vx(curroute->mergebox1->point), vy(curroute->mergebox1->point),
7441 // vx(curroute->mergebox2->point), vy(curroute->mergebox2->point));
7443 if(curroute
->score
- curroute
->detourscore
> ROAR_DETOUR_THRESHOLD
) {
7444 roar_detour_route(r
, curroute
);
7451 r
->flags
^= TOPOROUTER_FLAG_DETOUR
;
7453 g_ptr_array_free(scores
, TRUE
);
7458 rubix_router(toporouter_t
*r
, gint failcount
)
7460 GList
*i
, *ordering
;
7461 order_nets_preroute_greedy(r
, r
->failednets
, &ordering
);
7465 toporouter_route_t
*data
= TOPOROUTER_ROUTE(i
->data
);
7467 if(route(r
, data
, 0)) {
7468 INSERT_ROUTING(data
);
7469 cluster_merge(data
);
7476 g_list_free(ordering
);
7482 hybrid_router(toporouter_t
*r
)
7484 gint failcount
= g_list_length(r
->failednets
);
7485 r
->flags
|= TOPOROUTER_FLAG_AFTERORDER
;
7486 r
->flags
|= TOPOROUTER_FLAG_AFTERRUBIX
;
7487 failcount
= rubix_router(r
, failcount
);
7489 Message(_("RUBIX router: %d nets remaining\n"), failcount
);
7490 printf("RUBIX router: %d nets remaining\n", failcount
);
7492 r
->flags
|= TOPOROUTER_FLAG_GOFAR
;
7494 for(guint i
=0;i
<6 && failcount
;i
++) {
7496 failcount
= roar_router(r
, failcount
, 5);
7497 // printf("THRESH 5\n");
7499 failcount
= roar_router(r
, failcount
, 2);
7500 // printf("THRESH 2\n");
7506 failcount
= roar_router(r
, failcount
, 2);
7513 parse_arguments(toporouter_t
*r
, int argc
, char **argv
)
7516 for(i
=0;i
<argc
;i
++) {
7517 if(sscanf(argv
[i
], "viacost=%d", &tempint
)) {
7518 /* XXX: We should be using PCB's generic value with unit parsing here */
7519 r
->viacost
= (double)tempint
;
7520 }else if(sscanf(argv
[i
], "l%d", &tempint
)) {
7521 gdouble
*layer
= (gdouble
*)malloc(sizeof(gdouble
));
7522 *layer
= (double)tempint
;
7523 r
->keepoutlayers
= g_list_prepend(r
->keepoutlayers
, layer
);
7527 for (guint group
= 0; group
< max_group
; group
++)
7528 for (i
= 0; i
< PCB
->LayerGroups
.Number
[group
]; i
++)
7529 if ((PCB
->LayerGroups
.Entries
[group
][i
] < max_copper_layer
) && !(PCB
->Data
->Layer
[PCB
->LayerGroups
.Entries
[group
][i
]].On
)) {
7530 gdouble
*layer
= (gdouble
*)malloc(sizeof(gdouble
));
7531 *layer
= (double)group
;
7532 r
->keepoutlayers
= g_list_prepend(r
->keepoutlayers
, layer
);
7538 toporouter_new(void)
7540 toporouter_t
*r
= (toporouter_t
*)calloc(1, sizeof(toporouter_t
));
7543 gettimeofday(&r
->starttime
, NULL
);
7545 r
->netsort
= netscore_pairwise_compare
;
7547 r
->destboxes
= NULL
;
7548 r
->consumeddestboxes
= NULL
;
7554 r
->viacost
= VIA_COST_AS_DISTANCE
;
7556 r
->wiring_score
= 0.;
7561 r
->netlists
= g_ptr_array_new();
7562 r
->routes
= g_ptr_array_new();
7564 r
->keepoutlayers
= NULL
;
7566 r
->routednets
= NULL
;
7567 r
->failednets
= NULL
;
7571 gts_predicates_init();
7573 Message(_("Topological Autorouter\n"));
7574 Message(_("Started %s"),asctime(localtime(<ime
)));
7575 Message(_("-------------------------------------\n"));
7580 acquire_twonets(toporouter_t
*r
)
7582 RAT_LOOP(PCB
->Data
);
7583 if( TEST_FLAG(SELECTEDFLAG
, line
) ) import_route(r
, line
);
7586 if(!r
->routes
->len
) {
7587 RAT_LOOP(PCB
->Data
);
7588 import_route(r
, line
);
7595 toporouter_netlist_t
*
7596 find_netlist_by_name(toporouter_t
*r
, char *name
)
7598 FOREACH_NETLIST(r
->netlists
) {
7599 if(!strcmp(netlist
->netlist
, name
)) return netlist
;
7605 toporouter_set_pair(toporouter_t
*r
, toporouter_netlist_t
*n1
, toporouter_netlist_t
*n2
)
7607 if(!n1
|| !n2
) return 0;
7614 toporouter (int argc
, char **argv
, Coord x
, Coord y
)
7616 toporouter_t
*r
= toporouter_new();
7617 parse_arguments(r
, argc
, argv
);
7621 //if(!toporouter_set_pair(r, find_netlist_by_name(r, " DRAM_DQS_N"), find_netlist_by_name(r, " DRAM_DQS"))) {
7622 // printf("Couldn't associate pair\n");
7627 for(gint i=0;i<groupcount();i++) {
7628 gts_surface_foreach_edge(r->layers[i].surface, space_edge, NULL);
7632 for(i=0;i<groupcount();i++) {
7634 sprintf(buffer, "route%d.png", i);
7635 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, NULL, i, NULL);
7639 toporouter_export(r
);
7642 SaveUndoSerialNumber ();
7644 RestoreUndoSerialNumber ();
7645 AddAllRats (false, NULL
);
7646 RestoreUndoSerialNumber ();
7647 IncrementUndoSerialNumber ();
7654 escape (int argc
, char **argv
, Coord x
, Coord y
)
7656 guint dir
, viax
, viay
;
7657 gdouble pitch
, length
, dx
, dy
;
7659 if(argc
!= 1) return 0;
7661 dir
= atoi(argv
[0]);
7664 ALLPAD_LOOP(PCB
->Data
);
7666 if( TEST_FLAG(SELECTEDFLAG
, pad
) ) {
7670 PadType
*pad0
= element
->Pad
->data
;
7671 PadType
*pad1
= g_list_next (element
->Pad
)->data
;
7673 pitch
= sqrt (pow (abs (pad0
->Point1
.X
- pad1
->Point1
.X
), 2) +
7674 pow (abs (pad0
->Point1
.Y
- pad1
->Point1
.Y
), 2) );
7675 length
= sqrt(pow(pitch
,2) + pow(pitch
,2)) / 2.;
7677 dx
= length
* sin(M_PI
/4.);
7678 dy
= length
* cos(M_PI
/4.);
7682 viax
= pad
->Point1
.X
- dx
;
7683 viay
= pad
->Point1
.Y
+ dy
;
7686 viax
= pad
->Point1
.X
+ dx
;
7687 viay
= pad
->Point1
.Y
+ dy
;
7690 viax
= pad
->Point1
.X
+ dx
;
7691 viay
= pad
->Point1
.Y
- dy
;
7694 viax
= pad
->Point1
.X
- dx
;
7695 viay
= pad
->Point1
.Y
- dy
;
7698 viax
= pad
->Point1
.X
;
7699 viay
= pad
->Point1
.Y
+ (pitch
/2);
7702 viax
= pad
->Point1
.X
;
7703 viay
= pad
->Point1
.Y
- (pitch
/2);
7706 viax
= pad
->Point1
.X
- (pitch
/2);
7707 viay
= pad
->Point1
.Y
;
7710 viax
= pad
->Point1
.X
+ (pitch
/2);
7711 viay
= pad
->Point1
.Y
;
7714 printf("ERROR: escape() with bad direction (%d)\n", dir
);
7718 if ((via
= CreateNewVia (PCB
->Data
, viax
, viay
,
7719 Settings
.ViaThickness
, 2 * Settings
.Keepaway
,
7720 0, Settings
.ViaDrillingHole
, NULL
,
7721 NoFlags ())) != NULL
)
7723 AddObjectToCreateUndoList (VIA_TYPE
, via
, via
, via
);
7724 // if (gui->shift_is_pressed ())
7725 // ChangeObjectThermal (VIA_TYPE, via, via, via, PCB->ThermStyle);
7727 if((line
= CreateDrawnLineOnLayer (CURRENT
, pad
->Point1
.X
+ 1., pad
->Point1
.Y
+ 1., viax
+ 1., viay
+ 1.,
7728 Settings
.LineThickness
, 2 * Settings
.Keepaway
,
7732 AddObjectToCreateUndoList (LINE_TYPE
, CURRENT
, line
, line
);
7733 DrawLine (CURRENT
, line
);
7744 IncrementUndoSerialNumber ();
7749 static HID_Action toporouter_action_list
[] = {
7750 {"Escape", "Select a set of pads", escape
, "Pad escape", "Escape()"},
7751 {"Toporouter", "Select net(s)", toporouter
, "Topological autorouter", "Toporouter()"}
7754 REGISTER_ACTIONS (toporouter_action_list
)
7756 void hid_toporouter_init()
7758 register_toporouter_action_list();