path: root/src/libslic3r/Brim.cpp

#include "clipper/clipper_z.hpp"

#include "ClipperUtils.hpp"
#include "EdgeGrid.hpp"
#include "Layer.hpp"
#include "Print.hpp"
#include "ShortestPath.hpp"
#include "libslic3r.h"

#include <algorithm>
#include <numeric>
#include <tbb/parallel_for.h>

namespace Slic3r {

static void append_and_translate(ExPolygons &dst, const ExPolygons &src, const PrintInstance &instance) {
    size_t dst_idx = dst.size();
    expolygons_append(dst, src);
    for (; dst_idx < dst.size(); ++dst_idx)
        dst[dst_idx].translate(instance.shift.x(), instance.shift.y());
}

static void append_and_translate(Polygons &dst, const Polygons &src, const PrintInstance &instance) {
    size_t dst_idx = dst.size();
    polygons_append(dst, src);
    for (; dst_idx < dst.size(); ++dst_idx)
        dst[dst_idx].translate(instance.shift.x(), instance.shift.y());
}

static float max_brim_width(const ConstPrintObjectPtrsAdaptor &objects)
{
    assert(!objects.empty());
    return float(std::accumulate(objects.begin() + 1, objects.end(), objects.front()->config().brim_width.value,
                                 [](double partial_result, const PrintObject *object) {
                                     return std::max(partial_result, object->config().brim_width.value);
                                 }));
}

static ConstPrintObjectPtrs get_top_level_objects_with_brim(const Print &print)
{
    Polygons             islands;
    ConstPrintObjectPtrs island_to_object;
    for (const PrintObject *object : print.objects()) {
        Polygons islands_object;
        for (const ExPolygon &ex_poly : object->layers().front()->lslices)
            islands_object.emplace_back(ex_poly.contour);

        islands.reserve(islands.size() + object->instances().size() * islands_object.size());
        for (const PrintInstance &instance : object->instances())
            for (Polygon &poly : islands_object) {
                islands.emplace_back(poly);
                islands.back().translate(instance.shift);
                island_to_object.emplace_back(object);
            }
    }
    assert(islands.size() == island_to_object.size());

    ClipperLib_Z::Paths islands_clip;
    islands_clip.reserve(islands.size());
    for (const Polygon &poly : islands) {
        islands_clip.emplace_back();
        ClipperLib_Z::Path &island_clip = islands_clip.back();
        island_clip.reserve(poly.points.size());
        int island_idx = int(&poly - &islands.front());
        // The Z coordinate carries index of the island used to get the pointer to the object.
        for (const Point &pt : poly.points)
            island_clip.emplace_back(pt.x(), pt.y(), island_idx + 1);
    }

    // Init Clipper
    ClipperLib_Z::Clipper clipper;
    // Assign the maximum Z from four points. This values is valid index of the island
    clipper.ZFillFunction([](const ClipperLib_Z::IntPoint &e1bot, const ClipperLib_Z::IntPoint &e1top, const ClipperLib_Z::IntPoint &e2bot,
                             const ClipperLib_Z::IntPoint &e2top, ClipperLib_Z::IntPoint &pt) {
        pt.Z = std::max(std::max(e1bot.Z, e1top.Z), std::max(e2bot.Z, e2top.Z));
    });
    // Add islands
    clipper.AddPaths(islands_clip, ClipperLib_Z::ptSubject, true);
    // Execute union operation to construct polytree
    ClipperLib_Z::PolyTree islands_polytree;
    clipper.Execute(ClipperLib_Z::ctUnion, islands_polytree, ClipperLib_Z::pftEvenOdd, ClipperLib_Z::pftEvenOdd);

    std::unordered_set<size_t> processed_objects_idx;
    ConstPrintObjectPtrs       top_level_objects_with_brim;
    for (int i = 0; i < islands_polytree.ChildCount(); ++i) {
        for (const ClipperLib_Z::IntPoint &point : islands_polytree.Childs[i]->Contour) {
            if (point.Z != 0 && processed_objects_idx.find(island_to_object[point.Z - 1]->id().id) == processed_objects_idx.end()) {
                top_level_objects_with_brim.emplace_back(island_to_object[point.Z - 1]);
                processed_objects_idx.insert(island_to_object[point.Z - 1]->id().id);
            }
        }
    }
    return top_level_objects_with_brim;
}

static Polygons top_level_outer_brim_islands(const ConstPrintObjectPtrs &top_level_objects_with_brim)
{
    Polygons islands;
    for (const PrintObject *object : top_level_objects_with_brim) {
        float    brim_offset = float(scale_(object->config().brim_offset.value));
        Polygons islands_object;
        for (const ExPolygon &ex_poly : object->layers().front()->lslices) {
            Polygons contour_offset = offset(ex_poly.contour, brim_offset);
            for (Polygon &poly : contour_offset)
                poly.douglas_peucker(SCALED_RESOLUTION);

            polygons_append(islands_object, std::move(contour_offset));
        }

        for (const PrintInstance &instance : object->instances())
            append_and_translate(islands, islands_object, instance);
    }
    return islands;
}

static ExPolygons top_level_outer_brim_area(const Print &print, const ConstPrintObjectPtrs &top_level_objects_with_brim, const float no_brim_offset)
{
    std::unordered_set<size_t> top_level_objects_idx;
    top_level_objects_idx.reserve(top_level_objects_with_brim.size());
    for (const PrintObject *object : top_level_objects_with_brim)
        top_level_objects_idx.insert(object->id().id);

    ExPolygons brim_area;
    Polygons   no_brim_area;
    for (const PrintObject *object : print.objects()) {
        const BrimType brim_type         = object->config().brim_type.value;
        const float    brim_offset       = scale_(object->config().brim_offset.value);
        const float    brim_width        = scale_(object->config().brim_width.value);
        const bool     is_top_outer_brim = top_level_objects_idx.find(object->id().id) != top_level_objects_idx.end();

        ExPolygons brim_area_object;
        Polygons   no_brim_area_object;
        for (const ExPolygon &ex_poly : object->layers().front()->lslices) {
            if ((brim_type == BrimType::btOuterOnly || brim_type == BrimType::btOuterAndInner) && is_top_outer_brim)
                append(brim_area_object, diff_ex(offset_ex(ex_poly.contour, brim_width + brim_offset), offset_ex(ex_poly.contour, brim_offset)));

            if (brim_type == BrimType::btOuterOnly || brim_type == BrimType::btNoBrim)
                append(no_brim_area_object, offset(ex_poly.holes, -no_brim_offset));

            if (brim_type != BrimType::btNoBrim)
                append(no_brim_area_object, offset(ex_poly.contour, brim_offset));

            no_brim_area_object.emplace_back(ex_poly.contour);
        }

        for (const PrintInstance &instance : object->instances()) {
            append_and_translate(brim_area, brim_area_object, instance);
            append_and_translate(no_brim_area, no_brim_area_object, instance);
        }
    }

    return diff_ex(to_polygons(std::move(brim_area)), no_brim_area);
}

static ExPolygons inner_brim_area(const Print &print, const ConstPrintObjectPtrs &top_level_objects_with_brim, const float no_brim_offset)
{
    std::unordered_set<size_t> top_level_objects_idx;
    top_level_objects_idx.reserve(top_level_objects_with_brim.size());
    for (const PrintObject *object : top_level_objects_with_brim)
        top_level_objects_idx.insert(object->id().id);

    ExPolygons brim_area;
    ExPolygons no_brim_area;
    Polygons   holes;
    for (const PrintObject *object : print.objects()) {
        const BrimType brim_type      = object->config().brim_type.value;
        const float    brim_offset    = scale_(object->config().brim_offset.value);
        const float    brim_width     = scale_(object->config().brim_width.value);
        const bool     top_outer_brim = top_level_objects_idx.find(object->id().id) != top_level_objects_idx.end();

        ExPolygons brim_area_object;
        ExPolygons no_brim_area_object;
        Polygons   holes_object;
        for (const ExPolygon &ex_poly : object->layers().front()->lslices) {
            if (brim_type == BrimType::btOuterOnly || brim_type == BrimType::btOuterAndInner) {
                if (top_outer_brim)
                    no_brim_area_object.emplace_back(ex_poly);
                else
                    append(brim_area_object, diff_ex(offset_ex(ex_poly.contour, brim_width + brim_offset), offset_ex(ex_poly.contour, brim_offset)));
            }

            if (brim_type == BrimType::btInnerOnly || brim_type == BrimType::btOuterAndInner)
                append(brim_area_object, diff_ex(offset_ex(ex_poly.holes, -brim_offset), offset_ex(ex_poly.holes, -brim_width - brim_offset)));

            if (brim_type == BrimType::btInnerOnly || brim_type == BrimType::btNoBrim)
                append(no_brim_area_object, offset_ex(ex_poly.contour, no_brim_offset));

            if (brim_type == BrimType::btOuterOnly || brim_type == BrimType::btNoBrim)
                append(no_brim_area_object, offset_ex(ex_poly.holes, -no_brim_offset));

            append(holes_object, ex_poly.holes);
        }
        append(no_brim_area_object, offset_ex(object->layers().front()->lslices, brim_offset));

        for (const PrintInstance &instance : object->instances()) {
            append_and_translate(brim_area, brim_area_object, instance);
            append_and_translate(no_brim_area, no_brim_area_object, instance);
            append_and_translate(holes, holes_object, instance);
        }
    }

    return diff_ex(intersection_ex(to_polygons(std::move(brim_area)), holes), no_brim_area);
}

static void optimize_polylines_by_reversing(Polylines *polylines)
{
    for (size_t poly_idx = 1; poly_idx < polylines->size(); ++poly_idx) {
        const Polyline &prev = (*polylines)[poly_idx - 1];
        Polyline &      next = (*polylines)[poly_idx];

        if (!next.is_closed()) {
            double dist_to_start = (next.first_point() - prev.last_point()).cast<double>().norm();
            double dist_to_end   = (next.last_point() - prev.last_point()).cast<double>().norm();

            if (dist_to_end < dist_to_start) next.reverse();
        }
    }
}

static Polylines connect_brim_lines(Polylines &&polylines, const Polygons &brim_area, float max_connection_length)
{
    EdgeGrid::Grid grid;
    BoundingBox    bbox(get_extents(polylines));
    bbox.offset(SCALED_EPSILON);
    grid.set_bbox(bbox);

    std::vector<Points> polylines_points(polylines.size() + brim_area.size());
    for (const Polyline &poly : polylines)
        polylines_points[&poly - &polylines.front()] = poly.points;
    for (const Polygon &poly : brim_area)
        polylines_points.emplace_back(poly.points);
    grid.create(polylines_points, coord_t(scale_(10.)));

    struct Visitor
    {
        explicit Visitor(const EdgeGrid::Grid &grid) : grid(grid) {}

        bool operator()(coord_t iy, coord_t ix)
        {
            // Called with a row and colum of the grid cell, which is intersected by a line.
            auto cell_data_range = grid.cell_data_range(iy, ix);
            this->intersect      = false;
            for (auto it_contour_and_segment = cell_data_range.first; it_contour_and_segment != cell_data_range.second; ++it_contour_and_segment) {
                // End points of the line segment and their vector.
                auto segment = grid.segment(*it_contour_and_segment);
                if (Geometry::segments_intersect(segment.first, segment.second, brim_line.a, brim_line.b)) {
                    this->intersect = true;
                    return false;
                }
            }
            // Continue traversing the grid along the edge.
            return true;
        }

        const EdgeGrid::Grid &grid;
        Line                  brim_line;
        bool                  intersect;

    } visitor(grid);

    Polyline *prev = &polylines.front();
    for (size_t poly_idx = 1; poly_idx < polylines.size(); ++poly_idx) {
        Polyline &next = polylines[poly_idx];

        double dist = Line(prev->last_point(), next.first_point()).length();
        if (dist <= max_connection_length) {
            visitor.brim_line.a = prev->last_point();
            visitor.brim_line.b = next.first_point();
            visitor.brim_line.extend(-SCALED_EPSILON);
            grid.visit_cells_intersecting_line(visitor.brim_line.a, visitor.brim_line.b, visitor);
            if (!visitor.intersect)
                append(prev->points, std::move(next.points));
            else
                prev = &next;
        }
    }

    Polylines polylines_out;
    polylines_out.reserve(std::count_if(polylines.begin(), polylines.end(), [](const Polyline &pl) { return !pl.empty(); }));
    for (Polyline &pl : polylines)
        if (!pl.empty())
            polylines_out.emplace_back(std::move(pl));

    return polylines_out;
}

static void make_inner_brim(const Print &print, const ConstPrintObjectPtrs &top_level_objects_with_brim, ExtrusionEntityCollection &brim)
{
    Flow       flow = print.brim_flow();
    ExPolygons islands_ex = inner_brim_area(print, top_level_objects_with_brim, flow.scaled_spacing());
    ExPolygons loops_ex;
    islands_ex      = offset_ex(islands_ex, -0.5f * float(flow.scaled_spacing()), jtSquare);
    for (size_t i = 0; !islands_ex.empty(); ++i) {
        for (ExPolygon &poly_ex : islands_ex)
            poly_ex.douglas_peucker(SCALED_RESOLUTION);
        expolygons_append(loops_ex, islands_ex);
        islands_ex = offset_ex(islands_ex, -float(flow.scaled_spacing()), jtSquare);
    }

    Polygons loops = union_pt_chained_outside_in(loops, false);
    std::reverse(loops.begin(), loops.end());
    extrusion_entities_append_loops(brim.entities, std::move(loops), erSkirt, float(flow.mm3_per_mm()),
                                    float(flow.width), float(print.skirt_first_layer_height()));
}

// Produce brim lines around those objects, that have the brim enabled.
// Collect islands_area to be merged into the final 1st layer convex hull.
ExtrusionEntityCollection make_brim(const Print &print, PrintTryCancel try_cancel, Polygons &islands_area)
{
    Flow                 flow                         = print.brim_flow();
    ConstPrintObjectPtrs top_level_objects_with_brim  = get_top_level_objects_with_brim(print);
    Polygons             islands                      = top_level_outer_brim_islands(top_level_objects_with_brim);
    ExPolygons           islands_area_ex              = top_level_outer_brim_area(print, top_level_objects_with_brim, flow.scaled_spacing());
    islands_area                                      = to_polygons(islands_area_ex);

    Polygons        loops;
    size_t          num_loops = size_t(floor(max_brim_width(print.objects()) / flow.spacing()));
    for (size_t i = 0; i < num_loops; ++i) {
        try_cancel();
        islands = offset(islands, float(flow.scaled_spacing()), jtSquare);
        for (Polygon &poly : islands) 
            poly.douglas_peucker(SCALED_RESOLUTION);
        polygons_append(loops, offset(islands, -0.5f * float(flow.scaled_spacing())));
    }
    loops = union_pt_chained_outside_in(loops, false);

    std::vector<Polylines> loops_pl_by_levels;
    {
        Polylines              loops_pl = to_polylines(loops);
        loops_pl_by_levels.assign(loops_pl.size(), Polylines());
        tbb::parallel_for(tbb::blocked_range<size_t>(0, loops_pl.size()),
            [&loops_pl_by_levels, &loops_pl, &islands_area](const tbb::blocked_range<size_t> &range) {
                for (size_t i = range.begin(); i < range.end(); ++i) {
                    loops_pl_by_levels[i] = chain_polylines(intersection_pl({ std::move(loops_pl[i]) }, islands_area));
                }
            });
    }

    // output
    ExtrusionEntityCollection brim;

    // Reduce down to the ordered list of polylines.
    Polylines all_loops;
    for (Polylines &polylines : loops_pl_by_levels)
        append(all_loops, std::move(polylines));
    loops_pl_by_levels.clear();

    optimize_polylines_by_reversing(&all_loops);
    all_loops = connect_brim_lines(std::move(all_loops), offset(islands_area_ex,SCALED_EPSILON), flow.scaled_spacing() * 2);

    const bool could_brim_intersects_skirt = std::any_of(print.objects().begin(), print.objects().end(), [&print](PrintObject *object) {
        const BrimType &bt = object->config().brim_type;
        return (bt == btOuterOnly || bt == btOuterAndInner) && print.config().skirt_distance.value < object->config().brim_width;
    });
    // If there is a possibility that brim intersects skirt, go through loops and split those extrusions
    // The result is either the original Polygon or a list of Polylines
    if (! print.skirt().empty() && could_brim_intersects_skirt)
    {
        // Find the bounding polygons of the skirt
        const Polygons skirt_inners = offset(dynamic_cast<ExtrusionLoop*>(print.skirt().entities.back())->polygon(),
                                              -float(scale_(print.skirt_flow().spacing()))/2.f,
                                              ClipperLib::jtRound,
                                              float(scale_(0.1)));
        const Polygons skirt_outers = offset(dynamic_cast<ExtrusionLoop*>(print.skirt().entities.front())->polygon(),
                                              float(scale_(print.skirt_flow().spacing()))/2.f,
                                              ClipperLib::jtRound,
                                              float(scale_(0.1)));

        // First calculate the trimming region.
		ClipperLib_Z::Paths trimming;
		{
		    ClipperLib_Z::Paths input_subject;
		    ClipperLib_Z::Paths input_clip;
		    for (const Polygon &poly : skirt_outers) {
		    	input_subject.emplace_back();
		    	ClipperLib_Z::Path &out = input_subject.back();
		    	out.reserve(poly.points.size());
			    for (const Point &pt : poly.points)
					out.emplace_back(pt.x(), pt.y(), 0);
		    }
		    for (const Polygon &poly : skirt_inners) {
		    	input_clip.emplace_back();
		    	ClipperLib_Z::Path &out = input_clip.back();
		    	out.reserve(poly.points.size());
			    for (const Point &pt : poly.points)
					out.emplace_back(pt.x(), pt.y(), 0);
		    }
		    // init Clipper
		    ClipperLib_Z::Clipper clipper;
		    // add polygons
		    clipper.AddPaths(input_subject, ClipperLib_Z::ptSubject, true);
		    clipper.AddPaths(input_clip,    ClipperLib_Z::ptClip,    true);
		    // perform operation
		    clipper.Execute(ClipperLib_Z::ctDifference, trimming, ClipperLib_Z::pftEvenOdd, ClipperLib_Z::pftEvenOdd);
		}

		// Second, trim the extrusion loops with the trimming regions.
		ClipperLib_Z::Paths loops_trimmed;
		{
            // Produce ClipperLib_Z::Paths from polylines (not necessarily closed).
			ClipperLib_Z::Paths input_clip;
			for (const Polyline &loop_pl : all_loops) {
				input_clip.emplace_back();
				ClipperLib_Z::Path& out = input_clip.back();
				out.reserve(loop_pl.points.size());
				int64_t loop_idx = &loop_pl - &all_loops.front();
				for (const Point& pt : loop_pl.points)
					// The Z coordinate carries index of the source loop.
					out.emplace_back(pt.x(), pt.y(), loop_idx + 1);
			}
			// init Clipper
			ClipperLib_Z::Clipper clipper;
			clipper.ZFillFunction([](const ClipperLib_Z::IntPoint& e1bot, const ClipperLib_Z::IntPoint& e1top, const ClipperLib_Z::IntPoint& e2bot, const ClipperLib_Z::IntPoint& e2top, ClipperLib_Z::IntPoint& pt) {
				// Assign a valid input loop identifier. Such an identifier is strictly positive, the next line is safe even in case one side of a segment
				// hat the Z coordinate not set to the contour coordinate.
				pt.Z = std::max(std::max(e1bot.Z, e1top.Z), std::max(e2bot.Z, e2top.Z));
			});
			// add polygons
			clipper.AddPaths(input_clip, ClipperLib_Z::ptSubject, false);
			clipper.AddPaths(trimming,   ClipperLib_Z::ptClip,    true);
			// perform operation
			ClipperLib_Z::PolyTree loops_trimmed_tree;
			clipper.Execute(ClipperLib_Z::ctDifference, loops_trimmed_tree, ClipperLib_Z::pftEvenOdd, ClipperLib_Z::pftEvenOdd);
			ClipperLib_Z::PolyTreeToPaths(loops_trimmed_tree, loops_trimmed);
		}

		// Third, produce the extrusions, sorted by the source loop indices.
		{
			std::vector<std::pair<const ClipperLib_Z::Path*, size_t>> loops_trimmed_order;
			loops_trimmed_order.reserve(loops_trimmed.size());
			for (const ClipperLib_Z::Path &path : loops_trimmed) {
				size_t input_idx = 0;
				for (const ClipperLib_Z::IntPoint &pt : path)
					if (pt.Z > 0) {
						input_idx = (size_t)pt.Z;
						break;
					}
				assert(input_idx != 0);
				loops_trimmed_order.emplace_back(&path, input_idx);
			}
			std::stable_sort(loops_trimmed_order.begin(), loops_trimmed_order.end(),
				[](const std::pair<const ClipperLib_Z::Path*, size_t> &l, const std::pair<const ClipperLib_Z::Path*, size_t> &r) {
					return l.second < r.second;
				});

			Point last_pt(0, 0);
			for (size_t i = 0; i < loops_trimmed_order.size();) {
				// Find all pieces that the initial loop was split into.
				size_t j = i + 1;
                for (; j < loops_trimmed_order.size() && loops_trimmed_order[i].second == loops_trimmed_order[j].second; ++ j) ;
                const ClipperLib_Z::Path &first_path = *loops_trimmed_order[i].first;
				if (i + 1 == j && first_path.size() > 3 && first_path.front().X == first_path.back().X && first_path.front().Y == first_path.back().Y) {
					auto *loop = new ExtrusionLoop();
                    brim.entities.emplace_back(loop);
					loop->paths.emplace_back(erSkirt, float(flow.mm3_per_mm()), float(flow.width), float(print.skirt_first_layer_height()));
		            Points &points = loop->paths.front().polyline.points;
		            points.reserve(first_path.size());
		            for (const ClipperLib_Z::IntPoint &pt : first_path)
		            	points.emplace_back(coord_t(pt.X), coord_t(pt.Y));
		            i = j;
				} else {
			    	//FIXME The path chaining here may not be optimal.
			    	ExtrusionEntityCollection this_loop_trimmed;
					this_loop_trimmed.entities.reserve(j - i);
			    	for (; i < j; ++ i) {
			            this_loop_trimmed.entities.emplace_back(new ExtrusionPath(erSkirt, float(flow.mm3_per_mm()), float(flow.width), float(print.skirt_first_layer_height())));
						const ClipperLib_Z::Path &path = *loops_trimmed_order[i].first;
			            Points &points = static_cast<ExtrusionPath*>(this_loop_trimmed.entities.back())->polyline.points;
			            points.reserve(path.size());
			            for (const ClipperLib_Z::IntPoint &pt : path)
			            	points.emplace_back(coord_t(pt.X), coord_t(pt.Y));
		           	}
		           	chain_and_reorder_extrusion_entities(this_loop_trimmed.entities, &last_pt);
                    brim.entities.reserve(brim.entities.size() + this_loop_trimmed.entities.size());
		           	append(brim.entities, std::move(this_loop_trimmed.entities));
		           	this_loop_trimmed.entities.clear();
		        }
		        last_pt = brim.last_point();
			}
		}
    } else {
        extrusion_entities_append_loops_and_paths(brim.entities, std::move(all_loops), erSkirt, float(flow.mm3_per_mm()), float(flow.width), float(print.skirt_first_layer_height()));
    }

    make_inner_brim(print, top_level_objects_with_brim, brim);

    return brim;
}

} // namespace Slic3r