Index: src/plugins/rt_topo/laa3_solve.c =================================================================== --- src/plugins/rt_topo/laa3_solve.c (revision 1464) +++ src/plugins/rt_topo/laa3_solve.c (revision 1465) @@ -243,6 +243,53 @@ tn2->br.array[LAA_MAX(tn2->br.used-1, 0)].via = via; } +static void laa3_via_rtree_reg(laa3_t *laa3, rtrnd_rtree_t *rtv, rtrnd_via_t *via) +{ + rtrnd_rtree_insert(rtv, via, &via->hdr.bbox); +} + +static void laa3_via_rtree_unreg(laa3_t *laa3, rtrnd_rtree_t *rtv, rtrnd_via_t *via) +{ + rtrnd_rtree_delete(rtv, via, &via->hdr.bbox); +} + +static int laa3_via_rtree_find(laa3_t *laa3, rtrnd_rtree_t *rtv, rtrnd_via_t *via) +{ + rtrnd_via_t *v; + rtrnd_rtree_it_t it; + + for(v = rtrnd_rtree_first(&it, rtv, &via->hdr.bbox); v != NULL; v = rtrnd_rtree_next(&it)) + if (v != via) + return 2; + + return 0; +} + + +static void laa3_via_rtree_init(laa3_t *laa3, rtrnd_rtree_t *rtv, vtp0_t *vias) +{ + rtrnd_t *ctx = laa3->ctx; + long n; + double bloat; + + /* bloat up via bboxes so via-via placement leaves enough room for a trace */ + bloat = (rt_topo_cfg.wire_thick + rt_topo_cfg.wire_clr) * rt_topo_cfg.via_via_space; + + rtrnd_rtree_init(rtv); + for(n = 0; n < vias->used; n++) { + rtrnd_via_t *via = vias->array[n]; + via->hdr.bbox.x1 -= bloat; via->hdr.bbox.y1 -= bloat; + via->hdr.bbox.x2 += bloat; via->hdr.bbox.y2 += bloat; + laa3_via_rtree_reg(laa3, rtv, via); + } +} + +static void laa3_via_rtree_uninit(laa3_t *laa3, rtrnd_rtree_t *rtv, vtp0_t *vias) +{ + rtrnd_rtree_uninit(rtv); +} + + int laa3_try_place_vias(laa3_t *laa3, vtp0_t *vias) { rtrnd_t *ctx = laa3->ctx; @@ -250,6 +297,7 @@ htsp_entry_t *e; rt_topo_laa_2net_t *tn, *tn1, *tn2; int bi, limit; + rtrnd_rtree_t rtv; /* create vias on steiner points if there's a layer switch */ for(e = htsp_first(&ctx->board->nets); e != NULL; e = htsp_next(&ctx->board->nets, e)) { @@ -314,8 +362,10 @@ } } + laa3_via_rtree_init(laa3, &rtv, vias); + /* resolve via geo collisions by randomly tuning via positions */ - for(limit = 1024; limit > 0; limit--) { + for(limit = 10240; limit > 0; limit--) { int collided = 0; long n; @@ -322,10 +372,20 @@ for(n = 0; n < vias->used; n++) { rtrnd_via_t *via = vias->array[n]; rtrnd_find_t fctx = {0}; + double dx, dy; + int find_inited; - fctx.found_cb = found_stop_cb; - fctx.bloat = rt_topo_cfg.via_clr; - rtrnd_find_from_obj(&fctx, ctx->board, (rtrnd_any_obj_t *)via); + fctx.nfound = laa3_via_rtree_find(laa3, &rtv, via); + + if (fctx.nfound == 0) { + fctx.found_cb = found_stop_cb; + fctx.bloat = rt_topo_cfg.via_clr; + find_inited = 1; + rtrnd_find_from_obj(&fctx, ctx->board, (rtrnd_any_obj_t *)via); + } + else + find_inited = 0; + if (fctx.nfound > 1) { static int mtw_inited; static psr_mtw_t mtw; @@ -334,20 +394,33 @@ psr_mtw_init(&mtw, 37); mtw_inited = 1; } - via->x += psr_mtw_rand01(&mtw) * 0.2 - 0.1; - via->y += psr_mtw_rand01(&mtw) * 0.2 - 0.1; + laa3_via_rtree_unreg(laa3, &rtv, via); + dx = psr_mtw_rand01(&mtw) * 0.2 - 0.1; + dy = psr_mtw_rand01(&mtw) * 0.2 - 0.1; + via->x += dx; + via->y += dy; + via->hdr.bbox.x1 += dx; + via->hdr.bbox.y1 += dy; + via->hdr.bbox.x2 += dx; + via->hdr.bbox.y2 += dy; + laa3_via_rtree_reg(laa3, &rtv, via); collided = 1; } - rtrnd_find_free(&fctx); + + if (find_inited) + rtrnd_find_free(&fctx); } if (!collided) goto done; /* no collision => done */ } printf("Failed to resolve via sites\n"); + laa3_via_rtree_uninit(laa3, &rtv, vias); return -1; done: + laa3_via_rtree_uninit(laa3, &rtv, vias); + /* when ends are tied to vias make sure their coords are updated to via moves */ for(e = htsp_first(&ctx->board->nets); e != NULL; e = htsp_next(&ctx->board->nets, e)) { rtrnd_net_t *net = e->value; Index: src/plugins/rt_topo/rt_topo.c =================================================================== --- src/plugins/rt_topo/rt_topo.c (revision 1464) +++ src/plugins/rt_topo/rt_topo.c (revision 1465) @@ -46,6 +46,7 @@ RTRND_CONF_BOOLEAN("mid_virt", 0, "split long triangulation edges in half by inserting 0 sized virtual points; makes more routes possible but also makes tracks longer with unnecessary curves and detours", &rt_topo_cfg.beta) RTRND_CONF_DOUBLE("max_hop_mult", 1, 0.1, 10000, "when to give up the search for a route on a layer; higher value means give up later", &rt_topo_cfg.max_hop_mult) RTRND_CONF_DOUBLE("junction_penalty", 1, 0.25, 1000, "higher value results in less junctions (Stenier points)", &rt_topo_cfg.junction_penalty) + RTRND_CONF_DOUBLE("via_via_space", 1, 0.1, 10, "higher value makes newly placed vias keep more space between each other so more wires can pass", &rt_topo_cfg.via_via_space) /* RTRND_CONF_BOOLEAN("octilinear", 0, "draw 90 and 45 degree lines", &rt_topo_cfg.octilin)*/ @@ -59,6 +60,7 @@ RTRND_CONF_COORD("via_clr", 0.20, 0.01, 10, "clearance around via copper", &rt_topo_cfg.via_clr) RTRND_CONF_DOUBLE("beta", 50, 0, 100, "via vs. wire length preference; high value = short wires, low value = less vias", &rt_topo_cfg.beta) RTRND_CONF_DOUBLE("junction_penalty", 1, 0.25, 1000, "higher value results in less junctions (Stenier points)", &rt_topo_cfg.junction_penalty) + RTRND_CONF_DOUBLE("via_via_space", 1, 0.1, 10, "higher value makes newly placed vias keep more space between each other so more wires can pass", &rt_topo_cfg.via_via_space) /* RTRND_CONF_BOOLEAN("octilinear", 0, "draw 90 and 45 degree lines", &rt_topo_cfg.octilin)*/ RTRND_CONF_TERMINATE Index: src/plugins/rt_topo/rt_topo.h =================================================================== --- src/plugins/rt_topo/rt_topo.h (revision 1464) +++ src/plugins/rt_topo/rt_topo.h (revision 1465) @@ -18,7 +18,7 @@ /* configured */ double wire_thick, wire_clr, via_dia, via_clr, beta; int octilin, algo, mid_virt; - double max_hop_mult, junction_penalty; + double max_hop_mult, junction_penalty, via_via_space; /* calculated */ double alpha, alpha2;