Slic3r::AABBTreeIndirect Namespace Reference

Namespaces
namespace	detail

Classes
class	Tree
class	BoundingBoxWrapper
struct	Intersecting
struct	Intersecting< Eigen::AlignedBox< CoordType, NumD > >
struct	Within
struct	Within< Eigen::AlignedBox< CoordType, NumD > >

Typedefs
using	Tree2f = Tree<2, float>
using	Tree3f = Tree<3, float>
using	Tree2d = Tree<2, double>
using	Tree3d = Tree<3, double>

Functions
template<typename VertexType, typename IndexedFaceType>
Tree< 3, typename VertexType::Scalar >	build_aabb_tree_over_indexed_triangle_set (const std::vector< VertexType > &vertices, const std::vector< IndexedFaceType > &faces, const typename VertexType::Scalar eps=0)
template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>
bool	intersect_ray_first_hit (const std::vector< VertexType > &vertices, const std::vector< IndexedFaceType > &faces, const TreeType &tree, const VectorType &origin, const VectorType &dir, igl::Hit< float > &hit, const double eps=0.000001)
template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>
bool	intersect_ray_all_hits (const std::vector< VertexType > &vertices, const std::vector< IndexedFaceType > &faces, const TreeType &tree, const VectorType &origin, const VectorType &dir, std::vector< igl::Hit< float > > &hits, const double eps=0.000001)
template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>
VectorType::Scalar	squared_distance_to_indexed_triangle_set (const std::vector< VertexType > &vertices, const std::vector< IndexedFaceType > &faces, const TreeType &tree, const VectorType &point, size_t &hit_idx_out, Eigen::PlainObjectBase< VectorType > &hit_point_out)
template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>
bool	is_any_triangle_in_radius (const std::vector< VertexType > &vertices, const std::vector< IndexedFaceType > &faces, const TreeType &tree, const VectorType &point, typename VectorType::Scalar &max_distance_squared)
template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>
std::vector< size_t >	all_triangles_in_radius (const std::vector< VertexType > &vertices, const std::vector< IndexedFaceType > &faces, const TreeType &tree, const VectorType &point, typename VectorType::Scalar max_distance_squared)
template<typename TreeType, typename VectorType>
void	get_candidate_idxs (const TreeType &tree, const VectorType &v, std::vector< size_t > &candidates, size_t node_idx=0)
template<class G>
auto	intersecting (const G &g)
template<class G>
auto	within (const G &g)
template<int Dims, typename T, typename Predicate, typename Fn>
void	traverse (const Tree< Dims, T > &tree, Predicate &&pred, Fn &&callback)

---

Class Documentation

Slic3r::AABBTreeIndirect::Intersecting

struct Slic3r::AABBTreeIndirect::Intersecting

template<class G>
struct Slic3r::AABBTreeIndirect::Intersecting< G >

Inheritance diagram for Slic3r::AABBTreeIndirect::Intersecting< G >:

Slic3r::AABBTreeIndirect::Within

struct Slic3r::AABBTreeIndirect::Within

template<class G>
struct Slic3r::AABBTreeIndirect::Within< G >

Inheritance diagram for Slic3r::AABBTreeIndirect::Within< G >:

Typedef Documentation

Tree2d

using Slic3r::AABBTreeIndirect::Tree2d = Tree<2, double>

Tree2f

using Slic3r::AABBTreeIndirect::Tree2f = Tree<2, float>

Tree3d

using Slic3r::AABBTreeIndirect::Tree3d = Tree<3, double>

Tree3f

using Slic3r::AABBTreeIndirect::Tree3f = Tree<3, float>

Function Documentation

all_triangles_in_radius()

template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>

std::vector< size_t > Slic3r::AABBTreeIndirect::all_triangles_in_radius ( const std::vector< VertexType > & vertices, const std::vector< IndexedFaceType > & faces, const TreeType & tree, const VectorType & point, typename VectorType::Scalar max_distance_squared )

inline

{
    auto distancer = detail::IndexedTriangleSetDistancer<VertexType, IndexedFaceType, TreeType, VectorType>
            { vertices, faces, tree, point };
 
  if(tree.empty())
  {
    return {};
  }
 
  std::vector<size_t> found_triangles{};
  detail::indexed_primitives_within_distance_squared_recurisve(distancer, size_t(0), max_distance_squared, found_triangles);
  return found_triangles;
}

References Slic3r::AABBTreeIndirect::detail::indexed_primitives_within_distance_squared_recurisve().

Here is the call graph for this function:

build_aabb_tree_over_indexed_triangle_set()

template<typename VertexType, typename IndexedFaceType>

Tree< 3, typename VertexType::Scalar > Slic3r::AABBTreeIndirect::build_aabb_tree_over_indexed_triangle_set ( const std::vector< VertexType > & vertices, const std::vector< IndexedFaceType > & faces, const typename VertexType::Scalar eps = 0 )

inline

{
    using          TreeType     = Tree<3, typename VertexType::Scalar>;
//    using        CoordType      = typename TreeType::CoordType;
    using          VectorType     = typename TreeType::VectorType;
    using          BoundingBox  = typename TreeType::BoundingBox;
 
  struct InputType {
        size_t        idx()       const { return m_idx; }
        const BoundingBox&  bbox()      const { return m_bbox; }
        const VectorType&   centroid()  const { return m_centroid; }
 
    size_t    m_idx;
    BoundingBox m_bbox;
        VectorType  m_centroid;
  };
 
  std::vector<InputType> input;
  input.reserve(faces.size());
    const VectorType veps(eps, eps, eps);
  for (size_t i = 0; i < faces.size(); ++ i) {
        const IndexedFaceType &face = faces[i];
    const VertexType &v1 = vertices[face(0)];
    const VertexType &v2 = vertices[face(1)];
    const VertexType &v3 = vertices[face(2)];
    InputType n;
        n.m_idx      = i;
        n.m_centroid = (1./3.) * (v1 + v2 + v3);
        n.m_bbox = BoundingBox(v1, v1);
        n.m_bbox.extend(v2);
        n.m_bbox.extend(v3);
        n.m_bbox.min() -= veps;
        n.m_bbox.max() += veps;
        input.emplace_back(n);
  }
 
  TreeType out;
  out.build(std::move(input));
  return out;
}

Referenced by Slic3r::anonymous_namespace{TextureDisplacement.cpp}::build_texture_displacement_v2(), Slic3r::SeamPlacerImpl::compute_global_occlusion(), Slic3r::SeamPlacerImpl::gather_enforcers_blockers(), Slic3r::AABBMesh::AABBImpl::init(), Slic3r::sla::IndexedMesh::AABBImpl::init(), Slic3r::GUI::GLGizmoTextureDisplacement::prepare_mesh(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::prepare_sampleable_layers(), Slic3r::TriangleSelector::remap_painting(), Slic3r::tex2color::color_utils::remesh_mesh(), Slic3r::tex2color::repair_cluster_smooth(), Slic3r::transfer_facet_paint(), and Slic3r::transfer_uv_channel().

Here is the caller graph for this function:

get_candidate_idxs()

template<typename TreeType, typename VectorType>

void Slic3r::AABBTreeIndirect::get_candidate_idxs	(	const TreeType &	tree,
		const VectorType &	v,
		std::vector< size_t > &	candidates,
		size_t	node_idx = 0 )

{
    if (tree.empty() || ! tree.node(node_idx).bbox.contains(v))
        return;
 
    decltype(tree.node(node_idx)) node = tree.node(node_idx);
    static_assert(std::is_reference<decltype(node)>::value,
                  "Nodes shall be addressed by reference.");
    assert(node.is_valid());
    assert(node.bbox.contains(v));
 
    if (! node.is_leaf()) {
        if (tree.left_child(node_idx).bbox.contains(v))
            get_candidate_idxs(tree, v, candidates, tree.left_child_idx(node_idx));
        if (tree.right_child(node_idx).bbox.contains(v))
            get_candidate_idxs(tree, v, candidates, tree.right_child_idx(node_idx));
    } else
        candidates.push_back(node.idx);
 
    return;
}

References get_candidate_idxs().

Referenced by get_candidate_idxs().

Here is the call graph for this function:

Here is the caller graph for this function:

intersect_ray_all_hits()

template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>

bool Slic3r::AABBTreeIndirect::intersect_ray_all_hits ( const std::vector< VertexType > & vertices, const std::vector< IndexedFaceType > & faces, const TreeType & tree, const VectorType & origin, const VectorType & dir, std::vector< igl::Hit< float > > & hits, const double eps = 0.000001 )

inline

{
    auto ray_intersector = detail::RayIntersectorHits<VertexType, IndexedFaceType, TreeType, VectorType> {
        { vertices, faces, {tree},
        origin, dir, VectorType(dir.cwiseInverse()),
        eps }
  };
  if (tree.empty()) {
    hits.clear();
  } else {
    // Reusing the output memory if there is some memory already pre-allocated.
        ray_intersector.hits = std::move(hits);
        ray_intersector.hits.clear();
        ray_intersector.hits.reserve(8);
    detail::intersect_ray_recursive_all_hits(ray_intersector, 0);
    hits = std::move(ray_intersector.hits);
      std::sort(hits.begin(), hits.end(), [](const auto &l, const auto &r) { return l.t < r.t; });
  }
  return ! hits.empty();
}

References Slic3r::AABBTreeIndirect::detail::intersect_ray_recursive_all_hits().

Referenced by Slic3r::AABBMesh::AABBImpl::intersect_ray(), and Slic3r::sla::IndexedMesh::AABBImpl::intersect_ray().

Here is the call graph for this function:

Here is the caller graph for this function:

intersect_ray_first_hit()

template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>

bool Slic3r::AABBTreeIndirect::intersect_ray_first_hit ( const std::vector< VertexType > & vertices, const std::vector< IndexedFaceType > & faces, const TreeType & tree, const VectorType & origin, const VectorType & dir, igl::Hit< float > & hit, const double eps = 0.000001 )

inline

{
    using Scalar = typename VectorType::Scalar;
  auto ray_intersector = detail::RayIntersector<VertexType, IndexedFaceType, TreeType, VectorType> {
    vertices, faces, tree,
        origin, dir, VectorType(dir.cwiseInverse()),
        eps
  };
  return ! tree.empty() && detail::intersect_ray_recursive_first_hit(
        ray_intersector, size_t(0), std::numeric_limits<Scalar>::infinity(), hit);
}

References Slic3r::AABBTreeIndirect::detail::intersect_ray_recursive_first_hit().

Referenced by Slic3r::AABBMesh::AABBImpl::intersect_ray(), and Slic3r::sla::IndexedMesh::AABBImpl::intersect_ray().

Here is the call graph for this function:

Here is the caller graph for this function:

intersecting()

template<class G>

auto Slic3r::AABBTreeIndirect::intersecting

(

const G &

g

)

{ return Intersecting<G>{g}; }

Referenced by Slic3r::SeamPlacerImpl::PaintedContour::crossings(), Slic3r::SeamPlacerImpl::fully_enforced_loop(), Slic3r::SeamContour::Resolver::query(), and Slic3r::TriangleSelector::remap_painting().

Here is the caller graph for this function:

is_any_triangle_in_radius()

template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>

bool Slic3r::AABBTreeIndirect::is_any_triangle_in_radius ( const std::vector< VertexType > & vertices, const std::vector< IndexedFaceType > & faces, const TreeType & tree, const VectorType & point, typename VectorType::Scalar & max_distance_squared )

inline

{
    using Scalar = typename VectorType::Scalar;
    auto distancer = detail::IndexedTriangleSetDistancer<VertexType, IndexedFaceType, TreeType, VectorType>
            { vertices, faces, tree, point };
 
    size_t hit_idx;
    VectorType hit_point = VectorType::Ones() * (NaN<typename VectorType::Scalar>);
 
  if(tree.empty())
  {
    return false;
  }
 
  detail::squared_distance_to_indexed_primitives_recursive(distancer, size_t(0), Scalar(0), max_distance_squared, hit_idx, hit_point);
 
    return hit_point.allFinite();
}

References Slic3r::NaN, and Slic3r::AABBTreeIndirect::detail::squared_distance_to_indexed_primitives_recursive().

Referenced by Slic3r::anonymous_namespace{TextureDisplacement.cpp}::build_texture_displacement_v2(), Slic3r::SeamPlacerImpl::GlobalModelInfo::is_blocked(), and Slic3r::SeamPlacerImpl::GlobalModelInfo::is_enforced().

Here is the call graph for this function:

Here is the caller graph for this function:

squared_distance_to_indexed_triangle_set()

template<typename VertexType, typename IndexedFaceType, typename TreeType, typename VectorType>

VectorType::Scalar Slic3r::AABBTreeIndirect::squared_distance_to_indexed_triangle_set ( const std::vector< VertexType > & vertices, const std::vector< IndexedFaceType > & faces, const TreeType & tree, const VectorType & point, size_t & hit_idx_out, Eigen::PlainObjectBase< VectorType > & hit_point_out )

inline

{
    using Scalar = typename VectorType::Scalar;
    auto distancer = detail::IndexedTriangleSetDistancer<VertexType, IndexedFaceType, TreeType, VectorType>
        { vertices, faces, tree, point };
    return tree.empty() ? Scalar(-1) : 
      detail::squared_distance_to_indexed_primitives_recursive(distancer, size_t(0), Scalar(0), std::numeric_limits<Scalar>::infinity(), hit_idx_out, hit_point_out);
}

References Slic3r::AABBTreeIndirect::detail::squared_distance_to_indexed_primitives_recursive().

Referenced by Slic3r::anonymous_namespace{TextureDisplacement.cpp}::build_texture_displacement_v2(), Slic3r::anonymous_namespace{TextureDisplacement.cpp}::PatchRegion::contains(), Slic3r::AABBMesh::AABBImpl::squared_distance(), Slic3r::sla::IndexedMesh::AABBImpl::squared_distance(), and Slic3r::anonymous_namespace{TextureDisplacement.cpp}::LscmLookup::uv_at().

Here is the call graph for this function:

Here is the caller graph for this function:

traverse()

template<int Dims, typename T, typename Predicate, typename Fn>

void Slic3r::AABBTreeIndirect::traverse	(	const Tree< Dims, T > &	tree,
		Predicate &&	pred,
		Fn &&	callback )

{
    if (tree.empty()) return;
 
    detail::traverse_recurse(tree, size_t(0), std::forward<Predicate>(pred),
                             std::forward<Fn>(callback));
}

References Slic3r::AABBTreeIndirect::Tree< ANumDimensions, ACoordType >::empty(), and Slic3r::AABBTreeIndirect::detail::traverse_recurse().

Referenced by Slic3r::anonymous_namespace{ClipperUtils.cpp}::c2_attach_stray_holes(), Slic3r::connected_bodies(), Slic3r::SeamPlacerImpl::PaintedContour::crossings(), Slic3r::SeamPlacerImpl::fully_enforced_loop(), Slic3r::SeamContour::Resolver::query(), Slic3r::TriangleSelector::remap_painting(), Slic3r::Algorithm::sample_in_expolygons(), and Slic3r::RetractWhenCrossingPerimeters::travel_inside_internal_regions().

Here is the call graph for this function:

Here is the caller graph for this function:

within()

template<class G>

auto Slic3r::AABBTreeIndirect::within

(

const G &

g

)

{ return Within<G>{g}; }