Slic3r::branchingtree Namespace Reference

Classes
class	Builder
struct	Node
class	PointCloud
class	Properties
struct	TraverseReturnT

Enumerations
enum	PtType {   LEAF , MESH , BED , JUNCTION ,   NONE }

Functions
void	build_tree (PointCloud &nodes, Builder &builder)
void	build_tree (const indexed_triangle_set &its, const std::vector< Node > &support_roots, Builder &builder, const Properties &properties)
ExPolygon	make_bed_poly (const indexed_triangle_set &its)
bool	is_occupied (const Node &n)
void	build_tree (const indexed_triangle_set &its, const std::vector< Node > &support_leafs, Builder &&builder, const Properties &properties={})
std::optional< Vec3f >	find_merge_pt (const Vec3f &A, const Vec3f &B, float max_slope)
void	to_eigen_mesh (const indexed_triangle_set &its, Eigen::MatrixXd &V, Eigen::MatrixXi &F)
std::vector< Node >	sample_mesh (const indexed_triangle_set &its, double radius)
std::vector< Node >	sample_bed (const ExPolygons &bed, float z, double radius)
BoundingBox3Base< Vec3f >	get_support_cone_bb (const Vec3f &p, const Properties &props)
template<class PC , class Fn >
void	traverse (PC &&pc, size_t root, Fn &&fn)
void	build_tree (PointCloud &&pc, Builder &builder)

Variables
template<class Fn >
constexpr bool	IsTraverseFn = std::is_invocable_v<Fn, Node&>

---

Class Documentation

Slic3r::branchingtree::TraverseReturnT

struct Slic3r::branchingtree::TraverseReturnT

Class Members
bool	to_left: 1
bool	to_right: 1

Enumeration Type Documentation

PtType

enum Slic3r::branchingtree::PtType

Enumerator
LEAF
MESH
BED
JUNCTION
NONE

{ LEAF, MESH, BED, JUNCTION, NONE };

Function Documentation

build_tree() [1/4]

void Slic3r::branchingtree::build_tree ( const indexed_triangle_set &  its, const std::vector< Node > &  support_leafs, Builder &&  builder, const Properties &  properties = {}  )

inline

                                                                {})
{
    build_tree(its, support_leafs, builder, properties);
}

build_tree() [2/4]

void Slic3r::branchingtree::build_tree	(	const indexed_triangle_set &	its,
		const std::vector< Node > &	support_roots,
		Builder &	builder,
		const Properties &	properties
	)

{
    PointCloud nodes(its, support_roots, properties);
 
    build_tree(nodes, builder);
}

References build_tree().

Here is the call graph for this function:

build_tree() [3/4]

void Slic3r::branchingtree::build_tree ( PointCloud &&  pc, Builder &  builder  )

inline

{
    build_tree(pc, builder);
}

References build_tree().

Here is the call graph for this function:

build_tree() [4/4]

void Slic3r::branchingtree::build_tree	(	PointCloud &	nodes,
		Builder &	builder
	)

{
    constexpr size_t initK = 5;
 
    auto ptsqueue = nodes.start_queue();
    auto &properties = nodes.properties();
 
    struct NodeDistance
    {
        size_t node_id       = Node::ID_NONE;
        float  dst_branching = NaNf;
        float  dst_euql      = NaNf;
    };
    auto distances = reserve_vector<NodeDistance>(initK);
    double prev_dist_max = 0.;
    size_t K = initK;
    bool   routed = true;
    size_t node_id = Node::ID_NONE;
 
    while ((!ptsqueue.empty() && builder.is_valid()) || !routed) {
        if (routed) {
            node_id = ptsqueue.top();
            ptsqueue.pop();
        }
 
        Node node = nodes.get(node_id);
        nodes.mark_unreachable(node_id);
 
        distances.clear();
        distances.reserve(K);
 
        float dmax = 0.;
        nodes.foreach_reachable(
            node.pos,
            [&distances, &dmax](size_t id, float dst_branching, float dst_euql) {
                distances.emplace_back(NodeDistance{id, dst_branching, dst_euql});
                dmax = std::max(dmax, dst_euql);
            }, K, prev_dist_max);
 
        std::sort(distances.begin(), distances.end(),
                  [](auto &a, auto &b) { return a.dst_branching < b.dst_branching; });
 
        if (distances.empty()) {
            builder.report_unroutable(node);
            K = initK;
            prev_dist_max = 0.;
            routed = true;
 
            continue;
        }
 
        prev_dist_max = dmax;
        K *= 2;
 
        auto closest_it = distances.begin();
        routed = false;
        while (closest_it != distances.end() && !routed && builder.is_valid()) {
            size_t closest_node_id = closest_it->node_id;
            Node closest_node = nodes.get(closest_node_id);
 
            auto type = nodes.get_type(closest_node_id);
            float w = nodes.get(node_id).weight + closest_it->dst_branching;
            closest_node.Rmin = std::max(node.Rmin, closest_node.Rmin);
 
            switch (type) {
            case BED: {
                closest_node.weight = w;
                double max_br_len   = nodes.properties().max_branch_length();
                if (closest_it->dst_branching > max_br_len) {
                    std::optional<Vec3f> avo = builder.suggest_avoidance(node, max_br_len);
                    if (!avo)
                        break;
 
                    Node new_node {*avo, node.Rmin};
                    new_node.weight = nodes.get(node_id).weight + (node.pos - *avo).norm();
                    new_node.left   = node.id;
                    if ((routed = builder.add_bridge(node, new_node))) {
                        size_t new_idx = nodes.insert_junction(new_node);
                        ptsqueue.push(new_idx);
                    }
                } else if ((routed = builder.add_ground_bridge(node, closest_node))) {
                    closest_node.left = closest_node.right = node_id;
                    nodes.get(closest_node_id) = closest_node;
                    nodes.mark_unreachable(closest_node_id);
                }
 
                break;
            }
            case MESH: {
                closest_node.weight = w;
                if ((routed = builder.add_mesh_bridge(node, closest_node))) {
                    closest_node.left = closest_node.right = node_id;
                    nodes.get(closest_node_id) = closest_node;
                    nodes.mark_unreachable(closest_node_id);
                }
 
                break;
            }
            case LEAF:
            case JUNCTION: {
                auto max_slope = float(properties.max_slope());
 
                if (auto mergept = find_merge_pt(node.pos, closest_node.pos, max_slope)) {
 
                    float mergedist_closest = (*mergept - closest_node.pos).norm();
                    float mergedist_node = (*mergept - node.pos).norm();
                    float Wnode = nodes.get(node_id).weight;
                    float Wclosest = nodes.get(closest_node_id).weight;
                    float Wsum = std::max(Wnode, Wclosest);
                    float distsum = std::max(mergedist_closest, mergedist_node);
                    w = Wsum + distsum;
 
                    if (mergedist_closest > EPSILON && mergedist_node > EPSILON) {
                        Node mergenode{*mergept, closest_node.Rmin};
                        mergenode.weight = w;
                        mergenode.id = int(nodes.next_junction_id());
 
                        if ((routed = builder.add_merger(node, closest_node, mergenode))) {
                            mergenode.left = node_id;
                            mergenode.right = closest_node_id;
                            size_t new_idx = nodes.insert_junction(mergenode);
                            ptsqueue.push(new_idx);
                            size_t qid = nodes.get_queue_idx(closest_node_id);
 
                            if (qid != PointCloud::Unqueued)
                                ptsqueue.remove(nodes.get_queue_idx(closest_node_id));
 
                            nodes.mark_unreachable(closest_node_id);
                        }
                    } else if (closest_node.pos.z() < node.pos.z() &&
                               (closest_node.left == Node::ID_NONE ||
                                closest_node.right == Node::ID_NONE)) {
                        closest_node.weight = w;
                        if ((routed = builder.add_bridge(node, closest_node))) {
                            if (closest_node.left == Node::ID_NONE)
                                closest_node.left = node_id;
                            else if (closest_node.right == Node::ID_NONE)
                                closest_node.right = node_id;
 
                            nodes.get(closest_node_id) = closest_node;
                        }
                    }
                }
 
                break;
            }
            case NONE:;
            }
 
            ++closest_it;
        }
 
        if (routed) {
            prev_dist_max = 0.;
            K = initK;
        }
    }
}

References Slic3r::branchingtree::Builder::add_bridge(), Slic3r::branchingtree::Builder::add_ground_bridge(), Slic3r::branchingtree::Builder::add_merger(), Slic3r::branchingtree::Builder::add_mesh_bridge(), BED, dmax(), EPSILON, find_merge_pt(), Slic3r::branchingtree::PointCloud::foreach_reachable(), Slic3r::branchingtree::PointCloud::get(), Slic3r::branchingtree::PointCloud::get_queue_idx(), Slic3r::branchingtree::PointCloud::get_type(), Slic3r::branchingtree::Node::ID_NONE, Slic3r::branchingtree::PointCloud::insert_junction(), Slic3r::branchingtree::Builder::is_valid(), JUNCTION, LEAF, Slic3r::branchingtree::Node::left, Slic3r::branchingtree::PointCloud::mark_unreachable(), Slic3r::branchingtree::Properties::max_branch_length(), MESH, Slic3r::NaNf, Slic3r::branchingtree::PointCloud::next_junction_id(), NONE, Slic3r::branchingtree::Node::pos, Slic3r::branchingtree::PointCloud::properties(), Slic3r::branchingtree::Builder::report_unroutable(), Slic3r::branchingtree::Node::right, Slic3r::branchingtree::Node::Rmin, Slic3r::branchingtree::PointCloud::start_queue(), Slic3r::branchingtree::Builder::suggest_avoidance(), Slic3r::branchingtree::PointCloud::Unqueued, and Slic3r::branchingtree::Node::weight.

Referenced by build_tree(), build_tree(), and Slic3r::sla::create_branching_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

find_merge_pt()

std::optional< Vec3f > Slic3r::branchingtree::find_merge_pt	(	const Vec3f &	A,
		const Vec3f &	B,
		float	max_slope
	)

{
    return sla::find_merge_pt(A, B, max_slope);
}

References Slic3r::sla::find_merge_pt().

Referenced by build_tree(), and Slic3r::branchingtree::PointCloud::get_distance().

Here is the call graph for this function:

Here is the caller graph for this function:

get_support_cone_bb()

BoundingBox3Base< Vec3f > Slic3r::branchingtree::get_support_cone_bb ( const Vec3f &  p, const Properties &  props  )

inline

{
    double gnd = props.ground_level() - EPSILON;
    double h   = p.z() - gnd;
    double phi = PI / 2 - props.max_slope();
    auto   r   = float(std::min(h * std::tan(phi), props.max_branch_length() * std::sin(phi)));
 
    Vec3f bb_min = {p.x() - r, p.y() - r, float(gnd)};
    Vec3f bb_max = {p.x() + r, p.y() + r, p.z()};
 
    return {bb_min, bb_max};
}

References EPSILON, Slic3r::branchingtree::Properties::ground_level(), Slic3r::branchingtree::Properties::max_branch_length(), Slic3r::branchingtree::Properties::max_slope(), and PI.

Here is the call graph for this function:

is_occupied()

bool Slic3r::branchingtree::is_occupied ( const Node &  n )

inline

{
    return n.left != Node::ID_NONE && n.right != Node::ID_NONE;
}

References Slic3r::branchingtree::Node::ID_NONE, Slic3r::branchingtree::Node::left, and Slic3r::branchingtree::Node::right.

make_bed_poly()

ExPolygon Slic3r::branchingtree::make_bed_poly

(

const indexed_triangle_set &

its

)

{
    auto bb = bounding_box(its);
 
    BoundingBox bbcrd{scaled(to_2d(bb.min)), scaled(to_2d(bb.max))};
    bbcrd.offset(scaled(10.));
    Point     min = bbcrd.min, max = bbcrd.max;
    ExPolygon ret = {{min.x(), min.y()},
                     {max.x(), min.y()},
                     {max.x(), max.y()},
                     {min.x(), max.y()}};
 
    return ret;
}

References Slic3r::bounding_box(), make_bed_poly(), Slic3r::BoundingBoxBase< PointType, APointsType >::offset(), Slic3r::scaled(), Slic3r::to_2d(), and Eigen::half_impl::__half_raw::x.

Referenced by Slic3r::sla::create_branching_tree(), and make_bed_poly().

Here is the call graph for this function:

Here is the caller graph for this function:

sample_bed()

std::vector< Node > Slic3r::branchingtree::sample_bed	(	const ExPolygons &	bed,
		float	z,
		double	radius
	)

{
    auto triangles = triangulate_expolygons_3d(bed, z);
    indexed_triangle_set its;
    its.vertices.reserve(triangles.size());
 
    for (size_t i = 0; i < triangles.size(); i += 3) {
        its.vertices.emplace_back(triangles[i].cast<float>());
        its.vertices.emplace_back(triangles[i + 1].cast<float>());
        its.vertices.emplace_back(triangles[i + 2].cast<float>());
 
        its.indices.emplace_back(i, i + 1, i + 2);
    }
 
    return sample_mesh(its, radius);
}

References indexed_triangle_set::indices, sample_mesh(), Slic3r::triangulate_expolygons_3d(), and indexed_triangle_set::vertices.

Referenced by Slic3r::sla::create_branching_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

sample_mesh()

std::vector< Node > Slic3r::branchingtree::sample_mesh	(	const indexed_triangle_set &	its,
		double	radius
	)

{
    std::vector<Node> ret;
 
    double surface_area = 0.;
    for (const Vec3i &face : its.indices) {
        std::array<Vec3f, 3> tri = {its.vertices[face(0)],
                                    its.vertices[face(1)],
                                    its.vertices[face(2)]};
 
        auto U = tri[1] - tri[0], V = tri[2] - tri[0];
        surface_area += 0.5 * U.cross(V).norm();
    }
 
    int N = surface_area / (PI * radius * radius);
 
    Eigen::MatrixXd B;
    Eigen::MatrixXi FI;
    Eigen::MatrixXd V;
    Eigen::MatrixXi F;
    to_eigen_mesh(its, V, F);
    igl::random_points_on_mesh(N, V, F, B, FI);
 
    ret.reserve(size_t(N));
    for (int i = 0; i < FI.size(); i++) {
        int face_id = FI(i);
 
        if (face_id < 0 || face_id >= int(its.indices.size()))
            continue;
 
        Vec3i face = its.indices[face_id];
 
        if (face(0) >= int(its.vertices.size()) ||
            face(1) >= int(its.vertices.size()) ||
            face(2) >= int(its.vertices.size()))
            continue;
 
        Vec3f c = B.row(i)(0) * its.vertices[face(0)] +
                  B.row(i)(1) * its.vertices[face(1)] +
                  B.row(i)(2) * its.vertices[face(2)];
 
        ret.emplace_back(c);
    }
 
    return ret;
}

References Slic3r::F, indexed_triangle_set::indices, PI, igl::random_points_on_mesh(), to_eigen_mesh(), and indexed_triangle_set::vertices.

Referenced by Slic3r::sla::create_branching_tree(), and sample_bed().

Here is the call graph for this function:

Here is the caller graph for this function:

to_eigen_mesh()

void Slic3r::branchingtree::to_eigen_mesh	(	const indexed_triangle_set &	its,
		Eigen::MatrixXd &	V,
		Eigen::MatrixXi &	F
	)

{
    V.resize(its.vertices.size(), 3);
    F.resize(its.indices.size(), 3);
    for (unsigned int i = 0; i < its.indices.size(); ++i)
        F.row(i) = its.indices[i];
 
    for (unsigned int i = 0; i < its.vertices.size(); ++i)
        V.row(i) = its.vertices[i].cast<double>();
}

References Slic3r::F, indexed_triangle_set::indices, and indexed_triangle_set::vertices.

Referenced by sample_mesh().

Here is the caller graph for this function:

traverse()

template<class PC , class Fn >

void Slic3r::branchingtree::traverse	(	PC &&	pc,
		size_t	root,
		Fn &&	fn
	)

{
    if (auto nodeptr = pc.find(root); nodeptr != nullptr) {
        auto &nroot = *nodeptr;
        TraverseReturnT ret{true, true};
 
        if constexpr (std::is_same_v<std::invoke_result_t<Fn, decltype(nroot)>, void>) {
            // Our fn has no return value
            fn(nroot);
        } else {
            // Fn returns instructions about how to continue traversing
            ret = fn(nroot);
        }
 
        if (ret.to_left && nroot.left >= 0)
            traverse(pc, nroot.left, fn);
        if (ret.to_right && nroot.right >= 0)
            traverse(pc, nroot.right, fn);
    }
}

References traverse().

Referenced by traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

IsTraverseFn

template<class Fn >

constexpr bool Slic3r::branchingtree::IsTraverseFn = std::is_invocable_v<Fn, Node&>

constexpr