Root/
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 | |
23 | static 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 | |
36 | struct 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 | |
72 | struct 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 | |
86 | struct 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 | |
109 | struct 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 | |
148 | struct 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 | |
161 | static 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 | |
179 | struct 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 | |
199 | static 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 | |
211 | struct 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 |
Branches:
master