#include <src/libslic3r/JumpPointSearch.hpp>

Collaboration diagram for Slic3r::JPSPathFinder:

Public Member Functions
	JPSPathFinder ()=default

void	init_bed_shape (const Points &bed_shape)

void	clear ()

void	add_obstacles (const Lines &obstacles)

void	add_obstacles (const Layer *layer, const Point &global_origin)

Polyline	find_path (const Point &start, const Point &end)

Private Types
using	Pixel = Point

Private Member Functions
Pixel	pixelize (const Point &p)

Point	unpixelize (const Pixel &p)

Private Attributes
std::unordered_set< Pixel, PointHash >	inpassable

coordf_t	print_z

BoundingBox	max_search_box

Lines	bed_shape

const coord_t	resolution = scaled(1.5)

Detailed Description

Member Typedef Documentation

◆ Pixel

using Slic3r::JPSPathFinder::Pixel = Point

private

Constructor & Destructor Documentation

◆ JPSPathFinder()

Slic3r::JPSPathFinder::JPSPathFinder ( )

default

Member Function Documentation

◆ add_obstacles() [1/2]

void Slic3r::JPSPathFinder::add_obstacles	(	const Layer *	layer,
		const Point &	global_origin
	)

{
    if (layer == nullptr) return;
 
    this->print_z = layer->print_z;
    Lines obstacles;
    obstacles.reserve(layer->curled_lines.size());
    for (const Line &l : layer->curled_lines) { obstacles.push_back(Line{l.a + global_origin, l.b + global_origin}); }
    add_obstacles(obstacles);
}

References Slic3r::Line::a, add_obstacles(), Slic3r::Layer::curled_lines, print_z, and Slic3r::Layer::print_z.

Here is the call graph for this function:

◆ add_obstacles() [2/2]

void Slic3r::JPSPathFinder::add_obstacles ( const Lines & obstacles )

{
    auto store_obstacle = [&](coord_t x, coord_t y) {
        max_search_box.max.x() = std::max(max_search_box.max.x(), x);
        max_search_box.max.y() = std::max(max_search_box.max.y(), y);
        max_search_box.min.x() = std::min(max_search_box.min.x(), x);
        max_search_box.min.y() = std::min(max_search_box.min.y(), y);
        inpassable.insert(Pixel{x, y});
        return true;
    };
 
    for (const Line &l : obstacles) {
        Pixel start = pixelize(l.a);
        Pixel end   = pixelize(l.b);
        double_dda_with_offset(start.x(), start.y(), end.x(), end.y(), store_obstacle);
    }
}

References Slic3r::double_dda_with_offset(), inpassable, Slic3r::BoundingBoxBase< PointType, APointsType >::max, max_search_box, Slic3r::BoundingBoxBase< PointType, APointsType >::min, and pixelize().

Referenced by add_obstacles(), clear(), and Slic3r::GCode::process_layer().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clear()

void Slic3r::JPSPathFinder::clear ( )

{
    inpassable.clear();
    max_search_box.max = Pixel(std::numeric_limits<coord_t>::min(), std::numeric_limits<coord_t>::min());
    max_search_box.min = Pixel(std::numeric_limits<coord_t>::max(), std::numeric_limits<coord_t>::max());
    add_obstacles(bed_shape);
}

References add_obstacles(), bed_shape, inpassable, Slic3r::BoundingBoxBase< PointType, APointsType >::max, max_search_box, and Slic3r::BoundingBoxBase< PointType, APointsType >::min.

Referenced by Slic3r::GCode::process_layer().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_path()

Polyline Slic3r::JPSPathFinder::find_path	(	const Point &	start,
		const Point &	end
	)

{
    Pixel start = pixelize(p0);
    Pixel end   = pixelize(p1);
    if (inpassable.empty() || (start - end).cast<float>().norm() < 3.0) { return Polyline{p0, p1}; }
 
    if (inpassable.find(start) != inpassable.end()) {
        dda(start.x(), start.y(), end.x(), end.y(), [&](coord_t x, coord_t y) {
            if (inpassable.find(Pixel(x, y)) == inpassable.end() || start == end) { // new start not found yet, and xy passable
                start = Pixel(x, y);
                return false;
            }
            return true;
        });
    }
 
    if (inpassable.find(end) != inpassable.end()) {
        dda(end.x(), end.y(), start.x(), start.y(), [&](coord_t x, coord_t y) {
            if (inpassable.find(Pixel(x, y)) == inpassable.end() || start == end) { // new start not found yet, and xy passable
                end = Pixel(x, y);
                return false;
            }
            return true;
        });
    }
 
    BoundingBox search_box = max_search_box;
    search_box.max -= Pixel(1, 1);
    search_box.min += Pixel(1, 1);
 
    BoundingBox bounding_square(Points{start, end});
    bounding_square.max += Pixel(5, 5);
    bounding_square.min -= Pixel(5, 5);
    coord_t bounding_square_size = 2 * std::max(bounding_square.size().x(), bounding_square.size().y());
    bounding_square.max.x() += (bounding_square_size - bounding_square.size().x()) / 2;
    bounding_square.min.x() -= (bounding_square_size - bounding_square.size().x()) / 2;
    bounding_square.max.y() += (bounding_square_size - bounding_square.size().y()) / 2;
    bounding_square.min.y() -= (bounding_square_size - bounding_square.size().y()) / 2;
 
    // Intersection - limit the search box to a square area around the start and end, to fasten the path searching
    search_box.max = search_box.max.cwiseMin(bounding_square.max);
    search_box.min = search_box.min.cwiseMax(bounding_square.min);
 
    auto cell_query = [&](Pixel pixel) {
        return search_box.contains(pixel) && (pixel == start || pixel == end || inpassable.find(pixel) == inpassable.end());
    };
 
    JPSTracer<Pixel, decltype(cell_query)> tracer(end, cell_query);
    using QNode = astar::QNode<JPSTracer<Pixel, decltype(cell_query)>>;
 
    std::unordered_map<size_t, QNode>   astar_cache{};
    std::vector<Pixel, PointsAllocator<Pixel>> out_path;
    std::vector<decltype(tracer)::Node> out_nodes;
 
    if (!astar::search_route(tracer, {start, {0, 0}}, std::back_inserter(out_nodes), astar_cache)) {
        // path not found - just reconstruct the best path from astar cache.
        // Note that astar_cache is NOT empty - at least the starting point should always be there
        auto                coordiante_func = [&astar_cache](size_t idx, size_t dim) { return float(astar_cache[idx].node.position[dim]); };
        std::vector<size_t> keys;
        keys.reserve(astar_cache.size());
        for (const auto &pair : astar_cache) { keys.push_back(pair.first); }
        KDTreeIndirect<2, float, decltype(coordiante_func)> kd_tree(coordiante_func, keys);
        size_t                                              closest_qnode = find_closest_point(kd_tree, end.cast<float>());
 
        out_path.push_back(end);
        while (closest_qnode != astar::Unassigned) {
            out_path.push_back(astar_cache[closest_qnode].node.position);
            closest_qnode = astar_cache[closest_qnode].parent;
        }
    } else {
        for (const auto &node : out_nodes) { out_path.push_back(node.position); }
        out_path.push_back(start);
    }
 
#ifdef DEBUG_FILES
    auto scaled_points = [](const Points &ps) {
        Points r;
        for (const Point &p : ps) { r.push_back(Point::new_scale(p.x(), p.y())); }
        return r;
    };
    auto          scaled_point = [](const Point &p) { return Point::new_scale(p.x(), p.y()); };
    ::Slic3r::SVG svg(debug_out_path(("path_jps" + std::to_string(print_z) + "_" + std::to_string(rand() % 1000)).c_str()).c_str(),
                      BoundingBox(scaled_point(search_box.min), scaled_point(search_box.max)));
    for (const auto &p : inpassable) { svg.draw(scaled_point(p), "black", scale_(0.4)); }
    for (const auto &qn : astar_cache) { svg.draw(scaled_point(qn.second.node.position), "blue", scale_(0.3)); }
    svg.draw(Polyline(scaled_points(out_path)), "yellow", scale_(0.25));
    svg.draw(scaled_point(end), "purple", scale_(0.4));
    svg.draw(scaled_point(start), "green", scale_(0.4));
#endif
 
    std::vector<Pixel, PointsAllocator<Pixel>> tmp_path;
    tmp_path.reserve(out_path.size());
    // Some path found, reverse and remove points that do not change direction
    std::reverse(out_path.begin(), out_path.end());
    {
        tmp_path.push_back(out_path.front()); // first point
        for (size_t i = 1; i < out_path.size() - 1; i++) {
            if ((out_path[i] - out_path[i - 1]).cast<float>().normalized() != (out_path[i + 1] - out_path[i]).cast<float>().normalized()) {
                tmp_path.push_back(out_path[i]);
            }
        }
        tmp_path.push_back(out_path.back()); // last_point
        out_path = tmp_path;
    }
 
#ifdef DEBUG_FILES
    svg.draw(Polyline(scaled_points(out_path)), "orange", scale_(0.20));
#endif
 
    tmp_path.clear();
    // remove redundant jump points - there are points that change direction but are not needed - this inefficiency arises from the
    // usage of grid search The removal alg tries to find the longest Px Px+k path without obstacles. If Px Px+k+1 is blocked, it will
    // insert the Px+k point to result and continue search from Px+k
    {
        tmp_path.push_back(out_path.front()); // first point
        size_t index_of_last_stored_point = 0;
        for (size_t i = 1; i < out_path.size(); i++) {
            if (i - index_of_last_stored_point < 2) continue;
            bool passable       = true;
            auto store_obstacle = [&](coord_t x, coord_t y) {
                if (Pixel(x, y) != start && Pixel(x, y) != end && inpassable.find(Pixel(x, y)) != inpassable.end()) {
                    passable = false;
                    return false;
                }
                return true;
            };
            dda(tmp_path.back().x(), tmp_path.back().y(), out_path[i].x(), out_path[i].y(), store_obstacle);
            if (!passable) {
                tmp_path.push_back(out_path[i - 1]);
                index_of_last_stored_point = i - 1;
            }
        }
        tmp_path.push_back(out_path.back()); // last_point
        out_path = tmp_path;
    }
 
#ifdef DEBUG_FILES
    svg.draw(Polyline(scaled_points(out_path)), "red", scale_(0.15));
    svg.Close();
#endif
 
    // before returing the path, transform it from pixels back to points.
    // Also replace the first and last pixel by input points so that result path patches input params exactly.
    for (Pixel &p : out_path) { p = unpixelize(p); }
    out_path.front() = p0;
    out_path.back()  = p1;
 
    return Polyline(out_path);
}