#include <src/libslic3r/KDTreeIndirect.hpp>

Inheritance diagram for Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >:

Collaboration diagram for Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >:

Public Types
enum	: size_t { npos = size_t(-1) }

using	CoordinateFn = ACoordinateFn

using	CoordType = ACoordType

Public Member Functions
	KDTreeIndirect (CoordinateFn coordinate)

	KDTreeIndirect (CoordinateFn coordinate, std::vector< size_t > indices)

	KDTreeIndirect (CoordinateFn coordinate, size_t num_indices)

	KDTreeIndirect (KDTreeIndirect &&rhs)

KDTreeIndirect &	operator= (KDTreeIndirect &&rhs)

void	clear ()

void	build (size_t num_indices)

void	build (std::vector< size_t > &indices)

template<typename CoordType >
unsigned int	descent_mask (const CoordType &point_coord, const CoordType &search_radius, size_t idx, size_t dimension) const

template<typename Visitor >
void	visit (Visitor &visitor) const

Public Attributes
CoordinateFn	coordinate

Static Public Attributes
static constexpr size_t	NumDimensions = ANumDimensions

Private Member Functions
void	build_recursive (std::vector< size_t > &input, size_t node, const size_t dimension, const size_t left, const size_t right)

void	partition_input (std::vector< size_t > &input, const size_t dimension, size_t left, size_t right, const size_t k) const

template<typename Visitor >
void	visit_recursive (size_t node, size_t dimension, Visitor &visitor) const

Private Attributes
std::vector< size_t >	m_nodes

Detailed Description

template<size_t ANumDimensions, typename ACoordType, typename ACoordinateFn>
class Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >

Member Typedef Documentation

◆ CoordinateFn

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

using Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::CoordinateFn = ACoordinateFn

◆ CoordType

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

using Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::CoordType = ACoordType

Member Enumeration Documentation

◆ anonymous enum

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

anonymous enum : size_t

Enumerator
npos

         : size_t {
        npos = size_t(-1)
    };

Constructor & Destructor Documentation

◆ KDTreeIndirect() [1/4]

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::KDTreeIndirect ( CoordinateFn coordinate )

inline

33: coordinate(coordinate) {}

Slic3r::KDTreeIndirect::coordinate

CoordinateFn coordinate

Definition KDTreeIndirect.hpp:79

◆ KDTreeIndirect() [2/4]

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::KDTreeIndirect	(	CoordinateFn	coordinate,
		std::vector< size_t >	indices
	)

inline

34: coordinate(coordinate) { this->build(indices); }

Slic3r::KDTreeIndirect::build

void build(size_t num_indices)

Definition KDTreeIndirect.hpp:40

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build().

Here is the call graph for this function:

◆ KDTreeIndirect() [3/4]

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::KDTreeIndirect	(	CoordinateFn	coordinate,
		size_t	num_indices
	)

inline

35: coordinate(coordinate) { this->build(num_indices); }

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build().

Here is the call graph for this function:

◆ KDTreeIndirect() [4/4]

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::KDTreeIndirect ( KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn > && rhs )

inline

36: m_nodes(std::move(rhs.m_nodes)), coordinate(std::move(rhs.coordinate)) {}

Slic3r::KDTreeIndirect::m_nodes

std::vector< size_t > m_nodes

Definition KDTreeIndirect.hpp:189

Member Function Documentation

◆ build() [1/2]

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

void Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build ( size_t num_indices )

inline

    {
        std::vector<size_t> indices;
        indices.reserve(num_indices);
        for (size_t i = 0; i < num_indices; ++ i)
            indices.emplace_back(i);
        this->build(indices);
    }

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build().

Referenced by Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::KDTreeIndirect(), Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::KDTreeIndirect(), and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build() [2/2]

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

void Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build ( std::vector< size_t > & indices )

inline

    {
        if (indices.empty())
            clear();
        else {
            // Allocate enough memory for a full binary tree.
            m_nodes.assign(next_highest_power_of_2(indices.size() + 1), npos);
            build_recursive(indices, 0, 0, 0, indices.size() - 1);
        }
        indices.clear();
    }

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build_recursive(), Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::clear(), Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::m_nodes, Slic3r::next_highest_power_of_2(), and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::npos.

Here is the call graph for this function:

◆ build_recursive()

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

void Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build_recursive	(	std::vector< size_t > &	input,
		size_t	node,
		const size_t	dimension,
		const size_t	left,
		const size_t	right
	)

inlineprivate

    {
        if (left > right)
            return;
 
        assert(node < m_nodes.size());
 
        if (left == right) {
            // Insert a node into the balanced tree.
            m_nodes[node] = input[left];
            return;
        }
 
           // Partition the input to left / right pieces of the same length to produce a balanced tree.
        size_t center = (left + right) / 2;
        partition_input(input, dimension, left, right, center);
        // Insert a node into the tree.
        m_nodes[node] = input[center];
        // Build up the left / right subtrees.
        size_t next_dimension = dimension;
        if (++ next_dimension == NumDimensions)
            next_dimension = 0;
        if (center > left)
            build_recursive(input, node * 2 + 1, next_dimension, left, center - 1);
        build_recursive(input, node * 2 + 2, next_dimension, center + 1, right);
    }

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build_recursive(), input(), Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::m_nodes, Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::NumDimensions, and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::partition_input().

Referenced by Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build(), and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clear()

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

void Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::clear ( )

inline

38{ m_nodes.clear(); }

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::m_nodes.

Referenced by Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build().

Here is the caller graph for this function:

◆ descent_mask()

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

template<typename CoordType >

unsigned int Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::descent_mask	(	const CoordType &	point_coord,
		const CoordType &	search_radius,
		size_t	idx,
		size_t	dimension
	)		const

inline

    {
        CoordType dist = point_coord - this->coordinate(idx, dimension);
        return (dist * dist < search_radius + CoordType(EPSILON)) ?
                                                                    // The plane intersects a hypersphere centered at point_coord of search_radius.
                   ((unsigned int)(VisitorReturnMask::CONTINUE_LEFT) | (unsigned int)(VisitorReturnMask::CONTINUE_RIGHT)) :
                   // The plane does not intersect the hypersphere.
                   (dist > CoordType(0)) ? (unsigned int)(VisitorReturnMask::CONTINUE_RIGHT) : (unsigned int)(VisitorReturnMask::CONTINUE_LEFT);
    }

References Slic3r::CONTINUE_LEFT, Slic3r::CONTINUE_RIGHT, Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::coordinate, and EPSILON.

◆ operator=()

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

KDTreeIndirect & Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::operator= ( KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn > && rhs )

inline

37{ m_nodes = std::move(rhs.m_nodes); coordinate = std::move(rhs.coordinate); return *this; }

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::coordinate, and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::m_nodes.

◆ partition_input()

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

void Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::partition_input	(	std::vector< size_t > &	input,
		const size_t	dimension,
		size_t	left,
		size_t	right,
		const size_t	k
	)		const

inlineprivate

    {
        while (left < right) {
            size_t center = (left + right) / 2;
            CoordType pivot;
            {
                // Bubble sort the input[left], input[center], input[right], so that a median of the three values
                // will end up in input[center].
                CoordType left_value   = this->coordinate(input[left],   dimension);
                CoordType center_value = this->coordinate(input[center], dimension);
                CoordType right_value  = this->coordinate(input[right],  dimension);
                if (left_value > center_value) {
                    std::swap(input[left], input[center]);
                    std::swap(left_value,  center_value);
                }
                if (left_value > right_value) {
                    std::swap(input[left], input[right]);
                    right_value = left_value;
                }
                if (center_value > right_value) {
                    std::swap(input[center], input[right]);
                    center_value = right_value;
                }
                pivot = center_value;
            }
            if (right <= left + 2)
                // The <left, right> interval is already sorted.
                break;
            size_t i = left;
            size_t j = right - 1;
            std::swap(input[center], input[j]);
            // Partition the set based on the pivot.
            for (;;) {
                // Skip left points that are already at correct positions.
                // Search will certainly stop at position (right - 1), which stores the pivot.
                while (this->coordinate(input[++ i], dimension) < pivot) ;
                // Skip right points that are already at correct positions.
                while (this->coordinate(input[-- j], dimension) > pivot && i < j) ;
                if (i >= j)
                    break;
                std::swap(input[i], input[j]);
            }
            // Restore pivot to the center of the sequence.
            std::swap(input[i], input[right - 1]);
            // Which side the kth element is in?
            if (k < i)
                right = i - 1;
            else if (k == i)
                // Sequence is partitioned, kth element is at its place.
                break;
            else
                left = i + 1;
        }
    }

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::coordinate, and input().

Referenced by Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ visit()

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

template<typename Visitor >

void Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::visit ( Visitor & visitor ) const

inline

    {
        visit_recursive(0, 0, visitor);
    }

References Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::visit_recursive().

Referenced by Slic3r::find_closest_points().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ visit_recursive()

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

template<typename Visitor >

void Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::visit_recursive	(	size_t	node,
		size_t	dimension,
		Visitor &	visitor
	)		const

inlineprivate

    {
        assert(! m_nodes.empty());
        if (node >= m_nodes.size() || m_nodes[node] == npos)
            return;
 
           // Left / right child node index.
        size_t left  = node * 2 + 1;
        size_t right = left + 1;
        unsigned int mask = visitor(m_nodes[node], dimension);
        if ((mask & (unsigned int)VisitorReturnMask::STOP) == 0) {
            size_t next_dimension = (++ dimension == NumDimensions) ? 0 : dimension;
            if (mask & (unsigned int)VisitorReturnMask::CONTINUE_LEFT)
                visit_recursive(left,  next_dimension, visitor);
            if (mask & (unsigned int)VisitorReturnMask::CONTINUE_RIGHT)
                visit_recursive(right, next_dimension, visitor);
        }
    }

References Slic3r::CONTINUE_LEFT, Slic3r::CONTINUE_RIGHT, Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::m_nodes, Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::npos, Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::NumDimensions, Slic3r::STOP, and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::visit_recursive().

Referenced by Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::visit(), and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::visit_recursive().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ coordinate

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

CoordinateFn Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::coordinate

Referenced by Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::descent_mask(), Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::operator=(), and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::partition_input().

◆ m_nodes

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

std::vector<size_t> Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::m_nodes

private

Referenced by Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build(), Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build_recursive(), Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::clear(), Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::operator=(), and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::visit_recursive().

◆ NumDimensions

template<size_t ANumDimensions, typename ACoordType , typename ACoordinateFn >

constexpr size_t Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::NumDimensions = ANumDimensions

staticconstexpr

Referenced by Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::build_recursive(), and Slic3r::KDTreeIndirect< ANumDimensions, ACoordType, ACoordinateFn >::visit_recursive().

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

src/libslic3r/KDTreeIndirect.hpp

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ CoordinateFn

◆ CoordType

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ KDTreeIndirect() [1/4]

◆ KDTreeIndirect() [2/4]

◆ KDTreeIndirect() [3/4]

◆ KDTreeIndirect() [4/4]

Member Function Documentation

◆ build() [1/2]

◆ build() [2/2]

◆ build_recursive()

◆ clear()

◆ descent_mask()

◆ operator=()

◆ partition_input()

◆ visit()

◆ visit_recursive()

Member Data Documentation

◆ coordinate

◆ m_nodes

◆ NumDimensions