Fix distribution of gnet-pcbfwd.scm in the dist tarball
[geda-pcb/gde.git] / src / toporouter.c
bloba02f62862b0492c0d59d590d8ca1ebf3e3ebe9d8
1 /*
2 * COPYRIGHT
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"
59 static void
60 toporouter_edge_init (toporouter_edge_t *edge)
62 edge->routing = NULL;
63 edge->flags = 0;
66 toporouter_edge_class_t *
67 toporouter_edge_class(void)
69 static toporouter_edge_class_t *class = NULL;
71 if (class == NULL) {
72 GtsObjectClassInfo constraint_info = {
73 "toporouter_edge_t",
74 sizeof (toporouter_edge_t),
75 sizeof (toporouter_edge_class_t),
76 (GtsObjectClassInitFunc) NULL,
77 (GtsObjectInitFunc) toporouter_edge_init,
78 (GtsArgSetFunc) NULL,
79 (GtsArgGetFunc) NULL
81 class = gts_object_class_new (GTS_OBJECT_CLASS (gts_edge_class ()), &constraint_info);
84 return class;
87 static void
88 toporouter_bbox_init (toporouter_bbox_t *box)
90 box->data = NULL;
91 box->type = OTHER;
92 box->constraints = NULL;
93 box->cluster = NULL;
96 toporouter_bbox_class_t *
97 toporouter_bbox_class(void)
99 static toporouter_bbox_class_t *class = NULL;
101 if (class == NULL) {
102 GtsObjectClassInfo constraint_info = {
103 "toporouter_bbox_t",
104 sizeof (toporouter_bbox_t),
105 sizeof (toporouter_bbox_class_t),
106 (GtsObjectClassInitFunc) NULL,
107 (GtsObjectInitFunc) toporouter_bbox_init,
108 (GtsArgSetFunc) NULL,
109 (GtsArgGetFunc) NULL
111 class = gts_object_class_new (GTS_OBJECT_CLASS (gts_bbox_class ()), &constraint_info);
114 return class;
117 static void
118 toporouter_vertex_class_init (toporouter_vertex_class_t *klass)
123 static void
124 toporouter_vertex_init (toporouter_vertex_t *vertex)
126 vertex->bbox = NULL;
127 vertex->parent = NULL;
128 vertex->child = NULL;
129 vertex->flags = 0;
130 vertex->routingedge = NULL;
131 vertex->arc = NULL;
132 vertex->oproute = NULL;
133 vertex->route = NULL;
135 vertex->gcost = 0.;
136 vertex->hcost = 0.;
137 vertex->gn = 0;
140 toporouter_vertex_class_t *
141 toporouter_vertex_class(void)
143 static toporouter_vertex_class_t *klass = NULL;
145 if (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,
153 (GtsArgGetFunc) NULL
155 klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_vertex_class ()), &constraint_info);
158 return klass;
161 static void
162 toporouter_constraint_class_init (toporouter_constraint_class_t *klass)
167 static void
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;
179 if (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,
187 (GtsArgGetFunc) NULL
189 klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_constraint_class ()), &constraint_info);
192 return klass;
195 static void
196 toporouter_arc_init (toporouter_arc_t *arc)
198 arc->x0 = -1.;
199 arc->y0 = -1.;
200 arc->x1 = -1.;
201 arc->y1 = -1.;
202 arc->centre = NULL;
203 arc->v = NULL;
204 arc->v1 = NULL;
205 arc->v2 = NULL;
206 arc->r = -1.;
207 arc->dir = 31337;
208 arc->clearance = NULL;
209 arc->oproute = NULL;
212 toporouter_arc_class_t *
213 toporouter_arc_class(void)
215 static toporouter_arc_class_t *klass = NULL;
217 if (klass == NULL) {
218 GtsObjectClassInfo constraint_info = {
219 "toporouter_arc_t",
220 sizeof (toporouter_arc_t),
221 sizeof (toporouter_arc_class_t),
222 (GtsObjectClassInitFunc) NULL,
223 (GtsObjectInitFunc) toporouter_arc_init,
224 (GtsArgSetFunc) NULL,
225 (GtsArgGetFunc) NULL
227 klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_constraint_class ()), &constraint_info);
230 return klass;
233 #define MARGIN 10.0f
235 drawing_context_t *
236 toporouter_output_init(int w, int h, char *filename)
238 drawing_context_t *dc;
240 dc = malloc(sizeof(drawing_context_t));
242 dc->iw = w;
243 dc->ih = h;
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);
251 }else{
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);
263 cairo_fill (dc->cr);
265 #endif
267 return dc;
270 void
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);
277 #endif
280 gdouble
281 lookup_keepaway(char *name)
283 if(name)
284 STYLE_LOOP(PCB);
286 // if(!strcmp(style->Name, name)) return style->Keepaway + 1.;
287 if(!strcmp(style->Name, name)) return style->Keepaway;
289 END_LOOP;
290 // return Settings.Keepaway + 1.;
291 return Settings.Keepaway ;
294 gdouble
295 lookup_thickness(char *name)
297 if(name)
298 STYLE_LOOP(PCB);
300 if(!strcmp(style->Name, name)) return style->Thick;
302 END_LOOP;
303 return Settings.LineThickness;
306 inline gdouble
307 cluster_keepaway(toporouter_cluster_t *cluster)
309 if(cluster) return lookup_keepaway(cluster->netlist->style);
310 return lookup_keepaway(NULL);
313 inline gdouble
314 cluster_thickness(toporouter_cluster_t *cluster)
316 if(cluster) return lookup_thickness(cluster->netlist->style);
317 return lookup_thickness(NULL);
320 gint
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;
326 PinType *pin;
327 PadType *pad;
328 gdouble blue;
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);
335 cairo_arc(dc->cr,
336 tv->v.p.x * dc->s + MARGIN,
337 tv->v.p.y * dc->s + MARGIN,
338 500. * dc->s, 0, 2 * M_PI);
339 cairo_fill(dc->cr);
341 }else if(tv->flags & VERTEX_FLAG_GREEN) {
342 cairo_set_source_rgba(dc->cr, 0., 1., 0., 0.8f);
343 cairo_arc(dc->cr,
344 tv->v.p.x * dc->s + MARGIN,
345 tv->v.p.y * dc->s + MARGIN,
346 500. * dc->s, 0, 2 * M_PI);
347 cairo_fill(dc->cr);
349 }else if(tv->flags & VERTEX_FLAG_BLUE) {
350 cairo_set_source_rgba(dc->cr, 0., 0., 1., 0.8f);
351 cairo_arc(dc->cr,
352 tv->v.p.x * dc->s + MARGIN,
353 tv->v.p.y * dc->s + MARGIN,
354 500. * dc->s, 0, 2 * M_PI);
355 cairo_fill(dc->cr);
359 //printf("tv->type = %d\n", tv->type);
360 if(!dc->mode) {
361 if(tv->bbox) {
362 pin = (PinType*) tv->bbox->data;
363 pad = (PadType*) tv->bbox->data;
365 blue = 0.0f;
366 switch(tv->bbox->type) {
367 case PIN:
368 cairo_set_source_rgba(dc->cr, 1.0f, 0., 0.0f, 0.2f);
369 cairo_arc(dc->cr,
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);
373 cairo_fill(dc->cr);
375 cairo_set_source_rgba(dc->cr, 1.0f, 0., 0., 0.4f);
376 cairo_arc(dc->cr,
377 tv->v.p.x * dc->s + MARGIN,
378 tv->v.p.y * dc->s + MARGIN,
379 (gdouble)(pin->Thickness) / 2.0f * dc->s,
380 0, 2 * M_PI);
381 cairo_fill(dc->cr);
383 break;
384 case VIA:
385 cairo_set_source_rgba(dc->cr, 0.0f, 0., 1., 0.2f);
386 cairo_arc(dc->cr,
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);
390 cairo_fill(dc->cr);
392 cairo_set_source_rgba(dc->cr, 0.0f, 0., 1., 0.4f);
393 cairo_arc(dc->cr,
394 tv->v.p.x * dc->s + MARGIN,
395 tv->v.p.y * dc->s + MARGIN,
396 (gdouble)(pin->Thickness) / 2.0f * dc->s,
397 0, 2 * M_PI);
398 cairo_fill(dc->cr);
400 break;
401 case PAD:
402 cairo_set_source_rgba(dc->cr, 0.0f, 1., 0., 0.5f);
403 cairo_arc(dc->cr,
404 tv->v.p.x * dc->s + MARGIN,
405 tv->v.p.y * dc->s + MARGIN,
406 400. * dc->s, 0, 2 * M_PI);
407 cairo_fill(dc->cr);
409 break;
410 default:
411 break;
414 }else{
415 if(tv->flags & VERTEX_FLAG_BLUE) {
416 cairo_set_source_rgba(dc->cr, 0., 0., 1., 0.8f);
417 cairo_arc(dc->cr,
418 tv->v.p.x * dc->s + MARGIN,
419 tv->v.p.y * dc->s + MARGIN,
420 500. * dc->s, 0, 2 * M_PI);
421 cairo_fill(dc->cr);
422 }else if(tv->flags & VERTEX_FLAG_RED) {
423 cairo_set_source_rgba(dc->cr, 1., 0., 0., 0.8f);
424 cairo_arc(dc->cr,
425 tv->v.p.x * dc->s + MARGIN,
426 tv->v.p.y * dc->s + MARGIN,
427 500. * dc->s, 0, 2 * M_PI);
428 cairo_fill(dc->cr);
430 }else if(tv->flags & VERTEX_FLAG_GREEN) {
431 cairo_set_source_rgba(dc->cr, 0., 1., 0., 0.8f);
432 cairo_arc(dc->cr,
433 tv->v.p.x * dc->s + MARGIN,
434 tv->v.p.y * dc->s + MARGIN,
435 500. * dc->s, 0, 2 * M_PI);
436 cairo_fill(dc->cr);
440 }else{
441 fprintf(stderr, "Unknown data passed to toporouter_draw_vertex, aborting foreach\n");
442 return -1;
444 return 0;
445 #else
446 return -1;
447 #endif
450 gint
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);
470 if(tc->box) {
471 switch(tc->box->type) {
472 case BOARD:
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);
481 break;
482 case PIN:
483 case PAD:
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);
492 break;
493 case LINE:
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);
502 break;
504 default:
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);
513 break;
515 }else{
516 printf("CONSTRAINT without box\n");
519 }else{
520 fprintf(stderr, "Unknown data passed to toporouter_draw_edge, aborting foreach\n");
521 return -1;
524 return 0;
525 #else
526 return -1;
527 #endif
530 //#define vertex_bbox(v) (v->bbox)
531 ///*
532 toporouter_bbox_t *
533 vertex_bbox(toporouter_vertex_t *v)
535 return v ? v->bbox : NULL;
537 //*/
538 char *
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;
545 return NULL;
548 char *
549 constraint_netlist(toporouter_constraint_t *c)
551 toporouter_bbox_t *box = c->box;
553 if(box && box->cluster) return box->cluster->netlist->netlist;
555 return NULL;
558 inline guint
559 epsilon_equals(gdouble a, gdouble b)
561 if(a > b - EPSILON && a < b + EPSILON) return 1;
562 return 0;
565 void
566 print_bbox(toporouter_bbox_t *box)
568 printf("[BBOX ");
569 switch(box->type) {
570 case PAD:
571 printf("PAD "); break;
572 case PIN:
573 printf("PIN "); break;
574 case VIA:
575 printf("VIA "); break;
576 case LINE:
577 printf("LINE "); break;
578 case BOARD:
579 printf("BOARD "); break;
580 case POLYGON:
581 printf("POLYGON "); break;
582 default:
583 printf("UNKNOWN "); break;
586 if(box->point)
587 printf("P: %f,%f,%f ", vx(box->point), vy(box->point), vz(box->point));
588 else
589 printf("P: NONE ");
591 printf("LAYER: %d ", box->layer);
592 printf("CLUSTER: %d]\n", box->cluster ? box->cluster->c : -1);
596 void
597 print_vertex(toporouter_vertex_t *v)
599 if(v)
600 printf("[V %f,%f,%f ", vx(v), vy(v), vz(v));
601 else
602 printf("[V (null) ");
604 printf("%s ", vertex_netlist(v));
605 if(v->route && v->route->netlist)
606 printf("%s ", v->route->netlist->netlist);
608 if(v->routingedge) {
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))
613 printf("[CONST ");
614 else
615 printf("[EDGE ");
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 ");
627 printf("]\n");
631 gdouble
632 vertex_net_thickness(toporouter_vertex_t *v)
634 toporouter_bbox_t *box = vertex_bbox(v);
636 if(!box) {
638 while(v && (v->flags & VERTEX_FLAG_TEMP || v->flags & VERTEX_FLAG_ROUTE)) {
639 v = v->parent;
642 box = vertex_bbox(v);
644 }else{
645 if(box->type == PIN || box->type == VIA) {
646 PinType *pin = (PinType *)box->data;
647 if(TEST_FLAG(SQUAREFLAG, pin) || TEST_FLAG(OCTAGONFLAG, pin)) {
648 return 0.;
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;
657 return 0.;
658 }else if(box->type == BOARD) {
659 return 0.;
660 }else if(box->type == LINE) {
661 LineType *line = (LineType *) box->data;
662 return line->Thickness;
663 }else if(box->type == POLYGON) {
664 return 0.;
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);
676 gdouble
677 vertex_net_keepaway(toporouter_vertex_t *v)
679 toporouter_bbox_t *box = vertex_bbox(v);
680 if(!box) {
682 while(v && (v->flags & VERTEX_FLAG_TEMP || v->flags & VERTEX_FLAG_ROUTE)) {
683 v = v->parent;
685 box = vertex_bbox(v);
687 else{
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);
700 void
701 print_trace (void)
703 void *array[10];
704 size_t size;
705 char **strings;
706 size_t i;
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]);
716 free (strings);
719 /* fills in x and y with coordinates of point from a towards b of distance d */
720 void
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
728 if(!finite(theta)) {
729 // printf("!finte(theta): a = %f,%f b = %f,%f d = %f\n", vx(a), vy(a), vx(b), vy(b), d);
730 // print_trace();
731 //TODO: this shouldn't happen, fix the hack
732 *x = vx(a);
733 *y = vy(a);
734 return;
736 //#endif
738 g_assert(finite(theta));
740 *x = vx(a); *y = vy(a);
742 if( dx >= 0. ) {
744 if( dy >= 0. ) {
745 *x += d * cos(theta);
746 *y += d * sin(theta);
747 }else{
748 *x += d * cos(theta);
749 *y -= d * sin(theta);
752 }else{
754 if( dy >= 0. ) {
755 *x -= d * cos(theta);
756 *y += d * sin(theta);
757 }else{
758 *x -= d * cos(theta);
759 *y -= d * sin(theta);
766 inline gint
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);
776 /* wind_v:
777 * returns 1,0,-1 for counterclockwise, collinear or clockwise, respectively.
779 int
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);
789 inline int
790 vertex_wind(GtsVertex *a, GtsVertex *b, GtsVertex *c)
792 return point_wind(GTS_POINT(a), GTS_POINT(b), GTS_POINT(c));
795 inline int
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));
801 int
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);
811 inline int
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 */
818 void
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));
826 if(!finite(theta)) {
827 printf("!finite(theta) a = %f,%f p = %f,%f d = %f\n",
828 ax, ay, px, py, d);
832 g_assert(finite(theta));
834 if( dx >= 0. ) {
836 if( dy >= 0. ) {
837 *x = ax + (d * cos(theta));
838 *y = ay + (d * sin(theta));
839 }else{
840 *x = ax + (d * cos(theta));
841 *y = ay - (d * sin(theta));
844 }else{
846 if( dy >= 0. ) {
847 *x = ax - (d * cos(theta));
848 *y = ay + (d * sin(theta));
849 }else{
850 *x = ax - (d * cos(theta));
851 *y = ay - (d * sin(theta));
858 /* moves vertex v d units in the direction of vertex p */
859 void
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));
868 if( dx >= 0. ) {
870 if( dy >= 0. ) {
871 *x = GTS_POINT(v)->x + (d * cos(theta));
872 *y = GTS_POINT(v)->y + (d * sin(theta));
873 }else{
874 *x = GTS_POINT(v)->x + (d * cos(theta));
875 *y = GTS_POINT(v)->y - (d * sin(theta));
878 }else{
880 if( dy >= 0. ) {
881 *x = GTS_POINT(v)->x - (d * cos(theta));
882 *y = GTS_POINT(v)->y + (d * sin(theta));
883 }else{
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 */
893 void
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));
902 if( dx >= 0. ) {
904 if( dy >= 0. ) {
905 *x = GTS_POINT(v)->x + (d * cos(theta));
906 *y = GTS_POINT(v)->y + (d * sin(theta));
907 }else{
908 *x = GTS_POINT(v)->x + (d * cos(theta));
909 *y = GTS_POINT(v)->y - (d * sin(theta));
912 }else{
914 if( dy >= 0. ) {
915 *x = GTS_POINT(v)->x - (d * cos(theta));
916 *y = GTS_POINT(v)->y + (d * sin(theta));
917 }else{
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 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);
943 #ifdef SPACING_DEBUG
944 printf("v1halfthick = %f v2halfthick = %f v1keepaway = %f v2keepaway = %f ms = %f\n",
945 v1halfthick, v2halfthick, v1keepaway, v2keepaway, ms);
946 #endif
948 return ms;
951 // v1 is a vertex in the CDT, and v2 is a net... other way around?
952 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);
966 return ms;
969 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);
983 return ms;
986 gdouble
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);
1000 return ms;
1003 gdouble
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);
1017 return ms;
1020 void
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;
1026 //while(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);
1033 // }
1035 // i = i->next;
1037 #endif
1040 void
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;
1045 GList *i;
1046 toporouter_vertex_t *tv, *tv2 = NULL;
1048 dc = toporouter_output_init(w, h, filename);
1049 dc->mode = mode;
1050 dc->data = NULL;
1052 gts_surface_foreach_edge(s, toporouter_draw_edge, dc);
1053 gts_surface_foreach_vertex(s, toporouter_draw_vertex, dc);
1055 i = r->routednets;
1056 while(i) {
1057 GList *j = TOPOROUTER_ROUTE(i->data)->path;
1058 tv2 = NULL;
1059 while(j) {
1060 tv = TOPOROUTER_VERTEX(j->data);
1061 if(GTS_POINT(tv)->z == layer) {
1062 if(tv && tv2) {
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);
1075 cairo_arc(dc->cr,
1076 tv->v.p.x * dc->s + MARGIN,
1077 tv->v.p.y * dc->s + MARGIN,
1078 500. * dc->s, 0, 2 * M_PI);
1079 cairo_fill(dc->cr);
1081 }else if(tv->flags & VERTEX_FLAG_GREEN) {
1082 cairo_set_source_rgba(dc->cr, 0., 1., 0., 0.8f);
1083 cairo_arc(dc->cr,
1084 tv->v.p.x * dc->s + MARGIN,
1085 tv->v.p.y * dc->s + MARGIN,
1086 500. * dc->s, 0, 2 * M_PI);
1087 cairo_fill(dc->cr);
1089 }else if(tv->flags & VERTEX_FLAG_BLUE) {
1090 cairo_set_source_rgba(dc->cr, 0., 0., 1., 0.8f);
1091 cairo_arc(dc->cr,
1092 tv->v.p.x * dc->s + MARGIN,
1093 tv->v.p.y * dc->s + MARGIN,
1094 500. * dc->s, 0, 2 * M_PI);
1095 cairo_fill(dc->cr);
1098 else {
1100 cairo_set_source_rgba(dc->cr, 1., 1., 1., 0.8f);
1101 cairo_arc(dc->cr,
1102 tv->v.p.x * dc->s + MARGIN,
1103 tv->v.p.y * dc->s + MARGIN,
1104 500. * dc->s, 0, 2 * M_PI);
1105 cairo_fill(dc->cr);
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);
1143 tv2 = tv;
1144 j = j->next;
1146 i = i->next;
1149 while(datas) {
1150 toporouter_route_t *routedata = (toporouter_route_t *) datas->data;
1152 GList *i;//, *k;
1154 toporouter_draw_cluster(r, dc, routedata->src, 1., 0., 0., layer);
1155 toporouter_draw_cluster(r, dc, routedata->dest, 0., 0., 1., layer);
1157 tv2 = NULL;
1158 i = routedata->path;
1159 while(i) {
1160 tv = TOPOROUTER_VERTEX(i->data);
1161 if(GTS_POINT(tv)->z == layer) {
1162 if(tv && tv2) {
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);
1173 tv2 = tv;
1174 i = i->next;
1178 if(routedata->alltemppoints) {
1179 GList *i, *j;
1180 i = j = g_hash_table_get_keys (routedata->alltemppoints);
1181 while(i) {
1182 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
1184 if(GTS_POINT(tv)->z != layer) {
1185 i = i->next;
1186 continue;
1188 if(tv->flags & VERTEX_FLAG_BLUE) {
1189 cairo_set_source_rgba(dc->cr, 0., 0., 1., 0.8f);
1190 cairo_arc(dc->cr,
1191 tv->v.p.x * dc->s + MARGIN,
1192 tv->v.p.y * dc->s + MARGIN,
1193 500. * dc->s, 0, 2 * M_PI);
1194 cairo_fill(dc->cr);
1195 }else if(tv->flags & VERTEX_FLAG_RED) {
1196 cairo_set_source_rgba(dc->cr, 1., 0., 0., 0.8f);
1197 cairo_arc(dc->cr,
1198 tv->v.p.x * dc->s + MARGIN,
1199 tv->v.p.y * dc->s + MARGIN,
1200 500. * dc->s, 0, 2 * M_PI);
1201 cairo_fill(dc->cr);
1203 }else if(tv->flags & VERTEX_FLAG_GREEN) {
1204 cairo_set_source_rgba(dc->cr, 0., 1., 0., 0.8f);
1205 cairo_arc(dc->cr,
1206 tv->v.p.x * dc->s + MARGIN,
1207 tv->v.p.y * dc->s + MARGIN,
1208 500. * dc->s, 0, 2 * M_PI);
1209 cairo_fill(dc->cr);
1210 }else{
1211 cairo_set_source_rgba(dc->cr, 1., 1., 1., 0.8f);
1212 cairo_arc(dc->cr,
1213 tv->v.p.x * dc->s + MARGIN,
1214 tv->v.p.y * dc->s + MARGIN,
1215 500. * dc->s, 0, 2 * M_PI);
1216 cairo_fill(dc->cr);
1218 i = i->next;
1220 g_list_free(j);
1222 datas = datas->next;
1224 toporouter_output_close(dc);
1225 #endif
1229 void
1230 toporouter_layer_free(toporouter_layer_t *l)
1232 g_list_free(l->vertices);
1233 g_list_free(l->constraints);
1237 guint
1238 groupcount(void)
1240 int group;
1241 guint count = 0;
1243 for (group = 0; group < max_layer; group++) {
1244 if(PCB->LayerGroups.Number[group] > 0) count++;
1247 return count;
1250 void
1251 toporouter_free(toporouter_t *r)
1253 struct timeval endtime;
1254 int secs, usecs;
1256 int i;
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);
1267 if(usecs < 0) {
1268 secs -= 1;
1269 usecs += 1000;
1272 Message(_("Elapsed time: %d.%02d seconds\n"), secs, usecs);
1273 free(r->layers);
1274 free(r);
1278 /* wind:
1279 * returns 1,0,-1 for counterclockwise, collinear or clockwise, respectively.
1281 int
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);
1291 /* wind_double:
1292 * returns 1,0,-1 for counterclockwise, collinear or clockwise, respectively.
1294 int
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);
1304 inline void
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);
1314 inline void
1315 print_toporouter_vertex(toporouter_vertex_t *tv)
1317 printf("%f,%f ", tv->v.p.x, tv->v.p.y);
1322 * vertices_on_line:
1323 * Given vertex a, gradient m, and radius r:
1325 * Return vertices on line of a & m at r from a
1327 void
1328 vertices_on_line(toporouter_spoint_t *a, gdouble m, gdouble r, toporouter_spoint_t *b0, toporouter_spoint_t *b1)
1331 gdouble c, temp;
1333 if(m == INFINITY || m == -INFINITY) {
1334 b0->y = a->y + r;
1335 b1->y = a->y - r;
1337 b0->x = a->x;
1338 b1->x = a->x;
1340 return;
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;
1356 * vertices_on_line:
1357 * Given vertex a, gradient m, and radius r:
1359 * Return vertices on line of a & m at r from a
1361 void
1362 coords_on_line(gdouble ax, gdouble ay, gdouble m, gdouble r, gdouble *b0x, gdouble *b0y, gdouble *b1x, gdouble *b1y)
1365 gdouble c, temp;
1367 if(m == INFINITY || m == -INFINITY) {
1368 *b0y = ay + r;
1369 *b1y = ay - r;
1371 *b0x = ax;
1372 *b1x = ax;
1374 return;
1377 c = ay - (m * ax);
1379 temp = sqrt( pow(r, 2) / ( 1 + pow(m, 2) ) );
1381 *b0x = ax + temp;
1382 *b1x = ax - temp;
1384 *b0y = *b0x * m + c;
1385 *b1y = *b1x * m + c;
1390 * vertices_on_line:
1391 * Given vertex a, gradient m, and radius r:
1393 * Return vertices on line of a & m at r from a
1395 void
1396 points_on_line(GtsPoint *a, gdouble m, gdouble r, GtsPoint *b0, GtsPoint *b1)
1399 gdouble c, temp;
1401 if(m == INFINITY || m == -INFINITY) {
1402 b0->y = a->y + r;
1403 b1->y = a->y - r;
1405 b0->x = a->x;
1406 b1->x = a->x;
1408 return;
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
1426 gdouble
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 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 inline gdouble
1449 point_gradient(GtsPoint *a, GtsPoint *b)
1451 return cartesian_gradient(a->x, a->y, b->x, b->y);
1454 gdouble
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
1467 gdouble
1468 perpendicular_gradient(gdouble m)
1470 if(isinf(m)) return 0.0f;
1471 if(m < EPSILON && m > -EPSILON) return INFINITY;
1472 return -1.0f/m;
1476 * Returns the distance between two vertices in the x-y plane
1478 gdouble
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
1486 inline void
1487 vertex_outside_segment(toporouter_spoint_t *a, toporouter_spoint_t *b, gdouble r, toporouter_spoint_t *p)
1489 gdouble m;
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)) {
1497 p->x = temp[0].x;
1498 p->y = temp[0].y;
1499 }else{
1500 p->x = temp[1].x;
1501 p->y = temp[1].y;
1506 /* proper intersection:
1507 * AB and CD must share a point interior to both segments.
1508 * returns TRUE if AB properly intersects CD.
1510 gint
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) );
1540 inline int
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));
1546 inline int
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));
1552 inline int
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;
1557 return
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.
1567 GtsVertex *
1568 vertex_intersect(GtsVertex *a, GtsVertex *b, GtsVertex *c, GtsVertex *d)
1570 GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
1571 GtsVertex *rval;
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);
1587 return rval;
1590 /* intersection vertex:
1591 * AB and CD must share a point interior to both segments.
1592 * returns vertex at intersection of AB and CD.
1594 void
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) &&
1618 (c->x <= b->x)) ||
1619 ((a->x >= c->x) &&
1620 (c->x >= b->x));
1622 return ((a->y <= c->y) &&
1623 (c->y <= b->y)) ||
1624 ((a->y >= c->y) &&
1625 (c->y >= b->y));
1628 inline int
1629 vertex_between(GtsVertex *a, GtsVertex *b, GtsVertex *c)
1631 return point_between(GTS_POINT(a), GTS_POINT(b), GTS_POINT(c));
1634 void
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;
1641 while (i) {
1642 vertices_slist = g_slist_prepend(vertices_slist, i->data);
1643 i = i->next;
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));
1655 i = vertices;
1656 while (i) {
1657 toporouter_vertex_t *v = TOPOROUTER_VERTEX(gts_delaunay_add_vertex (*surface, i->data, NULL));
1659 if(v) {
1660 printf("ERROR: vertex could not be added to CDT ");
1661 print_vertex(v);
1664 i = i->next;
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);
1674 // return surface;
1677 GSList *
1678 list_to_slist(GList *i)
1680 GSList *rval = NULL;
1681 while(i) {
1682 rval = g_slist_prepend(rval, i->data);
1683 i = i->next;
1685 return rval;
1688 toporouter_bbox_t *
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) );
1696 bbox->type = type;
1697 bbox->data = data;
1699 bbox->surface = NULL;
1700 bbox->enclosing = NULL;
1702 bbox->layer = layer;
1704 bbox->point = NULL;
1705 bbox->realpoint = NULL;
1707 g_slist_free(vertices_slist);
1708 return bbox;
1711 toporouter_bbox_t *
1712 toporouter_bbox_create(int layer, GList *vertices, toporouter_term_t type, gpointer data)
1714 toporouter_bbox_t *bbox;
1715 GtsSurface *s;
1716 GtsTriangle *t;
1718 delaunay_create_from_vertices(vertices, &s, &t);
1719 bbox = TOPOROUTER_BBOX( gts_bbox_surface(GTS_BBOX_CLASS(toporouter_bbox_class()), s) );
1720 bbox->type = type;
1721 bbox->data = data;
1723 bbox->surface = s;
1724 bbox->enclosing = t;
1726 bbox->layer = layer;
1728 return bbox;
1731 GtsVertex *
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 ());
1735 GtsVertex *v;
1736 GList *i;
1738 i = l->vertices;
1739 while (i) {
1740 v = i->data;
1741 if(v->p.x == x && v->p.y == y) {
1742 TOPOROUTER_VERTEX(v)->bbox = box;
1743 return v;
1745 i = i->next;
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);
1752 return v;
1755 GList *
1756 insert_constraint_edge(toporouter_t *r, toporouter_layer_t *l, gdouble x1, gdouble y1, guint flags1, gdouble x2, gdouble y2, guint flags2, toporouter_bbox_t *box)
1758 GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
1759 GtsEdgeClass *edge_class = GTS_EDGE_CLASS (toporouter_constraint_class ());
1760 GtsVertex *p[2];
1761 GtsVertex *v;
1762 GList *i;
1763 GtsEdge *e;
1765 p[0] = p[1] = NULL;
1767 /* insert or find points */
1769 i = l->vertices;
1770 while (i) {
1771 v = i->data;
1772 if(v->p.x == x1 && v->p.y == y1)
1773 p[0] = v;
1774 if(v->p.x == x2 && v->p.y == y2)
1775 p[1] = v;
1776 i = i->next;
1779 if(p[0] == NULL) {
1780 p[0] = gts_vertex_new (vertex_class, x1, y1, l - r->layers);
1781 TOPOROUTER_VERTEX(p[0])->bbox = box;
1782 l->vertices = g_list_prepend(l->vertices, p[0]);
1784 if(p[1] == NULL) {
1785 p[1] = gts_vertex_new (vertex_class, x2, y2, l - r->layers);
1786 TOPOROUTER_VERTEX(p[1])->bbox = box;
1787 l->vertices = g_list_prepend(l->vertices, p[1]);
1790 TOPOROUTER_VERTEX(p[0])->flags = flags1;
1791 TOPOROUTER_VERTEX(p[1])->flags = flags2;
1793 e = gts_edge_new (edge_class, p[0], p[1]);
1794 TOPOROUTER_CONSTRAINT(e)->box = box;
1795 l->constraints = g_list_prepend (l->constraints, e);
1796 // return insert_constraint_edge_rec(r, l, p, box);
1797 return g_list_prepend(NULL, e);
1801 void
1802 insert_constraints_from_list(toporouter_t *r, toporouter_layer_t *l, GList *vlist, toporouter_bbox_t *box)
1804 GList *i = vlist;
1805 toporouter_vertex_t *pv = NULL, *v;
1807 while(i) {
1808 v = TOPOROUTER_VERTEX(i->data);
1810 if(pv) {
1811 box->constraints =
1812 g_list_concat(box->constraints, insert_constraint_edge(r, l, vx(v), vy(v), v->flags, vx(pv), vy(pv), pv->flags, box));
1815 pv = v;
1816 i = i->next;
1819 v = TOPOROUTER_VERTEX(vlist->data);
1820 box->constraints =
1821 g_list_concat(box->constraints, insert_constraint_edge(r, l, vx(v), vy(v), v->flags, vx(pv), vy(pv), pv->flags, box));
1825 void
1826 insert_centre_point(toporouter_t *r, toporouter_layer_t *l, gdouble x, gdouble y)
1828 GList *i;
1829 GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
1831 i = l->vertices;
1832 while (i) {
1833 GtsPoint *p = GTS_POINT(i->data);
1834 if(p->x == x && p->y == y)
1835 return;
1836 i = i->next;
1839 l->vertices = g_list_prepend(l->vertices, gts_vertex_new(vertex_class, x, y, 0.0f));
1842 GtsPoint *
1843 midpoint(GtsPoint *a, GtsPoint *b)
1845 return gts_point_new(gts_point_class(), (a->x + b->x) / 2., (a->y + b->y) / 2., 0.);
1848 inline gdouble
1849 pad_rad(PadType *pad)
1851 return (lookup_thickness(pad->Name) / 2.) + lookup_keepaway(pad->Name);
1854 inline gdouble
1855 pin_rad(PinType *pin)
1857 return (lookup_thickness(pin->Name) / 2.) + lookup_keepaway(pin->Name);
1860 GList *
1861 rect_with_attachments(gdouble rad,
1862 gdouble x0, gdouble y0,
1863 gdouble x1, gdouble y1,
1864 gdouble x2, gdouble y2,
1865 gdouble x3, gdouble y3,
1866 gdouble z)
1868 GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
1869 GList *r = NULL, *rr = NULL, *i;
1870 toporouter_vertex_t *curpoint, *temppoint;
1873 curpoint = TOPOROUTER_VERTEX(gts_vertex_new (vertex_class, x0, y0, z));
1875 r = g_list_prepend(NULL, curpoint);
1876 r = g_list_prepend(r, gts_vertex_new (vertex_class, x1, y1, z));
1877 r = g_list_prepend(r, gts_vertex_new (vertex_class, x2, y2, z));
1878 r = g_list_prepend(r, gts_vertex_new (vertex_class, x3, y3, z));
1880 i = r;
1881 while(i) {
1882 temppoint = TOPOROUTER_VERTEX(i->data);
1883 rr = g_list_prepend(rr, curpoint);
1885 curpoint = temppoint;
1886 i = i->next;
1889 g_list_free(r);
1891 return rr;
1894 #define VERTEX_CENTRE(x) TOPOROUTER_VERTEX( vertex_bbox(x)->point )
1897 * Read pad data from layer into toporouter_layer_t struct
1899 * Inserts points and constraints into GLists
1902 read_pads(toporouter_t *r, toporouter_layer_t *l, guint layer)
1904 toporouter_spoint_t p[2], rv[5];
1905 gdouble x[2], y[2], t, m;
1906 GList *objectconstraints;
1908 GList *vlist = NULL;
1909 toporouter_bbox_t *bbox = NULL;
1911 guint front = GetLayerGroupNumberByNumber (max_layer + COMPONENT_LAYER);
1912 guint back = GetLayerGroupNumberByNumber (max_layer + SOLDER_LAYER);
1914 // printf("read_pads: front = %d back = %d layer = %d\n",
1915 // front, back, layer);
1917 /* If its not the top or bottom layer, there are no pads to read */
1918 if(l - r->layers != front && l - r->layers != back) return 0;
1920 ELEMENT_LOOP(PCB->Data);
1922 PAD_LOOP(element);
1924 if( (l - r->layers == back && TEST_FLAG(ONSOLDERFLAG, pad)) ||
1925 (l - r->layers == front && !TEST_FLAG(ONSOLDERFLAG, pad)) ) {
1928 objectconstraints = NULL;
1929 t = (gdouble)pad->Thickness / 2.0f;
1930 x[0] = pad->Point1.X;
1931 x[1] = pad->Point2.X;
1932 y[0] = pad->Point1.Y;
1933 y[1] = pad->Point2.Y;
1936 if(TEST_FLAG(SQUAREFLAG, pad)) {
1937 /* Square or oblong pad. Four points and four constraint edges are
1938 * used */
1940 if(x[0] == x[1] && y[0] == y[1]) {
1941 /* Pad is square */
1943 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, x[0]-t, y[0]-t, 0.));
1944 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]-t, y[0]+t, 0.));
1945 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]+t, y[0]+t, 0.));
1946 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, x[0]+t, y[0]-t, 0.));
1947 vlist = rect_with_attachments(pad_rad(pad),
1948 x[0]-t, y[0]-t,
1949 x[0]-t, y[0]+t,
1950 x[0]+t, y[0]+t,
1951 x[0]+t, y[0]-t,
1952 l - r->layers);
1953 bbox = toporouter_bbox_create(l - r->layers, vlist, PAD, pad);
1954 r->bboxes = g_slist_prepend(r->bboxes, bbox);
1955 insert_constraints_from_list(r, l, vlist, bbox);
1956 g_list_free(vlist);
1958 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, x[0], y[0], 0.) );
1959 bbox->point = GTS_POINT( insert_vertex(r, l, x[0], y[0], bbox) );
1960 g_assert(TOPOROUTER_VERTEX(bbox->point)->bbox == bbox);
1961 }else {
1962 /* Pad is diagonal oblong or othogonal oblong */
1964 m = cartesian_gradient(x[0], y[0], x[1], y[1]);
1966 p[0].x = x[0]; p[0].y = y[0];
1967 p[1].x = x[1]; p[1].y = y[1];
1969 vertex_outside_segment(&p[0], &p[1], t, &rv[0]);
1970 vertices_on_line(&rv[0], perpendicular_gradient(m), t, &rv[1], &rv[2]);
1972 vertex_outside_segment(&p[1], &p[0], t, &rv[0]);
1973 vertices_on_line(&rv[0], perpendicular_gradient(m), t, &rv[3], &rv[4]);
1975 if(wind(&rv[1], &rv[2], &rv[3]) != wind(&rv[2], &rv[3], &rv[4])) {
1976 rv[0].x = rv[3].x; rv[0].y = rv[3].y;
1977 rv[3].x = rv[4].x; rv[3].y = rv[4].y;
1978 rv[4].x = rv[0].x; rv[4].y = rv[0].y;
1981 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, rv[1].x, rv[1].y, 0.));
1982 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[2].x, rv[2].y, 0.));
1983 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[3].x, rv[3].y, 0.));
1984 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, rv[4].x, rv[4].y, 0.));
1985 vlist = rect_with_attachments(pad_rad(pad),
1986 rv[1].x, rv[1].y,
1987 rv[2].x, rv[2].y,
1988 rv[3].x, rv[3].y,
1989 rv[4].x, rv[4].y,
1990 l - r->layers);
1991 bbox = toporouter_bbox_create(l - r->layers, vlist, PAD, pad);
1992 r->bboxes = g_slist_prepend(r->bboxes, bbox);
1993 insert_constraints_from_list(r, l, vlist, bbox);
1994 g_list_free(vlist);
1996 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., 0.) );
1997 bbox->point = GTS_POINT( insert_vertex(r, l, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., bbox) );
1998 g_assert(TOPOROUTER_VERTEX(bbox->point)->bbox == bbox);
2002 }else {
2003 /* Either round pad or pad with curved edges */
2005 if(x[0] == x[1] && y[0] == y[1]) {
2006 /* One point */
2008 /* bounding box same as square pad */
2009 vlist = rect_with_attachments(pad_rad(pad),
2010 x[0]-t, y[0]-t,
2011 x[0]-t, y[0]+t,
2012 x[0]+t, y[0]+t,
2013 x[0]+t, y[0]-t,
2014 l - r->layers);
2015 bbox = toporouter_bbox_create(l - r->layers, vlist, PAD, pad);
2016 r->bboxes = g_slist_prepend(r->bboxes, bbox);
2017 g_list_free(vlist);
2019 //bbox->point = GTS_POINT( insert_vertex(r, l, x[0], y[0], bbox) );
2020 bbox->point = GTS_POINT( insert_vertex(r, l, x[0], y[0], bbox) );
2022 }else{
2023 /* Two points and one constraint edge */
2025 /* the rest is just for bounding box */
2026 m = cartesian_gradient(x[0], y[0], x[1], y[1]);
2028 p[0].x = x[0]; p[0].y = y[0];
2029 p[1].x = x[1]; p[1].y = y[1];
2031 vertex_outside_segment(&p[0], &p[1], t, &rv[0]);
2032 vertices_on_line(&rv[0], perpendicular_gradient(m), t, &rv[1], &rv[2]);
2034 vertex_outside_segment(&p[1], &p[0], t, &rv[0]);
2035 vertices_on_line(&rv[0], perpendicular_gradient(m), t, &rv[3], &rv[4]);
2037 if(wind(&rv[1], &rv[2], &rv[3]) != wind(&rv[2], &rv[3], &rv[4])) {
2038 rv[0].x = rv[3].x; rv[0].y = rv[3].y;
2039 rv[3].x = rv[4].x; rv[3].y = rv[4].y;
2040 rv[4].x = rv[0].x; rv[4].y = rv[0].y;
2043 vlist = rect_with_attachments(pad_rad(pad),
2044 rv[1].x, rv[1].y,
2045 rv[2].x, rv[2].y,
2046 rv[3].x, rv[3].y,
2047 rv[4].x, rv[4].y,
2048 l - r->layers);
2049 bbox = toporouter_bbox_create(l - r->layers, vlist, PAD, pad);
2050 r->bboxes = g_slist_prepend(r->bboxes, bbox);
2051 insert_constraints_from_list(r, l, vlist, bbox);
2052 g_list_free(vlist);
2054 //bbox->point = GTS_POINT( gts_vertex_new(vertex_class, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., 0.) );
2055 bbox->point = GTS_POINT( insert_vertex(r, l, (x[0] + x[1]) / 2., (y[0] + y[1]) / 2., bbox) );
2057 //bbox->constraints = g_list_concat(bbox->constraints, insert_constraint_edge(r, l, x[0], y[0], x[1], y[1], bbox));
2066 END_LOOP;
2068 END_LOOP;
2070 return 0;
2074 * Read points data (all layers) into GList
2076 * Inserts pin and via points
2079 read_points(toporouter_t *r, toporouter_layer_t *l, int layer)
2081 gdouble x, y, t;
2083 GList *vlist = NULL;
2084 toporouter_bbox_t *bbox = NULL;
2086 ELEMENT_LOOP(PCB->Data);
2088 PIN_LOOP(element);
2091 t = (gdouble)pin->Thickness / 2.0f;
2092 x = pin->X;
2093 y = pin->Y;
2095 if(TEST_FLAG (SQUAREFLAG, pin)) {
2097 vlist = rect_with_attachments(pin_rad(pin),
2098 x-t, y-t,
2099 x-t, y+t,
2100 x+t, y+t,
2101 x+t, y-t,
2102 l - r->layers);
2103 bbox = toporouter_bbox_create(l - r->layers, vlist, PIN, pin);
2104 r->bboxes = g_slist_prepend(r->bboxes, bbox);
2105 insert_constraints_from_list(r, l, vlist, bbox);
2106 g_list_free(vlist);
2107 bbox->point = GTS_POINT( insert_vertex(r, l, x, y, bbox) );
2109 }else if(TEST_FLAG(OCTAGONFLAG, pin)){
2110 /* TODO: Handle octagon pins */
2111 fprintf(stderr, "No support for octagon pins yet\n");
2112 }else{
2113 vlist = rect_with_attachments(pin_rad(pin),
2114 x-t, y-t,
2115 x-t, y+t,
2116 x+t, y+t,
2117 x+t, y-t,
2118 l - r->layers);
2119 bbox = toporouter_bbox_create(l - r->layers, vlist, PIN, pin);
2120 r->bboxes = g_slist_prepend(r->bboxes, bbox);
2121 g_list_free(vlist);
2122 bbox->point = GTS_POINT( insert_vertex(r, l, x, y, bbox) );
2125 END_LOOP;
2127 END_LOOP;
2129 VIA_LOOP(PCB->Data);
2132 t = (gdouble)via->Thickness / 2.0f;
2133 x = via->X;
2134 y = via->Y;
2136 if(TEST_FLAG (SQUAREFLAG, via)) {
2138 vlist = rect_with_attachments(pin_rad((PinType*)via),
2139 x-t, y-t,
2140 x-t, y+t,
2141 x+t, y+t,
2142 x+t, y-t,
2143 l - r->layers);
2144 bbox = toporouter_bbox_create(l - r->layers, vlist, VIA, via);
2145 r->bboxes = g_slist_prepend(r->bboxes, bbox);
2146 insert_constraints_from_list(r, l, vlist, bbox);
2147 g_list_free(vlist);
2148 bbox->point = GTS_POINT( insert_vertex(r, l, x, y, bbox) );
2150 }else if(TEST_FLAG(OCTAGONFLAG, via)){
2151 /* TODO: Handle octagon vias */
2152 fprintf(stderr, "No support for octagon vias yet\n");
2153 }else{
2155 vlist = rect_with_attachments(pin_rad((PinType*)via),
2156 x-t, y-t,
2157 x-t, y+t,
2158 x+t, y+t,
2159 x+t, y-t,
2160 l - r->layers);
2161 bbox = toporouter_bbox_create(l - r->layers, vlist, VIA, via);
2162 r->bboxes = g_slist_prepend(r->bboxes, bbox);
2163 g_list_free(vlist);
2165 bbox->point = GTS_POINT( insert_vertex(r, l, x, y, bbox) );
2169 END_LOOP;
2170 return 0;
2174 * Read line data from layer into toporouter_layer_t struct
2176 * Inserts points and constraints into GLists
2179 read_lines(toporouter_t *r, toporouter_layer_t *l, LayerType *layer, int ln)
2181 gdouble xs[2], ys[2];
2183 GList *vlist = NULL;
2184 toporouter_bbox_t *bbox = NULL;
2186 GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
2188 LINE_LOOP(layer);
2190 xs[0] = line->Point1.X;
2191 xs[1] = line->Point2.X;
2192 ys[0] = line->Point1.Y;
2193 ys[1] = line->Point2.Y;
2194 if(!(xs[0] == xs[1] && ys[0] == ys[1])) {
2195 vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, xs[0], ys[0], l - r->layers));
2196 vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, xs[1], ys[1], l - r->layers));
2197 bbox = toporouter_bbox_create_from_points(GetLayerGroupNumberByNumber(ln), vlist, LINE, line);
2198 r->bboxes = g_slist_prepend(r->bboxes, bbox);
2199 g_list_free(vlist);
2201 bbox->constraints = g_list_concat(bbox->constraints, insert_constraint_edge(r, l, xs[0], ys[0], 0, xs[1], ys[1], 0, bbox));
2204 END_LOOP;
2206 return 0;
2211 void
2212 create_board_edge(gdouble x0, gdouble y0, gdouble x1, gdouble y1, gdouble max, gint layer, GList **vlist)
2214 GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
2215 gdouble d = sqrt(pow(x0-x1,2) + pow(y0-y1,2));
2216 guint n = d / max, count = 1;
2217 gdouble inc = n ? d / n : d;
2218 gdouble x = x0, y = y0;
2220 *vlist = g_list_prepend(*vlist, gts_vertex_new (vertex_class, x0, y0, layer));
2222 while(count < n) {
2223 coord_move_towards_coord_values(x0, y0, x1, y1, inc, &x, &y);
2224 *vlist = g_list_prepend(*vlist, gts_vertex_new (vertex_class, x, y, layer));
2226 x0 = x; y0 = y;
2227 count++;
2234 read_board_constraints(toporouter_t *r, toporouter_layer_t *l, int layer)
2236 // GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
2237 GList *vlist = NULL;
2238 toporouter_bbox_t *bbox = NULL;
2240 /* Add points for corners of board, and constrain those edges */
2241 // vlist = g_list_prepend(NULL, gts_vertex_new (vertex_class, 0., 0., layer));
2242 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, PCB->MaxWidth, 0., layer));
2243 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, PCB->MaxWidth, PCB->MaxHeight, layer));
2244 // vlist = g_list_prepend(vlist, gts_vertex_new (vertex_class, 0., PCB->MaxHeight, layer));
2246 create_board_edge(0., 0., PCB->MaxWidth, 0., 10000., layer, &vlist);
2247 create_board_edge(PCB->MaxWidth, 0., PCB->MaxWidth, PCB->MaxHeight, 10000., layer, &vlist);
2248 create_board_edge(PCB->MaxWidth, PCB->MaxHeight, 0., PCB->MaxHeight, 10000., layer, &vlist);
2249 create_board_edge(0., PCB->MaxHeight, 0., 0., 10000., layer, &vlist);
2251 bbox = toporouter_bbox_create(layer, vlist, BOARD, NULL);
2252 r->bboxes = g_slist_prepend(r->bboxes, bbox);
2253 insert_constraints_from_list(r, l, vlist, bbox);
2254 g_list_free(vlist);
2256 return 0;
2259 gdouble
2260 triangle_cost(GtsTriangle *t, gpointer *data){
2262 gdouble *min_quality = data[0];
2263 gdouble *max_area = data[1];
2264 gdouble quality = gts_triangle_quality(t);
2265 gdouble area = gts_triangle_area(t);
2267 if (quality < *min_quality || area > *max_area)
2268 return quality;
2269 return 0.0;
2275 void
2276 build_cdt(toporouter_t *r, toporouter_layer_t *l)
2278 /* TODO: generalize into surface *cdt_create(vertices, constraints) */
2279 GList *i;
2280 GtsEdge *temp;
2281 GtsVertex *v;
2282 GtsTriangle *t;
2283 GtsVertex *v1, *v2, *v3;
2284 GSList *vertices_slist = list_to_slist(l->vertices);
2287 t = gts_triangle_enclosing (gts_triangle_class (), vertices_slist, 1000.0f);
2288 gts_triangle_vertices (t, &v1, &v2, &v3);
2290 g_slist_free(vertices_slist);
2292 l->surface = gts_surface_new (gts_surface_class (), gts_face_class (),
2293 GTS_EDGE_CLASS(toporouter_edge_class ()), GTS_VERTEX_CLASS(toporouter_vertex_class ()) );
2295 gts_surface_add_face (l->surface, gts_face_new (gts_face_class (), t->e1, t->e2, t->e3));
2297 i = l->vertices;
2298 while (i) {
2299 v = i->data;
2300 //if(r->flags & TOPOROUTER_FLAG_DEBUG_CDTS)
2301 // fprintf(stderr, "\tadding vertex %f,%f\n", v->p.x, v->p.y);
2302 g_assert (gts_delaunay_add_vertex (l->surface, i->data, NULL) == NULL);
2303 i = i->next;
2306 // fprintf(stderr, "ADDED VERTICES\n");
2308 if((debugface = gts_delaunay_check(l->surface))) {
2309 fprintf(stderr, "WARNING: Delaunay check failed\n");
2310 fprintf(stderr, "\tViolating triangle:\n");
2311 fprintf(stderr, "\t%f,%f %f,%f\n",
2312 debugface->triangle.e1->segment.v1->p.x,
2313 debugface->triangle.e1->segment.v1->p.y,
2314 debugface->triangle.e1->segment.v2->p.x,
2315 debugface->triangle.e1->segment.v2->p.y
2317 fprintf(stderr, "\t%f,%f %f,%f\n",
2318 debugface->triangle.e2->segment.v1->p.x,
2319 debugface->triangle.e2->segment.v1->p.y,
2320 debugface->triangle.e2->segment.v2->p.x,
2321 debugface->triangle.e2->segment.v2->p.y
2323 fprintf(stderr, "\t%f,%f %f,%f\n",
2324 debugface->triangle.e3->segment.v1->p.x,
2325 debugface->triangle.e3->segment.v1->p.y,
2326 debugface->triangle.e3->segment.v2->p.x,
2327 debugface->triangle.e3->segment.v2->p.y
2329 if((f=fopen("fail.oogl", "w")) == NULL) {
2330 fprintf(stderr, "Error opening file fail.oogl for output\n");
2331 }else{
2332 gts_surface_write_oogl(l->surface, f);
2333 fclose(f);
2335 toporouter_draw_surface(l->surface, "debug.png", 4096, 4096);
2339 i = l->constraints;
2340 while (i) {
2341 temp = i->data;
2342 //if(r->flags & TOPOROUTER_FLAG_DEBUG_CDTS)
2343 /* fprintf(r->debug, "edge p1=%f,%f p2=%f,%f\n",
2344 temp->segment.v1->p.x,
2345 temp->segment.v1->p.y,
2346 temp->segment.v2->p.x,
2347 temp->segment.v2->p.y);
2349 g_assert (gts_delaunay_add_constraint (l->surface, i->data) == NULL);
2350 i = i->next;
2352 // fprintf(stderr, "ADDED CONSTRAINTS\n");
2353 gts_allow_floating_vertices = TRUE;
2354 gts_object_destroy (GTS_OBJECT (v1));
2355 gts_object_destroy (GTS_OBJECT (v2));
2356 gts_object_destroy (GTS_OBJECT (v3));
2357 gts_allow_floating_vertices = FALSE;
2360 gpointer data[2];
2361 gdouble quality = 0.50, area = G_MAXDOUBLE;
2362 guint num = gts_delaunay_conform(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL);
2364 if (num == 0){
2365 data[0] = &quality;
2366 data[1] = &area;
2367 num = gts_delaunay_refine(l->surface, -1, (GtsEncroachFunc) gts_vertex_encroaches_edge, NULL, (GtsKeyFunc) triangle_cost, data);
2371 #ifdef DEBUG_IMPORT
2372 gts_surface_print_stats(l->surface, stderr);
2373 #endif
2376 gint
2377 visited_cmp(gconstpointer a, gconstpointer b)
2379 if(a<b) return -1;
2380 if(a>b) return 1;
2381 return 0;
2384 gdouble
2385 coord_xangle(gdouble ax, gdouble ay, gdouble bx, gdouble by)
2387 gdouble dx, dy, theta;
2389 dx = fabs(ax - bx);
2390 dy = fabs(ay - by);
2392 if(dx < EPSILON) {
2393 theta = M_PI / 2.;
2394 } else theta = atan(dy/dx);
2396 if(by <= ay) {
2397 if(bx < ax) theta = M_PI - theta;
2398 }else{
2399 if(bx < ax) theta += M_PI;
2400 else theta = (2 * M_PI) - theta;
2403 return theta;
2406 gdouble
2407 point_xangle(GtsPoint *a, GtsPoint *b)
2409 gdouble dx, dy, theta;
2411 dx = fabs(a->x - b->x);
2412 dy = fabs(a->y - b->y);
2414 if(dx < EPSILON) {
2415 theta = M_PI / 2.;
2416 } else theta = atan(dy/dx);
2418 if(b->y >= a->y) {
2419 if(b->x < a->x) theta = M_PI - theta;
2420 }else{
2421 if(b->x < a->x) theta += M_PI;
2422 else theta = (2 * M_PI) - theta;
2425 return theta;
2429 GList *
2430 cluster_vertices(toporouter_t *r, toporouter_cluster_t *c)
2432 GList *rval = NULL;
2434 if(!c) return NULL;
2436 FOREACH_CLUSTER(c->netlist->clusters) {
2437 if((r->flags & TOPOROUTER_FLAG_AFTERRUBIX && cluster->c == c->c) || (!(r->flags & TOPOROUTER_FLAG_AFTERRUBIX) && cluster == c)) {
2438 FOREACH_BBOX(cluster->boxes) {
2439 if(box->type == LINE) {
2440 g_assert(box->constraints->data);
2441 rval = g_list_prepend(rval, tedge_v1(box->constraints->data));
2442 rval = g_list_prepend(rval, tedge_v2(box->constraints->data));
2443 }else if(box->point) {
2444 rval = g_list_prepend(rval, TOPOROUTER_VERTEX(box->point));
2445 //g_assert(vertex_bbox(TOPOROUTER_VERTEX(box->point)) == box);
2446 }else {
2447 printf("WARNING: cluster_vertices: unhandled bbox type\n");
2450 } FOREACH_END;
2455 } FOREACH_END;
2457 return rval;
2460 void
2461 print_cluster(toporouter_cluster_t *c)
2464 if(!c) {
2465 printf("[CLUSTER (NULL)]\n");
2466 return;
2469 printf("CLUSTER %d: NETLIST = %s STYLE = %s\n", c->c, c->netlist->netlist, c->netlist->style);
2471 FOREACH_BBOX(c->boxes) {
2472 print_bbox(box);
2473 } FOREACH_END;
2477 toporouter_cluster_t *
2478 cluster_create(toporouter_t *r, toporouter_netlist_t *netlist)
2480 toporouter_cluster_t *c = malloc(sizeof(toporouter_cluster_t));
2482 c->c = c->pc = netlist->clusters->len;
2483 g_ptr_array_add(netlist->clusters, c);
2484 c->netlist = netlist;
2485 c->boxes = g_ptr_array_new();
2487 return c;
2490 toporouter_bbox_t *
2491 toporouter_bbox_locate(toporouter_t *r, toporouter_term_t type, void *data, gdouble x, gdouble y, guint layergroup)
2493 GtsPoint *p = gts_point_new(gts_point_class(), x, y, layergroup);
2494 GSList *boxes = gts_bb_tree_stabbed(r->bboxtree, p), *i = boxes;
2496 gts_object_destroy(GTS_OBJECT(p));
2498 while(i) {
2499 toporouter_bbox_t *box = TOPOROUTER_BBOX(i->data);
2501 if(box->type == type && box->data == data) {
2502 g_slist_free(boxes);
2503 return box;
2506 i = i->next;
2509 g_slist_free(boxes);
2510 return NULL;
2513 void
2514 cluster_join_bbox(toporouter_cluster_t *cluster, toporouter_bbox_t *box)
2516 if(box) {
2517 g_ptr_array_add(cluster->boxes, box);
2518 box->cluster = cluster;
2522 toporouter_netlist_t *
2523 netlist_create(toporouter_t *r, char *netlist, char *style)
2525 toporouter_netlist_t *nl = malloc(sizeof(toporouter_netlist_t));
2526 nl->netlist = netlist;
2527 nl->style = style;
2528 nl->clusters = g_ptr_array_new();
2529 nl->routes = g_ptr_array_new();
2530 nl->routed = NULL;
2531 nl->pair = NULL;
2532 g_ptr_array_add(r->netlists, nl);
2533 return nl;
2536 void
2537 import_clusters(toporouter_t *r)
2539 NetListListType nets;
2540 ResetFoundPinsViasAndPads (False);
2541 ResetFoundLinesAndPolygons (False);
2542 nets = CollectSubnets(False);
2543 NETLIST_LOOP(&nets);
2545 if(netlist->NetN > 0) {
2546 toporouter_netlist_t *nl = netlist_create(r, netlist->Net->Connection->menu->Name, netlist->Net->Connection->menu->Style);
2548 NET_LOOP(netlist);
2551 toporouter_cluster_t *cluster = cluster_create(r, nl);
2552 #ifdef DEBUG_MERGING
2553 printf("NET:\n");
2554 #endif
2555 CONNECTION_LOOP (net);
2558 if(connection->type == LINE_TYPE) {
2559 LineType *line = (LineType *) connection->ptr2;
2560 toporouter_bbox_t *box = toporouter_bbox_locate(r, LINE, line, connection->X, connection->Y, connection->group);
2561 cluster_join_bbox(cluster, box);
2563 #ifdef DEBUG_MERGING
2564 printf("\tLINE %d,%d\n", connection->X, connection->Y);
2565 #endif
2566 }else if(connection->type == PAD_TYPE) {
2567 PadType *pad = (PadType *) connection->ptr2;
2568 toporouter_bbox_t *box = toporouter_bbox_locate(r, PAD, pad, connection->X, connection->Y, connection->group);
2569 cluster_join_bbox(cluster, box);
2571 #ifdef DEBUG_MERGING
2572 printf("\tPAD %d,%d\n", connection->X, connection->Y);
2573 #endif
2574 }else if(connection->type == PIN_TYPE) {
2576 for(guint m=0;m<groupcount();m++) {
2577 PinType *pin = (PinType *) connection->ptr2;
2578 toporouter_bbox_t *box = toporouter_bbox_locate(r, PIN, pin, connection->X, connection->Y, m);
2579 cluster_join_bbox(cluster, box);
2582 #ifdef DEBUG_MERGING
2583 printf("\tPIN %d,%d\n", connection->X, connection->Y);
2584 #endif
2585 }else if(connection->type == VIA_TYPE) {
2587 for(guint m=0;m<groupcount();m++) {
2588 PinType *pin = (PinType *) connection->ptr2;
2589 toporouter_bbox_t *box = toporouter_bbox_locate(r, VIA, pin, connection->X, connection->Y, m);
2590 cluster_join_bbox(cluster, box);
2593 #ifdef DEBUG_MERGING
2594 printf("\tVIA %d,%d\n", connection->X, connection->Y);
2595 #endif
2596 }else if(connection->type == POLYGON_TYPE) {
2597 PolygonType *polygon = (PolygonType *) connection->ptr2;
2598 toporouter_bbox_t *box = toporouter_bbox_locate(r, POLYGON, polygon, connection->X, connection->Y, connection->group);
2599 cluster_join_bbox(cluster, box);
2601 #ifdef DEBUG_MERGING
2602 printf("\tPOLYGON %d,%d\n", connection->X, connection->Y);
2603 #endif
2607 END_LOOP;
2608 #ifdef DEBUG_MERGING
2609 printf("\n");
2610 #endif
2612 END_LOOP;
2616 END_LOOP;
2617 FreeNetListListMemory(&nets);
2620 void
2621 import_geometry(toporouter_t *r)
2623 toporouter_layer_t *cur_layer;
2625 int group;
2627 #ifdef DEBUG_IMPORT
2628 for (group = 0; group < max_layer; group++) {
2629 printf("Group %d: Number %d:\n", group, PCB->LayerGroups.Number[group]);
2631 for (int entry = 0; entry < PCB->LayerGroups.Number[group]; entry++) {
2632 printf("\tEntry %d\n", PCB->LayerGroups.Entries[group][entry]);
2635 #endif
2636 /* Allocate space for per layer struct */
2637 cur_layer = r->layers = malloc(groupcount() * sizeof(toporouter_layer_t));
2639 /* Foreach layer, read in pad vertices and constraints, and build CDT */
2640 for (group = 0; group < max_layer; group++) {
2641 #ifdef DEBUG_IMPORT
2642 printf("*** LAYER GROUP %d ***\n", group);
2643 #endif
2644 if(PCB->LayerGroups.Number[group] > 0){
2645 cur_layer->vertices = NULL;
2646 cur_layer->constraints = NULL;
2648 #ifdef DEBUG_IMPORT
2649 printf("reading board constraints from layer %d into group %d\n", PCB->LayerGroups.Entries[group][0], group);
2650 #endif
2651 read_board_constraints(r, cur_layer, PCB->LayerGroups.Entries[group][0]);
2652 #ifdef DEBUG_IMPORT
2653 printf("reading points from layer %d into group %d \n",PCB->LayerGroups.Entries[group][0], group);
2654 #endif
2655 read_points(r, cur_layer, PCB->LayerGroups.Entries[group][0]);
2657 //#ifdef DEBUG_IMPORT
2658 // printf("reading pads from layer %d into group %d\n", number, group);
2659 //#endif
2660 read_pads(r, cur_layer, group);
2662 GROUP_LOOP(PCB->Data, group)
2665 #ifdef DEBUG_IMPORT
2666 printf("reading lines from layer %d into group %d\n", number, group);
2667 #endif
2668 read_lines(r, cur_layer, layer, number);
2671 END_LOOP;
2675 #ifdef DEBUG_IMPORT
2676 printf("building CDT\n");
2677 #endif
2678 build_cdt(r, cur_layer);
2679 #ifdef DEBUG_IMPORT
2680 printf("finished building CDT\n");
2681 #endif
2682 cur_layer++;
2686 r->bboxtree = gts_bb_tree_new(r->bboxes);
2688 import_clusters(r);
2690 #ifdef DEBUG_IMPORT
2691 printf("finished import!\n");
2692 #endif
2696 gint
2697 compare_points(gconstpointer a, gconstpointer b)
2699 GtsPoint *i = GTS_POINT(a);
2700 GtsPoint *j = GTS_POINT(b);
2702 if(i->x == j->x) {
2703 if(i->y == j->y) return 0;
2704 if(i->y < j->y) return -1;
2705 return 1;
2707 if(i->x < j->x) return -1;
2708 return 1;
2711 gint
2712 compare_segments(gconstpointer a, gconstpointer b)
2714 if(a == b) return 0;
2715 if(a < b) return -1;
2716 return 1;
2719 toporouter_cluster_t *
2720 cluster_find(toporouter_t *r, gdouble x, gdouble y, gdouble z)
2722 GtsPoint *p = gts_point_new(gts_point_class(), x, y, z);
2723 GSList *hits = gts_bb_tree_stabbed(r->bboxtree, p);
2724 toporouter_cluster_t *rval = NULL;
2726 #ifdef DEBUG_CLUSTER_FIND
2727 printf("FINDING %f,%f,%f\n\n", x, y, z);
2728 #endif
2730 while(hits) {
2731 toporouter_bbox_t *box = TOPOROUTER_BBOX(hits->data);
2733 #ifdef DEBUG_CLUSTER_FIND
2734 printf("HIT BOX: "); print_bbox(box);
2735 #endif
2737 if(box->layer == (int)z) {
2738 if(box->type != BOARD) {
2739 if(box->type == LINE) {
2740 LineType *line = (LineType *)box->data;
2741 gint linewind = coord_wind(line->Point1.X, line->Point1.Y, x, y, line->Point2.X, line->Point2.Y);
2743 if(!linewind) {
2744 rval = box->cluster;
2745 //break;
2748 }else if(box->surface) {
2750 if(gts_point_locate(p, box->surface, NULL)) {
2751 rval = box->cluster;
2752 break;
2758 hits = hits->next;
2761 gts_object_destroy(GTS_OBJECT(p));
2764 #ifdef DEBUG_CLUSTER_FIND
2765 printf("cluster_find: %f,%f,%f: ", x, y, z);
2766 print_cluster(rval);
2767 #endif
2769 return rval;
2772 gdouble
2773 simple_h_cost(toporouter_t *r, toporouter_vertex_t *curpoint, toporouter_vertex_t *destpoint)
2775 gdouble layerpenalty = (vz(curpoint) == vz(destpoint)) ? 0. : r->viacost;
2777 return gts_point_distance(GTS_POINT(curpoint), GTS_POINT(destpoint)) + layerpenalty;
2780 #define FCOST(x) (x->gcost + x->hcost)
2781 gdouble
2782 route_heap_cmp(gpointer item, gpointer data)
2784 return FCOST(TOPOROUTER_VERTEX(item));
2787 #define closelist_insert(p) closelist = g_list_prepend(closelist, p)
2789 typedef struct {
2790 toporouter_vertex_t *key;
2791 toporouter_vertex_t *result;
2792 }toporouter_heap_search_data_t;
2794 void
2795 toporouter_heap_search(gpointer data, gpointer user_data)
2797 toporouter_vertex_t *v = TOPOROUTER_VERTEX(data);
2798 toporouter_heap_search_data_t *heap_search_data = (toporouter_heap_search_data_t *)user_data;
2799 if(v == heap_search_data->key) heap_search_data->result = v;
2802 void
2803 toporouter_heap_color(gpointer data, gpointer user_data)
2805 toporouter_vertex_t *v = TOPOROUTER_VERTEX(data);
2806 v->flags |= (unsigned int) user_data;
2809 inline gdouble
2810 angle_span(gdouble a1, gdouble a2)
2812 if(a1 > a2)
2813 return ((2*M_PI)-a1 + a2);
2814 return a2-a1;
2817 gdouble
2818 region_span(toporouter_vertex_region_t *region)
2820 gdouble a1,a2;
2822 g_assert(region->v1 != NULL);
2823 g_assert(region->v2 != NULL);
2824 g_assert(region->origin != NULL);
2826 a1 = point_xangle(GTS_POINT(region->origin), GTS_POINT(region->v1));
2827 a2 = point_xangle(GTS_POINT(region->origin), GTS_POINT(region->v2));
2829 return angle_span(a1, a2);
2832 gdouble
2833 edge_capacity(toporouter_edge_t *e)
2835 return gts_point_distance(GTS_POINT(edge_v1(e)), GTS_POINT(edge_v2(e)));
2838 gdouble
2839 edge_flow(toporouter_edge_t *e, toporouter_vertex_t *v1, toporouter_vertex_t *v2, toporouter_vertex_t *dest)
2841 GList *i = edge_routing(e);
2842 toporouter_vertex_t *pv = tedge_v1(e), *v = NULL;
2843 gdouble flow = 0.;
2844 guint waiting = 1;
2846 if((pv == v1 || pv == v2) && waiting) {
2847 flow += min_vertex_net_spacing(pv, dest);
2848 pv = dest;
2849 waiting = 0;
2852 g_assert(v1 != v2);
2854 while(i) {
2855 v = TOPOROUTER_VERTEX(i->data);
2858 if(pv == dest)
2859 flow += min_vertex_net_spacing(v, pv);
2860 else
2861 flow += min_spacing(v, pv);
2863 if((v == v1 || v == v2) && waiting) {
2864 flow += min_vertex_net_spacing(v, dest);
2865 pv = dest;
2866 waiting = 0;
2867 }else{
2868 pv = v;
2870 i = i->next;
2873 if(pv == dest)
2874 flow += min_vertex_net_spacing(tedge_v2(e), pv);
2875 else
2876 flow += min_spacing(tedge_v2(e), pv);
2878 return flow;
2881 void
2882 print_path(GList *path)
2884 GList *i = path;
2886 printf("PATH:\n");
2887 while(i) {
2888 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
2889 // printf("[V %f,%f,%f]\n", vx(v), vy(v), vz(v));
2890 print_vertex(v);
2892 if(v->child && !g_list_find(path, v->child))
2893 printf("\t CHILD NOT IN LIST\n");
2894 if(v->parent && !g_list_find(path, v->parent))
2895 printf("\t parent NOT IN LIST\n");
2896 i = i->next;
2902 GList *
2903 split_path(GList *path)
2905 toporouter_vertex_t *pv = NULL;
2906 GList *curpath = NULL, *i, *paths = NULL;
2907 #ifdef DEBUG_ROUTE
2908 printf("PATH:\n");
2909 #endif
2910 i = path;
2911 while(i) {
2912 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
2914 #ifdef DEBUG_ROUTE
2915 printf("v = %f,%f ", vx(v), vy(v));
2916 if(v->parent) printf("parent = %f,%f ", vx(v->parent), vy(v->parent));
2917 if(v->child) printf("child = %f,%f ", vx(v->child), vy(v->child));
2918 printf("\n");
2919 #endif
2920 // printf("***\n");
2921 // if(v) printf("v = %f,%f\n", GTS_POINT(v)->x, GTS_POINT(v)->y);
2922 // if(pv) printf("pv = %f,%f\n", GTS_POINT(pv)->x, GTS_POINT(pv)->y);
2925 if(pv)
2926 if(GTS_POINT(v)->x == GTS_POINT(pv)->x && GTS_POINT(v)->y == GTS_POINT(pv)->y) {
2927 if(g_list_length(curpath) > 1) paths = g_list_prepend(paths, curpath);
2928 curpath = NULL;
2930 pv->child = NULL;
2931 v->parent = NULL;
2934 curpath = g_list_append(curpath, v);
2936 pv = v;
2937 i = i->next;
2940 if(g_list_length(curpath) > 1)
2941 paths = g_list_prepend(paths, curpath);
2943 return paths;
2948 #define edge_gradient(e) (cartesian_gradient(GTS_POINT(GTS_SEGMENT(e)->v1)->x, GTS_POINT(GTS_SEGMENT(e)->v1)->y, \
2949 GTS_POINT(GTS_SEGMENT(e)->v2)->x, GTS_POINT(GTS_SEGMENT(e)->v2)->y))
2952 /* sorting into ascending distance from v1 */
2953 gint
2954 routing_edge_insert(gconstpointer a, gconstpointer b, gpointer user_data)
2956 GtsPoint *v1 = GTS_POINT(edge_v1(user_data));
2958 if(gts_point_distance2(v1, GTS_POINT(a)) < gts_point_distance2(v1, GTS_POINT(b)) - EPSILON)
2959 return -1;
2960 if(gts_point_distance2(v1, GTS_POINT(a)) > gts_point_distance2(v1, GTS_POINT(b)) + EPSILON)
2961 return 1;
2963 printf("a = %x b = %x\n", (int) a, (int) b);
2965 printf("WARNING: routing_edge_insert() with same points..\n \
2966 v1 @ %f,%f\n\
2967 a @ %f,%f\n\
2968 b @ %f,%f\n",
2969 v1->x, v1->y,
2970 vx(a), vy(a),
2971 vx(a), vy(b));
2972 printf("A: "); print_vertex(TOPOROUTER_VERTEX(a));
2973 printf("B: "); print_vertex(TOPOROUTER_VERTEX(b));
2975 TOPOROUTER_VERTEX(a)->flags |= VERTEX_FLAG_RED;
2976 TOPOROUTER_VERTEX(b)->flags |= VERTEX_FLAG_RED;
2978 return 0;
2981 void
2982 print_edge(toporouter_edge_t *e)
2984 GList *i = edge_routing(e);
2986 printf("EDGE:\n");
2988 print_vertex(tedge_v1(e));
2990 while(i) {
2991 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
2992 print_vertex(v);
2993 i = i->next;
2996 print_vertex(tedge_v2(e));
2999 toporouter_vertex_t *
3000 new_temp_toporoutervertex(gdouble x, gdouble y, toporouter_edge_t *e)
3002 GtsVertexClass *vertex_class = GTS_VERTEX_CLASS (toporouter_vertex_class ());
3003 GList *i = edge_routing(e);
3004 toporouter_vertex_t *r;
3005 ///*
3006 while(i) {
3007 r = TOPOROUTER_VERTEX(i->data);
3008 if(epsilon_equals(vx(r),x) && epsilon_equals(vy(r),y)) {
3009 if(r->flags & VERTEX_FLAG_TEMP) return r;
3011 i = i->next;
3013 //*/
3014 r = TOPOROUTER_VERTEX( gts_vertex_new (vertex_class, x, y, vz(edge_v1(e))) );
3015 r->flags |= VERTEX_FLAG_TEMP;
3016 r->routingedge = e;
3018 if(TOPOROUTER_IS_CONSTRAINT(e))
3019 TOPOROUTER_CONSTRAINT(e)->routing = g_list_insert_sorted_with_data(edge_routing(e), r, routing_edge_insert, e);
3020 else
3021 e->routing = g_list_insert_sorted_with_data(edge_routing(e), r, routing_edge_insert, e);
3023 return r;
3027 /* create vertex on edge e at radius r from v, closest to ref */
3028 toporouter_vertex_t *
3029 new_temp_toporoutervertex_in_segment(toporouter_edge_t *e, toporouter_vertex_t *v, gdouble r, toporouter_vertex_t *ref)
3031 gdouble m = edge_gradient(e);
3032 toporouter_spoint_t p, np1, np2;
3033 // toporouter_vertex_t *b = TOPOROUTER_VERTEX((GTS_VERTEX(v) == edge_v1(e)) ? edge_v2(e) : edge_v1(e));
3034 toporouter_vertex_t *rval = NULL;
3035 p.x = vx(v); p.y = vy(v);
3037 vertices_on_line(&p, m, r, &np1, &np2);
3039 if( (pow(np1.x - vx(ref), 2) + pow(np1.y - vy(ref), 2)) < (pow(np2.x - vx(ref), 2) + pow(np2.y - vy(ref), 2)) )
3040 rval = new_temp_toporoutervertex(np1.x, np1.y, e);
3041 else
3042 rval = new_temp_toporoutervertex(np2.x, np2.y, e);
3044 return rval;
3047 gint
3048 vertex_keepout_test(toporouter_t *r, toporouter_vertex_t *v)
3050 GList *i = r->keepoutlayers;
3051 while(i) {
3052 gdouble keepout = *((double *) i->data);
3053 if(vz(v) == keepout) return 1;
3054 i = i->next;
3056 return 0;
3059 void
3060 closest_cluster_pair(toporouter_t *r, GList *src_vertices, GList *dest_vertices, toporouter_vertex_t **a, toporouter_vertex_t **b)
3062 GList *i = src_vertices, *j = dest_vertices;
3064 gdouble min = 0.;
3065 *a = NULL; *b = NULL;
3067 i = src_vertices;
3068 while(i) {
3069 toporouter_vertex_t *v1 = TOPOROUTER_VERTEX(i->data);
3071 if(vertex_keepout_test(r, v1)) { i = i->next; continue; }
3073 j = dest_vertices;
3074 while(j) {
3075 toporouter_vertex_t *v2 = TOPOROUTER_VERTEX(j->data);
3076 if(vertex_keepout_test(r, v2) || vz(v2) != vz(v1)) { j = j->next; continue; }
3078 if(!*a) {
3079 *a = v1; *b = v2; min = simple_h_cost(r, *a, *b);
3080 }else{
3081 gdouble tempd = simple_h_cost(r, v1, v2);
3082 if(r->flags & TOPOROUTER_FLAG_GOFAR && tempd > min) {
3083 *a = v1; *b = v2; min = tempd;
3084 }else
3085 if(tempd < min) {
3086 *a = v1; *b = v2; min = tempd;
3090 j = j->next;
3093 i = i->next;
3096 // g_list_free(src_vertices);
3097 // g_list_free(dest_vertices);
3101 toporouter_vertex_t *
3102 closest_dest_vertex(toporouter_t *r, toporouter_vertex_t *v, toporouter_route_t *routedata)
3104 GList //*vertices = cluster_vertices(r, routedata->dest),
3105 *i = routedata->destvertices;
3106 toporouter_vertex_t *closest = NULL;
3107 gdouble closest_distance = 0.;
3109 // if(routedata->flags & TOPOROUTER_FLAG_FLEX) i = r->destboxes;
3111 while(i) {
3112 toporouter_vertex_t *cv = TOPOROUTER_VERTEX(i->data);
3114 if(vz(cv) != vz(v)) { i = i->next; continue; }
3116 if(!closest) {
3117 closest = cv; closest_distance = simple_h_cost(r, v, closest);
3118 }else{
3119 gdouble tempd = simple_h_cost(r, v, cv);
3120 if(r->flags & TOPOROUTER_FLAG_GOFAR && tempd > closest_distance) {
3121 closest = cv; closest_distance = tempd;
3122 }else
3123 if(tempd < closest_distance) {
3124 closest = cv; closest_distance = tempd;
3127 i = i->next;
3130 // g_list_free(vertices);
3132 #ifdef DEBUG_ROUTE
3133 printf("CLOSEST = %f,%f,%f\n", vx(closest), vy(closest), vz(closest));
3134 #endif
3135 return closest;
3138 #define toporouter_edge_gradient(e) (cartesian_gradient(vx(edge_v1(e)), vy(edge_v1(e)), vx(edge_v2(e)), vy(edge_v2(e))))
3141 /* returns the capacity of the triangle cut through v */
3142 gdouble
3143 triangle_interior_capacity(GtsTriangle *t, toporouter_vertex_t *v)
3145 toporouter_edge_t *e = TOPOROUTER_EDGE(gts_triangle_edge_opposite(t, GTS_VERTEX(v)));
3146 gdouble x, y, m1, m2, c2, c1, len;
3148 g_assert(e);
3150 m1 = toporouter_edge_gradient(e);
3151 m2 = perpendicular_gradient(m1);
3152 c2 = (isinf(m2)) ? vx(v) : vy(v) - (m2 * vx(v));
3153 c1 = (isinf(m1)) ? vx(edge_v1(e)) : vy(edge_v1(e)) - (m1 * vx(edge_v1(e)));
3155 if(isinf(m2))
3156 x = vx(v);
3157 else if(isinf(m1))
3158 x = vx(edge_v1(e));
3159 else
3160 x = (c2 - c1) / (m1 - m2);
3162 y = (isinf(m2)) ? vy(edge_v1(e)) : (m2 * x) + c2;
3164 len = gts_point_distance2(GTS_POINT(edge_v1(e)), GTS_POINT(edge_v2(e)));
3166 #ifdef DEBUG_ROUTE
3167 printf("%f,%f len = %f v = %f,%f\n", x, y, len, vx(v), vy(v));
3168 #endif
3170 if(epsilon_equals(x,vx(edge_v1(e))) && epsilon_equals(y,vy(edge_v1(e)))) return INFINITY;
3171 if(epsilon_equals(x,vx(edge_v2(e))) && epsilon_equals(y,vy(edge_v2(e)))) return INFINITY;
3173 if(x >= MIN(vx(edge_v1(e)),vx(edge_v2(e))) &&
3174 x <= MAX(vx(edge_v1(e)),vx(edge_v2(e))) &&
3175 y >= MIN(vy(edge_v1(e)),vy(edge_v2(e))) &&
3176 y <= MAX(vy(edge_v1(e)),vy(edge_v2(e))))
3178 // if( (pow(vx(edge_v1(e)) - x, 2) + pow(vy(edge_v1(e)) - y, 2)) < len && (pow(vx(edge_v2(e)) - x, 2) + pow(vy(edge_v2(e)) - y, 2)) < len )
3179 return sqrt(pow(vx(v) - x, 2) + pow(vy(v) - y, 2));
3181 return INFINITY;
3184 inline toporouter_vertex_t *
3185 segment_common_vertex(GtsSegment *s1, GtsSegment *s2)
3187 if(!s1 || !s2) return NULL;
3188 if(s1->v1 == s2->v1) return TOPOROUTER_VERTEX(s1->v1);
3189 if(s1->v2 == s2->v1) return TOPOROUTER_VERTEX(s1->v2);
3190 if(s1->v1 == s2->v2) return TOPOROUTER_VERTEX(s1->v1);
3191 if(s1->v2 == s2->v2) return TOPOROUTER_VERTEX(s1->v2);
3192 return NULL;
3195 inline toporouter_vertex_t *
3196 route_vertices_common_vertex(toporouter_vertex_t *v1, toporouter_vertex_t *v2)
3198 return segment_common_vertex(GTS_SEGMENT(v1->routingedge), GTS_SEGMENT(v2->routingedge));
3202 inline guint
3203 edges_third_edge(GtsSegment *s1, GtsSegment *s2, toporouter_vertex_t **v1, toporouter_vertex_t **v2)
3205 if(!s1 || !s2) return 0;
3206 if(s1->v1 == s2->v1) {
3207 *v1 = TOPOROUTER_VERTEX(s1->v2);
3208 *v2 = TOPOROUTER_VERTEX(s2->v2);
3209 return 1;
3211 if(s1->v2 == s2->v1) {
3212 *v1 = TOPOROUTER_VERTEX(s1->v1);
3213 *v2 = TOPOROUTER_VERTEX(s2->v2);
3214 return 1;
3216 if(s1->v1 == s2->v2) {
3217 *v1 = TOPOROUTER_VERTEX(s1->v2);
3218 *v2 = TOPOROUTER_VERTEX(s2->v1);
3219 return 1;
3221 if(s1->v2 == s2->v2) {
3222 *v1 = TOPOROUTER_VERTEX(s1->v1);
3223 *v2 = TOPOROUTER_VERTEX(s2->v1);
3224 return 1;
3226 return 0;
3229 /* returns the flow from e1 to e2, and the flow from the vertex oppisate e1 to
3230 * e1 and the vertex oppisate e2 to e2 */
3231 gdouble
3232 flow_from_edge_to_edge(GtsTriangle *t, toporouter_edge_t *e1, toporouter_edge_t *e2,
3233 toporouter_vertex_t *common_v, toporouter_vertex_t *curpoint)
3235 gdouble r = 0.;
3236 toporouter_vertex_t *pv = common_v, *v;
3237 toporouter_edge_t *op_edge;
3239 GList *i = edge_routing(e1);
3240 while(i) {
3241 v = TOPOROUTER_VERTEX(i->data);
3243 if(v == curpoint) {
3244 r += min_spacing(v, pv);
3245 pv = v;
3246 i = i->next; continue;
3248 // if(!(v->flags & VERTEX_FLAG_TEMP)) {
3249 if((v->flags & VERTEX_FLAG_ROUTE)) {
3250 if(v->parent)
3251 if(v->parent->routingedge == e2) {
3252 r += min_spacing(v, pv);
3253 pv = v;
3254 i = i->next; continue;
3257 if(v->child)
3258 if(v->child->routingedge == e2) {
3259 r += min_spacing(v, pv);
3260 pv = v;
3261 i = i->next; continue;
3264 i = i->next;
3267 op_edge = TOPOROUTER_EDGE(gts_triangle_edge_opposite(t, GTS_VERTEX(common_v)));
3269 g_assert(op_edge);
3270 g_assert(e1);
3271 g_assert(e2);
3273 v = segment_common_vertex(GTS_SEGMENT(e2), GTS_SEGMENT(op_edge));
3274 g_assert(v);
3276 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e1)));
3277 if(v->flags & VERTEX_FLAG_ROUTE && v->parent && v->parent->routingedge) {
3278 if(v->parent->routingedge == e1)
3279 r += min_spacing(v, pv);
3282 v = segment_common_vertex(GTS_SEGMENT(e1), GTS_SEGMENT(op_edge));
3283 g_assert(v);
3285 //v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e2)));
3286 if(v->flags & VERTEX_FLAG_ROUTE && v->parent && v->parent->routingedge) {
3287 if(v->parent->routingedge == e1)
3288 r += min_spacing(v, pv);
3291 if(TOPOROUTER_IS_CONSTRAINT(op_edge)) {
3292 toporouter_bbox_t *box = vertex_bbox(TOPOROUTER_VERTEX(edge_v1(op_edge)));
3293 r += vertex_net_thickness(v) / 2.;
3294 if(box) {
3295 r += MAX(vertex_net_keepaway(v), cluster_keepaway(box->cluster));
3296 r += cluster_thickness(box->cluster) / 2.;
3297 }else{
3298 r += vertex_net_keepaway(v);
3303 return r;
3308 guint
3309 check_triangle_interior_capacity(GtsTriangle *t, toporouter_vertex_t *v, toporouter_vertex_t *curpoint,
3310 toporouter_edge_t *op_edge, toporouter_edge_t *adj_edge1, toporouter_edge_t *adj_edge2)
3312 gdouble ic = triangle_interior_capacity(t, v);
3313 gdouble flow = flow_from_edge_to_edge(t, adj_edge1, adj_edge2, v, curpoint);
3315 if(TOPOROUTER_IS_CONSTRAINT(adj_edge1) || TOPOROUTER_IS_CONSTRAINT(adj_edge2)) return 1;
3318 if(flow > ic) {
3319 #ifdef DEBUG_ROUTE
3320 printf("fail interior capacity flow = %f ic = %f\n", flow, ic);
3321 #endif
3322 return 0;
3325 return 1;
3328 toporouter_vertex_t *
3329 edge_routing_next_not_temp(toporouter_edge_t *e, GList *list)
3331 if(!TOPOROUTER_IS_CONSTRAINT(e)) {
3332 while(list) {
3333 toporouter_vertex_t *v = TOPOROUTER_VERTEX(list->data);
3334 if(!(v->flags & VERTEX_FLAG_TEMP))
3335 return v;
3337 list = list->next;
3340 return tedge_v2(e);
3343 toporouter_vertex_t *
3344 edge_routing_prev_not_temp(toporouter_edge_t *e, GList *list)
3346 if(!TOPOROUTER_IS_CONSTRAINT(e)) {
3347 while(list) {
3348 toporouter_vertex_t *v = TOPOROUTER_VERTEX(list->data);
3349 if(!(v->flags & VERTEX_FLAG_TEMP))
3350 return v;
3352 list = list->prev;
3355 return tedge_v1(e);
3358 void
3359 edge_adjacent_vertices(toporouter_edge_t *e, toporouter_vertex_t *v, toporouter_vertex_t **v1, toporouter_vertex_t **v2)
3361 GList *r = g_list_find(edge_routing(e), v);
3363 if(v == tedge_v1(e)) {
3364 *v1 = NULL;
3365 *v2 = edge_routing_next_not_temp(e, edge_routing(e));
3366 }else if(v == tedge_v2(e)) {
3367 *v1 = edge_routing_prev_not_temp(e, g_list_last(edge_routing(e)));
3368 *v2 = NULL;
3369 }else{
3370 // r = g_list_find(r, v);
3371 *v1 = edge_routing_prev_not_temp(e, r);
3372 *v2 = edge_routing_next_not_temp(e, r);
3379 GList *
3380 candidate_vertices(toporouter_vertex_t *v1, toporouter_vertex_t *v2, toporouter_vertex_t *dest, toporouter_edge_t *e)
3382 gdouble totald, v1ms, v2ms, flow, capacity, ms;
3383 GList *vs = NULL;
3385 g_assert(v1);
3386 g_assert(v2);
3387 g_assert(dest);
3389 g_assert(!(v1->flags & VERTEX_FLAG_TEMP));
3390 g_assert(!(v2->flags & VERTEX_FLAG_TEMP));
3391 #ifdef DEBUG_ROUTE
3392 printf("starting candidate vertices\n");
3393 printf("v1 = %f,%f v2 = %f,%f dest = %f,%f\n", vx(v1), vy(v1), vx(v2), vy(v2), vx(dest), vy(dest));
3394 #endif
3395 totald = gts_point_distance(GTS_POINT(v1), GTS_POINT(v2));
3396 v1ms = min_spacing(v1, dest);
3397 v2ms = min_spacing(v2, dest);
3398 ms = min_spacing(dest, dest);
3399 flow = TOPOROUTER_IS_CONSTRAINT(e) ? 0. : edge_flow(e, v1, v2, dest);
3400 capacity = edge_capacity(e);
3402 #ifdef DEBUG_ROUTE
3403 g_assert(totald > 0);
3405 printf("v1ms = %f v2ms = %f totald = %f ms = %f capacity = %f flow = %f\n", v1ms, v2ms, totald, ms, capacity, flow);
3406 #endif
3408 if(flow >= capacity) return NULL;
3411 if(v1ms + v2ms + ms >= totald) {
3412 vs = g_list_prepend(vs, new_temp_toporoutervertex((vx(v1)+vx(v2)) / 2., (vy(v1)+vy(v2)) / 2., e));
3413 }else{
3414 gdouble x0, y0, x1, y1, d;
3416 vertex_move_towards_vertex_values(GTS_VERTEX(v1), GTS_VERTEX(v2), v1ms, &x0, &y0);
3418 vs = g_list_prepend(vs, new_temp_toporoutervertex(x0, y0, e));
3420 vertex_move_towards_vertex_values(GTS_VERTEX(v2), GTS_VERTEX(v1), v2ms, &x1, &y1);
3422 vs = g_list_prepend(vs, new_temp_toporoutervertex(x1, y1, e));
3424 d = sqrt(pow(x0-x1,2) + pow(y0-y1,2));
3426 if(ms < d) {
3427 // guint nint = d / ms;
3428 // gdouble dif = d / (nint + 1);
3429 gdouble dif = d / 2;
3431 // for(guint j=0;j<nint;j++) {
3432 gdouble x, y;
3434 // coord_move_towards_coord_values(x0, y0, x1, y1, dif * j, &x, &y);
3435 coord_move_towards_coord_values(x0, y0, x1, y1, dif, &x, &y);
3437 vs = g_list_prepend(vs, new_temp_toporoutervertex(x, y, e));
3439 // }
3444 #ifdef DEBUG_ROUTE
3445 printf("candidate vertices returning %d\n", g_list_length(vs));
3446 #endif
3447 return vs;
3450 GList *
3451 edge_routing_first_not_temp(toporouter_edge_t *e)
3453 GList *i = edge_routing(e);
3454 toporouter_vertex_t *v;
3456 while(i) {
3457 v = TOPOROUTER_VERTEX(i->data);
3458 if(!(v->flags & VERTEX_FLAG_TEMP)) return i;
3460 i = i->next;
3463 return NULL;
3466 GList *
3467 edge_routing_last_not_temp(toporouter_edge_t *e)
3469 GList *i = edge_routing(e), *last = NULL;
3470 toporouter_vertex_t *v;
3472 while(i) {
3473 v = TOPOROUTER_VERTEX(i->data);
3474 if(!(v->flags & VERTEX_FLAG_TEMP)) last = i;
3476 i = i->next;
3479 return last;
3482 void
3483 delete_vertex(toporouter_vertex_t *v)
3486 if(v->flags & VERTEX_FLAG_TEMP) {
3487 if(v->routingedge) {
3488 if(TOPOROUTER_IS_CONSTRAINT(v->routingedge))
3489 TOPOROUTER_CONSTRAINT(v->routingedge)->routing = g_list_remove(TOPOROUTER_CONSTRAINT(v->routingedge)->routing, v);
3490 else
3491 v->routingedge->routing = g_list_remove(v->routingedge->routing, v);
3494 gts_object_destroy ( GTS_OBJECT(v) );
3498 #define edge_is_blocked(e) (TOPOROUTER_IS_EDGE(e) ? (e->flags & EDGE_FLAG_DIRECTCONNECTION) : 0)
3500 GList *
3501 triangle_candidate_points_from_vertex(GtsTriangle *t, toporouter_vertex_t *v, toporouter_vertex_t *dest, toporouter_route_t *routedata)
3503 toporouter_edge_t *op_e = TOPOROUTER_EDGE(gts_triangle_edge_opposite(t, GTS_VERTEX(v)));
3504 toporouter_vertex_t *vv1, *vv2, *constraintv = NULL;
3505 toporouter_edge_t *e1, *e2;
3506 GList *i;
3507 GList *rval = NULL;
3509 #ifdef DEBUG_ROUTE
3510 printf("\tTRIANGLE CAND POINT FROM VERTEX\n");
3512 g_assert(op_e);
3513 #endif
3515 e1 = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v), edge_v1(op_e)));
3516 e2 = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v), edge_v2(op_e)));
3519 if(TOPOROUTER_IS_CONSTRAINT(op_e)) {
3520 if(TOPOROUTER_CONSTRAINT(op_e)->box->type == BOARD) {
3521 #ifdef DEBUG_ROUTE
3522 printf("BOARD constraint\n");
3523 #endif
3524 return NULL;
3526 if(constraint_netlist(TOPOROUTER_CONSTRAINT(op_e)) != vertex_netlist(dest)) { // || TOPOROUTER_CONSTRAINT(op_e)->routing) {
3527 #ifdef DEBUG_ROUTE
3528 printf("op_e routing:\n");
3529 print_edge(op_e);
3530 #endif
3531 return NULL;
3533 #ifdef DEBUG_ROUTE
3534 printf("RETURNING CONSTRAINT POING\n");
3535 #endif
3536 constraintv = new_temp_toporoutervertex_in_segment(op_e, TOPOROUTER_VERTEX(edge_v1(op_e)),
3537 gts_point_distance(GTS_POINT(edge_v1(op_e)), GTS_POINT(edge_v2(op_e))) / 2., TOPOROUTER_VERTEX(edge_v2(op_e)));
3538 // return g_list_prepend(NULL, vv1);
3543 if(edge_is_blocked(op_e)) {
3544 goto triangle_candidate_points_from_vertex_exit;
3546 // v1 = tedge_v1(op_e);
3547 // v2 = tedge_v2(op_e);
3549 if(v == tedge_v1(e1)) {
3550 i = edge_routing_first_not_temp(e1);
3551 }else{
3552 i = edge_routing_last_not_temp(e1);
3555 if(i) {
3556 toporouter_vertex_t *temp = TOPOROUTER_VERTEX(i->data);
3558 if(temp->parent == tedge_v2(op_e) || temp->child == tedge_v2(op_e)) {
3559 #ifdef DEBUG_ROUTE
3560 printf("temp -> op_e->v2\n");
3561 #endif
3562 goto triangle_candidate_points_from_vertex_exit;
3564 if(temp->parent->routingedge == op_e) {
3565 vv1 = temp->parent;
3566 #ifdef DEBUG_ROUTE
3567 printf("vv1->parent\n");
3568 #endif
3570 }else if(temp->child->routingedge == op_e) {
3571 vv1 = temp->child;
3572 #ifdef DEBUG_ROUTE
3573 printf("vv1->child\n");
3574 #endif
3576 }else{
3577 // must be to e2
3578 #ifdef DEBUG_ROUTE
3579 printf("temp -> e2?\n");
3580 printf("op_e = %f,%f\t\t%f,%f\n", vx(edge_v1(op_e)), vy(edge_v1(op_e)), vx(edge_v2(op_e)), vy(edge_v2(op_e)) );
3581 if(temp->parent->routingedge)
3582 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3583 vx(edge_v1(temp->parent->routingedge)), vy(edge_v1(temp->parent->routingedge)),
3584 vx(edge_v2(temp->parent->routingedge)), vy(edge_v2(temp->parent->routingedge))
3586 else
3587 printf("temp->parent->routingedge = NULL\n");
3589 if(temp->child->routingedge)
3590 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3591 vx(edge_v1(temp->child->routingedge)), vy(edge_v1(temp->child->routingedge)),
3592 vx(edge_v2(temp->child->routingedge)), vy(edge_v2(temp->child->routingedge))
3594 else
3595 printf("temp->child->routingedge = NULL\n");
3596 #endif
3597 goto triangle_candidate_points_from_vertex_exit;
3600 }else{
3601 vv1 = tedge_v1(op_e);
3602 #ifdef DEBUG_ROUTE
3603 printf("nothing on e1\n");
3604 #endif
3607 if(v == tedge_v1(e2)) {
3608 i = edge_routing_first_not_temp(e2);
3609 }else{
3610 i = edge_routing_last_not_temp(e2);
3613 if(i) {
3614 toporouter_vertex_t *temp = TOPOROUTER_VERTEX(i->data);
3616 if(temp->parent == tedge_v1(op_e) || temp->child == tedge_v1(op_e)) {
3617 #ifdef DEBUG_ROUTE
3618 printf("temp -> op_e->v2\n");
3619 #endif
3620 goto triangle_candidate_points_from_vertex_exit;
3623 if(temp->parent->routingedge == op_e) {
3624 vv2 = temp->parent;
3625 #ifdef DEBUG_ROUTE
3626 printf("vv2->parent\n");
3627 #endif
3628 }else if(temp->child->routingedge == op_e) {
3629 vv2 = temp->child;
3630 #ifdef DEBUG_ROUTE
3631 printf("vv2->child\n");
3632 #endif
3634 }else{
3635 // must be to e1
3636 #ifdef DEBUG_ROUTE
3637 printf("temp -> e1?\n");
3638 printf("op_e = %f,%f\t\t%f,%f\n", vx(edge_v1(op_e)), vy(edge_v1(op_e)), vx(edge_v2(op_e)), vy(edge_v2(op_e)) );
3639 if(temp->parent->routingedge)
3640 printf("temp->parent->routingedge = %f,%f \t\t %f,%f\n",
3641 vx(edge_v1(temp->parent->routingedge)), vy(edge_v1(temp->parent->routingedge)),
3642 vx(edge_v2(temp->parent->routingedge)), vy(edge_v2(temp->parent->routingedge))
3644 else
3645 printf("temp->parent->routingedge = NULL\n");
3647 if(temp->child->routingedge)
3648 printf("temp->child->routingedge = %f,%f \t\t %f,%f\n",
3649 vx(edge_v1(temp->child->routingedge)), vy(edge_v1(temp->child->routingedge)),
3650 vx(edge_v2(temp->child->routingedge)), vy(edge_v2(temp->child->routingedge))
3652 else
3653 printf("temp->child->routingedge = NULL\n");
3654 #endif
3655 goto triangle_candidate_points_from_vertex_exit;
3658 }else{
3659 vv2 = tedge_v2(op_e);
3660 #ifdef DEBUG_ROUTE
3661 printf("nothing on e2\n");
3662 #endif
3665 #ifdef DEBUG_ROUTE
3666 printf("size of e1 routing = %d e2 routing = %d op_e routing = %d\n",
3667 g_list_length(edge_routing(e1)), g_list_length(edge_routing(e2)), g_list_length(edge_routing(op_e)));
3668 #endif
3670 if(constraintv) {
3671 #ifdef DEBUG_ROUTE
3672 print_vertex(constraintv);
3673 printf("constraintv %f,%f returning\n", vx(constraintv), vy(constraintv));
3674 #endif
3675 return g_list_prepend(NULL, constraintv);
3678 i = edge_routing(op_e);
3679 while(i) {
3680 toporouter_vertex_t *temp = TOPOROUTER_VERTEX(i->data);
3682 if(temp->parent == v || temp->child == v) {
3683 rval = g_list_concat(rval, candidate_vertices(vv1, temp, dest, op_e));
3684 vv1 = temp;
3687 i = i->next;
3690 rval = g_list_concat(rval, candidate_vertices(vv1, vv2, dest, op_e));
3692 return rval;
3696 triangle_candidate_points_from_vertex_exit:
3697 if(constraintv) //delete_vertex(constraintv);
3698 g_hash_table_insert(routedata->alltemppoints, constraintv, constraintv);
3700 g_list_free(rval);
3702 return NULL;
3705 void
3706 routedata_insert_temppoints(toporouter_route_t *data, GList *temppoints) {
3707 GList *j = temppoints;
3708 while(j) {
3709 g_hash_table_insert(data->alltemppoints, j->data, j->data);
3710 j = j->next;
3715 inline gint
3716 constraint_route_test(toporouter_constraint_t *c, toporouter_route_t *routedata)
3718 if(c->box->cluster && c->box->cluster->netlist == routedata->src->netlist) {
3719 if(c->box->cluster->c == routedata->dest->c || c->box->cluster->c == routedata->src->c) return 1;
3721 return 0;
3724 GList *
3725 all_candidates_on_edge(toporouter_edge_t *e, toporouter_route_t *routedata)
3727 GList *rval = NULL;
3728 if(edge_is_blocked(e)) return NULL;
3730 if(!TOPOROUTER_IS_CONSTRAINT(e)) {
3731 GList *i = edge_routing(e);
3732 toporouter_vertex_t *pv = tedge_v1(e);
3734 while(i) {
3735 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
3736 if(!(v->flags & VERTEX_FLAG_TEMP)) {
3737 rval = g_list_concat(rval, candidate_vertices(pv, v, TOPOROUTER_VERTEX(routedata->destvertices->data), e));
3738 pv = v;
3740 i = i->next;
3743 rval = g_list_concat(rval, candidate_vertices(pv, tedge_v2(e), TOPOROUTER_VERTEX(routedata->destvertices->data), e));
3744 }else if(TOPOROUTER_CONSTRAINT(e)->box->type == BOARD) {
3745 return NULL;
3746 }else if(constraint_route_test(TOPOROUTER_CONSTRAINT(e), routedata)) {
3747 toporouter_vertex_t *consv = new_temp_toporoutervertex_in_segment(e, tedge_v1(e), tvdistance(tedge_v1(e), tedge_v2(e)) / 2., tedge_v2(e));
3748 rval = g_list_prepend(rval, consv);
3749 // g_hash_table_insert(routedata->alltemppoints, consv, consv);
3752 return rval;
3755 GList *
3756 triangle_all_candidate_points_from_vertex(GtsTriangle *t, toporouter_vertex_t *v, toporouter_route_t *routedata)
3758 toporouter_edge_t *op_e = TOPOROUTER_EDGE(gts_triangle_edge_opposite(t, GTS_VERTEX(v)));
3759 return all_candidates_on_edge(op_e, routedata);
3762 GList *
3763 triangle_all_candidate_points_from_edge(toporouter_t *r, GtsTriangle *t, toporouter_edge_t *e, toporouter_route_t *routedata,
3764 toporouter_vertex_t **dest, toporouter_vertex_t *curpoint)
3766 toporouter_vertex_t *op_v;
3767 toporouter_edge_t *e1, *e2;
3768 GList *i, *rval = NULL, *rval2 = NULL;
3769 toporouter_vertex_t *boxpoint = NULL;
3770 guint e1intcap, e2intcap;
3772 op_v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e)));
3775 if(vertex_bbox(op_v)) boxpoint = TOPOROUTER_VERTEX(vertex_bbox(op_v)->point);
3777 if(g_list_find(routedata->destvertices, op_v)) {
3778 rval = g_list_prepend(rval, op_v);
3779 *dest = op_v;
3780 return rval;
3781 }else if(g_list_find(routedata->destvertices, boxpoint)) {
3782 *dest = boxpoint;
3783 }else if(g_list_find(routedata->srcvertices, op_v)) {
3784 rval = g_list_prepend(rval, op_v);
3787 e1 = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v), edge_v1(e)));
3788 e2 = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v), edge_v2(e)));
3790 rval = g_list_concat(rval, all_candidates_on_edge(e1, routedata));
3791 rval = g_list_concat(rval, all_candidates_on_edge(e2, routedata));
3793 e1intcap = check_triangle_interior_capacity(t, tedge_v1(e), curpoint, e2, e, e1);
3794 e2intcap = check_triangle_interior_capacity(t, tedge_v2(e), curpoint, e1, e, e2);
3796 i = rval;
3797 while(i) {
3798 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
3800 if(!v->routingedge)
3801 rval2 = g_list_prepend(rval2, v);
3802 else if(v->routingedge == e1 && !(!TOPOROUTER_IS_CONSTRAINT(e1) && !e1intcap))
3803 rval2 = g_list_prepend(rval2, v);
3804 else if(v->routingedge == e2 && !(!TOPOROUTER_IS_CONSTRAINT(e2) && !e2intcap))
3805 rval2 = g_list_prepend(rval2, v);
3807 i = i->next;
3809 g_list_free(rval);
3811 return rval2;
3814 GList *
3815 triangle_candidate_points_from_edge(toporouter_t *r, GtsTriangle *t, toporouter_edge_t *e, toporouter_vertex_t *v, toporouter_vertex_t **dest,
3816 toporouter_route_t *routedata)
3818 toporouter_vertex_t *v1, *v2, *op_v, *vv = NULL, *e1constraintv = NULL, *e2constraintv = NULL;
3819 toporouter_edge_t *e1, *e2;
3820 GList *e1cands = NULL, *e2cands = NULL, *rval = NULL;
3821 guint noe1 = 0, noe2 = 0;
3823 op_v = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(t, GTS_EDGE(e)));
3825 e1 = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v), edge_v1(e)));
3826 e2 = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(op_v), edge_v2(e)));
3828 g_assert(*dest);
3830 // v1 is prev dir, v2 is next dir
3831 edge_adjacent_vertices(e, v, &v1, &v2);
3833 if(TOPOROUTER_IS_CONSTRAINT(e1)) {
3834 GList *i = edge_routing(e1);
3836 if(TOPOROUTER_CONSTRAINT(e1)->box->type == BOARD) {
3837 noe1 = 1;
3838 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e1), routedata)) {
3839 noe1 = 1;
3840 #ifdef DEBUG_ROUTE
3841 printf("noe1 netlist\n");
3842 #endif
3843 }else
3845 if(v1 == tedge_v1(e) ||
3846 (v1->parent->routingedge && v1->parent->routingedge == e1) ||
3847 (v1->child->routingedge && v1->child->routingedge == e1)) {
3848 e1constraintv = new_temp_toporoutervertex_in_segment(e1, tedge_v1(e1), gts_point_distance(GTS_POINT(edge_v1(e1)), GTS_POINT(edge_v2(e1))) / 2., tedge_v2(e1));
3851 while(i) {
3852 toporouter_vertex_t *temp = TOPOROUTER_VERTEX(i->data);
3854 if((temp->child == tedge_v2(e) || temp->parent == tedge_v2(e)) && !(temp->flags & VERTEX_FLAG_TEMP)) noe2 = 1;
3856 i = i->next;
3859 goto triangle_candidate_points_e2;
3862 if(edge_is_blocked(e1)) {
3863 noe1 = 1;
3864 goto triangle_candidate_points_e2;
3867 if(v1 == tedge_v1(e)) {
3868 // continue up e1
3869 toporouter_vertex_t *vv1, *vv2;
3870 edge_adjacent_vertices(e1, v1, &vv1, &vv2);
3872 #ifdef DEBUG_ROUTE
3873 printf("v1 == e->v1\n");
3874 #endif
3876 if(vv1) {
3877 // candidates from v1 until vv1
3878 vv = vv1;
3879 }else{
3880 // candidates from v1 until vv2
3881 vv = vv2;
3884 if(!e1constraintv) e1cands = candidate_vertices(v1, vv, *dest, e1);
3886 if(vv != op_v) {
3887 if(vv->parent == tedge_v2(e) || vv->child == tedge_v2(e)) {
3888 #ifdef DEBUG_ROUTE
3889 printf("noe2 0\n");
3890 #endif
3891 noe2 = 1;
3895 }else if(v1->parent != op_v && v1->child != op_v) {
3896 toporouter_vertex_t *vv1 = NULL, *vv2 = NULL;
3898 #ifdef DEBUG_ROUTE
3899 printf("v1 != e->v1\n");
3900 #endif
3902 if(v1->parent->routingedge == e1) {
3903 vv1 = v1->parent;
3904 #ifdef DEBUG_ROUTE
3905 printf("v1 parent = e1\n");
3906 #endif
3907 if(op_v == tedge_v1(e1)) {
3908 // candidates from v1->parent until prev vertex
3909 vv2 = edge_routing_prev_not_temp(e1, g_list_find(edge_routing(e1), v1->parent)->prev);
3910 }else{
3911 // candidates from v1->parent until next vertex
3912 vv2 = edge_routing_next_not_temp(e1, g_list_find(edge_routing(e1), v1->parent)->next);
3915 }else if(v1->child->routingedge == e1) {
3916 vv1 = v1->child;
3917 #ifdef DEBUG_ROUTE
3918 printf("v1 child = e1\n");
3919 #endif
3920 if(op_v == tedge_v1(e1)) {
3921 // candidates from v1->child until prev vertex
3922 vv2 = edge_routing_prev_not_temp(e1, g_list_find(edge_routing(e1), v1->child)->prev);
3923 }else{
3924 // candidates from v1->child until next vertex
3925 vv2 = edge_routing_next_not_temp(e1, g_list_find(edge_routing(e1), v1->child)->next);
3928 }else{
3929 #ifdef DEBUG_ROUTE
3930 printf("v1 ? \n");
3931 #endif
3932 goto triangle_candidate_points_e2;
3935 if(vv1 && vv2) {
3936 if(vv2->parent == tedge_v2(e) || vv2->child == tedge_v2(e)) {
3937 #ifdef DEBUG_ROUTE
3938 printf("noe2 1\n");
3939 #endif
3940 noe2 = 1;
3943 if(!e1constraintv) e1cands = candidate_vertices(vv1, vv2, *dest, e1);
3945 vv = vv2;
3949 if(vv && vv == op_v) {
3950 toporouter_vertex_t *boxpoint = NULL;
3952 if(vertex_bbox(op_v)) boxpoint = TOPOROUTER_VERTEX(vertex_bbox(op_v)->point);
3954 if(g_list_find(routedata->destvertices, op_v)) {
3955 rval = g_list_prepend(rval, op_v);
3956 *dest = op_v;
3957 }else if(g_list_find(routedata->destvertices, boxpoint)) {
3958 *dest = boxpoint;
3959 }else if(g_list_find(routedata->srcvertices, op_v)) {
3960 rval = g_list_prepend(rval, op_v);
3964 triangle_candidate_points_e2:
3966 if(noe2) {
3967 // printf("noe2\n");
3968 goto triangle_candidate_points_finish;
3971 if(TOPOROUTER_IS_CONSTRAINT(e2)) {
3972 GList *i = edge_routing(e2);
3974 if(TOPOROUTER_CONSTRAINT(e2)->box->type == BOARD) {
3975 noe2 = 1;
3976 // goto triangle_candidate_points_finish;
3977 }else if(!constraint_route_test(TOPOROUTER_CONSTRAINT(e2), routedata)) {
3978 #ifdef DEBUG_ROUTE
3979 printf("noe2 netlist\n");
3980 #endif
3981 noe2 = 1;
3982 // goto triangle_candidate_points_finish;
3983 }else if(v2 == tedge_v2(e) ||
3984 (v2->parent->routingedge && v2->parent->routingedge == e2) ||
3985 (v2->child->routingedge && v2->child->routingedge == e2)) {
3987 e2constraintv = new_temp_toporoutervertex_in_segment(e2, tedge_v1(e2), gts_point_distance(GTS_POINT(edge_v1(e2)), GTS_POINT(edge_v2(e2))) / 2., tedge_v2(e2));
3991 while(i) {
3992 toporouter_vertex_t *temp = TOPOROUTER_VERTEX(i->data);
3994 if((temp->child == tedge_v1(e) || temp->parent == tedge_v1(e)) && !(temp->flags & VERTEX_FLAG_TEMP))
3995 noe1 = 1;
3997 i = i->next;
4002 goto triangle_candidate_points_finish;
4005 if(edge_is_blocked(e2)) {
4006 noe2 = 1;
4007 goto triangle_candidate_points_finish;
4010 if(v2 == tedge_v2(e)) {
4011 // continue up e2
4012 toporouter_vertex_t *vv1 = NULL, *vv2 = NULL;
4013 edge_adjacent_vertices(e2, v2, &vv1, &vv2);
4015 #ifdef DEBUG_ROUTE
4016 printf("v2 == e->v2\n");
4017 #endif
4019 if(vv1) {
4020 // candidates from v2 until vv1
4021 vv = vv1;
4022 }else{
4023 // candidates from v2 until vv2
4024 vv = vv2;
4027 if(!e2constraintv) e2cands = candidate_vertices(v2, vv, *dest, e2);
4029 if(vv != op_v) {
4030 if(vv->parent == tedge_v1(e) || vv->child == tedge_v1(e)) {
4031 #ifdef DEBUG_ROUTE
4032 printf("noe1 0\n");
4033 #endif
4034 noe1 = 1;
4038 }else if(v2->parent != op_v && v2->child != op_v) {
4039 toporouter_vertex_t *vv1 = NULL, *vv2 = NULL;
4041 #ifdef DEBUG_ROUTE
4042 printf("v2 == e->v2\n");
4043 #endif
4045 if(v2->parent->routingedge == e2) {
4046 vv1 = v2->parent;
4047 if(op_v == tedge_v1(e2)) {
4048 // candidates from v2->parent until prev vertex
4049 vv2 = edge_routing_prev_not_temp(e2, g_list_find(edge_routing(e2), vv1)->prev);
4050 }else{
4051 // candidates from v2->parent until next vertex
4052 vv2 = edge_routing_next_not_temp(e2, g_list_find(edge_routing(e2), vv1)->next);
4055 }else if(v2->child->routingedge == e2) {
4056 vv1 = v2->child;
4057 if(op_v == tedge_v1(e2)) {
4058 // candidates from v2->child until prev vertex
4059 vv2 = edge_routing_prev_not_temp(e2, g_list_find(edge_routing(e2), vv1)->prev);
4060 }else{
4061 // candidates from v2->child until next vertex
4062 vv2 = edge_routing_next_not_temp(e2, g_list_find(edge_routing(e2), vv1)->next);
4065 }else{
4066 goto triangle_candidate_points_finish;
4069 if(vv1 && vv2) {
4070 if(vv2->parent == tedge_v1(e) || vv2->child == tedge_v1(e)) {
4071 #ifdef DEBUG_ROUTE
4072 printf("noe1 1\n");
4073 #endif
4074 noe1 = 1;
4077 if(!e2constraintv) e2cands = candidate_vertices(vv1, vv2, *dest, e2);
4081 triangle_candidate_points_finish:
4083 v1 = segment_common_vertex(GTS_SEGMENT(e), GTS_SEGMENT(e1));
4084 v2 = segment_common_vertex(GTS_SEGMENT(e), GTS_SEGMENT(e2));
4086 if(noe1 || !check_triangle_interior_capacity(t, v1, v, e2, e, e1)) {
4087 #ifdef DEBUG_ROUTE
4088 printf("freeing e1cands\n");
4089 #endif
4090 routedata_insert_temppoints(routedata, e1cands);
4091 g_list_free(e1cands);
4092 e1cands = NULL;
4095 if(noe2 || !check_triangle_interior_capacity(t, v2, v, e1, e, e2)) {
4096 #ifdef DEBUG_ROUTE
4097 printf("freeing e2cands\n");
4098 #endif
4099 routedata_insert_temppoints(routedata, e2cands);
4100 g_list_free(e2cands);
4101 e2cands = NULL;
4104 if(!noe1 && e1constraintv) {
4105 e1cands = g_list_prepend(e1cands, e1constraintv);
4106 }else if(e1constraintv) {
4107 g_hash_table_insert(routedata->alltemppoints, e1constraintv, e1constraintv);
4108 // delete_vertex(e1constraintv);
4111 if(!noe2 && e2constraintv) {
4112 e2cands = g_list_prepend(e2cands, e2constraintv);
4113 }else if(e2constraintv) {
4114 g_hash_table_insert(routedata->alltemppoints, e2constraintv, e2constraintv);
4115 // delete_vertex(e2constraintv);
4118 if(!noe1 && !noe2) return g_list_concat(rval, g_list_concat(e1cands, e2cands));
4120 return g_list_concat(e1cands, e2cands);
4123 GList *
4124 compute_candidate_points(toporouter_t *tr, toporouter_layer_t *l, toporouter_vertex_t *curpoint, toporouter_route_t *data,
4125 toporouter_vertex_t **closestdest)
4127 GList *r = NULL, *j;
4128 toporouter_edge_t *edge = curpoint->routingedge, *tempedge;
4130 if(vertex_keepout_test(tr, curpoint)) goto compute_candidate_points_finish;
4132 /* direct connection */
4133 // if(curpoint == TOPOROUTER_VERTEX(data->src->point))
4134 if((tempedge = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(curpoint), GTS_VERTEX(*closestdest))))) {
4136 if(TOPOROUTER_IS_CONSTRAINT(tempedge)) {
4137 goto compute_candidate_points_finish;
4138 }else{
4139 if(!tempedge->routing) {
4140 r = g_list_prepend(NULL, *closestdest);
4141 tempedge->flags |= EDGE_FLAG_DIRECTCONNECTION;
4142 goto compute_candidate_points_finish;
4143 }else{
4144 #ifdef DEBUG_ROUTE
4145 printf("Direct connection, but has routing\n");
4146 #endif
4150 /* if we get to here, there is routing blocking the direct connection,
4151 * continue as per normal */
4154 /* a real point origin */
4155 if(!(curpoint->flags & VERTEX_FLAG_TEMP)) {
4156 GSList *triangles, *i;
4157 i = triangles = gts_vertex_triangles(GTS_VERTEX(curpoint), NULL);
4158 #ifdef DEBUG_ROUTE
4159 printf("triangle count = %d\n", g_slist_length(triangles));
4160 #endif
4161 while(i) {
4162 GtsTriangle *t = GTS_TRIANGLE(i->data);
4163 GList *temppoints;
4165 if(tr->flags & TOPOROUTER_FLAG_LEASTINVALID) temppoints = triangle_all_candidate_points_from_vertex(t, curpoint, data);
4166 else temppoints = triangle_candidate_points_from_vertex(t, curpoint, *closestdest, data);
4168 #ifdef DEBUG_ROUTE
4169 printf("\treturned %d points\n", g_list_length(temppoints));
4170 #endif
4171 routedata_insert_temppoints(data, temppoints);
4173 r = g_list_concat(r, temppoints);
4174 i = i->next;
4176 g_slist_free(triangles);
4177 }else /* a temp point */ {
4178 int prevwind = vertex_wind(GTS_SEGMENT(edge)->v1, GTS_SEGMENT(edge)->v2, GTS_VERTEX(curpoint->parent));
4179 // printf("tempoint\n");
4181 GSList *i = GTS_EDGE(edge)->triangles;
4183 while(i) {
4184 GtsVertex *oppv = gts_triangle_vertex_opposite(GTS_TRIANGLE(i->data), GTS_EDGE(edge));
4185 if(prevwind != vertex_wind(GTS_SEGMENT(edge)->v1, GTS_SEGMENT(edge)->v2, oppv)) {
4186 GList *temppoints;
4188 if(tr->flags & TOPOROUTER_FLAG_LEASTINVALID) temppoints = triangle_all_candidate_points_from_edge(tr, GTS_TRIANGLE(i->data), edge,
4189 data, closestdest, curpoint);
4190 else temppoints = triangle_candidate_points_from_edge(tr, GTS_TRIANGLE(i->data), edge, curpoint, closestdest, data);
4192 j = temppoints;
4193 while(j) {
4194 toporouter_vertex_t *tempj = TOPOROUTER_VERTEX(j->data);
4195 if(tempj->flags & VERTEX_FLAG_TEMP)
4196 g_hash_table_insert(data->alltemppoints, j->data, j->data);
4197 #ifdef DEBUG_ROUTE
4198 else
4199 printf("got cand not a temp\n");
4200 #endif
4201 j = j->next;
4203 r = g_list_concat(r, temppoints);
4205 break;
4207 i = i->next;
4211 compute_candidate_points_finish:
4213 if(vertex_bbox(curpoint)) {
4214 if(vertex_bbox(curpoint)->cluster->c == data->src->c) {
4215 r = g_list_concat(r, g_list_copy(data->srcvertices));
4219 return r;
4222 gboolean
4223 temp_point_clean(gpointer key, gpointer value, gpointer user_data)
4225 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(value);
4226 if(tv->flags & VERTEX_FLAG_TEMP) {
4227 if(TOPOROUTER_IS_CONSTRAINT(tv->routingedge))
4228 TOPOROUTER_CONSTRAINT(tv->routingedge)->routing = g_list_remove(TOPOROUTER_CONSTRAINT(tv->routingedge)->routing, tv);
4229 else
4230 tv->routingedge->routing = g_list_remove(tv->routingedge->routing, tv);
4231 gts_object_destroy ( GTS_OBJECT(tv) );
4233 return TRUE;
4236 void
4237 clean_routing_edges(toporouter_t *r, toporouter_route_t *data)
4239 g_hash_table_foreach_remove(data->alltemppoints, temp_point_clean, NULL);
4240 g_hash_table_destroy(data->alltemppoints);
4241 data->alltemppoints = NULL;
4244 gdouble
4245 path_score(toporouter_t *r, GList *path)
4247 gdouble score = 0.;
4248 toporouter_vertex_t *pv = NULL;
4250 if(!path) return INFINITY;
4252 while(path) {
4253 toporouter_vertex_t *v = TOPOROUTER_VERTEX(path->data);
4255 if(pv) {
4256 score += gts_point_distance(GTS_POINT(pv), GTS_POINT(v));
4257 if(vz(pv) != vz(v))
4258 if(path->next)
4259 score += r->viacost;
4263 pv = v;
4264 path = path->next;
4267 return score;
4270 void
4271 print_vertices(GList *vertices)
4273 while(vertices) {
4274 toporouter_vertex_t *v = TOPOROUTER_VERTEX(vertices->data);
4275 print_vertex(v);
4276 print_bbox(vertex_bbox(v));
4277 if(vertex_bbox(v)) {
4278 printf("has bbox\n");
4279 if(vertex_bbox(v)->cluster)
4280 printf("has cluster\n");
4281 else
4282 printf("no cluster\n");
4283 }else printf("no bbox\n");
4284 vertices = vertices->next;
4288 gint
4289 space_edge(gpointer item, gpointer data)
4291 toporouter_edge_t *e = TOPOROUTER_EDGE(item);
4292 GList *i;
4293 gdouble *forces;
4295 if(TOPOROUTER_IS_CONSTRAINT(e)) return 0;
4297 if(!edge_routing(e) || !g_list_length(edge_routing(e))) return 0;
4299 forces = malloc(sizeof(double) * g_list_length(edge_routing(e)));
4301 for(guint j=0;j<100;j++) {
4302 guint k=0;
4303 guint equilibrium = 1;
4305 i = edge_routing(e);
4306 while(i) {
4307 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
4308 gdouble ms, d;
4310 if(i->prev) {
4311 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->prev->data), v);
4312 ms = min_spacing(TOPOROUTER_VERTEX(i->prev->data), v);
4313 d = gts_point_distance(GTS_POINT(i->prev->data), GTS_POINT(v));
4314 }else{
4315 // ms = min_vertex_net_spacing(v, tedge_v1(e));
4316 ms = min_spacing(v, tedge_v1(e));
4317 d = gts_point_distance(GTS_POINT(edge_v1(e)), GTS_POINT(v));
4320 if(d < ms) forces[k] = ms - d;
4321 else forces[k] = 0.;
4323 if(i->next) {
4324 // ms = min_net_net_spacing(TOPOROUTER_VERTEX(i->next->data), v);
4325 ms = min_spacing(TOPOROUTER_VERTEX(i->next->data), v);
4326 d = gts_point_distance(GTS_POINT(i->next->data), GTS_POINT(v));
4327 }else{
4328 // ms = min_vertex_net_spacing(v, tedge_v2(e));
4329 ms = min_spacing(v, tedge_v2(e));
4330 d = gts_point_distance(GTS_POINT(edge_v2(e)), GTS_POINT(v));
4333 if(d < ms) forces[k] += d - ms;
4335 k++; i = i->next;
4338 k = 0;
4339 i = edge_routing(e);
4340 while(i) {
4341 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
4342 if(forces[k] > EPSILON || forces[k] < -EPSILON) equilibrium = 0;
4343 vertex_move_towards_vertex_values(GTS_VERTEX(v), edge_v2(e), forces[k] * 0.1, &(GTS_POINT(v)->x), &(GTS_POINT(v)->y));
4344 k++; i = i->next;
4347 if(equilibrium) {
4348 // printf("reached equilibriium at %d\n", j);
4349 break;
4354 free(forces);
4355 return 0;
4358 void
4359 swap_vertices(toporouter_vertex_t **v1, toporouter_vertex_t **v2)
4361 toporouter_vertex_t *tempv = *v1;
4362 *v1 = *v2;
4363 *v2 = tempv;
4366 void
4367 split_edge_routing(toporouter_vertex_t *v, GList **l1, GList **l2)
4369 GList *base, *i;
4371 g_assert(v);
4372 g_assert(v->routingedge);
4374 base = g_list_find(vrouting(v), v);
4376 *l1 = g_list_prepend(*l1, tedge_v1(v->routingedge));
4377 *l2 = g_list_prepend(*l2, tedge_v2(v->routingedge));
4379 g_assert(base);
4381 i = base->next;
4382 while(i) {
4383 if(!(TOPOROUTER_VERTEX(i->data)->flags & VERTEX_FLAG_TEMP)) *l2 = g_list_prepend(*l2, i->data);
4384 i = i->next;
4387 i = base->prev;
4388 while(i) {
4389 if(!(TOPOROUTER_VERTEX(i->data)->flags & VERTEX_FLAG_TEMP)) *l1 = g_list_prepend(*l1, i->data);
4390 i = i->prev;
4394 GList *
4395 vertices_routing_conflicts(toporouter_vertex_t *v, toporouter_vertex_t *pv)
4397 toporouter_edge_t *e;
4398 GList *rval = NULL, *l1 = NULL, *l2 = NULL, *i;
4400 if(vz(v) != vz(pv)) return NULL;
4401 g_assert(v != pv);
4403 if(!v->routingedge && !pv->routingedge) {
4404 e = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(v), GTS_VERTEX(pv)));
4405 if(!e) return NULL;
4406 i = edge_routing(e);
4407 while(i) {
4408 rval = g_list_prepend(rval, TOPOROUTER_VERTEX(i->data)->route);
4409 i = i->next;
4411 return rval;
4414 if(TOPOROUTER_IS_CONSTRAINT(v->routingedge) && TOPOROUTER_IS_CONSTRAINT(pv->routingedge))
4415 return NULL;
4417 if(TOPOROUTER_IS_CONSTRAINT(pv->routingedge)) swap_vertices(&pv, &v);
4419 if(!v->routingedge) swap_vertices(&pv, &v);
4421 e = v->routingedge;
4423 split_edge_routing(v, &l1, &l2);
4424 g_assert(l2);
4425 g_assert(l1);
4427 if(!pv->routingedge) {
4428 toporouter_edge_t *e1, *e2;
4429 e1 = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv), edge_v1(e)));
4430 e2 = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(pv), edge_v2(e)));
4432 l1 = g_list_concat(l1, g_list_copy(edge_routing(e1)));
4433 l2 = g_list_concat(l2, g_list_copy(edge_routing(e2)));
4435 }else{
4436 GList *pvlist1 = NULL, *pvlist2 = NULL;
4437 toporouter_vertex_t *commonv = route_vertices_common_vertex(v, pv);
4439 g_assert(commonv);
4441 split_edge_routing(pv, &pvlist1, &pvlist2);
4443 if(commonv == tedge_v1(e)) {
4444 toporouter_edge_t *ope;
4446 if(commonv == tedge_v1(pv->routingedge)) {
4447 l1 = g_list_concat(l1, pvlist1);
4448 l2 = g_list_concat(l2, pvlist2);
4449 ope = TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e), edge_v2(pv->routingedge)));
4450 }else{
4451 l1 = g_list_concat(l1, pvlist2);
4452 l2 = g_list_concat(l2, pvlist1);
4453 ope = TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v2(e), edge_v1(pv->routingedge)));
4455 g_assert(ope);
4456 l2 = g_list_concat(l2, g_list_copy(edge_routing(ope)));
4458 }else{
4459 toporouter_edge_t *ope;
4460 if(commonv == tedge_v1(pv->routingedge)) {
4461 l1 = g_list_concat(l1, pvlist2);
4462 l2 = g_list_concat(l2, pvlist1);
4463 ope = TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e), edge_v2(pv->routingedge)));
4464 }else{
4465 l1 = g_list_concat(l1, pvlist1);
4466 l2 = g_list_concat(l2, pvlist2);
4467 ope = TOPOROUTER_EDGE(gts_vertices_are_connected(edge_v1(e), edge_v1(pv->routingedge)));
4469 g_assert(ope);
4470 l1 = g_list_concat(l1, g_list_copy(edge_routing(ope)));
4474 i = l1;
4475 while(i) {
4476 toporouter_vertex_t *curv = TOPOROUTER_VERTEX(i->data);
4478 if(curv->flags & VERTEX_FLAG_ROUTE && (g_list_find(l2, curv->parent) || g_list_find(l2, curv->child))) {
4479 if(!g_list_find(rval, curv->route)) rval = g_list_prepend(rval, curv->route);
4481 i = i->next;
4483 i = l2;
4484 while(i) {
4485 toporouter_vertex_t *curv = TOPOROUTER_VERTEX(i->data);
4487 if(curv->flags & VERTEX_FLAG_ROUTE && (g_list_find(l1, curv->parent) || g_list_find(l1, curv->child))) {
4488 if(!g_list_find(rval, curv->route)) rval = g_list_prepend(rval, curv->route);
4490 i = i->next;
4493 g_list_free(l1);
4494 g_list_free(l2);
4496 return rval;
4499 gdouble
4500 vertices_routing_conflict_cost(toporouter_t *r, toporouter_vertex_t *v, toporouter_vertex_t *pv, guint *n)
4502 GList *conflicts = vertices_routing_conflicts(v, pv), *i;
4503 gdouble penalty = 0.;
4505 i = conflicts;
4506 while(i) {
4507 (*n) += 1;
4508 penalty += TOPOROUTER_ROUTE(i->data)->score;
4509 i = i->next;
4511 g_list_free(conflicts);
4512 // if(penalty > 0.) printf("conflict penalty of %f with %f,%f %f,%f\n", penalty, vx(v), vy(v), vx(pv), vy(pv));
4513 return penalty;
4516 gdouble
4517 gcost(toporouter_t *r, toporouter_route_t *data, toporouter_vertex_t *srcv, toporouter_vertex_t *v, toporouter_vertex_t *pv, guint *n,
4518 toporouter_netlist_t *pair)
4520 gdouble cost = 0., segcost;
4522 *n = pv->gn;
4524 if(g_list_find(data->srcvertices, v)) return 0.;
4526 segcost = tvdistance(pv, v);
4528 if(pair && !TOPOROUTER_IS_CONSTRAINT(v->routingedge) && v->routingedge) {
4529 GList *list = g_list_find(v->routingedge->routing, v);
4530 toporouter_vertex_t *pv = edge_routing_prev_not_temp(v->routingedge, list);
4531 toporouter_vertex_t *nv = edge_routing_next_not_temp(v->routingedge, list);
4533 if(pv->route && pv->route->netlist == pair) {
4534 }else if(nv->route && nv->route->netlist == pair) {
4535 }else{
4536 segcost *= 10.;
4540 cost = pv->gcost + segcost;
4542 if(r->flags & TOPOROUTER_FLAG_LEASTINVALID) {
4543 gdouble conflictcost = 0.;
4545 if(pv && v != pv && vz(v) == vz(pv)) conflictcost = vertices_routing_conflict_cost(r, v, pv, n);
4547 if(!(r->flags & TOPOROUTER_FLAG_DETOUR && *n == 1)) {
4548 cost += conflictcost * (pow(*n,2));
4552 return cost;
4555 #define vlayer(x) (&r->layers[(int)vz(x)])
4557 guint
4558 candidate_is_available(toporouter_vertex_t *pv, toporouter_vertex_t *v)
4560 // TODO: still needed?
4561 while(pv) {
4562 if(pv == v) return 0;
4563 pv = pv->parent;
4566 return 1;
4569 GList *
4570 route(toporouter_t *r, toporouter_route_t *data, guint debug)
4572 GtsEHeap *openlist = gts_eheap_new(route_heap_cmp, NULL);
4573 GList *closelist = NULL;
4574 GList *i, *rval = NULL;
4575 toporouter_netlist_t *pair = NULL;
4576 gint count = 0;
4578 toporouter_vertex_t *srcv = NULL, *destv = NULL, *curpoint = NULL;
4579 toporouter_layer_t *cur_layer, *dest_layer;
4581 g_assert(data->src->c != data->dest->c);
4583 if(data->destvertices) g_list_free(data->destvertices);
4584 if(data->srcvertices) g_list_free(data->srcvertices);
4586 data->destvertices = cluster_vertices(r, data->dest);
4587 data->srcvertices = cluster_vertices(r, data->src);
4589 closest_cluster_pair(r, data->srcvertices, data->destvertices, &curpoint, &destv);
4591 if(!curpoint || !destv) goto routing_return;
4593 srcv = curpoint;
4594 cur_layer = vlayer(curpoint); dest_layer = vlayer(destv);
4596 data->path = NULL;
4598 data->alltemppoints = g_hash_table_new(g_direct_hash, g_direct_equal);
4600 curpoint->parent = NULL;
4601 curpoint->child = NULL;
4602 curpoint->gcost = 0.;
4603 curpoint->gn = 0;
4604 curpoint->hcost = simple_h_cost(r, curpoint, destv);
4606 if(data->netlist && data->netlist->pair) {
4607 GList *i = r->routednets;
4608 while(i) {
4609 toporouter_route_t *curroute = TOPOROUTER_ROUTE(i->data);
4610 if(curroute->netlist == data->netlist->pair) {
4611 pair = data->netlist->pair;
4612 break;
4614 i = i->next;
4618 gts_eheap_insert(openlist, curpoint);
4620 while(gts_eheap_size(openlist) > 0) {
4621 GList *candidatepoints;
4622 data->curpoint = curpoint;
4623 //draw_route_status(r, closelist, openlist, curpoint, data, count++);
4625 curpoint = TOPOROUTER_VERTEX( gts_eheap_remove_top(openlist, NULL) );
4626 if(curpoint->parent && !(curpoint->flags & VERTEX_FLAG_TEMP)) {
4627 if(vz(curpoint) != vz(destv)) {
4628 toporouter_vertex_t *tempv;
4629 cur_layer = vlayer(curpoint);//&r->layers[(int)vz(curpoint)];
4630 tempv = closest_dest_vertex(r, curpoint, data);
4631 if(tempv) {
4632 destv = tempv;
4633 dest_layer = vlayer(destv);//&r->layers[(int)vz(destv)];
4639 // destpoint = closest_dest_vertex(r, curpoint, data);
4640 // dest_layer = &r->layers[(int)vz(destpoint)];
4642 if(g_list_find(data->destvertices, curpoint)) {
4643 toporouter_vertex_t *temppoint = curpoint;
4644 srcv = NULL;
4645 destv = curpoint;
4647 data->path = NULL;
4649 while(temppoint) {
4650 data->path = g_list_prepend(data->path, temppoint);
4651 if(g_list_find(data->srcvertices, temppoint)) {
4652 srcv = temppoint;
4653 if(r->flags & TOPOROUTER_FLAG_AFTERORDER) break;
4655 temppoint = temppoint->parent;
4657 rval = data->path;
4658 data->score = path_score(r, data->path);
4659 #ifdef DEBUG_ROUTE
4660 printf("ROUTE: path score = %f computation cost = %d\n", data->score, count);
4661 #endif
4663 if(srcv->bbox->cluster != data->src) {
4664 data->src = srcv->bbox->cluster;
4667 if(destv->bbox->cluster != data->dest) {
4668 data->dest = destv->bbox->cluster;
4670 goto route_finish;
4672 closelist_insert(curpoint);
4673 #ifdef DEBUG_ROUTE
4674 printf("\n\n\n*** ROUTE COUNT = %d\n", count);
4675 #endif
4676 candidatepoints = compute_candidate_points(r, cur_layer, curpoint, data, &destv);
4678 //#ifdef DEBUG_ROUTE
4679 /*********************
4680 if(debug && !strcmp(data->dest->netlist, " unnamed_net2"))
4682 unsigned int mask = ~(VERTEX_FLAG_RED | VERTEX_FLAG_GREEN | VERTEX_FLAG_BLUE);
4683 char buffer[256];
4684 int j;
4686 for(j=0;j<groupcount();j++) {
4687 i = r->layers[j].vertices;
4688 while(i) {
4689 TOPOROUTER_VERTEX(i->data)->flags &= mask;
4690 i = i->next;
4694 i = candidatepoints;
4695 while(i) {
4696 TOPOROUTER_VERTEX(i->data)->flags |= VERTEX_FLAG_GREEN;
4697 // printf("flagged a candpoint @ %f,%f\n",
4698 // vx(i->data), vy(i->data));
4699 i = i->next;
4702 curpoint->flags |= VERTEX_FLAG_BLUE;
4703 if(curpoint->parent)
4704 curpoint->parent->flags |= VERTEX_FLAG_RED;
4707 for(j=0;j<groupcount();j++) {
4708 GList *datas = g_list_prepend(NULL, data);
4709 sprintf(buffer, "route-%d-%05d.png", j, count);
4710 toporouter_draw_surface(r, r->layers[j].surface, buffer, 1024, 1024, 2, datas, j, candidatepoints);
4711 g_list_free(datas);
4714 //#endif
4715 *********************/
4716 count++;
4717 // if(count > 100) exit(0);
4718 i = candidatepoints;
4719 while(i) {
4720 toporouter_vertex_t *temppoint = TOPOROUTER_VERTEX(i->data);
4721 if(!g_list_find(closelist, temppoint) && candidate_is_available(curpoint, temppoint)) { //&& temppoint != curpoint) {
4722 toporouter_heap_search_data_t heap_search_data = { temppoint, NULL };
4724 guint temp_gn;
4725 gdouble temp_g_cost = gcost(r, data, srcv, temppoint, curpoint, &temp_gn, pair);
4728 gts_eheap_foreach(openlist,toporouter_heap_search, &heap_search_data);
4730 if(heap_search_data.result) {
4731 if(temp_g_cost < temppoint->gcost) {
4733 temppoint->gcost = temp_g_cost;
4734 temppoint->gn = temp_gn;
4736 temppoint->parent = curpoint;
4737 curpoint->child = temppoint;
4739 gts_eheap_update(openlist);
4741 }else{
4742 temppoint->parent = curpoint;
4743 curpoint->child = temppoint;
4745 temppoint->gcost = temp_g_cost;
4746 temppoint->gn = temp_gn;
4748 temppoint->hcost = simple_h_cost(r, temppoint, destv);
4749 // if(cur_layer != dest_layer) temppoint->hcost += r->viacost;
4750 gts_eheap_insert(openlist, temppoint);
4754 i = i->next;
4756 g_list_free(candidatepoints);
4759 #ifdef DEBUG_ROUTE
4760 printf("ROUTE: could not find path!\n");
4761 #endif
4763 data->score = INFINITY;
4764 clean_routing_edges(r, data);
4766 data->path = NULL;
4767 //TOPOROUTER_VERTEX(data->src->point)->parent = NULL;
4768 //TOPOROUTER_VERTEX(data->src->point)->child = NULL;
4769 goto routing_return;
4773 int i;
4774 for(i=0;i<groupcount();i++) {
4775 char buffer[256];
4776 sprintf(buffer, "route-error-%d-%d.png", r->routecount, i);
4777 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1280, 1280, 2, data, i, NULL);
4779 r->routecount++;
4781 // exit(0);
4783 route_finish:
4784 // printf(" * finished a*\n");
4787 int i;
4788 for(i=0;i<groupcount();i++) {
4789 char buffer[256];
4790 sprintf(buffer, "route-preclean-%d-%d.png", i, r->routecount);
4791 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, data, i, NULL);
4793 r->routecount++;
4796 /* {
4797 i = data->path;
4798 while(i) {
4799 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
4801 if(tv->routingedge) {
4802 GList *list = g_list_find(edge_routing(tv->routingedge), tv);
4803 toporouter_vertex_t *restartv = NULL, *boxpoint;
4805 g_assert(list);
4807 if(!list->next) {
4808 if(vertex_bbox(tedge_v2(tv->routingedge)))
4809 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v2(tv->routingedge))->point);
4810 else
4811 boxpoint = NULL;
4813 if(tedge_v2(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v2(tv->routingedge)))
4814 restartv = tedge_v2(tv->routingedge);
4815 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
4816 restartv = boxpoint;
4819 if(!list->prev) {
4820 if(vertex_bbox(tedge_v1(tv->routingedge)))
4821 boxpoint = TOPOROUTER_VERTEX(vertex_bbox(tedge_v1(tv->routingedge))->point);
4822 else
4823 boxpoint = NULL;
4825 if(tedge_v1(tv->routingedge) != srcv && g_list_find(data->srcvertices, tedge_v1(tv->routingedge)))
4826 restartv = tedge_v1(tv->routingedge);
4827 else if(boxpoint != srcv && g_list_find(data->srcvertices, boxpoint))
4828 restartv = boxpoint;
4832 if(restartv) {
4833 clean_routing_edges(r, data);
4834 gts_eheap_destroy(openlist);
4835 g_list_free(closelist);
4836 openlist = gts_eheap_new(route_heap_cmp, NULL);
4837 closelist = NULL;
4838 g_list_free(data->path);
4839 printf("ROUTING RESTARTING with new src %f,%f,%f\n", vx(restartv), vy(restartv), vz(restartv));
4840 curpoint = restartv;
4841 goto route_begin;
4845 i = i->next;
4848 ///*
4850 toporouter_vertex_t *pv = NULL;
4851 GList *i = data->path;
4852 while(i) {
4853 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
4855 if(pv && g_list_find(data->srcvertices, tv)) {
4856 GList *temp = g_list_copy(i);
4857 g_list_free(data->path);
4858 data->path = temp;
4859 i = data->path;
4861 pv = tv;
4862 i = i->next;
4865 //*/
4867 toporouter_vertex_t *pv = NULL;
4868 GList *i = data->path;
4869 while(i) {
4870 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
4871 if(tv->flags & VERTEX_FLAG_TEMP) {
4872 tv->flags ^= VERTEX_FLAG_TEMP;
4873 tv->flags |= VERTEX_FLAG_ROUTE;
4875 if(pv) pv->child = tv;
4877 if(tv->routingedge) tv->route = data;
4879 // if(tv->routingedge && !TOPOROUTER_IS_CONSTRAINT(tv->routingedge)) space_edge(tv->routingedge, NULL);
4881 pv = tv;
4882 i = i->next;
4887 toporouter_vertex_t *pv = NULL, *v = NULL;
4889 GList *i = data->path;
4890 while(i) {
4891 v = TOPOROUTER_VERTEX(i->data);
4893 if(pv) {
4894 v->parent = pv;
4895 pv->child = v;
4896 }else{
4897 v->parent = NULL;
4900 pv = v;
4901 i = i->next;
4904 if(v) v->child = NULL;
4907 clean_routing_edges(r, data);
4908 // /*
4910 GList *i = data->path;
4911 while(i) {
4912 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
4914 if(v->routingedge && !TOPOROUTER_IS_CONSTRAINT(v->routingedge))
4915 space_edge(v->routingedge, NULL);
4916 i = i->next;
4919 // */
4920 routing_return:
4922 g_list_free(data->destvertices);
4923 g_list_free(data->srcvertices);
4924 data->destvertices = NULL;
4925 data->srcvertices = NULL;
4926 gts_eheap_destroy(openlist);
4927 g_list_free(closelist);
4929 data->alltemppoints = NULL;
4931 return rval;
4934 /* moves vertex v d units in the direction of vertex p */
4935 void
4936 vertex_move_towards_point(GtsVertex *v, gdouble px, gdouble py, gdouble d)
4938 gdouble dx = px - GTS_POINT(v)->x;
4939 gdouble dy = py - GTS_POINT(v)->y;
4940 gdouble theta = atan(fabs(dy/dx));
4942 g_assert(finite(theta));
4944 if( dx >= 0. ) {
4946 if( dy >= 0. ) {
4947 GTS_POINT(v)->x += d * cos(theta);
4948 GTS_POINT(v)->y += d * sin(theta);
4949 }else{
4950 GTS_POINT(v)->x += d * cos(theta);
4951 GTS_POINT(v)->y -= d * sin(theta);
4954 }else{
4956 if( dy >= 0. ) {
4957 GTS_POINT(v)->x -= d * cos(theta);
4958 GTS_POINT(v)->y += d * sin(theta);
4959 }else{
4960 GTS_POINT(v)->x -= d * cos(theta);
4961 GTS_POINT(v)->y -= d * sin(theta);
4968 /* moves vertex v d units in the direction of vertex p */
4969 void
4970 vertex_move_towards_vertex(GtsVertex *v, GtsVertex *p, gdouble d)
4972 gdouble dx = GTS_POINT(p)->x - GTS_POINT(v)->x;
4973 gdouble dy = GTS_POINT(p)->y - GTS_POINT(v)->y;
4974 gdouble theta = atan(fabs(dy/dx));
4976 g_assert(finite(theta));
4978 if( dx >= 0. ) {
4980 if( dy >= 0. ) {
4981 GTS_POINT(v)->x += d * cos(theta);
4982 GTS_POINT(v)->y += d * sin(theta);
4983 }else{
4984 GTS_POINT(v)->x += d * cos(theta);
4985 GTS_POINT(v)->y -= d * sin(theta);
4988 }else{
4990 if( dy >= 0. ) {
4991 GTS_POINT(v)->x -= d * cos(theta);
4992 GTS_POINT(v)->y += d * sin(theta);
4993 }else{
4994 GTS_POINT(v)->x -= d * cos(theta);
4995 GTS_POINT(v)->y -= d * sin(theta);
5003 gdouble
5004 pathvertex_arcing_through_constraint(toporouter_vertex_t *pathv, toporouter_vertex_t *arcv)
5006 toporouter_vertex_t *v = pathv->child;
5008 if(!v || !v->routingedge) return 0.;
5010 while(v->flags & VERTEX_FLAG_ROUTE && (tedge_v1(v->routingedge) == arcv || tedge_v2(v->routingedge) == arcv)) {
5011 if(TOPOROUTER_IS_CONSTRAINT(v->routingedge))
5012 return gts_point_distance(GTS_POINT(tedge_v1(v->routingedge)), GTS_POINT(tedge_v2(v->routingedge)));
5013 v = v->child;
5016 v = pathv->parent;
5017 while(v->flags & VERTEX_FLAG_ROUTE && (tedge_v1(v->routingedge) == arcv || tedge_v2(v->routingedge) == arcv)) {
5018 if(TOPOROUTER_IS_CONSTRAINT(v->routingedge))
5019 return gts_point_distance(GTS_POINT(tedge_v1(v->routingedge)), GTS_POINT(tedge_v2(v->routingedge)));
5020 v = v->parent;
5023 return 0.;
5026 gint
5027 vertices_connected(toporouter_vertex_t *a, toporouter_vertex_t *b)
5029 return ((a->route->netlist == b->route->netlist && a->route->src->c == b->route->src->c) ? 1 : 0);
5032 gdouble
5033 edge_min_spacing(GList *list, toporouter_edge_t *e, toporouter_vertex_t *v, guint debug)
5035 toporouter_vertex_t *origin;
5036 GList *i = list;
5037 gdouble space = 0.;
5038 toporouter_vertex_t *nextv, *prevv;
5039 //toporouter_vertex_t *edgev;
5040 //gdouble constraint_spacing;
5042 if(!list) return INFINITY;
5044 // printf("\t CMS %f,%f - %f,%f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), vx(tedge_v2(e)), vy(tedge_v2(e)));
5046 prevv = origin = TOPOROUTER_VERTEX(list->data);
5048 // print_edge(e);
5050 i = list;
5051 if(gts_point_distance2(GTS_POINT(origin), GTS_POINT(edge_v1(e))) < gts_point_distance2(GTS_POINT(v), GTS_POINT(edge_v1(e)))) {
5053 /* towards v2 */
5054 while(i) {
5055 nextv = edge_routing_next(e, i);
5056 if(nextv->route && vertices_connected(nextv, prevv)) { i = i->next; continue; }
5057 if(!(nextv->flags & VERTEX_FLAG_TEMP)) {
5058 gdouble ms = min_spacing(prevv, nextv);
5059 if(nextv == tedge_v2(e)) {
5060 gdouble cms = pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i->data), tedge_v2(e));
5061 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v2(e)), vy(tedge_v2(e)), cms, ms);
5062 // if(vx(tedge_v2(e)) > -EPSILON && vx(tedge_v2(e)) < EPSILON) {
5063 // printf("\t\tPROB: ");
5064 // print_vertex(tedge_v2(e));
5065 // }
5066 if(cms > EPSILON) space += MIN(ms, cms / 2.);
5067 else space += ms;
5068 } else
5069 space += ms;
5071 prevv = nextv;
5073 // printf("%f ", space);
5074 i = i->next;
5076 }else{
5078 /* towards v1 */
5079 while(i) {
5080 nextv = edge_routing_prev(e, i);
5081 if(nextv->route && vertices_connected(nextv, prevv)) { i = i->prev; continue; }
5082 if(!(nextv->flags & VERTEX_FLAG_TEMP)) {
5083 gdouble ms = min_spacing(prevv, nextv);
5084 if(nextv == tedge_v1(e)) {
5085 gdouble cms = pathvertex_arcing_through_constraint(TOPOROUTER_VERTEX(i->data), tedge_v1(e));
5086 // printf("\t CMS to %f,%f = %f \t ms = %f\n", vx(tedge_v1(e)), vy(tedge_v1(e)), cms, ms);
5087 // if(vx(tedge_v1(e)) > -EPSILON && vx(tedge_v1(e)) < EPSILON) {
5088 // printf("\t\tPROB: ");
5089 // print_vertex(tedge_v1(e));
5090 // }
5091 if(cms > EPSILON) space += MIN(ms, cms / 2.);
5092 else space += ms;
5093 } else
5094 space += ms;
5096 prevv = nextv;
5098 // printf("%f ", space);
5099 i = i->prev;
5103 if(TOPOROUTER_IS_CONSTRAINT(e) && space > gts_point_distance(GTS_POINT(edge_v1(e)), GTS_POINT(edge_v2(e))) / 2.)
5104 space = gts_point_distance(GTS_POINT(edge_v1(e)), GTS_POINT(edge_v2(e))) / 2.;
5106 // if(debug) printf("\tedge_min_spacing: %f\n", space);
5107 return space;
5110 /* line segment is 1 & 2, point is 3
5111 returns 0 if v3 is outside seg
5113 guint
5114 vertex_line_normal_intersection(gdouble x1, gdouble y1, gdouble x2, gdouble y2, gdouble x3, gdouble y3, gdouble *x, gdouble *y)
5116 gdouble m1 = cartesian_gradient(x1,y1,x2,y2);
5117 gdouble m2 = perpendicular_gradient(m1);
5118 gdouble c2 = (isinf(m2)) ? x3 : y3 - (m2 * x3);
5119 gdouble c1 = (isinf(m1)) ? x1 : y1 - (m1 * x1);
5121 if(isinf(m2))
5122 *x = x3;
5123 else if(isinf(m1))
5124 *x = x1;
5125 else
5126 *x = (c2 - c1) / (m1 - m2);
5128 *y = (isinf(m2)) ? y1 : (m2 * (*x)) + c2;
5130 if(*x >= MIN(x1,x2) - EPSILON && *x <= MAX(x1,x2) + EPSILON && *y >= MIN(y1,y2) - EPSILON && *y <= MAX(y1,y2) + EPSILON)
5131 return 1;
5132 return 0;
5135 void
5136 print_toporouter_arc(toporouter_arc_t *arc)
5138 // GList *i = arc->vs;
5140 printf("ARC CENTRE: %f,%f ", vx(arc->centre), vy(arc->centre));// print_vertex(arc->centre);
5141 printf("RADIUS: %f", arc->r);
5143 if(arc->dir>0) printf(" COUNTERCLOCKWISE ");
5144 else if(arc->dir<0) printf(" CLOCKWISE ");
5145 else printf(" COLINEAR(ERROR) ");
5147 printf("\n\tVS: ");
5149 while(i) {
5150 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
5151 printf("%f,%f ", vx(v), vy(v));
5153 i = i->next;
5158 void
5159 toporouter_arc_remove(toporouter_oproute_t *oproute, toporouter_arc_t *arc)
5161 oproute->arcs = g_list_remove(oproute->arcs, arc);
5163 if(arc->v) arc->v->arc = NULL;
5166 toporouter_arc_t *
5167 toporouter_arc_new(toporouter_oproute_t *oproute, toporouter_vertex_t *v1, toporouter_vertex_t *v2, toporouter_vertex_t *centre, gdouble r, gint dir)
5169 toporouter_arc_t *arc = TOPOROUTER_ARC(gts_object_new(GTS_OBJECT_CLASS(toporouter_arc_class())));
5170 arc->centre = centre;
5171 arc->v = v1;
5172 arc->v1 = v1;
5173 arc->v2 = v2;
5174 arc->r = r;
5175 arc->dir = dir;
5177 if(v1) v1->arc = arc;
5178 arc->oproute = oproute;
5180 arc->clearance = NULL;
5182 return arc;
5185 void
5186 path_set_oproute(GList *path, toporouter_oproute_t *oproute)
5188 while(path) {
5189 toporouter_vertex_t *v = TOPOROUTER_VERTEX(path->data);
5191 if(v->flags & VERTEX_FLAG_ROUTE)
5192 v->oproute = oproute;
5194 path = path->next;
5198 void
5199 print_oproute(toporouter_oproute_t *oproute)
5201 GList *i = oproute->arcs;
5203 printf("Optimized Route:\n");
5204 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", oproute->netlist, oproute->style);
5205 // printf("%s\n", oproute->netlist);
5207 i = oproute->term1->zlink;
5208 while(i) {
5209 toporouter_vertex_t *thisv = TOPOROUTER_VERTEX(i->data);
5210 printf("\tNetlist:\t\t%s\n\tStyle:\t\t%s\n", vertex_bbox(thisv)->netlist, vertex_bbox(thisv)->style);
5211 i = i->next;
5214 printf("\t"); print_vertex(oproute->term1); printf("\n");
5215 i = oproute->arcs;
5216 while(i) {
5217 toporouter_arc_t *arc = (toporouter_arc_t *)i->data;
5218 printf("\t"); print_toporouter_arc(arc); printf("\n");
5219 i = i->next;
5221 printf("\t"); print_vertex(oproute->term2); printf("\n");
5224 gdouble
5225 export_pcb_drawline(guint layer, guint x0, guint y0, guint x1, guint y1, guint thickness, guint keepaway)
5227 gdouble d = 0.;
5228 LineTypePtr line;
5229 line = CreateDrawnLineOnLayer( LAYER_PTR(layer), x0, y0, x1, y1,
5230 thickness, keepaway,
5231 MakeFlags (AUTOFLAG | (TEST_FLAG (CLEARNEWFLAG, PCB) ? CLEARLINEFLAG : 0)));
5233 if(line) {
5234 AddObjectToCreateUndoList (LINE_TYPE, LAYER_PTR(layer), line, line);
5235 d = coord_distance((double)x0, (double)y0, (double)x1, (double)y1) / 100.;
5237 return d;
5240 gdouble
5241 arc_angle(toporouter_arc_t *arc)
5243 gdouble x0, x1, y0, y1;
5245 x0 = arc->x0 - vx(arc->centre);
5246 x1 = arc->x1 - vx(arc->centre);
5247 y0 = arc->y0 - vy(arc->centre);
5248 y1 = arc->y1 - vy(arc->centre);
5250 return fabs(acos(((x0*x1)+(y0*y1))/(sqrt(pow(x0,2)+pow(y0,2))*sqrt(pow(x1,2)+pow(y1,2)))));
5253 gdouble
5254 export_pcb_drawarc(guint layer, toporouter_arc_t *a, guint thickness, guint keepaway)
5256 gdouble sa, da, theta;
5257 gdouble x0, y0, x1, y1, d=0.;
5258 ArcTypePtr arc;
5259 gint wind;
5261 wind = coord_wind(a->x0, a->y0, a->x1, a->y1, vx(a->centre), vy(a->centre));
5263 sa = coord_xangle(a->x0, a->y0, vx(a->centre), vy(a->centre)) * 180. / M_PI;
5265 x0 = a->x0 - vx(a->centre);
5266 x1 = a->x1 - vx(a->centre);
5267 y0 = a->y0 - vy(a->centre);
5268 y1 = a->y1 - vy(a->centre);
5270 theta = arc_angle(a);
5272 if(!a->dir || !wind) return 0.;
5274 if(a->dir != wind) theta = 2. * M_PI - theta;
5276 da = -a->dir * theta * 180. / M_PI;
5278 if(da < 1. && da > -1.) return 0.;
5279 if(da > 359. || da < -359.) return 0.;
5281 arc = CreateNewArcOnLayer(LAYER_PTR(layer), vx(a->centre), vy(a->centre), a->r, a->r,
5282 sa, da, thickness, keepaway,
5283 MakeFlags( AUTOFLAG | (TEST_FLAG (CLEARNEWFLAG, PCB) ? CLEARLINEFLAG : 0)));
5285 if(arc) {
5286 AddObjectToCreateUndoList( ARC_TYPE, LAYER_PTR(layer), arc, arc);
5287 d = a->r * theta / 100.;
5290 return d;
5293 void
5294 calculate_term_to_arc(toporouter_vertex_t *v, toporouter_arc_t *arc, guint dir)
5296 gdouble theta, a, b, bx, by, a0x, a0y, a1x, a1y;
5297 gint winddir;
5299 theta = acos(arc->r / gts_point_distance(GTS_POINT(v), GTS_POINT(arc->centre)));
5300 a = arc->r * sin(theta);
5301 b = arc->r * cos(theta);
5302 #ifdef DEBUG_EXPORT
5303 printf("drawing arc with r %f theta %f d %f centre = %f,%f\n", arc->r, theta, gts_point_distance(GTS_POINT(v), GTS_POINT(arc->centre)), vx(arc->centre), vy(arc->centre));
5304 #endif
5305 point_from_point_to_point(arc->centre, v, b, &bx, &by);
5307 coords_on_line(bx, by, perpendicular_gradient(point_gradient(GTS_POINT(v), GTS_POINT(arc->centre))), a, &a0x, &a0y, &a1x, &a1y);
5309 winddir = coord_wind(vx(v), vy(v), a0x, a0y, vx(arc->centre), vy(arc->centre));
5311 if(!winddir) {
5312 printf("!winddir @ v %f,%f arc->centre %f,%f\n", vx(v), vy(v), vx(arc->centre), vy(arc->centre));
5313 //TODO: fix hack: this shouldn't happen
5314 arc->x0 = vx(v);
5315 arc->y0 = vy(v);
5316 arc->x1 = vx(v);
5317 arc->y1 = vy(v);
5318 return;
5321 g_assert(winddir);
5323 if(dir) winddir = -winddir;
5325 if(winddir == arc->dir) {
5326 if(!dir) { arc->x0 = a0x; arc->y0 = a0y; }
5327 else{ arc->x1 = a0x; arc->y1 = a0y; }
5328 }else{
5329 if(!dir) { arc->x0 = a1x; arc->y0 = a1y; }
5330 else{ arc->x1 = a1x; arc->y1 = a1y; }
5337 // b1 is the projection in the direction of narc, while b2 is the perpendicular projection
5338 void
5339 arc_ortho_projections(toporouter_arc_t *arc, toporouter_arc_t *narc, gdouble *b1, gdouble *b2)
5341 gdouble nax, nay, ax, ay, alen2, c;
5342 gdouble b1x, b1y, b2x, b2y;
5344 #ifdef DEBUG_EXPORT
5345 printf("arc c = %f,%f narc c = %f,%f arc->0 = %f,%f\n",
5346 vx(arc->centre), vy(arc->centre),
5347 vx(narc->centre), vy(narc->centre),
5348 arc->x0, arc->y0);
5349 #endif
5351 nax = vx(narc->centre) - vx(arc->centre);
5352 nay = vy(narc->centre) - vy(arc->centre);
5353 alen2 = pow(nax,2) + pow(nay,2);
5356 ax = arc->x0 - vx(arc->centre);
5357 ay = arc->y0 - vy(arc->centre);
5359 #ifdef DEBUG_EXPORT
5360 printf("norm narc = %f,%f - %f\tA=%f,%f\n", nax, nay, sqrt(alen2), ax, ay);
5361 #endif
5363 c = ((ax*nax)+(ay*nay)) / alen2;
5365 b1x = c * nax;
5366 b1y = c * nay;
5367 b2x = ax - b1x;
5368 b2y = ay - b1y;
5370 #ifdef DEBUG_EXPORT
5371 printf("proj = %f,%f perp proj = %f,%f\n", b1x, b1y, b2x, b2y);
5372 #endif
5374 *b1 = sqrt(pow(b1x,2) + pow(b1y,2));
5375 *b2 = sqrt(pow(b2x,2) + pow(b2y,2));
5379 guint
5380 calculate_arc_to_arc(toporouter_t *ar, toporouter_arc_t *parc, toporouter_arc_t *arc)
5382 gdouble theta, a, b, bx, by, a0x, a0y, a1x, a1y, m, preva, prevb;
5383 gint winddir;
5384 toporouter_arc_t *bigr, *smallr;
5386 if(parc->r > arc->r) {
5387 bigr = parc; smallr = arc;
5388 }else{
5389 bigr = arc; smallr = parc;
5391 #ifdef DEBUG_EXPORT
5392 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr->centre), vy(bigr->centre),
5393 vx(smallr->centre), vy(smallr->centre));
5394 #endif
5396 m = perpendicular_gradient(point_gradient(GTS_POINT(bigr->centre), GTS_POINT(smallr->centre)));
5398 if(bigr->centre == smallr->centre) {
5400 printf("bigr->centre == smallr->centre @ %f,%f\n", vx(smallr->centre), vy(smallr->centre));
5403 g_assert(bigr->centre != smallr->centre);
5405 if(parc->dir == arc->dir) {
5406 //export_arc_straight:
5408 theta = acos((bigr->r - smallr->r) / gts_point_distance(GTS_POINT(bigr->centre), GTS_POINT(smallr->centre)));
5409 a = bigr->r * sin(theta);
5410 b = bigr->r * cos(theta);
5412 point_from_point_to_point(bigr->centre, smallr->centre, b, &bx, &by);
5414 coords_on_line(bx, by, m, a, &a0x, &a0y, &a1x, &a1y);
5416 winddir = coord_wind(vx(smallr->centre), vy(smallr->centre), a0x, a0y, vx(bigr->centre), vy(bigr->centre));
5418 arc_ortho_projections(parc, arc, &prevb, &preva);
5419 //#ifdef DEBUG_EXPORT
5420 if(!winddir) {
5422 printf("STRAIGHT:\n");
5423 printf("bigr centre = %f,%f smallr centre = %f,%f\n", vx(bigr->centre), vy(bigr->centre),
5424 vx(smallr->centre), vy(smallr->centre));
5425 printf("theta = %f a = %f b = %f bigrr = %f d = %f po = %f\n", theta, a, b, bigr->r,
5426 gts_point_distance(GTS_POINT(bigr->centre), GTS_POINT(smallr->centre)),
5427 bigr->r / gts_point_distance(GTS_POINT(bigr->centre), GTS_POINT(smallr->centre)));
5428 printf("bigr-r = %f smallr-r = %f ratio = %f\n",
5429 bigr->r, smallr->r, (bigr->r - smallr->r) / gts_point_distance(GTS_POINT(bigr->centre), GTS_POINT(smallr->centre)));
5430 printf("preva = %f prevb = %f\n\n", preva, prevb);
5433 //#endif
5434 g_assert(winddir);
5436 if(bigr==parc) winddir = -winddir;
5438 if(winddir == bigr->dir) {
5439 if(bigr==arc) {
5440 bigr->x0 = a0x;
5441 bigr->y0 = a0y;
5442 }else{
5443 bigr->x1 = a0x;
5444 bigr->y1 = a0y;
5446 }else{
5447 if(bigr==arc) {
5448 bigr->x0 = a1x;
5449 bigr->y0 = a1y;
5450 }else{
5451 bigr->x1 = a1x;
5452 bigr->y1 = a1y;
5456 a = smallr->r * sin(theta);
5457 b = smallr->r * cos(theta);
5459 #ifdef DEBUG_EXPORT
5460 printf("a = %f b = %f\n", a, b);
5461 #endif
5462 point_from_point_to_point(smallr->centre, bigr->centre, -b, &bx, &by);
5464 coords_on_line(bx, by, m, a, &a0x, &a0y, &a1x, &a1y);
5466 if(winddir == bigr->dir) {
5467 if(bigr==arc) {
5468 smallr->x1 = a0x;
5469 smallr->y1 = a0y;
5470 }else{
5471 smallr->x0 = a0x;
5472 smallr->y0 = a0y;
5474 }else{
5475 if(bigr==arc) {
5476 smallr->x1 = a1x;
5477 smallr->y1 = a1y;
5478 }else{
5479 smallr->x0 = a1x;
5480 smallr->y0 = a1y;
5484 }else{
5486 //export_arc_twist:
5488 theta = acos((bigr->r + smallr->r) / gts_point_distance(GTS_POINT(bigr->centre), GTS_POINT(smallr->centre)));
5489 a = bigr->r * sin(theta);
5490 b = bigr->r * cos(theta);
5492 point_from_point_to_point(bigr->centre, smallr->centre, b, &bx, &by);
5494 coords_on_line(bx, by, m, a, &a0x, &a0y, &a1x, &a1y);
5496 winddir = coord_wind(vx(smallr->centre), vy(smallr->centre), a0x, a0y, vx(bigr->centre), vy(bigr->centre));
5497 //#ifdef DEBUG_EXPORT
5498 if(!winddir) {
5499 printf("TWIST:\n");
5500 printf("theta = %f a = %f b = %f r = %f d = %f po = %f\n", theta, a, b, bigr->r + smallr->r,
5501 gts_point_distance(GTS_POINT(bigr->centre), GTS_POINT(smallr->centre)),
5502 (bigr->r+smallr->r) / gts_point_distance(GTS_POINT(bigr->centre), GTS_POINT(smallr->centre)));
5504 printf("bigr centre = %f,%f smallr centre = %f,%f\n\n", vx(bigr->centre), vy(bigr->centre),
5505 vx(smallr->centre), vy(smallr->centre));
5507 printf("big wind = %d small wind = %d\n", bigr->dir, smallr->dir);
5508 return 1;
5510 //#endif
5511 /* if(!winddir) {
5512 smallr->centre->flags |= VERTEX_FLAG_RED;
5513 bigr->centre->flags |= VERTEX_FLAG_GREEN;
5514 //bigr->centre->flags |= VERTEX_FLAG_RED;
5516 int i;
5517 for(i=0;i<groupcount();i++) {
5518 char buffer[256];
5519 sprintf(buffer, "wind%d.png", i);
5520 toporouter_draw_surface(ar, ar->layers[i].surface, buffer, 2096, 2096, 2, NULL, i, NULL);
5523 return;
5526 g_assert(winddir);
5528 if(bigr==parc) winddir = -winddir;
5530 if(winddir == bigr->dir) {
5531 if(bigr==arc) {
5532 bigr->x0 = a0x;
5533 bigr->y0 = a0y;
5534 }else{
5535 bigr->x1 = a0x;
5536 bigr->y1 = a0y;
5538 }else{
5539 if(bigr==arc) {
5540 bigr->x0 = a1x;
5541 bigr->y0 = a1y;
5542 }else{
5543 bigr->x1 = a1x;
5544 bigr->y1 = a1y;
5548 a = smallr->r * sin(theta);
5549 b = smallr->r * cos(theta);
5551 point_from_point_to_point(smallr->centre, bigr->centre, b, &bx, &by);
5553 coords_on_line(bx, by, m, a, &a0x, &a0y, &a1x, &a1y);
5555 winddir = coord_wind(vx(smallr->centre), vy(smallr->centre), a0x, a0y, vx(bigr->centre), vy(bigr->centre));
5557 g_assert(winddir);
5559 if(bigr==parc) winddir = -winddir;
5561 if(winddir == smallr->dir) {
5562 if(bigr==arc) {
5563 smallr->x1 = a0x;
5564 smallr->y1 = a0y;
5565 }else{
5566 smallr->x0 = a0x;
5567 smallr->y0 = a0y;
5569 }else{
5570 if(bigr==arc) {
5571 smallr->x1 = a1x;
5572 smallr->y1 = a1y;
5573 }else{
5574 smallr->x0 = a1x;
5575 smallr->y0 = a1y;
5581 return 0;
5584 void
5585 export_oproutes(toporouter_t *ar, toporouter_oproute_t *oproute)
5587 guint layer = PCB->LayerGroups.Entries[oproute->layergroup][0];
5588 guint thickness = lookup_thickness(oproute->style);
5589 guint keepaway = lookup_keepaway(oproute->style);
5590 GList *arcs = oproute->arcs;
5591 toporouter_arc_t *arc, *parc = NULL;
5593 if(!arcs) {
5594 ar->wiring_score += export_pcb_drawline(layer, vx(oproute->term1), vy(oproute->term1), vx(oproute->term2), vy(oproute->term2), thickness, keepaway);
5595 return;
5599 // calculate_term_to_arc(oproute->term1, TOPOROUTER_ARC(arcs->data), 0, layer);
5601 while(arcs) {
5602 arc = TOPOROUTER_ARC(arcs->data);
5604 if(parc && arc) {
5605 ar->wiring_score += export_pcb_drawarc(layer, parc, thickness, keepaway);
5606 ar->wiring_score += export_pcb_drawline(layer, parc->x1, parc->y1, arc->x0, arc->y0, thickness, keepaway);
5607 }else if(!parc) {
5608 ar->wiring_score += export_pcb_drawline(layer, vx(oproute->term1), vy(oproute->term1), arc->x0, arc->y0, thickness, keepaway);
5611 parc = arc;
5612 arcs = arcs->next;
5614 ar->wiring_score += export_pcb_drawarc(layer, arc, thickness, keepaway);
5615 ar->wiring_score += export_pcb_drawline(layer, arc->x1, arc->y1, vx(oproute->term2), vy(oproute->term2), thickness, keepaway);
5621 void
5622 oproute_free(toporouter_oproute_t *oproute)
5624 GList *i = oproute->arcs;
5625 while(i) {
5626 toporouter_arc_t *arc = (toporouter_arc_t *) i->data;
5627 if(arc->centre->flags & VERTEX_FLAG_TEMP)
5628 gts_object_destroy(GTS_OBJECT(arc->centre));
5630 i = i->next;
5633 g_list_free(oproute->arcs);
5634 free(oproute);
5637 void
5638 oproute_calculate_tof(toporouter_oproute_t *oproute)
5640 GList *arcs = oproute->arcs;
5641 toporouter_arc_t *parc = NULL, *arc;
5643 oproute->tof = 0.;
5645 if(!arcs) {
5646 oproute->tof = gts_point_distance(GTS_POINT(oproute->term1), GTS_POINT(oproute->term2));
5647 return;
5650 while(arcs) {
5651 arc = TOPOROUTER_ARC(arcs->data);
5653 if(parc && arc) {
5654 oproute->tof += arc_angle(parc) * parc->r;
5655 oproute->tof += sqrt(pow(parc->x1-arc->x0,2)+pow(parc->y1-arc->y0,2));
5656 }else if(!parc) {
5657 oproute->tof += sqrt(pow(arc->x0-vx(oproute->term1),2)+pow(arc->y0-vy(oproute->term1),2));
5660 parc = arc;
5661 arcs = arcs->next;
5664 oproute->tof += arc_angle(parc) * parc->r;
5665 oproute->tof += sqrt(pow(arc->x1-vx(oproute->term2),2)+pow(arc->y1-vy(oproute->term2),2));
5669 gdouble
5670 line_line_distance_at_normal(
5671 gdouble line1_x1, gdouble line1_y1,
5672 gdouble line1_x2, gdouble line1_y2,
5673 gdouble line2_x1, gdouble line2_y1,
5674 gdouble line2_x2, gdouble line2_y2,
5675 gdouble x, gdouble y)
5677 gdouble m1 = perpendicular_gradient(cartesian_gradient(line1_x1, line1_y1, line1_x2, line1_y2));
5678 gdouble m2 = cartesian_gradient(line2_x1, line2_y1, line2_x2, line2_y2);
5679 gdouble c1 = (isinf(m1)) ? x : y - (m1 * x);
5680 gdouble c2 = (isinf(m2)) ? line2_x1 : line2_y1 - (m2 * line2_x1);
5682 gdouble intx, inty;
5684 if(isinf(m2)) intx = line2_x1;
5685 else if(isinf(m1)) intx = x;
5686 else intx = (c2 - c1) / (m1 - m2);
5688 inty = (isinf(m2)) ? (m1 * intx) + c1 : (m2 * intx) + c2;
5690 return sqrt(pow(x-intx,2)+pow(y-inty,2));
5693 void
5694 calculate_serpintine(gdouble delta, gdouble r, gdouble initiala, gdouble *a, guint *nhalfcycles)
5696 gdouble lhalfcycle = 2.*(initiala-r)+(M_PI*r);
5697 guint n;
5699 printf("lhalfcycle = %f r = %f\n", lhalfcycle, r);
5701 n = (delta - M_PI*r) / (lhalfcycle - 2.*r) + 1;
5702 *a = (delta + 4.*n*r - n*M_PI*r + 4.*r - M_PI*r)/(2.*n);
5703 *nhalfcycles = n;
5706 gdouble
5707 oproute_min_spacing(toporouter_oproute_t *a, toporouter_oproute_t *b)
5709 return lookup_thickness(a->style) / 2. + lookup_thickness(b->style) / 2. + MAX(lookup_keepaway(a->style), lookup_keepaway(b->style));
5712 gdouble
5713 vector_angle(gdouble ox, gdouble oy, gdouble ax, gdouble ay, gdouble bx, gdouble by)
5715 gdouble alen = sqrt(pow(ax-ox,2)+pow(ay-oy,2));
5716 gdouble blen = sqrt(pow(bx-ox,2)+pow(by-oy,2));
5717 return acos( ((ax-ox)*(bx-ox)+(ay-oy)*(by-oy)) / (alen * blen) );
5720 toporouter_serpintine_t *
5721 toporouter_serpintine_new(gdouble x, gdouble y, gdouble x0, gdouble y0, gdouble x1, gdouble y1, gpointer start, gdouble halfa, gdouble
5722 radius, guint nhalfcycles)
5724 toporouter_serpintine_t *serp = malloc(sizeof(toporouter_serpintine_t));
5725 serp->x = x;
5726 serp->y = y;
5727 serp->x0 = x0;
5728 serp->y0 = y0;
5729 serp->x1 = x1;
5730 serp->y1 = y1;
5731 serp->start = start;
5732 serp->halfa = halfa;
5733 serp->radius = radius;
5734 serp->nhalfcycles = nhalfcycles;
5735 serp->arcs = NULL;
5736 return serp;
5739 //#define DEBUG_RUBBERBAND 1
5741 gdouble
5742 check_non_intersect_vertex(gdouble x0, gdouble y0, gdouble x1, gdouble y1, toporouter_vertex_t *pathv, toporouter_vertex_t *arcv,
5743 toporouter_vertex_t *opv, gint wind, gint *arcwind, gdouble *arcr, guint debug)
5745 gdouble ms, line_int_x, line_int_y, x, y, d = 0., m;
5746 gdouble tx0, ty0, tx1, ty1;
5747 gint wind1, wind2;
5749 g_assert(pathv->routingedge);
5751 if(TOPOROUTER_IS_CONSTRAINT(pathv->routingedge)) {
5752 gdouble d = tvdistance(tedge_v1(pathv->routingedge), tedge_v2(pathv->routingedge)) / 2.;
5753 ms = min_spacing(pathv, arcv);
5754 if(ms > d) ms = d;
5755 }else{
5756 ms = edge_min_spacing(g_list_find(edge_routing(pathv->routingedge), pathv), pathv->routingedge, arcv, debug);
5760 if(!vertex_line_normal_intersection(x0, y0, x1, y1, vx(arcv), vy(arcv), &line_int_x, &line_int_y)) {
5762 if(coord_distance2(x0, y0, line_int_x, line_int_y) < coord_distance2(x1, y1, line_int_x, line_int_y))
5763 { line_int_x = x0; line_int_y = y0; }else{ line_int_x = x1; line_int_y = y1; }
5765 m = perpendicular_gradient(cartesian_gradient(vx(arcv), vy(arcv), line_int_x, line_int_y));
5766 }else{
5767 m = cartesian_gradient(x0, y0, x1, y1);
5770 coords_on_line(vx(arcv), vy(arcv), m, 100., &tx0, &ty0, &tx1, &ty1);
5772 wind1 = coord_wind(tx0, ty0, tx1, ty1, line_int_x, line_int_y);
5773 wind2 = coord_wind(tx0, ty0, tx1, ty1, vx(opv), vy(opv));
5775 if(!wind2 || wind1 == wind2) return -1.;
5777 if(!wind) {
5778 coords_on_line(line_int_x, line_int_y, perpendicular_gradient(m), ms, &tx0, &ty0, &tx1, &ty1);
5779 if(coord_distance2(tx0, ty0, vx(opv), vy(opv)) < coord_distance2(tx1, ty1, vx(opv), vy(opv)))
5780 { x = tx0; y = ty0; }else{ x = tx1; y = ty1; }
5781 }else{
5782 toporouter_vertex_t *parent = pathv->parent, *child = pathv->child;
5783 guint windtests = 0;
5785 d = coord_distance(vx(arcv), vy(arcv), line_int_x, line_int_y);
5786 coord_move_towards_coord_values(line_int_x, line_int_y, vx(arcv), vy(arcv), ms + d, &x, &y);
5787 rewind_test:
5788 wind1 = coord_wind(line_int_x, line_int_y, x, y, vx(parent), vy(parent));
5789 wind2 = coord_wind(line_int_x, line_int_y, x, y, vx(child), vy(child));
5790 if(wind1 && wind2 && wind1 == wind2) {
5791 // return -1.;
5792 if(windtests++ == 2) return -1.;
5794 if(parent->flags & VERTEX_FLAG_ROUTE) parent = parent->parent;
5795 if(child->flags & VERTEX_FLAG_ROUTE) child = child->child;
5796 goto rewind_test;
5801 *arcr = ms;
5802 *arcwind = tvertex_wind(pathv->parent, pathv, arcv);
5804 #ifdef DEBUG_RUBBERBAND
5805 //if(debug)
5806 // printf("non-int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, d + ms,
5807 // vx(arcv), vy(arcv), vx(opv), vy(opv));
5808 #endif
5810 return d + ms;
5813 gdouble
5814 check_intersect_vertex(gdouble x0, gdouble y0, gdouble x1, gdouble y1, toporouter_vertex_t *pathv, toporouter_vertex_t *arcv,
5815 toporouter_vertex_t *opv, gint wind, gint *arcwind, gdouble *arcr, guint debug)
5817 gdouble ms, line_int_x, line_int_y, x, y, d = 0.;
5819 if(TOPOROUTER_IS_CONSTRAINT(pathv->routingedge)) {
5820 gdouble d = tvdistance(tedge_v1(pathv->routingedge), tedge_v2(pathv->routingedge)) / 2.;
5821 ms = min_spacing(pathv, arcv);
5822 if(ms > d) ms = d;
5823 }else {
5824 ms = edge_min_spacing(g_list_find(edge_routing(pathv->routingedge), pathv), pathv->routingedge, arcv, debug);
5827 if(!vertex_line_normal_intersection(x0, y0, x1, y1, vx(arcv), vy(arcv), &line_int_x, &line_int_y))
5828 return -1.;
5830 d = coord_distance(line_int_x, line_int_y, vx(arcv), vy(arcv));
5833 if(d > ms - EPSILON)
5834 return -1.;
5836 coord_move_towards_coord_values(vx(arcv), vy(arcv), line_int_x, line_int_y, ms, &x, &y);
5838 *arcr = ms;
5839 *arcwind = tvertex_wind(pathv->parent, pathv, arcv);
5840 // *arcwind = coord_wind(x0, y0, x, y, x1, y1);
5841 #ifdef DEBUG_RUBBERBAND
5842 //if(debug)
5843 // printf("int check %f,%f ms %f d %f arcv %f,%f opv %f,%f\n", vx(arcv), vy(arcv), ms, ms - d,
5844 // vx(arcv), vy(arcv), vx(opv), vy(opv));
5845 #endif
5847 return ms - d;
5850 /* returns non-zero if arc has loops */
5851 guint
5852 check_arc_for_loops(gpointer t1, toporouter_arc_t *arc, gpointer t2)
5854 gdouble x0, y0, x1, y1;
5856 if(TOPOROUTER_IS_VERTEX(t1)) { x0 = vx(TOPOROUTER_VERTEX(t1)); y0 = vy(TOPOROUTER_VERTEX(t1)); }
5857 else { x0 = TOPOROUTER_ARC(t1)->x1; y0 = TOPOROUTER_ARC(t1)->y1; }
5859 if(TOPOROUTER_IS_VERTEX(t2)) { x1 = vx(TOPOROUTER_VERTEX(t2)); y1 = vy(TOPOROUTER_VERTEX(t2)); }
5860 else { x1 = TOPOROUTER_ARC(t2)->x0; y1 = TOPOROUTER_ARC(t2)->y0; }
5862 if(coord_intersect_prop(x0, y0, arc->x0, arc->y0, arc->x1, arc->y1, x1, y1) ) {
5863 // ||
5864 // (arc->x0 > arc->x1 - EPSILON && arc->x0 < arc->x1 + EPSILON &&
5865 // arc->y0 > arc->y1 - EPSILON && arc->y0 < arc->y1 + EPSILON)
5866 // ) {
5867 #ifdef DEBUG_RUBBERBAND
5868 printf("LOOPS %f %f -> %f %f & %f %f -> %f %f\n", x0, y0, arc->x0, arc->y0, arc->x1, arc->y1, x1, y1);
5869 #endif
5870 return 1;
5872 return 0;
5875 toporouter_rubberband_arc_t *
5876 new_rubberband_arc(toporouter_vertex_t *pathv, toporouter_vertex_t *arcv, gdouble r, gdouble d, gint wind, GList *list)
5878 toporouter_rubberband_arc_t *rba = malloc(sizeof(toporouter_rubberband_arc_t));
5879 rba->pathv = pathv;
5880 rba->arcv = arcv;
5881 rba->r = r;
5882 rba->d = d;
5883 rba->wind = wind;
5884 rba->list = list;
5885 return rba;
5888 gint
5889 compare_rubberband_arcs(toporouter_rubberband_arc_t *a, toporouter_rubberband_arc_t *b)
5890 { return b->d - a->d; }
5892 void
5893 free_list_elements(gpointer data, gpointer user_data)
5894 { free(data); }
5897 /* returns the edge opposite v from the triangle facing (x,y), or NULL if v is colinear with an edge between v and a neighbor */
5899 GtsEdge *
5900 vertex_edge_facing_vertex(GtsVertex *v, gdouble x, gdouble y)
5902 GSList *ts = gts_vertex_triangles(GTS_VERTEX(n), NULL);
5903 GSList *i = ts;
5905 while(i) {
5906 GtsTriangle *t = GTS_TRIANGLE(i->data);
5907 GtsEdge *e = gts_triangle_edge_opposite(t, v);
5909 if(coord_wind(vx(edge_v1(e)), vy(edge_v1(e)), vx(v), vy(v), x, y) == vertex_wind(edge_v1(e), v, edge_v2(e)) &&
5910 coord_wind(vx(edge_v2(e)), vy(edge_v2(e)), vx(v), vy(v), x, y) == vertex_wind(edge_v2(e), v, edge_v1(e))
5912 g_slist_free(ts);
5913 return e;
5916 i = i->next;
5919 g_slist_free(ts);
5920 return NULL;
5924 gdouble
5925 check_adj_pushing_vertex(toporouter_oproute_t *oproute, gdouble x0, gdouble y0, gdouble x1, gdouble y1, toporouter_vertex_t *v, gdouble *arcr, gint *arcwind, toporouter_vertex_t **arc)
5927 GSList *ns = gts_vertex_neighbors(GTS_VERTEX(v), NULL, NULL);
5928 GSList *i = ns;
5929 gdouble maxd = 0.;
5931 while(i) {
5932 toporouter_vertex_t *n = TOPOROUTER_VERTEX(i->data);
5933 gdouble segintx, seginty;
5934 if(vertex_line_normal_intersection(x0, y0, x1, y1, vx(n), vy(n), &segintx, &seginty)) {
5935 toporouter_edge_t *e = tedge(n, v);
5936 gdouble ms = 0., d = coord_distance(segintx, seginty, vx(n), vy(n));
5937 toporouter_vertex_t *a, *b;
5938 GList *closestnet = NULL;
5940 g_assert(e);
5942 if(v == tedge_v1(e)) {
5943 a = tedge_v1(e);
5944 b = tedge_v2(e);
5945 closestnet = edge_routing(e);
5946 }else{
5947 a = tedge_v2(e);
5948 b = tedge_v1(e);
5949 closestnet = g_list_last(edge_routing(e));
5952 if(closestnet) {
5953 ms = edge_min_spacing(closestnet, e, b, 0);
5954 ms += min_oproute_net_spacing(oproute, TOPOROUTER_VERTEX(closestnet->data));
5955 }else{
5956 ms = min_oproute_vertex_spacing(oproute, b);
5959 if(ms - d > maxd) {
5960 *arcr = ms;
5961 *arc = n;
5962 maxd = ms - d;
5963 if(vx(v) == x0 && vy(v) == y0) {
5964 *arcwind = coord_wind(x0, y0, vx(n), vy(n), x1, y1);
5965 }else if(vx(v) == x1 && vy(v) == y1) {
5966 *arcwind = coord_wind(x1, y1, vx(n), vy(n), x0, y0);
5967 }else{
5968 fprintf(stderr, "ERROR: check_adj_pushing_vertex encountered bad vertex v (coordinates don't match)\n");
5973 i = i->next;
5976 g_slist_free(ns);
5977 return maxd;
5981 // path is t1 path
5982 GList *
5983 oproute_rubberband_segment(toporouter_t *r, toporouter_oproute_t *oproute, GList *path, gpointer t1, gpointer t2, guint debug)
5985 gdouble x0, y0, x1, y1;
5986 toporouter_vertex_t *v1, *v2, *av1, *av2; /* v{1,2} are the vertex terminals of the segment, or arc terminal centres */
5987 toporouter_arc_t *arc1 = NULL, *arc2 = NULL, *newarc = NULL; /* arc{1,2} are the arc terminals of the segment, if they exist */
5988 GList *i = path;
5989 GList *list1, *list2;
5991 GList *arcs = NULL;
5992 toporouter_rubberband_arc_t *max = NULL;
5994 gdouble d, arcr;
5995 gint v1wind, v2wind, arcwind;
5997 if(TOPOROUTER_IS_VERTEX(t1)) {
5998 v1 = TOPOROUTER_VERTEX(t1);
5999 x0 = vx(v1); y0 = vy(v1);
6000 }else{
6001 g_assert(TOPOROUTER_IS_ARC(t1));
6002 arc1 = TOPOROUTER_ARC(t1);
6003 v1 = TOPOROUTER_VERTEX(arc1->v1);
6004 x0 = arc1->x1;
6005 y0 = arc1->y1;
6008 if(TOPOROUTER_IS_VERTEX(t2)) {
6009 v2 = TOPOROUTER_VERTEX(t2);
6010 x1 = vx(v2); y1 = vy(v2);
6011 }else{
6012 g_assert(TOPOROUTER_IS_ARC(t2));
6013 arc2 = TOPOROUTER_ARC(t2);
6014 v2 = TOPOROUTER_VERTEX(arc2->v2);
6015 x1 = arc2->x0;
6016 y1 = arc2->y0;
6019 #define TEST_AND_INSERT(z) if(d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v, z, arcr, d, arcwind, i));
6020 #define ARC_CHECKS(z) (!(arc1 && arc1->centre == z) && !(arc2 && arc2->centre == z) && \
6021 !(TOPOROUTER_IS_VERTEX(t1) && z == v1) && !(TOPOROUTER_IS_VERTEX(t2) && z == v2))
6023 if(v1 == v2 || !i->next || TOPOROUTER_VERTEX(i->data) == v2) return NULL;
6025 //#ifdef DEBUG_RUBBERBAND
6026 if(debug) {
6027 printf("\nRB: line %f,%f %f,%f v1 = %f,%f v2 = %f,%f \n ", x0, y0, x1, y1, vx(v1), vy(v1), vx(v2), vy(v2));
6028 // if(v1->routingedge) print_edge(v1->routingedge);
6029 // if(v2->routingedge) print_edge(v2->routingedge);
6032 //#endif
6034 /* check the vectices adjacent to the terminal vectices for push against the segment */
6035 //if(TOPOROUTER_IS_VERTEX(t1)) {
6036 // toporouter_vertex_t *arcc = NULL;
6037 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v1, &arcr, &arcwind, &arcc);
6038 // g_assert(arcc != v1);
6039 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v1, arcc, arcr, d, arcwind, path->next));
6042 //if(TOPOROUTER_IS_VERTEX(t2)) {
6043 // toporouter_vertex_t *arcc = NULL;
6044 // d = check_adj_pushing_vertex(oproute, x0, y0, x1, y1, v2, &arcr, &arcwind, &arcc);
6045 // g_assert(arcc != v2);
6046 // if(ARC_CHECKS(arcc) && d > EPSILON) arcs = g_list_prepend(arcs, new_rubberband_arc(v2, arcc, arcr, d, arcwind, g_list_last(path)->prev));
6049 i = i->next;
6050 while(i) {
6051 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
6053 if(v == v2 || v == v1 || !v->routingedge) break;
6055 #ifdef DEBUG_RUBBERBAND
6056 // if(debug)
6057 // printf("current v %f,%f - edge %f,%f %f,%f\n", vx(v), vy(v),
6058 // vx(tedge_v1(v->routingedge)), vy(tedge_v1(v->routingedge)),
6059 // vx(tedge_v2(v->routingedge)), vy(tedge_v2(v->routingedge))
6060 // );
6061 #endif
6062 g_assert(v->routingedge);
6064 v1wind = coord_wind(x0, y0, x1, y1, vx(tedge_v1(v->routingedge)), vy(tedge_v1(v->routingedge)));
6065 v2wind = coord_wind(x0, y0, x1, y1, vx(tedge_v2(v->routingedge)), vy(tedge_v2(v->routingedge)));
6066 // if(debug) printf("\twinds: %d %d\n", v1wind, v2wind);
6067 if(!v1wind && !v2wind) { i = i->next; continue; }
6070 if(v1wind && v2wind && v1wind != v2wind) { /* edge is cutting through the current segment */
6072 if(ARC_CHECKS(tedge_v1(v->routingedge)) ){ /* edge v1 is not the centre of an arc terminal */
6073 d = check_intersect_vertex(x0, y0, x1, y1, v, tedge_v1(v->routingedge), tedge_v2(v->routingedge), v1wind, &arcwind, &arcr, debug);
6074 TEST_AND_INSERT(tedge_v1(v->routingedge));
6077 if(ARC_CHECKS(tedge_v2(v->routingedge)) ){ /* edge v2 is not the centre of an arc terminal */
6078 d = check_intersect_vertex(x0, y0, x1, y1, v, tedge_v2(v->routingedge), tedge_v1(v->routingedge), v2wind, &arcwind, &arcr, debug);
6079 TEST_AND_INSERT(tedge_v2(v->routingedge));
6081 }else{ /* edge is on one side of the segment */
6083 if(ARC_CHECKS(tedge_v1(v->routingedge)) ){ /* edge v1 is not the centre of an arc terminal */
6084 d = check_non_intersect_vertex(x0, y0, x1, y1, v, tedge_v1(v->routingedge), tedge_v2(v->routingedge), v1wind, &arcwind, &arcr, debug);
6085 TEST_AND_INSERT(tedge_v1(v->routingedge));
6088 if(ARC_CHECKS(tedge_v2(v->routingedge)) ){ /* edge v2 is not the centre of an arc terminal */
6089 d = check_non_intersect_vertex(x0, y0, x1, y1, v, tedge_v2(v->routingedge), tedge_v1(v->routingedge), v2wind, &arcwind, &arcr, debug);
6090 TEST_AND_INSERT(tedge_v2(v->routingedge));
6094 i = i->next;
6097 arcs = g_list_sort(arcs, (GCompareFunc) compare_rubberband_arcs);
6098 rubberband_insert_maxarc:
6099 if(!arcs) return NULL;
6100 max = TOPOROUTER_RUBBERBAND_ARC(arcs->data);
6102 av2 = max->pathv; i = max->list->next;
6103 while(i) {
6104 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
6105 if(v->routingedge && (tedge_v1(v->routingedge) == max->arcv || tedge_v2(v->routingedge) == max->arcv)) {
6106 av2 = v; i = i->next; continue;
6108 break;
6111 av1 = max->pathv; i = max->list->prev;
6112 while(i) {
6113 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
6114 if(v->routingedge && (tedge_v1(v->routingedge) == max->arcv || tedge_v2(v->routingedge) == max->arcv)) {
6115 av1 = v; i = i->prev; continue;
6117 break;
6119 //#ifdef DEBUG_RUBBERBAND
6120 if(debug)
6121 printf("newarc @ %f,%f \t v1 = %f,%f v2 = %f,%f r = %f\n", vx(max->arcv), vy(max->arcv), vx(av1), vy(av1), vx(av2), vy(av2), max->r);
6122 //#endif
6123 newarc = toporouter_arc_new(oproute, av1, av2, max->arcv, max->r, max->wind);
6125 if(TOPOROUTER_IS_VERTEX(t1))
6126 calculate_term_to_arc(TOPOROUTER_VERTEX(t1), newarc, 0);
6127 else if(calculate_arc_to_arc(r, TOPOROUTER_ARC(t1), newarc)) {
6128 printf("\tERROR: best: r = %f d = %f\n", max->r, max->d);
6129 printf("\tOPROUTE: %s\n", oproute->netlist);
6130 print_vertex(oproute->term1);
6131 print_vertex(oproute->term2);
6132 return NULL;
6135 if(TOPOROUTER_IS_VERTEX(t2))
6136 calculate_term_to_arc(TOPOROUTER_VERTEX(t2), newarc, 1);
6137 else if(calculate_arc_to_arc(r, newarc, TOPOROUTER_ARC(t2))) {
6138 printf("\tERROR: best: r = %f d = %f\n", max->r, max->d);
6139 printf("\tOPROUTE: %s\n", oproute->netlist);
6140 print_vertex(oproute->term1);
6141 print_vertex(oproute->term2);
6142 return NULL;
6145 //if(check_arc_for_loops(t1, newarc, t2)) {
6146 // if(arc1 && arc2) calculate_arc_to_arc(r, arc1, arc2);
6147 // else if(arc1) calculate_term_to_arc(TOPOROUTER_VERTEX(t2), arc1, 1);
6148 // else if(arc2) calculate_term_to_arc(TOPOROUTER_VERTEX(t1), arc2, 0);
6150 //#ifdef DEBUG_RUBBERBAND
6151 // printf("REMOVING NEW ARC @ %f,%f\n", vx(newarc->centre), vy(newarc->centre));
6152 // //TODO: properly remove newarc
6153 //#endif
6155 // arcs = g_list_remove(arcs, max);
6156 // free(max);
6157 // goto rubberband_insert_maxarc;
6161 list1 = oproute_rubberband_segment(r, oproute, path, t1, newarc, debug);
6162 list2 = oproute_rubberband_segment(r, oproute, i->next, newarc, t2, debug);
6164 if(list1) {
6165 GList *list = g_list_last(list1);
6166 toporouter_arc_t *testarc = TOPOROUTER_ARC(list->data);
6167 toporouter_arc_t *parc = list->prev ? TOPOROUTER_ARC(list->prev->data) : arc1;
6168 gdouble px = parc ? parc->x1 : vx(TOPOROUTER_VERTEX(t1)), py = parc ? parc->y1 : vy(TOPOROUTER_VERTEX(t1));
6170 if(coord_intersect_prop(px, py, testarc->x0, testarc->y0, testarc->x1, testarc->y1, newarc->x0, newarc->y0)) {
6171 list1 = g_list_remove(list1, testarc);
6172 if(parc) calculate_arc_to_arc(r, parc, newarc);
6173 else calculate_term_to_arc(TOPOROUTER_VERTEX(t1), newarc, 0);
6174 //#ifdef DEBUG_RUBBERBAND
6175 if(debug)
6176 printf("REMOVING ARC @ %f,%f\n", vx(testarc->centre), vy(testarc->centre));
6177 //#endif
6180 if(list2) {
6181 toporouter_arc_t *testarc = TOPOROUTER_ARC(list2->data);
6182 toporouter_arc_t *narc = list2->next ? TOPOROUTER_ARC(list2->next->data) : arc2;
6183 gdouble nx = narc ? narc->x0 : vx(TOPOROUTER_VERTEX(t2)), ny = narc ? narc->y0 : vy(TOPOROUTER_VERTEX(t2));
6185 if(coord_intersect_prop(newarc->x1, newarc->y1, testarc->x0, testarc->y0, testarc->x1, testarc->y1, nx, ny)) {
6186 list2 = g_list_remove(list2, testarc);
6187 if(narc) calculate_arc_to_arc(r, newarc, narc);
6188 else calculate_term_to_arc(TOPOROUTER_VERTEX(t2), newarc, 1);
6190 //#ifdef DEBUG_RUBBERBAND
6191 if(debug)
6192 printf("REMOVING ARC @ %f,%f\n", vx(testarc->centre), vy(testarc->centre));
6193 //#endif
6197 g_list_foreach(arcs, free_list_elements, NULL);
6198 g_list_free(arcs);
6200 return g_list_concat(list1, g_list_prepend(list2, newarc));
6203 void
6204 oproute_check_all_loops(toporouter_t *r, toporouter_oproute_t *oproute)
6206 GList *i;
6207 gpointer t1;
6209 loopcheck_restart:
6210 t1 = oproute->term1;
6211 i = oproute->arcs;
6212 while(i) {
6213 toporouter_arc_t *arc = TOPOROUTER_ARC(i->data);
6214 gpointer t2 = i->next ? i->next->data : oproute->term2;
6216 if(check_arc_for_loops(t1, arc, t2)) {
6218 if(TOPOROUTER_IS_ARC(t1) && TOPOROUTER_IS_ARC(t2))
6219 calculate_arc_to_arc(r, TOPOROUTER_ARC(t1), TOPOROUTER_ARC(t2));
6220 else if(TOPOROUTER_IS_ARC(t1))
6221 calculate_term_to_arc(TOPOROUTER_VERTEX(t2), TOPOROUTER_ARC(t1), 1);
6222 else if(TOPOROUTER_IS_ARC(t2))
6223 calculate_term_to_arc(TOPOROUTER_VERTEX(t1), TOPOROUTER_ARC(t2), 0);
6225 oproute->arcs = g_list_remove(oproute->arcs, arc);
6226 goto loopcheck_restart;
6229 t1 = arc;
6231 i = i->next;
6236 GtsTriangle *
6237 opposite_triangle(GtsTriangle *t, toporouter_edge_t *e)
6239 GSList *i = GTS_EDGE(e)->triangles;
6241 g_assert(e && t);
6243 while(i) {
6244 if(GTS_TRIANGLE(i->data) != t) return GTS_TRIANGLE(i->data);
6245 i = i->next;
6248 return NULL;
6252 void
6253 speccut_edge_routing_from_edge(GList *i, toporouter_edge_t *e)
6255 while(i) {
6256 toporouter_vertex_t *curv = TOPOROUTER_VERTEX(i->data);
6258 if(!(curv->flags & VERTEX_FLAG_TEMP)) {
6259 toporouter_vertex_t *newv = tvertex_intersect(curv, curv->parent, tedge_v1(e), tedge_v2(e));
6261 // printf("\nCURV:\n");
6262 // print_vertex(curv);
6264 // printf("CURV child:\n");
6265 // if(curv->child)
6266 // print_vertex(curv->child);
6267 // else
6268 // printf("NULL\n");
6270 // printf("CURV parent:\n");
6271 // if(curv->parent)
6272 // print_vertex(curv->parent);
6273 // else
6274 // printf("NULL\n");
6276 if(newv) {
6277 gint index;
6278 newv->flags |= VERTEX_FLAG_ROUTE;
6279 newv->flags |= VERTEX_FLAG_SPECCUT;
6280 e->routing = g_list_insert_sorted_with_data(e->routing, newv, routing_edge_insert, e);
6281 newv->route = curv->route;
6282 newv->oproute = curv->oproute;
6283 newv->routingedge = e;
6284 GTS_POINT(newv)->z = vz(curv);
6286 newv->parent = curv->parent;
6287 newv->child = curv;
6289 // curv->parent = newv;
6291 index = g_list_index(newv->route->path, curv);
6293 newv->route->path = g_list_insert(newv->route->path, newv, index);
6296 if(newv->oproute) newv->oproute->path = newv->route->path;
6299 if(!(curv->child->routingedge)) {
6300 newv = tvertex_intersect(curv, curv->child, tedge_v1(e), tedge_v2(e));
6302 if(newv) {
6303 gint index;
6304 newv->flags |= VERTEX_FLAG_ROUTE;
6305 newv->flags |= VERTEX_FLAG_SPECCUT;
6306 e->routing = g_list_insert_sorted_with_data(e->routing, newv, routing_edge_insert, e);
6307 newv->route = curv->route;
6308 newv->oproute = curv->oproute;
6309 newv->routingedge = e;
6310 GTS_POINT(newv)->z = vz(curv);
6312 newv->parent = curv;
6313 newv->child = curv->child;
6315 // curv->child = newv;
6317 index = g_list_index(newv->route->path, curv);
6319 newv->route->path = g_list_insert(newv->route->path, newv, index+1);
6322 if(newv->oproute) newv->oproute->path = newv->route->path;
6328 i = i->next;
6333 void
6334 speccut_edge_patch_links(toporouter_edge_t *e)
6336 GList *i = e->routing;
6337 while(i) {
6338 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
6339 v->parent->child = v;
6340 v->child->parent = v;
6341 i = i->next;
6345 gint
6346 check_speccut(toporouter_oproute_t *oproute, toporouter_vertex_t *v1, toporouter_vertex_t *v2, toporouter_edge_t *e, toporouter_edge_t *e1, toporouter_edge_t *e2)
6348 GtsTriangle *t, *opt;
6349 toporouter_vertex_t *opv, *opv2;
6350 toporouter_edge_t *ope1, *ope2;
6351 gdouble cap, flow, line_int_x, line_int_y;
6353 if(TOPOROUTER_IS_CONSTRAINT(e)) return 0;
6356 if(!(t = gts_triangle_use_edges(GTS_EDGE(e), GTS_EDGE(e1), GTS_EDGE(e2)))) {
6357 printf("check_speccut: NULL t\n");
6358 return 0;
6361 if(!(opt = opposite_triangle(t, e))) {
6362 printf("check_speccut: NULL opt\n");
6363 return 0;
6366 if(!(opv = segment_common_vertex(GTS_SEGMENT(e1), GTS_SEGMENT(e2)))) {
6367 printf("check_speccut: NULL opv\n");
6368 return 0;
6371 if(!(opv2 = TOPOROUTER_VERTEX(gts_triangle_vertex_opposite(opt, GTS_EDGE(e))))) {
6372 printf("check_speccut: NULL opv2\n");
6373 return 0;
6376 //TODO: shifting it out of the way would be better
6377 if(e->routing) {
6378 GList *i = e->routing;
6379 while(i) {
6380 toporouter_vertex_t *ev = TOPOROUTER_VERTEX(i->data);
6381 if(!tvertex_wind(opv, ev, opv2)) return 0;
6382 i = i->next;
6387 ope1 = tedge(opv2, tedge_v1(e));
6388 ope2 = tedge(opv2, tedge_v2(e));
6390 if(!tvertex_wind(opv2, tedge_v1(e), opv)) return 0;
6391 if(!tvertex_wind(opv2, tedge_v2(e), opv)) return 0;
6393 if(!vertex_line_normal_intersection(
6394 vx(tedge_v1(e)), vy(tedge_v1(e)),
6395 vx(tedge_v2(e)), vy(tedge_v2(e)),
6396 vx(opv2), vy(opv2),
6397 &line_int_x, &line_int_y)) return 0;
6400 // return 0;
6401 //if(vertex_line_normal_intersection(tev1x(e), tev1y(e), tev2x(e), tev2y(e), vx(opv), vy(opv), &line_int_x, &line_int_y))
6402 // return 0;
6404 g_assert(opt && opv2);
6406 /* this is just temp, for the purposes of determining flow */
6407 if(tedge_v1(ope1) == opv2) {
6408 if(TOPOROUTER_IS_CONSTRAINT(ope1))
6409 TOPOROUTER_CONSTRAINT(ope1)->routing = g_list_append(TOPOROUTER_CONSTRAINT(ope1)->routing, v1);
6410 else
6411 ope1->routing = g_list_append(ope1->routing, v1);
6412 }else{
6413 if(TOPOROUTER_IS_CONSTRAINT(ope1))
6414 TOPOROUTER_CONSTRAINT(ope1)->routing = g_list_prepend(TOPOROUTER_CONSTRAINT(ope1)->routing, v1);
6415 else
6416 ope1->routing = g_list_prepend(ope1->routing, v1);
6419 cap = triangle_interior_capacity(opt, opv2);
6420 flow = flow_from_edge_to_edge(opt, tedge(opv2, tedge_v1(e)), tedge(opv2, tedge_v2(e)), opv2, v1);
6422 /* temp v1 removed */
6423 if(TOPOROUTER_IS_CONSTRAINT(ope1))
6424 TOPOROUTER_CONSTRAINT(ope1)->routing = g_list_remove(TOPOROUTER_CONSTRAINT(ope1)->routing, v1);
6425 else
6426 ope1->routing = g_list_remove(ope1->routing, v1);
6428 if(flow >= cap) {
6429 toporouter_edge_t *newe = TOPOROUTER_EDGE(gts_edge_new(GTS_EDGE_CLASS(toporouter_edge_class()), GTS_VERTEX(opv), GTS_VERTEX(opv2)));
6431 speccut_edge_routing_from_edge(edge_routing(e1), newe);
6432 speccut_edge_routing_from_edge(edge_routing(e2), newe);
6433 speccut_edge_routing_from_edge(edge_routing(ope1), newe);
6434 speccut_edge_routing_from_edge(edge_routing(ope2), newe);
6436 speccut_edge_patch_links(newe);
6438 printf("SPECCUT WITH v %f,%f for seg %f,%f %f,%f detected\n", vx(opv2), vy(opv2),
6439 vx(v1), vy(v1),
6440 vx(v2), vy(v2));
6441 printf("\tflow %f cap %f\n", flow, cap);
6442 print_edge(newe);
6444 if(newe->routing) return 1;
6448 return 0;
6452 gint
6453 oproute_path_speccut(toporouter_oproute_t *oproute)
6455 GList *i;
6456 toporouter_vertex_t *pv;
6457 path_speccut_restart:
6458 i = oproute->path;
6459 pv = NULL;
6460 while(i) {
6461 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
6464 if(pv && (v->routingedge || pv->routingedge) && !(pv->flags & VERTEX_FLAG_SPECCUT) && !(v->flags & VERTEX_FLAG_SPECCUT)) {
6466 if(!v->routingedge) {
6467 if(check_speccut(oproute, pv, v, tedge(tedge_v1(pv->routingedge), v), pv->routingedge, tedge(tedge_v2(pv->routingedge), v)))
6468 goto path_speccut_restart;
6469 if(check_speccut(oproute, pv, v, tedge(tedge_v2(pv->routingedge), v), pv->routingedge, tedge(tedge_v1(pv->routingedge), v)))
6470 goto path_speccut_restart;
6471 }else if(!pv->routingedge) {
6472 if(check_speccut(oproute, v, pv, tedge(tedge_v1(v->routingedge), pv), v->routingedge, tedge(tedge_v2(v->routingedge), pv)))
6473 goto path_speccut_restart;
6474 if(check_speccut(oproute, v, pv, tedge(tedge_v2(v->routingedge), pv), v->routingedge, tedge(tedge_v1(v->routingedge), pv)))
6475 goto path_speccut_restart;
6476 }else{
6477 toporouter_vertex_t *v1 = NULL, *v2 = NULL;
6478 edges_third_edge(GTS_SEGMENT(v->routingedge), GTS_SEGMENT(pv->routingedge), &v1, &v2);
6479 if(check_speccut(oproute, v, pv, tedge(v1, v2), v->routingedge, pv->routingedge))
6480 goto path_speccut_restart;
6485 pv = v;
6486 i = i->next;
6489 return 0;
6492 toporouter_oproute_t *
6493 oproute_rubberband(toporouter_t *r, GList *path)
6495 toporouter_oproute_t *oproute = malloc(sizeof(toporouter_oproute_t));
6497 g_assert(path);
6499 oproute->term1 = TOPOROUTER_VERTEX(path->data);
6500 oproute->term2 = TOPOROUTER_VERTEX(g_list_last(path)->data);
6501 oproute->arcs = NULL;
6502 oproute->style = vertex_bbox(oproute->term1)->cluster->netlist->style;
6503 oproute->netlist = vertex_bbox(oproute->term1)->cluster->netlist->netlist;
6504 oproute->layergroup = vz(oproute->term1);
6505 oproute->path = path;
6506 oproute->serp = NULL;
6508 oproute->term1->parent = NULL;
6509 oproute->term2->child = NULL;
6511 path_set_oproute(path, oproute);
6513 // if(!strcmp(oproute->netlist, " unnamed_net1"))
6514 oproute_path_speccut(oproute);
6516 #ifdef DEBUG_RUBBERBAND
6517 if(!strcmp(oproute->netlist, " VCC3V3") && vx(oproute->term1) == 95700. && vy(oproute->term1) == 70800. &&
6518 vx(oproute->term2) == 196700. && vy(oproute->term2) == 67300.)
6520 // printf("OPROUTE %s - %f,%f %f,%f\n", oproute->netlist, vx(oproute->term1), vy(oproute->term1), vx(oproute->term2), vy(oproute->term2));
6521 // print_path(path);
6522 oproute->arcs = oproute_rubberband_segment(r, oproute, path, oproute->term1, oproute->term2, 1);
6523 }else
6524 #endif
6525 oproute->arcs = oproute_rubberband_segment(r, oproute, path, oproute->term1, oproute->term2, 0);
6527 oproute_check_all_loops(r, oproute);
6528 return oproute;
6532 void
6533 toporouter_export(toporouter_t *r)
6535 GList *i = r->routednets;
6536 GList *oproutes = NULL;
6538 while(i) {
6539 toporouter_route_t *routedata = TOPOROUTER_ROUTE(i->data);
6540 toporouter_oproute_t *oproute = oproute_rubberband(r, routedata->path);
6541 oproutes = g_list_prepend(oproutes, oproute);
6542 i = i->next;
6545 i = oproutes;
6546 while(i) {
6547 toporouter_oproute_t *oproute = (toporouter_oproute_t *) i->data;
6548 export_oproutes(r, oproute);
6549 oproute_free(oproute);
6550 i = i->next;
6553 Message(_("Reticulating splines... successful\n\n"));
6554 Message(_("Wiring cost: %f inches\n"), r->wiring_score / 1000.);
6555 printf("Wiring cost: %f inches\n", r->wiring_score / 1000.);
6557 g_list_free(oproutes);
6561 toporouter_route_t *
6562 routedata_create(void)
6564 toporouter_route_t *routedata = malloc(sizeof(toporouter_route_t));
6565 routedata->netlist = NULL;
6566 routedata->alltemppoints = NULL;
6567 routedata->path = NULL;
6568 routedata->curpoint = NULL;
6569 routedata->pscore = routedata->score = 0.;
6570 routedata->flags = 0;
6571 routedata->src = routedata->dest = NULL;
6572 routedata->psrc = routedata->pdest = NULL;
6573 routedata->ppath = routedata->topopath = NULL;
6575 routedata->ppathindices = NULL;
6577 routedata->destvertices = routedata->srcvertices = NULL;
6578 return routedata;
6581 void
6582 print_routedata(toporouter_route_t *routedata)
6584 GList *srcvertices = cluster_vertices(routedata->src);
6585 GList *destvertices = cluster_vertices(routedata->dest);
6587 printf("ROUTEDATA:\n");
6588 printf("SRCVERTICES:\n");
6589 print_vertices(srcvertices);
6590 printf("DESTVERTICES:\n");
6591 print_vertices(destvertices);
6593 g_list_free(srcvertices);
6594 g_list_free(destvertices);
6597 toporouter_route_t *
6598 import_route(toporouter_t *r, RatType *line)
6600 toporouter_route_t *routedata = routedata_create();
6602 routedata->src = cluster_find(r, line->Point1.X, line->Point1.Y, line->group1);
6603 routedata->dest = cluster_find(r, line->Point2.X, line->Point2.Y, line->group2);
6605 if(!routedata->src) printf("couldn't locate src\n");
6606 if(!routedata->dest) printf("couldn't locate dest\n");
6608 if(!routedata->src || !routedata->dest) {
6609 printf("PROBLEM: couldn't locate rat src or dest for rat %d,%d,%d -> %d,%d,%d\n",
6610 line->Point1.X, line->Point1.Y, line->group1, line->Point2.X, line->Point2.Y, line->group2);
6611 free(routedata);
6612 return NULL;
6615 routedata->netlist = routedata->src->netlist;
6617 g_assert(routedata->src->netlist == routedata->dest->netlist);
6619 g_ptr_array_add(r->routes, routedata);
6620 g_ptr_array_add(routedata->netlist->routes, routedata);
6622 r->failednets = g_list_prepend(r->failednets, routedata);
6624 return routedata;
6627 void
6628 delete_route(toporouter_route_t *routedata, guint destroy)
6630 GList *i = routedata->path;
6631 toporouter_vertex_t *pv = NULL;
6633 while(i) {
6634 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
6636 g_assert(tv);
6638 if(tv && pv && !(tv->flags & VERTEX_FLAG_ROUTE) && !(pv->flags & VERTEX_FLAG_ROUTE)) {
6639 toporouter_edge_t *e = TOPOROUTER_EDGE(gts_vertices_are_connected(GTS_VERTEX(tv), GTS_VERTEX(pv)));
6641 if(e && (e->flags & EDGE_FLAG_DIRECTCONNECTION)) {
6642 e->flags ^= EDGE_FLAG_DIRECTCONNECTION;
6645 pv = tv;
6646 i = i->next;
6649 i = routedata->path;
6650 while(i) {
6651 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
6653 tv->parent = NULL;
6654 tv->child = NULL;
6656 if(tv->routingedge) {
6657 if(TOPOROUTER_IS_CONSTRAINT(tv->routingedge))
6658 TOPOROUTER_CONSTRAINT(tv->routingedge)->routing = g_list_remove(TOPOROUTER_CONSTRAINT(tv->routingedge)->routing, tv);
6659 else
6660 tv->routingedge->routing = g_list_remove(tv->routingedge->routing, tv);
6661 if(destroy) gts_object_destroy ( GTS_OBJECT(tv) );
6664 i = i->next;
6667 if(routedata->path) g_list_free(routedata->path);
6668 routedata->path = NULL;
6669 routedata->curpoint = NULL;
6670 routedata->score = INFINITY;
6671 routedata->alltemppoints = NULL;
6674 /* remove route can be later reapplied */
6675 void
6676 remove_route(GList *path)
6678 GList *i = path;
6680 while(i) {
6681 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
6683 tv->parent = NULL;
6684 tv->child = NULL;
6686 // if(tv->flags & VERTEX_FLAG_ROUTE) g_assert(tv->route == routedata);
6688 if(tv->routingedge) {
6690 if(TOPOROUTER_IS_CONSTRAINT(tv->routingedge))
6691 TOPOROUTER_CONSTRAINT(tv->routingedge)->routing = g_list_remove(TOPOROUTER_CONSTRAINT(tv->routingedge)->routing, tv);
6692 else
6693 tv->routingedge->routing = g_list_remove(tv->routingedge->routing, tv);
6695 i = i->next;
6700 gint
6701 apply_route(GList *path, toporouter_route_t *routedata)
6703 GList *i = path;
6704 toporouter_vertex_t *pv = NULL;
6705 gint count = 0;
6707 if(!path) return 0;
6708 // g_assert(path);
6710 while(i) {
6711 toporouter_vertex_t *tv = TOPOROUTER_VERTEX(i->data);
6713 if(tv->routingedge) {
6714 if(TOPOROUTER_IS_CONSTRAINT(tv->routingedge))
6715 TOPOROUTER_CONSTRAINT(tv->routingedge)->routing = g_list_insert_sorted_with_data(
6716 TOPOROUTER_CONSTRAINT(tv->routingedge)->routing,
6717 tv,
6718 routing_edge_insert,
6719 tv->routingedge);
6720 else
6721 tv->routingedge->routing = g_list_insert_sorted_with_data(
6722 tv->routingedge->routing,
6723 tv,
6724 routing_edge_insert,
6725 tv->routingedge);
6727 count++;
6730 if(pv) {
6731 pv->child = tv;
6732 tv->parent = pv;
6735 if(tv->flags & VERTEX_FLAG_ROUTE) g_assert(tv->route == routedata);
6737 pv = tv;
6738 i = i->next;
6741 TOPOROUTER_VERTEX(path->data)->parent = NULL;
6742 pv->child = NULL;
6744 return count;
6748 gint
6749 compare_routedata_ascending(gconstpointer a, gconstpointer b)
6751 toporouter_route_t *ra = (toporouter_route_t *)a;
6752 toporouter_route_t *rb = (toporouter_route_t *)b;
6753 return ra->score - rb->score;
6756 void
6757 print_costmatrix(gdouble *m, guint n)
6759 printf("COST MATRIX:\n");
6760 for(guint i = 0;i<n;i++) {
6761 for(guint j = 0;j<n;j++) {
6762 printf("%f ", m[(i*n)+j]);
6764 printf("\n");
6769 inline void
6770 init_cost_matrix(gdouble *m, guint n)
6772 for(guint i=0;i<n;i++) {
6773 for(guint j=0;j<n;j++) {
6774 m[(i*n)+j] = INFINITY;
6780 toporouter_netscore_t *
6781 netscore_create(toporouter_t *r, toporouter_route_t *routedata, guint n, guint id)
6783 toporouter_netscore_t *netscore = malloc(sizeof(toporouter_netscore_t));
6784 GList *path = route(r, routedata, 0);
6786 netscore->id = id;
6788 netscore->routedata = routedata;
6789 routedata->detourscore = netscore->score = routedata->score;
6791 if(!finite(routedata->detourscore)) {
6792 printf("WARNING: !finite(detourscore)\n");
6793 print_cluster(routedata->src);
6794 print_cluster(routedata->dest);
6798 netscore->pairwise_nodetour = malloc(n * sizeof(guint));
6800 for(guint i=0;i<n;i++) {
6801 netscore->pairwise_nodetour[i] = 0;
6804 netscore->pairwise_detour_sum = 0.;
6805 netscore->pairwise_fails = 0;
6807 netscore->r = r;
6809 if(path) {
6810 routedata->topopath = g_list_copy(routedata->path);
6811 delete_route(routedata, 0);
6814 return netscore;
6817 inline void
6818 netscore_destroy(toporouter_netscore_t *netscore)
6820 free(netscore->pairwise_nodetour);
6821 free(netscore);
6824 void
6825 print_netscores(GPtrArray* netscores)
6827 printf("NETSCORES: \n\n");
6828 printf(" %15s %15s %15s\n----------------------------------------------------\n", "Score", "Detour Sum", "Pairwise Fails");
6830 for(toporouter_netscore_t **i = (toporouter_netscore_t **) netscores->pdata; i < (toporouter_netscore_t **) netscores->pdata + netscores->len; i++) {
6831 printf("%4d %15f %15f %15d %15x\n", (*i)->id, (*i)->score, (*i)->pairwise_detour_sum, (*i)->pairwise_fails, (unsigned int)*i);
6833 printf("\n");
6836 void
6837 netscore_pairwise_calculation(toporouter_netscore_t *netscore, GPtrArray *netscores)
6839 toporouter_netscore_t **netscores_base = (toporouter_netscore_t **) (netscores->pdata);
6840 toporouter_route_t *temproutedata = routedata_create();
6842 //route(netscore->r, netscore->routedata, 0);
6843 apply_route(netscore->routedata->topopath, netscore->routedata);
6845 for(toporouter_netscore_t **i = netscores_base; i < netscores_base + netscores->len; i++) {
6847 if(!netscore->pairwise_nodetour[i-netscores_base] && *i != netscore && (*i)->routedata->netlist != netscore->routedata->netlist) {
6849 temproutedata->src = (*i)->routedata->src;
6850 temproutedata->dest = (*i)->routedata->dest;
6852 route(netscore->r, temproutedata, 0);
6854 if(temproutedata->score == (*i)->score) {
6855 netscore->pairwise_nodetour[i-netscores_base] = 1;
6856 (*i)->pairwise_nodetour[netscore->id] = 1;
6857 }else
6858 if(!finite(temproutedata->score)) {
6859 netscore->pairwise_fails += 1;
6860 }else{
6861 netscore->pairwise_detour_sum += temproutedata->score - (*i)->score;
6864 delete_route(temproutedata, 1);
6869 // delete_route(netscore->routedata, 1);
6870 remove_route(netscore->routedata->topopath);
6872 free(temproutedata);
6875 gint
6876 netscore_pairwise_size_compare(toporouter_netscore_t **a, toporouter_netscore_t **b)
6878 // infinite scores are last
6879 if(!finite((*a)->score) && !finite((*b)->score)) return 0;
6880 if(finite((*a)->score) && !finite((*b)->score)) return -1;
6881 if(finite((*b)->score) && !finite((*a)->score)) return 1;
6883 // order by pairwise fails
6884 if((*a)->pairwise_fails < (*b)->pairwise_fails) return -1;
6885 if((*b)->pairwise_fails < (*a)->pairwise_fails) return 1;
6887 // order by pairwise detour
6888 if((*a)->pairwise_detour_sum < (*b)->pairwise_detour_sum) return -1;
6889 if((*b)->pairwise_detour_sum < (*a)->pairwise_detour_sum) return 1;
6891 // order by score
6892 if((*a)->score < (*b)->score) return -1;
6893 if((*b)->score < (*a)->score) return 1;
6895 return 0;
6898 gint
6899 netscore_pairwise_compare(toporouter_netscore_t **a, toporouter_netscore_t **b)
6901 // infinite scores are last
6902 if(!finite((*a)->score) && !finite((*b)->score)) return 0;
6903 if(finite((*a)->score) && !finite((*b)->score)) return -1;
6904 if(finite((*b)->score) && !finite((*a)->score)) return 1;
6906 // order by pairwise fails
6907 if((*a)->pairwise_fails < (*b)->pairwise_fails) return -1;
6908 if((*b)->pairwise_fails < (*a)->pairwise_fails) return 1;
6910 // order by pairwise detour
6911 if((*a)->pairwise_detour_sum < (*b)->pairwise_detour_sum) return -1;
6912 if((*b)->pairwise_detour_sum < (*a)->pairwise_detour_sum) return 1;
6914 return 0;
6917 guint
6918 order_nets_preroute_greedy(toporouter_t *r, GList *nets, GList **rnets)
6920 gint len = g_list_length(nets);
6921 GPtrArray* netscores = g_ptr_array_sized_new(len);
6922 guint failcount = 0;
6924 while(nets) {
6925 g_ptr_array_add(netscores, netscore_create(r, TOPOROUTER_ROUTE(nets->data), len, failcount++));
6926 nets = nets->next;
6929 failcount = 0;
6931 g_ptr_array_foreach(netscores, (GFunc) netscore_pairwise_calculation, netscores);
6933 g_ptr_array_sort(netscores, (GCompareFunc) r->netsort);
6935 #ifdef DEBUG_ORDERING
6936 print_netscores(netscores);
6937 #endif
6939 *rnets = NULL;
6940 FOREACH_NETSCORE(netscores) {
6941 *rnets = g_list_prepend(*rnets, netscore->routedata);
6942 if(!finite(netscore->score)) failcount++;
6943 netscore_destroy(netscore);
6944 } FOREACH_END;
6946 g_ptr_array_free(netscores, TRUE);
6948 return failcount;
6951 toporouter_vertex_t *
6952 edge_closest_vertex(toporouter_edge_t *e, toporouter_vertex_t *v)
6954 GList *i = v->routingedge ? edge_routing(v->routingedge) : NULL;
6955 gdouble closestd = 0.;
6956 toporouter_vertex_t *closestv = NULL;
6958 while(i) {
6959 toporouter_vertex_t *ev = TOPOROUTER_VERTEX(i->data);
6960 gdouble tempd = gts_point_distance2(GTS_POINT(ev), GTS_POINT(v));
6962 if(!closestv || (tempd < closestd)) {
6963 closestd = tempd;
6964 closestv = ev;
6967 i = i->next;
6970 return closestv;
6973 void
6974 snapshot(toporouter_t *r, char *name, GList *datas)
6976 ///*
6978 int i;
6979 for(i=0;i<groupcount();i++) {
6980 char buffer[256];
6981 sprintf(buffer, "route-%s-%d.png", name, i);
6982 toporouter_draw_surface(r, r->layers[i].surface, buffer, 2048, 2048, 2, datas, i, NULL);
6985 //*/
6989 gdouble
6990 route_conflict(toporouter_t *r, toporouter_route_t *route, guint *n)
6992 GList *i = route->path;
6993 toporouter_vertex_t *pv = NULL;
6994 gdouble cost = 0.;
6996 while(i) {
6997 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
6998 if(pv && vz(v) == vz(pv))
6999 cost += vertices_routing_conflict_cost(r, v, pv, n);
7000 pv = v;
7001 i = i->next;
7004 return cost;
7007 GList *
7008 route_conflicts(toporouter_route_t *route)
7010 GList *conflicts = NULL, *i = route->path;
7011 toporouter_vertex_t *pv = NULL;
7013 while(i) {
7014 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
7016 if(pv && vz(pv) == vz(v)) {
7017 GList *temp = vertices_routing_conflicts(pv, v), *j;
7019 j = temp;
7020 while(j) {
7021 toporouter_route_t *conroute = TOPOROUTER_ROUTE(j->data);
7022 if(!g_list_find(conflicts, conroute))
7023 conflicts = g_list_prepend(conflicts, conroute);
7024 j = j->next;
7027 if(temp) g_list_free(temp);
7030 pv = v;
7031 i = i->next;
7033 return conflicts;
7036 gint
7037 spread_edge(gpointer item, gpointer data)
7039 toporouter_edge_t *e = TOPOROUTER_EDGE(item);
7040 toporouter_vertex_t *v;
7041 gdouble spacing, s;
7042 GList *i;
7044 if(TOPOROUTER_IS_CONSTRAINT(e)) return 0;
7046 i = edge_routing(e);
7048 if(!g_list_length(i)) return 0;
7050 if(g_list_length(i) == 1) {
7051 v = TOPOROUTER_VERTEX(i->data);
7052 GTS_POINT(v)->x = (vx(edge_v1(e)) + vx(edge_v2(e))) / 2.;
7053 GTS_POINT(v)->y = (vy(edge_v1(e)) + vy(edge_v2(e))) / 2.;
7054 return 0;
7057 s = spacing = (gts_point_distance(GTS_POINT(edge_v1(e)), GTS_POINT(edge_v2(e))) ) / (g_list_length(i) + 1);
7059 while(i) {
7060 v = TOPOROUTER_VERTEX(i->data);
7061 vertex_move_towards_vertex_values(edge_v1(e), edge_v2(e), s, &(GTS_POINT(v)->x), &(GTS_POINT(v)->y));
7063 s += spacing;
7064 i = i->next;
7067 return 0;
7070 void
7071 route_checkpoint(toporouter_route_t *route, toporouter_route_t *temproute)
7073 GList *i = g_list_last(route->path);
7074 gint n = g_list_length(route->path);
7076 if(route->ppathindices) free(route->ppathindices);
7077 route->ppathindices = malloc(sizeof(gint)*n);
7079 // n = 0;
7080 while(i) {
7081 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
7082 n--;
7084 if(v->routingedge) {
7085 GList *j = g_list_find(edge_routing(v->routingedge), v)->prev;
7086 gint tempindex = g_list_index(edge_routing(v->routingedge), v);
7088 while(j) {
7089 if(TOPOROUTER_VERTEX(j->data)->route == temproute) tempindex--;
7090 j = j->prev;
7093 route->ppathindices[n] = tempindex;
7095 if(TOPOROUTER_IS_CONSTRAINT(v->routingedge))
7096 TOPOROUTER_CONSTRAINT(v->routingedge)->routing = g_list_remove(TOPOROUTER_CONSTRAINT(v->routingedge)->routing, v);
7097 else
7098 v->routingedge->routing = g_list_remove(v->routingedge->routing, v);
7101 i = i->prev;
7104 route->pscore = route->score;
7105 route->ppath = route->path;
7106 remove_route(route->path);
7107 route->path = NULL;
7108 route->psrc = route->src;
7109 route->pdest = route->dest;
7110 //route->src->pc = route->src->c;
7111 //route->dest->pc = route->dest->c;
7114 void
7115 route_restore(toporouter_route_t *route)
7117 GList *i;
7118 toporouter_vertex_t *pv = NULL;
7119 gint n = 0;
7121 g_assert(route->ppath);
7122 g_assert(route->ppathindices);
7124 route->path = route->ppath;
7125 i = route->ppath;
7126 while(i) {
7127 toporouter_vertex_t *v = TOPOROUTER_VERTEX(i->data);
7129 if(v->routingedge) {
7130 if(TOPOROUTER_IS_CONSTRAINT(v->routingedge))
7131 TOPOROUTER_CONSTRAINT(v->routingedge)->routing = g_list_insert(TOPOROUTER_CONSTRAINT(v->routingedge)->routing, v, route->ppathindices[n]);
7132 else
7133 v->routingedge->routing = g_list_insert(v->routingedge->routing, v, route->ppathindices[n]);
7135 // space_edge(v->routingedge, NULL);
7138 if(pv) {
7139 pv->child = v;
7140 v->parent = pv;
7143 n++;
7144 pv = v;
7145 i = i->next;
7148 route->score = route->pscore;
7149 route->src = route->psrc;
7150 route->dest = route->pdest;
7151 //route->src->c = route->src->pc;
7152 //route->dest->c = route->dest->pc;
7156 void
7157 cluster_merge(toporouter_route_t *routedata)
7159 gint oldc = routedata->dest->c, newc = routedata->src->c;
7161 FOREACH_CLUSTER(routedata->netlist->clusters) {
7162 if(cluster->c == oldc)
7163 cluster->c = newc;
7164 } FOREACH_END;
7168 void
7169 netlist_recalculate(toporouter_netlist_t *netlist, GList *ignore)
7171 GList *i = g_list_last(netlist->routed);
7172 gint n = netlist->clusters->len-1;
7174 FOREACH_CLUSTER(netlist->clusters) {
7175 cluster->c = n--;
7176 } FOREACH_END;
7178 while(i) {
7179 if(!ignore || !g_list_find(ignore, i->data)) cluster_merge(TOPOROUTER_ROUTE(i->data));
7180 i = i->prev;
7185 void
7186 netlists_recalculate(GList *netlists, GList *ignore)
7188 GList *i = netlists;
7189 while(i) {
7190 netlist_recalculate(TOPOROUTER_NETLIST(i->data), ignore);
7191 i = i->next;
7195 void
7196 netlists_rollback(GList *netlists)
7198 // netlists_recalculate(netlists, NULL);
7199 while(netlists) {
7200 toporouter_netlist_t *netlist = TOPOROUTER_NETLIST(netlists->data);
7202 FOREACH_CLUSTER(netlist->clusters) {
7203 cluster->c = cluster->pc;
7204 } FOREACH_END;
7206 netlists = netlists->next;
7210 void
7211 print_netlist(toporouter_netlist_t *netlist)
7214 printf("NETLIST %s: ", netlist->netlist);
7216 FOREACH_CLUSTER(netlist->clusters) {
7217 printf("%d ", cluster->c);
7219 } FOREACH_END;
7220 printf("\n");
7223 #define REMOVE_ROUTING(x) x->netlist->routed = g_list_remove(x->netlist->routed, x); \
7224 r->routednets = g_list_remove(r->routednets, x); \
7225 r->failednets = g_list_prepend(r->failednets, x)
7227 #define INSERT_ROUTING(x) x->netlist->routed = g_list_prepend(x->netlist->routed, x); \
7228 r->routednets = g_list_prepend(r->routednets, x); \
7229 r->failednets = g_list_remove(r->failednets, x)
7231 gint
7232 roar_route(toporouter_t *r, toporouter_route_t *routedata, gint threshold)
7234 gint intfails = 0;
7235 GList *netlists = NULL, *routed = NULL;
7237 g_assert(!routedata->path);
7239 if(routedata->src->c == routedata->dest->c) {
7240 printf("ERROR: attempt to route already complete route\n");
7241 g_assert(routedata->src->c != routedata->dest->c);
7244 routedata->src->pc = routedata->src->c;
7245 routedata->dest->pc = routedata->dest->c;
7246 routedata->psrc = routedata->src;
7247 routedata->pdest = routedata->dest;
7249 r->flags |= TOPOROUTER_FLAG_LEASTINVALID;
7250 if(route(r, routedata, 0)) {
7251 GList *conflicts, *j;
7253 INSERT_ROUTING(routedata);
7255 conflicts = route_conflicts(routedata);
7256 cluster_merge(routedata);
7258 r->flags &= ~TOPOROUTER_FLAG_LEASTINVALID;
7260 j = conflicts;
7261 while(j) {
7262 toporouter_route_t *conflict = TOPOROUTER_ROUTE(j->data);
7263 if(!g_list_find(netlists, conflict->netlist))
7264 netlists = g_list_prepend(netlists, conflict->netlist);
7266 route_checkpoint(conflict, routedata);
7268 REMOVE_ROUTING(conflict);
7269 j = j->next;
7272 netlists = g_list_prepend(netlists, routedata->netlist);
7273 netlists_recalculate(netlists, NULL);
7275 j = conflicts;
7276 while(j) {
7277 toporouter_route_t *conflict = TOPOROUTER_ROUTE(j->data);
7278 g_assert(conflict->src->c != conflict->dest->c);
7279 if(route(r, conflict, 0)) {
7280 cluster_merge(conflict);
7282 routed = g_list_prepend(routed, conflict);
7284 INSERT_ROUTING(conflict);
7286 netlist_recalculate(conflict->netlist, NULL);
7288 }else{
7289 if(++intfails >= threshold) {
7290 GList *i = routed;
7291 while(i) {
7292 toporouter_route_t *intconflict = TOPOROUTER_ROUTE(i->data);
7293 REMOVE_ROUTING(intconflict);
7294 delete_route(intconflict, 1);
7295 i = i->next;
7297 delete_route(routedata, 1);
7298 i = g_list_last(conflicts);
7299 while(i) {
7300 toporouter_route_t *intconflict = TOPOROUTER_ROUTE(i->data);
7302 route_restore(intconflict);
7303 INSERT_ROUTING(intconflict);
7305 i = i->prev;
7307 REMOVE_ROUTING(routedata);
7308 intfails = 0;
7309 netlists_recalculate(netlists, NULL);
7310 goto roar_route_end;
7314 j = j->next;
7318 netlists_recalculate(netlists, NULL);
7320 intfails--;
7321 roar_route_end:
7322 g_list_free(conflicts);
7323 g_list_free(netlists);
7325 }else{
7326 r->flags &= ~TOPOROUTER_FLAG_LEASTINVALID;
7329 g_list_free(routed);
7330 return intfails;
7333 gint
7334 roar_router(toporouter_t *r, gint failcount, gint threshold)
7336 gint pfailcount = failcount +1;
7338 Message(_("ROAR router: "));
7339 for(guint j=0;j<6;j++) {
7340 GList *failed = g_list_copy(r->failednets), *k = failed;
7342 k = failed;
7343 while(k) {
7344 failcount += roar_route(r, TOPOROUTER_ROUTE(k->data), threshold);
7345 k = k->next;
7347 g_list_free(failed);
7349 printf("\tROAR pass %d - %d routed - %d failed\n", j, g_list_length(r->routednets), g_list_length(r->failednets));
7351 if(!failcount || failcount >= pfailcount) {
7352 Message(_("%d nets remaining\n"), failcount);
7353 break;
7355 Message(_("%d -> "), failcount);
7356 pfailcount = failcount;
7359 return failcount;
7362 gint
7363 route_detour_compare(toporouter_route_t **a, toporouter_route_t **b)
7364 { return ((*b)->score - (*b)->detourscore) - ((*a)->score - (*a)->detourscore); }
7368 void
7369 roar_detour_route(toporouter_t *r, toporouter_route_t *data)
7371 gdouble pscore = data->score, nscore = 0.;
7372 GList *netlists = NULL;
7374 route_checkpoint(data, NULL);
7376 REMOVE_ROUTING(data);
7378 netlists = g_list_prepend(NULL, data->netlist);
7379 netlists_recalculate(netlists, NULL);
7381 r->flags |= TOPOROUTER_FLAG_LEASTINVALID;
7382 if(route(r, data, 0)) {
7383 GList *conflicts, *j;
7385 nscore = data->score;
7386 conflicts = route_conflicts(data);
7388 INSERT_ROUTING(data);
7390 r->flags &= ~TOPOROUTER_FLAG_LEASTINVALID;
7392 j = conflicts;
7393 while(j) {
7394 toporouter_route_t *conflict = TOPOROUTER_ROUTE(j->data);
7396 if(!g_list_find(netlists, conflict->netlist))
7397 netlists = g_list_prepend(netlists, conflict->netlist);
7398 pscore += conflict->score;
7400 route_checkpoint(conflict, NULL);
7401 REMOVE_ROUTING(conflict);
7403 j = j->next;
7405 netlists_recalculate(netlists, NULL);
7407 j = conflicts;
7408 while(j) {
7409 toporouter_route_t *conflict = TOPOROUTER_ROUTE(j->data);
7411 if(route(r, conflict, 0)) {
7412 cluster_merge(conflict);
7413 INSERT_ROUTING(conflict);
7414 nscore += conflict->score;
7415 }else{
7416 j = j->prev;
7417 goto roar_detour_route_rollback_int;
7419 j = j->next;
7422 if(nscore > pscore) {
7423 j = g_list_last(conflicts);
7424 roar_detour_route_rollback_int:
7425 REMOVE_ROUTING(data);
7427 while(j) {
7428 toporouter_route_t *conflict = TOPOROUTER_ROUTE(j->data);
7429 REMOVE_ROUTING(conflict);
7430 delete_route(conflict, 1);
7431 j = j->prev;
7434 j = g_list_last(conflicts);
7435 while(j) {
7436 toporouter_route_t *conflict = TOPOROUTER_ROUTE(j->data);
7437 route_restore(conflict);
7438 INSERT_ROUTING(conflict);
7439 j = j->prev;
7441 delete_route(data, 1);
7443 goto roar_detour_route_rollback_exit;
7447 g_list_free(conflicts);
7448 }else{
7449 r->flags &= ~TOPOROUTER_FLAG_LEASTINVALID;
7450 roar_detour_route_rollback_exit:
7451 route_restore(data);
7452 INSERT_ROUTING(data);
7454 netlists_recalculate(netlists, NULL);
7456 g_list_free(netlists);
7459 void
7460 detour_router(toporouter_t *r)
7462 GList *i = r->routednets;
7463 guint n = g_list_length(r->routednets);
7464 GPtrArray* scores = g_ptr_array_sized_new(n);
7466 while(i) {
7467 toporouter_route_t *curroute = TOPOROUTER_ROUTE(i->data);
7468 curroute->score = path_score(r, curroute->path);
7469 g_ptr_array_add(scores, i->data);
7470 i = i->next;
7473 g_ptr_array_sort(scores, (GCompareFunc) route_detour_compare);
7475 r->flags |= TOPOROUTER_FLAG_DETOUR;
7477 for(toporouter_route_t **i = (toporouter_route_t **) scores->pdata; i < (toporouter_route_t **) scores->pdata + scores->len; i++) {
7478 toporouter_route_t *curroute = (*i);
7480 if(finite(curroute->score) && finite(curroute->detourscore)) {
7481 // printf("%15s %15f \t %8f,%8f - %8f,%8f\n", (*i)->src->netlist + 2, (*i)->score - (*i)->detourscore,
7482 // vx(curroute->mergebox1->point), vy(curroute->mergebox1->point),
7483 // vx(curroute->mergebox2->point), vy(curroute->mergebox2->point));
7485 if(curroute->score - curroute->detourscore > 1000.) {
7486 roar_detour_route(r, curroute);
7487 }else break;
7491 printf("\n");
7493 r->flags ^= TOPOROUTER_FLAG_DETOUR;
7495 g_ptr_array_free(scores, TRUE);
7499 gint
7500 rubix_router(toporouter_t *r, gint failcount)
7502 GList *i, *ordering;
7503 order_nets_preroute_greedy(r, r->failednets, &ordering);
7505 i = ordering;
7506 while(i) {
7507 toporouter_route_t *data = TOPOROUTER_ROUTE(i->data);
7509 if(route(r, data, 0)) {
7510 INSERT_ROUTING(data);
7511 cluster_merge(data);
7512 failcount--;
7515 i = i->next;
7518 g_list_free(ordering);
7520 return failcount;
7523 guint
7524 hybrid_router(toporouter_t *r)
7526 gint failcount = g_list_length(r->failednets);
7527 r->flags |= TOPOROUTER_FLAG_AFTERORDER;
7528 r->flags |= TOPOROUTER_FLAG_AFTERRUBIX;
7529 failcount = rubix_router(r, failcount);
7531 Message(_("RUBIX router: %d nets remaining\n"), failcount);
7532 printf("RUBIX router: %d nets remaining\n", failcount);
7534 r->flags |= TOPOROUTER_FLAG_GOFAR;
7536 for(guint i=0;i<6 && failcount;i++) {
7537 if(i % 2 == 1) {
7538 failcount = roar_router(r, failcount, 5);
7539 // printf("THRESH 5\n");
7540 }else{
7541 failcount = roar_router(r, failcount, 2);
7542 // printf("THRESH 2\n");
7545 detour_router(r);
7548 failcount = roar_router(r, failcount, 2);
7549 detour_router(r);
7551 return failcount;
7554 void
7555 parse_arguments(toporouter_t *r, int argc, char **argv)
7557 int i, tempint;
7558 for(i=0;i<argc;i++) {
7559 if(sscanf(argv[i], "viacost=%d", &tempint)) {
7560 r->viacost = (double)tempint;
7561 }else if(sscanf(argv[i], "l%d", &tempint)) {
7562 gdouble *layer = malloc(sizeof(gdouble));
7563 *layer = (double)tempint;
7564 r->keepoutlayers = g_list_prepend(r->keepoutlayers, layer);
7568 for (guint group = 0; group < max_layer; group++)
7569 for (i = 0; i < PCB->LayerGroups.Number[group]; i++)
7570 if ((PCB->LayerGroups.Entries[group][i] < max_layer) && !(PCB->Data->Layer[PCB->LayerGroups.Entries[group][i]].On)) {
7571 gdouble *layer = malloc(sizeof(gdouble));
7572 *layer = (double)group;
7573 r->keepoutlayers = g_list_prepend(r->keepoutlayers, layer);
7578 toporouter_t *
7579 toporouter_new(void)
7581 toporouter_t *r = calloc(1, sizeof(toporouter_t));
7582 time_t ltime;
7584 gettimeofday(&r->starttime, NULL);
7586 r->netsort = netscore_pairwise_compare;
7588 r->destboxes = NULL;
7589 r->consumeddestboxes = NULL;
7591 r->paths = NULL;
7593 r->layers = NULL;
7594 r->flags = 0;
7595 r->viamax = 3;
7596 r->viacost = 10000.;
7597 r->stublength = 300.;
7598 r->serpintine_half_amplitude = 1500.;
7600 r->wiring_score = 0.;
7602 r->bboxes = NULL;
7603 r->bboxtree = NULL;
7605 r->netlists = g_ptr_array_new();
7606 r->routes = g_ptr_array_new();
7608 r->keepoutlayers = NULL;
7610 r->routednets = NULL;
7611 r->failednets = NULL;
7613 ltime=time(NULL);
7615 gts_predicates_init();
7617 Message(_("Topological Autorouter\n"));
7618 Message(_("Started %s"),asctime(localtime(&ltime)));
7619 Message(_("-------------------------------------\n"));
7620 Message(_("Copyright 2009 Anthony Blake (tonyb33@gmail.com)\n\n"));
7621 return r;
7624 void
7625 acquire_twonets(toporouter_t *r)
7627 RAT_LOOP(PCB->Data);
7628 if( TEST_FLAG(SELECTEDFLAG, line) ) import_route(r, line);
7629 END_LOOP;
7630 // /*
7631 if(!r->routes->len) {
7632 RAT_LOOP(PCB->Data);
7633 import_route(r, line);
7634 END_LOOP;
7636 // */
7640 toporouter_netlist_t *
7641 find_netlist_by_name(toporouter_t *r, char *name)
7643 FOREACH_NETLIST(r->netlists) {
7644 if(!strcmp(netlist->netlist, name)) return netlist;
7645 } FOREACH_END;
7646 return NULL;
7649 gint
7650 toporouter_set_pair(toporouter_t *r, toporouter_netlist_t *n1, toporouter_netlist_t *n2)
7652 if(!n1 || !n2) return 0;
7653 n1->pair = n2;
7654 n2->pair = n1;
7655 return 1;
7658 static int
7659 toporouter (int argc, char **argv, int x, int y)
7661 toporouter_t *r = toporouter_new();
7662 parse_arguments(r, argc, argv);
7663 import_geometry(r);
7664 acquire_twonets(r);
7666 //if(!toporouter_set_pair(r, find_netlist_by_name(r, " DRAM_DQS_N"), find_netlist_by_name(r, " DRAM_DQS"))) {
7667 // printf("Couldn't associate pair\n");
7670 hybrid_router(r);
7672 // for(gint i=0;i<groupcount();i++) {
7673 // gts_surface_foreach_edge(r->layers[i].surface, space_edge, NULL);
7674 // }
7676 int i;
7677 for(i=0;i<groupcount();i++) {
7678 char buffer[256];
7679 sprintf(buffer, "route%d.png", i);
7680 toporouter_draw_surface(r, r->layers[i].surface, buffer, 1024, 1024, 2, NULL, i, NULL);
7684 toporouter_export(r);
7685 toporouter_free(r);
7687 SaveUndoSerialNumber ();
7688 DeleteRats (False);
7689 RestoreUndoSerialNumber ();
7690 AddAllRats (False, NULL);
7691 RestoreUndoSerialNumber ();
7692 IncrementUndoSerialNumber ();
7693 ClearAndRedrawOutput ();
7695 return 0;
7698 static int
7699 escape (int argc, char **argv, int x, int y)
7701 guint dir, viax, viay;
7702 gdouble pitch, length, dx, dy;
7704 if(argc != 1) return 0;
7706 dir = atoi(argv[0]);
7709 ALLPAD_LOOP(PCB->Data);
7711 if( TEST_FLAG(SELECTEDFLAG, pad) ) {
7712 PinTypePtr via;
7713 LineTypePtr line;
7715 pitch = sqrt( pow(abs(element->Pad[0].Point1.X - element->Pad[1].Point1.X), 2) +
7716 pow(abs(element->Pad[0].Point1.Y - element->Pad[1].Point1.Y), 2) );
7717 length = sqrt(pow(pitch,2) + pow(pitch,2)) / 2.;
7719 dx = length * sin(M_PI/4.);
7720 dy = length * cos(M_PI/4.);
7722 switch(dir) {
7723 case 1:
7724 viax = pad->Point1.X - dx;
7725 viay = pad->Point1.Y + dy;
7726 break;
7727 case 3:
7728 viax = pad->Point1.X + dx;
7729 viay = pad->Point1.Y + dy;
7730 break;
7731 case 9:
7732 viax = pad->Point1.X + dx;
7733 viay = pad->Point1.Y - dy;
7734 break;
7735 case 7:
7736 viax = pad->Point1.X - dx;
7737 viay = pad->Point1.Y - dy;
7738 break;
7739 case 2:
7740 viax = pad->Point1.X;
7741 viay = pad->Point1.Y + (pitch/2);
7742 break;
7743 case 8:
7744 viax = pad->Point1.X;
7745 viay = pad->Point1.Y - (pitch/2);
7746 break;
7747 case 4:
7748 viax = pad->Point1.X - (pitch/2);
7749 viay = pad->Point1.Y;
7750 break;
7751 case 6:
7752 viax = pad->Point1.X + (pitch/2);
7753 viay = pad->Point1.Y;
7754 break;
7755 default:
7756 printf("ERROR: escape() with bad direction (%d)\n", dir);
7757 return 1;
7760 if ((via = CreateNewVia (PCB->Data, viax, viay,
7761 Settings.ViaThickness, 2 * Settings.Keepaway,
7762 0, Settings.ViaDrillingHole, NULL,
7763 NoFlags ())) != NULL)
7765 AddObjectToCreateUndoList (VIA_TYPE, via, via, via);
7766 // if (gui->shift_is_pressed ())
7767 // ChangeObjectThermal (VIA_TYPE, via, via, via, PCB->ThermStyle);
7768 DrawVia (via, 0);
7769 if((line = CreateDrawnLineOnLayer (CURRENT, pad->Point1.X + 1., pad->Point1.Y + 1., viax + 1., viay + 1.,
7770 Settings.LineThickness, 2 * Settings.Keepaway,
7771 NoFlags())))
7774 AddObjectToCreateUndoList (LINE_TYPE, CURRENT, line, line);
7775 DrawLine (CURRENT, line, 0);
7783 END_LOOP;
7784 END_LOOP;
7786 IncrementUndoSerialNumber ();
7787 Draw ();
7788 return 0;
7791 static HID_Action toporouter_action_list[] = {
7792 {"Escape", "Select a set of pads", escape, "Pad escape", "Escape()"},
7793 {"Toporouter", "Select net(s)", toporouter, "Topological autorouter", "Toporouter()"}
7796 REGISTER_ACTIONS (toporouter_action_list)
7798 void hid_toporouter_init()
7800 register_toporouter_action_list();