Root/cameo/ops.c

1/*
2 * ops.c - Higher-level toolpath operations
3 *
4 * Written 2010-2013, 2015 by Werner Almesberger
5 * Copyright 2010-2013, 2105 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 <stddef.h>
15#include <stdbool.h>
16#include <math.h>
17
18#include "path.h"
19#include "shape.h"
20#include "ops.h"
21
22
23static struct path *tool_comp_1(const struct path *path, int inside,
24    int dog_bone)
25{
26    int left;
27
28    left = path_tool_is_left(path);
29    if (inside)
30        return path_offset(path, !left, path->notch);
31    else
32        return path_offset(path, left, path->notch || dog_bone);
33}
34
35
36struct path *tool_comp_paths(const struct path *paths, int dog_bone,
37    int all_inside)
38{
39    const struct path *leftmost, *path;
40    struct path *new = NULL, **anchor = &new;
41
42    /*
43     * We don't have an algorithm (yet) that can detect which paths are
44     * inside other paths. Therefore, we fake it by looking for the path
45     * that contains the lowest x coordinate. This ought to be the outer
46     * boundary of the piece.
47     *
48     * Note that this heuristic falls apart when a job consists of
49     * multiple pieces. In this case, the #%outside hint can be used to
50     * explicitly tell cameo to treat the path as an outside edge.
51     */
52
53    if (!paths)
54        return NULL;
55    leftmost = path_find_leftmost(paths);
56    for (path = paths; path; path = path->next)
57        if (path != leftmost && (all_inside || !path->outside)) {
58            *anchor = tool_comp_1(path, 1, dog_bone);
59            anchor = &(*anchor)->next;
60        }
61    if (!all_inside)
62        for (path = paths; path; path = path->next)
63            if (path != leftmost && path->outside) {
64                *anchor = tool_comp_1(path, 0, dog_bone);
65                anchor = &(*anchor)->next;
66            }
67    *anchor = tool_comp_1(leftmost, all_inside, dog_bone);
68    return new;
69}
70
71
72struct path *try_drill(struct path *path, double d_min, double d_max)
73{
74    struct path *new;
75
76    if (path->r_tool*2 < d_min || path->r_tool*2 > d_max)
77        return NULL;
78    if (!path->first || path->first != path->last)
79        return NULL;
80    new = path_new((d_min+d_max)/2, path->id); /* @@@ fishy */
81    path_add(new, path->first->x, path->first->y, path->first->z);
82    return new;
83}
84
85
86struct path *try_mill(struct path *path, double diam, double step, int any)
87{
88    if (!any && path->r_tool*2 < diam)
89        return NULL;
90    if (!path->first)
91        return NULL;
92    if (path->first == path->last)
93        return circle(path->first->x, path->first->y, path->first->z,
94            path->r_tool, diam/2, step, path->id);
95    if (path->first->next == path->last)
96        return slot(path->first->x, path->first->y,
97            path->first->next->x, path->first->next->y,
98            path->first->z, path->r_tool, diam/2, step, path->id);
99    return NULL;
100}
101
102
103/*
104 * This isn't a perfect solution for the traveling salesman problem, but it's
105 * easy to implement and usually produces results that don't look overly
106 * offensive.
107 */
108
109struct path *optimize_paths(struct path *paths)
110{
111    struct path **walk, **best = NULL;
112    struct path *res = NULL, **anchor = &res;
113    struct path *curr;
114    struct point *p;
115    double best_d = 0, d;
116
117    for (walk = &paths; *walk; walk = &(*walk)->next) {
118        p = (*walk)->first;
119        if (!p)
120            continue;
121        d = hypot(p->x, p->y);
122        if (!best || d < best_d) {
123            best = walk;
124            best_d = d;
125        }
126    }
127    while (best) {
128        curr = *best;
129        *anchor = *best;
130        anchor = &curr->next;
131        *best = curr->next;
132        best = NULL;
133        for (walk = &paths; *walk; walk = &(*walk)->next) {
134            p = (*walk)->first;
135            if (!p)
136                continue;
137            d = hypot(p->x-curr->last->x, p->y-curr->last->y);
138            if (!best || d < best_d) {
139                best = walk;
140                best_d = d;
141            }
142        }
143    }
144    return res;
145}
146
147
148struct path *reverse_paths(const struct path *paths)
149{
150    const struct path *path;
151    struct path *res = NULL, **last = &res;
152
153    for (path = paths; path; path = path->next) {
154        *last = path_reverse(path);
155        last = &(*last)->next;
156    }
157    return res;
158}
159
160
161static int select_path(const struct path *path, double xa, double ya,
162    double xb, double yb, int inside)
163{
164    const struct point *p;
165
166    for (p = path->first; p; p = p->next) {
167        if (p->x >= xa && p->x <= xb && p->y >= ya && p->y <= yb) {
168            if (!inside)
169                return 0;
170        } else {
171            if (inside)
172                return 0;
173        }
174    }
175    return 1;
176}
177
178
179struct path *select_paths(const struct path *paths, double xa, double ya,
180    double xb, double yb, int inside)
181{
182    struct path *res = NULL, **last = &res;
183
184    if (xa > xb)
185        return select_paths(paths, xb, ya, xa, yb, inside);
186    if (ya > yb)
187        return select_paths(paths, xa, yb, xb, ya, inside);
188    while (paths) {
189        if (select_path(paths, xa, ya, xb, yb, inside)) {
190            *last = path_clone(paths);
191            last = &(*last)->next;
192        }
193        paths = paths->next;
194    }
195    return res;
196}
197
198
199static double cross_area(double ax, double ay, double az, double bx, double by,
200    double bz)
201{
202    double x, y, z;
203
204    x = ay * bz - by * az;
205    y = az * bx - ax * bz;
206    z = ax * by - ay * bx;
207    return hypot(hypot(x, y), z);
208}
209
210
211struct path *purge_paths(const struct path *paths, double len)
212{
213    const struct path *path;
214    struct path *p = NULL, **anchor = &p, *new;
215    struct point *a, *b, *c;
216    struct point *end;
217    double area, t;
218    bool closed;
219
220    if (!len)
221        len = EPSILON_PURGE;
222    area = len * len;
223    for (path = paths; path; path = path->next) {
224        if (!path->first)
225            continue;
226        closed = path_is_closed(path);
227        if (closed) {
228            end = path->first;
229            while (end->next != path->last)
230                end = end->next;
231        } else {
232            end = path->last;
233        }
234        a = end;
235        b = path->first;
236        c = b->next;
237        if (!c)
238            continue;
239        new = path_from(path);
240        while (1) {
241            t = cross_area(a->x - b->x, a->y - b->y, a->z - b->z,
242                c->x - b->x, c->y - b->y, c->z - b->z);
243            if (t >= area) {
244                path_add(new, b->x, b->y, b->z);
245                a = b;
246            }
247            b = c;
248            if (closed) {
249                c = c == end ? path->first : c->next;
250            } else {
251                c = c->next;
252            }
253            if (b == path->first || !c)
254                break;
255        }
256        if (new->first) {
257            if (closed)
258                path_add(new, new->first->x, new->first->y,
259                    new->first->z);
260            *anchor = new;
261            anchor = &new->next;
262        } else {
263            path_free(new);
264        }
265    }
266    return p;
267}
268

Archive Download this file

Branches:
master



interactive