Slic3r::FillMonotonicLine Class Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Fill/FillRectilinear.hpp>

Inheritance diagram for Slic3r::FillMonotonicLine:

Collaboration diagram for Slic3r::FillMonotonicLine:

Public Member Functions
Fill *	clone () const override
	~FillMonotonicLine () override=default
Polylines	fill_surface (const Surface *surface, const FillParams &params) override
bool	no_sort () const override
bool	is_self_crossing () override
virtual bool	use_bridge_flow () const
void	set_bounding_box (const Slic3r::BoundingBox &bbox)
BoundingBox	extended_object_bounding_box () const
virtual bool	has_consistent_pattern () const
virtual bool	aligned_to_origin () const
virtual ThickPolylines	fill_surface_arachne (const Surface *surface, const FillParams &params)
virtual void	set_lock_region_param (const LockRegionParam &lock_param)
virtual void	fill_surface_extrusion (const Surface *surface, const FillParams &params, ExtrusionEntitiesPtr &out)

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	chain_or_connect_infill (Polylines &&infill_ordered, const ExPolygon &boundary, Polylines &polylines_out, const 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
bool	fixed_angle {false}
coord_t	link_max_length
coord_t	loop_clipping
BoundingBox	bounding_box
FillAdaptive::Octree *	adapt_fill_octree = nullptr
const AdaptiveInfillField *	adaptive_infill_field = nullptr
const PrintConfig *	print_config = nullptr
const PrintObjectConfig *	print_object_config = nullptr
ExPolygons	no_overlap_expolygons
bool	dont_alternate_fill_direction = false

Static Public Attributes
static float	infill_anchor = 400
static float	infill_anchor_max = 20

Protected Member Functions
bool	fill_surface_by_lines (const Surface *surface, const FillParams &params, float angleBase, float pattern_shift, Polylines &polylines_out)
bool	fill_surface_by_multilines (const Surface *surface, FillParams params, const std::initializer_list< SweepParams > &sweep_params, Polylines &polylines_out)
bool	fill_surface_trapezoidal (const Surface *surface, FillParams params, Polylines &polylines_out, int Pattern_type)
virtual void	_fill_surface_single (const FillParams &, unsigned int, const std::pair< float, Point > &, ExPolygon, Polylines &)
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
virtual std::pair< float, Point >	_infill_direction (const Surface *surface) const
void	_create_gap_fill (const Surface *surface, const FillParams &params, ExtrusionEntityCollection *out)

Detailed Description

Constructor & Destructor Documentation

~FillMonotonicLine()

Slic3r::FillMonotonicLine::~FillMonotonicLine ( )

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.

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

Here is the caller graph for this function:

_create_gap_fill()

void Slic3r::Fill::_create_gap_fill ( const Surface * surface, const FillParams & params, ExtrusionEntityCollection * out )

protectedinherited

                                                                                                           {
 
    //Orca: just to be safe, check against null pointer for the print object config and if NULL return.
    if (this->print_object_config == nullptr) return;
 
    // Orca: Enable gap fill as per the user preference. Return early if gap fill is to not be applied.
    if ((this->print_object_config->gap_fill_target.value == gftNowhere) ||
        (surface->surface_type == stInternalSolid && this->print_object_config->gap_fill_target.value != gftEverywhere))
        return;
 
    Flow new_flow = params.flow;
    ExPolygons unextruded_areas;
    unextruded_areas = diff_ex(this->no_overlap_expolygons, union_ex(out->polygons_covered_by_spacing(10)));
    ExPolygons gapfill_areas = union_ex(unextruded_areas);
    if (!this->no_overlap_expolygons.empty())
        gapfill_areas = intersection_ex(gapfill_areas, this->no_overlap_expolygons);
 
    if (gapfill_areas.size() > 0 && params.density >= 1) {
        double min = 0.2 * new_flow.scaled_spacing() * (1 - INSET_OVERLAP_TOLERANCE);
        double max = 2. * new_flow.scaled_spacing();
        ExPolygons gaps_ex = diff_ex(
                                     opening_ex(gapfill_areas, float(min / 2.)),
                                     offset2_ex(gapfill_areas, -float(max / 2.), float(max / 2. + ClipperSafetyOffset)));
        //BBS: sort the gap_ex to avoid mess travel
        Points ordering_points;
        ordering_points.reserve(gaps_ex.size());
        ExPolygons gaps_ex_sorted;
        gaps_ex_sorted.reserve(gaps_ex.size());
        for (const ExPolygon &ex : gaps_ex)
            ordering_points.push_back(ex.contour.first_point());
        std::vector<Points::size_type> order2 = chain_points(ordering_points);
        for (size_t i : order2)
            gaps_ex_sorted.emplace_back(std::move(gaps_ex[i]));
 
        ThickPolylines polylines;
        for (ExPolygon& ex : gaps_ex_sorted) {
            //BBS: Use DP simplify to avoid duplicated points and accelerate medial-axis calculation as well.
            ex.douglas_peucker(SCALED_RESOLUTION * 0.1);
            ex.medial_axis(min, max, &polylines);
        }
 
        if (!polylines.empty() && !is_bridge(params.extrusion_role)) {
            polylines.erase(std::remove_if(polylines.begin(), polylines.end(),
                                           [&](const ThickPolyline& p) {
                return p.length() < scale_(params.config->filter_out_gap_fill.value);
            }), polylines.end());
 
            if (out->no_sort)
                insert_gap_fill(polylines, params.flow, out->entities);
            else
                variable_width(polylines, erGapFill, params.flow, out->entities);
        }
    }
}

References Slic3r::chain_points(), Slic3r::ClipperSafetyOffset, Slic3r::FillParams::density, Slic3r::diff_ex(), Slic3r::ExtrusionEntityCollection::entities, Slic3r::erGapFill, Slic3r::FillParams::extrusion_role, Slic3r::FillParams::flow, Slic3r::gftEverywhere, Slic3r::gftNowhere, Slic3r::insert_gap_fill(), INSET_OVERLAP_TOLERANCE, Slic3r::intersection_ex(), Slic3r::is_bridge(), no_overlap_expolygons, Slic3r::ExtrusionEntityCollection::no_sort, Slic3r::offset2_ex(), Slic3r::opening_ex(), Slic3r::ExtrusionEntityCollection::polygons_covered_by_spacing(), print_object_config, SCALED_RESOLUTION, Slic3r::Flow::scaled_spacing(), Slic3r::stInternalSolid, Slic3r::Surface::surface_type, Slic3r::union_ex(), and Slic3r::variable_width().

Referenced by fill_surface_extrusion().

Here is the call graph for this function:

Here is the caller graph for this function:

_fill_surface_single() [1/2]

virtual void Slic3r::Fill::_fill_surface_single ( const FillParams & , unsigned int , const std::pair< float, Point > & , ExPolygon , Polylines &  )

inlineprotectedvirtualinherited

Reimplemented in Slic3r::Fill3DHoneycomb, Slic3r::FillAdaptive::Filler, Slic3r::FillConcentric, Slic3r::FillCrossHatch, Slic3r::FillGyroid, Slic3r::FillHoneycomb, Slic3r::FillLightning::Filler, Slic3r::FillLine, Slic3r::FillPlanePath, Slic3r::FillSpiralInset, Slic3r::FillTpmsD, and Slic3r::FillTpmsFK.

                                             {}

Referenced by fill_surface(), and fill_surface_arachne().

Here is the caller 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, and Slic3r::FillSpiralInset.

                                             {}

_infill_direction()

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

protectedvirtualinherited

{
    // set infill angle
    float out_angle = this->angle;
 
  if (out_angle == FLT_MAX) {
    //FIXME Vojtech: Add a warning?
        printf("Using undefined infill angle\n");
        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) && !fixed_angle) {
        // alternate fill direction
        //Orca: Do not alternate direction if Fill.fixed_angle is true
        if (!this->dont_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 _layer_angle(), angle, bounding_box, Slic3r::MultiPoint::bounding_box(), Slic3r::Surface::bridge_angle, Slic3r::BoundingBoxBase< PointType, APointsType >::center(), Slic3r::ExPolygon::contour, dont_alternate_fill_direction, Slic3r::empty(), Slic3r::Surface::expolygon, fixed_angle, layer_id, M_PI, and Slic3r::Surface::thickness_layers.

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

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::FillAlignedRectilinear, Slic3r::FillCubic, Slic3r::FillGrid, Slic3r::FillHoneycomb, Slic3r::FillLateralLattice, Slic3r::FillPlanePath, Slic3r::FillQuarterCubic, Slic3r::FillStars, Slic3r::FillSupportBase, and Slic3r::FillTriangles.

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

References fixed_angle, and M_PI.

Referenced by _infill_direction().

Here is the caller graph for this function:

aligned_to_origin()

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

inlinevirtualinherited

Reimplemented in Slic3r::Fill3DHoneycomb, Slic3r::FillCrossHatch, Slic3r::FillGyroid, Slic3r::FillHoneycomb, Slic3r::FillTpmsD, and Slic3r::FillTpmsFK.

{ return false; }

Referenced by fill_surface().

Here is the caller graph for this function:

chain_or_connect_infill()

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

staticinherited

{
    if (!infill_ordered.empty()) {
        if (params.dont_connect()) {
            if (infill_ordered.size() > 1)
                infill_ordered = chain_polylines(std::move(infill_ordered));
            append(polylines_out, std::move(infill_ordered));
        } else
            connect_infill(std::move(infill_ordered), boundary, polylines_out, spacing, params);
    }
}

References Slic3r::append(), Slic3r::chain_polylines(), connect_infill(), Slic3r::FillParams::dont_connect(), and spacing.

Referenced by Slic3r::Fill3DHoneycomb::_fill_surface_single(), Slic3r::FillCrossHatch::_fill_surface_single(), Slic3r::FillGyroid::_fill_surface_single(), Slic3r::FillHoneycomb::_fill_surface_single(), and Slic3r::FillLightning::Filler::_fill_surface_single().

Here is the call graph for this function:

Here is the caller graph for this function:

clone()

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

inlineoverridevirtual

Implements Slic3r::Fill.

{ return new FillMonotonicLine(*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);
}

References connect_base_support(), Slic3r::reserve_vector(), and spacing.

Here is the call graph for this function:

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);
    // Must not be static: line_spacing varies per call (base vs interface fills differ),
    // and a static here would fix these to whichever call ran first, order depending on thread count.
    const double cost_low      = line_spacing * 1.3;
    const double cost_high     = line_spacing * 2.;
    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));
}

References Slic3r::FillParams::anchor_length, Slic3r::FillParams::anchor_length_max, Slic3r::base_support_extend_infill_lines(), Slic3r::BoundaryInfillGraph::boundary, Slic3r::boundary_idx_unconnected, Slic3r::BoundaryInfillGraph::boundary_params, Slic3r::Polyline::clip_end(), Slic3r::Polyline::clip_start(), Slic3r::ContourIntersectionPoint::consumed, Slic3r::contour(), Slic3r::ContourIntersectionPoint::contour_idx, Slic3r::ContourIntersectionPoint::contour_not_taken_length_next, Slic3r::ContourIntersectionPoint::contour_not_taken_length_prev, Slic3r::SupportArcCost::cost, Slic3r::ContourIntersectionPoint::could_connect_next(), Slic3r::ContourIntersectionPoint::could_take_next(), Slic3r::ContourIntersectionPoint::could_take_prev(), Slic3r::create_boundary_infill_graph(), Slic3r::cyclic_interval_inside_interval(), Slic3r::debug_out_path(), Slic3r::FillParams::density, Slic3r::BoundaryInfillGraph::dir_next(), Slic3r::BoundaryInfillGraph::dir_prev(), Slic3r::BoundaryInfillGraph::Down, Slic3r::emit_loops_in_band(), Slic3r::MultiPoint::empty(), Slic3r::evaluate_support_arches(), Slic3r::BoundaryInfillGraph::first(), Slic3r::intersection(), Slic3r::BoundaryInfillGraph::map_infill_end_point_to_boundary, Slic3r::mark_boundary_segments_overlapping_infill(), Slic3r::ContourIntersectionPoint::next_on_contour, Slic3r::ContourIntersectionPoint::next_trimmed, Slic3r::BoundaryInfillGraph::other(), Slic3r::ContourIntersectionPoint::param, Slic3r::path_length_along_contour_ccw(), Slic3r::BoundaryInfillGraph::point(), Slic3r::ContourIntersectionPoint::point_idx, Slic3r::MultiPoint::points, Slic3r::ContourIntersectionPoint::prev_on_contour, Slic3r::ContourIntersectionPoint::prev_trimmed, Slic3r::Polyline::reverse(), scale_, SCALED_EPSILON, Slic3r::SupportArcCost::self_loop, Slic3r::MultiPoint::size(), spacing, Slic3r::take(), Slic3r::take_ccw_limited(), Slic3r::take_cw_limited(), Slic3r::take_limited(), Slic3r::ContourIntersectionPoint::trim_next(), Slic3r::ContourIntersectionPoint::trim_prev(), and Slic3r::BoundaryInfillGraph::Up.

Referenced by connect_base_support(), and 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 connect_infill(), Slic3r::ExPolygon::contour, Slic3r::get_extents(), Slic3r::ExPolygon::holes, Slic3r::MultiPoint::points, Slic3r::reserve_vector(), and spacing.

Referenced by Slic3r::FillPlanePath::_fill_surface_single(), Slic3r::FillTpmsD::_fill_surface_single(), Slic3r::FillTpmsFK::_fill_surface_single(), chain_or_connect_infill(), connect_infill(), connect_infill(), Slic3r::FillRectilinear::fill_surface_by_multilines(), and Slic3r::FillRectilinear::fill_surface_trapezoidal().

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 connect_infill(), Slic3r::reserve_vector(), and 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);
    // Two ends whose anchors would meet are joined instead, with about as much wall.
    const double join_length = anchor_length > SCALED_EPSILON ? std::max(anchor_length_max, 2. * (anchor_length + line_half_width)) : anchor_length_max;
 
#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
 
    // Line ends not yet joined to another line along the contour.
    std::vector<char> open_end(graph.map_infill_end_point_to_boundary.size(), 1);
    auto end_index = [&graph](const ContourIntersectionPoint *cp) { return size_t(cp - graph.map_infill_end_point_to_boundary.data()); };
 
    struct Arc {
        ContourIntersectionPoint    *intersection;
        double                       arc_length;
    };
    std::vector<Arc> arches;
    if (!params.dont_sort) {
        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; });
 
        // Lines the arcs would join in this order.
        auto count_joins = [&](const std::vector<Arc> &order) {
            std::vector<char> consumed(graph.map_infill_end_point_to_boundary.size());
            for (size_t i = 0; i < consumed.size(); ++ i)
                consumed[i] = graph.map_infill_end_point_to_boundary[i].consumed;
            std::vector<size_t> parent(infill_ordered.size());
            std::iota(parent.begin(), parent.end(), 0);
            auto find = [&parent](size_t i) {
                while (parent[i] != i)
                    i = parent[i] = parent[parent[i]];
                return i;
            };
            size_t joins = 0;
            for (const Arc &arc : order) {
                const size_t end1 = end_index(arc.intersection), end2 = end_index(arc.intersection->next_on_contour);
                if (consumed[end1] || consumed[end2] || (params.multiline > 1 && arc.arc_length < scale_(spacing) * params.multiline))
                    continue;
                const size_t polyline1 = find(end1 / 2), polyline2 = find(end2 / 2);
                if (polyline1 == polyline2)
                    continue;
                if (arc.arc_length < join_length) {
                    parent[polyline2] = polyline1;
                    ++ joins;
                } else if (anchor_length <= SCALED_EPSILON)
                    continue;
                consumed[end1] = consumed[end2] = 1;
            }
            // The last pass joins the open ends next to each other, also those of a multiline group.
            for (size_t end = 0; end < consumed.size(); ++ end) {
                const ContourIntersectionPoint &cp = graph.map_infill_end_point_to_boundary[end];
                if (consumed[end] || cp.contour_idx == boundary_idx_unconnected)
                    continue;
                const double length = graph.boundary_params[cp.contour_idx].back();
                auto open = [&](const ContourIntersectionPoint *other, bool trimmed) {
                    return other != &cp && ! consumed[end_index(other)] && ! trimmed;
                };
                const double lprev = open(cp.prev_on_contour, cp.prev_trimmed || cp.prev_on_contour->next_trimmed) ?
                    path_length_along_contour_ccw(cp.prev_on_contour, &cp, length) : std::numeric_limits<double>::max();
                const double lnext = open(cp.next_on_contour, cp.next_trimmed || cp.next_on_contour->prev_trimmed) ?
                    path_length_along_contour_ccw(&cp, cp.next_on_contour, length) : std::numeric_limits<double>::max();
                consumed[end] = anchor_length > SCALED_EPSILON;
                for (const double l : { std::min(lprev, lnext), std::max(lprev, lnext) }) {
                    if (l > join_length)
                        break;
                    const size_t other = end_index(l == lprev ? cp.prev_on_contour : cp.next_on_contour);
                    const size_t polyline1 = find(end / 2), polyline2 = find(other / 2);
                    if (polyline1 == polyline2)
                        continue;
                    parent[polyline2] = polyline1;
                    consumed[end] = consumed[other] = 1;
                    ++ joins;
                    break;
                }
            }
            return joins;
        };
        // Equal arcs taken along the contour pair a wall in one phase; keep the order that joins the most lines.
        size_t best_joins = count_joins(arches);
        const double bucket = 0.5 * scale_(spacing);
        for (const bool backwards : { false, true }) {
            std::vector<Arc> along_contour = arches;
            std::sort(along_contour.begin(), along_contour.end(), [bucket, backwards](const Arc &l, const Arc &r) {
                const long long bucket_l = std::llround(l.arc_length / bucket), bucket_r = std::llround(r.arc_length / bucket);
                if (bucket_l != bucket_r)
                    return bucket_l < bucket_r;
                if (l.intersection->contour_idx != r.intersection->contour_idx)
                    return l.intersection->contour_idx < r.intersection->contour_idx;
                return backwards ? l.intersection->param > r.intersection->param : l.intersection->param < r.intersection->param;
            });
            if (const size_t joins = count_joins(along_contour); joins > best_joins) {
                best_joins = joins;
                arches     = std::move(along_contour);
            }
        }
    }
 
    //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];
 
            // Orca: If multiline infill is requested, skip connections that are too short.
            if (params.multiline > 1 && arc.arc_length < scale_(spacing) * params.multiline) {
                continue;
            }
 
            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 < join_length) {
                    // 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);
                    open_end[end_index(cp1)] = open_end[end_index(cp2)] = 0;
                    // 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);
                }
            }
        }
 
    // Distance along the contour to the nearest open end of another polyline, within 64 ends.
    auto distance_to_open_end = [&](const ContourIntersectionPoint &from, size_t polyline_idx, bool backwards) {
        const double length   = graph.boundary_params[from.contour_idx].back();
        double       distance = 0.;
        const ContourIntersectionPoint *cp = &from;
        for (size_t step = 0; step < 64; ++ step) {
            const ContourIntersectionPoint *other = backwards ? cp->prev_on_contour : cp->next_on_contour;
            if (other == nullptr || other == &from)
                break;
            distance += backwards ? closed_contour_distance_cw(cp->param, other->param, length) : closed_contour_distance_ccw(cp->param, other->param, length);
            if (open_end[end_index(other)] && get_and_update_merged_with(end_index(other) / 2) != polyline_idx)
                return distance;
            cp = other;
        }
        return std::numeric_limits<double>::max();
    };
 
    // 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 > join_length)
                    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);
                open_end[end_index(&contour_point)] = open_end[end_index(cp2)] = 0;
                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) {
                // Hook toward the nearest open end of another polyline, where the next path likely starts.
                const double free_prev = contour_point.contour_not_taken_length_prev;
                const double free_next = contour_point.contour_not_taken_length_next;
                const double to_prev   = distance_to_open_end(contour_point, polyline_idx, true);
                const double to_next   = distance_to_open_end(contour_point, polyline_idx, false);
                bool backwards = free_prev > free_next;
                if (to_prev < to_next && free_prev > SCALED_EPSILON)
                    backwards = true;
                else if (to_next < to_prev && free_next > SCALED_EPSILON)
                    backwards = false;
                // Orca: with multiline, a hook toward a copy stops short of it; the copy takes half a width over the sine of its wall angle.
                double length = anchor_length;
                if (const ContourIntersectionPoint *other = backwards ? contour_point.prev_on_contour : contour_point.next_on_contour;
                    params.multiline > 1 && other != &contour_point) {
                    const Point &end = contour[contour_point.point_idx];
                    Vec2d        dir = Vec2d::Zero();
                    for (size_t i = 1; i < polyline.size() && dir.squaredNorm() < sqr(2. * scale_(spacing) * params.multiline); ++ i)
                        dir = (end - polyline.points[polyline.points.front() == end ? i : polyline.size() - 1 - i]).cast<double>();
                    const Vec2d  to_copy = (contour[other->point_idx] - end).cast<double>();
                    const double across  = dir.squaredNorm() > 0. ? std::abs(cross2(dir.normalized(), to_copy)) : 0.;
                    if (across > SCALED_EPSILON && across < scale_(spacing) * params.multiline) {
                        const double gap = backwards ? path_length_along_contour_ccw(other, &contour_point, contour_params.back()) :
                                                       path_length_along_contour_ccw(&contour_point, other, contour_params.back());
                        length = std::min(length, gap - line_half_width * (1. + to_copy.norm() / across));
                    }
                }
                if ((backwards ? free_prev : free_next) > SCALED_EPSILON)
                    take_limited(polyline, contour, contour_params, &contour_point, backwards ? contour_point.prev_on_contour : contour_point.next_on_contour,
                                 backwards, std::max(0., 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::cast(), Slic3r::closed_contour_distance_ccw(), Slic3r::closed_contour_distance_cw(), Slic3r::ContourIntersectionPoint::consumed, Slic3r::contour(), Slic3r::ContourIntersectionPoint::contour_idx, Slic3r::ContourIntersectionPoint::could_connect_next(), Slic3r::create_boundary_infill_graph(), Slic3r::cross2(), Slic3r::FillParams::density, Slic3r::FillParams::dont_sort, Slic3r::MultiPoint::empty(), Slic3r::intersection(), Slic3r::length(), Slic3r::BoundaryInfillGraph::map_infill_end_point_to_boundary, Slic3r::FillParams::multiline, 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::point_idx, Slic3r::MultiPoint::points, Slic3r::ContourIntersectionPoint::prev_on_contour, Slic3r::ContourIntersectionPoint::prev_trimmed, Slic3r::Polyline::reverse(), scale_, SCALED_EPSILON, Slic3r::MultiPoint::size(), spacing, Slic3r::sqr(), Slic3r::take(), and Slic3r::take_limited().

Here is the call graph for this function:

extended_object_bounding_box()

BoundingBox Slic3r::Fill::extended_object_bounding_box ( ) const

inherited

{
    // Orca: Extend about the box center, which separated infills move off the origin.
    const Point c   = this->bounding_box.center();
    BoundingBox out = this->bounding_box;
    out.translate(-c.x(), -c.y());
    out.merge(Point(out.min.y(), out.min.x()));
    out.merge(Point(out.max.y(), out.max.x()));
 
    // The bounding box is scaled by sqrt(2.) to ensure that the bounding box
    // covers any possible rotations.
    out = out.scaled(sqrt(2.));
    out.translate(c.x(), c.y());
    return out;
}

References bounding_box, Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::BoundingBoxBase< PointType, APointsType >::min, Slic3r::BoundingBox::scaled(), and Slic3r::BoundingBoxBase< PointType, APointsType >::translate().

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

Here is the call graph for this function:

Here is the caller graph for this function:

fill_surface()

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

overridevirtual

Reimplemented from Slic3r::Fill.

{
    FillParams params2 = params;
    params2.monotonic = true;
    params2.anchor_length_max = 0.0f;
    Polylines polylines_out;
    if (! fill_surface_by_lines(surface, params2, 0.f, 0.f, polylines_out))
        BOOST_LOG_TRIVIAL(error) << "Failed to fill a region by MonotonicLine pattern";
    return polylines_out;
}

References Slic3r::FillParams::anchor_length_max, Slic3r::FillRectilinear::fill_surface_by_lines(), and Slic3r::FillParams::monotonic.

Here is the call graph for this function:

fill_surface_arachne()

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

virtualinherited

{
    // 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 _fill_surface_single(), _infill_direction(), Slic3r::Surface::expolygon, Slic3r::offset_ex(), overlap, scale_, spacing, and Slic3r::Surface::thickness_layers.

Referenced by fill_surface_extrusion().

Here is the call graph for this function:

Here is the caller graph for this function:

fill_surface_by_lines()

bool Slic3r::FillRectilinear::fill_surface_by_lines ( const Surface * surface, const FillParams & params, float angleBase, float pattern_shift, Polylines & polylines_out )

protectedinherited

{
    // 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);
    if (params.locked_zag)
        rotate_vector.first += float(M_PI/2.);
    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, 
        float(scale_(this->overlap - (0.5 - INFILL_OVERLAP_OVER_SPACING) * this->spacing)),
        float(scale_(this->overlap - 0.5f * 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;
    }
 
    // For infill that needs to be consistent between layers (like Zig Zag),
    // we use bounding box of whole object to match vertical lines between layers.
    BoundingBox bounding_box_src = poly_with_offset.bounding_box_src();
    BoundingBox bounding_box     = bounding_box_src;
    if (this->has_consistent_pattern()) {
        // Orca: The polygons are rotated about the origin, so follow the box center to where it was rotated.
        const Point c = this->bounding_box.center();
        bounding_box  = this->extended_object_bounding_box();
        bounding_box.translate(c.rotated(- rotate_vector.first) - c);
    }
 
    // define flow spacing according to requested density
    if (params.full_infill() && !params.dont_adjust) {
        line_spacing = this->_adjust_solid_spacing(bounding_box_src.size().x(), 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.x() -= (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 + coord_t(SCALED_EPSILON)) / 2;
 
    int gap_line = params.horiz_move / line_spacing;
    if (gap_line % 2 == 0) {
        x0 += params.horiz_move - gap_line * line_spacing;
    } else {
        x0 += params.horiz_move - (gap_line - 1) * line_spacing;
        n_vlines += 1;
    }
#ifdef SLIC3R_DEBUG
    static int iRun = 0;
    BoundingBox bbox_svg = poly_with_offset.bounding_box_outer();
    ::Slic3r::SVG svg(debug_out_path("FillRectilinear-%d.svg", iRun), bbox_svg); // , scale_(1.));
    poly_with_offset.export_to_svg(svg);
    {
        ::Slic3r::SVG svg(debug_out_path("FillRectilinear-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 by horizontal / vertical links, classify the links based on link_max_length as too long.
  connect_segment_intersections_by_contours(poly_with_offset, segs, params, link_max_length);
 
#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 */
 
    //FIXME this is a hack to get the monotonic infill rolling. We likely want a smarter switch, likely based on user decison.
    bool monotonic_infill = params.monotonic; // || params.density > 0.99;
    if (monotonic_infill) {
        // Sometimes the outer contour pinches the inner contour from both sides along a single vertical line.
        // This situation is not handled correctly by generate_montonous_regions().
        // Insert phony OUTER_HIGH / OUTER_LOW pairs at the position where the contour is pinched.
        pinch_contours_insert_phony_outer_intersections(segs);
    std::vector<MonotonicRegion> regions = generate_montonous_regions(segs);
#ifdef INFILL_DEBUG_OUTPUT
        {
            static int iRun;
            export_monotonous_regions_to_svg(poly_with_offset, segs, regions, debug_out_path("%s-%03d.svg", "MontonousRegions-initial", iRun ++));
        }
#endif // INFILL_DEBUG_OUTPUT
    connect_monotonic_regions(regions, poly_with_offset, segs);
        if (! regions.empty()) {
        std::mt19937_64 rng;
        std::vector<MonotonicRegionLink> path = chain_monotonic_regions(regions, poly_with_offset, segs, rng);
        polylines_from_paths(path, poly_with_offset, segs, polylines_out);
        }
  } else {
    traverse_graph_generate_polylines(poly_with_offset, params, segs, this->has_consistent_pattern(), polylines_out);
    }
 
#ifdef SLIC3R_DEBUG
    {
        {
            ::Slic3r::SVG svg(debug_out_path("FillRectilinear-final-%03d.svg", iRun), bbox_svg); // , scale_(1.));
            poly_with_offset.export_to_svg(svg);
            for (size_t i = n_polylines_out_initial; i < polylines_out.size(); ++ i)
                svg.draw(polylines_out[i].lines(), "black");
        }
        // Paint a picture per polyline. This makes it easier to discover the order of the polylines and their overlap.
        for (size_t i_polyline = n_polylines_out_initial; i_polyline < polylines_out.size(); ++ i_polyline) {
            ::Slic3r::SVG svg(debug_out_path("FillRectilinear-final-%03d-%03d.svg", iRun, i_polyline), bbox_svg); // , scale_(1.));
            svg.draw(polylines_out[i_polyline].lines(), "black");
        }
    }
#endif /* SLIC3R_DEBUG */
 
    // paths must be rotated back
    for (Polylines::iterator it = polylines_out.begin() + n_polylines_out_initial; it != polylines_out.end(); ++ it) {
        // No need to translate, the absolute position is irrelevant.
        // it->translate(- rotate_vector.second(0), - rotate_vector.second(1));
        assert(! it->has_duplicate_points());
        it->rotate(rotate_vector.first);
        //FIXME rather simplify the paths to avoid very short edges?
        //assert(! it->has_duplicate_points());
        it->remove_duplicate_points();
 
         //get origin direction infill
        if (params.symmetric_infill_y_axis) {
            it->symmetric_y(params.symmetric_y_axis);
        }
    }
 
#ifdef SLIC3R_DEBUG
    // Verify, that there are no duplicate points in the sequence.
    for (Polyline &polyline : polylines_out)
        assert(! polyline.has_duplicate_points());
#endif /* SLIC3R_DEBUG */
 
 
 
    return true;
}

References Slic3r::Fill::_adjust_solid_spacing(), Slic3r::Fill::_infill_direction(), Slic3r::align_to_grid(), Slic3r::Fill::bounding_box, Slic3r::ExPolygonWithOffset::bounding_box_outer(), Slic3r::ExPolygonWithOffset::bounding_box_src(), Slic3r::BoundingBoxBase< PointType, APointsType >::center(), Slic3r::chain_monotonic_regions(), Slic3r::SVG::Close(), Slic3r::connect_monotonic_regions(), Slic3r::connect_segment_intersections_by_contours(), Slic3r::debug_out_path(), Slic3r::FillParams::density, Slic3r::FillParams::dont_adjust, Slic3r::SVG::draw(), Slic3r::Surface::expolygon, Slic3r::Fill::extended_object_bounding_box(), Slic3r::FillParams::full_infill(), Slic3r::generate_montonous_regions(), Slic3r::Fill::has_consistent_pattern(), Slic3r::FillParams::horiz_move, Slic3r::SegmentedIntersectionLine::intersections, Slic3r::Fill::link_max_length, Slic3r::FillParams::locked_zag, M_PI, Slic3r::FillParams::monotonic, Slic3r::ExPolygonWithOffset::n_contours_inner, Slic3r::Fill::overlap, Slic3r::pinch_contours_insert_phony_outer_intersections(), Slic3r::polylines_from_paths(), Slic3r::SegmentedIntersectionLine::pos, Slic3r::Point::rotated(), scale_, SCALED_EPSILON, Slic3r::BoundingBoxBase< PointType, APointsType >::size(), Slic3r::slice_region_by_vertical_lines(), Slic3r::Fill::spacing, Slic3r::FillParams::symmetric_infill_y_axis, Slic3r::FillParams::symmetric_y_axis, Slic3r::BoundingBoxBase< PointType, APointsType >::translate(), Slic3r::traverse_graph_generate_polylines(), and Slic3r::unscale().

Referenced by Slic3r::FillMonotonic::fill_surface(), Slic3r::FillMonotonicLine::fill_surface(), Slic3r::FillMonotonicLines::fill_surface(), and fill_surface().

Here is the call graph for this function:

Here is the caller graph for this function:

fill_surface_by_multilines()

bool Slic3r::FillRectilinear::fill_surface_by_multilines ( const Surface * surface, FillParams params, const std::initializer_list< SweepParams > & sweep_params, Polylines & polylines_out )

protectedinherited

{
    assert(sweep_params.size() >= 1);
    assert(!params.full_infill());
    params.density /= double(sweep_params.size());
    assert(params.density > 0.0001f && params.density <= 1.f);
 
    ExPolygonWithOffset poly_with_offset_base(surface->expolygon, 0, float(scale_(this->overlap + 0.5 * params.multiline * this->spacing)));//increase offset to crop infill lines when using multiline infill
    if (poly_with_offset_base.n_contours == 0)
        // Not a single infill line fits.
        return true;
 
    Polylines fill_lines;
    coord_t line_width   = coord_t(scale_(this->spacing));
    coord_t line_spacing = coord_t(scale_(this->spacing) * params.multiline / params.density);
    std::pair<float, Point> rotate_vector = this->_infill_direction(surface);
    for (const SweepParams &sweep : sweep_params) {
        // Rotate polygons so that we can work with vertical lines here
        float angle = rotate_vector.first + sweep.angle_base;
 
        make_fill_lines(ExPolygonWithOffset(poly_with_offset_base, -angle), rotate_vector.second.rotated(-angle), angle,
                        line_width + coord_t(SCALED_EPSILON), line_spacing, coord_t(scale_(sweep.pattern_shift)), fill_lines);
    }
        
    // Apply multiline offset if needed
    multiline_fill(fill_lines, params, spacing);
 
    // Contract surface polygon by half line width to avoid excesive overlap with perimeter
    const ExPolygons contracted = offset_ex(surface->expolygon, -float(scale_(0.5 * this->spacing)));
 
    // if contraction results in empty ExPolygons, use original surface
    const ExPolygons& intersection_surface = contracted.empty() ? ExPolygons{surface->expolygon} : contracted;
 
    // Intersect polylines with perimeter
    fill_lines = intersection_pl(std::move(fill_lines), intersection_surface);
 
    if ((params.pattern == ipLateralLattice || params.pattern == ipLateralHoneycomb) && params.multiline > 1)
        remove_overlapped(fill_lines, line_width);
 
    if (!fill_lines.empty()) {
        if (params.dont_connect()) {
            if (fill_lines.size() > 1)
                fill_lines = chain_polylines(std::move(fill_lines));
            append(polylines_out, std::move(fill_lines));
        } else
            connect_infill(std::move(fill_lines), to_polygons(intersection_surface), get_extents(surface->expolygon.contour), polylines_out,
                           this->spacing, params);
    }
 
    return true;
}

References Slic3r::Fill::_infill_direction(), Slic3r::Fill::angle, Slic3r::append(), Slic3r::chain_polylines(), Slic3r::Fill::connect_infill(), Slic3r::ExPolygon::contour, Slic3r::FillParams::density, Slic3r::FillParams::dont_connect(), Slic3r::Surface::expolygon, Slic3r::FillParams::full_infill(), Slic3r::get_extents(), Slic3r::intersection_pl(), Slic3r::ipLateralHoneycomb, Slic3r::ipLateralLattice, Slic3r::make_fill_lines(), Slic3r::FillParams::multiline, Slic3r::multiline_fill(), Slic3r::ExPolygonWithOffset::n_contours, Slic3r::offset_ex(), Slic3r::Fill::overlap, Slic3r::FillParams::pattern, Slic3r::remove_overlapped(), scale_, SCALED_EPSILON, Slic3r::Fill::spacing, and Slic3r::to_polygons().

Referenced by Slic3r::FillCubic::fill_surface(), Slic3r::FillGrid::fill_surface(), Slic3r::FillLateralHoneycomb::fill_surface(), Slic3r::FillLateralLattice::fill_surface(), Slic3r::FillQuarterCubic::fill_surface(), fill_surface(), Slic3r::FillStars::fill_surface(), and Slic3r::FillTriangles::fill_surface().

Here is the call graph for this function:

Here is the caller graph for this function:

fill_surface_extrusion()

void Slic3r::Fill::fill_surface_extrusion ( const Surface * surface, const FillParams & params, ExtrusionEntitiesPtr & out )

virtualinherited

Reimplemented in Slic3r::FillConcentricInternal, and Slic3r::FillLockedZag.

{
    Polylines polylines;
    ThickPolylines thick_polylines;
    try {
        if (params.use_arachne)
            thick_polylines = this->fill_surface_arachne(surface, params);
        else
            polylines = this->fill_surface(surface, params);
    }
    catch (InfillFailedException&) {}
 
    if (!polylines.empty() || !thick_polylines.empty()) {
        // calculate actual flow from spacing (which might have been adjusted by the infill
        // pattern generator)
        double flow_mm3_per_mm = params.flow.mm3_per_mm();
        double flow_width = params.flow.width();
        if (params.using_internal_flow) {
            // if we used the internal flow we're not doing a solid infill
            // so we can safely ignore the slight variation that might have
            // been applied to f->spacing
        }
        else {
            Flow new_flow = params.flow.with_spacing(this->spacing);
            flow_mm3_per_mm = new_flow.mm3_per_mm();
            flow_width = new_flow.width();
        }
        // Save into layer.
        ExtrusionEntityCollection* eec = nullptr;
        out.push_back(eec = new ExtrusionEntityCollection());
        // Only concentric fills are not sorted.
        eec->no_sort = this->no_sort();
        // ORCA: special flag for flow rate calibration
        auto is_flow_calib = params.extrusion_role == erTopSolidInfill && this->print_object_config->has("calib_flowrate_topinfill_special_order") &&
                             this->print_object_config->option("calib_flowrate_topinfill_special_order")->getBool();
        // Orca: a forced surface fill order must survive the G-code path planner, which would
        // otherwise re-chain and possibly reverse the paths. The same applies to the flow rate
        // calibration's special toolpath order.
        const bool keep_fill_order = params.fill_order != SurfaceFillOrder::Default;
        if (is_flow_calib || keep_fill_order) {
            eec->no_sort = true;
        }
        size_t idx   = eec->entities.size();
        if (params.use_arachne) {
            Flow new_flow = params.flow.with_spacing(float(this->spacing));
            variable_width(thick_polylines, params.extrusion_role, new_flow, eec->entities);
            thick_polylines.clear();
        }
        else {
            // Orca: sparse infill lines whose ends are next to each other print as one path, without a travel between them.
            if (params.extrusion_role == erInternalInfill && ! eec->no_sort)
                join_close_ends(polylines, scale_(2. * this->spacing), params.can_reverse);
            extrusion_entities_append_paths(
                eec->entities, std::move(polylines),
                params.extrusion_role,
                flow_mm3_per_mm, float(flow_width), params.flow.height());
        }
        if (!params.can_reverse || is_flow_calib || keep_fill_order) {
            for (size_t i = idx; i < eec->entities.size(); i++)
                eec->entities[i]->set_reverse();
        }
 
        // Orca: run gap fill
        this->_create_gap_fill(surface, params, eec);
    }
}

References _create_gap_fill(), Slic3r::FillParams::can_reverse, Slic3r::Default, Slic3r::ExtrusionEntityCollection::entities, Slic3r::erInternalInfill, Slic3r::erTopSolidInfill, Slic3r::extrusion_entities_append_paths(), Slic3r::FillParams::extrusion_role, Slic3r::FillParams::fill_order, fill_surface(), fill_surface_arachne(), Slic3r::FillParams::flow, Slic3r::Flow::height(), Slic3r::join_close_ends(), Slic3r::Flow::mm3_per_mm(), Slic3r::ExtrusionEntityCollection::no_sort, no_sort(), print_object_config, scale_, spacing, Slic3r::FillParams::use_arachne, Slic3r::FillParams::using_internal_flow, Slic3r::variable_width(), Slic3r::Flow::width(), and Slic3r::Flow::with_spacing().

Here is the call graph for this function:

fill_surface_trapezoidal()

bool Slic3r::FillRectilinear::fill_surface_trapezoidal ( const Surface * surface, FillParams params, Polylines & polylines_out, int Pattern_type )

protectedinherited

{
    assert(params.multiline > 1);
 
    Polylines polylines;
 
    // Common parameters
    const coord_t d1 = coord_t(scale_(this->spacing)) * params.multiline; // Infill total wall thickness
 
    // Pattern-specific parameters
    coord_t                  period;
    double                   base_angle;
    std::pair<double, Point> rotate_vector = this->_infill_direction(surface);
 
    if (Pattern_type == 0) {
        // Grid pattern parameters
        period     = coord_t((2.0 * d1 / params.density) * std::sqrt(2.0));
        base_angle = rotate_vector.first + M_PI_4; // 45
    } else {
        // Triangular-family pattern parameters (triangles / stars)
        period     = coord_t((2.0 * d1 / params.density) * std::sqrt(3.0));
        base_angle = rotate_vector.first + M_PI_2; // 90
    }
 
    // Obtain the expolygon and rotate to align with pattern base angle
    ExPolygon expolygon = surface->expolygon;
    if (std::abs(base_angle) >= EPSILON) {
        expolygon.rotate(-base_angle, rotate_vector.second);
    }
 
    const size_t infill_layer_id = (surface->thickness_layers > 0) ? this->layer_id / surface->thickness_layers : this->layer_id;
    // The triangular family turns by 120 degrees every layer, about the origin of the frame it is built in.
    const size_t layer_mod = infill_layer_id % 3;
    const double angle     = layer_mod * 2.0 * M_PI / 3.0;
 
    // Only build the rows over the surface, seen in the frame they are built in.
    Polygon local = expolygon.contour;
    if (Pattern_type != 0) {
        local.translate(-rotate_vector.second.x(), -rotate_vector.second.y());
        if (layer_mod)
            local.rotate(-angle);
    }
    BoundingBox cover = get_extents(local);
    cover.offset(period);
 
    switch (Pattern_type) {
    case 0: // Grid / Trapezoidal
    {
        // Generate a non-crossing trapezoidal pattern to avoid overextrusion at intersections when `multiline > 1`.
        /*
         *         P2--P3
         *        /      \
         *  P0_P1/        \P4_
         */
        // P0xP1x=P4xP0x=d1/2
        // P2xP3x=d1
        // P1yP2y=P2yP3y=d2
        
        const coord_t d2 = coord_t(0.5 * period - d1);
 
        //  Align bounding box to the grid, phased through the box center so separated infills align
        //  each part on itself (grid_center is the origin for a standalone object / feature off).
        //  Captured before the merge, which grows bb and would otherwise shift its center.
        BoundingBox bb = this->extended_object_bounding_box();
        const Point grid_center = bb.center();
        bb.merge(align_to_grid(bb.min, Point(period, period), grid_center));
        const coord_t xmin = bb.min.x();
        const coord_t ymin = bb.min.y();
 
        auto transpose = [&grid_center](const Point &p) {
            return Point(grid_center.x() + p.y() - grid_center.y(), grid_center.y() + p.x() - grid_center.x());
        };
        if (infill_layer_id % 2 == 1)
            cover = BoundingBox(transpose(cover.min), transpose(cover.max));
        const coord_t row_spacing = period / 2;
        const coord_t first_x = xmin + (coord_t(std::floor(double(cover.min.x() - xmin) / period)) - 1) * period;
        const coord_t last_x  = xmin + (coord_t(std::ceil(double(cover.max.x() - xmin) / period)) + 1) * period;
        const coord_t first_row = coord_t(std::floor(double(cover.min.y() - ymin) / row_spacing)) - 1;
        const coord_t last_row  = coord_t(std::ceil(double(cover.max.y() - ymin) / row_spacing)) + 1;
 
        // Create the two base row patterns once
        Polyline base_row_normal;
        base_row_normal.points.reserve(((last_x - first_x) / period + 1) * 5); // 5 points per trapezoid
        Polyline base_row_flipped;
        base_row_flipped.points.reserve(((last_x - first_x) / period + 1) * 5); // 5 points per trapezoid
 
        // Build rows on the same global period grid, limited to the surface cover.
        for (coord_t x = first_x; x < last_x; x += period) {
            // Normal row
            base_row_normal.points.emplace_back(Point(x, d1 / 2));                             // P0
            base_row_normal.points.emplace_back(Point(x + d1 / 2, d1 / 2));                    // P1
            base_row_normal.points.emplace_back(Point(x + d1 / 2 + d2, d1 / 2 + d2));          // P2
            base_row_normal.points.emplace_back(Point(x + d1 / 2 + d2 + d1, d1 / 2 + d2));     // P3
            base_row_normal.points.emplace_back(Point(x + period - d1 / 2, d1 / 2));           // P4
        }
 
        // Flipped row (mirrored vertically)
        base_row_flipped.points = base_row_normal.points;
        for (auto& p : base_row_flipped.points) {
            p.y() = period / 2 - p.y();
        }
        
        // Pre-allocate polylines
        const size_t estimated_rows = size_t(last_row - first_row + 1);
        polylines.reserve(estimated_rows);
 
        bool flip_vertical = (first_row % 2) != 0;
 
        // Copy and translate only rows intersecting the surface cover.
        for (coord_t row = first_row; row <= last_row; ++row) {
            const coord_t y = ymin + row * row_spacing;
            Polyline pl_row = flip_vertical ? base_row_flipped : base_row_normal;
 
            // Translate all points vertically
            for (Point& p : pl_row.points) {
                p.y() += y;
            }
 
            polylines.emplace_back(std::move(pl_row));
            flip_vertical = !flip_vertical;
        }
 
        // transpose points for odd infill layers (taking infill combination into account).
        // Orca: mirror across the diagonal through grid_center (not the origin), so the swapped
        // layers stay aligned with the center-phased grid. For a standalone object / feature off,
        // grid_center is the origin and this is a plain x/y swap.
        if (infill_layer_id % 2 == 1)
            for (Polyline& pl : polylines)
                for (Point& p : pl.points)
                    p = transpose(p);
        break;
    }
 
    case 1: // Triangular
    {
        // Generate a non-crossing trapezoidal pattern with a base line below.
        /*
         *      P1-P2
         *     /     \
         *  P0/       \P3_P4
         *  ----------------
         */
        // P1xP2x=P3xP4x=d2
        // P0yP1y=P2yP3y=h-2d1
        //
        
        // Triangular pattern density adjustment:
        const coord_t d2_tri = coord_t(2.0 / std::sqrt(3.0) * d1);
        const coord_t h      = coord_t(0.5 * std::sqrt(3.0) * period); // height of triangle
 
        // Keep the existing origin-anchored lattice, but generate only nearby tiles.
        const coord_t x_min_aligned = (coord_t(std::floor(double(cover.min.x()) / period)) - 1) * period;
        const coord_t x_max_aligned = (coord_t(std::ceil(double(cover.max.x()) / period)) + 1) * period;
        const coord_t first_row = coord_t(std::floor(double(cover.min.y()) / h)) - 1;
        const coord_t last_row  = coord_t(std::ceil(double(cover.max.y()) / h)) + 1;
 
        // Pre-allocate estimated number of polylines
        const size_t estimated_rows = size_t(last_row - first_row + 1);
        const size_t estimated_polylines = estimated_rows * 2; // base line + trapezoid line per row
        polylines.reserve(estimated_polylines);
 
        // Create the two base row templates once
        Polyline base_line_template;
        base_line_template.points.reserve(2); // 2 points for base line
        Polyline trapezoid_row_normal;
        trapezoid_row_normal.points.reserve(((x_max_aligned - x_min_aligned) / period) * 5); // 5 points per trapezoid
        Polyline trapezoid_row_shifted;
        trapezoid_row_shifted.points.reserve(((x_max_aligned - x_min_aligned) / period) * 5); // 5 points per trapezoid
        // Build base line template (from x_min_aligned to x_max_aligned)
        base_line_template.points.emplace_back(Point(x_min_aligned, 0));
        base_line_template.points.emplace_back(Point(x_max_aligned, 0));
 
        // Build complete trapezoid rows once
        // Normal row (no shift)
        for (coord_t x = x_min_aligned; x < x_max_aligned; x += period) {
            trapezoid_row_normal.points.emplace_back(Point(x + d2_tri / 2, d1));                  // P0
            trapezoid_row_normal.points.emplace_back(Point(x + period / 2 - d2_tri / 2, h - d1)); // P1
            trapezoid_row_normal.points.emplace_back(Point(x + period / 2 + d2_tri / 2, h - d1)); // P2
            trapezoid_row_normal.points.emplace_back(Point(x + period - d2_tri / 2, d1));         // P3
            trapezoid_row_normal.points.emplace_back(Point(x + period, d1));                      // P4
        }
 
        // Shifted row (mirrored vertically)
        trapezoid_row_shifted.points = trapezoid_row_normal.points;
        for (auto& p : trapezoid_row_shifted.points)
            p.y() = h - p.y();
 
        // Generate pattern by copying and translating templates vertically
        bool shift_row = (first_row % 2) != 0;
        for (coord_t row = first_row; row <= last_row; ++row) {
            const coord_t y = row * h;
            // Base line - copy and translate
            Polyline base_line = base_line_template;
            for (Point& p : base_line.points) {
                p.y() += y;
            }
            polylines.emplace_back(std::move(base_line));
 
            // Trapezoid line - copy and translate the appropriate template
            Polyline trapezoid_line = shift_row ? trapezoid_row_shifted : trapezoid_row_normal;
            for (Point& p : trapezoid_line.points) {
                p.y() += y;
            }
 
            if (!trapezoid_line.points.empty()) {
                polylines.emplace_back(std::move(trapezoid_line));
            }
 
            shift_row = !shift_row;
        }
        break;
    }
 
    case 2: // Tri-hexagon / FillStars
    {
        // Pattern parameters
        const coord_t hex_height     = coord_t(0.5 * std::sqrt(3.0) * period);
        const coord_t tri_height     = hex_height / 2;
        const coord_t d1_half        = d1 / 2;
        const coord_t chamfer_height = std::sqrt(3.0) * d1_half;
        const coord_t d1_half_base   = d1_half / std::sqrt(3.0);
        const coord_t half_period    = period / 2;
        const coord_t quarter_period = period / 4;
        const coord_t row_y_offset   = tri_height - (2 * tri_height) / 3;
 
        // Keep the lattice anchored at the origin while generating only tiles around this surface.
        const int64_t first_tile = int64_t(std::floor(double(cover.min.x()) / period)) - 1;
        const int64_t last_tile  = int64_t(std::ceil(double(cover.max.x()) / period)) + 1;
        const int64_t first_row  = int64_t(std::floor(double(cover.min.y() - row_y_offset) / hex_height)) - 1;
        const int64_t last_row   = int64_t(std::ceil(double(cover.max.y() - row_y_offset) / hex_height)) + 1;
 
        const size_t estimated_rows      = size_t(last_row - first_row + 1);
        const size_t estimated_polylines = estimated_rows * 2;
        polylines.reserve(estimated_polylines);
 
        Polyline star_row_normal;
        star_row_normal.points.reserve(size_t(last_tile - first_tile) * 7);
        Polyline star_row_mirrored;
        star_row_mirrored.points.reserve(size_t(last_tile - first_tile) * 7);
 
        for (int64_t tile = first_tile; tile < last_tile; ++tile) {
            const coord_t x = coord_t(tile * period) - half_period;
            star_row_normal.points.emplace_back(Point(x, hex_height));                                               // P0
            star_row_normal.points.emplace_back(Point(x + quarter_period - d1, hex_height));                         // P1
            star_row_normal.points.emplace_back(Point(x + quarter_period + d1_half, hex_height - chamfer_height));   // P2
            star_row_normal.points.emplace_back(Point(x + half_period - d1_half_base, tri_height + d1_half));        // P3
            star_row_normal.points.emplace_back(Point(x + half_period + d1_half_base, tri_height + d1_half));        // P4
            star_row_normal.points.emplace_back(Point(x + (period * 3) / 4 - d1_half, hex_height - chamfer_height)); // P5
            star_row_normal.points.emplace_back(Point(x + (period * 3) / 4 + d1, hex_height));                       // P6
        }
 
        star_row_mirrored.points = star_row_normal.points;
        for (auto& p : star_row_mirrored.points)
            p.y() = hex_height - p.y();
 
        const coord_t global_x_shift = half_period;
        auto append_row_with_shift   = [&polylines](const Polyline& row_template, coord_t x_shift, coord_t y_shift) {
            Polyline row = row_template;
            for (Point& p : row.points) {
                p.x() += x_shift;
                p.y() += y_shift;
            }
            if (!row.points.empty())
                polylines.emplace_back(std::move(row));
        };
 
        for (int64_t row = first_row; row <= last_row; ++row) {
            const coord_t y = coord_t(row * hex_height) + row_y_offset;
            const coord_t x_shift = (row % 2 == 0) ? 0 : half_period;
            append_row_with_shift(star_row_normal, x_shift + global_x_shift, y);
            append_row_with_shift(star_row_mirrored, x_shift + global_x_shift, y);
        }
        break;
    }
 
    case 3: // Cubic
    {
        // Same z shifted lines as the single-line cubic; the slanted ones cross tau above the horizontal ones.
        auto pos_mod = [](double a, double m) { const double r = std::fmod(a, m); return r < 0. ? r + m : r; };
        const double h     = 0.5 * std::sqrt(3.0) * period;
        const double shift = scale_(std::sqrt(0.5) * this->z);
        const double tau   = pos_mod(-3. * shift, h);
        const double y0    = pos_mod(-2. * shift, 2. * h);
 
        std::array<std::vector<Vec2d>, 2> levels{ cubic_upper_level(h - tau, h, period, d1), cubic_upper_level(tau, h, period, d1) };
        for (Vec2d &p : levels.front())
            p.y() = h - p.y();
 
        const int64_t n_min = int64_t(std::floor((cover.min.y() - y0) / h)) - 1;
        const int64_t n_max = int64_t(std::ceil((cover.max.y() - y0) / h)) + 1;
        polylines.reserve(size_t(n_max - n_min + 1) * levels.size());
        for (int64_t n = n_min; n <= n_max; ++n) {
            const double  x_off = (n & 1) ? 0.5 * period : 0.;
            const double  base  = y0 + double(n) * h - tau;
            const int64_t j_min = int64_t(std::floor((cover.min.x() - x_off) / period)) - 1;
            const int64_t j_max = int64_t(std::ceil((cover.max.x() - x_off) / period));
            for (const std::vector<Vec2d> &level : levels) {
                Polyline row;
                row.points.reserve(size_t(j_max - j_min + 1) * level.size());
                for (int64_t j = j_min; j <= j_max; ++j)
                    for (size_t i = (j == j_min) ? 0 : 1; i < level.size(); ++i)
                        row.points.emplace_back(coord_t(std::round(x_off + double(j * period) + level[i].x())),
                                                coord_t(std::round(base + level[i].y())));
                polylines.emplace_back(std::move(row));
            }
        }
        break;
    }
 
    default:
        // Handle unknown pattern type
        break;
    }
 
    // Orca: cases 1 to 3 anchor the pattern at the origin, so on their own they phase to the global
    // origin and every part shares one grid. Shift the pattern onto the box center
    // this->bounding_box carries, so separated infills align each part on itself. The center is the
    // origin for a standalone object (or when the feature is off), making the shift a no-op there.
    if (Pattern_type != 0)
        for (Polyline &pl : polylines) {
            if (layer_mod)
                pl.rotate(angle, Point(0, 0));
            pl.translate(rotate_vector.second);
        }
 
    // Orca: round the corners of the trapezoids. The straight base lines of the triangular family
    // have no corner to round.
    smooth_polylines_corners(polylines, params.corner_smoothing());
 
    // Only the centerlines within d1 / 2 of the surface have outlines reaching it.
    polylines = intersection_pl(std::move(polylines), offset(expolygon, float(d1 / 2)));
 
    // Apply multiline fill
    multiline_fill(polylines, params, spacing);
 
    // Start each outline on the cap at the first end of its path, outside the surface, so clipping splits it only there.
    const Vec2d row_dir = Pattern_type != 0 ? Vec2d(std::cos(angle), std::sin(angle)) : infill_layer_id % 2 ? Vec2d::UnitY() : Vec2d::UnitX();
    for (Polyline &pl : polylines)
        if (pl.size() > 3 && pl.first_point() == pl.last_point()) {
            pl.points.pop_back();
            std::rotate(pl.points.begin(), std::min_element(pl.points.begin(), pl.points.end(), [&row_dir](const Point &a, const Point &b) {
                return row_dir.dot(a.cast<double>()) < row_dir.dot(b.cast<double>());
            }), pl.points.end());
            pl.points.emplace_back(pl.points.front());
        }
 
    // Contract surface polygon by half line width to avoid excesive overlap with perimeter
    ExPolygons contracted = offset_ex(expolygon, -float(scale_(0.5 * this->spacing)));
 
    // if contraction results in empty polygon, use original surface
    const ExPolygons& intersection_surface = contracted.empty() ? ExPolygons{expolygon} : contracted;
 
    // Intersect polylines with offset expolygon
    polylines = intersection_pl(std::move(polylines), intersection_surface);
 
    // Remove very short segments that may cause connection issues
    const double minlength = scale_(0.8 * this->spacing);
    if (minlength > 0 && !polylines.empty()) {
        polylines.erase(std::remove_if(polylines.begin(), polylines.end(),
                                       [minlength](const Polyline& pl) { return pl.length() < minlength; }),
                        polylines.end());
    }
 
    // Connect infill lines using offset expolygon
    int infill_start_idx = polylines_out.size();
    if (!polylines.empty()) {
        if (params.dont_connect()) {
            if (polylines.size() > 1)
                polylines = chain_polylines(std::move(polylines));
            append(polylines_out, std::move(polylines));
        } else {
            connect_infill(std::move(polylines), to_polygons(intersection_surface), get_extents(intersection_surface), polylines_out,
                           this->spacing, params);
        }
 
        // Rotate back the infill lines to original orientation
        if (std::abs(base_angle) >= EPSILON) {
            for (auto it = polylines_out.begin() + infill_start_idx; it != polylines_out.end(); ++it) {
                it->rotate(base_angle, rotate_vector.second);
            }
        }
    }
 
    return true;
}

References Slic3r::Fill::_infill_direction(), Slic3r::align_to_grid(), Slic3r::Fill::angle, Slic3r::append(), Slic3r::BoundingBoxBase< PointType, APointsType >::center(), Slic3r::chain_polylines(), Slic3r::Fill::connect_infill(), Slic3r::ExPolygon::contour, Slic3r::FillParams::corner_smoothing(), Slic3r::cubic_upper_level(), Slic3r::FillParams::density, Slic3r::FillParams::dont_connect(), EPSILON, Slic3r::Surface::expolygon, Slic3r::Fill::extended_object_bounding_box(), Slic3r::get_extents(), Slic3r::intersection_pl(), Slic3r::Fill::layer_id, M_PI, Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::BoundingBoxBase< PointType, APointsType >::min, Slic3r::FillParams::multiline, Slic3r::multiline_fill(), Slic3r::BoundingBoxBase< PointType, APointsType >::offset(), Slic3r::offset(), Slic3r::offset_ex(), Slic3r::MultiPoint::points, Slic3r::ExPolygon::rotate(), scale_, Slic3r::smooth_polylines_corners(), Slic3r::Fill::spacing, Slic3r::Surface::thickness_layers, Slic3r::to_polygons(), and Slic3r::Fill::z.

Referenced by Slic3r::FillCubic::fill_surface(), Slic3r::FillGrid::fill_surface(), Slic3r::FillStars::fill_surface(), and Slic3r::FillTriangles::fill_surface().

Here is the call graph for this function:

Here is the caller graph for this function:

has_consistent_pattern()

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

inlinevirtualinherited

Reimplemented in Slic3r::FillCrossZag, Slic3r::FillLockedZag, and Slic3r::FillZigZag.

{ return false; }

Referenced by Slic3r::FillRectilinear::fill_surface_by_lines().

Here is the caller graph for this function:

is_self_crossing()

bool Slic3r::FillRectilinear::is_self_crossing ( )

inlineoverridevirtualinherited

Implements Slic3r::Fill.

Reimplemented in Slic3r::FillStars, and Slic3r::FillTriangles.

{ return false; }

new_from_type() [1/2]

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

staticinherited

{
    switch (type) {
    case ipConcentric:          return new FillConcentric();
    case ipSpiralInset:    return new FillSpiralInset();
    case ipHoneycomb:           return new FillHoneycomb();
    case ipLateralHoneycomb:         return new FillLateralHoneycomb();
    case ip3DHoneycomb:         return new Fill3DHoneycomb();
    case ipGyroid:              return new FillGyroid();
    case ipTpmsD:               return new FillTpmsD();//from creality print
    case ipTpmsFK:              return new FillTpmsFK();
    case ipRectilinear:         return new FillRectilinear();
    case ipAlignedRectilinear:  return new FillAlignedRectilinear();
    case ipCrossHatch:          return new FillCrossHatch();
    case ipMonotonic:           return new FillMonotonic();
    case ipLine:                return new FillLine();
    case ipGrid:                return new FillGrid();
    case ipLateralLattice:           return new FillLateralLattice();
    case ipTriangles:           return new FillTriangles();
    case ipStars:               return new FillStars();
    case ipCubic:               return new FillCubic();
    case ipQuarterCubic:        return new FillQuarterCubic();
    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();  // simply line fill
    case ipLightning:           return new FillLightning::Filler();
    // BBS: for internal solid infill only
    case ipConcentricInternal:  return new FillConcentricInternal();
    // BBS: for bottom and top surface only
    // Orca: Replace BBS implementation with Prusa implementation
    case ipMonotonicLine:       return new FillMonotonicLines();
    case ipZigZag:              return new FillZigZag();
    case ipCrossZag:            return new FillCrossZag();
    case ipLockedZag:           return new FillLockedZag();
    default: throw Slic3r::InvalidArgument("unknown type");
    }
}

References Fill(), Slic3r::ip3DHoneycomb, Slic3r::ipAdaptiveCubic, Slic3r::ipAlignedRectilinear, Slic3r::ipArchimedeanChords, Slic3r::ipConcentric, Slic3r::ipConcentricInternal, Slic3r::ipCrossHatch, Slic3r::ipCrossZag, Slic3r::ipCubic, Slic3r::ipGrid, Slic3r::ipGyroid, Slic3r::ipHilbertCurve, Slic3r::ipHoneycomb, Slic3r::ipLateralHoneycomb, Slic3r::ipLateralLattice, Slic3r::ipLightning, Slic3r::ipLine, Slic3r::ipLockedZag, Slic3r::ipMonotonic, Slic3r::ipMonotonicLine, Slic3r::ipOctagramSpiral, Slic3r::ipQuarterCubic, Slic3r::ipRectilinear, Slic3r::ipSpiralInset, Slic3r::ipStars, Slic3r::ipSupportBase, Slic3r::ipSupportCubic, Slic3r::ipTpmsD, Slic3r::ipTpmsFK, Slic3r::ipTriangles, and Slic3r::ipZigZag.

Referenced by Slic3r::Layer::generate_sparse_infill_polylines_for_anchoring(), Slic3r::WipeTower2::generate_support_cone_wall(), Slic3r::TreeSupport3D::generate_support_infill_lines(), Slic3r::generate_support_toolpaths(), Slic3r::TreeSupport::generate_toolpaths(), Slic3r::Layer::make_fills(), Slic3r::Layer::make_ironing(), new_from_type(), Slic3r::spreadDotsArea(), and use_bridge_flow().

Here is the call graph for this function:

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 Fill(), Slic3r::ConfigOptionEnum< T >::get_enum_values(), and new_from_type().

Here is the call graph for this function:

no_sort()

bool Slic3r::FillMonotonicLine::no_sort ( ) const

inlineoverridevirtual

Reimplemented from Slic3r::Fill.

{ return true; }

set_bounding_box()

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

inlineinherited

{ bounding_box = bbox; }

References bounding_box.

set_lock_region_param()

virtual void Slic3r::Fill::set_lock_region_param ( const LockRegionParam & lock_param )

inlinevirtualinherited

Reimplemented in Slic3r::FillLockedZag.

{};

use_bridge_flow() [1/2]

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

inlinevirtualinherited

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

{ return false; }

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;
}

References Slic3r::ipCount, and new_from_type().

Referenced by Slic3r::group_fills().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

adapt_fill_octree

FillAdaptive::Octree* Slic3r::Fill::adapt_fill_octree = nullptr

inherited

Referenced by Slic3r::FillAdaptive::Filler::_fill_surface_single().

adaptive_infill_field

const AdaptiveInfillField* Slic3r::Fill::adaptive_infill_field = nullptr

inherited

Referenced by Slic3r::FillGyroid::_fill_surface_single(), Slic3r::FillTpmsD::_fill_surface_single(), and Slic3r::FillTpmsFK::_fill_surface_single().

angle

float Slic3r::Fill::angle

inherited

Referenced by Fill(), Slic3r::Fill3DHoneycomb::_fill_surface_single(), Slic3r::FillCrossHatch::_fill_surface_single(), Slic3r::FillGyroid::_fill_surface_single(), Slic3r::FillTpmsD::_fill_surface_single(), Slic3r::FillTpmsFK::_fill_surface_single(), _infill_direction(), Slic3r::FillRectilinear::fill_surface_by_multilines(), Slic3r::FillRectilinear::fill_surface_trapezoidal(), Slic3r::generate_support_toolpaths(), Slic3r::TreeSupport::generate_toolpaths(), and Slic3r::make_perimeter_and_infill().

bounding_box

BoundingBox Slic3r::Fill::bounding_box

inherited

Referenced by Fill(), Slic3r::FillConcentric::_fill_surface_single(), Slic3r::FillHoneycomb::_fill_surface_single(), Slic3r::FillLine::_fill_surface_single(), Slic3r::FillPlanePath::_fill_surface_single(), Slic3r::FillSpiralInset::_fill_surface_single(), _infill_direction(), extended_object_bounding_box(), fill_surface(), Slic3r::FillRectilinear::fill_surface_by_lines(), and set_bounding_box().

dont_alternate_fill_direction

bool Slic3r::Fill::dont_alternate_fill_direction = false

inherited

Referenced by _infill_direction().

fixed_angle

bool Slic3r::Fill::fixed_angle {false}

inherited

{false};

Referenced by _infill_direction(), and _layer_angle().

infill_anchor

float Slic3r::Fill::infill_anchor = 400

staticinherited

infill_anchor_max

float Slic3r::Fill::infill_anchor_max = 20

staticinherited

layer_id

size_t Slic3r::Fill::layer_id

inherited

Referenced by Fill(), Slic3r::FillLightning::Filler::_fill_surface_single(), _infill_direction(), Slic3r::FillGrid::fill_surface(), Slic3r::FillLateralHoneycomb::fill_surface(), Slic3r::FillLateralLattice::fill_surface(), and Slic3r::FillRectilinear::fill_surface_trapezoidal().

link_max_length

coord_t Slic3r::Fill::link_max_length

inherited

Referenced by Fill(), Slic3r::FillRectilinear::fill_surface_by_lines(), and Slic3r::generate_support_toolpaths().

loop_clipping

coord_t Slic3r::Fill::loop_clipping

inherited

Referenced by Fill(), Slic3r::FillConcentric::_fill_surface_single(), Slic3r::FillConcentric::_fill_surface_single(), and Slic3r::FillConcentricInternal::fill_surface_extrusion().

no_overlap_expolygons

ExPolygons Slic3r::Fill::no_overlap_expolygons

inherited

Referenced by _create_gap_fill(), and Slic3r::FillConcentricInternal::fill_surface_extrusion().

overlap

coordf_t Slic3r::Fill::overlap

inherited

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

print_config

const PrintConfig* Slic3r::Fill::print_config = nullptr

inherited

Referenced by Slic3r::FillConcentric::_fill_surface_single(), Slic3r::FillSpiralInset::_fill_surface_single(), Slic3r::FillConcentricInternal::fill_surface_extrusion(), and Slic3r::Layer::make_fills().

print_object_config

const PrintObjectConfig* Slic3r::Fill::print_object_config = nullptr

inherited

Referenced by _create_gap_fill(), Slic3r::FillConcentric::_fill_surface_single(), Slic3r::FillPlanePath::_fill_surface_single(), Slic3r::FillSpiralInset::_fill_surface_single(), fill_surface_extrusion(), Slic3r::FillConcentricInternal::fill_surface_extrusion(), and Slic3r::Layer::make_fills().

spacing

coordf_t Slic3r::Fill::spacing

inherited

Referenced by Fill(), Slic3r::Fill3DHoneycomb::_fill_surface_single(), Slic3r::FillConcentric::_fill_surface_single(), Slic3r::FillConcentric::_fill_surface_single(), Slic3r::FillCrossHatch::_fill_surface_single(), Slic3r::FillGyroid::_fill_surface_single(), Slic3r::FillHoneycomb::_fill_surface_single(), Slic3r::FillLightning::Filler::_fill_surface_single(), Slic3r::FillLine::_fill_surface_single(), Slic3r::FillPlanePath::_fill_surface_single(), Slic3r::FillSpiralInset::_fill_surface_single(), Slic3r::FillSpiralInset::_fill_surface_single(), Slic3r::FillTpmsD::_fill_surface_single(), Slic3r::FillTpmsFK::_fill_surface_single(), chain_or_connect_infill(), connect_base_support(), connect_base_support(), connect_infill(), connect_infill(), connect_infill(), fill_surface(), Slic3r::FillLateralHoneycomb::fill_surface(), Slic3r::FillQuarterCubic::fill_surface(), Slic3r::FillStars::fill_surface(), Slic3r::FillSupportBase::fill_surface(), fill_surface_arachne(), Slic3r::FillRectilinear::fill_surface_by_lines(), Slic3r::FillRectilinear::fill_surface_by_multilines(), fill_surface_extrusion(), Slic3r::FillConcentricInternal::fill_surface_extrusion(), Slic3r::FillLockedZag::fill_surface_extrusion(), Slic3r::FillRectilinear::fill_surface_trapezoidal(), Slic3r::generate_support_toolpaths(), and Slic3r::TreeSupport::generate_toolpaths().

z

coordf_t Slic3r::Fill::z

inherited

Referenced by Fill(), Slic3r::Fill3DHoneycomb::_fill_surface_single(), Slic3r::FillAdaptive::Filler::_fill_surface_single(), Slic3r::FillCrossHatch::_fill_surface_single(), Slic3r::FillGyroid::_fill_surface_single(), Slic3r::FillTpmsD::_fill_surface_single(), Slic3r::FillTpmsFK::_fill_surface_single(), Slic3r::FillCubic::fill_surface(), Slic3r::FillLateralHoneycomb::fill_surface(), Slic3r::FillLateralLattice::fill_surface(), Slic3r::FillQuarterCubic::fill_surface(), and Slic3r::FillRectilinear::fill_surface_trapezoidal().

---

The documentation for this class was generated from the following files:

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Fill/FillRectilinear.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Fill/FillRectilinear.cpp