#include <src/libslic3r/Fill/FillLine.hpp>

Inheritance diagram for Slic3r::FillLine:

Collaboration diagram for Slic3r::FillLine:

Public Member Functions
Fill *	clone () const override

	~FillLine () override=default

virtual bool	use_bridge_flow () const

void	set_bounding_box (const Slic3r::BoundingBox &bbox)

virtual bool	no_sort () const

virtual Polylines	fill_surface (const Surface *surface, const FillParams &params)

virtual ThickPolylines	fill_surface_arachne (const Surface *surface, const FillParams &params)

virtual std::pair< float, Point >	_infill_direction (const Surface *surface) const

Static Public Member Functions
static Fill *	new_from_type (const InfillPattern type)

static Fill *	new_from_type (const std::string &type)

static bool	use_bridge_flow (const InfillPattern type)

static void	connect_infill (Polylines &&infill_ordered, const ExPolygon &boundary, Polylines &polylines_out, const double spacing, const FillParams &params)

static void	connect_infill (Polylines &&infill_ordered, const Polygons &boundary, const BoundingBox &bbox, Polylines &polylines_out, const double spacing, const FillParams &params)

static void	connect_infill (Polylines &&infill_ordered, const std::vector< const Polygon * > &boundary, const BoundingBox &bbox, Polylines &polylines_out, double spacing, const FillParams &params)

static void	connect_base_support (Polylines &&infill_ordered, const std::vector< const Polygon * > &boundary_src, const BoundingBox &bbox, Polylines &polylines_out, const double spacing, const FillParams &params)

static void	connect_base_support (Polylines &&infill_ordered, const Polygons &boundary_src, const BoundingBox &bbox, Polylines &polylines_out, const double spacing, const FillParams &params)

static coord_t	_adjust_solid_spacing (const coord_t width, const coord_t distance)

Public Attributes
size_t	layer_id

coordf_t	z

coordf_t	spacing

coordf_t	overlap

float	angle

coord_t	link_max_length

coord_t	loop_clipping

BoundingBox	bounding_box

FillAdaptive::Octree *	adapt_fill_octree = nullptr

const PrintConfig *	print_config = nullptr

const PrintObjectConfig *	print_object_config = nullptr

Protected Member Functions
void	_fill_surface_single (const FillParams &params, unsigned int thickness_layers, const std::pair< float, Point > &direction, ExPolygon expolygon, Polylines &polylines_out) override

Line	_line (int i, coord_t x, coord_t y_min, coord_t y_max) const

bool	_can_connect (coord_t dist_X, coord_t dist_Y)

virtual void	_fill_surface_single (const FillParams &params, unsigned int thickness_layers, const std::pair< float, Point > &direction, ExPolygon expolygon, ThickPolylines &thick_polylines_out)

virtual float	_layer_angle (size_t idx) const

Protected Attributes
coord_t	_min_spacing

coord_t	_line_spacing

coord_t	_diagonal_distance

coord_t	_line_oscillation

Detailed Description

Constructor & Destructor Documentation

◆ ~FillLine()

Slic3r::FillLine::~FillLine ( )

overridedefault

Member Function Documentation

◆ _adjust_solid_spacing()

coord_t Slic3r::Fill::_adjust_solid_spacing	(	const coord_t	width,
		const coord_t	distance
	)

staticinherited

{
    assert(width >= 0);
    assert(distance > 0);
    // floor(width / distance)
    const auto  number_of_intervals = coord_t((width - EPSILON) / distance);
    coord_t     distance_new        = (number_of_intervals == 0) ? 
        distance : 
        coord_t((width - EPSILON) / number_of_intervals);
    const coordf_t factor = coordf_t(distance_new) / coordf_t(distance);
    assert(factor > 1. - 1e-5);
    // How much could the extrusion width be increased? By 20%.
    const coordf_t factor_max = 1.2;
    if (factor > factor_max)
        distance_new = coord_t(floor((coordf_t(distance) * factor_max + 0.5)));
    return distance_new;
}

References EPSILON, and floor().

Referenced by Slic3r::FillConcentric::_fill_surface_single(), _fill_surface_single(), and Slic3r::FillRectilinear::fill_surface_by_lines().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _can_connect()

bool Slic3r::FillLine::_can_connect	(	coord_t	dist_X,
		coord_t	dist_Y
	)

inlineprotected

  {
      const auto TOLERANCE = coord_t(10 * SCALED_EPSILON);
      return (dist_X >= (this->_line_spacing - this->_line_oscillation) - TOLERANCE)
          && (dist_X <= (this->_line_spacing + this->_line_oscillation) + TOLERANCE)
          && (dist_Y <= this->_diagonal_distance);
    }

References _diagonal_distance, _line_oscillation, SCALED_EPSILON, and TOLERANCE.

Referenced by _fill_surface_single().

Here is the caller graph for this function:

◆ _fill_surface_single() [1/2]

void Slic3r::FillLine::_fill_surface_single	(	const FillParams &	params,
		unsigned int	thickness_layers,
		const std::pair< float, Point > &	direction,
		ExPolygon	expolygon,
		Polylines &	polylines_out
	)

overrideprotectedvirtual

Reimplemented from Slic3r::Fill.

{
    // rotate polygons so that we can work with vertical lines here
    expolygon.rotate(- direction.first);
 
    this->_min_spacing = scale_(this->spacing);
    assert(params.density > 0.0001f && params.density <= 1.f);
    this->_line_spacing = coord_t(coordf_t(this->_min_spacing) / params.density);
    this->_diagonal_distance = this->_line_spacing * 2;
    this->_line_oscillation = this->_line_spacing - this->_min_spacing; // only for Line infill
    BoundingBox bounding_box = expolygon.contour.bounding_box();
    
    // define flow spacing according to requested density
    if (params.density > 0.9999f && !params.dont_adjust) {
        this->_line_spacing = this->_adjust_solid_spacing(bounding_box.size()(0), this->_line_spacing);
        this->spacing = unscale<double>(this->_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.
        bounding_box.merge(align_to_grid(
            bounding_box.min, 
            Point(this->_line_spacing, this->_line_spacing), 
            direction.second.rotated(- direction.first)));
    }
 
    // generate the basic pattern
    coord_t x_max = bounding_box.max(0) + SCALED_EPSILON;
    Lines lines;
    for (coord_t x = bounding_box.min(0); x <= x_max; x += this->_line_spacing)
        lines.push_back(this->_line(lines.size(), x, bounding_box.min(1), bounding_box.max(1)));
 
    // clip paths against a slightly larger expolygon, so that the first and last paths
    // are kept even if the expolygon has vertical sides
    // the minimum offset for preventing edge lines from being clipped is SCALED_EPSILON;
    // however we use a larger offset to support expolygons with slightly skewed sides and 
    // not perfectly straight
    //FIXME Vojtech: Update the intersecton function to work directly with lines.
    Polylines polylines_src;
    polylines_src.reserve(lines.size());
    for (Lines::const_iterator it = lines.begin(); it != lines.end(); ++ it) {
        polylines_src.push_back(Polyline());
        Points &pts = polylines_src.back().points;
        pts.reserve(2);
        pts.push_back(it->a);
        pts.push_back(it->b);
    }
    Polylines polylines = intersection_pl(polylines_src, offset(expolygon, scale_(0.02)));
 
    // FIXME Vojtech: This is only performed for horizontal lines, not for the vertical lines!
    const float INFILL_OVERLAP_OVER_SPACING = 0.3f;
    // How much to extend an infill path from expolygon outside?
    coord_t extra = coord_t(floor(this->_min_spacing * INFILL_OVERLAP_OVER_SPACING + 0.5f));
    for (Polylines::iterator it_polyline = polylines.begin(); it_polyline != polylines.end(); ++ it_polyline) {
        Point *first_point = &it_polyline->points.front();
        Point *last_point  = &it_polyline->points.back();
        if (first_point->y() > last_point->y())
            std::swap(first_point, last_point);
        first_point->y() -= extra;
        last_point->y() += extra;
    }
 
    size_t n_polylines_out_old = polylines_out.size();
 
    // connect lines
    if (! params.dont_connect() && ! polylines.empty()) { // prevent calling leftmost_point() on empty collections
        // offset the expolygon by max(min_spacing/2, extra)
        ExPolygon expolygon_off;
        {
            ExPolygons expolygons_off = offset_ex(expolygon, this->_min_spacing/2);
            if (! expolygons_off.empty()) {
                // When expanding a polygon, the number of islands could only shrink. Therefore the offset_ex shall generate exactly one expanded island for one input island.
                assert(expolygons_off.size() == 1);
                std::swap(expolygon_off, expolygons_off.front());
            }
        }
        bool first = true;
        for (Polyline &polyline : chain_polylines(std::move(polylines))) {
            if (! first) {
                // Try to connect the lines.
                Points &pts_end = polylines_out.back().points;
                const Point &first_point = polyline.points.front();
                const Point &last_point = pts_end.back();
                // Distance in X, Y.
                const Vector distance = last_point - first_point;
                // TODO: we should also check that both points are on a fill_boundary to avoid 
                // connecting paths on the boundaries of internal regions
                if (this->_can_connect(std::abs(distance(0)), std::abs(distance(1))) && 
                    expolygon_off.contains(Line(last_point, first_point))) {
                    // Append the polyline.
                    pts_end.insert(pts_end.end(), polyline.points.begin(), polyline.points.end());
                    continue;
                }
            }
            // The lines cannot be connected.
            polylines_out.emplace_back(std::move(polyline));
            first = false;
        }
    }
 
    // paths must be rotated back
    for (Polylines::iterator it = polylines_out.begin() + n_polylines_out_old; it != polylines_out.end(); ++ it) {
        // No need to translate, the absolute position is irrelevant.
        // it->translate(- direction.second(0), - direction.second(1));
        it->rotate(direction.first);
    }
}

References Slic3r::Fill::_adjust_solid_spacing(), _can_connect(), _diagonal_distance, _line_oscillation, _line_spacing, _min_spacing, Slic3r::align_to_grid(), Slic3r::Fill::bounding_box, Slic3r::MultiPoint::bounding_box(), Slic3r::chain_polylines(), Slic3r::ExPolygon::contains(), Slic3r::ExPolygon::contour, Slic3r::FillParams::density, Slic3r::FillParams::dont_adjust, Slic3r::FillParams::dont_connect(), floor(), Slic3r::intersection_pl(), Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::BoundingBoxBase< PointType, APointsType >::min, Slic3r::offset(), Slic3r::offset_ex(), Slic3r::ExPolygon::rotate(), Slic3r::Point::rotate(), Slic3r::Point::rotated(), scale_, SCALED_EPSILON, Slic3r::BoundingBoxBase< PointType, APointsType >::size(), and Slic3r::Fill::spacing.

Here is the call graph for this function:

◆ _fill_surface_single() [2/2]

virtual void Slic3r::Fill::_fill_surface_single	(	const FillParams &	params,
		unsigned int	thickness_layers,
		const std::pair< float, Point > &	direction,
		ExPolygon	expolygon,
		ThickPolylines &	thick_polylines_out
	)

inlineprotectedvirtualinherited

Reimplemented in Slic3r::FillConcentric.

146 {}

◆ _infill_direction()

std::pair< float, Point > Slic3r::Fill::_infill_direction ( const Surface * surface ) const

virtualinherited

{
    // set infill angle
    float out_angle = this->angle;
 
  if (out_angle == FLT_MAX) {
        assert(false);
        BOOST_LOG_TRIVIAL(error) << "Using undefined infill angle";
        out_angle = 0.f;
    }
 
    // Bounding box is the bounding box of a perl object Slic3r::Print::Object (c++ object Slic3r::PrintObject)
    // The bounding box is only undefined in unit tests.
    Point out_shift = empty(this->bounding_box) ? 
      surface->expolygon.contour.bounding_box().center() : 
        this->bounding_box.center();
 
#if 0
    if (empty(this->bounding_box)) {
        printf("Fill::_infill_direction: empty bounding box!");
    } else {
        printf("Fill::_infill_direction: reference point %d, %d\n", out_shift.x, out_shift.y);
    }
#endif
 
    if (surface->bridge_angle >= 0) {
      // use bridge angle
    //FIXME Vojtech: Add a debugf?
        // Slic3r::debugf "Filling bridge with angle %d\n", rad2deg($surface->bridge_angle);
#ifdef SLIC3R_DEBUG
        printf("Filling bridge with angle %f\n", surface->bridge_angle);
#endif /* SLIC3R_DEBUG */
        out_angle = float(surface->bridge_angle);
    } else if (this->layer_id != size_t(-1)) {
        // alternate fill direction
        out_angle += this->_layer_angle(this->layer_id / surface->thickness_layers);
    } else {
//      printf("Layer_ID undefined!\n");
    }
 
    out_angle += float(M_PI/2.);
    return std::pair<float, Point>(out_angle, out_shift);
}

References Slic3r::Fill::_layer_angle(), Slic3r::Fill::angle, Slic3r::Fill::bounding_box, Slic3r::MultiPoint::bounding_box(), Slic3r::Surface::bridge_angle, Slic3r::BoundingBoxBase< PointType, APointsType >::center(), Slic3r::ExPolygon::contour, Slic3r::empty(), error, Slic3r::Surface::expolygon, Slic3r::Fill::layer_id, M_PI, and Slic3r::Surface::thickness_layers.

Referenced by Slic3r::Fill::fill_surface(), Slic3r::FillSupportBase::fill_surface(), Slic3r::Fill::fill_surface_arachne(), Slic3r::FillRectilinear::fill_surface_by_lines(), Slic3r::FillRectilinear::fill_surface_by_multilines(), and Slic3r::make_fill_polylines().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _layer_angle()

virtual float Slic3r::Fill::_layer_angle ( size_t idx ) const

inlineprotectedvirtualinherited

Reimplemented in Slic3r::FillHoneycomb, Slic3r::FillPlanePath, Slic3r::FillAlignedRectilinear, Slic3r::FillGrid, Slic3r::FillTriangles, Slic3r::FillStars, Slic3r::FillCubic, and Slic3r::FillSupportBase.

148{ return (idx & 1) ? float(M_PI/2.) : 0; }

References M_PI.

Referenced by Slic3r::Fill::_infill_direction().

Here is the caller graph for this function:

◆ _line()

Line Slic3r::FillLine::_line	(	int	i,
		coord_t	x,
		coord_t	y_min,
		coord_t	y_max
	)		const

inlineprotected

                                                                   {
    coord_t osc = (i & 1) ? this->_line_oscillation : 0;
    return Line(Point(x - osc, y_min), Point(x + osc, y_max));
  }

◆ clone()

Fill * Slic3r::FillLine::clone ( ) const

inlineoverridevirtual

Implements Slic3r::Fill.

15{ return new FillLine(*this); };

◆ connect_base_support() [1/2]

void Slic3r::Fill::connect_base_support	(	Polylines &&	infill_ordered,
		const Polygons &	boundary_src,
		const BoundingBox &	bbox,
		Polylines &	polylines_out,
		const double	spacing,
		const FillParams &	params
	)

staticinherited

{
    auto polygons_src = reserve_vector<const Polygon*>(boundary_src.size());
    for (const Polygon &polygon : boundary_src)
        polygons_src.emplace_back(&polygon);
 
    connect_base_support(std::move(infill_ordered), polygons_src, bbox, polylines_out, spacing, params);
}

◆ connect_base_support() [2/2]

void Slic3r::Fill::connect_base_support	(	Polylines &&	infill_ordered,
		const std::vector< const Polygon * > &	boundary_src,
		const BoundingBox &	bbox,
		Polylines &	polylines_out,
		const double	spacing,
		const FillParams &	params
	)

staticinherited

{
//    assert(! infill_ordered.empty());
    assert(params.anchor_length     >= 0.);
    assert(params.anchor_length_max >= 0.01f);
    assert(params.anchor_length_max >= params.anchor_length);
 
    BoundaryInfillGraph graph = create_boundary_infill_graph(infill_ordered, boundary_src, bbox, spacing);
 
#ifdef INFILL_DEBUG_OUTPUT
    static int iRun = 0;
    ++ iRun;
    export_partial_infill_to_svg(debug_out_path("connect_base_support-initial-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    const double        line_half_width = 0.5 * scale_(spacing);
    const double        line_spacing    = scale_(spacing) / params.density;
    const double        min_arch_length = 1.3 * line_spacing;
    const double        trim_length     = line_half_width * 0.3;
 
// After mark_boundary_segments_touching_infill() marks boundary segments overlapping trimmed infill lines,
// there are possibly some very short boundary segments unmarked, but overlapping the untrimmed infill lines fully.
// Mark those short boundary segments.
    mark_boundary_segments_overlapping_infill(graph, infill_ordered, scale_(spacing));
 
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-marked-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    // Detect loops with zero infill end points connected.
    // Extrude these loops as perimeters.
    {
        std::vector<size_t> num_boundary_contour_infill_points(graph.boundary.size(), 0);
        for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary)
            ++ num_boundary_contour_infill_points[cp.contour_idx];
        for (size_t i = 0; i < num_boundary_contour_infill_points.size(); ++ i)
            if (num_boundary_contour_infill_points[i] == 0 && graph.boundary_params[i].back() > trim_length + 0.5 * line_spacing) {
                // Emit a perimeter.
                Polyline pl(graph.boundary[i]);
                pl.points.emplace_back(pl.points.front());
                pl.clip_end(trim_length);
                if (pl.size() > 1)
                    polylines_out.emplace_back(std::move(pl));
            }
    }
 
    // Before processing the boundary arches, emit those arches, which were trimmed by the infill lines at both sides, but which
    // depart from the infill line at least once after touching the infill line.
    for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary) {
        if (cp.next_on_contour && cp.next_trimmed && cp.next_on_contour->prev_trimmed) {
            // The arch is leaving one infill line to end up at the same infill line or at the neighbouring one.
            // The arch is touching one of those infill lines at least once.
            // Trace those arches and emit their parts, which are not attached to the end points and they are not overlapping with the two infill lines mentioned.
            bool    first    = graph.first(cp);
            coord_t left     = graph.point(cp).x();
            coord_t right    = left;
            if (first) {
                left  += line_half_width;
                right += line_spacing - line_half_width;
            } else {
                left  -= line_spacing - line_half_width;
                right -= line_half_width;
            }
            double param_start    = cp.param + cp.contour_not_taken_length_next;
            double param_end      = cp.next_on_contour->param - cp.next_on_contour->contour_not_taken_length_prev;
            double contour_length = graph.boundary_params[cp.contour_idx].back();
            if (param_start >= contour_length)
                param_start -= contour_length;
            if (param_end < 0)
                param_end += contour_length;
            // Verify that the interval (param_overlap1, param_overlap2) is inside the interval (ip_low->param, ip_high->param).
            assert(cyclic_interval_inside_interval(cp.param, cp.next_on_contour->param, param_start, param_end, contour_length));
            emit_loops_in_band(left, right, graph.boundary[cp.contour_idx], graph.boundary_params[cp.contour_idx], param_start, param_end, 0.5 * line_spacing, polylines_out);
        }
    }
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-excess-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    base_support_extend_infill_lines(infill_ordered, graph, spacing, params);
    
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-extended-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    std::vector<size_t> merged_with(infill_ordered.size());
    std::iota(merged_with.begin(), merged_with.end(), 0);
    auto get_and_update_merged_with = [&graph, &merged_with](const ContourIntersectionPoint *cp) -> size_t {
        size_t polyline_idx = (cp - graph.map_infill_end_point_to_boundary.data()) / 2;
        for (size_t last = polyline_idx;;) {
            size_t lower = merged_with[last];
            assert(lower <= last);
            if (lower == last) {
                merged_with[polyline_idx] = last;
                return last;
            }
            last = lower;
        }
        assert(false);
        return std::numeric_limits<size_t>::max();
    };
 
    auto vertical = [](BoundaryInfillGraph::Direction dir) {
        return dir == BoundaryInfillGraph::Up || dir == BoundaryInfillGraph::Down;
    };
    // When both left / right arch connected to cp is vertical (ends up at the same vertical infill line), which one to take?
    auto take_vertical_prev = [](const ContourIntersectionPoint &cp) {
        return cp.prev_trimmed == cp.next_trimmed ?
            // Both are either trimmed or not trimmed. Take the longer contour.
            cp.contour_not_taken_length_prev > cp.contour_not_taken_length_next :
            // One is trimmed, the other is not trimmed. Take the not trimmed.
            ! cp.prev_trimmed && cp.next_trimmed;
    };
 
    // Connect infill lines at cp and cpo_next_on_contour.
    // If the complete arch cannot be taken, then 
    // if (take_first)
    //    take the infill line at cp and an arc from cp towards cp.next_on_contour.
    // else
    //    take the infill line at cp_next_on_contour and an arc from cp.next_on_contour towards cp.
    // If cp1 == next_on_contour (a single infill line is connected to a contour, this is a valid case for contours with holes),
    // then extrude the full circle.
    // Nothing is done if the arch could no more be taken (one of it end points were consumed already).
    auto take_next = [&graph, &infill_ordered, &merged_with, get_and_update_merged_with, line_half_width, trim_length](ContourIntersectionPoint &cp, bool take_first) {
        // Indices of the polylines to be connected by a perimeter segment.
        ContourIntersectionPoint  *cp1            = &cp;
        ContourIntersectionPoint  *cp2            = cp.next_on_contour;
        assert(cp1->next_trimmed == cp2->prev_trimmed);
        //assert(cp1->next_trimmed || cp1->consumed == cp2->consumed);
        if (take_first ? cp1->consumed : cp2->consumed)
            return;
        size_t                     polyline_idx1  = get_and_update_merged_with(cp1);
        size_t                     polyline_idx2  = get_and_update_merged_with(cp2);
        Polyline                  &polyline1      = infill_ordered[polyline_idx1];
        Polyline                  &polyline2      = infill_ordered[polyline_idx2];
        const Points              &contour        = graph.boundary[cp1->contour_idx];
        const std::vector<double> &contour_params = graph.boundary_params[cp1->contour_idx];
        assert(cp1->consumed || contour[cp1->point_idx] == polyline1.points.front() || contour[cp1->point_idx] == polyline1.points.back());
        assert(cp2->consumed || contour[cp2->point_idx] == polyline2.points.front() || contour[cp2->point_idx] == polyline2.points.back());
        bool trimmed = take_first ? cp1->next_trimmed : cp2->prev_trimmed;
        if (! trimmed) {
            // Trim the end if closing a loop or making a T-joint.
            trimmed = cp1 == cp2 || polyline_idx1 == polyline_idx2 || (take_first ? cp2->consumed : cp1->consumed);
            if (! trimmed) {
                const bool                      cp1_first = ((cp1 - graph.map_infill_end_point_to_boundary.data()) & 1) == 0;
                const ContourIntersectionPoint* cp1_other = cp1_first ? cp1 + 1 : cp1 - 1;
                // Self loop, connecting the end points of the same infill line.
                trimmed = cp2 == cp1_other;
            }
            if (trimmed) /* [[unlikely]] */ {
                // Single end point on a contour. This may happen on contours with holes. Extrude a loop.
                // Or a self loop, connecting the end points of the same infill line.
                // Or closing a chain of infill lines. This may happen if infilling a contour with a hole.
                double len = cp1 == cp2 ? contour_params.back() : path_length_along_contour_ccw(cp1, cp2, contour_params.back());
                if (take_first) {
                    cp1->trim_next(std::max(0., len - trim_length - SCALED_EPSILON));
                    cp2->trim_prev(0);
                } else {
                    cp1->trim_next(0);
                    cp2->trim_prev(std::max(0., len - trim_length - SCALED_EPSILON));
                }
            }
        }
        if (trimmed) {
            if (take_first)
                take_limited(polyline1, contour, contour_params, cp1, cp2, false, 1e10, line_half_width);
            else
                take_limited(polyline2, contour, contour_params, cp2, cp1, true, 1e10, line_half_width);
        } else if (! cp1->consumed && ! cp2->consumed) {
            if (contour[cp1->point_idx] == polyline1.points.front())
                polyline1.reverse();
            if (contour[cp2->point_idx] == polyline2.points.back())
                polyline2.reverse();
            take(polyline1, polyline2, contour, cp1, cp2, false);
            // Mark the second polygon as merged with the first one.
            if (polyline_idx2 < polyline_idx1) {
                polyline2 = std::move(polyline1);
                polyline1.points.clear();
                merged_with[polyline_idx1] = merged_with[polyline_idx2];
            } else {
                polyline2.points.clear();
                merged_with[polyline_idx2] = merged_with[polyline_idx1];
            }
        }
    };
 
    // Consume all vertical arches. If a vertical arch is touching a neighboring vertical infill line, thus the vertical arch is trimmed,
    // only consume the trimmed part if it is longer than min_arch_length.
    for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary) {
        assert(cp.contour_idx != boundary_idx_unconnected);
        if (cp.consumed)
            continue;
        const ContourIntersectionPoint &cp_other = graph.other(cp);
        assert((cp.next_on_contour == &cp_other) == (cp_other.prev_on_contour == &cp));
        assert((cp.prev_on_contour == &cp_other) == (cp_other.next_on_contour == &cp));
        BoundaryInfillGraph::Direction dir_prev = graph.dir_prev(cp);
        BoundaryInfillGraph::Direction dir_next = graph.dir_next(cp);
        // Following code will also consume contours with just a single infill line attached. (cp1->next_on_contour == cp1).
        assert((cp.next_on_contour == &cp) == (cp.prev_on_contour == &cp));
        bool can_take_prev = vertical(dir_prev) && ! cp.prev_on_contour->consumed && cp.prev_on_contour != &cp_other;
        bool can_take_next = vertical(dir_next) && ! cp.next_on_contour->consumed && cp.next_on_contour != &cp_other;
        if (can_take_prev && (! can_take_next || take_vertical_prev(cp))) {
            if (! cp.prev_trimmed || cp.contour_not_taken_length_prev > min_arch_length)
                // take previous
                take_next(*cp.prev_on_contour, false);
        } else if (can_take_next) {
            if (! cp.next_trimmed || cp.contour_not_taken_length_next > min_arch_length)
                // take next
                take_next(cp, true);
        }
    }
 
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-vertical-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    const std::vector<SupportArcCost> arches = evaluate_support_arches(infill_ordered, graph, spacing, params);
    static const double cost_low      = line_spacing * 1.3;
    static const double cost_high     = line_spacing * 2.;
    static const double cost_veryhigh = line_spacing * 3.;
 
    {
        std::vector<const SupportArcCost*> selected;
        selected.reserve(graph.map_infill_end_point_to_boundary.size());
        for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary) {
            if (cp.consumed)
                continue;
            const SupportArcCost &cost_prev = arches[(&cp - graph.map_infill_end_point_to_boundary.data()) * 2];
            const SupportArcCost &cost_next = *(&cost_prev + 1);
            double                cost_min = cost_prev.cost;
            double                cost_max = cost_next.cost;
            if (cost_min > cost_max)
                std::swap(cost_min, cost_max);
            if (cost_max < cost_low || cost_min > cost_high)
                // Don't take any of the prev / next arches now, take zig-zag instead. It does not matter which one will be taken.
                continue;
            const double           cost_diff_relative = (cost_max - cost_min) / cost_max;
            if (cost_diff_relative < 0.25)
                // Don't take any of the prev / next arches now, take zig-zag instead. It does not matter which one will be taken.
                continue;
            if (cost_prev.cost > cost_low)
                selected.emplace_back(&cost_prev);
            if (cost_next.cost > cost_low)
                selected.emplace_back(&cost_next);
        }
        // Take the longest arch first.
        std::sort(selected.begin(), selected.end(), [](const auto *l, const auto *r) { return l->cost > r->cost; });
        // And connect along the arches.
        for (const SupportArcCost *arc : selected) {
            ContourIntersectionPoint &cp = graph.map_infill_end_point_to_boundary[(arc - arches.data()) / 2];
            if (! cp.consumed) {
                bool prev = ((arc - arches.data()) & 1) == 0;
                if (prev)
                    take_next(*cp.prev_on_contour, false);
                else
                    take_next(cp, true);
            }
        }
    }
 
#if 0
    {
        // Connect infill lines with long horizontal arches. Only take a horizontal arch, if it will not block
        // the end caps (vertical arches) at the other side of the infill line.
        struct Arc {
            ContourIntersectionPoint    *intersection;
            double                       arc_length;
            bool                         take_next;
        };
        std::vector<Arc> arches;
        arches.reserve(graph.map_infill_end_point_to_boundary.size());
        for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary) {
            if (cp.consumed)
                continue;
            // Not a losed loop, such loops should already be consumed.
            assert(cp.next_on_contour != &cp);
            const bool                      first     = ((&cp - graph.map_infill_end_point_to_boundary.data()) & 1) == 0;
            const ContourIntersectionPoint *other_end = first ? &cp + 1 : &cp - 1;
            const bool                      loop_next = cp.next_on_contour == other_end;
            if (! loop_next && cp.could_connect_next()) {
                if (cp.contour_not_taken_length_next > min_arch_length) {
                    // Try both directions. This is useful to be able to close a loop back to the same line to take a long arch.
                    arches.push_back({ &cp, cp.contour_not_taken_length_next, true });
                    arches.push_back({ cp.next_on_contour, cp.contour_not_taken_length_next, false });
                }
            } else {
                //bool    first     = ((&cp - graph.map_infill_end_point_to_boundary) & 1) == 0;
                if (cp.prev_trimmed && cp.could_take_prev()) {
                    //FIXME trace the trimmed line to decide what priority to assign to it.
                    // Is the end point close to the current vertical line or to the other vertical line?
                    const Point &pt   = graph.point(cp);
                    const Point &prev = graph.point(*cp.prev_on_contour);
                    if (std::abs(pt.x() - prev.x()) < coord_t(0.5 * line_spacing)) {
                        // End point on the same line.
                        // Measure maximum distance from the current vertical line.
                        if (cp.contour_not_taken_length_prev > 0.5 * line_spacing)
                            arches.push_back({ &cp, cp.contour_not_taken_length_prev, false });
                    } else {
                        // End point on the other line.
                        if (cp.contour_not_taken_length_prev > min_arch_length)
                            arches.push_back({ &cp, cp.contour_not_taken_length_prev, false });
                    }
                }
                if (cp.next_trimmed && cp.could_take_next()) {
                    //FIXME trace the trimmed line to decide what priority to assign to it.
                    const Point &pt   = graph.point(cp);
                    const Point &next = graph.point(*cp.next_on_contour);
                    if (std::abs(pt.x() - next.x()) < coord_t(0.5 * line_spacing)) {
                        // End point on the same line.
                        // Measure maximum distance from the current vertical line.
                        if (cp.contour_not_taken_length_next > 0.5 * line_spacing)
                            arches.push_back({ &cp, cp.contour_not_taken_length_next, true });
                    } else {
                        // End point on the other line.
                        if (cp.contour_not_taken_length_next > min_arch_length)
                            arches.push_back({ &cp, cp.contour_not_taken_length_next, true });
                    }
                }
            }
        }
        // Take the longest arch first.
        std::sort(arches.begin(), arches.end(), [](const auto &l, const auto &r) { return l.arc_length > r.arc_length; });
        // And connect along the arches.
        for (Arc &arc : arches)
            if (arc.take_next)
                take_next(*arc.intersection, true);
            else
                take_next(*arc.intersection->prev_on_contour, false);
    }
#endif
 
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-arches-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    // Traverse the unconnected lines in a zig-zag fashion, left to right only.
    for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary) {
        assert(cp.contour_idx != boundary_idx_unconnected);
        if (cp.consumed)
            continue;
        bool first = ((&cp - graph.map_infill_end_point_to_boundary.data()) & 1) == 0;
        if (first) {
            // Only connect if the two lines are not connected by the same line already.
            if (get_and_update_merged_with(&cp) != get_and_update_merged_with(cp.next_on_contour))
                take_next(cp, true);
        } else {
            if (get_and_update_merged_with(&cp) != get_and_update_merged_with(cp.prev_on_contour))
                take_next(*cp.prev_on_contour, false);
        }
    }
 
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-zigzag-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    // Add the left caps.
    for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary) {
        const bool                      first = ((&cp - graph.map_infill_end_point_to_boundary.data()) & 1) == 0;
        const ContourIntersectionPoint *other_end = first ? &cp + 1 : &cp - 1;
        const bool                      loop_next = cp.next_on_contour == other_end;
        const bool                      loop_prev = other_end->next_on_contour == &cp;
#ifndef NDEBUG
        const SupportArcCost           &cost_prev = arches[(&cp - graph.map_infill_end_point_to_boundary.data()) * 2];
        const SupportArcCost           &cost_next = *(&cost_prev + 1);
        assert(cost_prev.self_loop == loop_prev);
        assert(cost_next.self_loop == loop_next);
#endif // NDEBUG
        if (loop_prev && cp.could_take_prev())
            take_next(*cp.prev_on_contour, false);
        if (loop_next && cp.could_take_next())
            take_next(cp, true);
    }
 
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-caps-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    // Connect with T joints using long arches. Loops could be created only if a very long arc has to be added.
    {
        std::vector<const SupportArcCost*> candidates;
        for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary) {
            if (cp.could_take_prev())
                candidates.emplace_back(&arches[(&cp - graph.map_infill_end_point_to_boundary.data()) * 2]);
            if (cp.could_take_next())
                candidates.emplace_back(&arches[(&cp - graph.map_infill_end_point_to_boundary.data()) * 2 + 1]);
        }
        std::sort(candidates.begin(), candidates.end(), [](auto *c1, auto *c2) { return c1->cost > c2->cost; });
        for (const SupportArcCost *candidate : candidates) {
            ContourIntersectionPoint &cp   = graph.map_infill_end_point_to_boundary[(candidate - arches.data()) / 2];
            bool                      prev = ((candidate - arches.data()) & 1) == 0;
            if (prev) {
                if (cp.could_take_prev() && (get_and_update_merged_with(&cp) != get_and_update_merged_with(cp.prev_on_contour) || candidate->cost > cost_high))
                    take_next(*cp.prev_on_contour, false);
            } else {
                if (cp.could_take_next() && (get_and_update_merged_with(&cp) != get_and_update_merged_with(cp.next_on_contour) || candidate->cost > cost_high))
                    take_next(cp, true);
            }
        }
    }
 
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-Tjoints-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    // Add very long arches and reasonably long caps even if both of its end points were already consumed.
    const double cap_cost = 0.5 * line_spacing;
    for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary) {
        const SupportArcCost &cost_prev = arches[(&cp - graph.map_infill_end_point_to_boundary.data()) * 2];
        const SupportArcCost &cost_next = *(&cost_prev + 1);
        if (cp.contour_not_taken_length_prev > SCALED_EPSILON && 
            (cost_prev.self_loop ?
                cost_prev.cost > cap_cost :
                cost_prev.cost > cost_veryhigh)) {
            assert(cp.consumed && (cp.prev_on_contour->consumed || cp.prev_trimmed));
            Polyline pl { graph.point(cp) };
            if (! cp.prev_trimmed) {
                cp.trim_prev(cp.contour_not_taken_length_prev - line_half_width);
                cp.prev_on_contour->trim_next(0);
            }
            if (cp.contour_not_taken_length_prev > SCALED_EPSILON) {
                take_cw_limited(pl, graph.boundary[cp.contour_idx], graph.boundary_params[cp.contour_idx], cp.point_idx, cp.prev_on_contour->point_idx, cp.contour_not_taken_length_prev);
                cp.trim_prev(0);
                pl.clip_start(line_half_width);
                polylines_out.emplace_back(std::move(pl));
            }
        }
        if (cp.contour_not_taken_length_next > SCALED_EPSILON && 
            (cost_next.self_loop ?
                cost_next.cost > cap_cost :
                cost_next.cost > cost_veryhigh)) {
            assert(cp.consumed && (cp.next_on_contour->consumed || cp.next_trimmed));
            Polyline pl { graph.point(cp) };
            if (! cp.next_trimmed) {
                cp.trim_next(cp.contour_not_taken_length_next - line_half_width);
                cp.next_on_contour->trim_prev(0);
            }
            if (cp.contour_not_taken_length_next > SCALED_EPSILON) {
                take_ccw_limited(pl, graph.boundary[cp.contour_idx], graph.boundary_params[cp.contour_idx], cp.point_idx, cp.next_on_contour->point_idx, cp.contour_not_taken_length_next); // line_half_width);
                cp.trim_next(0);
                pl.clip_start(line_half_width);
                polylines_out.emplace_back(std::move(pl));
            }
        }
    }
 
#ifdef INFILL_DEBUG_OUTPUT
    export_partial_infill_to_svg(debug_out_path("connect_base_support-final-%03d.svg", iRun), graph, infill_ordered, polylines_out);
#endif // INFILL_DEBUG_OUTPUT
 
    polylines_out.reserve(polylines_out.size() + std::count_if(infill_ordered.begin(), infill_ordered.end(), [](const Polyline &pl) { return ! pl.empty(); }));
    for (Polyline &pl : infill_ordered)
        if (! pl.empty())
            polylines_out.emplace_back(std::move(pl));
}

Referenced by Slic3r::FillSupportBase::fill_surface().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ connect_infill() [1/3]

void Slic3r::Fill::connect_infill	(	Polylines &&	infill_ordered,
		const ExPolygon &	boundary,
		Polylines &	polylines_out,
		const double	spacing,
		const FillParams &	params
	)

staticinherited

{
  assert(! boundary_src.contour.points.empty());
    auto polygons_src = reserve_vector<const Polygon*>(boundary_src.holes.size() + 1);
    polygons_src.emplace_back(&boundary_src.contour);
    for (const Polygon &polygon : boundary_src.holes)
        polygons_src.emplace_back(&polygon);
 
    connect_infill(std::move(infill_ordered), polygons_src, get_extents(boundary_src.contour), polylines_out, spacing, params);
}

References Slic3r::Fill::connect_infill(), Slic3r::ExPolygon::contour, Slic3r::get_extents(), Slic3r::ExPolygon::holes, Slic3r::MultiPoint::points, and Slic3r::Fill::spacing.

Referenced by Slic3r::Fill3DHoneycomb::_fill_surface_single(), Slic3r::FillGyroid::_fill_surface_single(), Slic3r::FillHoneycomb::_fill_surface_single(), Slic3r::FillLightning::Filler::_fill_surface_single(), Slic3r::FillPlanePath::_fill_surface_single(), Slic3r::Fill::connect_infill(), Slic3r::Fill::connect_infill(), and Slic3r::FillRectilinear::fill_surface_by_multilines().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ connect_infill() [2/3]

void Slic3r::Fill::connect_infill	(	Polylines &&	infill_ordered,
		const Polygons &	boundary,
		const BoundingBox &	bbox,
		Polylines &	polylines_out,
		const double	spacing,
		const FillParams &	params
	)

staticinherited

{
    auto polygons_src = reserve_vector<const Polygon*>(boundary_src.size());
    for (const Polygon &polygon : boundary_src)
        polygons_src.emplace_back(&polygon);
 
    connect_infill(std::move(infill_ordered), polygons_src, bbox, polylines_out, spacing, params);
}

References Slic3r::Fill::connect_infill(), and Slic3r::Fill::spacing.

Here is the call graph for this function:

◆ connect_infill() [3/3]

void Slic3r::Fill::connect_infill	(	Polylines &&	infill_ordered,
		const std::vector< const Polygon * > &	boundary,
		const BoundingBox &	bbox,
		Polylines &	polylines_out,
		double	spacing,
		const FillParams &	params
	)

staticinherited

{
  assert(! infill_ordered.empty());
    assert(params.anchor_length     >= 0.);
    assert(params.anchor_length_max >= 0.01f);
    assert(params.anchor_length_max >= params.anchor_length);
    const double anchor_length     = scale_(params.anchor_length);
    const double anchor_length_max = scale_(params.anchor_length_max);
 
#if 0
    append(polylines_out, infill_ordered);
    return;
#endif
 
    BoundaryInfillGraph graph = create_boundary_infill_graph(infill_ordered, boundary_src, bbox, spacing);
 
    std::vector<size_t> merged_with(infill_ordered.size());
    std::iota(merged_with.begin(), merged_with.end(), 0);
 
    auto get_and_update_merged_with = [&merged_with](size_t polyline_idx) -> size_t {
        for (size_t last = polyline_idx;;) {
            size_t lower = merged_with[last];
            assert(lower <= last);
            if (lower == last) {
                merged_with[polyline_idx] = last;
                return last;
            }
            last = lower;
        }
        assert(false);
        return std::numeric_limits<size_t>::max();
    };
 
    const double line_half_width = 0.5 * scale_(spacing);
 
#if 0
    // Connection from end of one infill line to the start of another infill line.
    //const double length_max = scale_(spacing);
//  const auto length_max = double(scale_((2. / params.density) * spacing));
    const auto length_max = double(scale_((1000. / params.density) * spacing));
    struct ConnectionCost {
        ConnectionCost(size_t idx_first, double cost, bool reversed) : idx_first(idx_first), cost(cost), reversed(reversed) {}
        size_t  idx_first;
        double  cost;
        bool    reversed;
    };
    std::vector<ConnectionCost> connections_sorted;
    connections_sorted.reserve(infill_ordered.size() * 2 - 2);
    for (size_t idx_chain = 1; idx_chain < infill_ordered.size(); ++ idx_chain) {
        const ContourIntersectionPoint      *cp1            = &graph.map_infill_end_point_to_boundary[(idx_chain - 1) * 2 + 1];
        const ContourIntersectionPoint      *cp2            = &graph.map_infill_end_point_to_boundary[idx_chain * 2];
        if (cp1->contour_idx != boundary_idx_unconnected && cp1->contour_idx == cp2->contour_idx) {
            // End points on the same contour. Try to connect them.
            std::pair<double, double> len = path_lengths_along_contour(cp1, cp2, graph.boundary_params[cp1->contour_idx].back());
            if (len.first < length_max)
                connections_sorted.emplace_back(idx_chain - 1, len.first, false);
            if (len.second < length_max)
                connections_sorted.emplace_back(idx_chain - 1, len.second, true);
        }
    }
    std::sort(connections_sorted.begin(), connections_sorted.end(), [](const ConnectionCost& l, const ConnectionCost& r) { return l.cost < r.cost; });
 
    for (ConnectionCost &connection_cost : connections_sorted) {
    ContourIntersectionPoint *cp1    = &graph.map_infill_end_point_to_boundary[connection_cost.idx_first * 2 + 1];
    ContourIntersectionPoint *cp2    = &graph.map_infill_end_point_to_boundary[(connection_cost.idx_first + 1) * 2];
        assert(cp1 != cp2);
        assert(cp1->contour_idx == cp2->contour_idx && cp1->contour_idx != boundary_idx_unconnected);
        if (cp1->consumed || cp2->consumed)
            continue;
        const double              length = connection_cost.cost;
        bool                      could_connect;
        {
            // cp1, cp2 sorted CCW.
            ContourIntersectionPoint *cp_low  = connection_cost.reversed ? cp2 : cp1;
            ContourIntersectionPoint *cp_high = connection_cost.reversed ? cp1 : cp2;
            assert(std::abs(length - closed_contour_distance_ccw(cp_low->param, cp_high->param, graph.boundary_params[cp1->contour_idx].back())) < SCALED_EPSILON);
            could_connect = ! cp_low->next_trimmed && ! cp_high->prev_trimmed;
            if (could_connect && cp_low->next_on_contour != cp_high) {
                // Other end of cp1, may or may not be on the same contour as cp1.
                const ContourIntersectionPoint *cp1prev = cp1 - 1;
                // Other end of cp2, may or may not be on the same contour as cp2.
                const ContourIntersectionPoint *cp2next = cp2 + 1;
                for (auto *cp = cp_low->next_on_contour; cp != cp_high; cp = cp->next_on_contour)
                    if (cp->consumed || cp == cp1prev || cp == cp2next || cp->prev_trimmed || cp->next_trimmed) {
                        could_connect = false;
                        break;
                    }
            }
        }
        // Indices of the polylines to be connected by a perimeter segment.
        size_t idx_first  = connection_cost.idx_first;
        size_t idx_second = idx_first + 1;
        idx_first = get_and_update_merged_with(idx_first);
        assert(idx_first < idx_second);
        assert(idx_second == merged_with[idx_second]);
        if (could_connect && length < anchor_length_max) {
            // Take the complete contour.
            // Connect the two polygons using the boundary contour.
            take(infill_ordered[idx_first], infill_ordered[idx_second], graph.boundary[cp1->contour_idx], cp1, cp2, connection_cost.reversed);
            // Mark the second polygon as merged with the first one.
            merged_with[idx_second] = merged_with[idx_first];
            infill_ordered[idx_second].points.clear();
        } else {
            // Try to connect cp1 resp. cp2 with a piece of perimeter line.
            take_limited(infill_ordered[idx_first],  graph.boundary[cp1->contour_idx], graph.boundary_params[cp1->contour_idx], cp1, cp2, connection_cost.reversed, anchor_length, line_half_width);
            take_limited(infill_ordered[idx_second], graph.boundary[cp1->contour_idx], graph.boundary_params[cp1->contour_idx], cp2, cp1, ! connection_cost.reversed, anchor_length, line_half_width);
        }
  }
#endif
 
    struct Arc {
        ContourIntersectionPoint    *intersection;
        double                       arc_length;
    };
    std::vector<Arc> arches;
    arches.reserve(graph.map_infill_end_point_to_boundary.size());
    for (ContourIntersectionPoint &cp : graph.map_infill_end_point_to_boundary)
        if (cp.contour_idx != boundary_idx_unconnected && cp.next_on_contour != &cp && cp.could_connect_next())
            arches.push_back({ &cp, path_length_along_contour_ccw(&cp, cp.next_on_contour, graph.boundary_params[cp.contour_idx].back()) });
    std::sort(arches.begin(), arches.end(), [](const auto &l, const auto &r) { return l.arc_length < r.arc_length; });
 
    //FIXME improve the Traveling Salesman problem with 2-opt and 3-opt local optimization.
    for (Arc &arc : arches)
        if (! arc.intersection->consumed && ! arc.intersection->next_on_contour->consumed) {
            // Indices of the polylines to be connected by a perimeter segment.
            ContourIntersectionPoint *cp1            = arc.intersection;
            ContourIntersectionPoint *cp2            = arc.intersection->next_on_contour;
            size_t                    polyline_idx1  = get_and_update_merged_with(((cp1 - graph.map_infill_end_point_to_boundary.data()) / 2));
            size_t                    polyline_idx2  = get_and_update_merged_with(((cp2 - graph.map_infill_end_point_to_boundary.data()) / 2));
            const Points             &contour        = graph.boundary[cp1->contour_idx];
            const std::vector<double> &contour_params = graph.boundary_params[cp1->contour_idx];
            if (polyline_idx1 != polyline_idx2) {
                Polyline &polyline1 = infill_ordered[polyline_idx1];
                Polyline &polyline2 = infill_ordered[polyline_idx2];
                if (arc.arc_length < anchor_length_max) {
                    // Not closing a loop, connecting the lines.
                    assert(contour[cp1->point_idx] == polyline1.points.front() || contour[cp1->point_idx] == polyline1.points.back());
                    if (contour[cp1->point_idx] == polyline1.points.front())
                        polyline1.reverse();
                    assert(contour[cp2->point_idx] == polyline2.points.front() || contour[cp2->point_idx] == polyline2.points.back());
                    if (contour[cp2->point_idx] == polyline2.points.back())
                        polyline2.reverse();
                    take(polyline1, polyline2, contour, cp1, cp2, false);
                    // Mark the second polygon as merged with the first one.
                    if (polyline_idx2 < polyline_idx1) {
                        polyline2 = std::move(polyline1);
                        polyline1.points.clear();
                        merged_with[polyline_idx1] = merged_with[polyline_idx2];
                    } else {
                        polyline2.points.clear();
                        merged_with[polyline_idx2] = merged_with[polyline_idx1];
                    }
                } else if (anchor_length > SCALED_EPSILON) {
                    // Move along the perimeter, but don't take the whole arc.
                    take_limited(polyline1, contour, contour_params, cp1, cp2, false, anchor_length, line_half_width);
                    take_limited(polyline2, contour, contour_params, cp2, cp1, true,  anchor_length, line_half_width);
                }
            }
        }
 
    // Connect the remaining open infill lines to the perimeter lines if possible.
    for (ContourIntersectionPoint &contour_point : graph.map_infill_end_point_to_boundary)
        if (! contour_point.consumed && contour_point.contour_idx != boundary_idx_unconnected) {
            const Points              &contour        = graph.boundary[contour_point.contour_idx];
            const std::vector<double> &contour_params = graph.boundary_params[contour_point.contour_idx];
 
            double    lprev         = contour_point.could_connect_prev() ?
                path_length_along_contour_ccw(contour_point.prev_on_contour, &contour_point, contour_params.back()) :
                std::numeric_limits<double>::max();
            double    lnext         = contour_point.could_connect_next() ?
                path_length_along_contour_ccw(&contour_point, contour_point.next_on_contour, contour_params.back()) :
                std::numeric_limits<double>::max();
            size_t    polyline_idx  = get_and_update_merged_with(((&contour_point - graph.map_infill_end_point_to_boundary.data()) / 2));
            Polyline &polyline      = infill_ordered[polyline_idx];
            assert(! polyline.empty());
            assert(contour[contour_point.point_idx] == polyline.points.front() || contour[contour_point.point_idx] == polyline.points.back());
            bool connected = false;
            for (double l : { std::min(lprev, lnext), std::max(lprev, lnext) }) {
                if (l == std::numeric_limits<double>::max() || l > anchor_length_max)
                    break;
                // Take the complete contour.
                bool      reversed      = l == lprev;
                ContourIntersectionPoint *cp2 = reversed ? contour_point.prev_on_contour : contour_point.next_on_contour;
                // Identify which end of the polyline touches the boundary.
                size_t    polyline_idx2 = get_and_update_merged_with(((cp2 - graph.map_infill_end_point_to_boundary.data()) / 2));
                if (polyline_idx == polyline_idx2)
                    // Try the other side.
                    continue;
                // Not closing a loop.
                if (contour[contour_point.point_idx] == polyline.points.front())
                    polyline.reverse();
                Polyline &polyline2 = infill_ordered[polyline_idx2];
                assert(! polyline.empty());
                assert(contour[cp2->point_idx] == polyline2.points.front() || contour[cp2->point_idx] == polyline2.points.back());
                if (contour[cp2->point_idx] == polyline2.points.back())
                    polyline2.reverse();
                take(polyline, polyline2, contour, &contour_point, cp2, reversed);
                if (polyline_idx < polyline_idx2) {
                    // Mark the second polyline as merged with the first one.
                    merged_with[polyline_idx2] = polyline_idx;
                    polyline2.points.clear();
                } else {
                    // Mark the first polyline as merged with the second one.
                    merged_with[polyline_idx] = polyline_idx2;
                    polyline2 = std::move(polyline);
                    polyline.points.clear();
                }
                connected = true;
                break;
            }
            if (! connected && anchor_length > SCALED_EPSILON) {
                // Which to take? One could optimize for:
                // 1) Shortest path
                // 2) Hook length
                // ...
                // Let's take the longer now, as this improves the chance of another hook to be placed on the other side of this contour point.
                double l = std::max(contour_point.contour_not_taken_length_prev, contour_point.contour_not_taken_length_next);
                if (l > SCALED_EPSILON) {
                    if (contour_point.contour_not_taken_length_prev > contour_point.contour_not_taken_length_next)
                        take_limited(polyline, contour, contour_params, &contour_point, contour_point.prev_on_contour, true, anchor_length, line_half_width);
                    else
                        take_limited(polyline, contour, contour_params, &contour_point, contour_point.next_on_contour, false, anchor_length, line_half_width);
                }
            }
        }
 
    polylines_out.reserve(polylines_out.size() + std::count_if(infill_ordered.begin(), infill_ordered.end(), [](const Polyline &pl) { return ! pl.empty(); }));
  for (Polyline &pl : infill_ordered)
    if (! pl.empty())
      polylines_out.emplace_back(std::move(pl));
}

References Slic3r::FillParams::anchor_length, Slic3r::FillParams::anchor_length_max, Slic3r::append(), Slic3r::BoundaryInfillGraph::boundary, Slic3r::boundary_idx_unconnected, Slic3r::BoundaryInfillGraph::boundary_params, Slic3r::closed_contour_distance_ccw(), Slic3r::ContourIntersectionPoint::consumed, Slic3r::ContourIntersectionPoint::contour_idx, Slic3r::create_boundary_infill_graph(), Slic3r::FillParams::density, Slic3r::intersection(), Slic3r::length(), Slic3r::BoundaryInfillGraph::map_infill_end_point_to_boundary, Slic3r::ContourIntersectionPoint::next_on_contour, Slic3r::ContourIntersectionPoint::next_trimmed, Slic3r::ContourIntersectionPoint::param, Slic3r::path_length_along_contour_ccw(), Slic3r::path_lengths_along_contour(), Slic3r::ContourIntersectionPoint::prev_trimmed, scale_, SCALED_EPSILON, Slic3r::Fill::spacing, Slic3r::take(), and Slic3r::take_limited().

Here is the call graph for this function:

◆ fill_surface()

Polylines Slic3r::Fill::fill_surface	(	const Surface *	surface,
		const FillParams &	params
	)

virtualinherited

Reimplemented in Slic3r::FillEnsuring, Slic3r::FillRectilinear, Slic3r::FillMonotonic, Slic3r::FillMonotonicLines, Slic3r::FillGrid, Slic3r::FillTriangles, Slic3r::FillStars, Slic3r::FillCubic, and Slic3r::FillSupportBase.

{
    // Perform offset.
    Slic3r::ExPolygons expp = offset_ex(surface->expolygon, float(scale_(this->overlap - 0.5 * this->spacing)));
    // Create the infills for each of the regions.
    Polylines polylines_out;
    for (ExPolygon &expoly : expp)
        _fill_surface_single(params, surface->thickness_layers, _infill_direction(surface), std::move(expoly), polylines_out);
    return polylines_out;
}

References Slic3r::Fill::_fill_surface_single(), Slic3r::Fill::_infill_direction(), Slic3r::Surface::expolygon, Slic3r::offset_ex(), Slic3r::Fill::overlap, scale_, Slic3r::Fill::spacing, and Slic3r::Surface::thickness_layers.

Referenced by Slic3r::FFFSupport::fill_expolygon_generate_paths().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fill_surface_arachne()

ThickPolylines Slic3r::Fill::fill_surface_arachne	(	const Surface *	surface,
		const FillParams &	params
	)

virtualinherited

Reimplemented in Slic3r::FillEnsuring.

{
    // Perform offset.
    Slic3r::ExPolygons expp = offset_ex(surface->expolygon, float(scale_(this->overlap - 0.5 * this->spacing)));
    // Create the infills for each of the regions.
    ThickPolylines thick_polylines_out;
    for (ExPolygon &expoly : expp)
        _fill_surface_single(params, surface->thickness_layers, _infill_direction(surface), std::move(expoly), thick_polylines_out);
    return thick_polylines_out;
}

References Slic3r::Fill::_fill_surface_single(), Slic3r::Fill::_infill_direction(), Slic3r::Surface::expolygon, Slic3r::offset_ex(), Slic3r::Fill::overlap, scale_, Slic3r::Fill::spacing, and Slic3r::Surface::thickness_layers.

Here is the call graph for this function:

◆ new_from_type() [1/2]

Fill * Slic3r::Fill::new_from_type ( const InfillPattern type )

staticinherited

{
    switch (type) {
    case ipConcentric:          return new FillConcentric();
    case ipHoneycomb:           return new FillHoneycomb();
    case ip3DHoneycomb:         return new Fill3DHoneycomb();
    case ipGyroid:              return new FillGyroid();
    case ipRectilinear:         return new FillRectilinear();
    case ipAlignedRectilinear:  return new FillAlignedRectilinear();
    case ipMonotonic:           return new FillMonotonic();
    case ipMonotonicLines:      return new FillMonotonicLines();
    case ipLine:                return new FillLine();
    case ipGrid:                return new FillGrid();
    case ipTriangles:           return new FillTriangles();
    case ipStars:               return new FillStars();
    case ipCubic:               return new FillCubic();
    case ipArchimedeanChords:   return new FillArchimedeanChords();
    case ipHilbertCurve:        return new FillHilbertCurve();
    case ipOctagramSpiral:      return new FillOctagramSpiral();
    case ipAdaptiveCubic:       return new FillAdaptive::Filler();
    case ipSupportCubic:        return new FillAdaptive::Filler();
    case ipSupportBase:         return new FillSupportBase();
    case ipLightning:           return new FillLightning::Filler();
    case ipEnsuring:            return new FillEnsuring();
    default: throw Slic3r::InvalidArgument("unknown type");
    }
}

References Slic3r::ip3DHoneycomb, Slic3r::ipAdaptiveCubic, Slic3r::ipAlignedRectilinear, Slic3r::ipArchimedeanChords, Slic3r::ipConcentric, Slic3r::ipCubic, Slic3r::ipEnsuring, Slic3r::ipGrid, Slic3r::ipGyroid, Slic3r::ipHilbertCurve, Slic3r::ipHoneycomb, Slic3r::ipLightning, Slic3r::ipLine, Slic3r::ipMonotonic, Slic3r::ipMonotonicLines, Slic3r::ipOctagramSpiral, Slic3r::ipRectilinear, Slic3r::ipStars, Slic3r::ipSupportBase, Slic3r::ipSupportCubic, and Slic3r::ipTriangles.

Referenced by Slic3r::WipeTower::finish_layer(), Slic3r::FFFTreeSupport::generate_support_infill_lines(), Slic3r::Fill::new_from_type(), and Slic3r::Fill::use_bridge_flow().

Here is the caller graph for this function:

◆ new_from_type() [2/2]

Fill * Slic3r::Fill::new_from_type ( const std::string & type )

staticinherited

{
    const t_config_enum_values &enum_keys_map = ConfigOptionEnum<InfillPattern>::get_enum_values();
    t_config_enum_values::const_iterator it = enum_keys_map.find(type);
    return (it == enum_keys_map.end()) ? nullptr : new_from_type(InfillPattern(it->second));
}

References Slic3r::ConfigOptionEnum< T >::get_enum_values(), and Slic3r::Fill::new_from_type().

Here is the call graph for this function:

◆ no_sort()

virtual bool Slic3r::Fill::no_sort ( ) const

inlinevirtualinherited

Reimplemented in Slic3r::FillAdaptive::Filler, Slic3r::FillConcentric, Slic3r::FillEnsuring, Slic3r::FillLightning::Filler, Slic3r::FillMonotonic, and Slic3r::FillMonotonicLines.

112{ return false; }

◆ set_bounding_box()

void Slic3r::Fill::set_bounding_box ( const Slic3r::BoundingBox & bbox )

inlineinherited

106{ bounding_box = bbox; }

References Slic3r::Fill::bounding_box.

Referenced by Slic3r::Layer::make_ironing().

Here is the caller graph for this function:

◆ use_bridge_flow() [1/2]

virtual bool Slic3r::Fill::use_bridge_flow ( ) const

inlinevirtualinherited

Reimplemented in Slic3r::Fill3DHoneycomb, and Slic3r::FillGyroid.

109{ return false; }

Referenced by Slic3r::group_fills().

Here is the caller graph for this function:

◆ use_bridge_flow() [2/2]

bool Slic3r::Fill::use_bridge_flow ( const InfillPattern type )

staticinherited

{
  static std::vector<unsigned char> cached;
  if (cached.empty()) {
    cached.assign(size_t(ipCount), 0);
    for (size_t i = 0; i < cached.size(); ++ i) {
      auto *fill = Fill::new_from_type((InfillPattern)i);
      cached[i] = fill->use_bridge_flow();
      delete fill;
    }
  }
  return cached[type] != 0;
}