4 * Topological Autorouter for
5 * PCB, interactive printed circuit board design
6 * Copyright (C) 2009 Anthony Blake
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 * Contact addresses for email:
23 * Anthony Blake, tonyb33@gmail.com
27 * This is *EXPERIMENTAL* code.
29 * As the code is experimental, the algorithms and code
30 * are likely to change. Which means it isn't documented
31 * or optimized. If you would like to learn about Topological
32 * Autorouters, the following papers are good starting points:
34 * This file implements a topological autorouter, and uses techniques from the
35 * following publications:
37 * Dayan, T. and Dai, W.W.M., "Layer Assignment for a Rubber Band Router" Tech
38 * Report UCSC-CRL-92-50, Univ. of California, Santa Cruz, 1992.
40 * Dai, W.W.M and Dayan, T. and Staepelaere, D., "Topological Routing in SURF:
41 * Generating a Rubber-Band Sketch" Proc. 28th ACM/IEEE Design Automation
42 * Conference, 1991, pp. 39-44.
44 * David Staepelaere, Jeffrey Jue, Tal Dayan, Wayne Wei-Ming Dai, "SURF:
45 * Rubber-Band Routing System for Multichip Modules," IEEE Design and Test of
46 * Computers ,vol. 10, no. 4, pp. 18-26, October/December, 1993.
48 * Dayan, T., "Rubber-band based topological router" PhD Thesis, Univ. of
49 * California, Santa Cruz, 1997.
51 * David Staepelaere, "Geometric transformations for a rubber-band sketch"
52 * Master's thesis, Univ. of California, Santa Cruz, September 1992.
57 #include "toporouter.h"
60 toporouter_edge_init (toporouter_edge_t
*edge
)
66 toporouter_edge_class_t
*
67 toporouter_edge_class(void)
69 static toporouter_edge_class_t
*class = NULL
;
72 GtsObjectClassInfo constraint_info
= {
74 sizeof (toporouter_edge_t
),
75 sizeof (toporouter_edge_class_t
),
76 (GtsObjectClassInitFunc
) NULL
,
77 (GtsObjectInitFunc
) toporouter_edge_init
,
81 class = gts_object_class_new (GTS_OBJECT_CLASS (gts_edge_class ()), &constraint_info
);
88 toporouter_bbox_init (toporouter_bbox_t
*box
)
92 box
->constraints
= NULL
;
96 toporouter_bbox_class_t
*
97 toporouter_bbox_class(void)
99 static toporouter_bbox_class_t
*class = NULL
;
102 GtsObjectClassInfo constraint_info
= {
104 sizeof (toporouter_bbox_t
),
105 sizeof (toporouter_bbox_class_t
),
106 (GtsObjectClassInitFunc
) NULL
,
107 (GtsObjectInitFunc
) toporouter_bbox_init
,
108 (GtsArgSetFunc
) NULL
,
111 class = gts_object_class_new (GTS_OBJECT_CLASS (gts_bbox_class ()), &constraint_info
);
118 toporouter_vertex_class_init (toporouter_vertex_class_t
*klass
)
124 toporouter_vertex_init (toporouter_vertex_t
*vertex
)
127 vertex
->parent
= NULL
;
128 vertex
->child
= NULL
;
130 vertex
->routingedge
= NULL
;
132 vertex
->oproute
= NULL
;
133 vertex
->route
= NULL
;
140 toporouter_vertex_class_t
*
141 toporouter_vertex_class(void)
143 static toporouter_vertex_class_t
*klass
= NULL
;
146 GtsObjectClassInfo constraint_info
= {
147 "toporouter_vertex_t",
148 sizeof (toporouter_vertex_t
),
149 sizeof (toporouter_vertex_class_t
),
150 (GtsObjectClassInitFunc
) toporouter_vertex_class_init
,
151 (GtsObjectInitFunc
) toporouter_vertex_init
,
152 (GtsArgSetFunc
) NULL
,
155 klass
= gts_object_class_new (GTS_OBJECT_CLASS (gts_vertex_class ()), &constraint_info
);
162 toporouter_constraint_class_init (toporouter_constraint_class_t
*klass
)
168 toporouter_constraint_init (toporouter_constraint_t
*constraint
)
170 constraint
->box
= NULL
;
171 constraint
->routing
= NULL
;
174 toporouter_constraint_class_t
*
175 toporouter_constraint_class(void)
177 static toporouter_constraint_class_t
*klass
= NULL
;
180 GtsObjectClassInfo constraint_info
= {
181 "toporouter_constraint_t",
182 sizeof (toporouter_constraint_t
),
183 sizeof (toporouter_constraint_class_t
),
184 (GtsObjectClassInitFunc
) toporouter_constraint_class_init
,
185 (GtsObjectInitFunc
) toporouter_constraint_init
,
186 (GtsArgSetFunc
) NULL
,
189 klass
= gts_object_class_new (GTS_OBJECT_CLASS (gts_constraint_class ()), &constraint_info
);
196 toporouter_arc_init (toporouter_arc_t
*arc
)
208 arc
->clearance
= NULL
;
212 toporouter_arc_class_t
*
213 toporouter_arc_class(void)
215 static toporouter_arc_class_t
*klass
= NULL
;
218 GtsObjectClassInfo constraint_info
= {
220 sizeof (toporouter_arc_t
),
221 sizeof (toporouter_arc_class_t
),
222 (GtsObjectClassInitFunc
) NULL
,
223 (GtsObjectInitFunc
) toporouter_arc_init
,
224 (GtsArgSetFunc
) NULL
,
227 klass
= gts_object_class_new (GTS_OBJECT_CLASS (gts_constraint_class ()), &constraint_info
);
236 toporouter_output_init(int w
, int h
, char *filename
)
238 drawing_context_t
*dc
;
240 dc
= malloc(sizeof(drawing_context_t
));
244 dc
->filename
= filename
;
246 /* Calculate scaling to maintain aspect ratio */
247 if(PCB
->MaxWidth
> PCB
->MaxHeight
) {
248 /* Scale board width to match image width minus 2xMARGIN */
249 dc
->s
= ((double)dc
->iw
- (2 * MARGIN
)) / (double)PCB
->MaxWidth
;
250 dc
->ih
= (double)PCB
->MaxHeight
* dc
->s
+ (2 * MARGIN
);
252 /* Scale board height to match image height minus 2xMARGIN */
253 dc
->s
= ((double)dc
->ih
- (2 * MARGIN
)) / (double)PCB
->MaxHeight
;
254 dc
->iw
= (double)PCB
->MaxWidth
* dc
->s
+ (2 * MARGIN
);
257 #if TOPO_OUTPUT_ENABLED
258 dc
->surface
= cairo_image_surface_create(CAIRO_FORMAT_ARGB32
, dc
->iw
, dc
->ih
);
259 dc
->cr
= cairo_create (dc
->surface
);
261 cairo_rectangle (dc
->cr
, 0, 0, dc
->iw
, dc
->ih
);
262 cairo_set_source_rgb (dc
->cr
, 0, 0, 0);
271 toporouter_output_close(drawing_context_t
*dc
)
273 #if TOPO_OUTPUT_ENABLED
274 cairo_surface_write_to_png (dc
->surface
, dc
->filename
);
275 cairo_destroy (dc
->cr
);
276 cairo_surface_destroy (dc
->surface
);
281 lookup_keepaway(char *name
)
286 // if(!strcmp(style->Name, name)) return style->Keepaway + 1.;
287 if(!strcmp(style
->Name
, name
)) return style
->Keepaway
;
290 // return Settings.Keepaway + 1.;
291 return Settings
.Keepaway
;
295 lookup_thickness(char *name
)
300 if(!strcmp(style
->Name
, name
)) return style
->Thick
;
303 return Settings
.LineThickness
;
307 cluster_keepaway(toporouter_cluster_t
*cluster
)
309 if(cluster
) return lookup_keepaway(cluster
->netlist
->style
);
310 return lookup_keepaway(NULL
);
314 cluster_thickness(toporouter_cluster_t
*cluster
)
316 if(cluster
) return lookup_thickness(cluster
->netlist
->style
);
317 return lookup_thickness(NULL
);
321 toporouter_draw_vertex(gpointer item
, gpointer data
)
323 #if TOPO_OUTPUT_ENABLED
324 drawing_context_t
*dc
= (drawing_context_t
*) data
;
325 toporouter_vertex_t
*tv
;
330 if(TOPOROUTER_IS_VERTEX((GtsObject
*)item
)) {
331 tv
= TOPOROUTER_VERTEX((GtsObject
*)item
);
333 if(tv
->flags
& VERTEX_FLAG_RED
) {
334 cairo_set_source_rgba(dc
->cr
, 1., 0., 0., 0.8f
);
336 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
337 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
338 500. * dc
->s
, 0, 2 * M_PI
);
341 }else if(tv
->flags
& VERTEX_FLAG_GREEN
) {
342 cairo_set_source_rgba(dc
->cr
, 0., 1., 0., 0.8f
);
344 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
345 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
346 500. * dc
->s
, 0, 2 * M_PI
);
349 }else if(tv
->flags
& VERTEX_FLAG_BLUE
) {
350 cairo_set_source_rgba(dc
->cr
, 0., 0., 1., 0.8f
);
352 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
353 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
354 500. * dc
->s
, 0, 2 * M_PI
);
359 //printf("tv->type = %d\n", tv->type);
362 pin
= (PinType
*) tv
->bbox
->data
;
363 pad
= (PadType
*) tv
->bbox
->data
;
366 switch(tv
->bbox
->type
) {
368 cairo_set_source_rgba(dc
->cr
, 1.0f
, 0., 0.0f
, 0.2f
);
370 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
371 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
372 (((gdouble
)pin
->Thickness
/ 2.0f
) + (gdouble
)lookup_keepaway(pin
->Name
) ) * dc
->s
, 0, 2 * M_PI
);
375 cairo_set_source_rgba(dc
->cr
, 1.0f
, 0., 0., 0.4f
);
377 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
378 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
379 (gdouble
)(pin
->Thickness
) / 2.0f
* dc
->s
,
385 cairo_set_source_rgba(dc
->cr
, 0.0f
, 0., 1., 0.2f
);
387 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
388 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
389 (((gdouble
)pin
->Thickness
/ 2.0f
) + (gdouble
)lookup_keepaway(pin
->Name
) ) * dc
->s
, 0, 2 * M_PI
);
392 cairo_set_source_rgba(dc
->cr
, 0.0f
, 0., 1., 0.4f
);
394 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
395 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
396 (gdouble
)(pin
->Thickness
) / 2.0f
* dc
->s
,
402 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1., 0., 0.5f
);
404 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
405 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
406 400. * dc
->s
, 0, 2 * M_PI
);
415 if(tv
->flags
& VERTEX_FLAG_BLUE
) {
416 cairo_set_source_rgba(dc
->cr
, 0., 0., 1., 0.8f
);
418 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
419 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
420 500. * dc
->s
, 0, 2 * M_PI
);
422 }else if(tv
->flags
& VERTEX_FLAG_RED
) {
423 cairo_set_source_rgba(dc
->cr
, 1., 0., 0., 0.8f
);
425 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
426 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
427 500. * dc
->s
, 0, 2 * M_PI
);
430 }else if(tv
->flags
& VERTEX_FLAG_GREEN
) {
431 cairo_set_source_rgba(dc
->cr
, 0., 1., 0., 0.8f
);
433 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
434 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
435 500. * dc
->s
, 0, 2 * M_PI
);
441 fprintf(stderr
, "Unknown data passed to toporouter_draw_vertex, aborting foreach\n");
451 toporouter_draw_edge(gpointer item
, gpointer data
)
453 #if TOPO_OUTPUT_ENABLED
454 drawing_context_t
*dc
= (drawing_context_t
*) data
;
455 toporouter_edge_t
*te
;
456 toporouter_constraint_t
*tc
;
458 if(TOPOROUTER_IS_EDGE((GtsObject
*)item
)) {
459 te
= TOPOROUTER_EDGE((GtsObject
*)item
);
460 cairo_set_source_rgba(dc
->cr
, 1.0f
, 1.0f
, 1.0f
, 0.5f
);
461 cairo_move_to(dc
->cr
,
462 te
->e
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
463 te
->e
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
464 cairo_line_to(dc
->cr
,
465 te
->e
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
466 te
->e
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
467 cairo_stroke(dc
->cr
);
468 }else if(TOPOROUTER_IS_CONSTRAINT((GtsObject
*)item
)) {
469 tc
= TOPOROUTER_CONSTRAINT((GtsObject
*)item
);
471 switch(tc
->box
->type
) {
473 cairo_set_source_rgba(dc
->cr
, 1.0f
, 0.0f
, 1.0f
, 0.9f
);
474 cairo_move_to(dc
->cr
,
475 tc
->c
.edge
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
476 tc
->c
.edge
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
477 cairo_line_to(dc
->cr
,
478 tc
->c
.edge
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
479 tc
->c
.edge
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
480 cairo_stroke(dc
->cr
);
484 cairo_set_source_rgba(dc
->cr
, 1.0f
, 0.0f
, 0.0f
, 0.9f
);
485 cairo_move_to(dc
->cr
,
486 tc
->c
.edge
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
487 tc
->c
.edge
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
488 cairo_line_to(dc
->cr
,
489 tc
->c
.edge
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
490 tc
->c
.edge
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
491 cairo_stroke(dc
->cr
);
494 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1.0f
, 0.0f
, 0.9f
);
495 cairo_move_to(dc
->cr
,
496 tc
->c
.edge
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
497 tc
->c
.edge
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
498 cairo_line_to(dc
->cr
,
499 tc
->c
.edge
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
500 tc
->c
.edge
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
501 cairo_stroke(dc
->cr
);
505 cairo_set_source_rgba(dc
->cr
, 1.0f
, 1.0f
, 0.0f
, 0.9f
);
506 cairo_move_to(dc
->cr
,
507 tc
->c
.edge
.segment
.v1
->p
.x
* dc
->s
+ MARGIN
,
508 tc
->c
.edge
.segment
.v1
->p
.y
* dc
->s
+ MARGIN
);
509 cairo_line_to(dc
->cr
,
510 tc
->c
.edge
.segment
.v2
->p
.x
* dc
->s
+ MARGIN
,
511 tc
->c
.edge
.segment
.v2
->p
.y
* dc
->s
+ MARGIN
);
512 cairo_stroke(dc
->cr
);
516 printf("CONSTRAINT without box\n");
520 fprintf(stderr
, "Unknown data passed to toporouter_draw_edge, aborting foreach\n");
530 //#define vertex_bbox(v) (v->bbox)
533 vertex_bbox(toporouter_vertex_t
*v
)
535 return v
? v
->bbox
: NULL
;
539 vertex_netlist(toporouter_vertex_t
*v
)
541 toporouter_bbox_t
*box
= vertex_bbox(v
);
543 if(box
&& box
->cluster
) return box
->cluster
->netlist
->netlist
;
549 constraint_netlist(toporouter_constraint_t
*c
)
551 toporouter_bbox_t
*box
= c
->box
;
553 if(box
&& box
->cluster
) return box
->cluster
->netlist
->netlist
;
559 epsilon_equals(gdouble a
, gdouble b
)
561 if(a
> b
- EPSILON
&& a
< b
+ EPSILON
) return 1;
566 print_bbox(toporouter_bbox_t
*box
)
571 printf("PAD "); break;
573 printf("PIN "); break;
575 printf("VIA "); break;
577 printf("LINE "); break;
579 printf("BOARD "); break;
581 printf("POLYGON "); break;
583 printf("UNKNOWN "); break;
587 printf("P: %f,%f,%f ", vx(box
->point
), vy(box
->point
), vz(box
->point
));
591 printf("LAYER: %d ", box
->layer
);
592 printf("CLUSTER: %d]\n", box
->cluster
? box
->cluster
->c
: -1);
597 print_vertex(toporouter_vertex_t
*v
)
600 printf("[V %f,%f,%f ", vx(v
), vy(v
), vz(v
));
602 printf("[V (null) ");
604 printf("%s ", vertex_netlist(v
));
605 if(v
->route
&& v
->route
->netlist
)
606 printf("%s ", v
->route
->netlist
->netlist
);
609 guint n
= g_list_length(edge_routing(v
->routingedge
));
610 guint pos
= g_list_index(edge_routing(v
->routingedge
), v
);
612 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
617 printf("%d/%d] ", pos
, n
);
622 if(v
->flags
& VERTEX_FLAG_TEMP
) printf("TEMP ");
623 if(v
->flags
& VERTEX_FLAG_ROUTE
) printf("ROUTE ");
624 if(v
->flags
& VERTEX_FLAG_SPECCUT
) printf("SPECCUT ");
625 if(v
->flags
& VERTEX_FLAG_FAKE
) printf("FAKE ");
632 vertex_net_thickness(toporouter_vertex_t
*v
)
634 toporouter_bbox_t
*box
= vertex_bbox(v
);
638 while(v
&& (v
->flags
& VERTEX_FLAG_TEMP
|| v
->flags
& VERTEX_FLAG_ROUTE
)) {
642 box
= vertex_bbox(v
);
645 if(box
->type
== PIN
|| box
->type
== VIA
) {
646 PinType
*pin
= (PinType
*)box
->data
;
647 if(TEST_FLAG(SQUAREFLAG
, pin
) || TEST_FLAG(OCTAGONFLAG
, pin
)) {
650 // return ((PinType *)box->data)->Thickness + 1.;
651 return ((PinType
*)box
->data
)->Thickness
;
652 }else if(box
->type
== PAD
) {
653 PadType
*pad
= (PadType
*)box
->data
;
654 if(pad
->Point1
.X
== pad
->Point2
.X
&& pad
->Point1
.Y
== pad
->Point2
.Y
&& !TEST_FLAG(SQUAREFLAG
, pad
)) {
655 return pad
->Thickness
;
658 }else if(box
->type
== BOARD
) {
660 }else if(box
->type
== LINE
) {
661 LineType
*line
= (LineType
*) box
->data
;
662 return line
->Thickness
;
663 }else if(box
->type
== POLYGON
) {
667 printf("Unrecognized type in thickness lookup..\n");
670 // if(!box || !box->cluster) return Settings.LineThickness + 1.;
671 if(!box
|| !box
->cluster
) return Settings
.LineThickness
;
673 return cluster_thickness(box
->cluster
);
677 vertex_net_keepaway(toporouter_vertex_t
*v
)
679 toporouter_bbox_t
*box
= vertex_bbox(v
);
682 while(v
&& (v
->flags
& VERTEX_FLAG_TEMP
|| v
->flags
& VERTEX_FLAG_ROUTE
)) {
685 box
= vertex_bbox(v
);
688 // if(box->type == PIN || box->type == VIA)
689 // return ((PinType *)box->data)->Clearance;
690 // else if(box->type == PAD)
691 // return ((PadType *)box->data)->Clearance;
695 // if(!box || !box->cluster) return Settings.Keepaway + 1.;
696 if(!box
|| !box
->cluster
) return Settings
.Keepaway
;
697 return cluster_keepaway(box
->cluster
);
708 size = backtrace (array, 10);
709 strings = backtrace_symbols (array, size);
711 printf ("Obtained %zd stack frames.\n", size);
713 for (i = 0; i < size; i++)
714 printf ("%s\n", strings[i]);
719 /* fills in x and y with coordinates of point from a towards b of distance d */
721 point_from_point_to_point(toporouter_vertex_t
*a
, toporouter_vertex_t
*b
, gdouble d
, gdouble
*x
, gdouble
*y
)
723 gdouble dx
= vx(b
) - vx(a
);
724 gdouble dy
= vy(b
) - vy(a
);
725 gdouble theta
= atan(fabs(dy
/dx
));
727 //#ifdef DEBUG_EXPORT
729 // printf("!finte(theta): a = %f,%f b = %f,%f d = %f\n", vx(a), vy(a), vx(b), vy(b), d);
731 //TODO: this shouldn't happen, fix the hack
738 g_assert(finite(theta
));
740 *x
= vx(a
); *y
= vy(a
);
745 *x
+= d
* cos(theta
);
746 *y
+= d
* sin(theta
);
748 *x
+= d
* cos(theta
);
749 *y
-= d
* sin(theta
);
755 *x
-= d
* cos(theta
);
756 *y
+= d
* sin(theta
);
758 *x
-= d
* cos(theta
);
759 *y
-= d
* sin(theta
);
767 coord_wind(gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
, gdouble cx
, gdouble cy
)
769 gdouble rval
, dx1
, dx2
, dy1
, dy2
;
770 dx1
= bx
- ax
; dy1
= by
- ay
;
771 dx2
= cx
- bx
; dy2
= cy
- by
;
772 rval
= (dx1
*dy2
)-(dy1
*dx2
);
773 return (rval
> EPSILON
) ? 1 : ((rval
< -EPSILON
) ? -1 : 0);
777 * returns 1,0,-1 for counterclockwise, collinear or clockwise, respectively.
780 point_wind(GtsPoint
*a
, GtsPoint
*b
, GtsPoint
*c
)
782 gdouble rval
, dx1
, dx2
, dy1
, dy2
;
783 dx1
= b
->x
- a
->x
; dy1
= b
->y
- a
->y
;
784 dx2
= c
->x
- b
->x
; dy2
= c
->y
- b
->y
;
785 rval
= (dx1
*dy2
)-(dy1
*dx2
);
786 return (rval
> EPSILON
) ? 1 : ((rval
< -EPSILON
) ? -1 : 0);
790 vertex_wind(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
)
792 return point_wind(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
));
796 tvertex_wind(toporouter_vertex_t
*a
, toporouter_vertex_t
*b
, toporouter_vertex_t
*c
)
798 return point_wind(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
));
802 sloppy_point_wind(GtsPoint
*a
, GtsPoint
*b
, GtsPoint
*c
)
804 gdouble rval
, dx1
, dx2
, dy1
, dy2
;
805 dx1
= b
->x
- a
->x
; dy1
= b
->y
- a
->y
;
806 dx2
= c
->x
- b
->x
; dy2
= c
->y
- b
->y
;
807 rval
= (dx1
*dy2
)-(dy1
*dx2
);
808 return (rval
> 10.) ? 1 : ((rval
< -10.) ? -1 : 0);
812 sloppy_vertex_wind(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
)
814 return point_wind(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
));
817 /* moves vertex v d units in the direction of vertex p */
819 coord_move_towards_coord_values(gdouble ax
, gdouble ay
, gdouble px
, gdouble py
, gdouble d
, gdouble
*x
, gdouble
*y
)
821 gdouble dx
= px
- ax
;
822 gdouble dy
= py
- ay
;
823 gdouble theta
= atan(fabs(dy
/dx
));
827 printf("!finite(theta) a = %f,%f p = %f,%f d = %f\n",
832 g_assert(finite(theta
));
837 *x
= ax
+ (d
* cos(theta
));
838 *y
= ay
+ (d
* sin(theta
));
840 *x
= ax
+ (d
* cos(theta
));
841 *y
= ay
- (d
* sin(theta
));
847 *x
= ax
- (d
* cos(theta
));
848 *y
= ay
+ (d
* sin(theta
));
850 *x
= ax
- (d
* cos(theta
));
851 *y
= ay
- (d
* sin(theta
));
858 /* moves vertex v d units in the direction of vertex p */
860 vertex_move_towards_point_values(GtsVertex
*v
, gdouble px
, gdouble py
, gdouble d
, gdouble
*x
, gdouble
*y
)
862 gdouble dx
= px
- GTS_POINT(v
)->x
;
863 gdouble dy
= py
- GTS_POINT(v
)->y
;
864 gdouble theta
= atan(fabs(dy
/dx
));
866 g_assert(finite(theta
));
871 *x
= GTS_POINT(v
)->x
+ (d
* cos(theta
));
872 *y
= GTS_POINT(v
)->y
+ (d
* sin(theta
));
874 *x
= GTS_POINT(v
)->x
+ (d
* cos(theta
));
875 *y
= GTS_POINT(v
)->y
- (d
* sin(theta
));
881 *x
= GTS_POINT(v
)->x
- (d
* cos(theta
));
882 *y
= GTS_POINT(v
)->y
+ (d
* sin(theta
));
884 *x
= GTS_POINT(v
)->x
- (d
* cos(theta
));
885 *y
= GTS_POINT(v
)->y
- (d
* sin(theta
));
892 /* moves vertex v d units in the direction of vertex p */
894 vertex_move_towards_vertex_values(GtsVertex
*v
, GtsVertex
*p
, gdouble d
, gdouble
*x
, gdouble
*y
)
896 gdouble dx
= GTS_POINT(p
)->x
- GTS_POINT(v
)->x
;
897 gdouble dy
= GTS_POINT(p
)->y
- GTS_POINT(v
)->y
;
898 gdouble theta
= atan(fabs(dy
/dx
));
900 g_assert(finite(theta
));
905 *x
= GTS_POINT(v
)->x
+ (d
* cos(theta
));
906 *y
= GTS_POINT(v
)->y
+ (d
* sin(theta
));
908 *x
= GTS_POINT(v
)->x
+ (d
* cos(theta
));
909 *y
= GTS_POINT(v
)->y
- (d
* sin(theta
));
915 *x
= GTS_POINT(v
)->x
- (d
* cos(theta
));
916 *y
= GTS_POINT(v
)->y
+ (d
* sin(theta
));
918 *x
= GTS_POINT(v
)->x
- (d
* cos(theta
));
919 *y
= GTS_POINT(v
)->y
- (d
* sin(theta
));
926 #define tv_on_layer(v,l) (l == TOPOROUTER_BBOX(TOPOROUTER_VERTEX(v)->boxes->data)->layer)
929 min_spacing(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
932 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
933 // toporouter_edge_t *e = v1->routingedge;
935 v1halfthick
= vertex_net_thickness(TOPOROUTER_VERTEX(v1
)) / 2.;
936 v2halfthick
= vertex_net_thickness(TOPOROUTER_VERTEX(v2
)) / 2.;
938 v1keepaway
= vertex_net_keepaway(TOPOROUTER_VERTEX(v1
));
939 v2keepaway
= vertex_net_keepaway(TOPOROUTER_VERTEX(v2
));
941 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
944 printf("v1halfthick = %f v2halfthick = %f v1keepaway = %f v2keepaway = %f ms = %f\n",
945 v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
);
951 // v1 is a vertex in the CDT, and v2 is a net... other way around?
953 min_vertex_net_spacing(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
956 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
958 v1halfthick
= vertex_net_thickness(TOPOROUTER_VERTEX(v1
)) / 2.;
959 v2halfthick
= cluster_thickness(vertex_bbox(v2
)->cluster
) / 2.;
961 v1keepaway
= vertex_net_keepaway(TOPOROUTER_VERTEX(v1
));
962 v2keepaway
= cluster_keepaway(vertex_bbox(v2
)->cluster
);
964 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
970 min_oproute_vertex_spacing(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v2
)
973 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
975 v1halfthick
= lookup_thickness(oproute
->style
) / 2.;
976 v2halfthick
= vertex_net_thickness(v2
) / 2.;
978 v1keepaway
= lookup_keepaway(oproute
->style
);
979 v2keepaway
= vertex_net_keepaway(v2
);
981 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
987 min_oproute_net_spacing(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v2
)
990 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
992 v1halfthick
= lookup_thickness(oproute
->style
) / 2.;
993 v2halfthick
= cluster_thickness(v2
->route
->src
) / 2.;
995 v1keepaway
= lookup_keepaway(oproute
->style
);
996 v2keepaway
= cluster_keepaway(v2
->route
->src
);
998 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
1004 min_net_net_spacing(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
1007 gdouble v1halfthick
, v2halfthick
, v1keepaway
, v2keepaway
, ms
;
1009 v1halfthick
= cluster_thickness(v1
->route
->src
) / 2.;
1010 v2halfthick
= cluster_thickness(v2
->route
->src
) / 2.;
1012 v1keepaway
= cluster_keepaway(v1
->route
->src
);
1013 v2keepaway
= cluster_keepaway(v2
->route
->src
);
1015 ms
= v1halfthick
+ v2halfthick
+ MAX(v1keepaway
, v2keepaway
);
1021 toporouter_draw_cluster(toporouter_t
*r
, drawing_context_t
*dc
, toporouter_cluster_t
*cluster
, gdouble red
, gdouble green
, gdouble blue
, guint layer
)
1023 #if TOPO_OUTPUT_ENABLED
1024 //GList *i = cluster->i;
1027 // toporouter_bbox_t *box = TOPOROUTER_BBOX(i->data);
1029 // if(box->point && vz(box->point) == layer) {
1030 // cairo_set_source_rgba(dc->cr, red, green, blue, 0.8f);
1031 // cairo_arc(dc->cr, vx(box->point) * dc->s + MARGIN, vy(box->point) * dc->s + MARGIN, 500. * dc->s, 0, 2 * M_PI);
1032 // cairo_fill(dc->cr);
1041 toporouter_draw_surface(toporouter_t
*r
, GtsSurface
*s
, char *filename
, int w
, int h
, int mode
, GList
*datas
, int layer
, GList
*candidatepoints
)
1043 #if TOPO_OUTPUT_ENABLED
1044 drawing_context_t
*dc
;
1046 toporouter_vertex_t
*tv
, *tv2
= NULL
;
1048 dc
= toporouter_output_init(w
, h
, filename
);
1052 gts_surface_foreach_edge(s
, toporouter_draw_edge
, dc
);
1053 gts_surface_foreach_vertex(s
, toporouter_draw_vertex
, dc
);
1057 GList
*j
= TOPOROUTER_ROUTE(i
->data
)->path
;
1060 tv
= TOPOROUTER_VERTEX(j
->data
);
1061 if(GTS_POINT(tv
)->z
== layer
) {
1063 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1.0f
, 0.0f
, 0.8f
);
1064 cairo_move_to(dc
->cr
,
1065 GTS_POINT(tv
)->x
* dc
->s
+ MARGIN
,
1066 GTS_POINT(tv
)->y
* dc
->s
+ MARGIN
);
1067 cairo_line_to(dc
->cr
,
1068 GTS_POINT(tv2
)->x
* dc
->s
+ MARGIN
,
1069 GTS_POINT(tv2
)->y
* dc
->s
+ MARGIN
);
1070 cairo_stroke(dc
->cr
);
1073 if(tv
->flags
& VERTEX_FLAG_RED
) {
1074 cairo_set_source_rgba(dc
->cr
, 1., 0., 0., 0.8f
);
1076 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1077 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1078 500. * dc
->s
, 0, 2 * M_PI
);
1081 }else if(tv
->flags
& VERTEX_FLAG_GREEN
) {
1082 cairo_set_source_rgba(dc
->cr
, 0., 1., 0., 0.8f
);
1084 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1085 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1086 500. * dc
->s
, 0, 2 * M_PI
);
1089 }else if(tv
->flags
& VERTEX_FLAG_BLUE
) {
1090 cairo_set_source_rgba(dc
->cr
, 0., 0., 1., 0.8f
);
1092 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1093 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1094 500. * dc
->s
, 0, 2 * M_PI
);
1100 cairo_set_source_rgba(dc
->cr
, 1., 1., 1., 0.8f
);
1102 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1103 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1104 500. * dc
->s
, 0, 2 * M_PI
);
1110 if(tv
->routingedge
&& !TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
)) {
1111 gdouble tempx
, tempy
, nms
, pms
;
1112 GList
*i
= g_list_find(edge_routing(tv
->routingedge
), tv
);
1113 toporouter_vertex_t
*nextv
, *prevv
;
1115 nextv
= edge_routing_next(tv
->routingedge
,i
);
1116 prevv
= edge_routing_prev(tv
->routingedge
,i
);
1118 nms
= min_spacing(tv
,nextv
);
1119 pms
= min_spacing(tv
,prevv
);
1121 g_assert(finite(nms
)); g_assert(finite(pms
));
1123 point_from_point_to_point(tv
, nextv
, nms
, &tempx
, &tempy
);
1125 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1.0f
, 1.0f
, 0.8f
);
1126 cairo_move_to(dc
->cr
, vx(tv
) * dc
->s
+ MARGIN
, vy(tv
) * dc
->s
+ MARGIN
);
1127 cairo_line_to(dc
->cr
, tempx
* dc
->s
+ MARGIN
, tempy
* dc
->s
+ MARGIN
);
1128 cairo_stroke(dc
->cr
);
1130 point_from_point_to_point(tv
, prevv
, pms
, &tempx
, &tempy
);
1132 cairo_move_to(dc
->cr
, vx(tv
) * dc
->s
+ MARGIN
, vy(tv
) * dc
->s
+ MARGIN
);
1133 cairo_line_to(dc
->cr
, tempx
* dc
->s
+ MARGIN
, tempy
* dc
->s
+ MARGIN
);
1134 cairo_stroke(dc
->cr
);
1150 toporouter_route_t
*routedata
= (toporouter_route_t
*) datas
->data
;
1154 toporouter_draw_cluster(r
, dc
, routedata
->src
, 1., 0., 0., layer
);
1155 toporouter_draw_cluster(r
, dc
, routedata
->dest
, 0., 0., 1., layer
);
1158 i
= routedata
->path
;
1160 tv
= TOPOROUTER_VERTEX(i
->data
);
1161 if(GTS_POINT(tv
)->z
== layer
) {
1163 cairo_set_source_rgba(dc
->cr
, 0.0f
, 1.0f
, 0.0f
, 0.8f
);
1164 cairo_move_to(dc
->cr
,
1165 GTS_POINT(tv
)->x
* dc
->s
+ MARGIN
,
1166 GTS_POINT(tv
)->y
* dc
->s
+ MARGIN
);
1167 cairo_line_to(dc
->cr
,
1168 GTS_POINT(tv2
)->x
* dc
->s
+ MARGIN
,
1169 GTS_POINT(tv2
)->y
* dc
->s
+ MARGIN
);
1170 cairo_stroke(dc
->cr
);
1178 if(routedata
->alltemppoints
) {
1180 i
= j
= g_hash_table_get_keys (routedata
->alltemppoints
);
1182 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
1184 if(GTS_POINT(tv
)->z
!= layer
) {
1188 if(tv
->flags
& VERTEX_FLAG_BLUE
) {
1189 cairo_set_source_rgba(dc
->cr
, 0., 0., 1., 0.8f
);
1191 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1192 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1193 500. * dc
->s
, 0, 2 * M_PI
);
1195 }else if(tv
->flags
& VERTEX_FLAG_RED
) {
1196 cairo_set_source_rgba(dc
->cr
, 1., 0., 0., 0.8f
);
1198 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1199 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1200 500. * dc
->s
, 0, 2 * M_PI
);
1203 }else if(tv
->flags
& VERTEX_FLAG_GREEN
) {
1204 cairo_set_source_rgba(dc
->cr
, 0., 1., 0., 0.8f
);
1206 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1207 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1208 500. * dc
->s
, 0, 2 * M_PI
);
1211 cairo_set_source_rgba(dc
->cr
, 1., 1., 1., 0.8f
);
1213 tv
->v
.p
.x
* dc
->s
+ MARGIN
,
1214 tv
->v
.p
.y
* dc
->s
+ MARGIN
,
1215 500. * dc
->s
, 0, 2 * M_PI
);
1222 datas
= datas
->next
;
1224 toporouter_output_close(dc
);
1230 toporouter_layer_free(toporouter_layer_t
*l
)
1232 g_list_free(l
->vertices
);
1233 g_list_free(l
->constraints
);
1243 for (group
= 0; group
< max_layer
; group
++) {
1244 if(PCB
->LayerGroups
.Number
[group
] > 0) count
++;
1251 toporouter_free(toporouter_t
*r
)
1253 struct timeval endtime
;
1257 for(i
=0;i
<groupcount();i
++) {
1258 toporouter_layer_free(&r
->layers
[i
]);
1262 gettimeofday(&endtime
, NULL
);
1264 secs
= (int)(endtime
.tv_sec
- r
->starttime
.tv_sec
);
1265 usecs
= (int)((endtime
.tv_usec
- r
->starttime
.tv_usec
) / 1000);
1272 Message(_("Elapsed time: %d.%02d seconds\n"), secs
, usecs
);
1279 * returns 1,0,-1 for counterclockwise, collinear or clockwise, respectively.
1282 wind(toporouter_spoint_t
*p1
, toporouter_spoint_t
*p2
, toporouter_spoint_t
*p3
)
1284 double rval
, dx1
, dx2
, dy1
, dy2
;
1285 dx1
= p2
->x
- p1
->x
; dy1
= p2
->y
- p1
->y
;
1286 dx2
= p3
->x
- p2
->x
; dy2
= p3
->y
- p2
->y
;
1287 rval
= (dx1
*dy2
)-(dy1
*dx2
);
1288 return (rval
> 0.0001) ? 1 : ((rval
< -0.0001) ? -1 : 0);
1292 * returns 1,0,-1 for counterclockwise, collinear or clockwise, respectively.
1295 wind_double(gdouble p1_x
, gdouble p1_y
, gdouble p2_x
, gdouble p2_y
, gdouble p3_x
, gdouble p3_y
)
1297 double rval
, dx1
, dx2
, dy1
, dy2
;
1298 dx1
= p2_x
- p1_x
; dy1
= p2_y
- p1_y
;
1299 dx2
= p3_x
- p2_x
; dy2
= p3_y
- p2_y
;
1300 rval
= (dx1
*dy2
)-(dy1
*dx2
);
1301 return (rval
> 0.0001) ? 1 : ((rval
< -0.0001) ? -1 : 0);
1305 print_toporouter_constraint(toporouter_constraint_t
*tc
)
1307 printf("%f,%f -> %f,%f ",
1308 tc
->c
.edge
.segment
.v1
->p
.x
,
1309 tc
->c
.edge
.segment
.v1
->p
.y
,
1310 tc
->c
.edge
.segment
.v2
->p
.x
,
1311 tc
->c
.edge
.segment
.v2
->p
.y
);
1315 print_toporouter_vertex(toporouter_vertex_t
*tv
)
1317 printf("%f,%f ", tv
->v
.p
.x
, tv
->v
.p
.y
);
1323 * Given vertex a, gradient m, and radius r:
1325 * Return vertices on line of a & m at r from a
1328 vertices_on_line(toporouter_spoint_t
*a
, gdouble m
, gdouble r
, toporouter_spoint_t
*b0
, toporouter_spoint_t
*b1
)
1333 if(m
== INFINITY
|| m
== -INFINITY
) {
1343 c
= a
->y
- (m
* a
->x
);
1345 temp
= sqrt( pow(r
, 2) / ( 1 + pow(m
, 2) ) );
1347 b0
->x
= a
->x
+ temp
;
1348 b1
->x
= a
->x
- temp
;
1350 b0
->y
= b0
->x
* m
+ c
;
1351 b1
->y
= b1
->x
* m
+ c
;
1357 * Given vertex a, gradient m, and radius r:
1359 * Return vertices on line of a & m at r from a
1362 coords_on_line(gdouble ax
, gdouble ay
, gdouble m
, gdouble r
, gdouble
*b0x
, gdouble
*b0y
, gdouble
*b1x
, gdouble
*b1y
)
1367 if(m
== INFINITY
|| m
== -INFINITY
) {
1379 temp
= sqrt( pow(r
, 2) / ( 1 + pow(m
, 2) ) );
1384 *b0y
= *b0x
* m
+ c
;
1385 *b1y
= *b1x
* m
+ c
;
1391 * Given vertex a, gradient m, and radius r:
1393 * Return vertices on line of a & m at r from a
1396 points_on_line(GtsPoint
*a
, gdouble m
, gdouble r
, GtsPoint
*b0
, GtsPoint
*b1
)
1401 if(m
== INFINITY
|| m
== -INFINITY
) {
1411 c
= a
->y
- (m
* a
->x
);
1413 temp
= sqrt( pow(r
, 2) / ( 1 + pow(m
, 2) ) );
1415 b0
->x
= a
->x
+ temp
;
1416 b1
->x
= a
->x
- temp
;
1418 b0
->y
= b0
->x
* m
+ c
;
1419 b1
->y
= b1
->x
* m
+ c
;
1424 * Returns gradient of segment given by a & b
1427 vertex_gradient(toporouter_spoint_t
*a
, toporouter_spoint_t
*b
)
1429 if(a
->x
== b
->x
) return INFINITY
;
1431 return ((b
->y
- a
->y
) / (b
->x
- a
->x
));
1435 * Returns gradient of segment given by (x0,y0) & (x1,y1)
1438 cartesian_gradient(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
)
1440 if(epsilon_equals(x0
,x1
)) return INFINITY
;
1442 return ((y1
- y0
) / (x1
- x0
));
1446 * Returns gradient of segment given by (x0,y0) & (x1,y1)
1449 point_gradient(GtsPoint
*a
, GtsPoint
*b
)
1451 return cartesian_gradient(a
->x
, a
->y
, b
->x
, b
->y
);
1455 segment_gradient(GtsSegment
*s
)
1457 return cartesian_gradient(
1458 GTS_POINT(s
->v1
)->x
,
1459 GTS_POINT(s
->v1
)->y
,
1460 GTS_POINT(s
->v2
)->x
,
1461 GTS_POINT(s
->v2
)->y
);
1465 * Returns gradient perpendicular to m
1468 perpendicular_gradient(gdouble m
)
1470 if(isinf(m
)) return 0.0f
;
1471 if(m
< EPSILON
&& m
> -EPSILON
) return INFINITY
;
1476 * Returns the distance between two vertices in the x-y plane
1479 vertices_plane_distance(toporouter_spoint_t
*a
, toporouter_spoint_t
*b
) {
1480 return sqrt( pow(a
->x
- b
->x
, 2) + pow(a
->y
- b
->y
, 2) );
1484 * Finds the point p distance r away from a on the line segment of a & b
1487 vertex_outside_segment(toporouter_spoint_t
*a
, toporouter_spoint_t
*b
, gdouble r
, toporouter_spoint_t
*p
)
1490 toporouter_spoint_t temp
[2];
1492 m
= vertex_gradient(a
,b
);
1494 vertices_on_line(a
, vertex_gradient(a
,b
), r
, &temp
[0], &temp
[1]);
1496 if(vertices_plane_distance(&temp
[0], b
) > vertices_plane_distance(&temp
[1], b
)) {
1506 /* proper intersection:
1507 * AB and CD must share a point interior to both segments.
1508 * returns TRUE if AB properly intersects CD.
1511 coord_intersect_prop(gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
, gdouble cx
, gdouble cy
, gdouble dx
, gdouble dy
)
1513 gint wind_abc
= coord_wind(ax
, ay
, bx
, by
, cx
, cy
);
1514 gint wind_abd
= coord_wind(ax
, ay
, bx
, by
, dx
, dy
);
1515 gint wind_cda
= coord_wind(cx
, cy
, dx
, dy
, ax
, ay
);
1516 gint wind_cdb
= coord_wind(cx
, cy
, dx
, dy
, bx
, by
);
1518 if( !wind_abc
|| !wind_abd
|| !wind_cda
|| !wind_cdb
) return 0;
1520 return ( wind_abc
^ wind_abd
) && ( wind_cda
^ wind_cdb
);
1523 /* proper intersection:
1524 * AB and CD must share a point interior to both segments.
1525 * returns TRUE if AB properly intersects CD.
1528 point_intersect_prop(GtsPoint
*a
, GtsPoint
*b
, GtsPoint
*c
, GtsPoint
*d
)
1531 if( point_wind(a
, b
, c
) == 0 ||
1532 point_wind(a
, b
, d
) == 0 ||
1533 point_wind(c
, d
, a
) == 0 ||
1534 point_wind(c
, d
, b
) == 0 ) return 0;
1536 return ( point_wind(a
, b
, c
) ^ point_wind(a
, b
, d
) ) &&
1537 ( point_wind(c
, d
, a
) ^ point_wind(c
, d
, b
) );
1541 vertex_intersect_prop(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
, GtsVertex
*d
)
1543 return point_intersect_prop(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
), GTS_POINT(d
));
1547 tvertex_intersect_prop(toporouter_vertex_t
*a
, toporouter_vertex_t
*b
, toporouter_vertex_t
*c
, toporouter_vertex_t
*d
)
1549 return point_intersect_prop(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
), GTS_POINT(d
));
1553 tvertex_intersect(toporouter_vertex_t *a, toporouter_vertex_t *b, toporouter_vertex_t *c, toporouter_vertex_t *d)
1555 if( !point_wind(GTS_POINT(a), GTS_POINT(d), GTS_POINT(b)) || !point_wind(GTS_POINT(a), GTS_POINT(c), GTS_POINT(b)) ) return 1;
1558 ( point_wind(GTS_POINT(a), GTS_POINT(b), GTS_POINT(c)) ^ point_wind(GTS_POINT(a), GTS_POINT(b), GTS_POINT(d)) ) &&
1559 ( point_wind(GTS_POINT(c), GTS_POINT(d), GTS_POINT(a)) ^ point_wind(GTS_POINT(c), GTS_POINT(d), GTS_POINT(b)) );
1563 /* intersection vertex:
1564 * AB and CD must share a point interior to both segments.
1565 * returns vertex at intersection of AB and CD.
1568 vertex_intersect(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
, GtsVertex
*d
)
1570 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1572 gdouble ua_top
, ua_bot
, ua
, rx
, ry
;
1574 /* TODO: this could be done more efficiently without duplicating computation */
1575 if(!vertex_intersect_prop(a
, b
, c
, d
)) return NULL
;
1577 ua_top
= ((d
->p
.x
- c
->p
.x
) * (a
->p
.y
- c
->p
.y
)) -
1578 ((d
->p
.y
- c
->p
.y
) * (a
->p
.x
- c
->p
.x
));
1579 ua_bot
= ((d
->p
.y
- c
->p
.y
) * (b
->p
.x
- a
->p
.x
)) -
1580 ((d
->p
.x
- c
->p
.x
) * (b
->p
.y
- a
->p
.y
));
1581 ua
= ua_top
/ ua_bot
;
1582 rx
= a
->p
.x
+ (ua
* (b
->p
.x
- a
->p
.x
));
1583 ry
= a
->p
.y
+ (ua
* (b
->p
.y
- a
->p
.y
));
1585 rval
= gts_vertex_new (vertex_class
, rx
, ry
, 0.0f
);
1590 /* intersection vertex:
1591 * AB and CD must share a point interior to both segments.
1592 * returns vertex at intersection of AB and CD.
1595 coord_intersect(gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
, gdouble cx
, gdouble cy
, gdouble dx
, gdouble dy
, gdouble
*rx
, gdouble
*ry
)
1597 gdouble ua_top
, ua_bot
, ua
;
1599 ua_top
= ((dx
- cx
) * (ay
- cy
)) - ((dy
- cy
) * (ax
- cx
));
1600 ua_bot
= ((dy
- cy
) * (bx
- ax
)) - ((dx
- cx
) * (by
- ay
));
1601 ua
= ua_top
/ ua_bot
;
1602 *rx
= ax
+ (ua
* (bx
- ax
));
1603 *ry
= ay
+ (ua
* (by
- ay
));
1609 * returns true if c is between a and b
1612 point_between(GtsPoint
*a
, GtsPoint
*b
, GtsPoint
*c
)
1614 if( point_wind(a
, b
, c
) != 0 ) return 0;
1616 if( a
->x
!= b
->x
) {
1617 return ((a
->x
<= c
->x
) &&
1622 return ((a
->y
<= c
->y
) &&
1629 vertex_between(GtsVertex
*a
, GtsVertex
*b
, GtsVertex
*c
)
1631 return point_between(GTS_POINT(a
), GTS_POINT(b
), GTS_POINT(c
));
1635 delaunay_create_from_vertices(GList
*vertices
, GtsSurface
**surface
, GtsTriangle
**t
)
1637 GList
*i
= vertices
;
1638 GtsVertex
*v1
, *v2
, *v3
;
1639 GSList
*vertices_slist
= NULL
;
1642 vertices_slist
= g_slist_prepend(vertices_slist
, i
->data
);
1646 // TODO: just work this out from the board outline
1647 *t
= gts_triangle_enclosing (gts_triangle_class (), vertices_slist
, 100000.0f
);
1648 gts_triangle_vertices (*t
, &v1
, &v2
, &v3
);
1650 *surface
= gts_surface_new (gts_surface_class (), gts_face_class (),
1651 GTS_EDGE_CLASS(toporouter_edge_class ()), GTS_VERTEX_CLASS(toporouter_vertex_class ()) );
1653 gts_surface_add_face (*surface
, gts_face_new (gts_face_class (), (*t
)->e1
, (*t
)->e2
, (*t
)->e3
));
1657 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(gts_delaunay_add_vertex (*surface
, i
->data
, NULL
));
1660 printf("ERROR: vertex could not be added to CDT ");
1667 gts_allow_floating_vertices
= TRUE
;
1668 gts_object_destroy (GTS_OBJECT (v1
));
1669 gts_object_destroy (GTS_OBJECT (v2
));
1670 gts_object_destroy (GTS_OBJECT (v3
));
1671 gts_allow_floating_vertices
= FALSE
;
1673 g_slist_free(vertices_slist
);
1678 list_to_slist(GList
*i
)
1680 GSList
*rval
= NULL
;
1682 rval
= g_slist_prepend(rval
, i
->data
);
1689 toporouter_bbox_create_from_points(int layer
, GList
*vertices
, toporouter_term_t type
, gpointer data
)
1691 toporouter_bbox_t
*bbox
;
1692 GSList
*vertices_slist
= list_to_slist(vertices
);
1694 // delaunay_create_from_vertices(vertices, &s, &t);
1695 bbox
= TOPOROUTER_BBOX( gts_bbox_points(GTS_BBOX_CLASS(toporouter_bbox_class()), vertices_slist
) );
1699 bbox
->surface
= NULL
;
1700 bbox
->enclosing
= NULL
;
1702 bbox
->layer
= layer
;
1705 bbox
->realpoint
= NULL
;
1707 g_slist_free(vertices_slist
);
1712 toporouter_bbox_create(int layer
, GList
*vertices
, toporouter_term_t type
, gpointer data
)
1714 toporouter_bbox_t
*bbox
;
1718 delaunay_create_from_vertices(vertices
, &s
, &t
);
1719 bbox
= TOPOROUTER_BBOX( gts_bbox_surface(GTS_BBOX_CLASS(toporouter_bbox_class()), s
) );
1724 bbox
->enclosing
= t
;
1726 bbox
->layer
= layer
;
1732 insert_vertex(toporouter_t
*r
, toporouter_layer_t
*l
, gdouble x
, gdouble y
, toporouter_bbox_t
*box
)
1734 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1741 if(v
->p
.x
== x
&& v
->p
.y
== y
) {
1742 TOPOROUTER_VERTEX(v
)->bbox
= box
;
1748 v
= gts_vertex_new (vertex_class
, x
, y
, l
- r
->layers
);
1749 TOPOROUTER_VERTEX(v
)->bbox
= box
;
1750 l
->vertices
= g_list_prepend(l
->vertices
, v
);
1756 insert_constraint_edge(toporouter_t
*r
, toporouter_layer_t
*l
, gdouble x1
, gdouble y1
, guint flags1
, gdouble x2
, gdouble y2
, guint flags2
, toporouter_bbox_t
*box
)
1758 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1759 GtsEdgeClass
*edge_class
= GTS_EDGE_CLASS (toporouter_constraint_class ());
1767 /* insert or find points */
1772 if(v
->p
.x
== x1
&& v
->p
.y
== y1
)
1774 if(v
->p
.x
== x2
&& v
->p
.y
== y2
)
1780 p
[0] = gts_vertex_new (vertex_class
, x1
, y1
, l
- r
->layers
);
1781 TOPOROUTER_VERTEX(p
[0])->bbox
= box
;
1782 l
->vertices
= g_list_prepend(l
->vertices
, p
[0]);
1785 p
[1] = gts_vertex_new (vertex_class
, x2
, y2
, l
- r
->layers
);
1786 TOPOROUTER_VERTEX(p
[1])->bbox
= box
;
1787 l
->vertices
= g_list_prepend(l
->vertices
, p
[1]);
1790 TOPOROUTER_VERTEX(p
[0])->flags
= flags1
;
1791 TOPOROUTER_VERTEX(p
[1])->flags
= flags2
;
1793 e
= gts_edge_new (edge_class
, p
[0], p
[1]);
1794 TOPOROUTER_CONSTRAINT(e
)->box
= box
;
1795 l
->constraints
= g_list_prepend (l
->constraints
, e
);
1796 // return insert_constraint_edge_rec(r, l, p, box);
1797 return g_list_prepend(NULL
, e
);
1802 insert_constraints_from_list(toporouter_t
*r
, toporouter_layer_t
*l
, GList
*vlist
, toporouter_bbox_t
*box
)
1805 toporouter_vertex_t
*pv
= NULL
, *v
;
1808 v
= TOPOROUTER_VERTEX(i
->data
);
1812 g_list_concat(box
->constraints
, insert_constraint_edge(r
, l
, vx(v
), vy(v
), v
->flags
, vx(pv
), vy(pv
), pv
->flags
, box
));
1819 v
= TOPOROUTER_VERTEX(vlist
->data
);
1821 g_list_concat(box
->constraints
, insert_constraint_edge(r
, l
, vx(v
), vy(v
), v
->flags
, vx(pv
), vy(pv
), pv
->flags
, box
));
1826 insert_centre_point(toporouter_t
*r
, toporouter_layer_t
*l
, gdouble x
, gdouble y
)
1829 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1833 GtsPoint
*p
= GTS_POINT(i
->data
);
1834 if(p
->x
== x
&& p
->y
== y
)
1839 l
->vertices
= g_list_prepend(l
->vertices
, gts_vertex_new(vertex_class
, x
, y
, 0.0f
));
1843 midpoint(GtsPoint
*a
, GtsPoint
*b
)
1845 return gts_point_new(gts_point_class(), (a
->x
+ b
->x
) / 2., (a
->y
+ b
->y
) / 2., 0.);
1849 pad_rad(PadType
*pad
)
1851 return (lookup_thickness(pad
->Name
) / 2.) + lookup_keepaway(pad
->Name
);
1855 pin_rad(PinType
*pin
)
1857 return (lookup_thickness(pin
->Name
) / 2.) + lookup_keepaway(pin
->Name
);
1861 rect_with_attachments(gdouble rad
,
1862 gdouble x0
, gdouble y0
,
1863 gdouble x1
, gdouble y1
,
1864 gdouble x2
, gdouble y2
,
1865 gdouble x3
, gdouble y3
,
1868 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1869 GList
*r
= NULL
, *rr
= NULL
, *i
;
1870 toporouter_vertex_t
*curpoint
, *temppoint
;
1873 curpoint
= TOPOROUTER_VERTEX(gts_vertex_new (vertex_class
, x0
, y0
, z
));
1875 r
= g_list_prepend(NULL
, curpoint
);
1876 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x1
, y1
, z
));
1877 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x2
, y2
, z
));
1878 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x3
, y3
, z
));
1882 temppoint
= TOPOROUTER_VERTEX(i
->data
);
1883 rr
= g_list_prepend(rr
, curpoint
);
1885 curpoint
= temppoint
;
1894 #define VERTEX_CENTRE(x) TOPOROUTER_VERTEX( vertex_bbox(x)->point )
1897 * Read pad data from layer into toporouter_layer_t struct
1899 * Inserts points and constraints into GLists
1902 read_pads(toporouter_t
*r
, toporouter_layer_t
*l
, guint layer
)
1904 toporouter_spoint_t p
[2], rv
[5];
1905 gdouble x
[2], y
[2], t
, m
;
1906 GList
*objectconstraints
;
1908 GList
*vlist
= NULL
;
1909 toporouter_bbox_t
*bbox
= NULL
;
1911 guint front
= GetLayerGroupNumberByNumber (max_layer
+ COMPONENT_LAYER
);
1912 guint back
= GetLayerGroupNumberByNumber (max_layer
+ SOLDER_LAYER
);
1914 // printf("read_pads: front = %d back = %d layer = %d\n",
1915 // front, back, layer);
1917 /* If its not the top or bottom layer, there are no pads to read */
1918 if(l
- r
->layers
!= front
&& l
- r
->layers
!= back
) return 0;
1920 ELEMENT_LOOP(PCB
->Data
);
1924 if( (l
- r
->layers
== back
&& TEST_FLAG(ONSOLDERFLAG
, pad
)) ||
1925 (l
- r
->layers
== front
&& !TEST_FLAG(ONSOLDERFLAG
, pad
)) ) {
1928 objectconstraints
= NULL
;
1929 t
= (gdouble
)pad
->Thickness
/ 2.0f
;
1930 x
[0] = pad
->Point1
.X
;
1931 x
[1] = pad
->Point2
.X
;
1932 y
[0] = pad
->Point1
.Y
;
1933 y
[1] = pad
->Point2
.Y
;
1936 if(TEST_FLAG(SQUAREFLAG
, pad
)) {
1937 /* Square or oblong pad. Four points and four constraint edges are
1940 if(x
[0] == x
[1] && y
[0] == y
[1]) {
1943 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, x[0]-t, y[0]-t, 0.));
1944 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]-t, y[0]+t, 0.));
1945 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]+t, y[0]+t, 0.));
1946 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]+t, y[0]-t, 0.));
1947 vlist
= rect_with_attachments(pad_rad(pad
),
1953 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
1954 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1955 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1958 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, x[0], y[0], 0.) );
1959 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
[0], y
[0], bbox
) );
1960 g_assert(TOPOROUTER_VERTEX(bbox
->point
)->bbox
== bbox
);
1962 /* Pad is diagonal oblong or othogonal oblong */
1964 m
= cartesian_gradient(x
[0], y
[0], x
[1], y
[1]);
1966 p
[0].x
= x
[0]; p
[0].y
= y
[0];
1967 p
[1].x
= x
[1]; p
[1].y
= y
[1];
1969 vertex_outside_segment(&p
[0], &p
[1], t
, &rv
[0]);
1970 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[1], &rv
[2]);
1972 vertex_outside_segment(&p
[1], &p
[0], t
, &rv
[0]);
1973 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[3], &rv
[4]);
1975 if(wind(&rv
[1], &rv
[2], &rv
[3]) != wind(&rv
[2], &rv
[3], &rv
[4])) {
1976 rv
[0].x
= rv
[3].x
; rv
[0].y
= rv
[3].y
;
1977 rv
[3].x
= rv
[4].x
; rv
[3].y
= rv
[4].y
;
1978 rv
[4].x
= rv
[0].x
; rv
[4].y
= rv
[0].y
;
1981 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, rv[1].x, rv[1].y, 0.));
1982 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[2].x, rv[2].y, 0.));
1983 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[3].x, rv[3].y, 0.));
1984 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[4].x, rv[4].y, 0.));
1985 vlist
= rect_with_attachments(pad_rad(pad
),
1991 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
1992 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1993 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1996 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., 0.) );
1997 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, (x
[0] + x
[1]) / 2., (y
[0] + y
[1]) / 2., bbox
) );
1998 g_assert(TOPOROUTER_VERTEX(bbox
->point
)->bbox
== bbox
);
2003 /* Either round pad or pad with curved edges */
2005 if(x
[0] == x
[1] && y
[0] == y
[1]) {
2008 /* bounding box same as square pad */
2009 vlist
= rect_with_attachments(pad_rad(pad
),
2015 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
2016 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2019 //bbox->point = GTS_POINT( insert_vertex(r, l, x[0], y[0], bbox) );
2020 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
[0], y
[0], bbox
) );
2023 /* Two points and one constraint edge */
2025 /* the rest is just for bounding box */
2026 m
= cartesian_gradient(x
[0], y
[0], x
[1], y
[1]);
2028 p
[0].x
= x
[0]; p
[0].y
= y
[0];
2029 p
[1].x
= x
[1]; p
[1].y
= y
[1];
2031 vertex_outside_segment(&p
[0], &p
[1], t
, &rv
[0]);
2032 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[1], &rv
[2]);
2034 vertex_outside_segment(&p
[1], &p
[0], t
, &rv
[0]);
2035 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[3], &rv
[4]);
2037 if(wind(&rv
[1], &rv
[2], &rv
[3]) != wind(&rv
[2], &rv
[3], &rv
[4])) {
2038 rv
[0].x
= rv
[3].x
; rv
[0].y
= rv
[3].y
;
2039 rv
[3].x
= rv
[4].x
; rv
[3].y
= rv
[4].y
;
2040 rv
[4].x
= rv
[0].x
; rv
[4].y
= rv
[0].y
;
2043 vlist
= rect_with_attachments(pad_rad(pad
),
2049 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
2050 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2051 insert_constraints_from_list(r
, l
, vlist
, bbox
);
2054 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., 0.) );
2055 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, (x
[0] + x
[1]) / 2., (y
[0] + y
[1]) / 2., bbox
) );
2057 //bbox->constraints = g_list_concat(bbox->constraints, insert_constraint_edge(r, l, x[0], y[0], x[1], y[1], bbox));
2074 * Read points data (all layers) into GList
2076 * Inserts pin and via points
2079 read_points(toporouter_t
*r
, toporouter_layer_t
*l
, int layer
)
2083 GList
*vlist
= NULL
;
2084 toporouter_bbox_t
*bbox
= NULL
;
2086 ELEMENT_LOOP(PCB
->Data
);
2091 t
= (gdouble
)pin
->Thickness
/ 2.0f
;
2095 if(TEST_FLAG (SQUAREFLAG
, pin
)) {
2097 vlist
= rect_with_attachments(pin_rad(pin
),
2103 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PIN
, pin
);
2104 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2105 insert_constraints_from_list(r
, l
, vlist
, bbox
);
2107 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
2109 }else if(TEST_FLAG(OCTAGONFLAG
, pin
)){
2110 /* TODO: Handle octagon pins */
2111 fprintf(stderr
, "No support for octagon pins yet\n");
2113 vlist
= rect_with_attachments(pin_rad(pin
),
2119 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PIN
, pin
);
2120 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2122 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
2129 VIA_LOOP(PCB
->Data
);
2132 t
= (gdouble
)via
->Thickness
/ 2.0f
;
2136 if(TEST_FLAG (SQUAREFLAG
, via
)) {
2138 vlist
= rect_with_attachments(pin_rad((PinType
*)via
),
2144 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, VIA
, via
);
2145 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2146 insert_constraints_from_list(r
, l
, vlist
, bbox
);
2148 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
2150 }else if(TEST_FLAG(OCTAGONFLAG
, via
)){
2151 /* TODO: Handle octagon vias */
2152 fprintf(stderr
, "No support for octagon vias yet\n");
2155 vlist
= rect_with_attachments(pin_rad((PinType
*)via
),
2161 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, VIA
, via
);
2162 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2165 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
2174 * Read line data from layer into toporouter_layer_t struct
2176 * Inserts points and constraints into GLists
2179 read_lines(toporouter_t
*r
, toporouter_layer_t
*l
, LayerType
*layer
, int ln
)
2181 gdouble xs
[2], ys
[2];
2183 GList
*vlist
= NULL
;
2184 toporouter_bbox_t
*bbox
= NULL
;
2186 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
2190 xs
[0] = line
->Point1
.X
;
2191 xs
[1] = line
->Point2
.X
;
2192 ys
[0] = line
->Point1
.Y
;
2193 ys
[1] = line
->Point2
.Y
;
2194 if(!(xs
[0] == xs
[1] && ys
[0] == ys
[1])) {
2195 vlist
= g_list_prepend(NULL
, gts_vertex_new (vertex_class
, xs
[0], ys
[0], l
- r
->layers
));
2196 vlist
= g_list_prepend(vlist
, gts_vertex_new (vertex_class
, xs
[1], ys
[1], l
- r
->layers
));
2197 bbox
= toporouter_bbox_create_from_points(GetLayerGroupNumberByNumber(ln
), vlist
, LINE
, line
);
2198 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2201 bbox
->constraints
= g_list_concat(bbox
->constraints
, insert_constraint_edge(r
, l
, xs
[0], ys
[0], 0, xs
[1], ys
[1], 0, bbox
));
2212 create_board_edge(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, gdouble max
, gint layer
, GList
**vlist
)
2214 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
2215 gdouble d
= sqrt(pow(x0
-x1
,2) + pow(y0
-y1
,2));
2216 guint n
= d
/ max
, count
= 1;
2217 gdouble inc
= n
? d
/ n
: d
;
2218 gdouble x
= x0
, y
= y0
;
2220 *vlist
= g_list_prepend(*vlist
, gts_vertex_new (vertex_class
, x0
, y0
, layer
));
2223 coord_move_towards_coord_values(x0
, y0
, x1
, y1
, inc
, &x
, &y
);
2224 *vlist
= g_list_prepend(*vlist
, gts_vertex_new (vertex_class
, x
, y
, layer
));
2234 read_board_constraints(toporouter_t
*r
, toporouter_layer_t
*l
, int layer
)
2236 // GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
2237 GList
*vlist
= NULL
;
2238 toporouter_bbox_t
*bbox
= NULL
;
2240 /* Add points for corners of board, and constrain those edges */
2241 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, 0., 0., layer));
2242 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, PCB->MaxWidth, 0., layer));
2243 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, PCB->MaxWidth, PCB->MaxHeight, layer));
2244 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, 0., PCB->MaxHeight, layer));
2246 create_board_edge(0., 0., PCB
->MaxWidth
, 0., 10000., layer
, &vlist
);
2247 create_board_edge(PCB
->MaxWidth
, 0., PCB
->MaxWidth
, PCB
->MaxHeight
, 10000., layer
, &vlist
);
2248 create_board_edge(PCB
->MaxWidth
, PCB
->MaxHeight
, 0., PCB
->MaxHeight
, 10000., layer
, &vlist
);
2249 create_board_edge(0., PCB
->MaxHeight
, 0., 0., 10000., layer
, &vlist
);
2251 bbox
= toporouter_bbox_create(layer
, vlist
, BOARD
, NULL
);
2252 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2253 insert_constraints_from_list(r
, l
, vlist
, bbox
);
2260 triangle_cost(GtsTriangle
*t
, gpointer
*data
){
2262 gdouble
*min_quality
= data
[0];
2263 gdouble
*max_area
= data
[1];
2264 gdouble quality
= gts_triangle_quality(t
);
2265 gdouble area
= gts_triangle_area(t
);
2267 if (quality
< *min_quality
|| area
> *max_area
)
2276 build_cdt(toporouter_t
*r
, toporouter_layer_t
*l
)
2278 /* TODO: generalize into surface *cdt_create(vertices, constraints) */
2283 GtsVertex
*v1
, *v2
, *v3
;
2284 GSList
*vertices_slist
= list_to_slist(l
->vertices
);
2287 t
= gts_triangle_enclosing (gts_triangle_class (), vertices_slist
, 1000.0f
);
2288 gts_triangle_vertices (t
, &v1
, &v2
, &v3
);
2290 g_slist_free(vertices_slist
);
2292 l
->surface
= gts_surface_new (gts_surface_class (), gts_face_class (),
2293 GTS_EDGE_CLASS(toporouter_edge_class ()), GTS_VERTEX_CLASS(toporouter_vertex_class ()) );
2295 gts_surface_add_face (l
->surface
, gts_face_new (gts_face_class (), t
->e1
, t
->e2
, t
->e3
));
2300 //if(r->flags & TOPOROUTER_FLAG_DEBUG_CDTS)
2301 // fprintf(stderr, "\tadding vertex %f,%f\n", v->p.x, v->p.y);
2302 g_assert (gts_delaunay_add_vertex (l
->surface
, i
->data
, NULL
) == NULL
);
2306 // fprintf(stderr, "ADDED VERTICES\n");
2308 if((debugface = gts_delaunay_check(l->surface))) {
2309 fprintf(stderr, "WARNING: Delaunay check failed\n");
2310 fprintf(stderr, "\tViolating triangle:\n");
2311 fprintf(stderr, "\t%f,%f %f,%f\n",
2312 debugface->triangle.e1->segment.v1->p.x,
2313 debugface->triangle.e1->segment.v1->p.y,
2314 debugface->triangle.e1->segment.v2->p.x,
2315 debugface->triangle.e1->segment.v2->p.y
2317 fprintf(stderr, "\t%f,%f %f,%f\n",
2318 debugface->triangle.e2->segment.v1->p.x,
2319 debugface->triangle.e2->segment.v1->p.y,
2320 debugface->triangle.e2->segment.v2->p.x,
2321 debugface->triangle.e2->segment.v2->p.y
2323 fprintf(stderr, "\t%f,%f %f,%f\n",
2324 debugface->triangle.e3->segment.v1->p.x,
2325 debugface->triangle.e3->segment.v1->p.y,
2326 debugface->triangle.e3->segment.v2->p.x,
2327 debugface->triangle.e3->segment.v2->p.y
2329 if((f=fopen("fail.oogl", "w")) == NULL) {
2330 fprintf(stderr, "Error opening file fail.oogl for output\n");
2332 gts_surface_write_oogl(l->surface, f);
2335 toporouter_draw_surface(l->surface, "debug.png", 4096, 4096);
2342 //if(r->flags & TOPOROUTER_FLAG_DEBUG_CDTS)
2343 /* fprintf(r->debug, "edge p1=%f,%f p2=%f,%f\n",
2344 temp->segment.v1->p.x,
2345 temp->segment.v1->p.y,
2346 temp->segment.v2->p.x,
2347 temp->segment.v2->p.y);
2349 g_assert (gts_delaunay_add_constraint (l
->surface
, i
->data
) == NULL
);
2352 // fprintf(stderr, "ADDED CONSTRAINTS\n");
2353 gts_allow_floating_vertices
= TRUE
;
2354 gts_object_destroy (GTS_OBJECT (v1
));
2355 gts_object_destroy (GTS_OBJECT (v2
));
2356 gts_object_destroy (GTS_OBJECT (v3
));
2357 gts_allow_floating_vertices
= FALSE
;
2361 gdouble quality = 0.50, area = G_MAXDOUBLE;
2362 guint num = gts_delaunay_conform(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL);
2367 num = gts_delaunay_refine(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL, (GtsKeyFunc) triangle_cost, data);
2372 gts_surface_print_stats(l
->surface
, stderr
);
2377 visited_cmp(gconstpointer a
, gconstpointer b
)
2385 coord_xangle(gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
)
2387 gdouble dx
, dy
, theta
;
2394 } else theta
= atan(dy
/dx
);
2397 if(bx
< ax
) theta
= M_PI
- theta
;
2399 if(bx
< ax
) theta
+= M_PI
;
2400 else theta
= (2 * M_PI
) - theta
;
2407 point_xangle(GtsPoint
*a
, GtsPoint
*b
)
2409 gdouble dx
, dy
, theta
;
2411 dx
= fabs(a
->x
- b
->x
);
2412 dy
= fabs(a
->y
- b
->y
);
2416 } else theta
= atan(dy
/dx
);
2419 if(b
->x
< a
->x
) theta
= M_PI
- theta
;
2421 if(b
->x
< a
->x
) theta
+= M_PI
;
2422 else theta
= (2 * M_PI
) - theta
;
2430 cluster_vertices(toporouter_t
*r
, toporouter_cluster_t
*c
)
2436 FOREACH_CLUSTER(c
->netlist
->clusters
) {
2437 if((r
->flags
& TOPOROUTER_FLAG_AFTERRUBIX
&& cluster
->c
== c
->c
) || (!(r
->flags
& TOPOROUTER_FLAG_AFTERRUBIX
) && cluster
== c
)) {
2438 FOREACH_BBOX(cluster
->boxes
) {
2439 if(box
->type
== LINE
) {
2440 g_assert(box
->constraints
->data
);
2441 rval
= g_list_prepend(rval
, tedge_v1(box
->constraints
->data
));
2442 rval
= g_list_prepend(rval
, tedge_v2(box
->constraints
->data
));
2443 }else if(box
->point
) {
2444 rval
= g_list_prepend(rval
, TOPOROUTER_VERTEX(box
->point
));
2445 //g_assert(vertex_bbox(TOPOROUTER_VERTEX(box->point)) == box);
2447 printf("WARNING: cluster_vertices: unhandled bbox type\n");
2461 print_cluster(toporouter_cluster_t
*c
)
2465 printf("[CLUSTER (NULL)]\n");
2469 printf("CLUSTER %d: NETLIST = %s STYLE = %s\n", c
->c
, c
->netlist
->netlist
, c
->netlist
->style
);
2471 FOREACH_BBOX(c
->boxes
) {
2477 toporouter_cluster_t
*
2478 cluster_create(toporouter_t
*r
, toporouter_netlist_t
*netlist
)
2480 toporouter_cluster_t
*c
= malloc(sizeof(toporouter_cluster_t
));
2482 c
->c
= c
->pc
= netlist
->clusters
->len
;
2483 g_ptr_array_add(netlist
->clusters
, c
);
2484 c
->netlist
= netlist
;
2485 c
->boxes
= g_ptr_array_new();
2491 toporouter_bbox_locate(toporouter_t
*r
, toporouter_term_t type
, void *data
, gdouble x
, gdouble y
, guint layergroup
)
2493 GtsPoint
*p
= gts_point_new(gts_point_class(), x
, y
, layergroup
);
2494 GSList
*boxes
= gts_bb_tree_stabbed(r
->bboxtree
, p
), *i
= boxes
;
2496 gts_object_destroy(GTS_OBJECT(p
));
2499 toporouter_bbox_t
*box
= TOPOROUTER_BBOX(i
->data
);
2501 if(box
->type
== type
&& box
->data
== data
) {
2502 g_slist_free(boxes
);
2509 g_slist_free(boxes
);
2514 cluster_join_bbox(toporouter_cluster_t
*cluster
, toporouter_bbox_t
*box
)
2517 g_ptr_array_add(cluster
->boxes
, box
);
2518 box
->cluster
= cluster
;
2522 toporouter_netlist_t
*
2523 netlist_create(toporouter_t
*r
, char *netlist
, char *style
)
2525 toporouter_netlist_t
*nl
= malloc(sizeof(toporouter_netlist_t
));
2526 nl
->netlist
= netlist
;
2528 nl
->clusters
= g_ptr_array_new();
2529 nl
->routes
= g_ptr_array_new();
2532 g_ptr_array_add(r
->netlists
, nl
);
2537 import_clusters(toporouter_t
*r
)
2539 NetListListType nets
;
2540 ResetFoundPinsViasAndPads (False
);
2541 ResetFoundLinesAndPolygons (False
);
2542 nets
= CollectSubnets(False
);
2543 NETLIST_LOOP(&nets
);
2545 if(netlist
->NetN
> 0) {
2546 toporouter_netlist_t
*nl
= netlist_create(r
, netlist
->Net
->Connection
->menu
->Name
, netlist
->Net
->Connection
->menu
->Style
);
2551 toporouter_cluster_t
*cluster
= cluster_create(r
, nl
);
2552 #ifdef DEBUG_MERGING
2555 CONNECTION_LOOP (net
);
2558 if(connection
->type
== LINE_TYPE
) {
2559 LineType
*line
= (LineType
*) connection
->ptr2
;
2560 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, LINE
, line
, connection
->X
, connection
->Y
, connection
->group
);
2561 cluster_join_bbox(cluster
, box
);
2563 #ifdef DEBUG_MERGING
2564 printf("\tLINE %d,%d\n", connection
->X
, connection
->Y
);
2566 }else if(connection
->type
== PAD_TYPE
) {
2567 PadType
*pad
= (PadType
*) connection
->ptr2
;
2568 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, PAD
, pad
, connection
->X
, connection
->Y
, connection
->group
);
2569 cluster_join_bbox(cluster
, box
);
2571 #ifdef DEBUG_MERGING
2572 printf("\tPAD %d,%d\n", connection
->X
, connection
->Y
);
2574 }else if(connection
->type
== PIN_TYPE
) {
2576 for(guint m
=0;m
<groupcount();m
++) {
2577 PinType
*pin
= (PinType
*) connection
->ptr2
;
2578 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, PIN
, pin
, connection
->X
, connection
->Y
, m
);
2579 cluster_join_bbox(cluster
, box
);
2582 #ifdef DEBUG_MERGING
2583 printf("\tPIN %d,%d\n", connection
->X
, connection
->Y
);
2585 }else if(connection
->type
== VIA_TYPE
) {
2587 for(guint m
=0;m
<groupcount();m
++) {
2588 PinType
*pin
= (PinType
*) connection
->ptr2
;
2589 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, VIA
, pin
, connection
->X
, connection
->Y
, m
);
2590 cluster_join_bbox(cluster
, box
);
2593 #ifdef DEBUG_MERGING
2594 printf("\tVIA %d,%d\n", connection
->X
, connection
->Y
);
2596 }else if(connection
->type
== POLYGON_TYPE
) {
2597 PolygonType
*polygon
= (PolygonType
*) connection
->ptr2
;
2598 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, POLYGON
, polygon
, connection
->X
, connection
->Y
, connection
->group
);
2599 cluster_join_bbox(cluster
, box
);
2601 #ifdef DEBUG_MERGING
2602 printf("\tPOLYGON %d,%d\n", connection
->X
, connection
->Y
);
2608 #ifdef DEBUG_MERGING
2617 FreeNetListListMemory(&nets
);
2621 import_geometry(toporouter_t
*r
)
2623 toporouter_layer_t
*cur_layer
;
2628 for (group
= 0; group
< max_layer
; group
++) {
2629 printf("Group %d: Number %d:\n", group
, PCB
->LayerGroups
.Number
[group
]);
2631 for (int entry
= 0; entry
< PCB
->LayerGroups
.Number
[group
]; entry
++) {
2632 printf("\tEntry %d\n", PCB
->LayerGroups
.Entries
[group
][entry
]);
2636 /* Allocate space for per layer struct */
2637 cur_layer
= r
->layers
= malloc(groupcount() * sizeof(toporouter_layer_t
));
2639 /* Foreach layer, read in pad vertices and constraints, and build CDT */
2640 for (group
= 0; group
< max_layer
; group
++) {
2642 printf("*** LAYER GROUP %d ***\n", group
);
2644 if(PCB
->LayerGroups
.Number
[group
] > 0){
2645 cur_layer
->vertices
= NULL
;
2646 cur_layer
->constraints
= NULL
;
2649 printf("reading board constraints from layer %d into group %d\n", PCB
->LayerGroups
.Entries
[group
][0], group
);
2651 read_board_constraints(r
, cur_layer
, PCB
->LayerGroups
.Entries
[group
][0]);
2653 printf("reading points from layer %d into group %d \n",PCB
->LayerGroups
.Entries
[group
][0], group
);
2655 read_points(r
, cur_layer
, PCB
->LayerGroups
.Entries
[group
][0]);
2657 //#ifdef DEBUG_IMPORT
2658 // printf("reading pads from layer %d into group %d\n", number, group);
2660 read_pads(r
, cur_layer
, group
);
2662 GROUP_LOOP(PCB
->Data
, group
)
2666 printf("reading lines from layer %d into group %d\n", number
, group
);
2668 read_lines(r
, cur_layer
, layer
, number
);
2676 printf("building CDT\n");
2678 build_cdt(r
, cur_layer
);
2680 printf("finished building CDT\n");
2686 r
->bboxtree
= gts_bb_tree_new(r
->bboxes
);
2691 printf("finished import!\n");
2697 compare_points(gconstpointer a
, gconstpointer b
)
2699 GtsPoint
*i
= GTS_POINT(a
);
2700 GtsPoint
*j
= GTS_POINT(b
);
2703 if(i
->y
== j
->y
) return 0;
2704 if(i
->y
< j
->y
) return -1;
2707 if(i
->x
< j
->x
) return -1;
2712 compare_segments(gconstpointer a
, gconstpointer b
)
2714 if(a
== b
) return 0;
2715 if(a
< b
) return -1;
2719 toporouter_cluster_t
*
2720 cluster_find(toporouter_t
*r
, gdouble x
, gdouble y
, gdouble z
)
2722 GtsPoint
*p
= gts_point_new(gts_point_class(), x
, y
, z
);
2723 GSList
*hits
= gts_bb_tree_stabbed(r
->bboxtree
, p
);
2724 toporouter_cluster_t
*rval
= NULL
;
2726 #ifdef DEBUG_CLUSTER_FIND
2727 printf("FINDING %f,%f,%f\n\n", x
, y
, z
);
2731 toporouter_bbox_t
*box
= TOPOROUTER_BBOX(hits
->data
);
2733 #ifdef DEBUG_CLUSTER_FIND
2734 printf("HIT BOX: "); print_bbox(box
);
2737 if(box
->layer
== (int)z
) {
2738 if(box
->type
!= BOARD
) {
2739 if(box
->type
== LINE
) {
2740 LineType
*line
= (LineType
*)box
->data
;
2741 gint linewind
= coord_wind(line
->Point1
.X
, line
->Point1
.Y
, x
, y
, line
->Point2
.X
, line
->Point2
.Y
);
2744 rval
= box
->cluster
;
2748 }else if(box
->surface
) {
2750 if(gts_point_locate(p
, box
->surface
, NULL
)) {
2751 rval
= box
->cluster
;
2761 gts_object_destroy(GTS_OBJECT(p
));
2764 #ifdef DEBUG_CLUSTER_FIND
2765 printf("cluster_find: %f,%f,%f: ", x
, y
, z
);
2766 print_cluster(rval
);
2773 simple_h_cost(toporouter_t
*r
, toporouter_vertex_t
*curpoint
, toporouter_vertex_t
*destpoint
)
2775 gdouble layerpenalty
= (vz(curpoint
) == vz(destpoint
)) ? 0. : r
->viacost
;
2777 return gts_point_distance(GTS_POINT(curpoint
), GTS_POINT(destpoint
)) + layerpenalty
;
2780 #define FCOST(x) (x->gcost + x->hcost)
2782 route_heap_cmp(gpointer item
, gpointer data
)
2784 return FCOST(TOPOROUTER_VERTEX(item
));
2787 #define closelist_insert(p) closelist = g_list_prepend(closelist, p)
2790 toporouter_vertex_t
*key
;
2791 toporouter_vertex_t
*result
;
2792 }toporouter_heap_search_data_t
;
2795 toporouter_heap_search(gpointer data
, gpointer user_data
)
2797 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(data
);
2798 toporouter_heap_search_data_t
*heap_search_data
= (toporouter_heap_search_data_t
*)user_data
;
2799 if(v
== heap_search_data
->key
) heap_search_data
->result
= v
;
2803 toporouter_heap_color(gpointer data
, gpointer user_data
)
2805 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(data
);
2806 v
->flags
|= (unsigned int) user_data
;
2810 angle_span(gdouble a1
, gdouble a2
)
2813 return ((2*M_PI
)-a1
+ a2
);
2818 region_span(toporouter_vertex_region_t
*region
)
2822 g_assert(region
->v1
!= NULL
);
2823 g_assert(region
->v2
!= NULL
);
2824 g_assert(region
->origin
!= NULL
);
2826 a1
= point_xangle(GTS_POINT(region
->origin
), GTS_POINT(region
->v1
));
2827 a2
= point_xangle(GTS_POINT(region
->origin
), GTS_POINT(region
->v2
));
2829 return angle_span(a1
, a2
);
2833 edge_capacity(toporouter_edge_t
*e
)
2835 return gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
)));
2839 edge_flow(toporouter_edge_t
*e
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*dest
)
2841 GList
*i
= edge_routing(e
);
2842 toporouter_vertex_t
*pv
= tedge_v1(e
), *v
= NULL
;
2846 if((pv
== v1
|| pv
== v2
) && waiting
) {
2847 flow
+= min_vertex_net_spacing(pv
, dest
);
2855 v
= TOPOROUTER_VERTEX(i
->data
);
2859 flow
+= min_vertex_net_spacing(v
, pv
);
2861 flow
+= min_spacing(v
, pv
);
2863 if((v
== v1
|| v
== v2
) && waiting
) {
2864 flow
+= min_vertex_net_spacing(v
, dest
);
2874 flow
+= min_vertex_net_spacing(tedge_v2(e
), pv
);
2876 flow
+= min_spacing(tedge_v2(e
), pv
);
2882 print_path(GList
*path
)
2888 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
2889 // printf("[V %f,%f,%f]\n", vx(v), vy(v), vz(v));
2892 if(v
->child
&& !g_list_find(path
, v
->child
))
2893 printf("\t CHILD NOT IN LIST\n");
2894 if(v
->parent
&& !g_list_find(path
, v
->parent
))
2895 printf("\t parent NOT IN LIST\n");
2903 split_path(GList
*path
)
2905 toporouter_vertex_t
*pv
= NULL
;
2906 GList
*curpath
= NULL
, *i
, *paths
= NULL
;
2912 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
2915 printf("v = %f,%f ", vx(v
), vy(v
));
2916 if(v
->parent
) printf("parent = %f,%f ", vx(v
->parent
), vy(v
->parent
));
2917 if(v
->child
) printf("child = %f,%f ", vx(v
->child
), vy(v
->child
));
2921 // if(v) printf("v = %f,%f\n", GTS_POINT(v)->x, GTS_POINT(v)->y);
2922 // if(pv) printf("pv = %f,%f\n", GTS_POINT(pv)->x, GTS_POINT(pv)->y);
2926 if(GTS_POINT(v
)->x
== GTS_POINT(pv
)->x
&& GTS_POINT(v
)->y
== GTS_POINT(pv
)->y
) {
2927 if(g_list_length(curpath
) > 1) paths
= g_list_prepend(paths
, curpath
);
2934 curpath
= g_list_append(curpath
, v
);
2940 if(g_list_length(curpath
) > 1)
2941 paths
= g_list_prepend(paths
, curpath
);
2948 #define edge_gradient(e) (cartesian_gradient(GTS_POINT(GTS_SEGMENT(e)->v1)->x, GTS_POINT(GTS_SEGMENT(e)->v1)->y, \
2949 GTS_POINT(GTS_SEGMENT(e)->v2)->x, GTS_POINT(GTS_SEGMENT(e)->v2)->y))
2952 /* sorting into ascending distance from v1 */
2954 routing_edge_insert(gconstpointer a
, gconstpointer b
, gpointer user_data
)
2956 GtsPoint
*v1
= GTS_POINT(edge_v1(user_data
));
2958 if(gts_point_distance2(v1
, GTS_POINT(a
)) < gts_point_distance2(v1
, GTS_POINT(b
)) - EPSILON
)
2960 if(gts_point_distance2(v1
, GTS_POINT(a
)) > gts_point_distance2(v1
, GTS_POINT(b
)) + EPSILON
)
2963 printf("a = %x b = %x\n", (int) a, (int) b);
2965 printf("WARNING: routing_edge_insert() with same points..\n \
2972 printf("A: "); print_vertex(TOPOROUTER_VERTEX(a));
2973 printf("B: "); print_vertex(TOPOROUTER_VERTEX(b));
2975 TOPOROUTER_VERTEX(a)->flags |= VERTEX_FLAG_RED;
2976 TOPOROUTER_VERTEX(b)->flags |= VERTEX_FLAG_RED;
2982 print_edge(toporouter_edge_t
*e
)
2984 GList
*i
= edge_routing(e
);
2988 print_vertex(tedge_v1(e
));
2991 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
2996 print_vertex(tedge_v2(e
));
2999 toporouter_vertex_t
*
3000 new_temp_toporoutervertex(gdouble x
, gdouble y
, toporouter_edge_t
*e
)
3002 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
3003 GList
*i
= edge_routing(e
);
3004 toporouter_vertex_t
*r
;
3007 r
= TOPOROUTER_VERTEX(i
->data
);
3008 if(epsilon_equals(vx(r
),x
) && epsilon_equals(vy(r
),y
)) {
3009 if(r
->flags
& VERTEX_FLAG_TEMP
) return r
;
3014 r
= TOPOROUTER_VERTEX( gts_vertex_new (vertex_class
, x
, y
, vz(edge_v1(e
))) );
3015 r
->flags
|= VERTEX_FLAG_TEMP
;
3018 if(TOPOROUTER_IS_CONSTRAINT(e
))
3019 TOPOROUTER_CONSTRAINT(e
)->routing
= g_list_insert_sorted_with_data(edge_routing(e
), r
, routing_edge_insert
, e
);
3021 e
->routing
= g_list_insert_sorted_with_data(edge_routing(e
), r
, routing_edge_insert
, e
);
3027 /* create vertex on edge e at radius r from v, closest to ref */
3028 toporouter_vertex_t
*
3029 new_temp_toporoutervertex_in_segment(toporouter_edge_t
*e
, toporouter_vertex_t
*v
, gdouble r
, toporouter_vertex_t
*ref
)
3031 gdouble m
= edge_gradient(e
);
3032 toporouter_spoint_t p
, np1
, np2
;
3033 // toporouter_vertex_t *b = TOPOROUTER_VERTEX((GTS_VERTEX(v) == edge_v1(e)) ? edge_v2(e) : edge_v1(e));
3034 toporouter_vertex_t
*rval
= NULL
;
3035 p
.x
= vx(v
); p
.y
= vy(v
);
3037 vertices_on_line(&p
, m
, r
, &np1
, &np2
);
3039 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)) )
3040 rval
= new_temp_toporoutervertex(np1
.x
, np1
.y
, e
);
3042 rval
= new_temp_toporoutervertex(np2
.x
, np2
.y
, e
);
3048 vertex_keepout_test(toporouter_t
*r
, toporouter_vertex_t
*v
)
3050 GList
*i
= r
->keepoutlayers
;
3052 gdouble keepout
= *((double *) i
->data
);
3053 if(vz(v
) == keepout
) return 1;
3060 closest_cluster_pair(toporouter_t
*r
, GList
*src_vertices
, GList
*dest_vertices
, toporouter_vertex_t
**a
, toporouter_vertex_t
**b
)
3062 GList
*i
= src_vertices
, *j
= dest_vertices
;
3065 *a
= NULL
; *b
= NULL
;
3069 toporouter_vertex_t
*v1
= TOPOROUTER_VERTEX(i
->data
);
3071 if(vertex_keepout_test(r
, v1
)) { i
= i
->next
; continue; }
3075 toporouter_vertex_t
*v2
= TOPOROUTER_VERTEX(j
->data
);
3076 if(vertex_keepout_test(r
, v2
) || vz(v2
) != vz(v1
)) { j
= j
->next
; continue; }
3079 *a
= v1
; *b
= v2
; min
= simple_h_cost(r
, *a
, *b
);
3081 gdouble tempd
= simple_h_cost(r
, v1
, v2
);
3082 if(r
->flags
& TOPOROUTER_FLAG_GOFAR
&& tempd
> min
) {
3083 *a
= v1
; *b
= v2
; min
= tempd
;
3086 *a
= v1
; *b
= v2
; min
= tempd
;
3096 // g_list_free(src_vertices);
3097 // g_list_free(dest_vertices);
3101 toporouter_vertex_t
*
3102 closest_dest_vertex(toporouter_t
*r
, toporouter_vertex_t
*v
, toporouter_route_t
*routedata
)
3104 GList
//*vertices = cluster_vertices(r, routedata->dest),
3105 *i
= routedata
->destvertices
;
3106 toporouter_vertex_t
*closest
= NULL
;
3107 gdouble closest_distance
= 0.;
3109 // if(routedata->flags & TOPOROUTER_FLAG_FLEX) i = r->destboxes;
3112 toporouter_vertex_t
*cv
= TOPOROUTER_VERTEX(i
->data
);
3114 if(vz(cv
) != vz(v
)) { i
= i
->next
; continue; }
3117 closest
= cv
; closest_distance
= simple_h_cost(r
, v
, closest
);
3119 gdouble tempd
= simple_h_cost(r
, v
, cv
);
3120 if(r
->flags
& TOPOROUTER_FLAG_GOFAR
&& tempd
> closest_distance
) {
3121 closest
= cv
; closest_distance
= tempd
;
3123 if(tempd
< closest_distance
) {
3124 closest
= cv
; closest_distance
= tempd
;
3130 // g_list_free(vertices);
3133 printf("CLOSEST = %f,%f,%f\n", vx(closest
), vy(closest
), vz(closest
));
3138 #define toporouter_edge_gradient(e) (cartesian_gradient(vx(edge_v1(e)), vy(edge_v1(e)), vx(edge_v2(e)), vy(edge_v2(e))))
3141 /* returns the capacity of the triangle cut through v */
3143 triangle_interior_capacity(GtsTriangle
*t
, toporouter_vertex_t
*v
)
3145 toporouter_edge_t
*e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3146 gdouble x
, y
, m1
, m2
, c2
, c1
, len
;
3150 m1
= toporouter_edge_gradient(e
);
3151 m2
= perpendicular_gradient(m1
);
3152 c2
= (isinf(m2
)) ? vx(v
) : vy(v
) - (m2
* vx(v
));
3153 c1
= (isinf(m1
)) ? vx(edge_v1(e
)) : vy(edge_v1(e
)) - (m1
* vx(edge_v1(e
)));
3160 x
= (c2
- c1
) / (m1
- m2
);
3162 y
= (isinf(m2
)) ? vy(edge_v1(e
)) : (m2
* x
) + c2
;
3164 len
= gts_point_distance2(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
)));
3167 printf("%f,%f len = %f v = %f,%f\n", x
, y
, len
, vx(v
), vy(v
));
3170 if(epsilon_equals(x
,vx(edge_v1(e
))) && epsilon_equals(y
,vy(edge_v1(e
)))) return INFINITY
;
3171 if(epsilon_equals(x
,vx(edge_v2(e
))) && epsilon_equals(y
,vy(edge_v2(e
)))) return INFINITY
;
3173 if(x
>= MIN(vx(edge_v1(e
)),vx(edge_v2(e
))) &&
3174 x
<= MAX(vx(edge_v1(e
)),vx(edge_v2(e
))) &&
3175 y
>= MIN(vy(edge_v1(e
)),vy(edge_v2(e
))) &&
3176 y
<= MAX(vy(edge_v1(e
)),vy(edge_v2(e
))))
3178 // 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 )
3179 return sqrt(pow(vx(v
) - x
, 2) + pow(vy(v
) - y
, 2));
3184 inline toporouter_vertex_t
*
3185 segment_common_vertex(GtsSegment
*s1
, GtsSegment
*s2
)
3187 if(!s1
|| !s2
) return NULL
;
3188 if(s1
->v1
== s2
->v1
) return TOPOROUTER_VERTEX(s1
->v1
);
3189 if(s1
->v2
== s2
->v1
) return TOPOROUTER_VERTEX(s1
->v2
);
3190 if(s1
->v1
== s2
->v2
) return TOPOROUTER_VERTEX(s1
->v1
);
3191 if(s1
->v2
== s2
->v2
) return TOPOROUTER_VERTEX(s1
->v2
);
3195 inline toporouter_vertex_t
*
3196 route_vertices_common_vertex(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
3198 return segment_common_vertex(GTS_SEGMENT(v1
->routingedge
), GTS_SEGMENT(v2
->routingedge
));
3203 edges_third_edge(GtsSegment
*s1
, GtsSegment
*s2
, toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
3205 if(!s1
|| !s2
) return 0;
3206 if(s1
->v1
== s2
->v1
) {
3207 *v1
= TOPOROUTER_VERTEX(s1
->v2
);
3208 *v2
= TOPOROUTER_VERTEX(s2
->v2
);
3211 if(s1
->v2
== s2
->v1
) {
3212 *v1
= TOPOROUTER_VERTEX(s1
->v1
);
3213 *v2
= TOPOROUTER_VERTEX(s2
->v2
);
3216 if(s1
->v1
== s2
->v2
) {
3217 *v1
= TOPOROUTER_VERTEX(s1
->v2
);
3218 *v2
= TOPOROUTER_VERTEX(s2
->v1
);
3221 if(s1
->v2
== s2
->v2
) {
3222 *v1
= TOPOROUTER_VERTEX(s1
->v1
);
3223 *v2
= TOPOROUTER_VERTEX(s2
->v1
);
3229 /* returns the flow from e1 to e2, and the flow from the vertex oppisate e1 to
3230 * e1 and the vertex oppisate e2 to e2 */
3232 flow_from_edge_to_edge(GtsTriangle
*t
, toporouter_edge_t
*e1
, toporouter_edge_t
*e2
,
3233 toporouter_vertex_t
*common_v
, toporouter_vertex_t
*curpoint
)
3236 toporouter_vertex_t
*pv
= common_v
, *v
;
3237 toporouter_edge_t
*op_edge
;
3239 GList
*i
= edge_routing(e1
);
3241 v
= TOPOROUTER_VERTEX(i
->data
);
3244 r
+= min_spacing(v
, pv
);
3246 i
= i
->next
; continue;
3248 // if(!(v->flags & VERTEX_FLAG_TEMP)) {
3249 if((v
->flags
& VERTEX_FLAG_ROUTE
)) {
3251 if(v
->parent
->routingedge
== e2
) {
3252 r
+= min_spacing(v
, pv
);
3254 i
= i
->next
; continue;
3258 if(v
->child
->routingedge
== e2
) {
3259 r
+= min_spacing(v
, pv
);
3261 i
= i
->next
; continue;
3267 op_edge
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(common_v
)));
3273 v
= segment_common_vertex(GTS_SEGMENT(e2
), GTS_SEGMENT(op_edge
));
3276 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e1)));
3277 if(v
->flags
& VERTEX_FLAG_ROUTE
&& v
->parent
&& v
->parent
->routingedge
) {
3278 if(v
->parent
->routingedge
== e1
)
3279 r
+= min_spacing(v
, pv
);
3282 v
= segment_common_vertex(GTS_SEGMENT(e1
), GTS_SEGMENT(op_edge
));
3285 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e2)));
3286 if(v
->flags
& VERTEX_FLAG_ROUTE
&& v
->parent
&& v
->parent
->routingedge
) {
3287 if(v
->parent
->routingedge
== e1
)
3288 r
+= min_spacing(v
, pv
);
3291 if(TOPOROUTER_IS_CONSTRAINT(op_edge
)) {
3292 toporouter_bbox_t
*box
= vertex_bbox(TOPOROUTER_VERTEX(edge_v1(op_edge
)));
3293 r
+= vertex_net_thickness(v
) / 2.;
3295 r
+= MAX(vertex_net_keepaway(v
), cluster_keepaway(box
->cluster
));
3296 r
+= cluster_thickness(box
->cluster
) / 2.;
3298 r
+= vertex_net_keepaway(v
);
3309 check_triangle_interior_capacity(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_vertex_t
*curpoint
,
3310 toporouter_edge_t
*op_edge
, toporouter_edge_t
*adj_edge1
, toporouter_edge_t
*adj_edge2
)
3312 gdouble ic
= triangle_interior_capacity(t
, v
);
3313 gdouble flow
= flow_from_edge_to_edge(t
, adj_edge1
, adj_edge2
, v
, curpoint
);
3315 if(TOPOROUTER_IS_CONSTRAINT(adj_edge1
) || TOPOROUTER_IS_CONSTRAINT(adj_edge2
)) return 1;
3320 printf("fail interior capacity flow = %f ic = %f\n", flow
, ic
);
3328 toporouter_vertex_t
*
3329 edge_routing_next_not_temp(toporouter_edge_t
*e
, GList
*list
)
3331 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3333 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(list
->data
);
3334 if(!(v
->flags
& VERTEX_FLAG_TEMP
))
3343 toporouter_vertex_t
*
3344 edge_routing_prev_not_temp(toporouter_edge_t
*e
, GList
*list
)
3346 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3348 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(list
->data
);
3349 if(!(v
->flags
& VERTEX_FLAG_TEMP
))
3359 edge_adjacent_vertices(toporouter_edge_t
*e
, toporouter_vertex_t
*v
, toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
3361 GList
*r
= g_list_find(edge_routing(e
), v
);
3363 if(v
== tedge_v1(e
)) {
3365 *v2
= edge_routing_next_not_temp(e
, edge_routing(e
));
3366 }else if(v
== tedge_v2(e
)) {
3367 *v1
= edge_routing_prev_not_temp(e
, g_list_last(edge_routing(e
)));
3370 // r = g_list_find(r, v);
3371 *v1
= edge_routing_prev_not_temp(e
, r
);
3372 *v2
= edge_routing_next_not_temp(e
, r
);
3380 candidate_vertices(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*dest
, toporouter_edge_t
*e
)
3382 gdouble totald
, v1ms
, v2ms
, flow
, capacity
, ms
;
3389 g_assert(!(v1
->flags
& VERTEX_FLAG_TEMP
));
3390 g_assert(!(v2
->flags
& VERTEX_FLAG_TEMP
));
3392 printf("starting candidate vertices\n");
3393 printf("v1 = %f,%f v2 = %f,%f dest = %f,%f\n", vx(v1
), vy(v1
), vx(v2
), vy(v2
), vx(dest
), vy(dest
));
3395 totald
= gts_point_distance(GTS_POINT(v1
), GTS_POINT(v2
));
3396 v1ms
= min_spacing(v1
, dest
);
3397 v2ms
= min_spacing(v2
, dest
);
3398 ms
= min_spacing(dest
, dest
);
3399 flow
= TOPOROUTER_IS_CONSTRAINT(e
) ? 0. : edge_flow(e
, v1
, v2
, dest
);
3400 capacity
= edge_capacity(e
);
3403 g_assert(totald
> 0);
3405 printf("v1ms = %f v2ms = %f totald = %f ms = %f capacity = %f flow = %f\n", v1ms
, v2ms
, totald
, ms
, capacity
, flow
);
3408 if(flow
>= capacity
) return NULL
;
3411 if(v1ms
+ v2ms
+ ms
>= totald
) {
3412 vs
= g_list_prepend(vs
, new_temp_toporoutervertex((vx(v1
)+vx(v2
)) / 2., (vy(v1
)+vy(v2
)) / 2., e
));
3414 gdouble x0
, y0
, x1
, y1
, d
;
3416 vertex_move_towards_vertex_values(GTS_VERTEX(v1
), GTS_VERTEX(v2
), v1ms
, &x0
, &y0
);
3418 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x0
, y0
, e
));
3420 vertex_move_towards_vertex_values(GTS_VERTEX(v2
), GTS_VERTEX(v1
), v2ms
, &x1
, &y1
);
3422 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x1
, y1
, e
));
3424 d
= sqrt(pow(x0
-x1
,2) + pow(y0
-y1
,2));
3427 // guint nint = d / ms;
3428 // gdouble dif = d / (nint + 1);
3429 gdouble dif
= d
/ 2;
3431 // for(guint j=0;j<nint;j++) {
3434 // coord_move_towards_coord_values(x0, y0, x1, y1, dif * j, &x, &y);
3435 coord_move_towards_coord_values(x0
, y0
, x1
, y1
, dif
, &x
, &y
);
3437 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x
, y
, e
));
3445 printf("candidate vertices returning %d\n", g_list_length(vs
));
3451 edge_routing_first_not_temp(toporouter_edge_t
*e
)
3453 GList
*i
= edge_routing(e
);
3454 toporouter_vertex_t
*v
;
3457 v
= TOPOROUTER_VERTEX(i
->data
);
3458 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) return i
;
3467 edge_routing_last_not_temp(toporouter_edge_t
*e
)
3469 GList
*i
= edge_routing(e
), *last
= NULL
;
3470 toporouter_vertex_t
*v
;
3473 v
= TOPOROUTER_VERTEX(i
->data
);
3474 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) last
= i
;
3483 delete_vertex(toporouter_vertex_t
*v
)
3486 if(v
->flags
& VERTEX_FLAG_TEMP
) {
3487 if(v
->routingedge
) {
3488 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
3489 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
);
3491 v
->routingedge
->routing
= g_list_remove(v
->routingedge
->routing
, v
);
3494 gts_object_destroy ( GTS_OBJECT(v
) );
3498 #define edge_is_blocked(e) (TOPOROUTER_IS_EDGE(e) ? (e->flags & EDGE_FLAG_DIRECTCONNECTION) : 0)
3501 triangle_candidate_points_from_vertex(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_vertex_t
*dest
, toporouter_route_t
*routedata
)
3503 toporouter_edge_t
*op_e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3504 toporouter_vertex_t
*vv1
, *vv2
, *constraintv
= NULL
;
3505 toporouter_edge_t
*e1
, *e2
;
3510 printf("\tTRIANGLE CAND POINT FROM VERTEX\n");
3515 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), edge_v1(op_e
)));
3516 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), edge_v2(op_e
)));
3519 if(TOPOROUTER_IS_CONSTRAINT(op_e
)) {
3520 if(TOPOROUTER_CONSTRAINT(op_e
)->box
->type
== BOARD
) {
3522 printf("BOARD constraint\n");
3526 if(constraint_netlist(TOPOROUTER_CONSTRAINT(op_e
)) != vertex_netlist(dest
)) { // || TOPOROUTER_CONSTRAINT(op_e)->routing) {
3528 printf("op_e routing:\n");
3534 printf("RETURNING CONSTRAINT POING\n");
3536 constraintv
= new_temp_toporoutervertex_in_segment(op_e
, TOPOROUTER_VERTEX(edge_v1(op_e
)),
3537 gts_point_distance(GTS_POINT(edge_v1(op_e
)), GTS_POINT(edge_v2(op_e
))) / 2., TOPOROUTER_VERTEX(edge_v2(op_e
)));
3538 // return g_list_prepend(NULL, vv1);
3543 if(edge_is_blocked(op_e
)) {
3544 goto triangle_candidate_points_from_vertex_exit
;
3546 // v1 = tedge_v1(op_e);
3547 // v2 = tedge_v2(op_e);
3549 if(v
== tedge_v1(e1
)) {
3550 i
= edge_routing_first_not_temp(e1
);
3552 i
= edge_routing_last_not_temp(e1
);
3556 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3558 if(temp
->parent
== tedge_v2(op_e
) || temp
->child
== tedge_v2(op_e
)) {
3560 printf("temp -> op_e->v2\n");
3562 goto triangle_candidate_points_from_vertex_exit
;
3564 if(temp
->parent
->routingedge
== op_e
) {
3567 printf("vv1->parent\n");
3570 }else if(temp
->child
->routingedge
== op_e
) {
3573 printf("vv1->child\n");
3579 printf("temp -> e2?\n");
3580 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
)) );
3581 if(temp
->parent
->routingedge
)
3582 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3583 vx(edge_v1(temp
->parent
->routingedge
)), vy(edge_v1(temp
->parent
->routingedge
)),
3584 vx(edge_v2(temp
->parent
->routingedge
)), vy(edge_v2(temp
->parent
->routingedge
))
3587 printf("temp->parent->routingedge = NULL\n");
3589 if(temp
->child
->routingedge
)
3590 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3591 vx(edge_v1(temp
->child
->routingedge
)), vy(edge_v1(temp
->child
->routingedge
)),
3592 vx(edge_v2(temp
->child
->routingedge
)), vy(edge_v2(temp
->child
->routingedge
))
3595 printf("temp->child->routingedge = NULL\n");
3597 goto triangle_candidate_points_from_vertex_exit
;
3601 vv1
= tedge_v1(op_e
);
3603 printf("nothing on e1\n");
3607 if(v
== tedge_v1(e2
)) {
3608 i
= edge_routing_first_not_temp(e2
);
3610 i
= edge_routing_last_not_temp(e2
);
3614 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3616 if(temp
->parent
== tedge_v1(op_e
) || temp
->child
== tedge_v1(op_e
)) {
3618 printf("temp -> op_e->v2\n");
3620 goto triangle_candidate_points_from_vertex_exit
;
3623 if(temp
->parent
->routingedge
== op_e
) {
3626 printf("vv2->parent\n");
3628 }else if(temp
->child
->routingedge
== op_e
) {
3631 printf("vv2->child\n");
3637 printf("temp -> e1?\n");
3638 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
)) );
3639 if(temp
->parent
->routingedge
)
3640 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3641 vx(edge_v1(temp
->parent
->routingedge
)), vy(edge_v1(temp
->parent
->routingedge
)),
3642 vx(edge_v2(temp
->parent
->routingedge
)), vy(edge_v2(temp
->parent
->routingedge
))
3645 printf("temp->parent->routingedge = NULL\n");
3647 if(temp
->child
->routingedge
)
3648 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3649 vx(edge_v1(temp
->child
->routingedge
)), vy(edge_v1(temp
->child
->routingedge
)),
3650 vx(edge_v2(temp
->child
->routingedge
)), vy(edge_v2(temp
->child
->routingedge
))
3653 printf("temp->child->routingedge = NULL\n");
3655 goto triangle_candidate_points_from_vertex_exit
;
3659 vv2
= tedge_v2(op_e
);
3661 printf("nothing on e2\n");
3666 printf("size of e1 routing = %d e2 routing = %d op_e routing = %d\n",
3667 g_list_length(edge_routing(e1
)), g_list_length(edge_routing(e2
)), g_list_length(edge_routing(op_e
)));
3672 print_vertex(constraintv
);
3673 printf("constraintv %f,%f returning\n", vx(constraintv
), vy(constraintv
));
3675 return g_list_prepend(NULL
, constraintv
);
3678 i
= edge_routing(op_e
);
3680 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3682 if(temp
->parent
== v
|| temp
->child
== v
) {
3683 rval
= g_list_concat(rval
, candidate_vertices(vv1
, temp
, dest
, op_e
));
3690 rval
= g_list_concat(rval
, candidate_vertices(vv1
, vv2
, dest
, op_e
));
3696 triangle_candidate_points_from_vertex_exit
:
3697 if(constraintv
) //delete_vertex(constraintv);
3698 g_hash_table_insert(routedata
->alltemppoints
, constraintv
, constraintv
);
3706 routedata_insert_temppoints(toporouter_route_t
*data
, GList
*temppoints
) {
3707 GList
*j
= temppoints
;
3709 g_hash_table_insert(data
->alltemppoints
, j
->data
, j
->data
);
3716 constraint_route_test(toporouter_constraint_t
*c
, toporouter_route_t
*routedata
)
3718 if(c
->box
->cluster
&& c
->box
->cluster
->netlist
== routedata
->src
->netlist
) {
3719 if(c
->box
->cluster
->c
== routedata
->dest
->c
|| c
->box
->cluster
->c
== routedata
->src
->c
) return 1;
3725 all_candidates_on_edge(toporouter_edge_t
*e
, toporouter_route_t
*routedata
)
3728 if(edge_is_blocked(e
)) return NULL
;
3730 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3731 GList
*i
= edge_routing(e
);
3732 toporouter_vertex_t
*pv
= tedge_v1(e
);
3735 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3736 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) {
3737 rval
= g_list_concat(rval
, candidate_vertices(pv
, v
, TOPOROUTER_VERTEX(routedata
->destvertices
->data
), e
));
3743 rval
= g_list_concat(rval
, candidate_vertices(pv
, tedge_v2(e
), TOPOROUTER_VERTEX(routedata
->destvertices
->data
), e
));
3744 }else if(TOPOROUTER_CONSTRAINT(e
)->box
->type
== BOARD
) {
3746 }else if(constraint_route_test(TOPOROUTER_CONSTRAINT(e
), routedata
)) {
3747 toporouter_vertex_t
*consv
= new_temp_toporoutervertex_in_segment(e
, tedge_v1(e
), tvdistance(tedge_v1(e
), tedge_v2(e
)) / 2., tedge_v2(e
));
3748 rval
= g_list_prepend(rval
, consv
);
3749 // g_hash_table_insert(routedata->alltemppoints, consv, consv);
3756 triangle_all_candidate_points_from_vertex(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_route_t
*routedata
)
3758 toporouter_edge_t
*op_e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3759 return all_candidates_on_edge(op_e
, routedata
);
3763 triangle_all_candidate_points_from_edge(toporouter_t
*r
, GtsTriangle
*t
, toporouter_edge_t
*e
, toporouter_route_t
*routedata
,
3764 toporouter_vertex_t
**dest
, toporouter_vertex_t
*curpoint
)
3766 toporouter_vertex_t
*op_v
;
3767 toporouter_edge_t
*e1
, *e2
;
3768 GList
*i
, *rval
= NULL
, *rval2
= NULL
;
3769 toporouter_vertex_t
*boxpoint
= NULL
;
3770 guint e1intcap
, e2intcap
;
3772 op_v
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t
, GTS_EDGE(e
)));
3775 if(vertex_bbox(op_v
)) boxpoint
= TOPOROUTER_VERTEX(vertex_bbox(op_v
)->point
);
3777 if(g_list_find(routedata
->destvertices
, op_v
)) {
3778 rval
= g_list_prepend(rval
, op_v
);
3781 }else if(g_list_find(routedata
->destvertices
, boxpoint
)) {
3783 }else if(g_list_find(routedata
->srcvertices
, op_v
)) {
3784 rval
= g_list_prepend(rval
, op_v
);
3787 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v1(e
)));
3788 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v2(e
)));
3790 rval
= g_list_concat(rval
, all_candidates_on_edge(e1
, routedata
));
3791 rval
= g_list_concat(rval
, all_candidates_on_edge(e2
, routedata
));
3793 e1intcap
= check_triangle_interior_capacity(t
, tedge_v1(e
), curpoint
, e2
, e
, e1
);
3794 e2intcap
= check_triangle_interior_capacity(t
, tedge_v2(e
), curpoint
, e1
, e
, e2
);
3798 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3801 rval2
= g_list_prepend(rval2
, v
);
3802 else if(v
->routingedge
== e1
&& !(!TOPOROUTER_IS_CONSTRAINT(e1
) && !e1intcap
))
3803 rval2
= g_list_prepend(rval2
, v
);
3804 else if(v
->routingedge
== e2
&& !(!TOPOROUTER_IS_CONSTRAINT(e2
) && !e2intcap
))
3805 rval2
= g_list_prepend(rval2
, v
);
3815 triangle_candidate_points_from_edge(toporouter_t
*r
, GtsTriangle
*t
, toporouter_edge_t
*e
, toporouter_vertex_t
*v
, toporouter_vertex_t
**dest
,
3816 toporouter_route_t
*routedata
)
3818 toporouter_vertex_t
*v1
, *v2
, *op_v
, *vv
= NULL
, *e1constraintv
= NULL
, *e2constraintv
= NULL
;
3819 toporouter_edge_t
*e1
, *e2
;
3820 GList
*e1cands
= NULL
, *e2cands
= NULL
, *rval
= NULL
;
3821 guint noe1
= 0, noe2
= 0;
3823 op_v
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t
, GTS_EDGE(e
)));
3825 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v1(e
)));
3826 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v2(e
)));
3830 // v1 is prev dir, v2 is next dir
3831 edge_adjacent_vertices(e
, v
, &v1
, &v2
);
3833 if(TOPOROUTER_IS_CONSTRAINT(e1
)) {
3834 GList
*i
= edge_routing(e1
);
3836 if(TOPOROUTER_CONSTRAINT(e1
)->box
->type
== BOARD
) {
3838 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e1
), routedata
)) {
3841 printf("noe1 netlist\n");
3845 if(v1
== tedge_v1(e
) ||
3846 (v1
->parent
->routingedge
&& v1
->parent
->routingedge
== e1
) ||
3847 (v1
->child
->routingedge
&& v1
->child
->routingedge
== e1
)) {
3848 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
));
3852 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3854 if((temp
->child
== tedge_v2(e
) || temp
->parent
== tedge_v2(e
)) && !(temp
->flags
& VERTEX_FLAG_TEMP
)) noe2
= 1;
3859 goto triangle_candidate_points_e2
;
3862 if(edge_is_blocked(e1
)) {
3864 goto triangle_candidate_points_e2
;
3867 if(v1
== tedge_v1(e
)) {
3869 toporouter_vertex_t
*vv1
, *vv2
;
3870 edge_adjacent_vertices(e1
, v1
, &vv1
, &vv2
);
3873 printf("v1 == e->v1\n");
3877 // candidates from v1 until vv1
3880 // candidates from v1 until vv2
3884 if(!e1constraintv
) e1cands
= candidate_vertices(v1
, vv
, *dest
, e1
);
3887 if(vv
->parent
== tedge_v2(e
) || vv
->child
== tedge_v2(e
)) {
3895 }else if(v1
->parent
!= op_v
&& v1
->child
!= op_v
) {
3896 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
3899 printf("v1 != e->v1\n");
3902 if(v1
->parent
->routingedge
== e1
) {
3905 printf("v1 parent = e1\n");
3907 if(op_v
== tedge_v1(e1
)) {
3908 // candidates from v1->parent until prev vertex
3909 vv2
= edge_routing_prev_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->parent
)->prev
);
3911 // candidates from v1->parent until next vertex
3912 vv2
= edge_routing_next_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->parent
)->next
);
3915 }else if(v1
->child
->routingedge
== e1
) {
3918 printf("v1 child = e1\n");
3920 if(op_v
== tedge_v1(e1
)) {
3921 // candidates from v1->child until prev vertex
3922 vv2
= edge_routing_prev_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->child
)->prev
);
3924 // candidates from v1->child until next vertex
3925 vv2
= edge_routing_next_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->child
)->next
);
3932 goto triangle_candidate_points_e2
;
3936 if(vv2
->parent
== tedge_v2(e
) || vv2
->child
== tedge_v2(e
)) {
3943 if(!e1constraintv
) e1cands
= candidate_vertices(vv1
, vv2
, *dest
, e1
);
3949 if(vv
&& vv
== op_v
) {
3950 toporouter_vertex_t
*boxpoint
= NULL
;
3952 if(vertex_bbox(op_v
)) boxpoint
= TOPOROUTER_VERTEX(vertex_bbox(op_v
)->point
);
3954 if(g_list_find(routedata
->destvertices
, op_v
)) {
3955 rval
= g_list_prepend(rval
, op_v
);
3957 }else if(g_list_find(routedata
->destvertices
, boxpoint
)) {
3959 }else if(g_list_find(routedata
->srcvertices
, op_v
)) {
3960 rval
= g_list_prepend(rval
, op_v
);
3964 triangle_candidate_points_e2
:
3967 // printf("noe2\n");
3968 goto triangle_candidate_points_finish
;
3971 if(TOPOROUTER_IS_CONSTRAINT(e2
)) {
3972 GList
*i
= edge_routing(e2
);
3974 if(TOPOROUTER_CONSTRAINT(e2
)->box
->type
== BOARD
) {
3976 // goto triangle_candidate_points_finish;
3977 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e2
), routedata
)) {
3979 printf("noe2 netlist\n");
3982 // goto triangle_candidate_points_finish;
3983 }else if(v2
== tedge_v2(e
) ||
3984 (v2
->parent
->routingedge
&& v2
->parent
->routingedge
== e2
) ||
3985 (v2
->child
->routingedge
&& v2
->child
->routingedge
== e2
)) {
3987 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
));
3992 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3994 if((temp
->child
== tedge_v1(e
) || temp
->parent
== tedge_v1(e
)) && !(temp
->flags
& VERTEX_FLAG_TEMP
))
4002 goto triangle_candidate_points_finish
;
4005 if(edge_is_blocked(e2
)) {
4007 goto triangle_candidate_points_finish
;
4010 if(v2
== tedge_v2(e
)) {
4012 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4013 edge_adjacent_vertices(e2
, v2
, &vv1
, &vv2
);
4016 printf("v2 == e->v2\n");
4020 // candidates from v2 until vv1
4023 // candidates from v2 until vv2
4027 if(!e2constraintv
) e2cands
= candidate_vertices(v2
, vv
, *dest
, e2
);
4030 if(vv
->parent
== tedge_v1(e
) || vv
->child
== tedge_v1(e
)) {
4038 }else if(v2
->parent
!= op_v
&& v2
->child
!= op_v
) {
4039 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4042 printf("v2 == e->v2\n");
4045 if(v2
->parent
->routingedge
== e2
) {
4047 if(op_v
== tedge_v1(e2
)) {
4048 // candidates from v2->parent until prev vertex
4049 vv2
= edge_routing_prev_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->prev
);
4051 // candidates from v2->parent until next vertex
4052 vv2
= edge_routing_next_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->next
);
4055 }else if(v2
->child
->routingedge
== e2
) {
4057 if(op_v
== tedge_v1(e2
)) {
4058 // candidates from v2->child until prev vertex
4059 vv2
= edge_routing_prev_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->prev
);
4061 // candidates from v2->child until next vertex
4062 vv2
= edge_routing_next_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->next
);
4066 goto triangle_candidate_points_finish
;
4070 if(vv2
->parent
== tedge_v1(e
) || vv2
->child
== tedge_v1(e
)) {
4077 if(!e2constraintv
) e2cands
= candidate_vertices(vv1
, vv2
, *dest
, e2
);
4081 triangle_candidate_points_finish
:
4083 v1
= segment_common_vertex(GTS_SEGMENT(e
), GTS_SEGMENT(e1
));
4084 v2
= segment_common_vertex(GTS_SEGMENT(e
), GTS_SEGMENT(e2
));
4086 if(noe1
|| !check_triangle_interior_capacity(t
, v1
, v
, e2
, e
, e1
)) {
4088 printf("freeing e1cands\n");
4090 routedata_insert_temppoints(routedata
, e1cands
);
4091 g_list_free(e1cands
);
4095 if(noe2
|| !check_triangle_interior_capacity(t
, v2
, v
, e1
, e
, e2
)) {
4097 printf("freeing e2cands\n");
4099 routedata_insert_temppoints(routedata
, e2cands
);
4100 g_list_free(e2cands
);
4104 if(!noe1
&& e1constraintv
) {
4105 e1cands
= g_list_prepend(e1cands
, e1constraintv
);
4106 }else if(e1constraintv
) {
4107 g_hash_table_insert(routedata
->alltemppoints
, e1constraintv
, e1constraintv
);
4108 // delete_vertex(e1constraintv);
4111 if(!noe2
&& e2constraintv
) {
4112 e2cands
= g_list_prepend(e2cands
, e2constraintv
);
4113 }else if(e2constraintv
) {
4114 g_hash_table_insert(routedata
->alltemppoints
, e2constraintv
, e2constraintv
);
4115 // delete_vertex(e2constraintv);
4118 if(!noe1
&& !noe2
) return g_list_concat(rval
, g_list_concat(e1cands
, e2cands
));
4120 return g_list_concat(e1cands
, e2cands
);
4124 compute_candidate_points(toporouter_t
*tr
, toporouter_layer_t
*l
, toporouter_vertex_t
*curpoint
, toporouter_route_t
*data
,
4125 toporouter_vertex_t
**closestdest
)
4127 GList
*r
= NULL
, *j
;
4128 toporouter_edge_t
*edge
= curpoint
->routingedge
, *tempedge
;
4130 if(vertex_keepout_test(tr
, curpoint
)) goto compute_candidate_points_finish
;
4132 /* direct connection */
4133 // if(curpoint == TOPOROUTER_VERTEX(data->src->point))
4134 if((tempedge
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(curpoint
), GTS_VERTEX(*closestdest
))))) {
4136 if(TOPOROUTER_IS_CONSTRAINT(tempedge
)) {
4137 goto compute_candidate_points_finish
;
4139 if(!tempedge
->routing
) {
4140 r
= g_list_prepend(NULL
, *closestdest
);
4141 tempedge
->flags
|= EDGE_FLAG_DIRECTCONNECTION
;
4142 goto compute_candidate_points_finish
;
4145 printf("Direct connection, but has routing\n");
4150 /* if we get to here, there is routing blocking the direct connection,
4151 * continue as per normal */
4154 /* a real point origin */
4155 if(!(curpoint
->flags
& VERTEX_FLAG_TEMP
)) {
4156 GSList
*triangles
, *i
;
4157 i
= triangles
= gts_vertex_triangles(GTS_VERTEX(curpoint
), NULL
);
4159 printf("triangle count = %d\n", g_slist_length(triangles
));
4162 GtsTriangle
*t
= GTS_TRIANGLE(i
->data
);
4165 if(tr
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) temppoints
= triangle_all_candidate_points_from_vertex(t
, curpoint
, data
);
4166 else temppoints
= triangle_candidate_points_from_vertex(t
, curpoint
, *closestdest
, data
);
4169 printf("\treturned %d points\n", g_list_length(temppoints
));
4171 routedata_insert_temppoints(data
, temppoints
);
4173 r
= g_list_concat(r
, temppoints
);
4176 g_slist_free(triangles
);
4177 }else /* a temp point */ {
4178 int prevwind
= vertex_wind(GTS_SEGMENT(edge
)->v1
, GTS_SEGMENT(edge
)->v2
, GTS_VERTEX(curpoint
->parent
));
4179 // printf("tempoint\n");
4181 GSList
*i
= GTS_EDGE(edge
)->triangles
;
4184 GtsVertex
*oppv
= gts_triangle_vertex_opposite(GTS_TRIANGLE(i
->data
), GTS_EDGE(edge
));
4185 if(prevwind
!= vertex_wind(GTS_SEGMENT(edge
)->v1
, GTS_SEGMENT(edge
)->v2
, oppv
)) {
4188 if(tr
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) temppoints
= triangle_all_candidate_points_from_edge(tr
, GTS_TRIANGLE(i
->data
), edge
,
4189 data
, closestdest
, curpoint
);
4190 else temppoints
= triangle_candidate_points_from_edge(tr
, GTS_TRIANGLE(i
->data
), edge
, curpoint
, closestdest
, data
);
4194 toporouter_vertex_t
*tempj
= TOPOROUTER_VERTEX(j
->data
);
4195 if(tempj
->flags
& VERTEX_FLAG_TEMP
)
4196 g_hash_table_insert(data
->alltemppoints
, j
->data
, j
->data
);
4199 printf("got cand not a temp\n");
4203 r
= g_list_concat(r
, temppoints
);
4211 compute_candidate_points_finish
:
4213 if(vertex_bbox(curpoint
)) {
4214 if(vertex_bbox(curpoint
)->cluster
->c
== data
->src
->c
) {
4215 r
= g_list_concat(r
, g_list_copy(data
->srcvertices
));
4223 temp_point_clean(gpointer key
, gpointer value
, gpointer user_data
)
4225 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(value
);
4226 if(tv
->flags
& VERTEX_FLAG_TEMP
) {
4227 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
4228 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
4230 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
4231 gts_object_destroy ( GTS_OBJECT(tv
) );
4237 clean_routing_edges(toporouter_t
*r
, toporouter_route_t
*data
)
4239 g_hash_table_foreach_remove(data
->alltemppoints
, temp_point_clean
, NULL
);
4240 g_hash_table_destroy(data
->alltemppoints
);
4241 data
->alltemppoints
= NULL
;
4245 path_score(toporouter_t
*r
, GList
*path
)
4248 toporouter_vertex_t
*pv
= NULL
;
4250 if(!path
) return INFINITY
;
4253 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(path
->data
);
4256 score
+= gts_point_distance(GTS_POINT(pv
), GTS_POINT(v
));
4259 score
+= r
->viacost
;
4271 print_vertices(GList
*vertices
)
4274 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(vertices
->data
);
4276 print_bbox(vertex_bbox(v
));
4277 if(vertex_bbox(v
)) {
4278 printf("has bbox\n");
4279 if(vertex_bbox(v
)->cluster
)
4280 printf("has cluster\n");
4282 printf("no cluster\n");
4283 }else printf("no bbox\n");
4284 vertices
= vertices
->next
;
4289 space_edge(gpointer item
, gpointer data
)
4291 toporouter_edge_t
*e
= TOPOROUTER_EDGE(item
);
4295 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
4297 if(!edge_routing(e
) || !g_list_length(edge_routing(e
))) return 0;
4299 forces
= malloc(sizeof(double) * g_list_length(edge_routing(e
)));
4301 for(guint j
=0;j
<100;j
++) {
4303 guint equilibrium
= 1;
4305 i
= edge_routing(e
);
4307 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4311 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->prev->data), v);
4312 ms
= min_spacing(TOPOROUTER_VERTEX(i
->prev
->data
), v
);
4313 d
= gts_point_distance(GTS_POINT(i
->prev
->data
), GTS_POINT(v
));
4315 // ms = min_vertex_net_spacing(v, tedge_v1(e));
4316 ms
= min_spacing(v
, tedge_v1(e
));
4317 d
= gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(v
));
4320 if(d
< ms
) forces
[k
] = ms
- d
;
4321 else forces
[k
] = 0.;
4324 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->next->data), v);
4325 ms
= min_spacing(TOPOROUTER_VERTEX(i
->next
->data
), v
);
4326 d
= gts_point_distance(GTS_POINT(i
->next
->data
), GTS_POINT(v
));
4328 // ms = min_vertex_net_spacing(v, tedge_v2(e));
4329 ms
= min_spacing(v
, tedge_v2(e
));
4330 d
= gts_point_distance(GTS_POINT(edge_v2(e
)), GTS_POINT(v
));
4333 if(d
< ms
) forces
[k
] += d
- ms
;
4339 i
= edge_routing(e
);
4341 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4342 if(forces
[k
] > EPSILON
|| forces
[k
] < -EPSILON
) equilibrium
= 0;
4343 vertex_move_towards_vertex_values(GTS_VERTEX(v
), edge_v2(e
), forces
[k
] * 0.1, &(GTS_POINT(v
)->x
), &(GTS_POINT(v
)->y
));
4348 // printf("reached equilibriium at %d\n", j);
4359 swap_vertices(toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
4361 toporouter_vertex_t
*tempv
= *v1
;
4367 split_edge_routing(toporouter_vertex_t
*v
, GList
**l1
, GList
**l2
)
4372 g_assert(v
->routingedge
);
4374 base
= g_list_find(vrouting(v
), v
);
4376 *l1
= g_list_prepend(*l1
, tedge_v1(v
->routingedge
));
4377 *l2
= g_list_prepend(*l2
, tedge_v2(v
->routingedge
));
4383 if(!(TOPOROUTER_VERTEX(i
->data
)->flags
& VERTEX_FLAG_TEMP
)) *l2
= g_list_prepend(*l2
, i
->data
);
4389 if(!(TOPOROUTER_VERTEX(i
->data
)->flags
& VERTEX_FLAG_TEMP
)) *l1
= g_list_prepend(*l1
, i
->data
);
4395 vertices_routing_conflicts(toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
)
4397 toporouter_edge_t
*e
;
4398 GList
*rval
= NULL
, *l1
= NULL
, *l2
= NULL
, *i
;
4400 if(vz(v
) != vz(pv
)) return NULL
;
4403 if(!v
->routingedge
&& !pv
->routingedge
) {
4404 e
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), GTS_VERTEX(pv
)));
4406 i
= edge_routing(e
);
4408 rval
= g_list_prepend(rval
, TOPOROUTER_VERTEX(i
->data
)->route
);
4414 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
) && TOPOROUTER_IS_CONSTRAINT(pv
->routingedge
))
4417 if(TOPOROUTER_IS_CONSTRAINT(pv
->routingedge
)) swap_vertices(&pv
, &v
);
4419 if(!v
->routingedge
) swap_vertices(&pv
, &v
);
4423 split_edge_routing(v
, &l1
, &l2
);
4427 if(!pv
->routingedge
) {
4428 toporouter_edge_t
*e1
, *e2
;
4429 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv
), edge_v1(e
)));
4430 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv
), edge_v2(e
)));
4432 l1
= g_list_concat(l1
, g_list_copy(edge_routing(e1
)));
4433 l2
= g_list_concat(l2
, g_list_copy(edge_routing(e2
)));
4436 GList
*pvlist1
= NULL
, *pvlist2
= NULL
;
4437 toporouter_vertex_t
*commonv
= route_vertices_common_vertex(v
, pv
);
4441 split_edge_routing(pv
, &pvlist1
, &pvlist2
);
4443 if(commonv
== tedge_v1(e
)) {
4444 toporouter_edge_t
*ope
;
4446 if(commonv
== tedge_v1(pv
->routingedge
)) {
4447 l1
= g_list_concat(l1
, pvlist1
);
4448 l2
= g_list_concat(l2
, pvlist2
);
4449 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e
), edge_v2(pv
->routingedge
)));
4451 l1
= g_list_concat(l1
, pvlist2
);
4452 l2
= g_list_concat(l2
, pvlist1
);
4453 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e
), edge_v1(pv
->routingedge
)));
4456 l2
= g_list_concat(l2
, g_list_copy(edge_routing(ope
)));
4459 toporouter_edge_t
*ope
;
4460 if(commonv
== tedge_v1(pv
->routingedge
)) {
4461 l1
= g_list_concat(l1
, pvlist2
);
4462 l2
= g_list_concat(l2
, pvlist1
);
4463 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e
), edge_v2(pv
->routingedge
)));
4465 l1
= g_list_concat(l1
, pvlist1
);
4466 l2
= g_list_concat(l2
, pvlist2
);
4467 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e
), edge_v1(pv
->routingedge
)));
4470 l1
= g_list_concat(l1
, g_list_copy(edge_routing(ope
)));
4476 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
4478 if(curv
->flags
& VERTEX_FLAG_ROUTE
&& (g_list_find(l2
, curv
->parent
) || g_list_find(l2
, curv
->child
))) {
4479 if(!g_list_find(rval
, curv
->route
)) rval
= g_list_prepend(rval
, curv
->route
);
4485 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
4487 if(curv
->flags
& VERTEX_FLAG_ROUTE
&& (g_list_find(l1
, curv
->parent
) || g_list_find(l1
, curv
->child
))) {
4488 if(!g_list_find(rval
, curv
->route
)) rval
= g_list_prepend(rval
, curv
->route
);
4500 vertices_routing_conflict_cost(toporouter_t
*r
, toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
, guint
*n
)
4502 GList
*conflicts
= vertices_routing_conflicts(v
, pv
), *i
;
4503 gdouble penalty
= 0.;
4508 penalty
+= TOPOROUTER_ROUTE(i
->data
)->score
;
4511 g_list_free(conflicts
);
4512 // if(penalty > 0.) printf("conflict penalty of %f with %f,%f %f,%f\n", penalty, vx(v), vy(v), vx(pv), vy(pv));
4517 gcost(toporouter_t
*r
, toporouter_route_t
*data
, toporouter_vertex_t
*srcv
, toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
, guint
*n
,
4518 toporouter_netlist_t
*pair
)
4520 gdouble cost
= 0., segcost
;
4524 if(g_list_find(data
->srcvertices
, v
)) return 0.;
4526 segcost
= tvdistance(pv
, v
);
4528 if(pair
&& !TOPOROUTER_IS_CONSTRAINT(v
->routingedge
) && v
->routingedge
) {
4529 GList
*list
= g_list_find(v
->routingedge
->routing
, v
);
4530 toporouter_vertex_t
*pv
= edge_routing_prev_not_temp(v
->routingedge
, list
);
4531 toporouter_vertex_t
*nv
= edge_routing_next_not_temp(v
->routingedge
, list
);
4533 if(pv
->route
&& pv
->route
->netlist
== pair
) {
4534 }else if(nv
->route
&& nv
->route
->netlist
== pair
) {
4540 cost
= pv
->gcost
+ segcost
;
4542 if(r
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) {
4543 gdouble conflictcost
= 0.;
4545 if(pv
&& v
!= pv
&& vz(v
) == vz(pv
)) conflictcost
= vertices_routing_conflict_cost(r
, v
, pv
, n
);
4547 if(!(r
->flags
& TOPOROUTER_FLAG_DETOUR
&& *n
== 1)) {
4548 cost
+= conflictcost
* (pow(*n
,2));
4555 #define vlayer(x) (&r->layers[(int)vz(x)])
4558 candidate_is_available(toporouter_vertex_t
*pv
, toporouter_vertex_t
*v
)
4560 // TODO: still needed?
4562 if(pv
== v
) return 0;
4570 route(toporouter_t
*r
, toporouter_route_t
*data
, guint debug
)
4572 GtsEHeap
*openlist
= gts_eheap_new(route_heap_cmp
, NULL
);
4573 GList
*closelist
= NULL
;
4574 GList
*i
, *rval
= NULL
;
4575 toporouter_netlist_t
*pair
= NULL
;
4578 toporouter_vertex_t
*srcv
= NULL
, *destv
= NULL
, *curpoint
= NULL
;
4579 toporouter_layer_t
*cur_layer
, *dest_layer
;
4581 g_assert(data
->src
->c
!= data
->dest
->c
);
4583 if(data
->destvertices
) g_list_free(data
->destvertices
);
4584 if(data
->srcvertices
) g_list_free(data
->srcvertices
);
4586 data
->destvertices
= cluster_vertices(r
, data
->dest
);
4587 data
->srcvertices
= cluster_vertices(r
, data
->src
);
4589 closest_cluster_pair(r
, data
->srcvertices
, data
->destvertices
, &curpoint
, &destv
);
4591 if(!curpoint
|| !destv
) goto routing_return
;
4594 cur_layer
= vlayer(curpoint
); dest_layer
= vlayer(destv
);
4598 data
->alltemppoints
= g_hash_table_new(g_direct_hash
, g_direct_equal
);
4600 curpoint
->parent
= NULL
;
4601 curpoint
->child
= NULL
;
4602 curpoint
->gcost
= 0.;
4604 curpoint
->hcost
= simple_h_cost(r
, curpoint
, destv
);
4606 if(data
->netlist
&& data
->netlist
->pair
) {
4607 GList
*i
= r
->routednets
;
4609 toporouter_route_t
*curroute
= TOPOROUTER_ROUTE(i
->data
);
4610 if(curroute
->netlist
== data
->netlist
->pair
) {
4611 pair
= data
->netlist
->pair
;
4618 gts_eheap_insert(openlist
, curpoint
);
4620 while(gts_eheap_size(openlist
) > 0) {
4621 GList
*candidatepoints
;
4622 data
->curpoint
= curpoint
;
4623 //draw_route_status(r, closelist, openlist, curpoint, data, count++);
4625 curpoint
= TOPOROUTER_VERTEX( gts_eheap_remove_top(openlist
, NULL
) );
4626 if(curpoint
->parent
&& !(curpoint
->flags
& VERTEX_FLAG_TEMP
)) {
4627 if(vz(curpoint
) != vz(destv
)) {
4628 toporouter_vertex_t
*tempv
;
4629 cur_layer
= vlayer(curpoint
);//&r->layers[(int)vz(curpoint)];
4630 tempv
= closest_dest_vertex(r
, curpoint
, data
);
4633 dest_layer
= vlayer(destv
);//&r->layers[(int)vz(destv)];
4639 // destpoint = closest_dest_vertex(r, curpoint, data);
4640 // dest_layer = &r->layers[(int)vz(destpoint)];
4642 if(g_list_find(data
->destvertices
, curpoint
)) {
4643 toporouter_vertex_t
*temppoint
= curpoint
;
4650 data
->path
= g_list_prepend(data
->path
, temppoint
);
4651 if(g_list_find(data
->srcvertices
, temppoint
)) {
4653 if(r
->flags
& TOPOROUTER_FLAG_AFTERORDER
) break;
4655 temppoint
= temppoint
->parent
;
4658 data
->score
= path_score(r
, data
->path
);
4660 printf("ROUTE: path score = %f computation cost = %d\n", data
->score
, count
);
4663 if(srcv
->bbox
->cluster
!= data
->src
) {
4664 data
->src
= srcv
->bbox
->cluster
;
4667 if(destv
->bbox
->cluster
!= data
->dest
) {
4668 data
->dest
= destv
->bbox
->cluster
;
4672 closelist_insert(curpoint
);
4674 printf("\n\n\n*** ROUTE COUNT = %d\n", count
);
4676 candidatepoints
= compute_candidate_points(r
, cur_layer
, curpoint
, data
, &destv
);
4678 //#ifdef DEBUG_ROUTE
4679 /*********************
4680 if(debug && !strcmp(data->dest->netlist, " unnamed_net2"))
4682 unsigned int mask = ~(VERTEX_FLAG_RED | VERTEX_FLAG_GREEN | VERTEX_FLAG_BLUE);
4686 for(j=0;j<groupcount();j++) {
4687 i = r->layers[j].vertices;
4689 TOPOROUTER_VERTEX(i->data)->flags &= mask;
4694 i = candidatepoints;
4696 TOPOROUTER_VERTEX(i->data)->flags |= VERTEX_FLAG_GREEN;
4697 // printf("flagged a candpoint @ %f,%f\n",
4698 // vx(i->data), vy(i->data));
4702 curpoint->flags |= VERTEX_FLAG_BLUE;
4703 if(curpoint->parent)
4704 curpoint->parent->flags |= VERTEX_FLAG_RED;
4707 for(j=0;j<groupcount();j++) {
4708 GList *datas = g_list_prepend(NULL, data);
4709 sprintf(buffer, "route-%d-%05d.png", j, count);
4710 toporouter_draw_surface(r, r->layers[j].surface, buffer, 1024, 1024, 2, datas, j, candidatepoints);
4715 *********************/
4717 // if(count > 100) exit(0);
4718 i
= candidatepoints
;
4720 toporouter_vertex_t
*temppoint
= TOPOROUTER_VERTEX(i
->data
);
4721 if(!g_list_find(closelist
, temppoint
) && candidate_is_available(curpoint
, temppoint
)) { //&& temppoint != curpoint) {
4722 toporouter_heap_search_data_t heap_search_data
= { temppoint
, NULL
};
4725 gdouble temp_g_cost
= gcost(r
, data
, srcv
, temppoint
, curpoint
, &temp_gn
, pair
);
4728 gts_eheap_foreach(openlist
,toporouter_heap_search
, &heap_search_data
);
4730 if(heap_search_data
.result
) {
4731 if(temp_g_cost
< temppoint
->gcost
) {
4733 temppoint
->gcost
= temp_g_cost
;
4734 temppoint
->gn
= temp_gn
;
4736 temppoint
->parent
= curpoint
;
4737 curpoint
->child
= temppoint
;
4739 gts_eheap_update(openlist
);
4742 temppoint
->parent
= curpoint
;
4743 curpoint
->child
= temppoint
;
4745 temppoint
->gcost
= temp_g_cost
;
4746 temppoint
->gn
= temp_gn
;
4748 temppoint
->hcost
= simple_h_cost(r
, temppoint
, destv
);
4749 // if(cur_layer != dest_layer) temppoint->hcost += r->viacost;
4750 gts_eheap_insert(openlist
, temppoint
);
4756 g_list_free(candidatepoints
);
4760 printf("ROUTE: could not find path!\n");
4763 data
->score
= INFINITY
;
4764 clean_routing_edges(r
, data
);
4767 //TOPOROUTER_VERTEX(data->src->point)->parent = NULL;
4768 //TOPOROUTER_VERTEX(data->src->point)->child = NULL;
4769 goto routing_return
;
4774 for(i=0;i<groupcount();i++) {
4776 sprintf(buffer, "route-error-%d-%d.png", r->routecount, i);
4777 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1280, 1280, 2, data, i, NULL);
4784 // printf(" * finished a*\n");
4788 for(i=0;i<groupcount();i++) {
4790 sprintf(buffer, "route-preclean-%d-%d.png", i, r->routecount);
4791 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, data, i, NULL);
4799 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
4801 if(tv->routingedge) {
4802 GList *list = g_list_find(edge_routing(tv->routingedge), tv);
4803 toporouter_vertex_t *restartv = NULL, *boxpoint;
4808 if(vertex_bbox(tedge_v2(tv->routingedge)))
4809 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v2(tv->routingedge))->point);
4813 if(tedge_v2(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v2(tv->routingedge)))
4814 restartv = tedge_v2(tv->routingedge);
4815 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
4816 restartv = boxpoint;
4820 if(vertex_bbox(tedge_v1(tv->routingedge)))
4821 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v1(tv->routingedge))->point);
4825 if(tedge_v1(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v1(tv->routingedge)))
4826 restartv = tedge_v1(tv->routingedge);
4827 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
4828 restartv = boxpoint;
4833 clean_routing_edges(r, data);
4834 gts_eheap_destroy(openlist);
4835 g_list_free(closelist);
4836 openlist = gts_eheap_new(route_heap_cmp, NULL);
4838 g_list_free(data->path);
4839 printf("ROUTING RESTARTING with new src %f,%f,%f\n", vx(restartv), vy(restartv), vz(restartv));
4840 curpoint = restartv;
4850 toporouter_vertex_t
*pv
= NULL
;
4851 GList
*i
= data
->path
;
4853 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
4855 if(pv
&& g_list_find(data
->srcvertices
, tv
)) {
4856 GList
*temp
= g_list_copy(i
);
4857 g_list_free(data
->path
);
4867 toporouter_vertex_t
*pv
= NULL
;
4868 GList
*i
= data
->path
;
4870 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
4871 if(tv
->flags
& VERTEX_FLAG_TEMP
) {
4872 tv
->flags
^= VERTEX_FLAG_TEMP
;
4873 tv
->flags
|= VERTEX_FLAG_ROUTE
;
4875 if(pv
) pv
->child
= tv
;
4877 if(tv
->routingedge
) tv
->route
= data
;
4879 // if(tv->routingedge && !TOPOROUTER_IS_CONSTRAINT(tv->routingedge)) space_edge(tv->routingedge, NULL);
4887 toporouter_vertex_t
*pv
= NULL
, *v
= NULL
;
4889 GList
*i
= data
->path
;
4891 v
= TOPOROUTER_VERTEX(i
->data
);
4904 if(v
) v
->child
= NULL
;
4907 clean_routing_edges(r
, data
);
4910 GList
*i
= data
->path
;
4912 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4914 if(v
->routingedge
&& !TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
4915 space_edge(v
->routingedge
, NULL
);
4922 g_list_free(data
->destvertices
);
4923 g_list_free(data
->srcvertices
);
4924 data
->destvertices
= NULL
;
4925 data
->srcvertices
= NULL
;
4926 gts_eheap_destroy(openlist
);
4927 g_list_free(closelist
);
4929 data
->alltemppoints
= NULL
;
4934 /* moves vertex v d units in the direction of vertex p */
4936 vertex_move_towards_point(GtsVertex
*v
, gdouble px
, gdouble py
, gdouble d
)
4938 gdouble dx
= px
- GTS_POINT(v
)->x
;
4939 gdouble dy
= py
- GTS_POINT(v
)->y
;
4940 gdouble theta
= atan(fabs(dy
/dx
));
4942 g_assert(finite(theta
));
4947 GTS_POINT(v
)->x
+= d
* cos(theta
);
4948 GTS_POINT(v
)->y
+= d
* sin(theta
);
4950 GTS_POINT(v
)->x
+= d
* cos(theta
);
4951 GTS_POINT(v
)->y
-= d
* sin(theta
);
4957 GTS_POINT(v
)->x
-= d
* cos(theta
);
4958 GTS_POINT(v
)->y
+= d
* sin(theta
);
4960 GTS_POINT(v
)->x
-= d
* cos(theta
);
4961 GTS_POINT(v
)->y
-= d
* sin(theta
);
4968 /* moves vertex v d units in the direction of vertex p */
4970 vertex_move_towards_vertex(GtsVertex
*v
, GtsVertex
*p
, gdouble d
)
4972 gdouble dx
= GTS_POINT(p
)->x
- GTS_POINT(v
)->x
;
4973 gdouble dy
= GTS_POINT(p
)->y
- GTS_POINT(v
)->y
;
4974 gdouble theta
= atan(fabs(dy
/dx
));
4976 g_assert(finite(theta
));
4981 GTS_POINT(v
)->x
+= d
* cos(theta
);
4982 GTS_POINT(v
)->y
+= d
* sin(theta
);
4984 GTS_POINT(v
)->x
+= d
* cos(theta
);
4985 GTS_POINT(v
)->y
-= d
* sin(theta
);
4991 GTS_POINT(v
)->x
-= d
* cos(theta
);
4992 GTS_POINT(v
)->y
+= d
* sin(theta
);
4994 GTS_POINT(v
)->x
-= d
* cos(theta
);
4995 GTS_POINT(v
)->y
-= d
* sin(theta
);
5004 pathvertex_arcing_through_constraint(toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
)
5006 toporouter_vertex_t
*v
= pathv
->child
;
5008 if(!v
|| !v
->routingedge
) return 0.;
5010 while(v
->flags
& VERTEX_FLAG_ROUTE
&& (tedge_v1(v
->routingedge
) == arcv
|| tedge_v2(v
->routingedge
) == arcv
)) {
5011 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
5012 return gts_point_distance(GTS_POINT(tedge_v1(v
->routingedge
)), GTS_POINT(tedge_v2(v
->routingedge
)));
5017 while(v
->flags
& VERTEX_FLAG_ROUTE
&& (tedge_v1(v
->routingedge
) == arcv
|| tedge_v2(v
->routingedge
) == arcv
)) {
5018 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
5019 return gts_point_distance(GTS_POINT(tedge_v1(v
->routingedge
)), GTS_POINT(tedge_v2(v
->routingedge
)));
5027 vertices_connected(toporouter_vertex_t
*a
, toporouter_vertex_t
*b
)
5029 return ((a
->route
->netlist
== b
->route
->netlist
&& a
->route
->src
->c
== b
->route
->src
->c
) ? 1 : 0);
5033 edge_min_spacing(GList
*list
, toporouter_edge_t
*e
, toporouter_vertex_t
*v
, guint debug
)
5035 toporouter_vertex_t
*origin
;
5038 toporouter_vertex_t
*nextv
, *prevv
;
5039 //toporouter_vertex_t *edgev;
5040 //gdouble constraint_spacing;
5042 if(!list
) return INFINITY
;
5044 // printf("\t CMS %f,%f - %f,%f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), vx(tedge_v2(e)), vy(tedge_v2(e)));
5046 prevv
= origin
= TOPOROUTER_VERTEX(list
->data
);
5051 if(gts_point_distance2(GTS_POINT(origin
), GTS_POINT(edge_v1(e
))) < gts_point_distance2(GTS_POINT(v
), GTS_POINT(edge_v1(e
)))) {
5055 nextv
= edge_routing_next(e
, i
);
5056 if(nextv
->route
&& vertices_connected(nextv
, prevv
)) { i
= i
->next
; continue; }
5057 if(!(nextv
->flags
& VERTEX_FLAG_TEMP
)) {
5058 gdouble ms
= min_spacing(prevv
, nextv
);
5059 if(nextv
== tedge_v2(e
)) {
5060 gdouble cms
= pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i
->data
), tedge_v2(e
));
5061 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v2(e)), vy(tedge_v2(e)), cms, ms);
5062 // if(vx(tedge_v2(e)) > -EPSILON && vx(tedge_v2(e)) < EPSILON) {
5063 // printf("\t\tPROB: ");
5064 // print_vertex(tedge_v2(e));
5066 if(cms
> EPSILON
) space
+= MIN(ms
, cms
/ 2.);
5073 // printf("%f ", space);
5080 nextv
= edge_routing_prev(e
, i
);
5081 if(nextv
->route
&& vertices_connected(nextv
, prevv
)) { i
= i
->prev
; continue; }
5082 if(!(nextv
->flags
& VERTEX_FLAG_TEMP
)) {
5083 gdouble ms
= min_spacing(prevv
, nextv
);
5084 if(nextv
== tedge_v1(e
)) {
5085 gdouble cms
= pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i
->data
), tedge_v1(e
));
5086 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), cms, ms);
5087 // if(vx(tedge_v1(e)) > -EPSILON && vx(tedge_v1(e)) < EPSILON) {
5088 // printf("\t\tPROB: ");
5089 // print_vertex(tedge_v1(e));
5091 if(cms
> EPSILON
) space
+= MIN(ms
, cms
/ 2.);
5098 // printf("%f ", space);
5103 if(TOPOROUTER_IS_CONSTRAINT(e
) && space
> gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) / 2.)
5104 space
= gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) / 2.;
5106 // if(debug) printf("\tedge_min_spacing: %f\n", space);
5110 /* line segment is 1 & 2, point is 3
5111 returns 0 if v3 is outside seg
5114 vertex_line_normal_intersection(gdouble x1
, gdouble y1
, gdouble x2
, gdouble y2
, gdouble x3
, gdouble y3
, gdouble
*x
, gdouble
*y
)
5116 gdouble m1
= cartesian_gradient(x1
,y1
,x2
,y2
);
5117 gdouble m2
= perpendicular_gradient(m1
);
5118 gdouble c2
= (isinf(m2
)) ? x3
: y3
- (m2
* x3
);
5119 gdouble c1
= (isinf(m1
)) ? x1
: y1
- (m1
* x1
);
5126 *x
= (c2
- c1
) / (m1
- m2
);
5128 *y
= (isinf(m2
)) ? y1
: (m2
* (*x
)) + c2
;
5130 if(*x
>= MIN(x1
,x2
) - EPSILON
&& *x
<= MAX(x1
,x2
) + EPSILON
&& *y
>= MIN(y1
,y2
) - EPSILON
&& *y
<= MAX(y1
,y2
) + EPSILON
)
5136 print_toporouter_arc(toporouter_arc_t
*arc
)
5138 // GList *i = arc->vs;
5140 printf("ARC CENTRE: %f,%f ", vx(arc
->centre
), vy(arc
->centre
));// print_vertex(arc->centre);
5141 printf("RADIUS: %f", arc
->r
);
5143 if(arc
->dir
>0) printf(" COUNTERCLOCKWISE ");
5144 else if(arc
->dir
<0) printf(" CLOCKWISE ");
5145 else printf(" COLINEAR(ERROR) ");
5150 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
5151 printf("%f,%f ", vx(v), vy(v));
5159 toporouter_arc_remove(toporouter_oproute_t
*oproute
, toporouter_arc_t
*arc
)
5161 oproute
->arcs
= g_list_remove(oproute
->arcs
, arc
);
5163 if(arc
->v
) arc
->v
->arc
= NULL
;
5167 toporouter_arc_new(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*centre
, gdouble r
, gint dir
)
5169 toporouter_arc_t
*arc
= TOPOROUTER_ARC(gts_object_new(GTS_OBJECT_CLASS(toporouter_arc_class())));
5170 arc
->centre
= centre
;
5177 if(v1
) v1
->arc
= arc
;
5178 arc
->oproute
= oproute
;
5180 arc
->clearance
= NULL
;
5186 path_set_oproute(GList
*path
, toporouter_oproute_t
*oproute
)
5189 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(path
->data
);
5191 if(v
->flags
& VERTEX_FLAG_ROUTE
)
5192 v
->oproute
= oproute
;
5199 print_oproute(toporouter_oproute_t
*oproute
)
5201 GList
*i
= oproute
->arcs
;
5203 printf("Optimized Route:\n");
5204 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", oproute
->netlist
, oproute
->style
);
5205 // printf("%s\n", oproute->netlist);
5207 i = oproute->term1->zlink;
5209 toporouter_vertex_t *thisv = TOPOROUTER_VERTEX(i->data);
5210 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", vertex_bbox(thisv)->netlist, vertex_bbox(thisv)->style);
5214 printf("\t"); print_vertex(oproute
->term1
); printf("\n");
5217 toporouter_arc_t
*arc
= (toporouter_arc_t
*)i
->data
;
5218 printf("\t"); print_toporouter_arc(arc
); printf("\n");
5221 printf("\t"); print_vertex(oproute
->term2
); printf("\n");
5225 export_pcb_drawline(guint layer
, guint x0
, guint y0
, guint x1
, guint y1
, guint thickness
, guint keepaway
)
5229 line
= CreateDrawnLineOnLayer( LAYER_PTR(layer
), x0
, y0
, x1
, y1
,
5230 thickness
, keepaway
,
5231 MakeFlags (AUTOFLAG
| (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
: 0)));
5234 AddObjectToCreateUndoList (LINE_TYPE
, LAYER_PTR(layer
), line
, line
);
5235 d
= coord_distance((double)x0
, (double)y0
, (double)x1
, (double)y1
) / 100.;
5241 arc_angle(toporouter_arc_t
*arc
)
5243 gdouble x0
, x1
, y0
, y1
;
5245 x0
= arc
->x0
- vx(arc
->centre
);
5246 x1
= arc
->x1
- vx(arc
->centre
);
5247 y0
= arc
->y0
- vy(arc
->centre
);
5248 y1
= arc
->y1
- vy(arc
->centre
);
5250 return fabs(acos(((x0
*x1
)+(y0
*y1
))/(sqrt(pow(x0
,2)+pow(y0
,2))*sqrt(pow(x1
,2)+pow(y1
,2)))));
5254 export_pcb_drawarc(guint layer
, toporouter_arc_t
*a
, guint thickness
, guint keepaway
)
5256 gdouble sa
, da
, theta
;
5257 gdouble x0
, y0
, x1
, y1
, d
=0.;
5261 wind
= coord_wind(a
->x0
, a
->y0
, a
->x1
, a
->y1
, vx(a
->centre
), vy(a
->centre
));
5263 sa
= coord_xangle(a
->x0
, a
->y0
, vx(a
->centre
), vy(a
->centre
)) * 180. / M_PI
;
5265 x0
= a
->x0
- vx(a
->centre
);
5266 x1
= a
->x1
- vx(a
->centre
);
5267 y0
= a
->y0
- vy(a
->centre
);
5268 y1
= a
->y1
- vy(a
->centre
);
5270 theta
= arc_angle(a
);
5272 if(!a
->dir
|| !wind
) return 0.;
5274 if(a
->dir
!= wind
) theta
= 2. * M_PI
- theta
;
5276 da
= -a
->dir
* theta
* 180. / M_PI
;
5278 if(da
< 1. && da
> -1.) return 0.;
5279 if(da
> 359. || da
< -359.) return 0.;
5281 arc
= CreateNewArcOnLayer(LAYER_PTR(layer
), vx(a
->centre
), vy(a
->centre
), a
->r
, a
->r
,
5282 sa
, da
, thickness
, keepaway
,
5283 MakeFlags( AUTOFLAG
| (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
: 0)));
5286 AddObjectToCreateUndoList( ARC_TYPE
, LAYER_PTR(layer
), arc
, arc
);
5287 d
= a
->r
* theta
/ 100.;
5294 calculate_term_to_arc(toporouter_vertex_t
*v
, toporouter_arc_t
*arc
, guint dir
)
5296 gdouble theta
, a
, b
, bx
, by
, a0x
, a0y
, a1x
, a1y
;
5299 theta
= acos(arc
->r
/ gts_point_distance(GTS_POINT(v
), GTS_POINT(arc
->centre
)));
5300 a
= arc
->r
* sin(theta
);
5301 b
= arc
->r
* cos(theta
);
5303 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
));
5305 point_from_point_to_point(arc
->centre
, v
, b
, &bx
, &by
);
5307 coords_on_line(bx
, by
, perpendicular_gradient(point_gradient(GTS_POINT(v
), GTS_POINT(arc
->centre
))), a
, &a0x
, &a0y
, &a1x
, &a1y
);
5309 winddir
= coord_wind(vx(v
), vy(v
), a0x
, a0y
, vx(arc
->centre
), vy(arc
->centre
));
5312 printf("!winddir @ v %f,%f arc->centre %f,%f\n", vx(v
), vy(v
), vx(arc
->centre
), vy(arc
->centre
));
5313 //TODO: fix hack: this shouldn't happen
5323 if(dir
) winddir
= -winddir
;
5325 if(winddir
== arc
->dir
) {
5326 if(!dir
) { arc
->x0
= a0x
; arc
->y0
= a0y
; }
5327 else{ arc
->x1
= a0x
; arc
->y1
= a0y
; }
5329 if(!dir
) { arc
->x0
= a1x
; arc
->y0
= a1y
; }
5330 else{ arc
->x1
= a1x
; arc
->y1
= a1y
; }
5337 // b1 is the projection in the direction of narc, while b2 is the perpendicular projection
5339 arc_ortho_projections(toporouter_arc_t
*arc
, toporouter_arc_t
*narc
, gdouble
*b1
, gdouble
*b2
)
5341 gdouble nax
, nay
, ax
, ay
, alen2
, c
;
5342 gdouble b1x
, b1y
, b2x
, b2y
;
5345 printf("arc c = %f,%f narc c = %f,%f arc->0 = %f,%f\n",
5346 vx(arc
->centre
), vy(arc
->centre
),
5347 vx(narc
->centre
), vy(narc
->centre
),
5351 nax
= vx(narc
->centre
) - vx(arc
->centre
);
5352 nay
= vy(narc
->centre
) - vy(arc
->centre
);
5353 alen2
= pow(nax
,2) + pow(nay
,2);
5356 ax
= arc
->x0
- vx(arc
->centre
);
5357 ay
= arc
->y0
- vy(arc
->centre
);
5360 printf("norm narc = %f,%f - %f\tA=%f,%f\n", nax
, nay
, sqrt(alen2
), ax
, ay
);
5363 c
= ((ax
*nax
)+(ay
*nay
)) / alen2
;
5371 printf("proj = %f,%f perp proj = %f,%f\n", b1x
, b1y
, b2x
, b2y
);
5374 *b1
= sqrt(pow(b1x
,2) + pow(b1y
,2));
5375 *b2
= sqrt(pow(b2x
,2) + pow(b2y
,2));
5380 calculate_arc_to_arc(toporouter_t
*ar
, toporouter_arc_t
*parc
, toporouter_arc_t
*arc
)
5382 gdouble theta
, a
, b
, bx
, by
, a0x
, a0y
, a1x
, a1y
, m
, preva
, prevb
;
5384 toporouter_arc_t
*bigr
, *smallr
;
5386 if(parc
->r
> arc
->r
) {
5387 bigr
= parc
; smallr
= arc
;
5389 bigr
= arc
; smallr
= parc
;
5392 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr
->centre
), vy(bigr
->centre
),
5393 vx(smallr
->centre
), vy(smallr
->centre
));
5396 m
= perpendicular_gradient(point_gradient(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5398 if(bigr
->centre
== smallr
->centre
) {
5400 printf("bigr->centre == smallr->centre @ %f,%f\n", vx(smallr
->centre
), vy(smallr
->centre
));
5403 g_assert(bigr
->centre
!= smallr
->centre
);
5405 if(parc
->dir
== arc
->dir
) {
5406 //export_arc_straight:
5408 theta
= acos((bigr
->r
- smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5409 a
= bigr
->r
* sin(theta
);
5410 b
= bigr
->r
* cos(theta
);
5412 point_from_point_to_point(bigr
->centre
, smallr
->centre
, b
, &bx
, &by
);
5414 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5416 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5418 arc_ortho_projections(parc
, arc
, &prevb
, &preva
);
5419 //#ifdef DEBUG_EXPORT
5422 printf("STRAIGHT:\n");
5423 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr
->centre
), vy(bigr
->centre
),
5424 vx(smallr
->centre
), vy(smallr
->centre
));
5425 printf("theta = %f a = %f b = %f bigrr = %f d = %f po = %f\n", theta
, a
, b
, bigr
->r
,
5426 gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)),
5427 bigr
->r
/ gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5428 printf("bigr-r = %f smallr-r = %f ratio = %f\n",
5429 bigr
->r
, smallr
->r
, (bigr
->r
- smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5430 printf("preva = %f prevb = %f\n\n", preva
, prevb
);
5436 if(bigr
==parc
) winddir
= -winddir
;
5438 if(winddir
== bigr
->dir
) {
5456 a
= smallr
->r
* sin(theta
);
5457 b
= smallr
->r
* cos(theta
);
5460 printf("a = %f b = %f\n", a
, b
);
5462 point_from_point_to_point(smallr
->centre
, bigr
->centre
, -b
, &bx
, &by
);
5464 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5466 if(winddir
== bigr
->dir
) {
5488 theta
= acos((bigr
->r
+ smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5489 a
= bigr
->r
* sin(theta
);
5490 b
= bigr
->r
* cos(theta
);
5492 point_from_point_to_point(bigr
->centre
, smallr
->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
));
5497 //#ifdef DEBUG_EXPORT
5500 printf("theta = %f a = %f b = %f r = %f d = %f po = %f\n", theta
, a
, b
, bigr
->r
+ smallr
->r
,
5501 gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)),
5502 (bigr
->r
+smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5504 printf("bigr centre = %f,%f smallr centre = %f,%f\n\n", vx(bigr
->centre
), vy(bigr
->centre
),
5505 vx(smallr
->centre
), vy(smallr
->centre
));
5507 printf("big wind = %d small wind = %d\n", bigr
->dir
, smallr
->dir
);
5512 smallr->centre->flags |= VERTEX_FLAG_RED;
5513 bigr->centre->flags |= VERTEX_FLAG_GREEN;
5514 //bigr->centre->flags |= VERTEX_FLAG_RED;
5517 for(i=0;i<groupcount();i++) {
5519 sprintf(buffer, "wind%d.png", i);
5520 toporouter_draw_surface(ar, ar->layers[i].surface, buffer, 2096, 2096, 2, NULL, i, NULL);
5528 if(bigr
==parc
) winddir
= -winddir
;
5530 if(winddir
== bigr
->dir
) {
5548 a
= smallr
->r
* sin(theta
);
5549 b
= smallr
->r
* cos(theta
);
5551 point_from_point_to_point(smallr
->centre
, bigr
->centre
, b
, &bx
, &by
);
5553 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5555 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5559 if(bigr
==parc
) winddir
= -winddir
;
5561 if(winddir
== smallr
->dir
) {
5585 export_oproutes(toporouter_t
*ar
, toporouter_oproute_t
*oproute
)
5587 guint layer
= PCB
->LayerGroups
.Entries
[oproute
->layergroup
][0];
5588 guint thickness
= lookup_thickness(oproute
->style
);
5589 guint keepaway
= lookup_keepaway(oproute
->style
);
5590 GList
*arcs
= oproute
->arcs
;
5591 toporouter_arc_t
*arc
, *parc
= NULL
;
5594 ar
->wiring_score
+= export_pcb_drawline(layer
, vx(oproute
->term1
), vy(oproute
->term1
), vx(oproute
->term2
), vy(oproute
->term2
), thickness
, keepaway
);
5599 // calculate_term_to_arc(oproute->term1, TOPOROUTER_ARC(arcs->data), 0, layer);
5602 arc
= TOPOROUTER_ARC(arcs
->data
);
5605 ar
->wiring_score
+= export_pcb_drawarc(layer
, parc
, thickness
, keepaway
);
5606 ar
->wiring_score
+= export_pcb_drawline(layer
, parc
->x1
, parc
->y1
, arc
->x0
, arc
->y0
, thickness
, keepaway
);
5608 ar
->wiring_score
+= export_pcb_drawline(layer
, vx(oproute
->term1
), vy(oproute
->term1
), arc
->x0
, arc
->y0
, thickness
, keepaway
);
5614 ar
->wiring_score
+= export_pcb_drawarc(layer
, arc
, thickness
, keepaway
);
5615 ar
->wiring_score
+= export_pcb_drawline(layer
, arc
->x1
, arc
->y1
, vx(oproute
->term2
), vy(oproute
->term2
), thickness
, keepaway
);
5622 oproute_free(toporouter_oproute_t
*oproute
)
5624 GList
*i
= oproute
->arcs
;
5626 toporouter_arc_t
*arc
= (toporouter_arc_t
*) i
->data
;
5627 if(arc
->centre
->flags
& VERTEX_FLAG_TEMP
)
5628 gts_object_destroy(GTS_OBJECT(arc
->centre
));
5633 g_list_free(oproute
->arcs
);
5638 oproute_calculate_tof(toporouter_oproute_t
*oproute
)
5640 GList
*arcs
= oproute
->arcs
;
5641 toporouter_arc_t
*parc
= NULL
, *arc
;
5646 oproute
->tof
= gts_point_distance(GTS_POINT(oproute
->term1
), GTS_POINT(oproute
->term2
));
5651 arc
= TOPOROUTER_ARC(arcs
->data
);
5654 oproute
->tof
+= arc_angle(parc
) * parc
->r
;
5655 oproute
->tof
+= sqrt(pow(parc
->x1
-arc
->x0
,2)+pow(parc
->y1
-arc
->y0
,2));
5657 oproute
->tof
+= sqrt(pow(arc
->x0
-vx(oproute
->term1
),2)+pow(arc
->y0
-vy(oproute
->term1
),2));
5664 oproute
->tof
+= arc_angle(parc
) * parc
->r
;
5665 oproute
->tof
+= sqrt(pow(arc
->x1
-vx(oproute
->term2
),2)+pow(arc
->y1
-vy(oproute
->term2
),2));
5670 line_line_distance_at_normal(
5671 gdouble line1_x1
, gdouble line1_y1
,
5672 gdouble line1_x2
, gdouble line1_y2
,
5673 gdouble line2_x1
, gdouble line2_y1
,
5674 gdouble line2_x2
, gdouble line2_y2
,
5675 gdouble x
, gdouble y
)
5677 gdouble m1
= perpendicular_gradient(cartesian_gradient(line1_x1
, line1_y1
, line1_x2
, line1_y2
));
5678 gdouble m2
= cartesian_gradient(line2_x1
, line2_y1
, line2_x2
, line2_y2
);
5679 gdouble c1
= (isinf(m1
)) ? x
: y
- (m1
* x
);
5680 gdouble c2
= (isinf(m2
)) ? line2_x1
: line2_y1
- (m2
* line2_x1
);
5684 if(isinf(m2
)) intx
= line2_x1
;
5685 else if(isinf(m1
)) intx
= x
;
5686 else intx
= (c2
- c1
) / (m1
- m2
);
5688 inty
= (isinf(m2
)) ? (m1
* intx
) + c1
: (m2
* intx
) + c2
;
5690 return sqrt(pow(x
-intx
,2)+pow(y
-inty
,2));
5694 calculate_serpintine(gdouble delta
, gdouble r
, gdouble initiala
, gdouble
*a
, guint
*nhalfcycles
)
5696 gdouble lhalfcycle
= 2.*(initiala
-r
)+(M_PI
*r
);
5699 printf("lhalfcycle = %f r = %f\n", lhalfcycle
, r
);
5701 n
= (delta
- M_PI
*r
) / (lhalfcycle
- 2.*r
) + 1;
5702 *a
= (delta
+ 4.*n
*r
- n
*M_PI
*r
+ 4.*r
- M_PI
*r
)/(2.*n
);
5707 oproute_min_spacing(toporouter_oproute_t
*a
, toporouter_oproute_t
*b
)
5709 return lookup_thickness(a
->style
) / 2. + lookup_thickness(b
->style
) / 2. + MAX(lookup_keepaway(a
->style
), lookup_keepaway(b
->style
));
5713 vector_angle(gdouble ox
, gdouble oy
, gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
)
5715 gdouble alen
= sqrt(pow(ax
-ox
,2)+pow(ay
-oy
,2));
5716 gdouble blen
= sqrt(pow(bx
-ox
,2)+pow(by
-oy
,2));
5717 return acos( ((ax
-ox
)*(bx
-ox
)+(ay
-oy
)*(by
-oy
)) / (alen
* blen
) );
5720 toporouter_serpintine_t
*
5721 toporouter_serpintine_new(gdouble x
, gdouble y
, gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, gpointer start
, gdouble halfa
, gdouble
5722 radius
, guint nhalfcycles
)
5724 toporouter_serpintine_t
*serp
= malloc(sizeof(toporouter_serpintine_t
));
5731 serp
->start
= start
;
5732 serp
->halfa
= halfa
;
5733 serp
->radius
= radius
;
5734 serp
->nhalfcycles
= nhalfcycles
;
5739 //#define DEBUG_RUBBERBAND 1
5742 check_non_intersect_vertex(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
,
5743 toporouter_vertex_t
*opv
, gint wind
, gint
*arcwind
, gdouble
*arcr
, guint debug
)
5745 gdouble ms
, line_int_x
, line_int_y
, x
, y
, d
= 0., m
;
5746 gdouble tx0
, ty0
, tx1
, ty1
;
5749 g_assert(pathv
->routingedge
);
5751 if(TOPOROUTER_IS_CONSTRAINT(pathv
->routingedge
)) {
5752 gdouble d
= tvdistance(tedge_v1(pathv
->routingedge
), tedge_v2(pathv
->routingedge
)) / 2.;
5753 ms
= min_spacing(pathv
, arcv
);
5756 ms
= edge_min_spacing(g_list_find(edge_routing(pathv
->routingedge
), pathv
), pathv
->routingedge
, arcv
, debug
);
5760 if(!vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(arcv
), vy(arcv
), &line_int_x
, &line_int_y
)) {
5762 if(coord_distance2(x0
, y0
, line_int_x
, line_int_y
) < coord_distance2(x1
, y1
, line_int_x
, line_int_y
))
5763 { line_int_x
= x0
; line_int_y
= y0
; }else{ line_int_x
= x1
; line_int_y
= y1
; }
5765 m
= perpendicular_gradient(cartesian_gradient(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
));
5767 m
= cartesian_gradient(x0
, y0
, x1
, y1
);
5770 coords_on_line(vx(arcv
), vy(arcv
), m
, 100., &tx0
, &ty0
, &tx1
, &ty1
);
5772 wind1
= coord_wind(tx0
, ty0
, tx1
, ty1
, line_int_x
, line_int_y
);
5773 wind2
= coord_wind(tx0
, ty0
, tx1
, ty1
, vx(opv
), vy(opv
));
5775 if(!wind2
|| wind1
== wind2
) return -1.;
5778 coords_on_line(line_int_x
, line_int_y
, perpendicular_gradient(m
), ms
, &tx0
, &ty0
, &tx1
, &ty1
);
5779 if(coord_distance2(tx0
, ty0
, vx(opv
), vy(opv
)) < coord_distance2(tx1
, ty1
, vx(opv
), vy(opv
)))
5780 { x
= tx0
; y
= ty0
; }else{ x
= tx1
; y
= ty1
; }
5782 toporouter_vertex_t
*parent
= pathv
->parent
, *child
= pathv
->child
;
5783 guint windtests
= 0;
5785 d
= coord_distance(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
);
5786 coord_move_towards_coord_values(line_int_x
, line_int_y
, vx(arcv
), vy(arcv
), ms
+ d
, &x
, &y
);
5788 wind1
= coord_wind(line_int_x
, line_int_y
, x
, y
, vx(parent
), vy(parent
));
5789 wind2
= coord_wind(line_int_x
, line_int_y
, x
, y
, vx(child
), vy(child
));
5790 if(wind1
&& wind2
&& wind1
== wind2
) {
5792 if(windtests
++ == 2) return -1.;
5794 if(parent
->flags
& VERTEX_FLAG_ROUTE
) parent
= parent
->parent
;
5795 if(child
->flags
& VERTEX_FLAG_ROUTE
) child
= child
->child
;
5802 *arcwind
= tvertex_wind(pathv
->parent
, pathv
, arcv
);
5804 #ifdef DEBUG_RUBBERBAND
5806 // printf("non-int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, d + ms,
5807 // vx(arcv), vy(arcv), vx(opv), vy(opv));
5814 check_intersect_vertex(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
,
5815 toporouter_vertex_t
*opv
, gint wind
, gint
*arcwind
, gdouble
*arcr
, guint debug
)
5817 gdouble ms
, line_int_x
, line_int_y
, x
, y
, d
= 0.;
5819 if(TOPOROUTER_IS_CONSTRAINT(pathv
->routingedge
)) {
5820 gdouble d
= tvdistance(tedge_v1(pathv
->routingedge
), tedge_v2(pathv
->routingedge
)) / 2.;
5821 ms
= min_spacing(pathv
, arcv
);
5824 ms
= edge_min_spacing(g_list_find(edge_routing(pathv
->routingedge
), pathv
), pathv
->routingedge
, arcv
, debug
);
5827 if(!vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(arcv
), vy(arcv
), &line_int_x
, &line_int_y
))
5830 d
= coord_distance(line_int_x
, line_int_y
, vx(arcv
), vy(arcv
));
5833 if(d
> ms
- EPSILON
)
5836 coord_move_towards_coord_values(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
, ms
, &x
, &y
);
5839 *arcwind
= tvertex_wind(pathv
->parent
, pathv
, arcv
);
5840 // *arcwind = coord_wind(x0, y0, x, y, x1, y1);
5841 #ifdef DEBUG_RUBBERBAND
5843 // printf("int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, ms - d,
5844 // vx(arcv), vy(arcv), vx(opv), vy(opv));
5850 /* returns non-zero if arc has loops */
5852 check_arc_for_loops(gpointer t1
, toporouter_arc_t
*arc
, gpointer t2
)
5854 gdouble x0
, y0
, x1
, y1
;
5856 if(TOPOROUTER_IS_VERTEX(t1
)) { x0
= vx(TOPOROUTER_VERTEX(t1
)); y0
= vy(TOPOROUTER_VERTEX(t1
)); }
5857 else { x0
= TOPOROUTER_ARC(t1
)->x1
; y0
= TOPOROUTER_ARC(t1
)->y1
; }
5859 if(TOPOROUTER_IS_VERTEX(t2
)) { x1
= vx(TOPOROUTER_VERTEX(t2
)); y1
= vy(TOPOROUTER_VERTEX(t2
)); }
5860 else { x1
= TOPOROUTER_ARC(t2
)->x0
; y1
= TOPOROUTER_ARC(t2
)->y0
; }
5862 if(coord_intersect_prop(x0
, y0
, arc
->x0
, arc
->y0
, arc
->x1
, arc
->y1
, x1
, y1
) ) {
5864 // (arc->x0 > arc->x1 - EPSILON && arc->x0 < arc->x1 + EPSILON &&
5865 // arc->y0 > arc->y1 - EPSILON && arc->y0 < arc->y1 + EPSILON)
5867 #ifdef DEBUG_RUBBERBAND
5868 printf("LOOPS %f %f -> %f %f & %f %f -> %f %f\n", x0
, y0
, arc
->x0
, arc
->y0
, arc
->x1
, arc
->y1
, x1
, y1
);
5875 toporouter_rubberband_arc_t
*
5876 new_rubberband_arc(toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
, gdouble r
, gdouble d
, gint wind
, GList
*list
)
5878 toporouter_rubberband_arc_t
*rba
= malloc(sizeof(toporouter_rubberband_arc_t
));
5889 compare_rubberband_arcs(toporouter_rubberband_arc_t
*a
, toporouter_rubberband_arc_t
*b
)
5890 { return b
->d
- a
->d
; }
5893 free_list_elements(gpointer data
, gpointer user_data
)
5897 /* 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 */
5900 vertex_edge_facing_vertex(GtsVertex *v, gdouble x, gdouble y)
5902 GSList *ts = gts_vertex_triangles(GTS_VERTEX(n), NULL);
5906 GtsTriangle *t = GTS_TRIANGLE(i->data);
5907 GtsEdge *e = gts_triangle_edge_opposite(t, v);
5909 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)) &&
5910 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))
5925 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
)
5927 GSList
*ns
= gts_vertex_neighbors(GTS_VERTEX(v
), NULL
, NULL
);
5932 toporouter_vertex_t
*n
= TOPOROUTER_VERTEX(i
->data
);
5933 gdouble segintx
, seginty
;
5934 if(vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(n
), vy(n
), &segintx
, &seginty
)) {
5935 toporouter_edge_t
*e
= tedge(n
, v
);
5936 gdouble ms
= 0., d
= coord_distance(segintx
, seginty
, vx(n
), vy(n
));
5937 toporouter_vertex_t
*a
, *b
;
5938 GList
*closestnet
= NULL
;
5942 if(v
== tedge_v1(e
)) {
5945 closestnet
= edge_routing(e
);
5949 closestnet
= g_list_last(edge_routing(e
));
5953 ms
= edge_min_spacing(closestnet
, e
, b
, 0);
5954 ms
+= min_oproute_net_spacing(oproute
, TOPOROUTER_VERTEX(closestnet
->data
));
5956 ms
= min_oproute_vertex_spacing(oproute
, b
);
5963 if(vx(v
) == x0
&& vy(v
) == y0
) {
5964 *arcwind
= coord_wind(x0
, y0
, vx(n
), vy(n
), x1
, y1
);
5965 }else if(vx(v
) == x1
&& vy(v
) == y1
) {
5966 *arcwind
= coord_wind(x1
, y1
, vx(n
), vy(n
), x0
, y0
);
5968 fprintf(stderr
, "ERROR: check_adj_pushing_vertex encountered bad vertex v (coordinates don't match)\n");
5983 oproute_rubberband_segment(toporouter_t
*r
, toporouter_oproute_t
*oproute
, GList
*path
, gpointer t1
, gpointer t2
, guint debug
)
5985 gdouble x0
, y0
, x1
, y1
;
5986 toporouter_vertex_t
*v1
, *v2
, *av1
, *av2
; /* v{1,2} are the vertex terminals of the segment, or arc terminal centres */
5987 toporouter_arc_t
*arc1
= NULL
, *arc2
= NULL
, *newarc
= NULL
; /* arc{1,2} are the arc terminals of the segment, if they exist */
5989 GList
*list1
, *list2
;
5992 toporouter_rubberband_arc_t
*max
= NULL
;
5995 gint v1wind
, v2wind
, arcwind
;
5997 if(TOPOROUTER_IS_VERTEX(t1
)) {
5998 v1
= TOPOROUTER_VERTEX(t1
);
5999 x0
= vx(v1
); y0
= vy(v1
);
6001 g_assert(TOPOROUTER_IS_ARC(t1
));
6002 arc1
= TOPOROUTER_ARC(t1
);
6003 v1
= TOPOROUTER_VERTEX(arc1
->v1
);
6008 if(TOPOROUTER_IS_VERTEX(t2
)) {
6009 v2
= TOPOROUTER_VERTEX(t2
);
6010 x1
= vx(v2
); y1
= vy(v2
);
6012 g_assert(TOPOROUTER_IS_ARC(t2
));
6013 arc2
= TOPOROUTER_ARC(t2
);
6014 v2
= TOPOROUTER_VERTEX(arc2
->v2
);
6019 #define TEST_AND_INSERT(z) if(d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v, z, arcr, d, arcwind, i));
6020 #define ARC_CHECKS(z) (!(arc1 && arc1->centre == z) && !(arc2 && arc2->centre == z) && \
6021 !(TOPOROUTER_IS_VERTEX(t1) && z == v1) && !(TOPOROUTER_IS_VERTEX(t2) && z == v2))
6023 if(v1
== v2
|| !i
->next
|| TOPOROUTER_VERTEX(i
->data
) == v2
) return NULL
;
6025 //#ifdef DEBUG_RUBBERBAND
6027 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
));
6028 // if(v1->routingedge) print_edge(v1->routingedge);
6029 // if(v2->routingedge) print_edge(v2->routingedge);
6034 /* check the vectices adjacent to the terminal vectices for push against the segment */
6035 //if(TOPOROUTER_IS_VERTEX(t1)) {
6036 // toporouter_vertex_t *arcc = NULL;
6037 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v1, &arcr, &arcwind, &arcc);
6038 // g_assert(arcc != v1);
6039 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v1, arcc, arcr, d, arcwind, path->next));
6042 //if(TOPOROUTER_IS_VERTEX(t2)) {
6043 // toporouter_vertex_t *arcc = NULL;
6044 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v2, &arcr, &arcwind, &arcc);
6045 // g_assert(arcc != v2);
6046 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v2, arcc, arcr, d, arcwind, g_list_last(path)->prev));
6051 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6053 if(v
== v2
|| v
== v1
|| !v
->routingedge
) break;
6055 #ifdef DEBUG_RUBBERBAND
6057 // printf("current v %f,%f - edge %f,%f %f,%f\n", vx(v), vy(v),
6058 // vx(tedge_v1(v->routingedge)), vy(tedge_v1(v->routingedge)),
6059 // vx(tedge_v2(v->routingedge)), vy(tedge_v2(v->routingedge))
6062 g_assert(v
->routingedge
);
6064 v1wind
= coord_wind(x0
, y0
, x1
, y1
, vx(tedge_v1(v
->routingedge
)), vy(tedge_v1(v
->routingedge
)));
6065 v2wind
= coord_wind(x0
, y0
, x1
, y1
, vx(tedge_v2(v
->routingedge
)), vy(tedge_v2(v
->routingedge
)));
6066 // if(debug) printf("\twinds: %d %d\n", v1wind, v2wind);
6067 if(!v1wind
&& !v2wind
) { i
= i
->next
; continue; }
6070 if(v1wind
&& v2wind
&& v1wind
!= v2wind
) { /* edge is cutting through the current segment */
6072 if(ARC_CHECKS(tedge_v1(v
->routingedge
)) ){ /* edge v1 is not the centre of an arc terminal */
6073 d
= check_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v1(v
->routingedge
), tedge_v2(v
->routingedge
), v1wind
, &arcwind
, &arcr
, debug
);
6074 TEST_AND_INSERT(tedge_v1(v
->routingedge
));
6077 if(ARC_CHECKS(tedge_v2(v
->routingedge
)) ){ /* edge v2 is not the centre of an arc terminal */
6078 d
= check_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v2(v
->routingedge
), tedge_v1(v
->routingedge
), v2wind
, &arcwind
, &arcr
, debug
);
6079 TEST_AND_INSERT(tedge_v2(v
->routingedge
));
6081 }else{ /* edge is on one side of the segment */
6083 if(ARC_CHECKS(tedge_v1(v
->routingedge
)) ){ /* edge v1 is not the centre of an arc terminal */
6084 d
= check_non_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v1(v
->routingedge
), tedge_v2(v
->routingedge
), v1wind
, &arcwind
, &arcr
, debug
);
6085 TEST_AND_INSERT(tedge_v1(v
->routingedge
));
6088 if(ARC_CHECKS(tedge_v2(v
->routingedge
)) ){ /* edge v2 is not the centre of an arc terminal */
6089 d
= check_non_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v2(v
->routingedge
), tedge_v1(v
->routingedge
), v2wind
, &arcwind
, &arcr
, debug
);
6090 TEST_AND_INSERT(tedge_v2(v
->routingedge
));
6097 arcs
= g_list_sort(arcs
, (GCompareFunc
) compare_rubberband_arcs
);
6098 rubberband_insert_maxarc
:
6099 if(!arcs
) return NULL
;
6100 max
= TOPOROUTER_RUBBERBAND_ARC(arcs
->data
);
6102 av2
= max
->pathv
; i
= max
->list
->next
;
6104 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6105 if(v
->routingedge
&& (tedge_v1(v
->routingedge
) == max
->arcv
|| tedge_v2(v
->routingedge
) == max
->arcv
)) {
6106 av2
= v
; i
= i
->next
; continue;
6111 av1
= max
->pathv
; i
= max
->list
->prev
;
6113 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6114 if(v
->routingedge
&& (tedge_v1(v
->routingedge
) == max
->arcv
|| tedge_v2(v
->routingedge
) == max
->arcv
)) {
6115 av1
= v
; i
= i
->prev
; continue;
6119 //#ifdef DEBUG_RUBBERBAND
6121 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
);
6123 newarc
= toporouter_arc_new(oproute
, av1
, av2
, max
->arcv
, max
->r
, max
->wind
);
6125 if(TOPOROUTER_IS_VERTEX(t1
))
6126 calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), newarc
, 0);
6127 else if(calculate_arc_to_arc(r
, TOPOROUTER_ARC(t1
), newarc
)) {
6128 printf("\tERROR: best: r = %f d = %f\n", max
->r
, max
->d
);
6129 printf("\tOPROUTE: %s\n", oproute
->netlist
);
6130 print_vertex(oproute
->term1
);
6131 print_vertex(oproute
->term2
);
6135 if(TOPOROUTER_IS_VERTEX(t2
))
6136 calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), newarc
, 1);
6137 else if(calculate_arc_to_arc(r
, newarc
, TOPOROUTER_ARC(t2
))) {
6138 printf("\tERROR: best: r = %f d = %f\n", max
->r
, max
->d
);
6139 printf("\tOPROUTE: %s\n", oproute
->netlist
);
6140 print_vertex(oproute
->term1
);
6141 print_vertex(oproute
->term2
);
6145 //if(check_arc_for_loops(t1, newarc, t2)) {
6146 // if(arc1 && arc2) calculate_arc_to_arc(r, arc1, arc2);
6147 // else if(arc1) calculate_term_to_arc(TOPOROUTER_VERTEX(t2), arc1, 1);
6148 // else if(arc2) calculate_term_to_arc(TOPOROUTER_VERTEX(t1), arc2, 0);
6150 //#ifdef DEBUG_RUBBERBAND
6151 // printf("REMOVING NEW ARC @ %f,%f\n", vx(newarc->centre), vy(newarc->centre));
6152 // //TODO: properly remove newarc
6155 // arcs = g_list_remove(arcs, max);
6157 // goto rubberband_insert_maxarc;
6161 list1
= oproute_rubberband_segment(r
, oproute
, path
, t1
, newarc
, debug
);
6162 list2
= oproute_rubberband_segment(r
, oproute
, i
->next
, newarc
, t2
, debug
);
6165 GList
*list
= g_list_last(list1
);
6166 toporouter_arc_t
*testarc
= TOPOROUTER_ARC(list
->data
);
6167 toporouter_arc_t
*parc
= list
->prev
? TOPOROUTER_ARC(list
->prev
->data
) : arc1
;
6168 gdouble px
= parc
? parc
->x1
: vx(TOPOROUTER_VERTEX(t1
)), py
= parc
? parc
->y1
: vy(TOPOROUTER_VERTEX(t1
));
6170 if(coord_intersect_prop(px
, py
, testarc
->x0
, testarc
->y0
, testarc
->x1
, testarc
->y1
, newarc
->x0
, newarc
->y0
)) {
6171 list1
= g_list_remove(list1
, testarc
);
6172 if(parc
) calculate_arc_to_arc(r
, parc
, newarc
);
6173 else calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), newarc
, 0);
6174 //#ifdef DEBUG_RUBBERBAND
6176 printf("REMOVING ARC @ %f,%f\n", vx(testarc
->centre
), vy(testarc
->centre
));
6181 toporouter_arc_t
*testarc
= TOPOROUTER_ARC(list2
->data
);
6182 toporouter_arc_t
*narc
= list2
->next
? TOPOROUTER_ARC(list2
->next
->data
) : arc2
;
6183 gdouble nx
= narc
? narc
->x0
: vx(TOPOROUTER_VERTEX(t2
)), ny
= narc
? narc
->y0
: vy(TOPOROUTER_VERTEX(t2
));
6185 if(coord_intersect_prop(newarc
->x1
, newarc
->y1
, testarc
->x0
, testarc
->y0
, testarc
->x1
, testarc
->y1
, nx
, ny
)) {
6186 list2
= g_list_remove(list2
, testarc
);
6187 if(narc
) calculate_arc_to_arc(r
, newarc
, narc
);
6188 else calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), newarc
, 1);
6190 //#ifdef DEBUG_RUBBERBAND
6192 printf("REMOVING ARC @ %f,%f\n", vx(testarc
->centre
), vy(testarc
->centre
));
6197 g_list_foreach(arcs
, free_list_elements
, NULL
);
6200 return g_list_concat(list1
, g_list_prepend(list2
, newarc
));
6204 oproute_check_all_loops(toporouter_t
*r
, toporouter_oproute_t
*oproute
)
6210 t1
= oproute
->term1
;
6213 toporouter_arc_t
*arc
= TOPOROUTER_ARC(i
->data
);
6214 gpointer t2
= i
->next
? i
->next
->data
: oproute
->term2
;
6216 if(check_arc_for_loops(t1
, arc
, t2
)) {
6218 if(TOPOROUTER_IS_ARC(t1
) && TOPOROUTER_IS_ARC(t2
))
6219 calculate_arc_to_arc(r
, TOPOROUTER_ARC(t1
), TOPOROUTER_ARC(t2
));
6220 else if(TOPOROUTER_IS_ARC(t1
))
6221 calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), TOPOROUTER_ARC(t1
), 1);
6222 else if(TOPOROUTER_IS_ARC(t2
))
6223 calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), TOPOROUTER_ARC(t2
), 0);
6225 oproute
->arcs
= g_list_remove(oproute
->arcs
, arc
);
6226 goto loopcheck_restart
;
6237 opposite_triangle(GtsTriangle
*t
, toporouter_edge_t
*e
)
6239 GSList
*i
= GTS_EDGE(e
)->triangles
;
6244 if(GTS_TRIANGLE(i
->data
) != t
) return GTS_TRIANGLE(i
->data
);
6253 speccut_edge_routing_from_edge(GList
*i
, toporouter_edge_t
*e
)
6256 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
6258 if(!(curv
->flags
& VERTEX_FLAG_TEMP
)) {
6259 toporouter_vertex_t
*newv
= tvertex_intersect(curv
, curv
->parent
, tedge_v1(e
), tedge_v2(e
));
6261 // printf("\nCURV:\n");
6262 // print_vertex(curv);
6264 // printf("CURV child:\n");
6266 // print_vertex(curv->child);
6268 // printf("NULL\n");
6270 // printf("CURV parent:\n");
6272 // print_vertex(curv->parent);
6274 // printf("NULL\n");
6278 newv
->flags
|= VERTEX_FLAG_ROUTE
;
6279 newv
->flags
|= VERTEX_FLAG_SPECCUT
;
6280 e
->routing
= g_list_insert_sorted_with_data(e
->routing
, newv
, routing_edge_insert
, e
);
6281 newv
->route
= curv
->route
;
6282 newv
->oproute
= curv
->oproute
;
6283 newv
->routingedge
= e
;
6284 GTS_POINT(newv
)->z
= vz(curv
);
6286 newv
->parent
= curv
->parent
;
6289 // curv->parent = newv;
6291 index
= g_list_index(newv
->route
->path
, curv
);
6293 newv
->route
->path
= g_list_insert(newv
->route
->path
, newv
, index
);
6296 if(newv
->oproute
) newv
->oproute
->path
= newv
->route
->path
;
6299 if(!(curv
->child
->routingedge
)) {
6300 newv
= tvertex_intersect(curv
, curv
->child
, tedge_v1(e
), tedge_v2(e
));
6304 newv
->flags
|= VERTEX_FLAG_ROUTE
;
6305 newv
->flags
|= VERTEX_FLAG_SPECCUT
;
6306 e
->routing
= g_list_insert_sorted_with_data(e
->routing
, newv
, routing_edge_insert
, e
);
6307 newv
->route
= curv
->route
;
6308 newv
->oproute
= curv
->oproute
;
6309 newv
->routingedge
= e
;
6310 GTS_POINT(newv
)->z
= vz(curv
);
6312 newv
->parent
= curv
;
6313 newv
->child
= curv
->child
;
6315 // curv->child = newv;
6317 index
= g_list_index(newv
->route
->path
, curv
);
6319 newv
->route
->path
= g_list_insert(newv
->route
->path
, newv
, index
+1);
6322 if(newv
->oproute
) newv
->oproute
->path
= newv
->route
->path
;
6334 speccut_edge_patch_links(toporouter_edge_t
*e
)
6336 GList
*i
= e
->routing
;
6338 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6339 v
->parent
->child
= v
;
6340 v
->child
->parent
= v
;
6346 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
)
6348 GtsTriangle
*t
, *opt
;
6349 toporouter_vertex_t
*opv
, *opv2
;
6350 toporouter_edge_t
*ope1
, *ope2
;
6351 gdouble cap
, flow
, line_int_x
, line_int_y
;
6353 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
6356 if(!(t
= gts_triangle_use_edges(GTS_EDGE(e
), GTS_EDGE(e1
), GTS_EDGE(e2
)))) {
6357 printf("check_speccut: NULL t\n");
6361 if(!(opt
= opposite_triangle(t
, e
))) {
6362 printf("check_speccut: NULL opt\n");
6366 if(!(opv
= segment_common_vertex(GTS_SEGMENT(e1
), GTS_SEGMENT(e2
)))) {
6367 printf("check_speccut: NULL opv\n");
6371 if(!(opv2
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(opt
, GTS_EDGE(e
))))) {
6372 printf("check_speccut: NULL opv2\n");
6376 //TODO: shifting it out of the way would be better
6378 GList
*i
= e
->routing
;
6380 toporouter_vertex_t
*ev
= TOPOROUTER_VERTEX(i
->data
);
6381 if(!tvertex_wind(opv
, ev
, opv2
)) return 0;
6387 ope1
= tedge(opv2
, tedge_v1(e
));
6388 ope2
= tedge(opv2
, tedge_v2(e
));
6390 if(!tvertex_wind(opv2
, tedge_v1(e
), opv
)) return 0;
6391 if(!tvertex_wind(opv2
, tedge_v2(e
), opv
)) return 0;
6393 if(!vertex_line_normal_intersection(
6394 vx(tedge_v1(e
)), vy(tedge_v1(e
)),
6395 vx(tedge_v2(e
)), vy(tedge_v2(e
)),
6397 &line_int_x
, &line_int_y
)) return 0;
6401 //if(vertex_line_normal_intersection(tev1x(e), tev1y(e), tev2x(e), tev2y(e), vx(opv), vy(opv), &line_int_x, &line_int_y))
6404 g_assert(opt
&& opv2
);
6406 /* this is just temp, for the purposes of determining flow */
6407 if(tedge_v1(ope1
) == opv2
) {
6408 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6409 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_append(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6411 ope1
->routing
= g_list_append(ope1
->routing
, v1
);
6413 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6414 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_prepend(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6416 ope1
->routing
= g_list_prepend(ope1
->routing
, v1
);
6419 cap
= triangle_interior_capacity(opt
, opv2
);
6420 flow
= flow_from_edge_to_edge(opt
, tedge(opv2
, tedge_v1(e
)), tedge(opv2
, tedge_v2(e
)), opv2
, v1
);
6422 /* temp v1 removed */
6423 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6424 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6426 ope1
->routing
= g_list_remove(ope1
->routing
, v1
);
6429 toporouter_edge_t
*newe
= TOPOROUTER_EDGE(gts_edge_new(GTS_EDGE_CLASS(toporouter_edge_class()), GTS_VERTEX(opv
), GTS_VERTEX(opv2
)));
6431 speccut_edge_routing_from_edge(edge_routing(e1
), newe
);
6432 speccut_edge_routing_from_edge(edge_routing(e2
), newe
);
6433 speccut_edge_routing_from_edge(edge_routing(ope1
), newe
);
6434 speccut_edge_routing_from_edge(edge_routing(ope2
), newe
);
6436 speccut_edge_patch_links(newe
);
6438 printf("SPECCUT WITH v %f,%f for seg %f,%f %f,%f detected\n", vx(opv2), vy(opv2),
6441 printf("\tflow %f cap %f\n", flow, cap);
6444 if(newe
->routing
) return 1;
6453 oproute_path_speccut(toporouter_oproute_t
*oproute
)
6456 toporouter_vertex_t
*pv
;
6457 path_speccut_restart
:
6461 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6464 if(pv
&& (v
->routingedge
|| pv
->routingedge
) && !(pv
->flags
& VERTEX_FLAG_SPECCUT
) && !(v
->flags
& VERTEX_FLAG_SPECCUT
)) {
6466 if(!v
->routingedge
) {
6467 if(check_speccut(oproute
, pv
, v
, tedge(tedge_v1(pv
->routingedge
), v
), pv
->routingedge
, tedge(tedge_v2(pv
->routingedge
), v
)))
6468 goto path_speccut_restart
;
6469 if(check_speccut(oproute
, pv
, v
, tedge(tedge_v2(pv
->routingedge
), v
), pv
->routingedge
, tedge(tedge_v1(pv
->routingedge
), v
)))
6470 goto path_speccut_restart
;
6471 }else if(!pv
->routingedge
) {
6472 if(check_speccut(oproute
, v
, pv
, tedge(tedge_v1(v
->routingedge
), pv
), v
->routingedge
, tedge(tedge_v2(v
->routingedge
), pv
)))
6473 goto path_speccut_restart
;
6474 if(check_speccut(oproute
, v
, pv
, tedge(tedge_v2(v
->routingedge
), pv
), v
->routingedge
, tedge(tedge_v1(v
->routingedge
), pv
)))
6475 goto path_speccut_restart
;
6477 toporouter_vertex_t
*v1
= NULL
, *v2
= NULL
;
6478 edges_third_edge(GTS_SEGMENT(v
->routingedge
), GTS_SEGMENT(pv
->routingedge
), &v1
, &v2
);
6479 if(check_speccut(oproute
, v
, pv
, tedge(v1
, v2
), v
->routingedge
, pv
->routingedge
))
6480 goto path_speccut_restart
;
6492 toporouter_oproute_t
*
6493 oproute_rubberband(toporouter_t
*r
, GList
*path
)
6495 toporouter_oproute_t
*oproute
= malloc(sizeof(toporouter_oproute_t
));
6499 oproute
->term1
= TOPOROUTER_VERTEX(path
->data
);
6500 oproute
->term2
= TOPOROUTER_VERTEX(g_list_last(path
)->data
);
6501 oproute
->arcs
= NULL
;
6502 oproute
->style
= vertex_bbox(oproute
->term1
)->cluster
->netlist
->style
;
6503 oproute
->netlist
= vertex_bbox(oproute
->term1
)->cluster
->netlist
->netlist
;
6504 oproute
->layergroup
= vz(oproute
->term1
);
6505 oproute
->path
= path
;
6506 oproute
->serp
= NULL
;
6508 oproute
->term1
->parent
= NULL
;
6509 oproute
->term2
->child
= NULL
;
6511 path_set_oproute(path
, oproute
);
6513 // if(!strcmp(oproute->netlist, " unnamed_net1"))
6514 oproute_path_speccut(oproute
);
6516 #ifdef DEBUG_RUBBERBAND
6517 if(!strcmp(oproute
->netlist
, " VCC3V3") && vx(oproute
->term1
) == 95700. && vy(oproute
->term1
) == 70800. &&
6518 vx(oproute
->term2
) == 196700. && vy(oproute
->term2
) == 67300.)
6520 // printf("OPROUTE %s - %f,%f %f,%f\n", oproute->netlist, vx(oproute->term1), vy(oproute->term1), vx(oproute->term2), vy(oproute->term2));
6521 // print_path(path);
6522 oproute
->arcs
= oproute_rubberband_segment(r
, oproute
, path
, oproute
->term1
, oproute
->term2
, 1);
6525 oproute
->arcs
= oproute_rubberband_segment(r
, oproute
, path
, oproute
->term1
, oproute
->term2
, 0);
6527 oproute_check_all_loops(r
, oproute
);
6533 toporouter_export(toporouter_t
*r
)
6535 GList
*i
= r
->routednets
;
6536 GList
*oproutes
= NULL
;
6539 toporouter_route_t
*routedata
= TOPOROUTER_ROUTE(i
->data
);
6540 toporouter_oproute_t
*oproute
= oproute_rubberband(r
, routedata
->path
);
6541 oproutes
= g_list_prepend(oproutes
, oproute
);
6547 toporouter_oproute_t
*oproute
= (toporouter_oproute_t
*) i
->data
;
6548 export_oproutes(r
, oproute
);
6549 oproute_free(oproute
);
6553 Message(_("Reticulating splines... successful\n\n"));
6554 Message(_("Wiring cost: %f inches\n"), r
->wiring_score
/ 1000.);
6555 printf("Wiring cost: %f inches\n", r
->wiring_score
/ 1000.);
6557 g_list_free(oproutes
);
6561 toporouter_route_t
*
6562 routedata_create(void)
6564 toporouter_route_t
*routedata
= malloc(sizeof(toporouter_route_t
));
6565 routedata
->netlist
= NULL
;
6566 routedata
->alltemppoints
= NULL
;
6567 routedata
->path
= NULL
;
6568 routedata
->curpoint
= NULL
;
6569 routedata
->pscore
= routedata
->score
= 0.;
6570 routedata
->flags
= 0;
6571 routedata
->src
= routedata
->dest
= NULL
;
6572 routedata
->psrc
= routedata
->pdest
= NULL
;
6573 routedata
->ppath
= routedata
->topopath
= NULL
;
6575 routedata
->ppathindices
= NULL
;
6577 routedata
->destvertices
= routedata
->srcvertices
= NULL
;
6582 print_routedata(toporouter_route_t *routedata)
6584 GList *srcvertices = cluster_vertices(routedata->src);
6585 GList *destvertices = cluster_vertices(routedata->dest);
6587 printf("ROUTEDATA:\n");
6588 printf("SRCVERTICES:\n");
6589 print_vertices(srcvertices);
6590 printf("DESTVERTICES:\n");
6591 print_vertices(destvertices);
6593 g_list_free(srcvertices);
6594 g_list_free(destvertices);
6597 toporouter_route_t
*
6598 import_route(toporouter_t
*r
, RatType
*line
)
6600 toporouter_route_t
*routedata
= routedata_create();
6602 routedata
->src
= cluster_find(r
, line
->Point1
.X
, line
->Point1
.Y
, line
->group1
);
6603 routedata
->dest
= cluster_find(r
, line
->Point2
.X
, line
->Point2
.Y
, line
->group2
);
6605 if(!routedata
->src
) printf("couldn't locate src\n");
6606 if(!routedata
->dest
) printf("couldn't locate dest\n");
6608 if(!routedata
->src
|| !routedata
->dest
) {
6609 printf("PROBLEM: couldn't locate rat src or dest for rat %d,%d,%d -> %d,%d,%d\n",
6610 line
->Point1
.X
, line
->Point1
.Y
, line
->group1
, line
->Point2
.X
, line
->Point2
.Y
, line
->group2
);
6615 routedata
->netlist
= routedata
->src
->netlist
;
6617 g_assert(routedata
->src
->netlist
== routedata
->dest
->netlist
);
6619 g_ptr_array_add(r
->routes
, routedata
);
6620 g_ptr_array_add(routedata
->netlist
->routes
, routedata
);
6622 r
->failednets
= g_list_prepend(r
->failednets
, routedata
);
6628 delete_route(toporouter_route_t
*routedata
, guint destroy
)
6630 GList
*i
= routedata
->path
;
6631 toporouter_vertex_t
*pv
= NULL
;
6634 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6638 if(tv
&& pv
&& !(tv
->flags
& VERTEX_FLAG_ROUTE
) && !(pv
->flags
& VERTEX_FLAG_ROUTE
)) {
6639 toporouter_edge_t
*e
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(tv
), GTS_VERTEX(pv
)));
6641 if(e
&& (e
->flags
& EDGE_FLAG_DIRECTCONNECTION
)) {
6642 e
->flags
^= EDGE_FLAG_DIRECTCONNECTION
;
6649 i
= routedata
->path
;
6651 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6656 if(tv
->routingedge
) {
6657 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6658 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
6660 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
6661 if(destroy
) gts_object_destroy ( GTS_OBJECT(tv
) );
6667 if(routedata
->path
) g_list_free(routedata
->path
);
6668 routedata
->path
= NULL
;
6669 routedata
->curpoint
= NULL
;
6670 routedata
->score
= INFINITY
;
6671 routedata
->alltemppoints
= NULL
;
6674 /* remove route can be later reapplied */
6676 remove_route(GList
*path
)
6681 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6686 // if(tv->flags & VERTEX_FLAG_ROUTE) g_assert(tv->route == routedata);
6688 if(tv
->routingedge
) {
6690 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6691 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
6693 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
6701 apply_route(GList
*path
, toporouter_route_t
*routedata
)
6704 toporouter_vertex_t
*pv
= NULL
;
6711 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6713 if(tv
->routingedge
) {
6714 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6715 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_insert_sorted_with_data(
6716 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
,
6718 routing_edge_insert
,
6721 tv
->routingedge
->routing
= g_list_insert_sorted_with_data(
6722 tv
->routingedge
->routing
,
6724 routing_edge_insert
,
6735 if(tv
->flags
& VERTEX_FLAG_ROUTE
) g_assert(tv
->route
== routedata
);
6741 TOPOROUTER_VERTEX(path
->data
)->parent
= NULL
;
6749 compare_routedata_ascending(gconstpointer a
, gconstpointer b
)
6751 toporouter_route_t
*ra
= (toporouter_route_t
*)a
;
6752 toporouter_route_t
*rb
= (toporouter_route_t
*)b
;
6753 return ra
->score
- rb
->score
;
6757 print_costmatrix(gdouble
*m
, guint n
)
6759 printf("COST MATRIX:\n");
6760 for(guint i
= 0;i
<n
;i
++) {
6761 for(guint j
= 0;j
<n
;j
++) {
6762 printf("%f ", m
[(i
*n
)+j
]);
6770 init_cost_matrix(gdouble
*m
, guint n
)
6772 for(guint i
=0;i
<n
;i
++) {
6773 for(guint j
=0;j
<n
;j
++) {
6774 m
[(i
*n
)+j
] = INFINITY
;
6780 toporouter_netscore_t
*
6781 netscore_create(toporouter_t
*r
, toporouter_route_t
*routedata
, guint n
, guint id
)
6783 toporouter_netscore_t
*netscore
= malloc(sizeof(toporouter_netscore_t
));
6784 GList
*path
= route(r
, routedata
, 0);
6788 netscore
->routedata
= routedata
;
6789 routedata
->detourscore
= netscore
->score
= routedata
->score
;
6791 if(!finite(routedata
->detourscore
)) {
6792 printf("WARNING: !finite(detourscore)\n");
6793 print_cluster(routedata
->src
);
6794 print_cluster(routedata
->dest
);
6798 netscore
->pairwise_nodetour
= malloc(n
* sizeof(guint
));
6800 for(guint i
=0;i
<n
;i
++) {
6801 netscore
->pairwise_nodetour
[i
] = 0;
6804 netscore
->pairwise_detour_sum
= 0.;
6805 netscore
->pairwise_fails
= 0;
6810 routedata
->topopath
= g_list_copy(routedata
->path
);
6811 delete_route(routedata
, 0);
6818 netscore_destroy(toporouter_netscore_t
*netscore
)
6820 free(netscore
->pairwise_nodetour
);
6825 print_netscores(GPtrArray
* netscores
)
6827 printf("NETSCORES: \n\n");
6828 printf(" %15s %15s %15s\n----------------------------------------------------\n", "Score", "Detour Sum", "Pairwise Fails");
6830 for(toporouter_netscore_t
**i
= (toporouter_netscore_t
**) netscores
->pdata
; i
< (toporouter_netscore_t
**) netscores
->pdata
+ netscores
->len
; i
++) {
6831 printf("%4d %15f %15f %15d %15x\n", (*i
)->id
, (*i
)->score
, (*i
)->pairwise_detour_sum
, (*i
)->pairwise_fails
, (unsigned int)*i
);
6837 netscore_pairwise_calculation(toporouter_netscore_t
*netscore
, GPtrArray
*netscores
)
6839 toporouter_netscore_t
**netscores_base
= (toporouter_netscore_t
**) (netscores
->pdata
);
6840 toporouter_route_t
*temproutedata
= routedata_create();
6842 //route(netscore->r, netscore->routedata, 0);
6843 apply_route(netscore
->routedata
->topopath
, netscore
->routedata
);
6845 for(toporouter_netscore_t
**i
= netscores_base
; i
< netscores_base
+ netscores
->len
; i
++) {
6847 if(!netscore
->pairwise_nodetour
[i
-netscores_base
] && *i
!= netscore
&& (*i
)->routedata
->netlist
!= netscore
->routedata
->netlist
) {
6849 temproutedata
->src
= (*i
)->routedata
->src
;
6850 temproutedata
->dest
= (*i
)->routedata
->dest
;
6852 route(netscore
->r
, temproutedata
, 0);
6854 if(temproutedata
->score
== (*i
)->score
) {
6855 netscore
->pairwise_nodetour
[i
-netscores_base
] = 1;
6856 (*i
)->pairwise_nodetour
[netscore
->id
] = 1;
6858 if(!finite(temproutedata
->score
)) {
6859 netscore
->pairwise_fails
+= 1;
6861 netscore
->pairwise_detour_sum
+= temproutedata
->score
- (*i
)->score
;
6864 delete_route(temproutedata
, 1);
6869 // delete_route(netscore->routedata, 1);
6870 remove_route(netscore
->routedata
->topopath
);
6872 free(temproutedata
);
6876 netscore_pairwise_size_compare(toporouter_netscore_t
**a
, toporouter_netscore_t
**b
)
6878 // infinite scores are last
6879 if(!finite((*a
)->score
) && !finite((*b
)->score
)) return 0;
6880 if(finite((*a
)->score
) && !finite((*b
)->score
)) return -1;
6881 if(finite((*b
)->score
) && !finite((*a
)->score
)) return 1;
6883 // order by pairwise fails
6884 if((*a
)->pairwise_fails
< (*b
)->pairwise_fails
) return -1;
6885 if((*b
)->pairwise_fails
< (*a
)->pairwise_fails
) return 1;
6887 // order by pairwise detour
6888 if((*a
)->pairwise_detour_sum
< (*b
)->pairwise_detour_sum
) return -1;
6889 if((*b
)->pairwise_detour_sum
< (*a
)->pairwise_detour_sum
) return 1;
6892 if((*a
)->score
< (*b
)->score
) return -1;
6893 if((*b
)->score
< (*a
)->score
) return 1;
6899 netscore_pairwise_compare(toporouter_netscore_t
**a
, toporouter_netscore_t
**b
)
6901 // infinite scores are last
6902 if(!finite((*a
)->score
) && !finite((*b
)->score
)) return 0;
6903 if(finite((*a
)->score
) && !finite((*b
)->score
)) return -1;
6904 if(finite((*b
)->score
) && !finite((*a
)->score
)) return 1;
6906 // order by pairwise fails
6907 if((*a
)->pairwise_fails
< (*b
)->pairwise_fails
) return -1;
6908 if((*b
)->pairwise_fails
< (*a
)->pairwise_fails
) return 1;
6910 // order by pairwise detour
6911 if((*a
)->pairwise_detour_sum
< (*b
)->pairwise_detour_sum
) return -1;
6912 if((*b
)->pairwise_detour_sum
< (*a
)->pairwise_detour_sum
) return 1;
6918 order_nets_preroute_greedy(toporouter_t
*r
, GList
*nets
, GList
**rnets
)
6920 gint len
= g_list_length(nets
);
6921 GPtrArray
* netscores
= g_ptr_array_sized_new(len
);
6922 guint failcount
= 0;
6925 g_ptr_array_add(netscores
, netscore_create(r
, TOPOROUTER_ROUTE(nets
->data
), len
, failcount
++));
6931 g_ptr_array_foreach(netscores
, (GFunc
) netscore_pairwise_calculation
, netscores
);
6933 g_ptr_array_sort(netscores
, (GCompareFunc
) r
->netsort
);
6935 #ifdef DEBUG_ORDERING
6936 print_netscores(netscores
);
6940 FOREACH_NETSCORE(netscores
) {
6941 *rnets
= g_list_prepend(*rnets
, netscore
->routedata
);
6942 if(!finite(netscore
->score
)) failcount
++;
6943 netscore_destroy(netscore
);
6946 g_ptr_array_free(netscores
, TRUE
);
6951 toporouter_vertex_t
*
6952 edge_closest_vertex(toporouter_edge_t
*e
, toporouter_vertex_t
*v
)
6954 GList
*i
= v
->routingedge
? edge_routing(v
->routingedge
) : NULL
;
6955 gdouble closestd
= 0.;
6956 toporouter_vertex_t
*closestv
= NULL
;
6959 toporouter_vertex_t
*ev
= TOPOROUTER_VERTEX(i
->data
);
6960 gdouble tempd
= gts_point_distance2(GTS_POINT(ev
), GTS_POINT(v
));
6962 if(!closestv
|| (tempd
< closestd
)) {
6974 snapshot(toporouter_t
*r
, char *name
, GList
*datas
)
6979 for(i
=0;i
<groupcount();i
++) {
6981 sprintf(buffer
, "route-%s-%d.png", name
, i
);
6982 toporouter_draw_surface(r
, r
->layers
[i
].surface
, buffer
, 2048, 2048, 2, datas
, i
, NULL
);
6990 route_conflict(toporouter_t *r, toporouter_route_t *route, guint *n)
6992 GList *i = route->path;
6993 toporouter_vertex_t *pv = NULL;
6997 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
6998 if(pv && vz(v) == vz(pv))
6999 cost += vertices_routing_conflict_cost(r, v, pv, n);
7008 route_conflicts(toporouter_route_t
*route
)
7010 GList
*conflicts
= NULL
, *i
= route
->path
;
7011 toporouter_vertex_t
*pv
= NULL
;
7014 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7016 if(pv
&& vz(pv
) == vz(v
)) {
7017 GList
*temp
= vertices_routing_conflicts(pv
, v
), *j
;
7021 toporouter_route_t
*conroute
= TOPOROUTER_ROUTE(j
->data
);
7022 if(!g_list_find(conflicts
, conroute
))
7023 conflicts
= g_list_prepend(conflicts
, conroute
);
7027 if(temp
) g_list_free(temp
);
7037 spread_edge(gpointer item
, gpointer data
)
7039 toporouter_edge_t
*e
= TOPOROUTER_EDGE(item
);
7040 toporouter_vertex_t
*v
;
7044 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
7046 i
= edge_routing(e
);
7048 if(!g_list_length(i
)) return 0;
7050 if(g_list_length(i
) == 1) {
7051 v
= TOPOROUTER_VERTEX(i
->data
);
7052 GTS_POINT(v
)->x
= (vx(edge_v1(e
)) + vx(edge_v2(e
))) / 2.;
7053 GTS_POINT(v
)->y
= (vy(edge_v1(e
)) + vy(edge_v2(e
))) / 2.;
7057 s
= spacing
= (gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) ) / (g_list_length(i
) + 1);
7060 v
= TOPOROUTER_VERTEX(i
->data
);
7061 vertex_move_towards_vertex_values(edge_v1(e
), edge_v2(e
), s
, &(GTS_POINT(v
)->x
), &(GTS_POINT(v
)->y
));
7071 route_checkpoint(toporouter_route_t
*route
, toporouter_route_t
*temproute
)
7073 GList
*i
= g_list_last(route
->path
);
7074 gint n
= g_list_length(route
->path
);
7076 if(route
->ppathindices
) free(route
->ppathindices
);
7077 route
->ppathindices
= malloc(sizeof(gint
)*n
);
7081 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7084 if(v
->routingedge
) {
7085 GList
*j
= g_list_find(edge_routing(v
->routingedge
), v
)->prev
;
7086 gint tempindex
= g_list_index(edge_routing(v
->routingedge
), v
);
7089 if(TOPOROUTER_VERTEX(j
->data
)->route
== temproute
) tempindex
--;
7093 route
->ppathindices
[n
] = tempindex
;
7095 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
7096 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
);
7098 v
->routingedge
->routing
= g_list_remove(v
->routingedge
->routing
, v
);
7104 route
->pscore
= route
->score
;
7105 route
->ppath
= route
->path
;
7106 remove_route(route
->path
);
7108 route
->psrc
= route
->src
;
7109 route
->pdest
= route
->dest
;
7110 //route->src->pc = route->src->c;
7111 //route->dest->pc = route->dest->c;
7115 route_restore(toporouter_route_t
*route
)
7118 toporouter_vertex_t
*pv
= NULL
;
7121 g_assert(route
->ppath
);
7122 g_assert(route
->ppathindices
);
7124 route
->path
= route
->ppath
;
7127 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7129 if(v
->routingedge
) {
7130 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
7131 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_insert(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
, route
->ppathindices
[n
]);
7133 v
->routingedge
->routing
= g_list_insert(v
->routingedge
->routing
, v
, route
->ppathindices
[n
]);
7135 // space_edge(v->routingedge, NULL);
7148 route
->score
= route
->pscore
;
7149 route
->src
= route
->psrc
;
7150 route
->dest
= route
->pdest
;
7151 //route->src->c = route->src->pc;
7152 //route->dest->c = route->dest->pc;
7157 cluster_merge(toporouter_route_t
*routedata
)
7159 gint oldc
= routedata
->dest
->c
, newc
= routedata
->src
->c
;
7161 FOREACH_CLUSTER(routedata
->netlist
->clusters
) {
7162 if(cluster
->c
== oldc
)
7169 netlist_recalculate(toporouter_netlist_t
*netlist
, GList
*ignore
)
7171 GList
*i
= g_list_last(netlist
->routed
);
7172 gint n
= netlist
->clusters
->len
-1;
7174 FOREACH_CLUSTER(netlist
->clusters
) {
7179 if(!ignore
|| !g_list_find(ignore
, i
->data
)) cluster_merge(TOPOROUTER_ROUTE(i
->data
));
7186 netlists_recalculate(GList
*netlists
, GList
*ignore
)
7188 GList
*i
= netlists
;
7190 netlist_recalculate(TOPOROUTER_NETLIST(i
->data
), ignore
);
7196 netlists_rollback(GList
*netlists
)
7198 // netlists_recalculate(netlists, NULL);
7200 toporouter_netlist_t
*netlist
= TOPOROUTER_NETLIST(netlists
->data
);
7202 FOREACH_CLUSTER(netlist
->clusters
) {
7203 cluster
->c
= cluster
->pc
;
7206 netlists
= netlists
->next
;
7211 print_netlist(toporouter_netlist_t
*netlist
)
7214 printf("NETLIST %s: ", netlist
->netlist
);
7216 FOREACH_CLUSTER(netlist
->clusters
) {
7217 printf("%d ", cluster
->c
);
7223 #define REMOVE_ROUTING(x) x->netlist->routed = g_list_remove(x->netlist->routed, x); \
7224 r->routednets = g_list_remove(r->routednets, x); \
7225 r->failednets = g_list_prepend(r->failednets, x)
7227 #define INSERT_ROUTING(x) x->netlist->routed = g_list_prepend(x->netlist->routed, x); \
7228 r->routednets = g_list_prepend(r->routednets, x); \
7229 r->failednets = g_list_remove(r->failednets, x)
7232 roar_route(toporouter_t
*r
, toporouter_route_t
*routedata
, gint threshold
)
7235 GList
*netlists
= NULL
, *routed
= NULL
;
7237 g_assert(!routedata
->path
);
7239 if(routedata
->src
->c
== routedata
->dest
->c
) {
7240 printf("ERROR: attempt to route already complete route\n");
7241 g_assert(routedata
->src
->c
!= routedata
->dest
->c
);
7244 routedata
->src
->pc
= routedata
->src
->c
;
7245 routedata
->dest
->pc
= routedata
->dest
->c
;
7246 routedata
->psrc
= routedata
->src
;
7247 routedata
->pdest
= routedata
->dest
;
7249 r
->flags
|= TOPOROUTER_FLAG_LEASTINVALID
;
7250 if(route(r
, routedata
, 0)) {
7251 GList
*conflicts
, *j
;
7253 INSERT_ROUTING(routedata
);
7255 conflicts
= route_conflicts(routedata
);
7256 cluster_merge(routedata
);
7258 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7262 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7263 if(!g_list_find(netlists
, conflict
->netlist
))
7264 netlists
= g_list_prepend(netlists
, conflict
->netlist
);
7266 route_checkpoint(conflict
, routedata
);
7268 REMOVE_ROUTING(conflict
);
7272 netlists
= g_list_prepend(netlists
, routedata
->netlist
);
7273 netlists_recalculate(netlists
, NULL
);
7277 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7278 g_assert(conflict
->src
->c
!= conflict
->dest
->c
);
7279 if(route(r
, conflict
, 0)) {
7280 cluster_merge(conflict
);
7282 routed
= g_list_prepend(routed
, conflict
);
7284 INSERT_ROUTING(conflict
);
7286 netlist_recalculate(conflict
->netlist
, NULL
);
7289 if(++intfails
>= threshold
) {
7292 toporouter_route_t
*intconflict
= TOPOROUTER_ROUTE(i
->data
);
7293 REMOVE_ROUTING(intconflict
);
7294 delete_route(intconflict
, 1);
7297 delete_route(routedata
, 1);
7298 i
= g_list_last(conflicts
);
7300 toporouter_route_t
*intconflict
= TOPOROUTER_ROUTE(i
->data
);
7302 route_restore(intconflict
);
7303 INSERT_ROUTING(intconflict
);
7307 REMOVE_ROUTING(routedata
);
7309 netlists_recalculate(netlists
, NULL
);
7310 goto roar_route_end
;
7318 netlists_recalculate(netlists
, NULL
);
7322 g_list_free(conflicts
);
7323 g_list_free(netlists
);
7326 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7329 g_list_free(routed
);
7334 roar_router(toporouter_t
*r
, gint failcount
, gint threshold
)
7336 gint pfailcount
= failcount
+1;
7338 Message(_("ROAR router: "));
7339 for(guint j
=0;j
<6;j
++) {
7340 GList
*failed
= g_list_copy(r
->failednets
), *k
= failed
;
7344 failcount
+= roar_route(r
, TOPOROUTER_ROUTE(k
->data
), threshold
);
7347 g_list_free(failed
);
7349 printf("\tROAR pass %d - %d routed - %d failed\n", j
, g_list_length(r
->routednets
), g_list_length(r
->failednets
));
7351 if(!failcount
|| failcount
>= pfailcount
) {
7352 Message(_("%d nets remaining\n"), failcount
);
7355 Message(_("%d -> "), failcount
);
7356 pfailcount
= failcount
;
7363 route_detour_compare(toporouter_route_t
**a
, toporouter_route_t
**b
)
7364 { return ((*b
)->score
- (*b
)->detourscore
) - ((*a
)->score
- (*a
)->detourscore
); }
7369 roar_detour_route(toporouter_t
*r
, toporouter_route_t
*data
)
7371 gdouble pscore
= data
->score
, nscore
= 0.;
7372 GList
*netlists
= NULL
;
7374 route_checkpoint(data
, NULL
);
7376 REMOVE_ROUTING(data
);
7378 netlists
= g_list_prepend(NULL
, data
->netlist
);
7379 netlists_recalculate(netlists
, NULL
);
7381 r
->flags
|= TOPOROUTER_FLAG_LEASTINVALID
;
7382 if(route(r
, data
, 0)) {
7383 GList
*conflicts
, *j
;
7385 nscore
= data
->score
;
7386 conflicts
= route_conflicts(data
);
7388 INSERT_ROUTING(data
);
7390 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7394 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7396 if(!g_list_find(netlists
, conflict
->netlist
))
7397 netlists
= g_list_prepend(netlists
, conflict
->netlist
);
7398 pscore
+= conflict
->score
;
7400 route_checkpoint(conflict
, NULL
);
7401 REMOVE_ROUTING(conflict
);
7405 netlists_recalculate(netlists
, NULL
);
7409 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7411 if(route(r
, conflict
, 0)) {
7412 cluster_merge(conflict
);
7413 INSERT_ROUTING(conflict
);
7414 nscore
+= conflict
->score
;
7417 goto roar_detour_route_rollback_int
;
7422 if(nscore
> pscore
) {
7423 j
= g_list_last(conflicts
);
7424 roar_detour_route_rollback_int
:
7425 REMOVE_ROUTING(data
);
7428 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7429 REMOVE_ROUTING(conflict
);
7430 delete_route(conflict
, 1);
7434 j
= g_list_last(conflicts
);
7436 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7437 route_restore(conflict
);
7438 INSERT_ROUTING(conflict
);
7441 delete_route(data
, 1);
7443 goto roar_detour_route_rollback_exit
;
7447 g_list_free(conflicts
);
7449 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7450 roar_detour_route_rollback_exit
:
7451 route_restore(data
);
7452 INSERT_ROUTING(data
);
7454 netlists_recalculate(netlists
, NULL
);
7456 g_list_free(netlists
);
7460 detour_router(toporouter_t
*r
)
7462 GList
*i
= r
->routednets
;
7463 guint n
= g_list_length(r
->routednets
);
7464 GPtrArray
* scores
= g_ptr_array_sized_new(n
);
7467 toporouter_route_t
*curroute
= TOPOROUTER_ROUTE(i
->data
);
7468 curroute
->score
= path_score(r
, curroute
->path
);
7469 g_ptr_array_add(scores
, i
->data
);
7473 g_ptr_array_sort(scores
, (GCompareFunc
) route_detour_compare
);
7475 r
->flags
|= TOPOROUTER_FLAG_DETOUR
;
7477 for(toporouter_route_t
**i
= (toporouter_route_t
**) scores
->pdata
; i
< (toporouter_route_t
**) scores
->pdata
+ scores
->len
; i
++) {
7478 toporouter_route_t
*curroute
= (*i
);
7480 if(finite(curroute
->score
) && finite(curroute
->detourscore
)) {
7481 // printf("%15s %15f \t %8f,%8f - %8f,%8f\n", (*i)->src->netlist + 2, (*i)->score - (*i)->detourscore,
7482 // vx(curroute->mergebox1->point), vy(curroute->mergebox1->point),
7483 // vx(curroute->mergebox2->point), vy(curroute->mergebox2->point));
7485 if(curroute
->score
- curroute
->detourscore
> 1000.) {
7486 roar_detour_route(r
, curroute
);
7493 r
->flags
^= TOPOROUTER_FLAG_DETOUR
;
7495 g_ptr_array_free(scores
, TRUE
);
7500 rubix_router(toporouter_t
*r
, gint failcount
)
7502 GList
*i
, *ordering
;
7503 order_nets_preroute_greedy(r
, r
->failednets
, &ordering
);
7507 toporouter_route_t
*data
= TOPOROUTER_ROUTE(i
->data
);
7509 if(route(r
, data
, 0)) {
7510 INSERT_ROUTING(data
);
7511 cluster_merge(data
);
7518 g_list_free(ordering
);
7524 hybrid_router(toporouter_t
*r
)
7526 gint failcount
= g_list_length(r
->failednets
);
7527 r
->flags
|= TOPOROUTER_FLAG_AFTERORDER
;
7528 r
->flags
|= TOPOROUTER_FLAG_AFTERRUBIX
;
7529 failcount
= rubix_router(r
, failcount
);
7531 Message(_("RUBIX router: %d nets remaining\n"), failcount
);
7532 printf("RUBIX router: %d nets remaining\n", failcount
);
7534 r
->flags
|= TOPOROUTER_FLAG_GOFAR
;
7536 for(guint i
=0;i
<6 && failcount
;i
++) {
7538 failcount
= roar_router(r
, failcount
, 5);
7539 // printf("THRESH 5\n");
7541 failcount
= roar_router(r
, failcount
, 2);
7542 // printf("THRESH 2\n");
7548 failcount
= roar_router(r
, failcount
, 2);
7555 parse_arguments(toporouter_t
*r
, int argc
, char **argv
)
7558 for(i
=0;i
<argc
;i
++) {
7559 if(sscanf(argv
[i
], "viacost=%d", &tempint
)) {
7560 r
->viacost
= (double)tempint
;
7561 }else if(sscanf(argv
[i
], "l%d", &tempint
)) {
7562 gdouble
*layer
= malloc(sizeof(gdouble
));
7563 *layer
= (double)tempint
;
7564 r
->keepoutlayers
= g_list_prepend(r
->keepoutlayers
, layer
);
7568 for (guint group
= 0; group
< max_layer
; group
++)
7569 for (i
= 0; i
< PCB
->LayerGroups
.Number
[group
]; i
++)
7570 if ((PCB
->LayerGroups
.Entries
[group
][i
] < max_layer
) && !(PCB
->Data
->Layer
[PCB
->LayerGroups
.Entries
[group
][i
]].On
)) {
7571 gdouble
*layer
= malloc(sizeof(gdouble
));
7572 *layer
= (double)group
;
7573 r
->keepoutlayers
= g_list_prepend(r
->keepoutlayers
, layer
);
7579 toporouter_new(void)
7581 toporouter_t
*r
= calloc(1, sizeof(toporouter_t
));
7584 gettimeofday(&r
->starttime
, NULL
);
7586 r
->netsort
= netscore_pairwise_compare
;
7588 r
->destboxes
= NULL
;
7589 r
->consumeddestboxes
= NULL
;
7596 r
->viacost
= 10000.;
7597 r
->stublength
= 300.;
7598 r
->serpintine_half_amplitude
= 1500.;
7600 r
->wiring_score
= 0.;
7605 r
->netlists
= g_ptr_array_new();
7606 r
->routes
= g_ptr_array_new();
7608 r
->keepoutlayers
= NULL
;
7610 r
->routednets
= NULL
;
7611 r
->failednets
= NULL
;
7615 gts_predicates_init();
7617 Message(_("Topological Autorouter\n"));
7618 Message(_("Started %s"),asctime(localtime(<ime
)));
7619 Message(_("-------------------------------------\n"));
7620 Message(_("Copyright 2009 Anthony Blake (tonyb33@gmail.com)\n\n"));
7625 acquire_twonets(toporouter_t
*r
)
7627 RAT_LOOP(PCB
->Data
);
7628 if( TEST_FLAG(SELECTEDFLAG
, line
) ) import_route(r
, line
);
7631 if(!r
->routes
->len
) {
7632 RAT_LOOP(PCB
->Data
);
7633 import_route(r
, line
);
7640 toporouter_netlist_t
*
7641 find_netlist_by_name(toporouter_t
*r
, char *name
)
7643 FOREACH_NETLIST(r
->netlists
) {
7644 if(!strcmp(netlist
->netlist
, name
)) return netlist
;
7650 toporouter_set_pair(toporouter_t
*r
, toporouter_netlist_t
*n1
, toporouter_netlist_t
*n2
)
7652 if(!n1
|| !n2
) return 0;
7659 toporouter (int argc
, char **argv
, int x
, int y
)
7661 toporouter_t
*r
= toporouter_new();
7662 parse_arguments(r
, argc
, argv
);
7666 //if(!toporouter_set_pair(r, find_netlist_by_name(r, " DRAM_DQS_N"), find_netlist_by_name(r, " DRAM_DQS"))) {
7667 // printf("Couldn't associate pair\n");
7672 // for(gint i=0;i<groupcount();i++) {
7673 // gts_surface_foreach_edge(r->layers[i].surface, space_edge, NULL);
7677 for(i=0;i<groupcount();i++) {
7679 sprintf(buffer, "route%d.png", i);
7680 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, NULL, i, NULL);
7684 toporouter_export(r
);
7687 SaveUndoSerialNumber ();
7689 RestoreUndoSerialNumber ();
7690 AddAllRats (False
, NULL
);
7691 RestoreUndoSerialNumber ();
7692 IncrementUndoSerialNumber ();
7693 ClearAndRedrawOutput ();
7699 escape (int argc
, char **argv
, int x
, int y
)
7701 guint dir
, viax
, viay
;
7702 gdouble pitch
, length
, dx
, dy
;
7704 if(argc
!= 1) return 0;
7706 dir
= atoi(argv
[0]);
7709 ALLPAD_LOOP(PCB
->Data
);
7711 if( TEST_FLAG(SELECTEDFLAG
, pad
) ) {
7715 pitch
= sqrt( pow(abs(element
->Pad
[0].Point1
.X
- element
->Pad
[1].Point1
.X
), 2) +
7716 pow(abs(element
->Pad
[0].Point1
.Y
- element
->Pad
[1].Point1
.Y
), 2) );
7717 length
= sqrt(pow(pitch
,2) + pow(pitch
,2)) / 2.;
7719 dx
= length
* sin(M_PI
/4.);
7720 dy
= length
* cos(M_PI
/4.);
7724 viax
= pad
->Point1
.X
- dx
;
7725 viay
= pad
->Point1
.Y
+ dy
;
7728 viax
= pad
->Point1
.X
+ dx
;
7729 viay
= pad
->Point1
.Y
+ dy
;
7732 viax
= pad
->Point1
.X
+ dx
;
7733 viay
= pad
->Point1
.Y
- dy
;
7736 viax
= pad
->Point1
.X
- dx
;
7737 viay
= pad
->Point1
.Y
- dy
;
7740 viax
= pad
->Point1
.X
;
7741 viay
= pad
->Point1
.Y
+ (pitch
/2);
7744 viax
= pad
->Point1
.X
;
7745 viay
= pad
->Point1
.Y
- (pitch
/2);
7748 viax
= pad
->Point1
.X
- (pitch
/2);
7749 viay
= pad
->Point1
.Y
;
7752 viax
= pad
->Point1
.X
+ (pitch
/2);
7753 viay
= pad
->Point1
.Y
;
7756 printf("ERROR: escape() with bad direction (%d)\n", dir
);
7760 if ((via
= CreateNewVia (PCB
->Data
, viax
, viay
,
7761 Settings
.ViaThickness
, 2 * Settings
.Keepaway
,
7762 0, Settings
.ViaDrillingHole
, NULL
,
7763 NoFlags ())) != NULL
)
7765 AddObjectToCreateUndoList (VIA_TYPE
, via
, via
, via
);
7766 // if (gui->shift_is_pressed ())
7767 // ChangeObjectThermal (VIA_TYPE, via, via, via, PCB->ThermStyle);
7769 if((line
= CreateDrawnLineOnLayer (CURRENT
, pad
->Point1
.X
+ 1., pad
->Point1
.Y
+ 1., viax
+ 1., viay
+ 1.,
7770 Settings
.LineThickness
, 2 * Settings
.Keepaway
,
7774 AddObjectToCreateUndoList (LINE_TYPE
, CURRENT
, line
, line
);
7775 DrawLine (CURRENT
, line
, 0);
7786 IncrementUndoSerialNumber ();
7791 static HID_Action toporouter_action_list
[] = {
7792 {"Escape", "Select a set of pads", escape
, "Pad escape", "Escape()"},
7793 {"Toporouter", "Select net(s)", toporouter
, "Topological autorouter", "Toporouter()"}
7796 REGISTER_ACTIONS (toporouter_action_list
)
7798 void hid_toporouter_init()
7800 register_toporouter_action_list();