diff options
| author | bubnikv <bubnikv@gmail.com> | 2020-04-22 11:54:11 +0300 |
|---|---|---|
| committer | bubnikv <bubnikv@gmail.com> | 2020-04-22 11:54:11 +0300 |
| commit | 03eb5ffcd5d71181e2c0533060fd94a6601be76f (patch) | |
| tree | 43a9cf6ff6814eb1d0062cd18a1339e168ea9c12 /src | |
| parent | 10110ed3075b2b2c50096e842a45ea456c8106e2 (diff) | |
WIP: Reworking of FillRectilinear2 to support monotonous infill
with ant colony optimization and 3-opt flips.
Diffstat (limited to 'src')
| -rw-r--r-- | src/libslic3r/Fill/FillBase.hpp | 6 | ||||
| -rw-r--r-- | src/libslic3r/Fill/FillRectilinear2.cpp | 1679 | ||||
| -rw-r--r-- | src/libslic3r/libslic3r.h | 1 |
3 files changed, 1281 insertions, 405 deletions
diff --git a/src/libslic3r/Fill/FillBase.hpp b/src/libslic3r/Fill/FillBase.hpp index 5a9e92739..9fb37d2c0 100644 --- a/src/libslic3r/Fill/FillBase.hpp +++ b/src/libslic3r/Fill/FillBase.hpp @@ -5,6 +5,7 @@ #include <memory.h> #include <float.h> #include <stdint.h> +#include <stdexcept> #include <type_traits> @@ -18,6 +19,11 @@ namespace Slic3r { class ExPolygon; class Surface; +class InfillFailedException : public std::runtime_error { +public: + InfillFailedException() : std::runtime_error("Infill failed") {} +}; + struct FillParams { bool full_infill() const { return density > 0.9999f; } diff --git a/src/libslic3r/Fill/FillRectilinear2.cpp b/src/libslic3r/Fill/FillRectilinear2.cpp index 8aea75886..c2c19046e 100644 --- a/src/libslic3r/Fill/FillRectilinear2.cpp +++ b/src/libslic3r/Fill/FillRectilinear2.cpp @@ -4,7 +4,9 @@ #include <algorithm> #include <cmath> #include <limits> +#include <random> +#include <boost/container/small_vector.hpp> #include <boost/static_assert.hpp> #include "../ClipperUtils.hpp" @@ -105,26 +107,15 @@ static inline void polygon_segment_append_reversed(Points &out, const Polygon &p } // Intersection point of a vertical line with a polygon segment. -class SegmentIntersection +struct SegmentIntersection { -public: - SegmentIntersection() : - iContour(0), - iSegment(0), - pos_p(0), - pos_q(1), - type(UNKNOWN), - consumed_vertical_up(false), - consumed_perimeter_right(false) - {} - // Index of a contour in ExPolygonWithOffset, with which this vertical line intersects. - size_t iContour; + size_t iContour { 0 }; // Index of a segment in iContour, with which this vertical line intersects. - size_t iSegment; - // y position of the intersection, ratinal number. - int64_t pos_p; - uint32_t pos_q; + size_t iSegment { 0 }; + // y position of the intersection, rational number. + int64_t pos_p { 0 }; + uint32_t pos_q { 1 }; coord_t pos() const { // Division rounds both positive and negative down to zero. @@ -141,30 +132,140 @@ public: // A vertical segment will be at least intersected by OUTER_LOW, OUTER_HIGH, // but it could be intersected with OUTER_LOW, INNER_LOW, INNER_HIGH, OUTER_HIGH, // and there may be more than one pair of INNER_LOW, INNER_HIGH between OUTER_LOW, OUTER_HIGH. - enum SegmentIntersectionType { + enum SegmentIntersectionType : char { OUTER_LOW = 0, OUTER_HIGH = 1, INNER_LOW = 2, INNER_HIGH = 3, UNKNOWN = -1 }; - SegmentIntersectionType type; + SegmentIntersectionType type { UNKNOWN }; + + // Left vertical line / contour intersection point. + // null if next_on_contour_vertical. + int32_t prev_on_contour { 0 }; + // Right vertical line / contour intersection point. + // If next_on_contour_vertical, then then next_on_contour contains next contour point on the same vertical line. + int32_t next_on_contour { 0 }; + + enum class LinkType : uint8_t { + // Horizontal link (left or right). + Horizontal, + // Vertical link, up. + Up, + // Vertical link, down. + Down + }; + enum class LinkQuality : uint8_t { + Invalid, + Valid, + // Valid link, to be followed when extruding. + // Link inside a monotonous region. + ValidMonotonous, + // Valid link, to be possibly followed when extruding. + // Link between two monotonous regions. + ValidNonMonotonous, + // Link from T to end of another contour. + FromT, + // Link from end of one contour to T. + ToT, + // Link from one T to another T, making a letter H. + H, + // Vertical segment + TooLong, + }; + + // Kept grouped with other booleans for smaller memory footprint. + LinkType prev_on_contour_type { LinkType::Horizontal }; + LinkType next_on_contour_type { LinkType::Horizontal }; + LinkQuality prev_on_contour_quality { true }; + LinkQuality next_on_contour_quality { true }; // Was this segment along the y axis consumed? // Up means up along the vertical segment. - bool consumed_vertical_up; + bool consumed_vertical_up { false }; // Was a segment of the inner perimeter contour consumed? // Right means right from the vertical segment. - bool consumed_perimeter_right; + bool consumed_perimeter_right { false }; // For the INNER_LOW type, this point may be connected to another INNER_LOW point following a perimeter contour. // For the INNER_HIGH type, this point may be connected to another INNER_HIGH point following a perimeter contour. // If INNER_LOW is connected to INNER_HIGH or vice versa, // one has to make sure the vertical infill line does not overlap with the connecting perimeter line. - bool is_inner() const { return type == INNER_LOW || type == INNER_HIGH; } - bool is_outer() const { return type == OUTER_LOW || type == OUTER_HIGH; } - bool is_low () const { return type == INNER_LOW || type == OUTER_LOW; } - bool is_high () const { return type == INNER_HIGH || type == OUTER_HIGH; } + bool is_inner() const { return type == INNER_LOW || type == INNER_HIGH; } + bool is_outer() const { return type == OUTER_LOW || type == OUTER_HIGH; } + bool is_low () const { return type == INNER_LOW || type == OUTER_LOW; } + bool is_high () const { return type == INNER_HIGH || type == OUTER_HIGH; } + + enum class Side { + Left, + Right + }; + enum class Direction { + Up, + Down + }; + + bool has_left_horizontal() const { return this->prev_on_contour_type == LinkType::Horizontal; } + bool has_right_horizontal() const { return this->next_on_contour_type == LinkType::Horizontal; } + bool has_horizontal(Side side) const { return side == Side::Left ? this->has_left_horizontal() : this->has_right_horizontal(); } + + bool has_left_vertical_up() const { return this->prev_on_contour_type == LinkType::Up; } + bool has_left_vertical_down() const { return this->prev_on_contour_type == LinkType::Down; } + bool has_left_vertical(Direction dir) const { return dir == Direction::Up ? this->has_left_vertical_up() : this->has_left_vertical_down(); } + bool has_left_vertical() const { return this->has_left_vertical_up() || this->has_left_vertical_down(); } + bool has_left_vertical_outside() const { return this->is_low() ? this->has_left_vertical_down() : this->has_left_vertical_up(); } + + bool has_right_vertical_up() const { return this->next_on_contour_type == LinkType::Up; } + bool has_right_vertical_down() const { return this->next_on_contour_type == LinkType::Down; } + bool has_right_vertical(Direction dir) const { return dir == Direction::Up ? this->has_right_vertical_up() : this->has_right_vertical_down(); } + bool has_right_vertical() const { return this->has_right_vertical_up() || this->has_right_vertical_down(); } + bool has_right_vertical_outside() const { return this->is_low() ? this->has_right_vertical_down() : this->has_right_vertical_up(); } + + bool has_vertical() const { return this->has_left_vertical() || this->has_right_vertical(); } + bool has_vertical(Side side) const { return side == Side::Left ? this->has_left_vertical() : this->has_right_vertical(); } + bool has_vertical_up() const { return this->has_left_vertical_up() || this->has_right_vertical_up(); } + bool has_vertical_down() const { return this->has_left_vertical_down() || this->has_right_vertical_down(); } + bool has_vertical(Direction dir) const { return dir == Direction::Up ? this->has_vertical_up() : this->has_vertical_down(); } + + int left_horizontal() const { return this->has_left_horizontal() ? this->prev_on_contour : -1; } + int right_horizontal() const { return this->has_right_horizontal() ? this->next_on_contour : -1; } + int horizontal(Side side) const { return side == Side::Left ? this->left_horizontal() : this->right_horizontal(); } + + int left_vertical_up() const { return this->has_left_vertical_up() ? this->prev_on_contour : -1; } + int left_vertical_down() const { return this->has_left_vertical_down() ? this->prev_on_contour : -1; } + int left_vertical(Direction dir) const { return (dir == Direction::Up ? this->has_left_vertical_up() : this->has_left_vertical_down()) ? this->prev_on_contour : -1; } + int left_vertical() const { return this->has_left_vertical() ? this->prev_on_contour : -1; } + int left_vertical_outside() const { return this->is_low() ? this->left_vertical_down() : this->left_vertical_up(); } + int right_vertical_up() const { return this->has_right_vertical_up() ? this->prev_on_contour : -1; } + int right_vertical_down() const { return this->has_right_vertical_down() ? this->prev_on_contour : -1; } + int right_vertical(Direction dir) const { return (dir == Direction::Up ? this->has_right_vertical_up() : this->has_right_vertical_down()) ? this->next_on_contour : -1; } + int right_vertical() const { return this->has_right_vertical() ? this->prev_on_contour : -1; } + int right_vertical_outside() const { return this->is_low() ? this->right_vertical_down() : this->right_vertical_up(); } + + int vertical_up(Side side) const { return side == Side::Left ? this->left_vertical_up() : this->right_vertical_up(); } + int vertical_down(Side side) const { return side == Side::Left ? this->left_vertical_down() : this->right_vertical_down(); } + int vertical_outside(Side side) const { return side == Side::Left ? this->left_vertical_outside() : this->right_vertical_outside(); } + int vertical_up() const { + assert(! this->has_left_vertical_up() || ! this->has_right_vertical_up()); + return this->has_left_vertical_up() ? this->left_vertical_up() : this->right_vertical_up(); + } + LinkQuality vertical_up_quality() const { + assert(! this->has_left_vertical_up() || ! this->has_right_vertical_up()); + return this->has_left_vertical_up() ? this->prev_on_contour_quality : this->next_on_contour_quality; + } + int vertical_down() const { + assert(! this->has_left_vertical_down() || ! this->has_right_vertical_down()); + return this->has_left_vertical_down() ? this->left_vertical_down() : this->right_vertical_down(); + } + LinkQuality vertical_down_quality() const { + assert(! this->has_left_vertical_down() || ! this->has_right_vertical_down()); + return this->has_left_vertical_down() ? this->prev_on_contour_quality : this->next_on_contour_quality; + } + int vertical_outside() const { return this->is_low() ? this->vertical_down() : this->vertical_up(); } + +// int next_up() const { return this->prev_on_contour_vertical ? -1 : this->prev_on_contour; } +// int next_right() const { return this->next_on_contour_vertical ? -1 : this->next_on_contour; } // Compare two y intersection points given by rational numbers. // Note that the rational number is given as pos_p/pos_q, where pos_p is int64 and pos_q is uint32. @@ -250,11 +351,11 @@ public: return l_hi + (l_lo >> 32) == r_hi + (r_lo >> 32); } }; +static_assert(sizeof(SegmentIntersection::pos_q) == 4, "SegmentIntersection::pos_q has to be 32bit long!"); // A vertical line with intersection points with polygons. -class SegmentedIntersectionLine +struct SegmentedIntersectionLine { -public: // Index of this vertical intersection line. size_t idx; // x position of this vertical intersection line. @@ -290,10 +391,10 @@ public: // bool sticks_removed = remove_sticks(polygons_src); // if (sticks_removed) printf("Sticks removed!\n"); - polygons_outer = offset(polygons_src, aoffset1, + polygons_outer = offset(polygons_src, float(aoffset1), ClipperLib::jtMiter, mitterLimit); - polygons_inner = offset(polygons_outer, aoffset2 - aoffset1, + polygons_inner = offset(polygons_outer, float(aoffset2 - aoffset1), ClipperLib::jtMiter, mitterLimit); // Filter out contours with zero area or small area, contours with 2 points only. @@ -364,97 +465,6 @@ static inline int distance_of_segmens(const Polygon &poly, size_t seg1, size_t s return d; } -// For a vertical line, an inner contour and an intersection point, -// find an intersection point on the previous resp. next vertical line. -// The intersection point is connected with the prev resp. next intersection point with iInnerContour. -// Return -1 if there is no such point on the previous resp. next vertical line. -static inline int intersection_on_prev_next_vertical_line( - const ExPolygonWithOffset &poly_with_offset, - const std::vector<SegmentedIntersectionLine> &segs, - size_t iVerticalLine, - size_t iInnerContour, - size_t iIntersection, - bool dir_is_next) -{ - size_t iVerticalLineOther = iVerticalLine; - if (dir_is_next) { - if (++ iVerticalLineOther == segs.size()) - // No successive vertical line. - return -1; - } else if (iVerticalLineOther -- == 0) { - // No preceding vertical line. - return -1; - } - - const SegmentedIntersectionLine &il = segs[iVerticalLine]; - const SegmentIntersection &itsct = il.intersections[iIntersection]; - const SegmentedIntersectionLine &il2 = segs[iVerticalLineOther]; - const Polygon &poly = poly_with_offset.contour(iInnerContour); -// const bool ccw = poly_with_offset.is_contour_ccw(iInnerContour); - const bool forward = itsct.is_low() == dir_is_next; - // Resulting index of an intersection point on il2. - int out = -1; - // Find an intersection point on iVerticalLineOther, intersecting iInnerContour - // at the same orientation as iIntersection, and being closest to iIntersection - // in the number of contour segments, when following the direction of the contour. - int dmin = std::numeric_limits<int>::max(); - for (size_t i = 0; i < il2.intersections.size(); ++ i) { - const SegmentIntersection &itsct2 = il2.intersections[i]; - if (itsct.iContour == itsct2.iContour && itsct.type == itsct2.type) { - /* - if (itsct.is_low()) { - assert(itsct.type == SegmentIntersection::INNER_LOW); - assert(iIntersection > 0); - assert(il.intersections[iIntersection-1].type == SegmentIntersection::OUTER_LOW); - assert(i > 0); - if (il2.intersections[i-1].is_inner()) - // Take only the lowest inner intersection point. - continue; - assert(il2.intersections[i-1].type == SegmentIntersection::OUTER_LOW); - } else { - assert(itsct.type == SegmentIntersection::INNER_HIGH); - assert(iIntersection+1 < il.intersections.size()); - assert(il.intersections[iIntersection+1].type == SegmentIntersection::OUTER_HIGH); - assert(i+1 < il2.intersections.size()); - if (il2.intersections[i+1].is_inner()) - // Take only the highest inner intersection point. - continue; - assert(il2.intersections[i+1].type == SegmentIntersection::OUTER_HIGH); - } - */ - // The intersection points lie on the same contour and have the same orientation. - // Find the intersection point with a shortest path in the direction of the contour. - int d = distance_of_segmens(poly, itsct.iSegment, itsct2.iSegment, forward); - if (d < dmin) { - out = i; - dmin = d; - } - } - } - //FIXME this routine is not asymptotic optimal, it will be slow if there are many intersection points along the line. - return out; -} - -static inline int intersection_on_prev_vertical_line( - const ExPolygonWithOffset &poly_with_offset, - const std::vector<SegmentedIntersectionLine> &segs, - size_t iVerticalLine, - size_t iInnerContour, - size_t iIntersection) -{ - return intersection_on_prev_next_vertical_line(poly_with_offset, segs, iVerticalLine, iInnerContour, iIntersection, false); -} - -static inline int intersection_on_next_vertical_line( - const ExPolygonWithOffset &poly_with_offset, - const std::vector<SegmentedIntersectionLine> &segs, - size_t iVerticalLine, - size_t iInnerContour, - size_t iIntersection) -{ - return intersection_on_prev_next_vertical_line(poly_with_offset, segs, iVerticalLine, iInnerContour, iIntersection, true); -} - enum IntersectionTypeOtherVLine { // There is no connection point on the other vertical line. INTERSECTION_TYPE_OTHER_VLINE_UNDEFINED = -1, @@ -477,17 +487,19 @@ static inline IntersectionTypeOtherVLine intersection_type_on_prev_next_vertical const std::vector<SegmentedIntersectionLine> &segs, size_t iVerticalLine, size_t iIntersection, - size_t iIntersectionOther, - bool dir_is_next) + SegmentIntersection::Side side) { - // This routine will propose a connecting line even if the connecting perimeter segment intersects - // iVertical line multiple times before reaching iIntersectionOther. - if (iIntersectionOther == size_t(-1)) - return INTERSECTION_TYPE_OTHER_VLINE_UNDEFINED; - assert(dir_is_next ? (iVerticalLine + 1 < segs.size()) : (iVerticalLine > 0)); const SegmentedIntersectionLine &il_this = segs[iVerticalLine]; const SegmentIntersection &itsct_this = il_this.intersections[iIntersection]; - const SegmentedIntersectionLine &il_other = segs[dir_is_next ? (iVerticalLine+1) : (iVerticalLine-1)]; + if (itsct_this.has_vertical(side)) + // Not the first intersection along the contor. This intersection point + // has been preceded by an intersection point along the vertical line. + return INTERSECTION_TYPE_OTHER_VLINE_NOT_FIRST; + int iIntersectionOther = itsct_this.horizontal(side); + if (iIntersectionOther == -1) + return INTERSECTION_TYPE_OTHER_VLINE_UNDEFINED; + assert(side == SegmentIntersection::Side::Right ? (iVerticalLine + 1 < segs.size()) : (iVerticalLine > 0)); + const SegmentedIntersectionLine &il_other = segs[side == SegmentIntersection::Side::Right ? (iVerticalLine+1) : (iVerticalLine-1)]; const SegmentIntersection &itsct_other = il_other.intersections[iIntersectionOther]; assert(itsct_other.is_inner()); assert(iIntersectionOther > 0); @@ -499,7 +511,7 @@ static inline IntersectionTypeOtherVLine intersection_type_on_prev_next_vertical // Only perimeter segments connecting to the end of a vertical segment are followed. return INTERSECTION_TYPE_OTHER_VLINE_INNER; assert(itsct_other.is_low() == itsct_other2.is_low()); - if (dir_is_next ? itsct_this.consumed_perimeter_right : itsct_other.consumed_perimeter_right) + if (side == SegmentIntersection::Side::Right ? itsct_this.consumed_perimeter_right : itsct_other.consumed_perimeter_right) // This perimeter segment was already consumed. return INTERSECTION_TYPE_OTHER_VLINE_CONSUMED; if (itsct_other.is_low() ? itsct_other.consumed_vertical_up : il_other.intersections[iIntersectionOther-1].consumed_vertical_up) @@ -511,19 +523,17 @@ static inline IntersectionTypeOtherVLine intersection_type_on_prev_next_vertical static inline IntersectionTypeOtherVLine intersection_type_on_prev_vertical_line( const std::vector<SegmentedIntersectionLine> &segs, size_t iVerticalLine, - size_t iIntersection, - size_t iIntersectionPrev) + size_t iIntersection) { - return intersection_type_on_prev_next_vertical_line(segs, iVerticalLine, iIntersection, iIntersectionPrev, false); + return intersection_type_on_prev_next_vertical_line(segs, iVerticalLine, iIntersection, SegmentIntersection::Side::Left); } static inline IntersectionTypeOtherVLine intersection_type_on_next_vertical_line( const std::vector<SegmentedIntersectionLine> &segs, size_t iVerticalLine, - size_t iIntersection, - size_t iIntersectionNext) + size_t iIntersection) { - return intersection_type_on_prev_next_vertical_line(segs, iVerticalLine, iIntersection, iIntersectionNext, true); + return intersection_type_on_prev_next_vertical_line(segs, iVerticalLine, iIntersection, SegmentIntersection::Side::Right); } // Measure an Euclidian length of a perimeter segment when going from iIntersection to iIntersection2. @@ -531,7 +541,6 @@ static inline coordf_t measure_perimeter_prev_next_segment_length( const ExPolygonWithOffset &poly_with_offset, const std::vector<SegmentedIntersectionLine> &segs, size_t iVerticalLine, - size_t iInnerContour, size_t iIntersection, size_t iIntersection2, bool dir_is_next) @@ -550,8 +559,9 @@ static inline coordf_t measure_perimeter_prev_next_segment_length( const SegmentIntersection &itsct = il.intersections[iIntersection]; const SegmentedIntersectionLine &il2 = segs[iVerticalLineOther]; const SegmentIntersection &itsct2 = il2.intersections[iIntersection2]; - const Polygon &poly = poly_with_offset.contour(iInnerContour); -// const bool ccw = poly_with_offset.is_contour_ccw(iInnerContour); + assert(itsct.iContour == itsct2.iContour); + const Polygon &poly = poly_with_offset.contour(itsct.iContour); +// const bool ccw = poly_with_offset.is_contour_ccw(il.iContour); assert(itsct.type == itsct2.type); assert(itsct.iContour == itsct2.iContour); assert(itsct.is_inner()); @@ -568,22 +578,20 @@ static inline coordf_t measure_perimeter_prev_segment_length( const ExPolygonWithOffset &poly_with_offset, const std::vector<SegmentedIntersectionLine> &segs, size_t iVerticalLine, - size_t iInnerContour, size_t iIntersection, size_t iIntersection2) { - return measure_perimeter_prev_next_segment_length(poly_with_offset, segs, iVerticalLine, iInnerContour, iIntersection, iIntersection2, false); + return measure_perimeter_prev_next_segment_length(poly_with_offset, segs, iVerticalLine, iIntersection, iIntersection2, false); } static inline coordf_t measure_perimeter_next_segment_length( const ExPolygonWithOffset &poly_with_offset, const std::vector<SegmentedIntersectionLine> &segs, size_t iVerticalLine, - size_t iInnerContour, size_t iIntersection, size_t iIntersection2) { - return measure_perimeter_prev_next_segment_length(poly_with_offset, segs, iVerticalLine, iInnerContour, iIntersection, iIntersection2, true); + return measure_perimeter_prev_next_segment_length(poly_with_offset, segs, iVerticalLine, iIntersection, iIntersection2, true); } // Append the points of a perimeter segment when going from iIntersection to iIntersection2. @@ -632,7 +640,6 @@ static inline coordf_t measure_perimeter_segment_on_vertical_line_length( const ExPolygonWithOffset &poly_with_offset, const std::vector<SegmentedIntersectionLine> &segs, size_t iVerticalLine, - size_t iInnerContour, size_t iIntersection, size_t iIntersection2, bool forward) @@ -640,11 +647,10 @@ static inline coordf_t measure_perimeter_segment_on_vertical_line_length( const SegmentedIntersectionLine &il = segs[iVerticalLine]; const SegmentIntersection &itsct = il.intersections[iIntersection]; const SegmentIntersection &itsct2 = il.intersections[iIntersection2]; - const Polygon &poly = poly_with_offset.contour(iInnerContour); + const Polygon &poly = poly_with_offset.contour(itsct.iContour); assert(itsct.is_inner()); assert(itsct2.is_inner()); assert(itsct.type != itsct2.type); - assert(itsct.iContour == iInnerContour); assert(itsct.iContour == itsct2.iContour); Point p1(il.pos, itsct.pos()); Point p2(il.pos, itsct2.pos()); @@ -759,80 +765,15 @@ enum DirectionMask DIR_BACKWARD = 2 }; -bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillParams ¶ms, float angleBase, float pattern_shift, Polylines &polylines_out) +static std::vector<SegmentedIntersectionLine> slice_region_by_vertical_lines(const ExPolygonWithOffset &poly_with_offset, size_t n_vlines, coord_t x0, coord_t line_spacing) { - // At the end, only the new polylines will be rotated back. - size_t n_polylines_out_initial = polylines_out.size(); - - // Shrink the input polygon a bit first to not push the infill lines out of the perimeters. -// const float INFILL_OVERLAP_OVER_SPACING = 0.3f; - const float INFILL_OVERLAP_OVER_SPACING = 0.45f; - assert(INFILL_OVERLAP_OVER_SPACING > 0 && INFILL_OVERLAP_OVER_SPACING < 0.5f); - - // Rotate polygons so that we can work with vertical lines here - std::pair<float, Point> rotate_vector = this->_infill_direction(surface); - rotate_vector.first += angleBase; - - assert(params.density > 0.0001f && params.density <= 1.f); - coord_t line_spacing = coord_t(scale_(this->spacing) / params.density); - - // On the polygons of poly_with_offset, the infill lines will be connected. - ExPolygonWithOffset poly_with_offset( - surface->expolygon, - - rotate_vector.first, - scale_(this->overlap - (0.5 - INFILL_OVERLAP_OVER_SPACING) * this->spacing), - scale_(this->overlap - 0.5 * this->spacing)); - if (poly_with_offset.n_contours_inner == 0) { - // Not a single infill line fits. - //FIXME maybe one shall trigger the gap fill here? - return true; - } - - BoundingBox bounding_box = poly_with_offset.bounding_box_src(); - - // define flow spacing according to requested density - if (params.full_infill() && !params.dont_adjust) { - line_spacing = this->_adjust_solid_spacing(bounding_box.size()(0), line_spacing); - this->spacing = unscale<double>(line_spacing); - } else { - // extend bounding box so that our pattern will be aligned with other layers - // Transform the reference point to the rotated coordinate system. - Point refpt = rotate_vector.second.rotated(- rotate_vector.first); - // _align_to_grid will not work correctly with positive pattern_shift. - coord_t pattern_shift_scaled = coord_t(scale_(pattern_shift)) % line_spacing; - refpt(0) -= (pattern_shift_scaled >= 0) ? pattern_shift_scaled : (line_spacing + pattern_shift_scaled); - bounding_box.merge(_align_to_grid( - bounding_box.min, - Point(line_spacing, line_spacing), - refpt)); - } - - // Intersect a set of euqally spaced vertical lines wiht expolygon. - // n_vlines = ceil(bbox_width / line_spacing) - size_t n_vlines = (bounding_box.max(0) - bounding_box.min(0) + line_spacing - 1) / line_spacing; - coord_t x0 = bounding_box.min(0); - if (params.full_infill()) - x0 += (line_spacing + SCALED_EPSILON) / 2; - -#ifdef SLIC3R_DEBUG - static int iRun = 0; - BoundingBox bbox_svg = poly_with_offset.bounding_box_outer(); - ::Slic3r::SVG svg(debug_out_path("FillRectilinear2-%d.svg", iRun), bbox_svg); // , scale_(1.)); - poly_with_offset.export_to_svg(svg); - { - ::Slic3r::SVG svg(debug_out_path("FillRectilinear2-initial-%d.svg", iRun), bbox_svg); // , scale_(1.)); - poly_with_offset.export_to_svg(svg); - } - iRun ++; -#endif /* SLIC3R_DEBUG */ - - // For each contour // Allocate storage for the segments. std::vector<SegmentedIntersectionLine> segs(n_vlines, SegmentedIntersectionLine()); - for (size_t i = 0; i < n_vlines; ++ i) { + for (coord_t i = 0; i < coord_t(n_vlines); ++ i) { segs[i].idx = i; segs[i].pos = x0 + i * line_spacing; } + // For each contour for (size_t iContour = 0; iContour < poly_with_offset.n_contours; ++ iContour) { const Points &contour = poly_with_offset.contour(iContour).points; if (contour.size() < 2) @@ -977,59 +918,361 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP } // Verify the segments. If something is wrong, give up. -#define ASSERT_OR_RETURN(CONDITION) do { assert(CONDITION); if (! (CONDITION)) return false; } while (0) +#define ASSERT_THROW(CONDITION) do { assert(CONDITION); throw InfillFailedException(); } while (0) for (size_t i_seg = 0; i_seg < segs.size(); ++ i_seg) { SegmentedIntersectionLine &sil = segs[i_seg]; // The intersection points have to be even. - ASSERT_OR_RETURN((sil.intersections.size() & 1) == 0); + ASSERT_THROW((sil.intersections.size() & 1) == 0); for (size_t i = 0; i < sil.intersections.size();) { // An intersection segment crossing the bigger contour may cross the inner offsetted contour even number of times. - ASSERT_OR_RETURN(sil.intersections[i].type == SegmentIntersection::OUTER_LOW); + ASSERT_THROW(sil.intersections[i].type == SegmentIntersection::OUTER_LOW); size_t j = i + 1; - ASSERT_OR_RETURN(j < sil.intersections.size()); - ASSERT_OR_RETURN(sil.intersections[j].type == SegmentIntersection::INNER_LOW || sil.intersections[j].type == SegmentIntersection::OUTER_HIGH); + ASSERT_THROW(j < sil.intersections.size()); + ASSERT_THROW(sil.intersections[j].type == SegmentIntersection::INNER_LOW || sil.intersections[j].type == SegmentIntersection::OUTER_HIGH); for (; j < sil.intersections.size() && sil.intersections[j].is_inner(); ++ j) ; - ASSERT_OR_RETURN(j < sil.intersections.size()); - ASSERT_OR_RETURN((j & 1) == 1); - ASSERT_OR_RETURN(sil.intersections[j].type == SegmentIntersection::OUTER_HIGH); - ASSERT_OR_RETURN(i + 1 == j || sil.intersections[j - 1].type == SegmentIntersection::INNER_HIGH); + ASSERT_THROW(j < sil.intersections.size()); + ASSERT_THROW((j & 1) == 1); + ASSERT_THROW(sil.intersections[j].type == SegmentIntersection::OUTER_HIGH); + ASSERT_THROW(i + 1 == j || sil.intersections[j - 1].type == SegmentIntersection::INNER_HIGH); i = j + 1; } } -#undef ASSERT_OR_RETURN +#undef ASSERT_THROW -#ifdef SLIC3R_DEBUG - // Paint the segments and finalize the SVG file. - for (size_t i_seg = 0; i_seg < segs.size(); ++ i_seg) { - SegmentedIntersectionLine &sil = segs[i_seg]; - for (size_t i = 0; i < sil.intersections.size();) { - size_t j = i + 1; - for (; j < sil.intersections.size() && sil.intersections[j].is_inner(); ++ j) ; - if (i + 1 == j) { - svg.draw(Line(Point(sil.pos, sil.intersections[i].pos()), Point(sil.pos, sil.intersections[j].pos())), "blue"); - } else { - svg.draw(Line(Point(sil.pos, sil.intersections[i].pos()), Point(sil.pos, sil.intersections[i+1].pos())), "green"); - svg.draw(Line(Point(sil.pos, sil.intersections[i+1].pos()), Point(sil.pos, sil.intersections[j-1].pos())), (j - i + 1 > 4) ? "yellow" : "magenta"); - svg.draw(Line(Point(sil.pos, sil.intersections[j-1].pos()), Point(sil.pos, sil.intersections[j].pos())), "green"); - } - i = j + 1; - } + return segs; +} + +// Connect each contour / vertical line intersection point with another two contour / vertical line intersection points. +// (fill in SegmentIntersection::{prev_on_contour, prev_on_contour_vertical, next_on_contour, next_on_contour_vertical}. +// These contour points are either on the same vertical line, or on the vertical line left / right to the current one. +static void connect_segment_intersections_by_contours(const ExPolygonWithOffset &poly_with_offset, std::vector<SegmentedIntersectionLine> &segs) +{ + for (size_t i_vline = 0; i_vline < segs.size(); ++ i_vline) { + SegmentedIntersectionLine &il = segs[i_vline]; + const SegmentedIntersectionLine *il_prev = i_vline > 0 ? &segs[i_vline - 1] : nullptr; + const SegmentedIntersectionLine *il_next = i_vline + 1 < segs.size() ? &segs[i_vline + 1] : nullptr; + + for (size_t i_intersection = 0; i_intersection + 1 < il.intersections.size(); ++ i_intersection) { + SegmentIntersection &itsct = il.intersections[i_intersection]; + const Polygon &poly = poly_with_offset.contour(itsct.iContour); + + // 1) Find possible connection points on the previous / next vertical line. + // Find an intersection point on iVerticalLineOther, intersecting iInnerContour + // at the same orientation as iIntersection, and being closest to iIntersection + // in the number of contour segments, when following the direction of the contour. + int iprev = -1; + if (il_prev) { + int dmin = std::numeric_limits<int>::max(); + for (size_t i = 0; i < il_prev->intersections.size(); ++ i) { + const SegmentIntersection &itsct2 = il_prev->intersections[i]; + if (itsct.iContour == itsct2.iContour && itsct.type == itsct2.type) { + // The intersection points lie on the same contour and have the same orientation. + // Find the intersection point with a shortest path in the direction of the contour. + int d = distance_of_segmens(poly, itsct.iSegment, itsct2.iSegment, false); + if (d < dmin) { + iprev = i; + dmin = d; + } + } + } + } + int inext = -1; + if (il_next) { + int dmin = std::numeric_limits<int>::max(); + for (size_t i = 0; i < il_next->intersections.size(); ++ i) { + const SegmentIntersection &itsct2 = il_next->intersections[i]; + if (itsct.iContour == itsct2.iContour && itsct.type == itsct2.type) { + // The intersection points lie on the same contour and have the same orientation. + // Find the intersection point with a shortest path in the direction of the contour. + int d = distance_of_segmens(poly, itsct.iSegment, itsct2.iSegment, true); + if (d < dmin) { + inext = i; + dmin = d; + } + } + } + } + + // 2) Find possible connection points on the same vertical line. + int iabove = -1; + // Does the perimeter intersect the current vertical line above intrsctn? + for (size_t i = i_intersection + 1; i + 1 < il.intersections.size(); ++ i) + if (il.intersections[i].iContour == itsct.iContour) { + iabove = i; + break; + } + // Does the perimeter intersect the current vertical line below intrsctn? + int ibelow = -1; + for (size_t i = i_intersection - 1; i > 0; -- i) + if (il.intersections[i].iContour == itsct.iContour) { + ibelow = i; + break; + } + + // 3) Sort the intersection points, clear iprev / inext / iSegBelow / iSegAbove, + // if it is preceded by any other intersection point along the contour. + // The perimeter contour orientation. + const bool forward = itsct.is_low(); // == poly_with_offset.is_contour_ccw(intrsctn->iContour); + { + int d_horiz = (iprev == -1) ? std::numeric_limits<int>::max() : + distance_of_segmens(poly, il_prev->intersections[iprev].iSegment, itsct.iSegment, forward); + int d_down = (ibelow == -1) ? std::numeric_limits<int>::max() : + distance_of_segmens(poly, il.intersections[ibelow].iSegment, itsct.iSegment, forward); + int d_up = (iabove == -1) ? std::numeric_limits<int>::max() : + distance_of_segmens(poly, il.intersections[ibelow].iSegment, itsct.iSegment, forward); + if (d_horiz < std::min(d_down, d_up)) { + itsct.prev_on_contour = iprev; + itsct.prev_on_contour_type = SegmentIntersection::LinkType::Horizontal; + } else if (d_down < d_up) { + itsct.prev_on_contour = ibelow; + itsct.prev_on_contour_type = SegmentIntersection::LinkType::Down; + } else { + itsct.prev_on_contour = iabove; + itsct.prev_on_contour_type = SegmentIntersection::LinkType::Up; + } + // There should always be a link to the next intersection point on the same contour. + assert(itsct.prev_on_contour != -1); + } + { + int d_horiz = (inext == -1) ? std::numeric_limits<int>::max() : + distance_of_segmens(poly, itsct.iSegment, il_next->intersections[inext].iSegment, forward); + int d_down = (ibelow == -1) ? std::numeric_limits<int>::max() : + distance_of_segmens(poly, itsct.iSegment, il.intersections[ibelow].iSegment, forward); + int d_up = (iabove == -1) ? std::numeric_limits<int>::max() : + distance_of_segmens(poly, itsct.iSegment, il.intersections[iabove].iSegment, forward); + if (d_horiz < std::min(d_down, d_up)) { + itsct.next_on_contour = inext; + itsct.next_on_contour_type = SegmentIntersection::LinkType::Horizontal; + } else if (d_down < d_up) { + itsct.next_on_contour = ibelow; + itsct.next_on_contour_type = SegmentIntersection::LinkType::Down; + } else { + itsct.next_on_contour = iabove; + itsct.next_on_contour_type = SegmentIntersection::LinkType::Up; + } + // There should always be a link to the next intersection point on the same contour. + assert(itsct.next_on_contour != -1); + } + } } - svg.Close(); -#endif /* SLIC3R_DEBUG */ +} + +// Find the last INNER_HIGH intersection starting with INNER_LOW, that is followed by OUTER_HIGH intersection. +// Such intersection shall always exist. +static const SegmentIntersection& end_of_vertical_run_raw(const SegmentIntersection &start) +{ + assert(start.type != SegmentIntersection::INNER_LOW); + // Step back to the beginning of the vertical segment to mark it as consumed. + auto *it = &start; + do { + ++ it; + } while (it->type != SegmentIntersection::OUTER_HIGH); + if ((it - 1)->is_inner()) { + // Step back. + -- it; + assert(it->type == SegmentIntersection::INNER_HIGH); + } + return *it; +} +static SegmentIntersection& end_of_vertical_run_raw(SegmentIntersection &start) +{ + return const_cast<SegmentIntersection&>(end_of_vertical_run_raw(std::as_const(start))); +} +// Find the last INNER_HIGH intersection starting with INNER_LOW, that is followed by OUTER_HIGH intersection, traversing vertical up contours if enabled. +// Such intersection shall always exist. +static const SegmentIntersection& end_of_vertical_run(const SegmentedIntersectionLine &il, const SegmentIntersection &start) +{ + assert(start.type != SegmentIntersection::INNER_LOW); + const SegmentIntersection *end = &end_of_vertical_run_raw(start); + assert(end->type == SegmentIntersection::INNER_HIGH); + for (;;) { + int up = end->vertical_up(); + if (up == -1 || (end->has_left_vertical_up() ? end->prev_on_contour_quality : end->next_on_contour_quality) != SegmentIntersection::LinkQuality::Valid) + break; + const SegmentIntersection &new_start = il.intersections[up]; + assert(end->iContour == new_start.iContour); + assert(new_start.type == SegmentIntersection::INNER_LOW); + end = &end_of_vertical_run_raw(new_start); + } + assert(end->type == SegmentIntersection::INNER_HIGH); + return *end; +} +static SegmentIntersection& end_of_vertical_run(SegmentedIntersectionLine &il, SegmentIntersection &start) +{ + return const_cast<SegmentIntersection&>(end_of_vertical_run(std::as_const(il), std::as_const(start))); +} + +static void classify_vertical_runs( + const ExPolygonWithOffset &poly_with_offset, const FillParams ¶ms, const coord_t link_max_length, + std::vector<SegmentedIntersectionLine> &segs, size_t i_vline) +{ + SegmentedIntersectionLine &vline = segs[i_vline]; + for (size_t i_intersection = 0; i_intersection + 1 < vline.intersections.size(); ++ i_intersection) { + if (vline.intersections[i_intersection].type == SegmentIntersection::OUTER_LOW) { + if (vline.intersections[++ i_intersection].type == SegmentIntersection::INNER_LOW) { + for (;;) { + SegmentIntersection &start = vline.intersections[i_intersection]; + SegmentIntersection &end = end_of_vertical_run_raw(start); + SegmentIntersection::LinkQuality link_quality = SegmentIntersection::LinkQuality::Valid; + // End of a contour starting at end and ending above end at the same vertical line. + int inext = end.vertical_outside(); + if (inext == -1) { + i_intersection = &end - vline.intersections.data() + 1; + break; + } + SegmentIntersection &start2 = vline.intersections[inext]; + if (params.dont_connect) + link_quality = SegmentIntersection::LinkQuality::TooLong; + else { + for (SegmentIntersection *it = &end + 1; it != &start2; ++ it) + if (it->is_inner()) { + link_quality = SegmentIntersection::LinkQuality::Invalid; + break; + } + if (link_quality == SegmentIntersection::LinkQuality::Valid && link_max_length > 0) { + // Measure length of the link. + coordf_t link_length = measure_perimeter_segment_on_vertical_line_length( + poly_with_offset, segs, i_vline, i_intersection, inext, end.has_right_vertical_outside()); + if (link_length > link_max_length) + link_quality = SegmentIntersection::LinkQuality::TooLong; + } + } + (end.has_left_vertical_up() ? end.prev_on_contour_quality : end.next_on_contour_quality) = link_quality; + (start2.has_left_vertical_down() ? start2.prev_on_contour_quality : start2.next_on_contour_quality) = link_quality; + if (link_quality != SegmentIntersection::LinkQuality::Valid) { + i_intersection = &end - vline.intersections.data() + 1; + break; + } + i_intersection = &start2 - vline.intersections.data(); + } + } else + ++ i_intersection; + } else + ++ i_intersection; + } +} + +static void classify_horizontal_links( + const ExPolygonWithOffset &poly_with_offset, const FillParams ¶ms, const coord_t link_max_length, + std::vector<SegmentedIntersectionLine> &segs, size_t i_vline) +{ + SegmentedIntersectionLine &vline_left = segs[i_vline]; + SegmentedIntersectionLine &vline_right = segs[i_vline + 1]; + + // Traverse both left and right together. + size_t i_intersection_left = 0; + size_t i_intersection_right = 0; + while (i_intersection_left + 1 < vline_left.intersections.size() && i_intersection_right + 1 < vline_right.intersections.size()) { + if (i_intersection_left < vline_left.intersections.size() && vline_left.intersections[i_intersection_left].type != SegmentIntersection::INNER_LOW) { + ++ i_intersection_left; + continue; + } + if (i_intersection_right < vline_right.intersections.size() && vline_right.intersections[i_intersection_right].type != SegmentIntersection::INNER_LOW) { + ++ i_intersection_right; + continue; + } + + if (i_intersection_left + 1 >= vline_left.intersections.size()) { + // Trace right only. + } else if (i_intersection_right + 1 >= vline_right.intersections.size()) { + // Trace left only. + } else { + // Trace both. + SegmentIntersection &start_left = vline_left.intersections[i_intersection_left]; + SegmentIntersection &end_left = end_of_vertical_run(vline_left, start_left); + SegmentIntersection &start_right = vline_right.intersections[i_intersection_right]; + SegmentIntersection &end_right = end_of_vertical_run(vline_right, start_right); + // Do these runs overlap? + int end_right_horizontal = end_left.right_horizontal(); + int end_left_horizontal = end_right.left_horizontal(); + if (end_right_horizontal != -1) { + if (end_right_horizontal < &start_right - vline_right.intersections.data()) { + // Left precedes the right segment. + } + } else if (end_left_horizontal != -1) { + if (end_left_horizontal < &start_left - vline_left.intersections.data()) { + // Right precedes the left segment. + } + } + } + } + +#if 0 + for (size_t i_intersection = 0; i_intersection + 1 < seg.intersections.size(); ++ i_intersection) { + if (segs.intersections[i_intersection].type == SegmentIntersection::OUTER_LOW) { + if (segs.intersections[++ i_intersection].type == SegmentIntersection::INNER_LOW) { + for (;;) { + SegmentIntersection &start = segs.intersections[i_intersection]; + SegmentIntersection &end = end_of_vertical_run_raw(start); + SegmentIntersection::LinkQuality link_quality = SegmentIntersection::LinkQuality::Valid; + // End of a contour starting at end and ending above end at the same vertical line. + int inext = end.vertical_outside(); + if (inext == -1) { + i_intersection = &end - segs.intersections.data() + 1; + break; + } + SegmentIntersection &start2 = segs.intersections[inext]; + if (params.dont_connect) + link_quality = SegmentIntersection::LinkQuality::TooLong; + else { + for (SegmentIntersection *it = &end + 1; it != &start2; ++ it) + if (it->is_inner()) { + link_quality = SegmentIntersection::LinkQuality::Invalid; + break; + } + if (link_quality == SegmentIntersection::LinkQuality::Valid && link_max_length > 0) { + // Measure length of the link. + coordf_t link_length = measure_perimeter_segment_on_vertical_line_length( + poly_with_offset, segs, i_vline, i_intersection, inext, intrsctn->has_right_vertical_outside()); + if (link_length > link_max_length) + link_quality = SegmentIntersection::LinkQuality::TooLong; + } + } + (end.has_left_vertical_up() ? end.prev_on_contour_quality : end.next_on_contour_quality) = link_quality; + (start2.has_left_vertical_down() ? start2.prev_on_contour_quality : start2.next_on_contour_quality) = link_quality; + if (link_quality != SegmentIntersection::LinkQuality::Valid) { + i_intersection = &end - segs.intersections.data() + 1; + break; + } + i_intersection = &start2 - segs.intersections.data(); + } + } else + ++ i_intersection; + } else + ++ i_intersection; + } +#endif +} + +static void disconnect_invalid_contour_links( + const ExPolygonWithOffset& poly_with_offset, const FillParams& params, const coord_t link_max_length, std::vector<SegmentedIntersectionLine>& segs) +{ + // Make the links symmetric! + + // Validate vertical runs including vertical contour links. + for (size_t i_vline = 0; i_vline < segs.size(); ++ i_vline) { + classify_vertical_runs(poly_with_offset, params, link_max_length, segs, i_vline); + if (i_vline > 0) + classify_horizontal_links(poly_with_offset, params, link_max_length, segs, i_vline - 1); + } +} + +static void traverse_graph_generate_polylines( + const ExPolygonWithOffset& poly_with_offset, const FillParams& params, const coord_t link_max_length, std::vector<SegmentedIntersectionLine>& segs, Polylines& polylines_out) +{ // For each outer only chords, measure their maximum distance to the bow of the outer contour. // Mark an outer only chord as consumed, if the distance is low. - for (size_t i_vline = 0; i_vline < segs.size(); ++ i_vline) { - SegmentedIntersectionLine &seg = segs[i_vline]; - for (size_t i_intersection = 0; i_intersection + 1 < seg.intersections.size(); ++ i_intersection) { + for (size_t i_vline = 0; i_vline < segs.size(); ++i_vline) { + SegmentedIntersectionLine& seg = segs[i_vline]; + for (size_t i_intersection = 0; i_intersection + 1 < seg.intersections.size(); ++i_intersection) { if (seg.intersections[i_intersection].type == SegmentIntersection::OUTER_LOW && - seg.intersections[i_intersection+1].type == SegmentIntersection::OUTER_HIGH) { + seg.intersections[i_intersection + 1].type == SegmentIntersection::OUTER_HIGH) { bool consumed = false; -// if (params.full_infill()) { -// measure_outer_contour_slab(poly_with_offset, segs, i_vline, i_ntersection); -// } else - consumed = true; + // if (params.full_infill()) { + // measure_outer_contour_slab(poly_with_offset, segs, i_vline, i_ntersection); + // } else + consumed = true; seg.intersections[i_intersection].consumed_vertical_up = consumed; } } @@ -1045,28 +1288,28 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP // Follow the line, connect the lines into a graph. // Until no new line could be added to the output path: Point pointLast; - Polyline *polyline_current = NULL; - if (! polylines_out.empty()) + Polyline* polyline_current = NULL; + if (!polylines_out.empty()) pointLast = polylines_out.back().points.back(); for (;;) { if (i_intersection == size_t(-1)) { // The path has been interrupted. Find a next starting point, closest to the previous extruder position. coordf_t dist2min = std::numeric_limits<coordf_t>().max(); - for (size_t i_vline2 = 0; i_vline2 < segs.size(); ++ i_vline2) { - const SegmentedIntersectionLine &seg = segs[i_vline2]; - if (! seg.intersections.empty()) { + for (size_t i_vline2 = 0; i_vline2 < segs.size(); ++i_vline2) { + const SegmentedIntersectionLine& seg = segs[i_vline2]; + if (!seg.intersections.empty()) { assert(seg.intersections.size() > 1); // Even number of intersections with the loops. assert((seg.intersections.size() & 1) == 0); assert(seg.intersections.front().type == SegmentIntersection::OUTER_LOW); - for (size_t i = 0; i < seg.intersections.size(); ++ i) { - const SegmentIntersection &intrsctn = seg.intersections[i]; + for (size_t i = 0; i < seg.intersections.size(); ++i) { + const SegmentIntersection& intrsctn = seg.intersections[i]; if (intrsctn.is_outer()) { assert(intrsctn.is_low() || i > 0); - bool consumed = intrsctn.is_low() ? - intrsctn.consumed_vertical_up : - seg.intersections[i-1].consumed_vertical_up; - if (! consumed) { + bool consumed = intrsctn.is_low() ? + intrsctn.consumed_vertical_up : + seg.intersections[i - 1].consumed_vertical_up; + if (!consumed) { coordf_t dist2 = sqr(coordf_t(pointLast(0) - seg.pos)) + sqr(coordf_t(pointLast(1) - intrsctn.pos())); if (dist2 < dist2min) { dist2min = dist2; @@ -1076,7 +1319,7 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP // by a shortest distance, while reversing the paths if needed. //if (polylines_out.empty()) // Initial state, take the first line, which is the first from the left. - goto found; + goto found; } } } @@ -1096,30 +1339,30 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP } // From the initial point (i_vline, i_intersection), follow a path. - SegmentedIntersectionLine &seg = segs[i_vline]; - SegmentIntersection *intrsctn = &seg.intersections[i_intersection]; + SegmentedIntersectionLine& seg = segs[i_vline]; + SegmentIntersection* intrsctn = &seg.intersections[i_intersection]; bool going_up = intrsctn->is_low(); bool try_connect = false; if (going_up) { - assert(! intrsctn->consumed_vertical_up); + assert(!intrsctn->consumed_vertical_up); assert(i_intersection + 1 < seg.intersections.size()); // Step back to the beginning of the vertical segment to mark it as consumed. if (intrsctn->is_inner()) { assert(i_intersection > 0); - -- intrsctn; - -- i_intersection; + --intrsctn; + --i_intersection; } // Consume the complete vertical segment up to the outer contour. do { intrsctn->consumed_vertical_up = true; - ++ intrsctn; - ++ i_intersection; + ++intrsctn; + ++i_intersection; assert(i_intersection < seg.intersections.size()); } while (intrsctn->type != SegmentIntersection::OUTER_HIGH); if ((intrsctn - 1)->is_inner()) { // Step back. - -- intrsctn; - -- i_intersection; + --intrsctn; + --i_intersection; assert(intrsctn->type == SegmentIntersection::INNER_HIGH); try_connect = true; } @@ -1127,20 +1370,20 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP // Going down. assert(intrsctn->is_high()); assert(i_intersection > 0); - assert(! (intrsctn - 1)->consumed_vertical_up); + assert(!(intrsctn - 1)->consumed_vertical_up); // Consume the complete vertical segment up to the outer contour. if (intrsctn->is_inner()) intrsctn->consumed_vertical_up = true; do { assert(i_intersection > 0); - -- intrsctn; - -- i_intersection; + --intrsctn; + --i_intersection; intrsctn->consumed_vertical_up = true; } while (intrsctn->type != SegmentIntersection::OUTER_LOW); if ((intrsctn + 1)->is_inner()) { // Step back. - ++ intrsctn; - ++ i_intersection; + ++intrsctn; + ++i_intersection; assert(intrsctn->type == SegmentIntersection::INNER_LOW); try_connect = true; } @@ -1149,92 +1392,20 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP // Decide, whether to finish the segment, or whether to follow the perimeter. // 1) Find possible connection points on the previous / next vertical line. - int iPrev = intersection_on_prev_vertical_line(poly_with_offset, segs, i_vline, intrsctn->iContour, i_intersection); - int iNext = intersection_on_next_vertical_line(poly_with_offset, segs, i_vline, intrsctn->iContour, i_intersection); - IntersectionTypeOtherVLine intrsctn_type_prev = intersection_type_on_prev_vertical_line(segs, i_vline, i_intersection, iPrev); - IntersectionTypeOtherVLine intrsctn_type_next = intersection_type_on_next_vertical_line(segs, i_vline, i_intersection, iNext); - - // 2) Find possible connection points on the same vertical line. - int iAbove = -1; - int iBelow = -1; - int iSegAbove = -1; - int iSegBelow = -1; - { -// SegmentIntersection::SegmentIntersectionType type_crossing = (intrsctn->type == SegmentIntersection::INNER_LOW) ? -// SegmentIntersection::INNER_HIGH : SegmentIntersection::INNER_LOW; - // Does the perimeter intersect the current vertical line above intrsctn? - for (size_t i = i_intersection + 1; i + 1 < seg.intersections.size(); ++ i) -// if (seg.intersections[i].iContour == intrsctn->iContour && seg.intersections[i].type == type_crossing) { - if (seg.intersections[i].iContour == intrsctn->iContour) { - iAbove = i; - iSegAbove = seg.intersections[i].iSegment; - break; - } - // Does the perimeter intersect the current vertical line below intrsctn? - for (size_t i = i_intersection - 1; i > 0; -- i) -// if (seg.intersections[i].iContour == intrsctn->iContour && seg.intersections[i].type == type_crossing) { - if (seg.intersections[i].iContour == intrsctn->iContour) { - iBelow = i; - iSegBelow = seg.intersections[i].iSegment; - break; - } - } - - // 3) Sort the intersection points, clear iPrev / iNext / iSegBelow / iSegAbove, - // if it is preceded by any other intersection point along the contour. - unsigned int vert_seg_dir_valid_mask = - (going_up ? - (iSegAbove != -1 && seg.intersections[iAbove].type == SegmentIntersection::INNER_LOW) : - (iSegBelow != -1 && seg.intersections[iBelow].type == SegmentIntersection::INNER_HIGH)) ? - (DIR_FORWARD | DIR_BACKWARD) : - 0; - { - // Invalidate iPrev resp. iNext, if the perimeter crosses the current vertical line earlier than iPrev resp. iNext. - // The perimeter contour orientation. - const bool forward = intrsctn->is_low(); // == poly_with_offset.is_contour_ccw(intrsctn->iContour); - const Polygon &poly = poly_with_offset.contour(intrsctn->iContour); - { - int d_horiz = (iPrev == -1) ? std::numeric_limits<int>::max() : - distance_of_segmens(poly, segs[i_vline-1].intersections[iPrev].iSegment, intrsctn->iSegment, forward); - int d_down = (iSegBelow == -1) ? std::numeric_limits<int>::max() : - distance_of_segmens(poly, iSegBelow, intrsctn->iSegment, forward); - int d_up = (iSegAbove == -1) ? std::numeric_limits<int>::max() : - distance_of_segmens(poly, iSegAbove, intrsctn->iSegment, forward); - if (intrsctn_type_prev == INTERSECTION_TYPE_OTHER_VLINE_OK && d_horiz > std::min(d_down, d_up)) - // The vertical crossing comes eralier than the prev crossing. - // Disable the perimeter going back. - intrsctn_type_prev = INTERSECTION_TYPE_OTHER_VLINE_NOT_FIRST; - if (going_up ? (d_up > std::min(d_horiz, d_down)) : (d_down > std::min(d_horiz, d_up))) - // The horizontal crossing comes earlier than the vertical crossing. - vert_seg_dir_valid_mask &= ~(forward ? DIR_BACKWARD : DIR_FORWARD); - } - { - int d_horiz = (iNext == -1) ? std::numeric_limits<int>::max() : - distance_of_segmens(poly, intrsctn->iSegment, segs[i_vline+1].intersections[iNext].iSegment, forward); - int d_down = (iSegBelow == -1) ? std::numeric_limits<int>::max() : - distance_of_segmens(poly, intrsctn->iSegment, iSegBelow, forward); - int d_up = (iSegAbove == -1) ? std::numeric_limits<int>::max() : - distance_of_segmens(poly, intrsctn->iSegment, iSegAbove, forward); - if (intrsctn_type_next == INTERSECTION_TYPE_OTHER_VLINE_OK && d_horiz > std::min(d_down, d_up)) - // The vertical crossing comes eralier than the prev crossing. - // Disable the perimeter going forward. - intrsctn_type_next = INTERSECTION_TYPE_OTHER_VLINE_NOT_FIRST; - if (going_up ? (d_up > std::min(d_horiz, d_down)) : (d_down > std::min(d_horiz, d_up))) - // The horizontal crossing comes earlier than the vertical crossing. - vert_seg_dir_valid_mask &= ~(forward ? DIR_FORWARD : DIR_BACKWARD); - } - } - - // 4) Try to connect to a previous or next vertical line, making a zig-zag pattern. + IntersectionTypeOtherVLine intrsctn_type_prev = intersection_type_on_prev_vertical_line(segs, i_vline, i_intersection); + IntersectionTypeOtherVLine intrsctn_type_next = intersection_type_on_next_vertical_line(segs, i_vline, i_intersection); + // Try to connect to a previous or next vertical line, making a zig-zag pattern. if (intrsctn_type_prev == INTERSECTION_TYPE_OTHER_VLINE_OK || intrsctn_type_next == INTERSECTION_TYPE_OTHER_VLINE_OK) { + int iPrev = intrsctn->left_horizontal(); + int iNext = intrsctn->right_horizontal(); coordf_t distPrev = (intrsctn_type_prev != INTERSECTION_TYPE_OTHER_VLINE_OK) ? std::numeric_limits<coord_t>::max() : - measure_perimeter_prev_segment_length(poly_with_offset, segs, i_vline, intrsctn->iContour, i_intersection, iPrev); + measure_perimeter_prev_segment_length(poly_with_offset, segs, i_vline, i_intersection, iPrev); coordf_t distNext = (intrsctn_type_next != INTERSECTION_TYPE_OTHER_VLINE_OK) ? std::numeric_limits<coord_t>::max() : - measure_perimeter_next_segment_length(poly_with_offset, segs, i_vline, intrsctn->iContour, i_intersection, iNext); + measure_perimeter_next_segment_length(poly_with_offset, segs, i_vline, i_intersection, iNext); // Take the shorter path. //FIXME this may not be always the best strategy to take the shortest connection line now. bool take_next = (intrsctn_type_prev == INTERSECTION_TYPE_OTHER_VLINE_OK && intrsctn_type_next == INTERSECTION_TYPE_OTHER_VLINE_OK) ? - (distNext < distPrev) : + (distNext < distPrev) : intrsctn_type_next == INTERSECTION_TYPE_OTHER_VLINE_OK; assert(intrsctn->is_inner()); bool skip = params.dont_connect || (link_max_length > 0 && (take_next ? distNext : distPrev) > link_max_length); @@ -1242,9 +1413,9 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP // Just skip the connecting contour and start a new path. goto dont_connect; polyline_current->points.push_back(Point(seg.pos, intrsctn->pos())); - polylines_out.push_back(Polyline()); - polyline_current = &polylines_out.back(); - const SegmentedIntersectionLine &il2 = segs[take_next ? (i_vline + 1) : (i_vline - 1)]; + polylines_out.push_back(Polyline()); + polyline_current = &polylines_out.back(); + const SegmentedIntersectionLine& il2 = segs[take_next ? (i_vline + 1) : (i_vline - 1)]; polyline_current->points.push_back(Point(il2.pos, il2.intersections[take_next ? iNext : iPrev].pos())); } else { polyline_current->points.push_back(Point(seg.pos, intrsctn->pos())); @@ -1252,97 +1423,94 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP } // Mark both the left and right connecting segment as consumed, because one cannot go to this intersection point as it has been consumed. if (iPrev != -1) - segs[i_vline-1].intersections[iPrev].consumed_perimeter_right = true; + segs[i_vline - 1].intersections[iPrev].consumed_perimeter_right = true; if (iNext != -1) intrsctn->consumed_perimeter_right = true; //FIXME consume the left / right connecting segments at the other end of this line? Currently it is not critical because a perimeter segment is not followed if the vertical segment at the other side has already been consumed. // Advance to the neighbor line. if (take_next) { - ++ i_vline; + ++i_vline; i_intersection = iNext; - } else { - -- i_vline; + } + else { + --i_vline; i_intersection = iPrev; } continue; - } + } // 5) Try to connect to a previous or next point on the same vertical line. - if (vert_seg_dir_valid_mask) { + if (int inext = intrsctn->vertical_outside(); inext != -1) { bool valid = true; // Verify, that there is no intersection with the inner contour up to the end of the contour segment. - // Verify, that the successive segment has not been consumed yet. - if (going_up) { - if (seg.intersections[iAbove].consumed_vertical_up) { - valid = false; - } else { - for (int i = (int)i_intersection + 1; i < iAbove && valid; ++i) - if (seg.intersections[i].is_inner()) - valid = false; - } + // Verify, that the successive segment has not been consumed yet. + if (going_up) { + if (seg.intersections[inext].consumed_vertical_up) + valid = false; + else { + for (int i = (int)i_intersection + 1; i < inext && valid; ++i) + if (seg.intersections[i].is_inner()) + valid = false; + } } else { - if (seg.intersections[iBelow-1].consumed_vertical_up) { - valid = false; - } else { - for (int i = iBelow + 1; i < (int)i_intersection && valid; ++i) - if (seg.intersections[i].is_inner()) - valid = false; - } + if (seg.intersections[inext - 1].consumed_vertical_up) + valid = false; + else { + for (int i = inext + 1; i < (int)i_intersection && valid; ++i) + if (seg.intersections[i].is_inner()) + valid = false; + } } if (valid) { - const Polygon &poly = poly_with_offset.contour(intrsctn->iContour); - int iNext = going_up ? iAbove : iBelow; - int iSegNext = going_up ? iSegAbove : iSegBelow; - bool dir_forward = (vert_seg_dir_valid_mask == (DIR_FORWARD | DIR_BACKWARD)) ? - // Take the shorter length between the current and the next intersection point. - (distance_of_segmens(poly, intrsctn->iSegment, iSegNext, true) < - distance_of_segmens(poly, intrsctn->iSegment, iSegNext, false)) : - (vert_seg_dir_valid_mask == DIR_FORWARD); + const Polygon& poly = poly_with_offset.contour(intrsctn->iContour); + assert(intrsctn->iContour == seg.intersections[inext].iContour); + int iSegNext = seg.intersections[inext].iSegment; // Skip this perimeter line? bool skip = params.dont_connect; + bool dir_forward = intrsctn->has_right_vertical_outside(); if (! skip && link_max_length > 0) { coordf_t link_length = measure_perimeter_segment_on_vertical_line_length( - poly_with_offset, segs, i_vline, intrsctn->iContour, i_intersection, iNext, dir_forward); + poly_with_offset, segs, i_vline, i_intersection, inext, dir_forward); skip = link_length > link_max_length; } polyline_current->points.push_back(Point(seg.pos, intrsctn->pos())); if (skip) { // Just skip the connecting contour and start a new path. - polylines_out.push_back(Polyline()); + polylines_out.push_back(Polyline()); polyline_current = &polylines_out.back(); - polyline_current->points.push_back(Point(seg.pos, seg.intersections[iNext].pos())); + polyline_current->points.push_back(Point(seg.pos, seg.intersections[inext].pos())); } else { // Consume the connecting contour and the next segment. - emit_perimeter_segment_on_vertical_line(poly_with_offset, segs, i_vline, intrsctn->iContour, i_intersection, iNext, *polyline_current, dir_forward); + emit_perimeter_segment_on_vertical_line(poly_with_offset, segs, i_vline, intrsctn->iContour, i_intersection, inext, *polyline_current, dir_forward); } // Mark both the left and right connecting segment as consumed, because one cannot go to this intersection point as it has been consumed. // If there are any outer intersection points skipped (bypassed) by the contour, // mark them as processed. if (going_up) { - for (int i = (int)i_intersection; i < iAbove; ++ i) + for (int i = (int)i_intersection; i < inext; ++i) seg.intersections[i].consumed_vertical_up = true; } else { - for (int i = iBelow; i < (int)i_intersection; ++ i) + for (int i = inext; i < (int)i_intersection; ++i) seg.intersections[i].consumed_vertical_up = true; } -// seg.intersections[going_up ? i_intersection : i_intersection - 1].consumed_vertical_up = true; + // seg.intersections[going_up ? i_intersection : i_intersection - 1].consumed_vertical_up = true; intrsctn->consumed_perimeter_right = true; - i_intersection = iNext; + i_intersection = inext; if (going_up) - ++ intrsctn; + ++intrsctn; else - -- intrsctn; + --intrsctn; intrsctn->consumed_perimeter_right = true; continue; } } - dont_connect: + dont_connect: // No way to continue the current polyline. Take the rest of the line up to the outer contour. // This will finish the polyline, starting another polyline at a new point. if (going_up) - ++ intrsctn; + ++intrsctn; else - -- intrsctn; + --intrsctn; } // Finish the current vertical line, @@ -1353,17 +1521,718 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP polyline_current->points.push_back(pointLast); // Handle duplicate points and zero length segments. polyline_current->remove_duplicate_points(); - assert(! polyline_current->has_duplicate_points()); + assert(!polyline_current->has_duplicate_points()); // Handle nearly zero length edges. if (polyline_current->points.size() <= 1 || - (polyline_current->points.size() == 2 && - std::abs(polyline_current->points.front()(0) - polyline_current->points.back()(0)) < SCALED_EPSILON && - std::abs(polyline_current->points.front()(1) - polyline_current->points.back()(1)) < SCALED_EPSILON)) + (polyline_current->points.size() == 2 && + std::abs(polyline_current->points.front()(0) - polyline_current->points.back()(0)) < SCALED_EPSILON && + std::abs(polyline_current->points.front()(1) - polyline_current->points.back()(1)) < SCALED_EPSILON)) polylines_out.pop_back(); intrsctn = NULL; i_intersection = -1; polyline_current = NULL; } +} + +struct MonotonousRegion; + +struct NextMonotonousRegion +{ + MonotonousRegion *region; + struct Path { + float length { 0 }; // Length of the link to the next region. + float visibility { 0 }; // 1 / length. Which length, just to the next region, or including the path accross the region? + float pheromone { 0 }; // <0, 1> + }; + enum Index : int { + LowLow, + LowHigh, + HighLow, + HighHigh + }; + Path paths[4]; +}; + +struct MonotonousRegion +{ + struct Boundary { + int vline; + int low; + int high; + }; + + Boundary left; + Boundary right; + + // Length when starting at left.low + double len1; + // Length when starting at left.high + double len2; + // If true, then when starting at left.low, then ending at right.high and vice versa. + // If false, then ending at the same side as starting. + bool flips; + + int left_intersection_point(bool region_flipped) const { return region_flipped ? left.high : left.low; } + int right_intersection_point(bool region_flipped) const { return (region_flipped == flips) ? right.low : right.high; } + + // Left regions are used to track whether all regions left to this one have already been printed. + boost::container::small_vector<MonotonousRegion*, 4> left_neighbors; + // Right regions are held to pick a next region to be extruded using the "Ant colony" heuristics. + boost::container::small_vector<NextMonotonousRegion, 4> right_neighbors; +}; + +struct MonotonousRegionLink +{ + MonotonousRegion *region; + bool flipped; + // Distance of right side of this region to left side of the next region, if the "flipped" flag of this region and the next region + // is applied as defined. + NextMonotonousRegion::Path *next; + // Distance of right side of this region to left side of the next region, if the "flipped" flag of this region and the next region + // is applied in reverse order as if the zig-zags were flipped. + NextMonotonousRegion::Path *next_flipped; +}; + +static const SegmentIntersection& vertical_run_bottom(const SegmentedIntersectionLine &vline, const SegmentIntersection &start) +{ + assert(start.is_inner()); + const SegmentIntersection *it = &start; + // Find the lowest SegmentIntersection::INNER_LOW starting with right. + for (;;) { + while (it->type != SegmentIntersection::INNER_LOW) + -- it; + int down = it->vertical_down(); + if (down == -1 || it->vertical_down_quality() != SegmentIntersection::LinkQuality::Valid) + break; + it = &vline.intersections[down]; + } + return *it; +} +static SegmentIntersection& vertical_run_bottom(SegmentedIntersectionLine& vline, SegmentIntersection& start) +{ + return const_cast<SegmentIntersection&>(vertical_run_bottom(std::as_const(vline), std::as_const(start))); +} + +static const SegmentIntersection& vertical_run_top(const SegmentedIntersectionLine &vline, const SegmentIntersection &start) +{ + assert(start.is_inner()); + const SegmentIntersection *it = &start; + // Find the lowest SegmentIntersection::INNER_LOW starting with right. + for (;;) { + while (it->type != SegmentIntersection::INNER_HIGH) + ++ it; + int up = it->vertical_up(); + if (up == -1 || it->vertical_up_quality() != SegmentIntersection::LinkQuality::Valid) + break; + it = &vline.intersections[up]; + } + return *it; +} +static SegmentIntersection& vertical_run_top(SegmentedIntersectionLine& vline, SegmentIntersection& start) +{ + return const_cast<SegmentIntersection&>(vertical_run_top(std::as_const(vline), std::as_const(start))); +} + +static SegmentIntersection* left_overlap_bottom(SegmentIntersection &start, SegmentIntersection &end, SegmentedIntersectionLine &vline_left) +{ + SegmentIntersection *left = nullptr; + for (SegmentIntersection *it = &start; it <= &end; ++ it) { + int i = it->left_horizontal(); + if (i != -1) { + left = &vline_left.intersections[i]; + break; + } + } + return left == nullptr ? nullptr : &vertical_run_bottom(vline_left, *left); +} + +static SegmentIntersection* left_overlap_top(SegmentIntersection &start, SegmentIntersection &end, SegmentedIntersectionLine &vline_left) +{ + SegmentIntersection *left = nullptr; + for (SegmentIntersection *it = &end; it >= &start; -- it) { + int i = it->left_horizontal(); + if (i != -1) { + left = &vline_left.intersections[i]; + break; + } + } + return left == nullptr ? nullptr : &vertical_run_top(vline_left, *left); +} + +static std::pair<SegmentIntersection*, SegmentIntersection*> left_overlap(SegmentIntersection &start, SegmentIntersection &end, SegmentedIntersectionLine &vline_left) +{ + std::pair<SegmentIntersection*, SegmentIntersection*> out(nullptr, nullptr); + out.first = left_overlap_bottom(start, end, vline_left); + if (out.first != nullptr) + out.second = left_overlap_top(start, end, vline_left); + return out; +} + +static std::pair<SegmentIntersection*, SegmentIntersection*> left_overlap(std::pair<SegmentIntersection*, SegmentIntersection*> &start_end, SegmentedIntersectionLine &vline_left) +{ + assert((start_end.first == nullptr) == (start_end.second == nullptr)); + return start_end.first == nullptr ? start_end : left_overlap(*start_end.first, *start_end.second, vline_left); +} + +static SegmentIntersection* right_overlap_bottom(SegmentIntersection &start, SegmentIntersection &end, SegmentedIntersectionLine &vline_right) +{ + SegmentIntersection *right = nullptr; + for (SegmentIntersection *it = &start; it <= &end; ++ it) { + int i = it->right_horizontal(); + if (i != -1) { + right = &vline_right.intersections[i]; + break; + } + } + return right == nullptr ? nullptr : &vertical_run_bottom(vline_right, *right); +} + +static SegmentIntersection* right_overlap_top(SegmentIntersection &start, SegmentIntersection &end, SegmentedIntersectionLine &vline_right) +{ + SegmentIntersection *right = nullptr; + for (SegmentIntersection *it = &end; it >= &start; -- it) { + int i = it->right_horizontal(); + if (i != -1) { + right = &vline_right.intersections[i]; + break; + } + } + return right == nullptr ? nullptr : &vertical_run_top(vline_right, *right); +} + +static std::pair<SegmentIntersection*, SegmentIntersection*> right_overlap(SegmentIntersection &start, SegmentIntersection &end, SegmentedIntersectionLine &vline_right) +{ + std::pair<SegmentIntersection*, SegmentIntersection*> out(nullptr, nullptr); + out.first = right_overlap_bottom(start, end, vline_right); + if (out.first != nullptr) + out.second = right_overlap_top(start, end, vline_right); + return out; +} + +static std::pair<SegmentIntersection*, SegmentIntersection*> right_overlap(std::pair<SegmentIntersection*, SegmentIntersection*> &start_end, SegmentedIntersectionLine &vline_right) +{ + assert((start_end.first == nullptr) == (start_end.second == nullptr)); + return start_end.first == nullptr ? start_end : right_overlap(*start_end.first, *start_end.second, vline_right); +} + +static std::vector<MonotonousRegion> generate_montonous_regions(std::vector<SegmentedIntersectionLine> &segs) +{ + std::vector<MonotonousRegion> monotonous_regions; + + for (size_t i_vline_seed = 0; i_vline_seed < segs.size(); ++ i_vline_seed) { + SegmentedIntersectionLine &vline_seed = segs[i_vline_seed]; + for (size_t i_intersection_seed = 1; i_intersection_seed + 1 < vline_seed.intersections.size(); ) { + while (i_intersection_seed + 1 < vline_seed.intersections.size() && + vline_seed.intersections[i_intersection_seed].type != SegmentIntersection::INNER_LOW) + ++ i_intersection_seed; + SegmentIntersection *start = &vline_seed.intersections[i_intersection_seed]; + SegmentIntersection *end = &end_of_vertical_run_raw(*start); + if (! start->consumed_vertical_up) { + // Draw a new monotonous region starting with this segment. + // while there is only a single right neighbor + start->consumed_vertical_up = true; + size_t i_vline = i_vline_seed; + std::pair<SegmentIntersection*, SegmentIntersection*> left(start, end); + MonotonousRegion region; + region.left.vline = i_vline; + region.left.low = left.first - vline_seed.intersections.data(); + region.left.high = left.second - vline_seed.intersections.data(); + region.right = region.left; + while (++ i_vline < segs.size()) { + SegmentedIntersectionLine &vline_left = segs[i_vline - 1]; + SegmentedIntersectionLine &vline_right = segs[i_vline]; + std::pair<SegmentIntersection*, SegmentIntersection*> right = right_overlap(left, vline_right); + std::pair<SegmentIntersection*, SegmentIntersection*> right_left = left_overlap(right, vline_left); + if (left != right_left) + // Left & right draws don't overlap exclusively. + break; + region.right.vline = i_vline; + region.right.low = right.first - vline_right.intersections.data(); + region.right.high = right.second - vline_right.intersections.data(); + right.first->consumed_vertical_up = true; + left = right; + } + } + i_intersection_seed = end - vline_seed.intersections.data() + 1; + } + } + + return monotonous_regions; +} + +static void connect_monotonous_regions(std::vector<MonotonousRegion> ®ions, std::vector<SegmentedIntersectionLine> &segs) +{ + // Map from low intersection to left / right side of a monotonous region. + using MapType = std::pair<SegmentIntersection*, MonotonousRegion*>; + std::vector<MapType> map_intersection_to_region_start; + std::vector<MapType> map_intersection_to_region_end; + map_intersection_to_region_start.reserve(regions.size()); + map_intersection_to_region_end.reserve(regions.size()); + for (MonotonousRegion ®ion : regions) { + map_intersection_to_region_start.emplace_back(&segs[region.left.vline].intersections[region.left.low], ®ion); + map_intersection_to_region_end.emplace_back(&segs[region.right.vline].intersections[region.right.low], ®ion); + } + auto intersections_lower = [](const MapType &l, const MapType &r){ return l.first < r.first ; }; + auto intersections_equal = [](const MapType &l, const MapType &r){ return l.first == r.first ; }; + std::sort(map_intersection_to_region_start.begin(), map_intersection_to_region_start.end(), intersections_lower); + std::sort(map_intersection_to_region_end.begin(), map_intersection_to_region_end.end(), intersections_lower); + + // Scatter links to neighboring regions. + for (MonotonousRegion ®ion : regions) { + if (region.left.vline > 0) { + auto &vline = segs[region.left.vline]; + auto begin = &vline.intersections[region.left.low]; + auto end = &vline.intersections[region.left.high]; + for (;;) { + MapType key(begin, nullptr); + auto it = std::lower_bound(map_intersection_to_region_end.begin(), map_intersection_to_region_end.end(), key); + assert(it != map_intersection_to_region_end.end() && it->first == key.first); + NextMonotonousRegion next_region{ ®ion }; + it->second->right_neighbors.emplace_back(next_region); + SegmentIntersection *next = &vertical_run_top(vline, *begin); + if (next == end) + break; + while (next->type != SegmentIntersection::INNER_LOW) + ++ next; + begin = next; + } + } + if (region.right.vline + 1 < segs.size()) { + auto &vline = segs[region.right.vline]; + auto begin = &vline.intersections[region.right.low]; + auto end = &vline.intersections[region.right.high]; + for (;;) { + MapType key(begin, nullptr); + auto it = std::lower_bound(map_intersection_to_region_start.begin(), map_intersection_to_region_start.end(), key); + assert(it != map_intersection_to_region_start.end() && it->first == key.first); + it->second->left_neighbors.emplace_back(®ion); + SegmentIntersection *next = &vertical_run_top(vline, *begin); + if (next == end) + break; + while (next->type != SegmentIntersection::INNER_LOW) + ++ next; + begin = next; + } + } + } +} + +// Raad Salman: Algorithms for the Precedence Constrained Generalized Travelling Salesperson Problem +// https://www.chalmers.se/en/departments/math/research/research-groups/optimization/OptimizationMasterTheses/MScThesis-RaadSalman-final.pdf +// Algorithm 6.1 Lexicographic Path Preserving 3-opt +// Optimize path while maintaining the ordering constraints. +void monotonous_3_opt(std::vector<MonotonousRegionLink> &path, std::vector<SegmentedIntersectionLine> &segs) +{ + // When doing the 3-opt path preserving flips, one has to fulfill two constraints: + // + // 1) The new path should be shorter than the old path. + // 2) The precedence constraints shall be satisified on the new path. + // + // Branch & bound with KD-tree may be used with the shorter path constraint, but the precedence constraint will have to be recalculated for each + // shorter path candidate found, which has a quadratic cost for a dense precedence graph. For a sparse precedence graph the precedence + // constraint verification will be cheaper. + // + // On the other side, if the full search space is traversed as in the diploma thesis by Raad Salman (page 24, Algorithm 6.1 Lexicographic Path Preserving 3-opt), + // then the precedence constraint verification is amortized inside the O(n^3) loop. Now which is better for our task? + // + // It is beneficial to also try flipping of the infill zig-zags, for which a prefix sum of both flipped and non-flipped paths over + // MonotonousRegionLinks may be utilized, however updating the prefix sum has a linear complexity, the same complexity as doing the 3-opt + // exchange by copying the pieces. +} + +// Find a run through monotonous infill blocks using an 'Ant colony" optimization method. +static std::vector<MonotonousRegionLink> chain_monotonous_regions( + std::vector<MonotonousRegion> ®ions, std::vector<SegmentedIntersectionLine> &segs, std::mt19937_64 &rng) +{ + // Start point of a region (left) given the direction of the initial infill line. + auto region_start_point = [&segs](const MonotonousRegion ®ion, bool dir) { + SegmentedIntersectionLine &vline = segs[region.left.vline]; + SegmentIntersection &ipt = vline.intersections[dir ? region.left.high : region.left.low]; + return Vec2f(float(vline.pos), float(ipt.pos())); + }; + // End point of a region (right) given the direction of the initial infill line and whether the monotonous run contains + // even or odd number of vertical lines. + auto region_end_point = [&segs](const MonotonousRegion ®ion, bool dir) { + SegmentedIntersectionLine &vline = segs[region.right.vline]; + SegmentIntersection &ipt = vline.intersections[(dir == region.flips) ? region.right.low : region.right.high]; + return Vec2f(float(vline.pos), float(ipt.pos())); + }; + + // Number of left neighbors (regions that this region depends on, this region cannot be printed before the regions left of it are printed). + std::vector<int32_t> left_neighbors_unprocessed(regions.size(), 0); + // Queue of regions, which have their left neighbors already printed. + std::vector<MonotonousRegion*> queue; + queue.reserve(regions.size()); + for (MonotonousRegion ®ion : regions) + if (region.left_neighbors.empty()) + queue.emplace_back(®ion); + else + left_neighbors_unprocessed[®ion - regions.data()] = region.left_neighbors.size(); + // Make copy of structures that need to be initialized at each ant iteration. + auto left_neighbors_unprocessed_initial = left_neighbors_unprocessed; + auto queue_initial = queue; + + std::vector<MonotonousRegionLink> path, best_path; + path.reserve(regions.size()); + best_path.reserve(regions.size()); + float best_path_length = std::numeric_limits<float>::max(); + + struct NextCandidate { + NextMonotonousRegion *region; + NextMonotonousRegion::Path *link; + NextMonotonousRegion::Path *link_flipped; + float cost; + bool dir; + }; + std::vector<NextCandidate> next_candidates; + + // How many times to repeat the ant simulation. + constexpr int num_runs = 10; + // With how many ants each of the run will be performed? + constexpr int num_ants = 10; + // Base (initial) pheromone level. + constexpr float pheromone_initial_deposit = 0.5f; + // Evaporation rate of pheromones. + constexpr float pheromone_evaporation = 0.1f; + // Probability at which to take the next best path. Otherwise take the the path based on the cost distribution. + constexpr float probability_take_best = 0.9f; + // Exponents of the cost function. + constexpr float pheromone_alpha = 1.f; // pheromone exponent + constexpr float pheromone_beta = 2.f; // attractiveness weighted towards edge length + // Cost of traversing a link between two monotonous regions. + auto path_cost = [pheromone_alpha, pheromone_beta](NextMonotonousRegion::Path &path) { + return pow(path.pheromone, pheromone_alpha) * pow(path.visibility, pheromone_beta); + }; + for (int run = 0; run < num_runs; ++ run) + { + for (int ant = 0; ant < num_ants; ++ ant) + { + // Find a new path following the pheromones deposited by the previous ants. + path.clear(); + queue = queue_initial; + left_neighbors_unprocessed = left_neighbors_unprocessed_initial; + while (! queue.empty()) { + // Sort the queue by distance to the last point. + // Take a candidate based on shortest distance? or ant colony? + if (path.empty()) { + // Pick randomly the first from the queue at random orientation. + int first_idx = std::uniform_int_distribution<>(0, int(queue.size()) - 1)(rng); + path.emplace_back(MonotonousRegionLink{ queue[first_idx], rng() > rng.max() / 2 }); + *(queue.begin() + first_idx) = std::move(queue.back()); + queue.pop_back(); + } else { + // Pick the closest neighbor from the queue? + } + -- left_neighbors_unprocessed[path.back().region - regions.data()]; + while (! path.back().region->right_neighbors.empty()) { + // Chain. + MonotonousRegion ®ion = *path.back().region; + bool dir = path.back().flipped; + Vec2f end_pt = region_end_point(region, dir); + // Sort by distance to pt. + next_candidates.reserve(region.right_neighbors.size() * 2); + for (NextMonotonousRegion &next : region.right_neighbors) { + int unprocessed = left_neighbors_unprocessed[next.region - regions.data()]; + assert(unprocessed > 0); + if (unprocessed == 1) { + // Dependencies of the successive blocks are satisfied. + bool flip = dir == region.flips; + auto path_cost = [pheromone_alpha, pheromone_beta](NextMonotonousRegion::Path& path) { + return pow(path.pheromone, pheromone_alpha) * pow(path.visibility, pheromone_beta); + }; + NextMonotonousRegion::Path &path_low = next.paths[flip ? NextMonotonousRegion::HighLow : NextMonotonousRegion::LowLow]; + NextMonotonousRegion::Path &path_low_flipped = next.paths[flip ? NextMonotonousRegion::LowHigh : NextMonotonousRegion::HighHigh]; + NextMonotonousRegion::Path &path_high = next.paths[flip ? NextMonotonousRegion::HighHigh : NextMonotonousRegion::LowHigh]; + NextMonotonousRegion::Path &path_high_flipped = next.paths[flip ? NextMonotonousRegion::LowLow : NextMonotonousRegion::HighLow]; + next_candidates.emplace_back(NextCandidate{ &next, &path_low, &path_low_flipped, path_cost(path_low), false }); + next_candidates.emplace_back(NextCandidate{ &next, &path_high, &path_high_flipped, path_cost(path_high), true }); + } + } + //std::sort(next_candidates.begin(), next_candidates.end(), [](const auto &l, const auto &r) { l.dist < r.dist; }); + float dice = float(rng()) / float(rng.max()); + std::vector<NextCandidate>::iterator take_path; + if (dice < probability_take_best) { + // Take the lowest cost path. + take_path = std::min_element(next_candidates.begin(), next_candidates.end(), [](auto &l, auto &r){ return l.cost < r.cost; }); + } else { + // Take the path based on the cost. + // Calculate the total cost. + float total_cost = std::accumulate(next_candidates.begin(), next_candidates.end(), 0.f, [](const float l, const NextCandidate& r) { return l + r.cost; }); + // Take a random path based on the cost. + float cost_threshold = floor(float(rng()) * total_cost / float(rng.max())); + take_path = next_candidates.end(); + -- take_path; + for (auto it = next_candidates.begin(); it < next_candidates.end(); ++ it) + if (cost_threshold -= it->cost <= 0.) { + take_path = it; + break; + } + } + // Extend the path. + NextMonotonousRegion &next_region = *take_path->region; + bool next_dir = take_path->dir; + path.back().next = take_path->link; + path.back().next_flipped = take_path->link_flipped; + path.emplace_back(MonotonousRegionLink{ next_region.region, next_dir }); + // Decrease the number of next block dependencies. + -- left_neighbors_unprocessed[next_region.region - regions.data()]; + // Update pheromones along this link. + take_path->link->pheromone = (1.f - pheromone_evaporation) * take_path->link->pheromone + pheromone_evaporation * pheromone_initial_deposit; + } + } + + // Perform 3-opt local optimization of the path. + monotonous_3_opt(path, segs); + + // Measure path length. + float path_length = std::accumulate(path.begin(), path.end(), 0.f, [](const float l, const MonotonousRegionLink& r) { return l + r.next->length; }); + // Save the shortest path. + if (path_length < best_path_length) { + best_path_length = path_length; + std::swap(best_path_length, path_length); + } + } + + // Reinforce the path feromones with the best path. + float total_cost = best_path_length; + for (MonotonousRegionLink &link : path) + link.next->pheromone = (1.f - pheromone_evaporation) * link.next->pheromone + pheromone_evaporation / total_cost; + } + + return best_path; +} + +// Traverse path, produce polylines. +static void polylines_from_paths(const std::vector<MonotonousRegionLink> &path, const ExPolygonWithOffset &poly_with_offset, const std::vector<SegmentedIntersectionLine> &segs, Polylines &polylines_out) +{ + Polyline *polyline = nullptr; + auto finish_polyline = [&polyline, &polylines_out]() { + polyline->remove_duplicate_points(); + // Handle duplicate points and zero length segments. + assert(!polyline->has_duplicate_points()); + // Handle nearly zero length edges. + if (polyline->points.size() <= 1 || + (polyline->points.size() == 2 && + std::abs(polyline->points.front()(0) - polyline->points.back()(0)) < SCALED_EPSILON && + std::abs(polyline->points.front()(1) - polyline->points.back()(1)) < SCALED_EPSILON)) + polylines_out.pop_back(); + polyline = nullptr; + }; + + for (const MonotonousRegionLink &path_segment : path) { + MonotonousRegion ®ion = *path_segment.region; + bool dir = path_segment.flipped; + + // From the initial point (i_vline, i_intersection), follow a path. + int i_intersection = region.left_intersection_point(dir); + int i_vline = region.left.vline; + + if (polyline != nullptr && &path_segment != path.data()) { + // Connect previous path segment with the new one. + const MonotonousRegionLink &path_segment_prev = *(&path_segment - 1); + const MonotonousRegion ®ion_prev = *path_segment_prev.region; + bool dir_prev = path_segment_prev.flipped; + int i_vline_prev = region_prev.right.vline; + const SegmentedIntersectionLine &vline_prev = segs[i_vline_prev]; + int i_intersection_prev = region_prev.right_intersection_point(dir_prev); + const SegmentIntersection *ip_prev = &vline_prev.intersections[i_intersection_prev]; + bool extended = false; + if (i_vline_prev + 1 == i_vline) { + if (ip_prev->right_horizontal() == i_intersection && ip_prev->next_on_contour_quality == SegmentIntersection::LinkQuality::Valid) { + // Emit a horizontal connection contour. + emit_perimeter_prev_next_segment(poly_with_offset, segs, i_vline_prev, ip_prev->iContour, i_intersection_prev, i_intersection, *polyline, true); + extended = true; + } + } + if (! extended) { + // Finish the current vertical line, + assert(ip_prev->is_inner()); + ip_prev->is_low() ? -- ip_prev : ++ ip_prev; + assert(ip_prev->is_outer()); + polyline->points.back() = Point(vline_prev.pos, ip_prev->pos()); + finish_polyline(); + } + } + + for (;;) { + const SegmentedIntersectionLine &seg = segs[i_vline]; + const SegmentIntersection *intrsctn = &seg.intersections[i_intersection]; + const bool going_up = intrsctn->is_low(); + if (polyline == nullptr) { + polylines_out.emplace_back(); + polyline = &polylines_out.back(); + // Extend the infill line up to the outer contour. + polyline->points.emplace_back(seg.pos, (intrsctn + (going_up ? - 1 : 1))->pos()); + } else + polyline->points.emplace_back(seg.pos, intrsctn->pos()); + + int iright = intrsctn->right_horizontal(); + if (going_up) { + // Consume the complete vertical segment up to the inner contour. + for (;;) { + do { + ++ intrsctn; + iright = std::max(iright, intrsctn->right_horizontal()); + } while (intrsctn->type != SegmentIntersection::INNER_HIGH); + polyline->points.emplace_back(seg.pos, intrsctn->pos()); + int inext = intrsctn->vertical_up(); + if (inext == -1) + break; + const Polygon &poly = poly_with_offset.contour(intrsctn->iContour); + assert(intrsctn->iContour == seg.intersections[inext].iContour); + emit_perimeter_segment_on_vertical_line(poly_with_offset, segs, i_vline, intrsctn->iContour, i_intersection, inext, *polyline, intrsctn->has_right_vertical_up()); + intrsctn = seg.intersections.data() + inext; + } + } else { + // Going down. + assert(intrsctn->is_high()); + assert(i_intersection > 0); + for (;;) { + do { + -- intrsctn; + if (int iright_new = intrsctn->right_horizontal(); iright_new != -1) + iright = iright_new; + } while (intrsctn->type != SegmentIntersection::INNER_LOW); + polyline->points.emplace_back(seg.pos, intrsctn->pos()); + int inext = intrsctn->vertical_down(); + if (inext == -1) + break; + const Polygon &poly = poly_with_offset.contour(intrsctn->iContour); + assert(intrsctn->iContour == seg.intersections[inext].iContour); + emit_perimeter_segment_on_vertical_line(poly_with_offset, segs, i_vline, intrsctn->iContour, intrsctn - seg.intersections.data(), inext, *polyline, intrsctn->has_right_vertical_down()); + intrsctn = seg.intersections.data() + inext; + } + } + + if (i_vline == region.right.vline) + break; + + int inext = intrsctn->right_horizontal(); + if (inext != -1 && intrsctn->next_on_contour_quality == SegmentIntersection::LinkQuality::Valid) { + // Emit a horizontal connection contour. + emit_perimeter_prev_next_segment(poly_with_offset, segs, i_vline, intrsctn->iContour, intrsctn - seg.intersections.data(), inext, *polyline, true); + i_intersection = inext; + } else { + // Finish the current vertical line, + going_up ? ++ intrsctn : -- intrsctn; + assert(intrsctn->is_outer()); + assert(intrsctn->is_high() == going_up); + polyline->points.back() = Point(seg.pos, intrsctn->pos()); + finish_polyline(); + if (inext == -1) { + // Find the end of the next overlapping vertical segment. + const SegmentedIntersectionLine &vline_right = segs[i_vline + 1]; + const SegmentIntersection *right = going_up ? + &vertical_run_top(vline_right, vline_right.intersections[iright]) : &vertical_run_bottom(vline_right, vline_right.intersections[iright]); + i_intersection = right - vline_right.intersections.data(); + } else + i_intersection = inext; + } + + ++ i_vline; + } + } +} + +bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillParams ¶ms, float angleBase, float pattern_shift, Polylines &polylines_out) +{ + // At the end, only the new polylines will be rotated back. + size_t n_polylines_out_initial = polylines_out.size(); + + // Shrink the input polygon a bit first to not push the infill lines out of the perimeters. +// const float INFILL_OVERLAP_OVER_SPACING = 0.3f; + const float INFILL_OVERLAP_OVER_SPACING = 0.45f; + assert(INFILL_OVERLAP_OVER_SPACING > 0 && INFILL_OVERLAP_OVER_SPACING < 0.5f); + + // Rotate polygons so that we can work with vertical lines here + std::pair<float, Point> rotate_vector = this->_infill_direction(surface); + rotate_vector.first += angleBase; + + assert(params.density > 0.0001f && params.density <= 1.f); + coord_t line_spacing = coord_t(scale_(this->spacing) / params.density); + + // On the polygons of poly_with_offset, the infill lines will be connected. + ExPolygonWithOffset poly_with_offset( + surface->expolygon, + - rotate_vector.first, + scale_(this->overlap - (0.5 - INFILL_OVERLAP_OVER_SPACING) * this->spacing), + scale_(this->overlap - 0.5 * this->spacing)); + if (poly_with_offset.n_contours_inner == 0) { + // Not a single infill line fits. + //FIXME maybe one shall trigger the gap fill here? + return true; + } + + BoundingBox bounding_box = poly_with_offset.bounding_box_src(); + + // define flow spacing according to requested density + if (params.full_infill() && !params.dont_adjust) { + line_spacing = this->_adjust_solid_spacing(bounding_box.size()(0), line_spacing); + this->spacing = unscale<double>(line_spacing); + } else { + // extend bounding box so that our pattern will be aligned with other layers + // Transform the reference point to the rotated coordinate system. + Point refpt = rotate_vector.second.rotated(- rotate_vector.first); + // _align_to_grid will not work correctly with positive pattern_shift. + coord_t pattern_shift_scaled = coord_t(scale_(pattern_shift)) % line_spacing; + refpt(0) -= (pattern_shift_scaled >= 0) ? pattern_shift_scaled : (line_spacing + pattern_shift_scaled); + bounding_box.merge(_align_to_grid( + bounding_box.min, + Point(line_spacing, line_spacing), + refpt)); + } + + // Intersect a set of euqally spaced vertical lines wiht expolygon. + // n_vlines = ceil(bbox_width / line_spacing) + size_t n_vlines = (bounding_box.max(0) - bounding_box.min(0) + line_spacing - 1) / line_spacing; + coord_t x0 = bounding_box.min(0); + if (params.full_infill()) + x0 += (line_spacing + SCALED_EPSILON) / 2; + +#ifdef SLIC3R_DEBUG + static int iRun = 0; + BoundingBox bbox_svg = poly_with_offset.bounding_box_outer(); + ::Slic3r::SVG svg(debug_out_path("FillRectilinear2-%d.svg", iRun), bbox_svg); // , scale_(1.)); + poly_with_offset.export_to_svg(svg); + { + ::Slic3r::SVG svg(debug_out_path("FillRectilinear2-initial-%d.svg", iRun), bbox_svg); // , scale_(1.)); + poly_with_offset.export_to_svg(svg); + } + iRun ++; +#endif /* SLIC3R_DEBUG */ + + std::vector<SegmentedIntersectionLine> segs = slice_region_by_vertical_lines(poly_with_offset, n_vlines, x0, line_spacing); + connect_segment_intersections_by_contours(poly_with_offset, segs); + +#ifdef SLIC3R_DEBUG + // Paint the segments and finalize the SVG file. + for (size_t i_seg = 0; i_seg < segs.size(); ++ i_seg) { + SegmentedIntersectionLine &sil = segs[i_seg]; + for (size_t i = 0; i < sil.intersections.size();) { + size_t j = i + 1; + for (; j < sil.intersections.size() && sil.intersections[j].is_inner(); ++ j) ; + if (i + 1 == j) { + svg.draw(Line(Point(sil.pos, sil.intersections[i].pos()), Point(sil.pos, sil.intersections[j].pos())), "blue"); + } else { + svg.draw(Line(Point(sil.pos, sil.intersections[i].pos()), Point(sil.pos, sil.intersections[i+1].pos())), "green"); + svg.draw(Line(Point(sil.pos, sil.intersections[i+1].pos()), Point(sil.pos, sil.intersections[j-1].pos())), (j - i + 1 > 4) ? "yellow" : "magenta"); + svg.draw(Line(Point(sil.pos, sil.intersections[j-1].pos()), Point(sil.pos, sil.intersections[j].pos())), "green"); + } + i = j + 1; + } + } + svg.Close(); +#endif /* SLIC3R_DEBUG */ + + bool monotonous_infill = params.density > 0.99; + if (monotonous_infill) { + std::vector<MonotonousRegion> regions = generate_montonous_regions(segs); + connect_monotonous_regions(regions, segs); + std::mt19937_64 rng; + std::vector<MonotonousRegionLink> path = chain_monotonous_regions(regions, segs, rng); + polylines_from_paths(path, poly_with_offset, segs, polylines_out); + } else + traverse_graph_generate_polylines(poly_with_offset, params, this->link_max_length, segs, polylines_out); #ifdef SLIC3R_DEBUG { diff --git a/src/libslic3r/libslic3r.h b/src/libslic3r/libslic3r.h index 1cf946f8b..f6fbba994 100644 --- a/src/libslic3r/libslic3r.h +++ b/src/libslic3r/libslic3r.h @@ -25,6 +25,7 @@ // Saves around 32% RAM after slicing step, 6.7% after G-code export (tested on PrusaSlicer 2.2.0 final). typedef int32_t coord_t; #else +//FIXME At least FillRectilinear2 requires coord_t to be 32bit. typedef int64_t coord_t; #endif |