Date:2011-07-29 03:31:25 (12 years 7 months ago)
Author:Werner Almesberger
Commit:d4c96f129d67f4713cfe8d636e831939b5ed93fc
Message:ptrude/: path extrusion, work in progress

Files: ptrude/Makefile (1 diff)
ptrude/README (1 diff)
ptrude/arc.fig (1 diff)
ptrude/corner.fig (1 diff)
ptrude/path.c (1 diff)
ptrude/path.h (1 diff)
ptrude/ptrude.c (1 diff)
ptrude/try (1 diff)

Change Details

ptrude/Makefile
1CFLAGS = -Wall -g
2LDFLAGS = -lm
3OBJS = ptrude.o path.o
4
5.PHONY: clean try
6
7ptrude: $(OBJS)
8
9try: ptrude
10    ./ptrude <try | tee out
11
12clean:
13    rm -f $(OBJS)
ptrude/README
1File format
2-----------
3
4#r=radius
5    minimum bend radius. Propagates to all subsequent points.
6#delta=distance
7    maximum distance of line from curve. Propagates to all
8    subsequent points.
9#tag=name
10    name point or shape. Gets passed through 2D->2D transform.
11    Affects only the next point.
12x-coord y-coord
13    line endpoint
14
15#r=, #delta=, and #tag= modify the next point, e.g.,
16
170 0
18#r=2
19#tag=foo
201 0
211 1
22
23would set the bend radius at the corner (and the final point) to 2 mm
24and the tag of the corner point to "foo".
ptrude/arc.fig
1#FIG 3.2 Produced by xfig version 3.2.5b
2Landscape
3Center
4Metric
5A4
6100.00
7Single
8-2
91200 2
105 1 0 1 0 7 50 -1 -1 0.000 0 1 0 0 3822.761 2922.761 3825 7425 7193 5908 8325 2925
115 1 0 1 0 7 50 -1 -1 0.000 0 1 0 0 3821.168 2921.168 3825 7290 4883 7159 8190 2925
125 1 0 1 0 7 50 -1 -1 0.000 0 1 0 0 3822.431 2923.366 3825 7560 4969 7416 8459 2948
135 1 0 1 0 0 50 -1 -1 4.000 0 1 0 0 8324.358 7425.641 8775 7425 8706 7186 8325 6975
145 1 0 1 0 0 50 -1 -1 4.000 0 0 0 0 3823.445 2923.445 5400 2925 5284 3517 3825 4500
151 3 0 0 0 0 50 -1 20 0.000 1 0.0000 4725 7065 45 45 4725 7065 4770 7065
161 3 0 0 0 0 50 -1 20 0.000 1 0.0000 7065 5625 45 45 7065 5625 7110 5625
171 3 0 0 0 0 50 -1 20 0.000 1 0.0000 4950 7020 45 45 4950 7020 4995 7020
181 3 0 0 0 0 50 -1 20 0.000 1 0.0000 7245 5400 45 45 7245 5400 7290 5400
192 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
20     900 7425 3825 7425
212 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
22     8325 2925 8325 1125
232 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
24    0 0 1.00 120.00 120.00
25    0 0 1.00 120.00 120.00
26     3870 2790 8235 2790
272 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 3
28     3825 7425 6390 6795 8235 4320
292 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
30     3825 2925 8235 4320
312 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
32     3825 2925 7290 5580
332 1 1 2 0 0 50 -1 -1 6.000 0 0 -1 0 0 2
34     8235 4320 8280 3690
352 1 0 1 0 0 50 -1 -1 4.000 0 0 -1 0 0 2
36     8325 2925 8325 7650
372 1 0 1 0 0 50 -1 -1 4.000 0 0 -1 0 0 2
38     3825 7425 9000 7425
392 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
40     9000 2925 3330 2925
412 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
42     3825 2925 6390 6795
432 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
44     3825 2475 3825 8100
452 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
46     3825 2925 4860 7155
474 1 0 50 -1 18 18 0.0000 4 150 105 6075 2655 r\001
484 1 0 50 -1 18 18 0.0000 4 210 180 3690 7380 d\001
494 1 0 50 -1 18 18 0.0000 4 210 180 3690 7695 d\001
504 1 0 50 -1 18 18 0.0000 4 150 105 3645 5490 r\001
514 1 0 50 -1 18 18 0.0000 4 210 375 4365 6390 r-d\001
524 1 0 50 -1 18 18 0.0000 4 210 450 5580 6300 r+d\001
534 1 0 50 -1 18 18 0.0000 4 210 375 6210 5175 r-d\001
544 1 0 50 -1 18 18 0.0000 4 210 450 6840 4230 r+d\001
554 1 0 50 -1 18 18 0.0000 4 150 165 4545 7695 u\001
564 1 0 50 -1 18 18 0.0000 4 150 135 5625 7425 v\001
574 1 0 50 -1 18 18 0.0000 4 150 135 7290 6390 v\001
584 1 0 50 -1 18 18 0.0000 4 150 135 8055 5220 v\001
594 0 0 50 -1 18 18 0.0000 4 150 855 8640 3690 ...+v+u\001
604 1 0 50 -1 18 18 0.0000 4 195 240 8505 7380 2t\001
614 0 0 50 -1 18 18 0.0000 4 270 2085 9405 7200 (r-d)^2+u^2=r^2\001
624 0 0 50 -1 18 18 0.0000 4 270 2610 9405 7650 (r-d)^2+v^2=(r+d)^2\001
634 0 0 50 -1 18 18 0.0000 4 270 1530 9405 8100 2t = 2p+n*q\001
644 0 0 50 -1 18 18 0.0000 4 210 915 4410 3105 ...+q+p\001
654 1 0 50 -1 18 18 0.0000 4 210 180 4950 3555 q\001
664 1 0 50 -1 18 18 0.0000 4 210 180 4635 3870 q\001
674 1 0 50 -1 18 18 0.0000 4 210 180 4320 4050 q\001
684 1 0 50 -1 18 18 0.0000 4 210 180 3960 4185 p\001
ptrude/corner.fig
1#FIG 3.2 Produced by xfig version 3.2.5b
2Landscape
3Center
4Metric
5A4
6100.00
7Single
8-2
91200 2
105 1 0 2 0 7 48 -1 -1 0.000 0 1 0 0 4494.036 1337.375 4500 9000 6203 8807 9909 6759
115 1 0 1 0 7 48 -1 -1 0.000 0 1 0 0 4499.660 1353.986 5220 3105 5552 2928 5818 2713
125 1 0 1 0 7 52 -1 -1 0.000 0 1 0 0 7651.482 8999.573 9000 9000 8926 8559 8604 8045
135 1 0 1 0 7 52 -1 -1 0.000 0 1 0 0 3374.893 7199.935 3915 7200 3838 6922 2993 6818
145 1 0 2 0 7 48 -1 -1 0.000 0 1 0 0 1798.655 6524.275 1800 7200 2162 7094 2277 6047
151 3 0 0 0 7 46 -1 0 0.000 1 0.0000 2250 6255 45 45 2250 6255 2295 6255
161 3 0 0 0 7 46 -1 0 0.000 1 0.0000 1935 7065 45 45 1935 7065 1980 7065
171 3 0 0 0 7 46 -1 0 0.000 1 0.0000 4680 8820 45 45 4680 8820 4725 8820
181 3 0 0 0 7 46 -1 0 0.000 1 0.0000 9630 6750 45 45 9630 6750 9675 6750
192 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
20     9900 6750 4050 900
212 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 3
22     1575 9000 7650 9000 13050 3600
232 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
24     7650 9000 4185 585
252 1 0 1 0 7 52 -1 -1 0.000 0 0 -1 0 0 2
26     7650 9000 11025 9000
272 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 3
28     675 7200 3375 7200 1125 4950
292 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
30     1800 7200 1800 5850
312 1 0 1 0 7 52 -1 -1 0.000 0 0 -1 0 0 2
32     3375 7200 4050 7200
332 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
34     2250 6075 1350 6975
352 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
36     3375 7200 1620 6435
372 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
38    0 0 1.00 120.00 120.00
39    0 0 1.00 120.00 120.00
40     4500 9135 7650 9135
412 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
42    0 0 1.00 90.00 90.00
43    0 0 1.00 90.00 90.00
44     1800 7335 3375 7335
452 1 0 0 0 7 46 -1 0 0.000 0 0 -1 1 1 2
46    0 0 1.00 90.00 90.00
47    0 0 1.00 90.00 90.00
48     4500 1350 4500 9000
492 1 0 0 0 7 46 -1 0 0.000 0 0 -1 1 1 2
50    0 0 1.00 90.00 90.00
51    0 0 1.00 90.00 90.00
52     7425 8415 7650 9000
532 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
54     4500 9000 4500 675
554 1 0 50 -1 18 18 0.0000 4 210 180 7650 8685 d\001
564 0 0 50 -1 18 18 0.0000 4 150 105 4320 5580 r\001
574 0 0 50 -1 18 18 0.0000 4 150 105 6030 5760 r\001
584 0 0 50 -1 18 18 0.0000 4 195 90 5130 2475 t\001
594 0 0 50 -1 18 18 0.0000 4 270 1830 7425 1125 cos t = r/(r+d)\001
604 1 0 50 -1 18 18 0.0000 4 150 165 5985 9405 s\001
614 0 0 50 -1 18 18 0.0000 4 210 1305 7425 1575 s = r*tan t\001
624 0 0 50 -1 18 18 0.0000 4 195 240 8325 8775 2t\001
634 0 0 48 -1 18 18 0.0000 4 195 240 3330 7020 2t\001
644 1 0 48 -1 18 18 0.0000 4 195 90 2115 6525 t\001
654 1 0 48 -1 18 18 0.0000 4 150 105 1665 7020 r\001
664 1 0 48 -1 18 18 0.0000 4 210 180 2520 7110 d\001
674 1 0 50 -1 18 18 0.0000 4 150 165 2610 7605 s\001
684 0 0 50 -1 18 18 0.0000 4 270 2310 7425 2025 r^2+s^2 = (r+d)^2\001
ptrude/path.c
1#include <stdlib.h>
2#include <stdio.h>
3#include <string.h>
4#include <math.h>
5
6#include "path.h"
7
8
9#define alloc_type(t) ((t *) malloc(sizeof(t)))
10#define stralloc(s) strdup(s)
11
12
13static double deg(double rad)
14{
15    return rad/M_PI*180.0;
16}
17
18
19static struct path *alloc_path(void)
20{
21    struct path *path;
22
23    path = alloc_type(struct path);
24    path->vertices = NULL;
25    path->last = &path->vertices;
26    return path;
27}
28
29
30static struct vertex *alloc_vertex(void)
31{
32    struct vertex *v;
33
34    v = alloc_type(struct vertex);
35    v->r = 0;
36    v->d = 0;
37    v->tag = NULL;
38    v->next = NULL;
39    return v;
40}
41
42
43static void free_vertex(struct vertex *v)
44{
45    free(v);
46}
47
48
49void free_path(struct path *path)
50{
51    struct vertex *v, *next;
52
53    for (v = path->vertices; v; v = next) {
54        next = v->next;
55        free_vertex(v);
56    }
57    free(path);
58}
59
60
61static struct vertex *clone_vertex(const struct vertex *v)
62{
63    struct vertex *new;
64
65    new = alloc_type(struct vertex);
66    *new = *v;
67    new->next = NULL;
68    return new;
69}
70
71
72static void append_vertex(struct path *path, struct vertex *v)
73{
74    *path->last = v;
75    path->last = &v->next;
76}
77
78
79static const struct vertex *add_vertex(struct path *path, double x, double y,
80    double r, double d, const char *tag)
81{
82    struct vertex *v;
83
84    v = alloc_vertex();
85    v->x = x;
86    v->y = y;
87    v->r = r;
88    v->d = d;
89    v->tag = tag;
90    append_vertex(path, v);
91    return v;
92}
93
94
95static const struct vertex *corner(struct path *path, const struct vertex *a,
96    const struct vertex *b, const struct vertex *c, double r, double d)
97{
98    double ax = b->x-a->x;
99    double ay = b->y-a->y;
100    double bx = c->x-b->x;
101    double by = c->y-b->y;
102    double aa = hypot(ax, ay);
103    double bb = hypot(bx, by);
104    double dp = ax*bx+ay*by; /* a * b = a*b*cos 2t */
105    double cp = ax*by-ay*bx; /* |a x b| = a*b*sin 2t */
106    double dd; /* "d" of the given vectors */
107    double tt, s;
108    double t2, p, q, ang;
109    double u, v;
110    double f, x, y;
111    int n, i;
112
113    /*
114     * http://en.wikipedia.org/wiki/Dot_product
115     * dp = a*b*cos 2t
116     *
117     * http://en.wikipedia.org/wiki/Cross_product
118     * cp = a*b*sin 2t
119     *
120     * http://en.wikipedia.org/wiki/Tangent_half-angle_formula
121     * tan t = sin 2t/(1+cos 2t)
122     */
123    tt = cp/(aa*bb+dp);
124
125    /*
126     * From s = r*tan t
127     */
128    s = fabs(r*tt);
129
130    /*
131     * From r^2+s^2 = (r+d)^2
132     */
133    dd = hypot(r, s)-r;
134
135    fprintf(stderr, "a = (%g, %g)-(%g, %g) = (%g, %g); |a| = %g\n",
136        b->x, b->y, a->x, a->y, ax, ay, aa);
137    fprintf(stderr, "b = (%g, %g)-(%g, %g) = (%g, %g); |b| = %g\n",
138        c->x, c->y, b->x, b->y, bx, by, bb);
139    fprintf(stderr, "sin 2t = %g, cos 2t = %g, tan t = %g\n",
140        cp/aa/bb, dp/aa/bb, tt);
141    fprintf(stderr, "r = %g, d = %g, s = %g, dd = %g\n", r, d, s, dd);
142
143    /*
144     * We only know how to make a rounded corner if two vectors are
145     * involved. They therefore have to be long enough to accommodate the
146     * entire arc, from beginning to end. Furthermore, we split the
147     * available length in half, one for the inbound arc, the other for the
148     * outbound arc.
149     */
150    if (aa/2 < s) {
151        fprintf(stderr, "first vector is too short (%g/2 < %g)\n",
152            aa, s);
153        exit(1);
154    }
155    if (bb/2 < s) {
156        fprintf(stderr, "second vector is too short (%g/2 < %g)\n",
157            bb, s);
158        exit(1);
159    }
160
161    /*
162     * If the corner is already smooth enough, we just keep what we have.
163     */
164    if (dd <= d) {
165        append_vertex(path, clone_vertex(b));
166        return b;
167    }
168
169    /* Step 1: determine the total angle (2*t) */
170
171    t2 = acos(dp/aa/bb);
172
173    /*
174     * Step 2: determine the maximum angle of the first and last segment.
175     *
176     * We use
177     * r*cos p = r-d
178     * cos p = 1-d/r
179     */
180
181    p = acos(1-d/r);
182
183    /*
184     * Step 3: determine the maximum angle of intermediate segments (if
185     * there are any).
186     *
187      * We use
188     * (r+d)*cos q = r-d
189     * cos q = r-q/(r+d)
190     */
191
192    q = acos((r-d)/(r+d));
193
194    fprintf(stderr, "t2 = %g, p(max) = %g, q(max) = %g\n",
195        deg(t2), deg(p), deg(q));
196
197    /*
198     * Step 4: emit the starting point of the arc
199     */
200
201    f = s/aa;
202    x = b->x-f*ax;
203    y = b->y-f*ay;
204    add_vertex(path, x, y, b->r, b->d, b->tag);
205
206    /*
207     * Step 5: determine if we need intermediate points. If yes, how many,
208     * and then proceed to add them.
209     */
210
211    if (t2 > 2*p) {
212        n = (int) ceil((t2-2*(p+q))/(2*q));
213
214        /*
215         * @@@ We should evenly distribute the slack, but that seems
216         * difficult. For now, we just center the polygon.
217         */
218        q = (t2/2-p)/(n+1);
219
220        double dir = copysign(1, cp);
221#if 0
222        if (cp < 0) {
223// t2 = -t2;
224            q = -q;
225            p = -p;
226        }
227#endif
228
229        if (n)
230            ang = p+q;
231        else
232            ang = t2/2;
233        u = tan(p)*(r-d);
234        v = tan(q)*(r-d);
235        f = (u+v)/aa;
236        for (i = 0; i <= n; i++) {
237            x += f*ax*cos(ang-q)-dir*f*ay*sin(ang-q);
238            y += dir*f*ax*sin(ang-q)+f*ay*cos(ang-q);
239            fprintf(stderr, " %d/%d: %g %g @ %g\n", i, n,
240                x, y, deg(ang));
241            add_vertex(path, x, y, 0, 0, NULL);
242            ang += 2*q;
243            f = (2*v)/aa;
244        }
245    }
246
247    /*
248     * Step 6: emit the finishing point of the arc
249     */
250
251    f = s/bb;
252    return add_vertex(path, b->x+f*bx, b->y+f*by, 0, 0, NULL);
253}
254
255
256struct path *round_path(const struct path *path, double r, double d)
257{
258    struct path *new;
259    const struct vertex *prev, *v;
260
261    new = alloc_path();
262    prev = path->vertices;
263    if (!prev)
264        return new;
265    append_vertex(new, clone_vertex(prev));
266    if (!prev->next)
267        return new;
268
269    if (prev->r)
270        r = prev->r;
271    if (prev->d)
272        d = prev->d;
273
274    for (v = prev->next; v->next; v = v->next) {
275        if (v->r)
276            r = v->r;
277        if (v->d)
278            d = v->d;
279        prev = corner(new, prev, v, v->next, r, d);
280    }
281    append_vertex(new, clone_vertex(v));
282    return new;
283}
284
285
286struct path *load_path(FILE *file)
287{
288    struct path *path;
289    char buf[1100]; /* plenty :) */
290    char buf2[sizeof(buf)];
291    char *s;
292    float x, y, tmp;
293    float r = 0, d = 0;
294    const char *tag = NULL;
295
296    path = alloc_path();
297    while (fgets(buf, sizeof(buf),file)) {
298        s = strchr(buf, '\n');
299        if (s)
300            *s = 0;
301        if (sscanf(buf, "#r=%f", &tmp) == 1) {
302            r = tmp;
303            continue;
304        }
305        if (sscanf(buf, "#delta=%f", &tmp) == 1) {
306            d = tmp;
307            continue;
308        }
309        if (sscanf(buf, "#tag=%s", buf2) == 1) {
310            tag = stralloc(buf2);
311            continue;
312        }
313        if (*buf == '#')
314            continue;
315        if (sscanf(buf, "%f %f", &x, &y) != 2) {
316            fprintf(stderr, "can't parse \"%s\"\n", buf);
317            exit(1);
318        }
319
320        add_vertex(path, x, y, r, d, tag);
321
322        r = 0;
323        d = 0;
324        tag = NULL;
325    }
326
327    return path;
328}
329
330
331void save_path(FILE *file, const struct path *path)
332{
333    const struct vertex *v;
334
335    for (v = path->vertices; v; v = v->next) {
336        if (v->r)
337            fprintf(file, "#r=%f\n", v->r);
338        if (v->d)
339            fprintf(file, "#delta=%f\n", v->d);
340        if (v->tag)
341            fprintf(file, "#delta=%f\n", v->d);
342        fprintf(file, "%f %f\n", v->x, v->y);
343    }
344}
ptrude/path.h
1#ifndef PATH_H
2#define PATH_H
3
4#include <stdio.h>
5
6
7struct vertex {
8    double x, y;
9    double r; /* minimum bend radius; 0 = use previous value */
10    double d; /* max. distance of corner from ideal arc; 0 = prev */
11    const char *tag;
12    struct vertex *next;
13};
14
15struct path {
16    struct vertex *vertices;
17    struct vertex **last;
18};
19
20
21void free_path(struct path *path);
22
23struct path *round_path(const struct path *path, double r, double d);
24
25struct path *load_path(FILE *file);
26void save_path(FILE *file, const struct path *path);
27
28#endif /* !PATH_H */
ptrude/ptrude.c
1#include <stdio.h>
2
3#include "path.h"
4
5
6int main(void)
7{
8    const struct path *path;
9
10    path = load_path(stdin);
11    path = round_path(path, 1, 0.1);
12    save_path(stdout, path);
13
14    return 0;
15}
ptrude/try
10 0
2#r=10
3#delta=0.01
4100 0
5100 100
6200 100
7100 200
80 200
9100 100
100 100
110 50
12100 50
13150 0
14100 0

Archive Download the corresponding diff file

Branches:
master



interactive