Date:2012-03-18 17:16:26 (12 years 10 days ago)
Author:Werner Almesberger
Commit:2530a11c80b7818e30a19fe52fe7a61dc3508690
Message:cameo: an attempt at area fill (WIP)

Files: cameo/Makefile (2 diffs)
cameo/README (1 diff)
cameo/area.c (1 diff)
cameo/area.h (1 diff)
cameo/lang.l (2 diffs)
cameo/lang.y (4 diffs)

Change Details

cameo/Makefile
11#
22# Makefile - Makefile of cameo
33#
4# Written 2010 by Werner Almesberger
5# Copyright 2010 by Werner Almesberger
4# Written 2010, 2012 by Werner Almesberger
5# Copyright 2010, 2012 by Werner Almesberger
66#
77# This program is free software; you can redistribute it and/or modify
88# it under the terms of the GNU General Public License as published by
...... 
1515SHELL=/bin/bash
1616
1717MAIN=cameo
18OBJS=cameo.o excellon.o gerber.o gnuplot.o ops.o path.o shape.o \
18OBJS=cameo.o excellon.o area.o gerber.o gnuplot.o ops.o path.o shape.o \
1919     lex.yy.o y.tab.o
2020
2121CFLAGS_WARN=-Wall -Wshadow -Wmissing-prototypes \
cameo/README
206206
207207Try to reduce the movements made between paths by reordering the paths.
208208Note that this disturbs the order generated by "offset" and should thus
209not be used on paths that to be executed in a specific sequence.
209not be used on paths that are to be executed in a specific sequence.
210210
211211
212212Statistics:
cameo/area.c
1/*
2 * area.c - Area fill
3 *
4 * Written 2012 by Werner Almesberger
5 * Copyright 2012 Werner Almesberger
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 */
12
13
14#include <stdio.h>
15#include <stddef.h>
16#include <math.h>
17#include <assert.h>
18
19#include "util.h"
20#include "path.h"
21#include "area.h"
22
23
24#define EPSILON 0.0001
25
26
27static int bbox(const struct path *path,
28    double *xa, double *ya, double *xb, double *yb)
29{
30    const struct point *p = path->first;
31
32    if (!p)
33        return 0;
34    *xa = *xb = p->x;
35    *ya = *yb = p->y;
36    while (p) {
37        if (p->x < *xa)
38            *xa = p->x;
39        if (p->x > *xb)
40            *xb = p->x;
41        if (p->y < *ya)
42            *ya = p->y;
43        if (p->y > *yb)
44            *yb = p->y;
45        p = p->next;
46    }
47    return 1;
48}
49
50
51/*
52 * @@@ this is a bit too simple. E.g., it would report A as being inside B
53 * in this case:
54 *
55 * +---+
56 * +---+ | |
57 * | A | | |
58 * +---+ | |
59 * | B |
60 * +--------+ |
61 * | |
62 * +------------+
63 */
64
65static int is_inside(const struct path *a, const struct path *b)
66{
67        double xa, ya, xb, yb;
68    const struct point *p;
69
70    if (!bbox(b, &xa, &ya, &xb, &yb))
71        return 0;
72    for (p = a->first; p; p = p->next)
73        if (p->x < xa || p->x > xb ||
74            p->y < ya || p->y > yb)
75            return 0;
76    return 1;
77}
78
79
80/*
81 * Solve
82 *
83 * ax+na*bx = cx+nb*dx
84 * ay+na*by = cy+nb*dy
85 *
86 * which is
87 *
88 * na*bx + nb*-dx = cx-ax
89 * na*by + nb*-dy = cy-ay
90 *
91 * which we the solve with Cramer's rule:
92 * http://en.wikipedia.org/wiki/Cramer's_rule
93 */
94
95static int intersect(double ax, double ay, double bx, double by,
96    double cx, double cy, double dx, double dy, double *na, double *nb)
97{
98    double det;
99
100    det = dx*by-bx*dy;
101    if (fabs(det) < EPSILON)
102        return 0;
103
104    *na = (dx*(cy-ay)-dy*(cx-ax))/det;
105    *nb = (bx*(cy-ay)-by*(cx-ax))/det;
106    return 1;
107}
108
109
110/*
111 * Solve
112 *
113 * (ax+n*bx-cx)^2+(ay+n*by-cy)^2 = r^2 for n
114 *
115 * http://en.wikipedia.org/wiki/Quadratic_equation
116 */
117
118static int touch(double ax, double ay, double bx, double by,
119    double cx, double cy, double r, double *n)
120{
121    double dx = cx-ax;
122    double dy = cy-ay;
123    double a = bx*bx+by*by;
124    double b = -2*bx*dx-2*by*dy;
125    double c = dx*dx+dy*dy-r*r;
126    double d, n0, n1;
127
128    d = b*b-4*a*c;
129    if (d < 0)
130        return 0;
131    d = sqrt(d);
132    n0 = (-b-d)/2/a;
133    n1 = (-b+d)/2/a;
134
135    if (n0 > 0) {
136        *n = n0;
137        return 1;
138    }
139    if (n1 > 0) {
140        *n = n1;
141        return 1;
142    }
143    return 0;
144}
145
146
147static int hit_segment(double fx, double fy, double tx, double ty,
148    const struct point *a, const struct point *b, double r, double *n)
149{
150    double dx, dy, d;
151    double px, py;
152    double na, nb;
153
154printf(" seg (%g,%g)+(%g,%g) -> (%g,%g)-(%g,%g)\n",
155    fx, fy, tx, ty, a->x, a->y, b->x, b->y);
156    tx -= fx;
157    ty -= fy;
158
159    dx = b->x-a->x;
160    dy = b->y-a->y;
161    d = hypot(dx, dy);
162
163    px = a->x-dy/d*r;
164    py = a->y+dx/d*r;
165
166    if (!intersect(fx, fy, tx, ty, px, py, dx, dy, &na, &nb))
167        return 0;
168printf("\tna %g (%g) nb %g (%g)\n", na, fx+tx*na, nb, fx+tx*nb);
169    if (nb <= 0) {
170        if (!touch(fx, fy, tx, ty, a->x, a->y, r, &na))
171            return 0;
172    }
173    if (nb >= 1) {
174        if (!touch(fx, fy, tx, ty, b->x, b->y, r, &na))
175            return 0;
176    }
177    if (na <= 0 || na >= 1)
178        return 0;
179    *n = na;
180    return 1;
181}
182
183
184static int hit_path(double fx, double fy, double tx, double ty,
185    const struct path *path, int inside, double r, double *x)
186{
187    const struct point *p;
188    int left;
189    double nx, tmp;
190    int found = 0;
191
192    left = path_tool_is_left(path);
193    if (inside)
194        left = !left;
195    for (p = path->first; p != path->last; p = p->next) {
196        if (hit_segment(fx, fy, tx, ty,
197            left ? p : p->next, left ? p->next : p, r, &tmp)) {
198            if (!found || nx > tmp)
199                nx = tmp;
200            found = 1;
201        }
202    }
203    if (found)
204        *x = fx+nx*(tx-fx);
205    return found;
206}
207
208
209static const struct path **subordinates(const struct path *paths,
210    const struct path *path)
211{
212    const struct path **sub, **w, **a, **b;;
213    const struct path *p;
214    int n = 0;
215
216    for (p = paths; p; p = p->next)
217        n++;
218    sub = alloc_size(sizeof(struct path *)*n);
219    w = sub;
220    for (p = paths; p; p = p->next)
221        if (p != path && is_inside(p, path) && !is_inside(path, p))
222            *w++ = p;
223    *w = NULL;
224    for (a = sub; a != w; a++)
225        for (b = sub; b != w; b++)
226            if (a != b && is_inside(*a, *b)) {
227                *a = *w--;
228                *w = NULL;
229                a--;
230                break;
231            }
232    return sub;
233}
234
235
236static void do_line(const struct path *path, const struct path **sub,
237    double xa, double xb, double y, double r_tool, struct path **res)
238{
239    const struct path *last = path;
240    const struct path **s;
241    struct path *new;
242    double x, next;
243
244printf(" y=%g\n", y);
245    if (!hit_path(xa-3*r_tool, y, xb, y, last, 1, r_tool, &x))
246        return;
247    while (1) {
248printf(" x=%g\n", x);
249        next = xb;
250        last = NULL;
251        if (hit_path(x, y, xb, y, path, 1, r_tool, &next))
252            last = path;
253        for (s = sub; *s; s++)
254            if (hit_path(x, y, next, y, *s, 0, r_tool, &next))
255                last = *s;
256        new = path_new(r_tool, "");
257        path_add(new, x, y, path->first->z);
258        path_add(new, next, y, path->first->z);
259        new->next = *res;
260        *res = new;
261        if (!last)
262            return;
263        if (!hit_path(next+EPSILON, y, xb, y, last, last == path,
264            r_tool, &x))
265            return;
266    }
267}
268
269
270static void fill_path(const struct path *paths, const struct path *path,
271    double r_tool, double overlap, struct path **res)
272{
273    const struct path **sub, **s;
274    const struct path **sub2, **s2;
275        double xa, ya, xb, yb;
276    int n, i;
277
278    if (!bbox(path, &xa, &ya, &xb, &yb))
279        return;
280    sub = subordinates(paths, path);
281    xa += r_tool;
282    ya += r_tool;
283    xb -= r_tool;
284    yb -= r_tool;
285    n = ceil((yb-ya)/(2*r_tool-overlap));
286printf("x[%g:%g] y[%g:%g] n=%d\n", xa, xb, ya, yb, n);
287    for (i = 0; i <= n; i++)
288        do_line(path, sub, xa, xb, ya+(yb-ya)*((double) i/n), r_tool,
289            res);
290    for (s = sub; *s; s++) {
291        sub2 = subordinates(paths, *s);
292        for (s2 = sub2; *s2; s2++)
293            fill_path(paths, *s2, r_tool, overlap, res);
294        free(sub2);
295    }
296    free(sub);
297}
298
299
300struct path *area(const struct path *path, double r_tool, double overlap)
301{
302    struct path *res = NULL;
303
304    if (!path)
305        return NULL;
306    fill_path(path, path_find_leftmost(path), r_tool, overlap, &res);
307    return res;
308}
cameo/area.h
1/*
2 * area.h - Area fill
3 *
4 * Written 2012 by Werner Almesberger
5 * Copyright 2012 Werner Almesberger
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 */
12
13
14#ifndef AREA_H
15#define AREA_H
16
17
18#include "path.h"
19
20
21struct path *area(const struct path *path, double r_tool, double overlap);
22
23#endif /* !AREA_H */
cameo/lang.l
22/*
33 * lang.l - Toolpath adaptation language
44 *
5 * Written 2010-2011 by Werner Almesberger
6 * Copyright 2010-2011 by Werner Almesberger
5 * Written 2010-2012 by Werner Almesberger
6 * Copyright 2010-2012 by Werner Almesberger
77 *
88 * This program is free software; you can redistribute it and/or modify
99 * it under the terms of the GNU General Public License as published by
...... 
4444<INITIAL>clear return TOK_CLEAR;
4545<INITIAL>drill return TOK_DRILL;
4646<INITIAL>empty return TOK_EMPTY;
47<INITIAL>area return TOK_AREA;
4748<INITIAL>mill return TOK_MILL;
4849<INITIAL>offset return TOK_OFFSET;
4950<INITIAL>optimize return TOK_OPTIMIZE;
cameo/lang.y
22/*
33 * lang.y - Toolpath adaptation language
44 *
5 * Written 2010-2011 by Werner Almesberger
6 * Copyright 2010-2011 by Werner Almesberger
5 * Written 2010-2012 by Werner Almesberger
6 * Copyright 2010-2012 by Werner Almesberger
77 *
88 * This program is free software; you can redistribute it and/or modify
99 * it under the terms of the GNU General Public License as published by
...... 
1818
1919#include "path.h"
2020#include "ops.h"
21#include "area.h"
2122#include "gnuplot.h"
2223#include "gerber.h"
2324#include "excellon.h"
...... 
186187};
187188
188189
189%token TOK_ALIGN TOK_ARRAY TOK_CLEAR TOK_DRILL TOK_EMPTY
190%token TOK_ALIGN TOK_ARRAY TOK_CLEAR TOK_DRILL TOK_EMPTY TOK_AREA
190191%token TOK_MILL TOK_OFFSET TOK_OPTIMIZE TOK_REMAINDER TOK_RESET
191192%token TOK_ROTATE TOK_STATS TOK_TRANSLATE TOK_Z
192193%token TOK_APPEND TOK_GERBER TOK_GNUPLOT TOK_EXCELLON TOK_WRITE
...... 
327328                walk =
328329                    classify(walk, try_drill(*walk, $2, $4));
329330        }
331    | TOK_AREA dimen opt_comma dimen
332        {
333            struct path *tmp;
334
335            tmp = area(paths, $2/2, $4);
336            clear_paths();
337            paths = tmp;
338        }
330339    | TOK_MILL opt_any dimen dimen
331340        {
332341            struct path **walk;

Archive Download the corresponding diff file

Branches:
master



interactive