1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * Embroidery stitch live path effect (Implementation)
4 *
5 * Copyright (C) 2016 Michael Soegtrop
6 *
7 * Released under GNU GPL v2+, read the file 'COPYING' for more information.
8 */
9
10 #include "ui/widget/scalar.h"
11 #include <glibmm/i18n.h>
12
13 #include "live_effects/lpe-embrodery-stitch.h"
14 #include "live_effects/lpe-embrodery-stitch-ordering.h"
15
16 #include <2geom/path.h>
17 #include <2geom/piecewise.h>
18 #include <2geom/sbasis.h>
19 #include <2geom/sbasis-geometric.h>
20 #include <2geom/bezier-to-sbasis.h>
21 #include <2geom/sbasis-to-bezier.h>
22
23 namespace Inkscape {
24 namespace LivePathEffect {
25
26 using namespace Geom;
27 using namespace LPEEmbroderyStitchOrdering;
28
29 static const Util::EnumData<LPEEmbroderyStitch::order_method> OrderMethodData[LPEEmbroderyStitch::order_method_count] = {
30 // clang-format off
31 { LPEEmbroderyStitch::order_method_no_reorder, N_("no reordering"), "no-reorder" },
32 { LPEEmbroderyStitch::order_method_zigzag, N_("zig-zag"), "zig-zag" },
33 { LPEEmbroderyStitch::order_method_zigzag_rev_first, N_("zig-zag, reverse first"), "zig-zag-rev-first" },
34 { LPEEmbroderyStitch::order_method_closest, N_("closest"), "closest" },
35 { LPEEmbroderyStitch::order_method_closest_rev_first, N_("closest, reverse first"), "closest-rev-first" },
36 { LPEEmbroderyStitch::order_method_tsp_kopt_2, N_("traveling salesman 2-opt (fast, bad)"), "tsp-2opt" },
37 { LPEEmbroderyStitch::order_method_tsp_kopt_3, N_("traveling salesman 3-opt (fast, ok)"), "tsp-3opt" },
38 { LPEEmbroderyStitch::order_method_tsp_kopt_4, N_("traveling salesman 4-opt (seconds)"), "tsp-4opt" },
39 { LPEEmbroderyStitch::order_method_tsp_kopt_5, N_("traveling salesman 5-opt (minutes)"), "tsp-5opt" }
40 // clang-format on
41 };
42
43 static const Util::EnumDataConverter<LPEEmbroderyStitch::order_method>
44 OrderMethodConverter(OrderMethodData, sizeof(OrderMethodData) / sizeof(*OrderMethodData));
45
46 static const Util::EnumData<LPEEmbroderyStitch::connect_method> ConnectMethodData[LPEEmbroderyStitch::connect_method_count] = {
47 { LPEEmbroderyStitch::connect_method_line, N_("straight line"), "line" },
48 { LPEEmbroderyStitch::connect_method_move_point_from, N_("move to begin"), "move-begin" },
49 { LPEEmbroderyStitch::connect_method_move_point_mid, N_("move to middle"), "move-middle" },
50 { LPEEmbroderyStitch::connect_method_move_point_to, N_("move to end"), "move-end" }
51 };
52
53 static const Util::EnumDataConverter<LPEEmbroderyStitch::connect_method>
54 ConnectMethodConverter(ConnectMethodData, sizeof(ConnectMethodData) / sizeof(*ConnectMethodData));
55
LPEEmbroderyStitch(LivePathEffectObject * lpeobject)56 LPEEmbroderyStitch::LPEEmbroderyStitch(LivePathEffectObject *lpeobject) :
57 Effect(lpeobject),
58 ordering(_("Ordering method"), _("Method used to order sub paths"), "ordering", OrderMethodConverter, &wr, this, order_method_no_reorder),
59 connection(_("Connection method"), _("Method to connect end points of sub paths"), "connection", ConnectMethodConverter, &wr, this, connect_method_line),
60 stitch_length(_("Stitch length"), _("Divide path into straight segments of given length (in user units)"), "stitch-length", &wr, this, 10.0),
61 stitch_min_length(_("Minimum stitch length [%]"), _("Merge stitches that are shorter than this percentage of the stitch length"), "stitch-min-length", &wr, this, 25.0),
62 stitch_pattern(_("Stitch pattern"), _("Select between different stitch patterns"), "stitch_pattern", &wr, this, 0),
63 show_stitches(_("Show stitches"), _("Creates gaps between stitches (use only for preview, deactivate for use with embroidery machines)"), "show-stitches", &wr, this, false),
64 show_stitch_gap(_("Show stitch gap"), _("Length of the gap between stitches when showing stitches"), "show-stitch-gap", &wr, this, 0.5),
65 jump_if_longer(_("Jump if longer"), _("Jump connection if longer than"), "jump-if-longer", &wr, this, 100)
66 {
67 registerParameter(dynamic_cast<Parameter *>(&ordering));
68 registerParameter(dynamic_cast<Parameter *>(&connection));
69 registerParameter(dynamic_cast<Parameter *>(&stitch_length));
70 registerParameter(dynamic_cast<Parameter *>(&stitch_min_length));
71 registerParameter(dynamic_cast<Parameter *>(&stitch_pattern));
72 registerParameter(dynamic_cast<Parameter *>(&show_stitches));
73 registerParameter(dynamic_cast<Parameter *>(&show_stitch_gap));
74 registerParameter(dynamic_cast<Parameter *>(&jump_if_longer));
75
76 stitch_length.param_set_digits(1);
77 stitch_length.param_set_range(1, 10000);
78 stitch_min_length.param_set_digits(1);
79 stitch_min_length.param_set_range(0, 100);
80 stitch_pattern.param_make_integer();
81 stitch_pattern.param_set_range(0, 2);
82 show_stitch_gap.param_set_range(0.001, 10);
83 jump_if_longer.param_set_range(0.0, 1000000);
84 }
85
86 LPEEmbroderyStitch::~LPEEmbroderyStitch()
87 = default;
88
GetPatternInitialStep(int pattern,int line)89 double LPEEmbroderyStitch::GetPatternInitialStep(int pattern, int line)
90 {
91 switch (pattern) {
92 case 0:
93 return 0.0;
94
95 case 1:
96 switch (line % 4) {
97 case 0:
98 return 0.0;
99 case 1:
100 return 0.25;
101 case 2:
102 return 0.50;
103 case 3:
104 return 0.75;
105 }
106 return 0.0;
107
108 case 2:
109 switch (line % 4) {
110 case 0:
111 return 0.0;
112 case 1:
113 return 0.5;
114 case 2:
115 return 0.75;
116 case 3:
117 return 0.25;
118 }
119 return 0.0;
120
121 default:
122 return 0.0;
123 }
124
125 }
126
GetStartPointInterpolAfterRev(std::vector<OrderingInfo> const & info,unsigned i)127 Point LPEEmbroderyStitch::GetStartPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i)
128 {
129 Point start_this = info[i].GetBegRev();
130
131 if (i == 0) {
132 return start_this;
133 }
134
135 if (!info[i - 1].connect) {
136 return start_this;
137 }
138
139 Point end_prev = info[i - 1].GetEndRev();
140
141 switch (connection.get_value()) {
142 case connect_method_line:
143 return start_this;
144 case connect_method_move_point_from:
145 return end_prev;
146 case connect_method_move_point_mid:
147 return 0.5 * start_this + 0.5 * end_prev;
148 case connect_method_move_point_to:
149 return start_this;
150 default:
151 return start_this;
152 }
153 }
GetEndPointInterpolAfterRev(std::vector<OrderingInfo> const & info,unsigned i)154 Point LPEEmbroderyStitch::GetEndPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i)
155 {
156 Point end_this = info[i].GetEndRev();
157
158 if (i + 1 == info.size()) {
159 return end_this;
160 }
161
162 if (!info[i].connect) {
163 return end_this;
164 }
165
166 Point start_next = info[i + 1].GetBegRev();
167
168 switch (connection.get_value()) {
169 case connect_method_line:
170 return end_this;
171 case connect_method_move_point_from:
172 return end_this;
173 case connect_method_move_point_mid:
174 return 0.5 * start_next + 0.5 * end_this;
175 case connect_method_move_point_to:
176 return start_next;
177 default:
178 return end_this;
179 }
180 }
181
GetStartPointInterpolBeforeRev(std::vector<OrderingInfo> const & info,unsigned i)182 Point LPEEmbroderyStitch::GetStartPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i)
183 {
184 if (info[i].reverse) {
185 return GetEndPointInterpolAfterRev(info, i);
186 } else {
187 return GetStartPointInterpolAfterRev(info, i);
188 }
189 }
190
GetEndPointInterpolBeforeRev(std::vector<OrderingInfo> const & info,unsigned i)191 Point LPEEmbroderyStitch::GetEndPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i)
192 {
193 if (info[i].reverse) {
194 return GetStartPointInterpolAfterRev(info, i);
195 } else {
196 return GetEndPointInterpolAfterRev(info, i);
197 }
198 }
199
doEffect_path(PathVector const & path_in)200 PathVector LPEEmbroderyStitch::doEffect_path(PathVector const &path_in)
201 {
202 if (path_in.size() >= 2) {
203 PathVector path_out;
204
205 // Create vectors with start and end points
206 std::vector<OrderingInfo> orderinginfos(path_in.size());
207 // connect next path to this one
208 bool connect_with_previous = false;
209
210 for (PathVector::const_iterator it = path_in.begin(); it != path_in.end(); ++it) {
211 OrderingInfo &info = orderinginfos[ it - path_in.begin() ];
212 info.index = it - path_in.begin();
213 info.reverse = false;
214 info.used = false;
215 info.connect = true;
216 info.begOrig = it->front().initialPoint();
217 info.endOrig = it->back().finalPoint();
218 }
219
220 // Compute sub-path ordering
221 switch (ordering.get_value()) {
222 case order_method_no_reorder:
223 OrderingOriginal(orderinginfos);
224 break;
225
226 case order_method_zigzag:
227 OrderingZigZag(orderinginfos, false);
228 break;
229
230 case order_method_zigzag_rev_first:
231 OrderingZigZag(orderinginfos, true);
232 break;
233
234 case order_method_closest:
235 OrderingClosest(orderinginfos, false);
236 break;
237
238 case order_method_closest_rev_first:
239 OrderingClosest(orderinginfos, true);
240 break;
241
242 case order_method_tsp_kopt_2:
243 OrderingAdvanced(orderinginfos, 2);
244 break;
245
246 case order_method_tsp_kopt_3:
247 OrderingAdvanced(orderinginfos, 3);
248 break;
249
250 case order_method_tsp_kopt_4:
251 OrderingAdvanced(orderinginfos, 4);
252 break;
253
254 case order_method_tsp_kopt_5:
255 OrderingAdvanced(orderinginfos, 5);
256 break;
257
258 }
259
260 // Iterate over sub-paths in order found above
261 // Divide paths into stitches (currently always equidistant)
262 // Interpolate between neighboring paths, so that their ends coincide
263 for (std::vector<OrderingInfo>::const_iterator it = orderinginfos.begin(); it != orderinginfos.end(); ++it) {
264 // info index
265 unsigned iInfo = it - orderinginfos.begin();
266 // subpath index
267 unsigned iPath = it->index;
268 // decide of path shall be reversed
269 bool reverse = it->reverse;
270 // minimum stitch length in absolute measure
271 double stitch_min_length_abs = stitch_min_length * 0.01 * stitch_length;
272
273 // convert path to piecewise
274 Piecewise<D2<SBasis> > pwOrig = path_in[iPath].toPwSb();
275 // make piecewise equidistant in time
276 Piecewise<D2<SBasis> > pwEqdist = arc_length_parametrization(pwOrig);
277 Piecewise<D2<SBasis> > pwStitch;
278
279 // cut into stitches
280 double cutpos = 0.0;
281 Interval pwdomain = pwEqdist.domain();
282
283 // step length of first stitch
284 double step = GetPatternInitialStep(stitch_pattern, iInfo) * stitch_length;
285 if (step < stitch_min_length_abs) {
286 step += stitch_length;
287 }
288
289 bool last = false;
290 bool first = true;
291 double posnext;
292 for (double pos = pwdomain.min(); !last; pos = posnext, cutpos += 1.0) {
293 // start point
294 Point p1;
295 if (first) {
296 p1 = GetStartPointInterpolBeforeRev(orderinginfos, iInfo);
297 first = false;
298 } else {
299 p1 = pwEqdist.valueAt(pos);
300 }
301
302 // end point of this stitch
303 Point p2;
304 posnext = pos + step;
305 // last stitch is to end
306 if (posnext >= pwdomain.max() - stitch_min_length_abs) {
307 p2 = GetEndPointInterpolBeforeRev(orderinginfos, iInfo);
308 last = true;
309 } else {
310 p2 = pwEqdist.valueAt(posnext);
311 }
312
313 pwStitch.push_cut(cutpos);
314 pwStitch.push_seg(D2<SBasis>(SBasis(Linear(p1[X], p2[X])), SBasis(Linear(p1[Y], p2[Y]))));
315
316 // stitch length for all except first step
317 step = stitch_length;
318 }
319 pwStitch.push_cut(cutpos);
320
321 if (reverse) {
322 pwStitch = Geom::reverse(pwStitch);
323 }
324
325 if (it->connect && iInfo != orderinginfos.size() - 1) {
326 // Connect this segment with the previous segment by a straight line
327 Point end = pwStitch.lastValue();
328 Point start_next = GetStartPointInterpolAfterRev(orderinginfos, iInfo + 1);
329 // connect end and start point
330 if (end != start_next && distance(end, start_next) <= jump_if_longer) {
331 cutpos += 1.0;
332 pwStitch.push_seg(D2<SBasis>(SBasis(Linear(end[X], start_next[X])), SBasis(Linear(end[Y], start_next[Y]))));
333 pwStitch.push_cut(cutpos);
334 }
335 }
336
337 if (show_stitches) {
338 for (auto & seg : pwStitch.segs) {
339 // Create anew piecewise with just one segment
340 Piecewise<D2<SBasis> > pwOne;
341 pwOne.push_cut(0);
342 pwOne.push_seg(seg);
343 pwOne.push_cut(1);
344
345 // make piecewise equidistant in time
346 Piecewise<D2<SBasis> > pwOneEqdist = arc_length_parametrization(pwOne);
347 Interval pwdomain = pwOneEqdist.domain();
348
349 // Compute the points of the shortened piece
350 Coord len = pwdomain.max() - pwdomain.min();
351 Coord offs = 0.5 * (show_stitch_gap < 0.5 * len ? show_stitch_gap : 0.5 * len);
352 Point p1 = pwOneEqdist.valueAt(pwdomain.min() + offs);
353 Point p2 = pwOneEqdist.valueAt(pwdomain.max() - offs);
354 Piecewise<D2<SBasis> > pwOneGap;
355
356 // Create Linear SBasis
357 D2<SBasis> sbasis = D2<SBasis>(SBasis(Linear(p1[X], p2[X])), SBasis(Linear(p1[Y], p2[Y])));
358
359 // Convert to path and add to path list
360 Geom::Path path = path_from_sbasis(sbasis , LPE_CONVERSION_TOLERANCE, false);
361 path_out.push_back(path);
362 }
363 } else {
364 PathVector pathv = path_from_piecewise(pwStitch, LPE_CONVERSION_TOLERANCE);
365 for (const auto & ipv : pathv) {
366 if (connect_with_previous) {
367 path_out.back().append(ipv);
368 } else {
369 path_out.push_back(ipv);
370 }
371 }
372 }
373
374 connect_with_previous = it->connect;
375 }
376
377 return path_out;
378 } else {
379 return path_in;
380 }
381 }
382
383 void
resetDefaults(SPItem const * item)384 LPEEmbroderyStitch::resetDefaults(SPItem const *item)
385 {
386 Effect::resetDefaults(item);
387 }
388
389 } //namespace LivePathEffect
390 } /* namespace Inkscape */
391