From 66da2ec430dc20657579eb90289e8e5ff4f5c987 Mon Sep 17 00:00:00 2001 From: Nick Bowler Date: Wed, 14 Apr 2021 21:00:27 -0400 Subject: [PATCH] Fix inconsistent merging of asymmetric hole overlaps. When computing the overlap relation between holes with different sizes, the current search may not find all overlaps in the case where a smaller hole is visited before a larger one, because searching for holes within the radius of the smaller hole could potentially not find the larger one. The search procedure is altered slightly in order to solve this. First, we begin the search by looking at holes in descending tool diameter, to give a known upper bound at each stage. Then we find potential overlaps by finding all holes within this upper bound, and select the results that actually overlap. --- src/slotifier.c | 117 ++++++++++++++++++++++++++++++++++++++---------- tests/simple.at | 62 +++++++++++++++++++++++++ 2 files changed, 155 insertions(+), 24 deletions(-) diff --git a/src/slotifier.c b/src/slotifier.c index 3998926..05ede6b 100644 --- a/src/slotifier.c +++ b/src/slotifier.c @@ -193,15 +193,43 @@ static CNearTreeHandle build_search_tree(gerbv_image_t *drill) return t; } +static gerbv_aperture_type_t tool_type(gerbv_image_t *drill, int aperture) +{ + gerbv_aperture_t *tool = drill->aperture[abs(aperture)]; + + return tool->type; +} + +static double tool_radius(gerbv_image_t *drill, int aperture) +{ + gerbv_aperture_t *tool = drill->aperture[abs(aperture)]; + + /* Half a mil slop to decisively include points on boundary. */ + return tool->parameter[0] / 2.0 + 0.0005; +} + +static int holes_overlap(gerbv_image_t *drill, gerbv_net_t *a, gerbv_net_t *b) +{ + double d = hypot(a->start_x - b->start_x, a->start_y - b->start_y); + + return tool_radius(drill, a->aperture) >= d + || tool_radius(drill, b->aperture) >= d; +} + static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole, CNearTreeHandle t) { - int biggest_tool = hole->aperture; CVectorHandle group, tmp; - gerbv_aperture_t *tool; - int ret = -1; + int biggest_tool, ret = -1; + double biggest_r; size_t i, j; + /* + * Since we consider holes in order of decreasing size, the initial hole + * considered is by definition the biggest one we will find in a group. + */ + biggest_r = tool_radius(drill, (biggest_tool = hole->aperture)); + if (CVectorCreate(&group, sizeof (gerbv_net_t *), 10)) { fprintf(stderr, _("%s: failed to allocate memory\n"), progname); return -1; @@ -221,22 +249,15 @@ static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole, hole->aperture = -hole->aperture; for (i = 0; i < CVectorSize(group); i++) { - double xy[2], dia, r; + double xy[2]; CVectorGetElement(group, &hole, i); - tool = drill->aperture[abs(hole->aperture)]; - assert(tool->type == GERBV_APTYPE_CIRCLE); - - xy[0] = hole->start_x; xy[1] = hole->start_y; - dia = tool->parameter[0]; - - /* Half a mil slop to decisively include points on boundary. */ - r = dia/2 + 0.0005; - if (drill->aperture[biggest_tool]->parameter[0] < dia) - biggest_tool = abs(hole->aperture); + assert(tool_type(drill, hole->aperture) == GERBV_APTYPE_CIRCLE); + assert(tool_radius(drill, hole->aperture) <= biggest_r); - if (CNearTreeFindInSphere(t, r, 0, tmp, xy, 1) != 0) { + xy[0] = hole->start_x; xy[1] = hole->start_y; + if (CNearTreeFindInSphere(t, biggest_r, 0, tmp, xy, 1) != 0) { /* We should always should find at least one hole! */ fprintf(stderr, _("%s: fatal error searching holes\n"), progname); @@ -248,13 +269,18 @@ static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole, * of pointers to its internal copies of pointers * to the objects in the tree. So we need this * double indirection to get the actual hole. */ + gerbv_net_t *newhole; void *p; + CVectorGetElement(tmp, &p, j); - hole = *(void **)p; + newhole = *(void **)p; + + if (newhole->aperture < 0) + continue; /* already visited */ - if (hole->aperture >= 0) { - CVectorAddElement(group, &hole); - hole->aperture = -hole->aperture; + if (holes_overlap(drill, hole, newhole)) { + CVectorAddElement(group, &newhole); + newhole->aperture = -newhole->aperture; } } } @@ -318,10 +344,38 @@ err: return ret; } +/* + * Order two holes by hole diameter. + */ +static gerbv_image_t *hsc_drill_data; +static int hole_size_cmp(const void *a_, const void *b_) +{ + gerbv_net_t * const *a = a_, * const *b = b_; + gerbv_aperture_t *ta, *tb; + + ta = hsc_drill_data->aperture[abs(a[0]->aperture)]; + assert(ta->type == GERBV_APTYPE_CIRCLE); + + tb = hsc_drill_data->aperture[abs(b[0]->aperture)]; + assert(tb->type == GERBV_APTYPE_CIRCLE); + + if (ta->parameter[0] > tb->parameter[0]) + return -1; + if (ta->parameter[0] < tb->parameter[0]) + return 1; + return 0; +} + +static void sort_holes_by_size(gerbv_image_t *drill, CVectorHandle work) +{ + hsc_drill_data = drill; + qsort(work->array, work->size, work->elementsize, hole_size_cmp); +} + static int slotify(gerbv_image_t *drill) { + CVectorHandle holes, work; CNearTreeHandle t; - CVectorHandle holes; int ret = 0; size_t i; @@ -334,18 +388,32 @@ static int slotify(gerbv_image_t *drill) CNearTreeObjects(t, &holes); if (!holes) - goto out; + goto err_free_tree; - for (i = 0; i < CVectorSize(holes); i++) { + if (CVectorCreate(&work, sizeof (gerbv_net_t *), CVectorSize(holes))) { + fprintf(stderr, _("%s: failed to allocate memory\n"), progname); + goto err_free_tree; + } + + memcpy(work->array, holes->array, holes->size * holes->elementsize); + work->size = holes->size; + sort_holes_by_size(drill, work); + + for (i = 0; i < CVectorSize(work); i++) { gerbv_net_t *hole; - CVectorGetElement(holes, &hole, i); + CVectorGetElement(work, &hole, i); /* Skip holes we've already looked at */ if (hole->aperture < 0) continue; if (hole->aperture_state == GERBV_APERTURE_STATE_ON) continue; + if (verbose > 1) { + fprintf(stderr, _("%s: checking hole at (%.4f,%.4f) for overlaps\n"), + progname, hole->start_x, hole->start_y); + } + if (combine_holes(drill, hole, t) < 0) { ret = -1; break; @@ -361,7 +429,8 @@ static int slotify(gerbv_image_t *drill) gerbv_image_delete_net(hole); } -out: + CVectorFree(&work); +err_free_tree: CNearTreeFree(&t); return ret; } diff --git a/tests/simple.at b/tests/simple.at index 11c59b7..748a4bf 100644 --- a/tests/simple.at +++ b/tests/simple.at @@ -110,3 +110,65 @@ M30 ]]) AT_CLEANUP + +AT_SETUP([asymmetric overlap]) + +AT_DATA([test.cnc], +[[M48 +INCH +T25C0.025 +T24C0.050 +% +T25 +X010200Y010000 +X010300Y010000 +T24 +X010000Y010000 +M30 +]]) + +AT_CHECK([slotifier test.cnc], [0], +[[M48 +INCH,TZ +T10C0.050 +T11C0.025 +% +T10 +X010000Y010000G85X010300Y010000 +T11 +M30 + +]]) + +AT_CLEANUP + +AT_SETUP([asymmetric overlap #2]) + +AT_DATA([test.cnc], +[[M48 +INCH +T25C0.030 +T24C0.100 +% +T25 +X010400Y010250 +T24 +X010800Y010000 +X010000Y010000 +M30 +]]) + +AT_CHECK([slotifier test.cnc], [0], +[[M48 +INCH,TZ +T10C0.100 +T11C0.030 +% +T10 +X010800Y010000G85X010000Y010000 +T11 +M30 + +]]) + +AT_CLEANUP -- 2.43.2