Slic3r::JPSTracer< CellPositionType, CellQueryFn > Class Template Reference

Collaboration diagram for Slic3r::JPSTracer< CellPositionType, CellQueryFn >:

Classes
struct	Node

Public Member Functions
	JPSTracer (CellPositionType target, CellQueryFn is_passable)
template<class Fn >
void	foreach_reachable (const Node &from, Fn &&fn) const
float	distance (Node a, Node b) const
float	goal_heuristic (Node n) const
size_t	unique_id (Node n) const

Public Attributes
const std::vector< CellPositionType >	all_directions {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}

Private Member Functions
CellPositionType	find_jump_point (CellPositionType start, CellPositionType forward_dir) const
bool	is_jump_point (CellPositionType pos, CellPositionType forward_dir) const

Private Attributes
CellPositionType	target
CellQueryFn	is_passable

Detailed Description

template<typename CellPositionType, typename CellQueryFn>
class Slic3r::JPSTracer< CellPositionType, CellQueryFn >

---

Class Documentation

Slic3r::JPSTracer::Node

struct Slic3r::JPSTracer::Node

template<typename CellPositionType, typename CellQueryFn>
struct Slic3r::JPSTracer< CellPositionType, CellQueryFn >::Node

Class Members
CellPositionType	incoming_dir
CellPositionType	position

Constructor & Destructor Documentation

JPSTracer()

template<typename CellPositionType , typename CellQueryFn >

Slic3r::JPSTracer< CellPositionType, CellQueryFn >::JPSTracer ( CellPositionType  target, CellQueryFn  is_passable  )

inline

: target(target), is_passable(is_passable) {}

Member Function Documentation

distance()

template<typename CellPositionType , typename CellQueryFn >

float Slic3r::JPSTracer< CellPositionType, CellQueryFn >::distance ( Node  a, Node  b  ) const

inline

{ return (a.position - b.position).template cast<double>().norm(); }

find_jump_point()

template<typename CellPositionType , typename CellQueryFn >

CellPositionType Slic3r::JPSTracer< CellPositionType, CellQueryFn >::find_jump_point ( CellPositionType  start, CellPositionType  forward_dir  ) const

inlineprivate

    {
        CellPositionType next = start + forward_dir;
        while (next != target && is_passable(next) && !(is_jump_point(next, forward_dir))) { next = next + forward_dir; }
 
        if (is_passable(next)) {
            return next;
        } else {
            return start;
        }
    }

References Slic3r::JPSTracer< CellPositionType, CellQueryFn >::is_jump_point(), Slic3r::JPSTracer< CellPositionType, CellQueryFn >::is_passable, and Slic3r::JPSTracer< CellPositionType, CellQueryFn >::target.

Referenced by Slic3r::JPSTracer< CellPositionType, CellQueryFn >::foreach_reachable(), and Slic3r::JPSTracer< CellPositionType, CellQueryFn >::is_jump_point().

Here is the call graph for this function:

Here is the caller graph for this function:

foreach_reachable()

template<typename CellPositionType , typename CellQueryFn >

template<class Fn >

void Slic3r::JPSTracer< CellPositionType, CellQueryFn >::foreach_reachable ( const Node &  from, Fn &&  fn  ) const

inline

    {
        const CellPositionType       &pos         = from.position;
        const CellPositionType       &forward_dir = from.incoming_dir;
        std::vector<CellPositionType> dirs_to_check{};
 
        if (abs(forward_dir.x()) + abs(forward_dir.y()) == 0) { // special case for starting point
            dirs_to_check = all_directions;
        } else if (abs(forward_dir.x()) + abs(forward_dir.y()) == 2) {
            // diagonal
            CellPositionType horizontal_check_dir = CellPositionType{forward_dir.x(), 0};
            CellPositionType vertical_check_dir   = CellPositionType{0, forward_dir.y()};
 
            if (!is_passable(pos - horizontal_check_dir) && is_passable(pos + forward_dir - 2 * horizontal_check_dir)) {
                dirs_to_check.push_back(forward_dir - 2 * horizontal_check_dir);
            }
 
            if (!is_passable(pos - vertical_check_dir) && is_passable(pos + forward_dir - 2 * vertical_check_dir)) {
                dirs_to_check.push_back(forward_dir - 2 * vertical_check_dir);
            }
 
            dirs_to_check.push_back(horizontal_check_dir);
            dirs_to_check.push_back(vertical_check_dir);
            dirs_to_check.push_back(forward_dir);
 
        } else { // horizontal or vertical
            CellPositionType side_dir = CellPositionType(forward_dir.y(), forward_dir.x());
 
            if (!is_passable(pos + side_dir) && is_passable(pos + forward_dir + side_dir)) {
                dirs_to_check.push_back(forward_dir + side_dir);
            }
 
            if (!is_passable(pos - side_dir) && is_passable(pos + forward_dir - side_dir)) {
                dirs_to_check.push_back(forward_dir - side_dir);
            }
            dirs_to_check.push_back(forward_dir);
        }
 
        for (const CellPositionType &dir : dirs_to_check) {
            CellPositionType jp = find_jump_point(pos, dir);
            if (jp != pos) fn(Node{jp, dir});
        }
    }

References Slic3r::JPSTracer< CellPositionType, CellQueryFn >::all_directions, Slic3r::JPSTracer< CellPositionType, CellQueryFn >::find_jump_point(), Slic3r::JPSTracer< CellPositionType, CellQueryFn >::Node::incoming_dir, Slic3r::JPSTracer< CellPositionType, CellQueryFn >::is_passable, and Slic3r::JPSTracer< CellPositionType, CellQueryFn >::Node::position.

Here is the call graph for this function:

goal_heuristic()

template<typename CellPositionType , typename CellQueryFn >

float Slic3r::JPSTracer< CellPositionType, CellQueryFn >::goal_heuristic ( Node  n ) const

inline

{ return n.position == target ? -1.f : (target - n.position).template cast<double>().norm(); }

References Slic3r::JPSTracer< CellPositionType, CellQueryFn >::Node::position, and Slic3r::JPSTracer< CellPositionType, CellQueryFn >::target.

is_jump_point()

template<typename CellPositionType , typename CellQueryFn >

bool Slic3r::JPSTracer< CellPositionType, CellQueryFn >::is_jump_point ( CellPositionType  pos, CellPositionType  forward_dir  ) const

inlineprivate

    {
        if (abs(forward_dir.x()) + abs(forward_dir.y()) == 2) {
            // diagonal
            CellPositionType horizontal_check_dir = CellPositionType{forward_dir.x(), 0};
            CellPositionType vertical_check_dir   = CellPositionType{0, forward_dir.y()};
 
            if (!is_passable(pos - horizontal_check_dir) && is_passable(pos + forward_dir - 2 * horizontal_check_dir)) { return true; }
 
            if (!is_passable(pos - vertical_check_dir) && is_passable(pos + forward_dir - 2 * vertical_check_dir)) { return true; }
 
            if (find_jump_point(pos, horizontal_check_dir) != pos) { return true; }
 
            if (find_jump_point(pos, vertical_check_dir) != pos) { return true; }
 
            return false;
        } else { // horizontal or vertical
            CellPositionType side_dir = CellPositionType(forward_dir.y(), forward_dir.x());
 
            if (!is_passable(pos + side_dir) && is_passable(pos + forward_dir + side_dir)) { return true; }
 
            if (!is_passable(pos - side_dir) && is_passable(pos + forward_dir - side_dir)) { return true; }
 
            return false;
        }
    }

References Slic3r::JPSTracer< CellPositionType, CellQueryFn >::find_jump_point(), and Slic3r::JPSTracer< CellPositionType, CellQueryFn >::is_passable.

Referenced by Slic3r::JPSTracer< CellPositionType, CellQueryFn >::find_jump_point().

Here is the call graph for this function:

Here is the caller graph for this function:

unique_id()

template<typename CellPositionType , typename CellQueryFn >

size_t Slic3r::JPSTracer< CellPositionType, CellQueryFn >::unique_id ( Node  n ) const

inline

    {
        return (static_cast<size_t>(uint16_t(n.position.x())) << 16) + static_cast<size_t>(uint16_t(n.position.y()));
    }

References Slic3r::JPSTracer< CellPositionType, CellQueryFn >::Node::position.

Member Data Documentation

all_directions

template<typename CellPositionType , typename CellQueryFn >

const std::vector<CellPositionType> Slic3r::JPSTracer< CellPositionType, CellQueryFn >::all_directions {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}

Referenced by Slic3r::JPSTracer< CellPositionType, CellQueryFn >::foreach_reachable().

is_passable

template<typename CellPositionType , typename CellQueryFn >

CellQueryFn Slic3r::JPSTracer< CellPositionType, CellQueryFn >::is_passable

private

Referenced by Slic3r::JPSTracer< CellPositionType, CellQueryFn >::find_jump_point(), Slic3r::JPSTracer< CellPositionType, CellQueryFn >::foreach_reachable(), and Slic3r::JPSTracer< CellPositionType, CellQueryFn >::is_jump_point().

target

template<typename CellPositionType , typename CellQueryFn >

CellPositionType Slic3r::JPSTracer< CellPositionType, CellQueryFn >::target

private

Referenced by Slic3r::JPSTracer< CellPositionType, CellQueryFn >::find_jump_point(), and Slic3r::JPSTracer< CellPositionType, CellQueryFn >::goal_heuristic().

---

The documentation for this class was generated from the following file:

• src/libslic3r/JumpPointSearch.cpp