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
;
306 static inline gdouble
307 cluster_keepaway(toporouter_cluster_t
*cluster
)
309 if(cluster
) return lookup_keepaway(cluster
->netlist
->style
);
310 return lookup_keepaway(NULL
);
313 static inline gdouble
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)
928 static inline gdouble
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?
952 static inline gdouble
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
);
969 static inline gdouble
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_group
; 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)
1437 static inline gdouble
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)
1448 static inline gdouble
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.);
1849 static inline gdouble
1850 pad_rad(PadType
*pad
)
1852 return (lookup_thickness(pad
->Name
) / 2.) + lookup_keepaway(pad
->Name
);
1855 static inline gdouble
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 (component_silk_layer
);
1913 guint back
= GetLayerGroupNumberByNumber (solder_silk_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);
2582 // printf("adding cons: "); print_constraint(c1);
2584 GSList
*conflicts
= gts_delaunay_add_constraint (l
->surface
, i
->data
);
2585 GSList
*j
= conflicts
;
2587 if(TOPOROUTER_IS_CONSTRAINT(j
->data
)) {
2588 toporouter_constraint_t
*c2
= TOPOROUTER_CONSTRAINT(j
->data
);
2590 printf("\tconflict: "); print_constraint(c2
);
2595 g_slist_free(conflicts
);
2601 // goto build_cdt_continuation;
2602 // fprintf(stderr, "ADDED CONSTRAINTS\n");
2603 gts_allow_floating_vertices
= TRUE
;
2604 gts_object_destroy (GTS_OBJECT (v1
));
2605 gts_object_destroy (GTS_OBJECT (v2
));
2606 gts_object_destroy (GTS_OBJECT (v3
));
2607 gts_allow_floating_vertices
= FALSE
;
2612 gdouble quality = 0.50, area = G_MAXDOUBLE;
2613 guint num = gts_delaunay_conform(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL);
2618 num = gts_delaunay_refine(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL, (GtsKeyFunc) triangle_cost, data);
2623 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
);
2639 visited_cmp(gconstpointer a
, gconstpointer b
)
2647 coord_xangle(gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
)
2649 gdouble dx
, dy
, theta
;
2656 } else theta
= atan(dy
/dx
);
2659 if(bx
< ax
) theta
= M_PI
- theta
;
2661 if(bx
< ax
) theta
+= M_PI
;
2662 else theta
= (2 * M_PI
) - theta
;
2669 point_xangle(GtsPoint
*a
, GtsPoint
*b
)
2671 gdouble dx
, dy
, theta
;
2673 dx
= fabs(a
->x
- b
->x
);
2674 dy
= fabs(a
->y
- b
->y
);
2678 } else theta
= atan(dy
/dx
);
2681 if(b
->x
< a
->x
) theta
= M_PI
- theta
;
2683 if(b
->x
< a
->x
) theta
+= M_PI
;
2684 else theta
= (2 * M_PI
) - theta
;
2692 cluster_vertices(toporouter_t
*r
, toporouter_cluster_t
*c
)
2698 FOREACH_CLUSTER(c
->netlist
->clusters
) {
2699 if((r
->flags
& TOPOROUTER_FLAG_AFTERRUBIX
&& cluster
->c
== c
->c
) || (!(r
->flags
& TOPOROUTER_FLAG_AFTERRUBIX
) && cluster
== c
)) {
2700 FOREACH_BBOX(cluster
->boxes
) {
2701 if(box
->type
== LINE
) {
2702 g_assert(box
->constraints
->data
);
2703 rval
= g_list_prepend(rval
, tedge_v1(box
->constraints
->data
));
2704 rval
= g_list_prepend(rval
, tedge_v2(box
->constraints
->data
));
2705 }else if(box
->point
) {
2706 rval
= g_list_prepend(rval
, TOPOROUTER_VERTEX(box
->point
));
2707 //g_assert(vertex_bbox(TOPOROUTER_VERTEX(box->point)) == box);
2709 printf("WARNING: cluster_vertices: unhandled bbox type\n");
2723 print_cluster(toporouter_cluster_t
*c
)
2727 printf("[CLUSTER (NULL)]\n");
2731 printf("CLUSTER %d: NETLIST = %s STYLE = %s\n", c
->c
, c
->netlist
->netlist
, c
->netlist
->style
);
2733 FOREACH_BBOX(c
->boxes
) {
2739 toporouter_cluster_t
*
2740 cluster_create(toporouter_t
*r
, toporouter_netlist_t
*netlist
)
2742 toporouter_cluster_t
*c
= malloc(sizeof(toporouter_cluster_t
));
2744 c
->c
= c
->pc
= netlist
->clusters
->len
;
2745 g_ptr_array_add(netlist
->clusters
, c
);
2746 c
->netlist
= netlist
;
2747 c
->boxes
= g_ptr_array_new();
2753 toporouter_bbox_locate(toporouter_t
*r
, toporouter_term_t type
, void *data
, gdouble x
, gdouble y
, guint layergroup
)
2755 GtsPoint
*p
= gts_point_new(gts_point_class(), x
, y
, layergroup
);
2756 GSList
*boxes
= gts_bb_tree_stabbed(r
->bboxtree
, p
), *i
= boxes
;
2758 gts_object_destroy(GTS_OBJECT(p
));
2761 toporouter_bbox_t
*box
= TOPOROUTER_BBOX(i
->data
);
2763 if(box
->type
== type
&& box
->data
== data
) {
2764 g_slist_free(boxes
);
2771 g_slist_free(boxes
);
2776 cluster_join_bbox(toporouter_cluster_t
*cluster
, toporouter_bbox_t
*box
)
2779 g_ptr_array_add(cluster
->boxes
, box
);
2780 box
->cluster
= cluster
;
2784 toporouter_netlist_t
*
2785 netlist_create(toporouter_t
*r
, char *netlist
, char *style
)
2787 toporouter_netlist_t
*nl
= malloc(sizeof(toporouter_netlist_t
));
2788 nl
->netlist
= netlist
;
2790 nl
->clusters
= g_ptr_array_new();
2791 nl
->routes
= g_ptr_array_new();
2794 g_ptr_array_add(r
->netlists
, nl
);
2799 import_clusters(toporouter_t
*r
)
2801 NetListListType nets
;
2802 ResetFoundPinsViasAndPads (false);
2803 ResetFoundLinesAndPolygons (false);
2804 nets
= CollectSubnets(false);
2805 NETLIST_LOOP(&nets
);
2807 if(netlist
->NetN
> 0) {
2808 toporouter_netlist_t
*nl
= netlist_create(r
, netlist
->Net
->Connection
->menu
->Name
, netlist
->Net
->Connection
->menu
->Style
);
2813 toporouter_cluster_t
*cluster
= cluster_create(r
, nl
);
2814 #ifdef DEBUG_MERGING
2817 CONNECTION_LOOP (net
);
2820 if(connection
->type
== LINE_TYPE
) {
2821 LineType
*line
= (LineType
*) connection
->ptr2
;
2822 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, LINE
, line
, connection
->X
, connection
->Y
, connection
->group
);
2823 cluster_join_bbox(cluster
, box
);
2825 #ifdef DEBUG_MERGING
2826 printf("\tLINE %d,%d\n", connection
->X
, connection
->Y
);
2828 }else if(connection
->type
== PAD_TYPE
) {
2829 PadType
*pad
= (PadType
*) connection
->ptr2
;
2830 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, PAD
, pad
, connection
->X
, connection
->Y
, connection
->group
);
2831 cluster_join_bbox(cluster
, box
);
2833 #ifdef DEBUG_MERGING
2834 printf("\tPAD %d,%d\n", connection
->X
, connection
->Y
);
2836 }else if(connection
->type
== PIN_TYPE
) {
2838 for(guint m
=0;m
<groupcount();m
++) {
2839 PinType
*pin
= (PinType
*) connection
->ptr2
;
2840 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, PIN
, pin
, connection
->X
, connection
->Y
, m
);
2841 cluster_join_bbox(cluster
, box
);
2844 #ifdef DEBUG_MERGING
2845 printf("\tPIN %d,%d\n", connection
->X
, connection
->Y
);
2847 }else if(connection
->type
== VIA_TYPE
) {
2849 for(guint m
=0;m
<groupcount();m
++) {
2850 PinType
*pin
= (PinType
*) connection
->ptr2
;
2851 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, VIA
, pin
, connection
->X
, connection
->Y
, m
);
2852 cluster_join_bbox(cluster
, box
);
2855 #ifdef DEBUG_MERGING
2856 printf("\tVIA %d,%d\n", connection
->X
, connection
->Y
);
2858 }else if(connection
->type
== POLYGON_TYPE
) {
2859 PolygonType
*polygon
= (PolygonType
*) connection
->ptr2
;
2860 toporouter_bbox_t
*box
= toporouter_bbox_locate(r
, POLYGON
, polygon
, connection
->X
, connection
->Y
, connection
->group
);
2861 cluster_join_bbox(cluster
, box
);
2863 #ifdef DEBUG_MERGING
2864 printf("\tPOLYGON %d,%d\n", connection
->X
, connection
->Y
);
2870 #ifdef DEBUG_MERGING
2879 FreeNetListListMemory(&nets
);
2883 import_geometry(toporouter_t
*r
)
2885 toporouter_layer_t
*cur_layer
;
2890 for (group
= 0; group
< max_group
; group
++) {
2891 printf("Group %d: Number %d:\n", group
, PCB
->LayerGroups
.Number
[group
]);
2893 for (int entry
= 0; entry
< PCB
->LayerGroups
.Number
[group
]; entry
++) {
2894 printf("\tEntry %d\n", PCB
->LayerGroups
.Entries
[group
][entry
]);
2898 /* Allocate space for per layer struct */
2899 cur_layer
= r
->layers
= malloc(groupcount() * sizeof(toporouter_layer_t
));
2901 /* Foreach layer, read in pad vertices and constraints, and build CDT */
2902 for (group
= 0; group
< max_group
; group
++) {
2904 printf("*** LAYER GROUP %d ***\n", group
);
2906 if(PCB
->LayerGroups
.Number
[group
] > 0){
2907 cur_layer
->vertices
= NULL
;
2908 cur_layer
->constraints
= NULL
;
2911 printf("reading board constraints from layer %d into group %d\n", PCB
->LayerGroups
.Entries
[group
][0], group
);
2913 read_board_constraints(r
, cur_layer
, PCB
->LayerGroups
.Entries
[group
][0]);
2915 printf("reading points from layer %d into group %d \n",PCB
->LayerGroups
.Entries
[group
][0], group
);
2917 read_points(r
, cur_layer
, PCB
->LayerGroups
.Entries
[group
][0]);
2919 //#ifdef DEBUG_IMPORT
2920 // printf("reading pads from layer %d into group %d\n", number, group);
2922 read_pads(r
, cur_layer
, group
);
2924 GROUP_LOOP(PCB
->Data
, group
)
2928 printf("reading lines from layer %d into group %d\n", number
, group
);
2930 read_lines(r
, cur_layer
, layer
, number
);
2938 printf("building CDT\n");
2940 build_cdt(r
, cur_layer
);
2941 printf("finished\n");
2944 for(i=0;i<groupcount();i++) {
2946 sprintf(buffer, "build%d.png", i);
2947 toporouter_draw_surface(r, r->layers[i].surface, buffer, 2048, 2048, 2, NULL, i, NULL);
2951 printf("finished building CDT\n");
2957 r
->bboxtree
= gts_bb_tree_new(r
->bboxes
);
2962 printf("finished import!\n");
2968 compare_points(gconstpointer a
, gconstpointer b
)
2970 GtsPoint
*i
= GTS_POINT(a
);
2971 GtsPoint
*j
= GTS_POINT(b
);
2974 if(i
->y
== j
->y
) return 0;
2975 if(i
->y
< j
->y
) return -1;
2978 if(i
->x
< j
->x
) return -1;
2983 compare_segments(gconstpointer a
, gconstpointer b
)
2985 if(a
== b
) return 0;
2986 if(a
< b
) return -1;
2989 #define DEBUG_CLUSTER_FIND 1
2990 toporouter_cluster_t
*
2991 cluster_find(toporouter_t
*r
, gdouble x
, gdouble y
, gdouble z
)
2993 GtsPoint
*p
= gts_point_new(gts_point_class(), x
, y
, z
);
2994 GSList
*hits
= gts_bb_tree_stabbed(r
->bboxtree
, p
);
2995 toporouter_cluster_t
*rval
= NULL
;
2997 #ifdef DEBUG_CLUSTER_FIND
2998 printf("FINDING %f,%f,%f\n\n", x
, y
, z
);
3002 toporouter_bbox_t
*box
= TOPOROUTER_BBOX(hits
->data
);
3004 #ifdef DEBUG_CLUSTER_FIND
3005 printf("HIT BOX: "); print_bbox(box
);
3008 if(box
->layer
== (int)z
) {
3009 if(box
->type
!= BOARD
) {
3010 if(box
->type
== LINE
) {
3011 LineType
*line
= (LineType
*)box
->data
;
3012 gint linewind
= coord_wind(line
->Point1
.X
, line
->Point1
.Y
, x
, y
, line
->Point2
.X
, line
->Point2
.Y
);
3014 if(line
->Point1
.X
> x
- EPSILON
&& line
->Point1
.X
< x
+ EPSILON
&&
3015 line
->Point1
.Y
> y
- EPSILON
&& line
->Point1
.Y
< y
+ EPSILON
) {
3016 rval
= box
->cluster
;
3019 if(line
->Point2
.X
> x
- EPSILON
&& line
->Point2
.X
< x
+ EPSILON
&&
3020 line
->Point2
.Y
> y
- EPSILON
&& line
->Point2
.Y
< y
+ EPSILON
) {
3021 rval
= box
->cluster
;
3025 rval
= box
->cluster
;
3029 }else if(box
->surface
) {
3031 if(gts_point_locate(p
, box
->surface
, NULL
)) {
3032 rval
= box
->cluster
;
3042 gts_object_destroy(GTS_OBJECT(p
));
3045 #ifdef DEBUG_CLUSTER_FIND
3046 printf("cluster_find: %f,%f,%f: ", x
, y
, z
);
3047 print_cluster(rval
);
3054 simple_h_cost(toporouter_t
*r
, toporouter_vertex_t
*curpoint
, toporouter_vertex_t
*destpoint
)
3056 gdouble layerpenalty
= (vz(curpoint
) == vz(destpoint
)) ? 0. : r
->viacost
;
3058 return gts_point_distance(GTS_POINT(curpoint
), GTS_POINT(destpoint
)) + layerpenalty
;
3061 #define FCOST(x) (x->gcost + x->hcost)
3063 route_heap_cmp(gpointer item
, gpointer data
)
3065 return FCOST(TOPOROUTER_VERTEX(item
));
3068 #define closelist_insert(p) closelist = g_list_prepend(closelist, p)
3071 toporouter_vertex_t
*key
;
3072 toporouter_vertex_t
*result
;
3073 }toporouter_heap_search_data_t
;
3076 toporouter_heap_search(gpointer data
, gpointer user_data
)
3078 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(data
);
3079 toporouter_heap_search_data_t
*heap_search_data
= (toporouter_heap_search_data_t
*)user_data
;
3080 if(v
== heap_search_data
->key
) heap_search_data
->result
= v
;
3084 toporouter_heap_color(gpointer data, gpointer user_data)
3086 toporouter_vertex_t *v = TOPOROUTER_VERTEX(data);
3087 v->flags |= (guint) user_data;
3090 static inline gdouble
3091 angle_span(gdouble a1
, gdouble a2
)
3094 return ((2*M_PI
)-a1
+ a2
);
3099 region_span(toporouter_vertex_region_t
*region
)
3103 g_assert(region
->v1
!= NULL
);
3104 g_assert(region
->v2
!= NULL
);
3105 g_assert(region
->origin
!= NULL
);
3107 a1
= point_xangle(GTS_POINT(region
->origin
), GTS_POINT(region
->v1
));
3108 a2
= point_xangle(GTS_POINT(region
->origin
), GTS_POINT(region
->v2
));
3110 return angle_span(a1
, a2
);
3114 edge_capacity(toporouter_edge_t
*e
)
3116 return gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
)));
3120 edge_flow(toporouter_edge_t
*e
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*dest
)
3122 GList
*i
= edge_routing(e
);
3123 toporouter_vertex_t
*pv
= tedge_v1(e
), *v
= NULL
;
3127 if((pv
== v1
|| pv
== v2
) && waiting
) {
3128 flow
+= min_vertex_net_spacing(pv
, dest
);
3136 v
= TOPOROUTER_VERTEX(i
->data
);
3140 flow
+= min_vertex_net_spacing(v
, pv
);
3142 flow
+= min_spacing(v
, pv
);
3144 if((v
== v1
|| v
== v2
) && waiting
) {
3145 flow
+= min_vertex_net_spacing(v
, dest
);
3155 flow
+= min_vertex_net_spacing(tedge_v2(e
), pv
);
3157 flow
+= min_spacing(tedge_v2(e
), pv
);
3163 print_path(GList
*path
)
3169 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3170 // printf("[V %f,%f,%f]\n", vx(v), vy(v), vz(v));
3173 if(v
->child
&& !g_list_find(path
, v
->child
))
3174 printf("\t CHILD NOT IN LIST\n");
3175 if(v
->parent
&& !g_list_find(path
, v
->parent
))
3176 printf("\t parent NOT IN LIST\n");
3184 split_path(GList
*path
)
3186 toporouter_vertex_t
*pv
= NULL
;
3187 GList
*curpath
= NULL
, *i
, *paths
= NULL
;
3193 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
3196 printf("v = %f,%f ", vx(v
), vy(v
));
3197 if(v
->parent
) printf("parent = %f,%f ", vx(v
->parent
), vy(v
->parent
));
3198 if(v
->child
) printf("child = %f,%f ", vx(v
->child
), vy(v
->child
));
3202 // if(v) printf("v = %f,%f\n", GTS_POINT(v)->x, GTS_POINT(v)->y);
3203 // if(pv) printf("pv = %f,%f\n", GTS_POINT(pv)->x, GTS_POINT(pv)->y);
3207 if(GTS_POINT(v
)->x
== GTS_POINT(pv
)->x
&& GTS_POINT(v
)->y
== GTS_POINT(pv
)->y
) {
3208 if(g_list_length(curpath
) > 1) paths
= g_list_prepend(paths
, curpath
);
3215 curpath
= g_list_append(curpath
, v
);
3221 if(g_list_length(curpath
) > 1)
3222 paths
= g_list_prepend(paths
, curpath
);
3229 #define edge_gradient(e) (cartesian_gradient(GTS_POINT(GTS_SEGMENT(e)->v1)->x, GTS_POINT(GTS_SEGMENT(e)->v1)->y, \
3230 GTS_POINT(GTS_SEGMENT(e)->v2)->x, GTS_POINT(GTS_SEGMENT(e)->v2)->y))
3233 /* sorting into ascending distance from v1 */
3235 routing_edge_insert(gconstpointer a
, gconstpointer b
, gpointer user_data
)
3237 GtsPoint
*v1
= GTS_POINT(edge_v1(user_data
));
3239 if(gts_point_distance2(v1
, GTS_POINT(a
)) < gts_point_distance2(v1
, GTS_POINT(b
)) - EPSILON
)
3241 if(gts_point_distance2(v1
, GTS_POINT(a
)) > gts_point_distance2(v1
, GTS_POINT(b
)) + EPSILON
)
3244 printf("a = %x b = %x\n", (int) a, (int) b);
3246 printf("WARNING: routing_edge_insert() with same points..\n \
3253 printf("A: "); print_vertex(TOPOROUTER_VERTEX(a));
3254 printf("B: "); print_vertex(TOPOROUTER_VERTEX(b));
3256 TOPOROUTER_VERTEX(a)->flags |= VERTEX_FLAG_RED;
3257 TOPOROUTER_VERTEX(b)->flags |= VERTEX_FLAG_RED;
3263 toporouter_vertex_t
*
3264 new_temp_toporoutervertex(gdouble x
, gdouble y
, toporouter_edge_t
*e
)
3266 GtsVertexClass
*vertex_class
= GTS_VERTEX_CLASS (toporouter_vertex_class ());
3267 GList
*i
= edge_routing(e
);
3268 toporouter_vertex_t
*r
;
3271 r
= TOPOROUTER_VERTEX(i
->data
);
3272 if(epsilon_equals(vx(r
),x
) && epsilon_equals(vy(r
),y
)) {
3273 if(r
->flags
& VERTEX_FLAG_TEMP
) return r
;
3278 r
= TOPOROUTER_VERTEX( gts_vertex_new (vertex_class
, x
, y
, vz(edge_v1(e
))) );
3279 r
->flags
|= VERTEX_FLAG_TEMP
;
3282 if(TOPOROUTER_IS_CONSTRAINT(e
))
3283 TOPOROUTER_CONSTRAINT(e
)->routing
= g_list_insert_sorted_with_data(edge_routing(e
), r
, routing_edge_insert
, e
);
3285 e
->routing
= g_list_insert_sorted_with_data(edge_routing(e
), r
, routing_edge_insert
, e
);
3291 /* create vertex on edge e at radius r from v, closest to ref */
3292 toporouter_vertex_t
*
3293 new_temp_toporoutervertex_in_segment(toporouter_edge_t
*e
, toporouter_vertex_t
*v
, gdouble r
, toporouter_vertex_t
*ref
)
3295 gdouble m
= edge_gradient(e
);
3296 toporouter_spoint_t p
, np1
, np2
;
3297 // toporouter_vertex_t *b = TOPOROUTER_VERTEX((GTS_VERTEX(v) == edge_v1(e)) ? edge_v2(e) : edge_v1(e));
3298 toporouter_vertex_t
*rval
= NULL
;
3299 p
.x
= vx(v
); p
.y
= vy(v
);
3301 vertices_on_line(&p
, m
, r
, &np1
, &np2
);
3303 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)) )
3304 rval
= new_temp_toporoutervertex(np1
.x
, np1
.y
, e
);
3306 rval
= new_temp_toporoutervertex(np2
.x
, np2
.y
, e
);
3312 vertex_keepout_test(toporouter_t
*r
, toporouter_vertex_t
*v
)
3314 GList
*i
= r
->keepoutlayers
;
3316 gdouble keepout
= *((double *) i
->data
);
3317 if(vz(v
) == keepout
) return 1;
3324 closest_cluster_pair(toporouter_t
*r
, GList
*src_vertices
, GList
*dest_vertices
, toporouter_vertex_t
**a
, toporouter_vertex_t
**b
)
3326 GList
*i
= src_vertices
, *j
= dest_vertices
;
3329 *a
= NULL
; *b
= NULL
;
3333 toporouter_vertex_t
*v1
= TOPOROUTER_VERTEX(i
->data
);
3335 if(vertex_keepout_test(r
, v1
)) { i
= i
->next
; continue; }
3339 toporouter_vertex_t
*v2
= TOPOROUTER_VERTEX(j
->data
);
3340 if(vertex_keepout_test(r
, v2
) || vz(v2
) != vz(v1
)) { j
= j
->next
; continue; }
3343 *a
= v1
; *b
= v2
; min
= simple_h_cost(r
, *a
, *b
);
3345 gdouble tempd
= simple_h_cost(r
, v1
, v2
);
3346 if(r
->flags
& TOPOROUTER_FLAG_GOFAR
&& tempd
> min
) {
3347 *a
= v1
; *b
= v2
; min
= tempd
;
3350 *a
= v1
; *b
= v2
; min
= tempd
;
3360 // g_list_free(src_vertices);
3361 // g_list_free(dest_vertices);
3365 toporouter_vertex_t
*
3366 closest_dest_vertex(toporouter_t
*r
, toporouter_vertex_t
*v
, toporouter_route_t
*routedata
)
3368 GList
//*vertices = cluster_vertices(r, routedata->dest),
3369 *i
= routedata
->destvertices
;
3370 toporouter_vertex_t
*closest
= NULL
;
3371 gdouble closest_distance
= 0.;
3373 // if(routedata->flags & TOPOROUTER_FLAG_FLEX) i = r->destboxes;
3376 toporouter_vertex_t
*cv
= TOPOROUTER_VERTEX(i
->data
);
3378 if(vz(cv
) != vz(v
)) { i
= i
->next
; continue; }
3381 closest
= cv
; closest_distance
= simple_h_cost(r
, v
, closest
);
3383 gdouble tempd
= simple_h_cost(r
, v
, cv
);
3384 if(r
->flags
& TOPOROUTER_FLAG_GOFAR
&& tempd
> closest_distance
) {
3385 closest
= cv
; closest_distance
= tempd
;
3387 if(tempd
< closest_distance
) {
3388 closest
= cv
; closest_distance
= tempd
;
3394 // g_list_free(vertices);
3397 printf("CLOSEST = %f,%f,%f\n", vx(closest
), vy(closest
), vz(closest
));
3402 #define toporouter_edge_gradient(e) (cartesian_gradient(vx(edge_v1(e)), vy(edge_v1(e)), vx(edge_v2(e)), vy(edge_v2(e))))
3405 /* returns the capacity of the triangle cut through v */
3407 triangle_interior_capacity(GtsTriangle
*t
, toporouter_vertex_t
*v
)
3409 toporouter_edge_t
*e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3410 gdouble x
, y
, m1
, m2
, c2
, c1
, len
;
3414 m1
= toporouter_edge_gradient(e
);
3415 m2
= perpendicular_gradient(m1
);
3416 c2
= (isinf(m2
)) ? vx(v
) : vy(v
) - (m2
* vx(v
));
3417 c1
= (isinf(m1
)) ? vx(edge_v1(e
)) : vy(edge_v1(e
)) - (m1
* vx(edge_v1(e
)));
3424 x
= (c2
- c1
) / (m1
- m2
);
3426 y
= (isinf(m2
)) ? vy(edge_v1(e
)) : (m2
* x
) + c2
;
3428 len
= gts_point_distance2(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
)));
3431 printf("%f,%f len = %f v = %f,%f\n", x
, y
, len
, vx(v
), vy(v
));
3434 if(epsilon_equals(x
,vx(edge_v1(e
))) && epsilon_equals(y
,vy(edge_v1(e
)))) return INFINITY
;
3435 if(epsilon_equals(x
,vx(edge_v2(e
))) && epsilon_equals(y
,vy(edge_v2(e
)))) return INFINITY
;
3437 if(x
>= MIN(vx(edge_v1(e
)),vx(edge_v2(e
))) &&
3438 x
<= MAX(vx(edge_v1(e
)),vx(edge_v2(e
))) &&
3439 y
>= MIN(vy(edge_v1(e
)),vy(edge_v2(e
))) &&
3440 y
<= MAX(vy(edge_v1(e
)),vy(edge_v2(e
))))
3442 // 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 )
3443 return sqrt(pow(vx(v
) - x
, 2) + pow(vy(v
) - y
, 2));
3448 static inline toporouter_vertex_t
*
3449 segment_common_vertex(GtsSegment
*s1
, GtsSegment
*s2
)
3451 if(!s1
|| !s2
) return NULL
;
3452 if(s1
->v1
== s2
->v1
) return TOPOROUTER_VERTEX(s1
->v1
);
3453 if(s1
->v2
== s2
->v1
) return TOPOROUTER_VERTEX(s1
->v2
);
3454 if(s1
->v1
== s2
->v2
) return TOPOROUTER_VERTEX(s1
->v1
);
3455 if(s1
->v2
== s2
->v2
) return TOPOROUTER_VERTEX(s1
->v2
);
3459 static inline toporouter_vertex_t
*
3460 route_vertices_common_vertex(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
)
3462 return segment_common_vertex(GTS_SEGMENT(v1
->routingedge
), GTS_SEGMENT(v2
->routingedge
));
3467 edges_third_edge(GtsSegment
*s1
, GtsSegment
*s2
, toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
3469 if(!s1
|| !s2
) return 0;
3470 if(s1
->v1
== s2
->v1
) {
3471 *v1
= TOPOROUTER_VERTEX(s1
->v2
);
3472 *v2
= TOPOROUTER_VERTEX(s2
->v2
);
3475 if(s1
->v2
== s2
->v1
) {
3476 *v1
= TOPOROUTER_VERTEX(s1
->v1
);
3477 *v2
= TOPOROUTER_VERTEX(s2
->v2
);
3480 if(s1
->v1
== s2
->v2
) {
3481 *v1
= TOPOROUTER_VERTEX(s1
->v2
);
3482 *v2
= TOPOROUTER_VERTEX(s2
->v1
);
3485 if(s1
->v2
== s2
->v2
) {
3486 *v1
= TOPOROUTER_VERTEX(s1
->v1
);
3487 *v2
= TOPOROUTER_VERTEX(s2
->v1
);
3493 /* returns the flow from e1 to e2, and the flow from the vertex oppisate e1 to
3494 * e1 and the vertex oppisate e2 to e2 */
3496 flow_from_edge_to_edge(GtsTriangle
*t
, toporouter_edge_t
*e1
, toporouter_edge_t
*e2
,
3497 toporouter_vertex_t
*common_v
, toporouter_vertex_t
*curpoint
)
3500 toporouter_vertex_t
*pv
= common_v
, *v
;
3501 toporouter_edge_t
*op_edge
;
3503 GList
*i
= edge_routing(e1
);
3505 v
= TOPOROUTER_VERTEX(i
->data
);
3508 r
+= min_spacing(v
, pv
);
3510 i
= i
->next
; continue;
3512 // if(!(v->flags & VERTEX_FLAG_TEMP)) {
3513 if((v
->flags
& VERTEX_FLAG_ROUTE
)) {
3515 if(v
->parent
->routingedge
== e2
) {
3516 r
+= min_spacing(v
, pv
);
3518 i
= i
->next
; continue;
3522 if(v
->child
->routingedge
== e2
) {
3523 r
+= min_spacing(v
, pv
);
3525 i
= i
->next
; continue;
3531 op_edge
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(common_v
)));
3537 v
= segment_common_vertex(GTS_SEGMENT(e2
), GTS_SEGMENT(op_edge
));
3540 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e1)));
3541 if(v
->flags
& VERTEX_FLAG_ROUTE
&& v
->parent
&& v
->parent
->routingedge
) {
3542 if(v
->parent
->routingedge
== e1
)
3543 r
+= min_spacing(v
, pv
);
3546 v
= segment_common_vertex(GTS_SEGMENT(e1
), GTS_SEGMENT(op_edge
));
3549 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e2)));
3550 if(v
->flags
& VERTEX_FLAG_ROUTE
&& v
->parent
&& v
->parent
->routingedge
) {
3551 if(v
->parent
->routingedge
== e1
)
3552 r
+= min_spacing(v
, pv
);
3555 if(TOPOROUTER_IS_CONSTRAINT(op_edge
)) {
3556 toporouter_bbox_t
*box
= vertex_bbox(TOPOROUTER_VERTEX(edge_v1(op_edge
)));
3557 r
+= vertex_net_thickness(v
) / 2.;
3559 r
+= MAX(vertex_net_keepaway(v
), cluster_keepaway(box
->cluster
));
3560 r
+= cluster_thickness(box
->cluster
) / 2.;
3562 r
+= vertex_net_keepaway(v
);
3573 check_triangle_interior_capacity(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_vertex_t
*curpoint
,
3574 toporouter_edge_t
*op_edge
, toporouter_edge_t
*adj_edge1
, toporouter_edge_t
*adj_edge2
)
3576 gdouble ic
= triangle_interior_capacity(t
, v
);
3577 gdouble flow
= flow_from_edge_to_edge(t
, adj_edge1
, adj_edge2
, v
, curpoint
);
3579 if(TOPOROUTER_IS_CONSTRAINT(adj_edge1
) || TOPOROUTER_IS_CONSTRAINT(adj_edge2
)) return 1;
3584 printf("fail interior capacity flow = %f ic = %f\n", flow
, ic
);
3592 toporouter_vertex_t
*
3593 edge_routing_next_not_temp(toporouter_edge_t
*e
, GList
*list
)
3595 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3597 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(list
->data
);
3598 if(!(v
->flags
& VERTEX_FLAG_TEMP
))
3607 toporouter_vertex_t
*
3608 edge_routing_prev_not_temp(toporouter_edge_t
*e
, GList
*list
)
3610 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3612 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(list
->data
);
3613 if(!(v
->flags
& VERTEX_FLAG_TEMP
))
3623 edge_adjacent_vertices(toporouter_edge_t
*e
, toporouter_vertex_t
*v
, toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
3625 GList
*r
= g_list_find(edge_routing(e
), v
);
3627 if(v
== tedge_v1(e
)) {
3629 *v2
= edge_routing_next_not_temp(e
, edge_routing(e
));
3630 }else if(v
== tedge_v2(e
)) {
3631 *v1
= edge_routing_prev_not_temp(e
, g_list_last(edge_routing(e
)));
3634 // r = g_list_find(r, v);
3635 *v1
= edge_routing_prev_not_temp(e
, r
);
3636 *v2
= edge_routing_next_not_temp(e
, r
);
3644 candidate_vertices(toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*dest
, toporouter_edge_t
*e
)
3646 gdouble totald
, v1ms
, v2ms
, flow
, capacity
, ms
;
3653 g_assert(!(v1
->flags
& VERTEX_FLAG_TEMP
));
3654 g_assert(!(v2
->flags
& VERTEX_FLAG_TEMP
));
3656 printf("starting candidate vertices\n");
3657 printf("v1 = %f,%f v2 = %f,%f dest = %f,%f\n", vx(v1
), vy(v1
), vx(v2
), vy(v2
), vx(dest
), vy(dest
));
3659 totald
= gts_point_distance(GTS_POINT(v1
), GTS_POINT(v2
));
3660 v1ms
= min_spacing(v1
, dest
);
3661 v2ms
= min_spacing(v2
, dest
);
3662 ms
= min_spacing(dest
, dest
);
3663 flow
= TOPOROUTER_IS_CONSTRAINT(e
) ? 0. : edge_flow(e
, v1
, v2
, dest
);
3664 capacity
= edge_capacity(e
);
3667 g_assert(totald
> 0);
3669 printf("v1ms = %f v2ms = %f totald = %f ms = %f capacity = %f flow = %f\n", v1ms
, v2ms
, totald
, ms
, capacity
, flow
);
3672 if(flow
>= capacity
) return NULL
;
3675 if(v1ms
+ v2ms
+ ms
>= totald
) {
3676 vs
= g_list_prepend(vs
, new_temp_toporoutervertex((vx(v1
)+vx(v2
)) / 2., (vy(v1
)+vy(v2
)) / 2., e
));
3678 gdouble x0
, y0
, x1
, y1
, d
;
3680 vertex_move_towards_vertex_values(GTS_VERTEX(v1
), GTS_VERTEX(v2
), v1ms
, &x0
, &y0
);
3682 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x0
, y0
, e
));
3684 vertex_move_towards_vertex_values(GTS_VERTEX(v2
), GTS_VERTEX(v1
), v2ms
, &x1
, &y1
);
3686 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x1
, y1
, e
));
3688 d
= sqrt(pow(x0
-x1
,2) + pow(y0
-y1
,2));
3691 // guint nint = d / ms;
3692 // gdouble dif = d / (nint + 1);
3693 gdouble dif
= d
/ 2;
3695 // for(guint j=0;j<nint;j++) {
3698 // coord_move_towards_coord_values(x0, y0, x1, y1, dif * j, &x, &y);
3699 coord_move_towards_coord_values(x0
, y0
, x1
, y1
, dif
, &x
, &y
);
3701 vs
= g_list_prepend(vs
, new_temp_toporoutervertex(x
, y
, e
));
3709 printf("candidate vertices returning %d\n", g_list_length(vs
));
3715 edge_routing_first_not_temp(toporouter_edge_t
*e
)
3717 GList
*i
= edge_routing(e
);
3718 toporouter_vertex_t
*v
;
3721 v
= TOPOROUTER_VERTEX(i
->data
);
3722 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) return i
;
3731 edge_routing_last_not_temp(toporouter_edge_t
*e
)
3733 GList
*i
= edge_routing(e
), *last
= NULL
;
3734 toporouter_vertex_t
*v
;
3737 v
= TOPOROUTER_VERTEX(i
->data
);
3738 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) last
= i
;
3747 delete_vertex(toporouter_vertex_t
*v
)
3750 if(v
->flags
& VERTEX_FLAG_TEMP
) {
3751 if(v
->routingedge
) {
3752 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
3753 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
);
3755 v
->routingedge
->routing
= g_list_remove(v
->routingedge
->routing
, v
);
3758 gts_object_destroy ( GTS_OBJECT(v
) );
3762 #define edge_is_blocked(e) (TOPOROUTER_IS_EDGE(e) ? (e->flags & EDGE_FLAG_DIRECTCONNECTION) : 0)
3765 triangle_candidate_points_from_vertex(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_vertex_t
*dest
, toporouter_route_t
*routedata
)
3767 toporouter_edge_t
*op_e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
3768 toporouter_vertex_t
*vv1
, *vv2
, *constraintv
= NULL
;
3769 toporouter_edge_t
*e1
, *e2
;
3774 printf("\tTRIANGLE CAND POINT FROM VERTEX\n");
3779 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), edge_v1(op_e
)));
3780 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), edge_v2(op_e
)));
3783 if(TOPOROUTER_IS_CONSTRAINT(op_e
)) {
3784 if(TOPOROUTER_CONSTRAINT(op_e
)->box
->type
== BOARD
) {
3786 printf("BOARD constraint\n");
3790 if(constraint_netlist(TOPOROUTER_CONSTRAINT(op_e
)) != vertex_netlist(dest
)) { // || TOPOROUTER_CONSTRAINT(op_e)->routing) {
3792 printf("op_e routing:\n");
3798 printf("RETURNING CONSTRAINT POING\n");
3800 constraintv
= new_temp_toporoutervertex_in_segment(op_e
, TOPOROUTER_VERTEX(edge_v1(op_e
)),
3801 gts_point_distance(GTS_POINT(edge_v1(op_e
)), GTS_POINT(edge_v2(op_e
))) / 2., TOPOROUTER_VERTEX(edge_v2(op_e
)));
3802 // return g_list_prepend(NULL, vv1);
3807 if(edge_is_blocked(op_e
)) {
3808 goto triangle_candidate_points_from_vertex_exit
;
3810 // v1 = tedge_v1(op_e);
3811 // v2 = tedge_v2(op_e);
3813 if(v
== tedge_v1(e1
)) {
3814 i
= edge_routing_first_not_temp(e1
);
3816 i
= edge_routing_last_not_temp(e1
);
3820 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3822 if(temp
->parent
== tedge_v2(op_e
) || temp
->child
== tedge_v2(op_e
)) {
3824 printf("temp -> op_e->v2\n");
3826 goto triangle_candidate_points_from_vertex_exit
;
3828 if(temp
->parent
->routingedge
== op_e
) {
3831 printf("vv1->parent\n");
3834 }else if(temp
->child
->routingedge
== op_e
) {
3837 printf("vv1->child\n");
3843 printf("temp -> e2?\n");
3844 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
)) );
3845 if(temp
->parent
->routingedge
)
3846 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3847 vx(edge_v1(temp
->parent
->routingedge
)), vy(edge_v1(temp
->parent
->routingedge
)),
3848 vx(edge_v2(temp
->parent
->routingedge
)), vy(edge_v2(temp
->parent
->routingedge
))
3851 printf("temp->parent->routingedge = NULL\n");
3853 if(temp
->child
->routingedge
)
3854 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3855 vx(edge_v1(temp
->child
->routingedge
)), vy(edge_v1(temp
->child
->routingedge
)),
3856 vx(edge_v2(temp
->child
->routingedge
)), vy(edge_v2(temp
->child
->routingedge
))
3859 printf("temp->child->routingedge = NULL\n");
3861 goto triangle_candidate_points_from_vertex_exit
;
3865 vv1
= tedge_v1(op_e
);
3867 printf("nothing on e1\n");
3871 if(v
== tedge_v1(e2
)) {
3872 i
= edge_routing_first_not_temp(e2
);
3874 i
= edge_routing_last_not_temp(e2
);
3878 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3880 if(temp
->parent
== tedge_v1(op_e
) || temp
->child
== tedge_v1(op_e
)) {
3882 printf("temp -> op_e->v2\n");
3884 goto triangle_candidate_points_from_vertex_exit
;
3887 if(temp
->parent
->routingedge
== op_e
) {
3890 printf("vv2->parent\n");
3892 }else if(temp
->child
->routingedge
== op_e
) {
3895 printf("vv2->child\n");
3901 printf("temp -> e1?\n");
3902 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
)) );
3903 if(temp
->parent
->routingedge
)
3904 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3905 vx(edge_v1(temp
->parent
->routingedge
)), vy(edge_v1(temp
->parent
->routingedge
)),
3906 vx(edge_v2(temp
->parent
->routingedge
)), vy(edge_v2(temp
->parent
->routingedge
))
3909 printf("temp->parent->routingedge = NULL\n");
3911 if(temp
->child
->routingedge
)
3912 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3913 vx(edge_v1(temp
->child
->routingedge
)), vy(edge_v1(temp
->child
->routingedge
)),
3914 vx(edge_v2(temp
->child
->routingedge
)), vy(edge_v2(temp
->child
->routingedge
))
3917 printf("temp->child->routingedge = NULL\n");
3919 goto triangle_candidate_points_from_vertex_exit
;
3923 vv2
= tedge_v2(op_e
);
3925 printf("nothing on e2\n");
3930 printf("size of e1 routing = %d e2 routing = %d op_e routing = %d\n",
3931 g_list_length(edge_routing(e1
)), g_list_length(edge_routing(e2
)), g_list_length(edge_routing(op_e
)));
3936 print_vertex(constraintv
);
3937 printf("constraintv %f,%f returning\n", vx(constraintv
), vy(constraintv
));
3939 return g_list_prepend(NULL
, constraintv
);
3942 i
= edge_routing(op_e
);
3944 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
3946 if(temp
->parent
== v
|| temp
->child
== v
) {
3947 rval
= g_list_concat(rval
, candidate_vertices(vv1
, temp
, dest
, op_e
));
3954 rval
= g_list_concat(rval
, candidate_vertices(vv1
, vv2
, dest
, op_e
));
3960 triangle_candidate_points_from_vertex_exit
:
3961 if(constraintv
) //delete_vertex(constraintv);
3962 g_hash_table_insert(routedata
->alltemppoints
, constraintv
, constraintv
);
3970 routedata_insert_temppoints(toporouter_route_t
*data
, GList
*temppoints
) {
3971 GList
*j
= temppoints
;
3973 g_hash_table_insert(data
->alltemppoints
, j
->data
, j
->data
);
3980 constraint_route_test(toporouter_constraint_t
*c
, toporouter_route_t
*routedata
)
3982 if(c
->box
->cluster
&& c
->box
->cluster
->netlist
== routedata
->src
->netlist
) {
3983 if(c
->box
->cluster
->c
== routedata
->dest
->c
|| c
->box
->cluster
->c
== routedata
->src
->c
) return 1;
3989 all_candidates_on_edge(toporouter_edge_t
*e
, toporouter_route_t
*routedata
)
3992 if(edge_is_blocked(e
)) return NULL
;
3994 if(!TOPOROUTER_IS_CONSTRAINT(e
)) {
3995 GList
*i
= edge_routing(e
);
3996 toporouter_vertex_t
*pv
= tedge_v1(e
);
3999 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4000 if(!(v
->flags
& VERTEX_FLAG_TEMP
)) {
4001 rval
= g_list_concat(rval
, candidate_vertices(pv
, v
, TOPOROUTER_VERTEX(routedata
->destvertices
->data
), e
));
4007 rval
= g_list_concat(rval
, candidate_vertices(pv
, tedge_v2(e
), TOPOROUTER_VERTEX(routedata
->destvertices
->data
), e
));
4008 }else if(TOPOROUTER_CONSTRAINT(e
)->box
->type
== BOARD
) {
4010 }else if(constraint_route_test(TOPOROUTER_CONSTRAINT(e
), routedata
)) {
4011 toporouter_vertex_t
*consv
= new_temp_toporoutervertex_in_segment(e
, tedge_v1(e
), tvdistance(tedge_v1(e
), tedge_v2(e
)) / 2., tedge_v2(e
));
4012 rval
= g_list_prepend(rval
, consv
);
4013 // g_hash_table_insert(routedata->alltemppoints, consv, consv);
4020 triangle_all_candidate_points_from_vertex(GtsTriangle
*t
, toporouter_vertex_t
*v
, toporouter_route_t
*routedata
)
4022 toporouter_edge_t
*op_e
= TOPOROUTER_EDGE(gts_triangle_edge_opposite(t
, GTS_VERTEX(v
)));
4023 return all_candidates_on_edge(op_e
, routedata
);
4027 triangle_all_candidate_points_from_edge(toporouter_t
*r
, GtsTriangle
*t
, toporouter_edge_t
*e
, toporouter_route_t
*routedata
,
4028 toporouter_vertex_t
**dest
, toporouter_vertex_t
*curpoint
)
4030 toporouter_vertex_t
*op_v
;
4031 toporouter_edge_t
*e1
, *e2
;
4032 GList
*i
, *rval
= NULL
, *rval2
= NULL
;
4033 toporouter_vertex_t
*boxpoint
= NULL
;
4034 guint e1intcap
, e2intcap
;
4036 op_v
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t
, GTS_EDGE(e
)));
4039 if(vertex_bbox(op_v
)) boxpoint
= TOPOROUTER_VERTEX(vertex_bbox(op_v
)->point
);
4041 if(g_list_find(routedata
->destvertices
, op_v
)) {
4042 rval
= g_list_prepend(rval
, op_v
);
4045 }else if(g_list_find(routedata
->destvertices
, boxpoint
)) {
4047 }else if(g_list_find(routedata
->srcvertices
, op_v
)) {
4048 rval
= g_list_prepend(rval
, op_v
);
4051 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v1(e
)));
4052 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v2(e
)));
4054 rval
= g_list_concat(rval
, all_candidates_on_edge(e1
, routedata
));
4055 rval
= g_list_concat(rval
, all_candidates_on_edge(e2
, routedata
));
4057 e1intcap
= check_triangle_interior_capacity(t
, tedge_v1(e
), curpoint
, e2
, e
, e1
);
4058 e2intcap
= check_triangle_interior_capacity(t
, tedge_v2(e
), curpoint
, e1
, e
, e2
);
4062 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4065 rval2
= g_list_prepend(rval2
, v
);
4066 else if(v
->routingedge
== e1
&& !(!TOPOROUTER_IS_CONSTRAINT(e1
) && !e1intcap
))
4067 rval2
= g_list_prepend(rval2
, v
);
4068 else if(v
->routingedge
== e2
&& !(!TOPOROUTER_IS_CONSTRAINT(e2
) && !e2intcap
))
4069 rval2
= g_list_prepend(rval2
, v
);
4079 triangle_candidate_points_from_edge(toporouter_t
*r
, GtsTriangle
*t
, toporouter_edge_t
*e
, toporouter_vertex_t
*v
, toporouter_vertex_t
**dest
,
4080 toporouter_route_t
*routedata
)
4082 toporouter_vertex_t
*v1
, *v2
, *op_v
, *vv
= NULL
, *e1constraintv
= NULL
, *e2constraintv
= NULL
;
4083 toporouter_edge_t
*e1
, *e2
;
4084 GList
*e1cands
= NULL
, *e2cands
= NULL
, *rval
= NULL
;
4085 guint noe1
= 0, noe2
= 0;
4087 op_v
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t
, GTS_EDGE(e
)));
4089 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v1(e
)));
4090 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v
), edge_v2(e
)));
4094 // v1 is prev dir, v2 is next dir
4095 edge_adjacent_vertices(e
, v
, &v1
, &v2
);
4097 if(TOPOROUTER_IS_CONSTRAINT(e1
)) {
4098 GList
*i
= edge_routing(e1
);
4100 if(TOPOROUTER_CONSTRAINT(e1
)->box
->type
== BOARD
) {
4102 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e1
), routedata
)) {
4105 printf("noe1 netlist\n");
4109 if(v1
== tedge_v1(e
) ||
4110 (v1
->parent
->routingedge
&& v1
->parent
->routingedge
== e1
) ||
4111 (v1
->child
->routingedge
&& v1
->child
->routingedge
== e1
)) {
4112 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
));
4116 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
4118 if((temp
->child
== tedge_v2(e
) || temp
->parent
== tedge_v2(e
)) && !(temp
->flags
& VERTEX_FLAG_TEMP
)) noe2
= 1;
4123 goto triangle_candidate_points_e2
;
4126 if(edge_is_blocked(e1
)) {
4128 goto triangle_candidate_points_e2
;
4131 if(v1
== tedge_v1(e
)) {
4133 toporouter_vertex_t
*vv1
, *vv2
;
4134 edge_adjacent_vertices(e1
, v1
, &vv1
, &vv2
);
4137 printf("v1 == e->v1\n");
4141 // candidates from v1 until vv1
4144 // candidates from v1 until vv2
4148 if(!e1constraintv
) e1cands
= candidate_vertices(v1
, vv
, *dest
, e1
);
4151 if(vv
->parent
== tedge_v2(e
) || vv
->child
== tedge_v2(e
)) {
4159 }else if(v1
->parent
!= op_v
&& v1
->child
!= op_v
) {
4160 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4163 printf("v1 != e->v1\n");
4166 if(v1
->parent
->routingedge
== e1
) {
4169 printf("v1 parent = e1\n");
4171 if(op_v
== tedge_v1(e1
)) {
4172 // candidates from v1->parent until prev vertex
4173 vv2
= edge_routing_prev_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->parent
)->prev
);
4175 // candidates from v1->parent until next vertex
4176 vv2
= edge_routing_next_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->parent
)->next
);
4179 }else if(v1
->child
->routingedge
== e1
) {
4182 printf("v1 child = e1\n");
4184 if(op_v
== tedge_v1(e1
)) {
4185 // candidates from v1->child until prev vertex
4186 vv2
= edge_routing_prev_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->child
)->prev
);
4188 // candidates from v1->child until next vertex
4189 vv2
= edge_routing_next_not_temp(e1
, g_list_find(edge_routing(e1
), v1
->child
)->next
);
4196 goto triangle_candidate_points_e2
;
4200 if(vv2
->parent
== tedge_v2(e
) || vv2
->child
== tedge_v2(e
)) {
4207 if(!e1constraintv
) e1cands
= candidate_vertices(vv1
, vv2
, *dest
, e1
);
4213 if(vv
&& vv
== op_v
) {
4214 toporouter_vertex_t
*boxpoint
= NULL
;
4216 if(vertex_bbox(op_v
)) boxpoint
= TOPOROUTER_VERTEX(vertex_bbox(op_v
)->point
);
4218 if(g_list_find(routedata
->destvertices
, op_v
)) {
4219 rval
= g_list_prepend(rval
, op_v
);
4221 }else if(g_list_find(routedata
->destvertices
, boxpoint
)) {
4223 }else if(g_list_find(routedata
->srcvertices
, op_v
)) {
4224 rval
= g_list_prepend(rval
, op_v
);
4228 triangle_candidate_points_e2
:
4231 // printf("noe2\n");
4232 goto triangle_candidate_points_finish
;
4235 if(TOPOROUTER_IS_CONSTRAINT(e2
)) {
4236 GList
*i
= edge_routing(e2
);
4238 if(TOPOROUTER_CONSTRAINT(e2
)->box
->type
== BOARD
) {
4240 // goto triangle_candidate_points_finish;
4241 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e2
), routedata
)) {
4243 printf("noe2 netlist\n");
4246 // goto triangle_candidate_points_finish;
4247 }else if(v2
== tedge_v2(e
) ||
4248 (v2
->parent
->routingedge
&& v2
->parent
->routingedge
== e2
) ||
4249 (v2
->child
->routingedge
&& v2
->child
->routingedge
== e2
)) {
4251 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
));
4256 toporouter_vertex_t
*temp
= TOPOROUTER_VERTEX(i
->data
);
4258 if((temp
->child
== tedge_v1(e
) || temp
->parent
== tedge_v1(e
)) && !(temp
->flags
& VERTEX_FLAG_TEMP
))
4266 goto triangle_candidate_points_finish
;
4269 if(edge_is_blocked(e2
)) {
4271 goto triangle_candidate_points_finish
;
4274 if(v2
== tedge_v2(e
)) {
4276 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4277 edge_adjacent_vertices(e2
, v2
, &vv1
, &vv2
);
4280 printf("v2 == e->v2\n");
4284 // candidates from v2 until vv1
4287 // candidates from v2 until vv2
4291 if(!e2constraintv
) e2cands
= candidate_vertices(v2
, vv
, *dest
, e2
);
4294 if(vv
->parent
== tedge_v1(e
) || vv
->child
== tedge_v1(e
)) {
4302 }else if(v2
->parent
!= op_v
&& v2
->child
!= op_v
) {
4303 toporouter_vertex_t
*vv1
= NULL
, *vv2
= NULL
;
4306 printf("v2 == e->v2\n");
4309 if(v2
->parent
->routingedge
== e2
) {
4311 if(op_v
== tedge_v1(e2
)) {
4312 // candidates from v2->parent until prev vertex
4313 vv2
= edge_routing_prev_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->prev
);
4315 // candidates from v2->parent until next vertex
4316 vv2
= edge_routing_next_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->next
);
4319 }else if(v2
->child
->routingedge
== e2
) {
4321 if(op_v
== tedge_v1(e2
)) {
4322 // candidates from v2->child until prev vertex
4323 vv2
= edge_routing_prev_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->prev
);
4325 // candidates from v2->child until next vertex
4326 vv2
= edge_routing_next_not_temp(e2
, g_list_find(edge_routing(e2
), vv1
)->next
);
4330 goto triangle_candidate_points_finish
;
4334 if(vv2
->parent
== tedge_v1(e
) || vv2
->child
== tedge_v1(e
)) {
4341 if(!e2constraintv
) e2cands
= candidate_vertices(vv1
, vv2
, *dest
, e2
);
4345 triangle_candidate_points_finish
:
4347 v1
= segment_common_vertex(GTS_SEGMENT(e
), GTS_SEGMENT(e1
));
4348 v2
= segment_common_vertex(GTS_SEGMENT(e
), GTS_SEGMENT(e2
));
4350 if(noe1
|| !check_triangle_interior_capacity(t
, v1
, v
, e2
, e
, e1
)) {
4352 printf("freeing e1cands\n");
4354 routedata_insert_temppoints(routedata
, e1cands
);
4355 g_list_free(e1cands
);
4359 if(noe2
|| !check_triangle_interior_capacity(t
, v2
, v
, e1
, e
, e2
)) {
4361 printf("freeing e2cands\n");
4363 routedata_insert_temppoints(routedata
, e2cands
);
4364 g_list_free(e2cands
);
4368 if(!noe1
&& e1constraintv
) {
4369 e1cands
= g_list_prepend(e1cands
, e1constraintv
);
4370 }else if(e1constraintv
) {
4371 g_hash_table_insert(routedata
->alltemppoints
, e1constraintv
, e1constraintv
);
4372 // delete_vertex(e1constraintv);
4375 if(!noe2
&& e2constraintv
) {
4376 e2cands
= g_list_prepend(e2cands
, e2constraintv
);
4377 }else if(e2constraintv
) {
4378 g_hash_table_insert(routedata
->alltemppoints
, e2constraintv
, e2constraintv
);
4379 // delete_vertex(e2constraintv);
4382 if(!noe1
&& !noe2
) return g_list_concat(rval
, g_list_concat(e1cands
, e2cands
));
4384 return g_list_concat(e1cands
, e2cands
);
4388 compute_candidate_points(toporouter_t
*tr
, toporouter_layer_t
*l
, toporouter_vertex_t
*curpoint
, toporouter_route_t
*data
,
4389 toporouter_vertex_t
**closestdest
)
4391 GList
*r
= NULL
, *j
;
4392 toporouter_edge_t
*edge
= curpoint
->routingedge
, *tempedge
;
4394 if(vertex_keepout_test(tr
, curpoint
)) goto compute_candidate_points_finish
;
4396 /* direct connection */
4397 // if(curpoint == TOPOROUTER_VERTEX(data->src->point))
4398 if((tempedge
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(curpoint
), GTS_VERTEX(*closestdest
))))) {
4400 if(TOPOROUTER_IS_CONSTRAINT(tempedge
)) {
4401 goto compute_candidate_points_finish
;
4403 if(!tempedge
->routing
) {
4404 r
= g_list_prepend(NULL
, *closestdest
);
4405 tempedge
->flags
|= EDGE_FLAG_DIRECTCONNECTION
;
4406 goto compute_candidate_points_finish
;
4409 printf("Direct connection, but has routing\n");
4414 /* if we get to here, there is routing blocking the direct connection,
4415 * continue as per normal */
4418 /* a real point origin */
4419 if(!(curpoint
->flags
& VERTEX_FLAG_TEMP
)) {
4420 GSList
*triangles
, *i
;
4421 i
= triangles
= gts_vertex_triangles(GTS_VERTEX(curpoint
), NULL
);
4423 printf("triangle count = %d\n", g_slist_length(triangles
));
4426 GtsTriangle
*t
= GTS_TRIANGLE(i
->data
);
4429 if(tr
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) temppoints
= triangle_all_candidate_points_from_vertex(t
, curpoint
, data
);
4430 else temppoints
= triangle_candidate_points_from_vertex(t
, curpoint
, *closestdest
, data
);
4433 printf("\treturned %d points\n", g_list_length(temppoints
));
4435 routedata_insert_temppoints(data
, temppoints
);
4437 r
= g_list_concat(r
, temppoints
);
4440 g_slist_free(triangles
);
4441 }else /* a temp point */ {
4442 int prevwind
= vertex_wind(GTS_SEGMENT(edge
)->v1
, GTS_SEGMENT(edge
)->v2
, GTS_VERTEX(curpoint
->parent
));
4443 // printf("tempoint\n");
4445 GSList
*i
= GTS_EDGE(edge
)->triangles
;
4448 GtsVertex
*oppv
= gts_triangle_vertex_opposite(GTS_TRIANGLE(i
->data
), GTS_EDGE(edge
));
4449 if(prevwind
!= vertex_wind(GTS_SEGMENT(edge
)->v1
, GTS_SEGMENT(edge
)->v2
, oppv
)) {
4452 if(tr
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) temppoints
= triangle_all_candidate_points_from_edge(tr
, GTS_TRIANGLE(i
->data
), edge
,
4453 data
, closestdest
, curpoint
);
4454 else temppoints
= triangle_candidate_points_from_edge(tr
, GTS_TRIANGLE(i
->data
), edge
, curpoint
, closestdest
, data
);
4458 toporouter_vertex_t
*tempj
= TOPOROUTER_VERTEX(j
->data
);
4459 if(tempj
->flags
& VERTEX_FLAG_TEMP
)
4460 g_hash_table_insert(data
->alltemppoints
, j
->data
, j
->data
);
4463 printf("got cand not a temp\n");
4467 r
= g_list_concat(r
, temppoints
);
4475 compute_candidate_points_finish
:
4477 if(vertex_bbox(curpoint
) && vertex_bbox(curpoint
)->cluster
) {
4478 if(vertex_bbox(curpoint
)->cluster
->c
== data
->src
->c
) {
4479 r
= g_list_concat(r
, g_list_copy(data
->srcvertices
));
4487 temp_point_clean(gpointer key
, gpointer value
, gpointer user_data
)
4489 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(value
);
4490 if(tv
->flags
& VERTEX_FLAG_TEMP
) {
4491 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
4492 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
4494 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
4495 gts_object_destroy ( GTS_OBJECT(tv
) );
4501 clean_routing_edges(toporouter_t
*r
, toporouter_route_t
*data
)
4503 g_hash_table_foreach_remove(data
->alltemppoints
, temp_point_clean
, NULL
);
4504 g_hash_table_destroy(data
->alltemppoints
);
4505 data
->alltemppoints
= NULL
;
4509 path_score(toporouter_t
*r
, GList
*path
)
4512 toporouter_vertex_t
*pv
= NULL
;
4513 toporouter_vertex_t
*v0
= NULL
;
4515 if(!path
) return INFINITY
;
4517 v0
= TOPOROUTER_VERTEX(path
->data
);
4520 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(path
->data
);
4523 score
+= gts_point_distance(GTS_POINT(pv
), GTS_POINT(v
));
4524 if(pv
!= v0
&& vz(pv
) != vz(v
))
4526 score
+= r
->viacost
;
4538 print_vertices(GList
*vertices
)
4541 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(vertices
->data
);
4543 print_bbox(vertex_bbox(v
));
4544 if(vertex_bbox(v
)) {
4545 printf("has bbox\n");
4546 if(vertex_bbox(v
)->cluster
)
4547 printf("has cluster\n");
4549 printf("no cluster\n");
4550 }else printf("no bbox\n");
4551 vertices
= vertices
->next
;
4556 space_edge(gpointer item
, gpointer data
)
4558 toporouter_edge_t
*e
= TOPOROUTER_EDGE(item
);
4562 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
4564 if(!edge_routing(e
) || !g_list_length(edge_routing(e
))) return 0;
4566 forces
= malloc(sizeof(double) * g_list_length(edge_routing(e
)));
4568 for(guint j
=0;j
<100;j
++) {
4570 guint equilibrium
= 1;
4572 i
= edge_routing(e
);
4574 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4578 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->prev->data), v);
4579 ms
= min_spacing(TOPOROUTER_VERTEX(i
->prev
->data
), v
);
4580 d
= gts_point_distance(GTS_POINT(i
->prev
->data
), GTS_POINT(v
));
4582 // ms = min_vertex_net_spacing(v, tedge_v1(e));
4583 ms
= min_spacing(v
, tedge_v1(e
));
4584 d
= gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(v
));
4587 if(d
< ms
) forces
[k
] = ms
- d
;
4588 else forces
[k
] = 0.;
4591 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->next->data), v);
4592 ms
= min_spacing(TOPOROUTER_VERTEX(i
->next
->data
), v
);
4593 d
= gts_point_distance(GTS_POINT(i
->next
->data
), GTS_POINT(v
));
4595 // ms = min_vertex_net_spacing(v, tedge_v2(e));
4596 ms
= min_spacing(v
, tedge_v2(e
));
4597 d
= gts_point_distance(GTS_POINT(edge_v2(e
)), GTS_POINT(v
));
4600 if(d
< ms
) forces
[k
] += d
- ms
;
4606 i
= edge_routing(e
);
4608 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
4609 if(forces
[k
] > EPSILON
|| forces
[k
] < -EPSILON
) equilibrium
= 0;
4610 vertex_move_towards_vertex_values(GTS_VERTEX(v
), edge_v2(e
), forces
[k
] * 0.1, &(GTS_POINT(v
)->x
), &(GTS_POINT(v
)->y
));
4615 // printf("reached equilibriium at %d\n", j);
4626 swap_vertices(toporouter_vertex_t
**v1
, toporouter_vertex_t
**v2
)
4628 toporouter_vertex_t
*tempv
= *v1
;
4634 split_edge_routing(toporouter_vertex_t
*v
, GList
**l1
, GList
**l2
)
4639 g_assert(v
->routingedge
);
4641 base
= g_list_find(vrouting(v
), v
);
4643 *l1
= g_list_prepend(*l1
, tedge_v1(v
->routingedge
));
4644 *l2
= g_list_prepend(*l2
, tedge_v2(v
->routingedge
));
4650 if(!(TOPOROUTER_VERTEX(i
->data
)->flags
& VERTEX_FLAG_TEMP
)) *l2
= g_list_prepend(*l2
, i
->data
);
4656 if(!(TOPOROUTER_VERTEX(i
->data
)->flags
& VERTEX_FLAG_TEMP
)) *l1
= g_list_prepend(*l1
, i
->data
);
4662 vertices_routing_conflicts(toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
)
4664 toporouter_edge_t
*e
;
4665 GList
*rval
= NULL
, *l1
= NULL
, *l2
= NULL
, *i
;
4667 if(vz(v
) != vz(pv
)) return NULL
;
4670 if(!v
->routingedge
&& !pv
->routingedge
) {
4671 e
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v
), GTS_VERTEX(pv
)));
4673 i
= edge_routing(e
);
4675 rval
= g_list_prepend(rval
, TOPOROUTER_VERTEX(i
->data
)->route
);
4681 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
) && TOPOROUTER_IS_CONSTRAINT(pv
->routingedge
))
4684 if(TOPOROUTER_IS_CONSTRAINT(pv
->routingedge
)) swap_vertices(&pv
, &v
);
4686 if(!v
->routingedge
) swap_vertices(&pv
, &v
);
4690 split_edge_routing(v
, &l1
, &l2
);
4694 if(!pv
->routingedge
) {
4695 toporouter_edge_t
*e1
, *e2
;
4696 e1
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv
), edge_v1(e
)));
4697 e2
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv
), edge_v2(e
)));
4699 l1
= g_list_concat(l1
, g_list_copy(edge_routing(e1
)));
4700 l2
= g_list_concat(l2
, g_list_copy(edge_routing(e2
)));
4703 GList
*pvlist1
= NULL
, *pvlist2
= NULL
;
4704 toporouter_vertex_t
*commonv
= route_vertices_common_vertex(v
, pv
);
4708 split_edge_routing(pv
, &pvlist1
, &pvlist2
);
4710 if(commonv
== tedge_v1(e
)) {
4711 toporouter_edge_t
*ope
;
4713 if(commonv
== tedge_v1(pv
->routingedge
)) {
4714 l1
= g_list_concat(l1
, pvlist1
);
4715 l2
= g_list_concat(l2
, pvlist2
);
4716 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e
), edge_v2(pv
->routingedge
)));
4718 l1
= g_list_concat(l1
, pvlist2
);
4719 l2
= g_list_concat(l2
, pvlist1
);
4720 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e
), edge_v1(pv
->routingedge
)));
4723 l2
= g_list_concat(l2
, g_list_copy(edge_routing(ope
)));
4726 toporouter_edge_t
*ope
;
4727 if(commonv
== tedge_v1(pv
->routingedge
)) {
4728 l1
= g_list_concat(l1
, pvlist2
);
4729 l2
= g_list_concat(l2
, pvlist1
);
4730 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e
), edge_v2(pv
->routingedge
)));
4732 l1
= g_list_concat(l1
, pvlist1
);
4733 l2
= g_list_concat(l2
, pvlist2
);
4734 ope
= TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e
), edge_v1(pv
->routingedge
)));
4737 l1
= g_list_concat(l1
, g_list_copy(edge_routing(ope
)));
4743 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
4745 if(curv
->flags
& VERTEX_FLAG_ROUTE
&& (g_list_find(l2
, curv
->parent
) || g_list_find(l2
, curv
->child
))) {
4746 if(!g_list_find(rval
, curv
->route
)) rval
= g_list_prepend(rval
, curv
->route
);
4752 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
4754 if(curv
->flags
& VERTEX_FLAG_ROUTE
&& (g_list_find(l1
, curv
->parent
) || g_list_find(l1
, curv
->child
))) {
4755 if(!g_list_find(rval
, curv
->route
)) rval
= g_list_prepend(rval
, curv
->route
);
4767 vertices_routing_conflict_cost(toporouter_t
*r
, toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
, guint
*n
)
4769 GList
*conflicts
= vertices_routing_conflicts(v
, pv
), *i
;
4770 gdouble penalty
= 0.;
4775 penalty
+= TOPOROUTER_ROUTE(i
->data
)->score
;
4778 g_list_free(conflicts
);
4779 // if(penalty > 0.) printf("conflict penalty of %f with %f,%f %f,%f\n", penalty, vx(v), vy(v), vx(pv), vy(pv));
4784 gcost(toporouter_t
*r
, toporouter_route_t
*data
, toporouter_vertex_t
*srcv
, toporouter_vertex_t
*v
, toporouter_vertex_t
*pv
, guint
*n
,
4785 toporouter_netlist_t
*pair
)
4787 gdouble cost
= 0., segcost
;
4791 if(g_list_find(data
->srcvertices
, v
)) return 0.;
4793 segcost
= tvdistance(pv
, v
);
4795 if(pair
&& !TOPOROUTER_IS_CONSTRAINT(v
->routingedge
) && v
->routingedge
) {
4796 GList
*list
= g_list_find(v
->routingedge
->routing
, v
);
4797 toporouter_vertex_t
*pv
= edge_routing_prev_not_temp(v
->routingedge
, list
);
4798 toporouter_vertex_t
*nv
= edge_routing_next_not_temp(v
->routingedge
, list
);
4800 if(pv
->route
&& pv
->route
->netlist
== pair
) {
4801 }else if(nv
->route
&& nv
->route
->netlist
== pair
) {
4807 cost
= pv
->gcost
+ segcost
;
4809 if(r
->flags
& TOPOROUTER_FLAG_LEASTINVALID
) {
4810 gdouble conflictcost
= 0.;
4812 if(pv
&& v
!= pv
&& vz(v
) == vz(pv
)) conflictcost
= vertices_routing_conflict_cost(r
, v
, pv
, n
);
4814 if(!(r
->flags
& TOPOROUTER_FLAG_DETOUR
&& *n
== 1)) {
4815 cost
+= conflictcost
* (pow(*n
,2));
4822 #define vlayer(x) (&r->layers[(int)vz(x)])
4825 candidate_is_available(toporouter_vertex_t
*pv
, toporouter_vertex_t
*v
)
4827 // TODO: still needed?
4829 if(pv
== v
) return 0;
4837 route(toporouter_t
*r
, toporouter_route_t
*data
, guint debug
)
4839 GtsEHeap
*openlist
= gts_eheap_new(route_heap_cmp
, NULL
);
4840 GList
*closelist
= NULL
;
4841 GList
*i
, *rval
= NULL
;
4842 toporouter_netlist_t
*pair
= NULL
;
4845 toporouter_vertex_t
*srcv
= NULL
, *destv
= NULL
, *curpoint
= NULL
;
4846 toporouter_layer_t
*cur_layer
, *dest_layer
;
4848 g_assert(data
->src
->c
!= data
->dest
->c
);
4850 if(data
->destvertices
) g_list_free(data
->destvertices
);
4851 if(data
->srcvertices
) g_list_free(data
->srcvertices
);
4853 data
->destvertices
= cluster_vertices(r
, data
->dest
);
4854 data
->srcvertices
= cluster_vertices(r
, data
->src
);
4856 closest_cluster_pair(r
, data
->srcvertices
, data
->destvertices
, &curpoint
, &destv
);
4858 if(!curpoint
|| !destv
) goto routing_return
;
4861 cur_layer
= vlayer(curpoint
); dest_layer
= vlayer(destv
);
4865 data
->alltemppoints
= g_hash_table_new(g_direct_hash
, g_direct_equal
);
4867 curpoint
->parent
= NULL
;
4868 curpoint
->child
= NULL
;
4869 curpoint
->gcost
= 0.;
4871 curpoint
->hcost
= simple_h_cost(r
, curpoint
, destv
);
4873 if(data
->netlist
&& data
->netlist
->pair
) {
4874 GList
*i
= r
->routednets
;
4876 toporouter_route_t
*curroute
= TOPOROUTER_ROUTE(i
->data
);
4877 if(curroute
->netlist
== data
->netlist
->pair
) {
4878 pair
= data
->netlist
->pair
;
4885 gts_eheap_insert(openlist
, curpoint
);
4887 while(gts_eheap_size(openlist
) > 0) {
4888 GList
*candidatepoints
;
4889 data
->curpoint
= curpoint
;
4890 //draw_route_status(r, closelist, openlist, curpoint, data, count++);
4892 curpoint
= TOPOROUTER_VERTEX( gts_eheap_remove_top(openlist
, NULL
) );
4893 if(curpoint
->parent
&& !(curpoint
->flags
& VERTEX_FLAG_TEMP
)) {
4894 if(vz(curpoint
) != vz(destv
)) {
4895 toporouter_vertex_t
*tempv
;
4896 cur_layer
= vlayer(curpoint
);//&r->layers[(int)vz(curpoint)];
4897 tempv
= closest_dest_vertex(r
, curpoint
, data
);
4900 dest_layer
= vlayer(destv
);//&r->layers[(int)vz(destv)];
4906 // destpoint = closest_dest_vertex(r, curpoint, data);
4907 // dest_layer = &r->layers[(int)vz(destpoint)];
4909 if(g_list_find(data
->destvertices
, curpoint
)) {
4910 toporouter_vertex_t
*temppoint
= curpoint
;
4917 data
->path
= g_list_prepend(data
->path
, temppoint
);
4918 if(g_list_find(data
->srcvertices
, temppoint
)) {
4920 if(r
->flags
& TOPOROUTER_FLAG_AFTERORDER
) break;
4922 temppoint
= temppoint
->parent
;
4925 data
->score
= path_score(r
, data
->path
);
4927 printf("ROUTE: path score = %f computation cost = %d\n", data
->score
, count
);
4930 if(srcv
->bbox
->cluster
!= data
->src
) {
4931 data
->src
= srcv
->bbox
->cluster
;
4934 if(destv
->bbox
->cluster
!= data
->dest
) {
4935 data
->dest
= destv
->bbox
->cluster
;
4939 closelist_insert(curpoint
);
4941 printf("\n\n\n*** ROUTE COUNT = %d\n", count
);
4943 candidatepoints
= compute_candidate_points(r
, cur_layer
, curpoint
, data
, &destv
);
4945 //#ifdef DEBUG_ROUTE
4946 /*********************
4947 if(debug && !strcmp(data->dest->netlist, " unnamed_net2"))
4949 unsigned int mask = ~(VERTEX_FLAG_RED | VERTEX_FLAG_GREEN | VERTEX_FLAG_BLUE);
4953 for(j=0;j<groupcount();j++) {
4954 i = r->layers[j].vertices;
4956 TOPOROUTER_VERTEX(i->data)->flags &= mask;
4961 i = candidatepoints;
4963 TOPOROUTER_VERTEX(i->data)->flags |= VERTEX_FLAG_GREEN;
4964 // printf("flagged a candpoint @ %f,%f\n",
4965 // vx(i->data), vy(i->data));
4969 curpoint->flags |= VERTEX_FLAG_BLUE;
4970 if(curpoint->parent)
4971 curpoint->parent->flags |= VERTEX_FLAG_RED;
4974 for(j=0;j<groupcount();j++) {
4975 GList *datas = g_list_prepend(NULL, data);
4976 sprintf(buffer, "route-%d-%05d.png", j, count);
4977 toporouter_draw_surface(r, r->layers[j].surface, buffer, 1024, 1024, 2, datas, j, candidatepoints);
4982 *********************/
4984 // if(count > 100) exit(0);
4985 i
= candidatepoints
;
4987 toporouter_vertex_t
*temppoint
= TOPOROUTER_VERTEX(i
->data
);
4988 if(!g_list_find(closelist
, temppoint
) && candidate_is_available(curpoint
, temppoint
)) { //&& temppoint != curpoint) {
4989 toporouter_heap_search_data_t heap_search_data
= { temppoint
, NULL
};
4992 gdouble temp_g_cost
= gcost(r
, data
, srcv
, temppoint
, curpoint
, &temp_gn
, pair
);
4995 gts_eheap_foreach(openlist
,toporouter_heap_search
, &heap_search_data
);
4997 if(heap_search_data
.result
) {
4998 if(temp_g_cost
< temppoint
->gcost
) {
5000 temppoint
->gcost
= temp_g_cost
;
5001 temppoint
->gn
= temp_gn
;
5003 temppoint
->parent
= curpoint
;
5004 curpoint
->child
= temppoint
;
5006 gts_eheap_update(openlist
);
5009 temppoint
->parent
= curpoint
;
5010 curpoint
->child
= temppoint
;
5012 temppoint
->gcost
= temp_g_cost
;
5013 temppoint
->gn
= temp_gn
;
5015 temppoint
->hcost
= simple_h_cost(r
, temppoint
, destv
);
5016 // if(cur_layer != dest_layer) temppoint->hcost += r->viacost;
5017 gts_eheap_insert(openlist
, temppoint
);
5023 g_list_free(candidatepoints
);
5027 printf("ROUTE: could not find path!\n");
5030 data
->score
= INFINITY
;
5031 clean_routing_edges(r
, data
);
5034 //TOPOROUTER_VERTEX(data->src->point)->parent = NULL;
5035 //TOPOROUTER_VERTEX(data->src->point)->child = NULL;
5036 goto routing_return
;
5041 for(i=0;i<groupcount();i++) {
5043 sprintf(buffer, "route-error-%d-%d.png", r->routecount, i);
5044 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1280, 1280, 2, data, i, NULL);
5051 // printf(" * finished a*\n");
5055 for(i=0;i<groupcount();i++) {
5057 sprintf(buffer, "route-preclean-%d-%d.png", i, r->routecount);
5058 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, data, i, NULL);
5066 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
5068 if(tv->routingedge) {
5069 GList *list = g_list_find(edge_routing(tv->routingedge), tv);
5070 toporouter_vertex_t *restartv = NULL, *boxpoint;
5075 if(vertex_bbox(tedge_v2(tv->routingedge)))
5076 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v2(tv->routingedge))->point);
5080 if(tedge_v2(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v2(tv->routingedge)))
5081 restartv = tedge_v2(tv->routingedge);
5082 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
5083 restartv = boxpoint;
5087 if(vertex_bbox(tedge_v1(tv->routingedge)))
5088 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v1(tv->routingedge))->point);
5092 if(tedge_v1(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v1(tv->routingedge)))
5093 restartv = tedge_v1(tv->routingedge);
5094 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
5095 restartv = boxpoint;
5100 clean_routing_edges(r, data);
5101 gts_eheap_destroy(openlist);
5102 g_list_free(closelist);
5103 openlist = gts_eheap_new(route_heap_cmp, NULL);
5105 g_list_free(data->path);
5106 printf("ROUTING RESTARTING with new src %f,%f,%f\n", vx(restartv), vy(restartv), vz(restartv));
5107 curpoint = restartv;
5117 toporouter_vertex_t
*pv
= NULL
;
5118 GList
*i
= data
->path
;
5120 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
5122 if(pv
&& g_list_find(data
->srcvertices
, tv
)) {
5123 GList
*temp
= g_list_copy(i
);
5124 g_list_free(data
->path
);
5134 toporouter_vertex_t
*pv
= NULL
;
5135 GList
*i
= data
->path
;
5137 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
5138 if(tv
->flags
& VERTEX_FLAG_TEMP
) {
5139 tv
->flags
^= VERTEX_FLAG_TEMP
;
5140 tv
->flags
|= VERTEX_FLAG_ROUTE
;
5142 if(pv
) pv
->child
= tv
;
5144 if(tv
->routingedge
) tv
->route
= data
;
5146 // if(tv->routingedge && !TOPOROUTER_IS_CONSTRAINT(tv->routingedge)) space_edge(tv->routingedge, NULL);
5154 toporouter_vertex_t
*pv
= NULL
, *v
= NULL
;
5156 GList
*i
= data
->path
;
5158 v
= TOPOROUTER_VERTEX(i
->data
);
5171 if(v
) v
->child
= NULL
;
5174 clean_routing_edges(r
, data
);
5177 GList
*i
= data
->path
;
5179 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
5181 if(v
->routingedge
&& !TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
5182 space_edge(v
->routingedge
, NULL
);
5189 g_list_free(data
->destvertices
);
5190 g_list_free(data
->srcvertices
);
5191 data
->destvertices
= NULL
;
5192 data
->srcvertices
= NULL
;
5193 gts_eheap_destroy(openlist
);
5194 g_list_free(closelist
);
5196 data
->alltemppoints
= NULL
;
5201 /* moves vertex v d units in the direction of vertex p */
5203 vertex_move_towards_point(GtsVertex
*v
, gdouble px
, gdouble py
, gdouble d
)
5205 gdouble dx
= px
- GTS_POINT(v
)->x
;
5206 gdouble dy
= py
- GTS_POINT(v
)->y
;
5207 gdouble theta
= atan(fabs(dy
/dx
));
5209 g_assert(finite(theta
));
5214 GTS_POINT(v
)->x
+= d
* cos(theta
);
5215 GTS_POINT(v
)->y
+= d
* sin(theta
);
5217 GTS_POINT(v
)->x
+= d
* cos(theta
);
5218 GTS_POINT(v
)->y
-= d
* sin(theta
);
5224 GTS_POINT(v
)->x
-= d
* cos(theta
);
5225 GTS_POINT(v
)->y
+= d
* sin(theta
);
5227 GTS_POINT(v
)->x
-= d
* cos(theta
);
5228 GTS_POINT(v
)->y
-= d
* sin(theta
);
5235 /* moves vertex v d units in the direction of vertex p */
5237 vertex_move_towards_vertex(GtsVertex
*v
, GtsVertex
*p
, gdouble d
)
5239 gdouble dx
= GTS_POINT(p
)->x
- GTS_POINT(v
)->x
;
5240 gdouble dy
= GTS_POINT(p
)->y
- GTS_POINT(v
)->y
;
5241 gdouble theta
= atan(fabs(dy
/dx
));
5243 g_assert(finite(theta
));
5248 GTS_POINT(v
)->x
+= d
* cos(theta
);
5249 GTS_POINT(v
)->y
+= d
* sin(theta
);
5251 GTS_POINT(v
)->x
+= d
* cos(theta
);
5252 GTS_POINT(v
)->y
-= d
* sin(theta
);
5258 GTS_POINT(v
)->x
-= d
* cos(theta
);
5259 GTS_POINT(v
)->y
+= d
* sin(theta
);
5261 GTS_POINT(v
)->x
-= d
* cos(theta
);
5262 GTS_POINT(v
)->y
-= d
* sin(theta
);
5271 pathvertex_arcing_through_constraint(toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
)
5273 toporouter_vertex_t
*v
= pathv
->child
;
5275 if(!v
|| !v
->routingedge
) return 0.;
5277 while(v
->flags
& VERTEX_FLAG_ROUTE
&& (tedge_v1(v
->routingedge
) == arcv
|| tedge_v2(v
->routingedge
) == arcv
)) {
5278 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
5279 return gts_point_distance(GTS_POINT(tedge_v1(v
->routingedge
)), GTS_POINT(tedge_v2(v
->routingedge
)));
5284 while(v
->flags
& VERTEX_FLAG_ROUTE
&& (tedge_v1(v
->routingedge
) == arcv
|| tedge_v2(v
->routingedge
) == arcv
)) {
5285 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
5286 return gts_point_distance(GTS_POINT(tedge_v1(v
->routingedge
)), GTS_POINT(tedge_v2(v
->routingedge
)));
5294 vertices_connected(toporouter_vertex_t
*a
, toporouter_vertex_t
*b
)
5296 return ((a
->route
->netlist
== b
->route
->netlist
&& a
->route
->src
->c
== b
->route
->src
->c
) ? 1 : 0);
5300 edge_min_spacing(GList
*list
, toporouter_edge_t
*e
, toporouter_vertex_t
*v
, guint debug
)
5302 toporouter_vertex_t
*origin
;
5305 toporouter_vertex_t
*nextv
, *prevv
;
5306 //toporouter_vertex_t *edgev;
5307 //gdouble constraint_spacing;
5309 if(!list
) return INFINITY
;
5311 // printf("\t CMS %f,%f - %f,%f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), vx(tedge_v2(e)), vy(tedge_v2(e)));
5313 prevv
= origin
= TOPOROUTER_VERTEX(list
->data
);
5318 if(gts_point_distance2(GTS_POINT(origin
), GTS_POINT(edge_v1(e
))) < gts_point_distance2(GTS_POINT(v
), GTS_POINT(edge_v1(e
)))) {
5322 nextv
= edge_routing_next(e
, i
);
5323 if(nextv
->route
&& vertices_connected(nextv
, prevv
)) { i
= i
->next
; continue; }
5324 if(!(nextv
->flags
& VERTEX_FLAG_TEMP
)) {
5325 gdouble ms
= min_spacing(prevv
, nextv
);
5326 if(nextv
== tedge_v2(e
)) {
5327 gdouble cms
= pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i
->data
), tedge_v2(e
));
5328 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v2(e)), vy(tedge_v2(e)), cms, ms);
5329 // if(vx(tedge_v2(e)) > -EPSILON && vx(tedge_v2(e)) < EPSILON) {
5330 // printf("\t\tPROB: ");
5331 // print_vertex(tedge_v2(e));
5333 if(cms
> EPSILON
) space
+= MIN(ms
, cms
/ 2.);
5340 // printf("%f ", space);
5347 nextv
= edge_routing_prev(e
, i
);
5348 if(nextv
->route
&& vertices_connected(nextv
, prevv
)) { i
= i
->prev
; continue; }
5349 if(!(nextv
->flags
& VERTEX_FLAG_TEMP
)) {
5350 gdouble ms
= min_spacing(prevv
, nextv
);
5351 if(nextv
== tedge_v1(e
)) {
5352 gdouble cms
= pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i
->data
), tedge_v1(e
));
5353 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), cms, ms);
5354 // if(vx(tedge_v1(e)) > -EPSILON && vx(tedge_v1(e)) < EPSILON) {
5355 // printf("\t\tPROB: ");
5356 // print_vertex(tedge_v1(e));
5358 if(cms
> EPSILON
) space
+= MIN(ms
, cms
/ 2.);
5365 // printf("%f ", space);
5370 if(TOPOROUTER_IS_CONSTRAINT(e
) && space
> gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) / 2.)
5371 space
= gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) / 2.;
5373 // if(debug) printf("\tedge_min_spacing: %f\n", space);
5377 /* line segment is 1 & 2, point is 3
5378 returns 0 if v3 is outside seg
5381 vertex_line_normal_intersection(gdouble x1
, gdouble y1
, gdouble x2
, gdouble y2
, gdouble x3
, gdouble y3
, gdouble
*x
, gdouble
*y
)
5383 gdouble m1
= cartesian_gradient(x1
,y1
,x2
,y2
);
5384 gdouble m2
= perpendicular_gradient(m1
);
5385 gdouble c2
= (isinf(m2
)) ? x3
: y3
- (m2
* x3
);
5386 gdouble c1
= (isinf(m1
)) ? x1
: y1
- (m1
* x1
);
5393 *x
= (c2
- c1
) / (m1
- m2
);
5395 *y
= (isinf(m2
)) ? y1
: (m2
* (*x
)) + c2
;
5397 if(*x
>= MIN(x1
,x2
) - EPSILON
&& *x
<= MAX(x1
,x2
) + EPSILON
&& *y
>= MIN(y1
,y2
) - EPSILON
&& *y
<= MAX(y1
,y2
) + EPSILON
)
5403 print_toporouter_arc(toporouter_arc_t
*arc
)
5405 // GList *i = arc->vs;
5407 printf("ARC CENTRE: %f,%f ", vx(arc
->centre
), vy(arc
->centre
));// print_vertex(arc->centre);
5408 printf("RADIUS: %f", arc
->r
);
5410 if(arc
->dir
>0) printf(" COUNTERCLOCKWISE ");
5411 else if(arc
->dir
<0) printf(" CLOCKWISE ");
5412 else printf(" COLINEAR(ERROR) ");
5417 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
5418 printf("%f,%f ", vx(v), vy(v));
5426 toporouter_arc_remove(toporouter_oproute_t
*oproute
, toporouter_arc_t
*arc
)
5428 oproute
->arcs
= g_list_remove(oproute
->arcs
, arc
);
5430 if(arc
->v
) arc
->v
->arc
= NULL
;
5434 toporouter_arc_new(toporouter_oproute_t
*oproute
, toporouter_vertex_t
*v1
, toporouter_vertex_t
*v2
, toporouter_vertex_t
*centre
, gdouble r
, gint dir
)
5436 toporouter_arc_t
*arc
= TOPOROUTER_ARC(gts_object_new(GTS_OBJECT_CLASS(toporouter_arc_class())));
5437 arc
->centre
= centre
;
5444 if(v1
) v1
->arc
= arc
;
5445 arc
->oproute
= oproute
;
5447 arc
->clearance
= NULL
;
5453 path_set_oproute(GList
*path
, toporouter_oproute_t
*oproute
)
5456 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(path
->data
);
5458 if(v
->flags
& VERTEX_FLAG_ROUTE
)
5459 v
->oproute
= oproute
;
5466 print_oproute(toporouter_oproute_t
*oproute
)
5468 GList
*i
= oproute
->arcs
;
5470 printf("Optimized Route:\n");
5471 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", oproute
->netlist
, oproute
->style
);
5472 // printf("%s\n", oproute->netlist);
5474 i = oproute->term1->zlink;
5476 toporouter_vertex_t *thisv = TOPOROUTER_VERTEX(i->data);
5477 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", vertex_bbox(thisv)->netlist, vertex_bbox(thisv)->style);
5481 printf("\t"); print_vertex(oproute
->term1
); printf("\n");
5484 toporouter_arc_t
*arc
= (toporouter_arc_t
*)i
->data
;
5485 printf("\t"); print_toporouter_arc(arc
); printf("\n");
5488 printf("\t"); print_vertex(oproute
->term2
); printf("\n");
5492 export_pcb_drawline(guint layer
, guint x0
, guint y0
, guint x1
, guint y1
, guint thickness
, guint keepaway
)
5496 line
= CreateDrawnLineOnLayer( LAYER_PTR(layer
), x0
, y0
, x1
, y1
,
5497 thickness
, keepaway
,
5498 MakeFlags (AUTOFLAG
| (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
: 0)));
5501 AddObjectToCreateUndoList (LINE_TYPE
, LAYER_PTR(layer
), line
, line
);
5502 d
= coord_distance((double)x0
, (double)y0
, (double)x1
, (double)y1
) / 100.;
5508 arc_angle(toporouter_arc_t
*arc
)
5510 gdouble x0
, x1
, y0
, y1
;
5512 x0
= arc
->x0
- vx(arc
->centre
);
5513 x1
= arc
->x1
- vx(arc
->centre
);
5514 y0
= arc
->y0
- vy(arc
->centre
);
5515 y1
= arc
->y1
- vy(arc
->centre
);
5517 return fabs(acos(((x0
*x1
)+(y0
*y1
))/(sqrt(pow(x0
,2)+pow(y0
,2))*sqrt(pow(x1
,2)+pow(y1
,2)))));
5521 export_pcb_drawarc(guint layer
, toporouter_arc_t
*a
, guint thickness
, guint keepaway
)
5523 gdouble sa
, da
, theta
;
5524 gdouble x0
, y0
, x1
, y1
, d
=0.;
5528 wind
= coord_wind(a
->x0
, a
->y0
, a
->x1
, a
->y1
, vx(a
->centre
), vy(a
->centre
));
5530 sa
= coord_xangle(a
->x0
, a
->y0
, vx(a
->centre
), vy(a
->centre
)) * 180. / M_PI
;
5532 x0
= a
->x0
- vx(a
->centre
);
5533 x1
= a
->x1
- vx(a
->centre
);
5534 y0
= a
->y0
- vy(a
->centre
);
5535 y1
= a
->y1
- vy(a
->centre
);
5537 theta
= arc_angle(a
);
5539 if(!a
->dir
|| !wind
) return 0.;
5541 if(a
->dir
!= wind
) theta
= 2. * M_PI
- theta
;
5543 da
= -a
->dir
* theta
* 180. / M_PI
;
5545 if(da
< 1. && da
> -1.) return 0.;
5546 if(da
> 359. || da
< -359.) return 0.;
5548 arc
= CreateNewArcOnLayer(LAYER_PTR(layer
), vx(a
->centre
), vy(a
->centre
), a
->r
, a
->r
,
5549 sa
, da
, thickness
, keepaway
,
5550 MakeFlags( AUTOFLAG
| (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
: 0)));
5553 AddObjectToCreateUndoList( ARC_TYPE
, LAYER_PTR(layer
), arc
, arc
);
5554 d
= a
->r
* theta
/ 100.;
5561 calculate_term_to_arc(toporouter_vertex_t
*v
, toporouter_arc_t
*arc
, guint dir
)
5563 gdouble theta
, a
, b
, bx
, by
, a0x
, a0y
, a1x
, a1y
;
5566 theta
= acos(arc
->r
/ gts_point_distance(GTS_POINT(v
), GTS_POINT(arc
->centre
)));
5567 a
= arc
->r
* sin(theta
);
5568 b
= arc
->r
* cos(theta
);
5570 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
));
5572 point_from_point_to_point(arc
->centre
, v
, b
, &bx
, &by
);
5574 coords_on_line(bx
, by
, perpendicular_gradient(point_gradient(GTS_POINT(v
), GTS_POINT(arc
->centre
))), a
, &a0x
, &a0y
, &a1x
, &a1y
);
5576 winddir
= coord_wind(vx(v
), vy(v
), a0x
, a0y
, vx(arc
->centre
), vy(arc
->centre
));
5579 printf("!winddir @ v %f,%f arc->centre %f,%f\n", vx(v
), vy(v
), vx(arc
->centre
), vy(arc
->centre
));
5580 //TODO: fix hack: this shouldn't happen
5590 if(dir
) winddir
= -winddir
;
5592 if(winddir
== arc
->dir
) {
5593 if(!dir
) { arc
->x0
= a0x
; arc
->y0
= a0y
; }
5594 else{ arc
->x1
= a0x
; arc
->y1
= a0y
; }
5596 if(!dir
) { arc
->x0
= a1x
; arc
->y0
= a1y
; }
5597 else{ arc
->x1
= a1x
; arc
->y1
= a1y
; }
5604 // b1 is the projection in the direction of narc, while b2 is the perpendicular projection
5606 arc_ortho_projections(toporouter_arc_t
*arc
, toporouter_arc_t
*narc
, gdouble
*b1
, gdouble
*b2
)
5608 gdouble nax
, nay
, ax
, ay
, alen2
, c
;
5609 gdouble b1x
, b1y
, b2x
, b2y
;
5612 printf("arc c = %f,%f narc c = %f,%f arc->0 = %f,%f\n",
5613 vx(arc
->centre
), vy(arc
->centre
),
5614 vx(narc
->centre
), vy(narc
->centre
),
5618 nax
= vx(narc
->centre
) - vx(arc
->centre
);
5619 nay
= vy(narc
->centre
) - vy(arc
->centre
);
5620 alen2
= pow(nax
,2) + pow(nay
,2);
5623 ax
= arc
->x0
- vx(arc
->centre
);
5624 ay
= arc
->y0
- vy(arc
->centre
);
5627 printf("norm narc = %f,%f - %f\tA=%f,%f\n", nax
, nay
, sqrt(alen2
), ax
, ay
);
5630 c
= ((ax
*nax
)+(ay
*nay
)) / alen2
;
5638 printf("proj = %f,%f perp proj = %f,%f\n", b1x
, b1y
, b2x
, b2y
);
5641 *b1
= sqrt(pow(b1x
,2) + pow(b1y
,2));
5642 *b2
= sqrt(pow(b2x
,2) + pow(b2y
,2));
5647 calculate_arc_to_arc(toporouter_t
*ar
, toporouter_arc_t
*parc
, toporouter_arc_t
*arc
)
5649 gdouble theta
, a
, b
, bx
, by
, a0x
, a0y
, a1x
, a1y
, m
, preva
, prevb
;
5651 toporouter_arc_t
*bigr
, *smallr
;
5653 if(parc
->r
> arc
->r
) {
5654 bigr
= parc
; smallr
= arc
;
5656 bigr
= arc
; smallr
= parc
;
5659 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr
->centre
), vy(bigr
->centre
),
5660 vx(smallr
->centre
), vy(smallr
->centre
));
5663 m
= perpendicular_gradient(point_gradient(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5665 if(bigr
->centre
== smallr
->centre
) {
5667 printf("bigr->centre == smallr->centre @ %f,%f\n", vx(smallr
->centre
), vy(smallr
->centre
));
5670 g_assert(bigr
->centre
!= smallr
->centre
);
5672 if(parc
->dir
== arc
->dir
) {
5673 //export_arc_straight:
5675 theta
= acos((bigr
->r
- smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5676 a
= bigr
->r
* sin(theta
);
5677 b
= bigr
->r
* cos(theta
);
5679 point_from_point_to_point(bigr
->centre
, smallr
->centre
, b
, &bx
, &by
);
5681 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5683 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5685 arc_ortho_projections(parc
, arc
, &prevb
, &preva
);
5686 //#ifdef DEBUG_EXPORT
5689 printf("STRAIGHT:\n");
5690 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr
->centre
), vy(bigr
->centre
),
5691 vx(smallr
->centre
), vy(smallr
->centre
));
5692 printf("theta = %f a = %f b = %f bigrr = %f d = %f po = %f\n", theta
, a
, b
, bigr
->r
,
5693 gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)),
5694 bigr
->r
/ gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5695 printf("bigr-r = %f smallr-r = %f ratio = %f\n",
5696 bigr
->r
, smallr
->r
, (bigr
->r
- smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5697 printf("preva = %f prevb = %f\n\n", preva
, prevb
);
5703 if(bigr
==parc
) winddir
= -winddir
;
5705 if(winddir
== bigr
->dir
) {
5723 a
= smallr
->r
* sin(theta
);
5724 b
= smallr
->r
* cos(theta
);
5727 printf("a = %f b = %f\n", a
, b
);
5729 point_from_point_to_point(smallr
->centre
, bigr
->centre
, -b
, &bx
, &by
);
5731 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5733 if(winddir
== bigr
->dir
) {
5755 theta
= acos((bigr
->r
+ smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5756 a
= bigr
->r
* sin(theta
);
5757 b
= bigr
->r
* cos(theta
);
5759 point_from_point_to_point(bigr
->centre
, smallr
->centre
, b
, &bx
, &by
);
5761 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5763 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5764 //#ifdef DEBUG_EXPORT
5767 printf("theta = %f a = %f b = %f r = %f d = %f po = %f\n", theta
, a
, b
, bigr
->r
+ smallr
->r
,
5768 gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)),
5769 (bigr
->r
+smallr
->r
) / gts_point_distance(GTS_POINT(bigr
->centre
), GTS_POINT(smallr
->centre
)));
5771 printf("bigr centre = %f,%f smallr centre = %f,%f\n\n", vx(bigr
->centre
), vy(bigr
->centre
),
5772 vx(smallr
->centre
), vy(smallr
->centre
));
5774 printf("big wind = %d small wind = %d\n", bigr
->dir
, smallr
->dir
);
5779 smallr->centre->flags |= VERTEX_FLAG_RED;
5780 bigr->centre->flags |= VERTEX_FLAG_GREEN;
5781 //bigr->centre->flags |= VERTEX_FLAG_RED;
5784 for(i=0;i<groupcount();i++) {
5786 sprintf(buffer, "wind%d.png", i);
5787 toporouter_draw_surface(ar, ar->layers[i].surface, buffer, 2096, 2096, 2, NULL, i, NULL);
5795 if(bigr
==parc
) winddir
= -winddir
;
5797 if(winddir
== bigr
->dir
) {
5815 a
= smallr
->r
* sin(theta
);
5816 b
= smallr
->r
* cos(theta
);
5818 point_from_point_to_point(smallr
->centre
, bigr
->centre
, b
, &bx
, &by
);
5820 coords_on_line(bx
, by
, m
, a
, &a0x
, &a0y
, &a1x
, &a1y
);
5822 winddir
= coord_wind(vx(smallr
->centre
), vy(smallr
->centre
), a0x
, a0y
, vx(bigr
->centre
), vy(bigr
->centre
));
5826 if(bigr
==parc
) winddir
= -winddir
;
5828 if(winddir
== smallr
->dir
) {
5852 export_oproutes(toporouter_t
*ar
, toporouter_oproute_t
*oproute
)
5854 guint layer
= PCB
->LayerGroups
.Entries
[oproute
->layergroup
][0];
5855 guint thickness
= lookup_thickness(oproute
->style
);
5856 guint keepaway
= lookup_keepaway(oproute
->style
);
5857 GList
*arcs
= oproute
->arcs
;
5858 toporouter_arc_t
*arc
, *parc
= NULL
;
5861 ar
->wiring_score
+= export_pcb_drawline(layer
, vx(oproute
->term1
), vy(oproute
->term1
), vx(oproute
->term2
), vy(oproute
->term2
), thickness
, keepaway
);
5866 // calculate_term_to_arc(oproute->term1, TOPOROUTER_ARC(arcs->data), 0, layer);
5869 arc
= TOPOROUTER_ARC(arcs
->data
);
5872 ar
->wiring_score
+= export_pcb_drawarc(layer
, parc
, thickness
, keepaway
);
5873 ar
->wiring_score
+= export_pcb_drawline(layer
, parc
->x1
, parc
->y1
, arc
->x0
, arc
->y0
, thickness
, keepaway
);
5875 ar
->wiring_score
+= export_pcb_drawline(layer
, vx(oproute
->term1
), vy(oproute
->term1
), arc
->x0
, arc
->y0
, thickness
, keepaway
);
5881 ar
->wiring_score
+= export_pcb_drawarc(layer
, arc
, thickness
, keepaway
);
5882 ar
->wiring_score
+= export_pcb_drawline(layer
, arc
->x1
, arc
->y1
, vx(oproute
->term2
), vy(oproute
->term2
), thickness
, keepaway
);
5889 oproute_free(toporouter_oproute_t
*oproute
)
5891 GList
*i
= oproute
->arcs
;
5893 toporouter_arc_t
*arc
= (toporouter_arc_t
*) i
->data
;
5894 if(arc
->centre
->flags
& VERTEX_FLAG_TEMP
)
5895 gts_object_destroy(GTS_OBJECT(arc
->centre
));
5900 g_list_free(oproute
->arcs
);
5905 oproute_calculate_tof(toporouter_oproute_t
*oproute
)
5907 GList
*arcs
= oproute
->arcs
;
5908 toporouter_arc_t
*parc
= NULL
, *arc
;
5913 oproute
->tof
= gts_point_distance(GTS_POINT(oproute
->term1
), GTS_POINT(oproute
->term2
));
5918 arc
= TOPOROUTER_ARC(arcs
->data
);
5921 oproute
->tof
+= arc_angle(parc
) * parc
->r
;
5922 oproute
->tof
+= sqrt(pow(parc
->x1
-arc
->x0
,2)+pow(parc
->y1
-arc
->y0
,2));
5924 oproute
->tof
+= sqrt(pow(arc
->x0
-vx(oproute
->term1
),2)+pow(arc
->y0
-vy(oproute
->term1
),2));
5931 oproute
->tof
+= arc_angle(parc
) * parc
->r
;
5932 oproute
->tof
+= sqrt(pow(arc
->x1
-vx(oproute
->term2
),2)+pow(arc
->y1
-vy(oproute
->term2
),2));
5937 line_line_distance_at_normal(
5938 gdouble line1_x1
, gdouble line1_y1
,
5939 gdouble line1_x2
, gdouble line1_y2
,
5940 gdouble line2_x1
, gdouble line2_y1
,
5941 gdouble line2_x2
, gdouble line2_y2
,
5942 gdouble x
, gdouble y
)
5944 gdouble m1
= perpendicular_gradient(cartesian_gradient(line1_x1
, line1_y1
, line1_x2
, line1_y2
));
5945 gdouble m2
= cartesian_gradient(line2_x1
, line2_y1
, line2_x2
, line2_y2
);
5946 gdouble c1
= (isinf(m1
)) ? x
: y
- (m1
* x
);
5947 gdouble c2
= (isinf(m2
)) ? line2_x1
: line2_y1
- (m2
* line2_x1
);
5951 if(isinf(m2
)) intx
= line2_x1
;
5952 else if(isinf(m1
)) intx
= x
;
5953 else intx
= (c2
- c1
) / (m1
- m2
);
5955 inty
= (isinf(m2
)) ? (m1
* intx
) + c1
: (m2
* intx
) + c2
;
5957 return sqrt(pow(x
-intx
,2)+pow(y
-inty
,2));
5961 calculate_serpintine(gdouble delta
, gdouble r
, gdouble initiala
, gdouble
*a
, guint
*nhalfcycles
)
5963 gdouble lhalfcycle
= 2.*(initiala
-r
)+(M_PI
*r
);
5966 printf("lhalfcycle = %f r = %f\n", lhalfcycle
, r
);
5968 n
= (delta
- M_PI
*r
) / (lhalfcycle
- 2.*r
) + 1;
5969 *a
= (delta
+ 4.*n
*r
- n
*M_PI
*r
+ 4.*r
- M_PI
*r
)/(2.*n
);
5974 oproute_min_spacing(toporouter_oproute_t
*a
, toporouter_oproute_t
*b
)
5976 return lookup_thickness(a
->style
) / 2. + lookup_thickness(b
->style
) / 2. + MAX(lookup_keepaway(a
->style
), lookup_keepaway(b
->style
));
5980 vector_angle(gdouble ox
, gdouble oy
, gdouble ax
, gdouble ay
, gdouble bx
, gdouble by
)
5982 gdouble alen
= sqrt(pow(ax
-ox
,2)+pow(ay
-oy
,2));
5983 gdouble blen
= sqrt(pow(bx
-ox
,2)+pow(by
-oy
,2));
5984 return acos( ((ax
-ox
)*(bx
-ox
)+(ay
-oy
)*(by
-oy
)) / (alen
* blen
) );
5987 toporouter_serpintine_t
*
5988 toporouter_serpintine_new(gdouble x
, gdouble y
, gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, gpointer start
, gdouble halfa
, gdouble
5989 radius
, guint nhalfcycles
)
5991 toporouter_serpintine_t
*serp
= malloc(sizeof(toporouter_serpintine_t
));
5998 serp
->start
= start
;
5999 serp
->halfa
= halfa
;
6000 serp
->radius
= radius
;
6001 serp
->nhalfcycles
= nhalfcycles
;
6006 //#define DEBUG_RUBBERBAND 1
6009 check_non_intersect_vertex(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
,
6010 toporouter_vertex_t
*opv
, gint wind
, gint
*arcwind
, gdouble
*arcr
, guint debug
)
6012 gdouble ms
, line_int_x
, line_int_y
, x
, y
, d
= 0., m
;
6013 gdouble tx0
, ty0
, tx1
, ty1
;
6016 g_assert(pathv
->routingedge
);
6018 if(TOPOROUTER_IS_CONSTRAINT(pathv
->routingedge
)) {
6019 gdouble d
= tvdistance(tedge_v1(pathv
->routingedge
), tedge_v2(pathv
->routingedge
)) / 2.;
6020 ms
= min_spacing(pathv
, arcv
);
6023 ms
= edge_min_spacing(g_list_find(edge_routing(pathv
->routingedge
), pathv
), pathv
->routingedge
, arcv
, debug
);
6027 if(!vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(arcv
), vy(arcv
), &line_int_x
, &line_int_y
)) {
6029 if(coord_distance2(x0
, y0
, line_int_x
, line_int_y
) < coord_distance2(x1
, y1
, line_int_x
, line_int_y
))
6030 { line_int_x
= x0
; line_int_y
= y0
; }else{ line_int_x
= x1
; line_int_y
= y1
; }
6032 m
= perpendicular_gradient(cartesian_gradient(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
));
6034 m
= cartesian_gradient(x0
, y0
, x1
, y1
);
6037 coords_on_line(vx(arcv
), vy(arcv
), m
, 100., &tx0
, &ty0
, &tx1
, &ty1
);
6039 wind1
= coord_wind(tx0
, ty0
, tx1
, ty1
, line_int_x
, line_int_y
);
6040 wind2
= coord_wind(tx0
, ty0
, tx1
, ty1
, vx(opv
), vy(opv
));
6042 if(!wind2
|| wind1
== wind2
) return -1.;
6045 coords_on_line(line_int_x
, line_int_y
, perpendicular_gradient(m
), ms
, &tx0
, &ty0
, &tx1
, &ty1
);
6046 if(coord_distance2(tx0
, ty0
, vx(opv
), vy(opv
)) < coord_distance2(tx1
, ty1
, vx(opv
), vy(opv
)))
6047 { x
= tx0
; y
= ty0
; }else{ x
= tx1
; y
= ty1
; }
6049 toporouter_vertex_t
*parent
= pathv
->parent
, *child
= pathv
->child
;
6050 guint windtests
= 0;
6052 d
= coord_distance(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
);
6053 coord_move_towards_coord_values(line_int_x
, line_int_y
, vx(arcv
), vy(arcv
), ms
+ d
, &x
, &y
);
6055 wind1
= coord_wind(line_int_x
, line_int_y
, x
, y
, vx(parent
), vy(parent
));
6056 wind2
= coord_wind(line_int_x
, line_int_y
, x
, y
, vx(child
), vy(child
));
6057 if(wind1
&& wind2
&& wind1
== wind2
) {
6059 if(windtests
++ == 2) return -1.;
6061 if(parent
->flags
& VERTEX_FLAG_ROUTE
) parent
= parent
->parent
;
6062 if(child
->flags
& VERTEX_FLAG_ROUTE
) child
= child
->child
;
6069 *arcwind
= tvertex_wind(pathv
->parent
, pathv
, arcv
);
6071 #ifdef DEBUG_RUBBERBAND
6073 // printf("non-int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, d + ms,
6074 // vx(arcv), vy(arcv), vx(opv), vy(opv));
6081 check_intersect_vertex(gdouble x0
, gdouble y0
, gdouble x1
, gdouble y1
, toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
,
6082 toporouter_vertex_t
*opv
, gint wind
, gint
*arcwind
, gdouble
*arcr
, guint debug
)
6084 gdouble ms
, line_int_x
, line_int_y
, x
, y
, d
= 0.;
6086 if(TOPOROUTER_IS_CONSTRAINT(pathv
->routingedge
)) {
6087 gdouble d
= tvdistance(tedge_v1(pathv
->routingedge
), tedge_v2(pathv
->routingedge
)) / 2.;
6088 ms
= min_spacing(pathv
, arcv
);
6091 ms
= edge_min_spacing(g_list_find(edge_routing(pathv
->routingedge
), pathv
), pathv
->routingedge
, arcv
, debug
);
6094 if(!vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(arcv
), vy(arcv
), &line_int_x
, &line_int_y
))
6097 d
= coord_distance(line_int_x
, line_int_y
, vx(arcv
), vy(arcv
));
6100 if(d
> ms
- EPSILON
)
6103 coord_move_towards_coord_values(vx(arcv
), vy(arcv
), line_int_x
, line_int_y
, ms
, &x
, &y
);
6106 *arcwind
= tvertex_wind(pathv
->parent
, pathv
, arcv
);
6107 // *arcwind = coord_wind(x0, y0, x, y, x1, y1);
6108 #ifdef DEBUG_RUBBERBAND
6110 // printf("int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, ms - d,
6111 // vx(arcv), vy(arcv), vx(opv), vy(opv));
6117 /* returns non-zero if arc has loops */
6119 check_arc_for_loops(gpointer t1
, toporouter_arc_t
*arc
, gpointer t2
)
6121 gdouble x0
, y0
, x1
, y1
;
6123 if(TOPOROUTER_IS_VERTEX(t1
)) { x0
= vx(TOPOROUTER_VERTEX(t1
)); y0
= vy(TOPOROUTER_VERTEX(t1
)); }
6124 else { x0
= TOPOROUTER_ARC(t1
)->x1
; y0
= TOPOROUTER_ARC(t1
)->y1
; }
6126 if(TOPOROUTER_IS_VERTEX(t2
)) { x1
= vx(TOPOROUTER_VERTEX(t2
)); y1
= vy(TOPOROUTER_VERTEX(t2
)); }
6127 else { x1
= TOPOROUTER_ARC(t2
)->x0
; y1
= TOPOROUTER_ARC(t2
)->y0
; }
6129 if(coord_intersect_prop(x0
, y0
, arc
->x0
, arc
->y0
, arc
->x1
, arc
->y1
, x1
, y1
) ) {
6131 // (arc->x0 > arc->x1 - EPSILON && arc->x0 < arc->x1 + EPSILON &&
6132 // arc->y0 > arc->y1 - EPSILON && arc->y0 < arc->y1 + EPSILON)
6134 #ifdef DEBUG_RUBBERBAND
6135 printf("LOOPS %f %f -> %f %f & %f %f -> %f %f\n", x0
, y0
, arc
->x0
, arc
->y0
, arc
->x1
, arc
->y1
, x1
, y1
);
6142 toporouter_rubberband_arc_t
*
6143 new_rubberband_arc(toporouter_vertex_t
*pathv
, toporouter_vertex_t
*arcv
, gdouble r
, gdouble d
, gint wind
, GList
*list
)
6145 toporouter_rubberband_arc_t
*rba
= malloc(sizeof(toporouter_rubberband_arc_t
));
6156 compare_rubberband_arcs(toporouter_rubberband_arc_t
*a
, toporouter_rubberband_arc_t
*b
)
6157 { return b
->d
- a
->d
; }
6160 free_list_elements(gpointer data
, gpointer user_data
)
6164 /* 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 */
6167 vertex_edge_facing_vertex(GtsVertex *v, gdouble x, gdouble y)
6169 GSList *ts = gts_vertex_triangles(GTS_VERTEX(n), NULL);
6173 GtsTriangle *t = GTS_TRIANGLE(i->data);
6174 GtsEdge *e = gts_triangle_edge_opposite(t, v);
6176 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)) &&
6177 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))
6192 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
)
6194 GSList
*ns
= gts_vertex_neighbors(GTS_VERTEX(v
), NULL
, NULL
);
6199 toporouter_vertex_t
*n
= TOPOROUTER_VERTEX(i
->data
);
6200 gdouble segintx
, seginty
;
6201 if(vertex_line_normal_intersection(x0
, y0
, x1
, y1
, vx(n
), vy(n
), &segintx
, &seginty
)) {
6202 toporouter_edge_t
*e
= tedge(n
, v
);
6203 gdouble ms
= 0., d
= coord_distance(segintx
, seginty
, vx(n
), vy(n
));
6204 toporouter_vertex_t
*a
, *b
;
6205 GList
*closestnet
= NULL
;
6209 if(v
== tedge_v1(e
)) {
6212 closestnet
= edge_routing(e
);
6216 closestnet
= g_list_last(edge_routing(e
));
6220 ms
= edge_min_spacing(closestnet
, e
, b
, 0);
6221 ms
+= min_oproute_net_spacing(oproute
, TOPOROUTER_VERTEX(closestnet
->data
));
6223 ms
= min_oproute_vertex_spacing(oproute
, b
);
6230 if(vx(v
) == x0
&& vy(v
) == y0
) {
6231 *arcwind
= coord_wind(x0
, y0
, vx(n
), vy(n
), x1
, y1
);
6232 }else if(vx(v
) == x1
&& vy(v
) == y1
) {
6233 *arcwind
= coord_wind(x1
, y1
, vx(n
), vy(n
), x0
, y0
);
6235 fprintf(stderr
, "ERROR: check_adj_pushing_vertex encountered bad vertex v (coordinates don't match)\n");
6250 oproute_rubberband_segment(toporouter_t
*r
, toporouter_oproute_t
*oproute
, GList
*path
, gpointer t1
, gpointer t2
, guint debug
)
6252 gdouble x0
, y0
, x1
, y1
;
6253 toporouter_vertex_t
*v1
, *v2
, *av1
, *av2
; /* v{1,2} are the vertex terminals of the segment, or arc terminal centres */
6254 toporouter_arc_t
*arc1
= NULL
, *arc2
= NULL
, *newarc
= NULL
; /* arc{1,2} are the arc terminals of the segment, if they exist */
6256 GList
*list1
, *list2
;
6259 toporouter_rubberband_arc_t
*max
= NULL
;
6262 gint v1wind
, v2wind
, arcwind
;
6264 if(TOPOROUTER_IS_VERTEX(t1
)) {
6265 v1
= TOPOROUTER_VERTEX(t1
);
6266 x0
= vx(v1
); y0
= vy(v1
);
6268 g_assert(TOPOROUTER_IS_ARC(t1
));
6269 arc1
= TOPOROUTER_ARC(t1
);
6270 v1
= TOPOROUTER_VERTEX(arc1
->v1
);
6275 if(TOPOROUTER_IS_VERTEX(t2
)) {
6276 v2
= TOPOROUTER_VERTEX(t2
);
6277 x1
= vx(v2
); y1
= vy(v2
);
6279 g_assert(TOPOROUTER_IS_ARC(t2
));
6280 arc2
= TOPOROUTER_ARC(t2
);
6281 v2
= TOPOROUTER_VERTEX(arc2
->v2
);
6286 #define TEST_AND_INSERT(z) if(d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v, z, arcr, d, arcwind, i));
6287 #define ARC_CHECKS(z) (!(arc1 && arc1->centre == z) && !(arc2 && arc2->centre == z) && \
6288 !(TOPOROUTER_IS_VERTEX(t1) && z == v1) && !(TOPOROUTER_IS_VERTEX(t2) && z == v2))
6290 if(v1
== v2
|| !i
->next
|| TOPOROUTER_VERTEX(i
->data
) == v2
) return NULL
;
6292 //#ifdef DEBUG_RUBBERBAND
6294 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
));
6295 // if(v1->routingedge) print_edge(v1->routingedge);
6296 // if(v2->routingedge) print_edge(v2->routingedge);
6301 /* check the vectices adjacent to the terminal vectices for push against the segment */
6302 //if(TOPOROUTER_IS_VERTEX(t1)) {
6303 // toporouter_vertex_t *arcc = NULL;
6304 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v1, &arcr, &arcwind, &arcc);
6305 // g_assert(arcc != v1);
6306 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v1, arcc, arcr, d, arcwind, path->next));
6309 //if(TOPOROUTER_IS_VERTEX(t2)) {
6310 // toporouter_vertex_t *arcc = NULL;
6311 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v2, &arcr, &arcwind, &arcc);
6312 // g_assert(arcc != v2);
6313 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v2, arcc, arcr, d, arcwind, g_list_last(path)->prev));
6318 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6320 if(v
== v2
|| v
== v1
|| !v
->routingedge
) break;
6322 #ifdef DEBUG_RUBBERBAND
6324 // printf("current v %f,%f - edge %f,%f %f,%f\n", vx(v), vy(v),
6325 // vx(tedge_v1(v->routingedge)), vy(tedge_v1(v->routingedge)),
6326 // vx(tedge_v2(v->routingedge)), vy(tedge_v2(v->routingedge))
6329 g_assert(v
->routingedge
);
6331 v1wind
= coord_wind(x0
, y0
, x1
, y1
, vx(tedge_v1(v
->routingedge
)), vy(tedge_v1(v
->routingedge
)));
6332 v2wind
= coord_wind(x0
, y0
, x1
, y1
, vx(tedge_v2(v
->routingedge
)), vy(tedge_v2(v
->routingedge
)));
6333 // if(debug) printf("\twinds: %d %d\n", v1wind, v2wind);
6334 if(!v1wind
&& !v2wind
) { i
= i
->next
; continue; }
6337 if(v1wind
&& v2wind
&& v1wind
!= v2wind
) { /* edge is cutting through the current segment */
6339 if(ARC_CHECKS(tedge_v1(v
->routingedge
)) ){ /* edge v1 is not the centre of an arc terminal */
6340 d
= check_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v1(v
->routingedge
), tedge_v2(v
->routingedge
), v1wind
, &arcwind
, &arcr
, debug
);
6341 TEST_AND_INSERT(tedge_v1(v
->routingedge
));
6344 if(ARC_CHECKS(tedge_v2(v
->routingedge
)) ){ /* edge v2 is not the centre of an arc terminal */
6345 d
= check_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v2(v
->routingedge
), tedge_v1(v
->routingedge
), v2wind
, &arcwind
, &arcr
, debug
);
6346 TEST_AND_INSERT(tedge_v2(v
->routingedge
));
6348 }else{ /* edge is on one side of the segment */
6350 if(ARC_CHECKS(tedge_v1(v
->routingedge
)) ){ /* edge v1 is not the centre of an arc terminal */
6351 d
= check_non_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v1(v
->routingedge
), tedge_v2(v
->routingedge
), v1wind
, &arcwind
, &arcr
, debug
);
6352 TEST_AND_INSERT(tedge_v1(v
->routingedge
));
6355 if(ARC_CHECKS(tedge_v2(v
->routingedge
)) ){ /* edge v2 is not the centre of an arc terminal */
6356 d
= check_non_intersect_vertex(x0
, y0
, x1
, y1
, v
, tedge_v2(v
->routingedge
), tedge_v1(v
->routingedge
), v2wind
, &arcwind
, &arcr
, debug
);
6357 TEST_AND_INSERT(tedge_v2(v
->routingedge
));
6364 arcs
= g_list_sort(arcs
, (GCompareFunc
) compare_rubberband_arcs
);
6365 //rubberband_insert_maxarc:
6366 if(!arcs
) return NULL
;
6367 max
= TOPOROUTER_RUBBERBAND_ARC(arcs
->data
);
6369 av2
= max
->pathv
; i
= max
->list
->next
;
6371 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6372 if(v
->routingedge
&& (tedge_v1(v
->routingedge
) == max
->arcv
|| tedge_v2(v
->routingedge
) == max
->arcv
)) {
6373 av2
= v
; i
= i
->next
; continue;
6378 av1
= max
->pathv
; i
= max
->list
->prev
;
6380 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6381 if(v
->routingedge
&& (tedge_v1(v
->routingedge
) == max
->arcv
|| tedge_v2(v
->routingedge
) == max
->arcv
)) {
6382 av1
= v
; i
= i
->prev
; continue;
6386 //#ifdef DEBUG_RUBBERBAND
6388 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
);
6390 newarc
= toporouter_arc_new(oproute
, av1
, av2
, max
->arcv
, max
->r
, max
->wind
);
6392 if(TOPOROUTER_IS_VERTEX(t1
))
6393 calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), newarc
, 0);
6394 else if(calculate_arc_to_arc(r
, TOPOROUTER_ARC(t1
), newarc
)) {
6395 printf("\tERROR: best: r = %f d = %f\n", max
->r
, max
->d
);
6396 printf("\tOPROUTE: %s\n", oproute
->netlist
);
6397 print_vertex(oproute
->term1
);
6398 print_vertex(oproute
->term2
);
6402 if(TOPOROUTER_IS_VERTEX(t2
))
6403 calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), newarc
, 1);
6404 else if(calculate_arc_to_arc(r
, newarc
, TOPOROUTER_ARC(t2
))) {
6405 printf("\tERROR: best: r = %f d = %f\n", max
->r
, max
->d
);
6406 printf("\tOPROUTE: %s\n", oproute
->netlist
);
6407 print_vertex(oproute
->term1
);
6408 print_vertex(oproute
->term2
);
6412 //if(check_arc_for_loops(t1, newarc, t2)) {
6413 // if(arc1 && arc2) calculate_arc_to_arc(r, arc1, arc2);
6414 // else if(arc1) calculate_term_to_arc(TOPOROUTER_VERTEX(t2), arc1, 1);
6415 // else if(arc2) calculate_term_to_arc(TOPOROUTER_VERTEX(t1), arc2, 0);
6417 //#ifdef DEBUG_RUBBERBAND
6418 // printf("REMOVING NEW ARC @ %f,%f\n", vx(newarc->centre), vy(newarc->centre));
6419 // //TODO: properly remove newarc
6422 // arcs = g_list_remove(arcs, max);
6424 // goto rubberband_insert_maxarc;
6428 list1
= oproute_rubberband_segment(r
, oproute
, path
, t1
, newarc
, debug
);
6429 list2
= oproute_rubberband_segment(r
, oproute
, i
->next
, newarc
, t2
, debug
);
6432 GList
*list
= g_list_last(list1
);
6433 toporouter_arc_t
*testarc
= TOPOROUTER_ARC(list
->data
);
6434 toporouter_arc_t
*parc
= list
->prev
? TOPOROUTER_ARC(list
->prev
->data
) : arc1
;
6435 gdouble px
= parc
? parc
->x1
: vx(TOPOROUTER_VERTEX(t1
)), py
= parc
? parc
->y1
: vy(TOPOROUTER_VERTEX(t1
));
6437 if(coord_intersect_prop(px
, py
, testarc
->x0
, testarc
->y0
, testarc
->x1
, testarc
->y1
, newarc
->x0
, newarc
->y0
)) {
6438 list1
= g_list_remove(list1
, testarc
);
6439 if(parc
) calculate_arc_to_arc(r
, parc
, newarc
);
6440 else calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), newarc
, 0);
6441 //#ifdef DEBUG_RUBBERBAND
6443 printf("REMOVING ARC @ %f,%f\n", vx(testarc
->centre
), vy(testarc
->centre
));
6448 toporouter_arc_t
*testarc
= TOPOROUTER_ARC(list2
->data
);
6449 toporouter_arc_t
*narc
= list2
->next
? TOPOROUTER_ARC(list2
->next
->data
) : arc2
;
6450 gdouble nx
= narc
? narc
->x0
: vx(TOPOROUTER_VERTEX(t2
)), ny
= narc
? narc
->y0
: vy(TOPOROUTER_VERTEX(t2
));
6452 if(coord_intersect_prop(newarc
->x1
, newarc
->y1
, testarc
->x0
, testarc
->y0
, testarc
->x1
, testarc
->y1
, nx
, ny
)) {
6453 list2
= g_list_remove(list2
, testarc
);
6454 if(narc
) calculate_arc_to_arc(r
, newarc
, narc
);
6455 else calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), newarc
, 1);
6457 //#ifdef DEBUG_RUBBERBAND
6459 printf("REMOVING ARC @ %f,%f\n", vx(testarc
->centre
), vy(testarc
->centre
));
6464 g_list_foreach(arcs
, free_list_elements
, NULL
);
6467 return g_list_concat(list1
, g_list_prepend(list2
, newarc
));
6471 oproute_check_all_loops(toporouter_t
*r
, toporouter_oproute_t
*oproute
)
6477 t1
= oproute
->term1
;
6480 toporouter_arc_t
*arc
= TOPOROUTER_ARC(i
->data
);
6481 gpointer t2
= i
->next
? i
->next
->data
: oproute
->term2
;
6483 if(check_arc_for_loops(t1
, arc
, t2
)) {
6485 if(TOPOROUTER_IS_ARC(t1
) && TOPOROUTER_IS_ARC(t2
))
6486 calculate_arc_to_arc(r
, TOPOROUTER_ARC(t1
), TOPOROUTER_ARC(t2
));
6487 else if(TOPOROUTER_IS_ARC(t1
))
6488 calculate_term_to_arc(TOPOROUTER_VERTEX(t2
), TOPOROUTER_ARC(t1
), 1);
6489 else if(TOPOROUTER_IS_ARC(t2
))
6490 calculate_term_to_arc(TOPOROUTER_VERTEX(t1
), TOPOROUTER_ARC(t2
), 0);
6492 oproute
->arcs
= g_list_remove(oproute
->arcs
, arc
);
6493 goto loopcheck_restart
;
6504 opposite_triangle(GtsTriangle
*t
, toporouter_edge_t
*e
)
6506 GSList
*i
= GTS_EDGE(e
)->triangles
;
6511 if(GTS_TRIANGLE(i
->data
) != t
) return GTS_TRIANGLE(i
->data
);
6520 speccut_edge_routing_from_edge(GList
*i
, toporouter_edge_t
*e
)
6522 g_assert(TOPOROUTER_IS_EDGE(e
));
6524 toporouter_vertex_t
*curv
= TOPOROUTER_VERTEX(i
->data
);
6526 if(!(curv
->flags
& VERTEX_FLAG_TEMP
)) {
6527 toporouter_vertex_t
*newv
= tvertex_intersect(curv
, curv
->parent
, tedge_v1(e
), tedge_v2(e
));
6529 // printf("\nCURV:\n");
6530 // print_vertex(curv);
6532 // printf("CURV child:\n");
6534 // print_vertex(curv->child);
6536 // printf("NULL\n");
6538 // printf("CURV parent:\n");
6540 // print_vertex(curv->parent);
6542 // printf("NULL\n");
6546 newv
->flags
|= VERTEX_FLAG_ROUTE
;
6547 newv
->flags
|= VERTEX_FLAG_SPECCUT
;
6548 e
->routing
= g_list_insert_sorted_with_data(e
->routing
, newv
, routing_edge_insert
, e
);
6549 newv
->route
= curv
->route
;
6550 newv
->oproute
= curv
->oproute
;
6551 newv
->routingedge
= e
;
6552 GTS_POINT(newv
)->z
= vz(curv
);
6554 newv
->parent
= curv
->parent
;
6557 // curv->parent = newv;
6559 index
= g_list_index(newv
->route
->path
, curv
);
6561 newv
->route
->path
= g_list_insert(newv
->route
->path
, newv
, index
);
6564 if(newv
->oproute
) newv
->oproute
->path
= newv
->route
->path
;
6567 if(!(curv
->child
->routingedge
)) {
6568 newv
= tvertex_intersect(curv
, curv
->child
, tedge_v1(e
), tedge_v2(e
));
6572 newv
->flags
|= VERTEX_FLAG_ROUTE
;
6573 newv
->flags
|= VERTEX_FLAG_SPECCUT
;
6574 e
->routing
= g_list_insert_sorted_with_data(e
->routing
, newv
, routing_edge_insert
, e
);
6575 newv
->route
= curv
->route
;
6576 newv
->oproute
= curv
->oproute
;
6577 newv
->routingedge
= e
;
6578 GTS_POINT(newv
)->z
= vz(curv
);
6580 newv
->parent
= curv
;
6581 newv
->child
= curv
->child
;
6583 // curv->child = newv;
6585 index
= g_list_index(newv
->route
->path
, curv
);
6587 newv
->route
->path
= g_list_insert(newv
->route
->path
, newv
, index
+1);
6590 if(newv
->oproute
) newv
->oproute
->path
= newv
->route
->path
;
6602 speccut_edge_patch_links(toporouter_edge_t
*e
)
6604 GList
*i
= e
->routing
;
6605 g_assert(TOPOROUTER_IS_EDGE(e
));
6607 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6608 v
->parent
->child
= v
;
6609 v
->child
->parent
= v
;
6615 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
)
6617 GtsTriangle
*t
, *opt
;
6618 toporouter_vertex_t
*opv
, *opv2
;
6619 toporouter_edge_t
*ope1
, *ope2
;
6620 gdouble cap
, flow
, line_int_x
, line_int_y
;
6622 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
6624 if(!(t
= gts_triangle_use_edges(GTS_EDGE(e
), GTS_EDGE(e1
), GTS_EDGE(e2
)))) {
6625 printf("check_speccut: NULL t\n");
6629 if(!(opt
= opposite_triangle(t
, e
))) {
6630 // printf("check_speccut: NULL opt\n");
6634 if(!(opv
= segment_common_vertex(GTS_SEGMENT(e1
), GTS_SEGMENT(e2
)))) {
6635 printf("check_speccut: NULL opv\n");
6639 if(!(opv2
= TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(opt
, GTS_EDGE(e
))))) {
6640 printf("check_speccut: NULL opv2\n");
6644 //TODO: shifting it out of the way would be better
6646 GList
*i
= e
->routing
;
6648 toporouter_vertex_t
*ev
= TOPOROUTER_VERTEX(i
->data
);
6649 if(!tvertex_wind(opv
, ev
, opv2
)) return 0;
6655 ope1
= tedge(opv2
, tedge_v1(e
));
6656 ope2
= tedge(opv2
, tedge_v2(e
));
6658 //this fixes the weird pad exits in r8c board
6659 // if(TOPOROUTER_IS_CONSTRAINT(ope1)) return 0;
6660 if(TOPOROUTER_IS_CONSTRAINT(ope2
)) return 0;
6662 if(!tvertex_wind(opv2
, tedge_v1(e
), opv
)) return 0;
6663 if(!tvertex_wind(opv2
, tedge_v2(e
), opv
)) return 0;
6665 if(!vertex_line_normal_intersection(
6666 vx(tedge_v1(e
)), vy(tedge_v1(e
)),
6667 vx(tedge_v2(e
)), vy(tedge_v2(e
)),
6669 &line_int_x
, &line_int_y
)) return 0;
6673 //if(vertex_line_normal_intersection(tev1x(e), tev1y(e), tev2x(e), tev2y(e), vx(opv), vy(opv), &line_int_x, &line_int_y))
6676 g_assert(opt
&& opv2
);
6678 /* this is just temp, for the purposes of determining flow */
6679 if(tedge_v1(ope1
) == opv2
) {
6680 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6681 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_append(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6683 ope1
->routing
= g_list_append(ope1
->routing
, v1
);
6685 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6686 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_prepend(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6688 ope1
->routing
= g_list_prepend(ope1
->routing
, v1
);
6691 cap
= triangle_interior_capacity(opt
, opv2
);
6692 flow
= flow_from_edge_to_edge(opt
, tedge(opv2
, tedge_v1(e
)), tedge(opv2
, tedge_v2(e
)), opv2
, v1
);
6694 /* temp v1 removed */
6695 if(TOPOROUTER_IS_CONSTRAINT(ope1
))
6696 TOPOROUTER_CONSTRAINT(ope1
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(ope1
)->routing
, v1
);
6698 ope1
->routing
= g_list_remove(ope1
->routing
, v1
);
6701 toporouter_edge_t
*newe
= TOPOROUTER_EDGE(gts_edge_new(GTS_EDGE_CLASS(toporouter_edge_class()), GTS_VERTEX(opv
), GTS_VERTEX(opv2
)));
6703 speccut_edge_routing_from_edge(edge_routing(e1
), newe
);
6704 speccut_edge_routing_from_edge(edge_routing(e2
), newe
);
6705 speccut_edge_routing_from_edge(edge_routing(ope1
), newe
);
6706 speccut_edge_routing_from_edge(edge_routing(ope2
), newe
);
6708 speccut_edge_patch_links(newe
);
6710 printf("SPECCUT WITH v %f,%f for seg %f,%f %f,%f detected\n", vx(opv2), vy(opv2),
6713 printf("\tflow %f cap %f\n", flow, cap);
6716 if(newe
->routing
) return 1;
6725 oproute_path_speccut(toporouter_oproute_t
*oproute
)
6728 toporouter_vertex_t
*pv
;
6729 path_speccut_restart
:
6733 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
6736 if(pv
&& (v
->routingedge
|| pv
->routingedge
) && !(pv
->flags
& VERTEX_FLAG_SPECCUT
) && !(v
->flags
& VERTEX_FLAG_SPECCUT
)) {
6738 if(!v
->routingedge
) {
6739 if(check_speccut(oproute
, pv
, v
, tedge(tedge_v1(pv
->routingedge
), v
), pv
->routingedge
, tedge(tedge_v2(pv
->routingedge
), v
)))
6740 goto path_speccut_restart
;
6741 if(check_speccut(oproute
, pv
, v
, tedge(tedge_v2(pv
->routingedge
), v
), pv
->routingedge
, tedge(tedge_v1(pv
->routingedge
), v
)))
6742 goto path_speccut_restart
;
6743 }else if(!pv
->routingedge
) {
6744 if(check_speccut(oproute
, v
, pv
, tedge(tedge_v1(v
->routingedge
), pv
), v
->routingedge
, tedge(tedge_v2(v
->routingedge
), pv
)))
6745 goto path_speccut_restart
;
6746 if(check_speccut(oproute
, v
, pv
, tedge(tedge_v2(v
->routingedge
), pv
), v
->routingedge
, tedge(tedge_v1(v
->routingedge
), pv
)))
6747 goto path_speccut_restart
;
6749 toporouter_vertex_t
*v1
= NULL
, *v2
= NULL
;
6750 edges_third_edge(GTS_SEGMENT(v
->routingedge
), GTS_SEGMENT(pv
->routingedge
), &v1
, &v2
);
6751 if(check_speccut(oproute
, v
, pv
, tedge(v1
, v2
), v
->routingedge
, pv
->routingedge
))
6752 goto path_speccut_restart
;
6764 toporouter_oproute_t
*
6765 oproute_rubberband(toporouter_t
*r
, GList
*path
)
6767 toporouter_oproute_t
*oproute
= malloc(sizeof(toporouter_oproute_t
));
6771 oproute
->term1
= TOPOROUTER_VERTEX(path
->data
);
6772 oproute
->term2
= TOPOROUTER_VERTEX(g_list_last(path
)->data
);
6773 oproute
->arcs
= NULL
;
6774 oproute
->style
= vertex_bbox(oproute
->term1
)->cluster
->netlist
->style
;
6775 oproute
->netlist
= vertex_bbox(oproute
->term1
)->cluster
->netlist
->netlist
;
6776 oproute
->layergroup
= vz(oproute
->term1
);
6777 oproute
->path
= path
;
6778 oproute
->serp
= NULL
;
6780 oproute
->term1
->parent
= NULL
;
6781 oproute
->term2
->child
= NULL
;
6783 path_set_oproute(path
, oproute
);
6785 // if(!strcmp(oproute->netlist, " unnamed_net1"))
6786 oproute_path_speccut(oproute
);
6788 #ifdef DEBUG_RUBBERBAND
6789 if(!strcmp(oproute
->netlist
, " VCC3V3") && vx(oproute
->term1
) == 95700. && vy(oproute
->term1
) == 70800. &&
6790 vx(oproute
->term2
) == 196700. && vy(oproute
->term2
) == 67300.)
6792 // printf("OPROUTE %s - %f,%f %f,%f\n", oproute->netlist, vx(oproute->term1), vy(oproute->term1), vx(oproute->term2), vy(oproute->term2));
6793 // print_path(path);
6794 oproute
->arcs
= oproute_rubberband_segment(r
, oproute
, path
, oproute
->term1
, oproute
->term2
, 1);
6797 oproute
->arcs
= oproute_rubberband_segment(r
, oproute
, path
, oproute
->term1
, oproute
->term2
, 0);
6799 oproute_check_all_loops(r
, oproute
);
6805 toporouter_export(toporouter_t
*r
)
6807 GList
*i
= r
->routednets
;
6808 GList
*oproutes
= NULL
;
6811 toporouter_route_t
*routedata
= TOPOROUTER_ROUTE(i
->data
);
6812 toporouter_oproute_t
*oproute
= oproute_rubberband(r
, routedata
->path
);
6813 oproutes
= g_list_prepend(oproutes
, oproute
);
6819 toporouter_oproute_t
*oproute
= (toporouter_oproute_t
*) i
->data
;
6820 export_oproutes(r
, oproute
);
6821 oproute_free(oproute
);
6825 Message(_("Reticulating splines... successful\n\n"));
6826 Message(_("Wiring cost: %f inches\n"), r
->wiring_score
/ 1000.);
6827 printf("Wiring cost: %f inches\n", r
->wiring_score
/ 1000.);
6829 g_list_free(oproutes
);
6833 toporouter_route_t
*
6834 routedata_create(void)
6836 toporouter_route_t
*routedata
= malloc(sizeof(toporouter_route_t
));
6837 routedata
->netlist
= NULL
;
6838 routedata
->alltemppoints
= NULL
;
6839 routedata
->path
= NULL
;
6840 routedata
->curpoint
= NULL
;
6841 routedata
->pscore
= routedata
->score
= 0.;
6842 routedata
->flags
= 0;
6843 routedata
->src
= routedata
->dest
= NULL
;
6844 routedata
->psrc
= routedata
->pdest
= NULL
;
6845 routedata
->ppath
= routedata
->topopath
= NULL
;
6847 routedata
->ppathindices
= NULL
;
6849 routedata
->destvertices
= routedata
->srcvertices
= NULL
;
6854 print_routedata(toporouter_route_t *routedata)
6856 GList *srcvertices = cluster_vertices(routedata->src);
6857 GList *destvertices = cluster_vertices(routedata->dest);
6859 printf("ROUTEDATA:\n");
6860 printf("SRCVERTICES:\n");
6861 print_vertices(srcvertices);
6862 printf("DESTVERTICES:\n");
6863 print_vertices(destvertices);
6865 g_list_free(srcvertices);
6866 g_list_free(destvertices);
6869 toporouter_route_t
*
6870 import_route(toporouter_t
*r
, RatType
*line
)
6872 toporouter_route_t
*routedata
= routedata_create();
6874 routedata
->src
= cluster_find(r
, line
->Point1
.X
, line
->Point1
.Y
, line
->group1
);
6875 routedata
->dest
= cluster_find(r
, line
->Point2
.X
, line
->Point2
.Y
, line
->group2
);
6877 if(!routedata
->src
) printf("couldn't locate src\n");
6878 if(!routedata
->dest
) printf("couldn't locate dest\n");
6880 if(!routedata
->src
|| !routedata
->dest
) {
6881 printf("PROBLEM: couldn't locate rat src or dest for rat %d,%d,%d -> %d,%d,%d\n",
6882 line
->Point1
.X
, line
->Point1
.Y
, line
->group1
, line
->Point2
.X
, line
->Point2
.Y
, line
->group2
);
6887 routedata
->netlist
= routedata
->src
->netlist
;
6889 g_assert(routedata
->src
->netlist
== routedata
->dest
->netlist
);
6891 g_ptr_array_add(r
->routes
, routedata
);
6892 g_ptr_array_add(routedata
->netlist
->routes
, routedata
);
6894 r
->failednets
= g_list_prepend(r
->failednets
, routedata
);
6900 delete_route(toporouter_route_t
*routedata
, guint destroy
)
6902 GList
*i
= routedata
->path
;
6903 toporouter_vertex_t
*pv
= NULL
;
6906 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6910 if(tv
&& pv
&& !(tv
->flags
& VERTEX_FLAG_ROUTE
) && !(pv
->flags
& VERTEX_FLAG_ROUTE
)) {
6911 toporouter_edge_t
*e
= TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(tv
), GTS_VERTEX(pv
)));
6913 if(e
&& (e
->flags
& EDGE_FLAG_DIRECTCONNECTION
)) {
6914 e
->flags
^= EDGE_FLAG_DIRECTCONNECTION
;
6921 i
= routedata
->path
;
6923 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6928 if(tv
->routingedge
) {
6929 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6930 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
6932 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
6933 if(destroy
) gts_object_destroy ( GTS_OBJECT(tv
) );
6939 if(routedata
->path
) g_list_free(routedata
->path
);
6940 routedata
->path
= NULL
;
6941 routedata
->curpoint
= NULL
;
6942 routedata
->score
= INFINITY
;
6943 routedata
->alltemppoints
= NULL
;
6946 /* remove route can be later reapplied */
6948 remove_route(GList
*path
)
6953 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6958 // if(tv->flags & VERTEX_FLAG_ROUTE) g_assert(tv->route == routedata);
6960 if(tv
->routingedge
) {
6962 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6963 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
, tv
);
6965 tv
->routingedge
->routing
= g_list_remove(tv
->routingedge
->routing
, tv
);
6973 apply_route(GList
*path
, toporouter_route_t
*routedata
)
6976 toporouter_vertex_t
*pv
= NULL
;
6983 toporouter_vertex_t
*tv
= TOPOROUTER_VERTEX(i
->data
);
6985 if(tv
->routingedge
) {
6986 if(TOPOROUTER_IS_CONSTRAINT(tv
->routingedge
))
6987 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
= g_list_insert_sorted_with_data(
6988 TOPOROUTER_CONSTRAINT(tv
->routingedge
)->routing
,
6990 routing_edge_insert
,
6993 tv
->routingedge
->routing
= g_list_insert_sorted_with_data(
6994 tv
->routingedge
->routing
,
6996 routing_edge_insert
,
7007 if(tv
->flags
& VERTEX_FLAG_ROUTE
) g_assert(tv
->route
== routedata
);
7013 TOPOROUTER_VERTEX(path
->data
)->parent
= NULL
;
7021 compare_routedata_ascending(gconstpointer a
, gconstpointer b
)
7023 toporouter_route_t
*ra
= (toporouter_route_t
*)a
;
7024 toporouter_route_t
*rb
= (toporouter_route_t
*)b
;
7025 return ra
->score
- rb
->score
;
7029 print_costmatrix(gdouble
*m
, guint n
)
7031 printf("COST MATRIX:\n");
7032 for(guint i
= 0;i
<n
;i
++) {
7033 for(guint j
= 0;j
<n
;j
++) {
7034 printf("%f ", m
[(i
*n
)+j
]);
7042 init_cost_matrix(gdouble
*m
, guint n
)
7044 for(guint i
=0;i
<n
;i
++) {
7045 for(guint j
=0;j
<n
;j
++) {
7046 m
[(i
*n
)+j
] = INFINITY
;
7052 toporouter_netscore_t
*
7053 netscore_create(toporouter_t
*r
, toporouter_route_t
*routedata
, guint n
, guint id
)
7055 toporouter_netscore_t
*netscore
= malloc(sizeof(toporouter_netscore_t
));
7056 GList
*path
= route(r
, routedata
, 0);
7060 netscore
->routedata
= routedata
;
7061 routedata
->detourscore
= netscore
->score
= routedata
->score
;
7063 if(!finite(routedata
->detourscore
)) {
7064 printf("WARNING: !finite(detourscore)\n");
7065 print_cluster(routedata
->src
);
7066 print_cluster(routedata
->dest
);
7070 netscore
->pairwise_nodetour
= malloc(n
* sizeof(guint
));
7072 for(guint i
=0;i
<n
;i
++) {
7073 netscore
->pairwise_nodetour
[i
] = 0;
7076 netscore
->pairwise_detour_sum
= 0.;
7077 netscore
->pairwise_fails
= 0;
7082 routedata
->topopath
= g_list_copy(routedata
->path
);
7083 delete_route(routedata
, 0);
7090 netscore_destroy(toporouter_netscore_t
*netscore
)
7092 free(netscore
->pairwise_nodetour
);
7097 print_netscores(GPtrArray
* netscores
)
7099 printf("NETSCORES: \n\n");
7100 printf(" %15s %15s %15s\n----------------------------------------------------\n", "Score", "Detour Sum", "Pairwise Fails");
7102 for(toporouter_netscore_t
**i
= (toporouter_netscore_t
**) netscores
->pdata
; i
< (toporouter_netscore_t
**) netscores
->pdata
+ netscores
->len
; i
++) {
7103 #ifdef DEBUG_NETSCORES
7104 printf("%4d %15f %15f %15d %15x\n", (*i
)->id
, (*i
)->score
, (*i
)->pairwise_detour_sum
, (*i
)->pairwise_fails
, (guint
)*i
);
7112 netscore_pairwise_calculation(toporouter_netscore_t
*netscore
, GPtrArray
*netscores
)
7114 toporouter_netscore_t
**netscores_base
= (toporouter_netscore_t
**) (netscores
->pdata
);
7115 toporouter_route_t
*temproutedata
= routedata_create();
7117 //route(netscore->r, netscore->routedata, 0);
7118 apply_route(netscore
->routedata
->topopath
, netscore
->routedata
);
7120 for(toporouter_netscore_t
**i
= netscores_base
; i
< netscores_base
+ netscores
->len
; i
++) {
7122 if(!netscore
->pairwise_nodetour
[i
-netscores_base
] && *i
!= netscore
&& (*i
)->routedata
->netlist
!= netscore
->routedata
->netlist
) {
7124 temproutedata
->src
= (*i
)->routedata
->src
;
7125 temproutedata
->dest
= (*i
)->routedata
->dest
;
7127 route(netscore
->r
, temproutedata
, 0);
7129 if(temproutedata
->score
== (*i
)->score
) {
7130 netscore
->pairwise_nodetour
[i
-netscores_base
] = 1;
7131 (*i
)->pairwise_nodetour
[netscore
->id
] = 1;
7133 if(!finite(temproutedata
->score
)) {
7134 netscore
->pairwise_fails
+= 1;
7136 netscore
->pairwise_detour_sum
+= temproutedata
->score
- (*i
)->score
;
7139 delete_route(temproutedata
, 1);
7144 // delete_route(netscore->routedata, 1);
7145 remove_route(netscore
->routedata
->topopath
);
7147 free(temproutedata
);
7151 netscore_pairwise_size_compare(toporouter_netscore_t
**a
, toporouter_netscore_t
**b
)
7153 // infinite scores are last
7154 if(!finite((*a
)->score
) && !finite((*b
)->score
)) return 0;
7155 if(finite((*a
)->score
) && !finite((*b
)->score
)) return -1;
7156 if(finite((*b
)->score
) && !finite((*a
)->score
)) return 1;
7158 // order by pairwise fails
7159 if((*a
)->pairwise_fails
< (*b
)->pairwise_fails
) return -1;
7160 if((*b
)->pairwise_fails
< (*a
)->pairwise_fails
) return 1;
7162 // order by pairwise detour
7163 if((*a
)->pairwise_detour_sum
< (*b
)->pairwise_detour_sum
) return -1;
7164 if((*b
)->pairwise_detour_sum
< (*a
)->pairwise_detour_sum
) return 1;
7167 if((*a
)->score
< (*b
)->score
) return -1;
7168 if((*b
)->score
< (*a
)->score
) return 1;
7174 netscore_pairwise_compare(toporouter_netscore_t
**a
, toporouter_netscore_t
**b
)
7176 // infinite scores are last
7177 if(!finite((*a
)->score
) && !finite((*b
)->score
)) return 0;
7178 if(finite((*a
)->score
) && !finite((*b
)->score
)) return -1;
7179 if(finite((*b
)->score
) && !finite((*a
)->score
)) return 1;
7181 // order by pairwise fails
7182 if((*a
)->pairwise_fails
< (*b
)->pairwise_fails
) return -1;
7183 if((*b
)->pairwise_fails
< (*a
)->pairwise_fails
) return 1;
7185 // order by pairwise detour
7186 if((*a
)->pairwise_detour_sum
< (*b
)->pairwise_detour_sum
) return -1;
7187 if((*b
)->pairwise_detour_sum
< (*a
)->pairwise_detour_sum
) return 1;
7193 order_nets_preroute_greedy(toporouter_t
*r
, GList
*nets
, GList
**rnets
)
7195 gint len
= g_list_length(nets
);
7196 GPtrArray
* netscores
= g_ptr_array_sized_new(len
);
7197 guint failcount
= 0;
7200 toporouter_netscore_t
*ns
= netscore_create(r
, TOPOROUTER_ROUTE(nets
->data
), len
, failcount
++);
7201 if(ns
) g_ptr_array_add(netscores
, ns
);
7207 g_ptr_array_foreach(netscores
, (GFunc
) netscore_pairwise_calculation
, netscores
);
7209 g_ptr_array_sort(netscores
, (GCompareFunc
) r
->netsort
);
7211 #ifdef DEBUG_ORDERING
7212 print_netscores(netscores
);
7216 FOREACH_NETSCORE(netscores
) {
7217 *rnets
= g_list_prepend(*rnets
, netscore
->routedata
);
7218 if(!finite(netscore
->score
)) failcount
++;
7219 netscore_destroy(netscore
);
7222 g_ptr_array_free(netscores
, TRUE
);
7227 toporouter_vertex_t
*
7228 edge_closest_vertex(toporouter_edge_t
*e
, toporouter_vertex_t
*v
)
7230 GList
*i
= v
->routingedge
? edge_routing(v
->routingedge
) : NULL
;
7231 gdouble closestd
= 0.;
7232 toporouter_vertex_t
*closestv
= NULL
;
7235 toporouter_vertex_t
*ev
= TOPOROUTER_VERTEX(i
->data
);
7236 gdouble tempd
= gts_point_distance2(GTS_POINT(ev
), GTS_POINT(v
));
7238 if(!closestv
|| (tempd
< closestd
)) {
7250 snapshot(toporouter_t
*r
, char *name
, GList
*datas
)
7255 for(i
=0;i
<groupcount();i
++) {
7257 sprintf(buffer
, "route-%s-%d.png", name
, i
);
7258 toporouter_draw_surface(r
, r
->layers
[i
].surface
, buffer
, 2048, 2048, 2, datas
, i
, NULL
);
7266 route_conflict(toporouter_t *r, toporouter_route_t *route, guint *n)
7268 GList *i = route->path;
7269 toporouter_vertex_t *pv = NULL;
7273 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
7274 if(pv && vz(v) == vz(pv))
7275 cost += vertices_routing_conflict_cost(r, v, pv, n);
7284 route_conflicts(toporouter_route_t
*route
)
7286 GList
*conflicts
= NULL
, *i
= route
->path
;
7287 toporouter_vertex_t
*pv
= NULL
;
7290 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7292 if(pv
&& vz(pv
) == vz(v
)) {
7293 GList
*temp
= vertices_routing_conflicts(pv
, v
), *j
;
7297 toporouter_route_t
*conroute
= TOPOROUTER_ROUTE(j
->data
);
7298 if(!g_list_find(conflicts
, conroute
))
7299 conflicts
= g_list_prepend(conflicts
, conroute
);
7303 if(temp
) g_list_free(temp
);
7313 spread_edge(gpointer item
, gpointer data
)
7315 toporouter_edge_t
*e
= TOPOROUTER_EDGE(item
);
7316 toporouter_vertex_t
*v
;
7320 if(TOPOROUTER_IS_CONSTRAINT(e
)) return 0;
7322 i
= edge_routing(e
);
7324 if(!g_list_length(i
)) return 0;
7326 if(g_list_length(i
) == 1) {
7327 v
= TOPOROUTER_VERTEX(i
->data
);
7328 GTS_POINT(v
)->x
= (vx(edge_v1(e
)) + vx(edge_v2(e
))) / 2.;
7329 GTS_POINT(v
)->y
= (vy(edge_v1(e
)) + vy(edge_v2(e
))) / 2.;
7333 s
= spacing
= (gts_point_distance(GTS_POINT(edge_v1(e
)), GTS_POINT(edge_v2(e
))) ) / (g_list_length(i
) + 1);
7336 v
= TOPOROUTER_VERTEX(i
->data
);
7337 vertex_move_towards_vertex_values(edge_v1(e
), edge_v2(e
), s
, &(GTS_POINT(v
)->x
), &(GTS_POINT(v
)->y
));
7347 route_checkpoint(toporouter_route_t
*route
, toporouter_route_t
*temproute
)
7349 GList
*i
= g_list_last(route
->path
);
7350 gint n
= g_list_length(route
->path
);
7352 if(route
->ppathindices
) free(route
->ppathindices
);
7353 route
->ppathindices
= malloc(sizeof(gint
)*n
);
7357 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7360 if(v
->routingedge
) {
7361 GList
*j
= g_list_find(edge_routing(v
->routingedge
), v
)->prev
;
7362 gint tempindex
= g_list_index(edge_routing(v
->routingedge
), v
);
7365 if(TOPOROUTER_VERTEX(j
->data
)->route
== temproute
) tempindex
--;
7369 route
->ppathindices
[n
] = tempindex
;
7371 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
7372 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_remove(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
);
7374 v
->routingedge
->routing
= g_list_remove(v
->routingedge
->routing
, v
);
7380 route
->pscore
= route
->score
;
7381 route
->ppath
= route
->path
;
7382 remove_route(route
->path
);
7384 route
->psrc
= route
->src
;
7385 route
->pdest
= route
->dest
;
7386 //route->src->pc = route->src->c;
7387 //route->dest->pc = route->dest->c;
7391 route_restore(toporouter_route_t
*route
)
7394 toporouter_vertex_t
*pv
= NULL
;
7397 g_assert(route
->ppath
);
7398 g_assert(route
->ppathindices
);
7400 route
->path
= route
->ppath
;
7403 toporouter_vertex_t
*v
= TOPOROUTER_VERTEX(i
->data
);
7405 if(v
->routingedge
) {
7406 if(TOPOROUTER_IS_CONSTRAINT(v
->routingedge
))
7407 TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
= g_list_insert(TOPOROUTER_CONSTRAINT(v
->routingedge
)->routing
, v
, route
->ppathindices
[n
]);
7409 v
->routingedge
->routing
= g_list_insert(v
->routingedge
->routing
, v
, route
->ppathindices
[n
]);
7411 // space_edge(v->routingedge, NULL);
7424 route
->score
= route
->pscore
;
7425 route
->src
= route
->psrc
;
7426 route
->dest
= route
->pdest
;
7427 //route->src->c = route->src->pc;
7428 //route->dest->c = route->dest->pc;
7433 cluster_merge(toporouter_route_t
*routedata
)
7435 gint oldc
= routedata
->dest
->c
, newc
= routedata
->src
->c
;
7437 FOREACH_CLUSTER(routedata
->netlist
->clusters
) {
7438 if(cluster
->c
== oldc
)
7445 netlist_recalculate(toporouter_netlist_t
*netlist
, GList
*ignore
)
7447 GList
*i
= g_list_last(netlist
->routed
);
7448 gint n
= netlist
->clusters
->len
-1;
7450 FOREACH_CLUSTER(netlist
->clusters
) {
7455 if(!ignore
|| !g_list_find(ignore
, i
->data
)) cluster_merge(TOPOROUTER_ROUTE(i
->data
));
7462 netlists_recalculate(GList
*netlists
, GList
*ignore
)
7464 GList
*i
= netlists
;
7466 netlist_recalculate(TOPOROUTER_NETLIST(i
->data
), ignore
);
7472 netlists_rollback(GList
*netlists
)
7474 // netlists_recalculate(netlists, NULL);
7476 toporouter_netlist_t
*netlist
= TOPOROUTER_NETLIST(netlists
->data
);
7478 FOREACH_CLUSTER(netlist
->clusters
) {
7479 cluster
->c
= cluster
->pc
;
7482 netlists
= netlists
->next
;
7487 print_netlist(toporouter_netlist_t
*netlist
)
7490 printf("NETLIST %s: ", netlist
->netlist
);
7492 FOREACH_CLUSTER(netlist
->clusters
) {
7493 printf("%d ", cluster
->c
);
7499 #define REMOVE_ROUTING(x) x->netlist->routed = g_list_remove(x->netlist->routed, x); \
7500 r->routednets = g_list_remove(r->routednets, x); \
7501 r->failednets = g_list_prepend(r->failednets, x)
7503 #define INSERT_ROUTING(x) x->netlist->routed = g_list_prepend(x->netlist->routed, x); \
7504 r->routednets = g_list_prepend(r->routednets, x); \
7505 r->failednets = g_list_remove(r->failednets, x)
7508 roar_route(toporouter_t
*r
, toporouter_route_t
*routedata
, gint threshold
)
7511 GList
*netlists
= NULL
, *routed
= NULL
;
7513 g_assert(!routedata
->path
);
7515 if(routedata
->src
->c
== routedata
->dest
->c
) {
7516 printf("ERROR: attempt to route already complete route\n");
7517 g_assert(routedata
->src
->c
!= routedata
->dest
->c
);
7520 routedata
->src
->pc
= routedata
->src
->c
;
7521 routedata
->dest
->pc
= routedata
->dest
->c
;
7522 routedata
->psrc
= routedata
->src
;
7523 routedata
->pdest
= routedata
->dest
;
7525 r
->flags
|= TOPOROUTER_FLAG_LEASTINVALID
;
7526 if(route(r
, routedata
, 0)) {
7527 GList
*conflicts
, *j
;
7529 INSERT_ROUTING(routedata
);
7531 conflicts
= route_conflicts(routedata
);
7532 cluster_merge(routedata
);
7534 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7538 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7539 if(!g_list_find(netlists
, conflict
->netlist
))
7540 netlists
= g_list_prepend(netlists
, conflict
->netlist
);
7542 route_checkpoint(conflict
, routedata
);
7544 REMOVE_ROUTING(conflict
);
7548 netlists
= g_list_prepend(netlists
, routedata
->netlist
);
7549 netlists_recalculate(netlists
, NULL
);
7553 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7554 g_assert(conflict
->src
->c
!= conflict
->dest
->c
);
7555 if(route(r
, conflict
, 0)) {
7556 cluster_merge(conflict
);
7558 routed
= g_list_prepend(routed
, conflict
);
7560 INSERT_ROUTING(conflict
);
7562 netlist_recalculate(conflict
->netlist
, NULL
);
7565 if(++intfails
>= threshold
) {
7568 toporouter_route_t
*intconflict
= TOPOROUTER_ROUTE(i
->data
);
7569 REMOVE_ROUTING(intconflict
);
7570 delete_route(intconflict
, 1);
7573 delete_route(routedata
, 1);
7574 i
= g_list_last(conflicts
);
7576 toporouter_route_t
*intconflict
= TOPOROUTER_ROUTE(i
->data
);
7578 route_restore(intconflict
);
7579 INSERT_ROUTING(intconflict
);
7583 REMOVE_ROUTING(routedata
);
7585 netlists_recalculate(netlists
, NULL
);
7586 goto roar_route_end
;
7594 netlists_recalculate(netlists
, NULL
);
7598 g_list_free(conflicts
);
7599 g_list_free(netlists
);
7602 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7605 g_list_free(routed
);
7610 roar_router(toporouter_t
*r
, gint failcount
, gint threshold
)
7612 gint pfailcount
= failcount
+1;
7614 Message(_("ROAR router: "));
7615 for(guint j
=0;j
<6;j
++) {
7616 GList
*failed
= g_list_copy(r
->failednets
), *k
= failed
;
7620 failcount
+= roar_route(r
, TOPOROUTER_ROUTE(k
->data
), threshold
);
7623 g_list_free(failed
);
7625 printf("\tROAR pass %d - %d routed - %d failed\n", j
, g_list_length(r
->routednets
), g_list_length(r
->failednets
));
7627 if(!failcount
|| failcount
>= pfailcount
) {
7628 Message(_("%d nets remaining\n"), failcount
);
7631 Message(_("%d -> "), failcount
);
7632 pfailcount
= failcount
;
7639 route_detour_compare(toporouter_route_t
**a
, toporouter_route_t
**b
)
7640 { return ((*b
)->score
- (*b
)->detourscore
) - ((*a
)->score
- (*a
)->detourscore
); }
7645 roar_detour_route(toporouter_t
*r
, toporouter_route_t
*data
)
7647 gdouble pscore
= data
->score
, nscore
= 0.;
7648 GList
*netlists
= NULL
;
7650 route_checkpoint(data
, NULL
);
7652 REMOVE_ROUTING(data
);
7654 netlists
= g_list_prepend(NULL
, data
->netlist
);
7655 netlists_recalculate(netlists
, NULL
);
7657 r
->flags
|= TOPOROUTER_FLAG_LEASTINVALID
;
7658 if(route(r
, data
, 0)) {
7659 GList
*conflicts
, *j
;
7661 nscore
= data
->score
;
7662 conflicts
= route_conflicts(data
);
7664 INSERT_ROUTING(data
);
7666 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7670 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7672 if(!g_list_find(netlists
, conflict
->netlist
))
7673 netlists
= g_list_prepend(netlists
, conflict
->netlist
);
7674 pscore
+= conflict
->score
;
7676 route_checkpoint(conflict
, NULL
);
7677 REMOVE_ROUTING(conflict
);
7681 netlists_recalculate(netlists
, NULL
);
7685 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7687 if(route(r
, conflict
, 0)) {
7688 cluster_merge(conflict
);
7689 INSERT_ROUTING(conflict
);
7690 nscore
+= conflict
->score
;
7693 goto roar_detour_route_rollback_int
;
7698 if(nscore
> pscore
) {
7699 j
= g_list_last(conflicts
);
7700 roar_detour_route_rollback_int
:
7701 REMOVE_ROUTING(data
);
7704 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7705 REMOVE_ROUTING(conflict
);
7706 delete_route(conflict
, 1);
7710 j
= g_list_last(conflicts
);
7712 toporouter_route_t
*conflict
= TOPOROUTER_ROUTE(j
->data
);
7713 route_restore(conflict
);
7714 INSERT_ROUTING(conflict
);
7717 delete_route(data
, 1);
7719 goto roar_detour_route_rollback_exit
;
7723 g_list_free(conflicts
);
7725 r
->flags
&= ~TOPOROUTER_FLAG_LEASTINVALID
;
7726 roar_detour_route_rollback_exit
:
7727 route_restore(data
);
7728 INSERT_ROUTING(data
);
7730 netlists_recalculate(netlists
, NULL
);
7732 g_list_free(netlists
);
7736 detour_router(toporouter_t
*r
)
7738 GList
*i
= r
->routednets
;
7739 guint n
= g_list_length(r
->routednets
);
7740 GPtrArray
* scores
= g_ptr_array_sized_new(n
);
7743 toporouter_route_t
*curroute
= TOPOROUTER_ROUTE(i
->data
);
7744 curroute
->score
= path_score(r
, curroute
->path
);
7745 g_ptr_array_add(scores
, i
->data
);
7749 g_ptr_array_sort(scores
, (GCompareFunc
) route_detour_compare
);
7751 r
->flags
|= TOPOROUTER_FLAG_DETOUR
;
7753 for(toporouter_route_t
**i
= (toporouter_route_t
**) scores
->pdata
; i
< (toporouter_route_t
**) scores
->pdata
+ scores
->len
; i
++) {
7754 toporouter_route_t
*curroute
= (*i
);
7756 if(finite(curroute
->score
) && finite(curroute
->detourscore
)) {
7757 // printf("%15s %15f \t %8f,%8f - %8f,%8f\n", (*i)->src->netlist + 2, (*i)->score - (*i)->detourscore,
7758 // vx(curroute->mergebox1->point), vy(curroute->mergebox1->point),
7759 // vx(curroute->mergebox2->point), vy(curroute->mergebox2->point));
7761 if(curroute
->score
- curroute
->detourscore
> 1000.) {
7762 roar_detour_route(r
, curroute
);
7769 r
->flags
^= TOPOROUTER_FLAG_DETOUR
;
7771 g_ptr_array_free(scores
, TRUE
);
7776 rubix_router(toporouter_t
*r
, gint failcount
)
7778 GList
*i
, *ordering
;
7779 order_nets_preroute_greedy(r
, r
->failednets
, &ordering
);
7783 toporouter_route_t
*data
= TOPOROUTER_ROUTE(i
->data
);
7785 if(route(r
, data
, 0)) {
7786 INSERT_ROUTING(data
);
7787 cluster_merge(data
);
7794 g_list_free(ordering
);
7800 hybrid_router(toporouter_t
*r
)
7802 gint failcount
= g_list_length(r
->failednets
);
7803 r
->flags
|= TOPOROUTER_FLAG_AFTERORDER
;
7804 r
->flags
|= TOPOROUTER_FLAG_AFTERRUBIX
;
7805 failcount
= rubix_router(r
, failcount
);
7807 Message(_("RUBIX router: %d nets remaining\n"), failcount
);
7808 printf("RUBIX router: %d nets remaining\n", failcount
);
7810 r
->flags
|= TOPOROUTER_FLAG_GOFAR
;
7812 for(guint i
=0;i
<6 && failcount
;i
++) {
7814 failcount
= roar_router(r
, failcount
, 5);
7815 // printf("THRESH 5\n");
7817 failcount
= roar_router(r
, failcount
, 2);
7818 // printf("THRESH 2\n");
7824 failcount
= roar_router(r
, failcount
, 2);
7831 parse_arguments(toporouter_t
*r
, int argc
, char **argv
)
7834 for(i
=0;i
<argc
;i
++) {
7835 if(sscanf(argv
[i
], "viacost=%d", &tempint
)) {
7836 r
->viacost
= (double)tempint
;
7837 }else if(sscanf(argv
[i
], "l%d", &tempint
)) {
7838 gdouble
*layer
= malloc(sizeof(gdouble
));
7839 *layer
= (double)tempint
;
7840 r
->keepoutlayers
= g_list_prepend(r
->keepoutlayers
, layer
);
7844 for (guint group
= 0; group
< max_group
; group
++)
7845 for (i
= 0; i
< PCB
->LayerGroups
.Number
[group
]; i
++)
7846 if ((PCB
->LayerGroups
.Entries
[group
][i
] < max_copper_layer
) && !(PCB
->Data
->Layer
[PCB
->LayerGroups
.Entries
[group
][i
]].On
)) {
7847 gdouble
*layer
= malloc(sizeof(gdouble
));
7848 *layer
= (double)group
;
7849 r
->keepoutlayers
= g_list_prepend(r
->keepoutlayers
, layer
);
7855 toporouter_new(void)
7857 toporouter_t
*r
= calloc(1, sizeof(toporouter_t
));
7860 gettimeofday(&r
->starttime
, NULL
);
7862 r
->netsort
= netscore_pairwise_compare
;
7864 r
->destboxes
= NULL
;
7865 r
->consumeddestboxes
= NULL
;
7872 r
->viacost
= 10000.;
7873 r
->stublength
= 300.;
7874 r
->serpintine_half_amplitude
= 1500.;
7876 r
->wiring_score
= 0.;
7881 r
->netlists
= g_ptr_array_new();
7882 r
->routes
= g_ptr_array_new();
7884 r
->keepoutlayers
= NULL
;
7886 r
->routednets
= NULL
;
7887 r
->failednets
= NULL
;
7891 gts_predicates_init();
7893 Message(_("Topological Autorouter\n"));
7894 Message(_("Started %s"),asctime(localtime(<ime
)));
7895 Message(_("-------------------------------------\n"));
7896 Message(_("Copyright 2009 Anthony Blake (tonyb33@gmail.com)\n\n"));
7901 acquire_twonets(toporouter_t
*r
)
7903 RAT_LOOP(PCB
->Data
);
7904 if( TEST_FLAG(SELECTEDFLAG
, line
) ) import_route(r
, line
);
7907 if(!r
->routes
->len
) {
7908 RAT_LOOP(PCB
->Data
);
7909 import_route(r
, line
);
7916 toporouter_netlist_t
*
7917 find_netlist_by_name(toporouter_t
*r
, char *name
)
7919 FOREACH_NETLIST(r
->netlists
) {
7920 if(!strcmp(netlist
->netlist
, name
)) return netlist
;
7926 toporouter_set_pair(toporouter_t
*r
, toporouter_netlist_t
*n1
, toporouter_netlist_t
*n2
)
7928 if(!n1
|| !n2
) return 0;
7935 toporouter (int argc
, char **argv
, int x
, int y
)
7937 toporouter_t
*r
= toporouter_new();
7938 parse_arguments(r
, argc
, argv
);
7942 //if(!toporouter_set_pair(r, find_netlist_by_name(r, " DRAM_DQS_N"), find_netlist_by_name(r, " DRAM_DQS"))) {
7943 // printf("Couldn't associate pair\n");
7948 for(gint i=0;i<groupcount();i++) {
7949 gts_surface_foreach_edge(r->layers[i].surface, space_edge, NULL);
7953 for(i=0;i<groupcount();i++) {
7955 sprintf(buffer, "route%d.png", i);
7956 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, NULL, i, NULL);
7960 toporouter_export(r
);
7963 SaveUndoSerialNumber ();
7965 RestoreUndoSerialNumber ();
7966 AddAllRats (false, NULL
);
7967 RestoreUndoSerialNumber ();
7968 IncrementUndoSerialNumber ();
7969 ClearAndRedrawOutput ();
7975 escape (int argc
, char **argv
, int x
, int y
)
7977 guint dir
, viax
, viay
;
7978 gdouble pitch
, length
, dx
, dy
;
7980 if(argc
!= 1) return 0;
7982 dir
= atoi(argv
[0]);
7985 ALLPAD_LOOP(PCB
->Data
);
7987 if( TEST_FLAG(SELECTEDFLAG
, pad
) ) {
7991 pitch
= sqrt( pow(abs(element
->Pad
[0].Point1
.X
- element
->Pad
[1].Point1
.X
), 2) +
7992 pow(abs(element
->Pad
[0].Point1
.Y
- element
->Pad
[1].Point1
.Y
), 2) );
7993 length
= sqrt(pow(pitch
,2) + pow(pitch
,2)) / 2.;
7995 dx
= length
* sin(M_PI
/4.);
7996 dy
= length
* cos(M_PI
/4.);
8000 viax
= pad
->Point1
.X
- dx
;
8001 viay
= pad
->Point1
.Y
+ dy
;
8004 viax
= pad
->Point1
.X
+ dx
;
8005 viay
= pad
->Point1
.Y
+ dy
;
8008 viax
= pad
->Point1
.X
+ dx
;
8009 viay
= pad
->Point1
.Y
- dy
;
8012 viax
= pad
->Point1
.X
- dx
;
8013 viay
= pad
->Point1
.Y
- dy
;
8016 viax
= pad
->Point1
.X
;
8017 viay
= pad
->Point1
.Y
+ (pitch
/2);
8020 viax
= pad
->Point1
.X
;
8021 viay
= pad
->Point1
.Y
- (pitch
/2);
8024 viax
= pad
->Point1
.X
- (pitch
/2);
8025 viay
= pad
->Point1
.Y
;
8028 viax
= pad
->Point1
.X
+ (pitch
/2);
8029 viay
= pad
->Point1
.Y
;
8032 printf("ERROR: escape() with bad direction (%d)\n", dir
);
8036 if ((via
= CreateNewVia (PCB
->Data
, viax
, viay
,
8037 Settings
.ViaThickness
, 2 * Settings
.Keepaway
,
8038 0, Settings
.ViaDrillingHole
, NULL
,
8039 NoFlags ())) != NULL
)
8041 AddObjectToCreateUndoList (VIA_TYPE
, via
, via
, via
);
8042 // if (gui->shift_is_pressed ())
8043 // ChangeObjectThermal (VIA_TYPE, via, via, via, PCB->ThermStyle);
8045 if((line
= CreateDrawnLineOnLayer (CURRENT
, pad
->Point1
.X
+ 1., pad
->Point1
.Y
+ 1., viax
+ 1., viay
+ 1.,
8046 Settings
.LineThickness
, 2 * Settings
.Keepaway
,
8050 AddObjectToCreateUndoList (LINE_TYPE
, CURRENT
, line
, line
);
8051 DrawLine (CURRENT
, line
, 0);
8062 IncrementUndoSerialNumber ();
8067 static HID_Action toporouter_action_list
[] = {
8068 {"Escape", "Select a set of pads", escape
, "Pad escape", "Escape()"},
8069 {"Toporouter", "Select net(s)", toporouter
, "Topological autorouter", "Toporouter()"}
8072 REGISTER_ACTIONS (toporouter_action_list
)
8074 void hid_toporouter_init()
8076 register_toporouter_action_list();