← Back to branch summary

~ubuntu-branches/ubuntu/utopic/slic3r/utopic

« back to all changes in this revision

Viewing changes to xs/src/ClipperUtils.cpp

  • Committer: Package Import Robot
  • Author(s): Chow Loong Jin
  • Date: 2014-06-17 01:27:26 UTC
  • Revision ID: package-import@ubuntu.com-20140617012726-2wrs4zdo251nr4vg
Tags: upstream-1.1.4+dfsg
Import upstream version 1.1.4+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
xs/src/ClipperUtils.cpp
 
1
#include "ClipperUtils.hpp"
 
2
#include "Geometry.hpp"
 
3
 
 
4
namespace Slic3r {
 
5
 
 
6
//-----------------------------------------------------------
 
7
// legacy code from Clipper documentation
 
8
void AddOuterPolyNodeToExPolygons(ClipperLib::PolyNode& polynode, Slic3r::ExPolygons& expolygons)
 
9
{  
 
10
  size_t cnt = expolygons.size();
 
11
  expolygons.resize(cnt + 1);
 
12
  ClipperPath_to_Slic3rMultiPoint(polynode.Contour, expolygons[cnt].contour);
 
13
  expolygons[cnt].holes.resize(polynode.ChildCount());
 
14
  for (int i = 0; i < polynode.ChildCount(); ++i)
 
15
  {
 
16
    ClipperPath_to_Slic3rMultiPoint(polynode.Childs[i]->Contour, expolygons[cnt].holes[i]);
 
17
    //Add outer polygons contained by (nested within) holes ...
 
18
    for (int j = 0; j < polynode.Childs[i]->ChildCount(); ++j)
 
19
      AddOuterPolyNodeToExPolygons(*polynode.Childs[i]->Childs[j], expolygons);
 
20
  }
 
21
}
 
22
 
 
23
void PolyTreeToExPolygons(ClipperLib::PolyTree& polytree, Slic3r::ExPolygons& expolygons)
 
24
{
 
25
  expolygons.clear();
 
26
  for (int i = 0; i < polytree.ChildCount(); ++i)
 
27
    AddOuterPolyNodeToExPolygons(*polytree.Childs[i], expolygons);
 
28
}
 
29
//-----------------------------------------------------------
 
30
 
 
31
template <class T>
 
32
void
 
33
ClipperPath_to_Slic3rMultiPoint(const ClipperLib::Path &input, T &output)
 
34
{
 
35
    output.points.clear();
 
36
    for (ClipperLib::Path::const_iterator pit = input.begin(); pit != input.end(); ++pit) {
 
37
        output.points.push_back(Slic3r::Point( (*pit).X, (*pit).Y ));
 
38
    }
 
39
}
 
40
 
 
41
template <class T>
 
42
void
 
43
ClipperPaths_to_Slic3rMultiPoints(const ClipperLib::Paths &input, T &output)
 
44
{
 
45
    output.clear();
 
46
    for (ClipperLib::Paths::const_iterator it = input.begin(); it != input.end(); ++it) {
 
47
        typename T::value_type p;
 
48
        ClipperPath_to_Slic3rMultiPoint(*it, p);
 
49
        output.push_back(p);
 
50
    }
 
51
}
 
52
 
 
53
void
 
54
ClipperPaths_to_Slic3rExPolygons(const ClipperLib::Paths &input, Slic3r::ExPolygons &output)
 
55
{
 
56
    // init Clipper
 
57
    ClipperLib::Clipper clipper;
 
58
    clipper.Clear();
 
59
    
 
60
    // perform union
 
61
    clipper.AddPaths(input, ClipperLib::ptSubject, true);
 
62
    ClipperLib::PolyTree polytree;
 
63
    clipper.Execute(ClipperLib::ctUnion, polytree, ClipperLib::pftEvenOdd, ClipperLib::pftEvenOdd);  // offset results work with both EvenOdd and NonZero
 
64
    
 
65
    // write to ExPolygons object
 
66
    output.clear();
 
67
    PolyTreeToExPolygons(polytree, output);
 
68
}
 
69
 
 
70
void
 
71
Slic3rMultiPoint_to_ClipperPath(const Slic3r::MultiPoint &input, ClipperLib::Path &output)
 
72
{
 
73
    output.clear();
 
74
    for (Slic3r::Points::const_iterator pit = input.points.begin(); pit != input.points.end(); ++pit) {
 
75
        output.push_back(ClipperLib::IntPoint( (*pit).x, (*pit).y ));
 
76
    }
 
77
}
 
78
 
 
79
template <class T>
 
80
void
 
81
Slic3rMultiPoints_to_ClipperPaths(const T &input, ClipperLib::Paths &output)
 
82
{
 
83
    output.clear();
 
84
    for (typename T::const_iterator it = input.begin(); it != input.end(); ++it) {
 
85
        ClipperLib::Path p;
 
86
        Slic3rMultiPoint_to_ClipperPath(*it, p);
 
87
        output.push_back(p);
 
88
    }
 
89
}
 
90
 
 
91
void
 
92
scaleClipperPolygons(ClipperLib::Paths &polygons, const double scale)
 
93
{
 
94
    for (ClipperLib::Paths::iterator it = polygons.begin(); it != polygons.end(); ++it) {
 
95
        for (ClipperLib::Path::iterator pit = (*it).begin(); pit != (*it).end(); ++pit) {
 
96
            (*pit).X *= scale;
 
97
            (*pit).Y *= scale;
 
98
        }
 
99
    }
 
100
}
 
101
 
 
102
void
 
103
offset(const Slic3r::Polygons &polygons, ClipperLib::Paths &retval, const float delta,
 
104
    double scale, ClipperLib::JoinType joinType, double miterLimit)
 
105
{
 
106
    // read input
 
107
    ClipperLib::Paths input;
 
108
    Slic3rMultiPoints_to_ClipperPaths(polygons, input);
 
109
    
 
110
    // scale input
 
111
    scaleClipperPolygons(input, scale);
 
112
    
 
113
    // perform offset
 
114
    ClipperLib::ClipperOffset co;
 
115
    if (joinType == jtRound) {
 
116
        co.ArcTolerance = miterLimit;
 
117
    } else {
 
118
        co.MiterLimit = miterLimit;
 
119
    }
 
120
    co.AddPaths(input, joinType, ClipperLib::etClosedPolygon);
 
121
    co.Execute(retval, (delta*scale));
 
122
    
 
123
    // unscale output
 
124
    scaleClipperPolygons(retval, 1/scale);
 
125
}
 
126
 
 
127
void
 
128
offset(const Slic3r::Polygons &polygons, Slic3r::Polygons &retval, const float delta,
 
129
    double scale, ClipperLib::JoinType joinType, double miterLimit)
 
130
{
 
131
    // perform offset
 
132
    ClipperLib::Paths output;
 
133
    offset(polygons, output, delta, scale, joinType, miterLimit);
 
134
    
 
135
    // convert into ExPolygons
 
136
    ClipperPaths_to_Slic3rMultiPoints(output, retval);
 
137
}
 
138
 
 
139
void
 
140
offset(const Slic3r::Polylines &polylines, ClipperLib::Paths &retval, const float delta,
 
141
    double scale, ClipperLib::JoinType joinType, double miterLimit)
 
142
{
 
143
    // read input
 
144
    ClipperLib::Paths input;
 
145
    Slic3rMultiPoints_to_ClipperPaths(polylines, input);
 
146
    
 
147
    // scale input
 
148
    scaleClipperPolygons(input, scale);
 
149
    
 
150
    // perform offset
 
151
    ClipperLib::ClipperOffset co;
 
152
    if (joinType == jtRound) {
 
153
        co.ArcTolerance = miterLimit;
 
154
    } else {
 
155
        co.MiterLimit = miterLimit;
 
156
    }
 
157
    co.AddPaths(input, joinType, ClipperLib::etOpenButt);
 
158
    co.Execute(retval, (delta*scale));
 
159
    
 
160
    // unscale output
 
161
    scaleClipperPolygons(retval, 1/scale);
 
162
}
 
163
 
 
164
void
 
165
offset(const Slic3r::Polylines &polylines, Slic3r::Polygons &retval, const float delta,
 
166
    double scale, ClipperLib::JoinType joinType, double miterLimit)
 
167
{
 
168
    // perform offset
 
169
    ClipperLib::Paths output;
 
170
    offset(polylines, output, delta, scale, joinType, miterLimit);
 
171
    
 
172
    // convert into ExPolygons
 
173
    ClipperPaths_to_Slic3rMultiPoints(output, retval);
 
174
}
 
175
 
 
176
void
 
177
offset(const Slic3r::Surface &surface, Slic3r::Surfaces &retval, const float delta,
 
178
    double scale, ClipperLib::JoinType joinType, double miterLimit)
 
179
{
 
180
    // perform offset
 
181
    Slic3r::ExPolygons expp;
 
182
    offset_ex(surface.expolygon, expp, delta, scale, joinType, miterLimit);
 
183
    
 
184
    // clone the input surface for each expolygon we got
 
185
    retval.clear();
 
186
    retval.reserve(expp.size());
 
187
    for (ExPolygons::iterator it = expp.begin(); it != expp.end(); ++it) {
 
188
        Surface s = surface;  // clone
 
189
        s.expolygon = *it;
 
190
        retval.push_back(s);
 
191
    }
 
192
}
 
193
 
 
194
void
 
195
offset_ex(const Slic3r::Polygons &polygons, Slic3r::ExPolygons &retval, const float delta,
 
196
    double scale, ClipperLib::JoinType joinType, double miterLimit)
 
197
{
 
198
    // perform offset
 
199
    ClipperLib::Paths output;
 
200
    offset(polygons, output, delta, scale, joinType, miterLimit);
 
201
    
 
202
    // convert into ExPolygons
 
203
    ClipperPaths_to_Slic3rExPolygons(output, retval);
 
204
}
 
205
 
 
206
void
 
207
offset2(const Slic3r::Polygons &polygons, ClipperLib::Paths &retval, const float delta1,
 
208
    const float delta2, const double scale, const ClipperLib::JoinType joinType, const double miterLimit)
 
209
{
 
210
    // read input
 
211
    ClipperLib::Paths input;
 
212
    Slic3rMultiPoints_to_ClipperPaths(polygons, input);
 
213
    
 
214
    // scale input
 
215
    scaleClipperPolygons(input, scale);
 
216
    
 
217
    // prepare ClipperOffset object
 
218
    ClipperLib::ClipperOffset co;
 
219
    if (joinType == jtRound) {
 
220
        co.ArcTolerance = miterLimit;
 
221
    } else {
 
222
        co.MiterLimit = miterLimit;
 
223
    }
 
224
    
 
225
    // perform first offset
 
226
    ClipperLib::Paths output1;
 
227
    co.AddPaths(input, joinType, ClipperLib::etClosedPolygon);
 
228
    co.Execute(output1, (delta1*scale));
 
229
    
 
230
    // perform second offset
 
231
    co.Clear();
 
232
    co.AddPaths(output1, joinType, ClipperLib::etClosedPolygon);
 
233
    co.Execute(retval, (delta2*scale));
 
234
    
 
235
    // unscale output
 
236
    scaleClipperPolygons(retval, 1/scale);
 
237
}
 
238
 
 
239
void
 
240
offset2(const Slic3r::Polygons &polygons, Slic3r::Polygons &retval, const float delta1,
 
241
    const float delta2, const double scale, const ClipperLib::JoinType joinType, const double miterLimit)
 
242
{
 
243
    // perform offset
 
244
    ClipperLib::Paths output;
 
245
    offset2(polygons, output, delta1, delta2, scale, joinType, miterLimit);
 
246
    
 
247
    // convert into ExPolygons
 
248
    ClipperPaths_to_Slic3rMultiPoints(output, retval);
 
249
}
 
250
 
 
251
void
 
252
offset2_ex(const Slic3r::Polygons &polygons, Slic3r::ExPolygons &retval, const float delta1,
 
253
    const float delta2, const double scale, const ClipperLib::JoinType joinType, const double miterLimit)
 
254
{
 
255
    // perform offset
 
256
    ClipperLib::Paths output;
 
257
    offset2(polygons, output, delta1, delta2, scale, joinType, miterLimit);
 
258
    
 
259
    // convert into ExPolygons
 
260
    ClipperPaths_to_Slic3rExPolygons(output, retval);
 
261
}
 
262
 
 
263
template <class T>
 
264
void _clipper_do(const ClipperLib::ClipType clipType, const Slic3r::Polygons &subject, 
 
265
    const Slic3r::Polygons &clip, T &retval, const ClipperLib::PolyFillType fillType, const bool safety_offset_)
 
266
{
 
267
    // read input
 
268
    ClipperLib::Paths input_subject, input_clip;
 
269
    Slic3rMultiPoints_to_ClipperPaths(subject, input_subject);
 
270
    Slic3rMultiPoints_to_ClipperPaths(clip,    input_clip);
 
271
    
 
272
    // perform safety offset
 
273
    if (safety_offset_) {
 
274
        if (clipType == ClipperLib::ctUnion) {
 
275
            safety_offset(&input_subject);
 
276
        } else {
 
277
            safety_offset(&input_clip);
 
278
        }
 
279
    }
 
280
    
 
281
    // init Clipper
 
282
    ClipperLib::Clipper clipper;
 
283
    clipper.Clear();
 
284
    
 
285
    // add polygons
 
286
    clipper.AddPaths(input_subject, ClipperLib::ptSubject, true);
 
287
    clipper.AddPaths(input_clip, ClipperLib::ptClip, true);
 
288
    
 
289
    // perform operation
 
290
    clipper.Execute(clipType, retval, fillType, fillType);
 
291
}
 
292
 
 
293
void _clipper_do(const ClipperLib::ClipType clipType, const Slic3r::Polylines &subject, 
 
294
    const Slic3r::Polygons &clip, ClipperLib::PolyTree &retval, const ClipperLib::PolyFillType fillType,
 
295
    const bool safety_offset_)
 
296
{
 
297
    // read input
 
298
    ClipperLib::Paths input_subject, input_clip;
 
299
    Slic3rMultiPoints_to_ClipperPaths(subject, input_subject);
 
300
    Slic3rMultiPoints_to_ClipperPaths(clip,    input_clip);
 
301
    
 
302
    // perform safety offset
 
303
    if (safety_offset_) safety_offset(&input_clip);
 
304
    
 
305
    // init Clipper
 
306
    ClipperLib::Clipper clipper;
 
307
    clipper.Clear();
 
308
    
 
309
    // add polygons
 
310
    clipper.AddPaths(input_subject, ClipperLib::ptSubject, false);
 
311
    clipper.AddPaths(input_clip,    ClipperLib::ptClip,    true);
 
312
    
 
313
    // perform operation
 
314
    clipper.Execute(clipType, retval, fillType, fillType);
 
315
}
 
316
 
 
317
void _clipper(ClipperLib::ClipType clipType, const Slic3r::Polygons &subject, 
 
318
    const Slic3r::Polygons &clip, Slic3r::Polygons &retval, bool safety_offset_)
 
319
{
 
320
    // perform operation
 
321
    ClipperLib::Paths output;
 
322
    _clipper_do<ClipperLib::Paths>(clipType, subject, clip, output, ClipperLib::pftNonZero, safety_offset_);
 
323
    
 
324
    // convert into Polygons
 
325
    ClipperPaths_to_Slic3rMultiPoints(output, retval);
 
326
}
 
327
 
 
328
void _clipper(ClipperLib::ClipType clipType, const Slic3r::Polygons &subject, 
 
329
    const Slic3r::Polygons &clip, Slic3r::ExPolygons &retval, bool safety_offset_)
 
330
{
 
331
    // perform operation
 
332
    ClipperLib::PolyTree polytree;
 
333
    _clipper_do<ClipperLib::PolyTree>(clipType, subject, clip, polytree, ClipperLib::pftNonZero, safety_offset_);
 
334
    
 
335
    // convert into ExPolygons
 
336
    PolyTreeToExPolygons(polytree, retval);
 
337
}
 
338
 
 
339
void _clipper(ClipperLib::ClipType clipType, const Slic3r::Polylines &subject, 
 
340
    const Slic3r::Polygons &clip, Slic3r::Polylines &retval, bool safety_offset_)
 
341
{
 
342
    // perform operation
 
343
    ClipperLib::PolyTree polytree;
 
344
    _clipper_do(clipType, subject, clip, polytree, ClipperLib::pftNonZero, safety_offset_);
 
345
    
 
346
    // convert into Polylines
 
347
    ClipperLib::Paths output;
 
348
    ClipperLib::PolyTreeToPaths(polytree, output);
 
349
    ClipperPaths_to_Slic3rMultiPoints(output, retval);
 
350
}
 
351
 
 
352
void _clipper(ClipperLib::ClipType clipType, const Slic3r::Polygons &subject, 
 
353
    const Slic3r::Polygons &clip, Slic3r::Polylines &retval, bool safety_offset_)
 
354
{
 
355
    // transform input polygons into polylines
 
356
    Slic3r::Polylines polylines;
 
357
    polylines.reserve(subject.size());
 
358
    for (Slic3r::Polygons::const_iterator polygon = subject.begin(); polygon != subject.end(); ++polygon)
 
359
        polylines.push_back(*polygon);  // implicit call to split_at_first_point()
 
360
    
 
361
    // perform clipping
 
362
    _clipper(clipType, polylines, clip, retval, safety_offset_);
 
363
    
 
364
    /* If the split_at_first_point() call above happens to split the polygon inside the clipping area
 
365
       we would get two consecutive polylines instead of a single one, so we go through them in order
 
366
       to recombine continuous polylines. */
 
367
    for (size_t i = 0; i < retval.size(); ++i) {
 
368
        for (size_t j = i+1; j < retval.size(); ++j) {
 
369
            if (retval[i].points.back().coincides_with(retval[j].points.front())) {
 
370
                /* If last point of i coincides with first point of j,
 
371
                   append points of j to i and delete j */
 
372
                retval[i].points.insert(retval[i].points.end(), retval[j].points.begin()+1, retval[j].points.end());
 
373
                retval.erase(retval.begin() + j);
 
374
                --j;
 
375
            } else if (retval[i].points.front().coincides_with(retval[j].points.back())) {
 
376
                /* If first point of i coincides with last point of j,
 
377
                   prepend points of j to i and delete j */
 
378
                retval[i].points.insert(retval[i].points.begin(), retval[j].points.begin(), retval[j].points.end()-1);
 
379
                retval.erase(retval.begin() + j);
 
380
                --j;
 
381
            } else if (retval[i].points.front().coincides_with(retval[j].points.front())) {
 
382
                /* Since Clipper does not preserve orientation of polylines, 
 
383
                   also check the case when first point of i coincides with first point of j. */
 
384
                retval[j].reverse();
 
385
                retval[i].points.insert(retval[i].points.begin(), retval[j].points.begin(), retval[j].points.end()-1);
 
386
                retval.erase(retval.begin() + j);
 
387
                --j;
 
388
            } else if (retval[i].points.back().coincides_with(retval[j].points.back())) {
 
389
                /* Since Clipper does not preserve orientation of polylines, 
 
390
                   also check the case when last point of i coincides with last point of j. */
 
391
                retval[j].reverse();
 
392
                retval[i].points.insert(retval[i].points.end(), retval[j].points.begin()+1, retval[j].points.end());
 
393
                retval.erase(retval.begin() + j);
 
394
                --j;
 
395
            }
 
396
        }
 
397
    }   
 
398
}
 
399
 
 
400
template <class SubjectType, class ResultType>
 
401
void diff(const SubjectType &subject, const Slic3r::Polygons &clip, ResultType &retval, bool safety_offset_)
 
402
{
 
403
    _clipper(ClipperLib::ctDifference, subject, clip, retval, safety_offset_);
 
404
}
 
405
template void diff<Slic3r::Polygons, Slic3r::ExPolygons>(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, Slic3r::ExPolygons &retval, bool safety_offset_);
 
406
template void diff<Slic3r::Polygons, Slic3r::Polygons>(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, Slic3r::Polygons &retval, bool safety_offset_);
 
407
template void diff<Slic3r::Polygons, Slic3r::Polylines>(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, Slic3r::Polylines &retval, bool safety_offset_);
 
408
template void diff<Slic3r::Polylines, Slic3r::Polylines>(const Slic3r::Polylines &subject, const Slic3r::Polygons &clip, Slic3r::Polylines &retval, bool safety_offset_);
 
409
 
 
410
template <class SubjectType, class ResultType>
 
411
void intersection(const SubjectType &subject, const Slic3r::Polygons &clip, ResultType &retval, bool safety_offset_)
 
412
{
 
413
    _clipper(ClipperLib::ctIntersection, subject, clip, retval, safety_offset_);
 
414
}
 
415
template void intersection<Slic3r::Polygons, Slic3r::ExPolygons>(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, Slic3r::ExPolygons &retval, bool safety_offset_);
 
416
template void intersection<Slic3r::Polygons, Slic3r::Polygons>(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, Slic3r::Polygons &retval, bool safety_offset_);
 
417
template void intersection<Slic3r::Polygons, Slic3r::Polylines>(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, Slic3r::Polylines &retval, bool safety_offset_);
 
418
template void intersection<Slic3r::Polylines, Slic3r::Polylines>(const Slic3r::Polylines &subject, const Slic3r::Polygons &clip, Slic3r::Polylines &retval, bool safety_offset_);
 
419
 
 
420
void xor_ex(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, Slic3r::ExPolygons &retval, 
 
421
    bool safety_offset_)
 
422
{
 
423
    _clipper(ClipperLib::ctXor, subject, clip, retval, safety_offset_);
 
424
}
 
425
 
 
426
template <class T>
 
427
void union_(const Slic3r::Polygons &subject, T &retval, bool safety_offset_)
 
428
{
 
429
    Slic3r::Polygons p;
 
430
    _clipper(ClipperLib::ctUnion, subject, p, retval, safety_offset_);
 
431
}
 
432
template void union_<Slic3r::ExPolygons>(const Slic3r::Polygons &subject, Slic3r::ExPolygons &retval, bool safety_offset_);
 
433
template void union_<Slic3r::Polygons>(const Slic3r::Polygons &subject, Slic3r::Polygons &retval, bool safety_offset_);
 
434
 
 
435
void union_pt(const Slic3r::Polygons &subject, ClipperLib::PolyTree &retval, bool safety_offset_)
 
436
{
 
437
    Slic3r::Polygons clip;
 
438
    _clipper_do<ClipperLib::PolyTree>(ClipperLib::ctUnion, subject, clip, retval, ClipperLib::pftEvenOdd, safety_offset_);
 
439
}
 
440
 
 
441
void union_pt_chained(const Slic3r::Polygons &subject, Slic3r::Polygons &retval, bool safety_offset_)
 
442
{
 
443
    ClipperLib::PolyTree pt;
 
444
    union_pt(subject, pt, safety_offset_);
 
445
    traverse_pt(pt.Childs, retval);
 
446
}
 
447
 
 
448
static void traverse_pt(ClipperLib::PolyNodes &nodes, Slic3r::Polygons &retval)
 
449
{
 
450
    /* use a nearest neighbor search to order these children
 
451
       TODO: supply start_near to chained_path() too? */
 
452
    
 
453
    // collect ordering points
 
454
    Points ordering_points;
 
455
    ordering_points.reserve(nodes.size());
 
456
    for (ClipperLib::PolyNodes::const_iterator it = nodes.begin(); it != nodes.end(); ++it) {
 
457
        Point p((*it)->Contour.front().X, (*it)->Contour.front().Y);
 
458
        ordering_points.push_back(p);
 
459
    }
 
460
    
 
461
    // perform the ordering
 
462
    ClipperLib::PolyNodes ordered_nodes;
 
463
    Slic3r::Geometry::chained_path_items(ordering_points, nodes, ordered_nodes);
 
464
    
 
465
    // push results recursively
 
466
    for (ClipperLib::PolyNodes::iterator it = ordered_nodes.begin(); it != ordered_nodes.end(); ++it) {
 
467
        // traverse the next depth
 
468
        traverse_pt((*it)->Childs, retval);
 
469
        
 
470
        Polygon p;
 
471
        ClipperPath_to_Slic3rMultiPoint((*it)->Contour, p);
 
472
        retval.push_back(p);
 
473
        if ((*it)->IsHole()) retval.back().reverse();  // ccw
 
474
    }
 
475
}
 
476
 
 
477
void simplify_polygons(const Slic3r::Polygons &subject, Slic3r::Polygons &retval, bool preserve_collinear)
 
478
{
 
479
    // convert into Clipper polygons
 
480
    ClipperLib::Paths input_subject, output;
 
481
    Slic3rMultiPoints_to_ClipperPaths(subject, input_subject);
 
482
    
 
483
    if (preserve_collinear) {
 
484
        ClipperLib::Clipper c;
 
485
        c.PreserveCollinear(true);
 
486
        c.StrictlySimple(true);
 
487
        c.AddPaths(input_subject, ClipperLib::ptSubject, true);
 
488
        c.Execute(ClipperLib::ctUnion, output, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
 
489
    } else {
 
490
        ClipperLib::SimplifyPolygons(input_subject, output, ClipperLib::pftNonZero);
 
491
    }
 
492
    
 
493
    // convert into Slic3r polygons
 
494
    ClipperPaths_to_Slic3rMultiPoints(output, retval);
 
495
}
 
496
 
 
497
void simplify_polygons(const Slic3r::Polygons &subject, Slic3r::ExPolygons &retval, bool preserve_collinear)
 
498
{
 
499
    if (!preserve_collinear) {
 
500
        Polygons polygons;
 
501
        simplify_polygons(subject, polygons, preserve_collinear);
 
502
        union_(polygons, retval);
 
503
        return;
 
504
    }
 
505
    
 
506
    // convert into Clipper polygons
 
507
    ClipperLib::Paths input_subject;
 
508
    Slic3rMultiPoints_to_ClipperPaths(subject, input_subject);
 
509
    
 
510
    ClipperLib::PolyTree polytree;
 
511
    
 
512
    ClipperLib::Clipper c;
 
513
    c.PreserveCollinear(true);
 
514
    c.StrictlySimple(true);
 
515
    c.AddPaths(input_subject, ClipperLib::ptSubject, true);
 
516
    c.Execute(ClipperLib::ctUnion, polytree, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
 
517
    
 
518
    // convert into ExPolygons
 
519
    PolyTreeToExPolygons(polytree, retval);
 
520
}
 
521
 
 
522
void safety_offset(ClipperLib::Paths* paths)
 
523
{
 
524
    // scale input
 
525
    scaleClipperPolygons(*paths, CLIPPER_OFFSET_SCALE);
 
526
    
 
527
    // perform offset (delta = scale 1e-05)
 
528
    ClipperLib::ClipperOffset co;
 
529
    co.MiterLimit = 2;
 
530
    co.AddPaths(*paths, ClipperLib::jtMiter, ClipperLib::etClosedPolygon);
 
531
    co.Execute(*paths, 10.0 * CLIPPER_OFFSET_SCALE);
 
532
    
 
533
    // unscale output
 
534
    scaleClipperPolygons(*paths, 1.0/CLIPPER_OFFSET_SCALE);
 
535
}
 
536
 
 
537
///////////////////////
 
538
 
 
539
#ifdef SLIC3RXS
 
540
SV*
 
541
polynode_children_2_perl(const ClipperLib::PolyNode& node)
 
542
{
 
543
    AV* av = newAV();
 
544
    const unsigned int len = node.ChildCount();
 
545
    av_extend(av, len-1);
 
546
    for (int i = 0; i < len; ++i) {
 
547
        av_store(av, i, polynode2perl(*node.Childs[i]));
 
548
    }
 
549
    return (SV*)newRV_noinc((SV*)av);
 
550
}
 
551
 
 
552
SV*
 
553
polynode2perl(const ClipperLib::PolyNode& node)
 
554
{
 
555
    HV* hv = newHV();
 
556
    Slic3r::Polygon p;
 
557
    ClipperPath_to_Slic3rMultiPoint(node.Contour, p);
 
558
    if (node.IsHole()) {
 
559
        (void)hv_stores( hv, "hole", Slic3r::perl_to_SV_clone_ref(p) );
 
560
    } else {
 
561
        (void)hv_stores( hv, "outer", Slic3r::perl_to_SV_clone_ref(p) );
 
562
    }
 
563
    (void)hv_stores( hv, "children", polynode_children_2_perl(node) );
 
564
    return (SV*)newRV_noinc((SV*)hv);
 
565
}
 
566
#endif
 
567
 
 
568
}