Slic3r::ClipperUtils Namespace Reference

Classes
class	PathsProviderIteratorBase
class	EmptyPathsProvider
class	SinglePathProvider
class	PathsProvider
class	MultiPointsProvider
struct	ExPolygonProvider
struct	ExPolygonsProvider
struct	SurfacesProvider
struct	SurfacesPtrProvider
struct	ExPolygonsTile

Typedefs
using	PolygonsProvider = MultiPointsProvider<Polygons>
using	PolylinesProvider = MultiPointsProvider<Polylines>
using	ZPoint = Vec3i32
using	ZPoints = std::vector<Vec3i32>

Functions
template<typename PointsType>
void	clip_clipper_polygon_with_subject_bbox_templ (const PointsType &src, const BoundingBox &bbox, PointsType &out, const bool get_entire_polygons=false)
void	clip_clipper_polygon_with_subject_bbox (const Points &src, const BoundingBox &bbox, Points &out, const bool get_entire_polygons)
void	clip_clipper_polygon_with_subject_bbox (const ZPoints &src, const BoundingBox &bbox, ZPoints &out)
template<typename PointsType>
PointsType	clip_clipper_polygon_with_subject_bbox_templ (const PointsType &src, const BoundingBox &bbox)
Points	clip_clipper_polygon_with_subject_bbox (const Points &src, const BoundingBox &bbox)
ZPoints	clip_clipper_polygon_with_subject_bbox (const ZPoints &src, const BoundingBox &bbox)
void	clip_clipper_polygon_with_subject_bbox (const Polygon &src, const BoundingBox &bbox, Polygon &out)
Polygon	clip_clipper_polygon_with_subject_bbox (const Polygon &src, const BoundingBox &bbox, const bool get_entire_polygons)
Polygons	clip_clipper_polygons_with_subject_bbox (const Polygons &src, const BoundingBox &bbox)
Polygons	clip_clipper_polygons_with_subject_bbox (const ExPolygon &src, const BoundingBox &bbox, const bool get_entire_polygons)
Polygons	clip_clipper_polygons_with_subject_bbox (const ExPolygons &src, const BoundingBox &bbox, const bool get_entire_polygons)
std::vector< ExPolygonsTile >	tile_expolygons (const ExPolygons &expolygons, size_t per_tile)
std::optional< Point >	interior_point (const Polygon &polygon)

---

Class Documentation

Slic3r::ClipperUtils::ExPolygonsTile

struct Slic3r::ClipperUtils::ExPolygonsTile

Collaboration diagram for Slic3r::ClipperUtils::ExPolygonsTile:

Class Members
BoundingBox	bbox
vector< size_t >	members

Typedef Documentation

PolygonsProvider

using Slic3r::ClipperUtils::PolygonsProvider = MultiPointsProvider<Polygons>

PolylinesProvider

using Slic3r::ClipperUtils::PolylinesProvider = MultiPointsProvider<Polylines>

ZPoint

using Slic3r::ClipperUtils::ZPoint = Vec3i32

ZPoints

using Slic3r::ClipperUtils::ZPoints = std::vector<Vec3i32>

Function Documentation

clip_clipper_polygon_with_subject_bbox() [1/6]

Points Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox ( const Points & src, const BoundingBox & bbox )

nodiscard

{ return clip_clipper_polygon_with_subject_bbox_templ(src, bbox); }

References clip_clipper_polygon_with_subject_bbox_templ().

Here is the call graph for this function:

clip_clipper_polygon_with_subject_bbox() [2/6]

void Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox	(	const Points &	src,
		const BoundingBox &	bbox,
		Points &	out,
		const bool	get_entire_polygons )

{ clip_clipper_polygon_with_subject_bbox_templ(src, bbox, out, get_entire_polygons); }

References clip_clipper_polygon_with_subject_bbox_templ().

Referenced by clip_clipper_polygon_with_subject_bbox(), clip_clipper_polygon_with_subject_bbox(), clip_clipper_polygon_with_subject_bbox_templ(), clip_clipper_polygons_with_subject_bbox(), clip_clipper_polygons_with_subject_bbox(), and Slic3r::traverse_extrusions().

Here is the call graph for this function:

Here is the caller graph for this function:

clip_clipper_polygon_with_subject_bbox() [3/6]

Polygon Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox ( const Polygon & src, const BoundingBox & bbox, const bool get_entire_polygons )

nodiscard

{
    Polygon out;
    clip_clipper_polygon_with_subject_bbox(src.points, bbox, out.points, get_entire_polygons);
    return out;
}

References clip_clipper_polygon_with_subject_bbox(), and Slic3r::MultiPoint::points.

Here is the call graph for this function:

clip_clipper_polygon_with_subject_bbox() [4/6]

void Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox	(	const Polygon &	src,
		const BoundingBox &	bbox,
		Polygon &	out )

                                                                                                       { 
    clip_clipper_polygon_with_subject_bbox(src.points, bbox, out.points);
}

References clip_clipper_polygon_with_subject_bbox(), and Slic3r::MultiPoint::points.

Here is the call graph for this function:

clip_clipper_polygon_with_subject_bbox() [5/6]

ZPoints Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox ( const ZPoints & src, const BoundingBox & bbox )

nodiscard

{ return clip_clipper_polygon_with_subject_bbox_templ(src, bbox); }

References clip_clipper_polygon_with_subject_bbox_templ().

Here is the call graph for this function:

clip_clipper_polygon_with_subject_bbox() [6/6]

void Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox	(	const ZPoints &	src,
		const BoundingBox &	bbox,
		ZPoints &	out )

{ clip_clipper_polygon_with_subject_bbox_templ(src, bbox, out); }

References clip_clipper_polygon_with_subject_bbox_templ().

Here is the call graph for this function:

clip_clipper_polygon_with_subject_bbox_templ() [1/2]

template<typename PointsType>

PointsType Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox_templ ( const PointsType & src, const BoundingBox & bbox )

nodiscard

{
    PointsType out;
    clip_clipper_polygon_with_subject_bbox(src, bbox, out);
    return out;
}

References clip_clipper_polygon_with_subject_bbox().

Here is the call graph for this function:

clip_clipper_polygon_with_subject_bbox_templ() [2/2]

template<typename PointsType>

void Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox_templ ( const PointsType & src, const BoundingBox & bbox, PointsType & out, const bool get_entire_polygons = false )

inline

{
    using PointType = typename PointsType::value_type;
 
    out.clear();
    const size_t cnt = src.size();
    if (cnt < 3) return;
 
    enum class Side { Left = 1, Right = 2, Top = 4, Bottom = 8 };
 
    auto sides = [bbox](const PointType &p) {
        return int(p.x() < bbox.min.x()) * int(Side::Left) + int(p.x() > bbox.max.x()) * int(Side::Right) + int(p.y() < bbox.min.y()) * int(Side::Bottom) +
               int(p.y() > bbox.max.y()) * int(Side::Top);
    };
 
    int          sides_prev = sides(src.back());
    int          sides_this = sides(src.front());
    const size_t last       = cnt - 1;
    for (size_t i = 0; i < last; ++i) {
        int sides_next = sides(src[i + 1]);
        if ( // This point is inside. Take it.
            sides_this == 0 ||
            // Either this point is outside and previous or next is inside, or
            // the edge possibly cuts corner of the bounding box.
            (sides_prev & sides_this & sides_next) == 0) {
            out.emplace_back(src[i]);
            sides_prev = sides_this;
        } else {
            // All the three points (this, prev, next) are outside at the same side.
            // Ignore this point.
        }
        sides_this = sides_next;
    }
 
    // Never produce just a single point output polygon.
    if (!out.empty()) {
        if (get_entire_polygons) {
            out=src;
        } else {
            if (int sides_next = sides(out.front());
            // The last point is inside. Take it.
            sides_this == 0 ||
            // Either this point is outside and previous or next is inside, or
            // the edge possibly cuts corner of the bounding box.
            (sides_prev & sides_this & sides_next) == 0)
            out.emplace_back(src.back());
        }
    }
}

References Slic3r::Bottom, Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::min, and Slic3r::Top.

Referenced by clip_clipper_polygon_with_subject_bbox(), clip_clipper_polygon_with_subject_bbox(), clip_clipper_polygon_with_subject_bbox(), and clip_clipper_polygon_with_subject_bbox().

Here is the caller graph for this function:

clip_clipper_polygons_with_subject_bbox() [1/3]

Polygons Slic3r::ClipperUtils::clip_clipper_polygons_with_subject_bbox ( const ExPolygon & src, const BoundingBox & bbox, const bool get_entire_polygons )

nodiscard

{
    Polygons out;
    out.reserve(src.num_contours());
    out.emplace_back(clip_clipper_polygon_with_subject_bbox(src.contour, bbox, get_entire_polygons));
    for (const Polygon &p : src.holes) out.emplace_back(clip_clipper_polygon_with_subject_bbox(p, bbox, get_entire_polygons));
    out.erase(std::remove_if(out.begin(), out.end(), [](const Polygon &polygon) { return polygon.empty(); }), out.end());
    return out;
}

References clip_clipper_polygon_with_subject_bbox(), Slic3r::ExPolygon::contour, Slic3r::ExPolygon::holes, and Slic3r::ExPolygon::num_contours().

Here is the call graph for this function:

clip_clipper_polygons_with_subject_bbox() [2/3]

Polygons Slic3r::ClipperUtils::clip_clipper_polygons_with_subject_bbox ( const ExPolygons & src, const BoundingBox & bbox, const bool get_entire_polygons )

nodiscard

{
    Polygons out;
    out.reserve(number_polygons(src));
    for (const ExPolygon &p : src) {
        Polygons temp = clip_clipper_polygons_with_subject_bbox(p, bbox, get_entire_polygons);
        out.insert(out.end(), temp.begin(), temp.end());
    }
 
    out.erase(std::remove_if(out.begin(), out.end(), [](const Polygon &polygon) {return polygon.empty(); }), out.end());
    return out;
}

References clip_clipper_polygons_with_subject_bbox(), and Slic3r::number_polygons().

Here is the call graph for this function:

clip_clipper_polygons_with_subject_bbox() [3/3]

Polygons Slic3r::ClipperUtils::clip_clipper_polygons_with_subject_bbox ( const Polygons & src, const BoundingBox & bbox )

nodiscard

{
    Polygons out;
    out.reserve(src.size());
    for (const Polygon &p : src) out.emplace_back(clip_clipper_polygon_with_subject_bbox(p, bbox));
    out.erase(std::remove_if(out.begin(), out.end(), [](const Polygon &polygon) { return polygon.empty(); }), out.end());
    return out;
}

References clip_clipper_polygon_with_subject_bbox().

Referenced by Slic3r::avoid_object_remove_extra_small_parts(), clip_clipper_polygons_with_subject_bbox(), Slic3r::detect_steep_overhang(), Slic3r::diff_clipped(), Slic3r::diff_clipped(), Slic3r::diff_clipped(), Slic3r::generate_extra_perimeters_over_overhangs(), Slic3r::intersection_clipped(), Slic3r::Layer::make_fills(), Slic3r::PerimeterGenerator::process_classic(), Slic3r::Algorithm::propagate_wave_from_boundary(), Slic3r::TreeSupport3D::safe_offset_inc(), Slic3r::PerimeterGenerator::split_top_surfaces(), Slic3r::RetractWhenCrossingPerimeters::travel_inside_internal_regions(), and Slic3r::traverse_loops().

Here is the call graph for this function:

Here is the caller graph for this function:

interior_point()

std::optional< Point > Slic3r::ClipperUtils::interior_point ( const Polygon & polygon )

nodiscard

    {
        std::vector<coord_t> heights;
        heights.reserve(polygon.size());
        for (const Point &pt : polygon.points)
            heights.emplace_back(pt.y());
        std::sort(heights.begin(), heights.end());
        heights.erase(std::unique(heights.begin(), heights.end()), heights.end());
        std::vector<std::pair<coord_t, coord_t>> bands;
        for (size_t i = 1; i < heights.size(); ++ i)
            if (heights[i] - heights[i - 1] >= 2)
                bands.emplace_back(heights[i - 1], heights[i]);
        std::sort(bands.begin(), bands.end(), [](const auto &a, const auto &b) { return a.second - a.first > b.second - b.first; });
        std::vector<double> crossings;
        for (const auto &[low, high] : bands) {
            const coord_t y = low + (high - low) / 2;
            crossings.clear();
            for (size_t i = 0, j = polygon.size() - 1; i < polygon.size(); j = i ++) {
                const Point &a = polygon.points[j];
                const Point &b = polygon.points[i];
                if ((a.y() > y) != (b.y() > y))
                    crossings.emplace_back(double(a.x()) + double(y - a.y()) * double(b.x() - a.x()) / double(b.y() - a.y()));
            }
            std::sort(crossings.begin(), crossings.end());
            // Inside from the first crossing to the second, from the third to the fourth...
            double left = 0., right = 0.;
            for (size_t i = 1; i < crossings.size(); i += 2)
                if (crossings[i] - crossings[i - 1] > right - left) {
                    left  = crossings[i - 1];
                    right = crossings[i];
                }
            if (const Point pt(coord_t(std::round(0.5 * (left + right))), y); right > left && contains(polygon, pt, false))
                return pt;
        }
        return std::nullopt;
    }

References Slic3r::Geometry::contains(), Slic3r::MultiPoint::points, and Slic3r::MultiPoint::size().

Referenced by Slic3r::anonymous_namespace{ClipperUtils.cpp}::path_encloses().

Here is the call graph for this function:

Here is the caller graph for this function:

tile_expolygons()

std::vector< ExPolygonsTile > Slic3r::ClipperUtils::tile_expolygons ( const ExPolygons & expolygons, size_t per_tile )

nodiscard

    {
        BoundingBox              extent;
        std::vector<BoundingBox> bboxes;
        bboxes.reserve(expolygons.size());
        for (const ExPolygon &expoly : expolygons) {
            bboxes.emplace_back(get_extents(expoly));
            extent.merge(bboxes.back());
        }
        if (! extent.defined)
            return {};
        const int     tiles  = std::clamp(int(std::sqrt(double(expolygons.size()) / double(std::max<size_t>(per_tile, 1)))), 1, 32);
        const Point   size   = extent.size();
        const coord_t tile_w = std::max<coord_t>(1, size.x() / tiles + 1), tile_h = std::max<coord_t>(1, size.y() / tiles + 1);
        std::vector<ExPolygonsTile> out(size_t(tiles * tiles));
        for (size_t i = 0; i < expolygons.size(); ++ i) {
            const Point c = bboxes[i].center();
            ExPolygonsTile &tile = out[size_t(std::clamp(int((c.y() - extent.min.y()) / tile_h), 0, tiles - 1) * tiles +
                                              std::clamp(int((c.x() - extent.min.x()) / tile_w), 0, tiles - 1))];
            tile.members.emplace_back(i);
            tile.bbox.merge(bboxes[i]);
        }
        out.erase(std::remove_if(out.begin(), out.end(), [](const ExPolygonsTile &tile) { return tile.members.empty(); }), out.end());
        return out;
    }

References Slic3r::ClipperUtils::ExPolygonsTile::bbox, Slic3r::BoundingBoxBase< PointType, APointsType >::defined, Slic3r::get_extents(), Slic3r::ClipperUtils::ExPolygonsTile::members, Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::BoundingBoxBase< PointType, APointsType >::min, and Slic3r::BoundingBoxBase< PointType, APointsType >::size().

Referenced by Slic3r::clipper_ex_by_piece(), and Slic3r::segmentation_top_and_bottom_layers().

Here is the call graph for this function:

Here is the caller graph for this function: