Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType > Class Template Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/AABBTreeIndirect.hpp>

Inheritance diagram for Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >:

Collaboration diagram for Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >:

Classes
struct	Node

Public Types
enum	: size_t { npos = size_t(-1) , inner = size_t(-2) }
using	CoordType = ACoordType
using	VectorType = Eigen::Matrix<CoordType, NumDimensions, 1, Eigen::DontAlign>
using	BoundingBox = Eigen::AlignedBox<CoordType, NumDimensions>

Public Member Functions
void	clear ()
template<typename SourceNode>
void	build (std::vector< SourceNode > &&input)
template<typename SourceNode>
void	build_modify_input (std::vector< SourceNode > &input)
const std::vector< Node > &	nodes () const
const Node &	node (size_t idx) const
bool	empty () const
const Node &	left_child (size_t idx) const
const Node &	right_child (size_t idx) const
template<typename SourceNode>
void	build (const std::vector< SourceNode > &input)

Static Public Member Functions
static size_t	left_child_idx (size_t idx)
static size_t	right_child_idx (size_t idx)

Static Public Attributes
static constexpr int	NumDimensions = ANumDimensions

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

Private Attributes
std::vector< Node >	m_nodes

Detailed Description

template<int ANumDimensions, typename ACoordType>
class Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >

Member Typedef Documentation

BoundingBox

template<int ANumDimensions, typename ACoordType>

using Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::BoundingBox = Eigen::AlignedBox<CoordType, NumDimensions>

CoordType

template<int ANumDimensions, typename ACoordType>

using Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::CoordType = ACoordType

VectorType

template<int ANumDimensions, typename ACoordType>

using Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::VectorType = Eigen::Matrix<CoordType, NumDimensions, 1, Eigen::DontAlign>

Member Enumeration Documentation

anonymous enum

template<int ANumDimensions, typename ACoordType>

anonymous enum : size_t

Enumerator
npos
inner

         : size_t {
      // Node is not used.
        npos  = size_t(-1),
        // Inner node (not leaf).
        inner = size_t(-2)
    };

Member Function Documentation

build() [1/2]

template<int ANumDimensions, typename ACoordType>

template<typename SourceNode>

void Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::build ( const std::vector< SourceNode > & input )

inline

  {
        std::vector<SourceNode> copy(input);
        this->build(std::move(copy));
  }

build() [2/2]

template<int ANumDimensions, typename ACoordType>

template<typename SourceNode>

void Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::build ( std::vector< SourceNode > && input )

inline

  {
    this->build_modify_input(input);
        input.clear();
  }

Referenced by Slic3r::AABBTreeIndirect::Tree< 2, float >::build().

Here is the caller graph for this function:

build_modify_input()

template<int ANumDimensions, typename ACoordType>

template<typename SourceNode>

void Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::build_modify_input ( std::vector< SourceNode > & input )

inline

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

Referenced by Slic3r::AABBTreeIndirect::Tree< 2, float >::build(), Slic3r::Algorithm::build_aabb_tree_over_expolygons(), and Slic3r::TreeSupport3D::merge_influence_areas().

Here is the caller graph for this function:

build_recursive()

template<int ANumDimensions, typename ACoordType>

template<typename SourceNode>

void Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::build_recursive ( std::vector< SourceNode > & input, size_t node, const size_t left, const size_t right )

inlineprivate

  {
        assert(node < m_nodes.size());
        assert(left <= right);
 
    if (left == right) {
      // Insert a node into the balanced tree.
      m_nodes[node].set(input[left]);
      return;
    }
 
    // Calculate bounding box of the input.
        BoundingBox bbox(input[left].bbox());
        for (size_t i = left + 1; i <= right; ++ i)
            bbox.extend(input[i].bbox());
        int dimension = -1;
        bbox.diagonal().maxCoeff(&dimension);
 
    // 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, size_t(dimension), left, right, center);
    // Insert an inner node into the tree. Inner node does not reference any input entity (triangle, line segment etc).
    m_nodes[node].idx  = inner;
    m_nodes[node].bbox = bbox;
        build_recursive(input, node * 2 + 1, left, center);
    build_recursive(input, node * 2 + 2, center + 1, right);
  }

Referenced by Slic3r::AABBTreeIndirect::Tree< 2, float >::build_modify_input(), and Slic3r::AABBTreeIndirect::Tree< 2, float >::build_recursive().

Here is the caller graph for this function:

clear()

template<int ANumDimensions, typename ACoordType>

void Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::clear ( )

inline

{ m_nodes.clear(); }

Referenced by Slic3r::AABBTreeIndirect::Tree< 2, float >::build_modify_input().

Here is the caller graph for this function:

empty()

template<int ANumDimensions, typename ACoordType>

bool Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::empty ( ) const

inline

{ return m_nodes.empty(); }

Referenced by Slic3r::AABBTreeIndirect::detail::intersect_triangle_epsilon(), Slic3r::GUI::anonymous_namespace{GLGizmoTextureDisplacement.cpp}::remap_texture_paint_spatial(), Slic3r::AABBTreeIndirect::traverse(), and Slic3r::Algorithm::wave_seeds().

Here is the caller graph for this function:

left_child()

template<int ANumDimensions, typename ACoordType>

const Node & Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::left_child ( size_t idx ) const

inline

{ return m_nodes[left_child_idx(idx)]; }

left_child_idx()

template<int ANumDimensions, typename ACoordType>

size_t Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::left_child_idx ( size_t idx )

inlinestatic

{ return idx * 2 + 1; }

Referenced by Slic3r::AABBTreeIndirect::Tree< 2, float >::left_child(), Slic3r::AABBTreeIndirect::Tree< 2, float >::right_child_idx(), and Slic3r::AABBTreeIndirect::detail::traverse_recurse().

Here is the caller graph for this function:

node()

template<int ANumDimensions, typename ACoordType>

const Node & Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::node ( size_t idx ) const

inline

{ return m_nodes[idx]; }

Referenced by Slic3r::AABBTreeIndirect::detail::traverse_recurse().

Here is the caller graph for this function:

nodes()

template<int ANumDimensions, typename ACoordType>

const std::vector< Node > & Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::nodes ( ) const

inline

{ return m_nodes; }

Referenced by priv::find_closest_point_index(), and Slic3r::AABBTreeIndirect::detail::intersect_triangle_epsilon().

Here is the caller graph for this function:

partition_input()

template<int ANumDimensions, typename ACoordType>

template<typename SourceNode>

void Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::partition_input ( std::vector< SourceNode > & 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   = input[left  ].centroid()(dimension);
        CoordType center_value = input[center].centroid()(dimension);
        CoordType right_value  = input[right ].centroid()(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 (input[++ i].centroid()(dimension) < pivot) ;
        // Skip right points that are already at correct positions.
        while (input[-- j].centroid()(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;
    }
  }

Referenced by Slic3r::AABBTreeIndirect::Tree< 2, float >::build_recursive().

Here is the caller graph for this function:

right_child()

template<int ANumDimensions, typename ACoordType>

const Node & Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::right_child ( size_t idx ) const

inline

{ return m_nodes[right_child_idx(idx)]; }

right_child_idx()

template<int ANumDimensions, typename ACoordType>

size_t Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::right_child_idx ( size_t idx )

inlinestatic

{ return left_child_idx(idx) + 1; }

Referenced by Slic3r::AABBTreeIndirect::Tree< 2, float >::right_child(), and Slic3r::AABBTreeIndirect::detail::traverse_recurse().

Here is the caller graph for this function:

Member Data Documentation

m_nodes

template<int ANumDimensions, typename ACoordType>

std::vector<Node> Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::m_nodes

private

NumDimensions

template<int ANumDimensions, typename ACoordType>

int Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::NumDimensions = ANumDimensions

staticconstexpr

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/AABBTreeIndirect.hpp