Slic3r::FillSpiralInset Class Reference

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

Inheritance diagram for Slic3r::FillSpiralInset:

Collaboration diagram for Slic3r::FillSpiralInset:

Public Member Functions
	~FillSpiralInset () override=default
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 Polylines	fill_surface (const Surface *surface, const FillParams &params)
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
Fill *	clone () const override
void	_fill_surface_single (const FillParams &params, unsigned int thickness_layers, const std::pair< float, Point > &direction, ExPolygon expolygon, Polylines &polylines_out) override
void	_fill_surface_single (const FillParams &params, unsigned int thickness_layers, const std::pair< float, Point > &direction, ExPolygon expolygon, ThickPolylines &thick_polylines_out) override
bool	no_sort () const override
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

~FillSpiralInset()

Slic3r::FillSpiralInset::~FillSpiralInset ( )

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]

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

overrideprotectedvirtual

Reimplemented from Slic3r::Fill.

{
    BoundingBox bounding_box = expolygon.contour.bounding_box();
 
    coord_t min_spacing = scale_(this->spacing);
    coord_t distance    = coord_t(min_spacing / params.density);
 
    if (params.density > 0.9999f && !params.dont_adjust) {
        distance      = this->_adjust_solid_spacing(bounding_box.size()(0), distance);
        this->spacing = unscale<double>(distance);
    }
 
    Polygons loops = to_polygons(expolygon);
 
    ExPolygons last{std::move(expolygon)};
    while (!last.empty()) {
        last = offset2_ex(last, -(distance + min_spacing / 2), +min_spacing / 2);
        append(loops, to_polygons(last));
    }
 
    // Orders the loops outside in, depth first, which is the order the chaining below expects.
    loops = union_pt_chained_outside_in(loops);
 
    std::vector<const Polygon*> loop_refs;
    loop_refs.reserve(loops.size());
    for (const Polygon& loop : loops)
        loop_refs.emplace_back(&loop);
 
    Polylines spiral_result = generate_spiral_insets<Polygon, Polyline>(params, loop_refs, loops, distance, expolygon);
 
    append(polylines_out, spiral_result);
}

References Slic3r::Fill::_adjust_solid_spacing(), Slic3r::append(), Slic3r::Fill::bounding_box, Slic3r::MultiPoint::bounding_box(), Slic3r::ExPolygon::contour, Slic3r::FillParams::density, Slic3r::FillParams::dont_adjust, Slic3r::generate_spiral_insets(), Slic3r::offset2_ex(), scale_, Slic3r::BoundingBoxBase< PointType, APointsType >::size(), Slic3r::Fill::spacing, Slic3r::to_polygons(), Slic3r::union_pt_chained_outside_in(), and Slic3r::unscale().

Referenced by _fill_surface_single().

Here is the call graph for this function:

Here is the caller graph for this function:

_fill_surface_single() [2/2]

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

overrideprotectedvirtual

Reimplemented from Slic3r::Fill.

{
    assert(params.use_arachne);
    assert(this->print_config != nullptr && this->print_object_config != nullptr);
 
    // Internal solid infill must not add Arachne's standalone thin walls: one of those walls can
    // become the extra centre point after the spiral has finished. Top and bottom surfaces keep
    // Arachne, including the centre plug handled by generate_spiral_insets().
    if (params.extrusion_role == erSolidInfill) {
        Polylines polylines;
        this->_fill_surface_single(params, thickness_layers, direction, expolygon, polylines);
        append(thick_polylines_out, to_thick_polylines(std::move(polylines), scaled<coord_t>(this->spacing)));
        return;
    }
 
    // Only a solid surface is worth the variable width walls; a sparse one falls back to plain loops.
    if (params.density <= 0.9999f || params.dont_adjust) {
        Polylines polylines;
        this->_fill_surface_single(params, thickness_layers, direction, expolygon, polylines);
        append(thick_polylines_out, to_thick_polylines(std::move(polylines), scaled<coord_t>(this->spacing)));
        return;
    }
 
    // no rotation is supported for this infill pattern
    Point   bbox_size   = expolygon.contour.bounding_box().size();
    coord_t min_spacing = scaled<coord_t>(this->spacing);
 
    coord_t  loops_count = std::max(bbox_size.x(), bbox_size.y()) / min_spacing + 1;
    Polygons polygons    = offset(expolygon, float(min_spacing) / 2.f);
 
    double min_nozzle_diameter = *std::min_element(print_config->nozzle_diameter.values.begin(), print_config->nozzle_diameter.values.end());
    Arachne::WallToolPathsParams input_params;
    input_params.min_bead_width                = 0.85 * min_nozzle_diameter;
    input_params.min_feature_size              = 0.25 * min_nozzle_diameter;
    input_params.wall_transition_length        = 1.0 * min_nozzle_diameter;
    input_params.wall_transition_angle         = 10;
    input_params.wall_transition_filter_deviation = 0.25 * min_nozzle_diameter;
    input_params.wall_distribution_count       = 1;
 
    Arachne::WallToolPaths wallToolPaths(polygons, min_spacing, min_spacing, loops_count, 0, params.layer_height, input_params);
    std::vector<Arachne::VariableWidthLines> walls_by_inset = wallToolPaths.getToolPaths();
 
    // Open walls are the thin features Arachne fits between the closed ones. They cannot join a
    // spiral, so they go out as they are; leaving them behind is what would put the gaps back.
    std::vector<const Arachne::ExtrusionLine*> walls;
    Polygons                                   wall_outlines;
    ThickPolylines                             open_walls;
    for (const Arachne::VariableWidthLines& inset : walls_by_inset)
        for (const Arachne::ExtrusionLine& wall : inset) {
            if (wall.empty())
                continue;
            if (wall.is_closed) {
                walls.emplace_back(&wall);
                wall_outlines.emplace_back(wall.toPolygon());
            } else {
                open_walls.emplace_back(Arachne::to_thick_polyline(wall));
            }
        }
 
    // Arachne hands the walls back grouped by inset, which is not their nesting: around a hole the
    // wall of a given inset lies inside the wall of that same inset around the contour. Nest them by
    // containment instead, so the spiral follows one island all the way in before starting the next,
    // the same order union_pt_chained_outside_in gives the classic path above.
    const size_t      wall_count = walls.size();
    std::vector<int>  nesting_depth(wall_count, 0), parent(wall_count, -1);
    std::vector<char> inside(wall_count * wall_count, 0);
    for (size_t i = 0; i < wall_count; ++i)
        for (size_t j = 0; j < wall_count; ++j)
            if (i != j && wall_outlines[j].contains(walls[i]->junctions.front().p)) {
                inside[i * wall_count + j] = 1;
                ++nesting_depth[i];
            }
    // The innermost of the walls containing this one, which is the deepest of them, is its parent.
    for (size_t i = 0; i < wall_count; ++i)
        for (size_t j = 0; j < wall_count; ++j)
            if (inside[i * wall_count + j] && (parent[i] < 0 || nesting_depth[parent[i]] < nesting_depth[j]))
                parent[i] = int(j);
 
    std::vector<const Arachne::ExtrusionLine*> ordered;
    Polygons                                   outlines;
    ordered.reserve(wall_count);
    outlines.reserve(wall_count);
    std::function<void(int)> descend = [&](int idx) {
        ordered.emplace_back(walls[idx]);
        outlines.emplace_back(wall_outlines[idx]);
        for (size_t k = 0; k < wall_count; ++k)
            if (parent[k] == idx)
                descend(int(k));
    };
    for (size_t i = 0; i < wall_count; ++i)
        if (parent[i] < 0)
            descend(int(i));
 
    ThickPolylines spiral_result =
        generate_spiral_insets<Arachne::ExtrusionLine, ThickPolyline>(params, ordered, outlines, min_spacing, expolygon);
 
    append(thick_polylines_out, std::move(spiral_result));
    append(thick_polylines_out, std::move(open_walls));
}

References _fill_surface_single(), Slic3r::append(), Slic3r::MultiPoint::bounding_box(), Slic3r::Geometry::contains(), Slic3r::ExPolygon::contour, Slic3r::FillParams::density, Slic3r::FillParams::dont_adjust, Slic3r::erSolidInfill, Slic3r::FillParams::extrusion_role, Slic3r::generate_spiral_insets(), Slic3r::Arachne::WallToolPaths::getToolPaths(), Slic3r::FillParams::layer_height, Slic3r::Arachne::WallToolPathsParams::min_bead_width, Slic3r::Arachne::WallToolPathsParams::min_feature_size, Slic3r::offset(), Slic3r::Fill::print_config, Slic3r::Fill::print_object_config, Slic3r::scaled(), Slic3r::BoundingBoxBase< PointType, APointsType >::size(), Slic3r::Fill::spacing, Slic3r::Arachne::to_thick_polyline(), Slic3r::to_thick_polylines(), Slic3r::FillParams::use_arachne, Slic3r::Arachne::WallToolPathsParams::wall_distribution_count, Slic3r::Arachne::WallToolPathsParams::wall_transition_angle, Slic3r::Arachne::WallToolPathsParams::wall_transition_filter_deviation, and Slic3r::Arachne::WallToolPathsParams::wall_transition_length.

Here is the call graph for this function:

_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::FillSpiralInset::clone ( ) const

inlineoverrideprotectedvirtual

Implements Slic3r::Fill.

{ return new FillSpiralInset(*this); };

References Slic3r::Fill::Fill().

Here is the call graph for this function:

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::Fill::fill_surface ( const Surface * surface, const FillParams & params )

virtualinherited

Reimplemented in Slic3r::FillCubic, Slic3r::FillGrid, Slic3r::FillLateralHoneycomb, Slic3r::FillLateralLattice, Slic3r::FillMonotonic, Slic3r::FillMonotonicLine, Slic3r::FillMonotonicLines, Slic3r::FillQuarterCubic, Slic3r::FillRectilinear, Slic3r::FillStars, Slic3r::FillSupportBase, and Slic3r::FillTriangles.

{
    // Perform offset.
    Slic3r::ExPolygons expp = offset_ex(surface->expolygon, float(scale_(this->overlap - 0.5 * this->spacing)));
    // Orca: Separated infills move the box center onto each body; origin-aligned patterns follow it.
    const Point shift = this->aligned_to_origin() && ! empty(this->bounding_box) ? this->bounding_box.center() : Point::Zero();
    translate(expp, -shift);
    // Create the infills for each of the regions.
    Polylines polylines_out;
    for (size_t i = 0; i < expp.size(); ++ i)
        _fill_surface_single(
            params,
            surface->thickness_layers,
            _infill_direction(surface),
            std::move(expp[i]),
            polylines_out);
    for (Polyline &pl : polylines_out)
        pl.translate(shift);
    return polylines_out;
}

References _fill_surface_single(), _infill_direction(), aligned_to_origin(), bounding_box, Slic3r::empty(), Slic3r::Surface::expolygon, Slic3r::offset_ex(), overlap, scale_, spacing, Slic3r::Surface::thickness_layers, and Slic3r::translate().

Referenced by Slic3r::fill_expolygon_generate_paths(), Slic3r::fill_expolygon_generate_paths(), and fill_surface_extrusion().

Here is the call graph for this function:

Here is the caller graph for this function:

fill_surface_arachne()

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

virtualinherited

{
    // 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_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:

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::FillSpiralInset::is_self_crossing ( )

inlineoverridevirtual

Implements Slic3r::Fill.

{ 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::FillSpiralInset::no_sort ( ) const

inlineoverrideprotectedvirtual

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/FillSpiralInset.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Fill/FillSpiralInset.cpp