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
,
1757 gdouble x2
, gdouble y2
, guint flags2
, toporouter_bbox_t
*box
)
1759 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1760 GtsEdgeClass
*edge_class
= GTS_EDGE_CLASS (toporouter_constraint_class ());
1768 /* insert or find points */
1773 if(v
->p
.x
== x1
&& v
->p
.y
== y1
)
1775 if(v
->p
.x
== x2
&& v
->p
.y
== y2
)
1781 p
[0] = gts_vertex_new (vertex_class
, x1
, y1
, l
- r
->layers
);
1782 TOPOROUTER_VERTEX(p
[0])->bbox
= box
;
1783 l
->vertices
= g_list_prepend(l
->vertices
, p
[0]);
1786 p
[1] = gts_vertex_new (vertex_class
, x2
, y2
, l
- r
->layers
);
1787 TOPOROUTER_VERTEX(p
[1])->bbox
= box
;
1788 l
->vertices
= g_list_prepend(l
->vertices
, p
[1]);
1791 TOPOROUTER_VERTEX(p
[0])->flags
= flags1
;
1792 TOPOROUTER_VERTEX(p
[1])->flags
= flags2
;
1794 e
= gts_edge_new (edge_class
, p
[0], p
[1]);
1795 TOPOROUTER_CONSTRAINT(e
)->box
= box
;
1796 l
->constraints
= g_list_prepend (l
->constraints
, e
);
1797 // return insert_constraint_edge_rec(r, l, p, box);
1798 return g_list_prepend(NULL
, e
);
1803 insert_constraints_from_list(toporouter_t
*r
, toporouter_layer_t
*l
, GList
*vlist
, toporouter_bbox_t
*box
)
1806 toporouter_vertex_t
*pv
= NULL
, *v
;
1809 v
= TOPOROUTER_VERTEX(i
->data
);
1813 g_list_concat(box
->constraints
, insert_constraint_edge(r
, l
, vx(v
), vy(v
), v
->flags
, vx(pv
), vy(pv
), pv
->flags
, box
));
1820 v
= TOPOROUTER_VERTEX(vlist
->data
);
1822 g_list_concat(box
->constraints
, insert_constraint_edge(r
, l
, vx(v
), vy(v
), v
->flags
, vx(pv
), vy(pv
), pv
->flags
, box
));
1827 insert_centre_point(toporouter_t
*r
, toporouter_layer_t
*l
, gdouble x
, gdouble y
)
1830 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1834 GtsPoint
*p
= GTS_POINT(i
->data
);
1835 if(p
->x
== x
&& p
->y
== y
)
1840 l
->vertices
= g_list_prepend(l
->vertices
, gts_vertex_new(vertex_class
, x
, y
, 0.0f
));
1844 midpoint(GtsPoint
*a
, GtsPoint
*b
)
1846 return gts_point_new(gts_point_class(), (a
->x
+ b
->x
) / 2., (a
->y
+ b
->y
) / 2., 0.);
1850 pad_rad(PadType
*pad
)
1852 return (lookup_thickness(pad
->Name
) / 2.) + lookup_keepaway(pad
->Name
);
1856 pin_rad(PinType
*pin
)
1858 return (lookup_thickness(pin
->Name
) / 2.) + lookup_keepaway(pin
->Name
);
1862 rect_with_attachments(gdouble rad
,
1863 gdouble x0
, gdouble y0
,
1864 gdouble x1
, gdouble y1
,
1865 gdouble x2
, gdouble y2
,
1866 gdouble x3
, gdouble y3
,
1869 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
1870 GList
*r
= NULL
, *rr
= NULL
, *i
;
1871 toporouter_vertex_t
*curpoint
, *temppoint
;
1874 curpoint
= TOPOROUTER_VERTEX(gts_vertex_new (vertex_class
, x0
, y0
, z
));
1876 r
= g_list_prepend(NULL
, curpoint
);
1877 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x1
, y1
, z
));
1878 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x2
, y2
, z
));
1879 r
= g_list_prepend(r
, gts_vertex_new (vertex_class
, x3
, y3
, z
));
1883 temppoint
= TOPOROUTER_VERTEX(i
->data
);
1884 rr
= g_list_prepend(rr
, curpoint
);
1886 curpoint
= temppoint
;
1895 #define VERTEX_CENTRE(x) TOPOROUTER_VERTEX( vertex_bbox(x)->point )
1898 * Read pad data from layer into toporouter_layer_t struct
1900 * Inserts points and constraints into GLists
1903 read_pads(toporouter_t
*r
, toporouter_layer_t
*l
, guint layer
)
1905 toporouter_spoint_t p
[2], rv
[5];
1906 gdouble x
[2], y
[2], t
, m
;
1907 GList
*objectconstraints
;
1909 GList
*vlist
= NULL
;
1910 toporouter_bbox_t
*bbox
= NULL
;
1912 guint front
= GetLayerGroupNumberByNumber (max_layer
+ COMPONENT_LAYER
);
1913 guint back
= GetLayerGroupNumberByNumber (max_layer
+ SOLDER_LAYER
);
1915 // printf("read_pads: front = %d back = %d layer = %d\n",
1916 // front, back, layer);
1918 /* If its not the top or bottom layer, there are no pads to read */
1919 if(l
- r
->layers
!= front
&& l
- r
->layers
!= back
) return 0;
1921 ELEMENT_LOOP(PCB
->Data
);
1925 if( (l
- r
->layers
== back
&& TEST_FLAG(ONSOLDERFLAG
, pad
)) ||
1926 (l
- r
->layers
== front
&& !TEST_FLAG(ONSOLDERFLAG
, pad
)) ) {
1929 objectconstraints
= NULL
;
1930 t
= (gdouble
)pad
->Thickness
/ 2.0f
;
1931 x
[0] = pad
->Point1
.X
;
1932 x
[1] = pad
->Point2
.X
;
1933 y
[0] = pad
->Point1
.Y
;
1934 y
[1] = pad
->Point2
.Y
;
1937 if(TEST_FLAG(SQUAREFLAG
, pad
)) {
1938 /* Square or oblong pad. Four points and four constraint edges are
1941 if(x
[0] == x
[1] && y
[0] == y
[1]) {
1944 // vlist = g_list_prepend(NULL, 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 = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]+t, y[0]-t, 0.));
1948 vlist
= rect_with_attachments(pad_rad(pad
),
1954 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
1955 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1956 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1959 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, x[0], y[0], 0.) );
1960 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
[0], y
[0], bbox
) );
1961 g_assert(TOPOROUTER_VERTEX(bbox
->point
)->bbox
== bbox
);
1963 /* Pad is diagonal oblong or othogonal oblong */
1965 m
= cartesian_gradient(x
[0], y
[0], x
[1], y
[1]);
1967 p
[0].x
= x
[0]; p
[0].y
= y
[0];
1968 p
[1].x
= x
[1]; p
[1].y
= y
[1];
1970 vertex_outside_segment(&p
[0], &p
[1], t
, &rv
[0]);
1971 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[1], &rv
[2]);
1973 vertex_outside_segment(&p
[1], &p
[0], t
, &rv
[0]);
1974 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[3], &rv
[4]);
1976 if(wind(&rv
[1], &rv
[2], &rv
[3]) != wind(&rv
[2], &rv
[3], &rv
[4])) {
1977 rv
[0].x
= rv
[3].x
; rv
[0].y
= rv
[3].y
;
1978 rv
[3].x
= rv
[4].x
; rv
[3].y
= rv
[4].y
;
1979 rv
[4].x
= rv
[0].x
; rv
[4].y
= rv
[0].y
;
1982 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, rv[1].x, rv[1].y, 0.));
1983 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[2].x, rv[2].y, 0.));
1984 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[3].x, rv[3].y, 0.));
1985 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[4].x, rv[4].y, 0.));
1986 vlist
= rect_with_attachments(pad_rad(pad
),
1992 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
1993 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
1994 insert_constraints_from_list(r
, l
, vlist
, bbox
);
1997 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., 0.) );
1998 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, (x
[0] + x
[1]) / 2., (y
[0] + y
[1]) / 2., bbox
) );
1999 g_assert(TOPOROUTER_VERTEX(bbox
->point
)->bbox
== bbox
);
2004 /* Either round pad or pad with curved edges */
2006 if(x
[0] == x
[1] && y
[0] == y
[1]) {
2009 /* bounding box same as square pad */
2010 vlist
= rect_with_attachments(pad_rad(pad
),
2016 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
2017 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2020 //bbox->point = GTS_POINT( insert_vertex(r, l, x[0], y[0], bbox) );
2021 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
[0], y
[0], bbox
) );
2024 /* Two points and one constraint edge */
2026 /* the rest is just for bounding box */
2027 m
= cartesian_gradient(x
[0], y
[0], x
[1], y
[1]);
2029 p
[0].x
= x
[0]; p
[0].y
= y
[0];
2030 p
[1].x
= x
[1]; p
[1].y
= y
[1];
2032 vertex_outside_segment(&p
[0], &p
[1], t
, &rv
[0]);
2033 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[1], &rv
[2]);
2035 vertex_outside_segment(&p
[1], &p
[0], t
, &rv
[0]);
2036 vertices_on_line(&rv
[0], perpendicular_gradient(m
), t
, &rv
[3], &rv
[4]);
2038 if(wind(&rv
[1], &rv
[2], &rv
[3]) != wind(&rv
[2], &rv
[3], &rv
[4])) {
2039 rv
[0].x
= rv
[3].x
; rv
[0].y
= rv
[3].y
;
2040 rv
[3].x
= rv
[4].x
; rv
[3].y
= rv
[4].y
;
2041 rv
[4].x
= rv
[0].x
; rv
[4].y
= rv
[0].y
;
2044 vlist
= rect_with_attachments(pad_rad(pad
),
2050 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PAD
, pad
);
2051 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2052 insert_constraints_from_list(r
, l
, vlist
, bbox
);
2055 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., 0.) );
2056 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, (x
[0] + x
[1]) / 2., (y
[0] + y
[1]) / 2., bbox
) );
2058 //bbox->constraints = g_list_concat(bbox->constraints, insert_constraint_edge(r, l, x[0], y[0], x[1], y[1], bbox));
2075 * Read points data (all layers) into GList
2077 * Inserts pin and via points
2080 read_points(toporouter_t
*r
, toporouter_layer_t
*l
, int layer
)
2084 GList
*vlist
= NULL
;
2085 toporouter_bbox_t
*bbox
= NULL
;
2087 ELEMENT_LOOP(PCB
->Data
);
2092 t
= (gdouble
)pin
->Thickness
/ 2.0f
;
2096 if(TEST_FLAG (SQUAREFLAG
, pin
)) {
2098 vlist
= rect_with_attachments(pin_rad(pin
),
2104 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PIN
, pin
);
2105 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2106 insert_constraints_from_list(r
, l
, vlist
, bbox
);
2108 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
2110 }else if(TEST_FLAG(OCTAGONFLAG
, pin
)){
2111 /* TODO: Handle octagon pins */
2112 fprintf(stderr
, "No support for octagon pins yet\n");
2114 vlist
= rect_with_attachments(pin_rad(pin
),
2120 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, PIN
, pin
);
2121 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2123 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
2130 VIA_LOOP(PCB
->Data
);
2133 t
= (gdouble
)via
->Thickness
/ 2.0f
;
2137 if(TEST_FLAG (SQUAREFLAG
, via
)) {
2139 vlist
= rect_with_attachments(pin_rad((PinType
*)via
),
2145 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, VIA
, via
);
2146 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2147 insert_constraints_from_list(r
, l
, vlist
, bbox
);
2149 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
2151 }else if(TEST_FLAG(OCTAGONFLAG
, via
)){
2152 /* TODO: Handle octagon vias */
2153 fprintf(stderr
, "No support for octagon vias yet\n");
2156 vlist
= rect_with_attachments(pin_rad((PinType
*)via
),
2162 bbox
= toporouter_bbox_create(l
- r
->layers
, vlist
, VIA
, via
);
2163 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2166 bbox
->point
= GTS_POINT( insert_vertex(r
, l
, x
, y
, bbox
) );
2175 * Read line data from layer into toporouter_layer_t struct
2177 * Inserts points and constraints into GLists
2180 read_lines(toporouter_t
*r
, toporouter_layer_t
*l
, LayerType
*layer
, int ln
)
2182 gdouble xs
[2], ys
[2];
2184 GList
*vlist
= NULL
;
2185 toporouter_bbox_t
*bbox
= NULL
;
2187 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
2191 xs
[0] = line
->Point1
.X
;
2192 xs
[1] = line
->Point2
.X
;
2193 ys
[0] = line
->Point1
.Y
;
2194 ys
[1] = line
->Point2
.Y
;
2195 if(!(xs
[0] == xs
[1] && ys
[0] == ys
[1])) {
2196 vlist
= g_list_prepend(NULL
, gts_vertex_new (vertex_class
, xs
[0], ys
[0], l
- r
->layers
));
2197 vlist
= g_list_prepend(vlist
, gts_vertex_new (vertex_class
, xs
[1], ys
[1], l
- r
->layers
));
2198 // TODO: replace this with surface version
2199 bbox
= toporouter_bbox_create_from_points(GetLayerGroupNumberByNumber(ln
), vlist
, LINE
, line
);
2200 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2202 //insert_constraints_from_list(r, l, vlist, bbox);
2204 // bbox->point = GTS_POINT( insert_vertex(r, l, (xs[0]+xs[1])/2., (ys[0]+ys[1])/2., bbox) );
2206 bbox
->constraints
= g_list_concat(bbox
->constraints
, insert_constraint_edge(r
, l
, xs
[0], ys
[0], 0, xs
[1], ys
[1], 0, bbox
));
2215 create_board_edge(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, gdouble max
, gint layer
, GList
**vlist
)
2217 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
2218 gdouble d
= sqrt(pow(x0
-x1
,2) + pow(y0
-y1
,2));
2219 guint n
= d
/ max
, count
= 1;
2220 gdouble inc
= n
? d
/ n
: d
;
2221 gdouble x
= x0
, y
= y0
;
2223 *vlist
= g_list_prepend(*vlist
, gts_vertex_new (vertex_class
, x0
, y0
, layer
));
2226 coord_move_towards_coord_values(x0
, y0
, x1
, y1
, inc
, &x
, &y
);
2227 *vlist
= g_list_prepend(*vlist
, gts_vertex_new (vertex_class
, x
, y
, layer
));
2237 read_board_constraints(toporouter_t
*r
, toporouter_layer_t
*l
, int layer
)
2239 // GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
2240 GList
*vlist
= NULL
;
2241 toporouter_bbox_t
*bbox
= NULL
;
2243 /* Add points for corners of board, and constrain those edges */
2244 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, 0., 0., layer));
2245 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, PCB->MaxWidth, 0., layer));
2246 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, PCB->MaxWidth, PCB->MaxHeight, layer));
2247 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, 0., PCB->MaxHeight, layer));
2249 create_board_edge(0., 0., PCB
->MaxWidth
, 0., 10000., layer
, &vlist
);
2250 create_board_edge(PCB
->MaxWidth
, 0., PCB
->MaxWidth
, PCB
->MaxHeight
, 10000., layer
, &vlist
);
2251 create_board_edge(PCB
->MaxWidth
, PCB
->MaxHeight
, 0., PCB
->MaxHeight
, 10000., layer
, &vlist
);
2252 create_board_edge(0., PCB
->MaxHeight
, 0., 0., 10000., layer
, &vlist
);
2254 bbox
= toporouter_bbox_create(layer
, vlist
, BOARD
, NULL
);
2255 r
->bboxes
= g_slist_prepend(r
->bboxes
, bbox
);
2256 insert_constraints_from_list(r
, l
, vlist
, bbox
);
2263 triangle_cost(GtsTriangle
*t
, gpointer
*data
){
2265 gdouble
*min_quality
= data
[0];
2266 gdouble
*max_area
= data
[1];
2267 gdouble quality
= gts_triangle_quality(t
);
2268 gdouble area
= gts_triangle_area(t
);
2270 if (quality
< *min_quality
|| area
> *max_area
)
2277 print_constraint(toporouter_constraint_t
*e
)
2279 printf("CONSTRAINT:\n");
2280 print_vertex(tedge_v1(e
));
2281 print_vertex(tedge_v2(e
));
2285 print_edge(toporouter_edge_t
*e
)
2287 GList
*i
= edge_routing(e
);
2291 print_vertex(tedge_v1(e
));
2294 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
2299 print_vertex(tedge_v2(e
));
2301 static void pick_first_face (GtsFace
* f
, GtsFace
** first
)
2308 unconstrain(toporouter_layer_t
*l
, toporouter_constraint_t
*c
)
2310 toporouter_edge_t
*e
;
2312 gts_allow_floating_vertices
= TRUE
;
2313 e
= TOPOROUTER_EDGE(gts_edge_new (GTS_EDGE_CLASS (toporouter_edge_class ()), GTS_SEGMENT(c
)->v1
, GTS_SEGMENT(c
)->v2
));
2314 gts_edge_replace(GTS_EDGE(c
), GTS_EDGE(e
));
2315 l
->constraints
= g_list_remove(l
->constraints
, c
);
2316 c
->box
->constraints
= g_list_remove(c
->box
->constraints
, c
);
2318 gts_object_destroy (GTS_OBJECT (c
));
2319 gts_allow_floating_vertices
= FALSE
;
2323 build_cdt(toporouter_t
*r
, toporouter_layer_t
*l
)
2325 /* TODO: generalize into surface *cdt_create(vertices, constraints) */
2330 GtsVertex
*v1
, *v2
, *v3
;
2331 GSList
*vertices_slist
;
2333 vertices_slist
= list_to_slist(l
->vertices
);
2336 GtsFace
* first
= NULL
;
2337 gts_surface_foreach_face (l
->surface
, (GtsFunc
) pick_first_face
, &first
);
2338 gts_surface_traverse_destroy(gts_surface_traverse_new (l
->surface
, first
));
2341 t
= gts_triangle_enclosing (gts_triangle_class (), vertices_slist
, 1000.0f
);
2342 gts_triangle_vertices (t
, &v1
, &v2
, &v3
);
2344 g_slist_free(vertices_slist
);
2346 l
->surface
= gts_surface_new (gts_surface_class (), gts_face_class (),
2347 GTS_EDGE_CLASS(toporouter_edge_class ()), GTS_VERTEX_CLASS(toporouter_vertex_class ()) );
2349 gts_surface_add_face (l
->surface
, gts_face_new (gts_face_class (), t
->e1
, t
->e2
, t
->e3
));
2352 // fprintf(stderr, "ADDED VERTICES\n");
2356 if((debugface = gts_delaunay_check(l->surface))) {
2357 fprintf(stderr, "WARNING: Delaunay check failed\n");
2358 fprintf(stderr, "\tViolating triangle:\n");
2359 fprintf(stderr, "\t%f,%f %f,%f\n",
2360 debugface->triangle.e1->segment.v1->p.x,
2361 debugface->triangle.e1->segment.v1->p.y,
2362 debugface->triangle.e1->segment.v2->p.x,
2363 debugface->triangle.e1->segment.v2->p.y
2365 fprintf(stderr, "\t%f,%f %f,%f\n",
2366 debugface->triangle.e2->segment.v1->p.x,
2367 debugface->triangle.e2->segment.v1->p.y,
2368 debugface->triangle.e2->segment.v2->p.x,
2369 debugface->triangle.e2->segment.v2->p.y
2371 fprintf(stderr, "\t%f,%f %f,%f\n",
2372 debugface->triangle.e3->segment.v1->p.x,
2373 debugface->triangle.e3->segment.v1->p.y,
2374 debugface->triangle.e3->segment.v2->p.x,
2375 debugface->triangle.e3->segment.v2->p.y
2377 // toporouter_draw_surface(r, l->surface, "debug.png", 4096, 4096);
2380 for(i=0;i<groupcount();i++) {
2382 sprintf(buffer, "debug-%d.png", i);
2383 toporouter_draw_surface(r, r->layers[i].surface, buffer, 2048, 2048, 2, NULL, i, NULL);
2389 check_cons_continuation
:
2392 toporouter_constraint_t
*c1
= TOPOROUTER_CONSTRAINT(i
->data
);
2394 // printf("adding cons: "); print_constraint(c1);
2397 toporouter_constraint_t
*c2
= TOPOROUTER_CONSTRAINT(j
->data
);
2401 // printf("\tconflict: "); print_constraint(c2);
2402 toporouter_bbox_t
*c1box
= c1
->box
, *c2box
= c2
->box
;
2403 toporouter_vertex_t
*c1v1
= tedge_v1(c1
);
2404 toporouter_vertex_t
*c1v2
= tedge_v2(c1
);
2405 toporouter_vertex_t
*c2v1
= tedge_v1(c2
);
2406 toporouter_vertex_t
*c2v2
= tedge_v2(c2
);
2408 if(gts_segments_are_intersecting(GTS_SEGMENT(c1
), GTS_SEGMENT(c2
)) == GTS_IN
) {
2409 toporouter_vertex_t
*v
;
2410 unconstrain(l
, c1
); unconstrain(l
, c2
);
2412 // proper intersection
2413 v
= TOPOROUTER_VERTEX(vertex_intersect(
2419 // remove both constraints
2420 // replace with 4x constraints
2421 // insert new intersection vertex
2422 GTS_POINT(v
)->z
= vz(c1v1
);
2424 l
->vertices
= g_list_prepend(l
->vertices
, v
);
2425 // gts_delaunay_add_vertex (l->surface, GTS_VERTEX(v), NULL);
2429 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(v
), vy(v
), 0, c1box
);
2430 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2432 temp
= insert_constraint_edge(r
, l
, vx(c1v2
), vy(c1v2
), 0, vx(v
), vy(v
), 0, c1box
);
2433 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2435 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(v
), vy(v
), 0, c2box
);
2436 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2438 temp
= insert_constraint_edge(r
, l
, vx(c2v2
), vy(c2v2
), 0, vx(v
), vy(v
), 0, c2box
);
2439 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2441 }else if(gts_segments_are_intersecting(GTS_SEGMENT(c1
), GTS_SEGMENT(c2
)) == GTS_ON
||
2442 gts_segments_are_intersecting(GTS_SEGMENT(c2
), GTS_SEGMENT(c1
)) == GTS_ON
) {
2444 if(vertex_between(edge_v1(c2
), edge_v2(c2
), edge_v1(c1
)) && vertex_between(edge_v1(c2
), edge_v2(c2
), edge_v2(c1
))) {
2445 unconstrain(l
, c1
); unconstrain(l
, c2
);
2448 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c2v2
), vy(c2v2
), 0, c2box
);
2449 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2451 }else if(vertex_between(edge_v1(c1
), edge_v2(c1
), edge_v1(c2
)) && vertex_between(edge_v1(c1
), edge_v2(c1
), edge_v2(c2
))) {
2452 unconstrain(l
, c1
); unconstrain(l
, c2
);
2455 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c1v2
), vy(c1v2
), 0, c1box
);
2456 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2458 //}else if(!vertex_wind(edge_v1(c1), edge_v2(c1), edge_v1(c2)) && !vertex_wind(edge_v1(c1), edge_v2(c1), edge_v2(c2))) {
2459 /* }else if(vertex_between(edge_v1(c1), edge_v2(c1), edge_v1(c2)) || vertex_between(edge_v1(c1), edge_v2(c1), edge_v2(c2))) {
2460 unconstrain(l, c1); unconstrain(l, c2);
2462 printf("all colinear\n");
2464 temp = insert_constraint_edge(r, l, vx(c1v1), vy(c1v1), 0, vx(c1v2), vy(c1v2), 0, c1box);
2465 c1box->constraints = g_list_concat(c1box->constraints, temp);
2467 if(vertex_between(GTS_VERTEX(c1v1), GTS_VERTEX(c1v2), GTS_VERTEX(c2v2))) {
2468 // v2 of c2 is inner
2469 if(vertex_between(GTS_VERTEX(c2v1), GTS_VERTEX(c2v2), GTS_VERTEX(c1v2))) {
2470 // v2 of c1 is inner
2471 // c2 = c1.v2 -> c2.v1
2472 temp = insert_constraint_edge(r, l, vx(c1v2), vy(c1v2), 0, vx(c2v1), vy(c2v1), 0, c2box);
2473 c2box->constraints = g_list_concat(c2box->constraints, temp);
2475 // v1 of c1 is inner
2476 // c2 = c1.v1 -> c2.v1
2477 temp = insert_constraint_edge(r, l, vx(c1v1), vy(c1v1), 0, vx(c2v1), vy(c2v1), 0, c2box);
2478 c2box->constraints = g_list_concat(c2box->constraints, temp);
2481 // v1 of c2 is inner
2482 if(vertex_between(GTS_VERTEX(c2v1), GTS_VERTEX(c2v2), GTS_VERTEX(c1v2))) {
2483 // v2 of c1 is inner
2484 // c2 = c1.v2 -> c2.v2
2485 temp = insert_constraint_edge(r, l, vx(c1v2), vy(c1v2), 0, vx(c2v2), vy(c2v2), 0, c2box);
2486 c2box->constraints = g_list_concat(c2box->constraints, temp);
2488 // v1 of c1 is inner
2489 // c2 = c1.v1 -> c2.v2
2490 temp = insert_constraint_edge(r, l, vx(c1v1), vy(c1v1), 0, vx(c2v2), vy(c2v2), 0, c2box);
2491 c2box->constraints = g_list_concat(c2box->constraints, temp);
2494 }else if(vertex_between(edge_v1(c2
), edge_v2(c2
), edge_v1(c1
)) && c1v1
!= c2v1
&& c1v1
!= c2v2
) {
2495 unconstrain(l
, c1
); unconstrain(l
, c2
);
2498 printf("v1 of c1 on c2\n");
2500 // replace with 2x constraints
2501 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c1v1
), vy(c1v1
), 0, c2box
);
2502 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2503 temp
= insert_constraint_edge(r
, l
, vx(c2v2
), vy(c2v2
), 0, vx(c1v1
), vy(c1v1
), 0, c2box
);
2504 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2506 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c1v2
), vy(c1v2
), 0, c1box
);
2507 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2510 //temp = insert_constraint_edge(r, l, vx(tedge_v2(c1)), vy(tedge_v2(c1)), 0, vx(tedge_v1(c1)), vy(tedge_v1(c1)), 0, c1->box);
2511 //c2->box->constraints = g_list_concat(c2->box->constraints, temp);
2513 }else if(vertex_between(edge_v1(c2
), edge_v2(c2
), edge_v2(c1
)) && c1v2
!= c2v1
&& c1v2
!= c2v2
) {
2514 unconstrain(l
, c1
); unconstrain(l
, c2
);
2517 printf("v2 of c1 on c2\n");
2519 // replace with 2x constraints
2520 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c1v2
), vy(c1v2
), 0, c2box
);
2521 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2522 temp
= insert_constraint_edge(r
, l
, vx(c2v2
), vy(c2v2
), 0, vx(c1v2
), vy(c1v2
), 0, c2box
);
2523 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2525 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c1v2
), vy(c1v2
), 0, c1box
);
2526 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2528 }else if(vertex_between(edge_v1(c1
), edge_v2(c1
), edge_v1(c2
)) && c2v1
!= c1v1
&& c2v1
!= c1v2
) {
2529 unconstrain(l
, c1
); unconstrain(l
, c2
);
2532 printf("v1 of c2 on c1\n");
2534 // replace with 2x constraints
2535 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c2v1
), vy(c2v1
), 0, c1box
);
2536 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2537 temp
= insert_constraint_edge(r
, l
, vx(c1v2
), vy(c1v2
), 0, vx(c2v1
), vy(c2v1
), 0, c1box
);
2538 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2540 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c2v2
), vy(c2v2
), 0, c2box
);
2541 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2542 }else if(vertex_between(edge_v1(c1
), edge_v2(c1
), edge_v2(c2
)) && c2v2
!= c1v1
&& c2v2
!= c1v2
) {
2543 unconstrain(l
, c1
); unconstrain(l
, c2
);
2546 printf("v2 of c2 on c1\n");
2548 // replace with 2x constraints
2549 temp
= insert_constraint_edge(r
, l
, vx(c1v1
), vy(c1v1
), 0, vx(c2v2
), vy(c2v2
), 0, c1box
);
2550 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2551 temp
= insert_constraint_edge(r
, l
, vx(c1v2
), vy(c1v2
), 0, vx(c2v2
), vy(c2v2
), 0, c1box
);
2552 c1box
->constraints
= g_list_concat(c1box
->constraints
, temp
);
2554 temp
= insert_constraint_edge(r
, l
, vx(c2v1
), vy(c2v1
), 0, vx(c2v2
), vy(c2v2
), 0, c2box
);
2555 c2box
->constraints
= g_list_concat(c2box
->constraints
, temp
);
2558 if(rem
) goto check_cons_continuation
;
2569 //if(r->flags & TOPOROUTER_FLAG_DEBUG_CDTS)
2570 // fprintf(stderr, "\tadding vertex %f,%f\n", v->p.x, v->p.y);
2571 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(gts_delaunay_add_vertex (l
->surface
, i
->data
, NULL
));
2573 printf("conflict: "); print_vertex(v
);
2581 toporouter_constraint_t
*c1
= TOPOROUTER_CONSTRAINT(i
->data
);
2583 // printf("adding cons: "); print_constraint(c1);
2585 GSList
*conflicts
= gts_delaunay_add_constraint (l
->surface
, i
->data
);
2586 GSList
*j
= conflicts
;
2588 if(TOPOROUTER_IS_CONSTRAINT(j
->data
)) {
2589 toporouter_constraint_t
*c2
= TOPOROUTER_CONSTRAINT(j
->data
);
2591 printf("\tconflict: "); print_constraint(c2
);
2596 g_slist_free(conflicts
);
2602 // goto build_cdt_continuation;
2603 // fprintf(stderr, "ADDED CONSTRAINTS\n");
2604 gts_allow_floating_vertices
= TRUE
;
2605 gts_object_destroy (GTS_OBJECT (v1
));
2606 gts_object_destroy (GTS_OBJECT (v2
));
2607 gts_object_destroy (GTS_OBJECT (v3
));
2608 gts_allow_floating_vertices
= FALSE
;
2613 gdouble quality = 0.50, area = G_MAXDOUBLE;
2614 guint num = gts_delaunay_conform(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL);
2619 num = gts_delaunay_refine(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL, (GtsKeyFunc) triangle_cost, data);
2624 gts_surface_print_stats(l
->surface
, stderr
);
2630 sprintf(buffer
, "surface%d.gts", l
- r
->layers
);
2631 fout2
= fopen(buffer
, "w");
2632 gts_surface_write(l
->surface
, fout2
);
2638 visited_cmp(gconstpointer a
, gconstpointer b
)
2646 coord_xangle(gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
)
2648 gdouble dx
, dy
, theta
;
2655 } else theta
= atan(dy
/dx
);
2658 if(bx
< ax
) theta
= M_PI
- theta
;
2660 if(bx
< ax
) theta
+= M_PI
;
2661 else theta
= (2 * M_PI
) - theta
;
2668 point_xangle(GtsPoint
*a
, GtsPoint
*b
)
2670 gdouble dx
, dy
, theta
;
2672 dx
= fabs(a
->x
- b
->x
);
2673 dy
= fabs(a
->y
- b
->y
);
2677 } else theta
= atan(dy
/dx
);
2680 if(b
->x
< a
->x
) theta
= M_PI
- theta
;
2682 if(b
->x
< a
->x
) theta
+= M_PI
;
2683 else theta
= (2 * M_PI
) - theta
;
2691 cluster_vertices(toporouter_t
*r
, toporouter_cluster_t
*c
)
2697 FOREACH_CLUSTER(c
->netlist
->clusters
) {
2698 if((r
->flags
& TOPOROUTER_FLAG_AFTERRUBIX
&& cluster
->c
== c
->c
) || (!(r
->flags
& TOPOROUTER_FLAG_AFTERRUBIX
) && cluster
== c
)) {
2699 FOREACH_BBOX(cluster
->boxes
) {
2700 if(box
->type
== LINE
) {
2701 g_assert(box
->constraints
->data
);
2702 rval
= g_list_prepend(rval
, tedge_v1(box
->constraints
->data
));
2703 rval
= g_list_prepend(rval
, tedge_v2(box
->constraints
->data
));
2704 }else if(box
->point
) {
2705 rval
= g_list_prepend(rval
, TOPOROUTER_VERTEX(box
->point
));
2706 //g_assert(vertex_bbox(TOPOROUTER_VERTEX(box->point)) == box);
2708 printf("WARNING: cluster_vertices: unhandled bbox type\n");
2722 print_cluster(toporouter_cluster_t
*c
)
2726 printf("[CLUSTER (NULL)]\n");
2730 printf("CLUSTER %d: NETLIST = %s STYLE = %s\n", c
->c
, c
->netlist
->netlist
, c
->netlist
->style
);
2732 FOREACH_BBOX(c
->boxes
) {
2738 toporouter_cluster_t
*
2739 cluster_create(toporouter_t
*r
, toporouter_netlist_t
*netlist
)
2741 toporouter_cluster_t
*c
= malloc(sizeof(toporouter_cluster_t
));
2743 c
->c
= c
->pc
= netlist
->clusters
->len
;
2744 g_ptr_array_add(netlist
->clusters
, c
);
2745 c
->netlist
= netlist
;
2746 c
->boxes
= g_ptr_array_new();
2752 toporouter_bbox_locate(toporouter_t
*r
, toporouter_term_t type
, void *data
, gdouble x
, gdouble y
, guint layergroup
)
2754 GtsPoint
*p
= gts_point_new(gts_point_class(), x
, y
, layergroup
);
2755 GSList
*boxes
= gts_bb_tree_stabbed(r
->bboxtree
, p
), *i
= boxes
;
2757 gts_object_destroy(GTS_OBJECT(p
));
2760 toporouter_bbox_t
*box
= TOPOROUTER_BBOX(i
->data
);
2762 if(box
->type
== type
&& box
->data
== data
) {
2763 g_slist_free(boxes
);
2770 g_slist_free(boxes
);
2775 cluster_join_bbox(toporouter_cluster_t
*cluster
, toporouter_bbox_t
*box
)
2778 g_ptr_array_add(cluster
->boxes
, box
);
2779 box
->cluster
= cluster
;
2783 toporouter_netlist_t
*
2784 netlist_create(toporouter_t
*r
, char *netlist
, char *style
)
2786 toporouter_netlist_t
*nl
= malloc(sizeof(toporouter_netlist_t
));
2787 nl
->netlist
= netlist
;
2789 nl
->clusters
= g_ptr_array_new();
2790 nl
->routes
= g_ptr_array_new();
2793 g_ptr_array_add(r
->netlists
, nl
);
2798 import_clusters(toporouter_t
*r
)
2800 NetListListType nets
;
2801 ResetFoundPinsViasAndPads (false);
2802 ResetFoundLinesAndPolygons (false);
2803 nets
= CollectSubnets(false);
2804 NETLIST_LOOP(&nets
);
2806 if(netlist
->NetN
> 0) {
2807 toporouter_netlist_t
*nl
= netlist_create(r
, netlist
->Net
->Connection
->menu
->Name
, netlist
->Net
->Connection
->menu
->Style
);
2812 toporouter_cluster_t
*cluster
= cluster_create(r
, nl
);
2813 #ifdef DEBUG_MERGING
2816 CONNECTION_LOOP (net
);
2819 if(connection
->type
== LINE_TYPE
) {
2820 LineType
*line
= (LineType
*) connection
->ptr2
;
2821 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, LINE
, line
, connection
->X
, connection
->Y
, connection
->group
);
2822 cluster_join_bbox(cluster
, box
);
2824 #ifdef DEBUG_MERGING
2825 printf("\tLINE %d,%d\n", connection
->X
, connection
->Y
);
2827 }else if(connection
->type
== PAD_TYPE
) {
2828 PadType
*pad
= (PadType
*) connection
->ptr2
;
2829 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, PAD
, pad
, connection
->X
, connection
->Y
, connection
->group
);
2830 cluster_join_bbox(cluster
, box
);
2832 #ifdef DEBUG_MERGING
2833 printf("\tPAD %d,%d\n", connection
->X
, connection
->Y
);
2835 }else if(connection
->type
== PIN_TYPE
) {
2837 for(guint m
=0;m
<groupcount();m
++) {
2838 PinType
*pin
= (PinType
*) connection
->ptr2
;
2839 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, PIN
, pin
, connection
->X
, connection
->Y
, m
);
2840 cluster_join_bbox(cluster
, box
);
2843 #ifdef DEBUG_MERGING
2844 printf("\tPIN %d,%d\n", connection
->X
, connection
->Y
);
2846 }else if(connection
->type
== VIA_TYPE
) {
2848 for(guint m
=0;m
<groupcount();m
++) {
2849 PinType
*pin
= (PinType
*) connection
->ptr2
;
2850 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, VIA
, pin
, connection
->X
, connection
->Y
, m
);
2851 cluster_join_bbox(cluster
, box
);
2854 #ifdef DEBUG_MERGING
2855 printf("\tVIA %d,%d\n", connection
->X
, connection
->Y
);
2857 }else if(connection
->type
== POLYGON_TYPE
) {
2858 PolygonType
*polygon
= (PolygonType
*) connection
->ptr2
;
2859 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, POLYGON
, polygon
, connection
->X
, connection
->Y
, connection
->group
);
2860 cluster_join_bbox(cluster
, box
);
2862 #ifdef DEBUG_MERGING
2863 printf("\tPOLYGON %d,%d\n", connection
->X
, connection
->Y
);
2869 #ifdef DEBUG_MERGING
2878 FreeNetListListMemory(&nets
);
2882 import_geometry(toporouter_t
*r
)
2884 toporouter_layer_t
*cur_layer
;
2889 for (group
= 0; group
< max_layer
; group
++) {
2890 printf("Group %d: Number %d:\n", group
, PCB
->LayerGroups
.Number
[group
]);
2892 for (int entry
= 0; entry
< PCB
->LayerGroups
.Number
[group
]; entry
++) {
2893 printf("\tEntry %d\n", PCB
->LayerGroups
.Entries
[group
][entry
]);
2897 /* Allocate space for per layer struct */
2898 cur_layer
= r
->layers
= malloc(groupcount() * sizeof(toporouter_layer_t
));
2900 /* Foreach layer, read in pad vertices and constraints, and build CDT */
2901 for (group
= 0; group
< max_layer
; group
++) {
2903 printf("*** LAYER GROUP %d ***\n", group
);
2905 if(PCB
->LayerGroups
.Number
[group
] > 0){
2906 cur_layer
->vertices
= NULL
;
2907 cur_layer
->constraints
= NULL
;
2910 printf("reading board constraints from layer %d into group %d\n", PCB
->LayerGroups
.Entries
[group
][0], group
);
2912 read_board_constraints(r
, cur_layer
, PCB
->LayerGroups
.Entries
[group
][0]);
2914 printf("reading points from layer %d into group %d \n",PCB
->LayerGroups
.Entries
[group
][0], group
);
2916 read_points(r
, cur_layer
, PCB
->LayerGroups
.Entries
[group
][0]);
2918 //#ifdef DEBUG_IMPORT
2919 // printf("reading pads from layer %d into group %d\n", number, group);
2921 read_pads(r
, cur_layer
, group
);
2923 GROUP_LOOP(PCB
->Data
, group
)
2927 printf("reading lines from layer %d into group %d\n", number
, group
);
2929 read_lines(r
, cur_layer
, layer
, number
);
2937 printf("building CDT\n");
2939 build_cdt(r
, cur_layer
);
2940 printf("finished\n");
2943 for(i=0;i<groupcount();i++) {
2945 sprintf(buffer, "build%d.png", i);
2946 toporouter_draw_surface(r, r->layers[i].surface, buffer, 2048, 2048, 2, NULL, i, NULL);
2950 printf("finished building CDT\n");
2956 r
->bboxtree
= gts_bb_tree_new(r
->bboxes
);
2961 printf("finished import!\n");
2967 compare_points(gconstpointer a
, gconstpointer b
)
2969 GtsPoint
*i
= GTS_POINT(a
);
2970 GtsPoint
*j
= GTS_POINT(b
);
2973 if(i
->y
== j
->y
) return 0;
2974 if(i
->y
< j
->y
) return -1;
2977 if(i
->x
< j
->x
) return -1;
2982 compare_segments(gconstpointer a
, gconstpointer b
)
2984 if(a
== b
) return 0;
2985 if(a
< b
) return -1;
2988 #define DEBUG_CLUSTER_FIND 1
2989 toporouter_cluster_t
*
2990 cluster_find(toporouter_t
*r
, gdouble x
, gdouble y
, gdouble z
)
2992 GtsPoint
*p
= gts_point_new(gts_point_class(), x
, y
, z
);
2993 GSList
*hits
= gts_bb_tree_stabbed(r
->bboxtree
, p
);
2994 toporouter_cluster_t
*rval
= NULL
;
2996 #ifdef DEBUG_CLUSTER_FIND
2997 printf("FINDING %f,%f,%f\n\n", x
, y
, z
);
3001 toporouter_bbox_t
*box
= TOPOROUTER_BBOX(hits
->data
);
3003 #ifdef DEBUG_CLUSTER_FIND
3004 printf("HIT BOX: "); print_bbox(box
);
3007 if(box
->layer
== (int)z
) {
3008 if(box
->type
!= BOARD
) {
3009 if(box
->type
== LINE
) {
3010 LineType
*line
= (LineType
*)box
->data
;
3011 gint linewind
= coord_wind(line
->Point1
.X
, line
->Point1
.Y
, x
, y
, line
->Point2
.X
, line
->Point2
.Y
);
3013 if(line
->Point1
.X
> x
- EPSILON
&& line
->Point1
.X
< x
+ EPSILON
&&
3014 line
->Point1
.Y
> y
- EPSILON
&& line
->Point1
.Y
< y
+ EPSILON
) {
3015 rval
= box
->cluster
;
3018 if(line
->Point2
.X
> x
- EPSILON
&& line
->Point2
.X
< x
+ EPSILON
&&
3019 line
->Point2
.Y
> y
- EPSILON
&& line
->Point2
.Y
< y
+ EPSILON
) {
3020 rval
= box
->cluster
;
3024 rval
= box
->cluster
;
3028 }else if(box
->surface
) {
3030 if(gts_point_locate(p
, box
->surface
, NULL
)) {
3031 rval
= box
->cluster
;
3041 gts_object_destroy(GTS_OBJECT(p
));
3044 #ifdef DEBUG_CLUSTER_FIND
3045 printf("cluster_find: %f,%f,%f: ", x
, y
, z
);
3046 print_cluster(rval
);
3053 simple_h_cost(toporouter_t
*r
, toporouter_vertex_t
*curpoint
, toporouter_vertex_t
*destpoint
)
3055 gdouble layerpenalty
= (vz(curpoint
) == vz(destpoint
)) ? 0. : r
->viacost
;
3057 return gts_point_distance(GTS_POINT(curpoint
), GTS_POINT(destpoint
)) + layerpenalty
;
3060 #define FCOST(x) (x->gcost + x->hcost)
3062 route_heap_cmp(gpointer item
, gpointer data
)
3064 return FCOST(TOPOROUTER_VERTEX(item
));
3067 #define closelist_insert(p) closelist = g_list_prepend(closelist, p)
3070 toporouter_vertex_t
*key
;
3071 toporouter_vertex_t
*result
;
3072 }toporouter_heap_search_data_t
;
3075 toporouter_heap_search(gpointer data
, gpointer user_data
)
3077 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(data
);
3078 toporouter_heap_search_data_t
*heap_search_data
= (toporouter_heap_search_data_t
*)user_data
;
3079 if(v
== heap_search_data
->key
) heap_search_data
->result
= v
;
3083 toporouter_heap_color(gpointer data, gpointer user_data)
3085 toporouter_vertex_t *v = TOPOROUTER_VERTEX(data);
3086 v->flags |= (guint) user_data;
3090 angle_span(gdouble a1
, gdouble a2
)
3093 return ((2*M_PI
)-a1
+ a2
);
3098 region_span(toporouter_vertex_region_t
*region
)
3102 g_assert(region
->v1
!= NULL
);
3103 g_assert(region
->v2
!= NULL
);
3104 g_assert(region
->origin
!= NULL
);
3106 a1
= point_xangle(GTS_POINT(region
->origin
), GTS_POINT(region
->v1
));
3107 a2
= point_xangle(GTS_POINT(region
->origin
), GTS_POINT(region
->v2
));
3109 return angle_span(a1
, a2
);
3113 edge_capacity(toporouter_edge_t
*e
)
3115 return gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
)));
3119 edge_flow(toporouter_edge_t
*e
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*dest
)
3121 GList
*i
= edge_routing(e
);
3122 toporouter_vertex_t
*pv
= tedge_v1(e
), *v
= NULL
;
3126 if((pv
== v1
|| pv
== v2
) && waiting
) {
3127 flow
+= min_vertex_net_spacing(pv
, dest
);
3135 v
= TOPOROUTER_VERTEX(i
->data
);
3139 flow
+= min_vertex_net_spacing(v
, pv
);
3141 flow
+= min_spacing(v
, pv
);
3143 if((v
== v1
|| v
== v2
) && waiting
) {
3144 flow
+= min_vertex_net_spacing(v
, dest
);
3154 flow
+= min_vertex_net_spacing(tedge_v2(e
), pv
);
3156 flow
+= min_spacing(tedge_v2(e
), pv
);
3162 print_path(GList
*path
)
3168 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3169 // printf("[V %f,%f,%f]\n", vx(v), vy(v), vz(v));
3172 if(v
->child
&& !g_list_find(path
, v
->child
))
3173 printf("\t CHILD NOT IN LIST\n");
3174 if(v
->parent
&& !g_list_find(path
, v
->parent
))
3175 printf("\t parent NOT IN LIST\n");
3183 split_path(GList
*path
)
3185 toporouter_vertex_t
*pv
= NULL
;
3186 GList
*curpath
= NULL
, *i
, *paths
= NULL
;
3192 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3195 printf("v = %f,%f ", vx(v
), vy(v
));
3196 if(v
->parent
) printf("parent = %f,%f ", vx(v
->parent
), vy(v
->parent
));
3197 if(v
->child
) printf("child = %f,%f ", vx(v
->child
), vy(v
->child
));
3201 // if(v) printf("v = %f,%f\n", GTS_POINT(v)->x, GTS_POINT(v)->y);
3202 // if(pv) printf("pv = %f,%f\n", GTS_POINT(pv)->x, GTS_POINT(pv)->y);
3206 if(GTS_POINT(v
)->x
== GTS_POINT(pv
)->x
&& GTS_POINT(v
)->y
== GTS_POINT(pv
)->y
) {
3207 if(g_list_length(curpath
) > 1) paths
= g_list_prepend(paths
, curpath
);
3214 curpath
= g_list_append(curpath
, v
);
3220 if(g_list_length(curpath
) > 1)
3221 paths
= g_list_prepend(paths
, curpath
);
3228 #define edge_gradient(e) (cartesian_gradient(GTS_POINT(GTS_SEGMENT(e)->v1)->x, GTS_POINT(GTS_SEGMENT(e)->v1)->y, \
3229 GTS_POINT(GTS_SEGMENT(e)->v2)->x, GTS_POINT(GTS_SEGMENT(e)->v2)->y))
3232 /* sorting into ascending distance from v1 */
3234 routing_edge_insert(gconstpointer a
, gconstpointer b
, gpointer user_data
)
3236 GtsPoint
*v1
= GTS_POINT(edge_v1(user_data
));
3238 if(gts_point_distance2(v1
, GTS_POINT(a
)) < gts_point_distance2(v1
, GTS_POINT(b
)) - EPSILON
)
3240 if(gts_point_distance2(v1
, GTS_POINT(a
)) > gts_point_distance2(v1
, GTS_POINT(b
)) + EPSILON
)
3243 printf("a = %x b = %x\n", (int) a, (int) b);
3245 printf("WARNING: routing_edge_insert() with same points..\n \
3252 printf("A: "); print_vertex(TOPOROUTER_VERTEX(a));
3253 printf("B: "); print_vertex(TOPOROUTER_VERTEX(b));
3255 TOPOROUTER_VERTEX(a)->flags |= VERTEX_FLAG_RED;
3256 TOPOROUTER_VERTEX(b)->flags |= VERTEX_FLAG_RED;
3262 toporouter_vertex_t
*
3263 new_temp_toporoutervertex(gdouble x
, gdouble y
, toporouter_edge_t
*e
)
3265 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
3266 GList
*i
= edge_routing(e
);
3267 toporouter_vertex_t
*r
;
3270 r
= TOPOROUTER_VERTEX(i
->data
);
3271 if(epsilon_equals(vx(r
),x
) && epsilon_equals(vy(r
),y
)) {
3272 if(r
->flags
& VERTEX_FLAG_TEMP
) return r
;
3277 r
= TOPOROUTER_VERTEX( gts_vertex_new (vertex_class
, x
, y
, vz(edge_v1(e
))) );
3278 r
->flags
|= VERTEX_FLAG_TEMP
;
3281 if(TOPOROUTER_IS_CONSTRAINT(e
))
3282 TOPOROUTER_CONSTRAINT(e
)->routing
= g_list_insert_sorted_with_data(edge_routing(e
), r
, routing_edge_insert
, e
);
3284 e
->routing
= g_list_insert_sorted_with_data(edge_routing(e
), r
, routing_edge_insert
, e
);
3290 /* create vertex on edge e at radius r from v, closest to ref */
3291 toporouter_vertex_t
*
3292 new_temp_toporoutervertex_in_segment(toporouter_edge_t
*e
, toporouter_vertex_t
*v
, gdouble r
, toporouter_vertex_t
*ref
)
3294 gdouble m
= edge_gradient(e
);
3295 toporouter_spoint_t p
, np1
, np2
;
3296 // toporouter_vertex_t *b = TOPOROUTER_VERTEX((GTS_VERTEX(v) == edge_v1(e)) ? edge_v2(e) : edge_v1(e));
3297 toporouter_vertex_t
*rval
= NULL
;
3298 p
.x
= vx(v
); p
.y
= vy(v
);
3300 vertices_on_line(&p
, m
, r
, &np1
, &np2
);
3302 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)) )
3303 rval
= new_temp_toporoutervertex(np1
.x
, np1
.y
, e
);
3305 rval
= new_temp_toporoutervertex(np2
.x
, np2
.y
, e
);
3311 vertex_keepout_test(toporouter_t
*r
, toporouter_vertex_t
*v
)
3313 GList
*i
= r
->keepoutlayers
;
3315 gdouble keepout
= *((double *) i
->data
);
3316 if(vz(v
) == keepout
) return 1;
3323 closest_cluster_pair(toporouter_t
*r
, GList
*src_vertices
, GList
*dest_vertices
, toporouter_vertex_t
**a
, toporouter_vertex_t
**b
)
3325 GList
*i
= src_vertices
, *j
= dest_vertices
;
3328 *a
= NULL
; *b
= NULL
;
3332 toporouter_vertex_t
*v1
= TOPOROUTER_VERTEX(i
->data
);
3334 if(vertex_keepout_test(r
, v1
)) { i
= i
->next
; continue; }
3338 toporouter_vertex_t
*v2
= TOPOROUTER_VERTEX(j
->data
);
3339 if(vertex_keepout_test(r
, v2
) || vz(v2
) != vz(v1
)) { j
= j
->next
; continue; }
3342 *a
= v1
; *b
= v2
; min
= simple_h_cost(r
, *a
, *b
);
3344 gdouble tempd
= simple_h_cost(r
, v1
, v2
);
3345 if(r
->flags
& TOPOROUTER_FLAG_GOFAR
&& tempd
> min
) {
3346 *a
= v1
; *b
= v2
; min
= tempd
;
3349 *a
= v1
; *b
= v2
; min
= tempd
;
3359 // g_list_free(src_vertices);
3360 // g_list_free(dest_vertices);
3364 toporouter_vertex_t
*
3365 closest_dest_vertex(toporouter_t
*r
, toporouter_vertex_t
*v
, toporouter_route_t
*routedata
)
3367 GList
//*vertices = cluster_vertices(r, routedata->dest),
3368 *i
= routedata
->destvertices
;
3369 toporouter_vertex_t
*closest
= NULL
;
3370 gdouble closest_distance
= 0.;
3372 // if(routedata->flags & TOPOROUTER_FLAG_FLEX) i = r->destboxes;
3375 toporouter_vertex_t
*cv
= TOPOROUTER_VERTEX(i
->data
);
3377 if(vz(cv
) != vz(v
)) { i
= i
->next
; continue; }
3380 closest
= cv
; closest_distance
= simple_h_cost(r
, v
, closest
);
3382 gdouble tempd
= simple_h_cost(r
, v
, cv
);
3383 if(r
->flags
& TOPOROUTER_FLAG_GOFAR
&& tempd
> closest_distance
) {
3384 closest
= cv
; closest_distance
= tempd
;
3386 if(tempd
< closest_distance
) {
3387 closest
= cv
; closest_distance
= tempd
;
3393 // g_list_free(vertices);
3396 printf("CLOSEST = %f,%f,%f\n", vx(closest
), vy(closest
), vz(closest
));
3401 #define toporouter_edge_gradient(e) (cartesian_gradient(vx(edge_v1(e)), vy(edge_v1(e)), vx(edge_v2(e)), vy(edge_v2(e))))
3404 /* returns the capacity of the triangle cut through v */
3406 triangle_interior_capacity(GtsTriangle
*t
, toporouter_vertex_t
*v
)
3408 toporouter_edge_t
*e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3409 gdouble x
, y
, m1
, m2
, c2
, c1
, len
;
3413 m1
= toporouter_edge_gradient(e
);
3414 m2
= perpendicular_gradient(m1
);
3415 c2
= (isinf(m2
)) ? vx(v
) : vy(v
) - (m2
* vx(v
));
3416 c1
= (isinf(m1
)) ? vx(edge_v1(e
)) : vy(edge_v1(e
)) - (m1
* vx(edge_v1(e
)));
3423 x
= (c2
- c1
) / (m1
- m2
);
3425 y
= (isinf(m2
)) ? vy(edge_v1(e
)) : (m2
* x
) + c2
;
3427 len
= gts_point_distance2(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
)));
3430 printf("%f,%f len = %f v = %f,%f\n", x
, y
, len
, vx(v
), vy(v
));
3433 if(epsilon_equals(x
,vx(edge_v1(e
))) && epsilon_equals(y
,vy(edge_v1(e
)))) return INFINITY
;
3434 if(epsilon_equals(x
,vx(edge_v2(e
))) && epsilon_equals(y
,vy(edge_v2(e
)))) return INFINITY
;
3436 if(x
>= MIN(vx(edge_v1(e
)),vx(edge_v2(e
))) &&
3437 x
<= MAX(vx(edge_v1(e
)),vx(edge_v2(e
))) &&
3438 y
>= MIN(vy(edge_v1(e
)),vy(edge_v2(e
))) &&
3439 y
<= MAX(vy(edge_v1(e
)),vy(edge_v2(e
))))
3441 // 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 )
3442 return sqrt(pow(vx(v
) - x
, 2) + pow(vy(v
) - y
, 2));
3447 inline toporouter_vertex_t
*
3448 segment_common_vertex(GtsSegment
*s1
, GtsSegment
*s2
)
3450 if(!s1
|| !s2
) return NULL
;
3451 if(s1
->v1
== s2
->v1
) return TOPOROUTER_VERTEX(s1
->v1
);
3452 if(s1
->v2
== s2
->v1
) return TOPOROUTER_VERTEX(s1
->v2
);
3453 if(s1
->v1
== s2
->v2
) return TOPOROUTER_VERTEX(s1
->v1
);
3454 if(s1
->v2
== s2
->v2
) return TOPOROUTER_VERTEX(s1
->v2
);
3458 inline toporouter_vertex_t
*
3459 route_vertices_common_vertex(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
3461 return segment_common_vertex(GTS_SEGMENT(v1
->routingedge
), GTS_SEGMENT(v2
->routingedge
));
3466 edges_third_edge(GtsSegment
*s1
, GtsSegment
*s2
, toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
3468 if(!s1
|| !s2
) return 0;
3469 if(s1
->v1
== s2
->v1
) {
3470 *v1
= TOPOROUTER_VERTEX(s1
->v2
);
3471 *v2
= TOPOROUTER_VERTEX(s2
->v2
);
3474 if(s1
->v2
== s2
->v1
) {
3475 *v1
= TOPOROUTER_VERTEX(s1
->v1
);
3476 *v2
= TOPOROUTER_VERTEX(s2
->v2
);
3479 if(s1
->v1
== s2
->v2
) {
3480 *v1
= TOPOROUTER_VERTEX(s1
->v2
);
3481 *v2
= TOPOROUTER_VERTEX(s2
->v1
);
3484 if(s1
->v2
== s2
->v2
) {
3485 *v1
= TOPOROUTER_VERTEX(s1
->v1
);
3486 *v2
= TOPOROUTER_VERTEX(s2
->v1
);
3492 /* returns the flow from e1 to e2, and the flow from the vertex oppisate e1 to
3493 * e1 and the vertex oppisate e2 to e2 */
3495 flow_from_edge_to_edge(GtsTriangle
*t
, toporouter_edge_t
*e1
, toporouter_edge_t
*e2
,
3496 toporouter_vertex_t
*common_v
, toporouter_vertex_t
*curpoint
)
3499 toporouter_vertex_t
*pv
= common_v
, *v
;
3500 toporouter_edge_t
*op_edge
;
3502 GList
*i
= edge_routing(e1
);
3504 v
= TOPOROUTER_VERTEX(i
->data
);
3507 r
+= min_spacing(v
, pv
);
3509 i
= i
->next
; continue;
3511 // if(!(v->flags & VERTEX_FLAG_TEMP)) {
3512 if((v
->flags
& VERTEX_FLAG_ROUTE
)) {
3514 if(v
->parent
->routingedge
== e2
) {
3515 r
+= min_spacing(v
, pv
);
3517 i
= i
->next
; continue;
3521 if(v
->child
->routingedge
== e2
) {
3522 r
+= min_spacing(v
, pv
);
3524 i
= i
->next
; continue;
3530 op_edge
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(common_v
)));
3536 v
= segment_common_vertex(GTS_SEGMENT(e2
), GTS_SEGMENT(op_edge
));
3539 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e1)));
3540 if(v
->flags
& VERTEX_FLAG_ROUTE
&& v
->parent
&& v
->parent
->routingedge
) {
3541 if(v
->parent
->routingedge
== e1
)
3542 r
+= min_spacing(v
, pv
);
3545 v
= segment_common_vertex(GTS_SEGMENT(e1
), GTS_SEGMENT(op_edge
));
3548 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e2)));
3549 if(v
->flags
& VERTEX_FLAG_ROUTE
&& v
->parent
&& v
->parent
->routingedge
) {
3550 if(v
->parent
->routingedge
== e1
)
3551 r
+= min_spacing(v
, pv
);
3554 if(TOPOROUTER_IS_CONSTRAINT(op_edge
)) {
3555 toporouter_bbox_t
*box
= vertex_bbox(TOPOROUTER_VERTEX(edge_v1(op_edge
)));
3556 r
+= vertex_net_thickness(v
) / 2.;
3558 r
+= MAX(vertex_net_keepaway(v
), cluster_keepaway(box
->cluster
));
3559 r
+= cluster_thickness(box
->cluster
) / 2.;
3561 r
+= vertex_net_keepaway(v
);
3572 check_triangle_interior_capacity(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_vertex_t
*curpoint
,
3573 toporouter_edge_t
*op_edge
, toporouter_edge_t
*adj_edge1
, toporouter_edge_t
*adj_edge2
)
3575 gdouble ic
= triangle_interior_capacity(t
, v
);
3576 gdouble flow
= flow_from_edge_to_edge(t
, adj_edge1
, adj_edge2
, v
, curpoint
);
3578 if(TOPOROUTER_IS_CONSTRAINT(adj_edge1
) || TOPOROUTER_IS_CONSTRAINT(adj_edge2
)) return 1;
3583 printf("fail interior capacity flow = %f ic = %f\n", flow
, ic
);
3591 toporouter_vertex_t
*
3592 edge_routing_next_not_temp(toporouter_edge_t
*e
, GList
*list
)
3594 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3596 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(list
->data
);
3597 if(!(v
->flags
& VERTEX_FLAG_TEMP
))
3606 toporouter_vertex_t
*
3607 edge_routing_prev_not_temp(toporouter_edge_t
*e
, GList
*list
)
3609 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3611 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(list
->data
);
3612 if(!(v
->flags
& VERTEX_FLAG_TEMP
))
3622 edge_adjacent_vertices(toporouter_edge_t
*e
, toporouter_vertex_t
*v
, toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
3624 GList
*r
= g_list_find(edge_routing(e
), v
);
3626 if(v
== tedge_v1(e
)) {
3628 *v2
= edge_routing_next_not_temp(e
, edge_routing(e
));
3629 }else if(v
== tedge_v2(e
)) {
3630 *v1
= edge_routing_prev_not_temp(e
, g_list_last(edge_routing(e
)));
3633 // r = g_list_find(r, v);
3634 *v1
= edge_routing_prev_not_temp(e
, r
);
3635 *v2
= edge_routing_next_not_temp(e
, r
);
3643 candidate_vertices(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*dest
, toporouter_edge_t
*e
)
3645 gdouble totald
, v1ms
, v2ms
, flow
, capacity
, ms
;
3652 g_assert(!(v1
->flags
& VERTEX_FLAG_TEMP
));
3653 g_assert(!(v2
->flags
& VERTEX_FLAG_TEMP
));
3655 printf("starting candidate vertices\n");
3656 printf("v1 = %f,%f v2 = %f,%f dest = %f,%f\n", vx(v1
), vy(v1
), vx(v2
), vy(v2
), vx(dest
), vy(dest
));
3658 totald
= gts_point_distance(GTS_POINT(v1
), GTS_POINT(v2
));
3659 v1ms
= min_spacing(v1
, dest
);
3660 v2ms
= min_spacing(v2
, dest
);
3661 ms
= min_spacing(dest
, dest
);
3662 flow
= TOPOROUTER_IS_CONSTRAINT(e
) ? 0. : edge_flow(e
, v1
, v2
, dest
);
3663 capacity
= edge_capacity(e
);
3666 g_assert(totald
> 0);
3668 printf("v1ms = %f v2ms = %f totald = %f ms = %f capacity = %f flow = %f\n", v1ms
, v2ms
, totald
, ms
, capacity
, flow
);
3671 if(flow
>= capacity
) return NULL
;
3674 if(v1ms
+ v2ms
+ ms
>= totald
) {
3675 vs
= g_list_prepend(vs
, new_temp_toporoutervertex((vx(v1
)+vx(v2
)) / 2., (vy(v1
)+vy(v2
)) / 2., e
));
3677 gdouble x0
, y0
, x1
, y1
, d
;
3679 vertex_move_towards_vertex_values(GTS_VERTEX(v1
), GTS_VERTEX(v2
), v1ms
, &x0
, &y0
);
3681 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x0
, y0
, e
));
3683 vertex_move_towards_vertex_values(GTS_VERTEX(v2
), GTS_VERTEX(v1
), v2ms
, &x1
, &y1
);
3685 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x1
, y1
, e
));
3687 d
= sqrt(pow(x0
-x1
,2) + pow(y0
-y1
,2));
3690 // guint nint = d / ms;
3691 // gdouble dif = d / (nint + 1);
3692 gdouble dif
= d
/ 2;
3694 // for(guint j=0;j<nint;j++) {
3697 // coord_move_towards_coord_values(x0, y0, x1, y1, dif * j, &x, &y);
3698 coord_move_towards_coord_values(x0
, y0
, x1
, y1
, dif
, &x
, &y
);
3700 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x
, y
, e
));
3708 printf("candidate vertices returning %d\n", g_list_length(vs
));
3714 edge_routing_first_not_temp(toporouter_edge_t
*e
)
3716 GList
*i
= edge_routing(e
);
3717 toporouter_vertex_t
*v
;
3720 v
= TOPOROUTER_VERTEX(i
->data
);
3721 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) return i
;
3730 edge_routing_last_not_temp(toporouter_edge_t
*e
)
3732 GList
*i
= edge_routing(e
), *last
= NULL
;
3733 toporouter_vertex_t
*v
;
3736 v
= TOPOROUTER_VERTEX(i
->data
);
3737 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) last
= i
;
3746 delete_vertex(toporouter_vertex_t
*v
)
3749 if(v
->flags
& VERTEX_FLAG_TEMP
) {
3750 if(v
->routingedge
) {
3751 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
3752 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
);
3754 v
->routingedge
->routing
= g_list_remove(v
->routingedge
->routing
, v
);
3757 gts_object_destroy ( GTS_OBJECT(v
) );
3761 #define edge_is_blocked(e) (TOPOROUTER_IS_EDGE(e) ? (e->flags & EDGE_FLAG_DIRECTCONNECTION) : 0)
3764 triangle_candidate_points_from_vertex(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_vertex_t
*dest
, toporouter_route_t
*routedata
)
3766 toporouter_edge_t
*op_e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3767 toporouter_vertex_t
*vv1
, *vv2
, *constraintv
= NULL
;
3768 toporouter_edge_t
*e1
, *e2
;
3773 printf("\tTRIANGLE CAND POINT FROM VERTEX\n");
3778 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), edge_v1(op_e
)));
3779 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), edge_v2(op_e
)));
3782 if(TOPOROUTER_IS_CONSTRAINT(op_e
)) {
3783 if(TOPOROUTER_CONSTRAINT(op_e
)->box
->type
== BOARD
) {
3785 printf("BOARD constraint\n");
3789 if(constraint_netlist(TOPOROUTER_CONSTRAINT(op_e
)) != vertex_netlist(dest
)) { // || TOPOROUTER_CONSTRAINT(op_e)->routing) {
3791 printf("op_e routing:\n");
3797 printf("RETURNING CONSTRAINT POING\n");
3799 constraintv
= new_temp_toporoutervertex_in_segment(op_e
, TOPOROUTER_VERTEX(edge_v1(op_e
)),
3800 gts_point_distance(GTS_POINT(edge_v1(op_e
)), GTS_POINT(edge_v2(op_e
))) / 2., TOPOROUTER_VERTEX(edge_v2(op_e
)));
3801 // return g_list_prepend(NULL, vv1);
3806 if(edge_is_blocked(op_e
)) {
3807 goto triangle_candidate_points_from_vertex_exit
;
3809 // v1 = tedge_v1(op_e);
3810 // v2 = tedge_v2(op_e);
3812 if(v
== tedge_v1(e1
)) {
3813 i
= edge_routing_first_not_temp(e1
);
3815 i
= edge_routing_last_not_temp(e1
);
3819 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3821 if(temp
->parent
== tedge_v2(op_e
) || temp
->child
== tedge_v2(op_e
)) {
3823 printf("temp -> op_e->v2\n");
3825 goto triangle_candidate_points_from_vertex_exit
;
3827 if(temp
->parent
->routingedge
== op_e
) {
3830 printf("vv1->parent\n");
3833 }else if(temp
->child
->routingedge
== op_e
) {
3836 printf("vv1->child\n");
3842 printf("temp -> e2?\n");
3843 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
)) );
3844 if(temp
->parent
->routingedge
)
3845 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3846 vx(edge_v1(temp
->parent
->routingedge
)), vy(edge_v1(temp
->parent
->routingedge
)),
3847 vx(edge_v2(temp
->parent
->routingedge
)), vy(edge_v2(temp
->parent
->routingedge
))
3850 printf("temp->parent->routingedge = NULL\n");
3852 if(temp
->child
->routingedge
)
3853 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3854 vx(edge_v1(temp
->child
->routingedge
)), vy(edge_v1(temp
->child
->routingedge
)),
3855 vx(edge_v2(temp
->child
->routingedge
)), vy(edge_v2(temp
->child
->routingedge
))
3858 printf("temp->child->routingedge = NULL\n");
3860 goto triangle_candidate_points_from_vertex_exit
;
3864 vv1
= tedge_v1(op_e
);
3866 printf("nothing on e1\n");
3870 if(v
== tedge_v1(e2
)) {
3871 i
= edge_routing_first_not_temp(e2
);
3873 i
= edge_routing_last_not_temp(e2
);
3877 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3879 if(temp
->parent
== tedge_v1(op_e
) || temp
->child
== tedge_v1(op_e
)) {
3881 printf("temp -> op_e->v2\n");
3883 goto triangle_candidate_points_from_vertex_exit
;
3886 if(temp
->parent
->routingedge
== op_e
) {
3889 printf("vv2->parent\n");
3891 }else if(temp
->child
->routingedge
== op_e
) {
3894 printf("vv2->child\n");
3900 printf("temp -> e1?\n");
3901 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
)) );
3902 if(temp
->parent
->routingedge
)
3903 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3904 vx(edge_v1(temp
->parent
->routingedge
)), vy(edge_v1(temp
->parent
->routingedge
)),
3905 vx(edge_v2(temp
->parent
->routingedge
)), vy(edge_v2(temp
->parent
->routingedge
))
3908 printf("temp->parent->routingedge = NULL\n");
3910 if(temp
->child
->routingedge
)
3911 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3912 vx(edge_v1(temp
->child
->routingedge
)), vy(edge_v1(temp
->child
->routingedge
)),
3913 vx(edge_v2(temp
->child
->routingedge
)), vy(edge_v2(temp
->child
->routingedge
))
3916 printf("temp->child->routingedge = NULL\n");
3918 goto triangle_candidate_points_from_vertex_exit
;
3922 vv2
= tedge_v2(op_e
);
3924 printf("nothing on e2\n");
3929 printf("size of e1 routing = %d e2 routing = %d op_e routing = %d\n",
3930 g_list_length(edge_routing(e1
)), g_list_length(edge_routing(e2
)), g_list_length(edge_routing(op_e
)));
3935 print_vertex(constraintv
);
3936 printf("constraintv %f,%f returning\n", vx(constraintv
), vy(constraintv
));
3938 return g_list_prepend(NULL
, constraintv
);
3941 i
= edge_routing(op_e
);
3943 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3945 if(temp
->parent
== v
|| temp
->child
== v
) {
3946 rval
= g_list_concat(rval
, candidate_vertices(vv1
, temp
, dest
, op_e
));
3953 rval
= g_list_concat(rval
, candidate_vertices(vv1
, vv2
, dest
, op_e
));
3959 triangle_candidate_points_from_vertex_exit
:
3960 if(constraintv
) //delete_vertex(constraintv);
3961 g_hash_table_insert(routedata
->alltemppoints
, constraintv
, constraintv
);
3969 routedata_insert_temppoints(toporouter_route_t
*data
, GList
*temppoints
) {
3970 GList
*j
= temppoints
;
3972 g_hash_table_insert(data
->alltemppoints
, j
->data
, j
->data
);
3979 constraint_route_test(toporouter_constraint_t
*c
, toporouter_route_t
*routedata
)
3981 if(c
->box
->cluster
&& c
->box
->cluster
->netlist
== routedata
->src
->netlist
) {
3982 if(c
->box
->cluster
->c
== routedata
->dest
->c
|| c
->box
->cluster
->c
== routedata
->src
->c
) return 1;
3988 all_candidates_on_edge(toporouter_edge_t
*e
, toporouter_route_t
*routedata
)
3991 if(edge_is_blocked(e
)) return NULL
;
3993 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3994 GList
*i
= edge_routing(e
);
3995 toporouter_vertex_t
*pv
= tedge_v1(e
);
3998 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3999 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) {
4000 rval
= g_list_concat(rval
, candidate_vertices(pv
, v
, TOPOROUTER_VERTEX(routedata
->destvertices
->data
), e
));
4006 rval
= g_list_concat(rval
, candidate_vertices(pv
, tedge_v2(e
), TOPOROUTER_VERTEX(routedata
->destvertices
->data
), e
));
4007 }else if(TOPOROUTER_CONSTRAINT(e
)->box
->type
== BOARD
) {
4009 }else if(constraint_route_test(TOPOROUTER_CONSTRAINT(e
), routedata
)) {
4010 toporouter_vertex_t
*consv
= new_temp_toporoutervertex_in_segment(e
, tedge_v1(e
), tvdistance(tedge_v1(e
), tedge_v2(e
)) / 2., tedge_v2(e
));
4011 rval
= g_list_prepend(rval
, consv
);
4012 // g_hash_table_insert(routedata->alltemppoints, consv, consv);
4019 triangle_all_candidate_points_from_vertex(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_route_t
*routedata
)
4021 toporouter_edge_t
*op_e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
4022 return all_candidates_on_edge(op_e
, routedata
);
4026 triangle_all_candidate_points_from_edge(toporouter_t
*r
, GtsTriangle
*t
, toporouter_edge_t
*e
, toporouter_route_t
*routedata
,
4027 toporouter_vertex_t
**dest
, toporouter_vertex_t
*curpoint
)
4029 toporouter_vertex_t
*op_v
;
4030 toporouter_edge_t
*e1
, *e2
;
4031 GList
*i
, *rval
= NULL
, *rval2
= NULL
;
4032 toporouter_vertex_t
*boxpoint
= NULL
;
4033 guint e1intcap
, e2intcap
;
4035 op_v
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t
, GTS_EDGE(e
)));
4038 if(vertex_bbox(op_v
)) boxpoint
= TOPOROUTER_VERTEX(vertex_bbox(op_v
)->point
);
4040 if(g_list_find(routedata
->destvertices
, op_v
)) {
4041 rval
= g_list_prepend(rval
, op_v
);
4044 }else if(g_list_find(routedata
->destvertices
, boxpoint
)) {
4046 }else if(g_list_find(routedata
->srcvertices
, op_v
)) {
4047 rval
= g_list_prepend(rval
, op_v
);
4050 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v1(e
)));
4051 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v2(e
)));
4053 rval
= g_list_concat(rval
, all_candidates_on_edge(e1
, routedata
));
4054 rval
= g_list_concat(rval
, all_candidates_on_edge(e2
, routedata
));
4056 e1intcap
= check_triangle_interior_capacity(t
, tedge_v1(e
), curpoint
, e2
, e
, e1
);
4057 e2intcap
= check_triangle_interior_capacity(t
, tedge_v2(e
), curpoint
, e1
, e
, e2
);
4061 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4064 rval2
= g_list_prepend(rval2
, v
);
4065 else if(v
->routingedge
== e1
&& !(!TOPOROUTER_IS_CONSTRAINT(e1
) && !e1intcap
))
4066 rval2
= g_list_prepend(rval2
, v
);
4067 else if(v
->routingedge
== e2
&& !(!TOPOROUTER_IS_CONSTRAINT(e2
) && !e2intcap
))
4068 rval2
= g_list_prepend(rval2
, v
);
4078 triangle_candidate_points_from_edge(toporouter_t
*r
, GtsTriangle
*t
, toporouter_edge_t
*e
, toporouter_vertex_t
*v
, toporouter_vertex_t
**dest
,
4079 toporouter_route_t
*routedata
)
4081 toporouter_vertex_t
*v1
, *v2
, *op_v
, *vv
= NULL
, *e1constraintv
= NULL
, *e2constraintv
= NULL
;
4082 toporouter_edge_t
*e1
, *e2
;
4083 GList
*e1cands
= NULL
, *e2cands
= NULL
, *rval
= NULL
;
4084 guint noe1
= 0, noe2
= 0;
4086 op_v
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t
, GTS_EDGE(e
)));
4088 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v1(e
)));
4089 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v2(e
)));
4093 // v1 is prev dir, v2 is next dir
4094 edge_adjacent_vertices(e
, v
, &v1
, &v2
);
4096 if(TOPOROUTER_IS_CONSTRAINT(e1
)) {
4097 GList
*i
= edge_routing(e1
);
4099 if(TOPOROUTER_CONSTRAINT(e1
)->box
->type
== BOARD
) {
4101 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e1
), routedata
)) {
4104 printf("noe1 netlist\n");
4108 if(v1
== tedge_v1(e
) ||
4109 (v1
->parent
->routingedge
&& v1
->parent
->routingedge
== e1
) ||
4110 (v1
->child
->routingedge
&& v1
->child
->routingedge
== e1
)) {
4111 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
));
4115 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
4117 if((temp
->child
== tedge_v2(e
) || temp
->parent
== tedge_v2(e
)) && !(temp
->flags
& VERTEX_FLAG_TEMP
)) noe2
= 1;
4122 goto triangle_candidate_points_e2
;
4125 if(edge_is_blocked(e1
)) {
4127 goto triangle_candidate_points_e2
;
4130 if(v1
== tedge_v1(e
)) {
4132 toporouter_vertex_t
*vv1
, *vv2
;
4133 edge_adjacent_vertices(e1
, v1
, &vv1
, &vv2
);
4136 printf("v1 == e->v1\n");
4140 // candidates from v1 until vv1
4143 // candidates from v1 until vv2
4147 if(!e1constraintv
) e1cands
= candidate_vertices(v1
, vv
, *dest
, e1
);
4150 if(vv
->parent
== tedge_v2(e
) || vv
->child
== tedge_v2(e
)) {
4158 }else if(v1
->parent
!= op_v
&& v1
->child
!= op_v
) {
4159 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4162 printf("v1 != e->v1\n");
4165 if(v1
->parent
->routingedge
== e1
) {
4168 printf("v1 parent = e1\n");
4170 if(op_v
== tedge_v1(e1
)) {
4171 // candidates from v1->parent until prev vertex
4172 vv2
= edge_routing_prev_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->parent
)->prev
);
4174 // candidates from v1->parent until next vertex
4175 vv2
= edge_routing_next_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->parent
)->next
);
4178 }else if(v1
->child
->routingedge
== e1
) {
4181 printf("v1 child = e1\n");
4183 if(op_v
== tedge_v1(e1
)) {
4184 // candidates from v1->child until prev vertex
4185 vv2
= edge_routing_prev_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->child
)->prev
);
4187 // candidates from v1->child until next vertex
4188 vv2
= edge_routing_next_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->child
)->next
);
4195 goto triangle_candidate_points_e2
;
4199 if(vv2
->parent
== tedge_v2(e
) || vv2
->child
== tedge_v2(e
)) {
4206 if(!e1constraintv
) e1cands
= candidate_vertices(vv1
, vv2
, *dest
, e1
);
4212 if(vv
&& vv
== op_v
) {
4213 toporouter_vertex_t
*boxpoint
= NULL
;
4215 if(vertex_bbox(op_v
)) boxpoint
= TOPOROUTER_VERTEX(vertex_bbox(op_v
)->point
);
4217 if(g_list_find(routedata
->destvertices
, op_v
)) {
4218 rval
= g_list_prepend(rval
, op_v
);
4220 }else if(g_list_find(routedata
->destvertices
, boxpoint
)) {
4222 }else if(g_list_find(routedata
->srcvertices
, op_v
)) {
4223 rval
= g_list_prepend(rval
, op_v
);
4227 triangle_candidate_points_e2
:
4230 // printf("noe2\n");
4231 goto triangle_candidate_points_finish
;
4234 if(TOPOROUTER_IS_CONSTRAINT(e2
)) {
4235 GList
*i
= edge_routing(e2
);
4237 if(TOPOROUTER_CONSTRAINT(e2
)->box
->type
== BOARD
) {
4239 // goto triangle_candidate_points_finish;
4240 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e2
), routedata
)) {
4242 printf("noe2 netlist\n");
4245 // goto triangle_candidate_points_finish;
4246 }else if(v2
== tedge_v2(e
) ||
4247 (v2
->parent
->routingedge
&& v2
->parent
->routingedge
== e2
) ||
4248 (v2
->child
->routingedge
&& v2
->child
->routingedge
== e2
)) {
4250 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
));
4255 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
4257 if((temp
->child
== tedge_v1(e
) || temp
->parent
== tedge_v1(e
)) && !(temp
->flags
& VERTEX_FLAG_TEMP
))
4265 goto triangle_candidate_points_finish
;
4268 if(edge_is_blocked(e2
)) {
4270 goto triangle_candidate_points_finish
;
4273 if(v2
== tedge_v2(e
)) {
4275 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4276 edge_adjacent_vertices(e2
, v2
, &vv1
, &vv2
);
4279 printf("v2 == e->v2\n");
4283 // candidates from v2 until vv1
4286 // candidates from v2 until vv2
4290 if(!e2constraintv
) e2cands
= candidate_vertices(v2
, vv
, *dest
, e2
);
4293 if(vv
->parent
== tedge_v1(e
) || vv
->child
== tedge_v1(e
)) {
4301 }else if(v2
->parent
!= op_v
&& v2
->child
!= op_v
) {
4302 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4305 printf("v2 == e->v2\n");
4308 if(v2
->parent
->routingedge
== e2
) {
4310 if(op_v
== tedge_v1(e2
)) {
4311 // candidates from v2->parent until prev vertex
4312 vv2
= edge_routing_prev_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->prev
);
4314 // candidates from v2->parent until next vertex
4315 vv2
= edge_routing_next_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->next
);
4318 }else if(v2
->child
->routingedge
== e2
) {
4320 if(op_v
== tedge_v1(e2
)) {
4321 // candidates from v2->child until prev vertex
4322 vv2
= edge_routing_prev_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->prev
);
4324 // candidates from v2->child until next vertex
4325 vv2
= edge_routing_next_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->next
);
4329 goto triangle_candidate_points_finish
;
4333 if(vv2
->parent
== tedge_v1(e
) || vv2
->child
== tedge_v1(e
)) {
4340 if(!e2constraintv
) e2cands
= candidate_vertices(vv1
, vv2
, *dest
, e2
);
4344 triangle_candidate_points_finish
:
4346 v1
= segment_common_vertex(GTS_SEGMENT(e
), GTS_SEGMENT(e1
));
4347 v2
= segment_common_vertex(GTS_SEGMENT(e
), GTS_SEGMENT(e2
));
4349 if(noe1
|| !check_triangle_interior_capacity(t
, v1
, v
, e2
, e
, e1
)) {
4351 printf("freeing e1cands\n");
4353 routedata_insert_temppoints(routedata
, e1cands
);
4354 g_list_free(e1cands
);
4358 if(noe2
|| !check_triangle_interior_capacity(t
, v2
, v
, e1
, e
, e2
)) {
4360 printf("freeing e2cands\n");
4362 routedata_insert_temppoints(routedata
, e2cands
);
4363 g_list_free(e2cands
);
4367 if(!noe1
&& e1constraintv
) {
4368 e1cands
= g_list_prepend(e1cands
, e1constraintv
);
4369 }else if(e1constraintv
) {
4370 g_hash_table_insert(routedata
->alltemppoints
, e1constraintv
, e1constraintv
);
4371 // delete_vertex(e1constraintv);
4374 if(!noe2
&& e2constraintv
) {
4375 e2cands
= g_list_prepend(e2cands
, e2constraintv
);
4376 }else if(e2constraintv
) {
4377 g_hash_table_insert(routedata
->alltemppoints
, e2constraintv
, e2constraintv
);
4378 // delete_vertex(e2constraintv);
4381 if(!noe1
&& !noe2
) return g_list_concat(rval
, g_list_concat(e1cands
, e2cands
));
4383 return g_list_concat(e1cands
, e2cands
);
4387 compute_candidate_points(toporouter_t
*tr
, toporouter_layer_t
*l
, toporouter_vertex_t
*curpoint
, toporouter_route_t
*data
,
4388 toporouter_vertex_t
**closestdest
)
4390 GList
*r
= NULL
, *j
;
4391 toporouter_edge_t
*edge
= curpoint
->routingedge
, *tempedge
;
4393 if(vertex_keepout_test(tr
, curpoint
)) goto compute_candidate_points_finish
;
4395 /* direct connection */
4396 // if(curpoint == TOPOROUTER_VERTEX(data->src->point))
4397 if((tempedge
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(curpoint
), GTS_VERTEX(*closestdest
))))) {
4399 if(TOPOROUTER_IS_CONSTRAINT(tempedge
)) {
4400 goto compute_candidate_points_finish
;
4402 if(!tempedge
->routing
) {
4403 r
= g_list_prepend(NULL
, *closestdest
);
4404 tempedge
->flags
|= EDGE_FLAG_DIRECTCONNECTION
;
4405 goto compute_candidate_points_finish
;
4408 printf("Direct connection, but has routing\n");
4413 /* if we get to here, there is routing blocking the direct connection,
4414 * continue as per normal */
4417 /* a real point origin */
4418 if(!(curpoint
->flags
& VERTEX_FLAG_TEMP
)) {
4419 GSList
*triangles
, *i
;
4420 i
= triangles
= gts_vertex_triangles(GTS_VERTEX(curpoint
), NULL
);
4422 printf("triangle count = %d\n", g_slist_length(triangles
));
4425 GtsTriangle
*t
= GTS_TRIANGLE(i
->data
);
4428 if(tr
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) temppoints
= triangle_all_candidate_points_from_vertex(t
, curpoint
, data
);
4429 else temppoints
= triangle_candidate_points_from_vertex(t
, curpoint
, *closestdest
, data
);
4432 printf("\treturned %d points\n", g_list_length(temppoints
));
4434 routedata_insert_temppoints(data
, temppoints
);
4436 r
= g_list_concat(r
, temppoints
);
4439 g_slist_free(triangles
);
4440 }else /* a temp point */ {
4441 int prevwind
= vertex_wind(GTS_SEGMENT(edge
)->v1
, GTS_SEGMENT(edge
)->v2
, GTS_VERTEX(curpoint
->parent
));
4442 // printf("tempoint\n");
4444 GSList
*i
= GTS_EDGE(edge
)->triangles
;
4447 GtsVertex
*oppv
= gts_triangle_vertex_opposite(GTS_TRIANGLE(i
->data
), GTS_EDGE(edge
));
4448 if(prevwind
!= vertex_wind(GTS_SEGMENT(edge
)->v1
, GTS_SEGMENT(edge
)->v2
, oppv
)) {
4451 if(tr
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) temppoints
= triangle_all_candidate_points_from_edge(tr
, GTS_TRIANGLE(i
->data
), edge
,
4452 data
, closestdest
, curpoint
);
4453 else temppoints
= triangle_candidate_points_from_edge(tr
, GTS_TRIANGLE(i
->data
), edge
, curpoint
, closestdest
, data
);
4457 toporouter_vertex_t
*tempj
= TOPOROUTER_VERTEX(j
->data
);
4458 if(tempj
->flags
& VERTEX_FLAG_TEMP
)
4459 g_hash_table_insert(data
->alltemppoints
, j
->data
, j
->data
);
4462 printf("got cand not a temp\n");
4466 r
= g_list_concat(r
, temppoints
);
4474 compute_candidate_points_finish
:
4476 if(vertex_bbox(curpoint
) && vertex_bbox(curpoint
)->cluster
) {
4477 if(vertex_bbox(curpoint
)->cluster
->c
== data
->src
->c
) {
4478 r
= g_list_concat(r
, g_list_copy(data
->srcvertices
));
4486 temp_point_clean(gpointer key
, gpointer value
, gpointer user_data
)
4488 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(value
);
4489 if(tv
->flags
& VERTEX_FLAG_TEMP
) {
4490 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
4491 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
4493 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
4494 gts_object_destroy ( GTS_OBJECT(tv
) );
4500 clean_routing_edges(toporouter_t
*r
, toporouter_route_t
*data
)
4502 g_hash_table_foreach_remove(data
->alltemppoints
, temp_point_clean
, NULL
);
4503 g_hash_table_destroy(data
->alltemppoints
);
4504 data
->alltemppoints
= NULL
;
4508 path_score(toporouter_t
*r
, GList
*path
)
4511 toporouter_vertex_t
*pv
= NULL
;
4512 toporouter_vertex_t
*v0
= NULL
;
4514 if(!path
) return INFINITY
;
4516 v0
= TOPOROUTER_VERTEX(path
->data
);
4519 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(path
->data
);
4522 score
+= gts_point_distance(GTS_POINT(pv
), GTS_POINT(v
));
4523 if(pv
!= v0
&& vz(pv
) != vz(v
))
4525 score
+= r
->viacost
;
4537 print_vertices(GList
*vertices
)
4540 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(vertices
->data
);
4542 print_bbox(vertex_bbox(v
));
4543 if(vertex_bbox(v
)) {
4544 printf("has bbox\n");
4545 if(vertex_bbox(v
)->cluster
)
4546 printf("has cluster\n");
4548 printf("no cluster\n");
4549 }else printf("no bbox\n");
4550 vertices
= vertices
->next
;
4555 space_edge(gpointer item
, gpointer data
)
4557 toporouter_edge_t
*e
= TOPOROUTER_EDGE(item
);
4561 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
4563 if(!edge_routing(e
) || !g_list_length(edge_routing(e
))) return 0;
4565 forces
= malloc(sizeof(double) * g_list_length(edge_routing(e
)));
4567 for(guint j
=0;j
<100;j
++) {
4569 guint equilibrium
= 1;
4571 i
= edge_routing(e
);
4573 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4577 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->prev->data), v);
4578 ms
= min_spacing(TOPOROUTER_VERTEX(i
->prev
->data
), v
);
4579 d
= gts_point_distance(GTS_POINT(i
->prev
->data
), GTS_POINT(v
));
4581 // ms = min_vertex_net_spacing(v, tedge_v1(e));
4582 ms
= min_spacing(v
, tedge_v1(e
));
4583 d
= gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(v
));
4586 if(d
< ms
) forces
[k
] = ms
- d
;
4587 else forces
[k
] = 0.;
4590 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->next->data), v);
4591 ms
= min_spacing(TOPOROUTER_VERTEX(i
->next
->data
), v
);
4592 d
= gts_point_distance(GTS_POINT(i
->next
->data
), GTS_POINT(v
));
4594 // ms = min_vertex_net_spacing(v, tedge_v2(e));
4595 ms
= min_spacing(v
, tedge_v2(e
));
4596 d
= gts_point_distance(GTS_POINT(edge_v2(e
)), GTS_POINT(v
));
4599 if(d
< ms
) forces
[k
] += d
- ms
;
4605 i
= edge_routing(e
);
4607 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4608 if(forces
[k
] > EPSILON
|| forces
[k
] < -EPSILON
) equilibrium
= 0;
4609 vertex_move_towards_vertex_values(GTS_VERTEX(v
), edge_v2(e
), forces
[k
] * 0.1, &(GTS_POINT(v
)->x
), &(GTS_POINT(v
)->y
));
4614 // printf("reached equilibriium at %d\n", j);
4625 swap_vertices(toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
4627 toporouter_vertex_t
*tempv
= *v1
;
4633 split_edge_routing(toporouter_vertex_t
*v
, GList
**l1
, GList
**l2
)
4638 g_assert(v
->routingedge
);
4640 base
= g_list_find(vrouting(v
), v
);
4642 *l1
= g_list_prepend(*l1
, tedge_v1(v
->routingedge
));
4643 *l2
= g_list_prepend(*l2
, tedge_v2(v
->routingedge
));
4649 if(!(TOPOROUTER_VERTEX(i
->data
)->flags
& VERTEX_FLAG_TEMP
)) *l2
= g_list_prepend(*l2
, i
->data
);
4655 if(!(TOPOROUTER_VERTEX(i
->data
)->flags
& VERTEX_FLAG_TEMP
)) *l1
= g_list_prepend(*l1
, i
->data
);
4661 vertices_routing_conflicts(toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
)
4663 toporouter_edge_t
*e
;
4664 GList
*rval
= NULL
, *l1
= NULL
, *l2
= NULL
, *i
;
4666 if(vz(v
) != vz(pv
)) return NULL
;
4669 if(!v
->routingedge
&& !pv
->routingedge
) {
4670 e
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), GTS_VERTEX(pv
)));
4672 i
= edge_routing(e
);
4674 rval
= g_list_prepend(rval
, TOPOROUTER_VERTEX(i
->data
)->route
);
4680 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
) && TOPOROUTER_IS_CONSTRAINT(pv
->routingedge
))
4683 if(TOPOROUTER_IS_CONSTRAINT(pv
->routingedge
)) swap_vertices(&pv
, &v
);
4685 if(!v
->routingedge
) swap_vertices(&pv
, &v
);
4689 split_edge_routing(v
, &l1
, &l2
);
4693 if(!pv
->routingedge
) {
4694 toporouter_edge_t
*e1
, *e2
;
4695 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv
), edge_v1(e
)));
4696 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv
), edge_v2(e
)));
4698 l1
= g_list_concat(l1
, g_list_copy(edge_routing(e1
)));
4699 l2
= g_list_concat(l2
, g_list_copy(edge_routing(e2
)));
4702 GList
*pvlist1
= NULL
, *pvlist2
= NULL
;
4703 toporouter_vertex_t
*commonv
= route_vertices_common_vertex(v
, pv
);
4707 split_edge_routing(pv
, &pvlist1
, &pvlist2
);
4709 if(commonv
== tedge_v1(e
)) {
4710 toporouter_edge_t
*ope
;
4712 if(commonv
== tedge_v1(pv
->routingedge
)) {
4713 l1
= g_list_concat(l1
, pvlist1
);
4714 l2
= g_list_concat(l2
, pvlist2
);
4715 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e
), edge_v2(pv
->routingedge
)));
4717 l1
= g_list_concat(l1
, pvlist2
);
4718 l2
= g_list_concat(l2
, pvlist1
);
4719 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e
), edge_v1(pv
->routingedge
)));
4722 l2
= g_list_concat(l2
, g_list_copy(edge_routing(ope
)));
4725 toporouter_edge_t
*ope
;
4726 if(commonv
== tedge_v1(pv
->routingedge
)) {
4727 l1
= g_list_concat(l1
, pvlist2
);
4728 l2
= g_list_concat(l2
, pvlist1
);
4729 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e
), edge_v2(pv
->routingedge
)));
4731 l1
= g_list_concat(l1
, pvlist1
);
4732 l2
= g_list_concat(l2
, pvlist2
);
4733 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e
), edge_v1(pv
->routingedge
)));
4736 l1
= g_list_concat(l1
, g_list_copy(edge_routing(ope
)));
4742 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
4744 if(curv
->flags
& VERTEX_FLAG_ROUTE
&& (g_list_find(l2
, curv
->parent
) || g_list_find(l2
, curv
->child
))) {
4745 if(!g_list_find(rval
, curv
->route
)) rval
= g_list_prepend(rval
, curv
->route
);
4751 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
4753 if(curv
->flags
& VERTEX_FLAG_ROUTE
&& (g_list_find(l1
, curv
->parent
) || g_list_find(l1
, curv
->child
))) {
4754 if(!g_list_find(rval
, curv
->route
)) rval
= g_list_prepend(rval
, curv
->route
);
4766 vertices_routing_conflict_cost(toporouter_t
*r
, toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
, guint
*n
)
4768 GList
*conflicts
= vertices_routing_conflicts(v
, pv
), *i
;
4769 gdouble penalty
= 0.;
4774 penalty
+= TOPOROUTER_ROUTE(i
->data
)->score
;
4777 g_list_free(conflicts
);
4778 // if(penalty > 0.) printf("conflict penalty of %f with %f,%f %f,%f\n", penalty, vx(v), vy(v), vx(pv), vy(pv));
4783 gcost(toporouter_t
*r
, toporouter_route_t
*data
, toporouter_vertex_t
*srcv
, toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
, guint
*n
,
4784 toporouter_netlist_t
*pair
)
4786 gdouble cost
= 0., segcost
;
4790 if(g_list_find(data
->srcvertices
, v
)) return 0.;
4792 segcost
= tvdistance(pv
, v
);
4794 if(pair
&& !TOPOROUTER_IS_CONSTRAINT(v
->routingedge
) && v
->routingedge
) {
4795 GList
*list
= g_list_find(v
->routingedge
->routing
, v
);
4796 toporouter_vertex_t
*pv
= edge_routing_prev_not_temp(v
->routingedge
, list
);
4797 toporouter_vertex_t
*nv
= edge_routing_next_not_temp(v
->routingedge
, list
);
4799 if(pv
->route
&& pv
->route
->netlist
== pair
) {
4800 }else if(nv
->route
&& nv
->route
->netlist
== pair
) {
4806 cost
= pv
->gcost
+ segcost
;
4808 if(r
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) {
4809 gdouble conflictcost
= 0.;
4811 if(pv
&& v
!= pv
&& vz(v
) == vz(pv
)) conflictcost
= vertices_routing_conflict_cost(r
, v
, pv
, n
);
4813 if(!(r
->flags
& TOPOROUTER_FLAG_DETOUR
&& *n
== 1)) {
4814 cost
+= conflictcost
* (pow(*n
,2));
4821 #define vlayer(x) (&r->layers[(int)vz(x)])
4824 candidate_is_available(toporouter_vertex_t
*pv
, toporouter_vertex_t
*v
)
4826 // TODO: still needed?
4828 if(pv
== v
) return 0;
4836 route(toporouter_t
*r
, toporouter_route_t
*data
, guint debug
)
4838 GtsEHeap
*openlist
= gts_eheap_new(route_heap_cmp
, NULL
);
4839 GList
*closelist
= NULL
;
4840 GList
*i
, *rval
= NULL
;
4841 toporouter_netlist_t
*pair
= NULL
;
4844 toporouter_vertex_t
*srcv
= NULL
, *destv
= NULL
, *curpoint
= NULL
;
4845 toporouter_layer_t
*cur_layer
, *dest_layer
;
4847 g_assert(data
->src
->c
!= data
->dest
->c
);
4849 if(data
->destvertices
) g_list_free(data
->destvertices
);
4850 if(data
->srcvertices
) g_list_free(data
->srcvertices
);
4852 data
->destvertices
= cluster_vertices(r
, data
->dest
);
4853 data
->srcvertices
= cluster_vertices(r
, data
->src
);
4855 closest_cluster_pair(r
, data
->srcvertices
, data
->destvertices
, &curpoint
, &destv
);
4857 if(!curpoint
|| !destv
) goto routing_return
;
4860 cur_layer
= vlayer(curpoint
); dest_layer
= vlayer(destv
);
4864 data
->alltemppoints
= g_hash_table_new(g_direct_hash
, g_direct_equal
);
4866 curpoint
->parent
= NULL
;
4867 curpoint
->child
= NULL
;
4868 curpoint
->gcost
= 0.;
4870 curpoint
->hcost
= simple_h_cost(r
, curpoint
, destv
);
4872 if(data
->netlist
&& data
->netlist
->pair
) {
4873 GList
*i
= r
->routednets
;
4875 toporouter_route_t
*curroute
= TOPOROUTER_ROUTE(i
->data
);
4876 if(curroute
->netlist
== data
->netlist
->pair
) {
4877 pair
= data
->netlist
->pair
;
4884 gts_eheap_insert(openlist
, curpoint
);
4886 while(gts_eheap_size(openlist
) > 0) {
4887 GList
*candidatepoints
;
4888 data
->curpoint
= curpoint
;
4889 //draw_route_status(r, closelist, openlist, curpoint, data, count++);
4891 curpoint
= TOPOROUTER_VERTEX( gts_eheap_remove_top(openlist
, NULL
) );
4892 if(curpoint
->parent
&& !(curpoint
->flags
& VERTEX_FLAG_TEMP
)) {
4893 if(vz(curpoint
) != vz(destv
)) {
4894 toporouter_vertex_t
*tempv
;
4895 cur_layer
= vlayer(curpoint
);//&r->layers[(int)vz(curpoint)];
4896 tempv
= closest_dest_vertex(r
, curpoint
, data
);
4899 dest_layer
= vlayer(destv
);//&r->layers[(int)vz(destv)];
4905 // destpoint = closest_dest_vertex(r, curpoint, data);
4906 // dest_layer = &r->layers[(int)vz(destpoint)];
4908 if(g_list_find(data
->destvertices
, curpoint
)) {
4909 toporouter_vertex_t
*temppoint
= curpoint
;
4916 data
->path
= g_list_prepend(data
->path
, temppoint
);
4917 if(g_list_find(data
->srcvertices
, temppoint
)) {
4919 if(r
->flags
& TOPOROUTER_FLAG_AFTERORDER
) break;
4921 temppoint
= temppoint
->parent
;
4924 data
->score
= path_score(r
, data
->path
);
4926 printf("ROUTE: path score = %f computation cost = %d\n", data
->score
, count
);
4929 if(srcv
->bbox
->cluster
!= data
->src
) {
4930 data
->src
= srcv
->bbox
->cluster
;
4933 if(destv
->bbox
->cluster
!= data
->dest
) {
4934 data
->dest
= destv
->bbox
->cluster
;
4938 closelist_insert(curpoint
);
4940 printf("\n\n\n*** ROUTE COUNT = %d\n", count
);
4942 candidatepoints
= compute_candidate_points(r
, cur_layer
, curpoint
, data
, &destv
);
4944 //#ifdef DEBUG_ROUTE
4945 /*********************
4946 if(debug && !strcmp(data->dest->netlist, " unnamed_net2"))
4948 unsigned int mask = ~(VERTEX_FLAG_RED | VERTEX_FLAG_GREEN | VERTEX_FLAG_BLUE);
4952 for(j=0;j<groupcount();j++) {
4953 i = r->layers[j].vertices;
4955 TOPOROUTER_VERTEX(i->data)->flags &= mask;
4960 i = candidatepoints;
4962 TOPOROUTER_VERTEX(i->data)->flags |= VERTEX_FLAG_GREEN;
4963 // printf("flagged a candpoint @ %f,%f\n",
4964 // vx(i->data), vy(i->data));
4968 curpoint->flags |= VERTEX_FLAG_BLUE;
4969 if(curpoint->parent)
4970 curpoint->parent->flags |= VERTEX_FLAG_RED;
4973 for(j=0;j<groupcount();j++) {
4974 GList *datas = g_list_prepend(NULL, data);
4975 sprintf(buffer, "route-%d-%05d.png", j, count);
4976 toporouter_draw_surface(r, r->layers[j].surface, buffer, 1024, 1024, 2, datas, j, candidatepoints);
4981 *********************/
4983 // if(count > 100) exit(0);
4984 i
= candidatepoints
;
4986 toporouter_vertex_t
*temppoint
= TOPOROUTER_VERTEX(i
->data
);
4987 if(!g_list_find(closelist
, temppoint
) && candidate_is_available(curpoint
, temppoint
)) { //&& temppoint != curpoint) {
4988 toporouter_heap_search_data_t heap_search_data
= { temppoint
, NULL
};
4991 gdouble temp_g_cost
= gcost(r
, data
, srcv
, temppoint
, curpoint
, &temp_gn
, pair
);
4994 gts_eheap_foreach(openlist
,toporouter_heap_search
, &heap_search_data
);
4996 if(heap_search_data
.result
) {
4997 if(temp_g_cost
< temppoint
->gcost
) {
4999 temppoint
->gcost
= temp_g_cost
;
5000 temppoint
->gn
= temp_gn
;
5002 temppoint
->parent
= curpoint
;
5003 curpoint
->child
= temppoint
;
5005 gts_eheap_update(openlist
);
5008 temppoint
->parent
= curpoint
;
5009 curpoint
->child
= temppoint
;
5011 temppoint
->gcost
= temp_g_cost
;
5012 temppoint
->gn
= temp_gn
;
5014 temppoint
->hcost
= simple_h_cost(r
, temppoint
, destv
);
5015 // if(cur_layer != dest_layer) temppoint->hcost += r->viacost;
5016 gts_eheap_insert(openlist
, temppoint
);
5022 g_list_free(candidatepoints
);
5026 printf("ROUTE: could not find path!\n");
5029 data
->score
= INFINITY
;
5030 clean_routing_edges(r
, data
);
5033 //TOPOROUTER_VERTEX(data->src->point)->parent = NULL;
5034 //TOPOROUTER_VERTEX(data->src->point)->child = NULL;
5035 goto routing_return
;
5040 for(i=0;i<groupcount();i++) {
5042 sprintf(buffer, "route-error-%d-%d.png", r->routecount, i);
5043 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1280, 1280, 2, data, i, NULL);
5050 // printf(" * finished a*\n");
5054 for(i=0;i<groupcount();i++) {
5056 sprintf(buffer, "route-preclean-%d-%d.png", i, r->routecount);
5057 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, data, i, NULL);
5065 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
5067 if(tv->routingedge) {
5068 GList *list = g_list_find(edge_routing(tv->routingedge), tv);
5069 toporouter_vertex_t *restartv = NULL, *boxpoint;
5074 if(vertex_bbox(tedge_v2(tv->routingedge)))
5075 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v2(tv->routingedge))->point);
5079 if(tedge_v2(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v2(tv->routingedge)))
5080 restartv = tedge_v2(tv->routingedge);
5081 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
5082 restartv = boxpoint;
5086 if(vertex_bbox(tedge_v1(tv->routingedge)))
5087 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v1(tv->routingedge))->point);
5091 if(tedge_v1(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v1(tv->routingedge)))
5092 restartv = tedge_v1(tv->routingedge);
5093 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
5094 restartv = boxpoint;
5099 clean_routing_edges(r, data);
5100 gts_eheap_destroy(openlist);
5101 g_list_free(closelist);
5102 openlist = gts_eheap_new(route_heap_cmp, NULL);
5104 g_list_free(data->path);
5105 printf("ROUTING RESTARTING with new src %f,%f,%f\n", vx(restartv), vy(restartv), vz(restartv));
5106 curpoint = restartv;
5116 toporouter_vertex_t
*pv
= NULL
;
5117 GList
*i
= data
->path
;
5119 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
5121 if(pv
&& g_list_find(data
->srcvertices
, tv
)) {
5122 GList
*temp
= g_list_copy(i
);
5123 g_list_free(data
->path
);
5133 toporouter_vertex_t
*pv
= NULL
;
5134 GList
*i
= data
->path
;
5136 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
5137 if(tv
->flags
& VERTEX_FLAG_TEMP
) {
5138 tv
->flags
^= VERTEX_FLAG_TEMP
;
5139 tv
->flags
|= VERTEX_FLAG_ROUTE
;
5141 if(pv
) pv
->child
= tv
;
5143 if(tv
->routingedge
) tv
->route
= data
;
5145 // if(tv->routingedge && !TOPOROUTER_IS_CONSTRAINT(tv->routingedge)) space_edge(tv->routingedge, NULL);
5153 toporouter_vertex_t
*pv
= NULL
, *v
= NULL
;
5155 GList
*i
= data
->path
;
5157 v
= TOPOROUTER_VERTEX(i
->data
);
5170 if(v
) v
->child
= NULL
;
5173 clean_routing_edges(r
, data
);
5176 GList
*i
= data
->path
;
5178 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
5180 if(v
->routingedge
&& !TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
5181 space_edge(v
->routingedge
, NULL
);
5188 g_list_free(data
->destvertices
);
5189 g_list_free(data
->srcvertices
);
5190 data
->destvertices
= NULL
;
5191 data
->srcvertices
= NULL
;
5192 gts_eheap_destroy(openlist
);
5193 g_list_free(closelist
);
5195 data
->alltemppoints
= NULL
;
5200 /* moves vertex v d units in the direction of vertex p */
5202 vertex_move_towards_point(GtsVertex
*v
, gdouble px
, gdouble py
, gdouble d
)
5204 gdouble dx
= px
- GTS_POINT(v
)->x
;
5205 gdouble dy
= py
- GTS_POINT(v
)->y
;
5206 gdouble theta
= atan(fabs(dy
/dx
));
5208 g_assert(finite(theta
));
5213 GTS_POINT(v
)->x
+= d
* cos(theta
);
5214 GTS_POINT(v
)->y
+= d
* sin(theta
);
5216 GTS_POINT(v
)->x
+= d
* cos(theta
);
5217 GTS_POINT(v
)->y
-= d
* sin(theta
);
5223 GTS_POINT(v
)->x
-= d
* cos(theta
);
5224 GTS_POINT(v
)->y
+= d
* sin(theta
);
5226 GTS_POINT(v
)->x
-= d
* cos(theta
);
5227 GTS_POINT(v
)->y
-= d
* sin(theta
);
5234 /* moves vertex v d units in the direction of vertex p */
5236 vertex_move_towards_vertex(GtsVertex
*v
, GtsVertex
*p
, gdouble d
)
5238 gdouble dx
= GTS_POINT(p
)->x
- GTS_POINT(v
)->x
;
5239 gdouble dy
= GTS_POINT(p
)->y
- GTS_POINT(v
)->y
;
5240 gdouble theta
= atan(fabs(dy
/dx
));
5242 g_assert(finite(theta
));
5247 GTS_POINT(v
)->x
+= d
* cos(theta
);
5248 GTS_POINT(v
)->y
+= d
* sin(theta
);
5250 GTS_POINT(v
)->x
+= d
* cos(theta
);
5251 GTS_POINT(v
)->y
-= d
* sin(theta
);
5257 GTS_POINT(v
)->x
-= d
* cos(theta
);
5258 GTS_POINT(v
)->y
+= d
* sin(theta
);
5260 GTS_POINT(v
)->x
-= d
* cos(theta
);
5261 GTS_POINT(v
)->y
-= d
* sin(theta
);
5270 pathvertex_arcing_through_constraint(toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
)
5272 toporouter_vertex_t
*v
= pathv
->child
;
5274 if(!v
|| !v
->routingedge
) return 0.;
5276 while(v
->flags
& VERTEX_FLAG_ROUTE
&& (tedge_v1(v
->routingedge
) == arcv
|| tedge_v2(v
->routingedge
) == arcv
)) {
5277 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
5278 return gts_point_distance(GTS_POINT(tedge_v1(v
->routingedge
)), GTS_POINT(tedge_v2(v
->routingedge
)));
5283 while(v
->flags
& VERTEX_FLAG_ROUTE
&& (tedge_v1(v
->routingedge
) == arcv
|| tedge_v2(v
->routingedge
) == arcv
)) {
5284 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
5285 return gts_point_distance(GTS_POINT(tedge_v1(v
->routingedge
)), GTS_POINT(tedge_v2(v
->routingedge
)));
5293 vertices_connected(toporouter_vertex_t
*a
, toporouter_vertex_t
*b
)
5295 return ((a
->route
->netlist
== b
->route
->netlist
&& a
->route
->src
->c
== b
->route
->src
->c
) ? 1 : 0);
5299 edge_min_spacing(GList
*list
, toporouter_edge_t
*e
, toporouter_vertex_t
*v
, guint debug
)
5301 toporouter_vertex_t
*origin
;
5304 toporouter_vertex_t
*nextv
, *prevv
;
5305 //toporouter_vertex_t *edgev;
5306 //gdouble constraint_spacing;
5308 if(!list
) return INFINITY
;
5310 // printf("\t CMS %f,%f - %f,%f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), vx(tedge_v2(e)), vy(tedge_v2(e)));
5312 prevv
= origin
= TOPOROUTER_VERTEX(list
->data
);
5317 if(gts_point_distance2(GTS_POINT(origin
), GTS_POINT(edge_v1(e
))) < gts_point_distance2(GTS_POINT(v
), GTS_POINT(edge_v1(e
)))) {
5321 nextv
= edge_routing_next(e
, i
);
5322 if(nextv
->route
&& vertices_connected(nextv
, prevv
)) { i
= i
->next
; continue; }
5323 if(!(nextv
->flags
& VERTEX_FLAG_TEMP
)) {
5324 gdouble ms
= min_spacing(prevv
, nextv
);
5325 if(nextv
== tedge_v2(e
)) {
5326 gdouble cms
= pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i
->data
), tedge_v2(e
));
5327 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v2(e)), vy(tedge_v2(e)), cms, ms);
5328 // if(vx(tedge_v2(e)) > -EPSILON && vx(tedge_v2(e)) < EPSILON) {
5329 // printf("\t\tPROB: ");
5330 // print_vertex(tedge_v2(e));
5332 if(cms
> EPSILON
) space
+= MIN(ms
, cms
/ 2.);
5339 // printf("%f ", space);
5346 nextv
= edge_routing_prev(e
, i
);
5347 if(nextv
->route
&& vertices_connected(nextv
, prevv
)) { i
= i
->prev
; continue; }
5348 if(!(nextv
->flags
& VERTEX_FLAG_TEMP
)) {
5349 gdouble ms
= min_spacing(prevv
, nextv
);
5350 if(nextv
== tedge_v1(e
)) {
5351 gdouble cms
= pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i
->data
), tedge_v1(e
));
5352 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), cms, ms);
5353 // if(vx(tedge_v1(e)) > -EPSILON && vx(tedge_v1(e)) < EPSILON) {
5354 // printf("\t\tPROB: ");
5355 // print_vertex(tedge_v1(e));
5357 if(cms
> EPSILON
) space
+= MIN(ms
, cms
/ 2.);
5364 // printf("%f ", space);
5369 if(TOPOROUTER_IS_CONSTRAINT(e
) && space
> gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) / 2.)
5370 space
= gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) / 2.;
5372 // if(debug) printf("\tedge_min_spacing: %f\n", space);
5376 /* line segment is 1 & 2, point is 3
5377 returns 0 if v3 is outside seg
5380 vertex_line_normal_intersection(gdouble x1
, gdouble y1
, gdouble x2
, gdouble y2
, gdouble x3
, gdouble y3
, gdouble
*x
, gdouble
*y
)
5382 gdouble m1
= cartesian_gradient(x1
,y1
,x2
,y2
);
5383 gdouble m2
= perpendicular_gradient(m1
);
5384 gdouble c2
= (isinf(m2
)) ? x3
: y3
- (m2
* x3
);
5385 gdouble c1
= (isinf(m1
)) ? x1
: y1
- (m1
* x1
);
5392 *x
= (c2
- c1
) / (m1
- m2
);
5394 *y
= (isinf(m2
)) ? y1
: (m2
* (*x
)) + c2
;
5396 if(*x
>= MIN(x1
,x2
) - EPSILON
&& *x
<= MAX(x1
,x2
) + EPSILON
&& *y
>= MIN(y1
,y2
) - EPSILON
&& *y
<= MAX(y1
,y2
) + EPSILON
)
5402 print_toporouter_arc(toporouter_arc_t
*arc
)
5404 // GList *i = arc->vs;
5406 printf("ARC CENTRE: %f,%f ", vx(arc
->centre
), vy(arc
->centre
));// print_vertex(arc->centre);
5407 printf("RADIUS: %f", arc
->r
);
5409 if(arc
->dir
>0) printf(" COUNTERCLOCKWISE ");
5410 else if(arc
->dir
<0) printf(" CLOCKWISE ");
5411 else printf(" COLINEAR(ERROR) ");
5416 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
5417 printf("%f,%f ", vx(v), vy(v));
5425 toporouter_arc_remove(toporouter_oproute_t
*oproute
, toporouter_arc_t
*arc
)
5427 oproute
->arcs
= g_list_remove(oproute
->arcs
, arc
);
5429 if(arc
->v
) arc
->v
->arc
= NULL
;
5433 toporouter_arc_new(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*centre
, gdouble r
, gint dir
)
5435 toporouter_arc_t
*arc
= TOPOROUTER_ARC(gts_object_new(GTS_OBJECT_CLASS(toporouter_arc_class())));
5436 arc
->centre
= centre
;
5443 if(v1
) v1
->arc
= arc
;
5444 arc
->oproute
= oproute
;
5446 arc
->clearance
= NULL
;
5452 path_set_oproute(GList
*path
, toporouter_oproute_t
*oproute
)
5455 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(path
->data
);
5457 if(v
->flags
& VERTEX_FLAG_ROUTE
)
5458 v
->oproute
= oproute
;
5465 print_oproute(toporouter_oproute_t
*oproute
)
5467 GList
*i
= oproute
->arcs
;
5469 printf("Optimized Route:\n");
5470 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", oproute
->netlist
, oproute
->style
);
5471 // printf("%s\n", oproute->netlist);
5473 i = oproute->term1->zlink;
5475 toporouter_vertex_t *thisv = TOPOROUTER_VERTEX(i->data);
5476 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", vertex_bbox(thisv)->netlist, vertex_bbox(thisv)->style);
5480 printf("\t"); print_vertex(oproute
->term1
); printf("\n");
5483 toporouter_arc_t
*arc
= (toporouter_arc_t
*)i
->data
;
5484 printf("\t"); print_toporouter_arc(arc
); printf("\n");
5487 printf("\t"); print_vertex(oproute
->term2
); printf("\n");
5491 export_pcb_drawline(guint layer
, guint x0
, guint y0
, guint x1
, guint y1
, guint thickness
, guint keepaway
)
5495 line
= CreateDrawnLineOnLayer( LAYER_PTR(layer
), x0
, y0
, x1
, y1
,
5496 thickness
, keepaway
,
5497 MakeFlags (AUTOFLAG
| (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
: 0)));
5500 AddObjectToCreateUndoList (LINE_TYPE
, LAYER_PTR(layer
), line
, line
);
5501 d
= coord_distance((double)x0
, (double)y0
, (double)x1
, (double)y1
) / 100.;
5507 arc_angle(toporouter_arc_t
*arc
)
5509 gdouble x0
, x1
, y0
, y1
;
5511 x0
= arc
->x0
- vx(arc
->centre
);
5512 x1
= arc
->x1
- vx(arc
->centre
);
5513 y0
= arc
->y0
- vy(arc
->centre
);
5514 y1
= arc
->y1
- vy(arc
->centre
);
5516 return fabs(acos(((x0
*x1
)+(y0
*y1
))/(sqrt(pow(x0
,2)+pow(y0
,2))*sqrt(pow(x1
,2)+pow(y1
,2)))));
5520 export_pcb_drawarc(guint layer
, toporouter_arc_t
*a
, guint thickness
, guint keepaway
)
5522 gdouble sa
, da
, theta
;
5523 gdouble x0
, y0
, x1
, y1
, d
=0.;
5527 wind
= coord_wind(a
->x0
, a
->y0
, a
->x1
, a
->y1
, vx(a
->centre
), vy(a
->centre
));
5529 sa
= coord_xangle(a
->x0
, a
->y0
, vx(a
->centre
), vy(a
->centre
)) * 180. / M_PI
;
5531 x0
= a
->x0
- vx(a
->centre
);
5532 x1
= a
->x1
- vx(a
->centre
);
5533 y0
= a
->y0
- vy(a
->centre
);
5534 y1
= a
->y1
- vy(a
->centre
);
5536 theta
= arc_angle(a
);
5538 if(!a
->dir
|| !wind
) return 0.;
5540 if(a
->dir
!= wind
) theta
= 2. * M_PI
- theta
;
5542 da
= -a
->dir
* theta
* 180. / M_PI
;
5544 if(da
< 1. && da
> -1.) return 0.;
5545 if(da
> 359. || da
< -359.) return 0.;
5547 arc
= CreateNewArcOnLayer(LAYER_PTR(layer
), vx(a
->centre
), vy(a
->centre
), a
->r
, a
->r
,
5548 sa
, da
, thickness
, keepaway
,
5549 MakeFlags( AUTOFLAG
| (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
: 0)));
5552 AddObjectToCreateUndoList( ARC_TYPE
, LAYER_PTR(layer
), arc
, arc
);
5553 d
= a
->r
* theta
/ 100.;
5560 calculate_term_to_arc(toporouter_vertex_t
*v
, toporouter_arc_t
*arc
, guint dir
)
5562 gdouble theta
, a
, b
, bx
, by
, a0x
, a0y
, a1x
, a1y
;
5565 theta
= acos(arc
->r
/ gts_point_distance(GTS_POINT(v
), GTS_POINT(arc
->centre
)));
5566 a
= arc
->r
* sin(theta
);
5567 b
= arc
->r
* cos(theta
);
5569 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
));
5571 point_from_point_to_point(arc
->centre
, v
, b
, &bx
, &by
);
5573 coords_on_line(bx
, by
, perpendicular_gradient(point_gradient(GTS_POINT(v
), GTS_POINT(arc
->centre
))), a
, &a0x
, &a0y
, &a1x
, &a1y
);
5575 winddir
= coord_wind(vx(v
), vy(v
), a0x
, a0y
, vx(arc
->centre
), vy(arc
->centre
));
5578 printf("!winddir @ v %f,%f arc->centre %f,%f\n", vx(v
), vy(v
), vx(arc
->centre
), vy(arc
->centre
));
5579 //TODO: fix hack: this shouldn't happen
5589 if(dir
) winddir
= -winddir
;
5591 if(winddir
== arc
->dir
) {
5592 if(!dir
) { arc
->x0
= a0x
; arc
->y0
= a0y
; }
5593 else{ arc
->x1
= a0x
; arc
->y1
= a0y
; }
5595 if(!dir
) { arc
->x0
= a1x
; arc
->y0
= a1y
; }
5596 else{ arc
->x1
= a1x
; arc
->y1
= a1y
; }
5603 // b1 is the projection in the direction of narc, while b2 is the perpendicular projection
5605 arc_ortho_projections(toporouter_arc_t
*arc
, toporouter_arc_t
*narc
, gdouble
*b1
, gdouble
*b2
)
5607 gdouble nax
, nay
, ax
, ay
, alen2
, c
;
5608 gdouble b1x
, b1y
, b2x
, b2y
;
5611 printf("arc c = %f,%f narc c = %f,%f arc->0 = %f,%f\n",
5612 vx(arc
->centre
), vy(arc
->centre
),
5613 vx(narc
->centre
), vy(narc
->centre
),
5617 nax
= vx(narc
->centre
) - vx(arc
->centre
);
5618 nay
= vy(narc
->centre
) - vy(arc
->centre
);
5619 alen2
= pow(nax
,2) + pow(nay
,2);
5622 ax
= arc
->x0
- vx(arc
->centre
);
5623 ay
= arc
->y0
- vy(arc
->centre
);
5626 printf("norm narc = %f,%f - %f\tA=%f,%f\n", nax
, nay
, sqrt(alen2
), ax
, ay
);
5629 c
= ((ax
*nax
)+(ay
*nay
)) / alen2
;
5637 printf("proj = %f,%f perp proj = %f,%f\n", b1x
, b1y
, b2x
, b2y
);
5640 *b1
= sqrt(pow(b1x
,2) + pow(b1y
,2));
5641 *b2
= sqrt(pow(b2x
,2) + pow(b2y
,2));
5646 calculate_arc_to_arc(toporouter_t
*ar
, toporouter_arc_t
*parc
, toporouter_arc_t
*arc
)
5648 gdouble theta
, a
, b
, bx
, by
, a0x
, a0y
, a1x
, a1y
, m
, preva
, prevb
;
5650 toporouter_arc_t
*bigr
, *smallr
;
5652 if(parc
->r
> arc
->r
) {
5653 bigr
= parc
; smallr
= arc
;
5655 bigr
= arc
; smallr
= parc
;
5658 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr
->centre
), vy(bigr
->centre
),
5659 vx(smallr
->centre
), vy(smallr
->centre
));
5662 m
= perpendicular_gradient(point_gradient(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5664 if(bigr
->centre
== smallr
->centre
) {
5666 printf("bigr->centre == smallr->centre @ %f,%f\n", vx(smallr
->centre
), vy(smallr
->centre
));
5669 g_assert(bigr
->centre
!= smallr
->centre
);
5671 if(parc
->dir
== arc
->dir
) {
5672 //export_arc_straight:
5674 theta
= acos((bigr
->r
- smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5675 a
= bigr
->r
* sin(theta
);
5676 b
= bigr
->r
* cos(theta
);
5678 point_from_point_to_point(bigr
->centre
, smallr
->centre
, b
, &bx
, &by
);
5680 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5682 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5684 arc_ortho_projections(parc
, arc
, &prevb
, &preva
);
5685 //#ifdef DEBUG_EXPORT
5688 printf("STRAIGHT:\n");
5689 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr
->centre
), vy(bigr
->centre
),
5690 vx(smallr
->centre
), vy(smallr
->centre
));
5691 printf("theta = %f a = %f b = %f bigrr = %f d = %f po = %f\n", theta
, a
, b
, bigr
->r
,
5692 gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)),
5693 bigr
->r
/ gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5694 printf("bigr-r = %f smallr-r = %f ratio = %f\n",
5695 bigr
->r
, smallr
->r
, (bigr
->r
- smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5696 printf("preva = %f prevb = %f\n\n", preva
, prevb
);
5702 if(bigr
==parc
) winddir
= -winddir
;
5704 if(winddir
== bigr
->dir
) {
5722 a
= smallr
->r
* sin(theta
);
5723 b
= smallr
->r
* cos(theta
);
5726 printf("a = %f b = %f\n", a
, b
);
5728 point_from_point_to_point(smallr
->centre
, bigr
->centre
, -b
, &bx
, &by
);
5730 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5732 if(winddir
== bigr
->dir
) {
5754 theta
= acos((bigr
->r
+ smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5755 a
= bigr
->r
* sin(theta
);
5756 b
= bigr
->r
* cos(theta
);
5758 point_from_point_to_point(bigr
->centre
, smallr
->centre
, b
, &bx
, &by
);
5760 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5762 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5763 //#ifdef DEBUG_EXPORT
5766 printf("theta = %f a = %f b = %f r = %f d = %f po = %f\n", theta
, a
, b
, bigr
->r
+ smallr
->r
,
5767 gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)),
5768 (bigr
->r
+smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5770 printf("bigr centre = %f,%f smallr centre = %f,%f\n\n", vx(bigr
->centre
), vy(bigr
->centre
),
5771 vx(smallr
->centre
), vy(smallr
->centre
));
5773 printf("big wind = %d small wind = %d\n", bigr
->dir
, smallr
->dir
);
5778 smallr->centre->flags |= VERTEX_FLAG_RED;
5779 bigr->centre->flags |= VERTEX_FLAG_GREEN;
5780 //bigr->centre->flags |= VERTEX_FLAG_RED;
5783 for(i=0;i<groupcount();i++) {
5785 sprintf(buffer, "wind%d.png", i);
5786 toporouter_draw_surface(ar, ar->layers[i].surface, buffer, 2096, 2096, 2, NULL, i, NULL);
5794 if(bigr
==parc
) winddir
= -winddir
;
5796 if(winddir
== bigr
->dir
) {
5814 a
= smallr
->r
* sin(theta
);
5815 b
= smallr
->r
* cos(theta
);
5817 point_from_point_to_point(smallr
->centre
, bigr
->centre
, b
, &bx
, &by
);
5819 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5821 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5825 if(bigr
==parc
) winddir
= -winddir
;
5827 if(winddir
== smallr
->dir
) {
5851 export_oproutes(toporouter_t
*ar
, toporouter_oproute_t
*oproute
)
5853 guint layer
= PCB
->LayerGroups
.Entries
[oproute
->layergroup
][0];
5854 guint thickness
= lookup_thickness(oproute
->style
);
5855 guint keepaway
= lookup_keepaway(oproute
->style
);
5856 GList
*arcs
= oproute
->arcs
;
5857 toporouter_arc_t
*arc
, *parc
= NULL
;
5860 ar
->wiring_score
+= export_pcb_drawline(layer
, vx(oproute
->term1
), vy(oproute
->term1
), vx(oproute
->term2
), vy(oproute
->term2
), thickness
, keepaway
);
5865 // calculate_term_to_arc(oproute->term1, TOPOROUTER_ARC(arcs->data), 0, layer);
5868 arc
= TOPOROUTER_ARC(arcs
->data
);
5871 ar
->wiring_score
+= export_pcb_drawarc(layer
, parc
, thickness
, keepaway
);
5872 ar
->wiring_score
+= export_pcb_drawline(layer
, parc
->x1
, parc
->y1
, arc
->x0
, arc
->y0
, thickness
, keepaway
);
5874 ar
->wiring_score
+= export_pcb_drawline(layer
, vx(oproute
->term1
), vy(oproute
->term1
), arc
->x0
, arc
->y0
, thickness
, keepaway
);
5880 ar
->wiring_score
+= export_pcb_drawarc(layer
, arc
, thickness
, keepaway
);
5881 ar
->wiring_score
+= export_pcb_drawline(layer
, arc
->x1
, arc
->y1
, vx(oproute
->term2
), vy(oproute
->term2
), thickness
, keepaway
);
5888 oproute_free(toporouter_oproute_t
*oproute
)
5890 GList
*i
= oproute
->arcs
;
5892 toporouter_arc_t
*arc
= (toporouter_arc_t
*) i
->data
;
5893 if(arc
->centre
->flags
& VERTEX_FLAG_TEMP
)
5894 gts_object_destroy(GTS_OBJECT(arc
->centre
));
5899 g_list_free(oproute
->arcs
);
5904 oproute_calculate_tof(toporouter_oproute_t
*oproute
)
5906 GList
*arcs
= oproute
->arcs
;
5907 toporouter_arc_t
*parc
= NULL
, *arc
;
5912 oproute
->tof
= gts_point_distance(GTS_POINT(oproute
->term1
), GTS_POINT(oproute
->term2
));
5917 arc
= TOPOROUTER_ARC(arcs
->data
);
5920 oproute
->tof
+= arc_angle(parc
) * parc
->r
;
5921 oproute
->tof
+= sqrt(pow(parc
->x1
-arc
->x0
,2)+pow(parc
->y1
-arc
->y0
,2));
5923 oproute
->tof
+= sqrt(pow(arc
->x0
-vx(oproute
->term1
),2)+pow(arc
->y0
-vy(oproute
->term1
),2));
5930 oproute
->tof
+= arc_angle(parc
) * parc
->r
;
5931 oproute
->tof
+= sqrt(pow(arc
->x1
-vx(oproute
->term2
),2)+pow(arc
->y1
-vy(oproute
->term2
),2));
5936 line_line_distance_at_normal(
5937 gdouble line1_x1
, gdouble line1_y1
,
5938 gdouble line1_x2
, gdouble line1_y2
,
5939 gdouble line2_x1
, gdouble line2_y1
,
5940 gdouble line2_x2
, gdouble line2_y2
,
5941 gdouble x
, gdouble y
)
5943 gdouble m1
= perpendicular_gradient(cartesian_gradient(line1_x1
, line1_y1
, line1_x2
, line1_y2
));
5944 gdouble m2
= cartesian_gradient(line2_x1
, line2_y1
, line2_x2
, line2_y2
);
5945 gdouble c1
= (isinf(m1
)) ? x
: y
- (m1
* x
);
5946 gdouble c2
= (isinf(m2
)) ? line2_x1
: line2_y1
- (m2
* line2_x1
);
5950 if(isinf(m2
)) intx
= line2_x1
;
5951 else if(isinf(m1
)) intx
= x
;
5952 else intx
= (c2
- c1
) / (m1
- m2
);
5954 inty
= (isinf(m2
)) ? (m1
* intx
) + c1
: (m2
* intx
) + c2
;
5956 return sqrt(pow(x
-intx
,2)+pow(y
-inty
,2));
5960 calculate_serpintine(gdouble delta
, gdouble r
, gdouble initiala
, gdouble
*a
, guint
*nhalfcycles
)
5962 gdouble lhalfcycle
= 2.*(initiala
-r
)+(M_PI
*r
);
5965 printf("lhalfcycle = %f r = %f\n", lhalfcycle
, r
);
5967 n
= (delta
- M_PI
*r
) / (lhalfcycle
- 2.*r
) + 1;
5968 *a
= (delta
+ 4.*n
*r
- n
*M_PI
*r
+ 4.*r
- M_PI
*r
)/(2.*n
);
5973 oproute_min_spacing(toporouter_oproute_t
*a
, toporouter_oproute_t
*b
)
5975 return lookup_thickness(a
->style
) / 2. + lookup_thickness(b
->style
) / 2. + MAX(lookup_keepaway(a
->style
), lookup_keepaway(b
->style
));
5979 vector_angle(gdouble ox
, gdouble oy
, gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
)
5981 gdouble alen
= sqrt(pow(ax
-ox
,2)+pow(ay
-oy
,2));
5982 gdouble blen
= sqrt(pow(bx
-ox
,2)+pow(by
-oy
,2));
5983 return acos( ((ax
-ox
)*(bx
-ox
)+(ay
-oy
)*(by
-oy
)) / (alen
* blen
) );
5986 toporouter_serpintine_t
*
5987 toporouter_serpintine_new(gdouble x
, gdouble y
, gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, gpointer start
, gdouble halfa
, gdouble
5988 radius
, guint nhalfcycles
)
5990 toporouter_serpintine_t
*serp
= malloc(sizeof(toporouter_serpintine_t
));
5997 serp
->start
= start
;
5998 serp
->halfa
= halfa
;
5999 serp
->radius
= radius
;
6000 serp
->nhalfcycles
= nhalfcycles
;
6005 //#define DEBUG_RUBBERBAND 1
6008 check_non_intersect_vertex(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
,
6009 toporouter_vertex_t
*opv
, gint wind
, gint
*arcwind
, gdouble
*arcr
, guint debug
)
6011 gdouble ms
, line_int_x
, line_int_y
, x
, y
, d
= 0., m
;
6012 gdouble tx0
, ty0
, tx1
, ty1
;
6015 g_assert(pathv
->routingedge
);
6017 if(TOPOROUTER_IS_CONSTRAINT(pathv
->routingedge
)) {
6018 gdouble d
= tvdistance(tedge_v1(pathv
->routingedge
), tedge_v2(pathv
->routingedge
)) / 2.;
6019 ms
= min_spacing(pathv
, arcv
);
6022 ms
= edge_min_spacing(g_list_find(edge_routing(pathv
->routingedge
), pathv
), pathv
->routingedge
, arcv
, debug
);
6026 if(!vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(arcv
), vy(arcv
), &line_int_x
, &line_int_y
)) {
6028 if(coord_distance2(x0
, y0
, line_int_x
, line_int_y
) < coord_distance2(x1
, y1
, line_int_x
, line_int_y
))
6029 { line_int_x
= x0
; line_int_y
= y0
; }else{ line_int_x
= x1
; line_int_y
= y1
; }
6031 m
= perpendicular_gradient(cartesian_gradient(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
));
6033 m
= cartesian_gradient(x0
, y0
, x1
, y1
);
6036 coords_on_line(vx(arcv
), vy(arcv
), m
, 100., &tx0
, &ty0
, &tx1
, &ty1
);
6038 wind1
= coord_wind(tx0
, ty0
, tx1
, ty1
, line_int_x
, line_int_y
);
6039 wind2
= coord_wind(tx0
, ty0
, tx1
, ty1
, vx(opv
), vy(opv
));
6041 if(!wind2
|| wind1
== wind2
) return -1.;
6044 coords_on_line(line_int_x
, line_int_y
, perpendicular_gradient(m
), ms
, &tx0
, &ty0
, &tx1
, &ty1
);
6045 if(coord_distance2(tx0
, ty0
, vx(opv
), vy(opv
)) < coord_distance2(tx1
, ty1
, vx(opv
), vy(opv
)))
6046 { x
= tx0
; y
= ty0
; }else{ x
= tx1
; y
= ty1
; }
6048 toporouter_vertex_t
*parent
= pathv
->parent
, *child
= pathv
->child
;
6049 guint windtests
= 0;
6051 d
= coord_distance(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
);
6052 coord_move_towards_coord_values(line_int_x
, line_int_y
, vx(arcv
), vy(arcv
), ms
+ d
, &x
, &y
);
6054 wind1
= coord_wind(line_int_x
, line_int_y
, x
, y
, vx(parent
), vy(parent
));
6055 wind2
= coord_wind(line_int_x
, line_int_y
, x
, y
, vx(child
), vy(child
));
6056 if(wind1
&& wind2
&& wind1
== wind2
) {
6058 if(windtests
++ == 2) return -1.;
6060 if(parent
->flags
& VERTEX_FLAG_ROUTE
) parent
= parent
->parent
;
6061 if(child
->flags
& VERTEX_FLAG_ROUTE
) child
= child
->child
;
6068 *arcwind
= tvertex_wind(pathv
->parent
, pathv
, arcv
);
6070 #ifdef DEBUG_RUBBERBAND
6072 // printf("non-int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, d + ms,
6073 // vx(arcv), vy(arcv), vx(opv), vy(opv));
6080 check_intersect_vertex(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
,
6081 toporouter_vertex_t
*opv
, gint wind
, gint
*arcwind
, gdouble
*arcr
, guint debug
)
6083 gdouble ms
, line_int_x
, line_int_y
, x
, y
, d
= 0.;
6085 if(TOPOROUTER_IS_CONSTRAINT(pathv
->routingedge
)) {
6086 gdouble d
= tvdistance(tedge_v1(pathv
->routingedge
), tedge_v2(pathv
->routingedge
)) / 2.;
6087 ms
= min_spacing(pathv
, arcv
);
6090 ms
= edge_min_spacing(g_list_find(edge_routing(pathv
->routingedge
), pathv
), pathv
->routingedge
, arcv
, debug
);
6093 if(!vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(arcv
), vy(arcv
), &line_int_x
, &line_int_y
))
6096 d
= coord_distance(line_int_x
, line_int_y
, vx(arcv
), vy(arcv
));
6099 if(d
> ms
- EPSILON
)
6102 coord_move_towards_coord_values(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
, ms
, &x
, &y
);
6105 *arcwind
= tvertex_wind(pathv
->parent
, pathv
, arcv
);
6106 // *arcwind = coord_wind(x0, y0, x, y, x1, y1);
6107 #ifdef DEBUG_RUBBERBAND
6109 // printf("int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, ms - d,
6110 // vx(arcv), vy(arcv), vx(opv), vy(opv));
6116 /* returns non-zero if arc has loops */
6118 check_arc_for_loops(gpointer t1
, toporouter_arc_t
*arc
, gpointer t2
)
6120 gdouble x0
, y0
, x1
, y1
;
6122 if(TOPOROUTER_IS_VERTEX(t1
)) { x0
= vx(TOPOROUTER_VERTEX(t1
)); y0
= vy(TOPOROUTER_VERTEX(t1
)); }
6123 else { x0
= TOPOROUTER_ARC(t1
)->x1
; y0
= TOPOROUTER_ARC(t1
)->y1
; }
6125 if(TOPOROUTER_IS_VERTEX(t2
)) { x1
= vx(TOPOROUTER_VERTEX(t2
)); y1
= vy(TOPOROUTER_VERTEX(t2
)); }
6126 else { x1
= TOPOROUTER_ARC(t2
)->x0
; y1
= TOPOROUTER_ARC(t2
)->y0
; }
6128 if(coord_intersect_prop(x0
, y0
, arc
->x0
, arc
->y0
, arc
->x1
, arc
->y1
, x1
, y1
) ) {
6130 // (arc->x0 > arc->x1 - EPSILON && arc->x0 < arc->x1 + EPSILON &&
6131 // arc->y0 > arc->y1 - EPSILON && arc->y0 < arc->y1 + EPSILON)
6133 #ifdef DEBUG_RUBBERBAND
6134 printf("LOOPS %f %f -> %f %f & %f %f -> %f %f\n", x0
, y0
, arc
->x0
, arc
->y0
, arc
->x1
, arc
->y1
, x1
, y1
);
6141 toporouter_rubberband_arc_t
*
6142 new_rubberband_arc(toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
, gdouble r
, gdouble d
, gint wind
, GList
*list
)
6144 toporouter_rubberband_arc_t
*rba
= malloc(sizeof(toporouter_rubberband_arc_t
));
6155 compare_rubberband_arcs(toporouter_rubberband_arc_t
*a
, toporouter_rubberband_arc_t
*b
)
6156 { return b
->d
- a
->d
; }
6159 free_list_elements(gpointer data
, gpointer user_data
)
6163 /* 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 */
6166 vertex_edge_facing_vertex(GtsVertex *v, gdouble x, gdouble y)
6168 GSList *ts = gts_vertex_triangles(GTS_VERTEX(n), NULL);
6172 GtsTriangle *t = GTS_TRIANGLE(i->data);
6173 GtsEdge *e = gts_triangle_edge_opposite(t, v);
6175 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)) &&
6176 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))
6191 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
)
6193 GSList
*ns
= gts_vertex_neighbors(GTS_VERTEX(v
), NULL
, NULL
);
6198 toporouter_vertex_t
*n
= TOPOROUTER_VERTEX(i
->data
);
6199 gdouble segintx
, seginty
;
6200 if(vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(n
), vy(n
), &segintx
, &seginty
)) {
6201 toporouter_edge_t
*e
= tedge(n
, v
);
6202 gdouble ms
= 0., d
= coord_distance(segintx
, seginty
, vx(n
), vy(n
));
6203 toporouter_vertex_t
*a
, *b
;
6204 GList
*closestnet
= NULL
;
6208 if(v
== tedge_v1(e
)) {
6211 closestnet
= edge_routing(e
);
6215 closestnet
= g_list_last(edge_routing(e
));
6219 ms
= edge_min_spacing(closestnet
, e
, b
, 0);
6220 ms
+= min_oproute_net_spacing(oproute
, TOPOROUTER_VERTEX(closestnet
->data
));
6222 ms
= min_oproute_vertex_spacing(oproute
, b
);
6229 if(vx(v
) == x0
&& vy(v
) == y0
) {
6230 *arcwind
= coord_wind(x0
, y0
, vx(n
), vy(n
), x1
, y1
);
6231 }else if(vx(v
) == x1
&& vy(v
) == y1
) {
6232 *arcwind
= coord_wind(x1
, y1
, vx(n
), vy(n
), x0
, y0
);
6234 fprintf(stderr
, "ERROR: check_adj_pushing_vertex encountered bad vertex v (coordinates don't match)\n");
6249 oproute_rubberband_segment(toporouter_t
*r
, toporouter_oproute_t
*oproute
, GList
*path
, gpointer t1
, gpointer t2
, guint debug
)
6251 gdouble x0
, y0
, x1
, y1
;
6252 toporouter_vertex_t
*v1
, *v2
, *av1
, *av2
; /* v{1,2} are the vertex terminals of the segment, or arc terminal centres */
6253 toporouter_arc_t
*arc1
= NULL
, *arc2
= NULL
, *newarc
= NULL
; /* arc{1,2} are the arc terminals of the segment, if they exist */
6255 GList
*list1
, *list2
;
6258 toporouter_rubberband_arc_t
*max
= NULL
;
6261 gint v1wind
, v2wind
, arcwind
;
6263 if(TOPOROUTER_IS_VERTEX(t1
)) {
6264 v1
= TOPOROUTER_VERTEX(t1
);
6265 x0
= vx(v1
); y0
= vy(v1
);
6267 g_assert(TOPOROUTER_IS_ARC(t1
));
6268 arc1
= TOPOROUTER_ARC(t1
);
6269 v1
= TOPOROUTER_VERTEX(arc1
->v1
);
6274 if(TOPOROUTER_IS_VERTEX(t2
)) {
6275 v2
= TOPOROUTER_VERTEX(t2
);
6276 x1
= vx(v2
); y1
= vy(v2
);
6278 g_assert(TOPOROUTER_IS_ARC(t2
));
6279 arc2
= TOPOROUTER_ARC(t2
);
6280 v2
= TOPOROUTER_VERTEX(arc2
->v2
);
6285 #define TEST_AND_INSERT(z) if(d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v, z, arcr, d, arcwind, i));
6286 #define ARC_CHECKS(z) (!(arc1 && arc1->centre == z) && !(arc2 && arc2->centre == z) && \
6287 !(TOPOROUTER_IS_VERTEX(t1) && z == v1) && !(TOPOROUTER_IS_VERTEX(t2) && z == v2))
6289 if(v1
== v2
|| !i
->next
|| TOPOROUTER_VERTEX(i
->data
) == v2
) return NULL
;
6291 //#ifdef DEBUG_RUBBERBAND
6293 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
));
6294 // if(v1->routingedge) print_edge(v1->routingedge);
6295 // if(v2->routingedge) print_edge(v2->routingedge);
6300 /* check the vectices adjacent to the terminal vectices for push against the segment */
6301 //if(TOPOROUTER_IS_VERTEX(t1)) {
6302 // toporouter_vertex_t *arcc = NULL;
6303 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v1, &arcr, &arcwind, &arcc);
6304 // g_assert(arcc != v1);
6305 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v1, arcc, arcr, d, arcwind, path->next));
6308 //if(TOPOROUTER_IS_VERTEX(t2)) {
6309 // toporouter_vertex_t *arcc = NULL;
6310 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v2, &arcr, &arcwind, &arcc);
6311 // g_assert(arcc != v2);
6312 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v2, arcc, arcr, d, arcwind, g_list_last(path)->prev));
6317 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6319 if(v
== v2
|| v
== v1
|| !v
->routingedge
) break;
6321 #ifdef DEBUG_RUBBERBAND
6323 // printf("current v %f,%f - edge %f,%f %f,%f\n", vx(v), vy(v),
6324 // vx(tedge_v1(v->routingedge)), vy(tedge_v1(v->routingedge)),
6325 // vx(tedge_v2(v->routingedge)), vy(tedge_v2(v->routingedge))
6328 g_assert(v
->routingedge
);
6330 v1wind
= coord_wind(x0
, y0
, x1
, y1
, vx(tedge_v1(v
->routingedge
)), vy(tedge_v1(v
->routingedge
)));
6331 v2wind
= coord_wind(x0
, y0
, x1
, y1
, vx(tedge_v2(v
->routingedge
)), vy(tedge_v2(v
->routingedge
)));
6332 // if(debug) printf("\twinds: %d %d\n", v1wind, v2wind);
6333 if(!v1wind
&& !v2wind
) { i
= i
->next
; continue; }
6336 if(v1wind
&& v2wind
&& v1wind
!= v2wind
) { /* edge is cutting through the current segment */
6338 if(ARC_CHECKS(tedge_v1(v
->routingedge
)) ){ /* edge v1 is not the centre of an arc terminal */
6339 d
= check_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v1(v
->routingedge
), tedge_v2(v
->routingedge
), v1wind
, &arcwind
, &arcr
, debug
);
6340 TEST_AND_INSERT(tedge_v1(v
->routingedge
));
6343 if(ARC_CHECKS(tedge_v2(v
->routingedge
)) ){ /* edge v2 is not the centre of an arc terminal */
6344 d
= check_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v2(v
->routingedge
), tedge_v1(v
->routingedge
), v2wind
, &arcwind
, &arcr
, debug
);
6345 TEST_AND_INSERT(tedge_v2(v
->routingedge
));
6347 }else{ /* edge is on one side of the segment */
6349 if(ARC_CHECKS(tedge_v1(v
->routingedge
)) ){ /* edge v1 is not the centre of an arc terminal */
6350 d
= check_non_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v1(v
->routingedge
), tedge_v2(v
->routingedge
), v1wind
, &arcwind
, &arcr
, debug
);
6351 TEST_AND_INSERT(tedge_v1(v
->routingedge
));
6354 if(ARC_CHECKS(tedge_v2(v
->routingedge
)) ){ /* edge v2 is not the centre of an arc terminal */
6355 d
= check_non_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v2(v
->routingedge
), tedge_v1(v
->routingedge
), v2wind
, &arcwind
, &arcr
, debug
);
6356 TEST_AND_INSERT(tedge_v2(v
->routingedge
));
6363 arcs
= g_list_sort(arcs
, (GCompareFunc
) compare_rubberband_arcs
);
6364 //rubberband_insert_maxarc:
6365 if(!arcs
) return NULL
;
6366 max
= TOPOROUTER_RUBBERBAND_ARC(arcs
->data
);
6368 av2
= max
->pathv
; i
= max
->list
->next
;
6370 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6371 if(v
->routingedge
&& (tedge_v1(v
->routingedge
) == max
->arcv
|| tedge_v2(v
->routingedge
) == max
->arcv
)) {
6372 av2
= v
; i
= i
->next
; continue;
6377 av1
= max
->pathv
; i
= max
->list
->prev
;
6379 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6380 if(v
->routingedge
&& (tedge_v1(v
->routingedge
) == max
->arcv
|| tedge_v2(v
->routingedge
) == max
->arcv
)) {
6381 av1
= v
; i
= i
->prev
; continue;
6385 //#ifdef DEBUG_RUBBERBAND
6387 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
);
6389 newarc
= toporouter_arc_new(oproute
, av1
, av2
, max
->arcv
, max
->r
, max
->wind
);
6391 if(TOPOROUTER_IS_VERTEX(t1
))
6392 calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), newarc
, 0);
6393 else if(calculate_arc_to_arc(r
, TOPOROUTER_ARC(t1
), newarc
)) {
6394 printf("\tERROR: best: r = %f d = %f\n", max
->r
, max
->d
);
6395 printf("\tOPROUTE: %s\n", oproute
->netlist
);
6396 print_vertex(oproute
->term1
);
6397 print_vertex(oproute
->term2
);
6401 if(TOPOROUTER_IS_VERTEX(t2
))
6402 calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), newarc
, 1);
6403 else if(calculate_arc_to_arc(r
, newarc
, TOPOROUTER_ARC(t2
))) {
6404 printf("\tERROR: best: r = %f d = %f\n", max
->r
, max
->d
);
6405 printf("\tOPROUTE: %s\n", oproute
->netlist
);
6406 print_vertex(oproute
->term1
);
6407 print_vertex(oproute
->term2
);
6411 //if(check_arc_for_loops(t1, newarc, t2)) {
6412 // if(arc1 && arc2) calculate_arc_to_arc(r, arc1, arc2);
6413 // else if(arc1) calculate_term_to_arc(TOPOROUTER_VERTEX(t2), arc1, 1);
6414 // else if(arc2) calculate_term_to_arc(TOPOROUTER_VERTEX(t1), arc2, 0);
6416 //#ifdef DEBUG_RUBBERBAND
6417 // printf("REMOVING NEW ARC @ %f,%f\n", vx(newarc->centre), vy(newarc->centre));
6418 // //TODO: properly remove newarc
6421 // arcs = g_list_remove(arcs, max);
6423 // goto rubberband_insert_maxarc;
6427 list1
= oproute_rubberband_segment(r
, oproute
, path
, t1
, newarc
, debug
);
6428 list2
= oproute_rubberband_segment(r
, oproute
, i
->next
, newarc
, t2
, debug
);
6431 GList
*list
= g_list_last(list1
);
6432 toporouter_arc_t
*testarc
= TOPOROUTER_ARC(list
->data
);
6433 toporouter_arc_t
*parc
= list
->prev
? TOPOROUTER_ARC(list
->prev
->data
) : arc1
;
6434 gdouble px
= parc
? parc
->x1
: vx(TOPOROUTER_VERTEX(t1
)), py
= parc
? parc
->y1
: vy(TOPOROUTER_VERTEX(t1
));
6436 if(coord_intersect_prop(px
, py
, testarc
->x0
, testarc
->y0
, testarc
->x1
, testarc
->y1
, newarc
->x0
, newarc
->y0
)) {
6437 list1
= g_list_remove(list1
, testarc
);
6438 if(parc
) calculate_arc_to_arc(r
, parc
, newarc
);
6439 else calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), newarc
, 0);
6440 //#ifdef DEBUG_RUBBERBAND
6442 printf("REMOVING ARC @ %f,%f\n", vx(testarc
->centre
), vy(testarc
->centre
));
6447 toporouter_arc_t
*testarc
= TOPOROUTER_ARC(list2
->data
);
6448 toporouter_arc_t
*narc
= list2
->next
? TOPOROUTER_ARC(list2
->next
->data
) : arc2
;
6449 gdouble nx
= narc
? narc
->x0
: vx(TOPOROUTER_VERTEX(t2
)), ny
= narc
? narc
->y0
: vy(TOPOROUTER_VERTEX(t2
));
6451 if(coord_intersect_prop(newarc
->x1
, newarc
->y1
, testarc
->x0
, testarc
->y0
, testarc
->x1
, testarc
->y1
, nx
, ny
)) {
6452 list2
= g_list_remove(list2
, testarc
);
6453 if(narc
) calculate_arc_to_arc(r
, newarc
, narc
);
6454 else calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), newarc
, 1);
6456 //#ifdef DEBUG_RUBBERBAND
6458 printf("REMOVING ARC @ %f,%f\n", vx(testarc
->centre
), vy(testarc
->centre
));
6463 g_list_foreach(arcs
, free_list_elements
, NULL
);
6466 return g_list_concat(list1
, g_list_prepend(list2
, newarc
));
6470 oproute_check_all_loops(toporouter_t
*r
, toporouter_oproute_t
*oproute
)
6476 t1
= oproute
->term1
;
6479 toporouter_arc_t
*arc
= TOPOROUTER_ARC(i
->data
);
6480 gpointer t2
= i
->next
? i
->next
->data
: oproute
->term2
;
6482 if(check_arc_for_loops(t1
, arc
, t2
)) {
6484 if(TOPOROUTER_IS_ARC(t1
) && TOPOROUTER_IS_ARC(t2
))
6485 calculate_arc_to_arc(r
, TOPOROUTER_ARC(t1
), TOPOROUTER_ARC(t2
));
6486 else if(TOPOROUTER_IS_ARC(t1
))
6487 calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), TOPOROUTER_ARC(t1
), 1);
6488 else if(TOPOROUTER_IS_ARC(t2
))
6489 calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), TOPOROUTER_ARC(t2
), 0);
6491 oproute
->arcs
= g_list_remove(oproute
->arcs
, arc
);
6492 goto loopcheck_restart
;
6503 opposite_triangle(GtsTriangle
*t
, toporouter_edge_t
*e
)
6505 GSList
*i
= GTS_EDGE(e
)->triangles
;
6510 if(GTS_TRIANGLE(i
->data
) != t
) return GTS_TRIANGLE(i
->data
);
6519 speccut_edge_routing_from_edge(GList
*i
, toporouter_edge_t
*e
)
6521 g_assert(TOPOROUTER_IS_EDGE(e
));
6523 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
6525 if(!(curv
->flags
& VERTEX_FLAG_TEMP
)) {
6526 toporouter_vertex_t
*newv
= tvertex_intersect(curv
, curv
->parent
, tedge_v1(e
), tedge_v2(e
));
6528 // printf("\nCURV:\n");
6529 // print_vertex(curv);
6531 // printf("CURV child:\n");
6533 // print_vertex(curv->child);
6535 // printf("NULL\n");
6537 // printf("CURV parent:\n");
6539 // print_vertex(curv->parent);
6541 // printf("NULL\n");
6545 newv
->flags
|= VERTEX_FLAG_ROUTE
;
6546 newv
->flags
|= VERTEX_FLAG_SPECCUT
;
6547 e
->routing
= g_list_insert_sorted_with_data(e
->routing
, newv
, routing_edge_insert
, e
);
6548 newv
->route
= curv
->route
;
6549 newv
->oproute
= curv
->oproute
;
6550 newv
->routingedge
= e
;
6551 GTS_POINT(newv
)->z
= vz(curv
);
6553 newv
->parent
= curv
->parent
;
6556 // curv->parent = newv;
6558 index
= g_list_index(newv
->route
->path
, curv
);
6560 newv
->route
->path
= g_list_insert(newv
->route
->path
, newv
, index
);
6563 if(newv
->oproute
) newv
->oproute
->path
= newv
->route
->path
;
6566 if(!(curv
->child
->routingedge
)) {
6567 newv
= tvertex_intersect(curv
, curv
->child
, tedge_v1(e
), tedge_v2(e
));
6571 newv
->flags
|= VERTEX_FLAG_ROUTE
;
6572 newv
->flags
|= VERTEX_FLAG_SPECCUT
;
6573 e
->routing
= g_list_insert_sorted_with_data(e
->routing
, newv
, routing_edge_insert
, e
);
6574 newv
->route
= curv
->route
;
6575 newv
->oproute
= curv
->oproute
;
6576 newv
->routingedge
= e
;
6577 GTS_POINT(newv
)->z
= vz(curv
);
6579 newv
->parent
= curv
;
6580 newv
->child
= curv
->child
;
6582 // curv->child = newv;
6584 index
= g_list_index(newv
->route
->path
, curv
);
6586 newv
->route
->path
= g_list_insert(newv
->route
->path
, newv
, index
+1);
6589 if(newv
->oproute
) newv
->oproute
->path
= newv
->route
->path
;
6601 speccut_edge_patch_links(toporouter_edge_t
*e
)
6603 GList
*i
= e
->routing
;
6604 g_assert(TOPOROUTER_IS_EDGE(e
));
6606 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6607 v
->parent
->child
= v
;
6608 v
->child
->parent
= v
;
6614 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
)
6616 GtsTriangle
*t
, *opt
;
6617 toporouter_vertex_t
*opv
, *opv2
;
6618 toporouter_edge_t
*ope1
, *ope2
;
6619 gdouble cap
, flow
, line_int_x
, line_int_y
;
6621 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
6623 if(!(t
= gts_triangle_use_edges(GTS_EDGE(e
), GTS_EDGE(e1
), GTS_EDGE(e2
)))) {
6624 printf("check_speccut: NULL t\n");
6628 if(!(opt
= opposite_triangle(t
, e
))) {
6629 // printf("check_speccut: NULL opt\n");
6633 if(!(opv
= segment_common_vertex(GTS_SEGMENT(e1
), GTS_SEGMENT(e2
)))) {
6634 printf("check_speccut: NULL opv\n");
6638 if(!(opv2
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(opt
, GTS_EDGE(e
))))) {
6639 printf("check_speccut: NULL opv2\n");
6643 //TODO: shifting it out of the way would be better
6645 GList
*i
= e
->routing
;
6647 toporouter_vertex_t
*ev
= TOPOROUTER_VERTEX(i
->data
);
6648 if(!tvertex_wind(opv
, ev
, opv2
)) return 0;
6654 ope1
= tedge(opv2
, tedge_v1(e
));
6655 ope2
= tedge(opv2
, tedge_v2(e
));
6657 //this fixes the weird pad exits in r8c board
6658 // if(TOPOROUTER_IS_CONSTRAINT(ope1)) return 0;
6659 if(TOPOROUTER_IS_CONSTRAINT(ope2
)) return 0;
6661 if(!tvertex_wind(opv2
, tedge_v1(e
), opv
)) return 0;
6662 if(!tvertex_wind(opv2
, tedge_v2(e
), opv
)) return 0;
6664 if(!vertex_line_normal_intersection(
6665 vx(tedge_v1(e
)), vy(tedge_v1(e
)),
6666 vx(tedge_v2(e
)), vy(tedge_v2(e
)),
6668 &line_int_x
, &line_int_y
)) return 0;
6672 //if(vertex_line_normal_intersection(tev1x(e), tev1y(e), tev2x(e), tev2y(e), vx(opv), vy(opv), &line_int_x, &line_int_y))
6675 g_assert(opt
&& opv2
);
6677 /* this is just temp, for the purposes of determining flow */
6678 if(tedge_v1(ope1
) == opv2
) {
6679 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6680 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_append(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6682 ope1
->routing
= g_list_append(ope1
->routing
, v1
);
6684 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6685 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_prepend(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6687 ope1
->routing
= g_list_prepend(ope1
->routing
, v1
);
6690 cap
= triangle_interior_capacity(opt
, opv2
);
6691 flow
= flow_from_edge_to_edge(opt
, tedge(opv2
, tedge_v1(e
)), tedge(opv2
, tedge_v2(e
)), opv2
, v1
);
6693 /* temp v1 removed */
6694 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6695 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6697 ope1
->routing
= g_list_remove(ope1
->routing
, v1
);
6700 toporouter_edge_t
*newe
= TOPOROUTER_EDGE(gts_edge_new(GTS_EDGE_CLASS(toporouter_edge_class()), GTS_VERTEX(opv
), GTS_VERTEX(opv2
)));
6702 speccut_edge_routing_from_edge(edge_routing(e1
), newe
);
6703 speccut_edge_routing_from_edge(edge_routing(e2
), newe
);
6704 speccut_edge_routing_from_edge(edge_routing(ope1
), newe
);
6705 speccut_edge_routing_from_edge(edge_routing(ope2
), newe
);
6707 speccut_edge_patch_links(newe
);
6709 printf("SPECCUT WITH v %f,%f for seg %f,%f %f,%f detected\n", vx(opv2), vy(opv2),
6712 printf("\tflow %f cap %f\n", flow, cap);
6715 if(newe
->routing
) return 1;
6724 oproute_path_speccut(toporouter_oproute_t
*oproute
)
6727 toporouter_vertex_t
*pv
;
6728 path_speccut_restart
:
6732 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6735 if(pv
&& (v
->routingedge
|| pv
->routingedge
) && !(pv
->flags
& VERTEX_FLAG_SPECCUT
) && !(v
->flags
& VERTEX_FLAG_SPECCUT
)) {
6737 if(!v
->routingedge
) {
6738 if(check_speccut(oproute
, pv
, v
, tedge(tedge_v1(pv
->routingedge
), v
), pv
->routingedge
, tedge(tedge_v2(pv
->routingedge
), v
)))
6739 goto path_speccut_restart
;
6740 if(check_speccut(oproute
, pv
, v
, tedge(tedge_v2(pv
->routingedge
), v
), pv
->routingedge
, tedge(tedge_v1(pv
->routingedge
), v
)))
6741 goto path_speccut_restart
;
6742 }else if(!pv
->routingedge
) {
6743 if(check_speccut(oproute
, v
, pv
, tedge(tedge_v1(v
->routingedge
), pv
), v
->routingedge
, tedge(tedge_v2(v
->routingedge
), pv
)))
6744 goto path_speccut_restart
;
6745 if(check_speccut(oproute
, v
, pv
, tedge(tedge_v2(v
->routingedge
), pv
), v
->routingedge
, tedge(tedge_v1(v
->routingedge
), pv
)))
6746 goto path_speccut_restart
;
6748 toporouter_vertex_t
*v1
= NULL
, *v2
= NULL
;
6749 edges_third_edge(GTS_SEGMENT(v
->routingedge
), GTS_SEGMENT(pv
->routingedge
), &v1
, &v2
);
6750 if(check_speccut(oproute
, v
, pv
, tedge(v1
, v2
), v
->routingedge
, pv
->routingedge
))
6751 goto path_speccut_restart
;
6763 toporouter_oproute_t
*
6764 oproute_rubberband(toporouter_t
*r
, GList
*path
)
6766 toporouter_oproute_t
*oproute
= malloc(sizeof(toporouter_oproute_t
));
6770 oproute
->term1
= TOPOROUTER_VERTEX(path
->data
);
6771 oproute
->term2
= TOPOROUTER_VERTEX(g_list_last(path
)->data
);
6772 oproute
->arcs
= NULL
;
6773 oproute
->style
= vertex_bbox(oproute
->term1
)->cluster
->netlist
->style
;
6774 oproute
->netlist
= vertex_bbox(oproute
->term1
)->cluster
->netlist
->netlist
;
6775 oproute
->layergroup
= vz(oproute
->term1
);
6776 oproute
->path
= path
;
6777 oproute
->serp
= NULL
;
6779 oproute
->term1
->parent
= NULL
;
6780 oproute
->term2
->child
= NULL
;
6782 path_set_oproute(path
, oproute
);
6784 // if(!strcmp(oproute->netlist, " unnamed_net1"))
6785 oproute_path_speccut(oproute
);
6787 #ifdef DEBUG_RUBBERBAND
6788 if(!strcmp(oproute
->netlist
, " VCC3V3") && vx(oproute
->term1
) == 95700. && vy(oproute
->term1
) == 70800. &&
6789 vx(oproute
->term2
) == 196700. && vy(oproute
->term2
) == 67300.)
6791 // printf("OPROUTE %s - %f,%f %f,%f\n", oproute->netlist, vx(oproute->term1), vy(oproute->term1), vx(oproute->term2), vy(oproute->term2));
6792 // print_path(path);
6793 oproute
->arcs
= oproute_rubberband_segment(r
, oproute
, path
, oproute
->term1
, oproute
->term2
, 1);
6796 oproute
->arcs
= oproute_rubberband_segment(r
, oproute
, path
, oproute
->term1
, oproute
->term2
, 0);
6798 oproute_check_all_loops(r
, oproute
);
6804 toporouter_export(toporouter_t
*r
)
6806 GList
*i
= r
->routednets
;
6807 GList
*oproutes
= NULL
;
6810 toporouter_route_t
*routedata
= TOPOROUTER_ROUTE(i
->data
);
6811 toporouter_oproute_t
*oproute
= oproute_rubberband(r
, routedata
->path
);
6812 oproutes
= g_list_prepend(oproutes
, oproute
);
6818 toporouter_oproute_t
*oproute
= (toporouter_oproute_t
*) i
->data
;
6819 export_oproutes(r
, oproute
);
6820 oproute_free(oproute
);
6824 Message(_("Reticulating splines... successful\n\n"));
6825 Message(_("Wiring cost: %f inches\n"), r
->wiring_score
/ 1000.);
6826 printf("Wiring cost: %f inches\n", r
->wiring_score
/ 1000.);
6828 g_list_free(oproutes
);
6832 toporouter_route_t
*
6833 routedata_create(void)
6835 toporouter_route_t
*routedata
= malloc(sizeof(toporouter_route_t
));
6836 routedata
->netlist
= NULL
;
6837 routedata
->alltemppoints
= NULL
;
6838 routedata
->path
= NULL
;
6839 routedata
->curpoint
= NULL
;
6840 routedata
->pscore
= routedata
->score
= 0.;
6841 routedata
->flags
= 0;
6842 routedata
->src
= routedata
->dest
= NULL
;
6843 routedata
->psrc
= routedata
->pdest
= NULL
;
6844 routedata
->ppath
= routedata
->topopath
= NULL
;
6846 routedata
->ppathindices
= NULL
;
6848 routedata
->destvertices
= routedata
->srcvertices
= NULL
;
6853 print_routedata(toporouter_route_t *routedata)
6855 GList *srcvertices = cluster_vertices(routedata->src);
6856 GList *destvertices = cluster_vertices(routedata->dest);
6858 printf("ROUTEDATA:\n");
6859 printf("SRCVERTICES:\n");
6860 print_vertices(srcvertices);
6861 printf("DESTVERTICES:\n");
6862 print_vertices(destvertices);
6864 g_list_free(srcvertices);
6865 g_list_free(destvertices);
6868 toporouter_route_t
*
6869 import_route(toporouter_t
*r
, RatType
*line
)
6871 toporouter_route_t
*routedata
= routedata_create();
6873 routedata
->src
= cluster_find(r
, line
->Point1
.X
, line
->Point1
.Y
, line
->group1
);
6874 routedata
->dest
= cluster_find(r
, line
->Point2
.X
, line
->Point2
.Y
, line
->group2
);
6876 if(!routedata
->src
) printf("couldn't locate src\n");
6877 if(!routedata
->dest
) printf("couldn't locate dest\n");
6879 if(!routedata
->src
|| !routedata
->dest
) {
6880 printf("PROBLEM: couldn't locate rat src or dest for rat %d,%d,%d -> %d,%d,%d\n",
6881 line
->Point1
.X
, line
->Point1
.Y
, line
->group1
, line
->Point2
.X
, line
->Point2
.Y
, line
->group2
);
6886 routedata
->netlist
= routedata
->src
->netlist
;
6888 g_assert(routedata
->src
->netlist
== routedata
->dest
->netlist
);
6890 g_ptr_array_add(r
->routes
, routedata
);
6891 g_ptr_array_add(routedata
->netlist
->routes
, routedata
);
6893 r
->failednets
= g_list_prepend(r
->failednets
, routedata
);
6899 delete_route(toporouter_route_t
*routedata
, guint destroy
)
6901 GList
*i
= routedata
->path
;
6902 toporouter_vertex_t
*pv
= NULL
;
6905 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6909 if(tv
&& pv
&& !(tv
->flags
& VERTEX_FLAG_ROUTE
) && !(pv
->flags
& VERTEX_FLAG_ROUTE
)) {
6910 toporouter_edge_t
*e
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(tv
), GTS_VERTEX(pv
)));
6912 if(e
&& (e
->flags
& EDGE_FLAG_DIRECTCONNECTION
)) {
6913 e
->flags
^= EDGE_FLAG_DIRECTCONNECTION
;
6920 i
= routedata
->path
;
6922 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6927 if(tv
->routingedge
) {
6928 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6929 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
6931 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
6932 if(destroy
) gts_object_destroy ( GTS_OBJECT(tv
) );
6938 if(routedata
->path
) g_list_free(routedata
->path
);
6939 routedata
->path
= NULL
;
6940 routedata
->curpoint
= NULL
;
6941 routedata
->score
= INFINITY
;
6942 routedata
->alltemppoints
= NULL
;
6945 /* remove route can be later reapplied */
6947 remove_route(GList
*path
)
6952 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6957 // if(tv->flags & VERTEX_FLAG_ROUTE) g_assert(tv->route == routedata);
6959 if(tv
->routingedge
) {
6961 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6962 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
6964 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
6972 apply_route(GList
*path
, toporouter_route_t
*routedata
)
6975 toporouter_vertex_t
*pv
= NULL
;
6982 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6984 if(tv
->routingedge
) {
6985 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6986 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_insert_sorted_with_data(
6987 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
,
6989 routing_edge_insert
,
6992 tv
->routingedge
->routing
= g_list_insert_sorted_with_data(
6993 tv
->routingedge
->routing
,
6995 routing_edge_insert
,
7006 if(tv
->flags
& VERTEX_FLAG_ROUTE
) g_assert(tv
->route
== routedata
);
7012 TOPOROUTER_VERTEX(path
->data
)->parent
= NULL
;
7020 compare_routedata_ascending(gconstpointer a
, gconstpointer b
)
7022 toporouter_route_t
*ra
= (toporouter_route_t
*)a
;
7023 toporouter_route_t
*rb
= (toporouter_route_t
*)b
;
7024 return ra
->score
- rb
->score
;
7028 print_costmatrix(gdouble
*m
, guint n
)
7030 printf("COST MATRIX:\n");
7031 for(guint i
= 0;i
<n
;i
++) {
7032 for(guint j
= 0;j
<n
;j
++) {
7033 printf("%f ", m
[(i
*n
)+j
]);
7041 init_cost_matrix(gdouble
*m
, guint n
)
7043 for(guint i
=0;i
<n
;i
++) {
7044 for(guint j
=0;j
<n
;j
++) {
7045 m
[(i
*n
)+j
] = INFINITY
;
7051 toporouter_netscore_t
*
7052 netscore_create(toporouter_t
*r
, toporouter_route_t
*routedata
, guint n
, guint id
)
7054 toporouter_netscore_t
*netscore
= malloc(sizeof(toporouter_netscore_t
));
7055 GList
*path
= route(r
, routedata
, 0);
7059 netscore
->routedata
= routedata
;
7060 routedata
->detourscore
= netscore
->score
= routedata
->score
;
7062 if(!finite(routedata
->detourscore
)) {
7063 printf("WARNING: !finite(detourscore)\n");
7064 print_cluster(routedata
->src
);
7065 print_cluster(routedata
->dest
);
7069 netscore
->pairwise_nodetour
= malloc(n
* sizeof(guint
));
7071 for(guint i
=0;i
<n
;i
++) {
7072 netscore
->pairwise_nodetour
[i
] = 0;
7075 netscore
->pairwise_detour_sum
= 0.;
7076 netscore
->pairwise_fails
= 0;
7081 routedata
->topopath
= g_list_copy(routedata
->path
);
7082 delete_route(routedata
, 0);
7089 netscore_destroy(toporouter_netscore_t
*netscore
)
7091 free(netscore
->pairwise_nodetour
);
7096 print_netscores(GPtrArray
* netscores
)
7098 printf("NETSCORES: \n\n");
7099 printf(" %15s %15s %15s\n----------------------------------------------------\n", "Score", "Detour Sum", "Pairwise Fails");
7101 for(toporouter_netscore_t
**i
= (toporouter_netscore_t
**) netscores
->pdata
; i
< (toporouter_netscore_t
**) netscores
->pdata
+ netscores
->len
; i
++) {
7102 #ifdef DEBUG_NETSCORES
7103 printf("%4d %15f %15f %15d %15x\n", (*i
)->id
, (*i
)->score
, (*i
)->pairwise_detour_sum
, (*i
)->pairwise_fails
, (guint
)*i
);
7111 netscore_pairwise_calculation(toporouter_netscore_t
*netscore
, GPtrArray
*netscores
)
7113 toporouter_netscore_t
**netscores_base
= (toporouter_netscore_t
**) (netscores
->pdata
);
7114 toporouter_route_t
*temproutedata
= routedata_create();
7116 //route(netscore->r, netscore->routedata, 0);
7117 apply_route(netscore
->routedata
->topopath
, netscore
->routedata
);
7119 for(toporouter_netscore_t
**i
= netscores_base
; i
< netscores_base
+ netscores
->len
; i
++) {
7121 if(!netscore
->pairwise_nodetour
[i
-netscores_base
] && *i
!= netscore
&& (*i
)->routedata
->netlist
!= netscore
->routedata
->netlist
) {
7123 temproutedata
->src
= (*i
)->routedata
->src
;
7124 temproutedata
->dest
= (*i
)->routedata
->dest
;
7126 route(netscore
->r
, temproutedata
, 0);
7128 if(temproutedata
->score
== (*i
)->score
) {
7129 netscore
->pairwise_nodetour
[i
-netscores_base
] = 1;
7130 (*i
)->pairwise_nodetour
[netscore
->id
] = 1;
7132 if(!finite(temproutedata
->score
)) {
7133 netscore
->pairwise_fails
+= 1;
7135 netscore
->pairwise_detour_sum
+= temproutedata
->score
- (*i
)->score
;
7138 delete_route(temproutedata
, 1);
7143 // delete_route(netscore->routedata, 1);
7144 remove_route(netscore
->routedata
->topopath
);
7146 free(temproutedata
);
7150 netscore_pairwise_size_compare(toporouter_netscore_t
**a
, toporouter_netscore_t
**b
)
7152 // infinite scores are last
7153 if(!finite((*a
)->score
) && !finite((*b
)->score
)) return 0;
7154 if(finite((*a
)->score
) && !finite((*b
)->score
)) return -1;
7155 if(finite((*b
)->score
) && !finite((*a
)->score
)) return 1;
7157 // order by pairwise fails
7158 if((*a
)->pairwise_fails
< (*b
)->pairwise_fails
) return -1;
7159 if((*b
)->pairwise_fails
< (*a
)->pairwise_fails
) return 1;
7161 // order by pairwise detour
7162 if((*a
)->pairwise_detour_sum
< (*b
)->pairwise_detour_sum
) return -1;
7163 if((*b
)->pairwise_detour_sum
< (*a
)->pairwise_detour_sum
) return 1;
7166 if((*a
)->score
< (*b
)->score
) return -1;
7167 if((*b
)->score
< (*a
)->score
) return 1;
7173 netscore_pairwise_compare(toporouter_netscore_t
**a
, toporouter_netscore_t
**b
)
7175 // infinite scores are last
7176 if(!finite((*a
)->score
) && !finite((*b
)->score
)) return 0;
7177 if(finite((*a
)->score
) && !finite((*b
)->score
)) return -1;
7178 if(finite((*b
)->score
) && !finite((*a
)->score
)) return 1;
7180 // order by pairwise fails
7181 if((*a
)->pairwise_fails
< (*b
)->pairwise_fails
) return -1;
7182 if((*b
)->pairwise_fails
< (*a
)->pairwise_fails
) return 1;
7184 // order by pairwise detour
7185 if((*a
)->pairwise_detour_sum
< (*b
)->pairwise_detour_sum
) return -1;
7186 if((*b
)->pairwise_detour_sum
< (*a
)->pairwise_detour_sum
) return 1;
7192 order_nets_preroute_greedy(toporouter_t
*r
, GList
*nets
, GList
**rnets
)
7194 gint len
= g_list_length(nets
);
7195 GPtrArray
* netscores
= g_ptr_array_sized_new(len
);
7196 guint failcount
= 0;
7199 toporouter_netscore_t
*ns
= netscore_create(r
, TOPOROUTER_ROUTE(nets
->data
), len
, failcount
++);
7200 if(ns
) g_ptr_array_add(netscores
, ns
);
7206 g_ptr_array_foreach(netscores
, (GFunc
) netscore_pairwise_calculation
, netscores
);
7208 g_ptr_array_sort(netscores
, (GCompareFunc
) r
->netsort
);
7210 #ifdef DEBUG_ORDERING
7211 print_netscores(netscores
);
7215 FOREACH_NETSCORE(netscores
) {
7216 *rnets
= g_list_prepend(*rnets
, netscore
->routedata
);
7217 if(!finite(netscore
->score
)) failcount
++;
7218 netscore_destroy(netscore
);
7221 g_ptr_array_free(netscores
, TRUE
);
7226 toporouter_vertex_t
*
7227 edge_closest_vertex(toporouter_edge_t
*e
, toporouter_vertex_t
*v
)
7229 GList
*i
= v
->routingedge
? edge_routing(v
->routingedge
) : NULL
;
7230 gdouble closestd
= 0.;
7231 toporouter_vertex_t
*closestv
= NULL
;
7234 toporouter_vertex_t
*ev
= TOPOROUTER_VERTEX(i
->data
);
7235 gdouble tempd
= gts_point_distance2(GTS_POINT(ev
), GTS_POINT(v
));
7237 if(!closestv
|| (tempd
< closestd
)) {
7249 snapshot(toporouter_t
*r
, char *name
, GList
*datas
)
7254 for(i
=0;i
<groupcount();i
++) {
7256 sprintf(buffer
, "route-%s-%d.png", name
, i
);
7257 toporouter_draw_surface(r
, r
->layers
[i
].surface
, buffer
, 2048, 2048, 2, datas
, i
, NULL
);
7265 route_conflict(toporouter_t *r, toporouter_route_t *route, guint *n)
7267 GList *i = route->path;
7268 toporouter_vertex_t *pv = NULL;
7272 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
7273 if(pv && vz(v) == vz(pv))
7274 cost += vertices_routing_conflict_cost(r, v, pv, n);
7283 route_conflicts(toporouter_route_t
*route
)
7285 GList
*conflicts
= NULL
, *i
= route
->path
;
7286 toporouter_vertex_t
*pv
= NULL
;
7289 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7291 if(pv
&& vz(pv
) == vz(v
)) {
7292 GList
*temp
= vertices_routing_conflicts(pv
, v
), *j
;
7296 toporouter_route_t
*conroute
= TOPOROUTER_ROUTE(j
->data
);
7297 if(!g_list_find(conflicts
, conroute
))
7298 conflicts
= g_list_prepend(conflicts
, conroute
);
7302 if(temp
) g_list_free(temp
);
7312 spread_edge(gpointer item
, gpointer data
)
7314 toporouter_edge_t
*e
= TOPOROUTER_EDGE(item
);
7315 toporouter_vertex_t
*v
;
7319 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
7321 i
= edge_routing(e
);
7323 if(!g_list_length(i
)) return 0;
7325 if(g_list_length(i
) == 1) {
7326 v
= TOPOROUTER_VERTEX(i
->data
);
7327 GTS_POINT(v
)->x
= (vx(edge_v1(e
)) + vx(edge_v2(e
))) / 2.;
7328 GTS_POINT(v
)->y
= (vy(edge_v1(e
)) + vy(edge_v2(e
))) / 2.;
7332 s
= spacing
= (gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) ) / (g_list_length(i
) + 1);
7335 v
= TOPOROUTER_VERTEX(i
->data
);
7336 vertex_move_towards_vertex_values(edge_v1(e
), edge_v2(e
), s
, &(GTS_POINT(v
)->x
), &(GTS_POINT(v
)->y
));
7346 route_checkpoint(toporouter_route_t
*route
, toporouter_route_t
*temproute
)
7348 GList
*i
= g_list_last(route
->path
);
7349 gint n
= g_list_length(route
->path
);
7351 if(route
->ppathindices
) free(route
->ppathindices
);
7352 route
->ppathindices
= malloc(sizeof(gint
)*n
);
7356 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7359 if(v
->routingedge
) {
7360 GList
*j
= g_list_find(edge_routing(v
->routingedge
), v
)->prev
;
7361 gint tempindex
= g_list_index(edge_routing(v
->routingedge
), v
);
7364 if(TOPOROUTER_VERTEX(j
->data
)->route
== temproute
) tempindex
--;
7368 route
->ppathindices
[n
] = tempindex
;
7370 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
7371 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
);
7373 v
->routingedge
->routing
= g_list_remove(v
->routingedge
->routing
, v
);
7379 route
->pscore
= route
->score
;
7380 route
->ppath
= route
->path
;
7381 remove_route(route
->path
);
7383 route
->psrc
= route
->src
;
7384 route
->pdest
= route
->dest
;
7385 //route->src->pc = route->src->c;
7386 //route->dest->pc = route->dest->c;
7390 route_restore(toporouter_route_t
*route
)
7393 toporouter_vertex_t
*pv
= NULL
;
7396 g_assert(route
->ppath
);
7397 g_assert(route
->ppathindices
);
7399 route
->path
= route
->ppath
;
7402 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7404 if(v
->routingedge
) {
7405 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
7406 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_insert(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
, route
->ppathindices
[n
]);
7408 v
->routingedge
->routing
= g_list_insert(v
->routingedge
->routing
, v
, route
->ppathindices
[n
]);
7410 // space_edge(v->routingedge, NULL);
7423 route
->score
= route
->pscore
;
7424 route
->src
= route
->psrc
;
7425 route
->dest
= route
->pdest
;
7426 //route->src->c = route->src->pc;
7427 //route->dest->c = route->dest->pc;
7432 cluster_merge(toporouter_route_t
*routedata
)
7434 gint oldc
= routedata
->dest
->c
, newc
= routedata
->src
->c
;
7436 FOREACH_CLUSTER(routedata
->netlist
->clusters
) {
7437 if(cluster
->c
== oldc
)
7444 netlist_recalculate(toporouter_netlist_t
*netlist
, GList
*ignore
)
7446 GList
*i
= g_list_last(netlist
->routed
);
7447 gint n
= netlist
->clusters
->len
-1;
7449 FOREACH_CLUSTER(netlist
->clusters
) {
7454 if(!ignore
|| !g_list_find(ignore
, i
->data
)) cluster_merge(TOPOROUTER_ROUTE(i
->data
));
7461 netlists_recalculate(GList
*netlists
, GList
*ignore
)
7463 GList
*i
= netlists
;
7465 netlist_recalculate(TOPOROUTER_NETLIST(i
->data
), ignore
);
7471 netlists_rollback(GList
*netlists
)
7473 // netlists_recalculate(netlists, NULL);
7475 toporouter_netlist_t
*netlist
= TOPOROUTER_NETLIST(netlists
->data
);
7477 FOREACH_CLUSTER(netlist
->clusters
) {
7478 cluster
->c
= cluster
->pc
;
7481 netlists
= netlists
->next
;
7486 print_netlist(toporouter_netlist_t
*netlist
)
7489 printf("NETLIST %s: ", netlist
->netlist
);
7491 FOREACH_CLUSTER(netlist
->clusters
) {
7492 printf("%d ", cluster
->c
);
7498 #define REMOVE_ROUTING(x) x->netlist->routed = g_list_remove(x->netlist->routed, x); \
7499 r->routednets = g_list_remove(r->routednets, x); \
7500 r->failednets = g_list_prepend(r->failednets, x)
7502 #define INSERT_ROUTING(x) x->netlist->routed = g_list_prepend(x->netlist->routed, x); \
7503 r->routednets = g_list_prepend(r->routednets, x); \
7504 r->failednets = g_list_remove(r->failednets, x)
7507 roar_route(toporouter_t
*r
, toporouter_route_t
*routedata
, gint threshold
)
7510 GList
*netlists
= NULL
, *routed
= NULL
;
7512 g_assert(!routedata
->path
);
7514 if(routedata
->src
->c
== routedata
->dest
->c
) {
7515 printf("ERROR: attempt to route already complete route\n");
7516 g_assert(routedata
->src
->c
!= routedata
->dest
->c
);
7519 routedata
->src
->pc
= routedata
->src
->c
;
7520 routedata
->dest
->pc
= routedata
->dest
->c
;
7521 routedata
->psrc
= routedata
->src
;
7522 routedata
->pdest
= routedata
->dest
;
7524 r
->flags
|= TOPOROUTER_FLAG_LEASTINVALID
;
7525 if(route(r
, routedata
, 0)) {
7526 GList
*conflicts
, *j
;
7528 INSERT_ROUTING(routedata
);
7530 conflicts
= route_conflicts(routedata
);
7531 cluster_merge(routedata
);
7533 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7537 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7538 if(!g_list_find(netlists
, conflict
->netlist
))
7539 netlists
= g_list_prepend(netlists
, conflict
->netlist
);
7541 route_checkpoint(conflict
, routedata
);
7543 REMOVE_ROUTING(conflict
);
7547 netlists
= g_list_prepend(netlists
, routedata
->netlist
);
7548 netlists_recalculate(netlists
, NULL
);
7552 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7553 g_assert(conflict
->src
->c
!= conflict
->dest
->c
);
7554 if(route(r
, conflict
, 0)) {
7555 cluster_merge(conflict
);
7557 routed
= g_list_prepend(routed
, conflict
);
7559 INSERT_ROUTING(conflict
);
7561 netlist_recalculate(conflict
->netlist
, NULL
);
7564 if(++intfails
>= threshold
) {
7567 toporouter_route_t
*intconflict
= TOPOROUTER_ROUTE(i
->data
);
7568 REMOVE_ROUTING(intconflict
);
7569 delete_route(intconflict
, 1);
7572 delete_route(routedata
, 1);
7573 i
= g_list_last(conflicts
);
7575 toporouter_route_t
*intconflict
= TOPOROUTER_ROUTE(i
->data
);
7577 route_restore(intconflict
);
7578 INSERT_ROUTING(intconflict
);
7582 REMOVE_ROUTING(routedata
);
7584 netlists_recalculate(netlists
, NULL
);
7585 goto roar_route_end
;
7593 netlists_recalculate(netlists
, NULL
);
7597 g_list_free(conflicts
);
7598 g_list_free(netlists
);
7601 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7604 g_list_free(routed
);
7609 roar_router(toporouter_t
*r
, gint failcount
, gint threshold
)
7611 gint pfailcount
= failcount
+1;
7613 Message(_("ROAR router: "));
7614 for(guint j
=0;j
<6;j
++) {
7615 GList
*failed
= g_list_copy(r
->failednets
), *k
= failed
;
7619 failcount
+= roar_route(r
, TOPOROUTER_ROUTE(k
->data
), threshold
);
7622 g_list_free(failed
);
7624 printf("\tROAR pass %d - %d routed - %d failed\n", j
, g_list_length(r
->routednets
), g_list_length(r
->failednets
));
7626 if(!failcount
|| failcount
>= pfailcount
) {
7627 Message(_("%d nets remaining\n"), failcount
);
7630 Message(_("%d -> "), failcount
);
7631 pfailcount
= failcount
;
7638 route_detour_compare(toporouter_route_t
**a
, toporouter_route_t
**b
)
7639 { return ((*b
)->score
- (*b
)->detourscore
) - ((*a
)->score
- (*a
)->detourscore
); }
7644 roar_detour_route(toporouter_t
*r
, toporouter_route_t
*data
)
7646 gdouble pscore
= data
->score
, nscore
= 0.;
7647 GList
*netlists
= NULL
;
7649 route_checkpoint(data
, NULL
);
7651 REMOVE_ROUTING(data
);
7653 netlists
= g_list_prepend(NULL
, data
->netlist
);
7654 netlists_recalculate(netlists
, NULL
);
7656 r
->flags
|= TOPOROUTER_FLAG_LEASTINVALID
;
7657 if(route(r
, data
, 0)) {
7658 GList
*conflicts
, *j
;
7660 nscore
= data
->score
;
7661 conflicts
= route_conflicts(data
);
7663 INSERT_ROUTING(data
);
7665 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7669 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7671 if(!g_list_find(netlists
, conflict
->netlist
))
7672 netlists
= g_list_prepend(netlists
, conflict
->netlist
);
7673 pscore
+= conflict
->score
;
7675 route_checkpoint(conflict
, NULL
);
7676 REMOVE_ROUTING(conflict
);
7680 netlists_recalculate(netlists
, NULL
);
7684 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7686 if(route(r
, conflict
, 0)) {
7687 cluster_merge(conflict
);
7688 INSERT_ROUTING(conflict
);
7689 nscore
+= conflict
->score
;
7692 goto roar_detour_route_rollback_int
;
7697 if(nscore
> pscore
) {
7698 j
= g_list_last(conflicts
);
7699 roar_detour_route_rollback_int
:
7700 REMOVE_ROUTING(data
);
7703 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7704 REMOVE_ROUTING(conflict
);
7705 delete_route(conflict
, 1);
7709 j
= g_list_last(conflicts
);
7711 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7712 route_restore(conflict
);
7713 INSERT_ROUTING(conflict
);
7716 delete_route(data
, 1);
7718 goto roar_detour_route_rollback_exit
;
7722 g_list_free(conflicts
);
7724 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7725 roar_detour_route_rollback_exit
:
7726 route_restore(data
);
7727 INSERT_ROUTING(data
);
7729 netlists_recalculate(netlists
, NULL
);
7731 g_list_free(netlists
);
7735 detour_router(toporouter_t
*r
)
7737 GList
*i
= r
->routednets
;
7738 guint n
= g_list_length(r
->routednets
);
7739 GPtrArray
* scores
= g_ptr_array_sized_new(n
);
7742 toporouter_route_t
*curroute
= TOPOROUTER_ROUTE(i
->data
);
7743 curroute
->score
= path_score(r
, curroute
->path
);
7744 g_ptr_array_add(scores
, i
->data
);
7748 g_ptr_array_sort(scores
, (GCompareFunc
) route_detour_compare
);
7750 r
->flags
|= TOPOROUTER_FLAG_DETOUR
;
7752 for(toporouter_route_t
**i
= (toporouter_route_t
**) scores
->pdata
; i
< (toporouter_route_t
**) scores
->pdata
+ scores
->len
; i
++) {
7753 toporouter_route_t
*curroute
= (*i
);
7755 if(finite(curroute
->score
) && finite(curroute
->detourscore
)) {
7756 // printf("%15s %15f \t %8f,%8f - %8f,%8f\n", (*i)->src->netlist + 2, (*i)->score - (*i)->detourscore,
7757 // vx(curroute->mergebox1->point), vy(curroute->mergebox1->point),
7758 // vx(curroute->mergebox2->point), vy(curroute->mergebox2->point));
7760 if(curroute
->score
- curroute
->detourscore
> 1000.) {
7761 roar_detour_route(r
, curroute
);
7768 r
->flags
^= TOPOROUTER_FLAG_DETOUR
;
7770 g_ptr_array_free(scores
, TRUE
);
7775 rubix_router(toporouter_t
*r
, gint failcount
)
7777 GList
*i
, *ordering
;
7778 order_nets_preroute_greedy(r
, r
->failednets
, &ordering
);
7782 toporouter_route_t
*data
= TOPOROUTER_ROUTE(i
->data
);
7784 if(route(r
, data
, 0)) {
7785 INSERT_ROUTING(data
);
7786 cluster_merge(data
);
7793 g_list_free(ordering
);
7799 hybrid_router(toporouter_t
*r
)
7801 gint failcount
= g_list_length(r
->failednets
);
7802 r
->flags
|= TOPOROUTER_FLAG_AFTERORDER
;
7803 r
->flags
|= TOPOROUTER_FLAG_AFTERRUBIX
;
7804 failcount
= rubix_router(r
, failcount
);
7806 Message(_("RUBIX router: %d nets remaining\n"), failcount
);
7807 printf("RUBIX router: %d nets remaining\n", failcount
);
7809 r
->flags
|= TOPOROUTER_FLAG_GOFAR
;
7811 for(guint i
=0;i
<6 && failcount
;i
++) {
7813 failcount
= roar_router(r
, failcount
, 5);
7814 // printf("THRESH 5\n");
7816 failcount
= roar_router(r
, failcount
, 2);
7817 // printf("THRESH 2\n");
7823 failcount
= roar_router(r
, failcount
, 2);
7830 parse_arguments(toporouter_t
*r
, int argc
, char **argv
)
7833 for(i
=0;i
<argc
;i
++) {
7834 if(sscanf(argv
[i
], "viacost=%d", &tempint
)) {
7835 r
->viacost
= (double)tempint
;
7836 }else if(sscanf(argv
[i
], "l%d", &tempint
)) {
7837 gdouble
*layer
= malloc(sizeof(gdouble
));
7838 *layer
= (double)tempint
;
7839 r
->keepoutlayers
= g_list_prepend(r
->keepoutlayers
, layer
);
7843 for (guint group
= 0; group
< max_layer
; group
++)
7844 for (i
= 0; i
< PCB
->LayerGroups
.Number
[group
]; i
++)
7845 if ((PCB
->LayerGroups
.Entries
[group
][i
] < max_layer
) && !(PCB
->Data
->Layer
[PCB
->LayerGroups
.Entries
[group
][i
]].On
)) {
7846 gdouble
*layer
= malloc(sizeof(gdouble
));
7847 *layer
= (double)group
;
7848 r
->keepoutlayers
= g_list_prepend(r
->keepoutlayers
, layer
);
7854 toporouter_new(void)
7856 toporouter_t
*r
= calloc(1, sizeof(toporouter_t
));
7859 gettimeofday(&r
->starttime
, NULL
);
7861 r
->netsort
= netscore_pairwise_compare
;
7863 r
->destboxes
= NULL
;
7864 r
->consumeddestboxes
= NULL
;
7871 r
->viacost
= 10000.;
7872 r
->stublength
= 300.;
7873 r
->serpintine_half_amplitude
= 1500.;
7875 r
->wiring_score
= 0.;
7880 r
->netlists
= g_ptr_array_new();
7881 r
->routes
= g_ptr_array_new();
7883 r
->keepoutlayers
= NULL
;
7885 r
->routednets
= NULL
;
7886 r
->failednets
= NULL
;
7890 gts_predicates_init();
7892 Message(_("Topological Autorouter\n"));
7893 Message(_("Started %s"),asctime(localtime(<ime
)));
7894 Message(_("-------------------------------------\n"));
7895 Message(_("Copyright 2009 Anthony Blake (tonyb33@gmail.com)\n\n"));
7900 acquire_twonets(toporouter_t
*r
)
7902 RAT_LOOP(PCB
->Data
);
7903 if( TEST_FLAG(SELECTEDFLAG
, line
) ) import_route(r
, line
);
7906 if(!r
->routes
->len
) {
7907 RAT_LOOP(PCB
->Data
);
7908 import_route(r
, line
);
7915 toporouter_netlist_t
*
7916 find_netlist_by_name(toporouter_t
*r
, char *name
)
7918 FOREACH_NETLIST(r
->netlists
) {
7919 if(!strcmp(netlist
->netlist
, name
)) return netlist
;
7925 toporouter_set_pair(toporouter_t
*r
, toporouter_netlist_t
*n1
, toporouter_netlist_t
*n2
)
7927 if(!n1
|| !n2
) return 0;
7934 toporouter (int argc
, char **argv
, int x
, int y
)
7936 toporouter_t
*r
= toporouter_new();
7937 parse_arguments(r
, argc
, argv
);
7941 //if(!toporouter_set_pair(r, find_netlist_by_name(r, " DRAM_DQS_N"), find_netlist_by_name(r, " DRAM_DQS"))) {
7942 // printf("Couldn't associate pair\n");
7947 for(gint i=0;i<groupcount();i++) {
7948 gts_surface_foreach_edge(r->layers[i].surface, space_edge, NULL);
7952 for(i=0;i<groupcount();i++) {
7954 sprintf(buffer, "route%d.png", i);
7955 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, NULL, i, NULL);
7959 toporouter_export(r
);
7962 SaveUndoSerialNumber ();
7964 RestoreUndoSerialNumber ();
7965 AddAllRats (false, NULL
);
7966 RestoreUndoSerialNumber ();
7967 IncrementUndoSerialNumber ();
7968 ClearAndRedrawOutput ();
7974 escape (int argc
, char **argv
, int x
, int y
)
7976 guint dir
, viax
, viay
;
7977 gdouble pitch
, length
, dx
, dy
;
7979 if(argc
!= 1) return 0;
7981 dir
= atoi(argv
[0]);
7984 ALLPAD_LOOP(PCB
->Data
);
7986 if( TEST_FLAG(SELECTEDFLAG
, pad
) ) {
7990 pitch
= sqrt( pow(abs(element
->Pad
[0].Point1
.X
- element
->Pad
[1].Point1
.X
), 2) +
7991 pow(abs(element
->Pad
[0].Point1
.Y
- element
->Pad
[1].Point1
.Y
), 2) );
7992 length
= sqrt(pow(pitch
,2) + pow(pitch
,2)) / 2.;
7994 dx
= length
* sin(M_PI
/4.);
7995 dy
= length
* cos(M_PI
/4.);
7999 viax
= pad
->Point1
.X
- dx
;
8000 viay
= pad
->Point1
.Y
+ dy
;
8003 viax
= pad
->Point1
.X
+ dx
;
8004 viay
= pad
->Point1
.Y
+ dy
;
8007 viax
= pad
->Point1
.X
+ dx
;
8008 viay
= pad
->Point1
.Y
- dy
;
8011 viax
= pad
->Point1
.X
- dx
;
8012 viay
= pad
->Point1
.Y
- dy
;
8015 viax
= pad
->Point1
.X
;
8016 viay
= pad
->Point1
.Y
+ (pitch
/2);
8019 viax
= pad
->Point1
.X
;
8020 viay
= pad
->Point1
.Y
- (pitch
/2);
8023 viax
= pad
->Point1
.X
- (pitch
/2);
8024 viay
= pad
->Point1
.Y
;
8027 viax
= pad
->Point1
.X
+ (pitch
/2);
8028 viay
= pad
->Point1
.Y
;
8031 printf("ERROR: escape() with bad direction (%d)\n", dir
);
8035 if ((via
= CreateNewVia (PCB
->Data
, viax
, viay
,
8036 Settings
.ViaThickness
, 2 * Settings
.Keepaway
,
8037 0, Settings
.ViaDrillingHole
, NULL
,
8038 NoFlags ())) != NULL
)
8040 AddObjectToCreateUndoList (VIA_TYPE
, via
, via
, via
);
8041 // if (gui->shift_is_pressed ())
8042 // ChangeObjectThermal (VIA_TYPE, via, via, via, PCB->ThermStyle);
8044 if((line
= CreateDrawnLineOnLayer (CURRENT
, pad
->Point1
.X
+ 1., pad
->Point1
.Y
+ 1., viax
+ 1., viay
+ 1.,
8045 Settings
.LineThickness
, 2 * Settings
.Keepaway
,
8049 AddObjectToCreateUndoList (LINE_TYPE
, CURRENT
, line
, line
);
8050 DrawLine (CURRENT
, line
, 0);
8061 IncrementUndoSerialNumber ();
8066 static HID_Action toporouter_action_list
[] = {
8067 {"Escape", "Select a set of pads", escape
, "Pad escape", "Escape()"},
8068 {"Toporouter", "Select net(s)", toporouter
, "Topological autorouter", "Toporouter()"}
8071 REGISTER_ACTIONS (toporouter_action_list
)
8073 void hid_toporouter_init()
8075 register_toporouter_action_list();