Slic3r::Algorithm Namespace Reference

Classes
struct	SplitLineJunction
struct	RegionExpansionParameters
struct	WaveSeed
struct	RegionExpansion
struct	RegionExpansionEx

Typedefs
using	SplitNode = std::vector<ClipperZUtils::ZPath*>
using	SplittedLine = std::vector<SplitLineJunction>
using	AABBTreeBBoxes = AABBTreeIndirect::Tree<2, coord_t>
using	WaveSeeds = std::vector<WaveSeed>

Functions
static void	cb_split_line (const ClipperZUtils::ZPoint &e1bot, const ClipperZUtils::ZPoint &e1top, const ClipperZUtils::ZPoint &e2bot, const ClipperZUtils::ZPoint &e2top, ClipperZUtils::ZPoint &pt)
static bool	is_src (const ClipperZUtils::ZPoint &p)
static bool	is_clip (const ClipperZUtils::ZPoint &p)
static bool	is_new (const ClipperZUtils::ZPoint &p)
static size_t	to_src_idx (const ClipperZUtils::ZPoint &p)
static Point	to_point (const ClipperZUtils::ZPoint &p)
static bool	point_on_line (const Point &p, const Line &l)
SplittedLine	do_split_line (const ClipperZUtils::ZPath &path, const ExPolygons &clip, bool closed)
template<class PathType>
SplittedLine	split_line (const PathType &path, const ExPolygons &clip, bool closed)
double	clipper_round_offset_error (double offset, double arc_tolerance)
static ClipperZUtils::ZPaths	expolygons_to_zpaths_expanded_opened (const ExPolygons &src, const float expansion, coord_t &base_idx)
static void	merge_splits (ClipperZUtils::ZPaths &paths, std::vector< std::pair< ClipperZUtils::ZPoint, int > > &splits)
static AABBTreeBBoxes	build_aabb_tree_over_expolygons (const ExPolygons &expolygons)
static int	sample_in_expolygons (const AABBTreeBBoxes &aabb_tree, const ExPolygons &expolygons, const Point &sample)
std::vector< WaveSeed >	wave_seeds (const ExPolygons &src, const ExPolygons &boundary, float tiny_expansion, bool sorted)
static Polygons	wavefront_initial (const VecOfPoints &polylines, float offset, double arc_tolerance)
static Polygons	wavefront_step (const Polygons &polygons, float offset, double arc_tolerance)
static Polygons	wavefront_clip (const Polygons &wavefront, const Polygons &clipping)
static Polygons	propagate_wave_from_boundary (const VecOfPoints &seed, const ExPolygon &boundary, const float initial_step, const float other_step, const size_t num_other_steps, const float max_inflation, const double arc_tolerance)
std::vector< RegionExpansion >	propagate_waves (const WaveSeeds &seeds, const ExPolygons &boundary, const RegionExpansionParameters &params)
std::vector< RegionExpansion >	propagate_waves (const ExPolygons &src, const ExPolygons &boundary, const RegionExpansionParameters &params)
std::vector< RegionExpansion >	propagate_waves (const ExPolygons &src, const ExPolygons &boundary, float expansion, float expansion_step, size_t max_nr_steps)
std::vector< RegionExpansionEx >	propagate_waves_ex (const WaveSeeds &seeds, const ExPolygons &boundary, const RegionExpansionParameters &params)
std::vector< RegionExpansionEx >	propagate_waves_ex (const ExPolygons &src, const ExPolygons &boundary, float full_expansion, float expansion_step, size_t max_nr_expansion_steps)
std::vector< Polygons >	expand_expolygons (const ExPolygons &src, const ExPolygons &boundary, float expansion, float expansion_step, size_t max_nr_steps)
std::vector< ExPolygon >	merge_expansions_into_expolygons (ExPolygons &&src, std::vector< RegionExpansion > &&expanded)
std::vector< ExPolygon >	expand_merge_expolygons (ExPolygons &&src, const ExPolygons &boundary, const RegionExpansionParameters &params)
bool	lower_by_boundary_and_src (const WaveSeed &l, const WaveSeed &r)
bool	lower_by_src_and_boundary (const WaveSeed &l, const WaveSeed &r)

Variables
static constexpr auto	CLIP_IDX = std::numeric_limits<coord_t>::max()

---

Class Documentation

Slic3r::Algorithm::WaveSeed

struct Slic3r::Algorithm::WaveSeed

Collaboration diagram for Slic3r::Algorithm::WaveSeed:

Class Members
uint32_t	boundary
Points	path
uint32_t	src

Slic3r::Algorithm::RegionExpansion

struct Slic3r::Algorithm::RegionExpansion

Collaboration diagram for Slic3r::Algorithm::RegionExpansion:

Class Members
uint32_t	boundary_id
Polygon	polygon
uint32_t	src_id

Slic3r::Algorithm::RegionExpansionEx

struct Slic3r::Algorithm::RegionExpansionEx

Collaboration diagram for Slic3r::Algorithm::RegionExpansionEx:

Class Members
uint32_t	boundary_id
ExPolygon	expolygon
uint32_t	src_id

Typedef Documentation

AABBTreeBBoxes

using Slic3r::Algorithm::AABBTreeBBoxes = AABBTreeIndirect::Tree<2, coord_t>

SplitNode

using Slic3r::Algorithm::SplitNode = std::vector<ClipperZUtils::ZPath*>

SplittedLine

using Slic3r::Algorithm::SplittedLine = std::vector<SplitLineJunction>

WaveSeeds

using Slic3r::Algorithm::WaveSeeds = std::vector<WaveSeed>

Function Documentation

build_aabb_tree_over_expolygons()

AABBTreeBBoxes Slic3r::Algorithm::build_aabb_tree_over_expolygons ( const ExPolygons & expolygons )

static

{
    // Calculate bounding boxes of internal slices.
    std::vector<AABBTreeIndirect::BoundingBoxWrapper> bboxes;
    bboxes.reserve(expolygons.size());
    for (size_t i = 0; i < expolygons.size(); ++ i)
        bboxes.emplace_back(i, get_extents(expolygons[i].contour));
    // Build AABB tree over bounding boxes of boundary expolygons.
    AABBTreeBBoxes out;
    out.build_modify_input(bboxes);
    return out;
}

References Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::build_modify_input(), Slic3r::contour(), and Slic3r::get_extents().

Referenced by merge_expansions_into_expolygons(), and wave_seeds().

Here is the call graph for this function:

Here is the caller graph for this function:

cb_split_line()

void Slic3r::Algorithm::cb_split_line ( const ClipperZUtils::ZPoint & e1bot, const ClipperZUtils::ZPoint & e1top, const ClipperZUtils::ZPoint & e2bot, const ClipperZUtils::ZPoint & e2top, ClipperZUtils::ZPoint & pt )

static

{
    coord_t zs[4]{e1bot.z(), e1top.z(), e2bot.z(), e2top.z()};
    std::sort(zs, zs + 4);
    pt.z() = -(zs[0] + 1);
}

Referenced by do_split_line().

Here is the caller graph for this function:

clipper_round_offset_error()

double Slic3r::Algorithm::clipper_round_offset_error ( double offset, double arc_tolerance )

inline

{
    static constexpr const double def_arc_tolerance = 0.25;
    const double y =
        arc_tolerance <= 0 ?
            def_arc_tolerance :
            arc_tolerance > offset * def_arc_tolerance ?
                offset * def_arc_tolerance :
                arc_tolerance;
    double steps = std::min(M_PI / std::acos(1. - y / offset), offset * M_PI);
    return offset * (1. - cos(M_PI / steps));
}

References M_PI, and Slic3r::offset().

Here is the call graph for this function:

do_split_line()

SplittedLine Slic3r::Algorithm::do_split_line	(	const ClipperZUtils::ZPath &	path,
		const ExPolygons &	clip,
		bool	closed )

{
    assert(path.size() > 1);
#ifdef DEBUG_SPLIT_LINE
    const auto  dbg_path_points = ClipperZUtils::from_zpath<false>(path);
    BoundingBox dbg_bbox = get_extents(clip);
    dbg_bbox.merge(get_extents(dbg_path_points));
    dbg_bbox.offset(scale_(1.));
    const std::uint32_t dbg_id = g_dbg_id++;
    {
        ::Slic3r::SVG svg(debug_out_path("do_split_line_%d_input.svg", dbg_id).c_str(), dbg_bbox);
        svg.draw(clip, "red", 0.5);
        svg.draw_outline(clip, "red");
        svg.draw(Polyline{dbg_path_points});
        svg.draw(dbg_path_points);
        svg.Close();
    }
#endif
 
    ClipperZUtils::ZPaths intersections;
    // Perform an intersection
    {
        // Convert clip polygon to closed contours
        ClipperZUtils::ZPaths clip_path;
        for (const auto& exp : clip) {
            clip_path.emplace_back(ClipperZUtils::to_zpath<false>(exp.contour.points, CLIP_IDX));
            for (const Polygon& hole : exp.holes)
                clip_path.emplace_back(ClipperZUtils::to_zpath<false>(hole.points, CLIP_IDX));
        }
 
        intersections = ClipperZUtils::clip_zpaths(ctIntersection, ClipperZUtils::ZPaths{ path }, true, clip_path, cb_split_line, true);
    }
    if (intersections.empty()) {
        return {};
    }
 
#ifdef DEBUG_SPLIT_LINE
    {
        int i = 0;
        for (const auto& segment : intersections) {
            ::Slic3r::SVG svg(debug_out_path("do_split_line_%d_seg_%d.svg", dbg_id, i).c_str(), dbg_bbox);
            svg.draw(clip, "red", 0.5);
            svg.draw_outline(clip, "red");
            const auto segment_points = ClipperZUtils::from_zpath<false>(segment);
            svg.draw(Polyline{segment_points});
            for (const ClipperZUtils::ZPoint& p : segment) {
                const auto z = p.z();
                if (is_new(p)) {
                    svg.draw(to_point(p), "yellow");
                } else if (is_clip(p)) {
                    svg.draw(to_point(p), "red");
                } else {
                    svg.draw(to_point(p), "black");
                }
            }
            svg.Close();
            i++;
        }
    }
#endif
 
    // Connect the intersection back to the remaining loop
    std::vector<SplitNode> split_chain;
    {
        // AABBTree over source paths.
        // Only built if necessary, that is if any of the clipped segment has first point came from clip polygon,
        // and we need to find out which source edge that point came from.
        AABBTreeLines::LinesDistancer<Line> aabb_tree;
        const auto                          resolve_clip_point = [&path, &aabb_tree](ClipperZUtils::ZPoint& zp) {
            if (!is_clip(zp)) {
                return;
            }
 
            if (aabb_tree.get_lines().empty()) {
                Lines lines;
                lines.reserve(path.size() - 1);
                for (auto it = path.begin() + 1; it != path.end(); ++it) {
                    lines.emplace_back(to_point(it[-1]), to_point(*it));
                }
                aabb_tree = AABBTreeLines::LinesDistancer(lines);
            }
 
            const Point p = to_point(zp);
            const auto possible_edges = aabb_tree.all_lines_in_radius(p, SCALED_EPSILON);
            assert(!possible_edges.empty());
            for (const size_t l : possible_edges) {
                // Check if the point is on the line
                const Line line(to_point(path[l]), to_point(path[l + 1]));
                if (p == line.a) {
                    zp.z() = path[l].z();
                    break;
                }
                if (p == line.b) {
                    zp.z() = path[l + 1].z();
                    break;
                }
                if (point_on_line(p, line)) {
                    zp.z() = -(path[l].z() + 1);
                    break;
                }
            }
            if (is_clip(zp)) {
                // Too bad! Couldn't find the src edge, so we just pick the first one and hope it works
                zp.z() = -(path[possible_edges[0]].z() + 1);
            }
        };
 
        split_chain.assign(path.size(), {});
        for (ClipperZUtils::ZPath& segment : intersections) {
            assert(segment.size() >= 2);
            // Resolve all clip points
            std::for_each(segment.begin(), segment.end(), resolve_clip_point);
 
            // Ensure the point order in segment
            std::sort(segment.begin(), segment.end(), [&path](const ClipperZUtils::ZPoint& a, const ClipperZUtils::ZPoint& b) -> bool {
                if (is_new(a) && is_new(b) && a.z() == b.z()) {
                    // Make sure a point is closer to the src point than b
                    const auto src = to_point(path[-a.z() - 1]);
                    return (to_point(a) - src).squaredNorm() < (to_point(b) - src).squaredNorm();
                }
                const auto a_idx = to_src_idx(a);
                const auto b_idx = to_src_idx(b);
                if (a_idx == b_idx) {
                    // On same line, prefer the src point first
                    return is_src(a);
                } else {
                    return a_idx < b_idx;
                }
            });
 
            // Chain segment back to the original path
            ClipperZUtils::ZPoint& front = segment.front();
            const ClipperZUtils::ZPoint* previous_src_point = nullptr;
            if (is_src(front)) {
                // The segment starts with a point from src path, which means apart from the last point,
                // all other points on this segment should come from the src path or the clip polygon
 
                // Connect the segment to the src path
                auto& node = split_chain[front.z()];
                node.insert(node.begin(), &segment);
 
                previous_src_point = &front;
            } else if (is_new(front)) {
                const auto id = -front.z() - 1; // Get the src path index
                const ClipperZUtils::ZPoint& src_p = path[id]; // Get the corresponding src point
                const auto dist2 = (front - src_p).block<2, 1>(0,0).squaredNorm(); // Distance between the src point and current point
                // Find the place on the src line that current point should lie on
                auto& node = split_chain[id];
                auto it = std::find_if(node.begin(), node.end(), [dist2, &src_p](const ClipperZUtils::ZPath* p) {
                    const ClipperZUtils::ZPoint& p_front = p->front();
                    if (is_src(p_front)) {
                        return false;
                    }
 
                    const auto dist2_2 = (p_front - src_p).block<2, 1>(0, 0).squaredNorm();
                    return dist2_2 > dist2;
                });
                // Insert this split
                node.insert(it, &segment);
 
                previous_src_point = &src_p;
            } else {
                assert(false);
            }
 
            // Once we figured out the start point, we can then normalize the remaining points on the segment
            for (ClipperZUtils::ZPoint& p : segment) {
                assert(!is_new(p) || p == front || p == segment.back()); // Only the first and last point can be a new intersection
                if (is_src(p)) {
                    previous_src_point = &p;
                } else if (is_clip(p)) {
                    // Treat point from clip polygon as new point
                    p.z() = -(previous_src_point->z() + 1);
                }
            }
        }
    }
 
    // Now we reconstruct the final path by connecting splits
    SplittedLine result;
    size_t       idx  = 0;
    while (idx < split_chain.size()) {
        const ClipperZUtils::ZPoint& p = path[idx];
        const auto& node = split_chain[idx];
        if (node.empty()) {
            result.emplace_back(to_point(p), false, idx);
            idx++;
        } else {
            if (!is_src(node.front()->front())) {
                if (result.empty() || result.back().get_src_index() != to_src_idx(p)) {
                //const auto& last = result.back();
                //if (result.empty() || last.get_src_index() != to_src_idx(p)) {
                    result.emplace_back(to_point(p), false, idx);
                }
            }
            for (const auto segment : node) {
                for (const ClipperZUtils::ZPoint& sp : *segment) {
                    assert(!is_clip(sp));
                    result.emplace_back(to_point(sp), true, sp.z());
                }
                result.back().clipped = false; // Mark the end of the clipped line
            }
 
            // Determine the next start point
            const auto back = result.back().src_idx;
            if (back < 0) {
                auto next_idx = -back - 1;
                if (next_idx == idx) {
                    next_idx++;
                } else if (split_chain[next_idx].empty()) {
                    next_idx++;
                }
                idx = next_idx;
            } else {
                result.pop_back();
                idx = back;
            }
        }
    }
 
    
#ifdef DEBUG_SPLIT_LINE
    {
        ::Slic3r::SVG svg(debug_out_path("do_split_line_%d_result.svg", dbg_id).c_str(), dbg_bbox);
        svg.draw(clip, "red", 0.5);
        svg.draw_outline(clip, "red");
        for (auto it = result.begin() + 1; it != result.end(); ++it) {
            const auto& a = *(it - 1);
            const auto& b = *it;
            const bool  clipped = a.clipped;
            const Line  l(a.p, b.p);
            svg.draw(l, clipped ? "yellow" : "black");
        }
        svg.Close();
    }
#endif
 
    if (closed) {
        // Remove last point which was duplicated
        result.pop_back();
    }
 
    return result;
}

References Slic3r::Line::a, Slic3r::AABBTreeLines::LinesDistancer< LineType >::all_lines_in_radius(), Slic3r::Line::b, cb_split_line(), CLIP_IDX, Slic3r::ClipperZUtils::clip_zpaths(), Slic3r::SVG::Close(), Slic3r::ctIntersection, Slic3r::debug_out_path(), Slic3r::SVG::draw(), Slic3r::SVG::draw_outline(), Slic3r::ClipperZUtils::from_zpath(), Slic3r::get_extents(), Slic3r::AABBTreeLines::LinesDistancer< LineType >::get_lines(), is_clip(), is_new(), is_src(), Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::BoundingBoxBase< PointType, APointsType >::offset(), point_on_line(), Slic3r::MultiPoint::points, scale_, SCALED_EPSILON, to_point(), to_src_idx(), and Slic3r::ClipperZUtils::to_zpath().

Referenced by split_line().

Here is the call graph for this function:

Here is the caller graph for this function:

expand_expolygons()

std::vector< Polygons > Slic3r::Algorithm::expand_expolygons	(	const ExPolygons &	src,
		const ExPolygons &	boundary,
		float	expansion,
		float	expansion_step,
		size_t	max_nr_steps )

{
    std::vector<Polygons> out(src.size(), Polygons{});
    for (RegionExpansion &r : propagate_waves(src, boundary, expansion, expansion_step, max_nr_steps))
        out[r.src_id].emplace_back(std::move(r.polygon));
    return out;
}

References propagate_waves().

Here is the call graph for this function:

expand_merge_expolygons()

std::vector< ExPolygon > Slic3r::Algorithm::expand_merge_expolygons	(	ExPolygons &&	src,
		const ExPolygons &	boundary,
		const RegionExpansionParameters &	params )

{
    // expanded regions are sorted by boundary id and source id
    std::vector<RegionExpansion> expanded = propagate_waves(src, boundary, params);
    return merge_expansions_into_expolygons(std::move(src), std::move(expanded));
}

References merge_expansions_into_expolygons(), and propagate_waves().

Here is the call graph for this function:

expolygons_to_zpaths_expanded_opened()

ClipperZUtils::ZPaths Slic3r::Algorithm::expolygons_to_zpaths_expanded_opened ( const ExPolygons & src, const float expansion, coord_t & base_idx )

static

{
    ClipperZUtils::ZPaths out;
    out.reserve(2 * std::accumulate(src.begin(), src.end(), size_t(0),
        [](const size_t acc, const ExPolygon &expoly) { return acc + expoly.num_contours(); }));
    for (const ExPolygon &expoly : src) {
        for (size_t icontour = 0; icontour < expoly.num_contours(); ++ icontour) {
            // Orient CCW, then grow the contour and shrink the holes. The output contours are CCW.
            Polygon contour = expoly.contour_or_hole(icontour);
            if (! contour.is_counter_clockwise())
                contour.reverse();
            for (const Polygon &expanded : offset(contour, icontour == 0 ? expansion : -expansion, jtSquare))
                out.emplace_back(ClipperZUtils::to_zpath<true>(expanded.points, base_idx));
        }
        ++ base_idx;
    }
    return out;
}

References Slic3r::contour(), Slic3r::ExPolygon::contour_or_hole(), Slic3r::jtSquare, Slic3r::ExPolygon::num_contours(), Slic3r::offset(), and Slic3r::ClipperZUtils::to_zpath().

Referenced by wave_seeds().

Here is the call graph for this function:

Here is the caller graph for this function:

is_clip()

bool Slic3r::Algorithm::is_clip ( const ClipperZUtils::ZPoint & p )

static

{ return p.z() == CLIP_IDX; }

References CLIP_IDX.

Referenced by do_split_line(), and to_src_idx().

Here is the caller graph for this function:

is_new()

bool Slic3r::Algorithm::is_new ( const ClipperZUtils::ZPoint & p )

static

{ return p.z() < 0; }

Referenced by do_split_line().

Here is the caller graph for this function:

is_src()

bool Slic3r::Algorithm::is_src ( const ClipperZUtils::ZPoint & p )

static

{ return p.z() >= 0 && p.z() != CLIP_IDX; }

References CLIP_IDX.

Referenced by do_split_line(), and to_src_idx().

Here is the caller graph for this function:

lower_by_boundary_and_src()

bool Slic3r::Algorithm::lower_by_boundary_and_src ( const WaveSeed & l, const WaveSeed & r )

inline

{
    return l.boundary < r.boundary || (l.boundary == r.boundary && l.src < r.src);
}

References Slic3r::Algorithm::WaveSeed::boundary, and Slic3r::Algorithm::WaveSeed::src.

Referenced by wave_seeds().

Here is the caller graph for this function:

lower_by_src_and_boundary()

bool Slic3r::Algorithm::lower_by_src_and_boundary ( const WaveSeed & l, const WaveSeed & r )

inline

{
    return l.src < r.src || (l.src == r.src && l.boundary < r.boundary);
}

References Slic3r::Algorithm::WaveSeed::boundary, and Slic3r::Algorithm::WaveSeed::src.

Referenced by Slic3r::expand_bridges_detect_orientations().

Here is the caller graph for this function:

merge_expansions_into_expolygons()

std::vector< ExPolygon > Slic3r::Algorithm::merge_expansions_into_expolygons	(	ExPolygons &&	src,
		std::vector< RegionExpansion > &&	expanded )

{
    // expanded regions will be merged into source regions, thus they will be re-sorted by source id.
    std::sort(expanded.begin(), expanded.end(), [](const auto &l, const auto &r) { return l.src_id < r.src_id; });
    uint32_t   last = 0;
    Polygons   acc;
    ExPolygons out;
    out.reserve(src.size());
    for (auto it = expanded.begin(); it != expanded.end();) {
        for (; last < it->src_id; ++ last)
            out.emplace_back(std::move(src[last]));
        acc.clear();
        assert(it->src_id == last);
        for (; it != expanded.end() && it->src_id == last; ++ it)
            acc.emplace_back(std::move(it->polygon));
        //FIXME offset & merging could be more efficient, for example one does not need to copy the source expolygon
        ExPolygon &src_ex = src[last ++];
        assert(! src_ex.contour.empty());
#if 0
        {
            static int iRun = 0;
            BoundingBox bbox = get_extents(acc);
            bbox.merge(get_extents(src_ex));
            SVG svg(debug_out_path("expand_merge_expolygons-failed-union=%d.svg", iRun ++).c_str(), bbox);
            svg.draw(acc);
            svg.draw_outline(acc, "black", scale_(0.05));
            svg.draw(src_ex, "red");
            svg.Close();
        }
#endif
        Point sample = src_ex.contour.front();
        append(acc, to_polygons(std::move(src_ex)));
        ExPolygons merged = union_safety_offset_ex(acc);
        // Expanding one expolygon by waves should not change connectivity of the source expolygon:
        // Single expolygon should be produced possibly with increased number of holes.
        if (merged.size() > 1) {
            // assert(merged.size() == 1);
            // There is something wrong with the initial waves. Most likely the bridge was not valid at all
            // or the boundary region was very close to some bridge edge, but not really touching.
            // Pick only a single merged expolygon, which contains one sample point of the source expolygon.
            auto aabb_tree = build_aabb_tree_over_expolygons(merged);
            int id = sample_in_expolygons(aabb_tree, merged, sample);
            assert(id != -1);
            if (id != -1)
                out.emplace_back(std::move(merged[id]));
        } else if (merged.size() == 1)
            out.emplace_back(std::move(merged.front()));
    }
    for (; last < uint32_t(src.size()); ++ last)
        out.emplace_back(std::move(src[last]));
    return out;
}

References Slic3r::append(), build_aabb_tree_over_expolygons(), Slic3r::SVG::Close(), Slic3r::ExPolygon::contour, Slic3r::debug_out_path(), Slic3r::SVG::draw(), Slic3r::SVG::draw_outline(), Slic3r::MultiPoint::empty(), Slic3r::MultiPoint::front(), Slic3r::get_extents(), Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), sample_in_expolygons(), scale_, Slic3r::to_polygons(), and Slic3r::union_safety_offset_ex().

Referenced by expand_merge_expolygons(), and Slic3r::expand_merge_surfaces().

Here is the call graph for this function:

Here is the caller graph for this function:

merge_splits()

void Slic3r::Algorithm::merge_splits ( ClipperZUtils::ZPaths & paths, std::vector< std::pair< ClipperZUtils::ZPoint, int > > & splits )

inlinestatic

{
    for (auto it_path = paths.begin(); it_path != paths.end(); ) {
        ClipperZUtils::ZPath &path = *it_path;
        assert(path.size() >= 2);
        bool merged = false;
        if (path.size() >= 2) {
            const ClipperZUtils::ZPoint &front = path.front();
            const ClipperZUtils::ZPoint &back  = path.back();
            // The path before clipping was supposed to cross the clipping boundary or be fully out of it.
            // Thus the clipped contour is supposed to become open, with one exception: The anchor expands into a closed hole.
            if (front.x() != back.x() || front.y() != back.y()) {
                // Look up the ends in "splits", possibly join the contours.
                // "splits" maps into the other piece connected to the same end point.
                auto find_end = [&splits](const ClipperZUtils::ZPoint &pt) -> std::pair<ClipperZUtils::ZPoint, int>* {
                    auto it = std::lower_bound(splits.begin(), splits.end(), pt,
                        [](const auto &l, const auto &r){ return ClipperZUtils::zpoint_lower(l.first, r); });
                    return it != splits.end() && it->first == pt ? &(*it) : nullptr;
                };
                auto *end = find_end(front);
                bool  end_front = true;
                if (! end) {
                    end_front = false;
                    end = find_end(back);
                }
                if (end) {
                    // This segment ends at a split point of the source closed contour before clipping.
                    if (end->second == -1) {
                        // Open end was found, not matched yet.
                        end->second = int(it_path - paths.begin());
                    } else {
                        // Open end was found and matched with end->second
                        ClipperZUtils::ZPath &other_path = paths[end->second];
                        polylines_merge(other_path, other_path.front() == end->first, std::move(path), end_front);
                        if (std::next(it_path) == paths.end()) {
                            paths.pop_back();
                            break;
                        }
                        path = std::move(paths.back());
                        paths.pop_back();
                        merged = true;
                    }
                }
            }
        }
        if (! merged)
            ++ it_path;
    }
}

References Slic3r::polylines_merge().

Referenced by wave_seeds().

Here is the call graph for this function:

Here is the caller graph for this function:

point_on_line()

bool Slic3r::Algorithm::point_on_line ( const Point & p, const Line & l )

static

{
    // Check collinear
    const Vec2crd d1 = l.b - l.a;
    const Vec2crd d2 = p - l.a;
    if (d1.x() * d2.y() != d1.y() * d2.x()) { 
        return false;
    }
 
    // Make sure p is in between line.a and line.b
    if (l.a.x() != l.b.x())
        return (p.x() > l.a.x()) == (p.x() < l.b.x());
    else
        return (p.y() > l.a.y()) == (p.y() < l.b.y());
}

References Slic3r::Line::a, and Slic3r::Line::b.

Referenced by do_split_line().

Here is the caller graph for this function:

propagate_wave_from_boundary()

Polygons Slic3r::Algorithm::propagate_wave_from_boundary ( const VecOfPoints & seed, const ExPolygon & boundary, const float initial_step, const float other_step, const size_t num_other_steps, const float max_inflation, const double arc_tolerance )

static

{
    assert(! seed.empty() && seed.front().size() >= 2);
    Polygons clipping = ClipperUtils::clip_clipper_polygons_with_subject_bbox(boundary, get_extents<true>(seed).inflated(max_inflation));
    Polygons polygons = wavefront_clip(wavefront_initial(seed, initial_step, arc_tolerance), clipping);
    // Now offset the remaining 
    for (size_t ioffset = 0; ioffset < num_other_steps; ++ ioffset)
        polygons = wavefront_clip(wavefront_step(polygons, other_step, arc_tolerance), clipping);
    return polygons;
}

References Slic3r::ClipperUtils::clip_clipper_polygons_with_subject_bbox(), Slic3r::get_extents(), wavefront_clip(), wavefront_initial(), and wavefront_step().

Referenced by propagate_waves().

Here is the call graph for this function:

Here is the caller graph for this function:

propagate_waves() [1/3]

std::vector< RegionExpansion > Slic3r::Algorithm::propagate_waves	(	const ExPolygons &	src,
		const ExPolygons &	boundary,
		const RegionExpansionParameters &	params )

{
    return propagate_waves(wave_seeds(src, boundary, params.tiny_expansion, true), boundary, params);
}

References propagate_waves(), Slic3r::Algorithm::RegionExpansionParameters::tiny_expansion, and wave_seeds().

Here is the call graph for this function:

propagate_waves() [2/3]

std::vector< RegionExpansion > Slic3r::Algorithm::propagate_waves	(	const ExPolygons &	src,
		const ExPolygons &	boundary,
		float	expansion,
		float	expansion_step,
		size_t	max_nr_steps )

{
    return propagate_waves(src, boundary, RegionExpansionParameters::build(expansion, expansion_step, max_nr_steps));
}

References Slic3r::Algorithm::RegionExpansionParameters::build(), and propagate_waves().

Here is the call graph for this function:

propagate_waves() [3/3]

std::vector< RegionExpansion > Slic3r::Algorithm::propagate_waves	(	const WaveSeeds &	seeds,
		const ExPolygons &	boundary,
		const RegionExpansionParameters &	params )

{
    std::vector<RegionExpansion> out;
    VecOfPoints                  paths;
    for (auto it_seed = seeds.begin(); it_seed != seeds.end();) {
        auto it = it_seed;
        paths.clear();
        for (; it != seeds.end() && it->boundary == it_seed->boundary && it->src == it_seed->src; ++ it)
            paths.emplace_back(it->path);
        // Propagate the wavefront while clipping it with the trimmed boundary.
        // Collect the expanded polygons, merge them with the source polygons.
        RegionExpansion re;
        for (Polygon &polygon : propagate_wave_from_boundary(paths, boundary[it_seed->boundary], params.initial_step, params.other_step, params.num_other_steps, params.max_inflation, params.arc_tolerance))
            out.push_back({ std::move(polygon), it_seed->src, it_seed->boundary });
        it_seed = it;
    }
 
    return out;
}

References Slic3r::Algorithm::RegionExpansionParameters::arc_tolerance, Slic3r::Algorithm::RegionExpansionParameters::initial_step, Slic3r::Algorithm::RegionExpansionParameters::max_inflation, Slic3r::Algorithm::RegionExpansionParameters::num_other_steps, Slic3r::Algorithm::RegionExpansionParameters::other_step, and propagate_wave_from_boundary().

Referenced by expand_expolygons(), expand_merge_expolygons(), Slic3r::expand_merge_surfaces(), propagate_waves(), propagate_waves(), and propagate_waves_ex().

Here is the call graph for this function:

Here is the caller graph for this function:

propagate_waves_ex() [1/2]

std::vector< RegionExpansionEx > Slic3r::Algorithm::propagate_waves_ex	(	const ExPolygons &	src,
		const ExPolygons &	boundary,
		float	full_expansion,
		float	expansion_step,
		size_t	max_nr_expansion_steps )

{
    auto params = RegionExpansionParameters::build(full_expansion, expansion_step, max_nr_expansion_steps);
    return propagate_waves_ex(wave_seeds(src, boundary, params.tiny_expansion, true), boundary, params);
}

References Slic3r::Algorithm::RegionExpansionParameters::build(), propagate_waves_ex(), and wave_seeds().

Here is the call graph for this function:

propagate_waves_ex() [2/2]

std::vector< RegionExpansionEx > Slic3r::Algorithm::propagate_waves_ex	(	const WaveSeeds &	seeds,
		const ExPolygons &	boundary,
		const RegionExpansionParameters &	params )

{
    std::vector<RegionExpansion> expanded = propagate_waves(seeds, boundary, params);
    assert(std::is_sorted(seeds.begin(), seeds.end(), [](const auto &l, const auto &r){ return l.boundary < r.boundary || (l.boundary == r.boundary && l.src < r.src); }));
    Polygons acc;
    std::vector<RegionExpansionEx> out;
    for (auto it = expanded.begin(); it != expanded.end(); ) {
        auto it2 = it;
        acc.clear();
        for (; it2 != expanded.end() && it2->boundary_id == it->boundary_id && it2->src_id == it->src_id; ++ it2)
            acc.emplace_back(std::move(it2->polygon));
        size_t size = it2 - it;
        if (size == 1)
            out.push_back({ ExPolygon{std::move(acc.front())}, it->src_id, it->boundary_id });
        else {
            ExPolygons expolys = union_ex(acc);
            reserve_more_power_of_2(out, expolys.size());
            for (ExPolygon &ex : expolys)
                out.push_back({ std::move(ex), it->src_id, it->boundary_id });
        }
        it = it2;
    }
    return out;
}

References propagate_waves(), Slic3r::reserve_more_power_of_2(), and Slic3r::union_ex().

Referenced by propagate_waves_ex().

Here is the call graph for this function:

Here is the caller graph for this function:

sample_in_expolygons()

int Slic3r::Algorithm::sample_in_expolygons ( const AABBTreeBBoxes & aabb_tree, const ExPolygons & expolygons, const Point & sample )

static

{
    int out = -1;
    AABBTreeIndirect::traverse(aabb_tree,
        [&sample](const AABBTreeBBoxes::Node &node) {
            return node.bbox.contains(sample);
        },
        [&expolygons, &sample, &out](const AABBTreeBBoxes::Node &node) {
            assert(node.is_leaf());
            assert(node.is_valid());
            if (expolygons[node.idx].contains(sample)) {
                out = int(node.idx);
                // Stop traversal.
                return false;
            }
            // Continue traversal.
            return true;
        });
    return out;
}

References Slic3r::AABBTreeIndirect::traverse().

Referenced by merge_expansions_into_expolygons(), and wave_seeds().

Here is the call graph for this function:

Here is the caller graph for this function:

split_line()

template<class PathType>

SplittedLine Slic3r::Algorithm::split_line	(	const PathType &	path,
		const ExPolygons &	clip,
		bool	closed )

{
    if (path.empty()) {
        return {};
    }
 
    // Convert the input path into an open ZPath
    ClipperZUtils::ZPath p;
    p.reserve(path.size() + (closed ? 1 : 0));
    coord_t z = 0;
    for (const auto& point : path) {
        p.emplace_back(point.x(), point.y(), z);
        z++;
    }
    if (closed) {
        // duplicate the first point at the end to make a closed path open
        p.emplace_back(p.front());
        p.back().z() = z;
    }
 
    return do_split_line(p, clip, closed);
}

References do_split_line().

Referenced by Slic3r::Feature::FuzzySkin::apply_fuzzy_skin(), and Slic3r::Feature::FuzzySkin::apply_fuzzy_skin().

Here is the call graph for this function:

Here is the caller graph for this function:

to_point()

Point Slic3r::Algorithm::to_point ( const ClipperZUtils::ZPoint & p )

static

{ return {p.x(), p.y()}; }

Referenced by do_split_line().

Here is the caller graph for this function:

to_src_idx()

size_t Slic3r::Algorithm::to_src_idx ( const ClipperZUtils::ZPoint & p )

static

{
    assert(!is_clip(p));
    if (is_src(p)) {
        return p.z();
    } else {
        return -p.z() - 1;
    }
}

References is_clip(), and is_src().

Referenced by do_split_line().

Here is the call graph for this function:

Here is the caller graph for this function:

wave_seeds()

WaveSeeds Slic3r::Algorithm::wave_seeds	(	const ExPolygons &	src,
		const ExPolygons &	boundary,
		float	tiny_expansion,
		bool	sorted )

{
    assert(tiny_expansion > 0);
 
    if (src.empty() || boundary.empty())
        return {};
 
    using Intersection  = ClipperZUtils::ClipperZIntersectionVisitor::Intersection;
    using Intersections = ClipperZUtils::ClipperZIntersectionVisitor::Intersections;
 
    ClipperZUtils::ZPaths segments;
    Intersections         intersections;
 
    coord_t               idx_boundary_begin = 1;
    coord_t               idx_boundary_end   = idx_boundary_begin;
    coord_t               idx_src_end;
 
    {
        ClipperZUtils::ClipperZIntersectionVisitor visitor(intersections);
        // as closed contours
        ClipperZUtils::ZPaths zboundary = ClipperZUtils::expolygons_to_zpaths(boundary, idx_boundary_end);
        // as open contours
        std::vector<std::pair<ClipperZUtils::ZPoint, int>> zsrc_splits;
        idx_src_end = idx_boundary_end;
        ClipperZUtils::ZPaths zsrc = expolygons_to_zpaths_expanded_opened(src, tiny_expansion, idx_src_end);
        zsrc_splits.reserve(zsrc.size());
        for (const ClipperZUtils::ZPath &path : zsrc) {
            assert(path.size() >= 2);
            assert(path.front() == path.back());
            zsrc_splits.emplace_back(path.front(), -1);
        }
        std::sort(zsrc_splits.begin(), zsrc_splits.end(), [](const auto &l, const auto &r){ return ClipperZUtils::zpoint_lower(l.first, r.first); });
        segments = ClipperZUtils::clip_zpaths(ctIntersection, zsrc, true, zboundary, visitor.clipper_callback());
        merge_splits(segments, zsrc_splits);
    }
 
    // AABBTree over bounding boxes of boundaries.
    // Only built if necessary, that is if any of the seed contours is closed, thus there is no intersection point
    // with the boundary and all Z coordinates of the closed contour point to the source contour.
    AABBTreeBBoxes aabb_tree;
 
    // Sort paths into their respective islands.
    // Each src x boundary will be processed (wave expanded) independently.
    // Multiple pieces of a single src may intersect the same boundary.
    WaveSeeds out;
    out.reserve(segments.size());
    int iseed = 0;
    for (const ClipperZUtils::ZPath &path : segments) {
        assert(path.size() >= 2);
        ClipperZUtils::ZPoint front = path.front();
        ClipperZUtils::ZPoint back  = path.back();
        // Both ends of a seed segment are supposed to be inside a single boundary expolygon.
        // Thus as long as the seed contour is not closed, it should be open at a boundary point.
        assert((front == back && front.z() >= idx_boundary_end && front.z() < idx_src_end) || 
            //(front.z() < 0 && back.z() < 0));
            // Hope that at least one end of an open polyline is clipped by the boundary, thus an intersection point is created.
            (front.z() < 0 || back.z() < 0));
        // However, with complex geometry, both endpoints may coincide with existing polygon
        // vertices (z >= 0), which is handled below.
 
        if (front != back && front.z() >= 0 && back.z() >= 0) {
            // Very rare case when both endpoints intersect boundary ExPolygons in existing points.
            // So the ZFillFunction callback hasn't been called.
            // Both endpoints coincide with existing polygon vertices, so the
            // ZFillFunction callback was never called.  With complex geometry
            // this is common because source and boundary contours share many
            // vertices.  Determine src_id / boundary_id from Z coordinates
            // (and fall back to an AABB-tree point-in-polygon test when a
            // boundary ID is not directly available).
            coord_t src_z = -1, boundary_z = -1;
            // Scan all path points for the information we need.
            for (const ClipperZUtils::ZPoint &point : path) {
                if (point.z() >= idx_boundary_end && point.z() < idx_src_end && src_z < 0)
                    src_z = point.z();
                else if (point.z() >= idx_boundary_begin && point.z() < idx_boundary_end && boundary_z < 0)
                    boundary_z = point.z();
                if (src_z >= 0 && boundary_z >= 0)
                    break;
            }
            if (src_z >= 0) {
                uint32_t src_id = uint32_t(src_z - idx_boundary_end);
                if (boundary_z >= 0) {
                    out.push_back({ src_id, uint32_t(boundary_z - 1), ClipperZUtils::from_zpath(path) });
                } else {
                    // Source ID known but boundary unknown – use AABB tree.
                    if (aabb_tree.empty())
                        aabb_tree = build_aabb_tree_over_expolygons(boundary);
                    int boundary_id = sample_in_expolygons(aabb_tree, boundary, Point(front.x(), front.y()));
                    if (boundary_id >= 0)
                        out.push_back({ src_id, uint32_t(boundary_id), ClipperZUtils::from_zpath(path) });
                }
                ++ iseed;
                continue;
            }
            // Unable to determine source ID – drop the segment.
            continue;
        } else
        if (front == back && (front.z() < idx_boundary_end)) {
            // This should be a very rare exception.
            // See https://github.com/prusa3d/PrusaSlicer/issues/12469.
            // Segement is open, yet its first point seems to be part of boundary polygon.
            // Take the first point with src polygon index.
            for (const ClipperZUtils::ZPoint &point : path) {
                if (point.z() >= idx_boundary_end) {
                    front = point;
                    back = point;
                }
            }
        }
 
        const Intersection *intersection = nullptr;
        auto intersection_point_valid = [idx_boundary_end, idx_src_end](const Intersection &is) {
            return is.first >= 1 && is.first < idx_boundary_end &&
                   is.second >= idx_boundary_end && is.second < idx_src_end;
        };
        if (front.z() < 0) {
            const Intersection &is = intersections[- front.z() - 1];
            assert(intersection_point_valid(is));
            if (intersection_point_valid(is))
                intersection = &is;
        }
        if (! intersection && back.z() < 0) {
            const Intersection &is = intersections[- back.z() - 1];
            assert(intersection_point_valid(is));
            if (intersection_point_valid(is))
                intersection = &is;
        }
        if (intersection) {
            // The path intersects the boundary contour at least at one side. 
            out.push_back({ uint32_t(intersection->second - idx_boundary_end), uint32_t(intersection->first - 1), ClipperZUtils::from_zpath(path) });
        } else {
            // This should be a closed contour.
            assert(front == back && front.z() >= idx_boundary_end && front.z() < idx_src_end);
            // Find a source boundary expolygon of one sample of this closed path.
            if (aabb_tree.empty())
                aabb_tree = build_aabb_tree_over_expolygons(boundary);
            int boundary_id = sample_in_expolygons(aabb_tree, boundary, Point(front.x(), front.y()));
            // Boundary that contains the sample point was found.
            assert(boundary_id >= 0);
            if (boundary_id >= 0)
                out.push_back({ uint32_t(front.z() - idx_boundary_end), uint32_t(boundary_id), ClipperZUtils::from_zpath(path) });
        }
        ++ iseed;
    }
 
    if (sorted)
        // Sort the seeds by their intersection boundary and source contour.
        std::sort(out.begin(), out.end(), lower_by_boundary_and_src);
    return out;
}

References build_aabb_tree_over_expolygons(), Slic3r::ClipperZUtils::clip_zpaths(), Slic3r::ClipperZUtils::ClipperZIntersectionVisitor::clipper_callback(), Slic3r::ctIntersection, Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::empty(), Slic3r::ClipperZUtils::expolygons_to_zpaths(), expolygons_to_zpaths_expanded_opened(), Slic3r::ClipperZUtils::from_zpath(), Slic3r::intersection(), lower_by_boundary_and_src(), merge_splits(), and sample_in_expolygons().

Referenced by propagate_waves(), and propagate_waves_ex().

Here is the call graph for this function:

Here is the caller graph for this function:

wavefront_clip()

Polygons Slic3r::Algorithm::wavefront_clip ( const Polygons & wavefront, const Polygons & clipping )

static

{
    return intersection(wavefront, clipping, pftPositive);
}

References Slic3r::intersection(), and Slic3r::pftPositive.

Referenced by propagate_wave_from_boundary().

Here is the call graph for this function:

Here is the caller graph for this function:

wavefront_initial()

Polygons Slic3r::Algorithm::wavefront_initial ( const VecOfPoints & polylines, float offset, double arc_tolerance )

static

{
    Polygons out;
    out.reserve(polylines.size());
    for (const Points &path : polylines) {
        assert(path.size() >= 2);
        append(out, Slic3r::offset(Polyline(path), offset, jtRound, arc_tolerance, path.front() == path.back() ? etClosedLine : etOpenRound));
    }
    return out;
}

References Slic3r::append(), Slic3r::etClosedLine, Slic3r::etOpenRound, Slic3r::jtRound, and Slic3r::offset().

Referenced by propagate_wave_from_boundary().

Here is the call graph for this function:

Here is the caller graph for this function:

wavefront_step()

Polygons Slic3r::Algorithm::wavefront_step ( const Polygons & polygons, float offset, double arc_tolerance )

static

{
    Polygons out;
    out.reserve(polygons.size());
    for (const Polygon &polygon : polygons)
        // CCW contours grow, CW holes shrink.
        append(out, Slic3r::offset(polygon, offset, jtRound, arc_tolerance));
    return out;
}

References Slic3r::append(), Slic3r::jtRound, and Slic3r::offset().

Referenced by propagate_wave_from_boundary().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

CLIP_IDX

auto Slic3r::Algorithm::CLIP_IDX = std::numeric_limits<coord_t>::max()

staticconstexpr

Referenced by do_split_line(), is_clip(), and is_src().