Implemented utility functions to operate over lines, polylines, polygons,

surfaces.

13 files changed, 483 insertions, 54 deletions

diff --git a/xs/src/libslic3r/BoundingBox.hpp b/xs/src/libslic3r/BoundingBox.hpp
index ac52129e1..5f676151c 100644
--- a/xs/src/libslic3r/BoundingBox.hpp
+++ b/xs/src/libslic3r/BoundingBox.hpp
@@ -70,6 +70,8 @@ class BoundingBox : public BoundingBoxBase<Point>
     BoundingBox(const Point &pmin, const Point &pmax) : BoundingBoxBase<Point>(pmin, pmax) {};
     BoundingBox(const Points &points) : BoundingBoxBase<Point>(points) {};
     BoundingBox(const Lines &lines);
+
+    friend BoundingBox get_extents_rotated(const Points &points, double angle);
 };
 
 /*
diff --git a/xs/src/libslic3r/ClipperUtils.cpp b/xs/src/libslic3r/ClipperUtils.cpp
index f68610849..04357b15a 100644
--- a/xs/src/libslic3r/ClipperUtils.cpp
+++ b/xs/src/libslic3r/ClipperUtils.cpp
@@ -314,6 +314,113 @@ Slic3r::Polygons offset(const Slic3r::ExPolygon &expolygon, const float delta,
     return retval;
 }
 
+Slic3r::ExPolygons offset_ex(const Slic3r::ExPolygon &expolygon, const float delta,
+    double scale, ClipperLib::JoinType joinType, double miterLimit)
+{
+    // perform offset
+    ClipperLib::Paths output;
+    offset(expolygon, &output, delta, scale, joinType, miterLimit);
+    
+    // convert into ExPolygons
+    Slic3r::ExPolygons retval;
+    ClipperPaths_to_Slic3rExPolygons(output, &retval);
+    return retval;
+}
+
+// This is a safe variant of the polygon offset, tailored for a single ExPolygon:
+// a single polygon with multiple non-overlapping holes.
+// Each contour and hole is offsetted separately, then the holes are subtracted from the outer contours.
+void offset(const Slic3r::ExPolygons &expolygons, ClipperLib::Paths* retval, const float delta,
+    double scale, ClipperLib::JoinType joinType, double miterLimit)
+{
+//    printf("new ExPolygon offset\n");
+    const float delta_scaled = float(delta * scale);
+    ClipperLib::Paths contours;
+    ClipperLib::Paths holes;
+    contours.reserve(expolygons.size());
+    {
+        size_t n_holes = 0;
+        for (size_t i = 0; i < expolygons.size(); ++ i)
+            n_holes += expolygons[i].holes.size();
+        holes.reserve(n_holes);
+    }
+
+    for (Slic3r::ExPolygons::const_iterator it_expoly = expolygons.begin(); it_expoly != expolygons.end(); ++ it_expoly) {
+        // 1) Offset the outer contour.
+        {
+            ClipperLib::Path input;
+            Slic3rMultiPoint_to_ClipperPath(it_expoly->contour, &input);
+            scaleClipperPolygon(input, scale);
+            ClipperLib::ClipperOffset co;
+            if (joinType == jtRound)
+                co.ArcTolerance = miterLimit;
+            else
+                co.MiterLimit = miterLimit;
+            co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
+            ClipperLib::Paths out;
+            co.Execute(out, delta_scaled);
+            contours.insert(contours.end(), out.begin(), out.end());
+        }
+
+        // 2) Offset the holes one by one, collect the results.
+        {
+            for (Polygons::const_iterator it_hole = it_expoly->holes.begin(); it_hole != it_expoly->holes.end(); ++ it_hole) {
+                ClipperLib::Path input;
+                Slic3rMultiPoint_to_ClipperPath_reversed(*it_hole, &input);
+                scaleClipperPolygon(input, scale);
+                ClipperLib::ClipperOffset co;
+                if (joinType == jtRound)
+                    co.ArcTolerance = miterLimit;
+                else
+                    co.MiterLimit = miterLimit;
+                co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
+                ClipperLib::Paths out;
+                co.Execute(out, - delta_scaled);
+                holes.insert(holes.end(), out.begin(), out.end());
+            }
+        }
+    }
+
+    // 3) Subtract holes from the contours.
+    ClipperLib::Paths output;
+    {
+        ClipperLib::Clipper clipper;
+        clipper.Clear();
+        clipper.AddPaths(contours, ClipperLib::ptSubject, true);
+        clipper.AddPaths(holes, ClipperLib::ptClip, true);
+        clipper.Execute(ClipperLib::ctDifference, *retval, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
+    }
+    
+    // 4) Unscale the output.
+    scaleClipperPolygons(*retval, 1/scale);
+}
+
+Slic3r::Polygons offset(const Slic3r::ExPolygons &expolygons, const float delta,
+    double scale, ClipperLib::JoinType joinType, double miterLimit)
+{
+    // perform offset
+    ClipperLib::Paths output;
+    offset(expolygons, &output, delta, scale, joinType, miterLimit);
+    
+    // convert into ExPolygons
+    Slic3r::Polygons retval;
+    ClipperPaths_to_Slic3rMultiPoints(output, &retval);
+    return retval;
+}
+
+Slic3r::ExPolygons offset_ex(const Slic3r::ExPolygons &expolygons, const float delta,
+    double scale, ClipperLib::JoinType joinType, double miterLimit)
+{
+    // perform offset
+    ClipperLib::Paths output;
+    offset(expolygons, &output, delta, scale, joinType, miterLimit);
+    
+    // convert into ExPolygons
+    Slic3r::ExPolygons retval;
+    ClipperPaths_to_Slic3rExPolygons(output, &retval);
+    return retval;
+}
+
 Slic3r::ExPolygons
 offset_ex(const Slic3r::Polygons &polygons, const float delta,
     double scale, ClipperLib::JoinType joinType, double miterLimit)
diff --git a/xs/src/libslic3r/ClipperUtils.hpp b/xs/src/libslic3r/ClipperUtils.hpp
index 00b7a56a7..2bb58bdf6 100644
--- a/xs/src/libslic3r/ClipperUtils.hpp
+++ b/xs/src/libslic3r/ClipperUtils.hpp
@@ -55,9 +55,19 @@ Slic3r::Polygons offset(const Slic3r::Polygons &polygons, const float delta,
 void offset(const Slic3r::ExPolygon &expolygon, ClipperLib::Paths* retval, const float delta,
     double scale = CLIPPER_OFFSET_SCALE, ClipperLib::JoinType joinType = ClipperLib::jtMiter,
     double miterLimit = 3);
+void offset(const Slic3r::ExPolygons &expolygons, ClipperLib::Paths* retval, const float delta,
+    double scale = CLIPPER_OFFSET_SCALE, ClipperLib::JoinType joinType = ClipperLib::jtMiter,
+    double miterLimit = 3);
 Slic3r::Polygons offset(const Slic3r::ExPolygon &expolygon, const float delta,
     double scale = CLIPPER_OFFSET_SCALE, ClipperLib::JoinType joinType = ClipperLib::jtMiter,
     double miterLimit = 3);
+Slic3r::Polygons offset(const Slic3r::ExPolygons &expolygons, const float delta,
+    double scale = CLIPPER_OFFSET_SCALE, ClipperLib::JoinType joinType = ClipperLib::jtMiter,
+    double miterLimit = 3);
+Slic3r::ExPolygons offset_ex(const Slic3r::ExPolygon &expolygon, const float delta,
+    double scale, ClipperLib::JoinType joinType, double miterLimit);
+Slic3r::ExPolygons offset_ex(const Slic3r::ExPolygons &expolygons, const float delta,
+    double scale, ClipperLib::JoinType joinType, double miterLimit);
 
 // offset Polylines
 void offset(const Slic3r::Polylines &polylines, ClipperLib::Paths* retval, const float delta,
diff --git a/xs/src/libslic3r/ExPolygon.cpp b/xs/src/libslic3r/ExPolygon.cpp
index 71f90179a..f37e2e701 100644
--- a/xs/src/libslic3r/ExPolygon.cpp
+++ b/xs/src/libslic3r/ExPolygon.cpp
@@ -26,24 +26,12 @@ ExPolygon::operator Points() const
 
 ExPolygon::operator Polygons() const
 {
-    Polygons polygons;
-    polygons.reserve(this->holes.size() + 1);
-    polygons.push_back(this->contour);
-    for (Polygons::const_iterator it = this->holes.begin(); it != this->holes.end(); ++it) {
-        polygons.push_back(*it);
-    }
-    return polygons;
+    return to_polygons(*this);
 }
 
 ExPolygon::operator Polylines() const
 {
-    Polylines polylines;
-    polylines.reserve(this->holes.size() + 1);
-    polylines.push_back((Polyline)this->contour);
-    for (Polygons::const_iterator it = this->holes.begin(); it != this->holes.end(); ++it) {
-        polylines.push_back((Polyline)*it);
-    }
-    return polylines;
+    return to_polylines(*this);
 }
 
 void
@@ -583,6 +571,22 @@ BoundingBox get_extents(const ExPolygons &expolygons)
     return bbox;
 }
 
+BoundingBox get_extents_rotated(const ExPolygon &expolygon, double angle)
+{
+    return get_extents_rotated(expolygon.contour, angle);
+}
+
+BoundingBox get_extents_rotated(const ExPolygons &expolygons, double angle)
+{
+    BoundingBox bbox;
+    if (! expolygons.empty()) {
+        bbox = get_extents_rotated(expolygons.front().contour, angle);
+        for (size_t i = 1; i < expolygons.size(); ++ i)
+            bbox.merge(get_extents_rotated(expolygons[i].contour, angle));
+    }
+    return bbox;
+}
+
 bool remove_sticks(ExPolygon &poly)
 {
     return remove_sticks(poly.contour) || remove_sticks(poly.holes);
diff --git a/xs/src/libslic3r/ExPolygon.hpp b/xs/src/libslic3r/ExPolygon.hpp
index f3a6a99eb..c1204a953 100644
--- a/xs/src/libslic3r/ExPolygon.hpp
+++ b/xs/src/libslic3r/ExPolygon.hpp
@@ -25,6 +25,7 @@ class ExPolygon
     void rotate(double angle);
     void rotate(double angle, const Point &center);
     double area() const;
+    bool empty() const { return contour.points.empty(); }
     bool is_valid() const;
 
     // Contains the line / polyline / polylines etc COMPLETELY.
@@ -57,43 +58,174 @@ class ExPolygon
     std::string dump_perl() const;
 };
 
+// Count a nuber of polygons stored inside the vector of expolygons.
+// Useful for allocating space for polygons when converting expolygons to polygons.
+inline size_t number_polygons(const ExPolygons &expolys)
+{
+    size_t n_polygons = 0;
+    for (ExPolygons::const_iterator it = expolys.begin(); it != expolys.end(); ++ it)
+        n_polygons += it->holes.size() + 1;
+    return n_polygons;
+}
+
+inline Lines to_lines(const ExPolygon &src) 
+{
+    size_t n_lines = src.contour.points.size();
+    for (size_t i = 0; i < src.holes.size(); ++ i)
+        n_lines += src.holes[i].points.size();
+    Lines lines;
+    lines.reserve(n_lines);
+    for (size_t i = 0; i <= src.holes.size(); ++ i) {
+        const Polygon &poly = (i == 0) ? src.contour : src.holes[i - 1];
+        for (Points::const_iterator it = poly.points.begin(); it != poly.points.end()-1; ++it)
+            lines.push_back(Line(*it, *(it + 1)));
+        lines.push_back(Line(poly.points.back(), poly.points.front()));
+    }
+    return lines;
+}
+
+inline Lines to_lines(const ExPolygons &src) 
+{
+    size_t n_lines = 0;
+    for (ExPolygons::const_iterator it_expoly = src.begin(); it_expoly != src.end(); ++ it_expoly) {
+        n_lines += it_expoly->contour.points.size();
+        for (size_t i = 0; i < it_expoly->holes.size(); ++ i)
+            n_lines += it_expoly->holes[i].points.size();
+    }
+    Lines lines;
+    lines.reserve(n_lines);
+    for (ExPolygons::const_iterator it_expoly = src.begin(); it_expoly != src.end(); ++ it_expoly) {
+        for (size_t i = 0; i <= it_expoly->holes.size(); ++ i) {
+            const Points &points = ((i == 0) ? it_expoly->contour : it_expoly->holes[i - 1]).points;
+            for (Points::const_iterator it = points.begin(); it != points.end()-1; ++it)
+                lines.push_back(Line(*it, *(it + 1)));
+            lines.push_back(Line(points.back(), points.front()));
+        }
+    }
+    return lines;
+}
+
+inline Polylines to_polylines(const ExPolygon &src)
+{
+    Polylines polylines;
+    polylines.assign(src.holes.size() + 1, Polyline());
+    size_t idx = 0;
+    Polyline &pl = polylines[idx ++];
+    pl.points = src.contour.points;
+    pl.points.push_back(pl.points.front());
+    for (Polygons::const_iterator ith = src.holes.begin(); ith != src.holes.end(); ++ith) {
+        Polyline &pl = polylines[idx ++];
+        pl.points = ith->points;
+        pl.points.push_back(ith->points.front());
+    }
+    assert(idx == polylines.size());
+    return polylines;
+}
+
+inline Polylines to_polylines(const ExPolygons &src)
+{
+    Polylines polylines;
+    polylines.assign(number_polygons(src), Polyline());
+    size_t idx = 0;
+    for (ExPolygons::const_iterator it = src.begin(); it != src.end(); ++it) {
+        Polyline &pl = polylines[idx ++];
+        pl.points = it->contour.points;
+        pl.points.push_back(pl.points.front());
+        for (Polygons::const_iterator ith = it->holes.begin(); ith != it->holes.end(); ++ith) {
+            Polyline &pl = polylines[idx ++];
+            pl.points = ith->points;
+            pl.points.push_back(ith->points.front());
+        }
+    }
+    assert(idx == polylines.size());
+    return polylines;
+}
+
+#if SLIC3R_CPPVER >= 11
+inline Polylines to_polylines(ExPolygon &&src)
+{
+    Polylines polylines;
+    polylines.assign(src.holes.size() + 1, Polyline());
+    size_t idx = 0;
+    Polyline &pl = polylines[idx ++];
+    pl.points = std::move(src.contour.points);
+    pl.points.push_back(pl.points.front());
+    for (Polygons::const_iterator ith = src.holes.begin(); ith != src.holes.end(); ++ith) {
+        Polyline &pl = polylines[idx ++];
+        pl.points = std::move(ith->points);
+        pl.points.push_back(ith->points.front());
+    }
+    assert(idx == polylines.size());
+    return polylines;
+}
+inline Polylines to_polylines(ExPolygons &&src)
+{
+    Polylines polylines;
+    polylines.assign(number_polygons(src), Polyline());
+    size_t idx = 0;
+    for (ExPolygons::const_iterator it = src.begin(); it != src.end(); ++it) {
+        Polyline &pl = polylines[idx ++];
+        pl.points = std::move(it->contour.points);
+        pl.points.push_back(pl.points.front());
+        for (Polygons::const_iterator ith = it->holes.begin(); ith != it->holes.end(); ++ith) {
+            Polyline &pl = polylines[idx ++];
+            pl.points = std::move(ith->points);
+            pl.points.push_back(ith->points.front());
+        }
+    }
+    assert(idx == polylines.size());
+    return polylines;
+}
+#endif
+
+inline Polygons to_polygons(const ExPolygon &src)
+{
+    Polygons polygons;
+    polygons.reserve(src.holes.size() + 1);
+    polygons.push_back(src.contour);
+    polygons.insert(polygons.end(), src.holes.begin(), src.holes.end());
+    return polygons;
+}
+
 inline Polygons to_polygons(const ExPolygons &src)
 {
     Polygons polygons;
+    polygons.reserve(number_polygons(src));
     for (ExPolygons::const_iterator it = src.begin(); it != src.end(); ++it) {
         polygons.push_back(it->contour);
-        for (Polygons::const_iterator ith = it->holes.begin(); ith != it->holes.end(); ++ith) {
-            polygons.push_back(*ith);
-        }
+        polygons.insert(polygons.end(), it->holes.begin(), it->holes.end());
     }
     return polygons;
 }
 
 #if SLIC3R_CPPVER >= 11
+inline Polygons to_polygons(ExPolygon &&src)
+{
+    Polygons polygons;
+    polygons.reserve(src.holes.size() + 1);
+    polygons.push_back(std::move(src.contour));
+    std::move(std::begin(src.holes), std::end(src.holes), std::back_inserter(polygons));
+    return polygons;
+}
 inline Polygons to_polygons(ExPolygons &&src)
 {
     Polygons polygons;
+    polygons.reserve(number_polygons(src));
     for (ExPolygons::const_iterator it = src.begin(); it != src.end(); ++it) {
         polygons.push_back(std::move(it->contour));
-        for (Polygons::const_iterator ith = it->holes.begin(); ith != it->holes.end(); ++ith) {
-            polygons.push_back(std::move(*ith));
-        }
+        std::move(std::begin(it->holes), std::end(it->holes), std::back_inserter(polygons));
     }
     return polygons;
 }
 #endif
 
-// Count a nuber of polygons stored inside the vector of expolygons.
-// Useful for allocating space for polygons when converting expolygons to polygons.
-inline size_t number_polygons(const ExPolygons &expolys)
-{
-    size_t n_polygons = 0;
-    for (ExPolygons::const_iterator it = expolys.begin(); it != expolys.end(); ++ it)
-        n_polygons += it->holes.size() + 1;
-    return n_polygons;
+inline void polygons_append(Polygons &dst, const ExPolygon &src) 
+{ 
+    dst.reserve(dst.size() + src.holes.size() + 1);
+    dst.push_back(src.contour);
+    dst.insert(dst.end(), src.holes.begin(), src.holes.end());
 }
 
-// Append a vector of ExPolygons at the end of another vector of polygons.
 inline void polygons_append(Polygons &dst, const ExPolygons &src) 
 { 
     dst.reserve(dst.size() + number_polygons(src));
@@ -104,6 +236,13 @@ inline void polygons_append(Polygons &dst, const ExPolygons &src)
 }
 
 #if SLIC3R_CPPVER >= 11
+inline void polygons_append(Polygons &dst, ExPolygon &&src)
+{ 
+    dst.reserve(dst.size() + src.holes.size() + 1);
+    dst.push_back(std::move(src.contour));
+    std::move(std::begin(src.holes), std::end(src.holes), std::back_inserter(dst));
+}
+
 inline void polygons_append(Polygons &dst, ExPolygons &&src)
 { 
     dst.reserve(dst.size() + number_polygons(src));
@@ -114,8 +253,24 @@ inline void polygons_append(Polygons &dst, ExPolygons &&src)
 }
 #endif
 
+inline void expolygons_rotate(ExPolygons &expolys, double angle)
+{
+    for (ExPolygons::iterator p = expolys.begin(); p != expolys.end(); ++p)
+        p->rotate(angle);
+}
+
+inline bool expolygons_contain(ExPolygons &expolys, const Point &pt)
+{
+    for (ExPolygons::iterator p = expolys.begin(); p != expolys.end(); ++p)
+        if (p->contains(pt))
+            return true;
+    return false;
+}
+
 extern BoundingBox get_extents(const ExPolygon &expolygon);
 extern BoundingBox get_extents(const ExPolygons &expolygons);
+extern BoundingBox get_extents_rotated(const ExPolygon &poly, double angle);
+extern BoundingBox get_extents_rotated(const ExPolygons &polygons, double angle);
 
 extern bool        remove_sticks(ExPolygon &poly);
 
diff --git a/xs/src/libslic3r/MultiPoint.cpp b/xs/src/libslic3r/MultiPoint.cpp
index b771833ed..639eb6bb7 100644
--- a/xs/src/libslic3r/MultiPoint.cpp
+++ b/xs/src/libslic3r/MultiPoint.cpp
@@ -36,10 +36,10 @@ MultiPoint::rotate(double angle)
     double s = sin(angle);
     double c = cos(angle);
     for (Points::iterator it = points.begin(); it != points.end(); ++it) {
-	    double cur_x = (double)it->x;
-	    double cur_y = (double)it->y;
-	    it->x = (coord_t)round(c * cur_x - s * cur_y);
-	    it->y = (coord_t)round(c * cur_y + s * cur_x);
+        double cur_x = (double)it->x;
+        double cur_y = (double)it->y;
+        it->x = (coord_t)round(c * cur_x - s * cur_y);
+        it->y = (coord_t)round(c * cur_y + s * cur_x);
     }
 }
 
@@ -214,7 +214,38 @@ MultiPoint::_douglas_peucker(const Points &points, const double tolerance)
 
 BoundingBox get_extents(const MultiPoint &mp)
 { 
-    return mp.bounding_box();
+    return BoundingBox(mp.points);
+}
+
+BoundingBox get_extents_rotated(const Points &points, double angle)
+{ 
+    BoundingBox bbox;
+    if (! points.empty()) {
+        double s = sin(angle);
+        double c = cos(angle);
+        Points::const_iterator it = points.begin();
+        double cur_x = (double)it->x;
+        double cur_y = (double)it->y;
+        bbox.min.x = bbox.max.x = (coord_t)round(c * cur_x - s * cur_y);
+        bbox.min.y = bbox.max.y = (coord_t)round(c * cur_y + s * cur_x);
+        for (++it; it != points.end(); ++it) {
+            double cur_x = (double)it->x;
+            double cur_y = (double)it->y;
+            coord_t x = (coord_t)round(c * cur_x - s * cur_y);
+            coord_t y = (coord_t)round(c * cur_y + s * cur_x);
+            bbox.min.x = std::min(x, bbox.min.x);
+            bbox.min.y = std::min(y, bbox.min.y);
+            bbox.max.x = std::max(x, bbox.max.x);
+            bbox.max.y = std::max(y, bbox.max.y);
+        }
+        bbox.defined = true;
+    }
+    return bbox;
+}
+
+BoundingBox get_extents_rotated(const MultiPoint &mp, double angle)
+{
+    return get_extents_rotated(mp.points, angle);
 }
 
 }
diff --git a/xs/src/libslic3r/MultiPoint.hpp b/xs/src/libslic3r/MultiPoint.hpp
index 66b36d720..60e24e17e 100644
--- a/xs/src/libslic3r/MultiPoint.hpp
+++ b/xs/src/libslic3r/MultiPoint.hpp
@@ -48,6 +48,8 @@ class MultiPoint
 };
 
 extern BoundingBox get_extents(const MultiPoint &mp);
+extern BoundingBox get_extents_rotated(const std::vector<Point> &points, double angle);
+extern BoundingBox get_extents_rotated(const MultiPoint &mp, double angle);
 
 } // namespace Slic3r
 
diff --git a/xs/src/libslic3r/Polygon.cpp b/xs/src/libslic3r/Polygon.cpp
index 5fe0537fb..9338f2ec7 100644
--- a/xs/src/libslic3r/Polygon.cpp
+++ b/xs/src/libslic3r/Polygon.cpp
@@ -35,16 +35,9 @@ Polygon::last_point() const
     return this->points.front();  // last point == first point for polygons
 }
 
-Lines
-Polygon::lines() const
+Lines Polygon::lines() const
 {
-    Lines lines;
-    lines.reserve(this->points.size());
-    for (Points::const_iterator it = this->points.begin(); it != this->points.end()-1; ++it) {
-        lines.push_back(Line(*it, *(it + 1)));
-    }
-    lines.push_back(Line(this->points.back(), this->points.front()));
-    return lines;
+    return to_lines(*this);
 }
 
 Polyline
@@ -312,9 +305,25 @@ BoundingBox get_extents(const Polygons &polygons)
 {
     BoundingBox bb;
     if (! polygons.empty()) {
-        bb = polygons.front().bounding_box();
+        bb = get_extents(polygons.front());
+        for (size_t i = 1; i < polygons.size(); ++ i)
+            bb.merge(get_extents(polygons[i]));
+    }
+    return bb;
+}
+
+BoundingBox get_extents_rotated(const Polygon &poly, double angle) 
+{ 
+    return get_extents_rotated(poly.points, angle);
+}
+
+BoundingBox get_extents_rotated(const Polygons &polygons, double angle)
+{
+    BoundingBox bb;
+    if (! polygons.empty()) {
+        bb = get_extents_rotated(polygons.front().points, angle);
         for (size_t i = 1; i < polygons.size(); ++ i)
-            bb.merge(polygons[i]);
+            bb.merge(get_extents_rotated(polygons[i].points, angle));
     }
     return bb;
 }
diff --git a/xs/src/libslic3r/Polygon.hpp b/xs/src/libslic3r/Polygon.hpp
index 21f46117d..3ccd7154b 100644
--- a/xs/src/libslic3r/Polygon.hpp
+++ b/xs/src/libslic3r/Polygon.hpp
@@ -50,6 +50,8 @@ class Polygon : public MultiPoint {
 
 extern BoundingBox get_extents(const Polygon &poly);
 extern BoundingBox get_extents(const Polygons &polygons);
+extern BoundingBox get_extents_rotated(const Polygon &poly, double angle);
+extern BoundingBox get_extents_rotated(const Polygons &polygons, double angle);
 
 // Remove sticks (tentacles with zero area) from the polygon.
 extern bool        remove_sticks(Polygon &poly);
@@ -70,8 +72,71 @@ inline void        polygons_append(Polygons &dst, Polygons &&src)
         std::move(std::begin(src), std::end(src), std::back_inserter(dst));
 }
 #endif
+
+inline void polygons_rotate(Polygons &polys, double angle)
+{
+    for (Polygons::iterator p = polys.begin(); p != polys.end(); ++p)
+        p->rotate(angle);
+}
+
+inline Lines to_lines(const Polygon &poly) 
+{
+    Lines lines;
+    lines.reserve(poly.points.size());
+    for (Points::const_iterator it = poly.points.begin(); it != poly.points.end()-1; ++it)
+        lines.push_back(Line(*it, *(it + 1)));
+    lines.push_back(Line(poly.points.back(), poly.points.front()));
+    return lines;
 }
 
+inline Lines to_lines(const Polygons &polys) 
+{
+    size_t n_lines = 0;
+    for (size_t i = 0; i < polys.size(); ++ i)
+        n_lines += polys[i].points.size();
+    Lines lines;
+    lines.reserve(n_lines);
+    for (size_t i = 0; i < polys.size(); ++ i) {
+        const Polygon &poly = polys[i];
+        for (Points::const_iterator it = poly.points.begin(); it != poly.points.end()-1; ++it)
+            lines.push_back(Line(*it, *(it + 1)));
+        lines.push_back(Line(poly.points.back(), poly.points.front()));
+    }
+    return lines;
+}
+
+inline Polylines to_polylines(const Polygons &polys)
+{
+    Polylines polylines;
+    polylines.assign(polys.size(), Polyline());
+    size_t idx = 0;
+    for (Polygons::const_iterator it = polys.begin(); it != polys.end(); ++ it) {
+        Polyline &pl = polylines[idx ++];
+        pl.points = it->points;
+        pl.points.push_back(it->points.front());
+    }
+    assert(idx == polylines.size());
+    return polylines;
+}
+
+#if SLIC3R_CPPVER >= 11
+inline Polylines to_polylines(Polygons &&polys)
+{
+    Polylines polylines;
+    polylines.assign(polys.size(), Polyline());
+    size_t idx = 0;
+    for (Polygons::const_iterator it = polys.begin(); it != polys.end(); ++ it) {
+        Polyline &pl = polylines[idx ++];
+        pl.points = std::move(it->points);
+        pl.points.push_back(it->points.front());
+    }
+    assert(idx == polylines.size());
+    return polylines;
+}
+#endif
+
+} // Slic3r
+
 // start Boost
 #include <boost/polygon/polygon.hpp>
 namespace boost { namespace polygon {
diff --git a/xs/src/libslic3r/Polyline.hpp b/xs/src/libslic3r/Polyline.hpp
index dd2818199..b8c04a12a 100644
--- a/xs/src/libslic3r/Polyline.hpp
+++ b/xs/src/libslic3r/Polyline.hpp
@@ -36,6 +36,33 @@ class Polyline : public MultiPoint {
 extern BoundingBox get_extents(const Polyline &polyline);
 extern BoundingBox get_extents(const Polylines &polylines);
 
+inline Lines to_lines(const Polyline &poly) 
+{
+    Lines lines;
+    if (poly.points.size() >= 2) {
+        lines.reserve(poly.points.size() - 1);
+        for (Points::const_iterator it = poly.points.begin(); it != poly.points.end()-1; ++it)
+            lines.push_back(Line(*it, *(it + 1)));
+    }
+    return lines;
+}
+
+inline Lines to_lines(const Polylines &polys) 
+{
+    size_t n_lines = 0;
+    for (size_t i = 0; i < polys.size(); ++ i)
+        if (polys[i].points.size() > 1)
+            n_lines += polys[i].points.size() - 1;
+    Lines lines;
+    lines.reserve(n_lines);
+    for (size_t i = 0; i < polys.size(); ++ i) {
+        const Polyline &poly = polys[i];
+        for (Points::const_iterator it = poly.points.begin(); it != poly.points.end()-1; ++it)
+            lines.push_back(Line(*it, *(it + 1)));
+    }
+    return lines;
+}
+
 class ThickPolyline : public Polyline {
     public:
     std::vector<coordf_t> width;
diff --git a/xs/src/libslic3r/Surface.hpp b/xs/src/libslic3r/Surface.hpp
index d48b59557..9ef710741 100644
--- a/xs/src/libslic3r/Surface.hpp
+++ b/xs/src/libslic3r/Surface.hpp
@@ -56,6 +56,7 @@ public:
 #endif
     operator Polygons() const;
     double area() const;
+    bool empty() const { return expolygon.empty(); }
     bool is_solid() const;
     bool is_external() const;
     bool is_internal() const;
@@ -168,6 +169,10 @@ inline void surfaces_append(Surfaces &dst, const ExPolygons &src, const Surface
     for (ExPolygons::const_iterator it = src.begin(); it != src.end(); ++ it)
         dst.push_back(Surface(surfaceTempl, *it));
 }
+inline void surfaces_append(Surfaces &dst, const Surfaces &src) 
+{ 
+    dst.insert(dst.end(), src.begin(), src.end());
+}
 
 #if SLIC3R_CPPVER >= 11
 inline void surfaces_append(Surfaces &dst, ExPolygons &&src, SurfaceType surfaceType) 
@@ -182,12 +187,28 @@ inline void surfaces_append(Surfaces &dst, ExPolygons &&src, const Surface &surf
     for (ExPolygons::const_iterator it = src.begin(); it != src.end(); ++ it)
         dst.push_back(Surface(surfaceTempl, std::move(*it)));
 }
+inline void surfaces_append(Surfaces &dst, Surfaces &&src) 
+{ 
+    if (dst.empty())
+        dst = std::move(src);
+    else
+        std::move(std::begin(src), std::end(src), std::back_inserter(dst));
+}
 #endif
 
 extern BoundingBox get_extents(const Surface &surface);
 extern BoundingBox get_extents(const Surfaces &surfaces);
 extern BoundingBox get_extents(const SurfacesPtr &surfaces);
 
+inline bool surfaces_could_merge(const Surface &s1, const Surface &s2)
+{
+    return 
+        s1.surface_type      == s2.surface_type     &&
+        s1.thickness         == s2.thickness        &&
+        s1.thickness_layers  == s2.thickness_layers &&
+        s1.bridge_angle      == s2.bridge_angle;
+}
+
 class SVG;
 
 extern const char* surface_type_to_color_name(const SurfaceType surface_type);
diff --git a/xs/src/libslic3r/SurfaceCollection.cpp b/xs/src/libslic3r/SurfaceCollection.cpp
index c31d603c0..804190548 100644
--- a/xs/src/libslic3r/SurfaceCollection.cpp
+++ b/xs/src/libslic3r/SurfaceCollection.cpp
@@ -49,23 +49,16 @@ SurfaceCollection::group(std::vector<SurfacesPtr> *retval)
     for (Surfaces::iterator it = this->surfaces.begin(); it != this->surfaces.end(); ++it) {
         // find a group with the same properties
         SurfacesPtr* group = NULL;
-        for (std::vector<SurfacesPtr>::iterator git = retval->begin(); git != retval->end(); ++git) {
-            Surface* gkey = git->front();
-            if (   gkey->surface_type      == it->surface_type
-                && gkey->thickness         == it->thickness
-                && gkey->thickness_layers  == it->thickness_layers
-                && gkey->bridge_angle      == it->bridge_angle) {
+        for (std::vector<SurfacesPtr>::iterator git = retval->begin(); git != retval->end(); ++git)
+            if (! git->empty() && surfaces_could_merge(*git->front(), *it)) {
                 group = &*git;
                 break;
             }
-        }
-        
         // if no group with these properties exists, add one
         if (group == NULL) {
             retval->resize(retval->size() + 1);
             group = &retval->back();
         }
-        
         // append surface to group
         group->push_back(&*it);
     }
diff --git a/xs/src/libslic3r/libslic3r.h b/xs/src/libslic3r/libslic3r.h
index 431482cba..78853f145 100644
--- a/xs/src/libslic3r/libslic3r.h
+++ b/xs/src/libslic3r/libslic3r.h
@@ -60,10 +60,13 @@ void confess_at(const char *file, int line, const char *func, const char *pat, .
 // For example, could optimized functions with move semantics be used?
 #if __cplusplus==201402L
 	#define SLIC3R_CPPVER 14
+	#define STDMOVE(WHAT) std::move(WHAT)
 #elif __cplusplus==201103L
 	#define SLIC3R_CPPVER 11
+	#define STDMOVE(WHAT) std::move(WHAT)
 #else
 	#define SLIC3R_CPPVER 0
+	#define STDMOVE(WHAT) (WHAT)
 #endif
 
 #define SLIC3R_DEBUG_OUT_PATH_PREFIX "out/"