Slic3r::TreeSupport Class Reference

Generates a tree structure to support your models. More...

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

Collaboration diagram for Slic3r::TreeSupport:

Public Types
enum	OverhangType { Detected = 0 , Enforced , SharpTail }

Public Member Functions
	TreeSupport (PrintObject &object, const SlicingParameters &slicing_params)
	Creates an instance of the tree support generator.
void	move_bounds_to_contact_nodes (std::vector< TreeSupport3D::SupportElements > &move_bounds, PrintObject &print_object, const TreeSupport3D::TreeSupportSettings &config)
void	generate ()
	Create the areas that need support.
void	detect_overhangs (bool check_support_necessity=false)
SupportNode *	create_node (const Point position, const int distance_to_top, const int obj_layer_nr, const int support_roof_layers_below, const bool to_buildplate, SupportNode *parent, coordf_t print_z_, coordf_t height_, coordf_t dist_mm_to_top_=0, coordf_t radius_=0)

Public Attributes
int	avg_node_per_layer = 0
float	nodes_angle = 0
bool	has_sharp_tails = false
bool	has_cantilever = false
double	max_cantilever_dist = 0
SupportType	support_type
std::unique_ptr< FillLightning::Generator >	generator
std::unordered_map< double, size_t >	printZ_to_lightninglayer
std::function< void()>	throw_on_cancel
const PrintConfig *	m_print_config
ExPolygon	m_machine_border
	Polygons representing the limits of the printable area of the machine.
std::map< const ExPolygon *, OverhangType >	overhang_types
std::vector< std::pair< Vec3f, Vec3f > >	m_vertical_enforcer_points

Private Member Functions
double	belt_floor_print_z (const Point &pos_slicing) const
bool	belt_node_landed (const Point &pos_slicing, double radius, double print_z) const
bool	belt_polygon_landed (const ExPolygon &poly, double print_z) const
void	draw_circles ()
	Draws circles around each node of the tree into the final support.
void	drop_nodes ()
	Drops down the nodes of the tree support towards the build plate.
void	smooth_nodes ()
std::vector< LayerHeightData >	plan_layer_heights ()
	Optimize the generation of tree support by pre-planning the layer_heights.
void	generate_contact_points ()
	Creates points where support contacts the model.
void	insert_dropped_node (std::vector< SupportNode * > &nodes_layer, SupportNode *node)
	Add a node to the next layer.
void	create_tree_support_layers ()
void	generate_toolpaths ()
coordf_t	calc_branch_radius (coordf_t base_radius, size_t layers_to_top, size_t tip_layers, double diameter_angle_scale_factor)
coordf_t	calc_branch_radius (coordf_t base_radius, coordf_t mm_to_top, double diameter_angle_scale_factor, bool use_min_distance=true)
coordf_t	calc_radius (coordf_t mm_to_top)
coordf_t	get_radius (const SupportNode *node)
const ExPolygons &	get_avoidance (coordf_t radius, size_t obj_layer_nr)
const ExPolygons &	get_collision (coordf_t radius, size_t layer_nr)
Polygons	get_collision_polys (coordf_t radius, size_t layer_nr)
Polygons	get_trim_support_regions (const PrintObject &object, SupportLayer *support_layer_ptr, const coordf_t gap_extra_above, const coordf_t gap_extra_below, const coordf_t gap_xy)

Private Attributes
std::vector< std::vector< SupportNode * > >	contact_nodes
	Generator for model collision, avoidance and internal guide volumes.
std::shared_ptr< TreeSupportData >	m_ts_data
std::unique_ptr< TreeSupport3D::TreeModelVolumes >	m_model_volumes
PrintObject *	m_object
const PrintObjectConfig *	m_object_config
SlicingParameters	m_slicing_params
SupportParameters	m_support_params
size_t	m_raft_layers = 0
size_t	m_highest_overhang_layer = 0
std::vector< std::vector< MinimumSpanningTree > >	m_spanning_trees
std::vector< std::unordered_map< Line, bool, LineHash > >	m_mst_line_x_layer_contour_caches
coordf_t	base_radius = 0.0
const coordf_t	MAX_BRANCH_RADIUS = 10.0
const coordf_t	MIN_BRANCH_RADIUS = 0.4
const coordf_t	MAX_BRANCH_RADIUS_FIRST_LAYER = 12.0
const coordf_t	MIN_BRANCH_RADIUS_FIRST_LAYER = 2.0
double	diameter_angle_scale_factor = tan(5.0*M_PI/180.0)
const double	minimum_roof_area {SQ(scaled<double>(1.))}
float	top_z_distance = 0.0
bool	is_strong = false
bool	is_slim = false
bool	with_infill = false

Detailed Description

Generates a tree structure to support your models.

Member Enumeration Documentation

OverhangType

enum Slic3r::TreeSupport::OverhangType

Enumerator
Detected
Enforced
SharpTail

{ Detected = 0, Enforced, SharpTail };

Constructor & Destructor Documentation

TreeSupport()

Slic3r::TreeSupport::TreeSupport	(	PrintObject &	object,
		const SlicingParameters &	slicing_params )

Creates an instance of the tree support generator.

Parameters

storage

The data storage to get global settings from.

    : m_object(&object), m_slicing_params(slicing_params), m_support_params(object), m_object_config(&object.config())
{
    m_print_config = &m_object->print()->config();
    m_raft_layers = slicing_params.base_raft_layers + slicing_params.interface_raft_layers;
    support_type = m_object_config->support_type;
 
    SupportMaterialPattern support_pattern  = m_object_config->support_base_pattern;
    if (m_support_params.support_style == smsTreeHybrid && support_pattern == smpDefault)
        support_pattern = smpRectilinear;
 
    if(support_pattern == smpLightning)
        m_support_params.base_fill_pattern = ipLightning;
    diameter_angle_scale_factor              = std::clamp<double>(m_object_config->tree_support_branch_diameter_angle * M_PI / 180., 0., 0.5 * M_PI - EPSILON);
    is_slim                                  = is_tree_slim(support_type, m_support_params.support_style);
    is_strong = is_tree(support_type) && m_support_params.support_style == smsTreeStrong;
    base_radius                              = std::max(MIN_BRANCH_RADIUS, m_object_config->tree_support_branch_diameter.value / 2);
    // by default tree support needs no infill, unless it's tree hybrid which contains normal nodes.
    with_infill                              = support_pattern != smpNone && support_pattern != smpDefault;
    m_machine_border.contour = get_bed_shape_with_excluded_area(*m_print_config);
    Vec3d plate_offset       = m_object->print()->get_plate_origin();
    // align with the centered object in current plate (may not be the 1st plate, so need to add the plate offset)
    m_machine_border.translate(Point(scale_(plate_offset(0)), scale_(plate_offset(1))) - m_object->instances().front().shift);
    top_z_distance                            = m_object_config->support_top_z_distance.value;
    if (top_z_distance > EPSILON) top_z_distance = std::max(top_z_distance, float(m_slicing_params.min_layer_height));
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
    SVG svg(debug_out_path("machine_boarder.svg"), m_object->bounding_box());
    if (svg.is_opened()) svg.draw(m_machine_border, "yellow");
#endif
}

References base_radius, Slic3r::SlicingParameters::base_raft_layers, Slic3r::debug_out_path(), diameter_angle_scale_factor, Slic3r::SVG::draw(), EPSILON, Slic3r::get_bed_shape_with_excluded_area(), Slic3r::SlicingParameters::interface_raft_layers, Slic3r::ipLightning, is_slim, is_strong, Slic3r::is_tree(), Slic3r::is_tree_slim(), m_machine_border, m_object, m_object_config, M_PI, m_print_config, m_raft_layers, m_slicing_params, m_support_params, MIN_BRANCH_RADIUS, scale_, Slic3r::smpDefault, Slic3r::smpLightning, Slic3r::smpNone, Slic3r::smpRectilinear, Slic3r::smsTreeHybrid, Slic3r::smsTreeStrong, support_type, top_z_distance, and with_infill.

Here is the call graph for this function:

Member Function Documentation

belt_floor_print_z()

double Slic3r::TreeSupport::belt_floor_print_z ( const Point & pos_slicing ) const

private

{
    BeltFloorContext ctx;
    if (!ctx.init(m_slicing_params, *m_print_config))
        return -std::numeric_limits<double>::infinity();
    return ctx.floor_print_z(pos_slicing);
}

References Slic3r::BeltFloorContext::floor_print_z(), Slic3r::BeltFloorContext::init(), m_print_config, and m_slicing_params.

Here is the call graph for this function:

belt_node_landed()

bool Slic3r::TreeSupport::belt_node_landed ( const Point & pos_slicing, double radius, double print_z ) const

private

{
    BeltFloorContext ctx;
    if (!ctx.init(m_slicing_params, *m_print_config))
        return false;
    return print_z <= ctx.floor_print_z(pos_slicing) - std::abs(ctx.shear_factor()) * std::max(0., radius);
}

References Slic3r::BeltFloorContext::floor_print_z(), Slic3r::BeltFloorContext::init(), m_print_config, m_slicing_params, and Slic3r::BeltFloorContext::shear_factor().

Here is the call graph for this function:

belt_polygon_landed()

bool Slic3r::TreeSupport::belt_polygon_landed ( const ExPolygon & poly, double print_z ) const

private

{
    BeltFloorContext ctx;
    if (!ctx.init(m_slicing_params, *m_print_config))
        return false;
    double min_floor = std::numeric_limits<double>::max();
    for (const Point &pt : poly.contour.points)
        min_floor = std::min(min_floor, ctx.floor_print_z(pt));
    return print_z <= min_floor;
}

References Slic3r::BeltFloorContext::floor_print_z(), Slic3r::BeltFloorContext::init(), m_print_config, and m_slicing_params.

Here is the call graph for this function:

calc_branch_radius() [1/2]

coordf_t Slic3r::TreeSupport::calc_branch_radius ( coordf_t base_radius, coordf_t mm_to_top, double diameter_angle_scale_factor, bool use_min_distance = true )

private

{
    double radius;
    coordf_t tip_height = base_radius;// this is a 45 degree tip
    if (mm_to_top > tip_height)
    {
        radius = base_radius + (mm_to_top-tip_height) * diameter_angle_scale_factor;
    }
    else
    {
        radius = mm_to_top;// this is a 45 degree tip
    }
    radius = std::clamp(radius, MIN_BRANCH_RADIUS, MAX_BRANCH_RADIUS);
    // if have interface layers, radius should be larger
    if (m_object_config->support_interface_top_layers.value > 0)
        radius = std::max(radius, base_radius);
    return radius;
}

References base_radius, calc_branch_radius(), diameter_angle_scale_factor, m_object_config, MAX_BRANCH_RADIUS, and MIN_BRANCH_RADIUS.

Here is the call graph for this function:

calc_branch_radius() [2/2]

coordf_t Slic3r::TreeSupport::calc_branch_radius ( coordf_t base_radius, size_t layers_to_top, size_t tip_layers, double diameter_angle_scale_factor )

private

{
    double radius;
    if (!is_slim) {
        if ((layers_to_top + 1) > tip_layers) {
            radius = base_radius + base_radius * (layers_to_top + 1) * diameter_angle_scale_factor;
        } else {
            radius = base_radius * (layers_to_top + 1) / tip_layers;
        }
    } else {
        if ((layers_to_top + 1) > tip_layers * 2) {
            radius = base_radius + base_radius * (layers_to_top + 1) * diameter_angle_scale_factor;
        } else {
            radius = base_radius * (layers_to_top + 1) / (tip_layers * 2);
        }
    }
    radius = std::clamp(radius, MIN_BRANCH_RADIUS, MAX_BRANCH_RADIUS);
    return radius;
}

References base_radius, calc_branch_radius(), diameter_angle_scale_factor, is_slim, MAX_BRANCH_RADIUS, and MIN_BRANCH_RADIUS.

Referenced by calc_branch_radius(), calc_branch_radius(), and calc_radius().

Here is the call graph for this function:

Here is the caller graph for this function:

calc_radius()

coordf_t Slic3r::TreeSupport::calc_radius ( coordf_t mm_to_top )

private

{
    return calc_branch_radius(base_radius, mm_to_top, diameter_angle_scale_factor);
}

References base_radius, calc_branch_radius(), calc_radius(), and diameter_angle_scale_factor.

Referenced by calc_radius(), drop_nodes(), and get_radius().

Here is the call graph for this function:

Here is the caller graph for this function:

create_node()

SupportNode * Slic3r::TreeSupport::create_node ( const Point position, const int distance_to_top, const int obj_layer_nr, const int support_roof_layers_below, const bool to_buildplate, SupportNode * parent, coordf_t print_z_, coordf_t height_, coordf_t dist_mm_to_top_ = 0, coordf_t radius_ = 0 )

inline

    {
        return m_ts_data->create_node(position, distance_to_top, obj_layer_nr, support_roof_layers_below, to_buildplate, parent, print_z_, height_, dist_mm_to_top_, radius_);
    }

References m_ts_data.

Referenced by move_bounds_to_contact_nodes().

Here is the caller graph for this function:

create_tree_support_layers()

void Slic3r::TreeSupport::create_tree_support_layers ( )

private

{
    int layer_id = 0;
    if (m_raft_layers > 0) { //create raft layers
        coordf_t raft_print_z = 0.f;
        coordf_t raft_slice_z = 0.f;
        {
            // Do not add the raft contact layer, 1st layer should use first_print_layer_height
            coordf_t height = m_slicing_params.first_print_layer_height;
            raft_print_z += height;
            raft_slice_z = raft_print_z - height / 2;
            m_object->add_tree_support_layer(layer_id++, height, raft_print_z, raft_slice_z);
        }
        // Insert the base layers.
        for (size_t i = 1; i < m_slicing_params.base_raft_layers; i++) {
            coordf_t height = m_slicing_params.base_raft_layer_height;
            raft_print_z += height;
            raft_slice_z = raft_print_z - height / 2;
            m_object->add_tree_support_layer(layer_id++, height, raft_print_z, raft_slice_z);
        }
        // Insert the interface layers.
        for (size_t i = 0; i < m_slicing_params.interface_raft_layers; i++) {
            coordf_t height = m_slicing_params.interface_raft_layer_height;
            raft_print_z += height;
            raft_slice_z = raft_print_z - height / 2;
            m_object->add_tree_support_layer(layer_id++, height, raft_print_z, raft_slice_z);
        }
 
        // Layers between the raft contacts and bottom of the object.
        double dist_to_go = m_slicing_params.object_print_z_min - raft_print_z;
        // ORCA: Guard tiny residual raft-to-object gaps so the EPSILON-biased ceil()
        // below cannot turn them into zero steps after floating-point accumulation.
        if (dist_to_go > EPSILON) {
            // ORCA: Bias by EPSILON so near-equal gaps do not get an extra split from FP noise.
            auto nsteps = int(ceil((dist_to_go - EPSILON) / m_slicing_params.max_suport_layer_height));
            double height = dist_to_go / nsteps;
            for (int i = 0; i < nsteps; ++i) {
                raft_print_z += height;
                raft_slice_z = raft_print_z - height / 2;
                m_object->add_tree_support_layer(layer_id++, height, raft_print_z, raft_slice_z);
            }
        }
        m_raft_layers = layer_id;
    }
}

References create_tree_support_layers(), EPSILON, m_object, m_raft_layers, and m_slicing_params.

Referenced by create_tree_support_layers(), and generate().

Here is the call graph for this function:

Here is the caller graph for this function:

detect_overhangs()

void Slic3r::TreeSupport::detect_overhangs

(

bool

check_support_necessity = false

)

{
    bool tree_support_enable = m_object_config->enable_support.value && is_tree(m_object_config->support_type.value);
    if (!tree_support_enable && !check_support_necessity) {
        BOOST_LOG_TRIVIAL(info) << "Tree support is disabled.";
        return;
    }
 
    // Clear and create Tree Support Layers
    m_object->clear_support_layers();
    m_object->clear_tree_support_preview_cache();
 
    const PrintObjectConfig& config = m_object->config();
    SupportType stype = support_type;
    const coordf_t radius_sample_resolution = g_config_tree_support_collision_resolution;
    const double nozzle_diameter = m_object->print()->config().nozzle_diameter.get_at(0);
    const coordf_t extrusion_width = config.get_abs_value("line_width", nozzle_diameter);
    const coordf_t extrusion_width_scaled = scale_(extrusion_width);
    const coordf_t max_bridge_length = scale_(config.max_bridge_length.value);
    const bool bridge_no_support = max_bridge_length > 0;
    const bool support_critical_regions_only = config.support_critical_regions_only.value;
    bool config_remove_small_overhangs = config.support_remove_small_overhang.value;
    bool config_detect_sharp_tails = g_config_support_sharp_tails;
    const int enforce_support_layers = config.enforce_support_layers.value;
    const double area_thresh_well_supported = SQ(scale_(6));
    const double length_thresh_well_supported = scale_(6);
    static const double sharp_tail_max_support_height = 16.f;
    // a region is considered well supported if the number of layers below it exceeds this threshold
    const int thresh_layers_below = 10 / config.layer_height;
    // +1 makes the threshold inclusive
    double thresh_angle = config.support_threshold_angle.value > EPSILON ? config.support_threshold_angle.value + 1 : 30;
    thresh_angle = std::min(thresh_angle, 89.); // should be smaller than 90
    const double threshold_rad = Geometry::deg2rad(thresh_angle);
    // Build plate tilt: compute per-layer XY shift for tilted gravity direction
    const PrintConfig& print_cfg = m_object->print()->config();
    const Vec2d  tilt_slope = build_plate_tilt_slope(print_cfg);
    const bool   has_tilt   = tilt_slope.cwiseAbs().maxCoeff() > EPSILON;
 
    // Belt printers: the object is pre-rotated by the belt angle before slicing, so a wall
    // that is vertical in the world advances by one layer height per layer in the sliced
    // frame. The build-plate tilt shift above compensates for that, but its direction has to
    // follow the belt shear -- the sign and axis are already known exactly from the slicing
    // parameters, so take them from there rather than from tan(build_plate_tilt), which
    // carries a magnitude but no direction. Non-belt tilted beds keep the existing behaviour.
    BeltFloorContext ovh_belt_ctx;
    const bool belt_ovh_active = ovh_belt_ctx.init(m_slicing_params, print_cfg);
    const double belt_shear    = ovh_belt_ctx.shear_factor();
    const int    belt_axis     = ovh_belt_ctx.from_axis();
    // FIXME this is a fudge constant!
    double support_tree_tip_diameter = 0.8;
    auto   enforcer_overhang_offset  = scaled<double>(support_tree_tip_diameter);
 
    // for small overhang removal
    struct OverhangCluster {
        std::map<int, const ExPolygon*> layer_overhangs;
        ExPolygons merged_poly;
        BoundingBox merged_bbox;
        int min_layer = 1e7;
        int max_layer = 0;
        coordf_t offset = 0;
        bool is_cantilever = false;
        bool is_sharp_tail = false;
        bool is_small_overhang = false;
        OverhangCluster(const ExPolygon* expoly, int layer_nr) {
            push_back(expoly, layer_nr);
        }
        void push_back(const ExPolygon* expoly, int layer_nr) {
            layer_overhangs.emplace(layer_nr, expoly);
            auto dilate1 = offset_ex(*expoly, offset);
            if (!dilate1.empty())
                merged_poly = union_ex(merged_poly, dilate1);
            min_layer = std::min(min_layer, layer_nr);
            max_layer = std::max(max_layer, layer_nr);
            merged_bbox.merge(get_extents(dilate1));
        }
        int height() {
            return max_layer - min_layer + 1;
        }
        bool intersects(const ExPolygon& region, int layer_nr, coordf_t offset) {
            if (layer_nr < 1) return false;
            auto it = layer_overhangs.find(layer_nr - 1);
            if (it == layer_overhangs.end()) return false;
            const ExPolygon* overhang = it->second;
 
            this->offset = offset;
            auto dilate1 = offset_ex(region, offset);
            BoundingBox bbox = get_extents(dilate1);
            if (!merged_bbox.overlap(bbox))
                return false;
            return overlaps({ *overhang }, dilate1);
        }
        // it's basically the combination of push_back and intersects, but saves an offset_ex
        bool push_back_if_intersects(const ExPolygon& region, int layer_nr, coordf_t offset) {
            bool is_intersect = false;
            ExPolygons dilate1;
            BoundingBox bbox;
            do {
                if (layer_nr < 1) break;
                auto it = layer_overhangs.find(layer_nr - 1);
                if (it == layer_overhangs.end()) break;
                const ExPolygon* overhang = it->second;
 
                this->offset = offset;
                dilate1 = offset_ex(region, offset);
                if (dilate1.empty()) break;
                bbox = get_extents(dilate1);
                if (!merged_bbox.overlap(bbox))
                    break;
                is_intersect = overlaps({ *overhang }, dilate1);
            } while (0);
            if (is_intersect) {
                layer_overhangs.emplace(layer_nr, &region);
                merged_poly = union_ex(merged_poly, dilate1);
                min_layer = std::min(min_layer, layer_nr);
                max_layer = std::max(max_layer, layer_nr);
                merged_bbox.merge(bbox);
            }
            return is_intersect;
        }
    };
    std::vector<OverhangCluster> overhangClusters;
 
    auto find_and_insert_cluster = [](auto &regionClusters, const ExPolygon &region, int layer_nr, coordf_t offset) {
        OverhangCluster *cluster = nullptr;
        for (int i = 0; i < regionClusters.size(); i++) {
            auto cluster_i = &regionClusters[i];
            if (cluster_i->push_back_if_intersects(region, layer_nr, offset)) {
                cluster = cluster_i;
                break;
            }
        }
        if (!cluster) {
            cluster = &regionClusters.emplace_back(&region, layer_nr);
        }
        return cluster;
    };
 
    if (!is_tree(stype)) return;
 
    max_cantilever_dist = 0;
    m_highest_overhang_layer = 0;
 
    // calc the extrudable expolygons of each layer
    tbb::parallel_for(tbb::blocked_range<size_t>(0, m_object->layer_count()),
        [&](const tbb::blocked_range<size_t>& range) {
            for (size_t layer_nr = range.begin(); layer_nr < range.end(); layer_nr++) {
                if (m_object->print()->canceled())
                    break;
                Layer* layer = m_object->get_layer(layer_nr);
                // Filter out areas whose diameter that is smaller than extrusion_width, but we don't want to lose any details.
                layer->lslices_extrudable = intersection_ex(layer->lslices, offset2_ex(layer->lslices, -extrusion_width_scaled / 2, extrusion_width_scaled));
                layer->loverhangs.clear();
            }
        });
 
    typedef std::chrono::high_resolution_clock clock_;
    typedef std::chrono::duration<double, std::ratio<1> > second_;
    std::chrono::time_point<clock_> t0{ clock_::now() };
    // main part of overhang detection can be parallel
    tbb::concurrent_vector<ExPolygons> overhangs_all_layers(m_object->layer_count());
    tbb::parallel_for(tbb::blocked_range<size_t>(0, m_object->layer_count()),
        [&](const tbb::blocked_range<size_t>& range) {
            for (size_t layer_nr = range.begin(); layer_nr < range.end(); layer_nr++) {
                if (m_object->print()->canceled())
                    break;
 
                if (!is_auto(stype) && layer_nr > enforce_support_layers)
                    continue;
 
                Layer* layer = m_object->get_layer(layer_nr);
 
                if (layer->lower_layer == nullptr) {
                    for (auto& slice : layer->lslices_extrudable) {
                        auto bbox_size = get_extents(slice).size();
                        if (!((bbox_size.x() > length_thresh_well_supported && bbox_size.y() > length_thresh_well_supported))
                            && g_config_support_sharp_tails) {
                            layer->sharp_tails.push_back(slice);
                            layer->sharp_tails_height.push_back(layer->height);
                        }
                    }
                    continue;
                }
 
                Layer* lower_layer = layer->lower_layer;
                coordf_t lower_layer_offset = layer_nr < enforce_support_layers ? -0.15 * extrusion_width : (float)lower_layer->height / tan(threshold_rad);
                //lower_layer_offset = std::min(lower_layer_offset, extrusion_width);
                coordf_t support_offset_scaled = scale_(lower_layer_offset);
                ExPolygons& curr_polys = layer->lslices_extrudable;
                ExPolygons& lower_polys = lower_layer->lslices_extrudable;
 
                // Apply build plate tilt: shift lower layer polygons to simulate tilted gravity
                //
                // On a belt the object's very first slice can come out empty (the bottom
                // vertex is a sub-extrudable sliver), leaving the layer above it with an
                // empty predecessor even though it rests on the belt. That case needs no
                // special handling here: the belt surface is unioned into effective_lower
                // below and sampled at the bottom of the layer, so a contacting island is
                // covered and a genuinely floating one still reports its overhang. Doing it
                // that way keeps the decision per-island -- an earlier whole-layer skip,
                // conditioned on the nearest point of the *union* of the cross-section,
                // let one contacting island silence a separate floating one.
                ExPolygons shifted_lower;
                if (belt_ovh_active || has_tilt) {
                    shifted_lower = lower_polys; // copy
                    const double lh = lower_layer->height;
                    Point tilt_shift(0, 0);
                    if (belt_ovh_active) {
                        // Advance the lower layer along the belt by exactly the amount a
                        // world-vertical wall moves per layer, so such a wall stops reading
                        // as an overhang. Sign comes from the shear, not from a tilt angle.
                        const coord_t d = coord_t(-scale_(lh * belt_shear));
                        if (belt_axis == 0) tilt_shift.x() = d; else tilt_shift.y() = d;
                    } else {
                        tilt_shift = Point::new_scale(tilt_slope * lh);
                    }
                    translate(shifted_lower, tilt_shift);
                }
                ExPolygons effective_lower = (belt_ovh_active || has_tilt) ? shifted_lower : lower_polys;
 
                // Belt printers: material resting on the belt is held up by the belt, not by
                // the layer below it, so the belt surface counts as support from underneath.
                // Without this the object's belt-contact face reads as a fresh overhang on
                // every layer -- the leading strip that produced the spurious support nub.
                if (belt_ovh_active) {
                    // surface_polygon() is a +/-1000mm half-plane. Unioning that raw with
                    // 20mm-scale geometry and then offsetting it puts a huge dynamic range
                    // through Clipper, which left intermittent artefacts every few layers.
                    // Clip it to the layer's own bounding box first.
                    // Evaluate the belt surface at the BOTTOM of the layer, not its top:
                    // a layer meets the belt across its whole thickness, and print_z is the
                    // top. On the object's first layer -- which is thicker, and whose lower
                    // layer is empty -- using print_z left the leading 0.37mm uncovered and
                    // produced the one remaining spurious overhang.
                    Polygons belt_surface = ovh_belt_ctx.surface_polygon(layer->print_z - layer->height);
                    if (! belt_surface.empty()) {
                        BoundingBox clip_bb = get_extents(curr_polys);
                        clip_bb.merge(get_extents(lower_polys));
                        clip_bb.offset(scale_(10.));
                        belt_surface = intersection(belt_surface, Polygons{ clip_bb.polygon() });
                        if (! belt_surface.empty()) {
                            append(effective_lower, union_ex(belt_surface));
                            effective_lower = union_ex(effective_lower);
                        }
                    }
                }
 
                // normal overhang
                ExPolygons lower_layer_offseted = offset_ex(effective_lower, support_offset_scaled, SUPPORT_SURFACES_OFFSET_PARAMETERS);
                overhangs_all_layers[layer_nr] = diff_ex(curr_polys, lower_layer_offseted);
 
                double duration{ std::chrono::duration_cast<second_>(clock_::now() - t0).count() };
                if (duration > 30 || overhangs_all_layers[layer_nr].size() > 100) {
                    BOOST_LOG_TRIVIAL(info) << "detect_overhangs takes more than 30 secs, skip cantilever and sharp tails detection: layer_nr=" << layer_nr << " duration=" << duration;
                    config_detect_sharp_tails = false;
                    config_remove_small_overhangs = false;
                    continue;
                }
                if (is_auto(stype) && config_detect_sharp_tails)
                {
                    // BBS detect sharp tail
                    // On a belt, "below" has to include the belt itself and the
                    // shear-advanced lower layer, or every belt-contact island reads as
                    // a sharp tail -- which is what the empty-predecessor skip above was
                    // really masking. effective_lower is exactly that notion of below.
                    const ExPolygons &tail_lower = belt_ovh_active ? effective_lower : lower_polys;
                    // Each island is tested only against the lower islands whose box meets its own; overlaps() tries
                    // every pair, which is quadratic in the island counts of the two layers.
                    std::vector<BoundingBox> lower_bboxes;
                    lower_bboxes.reserve(tail_lower.size());
                    for (const ExPolygon &lower : tail_lower)
                        lower_bboxes.emplace_back(get_extents(lower));
                    for (const ExPolygon& expoly : curr_polys) {
                        bool  is_sharp_tail = false;
                        // 1. nothing below
                        // this is a sharp tail region if it's floating and non-ignorable
                        const ExPolygons  expanded = offset_ex(expoly, 0.1 * extrusion_width_scaled);
                        const BoundingBox bbox     = get_extents(expanded);
                        ExPolygons        lower_nearby;
                        for (size_t i = 0; i < tail_lower.size(); ++i)
                            if (lower_bboxes[i].overlap(bbox))
                                lower_nearby.emplace_back(tail_lower[i]);
                        // As overlaps(expanded, lower_nearby), with each lower island cut to the island's box first:
                        // below a fine relief the lower layer is a few islands with thousands of holes, and the whole
                        // of that boundary would otherwise be intersected once per island above.
                        const auto overlaps_nearby = [&]() {
                            for (const ExPolygon &a : expanded) {
                                if (a.empty())
                                    continue;
                                const BoundingBox a_bbox = get_extents(a);
                                for (const ExPolygon &b : lower_nearby) {
                                    if (b.empty() || !get_extents(b).overlap(a_bbox))
                                        continue;
                                    const Polygons b_near = ClipperUtils::clip_clipper_polygons_with_subject_bbox(b, a_bbox.inflated(SCALED_EPSILON));
                                    if (!intersection_pl(to_polylines(b_near), a).empty() || b.contains(a.contour.points.front()))
                                        return true;
                                }
                            }
                            return false;
                        };
                        if (!overlaps_nearby()) {
                            is_sharp_tail = !offset_ex(expoly, -0.1 * extrusion_width_scaled).empty();
                        }
 
                        if (is_sharp_tail) {
                            layer->sharp_tails.push_back(expoly);
                            layer->sharp_tails_height.push_back(0);
 
                            has_sharp_tails = true;
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
              SVG::export_expolygons(debug_out_path("sharp_tail_orig_%.02f.svg", layer->print_z), { expoly });
#endif
            }
                    }
                }
 
 
                // check cantilever
                // lower_layer_offset may be very small, so we need to do max and then add 0.1
                lower_layer_offseted = offset_ex(lower_layer_offseted, scale_(std::max(extrusion_width - lower_layer_offset, 0.) + 0.1));
                for (ExPolygon& poly : overhangs_all_layers[layer_nr]) {
                    auto cluster_boundary_ex = intersection_ex(poly, lower_layer_offseted);
                    Polygons cluster_boundary = to_polygons(cluster_boundary_ex);
                    if (cluster_boundary.empty()) continue;
                    double dist_max = 0;
                    for (auto& pt : poly.contour.points) {
                        double dist_pt = std::numeric_limits<double>::max();
                        for (auto& ply : cluster_boundary) {
                            double d = ply.distance_to(pt);
                            dist_pt = std::min(dist_pt, d);
                        }
                        dist_max = std::max(dist_max, dist_pt);
                    }
                    if (dist_max > scale_(3)) {  // is cantilever if the farmost point is larger than 3mm away from base
                        max_cantilever_dist = std::max(max_cantilever_dist, dist_max);
                        layer->cantilevers.emplace_back(poly);
                        BOOST_LOG_TRIVIAL(debug) << "found a cantilever cluster. layer_nr=" << layer_nr << dist_max;
                        has_cantilever = true;
                    }
                }
            }
        }
    ); // end tbb::parallel_for
 
    BOOST_LOG_TRIVIAL(info) << "max_cantilever_dist=" << max_cantilever_dist;
    if (check_support_necessity)
        return;
 
    // check if the sharp tails should be extended higher
    if (is_auto(stype) && config_detect_sharp_tails) {
        for (size_t layer_nr = 0; layer_nr < m_object->layer_count(); layer_nr++) {
            if (m_object->print()->canceled())
                break;
 
            Layer* layer = m_object->get_layer(layer_nr);
            Layer* lower_layer = layer->lower_layer;
            if (!lower_layer)
                continue;
 
            // BBS detect sharp tail
            const ExPolygons& lower_layer_sharptails = lower_layer->sharp_tails;
            const auto& lower_layer_sharptails_height = lower_layer->sharp_tails_height;
            for (ExPolygon& expoly : layer->lslices_extrudable) {
                bool  is_sharp_tail = false;
                float accum_height = layer->height;
                do {
                    // 2. something below
                    // check whether this is above a sharp tail region.
 
                    // 2.1 If no sharp tail below, this is considered as common region.
                    ExPolygons supported_by_lower = intersection_ex({ expoly }, lower_layer_sharptails);
                    if (supported_by_lower.empty()) {
                        is_sharp_tail = false;
                        break;
                    }
 
                    // 2.2 If sharp tail below, check whether it support this region enough.
#if 0
                    // judge by area isn't reliable, failure cases include 45 degree rotated cube
                    float       supported_area = area(supported_by_lower);
                    if (supported_area > area_thresh_well_supported) {
                        is_sharp_tail = false;
                        break;
                    }
#endif
                    BoundingBox bbox = get_extents(supported_by_lower);
                    if (bbox.size().x() > length_thresh_well_supported && bbox.size().y() > length_thresh_well_supported) {
                        is_sharp_tail = false;
                        break;
                    }
 
                    // 2.3 check whether sharp tail exceed the max height
                    for(size_t i=0;i<lower_layer_sharptails.size();i++) {
                        if (lower_layer_sharptails[i].overlaps(expoly)) {
                            accum_height += lower_layer_sharptails_height[i];
                            break;
                        }
                    }
                    if (accum_height > sharp_tail_max_support_height) {
                        is_sharp_tail = false;
                        break;
                    }
 
                    // 2.4 if the area grows fast than threshold, it get connected to other part or
                    // it has a sharp slop and will be auto supported.
                    ExPolygons new_overhang_expolys = diff_ex({ expoly }, lower_layer_sharptails);
                    if ((get_extents(new_overhang_expolys).size() - get_extents(lower_layer_sharptails).size()).both_comp(Point(scale_(5), scale_(5)), ">") || !offset_ex(new_overhang_expolys, -5.0 * extrusion_width_scaled).empty()) {
                        is_sharp_tail = false;
                        break;
                    }
 
                    // 2.5 mark the expoly as sharptail
                    is_sharp_tail = true;
                } while (0);
 
                if (is_sharp_tail) {
                    layer->sharp_tails.push_back(expoly);
                    layer->sharp_tails_height.push_back( accum_height);
                }
 
            }
        }
    }
 
    // group overhang clusters
    for (size_t layer_nr = 0; layer_nr < m_object->layer_count(); layer_nr++) {
        if (m_object->print()->canceled())
            break;
        Layer* layer = m_object->get_layer(layer_nr);
        for (auto& overhang : overhangs_all_layers[layer_nr]) {
            OverhangCluster* cluster = find_and_insert_cluster(overhangClusters, overhang, layer_nr, extrusion_width_scaled);
            if (overlaps({ overhang }, layer->cantilevers))
                cluster->is_cantilever = true;
        }
    }
 
    auto enforcers = m_object->slice_support_enforcers();
    auto blockers  = m_object->slice_support_blockers();
    m_vertical_enforcer_points.clear();
    m_object->project_and_append_custom_facets(false, EnforcerBlockerType::ENFORCER, enforcers, &m_vertical_enforcer_points);
    m_object->project_and_append_custom_facets(false, EnforcerBlockerType::BLOCKER, blockers);
 
    if (is_auto(stype) && config_remove_small_overhangs) {
        // remove small overhangs
        for (auto& cluster : overhangClusters) {
            // 3. check whether the small overhang is sharp tail
            cluster.is_sharp_tail = false;
            for (size_t layer_id = cluster.min_layer; layer_id <= cluster.max_layer; layer_id++) {
                Layer* layer = m_object->get_layer(layer_id);
                if (overlaps(layer->sharp_tails, cluster.merged_poly)) {
                    cluster.is_sharp_tail = true;
                    break;
                }
            }
 
            if (!cluster.is_sharp_tail && !cluster.is_cantilever) {
                // 2. check overhang cluster size is smaller than 3.0 * fw_scaled
                auto erode1 = offset_ex(cluster.merged_poly, -1 * extrusion_width_scaled);
                Point bbox_sz = get_extents(erode1).size();
                if (bbox_sz.x() < 2 * extrusion_width_scaled || bbox_sz.y() < 2 * extrusion_width_scaled) {
                    cluster.is_small_overhang = true;
                }
            }
 
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
            const Layer* layer1 = m_object->get_layer(cluster.min_layer);
            std::string fname = debug_out_path("overhangCluster_%d-%d_%.2f-%.2f_tail=%d_cantilever=%d_small=%d.svg",
                cluster.min_layer, cluster.max_layer, layer1->print_z, m_object->get_layer(cluster.max_layer)->print_z,
                cluster.is_sharp_tail, cluster.is_cantilever, cluster.is_small_overhang);
            SVG::export_expolygons(fname, {
                { layer1->lslices, {"min_layer_lslices","red",0.5} },
                { m_object->get_layer(cluster.max_layer)->lslices, {"max_layer_lslices","yellow",0.5} },
                { cluster.merged_poly,{"overhang", "blue", 0.5} },
                { cluster.is_cantilever? layer1->cantilevers: offset_ex(cluster.merged_poly, -1 * extrusion_width_scaled), {cluster.is_cantilever ? "cantilever":"erode1","green",0.5}} });
#endif
        }
    }
 
    for (auto& cluster : overhangClusters) {
        if (cluster.is_small_overhang) continue;
        // collect overhangs that's not small overhangs
        for (auto it = cluster.layer_overhangs.begin(); it != cluster.layer_overhangs.end(); it++) {
            int  layer_nr   = it->first;
            auto p_overhang = it->second;
            m_object->get_layer(layer_nr)->loverhangs.emplace_back(*p_overhang);
        }
    }
 
    int layers_with_overhangs = 0;
    int layers_with_enforcers = 0;
    for (int layer_nr = 0; layer_nr < m_object->layer_count(); layer_nr++) {
        if (m_object->print()->canceled())
            break;
 
        auto layer = m_object->get_layer(layer_nr);
        auto lower_layer = layer->lower_layer;
 
        // add support for every 1mm height for sharp tails
        ExPolygons sharp_tail_overhangs;
        if (lower_layer == nullptr)
            sharp_tail_overhangs = layer->sharp_tails;
        else {
            ExPolygons lower_layer_expanded = offset_ex(lower_layer->lslices_extrudable, SCALED_RESOLUTION);
            for (size_t i = 0; i < layer->sharp_tails_height.size();i++) {
                ExPolygons areas = diff_clipped({ layer->sharp_tails[i]}, lower_layer_expanded);
                float accum_height = layer->sharp_tails_height[i];
                if (!areas.empty() && int(accum_height * 10) % 5 == 0) {
                    append(sharp_tail_overhangs, areas);
                    has_sharp_tails = true;
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
                    SVG::export_expolygons(debug_out_path("sharp_tail_%.02f.svg", layer->print_z), areas);
#endif
                }
            }
        }
 
        if (layer_nr < blockers.size()) {
            // Arthur: union_ is a must because after mirroring, the blocker polygons are in left-hand coordinates, ie clockwise,
            // which are not valid polygons, and will be removed by offset_ex. union_ can make these polygons right.
            ExPolygons blocker = offset_ex(union_(blockers[layer_nr]), scale_(radius_sample_resolution));
            layer->loverhangs = diff_ex(layer->loverhangs, blocker);
            layer->cantilevers = diff_ex(layer->cantilevers, blocker);
            sharp_tail_overhangs = diff_ex(sharp_tail_overhangs, blocker);
        }
 
        if (support_critical_regions_only && is_auto(stype)) {
            layer->loverhangs.clear();  // remove oridinary overhangs, only keep cantilevers and sharp tails (added later)
            append(layer->loverhangs, layer->cantilevers);
        }
 
        if (max_bridge_length > 0 && layer->loverhangs.size() > 0 && lower_layer) {
            // do not break bridge as the interface will be poor, see #4318
            bool break_bridge = false;
            m_object->remove_bridges_from_contacts(lower_layer, layer, extrusion_width_scaled, &layer->loverhangs, max_bridge_length, break_bridge);
        }
 
    int nDetected = layer->loverhangs.size();
        // enforcers now follow same logic as normal support. See STUDIO-3692
        if (layer_nr < enforcers.size() && lower_layer) {
            ExPolygons enforced_overhangs   = intersection_ex(diff_ex(layer->lslices_extrudable, lower_layer->lslices_extrudable), enforcers[layer_nr]);
            if (!enforced_overhangs.empty()) {
                // FIXME this is a hack to make enforcers work on steep overhangs. See STUDIO-7538.
                enforced_overhangs = diff_ex(offset_ex(enforced_overhangs, enforcer_overhang_offset), lower_layer->lslices_extrudable);
                append(layer->loverhangs, enforced_overhangs);
            }
        }
        int nEnforced = layer->loverhangs.size();
 
        // add sharp tail overhangs
        append(layer->loverhangs, sharp_tail_overhangs);
 
        // fill overhang_types
        for (size_t i = 0; i < layer->loverhangs.size(); i++)
            overhang_types.emplace(&layer->loverhangs[i], i < nDetected ? OverhangType::Detected :
                i < nEnforced ? OverhangType::Enforced : OverhangType::SharpTail);
 
        if (!layer->loverhangs.empty()) {
            layers_with_overhangs++;
            m_highest_overhang_layer = std::max(m_highest_overhang_layer, size_t(layer_nr));
        }
        if (nEnforced > 0) layers_with_enforcers++;
        if (!layer->cantilevers.empty()) has_cantilever = true;
    }
 
    BOOST_LOG_TRIVIAL(info) << "Tree support overhang detection done. " << layers_with_overhangs << " layers with overhangs. nEnforced=" << layers_with_enforcers;
 
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
    for (const Layer* layer : m_object->layers()) {
        if (layer->loverhangs.empty() && (blockers.size()<=layer->id() || blockers[layer->id()].empty()))
            continue;
 
        SVG::export_expolygons(debug_out_path("overhang_areas_%d_%.2f.svg",layer->id(), layer->print_z), {
            { m_object->get_layer(layer->id())->lslices_extrudable, {"lslices_extrudable","yellow",0.5} },
            { layer->loverhangs, {"overhang","red",0.5} }
            });
 
        if (enforcers.size() > layer->id()) {
            SVG svg(format("SVG/enforcer_%s.svg", layer->print_z), m_object->bounding_box());
            if (svg.is_opened()) {
                svg.draw_outline(m_object->get_layer(layer->id())->lslices_extrudable, "yellow");
                svg.draw(enforcers[layer->id()], "red");
            }
        }
        if (blockers.size() > layer->id()) {
            SVG svg(format("SVG/blocker_%s.svg", layer->print_z), m_object->bounding_box());
            if (svg.is_opened()) {
                svg.draw_outline(m_object->get_layer(layer->id())->lslices_extrudable, "yellow");
                svg.draw(blockers[layer->id()], "red");
            }
        }
    }
#endif
}

References Slic3r::area_thresh_well_supported, Slic3r::build_plate_tilt_slope(), Slic3r::Geometry::deg2rad(), EPSILON, Slic3r::BeltFloorContext::from_axis(), g_config_support_sharp_tails, g_config_tree_support_collision_resolution, Slic3r::get_extents(), Slic3r::BeltFloorContext::init(), Slic3r::is_tree(), Slic3r::length_thresh_well_supported, m_highest_overhang_layer, m_object, m_object_config, m_slicing_params, max_cantilever_dist, Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::nozzle_diameter(), Slic3r::offset(), Slic3r::offset_ex(), Slic3r::BoundingBoxBase< PointType, APointsType >::overlap(), Slic3r::overlaps(), Slic3r::PrintObjectConfig, Slic3r::range(), scale_, Slic3r::scaled(), Slic3r::sharp_tail_max_support_height, Slic3r::BeltFloorContext::shear_factor(), SQ, support_type, and Slic3r::union_ex().

Referenced by generate(), Slic3r::TreeSupport3D::generate_support_areas(), and Slic3r::PrintObject::is_support_necessary().

Here is the call graph for this function:

Here is the caller graph for this function:

draw_circles()

void Slic3r::TreeSupport::draw_circles ( )

private

Draws circles around each node of the tree into the final support.

This also handles the areas that have to become support roof, support bottom, the Z distances, etc.

Parameters

storage[in,out]	The settings storage to get settings from and to save the resulting support polygons to.
contact_nodes	The nodes to draw as support.

{
    const PrintObjectConfig &config = m_object->config();
    const Print* print = m_object->print();
    bool has_brim = print->has_brim();
    const coordf_t bottom_gap_height = m_slicing_params.gap_object_support;
    const coordf_t branch_radius = config.tree_support_branch_diameter.value / 2;
    const coordf_t branch_radius_scaled = scale_(branch_radius);
    bool on_buildplate_only = m_object_config->support_on_build_plate_only.value;
    Polygon branch_circle; //Pre-generate a circle with correct diameter so that we don't have to recompute those (co)sines every time.
 
    // Use square support if there are too many nodes per layer because circle support needs much longer time to compute
    // Hower circle support can be printed faster, so we prefer circle for fewer nodes case.
    const bool SQUARE_SUPPORT = avg_node_per_layer > 200;
    const int  CIRCLE_RESOLUTION = SQUARE_SUPPORT ? 4 : 100; // The number of vertices in each circle.
 
 
    for (int i = 0; i < CIRCLE_RESOLUTION; i++)
    {
        double angle;
        if (SQUARE_SUPPORT)
            angle = (double) i / CIRCLE_RESOLUTION * TAU + M_PI_4 + nodes_angle;
        else
            angle = (double) i / CIRCLE_RESOLUTION * TAU;
        branch_circle.append(Point(cos(angle) * branch_radius_scaled, sin(angle) * branch_radius_scaled));
    }
 
    // Performance optimization. Only generate lslices for brim and skirt.
    size_t brim_skirt_layers = has_brim ? 1 : 0;
    const PrintConfig& print_config = print->config();
    for (const PrintObject* object : print->objects())
    {
        size_t skirt_layers = print->has_infinite_skirt() ? object->layer_count() : std::min(size_t(print_config.skirt_height.value), object->layer_count());
        brim_skirt_layers = std::max(brim_skirt_layers, skirt_layers);
    }
 
    // generate areas
    const coordf_t layer_height = config.layer_height.value;
    const size_t top_interface_layers = m_support_params.num_top_interface_layers;
    const int top_base_interface_layers = std::min<int>(
        int(m_support_params.num_top_base_interface_layers),
        top_interface_layers > 0 ? int(top_interface_layers) - 1 : 0);
    const size_t bottom_interface_layers = number_of_support_interface_bottom_layers(config);
    const double nozzle_diameter = m_object->print()->config().nozzle_diameter.get_at(0);
    const coordf_t line_width = config.get_abs_value("support_line_width", nozzle_diameter);
    const coordf_t line_width_scaled           = scale_(line_width);
    const bool with_lightning_infill = m_support_params.base_fill_pattern == ipLightning;
    coordf_t support_extrusion_width = m_support_params.support_extrusion_width;
    const float tree_brim_width = config.tree_support_brim_width.value;
    // Reinforce branches moving more than half a support-line width between layers.
    // Square the threshold for comparison with the squared XY movement below.
    const double max_move_sq = sqr(double(scale_(m_object_config->support_line_width / 2)));
    // Belt floor: the first object layer is not on a flat bed — it rests on the
    // tilted, moving belt. So the first-object-layer adhesion features (the tree
    // support brim, the hybrid first-layer base expansion) must be suppressed:
    // their expanded contact rings project to a stray brim/skirt loop sitting in
    // the Z=0 belt plane around the support footprint. false on non-belt printers,
    // so behavior there is unchanged.
    BeltFloorContext belt_ctx;
    const bool belt_floor_active = belt_ctx.init(m_slicing_params, *m_print_config);
 
    if (m_object->support_layer_count() <= m_raft_layers)
        return;
    BOOST_LOG_TRIVIAL(info) << "draw_circles for object: " << m_object->model_object()->name;
 
    tbb::parallel_for(tbb::blocked_range<size_t>(0, m_ts_data->layer_heights.size()),
        [&](const tbb::blocked_range<size_t>& range)
        {
            for (size_t layer_nr = range.begin(); layer_nr < range.end(); layer_nr++)
            {
                if (print->canceled())
                    break;
 
                const std::vector<SupportNode*>& curr_layer_nodes = contact_nodes[layer_nr];
                SupportLayer* ts_layer = m_object->get_support_layer(layer_nr + m_raft_layers);
                assert(ts_layer != nullptr);
 
                // skip if current layer has no points. This fixes potential crash in get_collision (see jira BBL001-355)
                if (curr_layer_nodes.empty()) {
                    ts_layer->print_z = 0.0;
                    ts_layer->height = 0.0;
                    continue;
                }
 
                ts_layer->print_z = m_ts_data->layer_heights[layer_nr].print_z;
                ts_layer->height = m_ts_data->layer_heights[layer_nr].height;
                size_t obj_layer_nr = m_ts_data->layer_heights[layer_nr].obj_layer_nr;
                if (ts_layer->height < EPSILON) {
                    continue;
                }
 
                ExPolygons& base_areas = ts_layer->base_areas;
                ExPolygons& roof_areas = ts_layer->roof_areas;
                ExPolygons roof_base_areas;
                ExPolygons& roof_1st_layer = ts_layer->roof_1st_layer;
                ExPolygons& floor_areas = ts_layer->floor_areas;
                ExPolygons& roof_gap_areas = ts_layer->roof_gap_areas;
                coordf_t         max_layers_above_base = 0;
                coordf_t         max_layers_above_roof = 0;
                coordf_t         max_layers_above_roof1 = 0;
                size_t           first_base_roof_area = 0;
                bool             floor_interface_as_base = false;
                bool has_circle_node = false;
                ExPolygons extra_wall_areas;
                ExPolygons collision_sharp_tails;
                ExPolygons collision_base;
                auto             get_collision = [&](bool sharp_tail) -> ExPolygons             &{
                    ExPolygons &collision = sharp_tail ? collision_sharp_tails : collision_base;
                    if (collision.empty()) {
                        collision = offset_ex(m_ts_data->m_layer_outlines[obj_layer_nr],
                                              sharp_tail ? scale_(top_z_distance) :
                                                           scale_((obj_layer_nr == 0) ? config.support_object_first_layer_gap : m_ts_data->m_xy_distance));
                        // the top layers may be too close to interface with adaptive layer heights and very small overhang angle
                        if (top_z_distance > EPSILON) {
                            float accum_height = 0;
                            for (size_t layer_id = obj_layer_nr + 1;
                                 layer_id < m_ts_data->m_layer_outlines.size() && (accum_height += m_object->get_layer(layer_id)->height) && accum_height <= top_z_distance;
                                 layer_id++) {
                                collision = union_ex(collision, offset_ex(m_ts_data->m_layer_outlines[layer_id], scale_(top_z_distance)));
                            }
                        }
                    }
                    return collision;
                };
 
                BOOST_LOG_TRIVIAL(debug) << "circles at layer " << layer_nr << " contact nodes size=" << curr_layer_nodes.size();
                //Draw the support areas and add the roofs appropriately to the support roof instead of normal areas.
                ts_layer->lslices.reserve(curr_layer_nodes.size());
                ExPolygons area_poly;  // the polygon node area which will be printed as normal support
                for (const SupportNode* p_node : curr_layer_nodes)
                {
                    if (print->canceled())
                        break;
 
                    const SupportNode& node = *p_node;
                    ExPolygons area;
                    // Generate directly from overhang polygon if one of the following is true:
                    // 1) node is a normal part of hybrid support
                    // 2) node is virtual
                    if (node.type == ePolygon || (node.distance_to_top<0 && !node.is_sharp_tail)) {
                        if (node.overhang.contour.size() > 100 || node.overhang.holes.size()>1)
                            area.emplace_back(node.overhang);
                        else {
                            area = offset_ex({ node.overhang }, scale_(m_ts_data->m_xy_distance));
                        }
                        area = diff_clipped(area, get_collision(node.is_sharp_tail && node.distance_to_top <= 0));
                        if (node.type == ePolygon) append(area_poly, area);
                    }
                    else {
                        Polygon circle(branch_circle);
                        double  scale = node.radius / branch_radius;
                        double moveX = node.movement.x() / (scale * branch_radius_scaled);
                        double moveY = node.movement.y() / (scale * branch_radius_scaled);
                        //BOOST_LOG_TRIVIAL(debug) << format("scale,moveX,moveY: %.3f,%.3f,%.3f", scale, moveX, moveY);
 
                        if (!SQUARE_SUPPORT && std::abs(moveX)>0.001 && std::abs(moveY)>0.001) { // draw ellipse along movement direction
                            const double vsize_inv = 0.5 / (0.01 + std::sqrt(moveX * moveX + moveY * moveY));
                            double       matrix[2*2]  = {
                                scale * (1 + moveX * moveX * vsize_inv),scale * (0 + moveX * moveY * vsize_inv),
                                scale * (0 + moveX * moveY * vsize_inv),scale * (1 + moveY * moveY * vsize_inv),
                            };
                            int i = 0;
                            for (auto vertex: branch_circle.points) {
                                vertex = Point(matrix[0] * vertex.x() + matrix[1] * vertex.y(), matrix[2] * vertex.x() + matrix[3] * vertex.y());
                                circle.points[i++] = node.position + vertex;
                            }
                        } else {
                            for (int i = 0;i< circle.points.size(); i++) {
                                circle.points[i] = circle.points[i] * scale + node.position;
                            }
                        }
                        if (obj_layer_nr == 0 && m_raft_layers == 0 && !belt_floor_active) {
                            double brim_width = !config.tree_support_auto_brim ? tree_brim_width : std::max(MIN_BRANCH_RADIUS_FIRST_LAYER, std::min(node.radius + node.dist_mm_to_top / (scale * branch_radius) * 0.5, MAX_BRANCH_RADIUS_FIRST_LAYER) - node.radius);
                            auto tmp=offset(circle, scale_(brim_width));
                            if(!tmp.empty())
                                circle = tmp[0];
                        }
                        area = avoid_object_remove_extra_small_parts(ExPolygon(circle), get_collision(node.is_sharp_tail && node.distance_to_top <= 0));
                        // area = diff_clipped({ ExPolygon(circle) }, get_collision(node.is_sharp_tail && node.distance_to_top <= 0));
 
                        if (!area.empty()) has_circle_node = true;
 
                        // merge overhang to get a smoother interface surface
                        // Do not merge when buildplate_only is on, because some underneath nodes may have been deleted.
                        if (top_interface_layers > 0 && node.support_roof_layers_below > 0 && !on_buildplate_only && !node.is_sharp_tail) {
                            ExPolygons overhang_expanded;
                            if (node.overhang.contour.size() > 100 || node.overhang.holes.size()>1)
                                overhang_expanded.emplace_back(node.overhang);
                            else {
                                overhang_expanded = offset_ex({ node.overhang }, scale_(m_ts_data->m_xy_distance));
                            }
                            append(area, overhang_expanded);
                        }
                    }
 
                    // Use the Pythagorean theorem to compare movement magnitude (dx² + dy²) without a square root.
                    if (node.is_processed && node.movement.cast<double>().squaredNorm() > max_move_sq)
                        append(extra_wall_areas, area);
 
                    if (obj_layer_nr>0 && node.distance_to_top < 0)
                        append(roof_gap_areas, area);
                    else if (obj_layer_nr > 0 && node.support_roof_layers_below == 1 &&
                             node.is_sharp_tail == false)
                    {
                        append(roof_1st_layer, area);
                        max_layers_above_roof1 = std::max(max_layers_above_roof1, node.dist_mm_to_top);
                    }
                    else if (obj_layer_nr > 0 && node.support_roof_layers_below > 1 &&
                             node.is_sharp_tail == false)
                    {
                        append(node.support_roof_layers_below <= top_base_interface_layers ? roof_base_areas : roof_areas, area);
                        max_layers_above_roof = std::max(max_layers_above_roof, node.dist_mm_to_top);
                    }
                    else
                    {
                        append(base_areas, area);
                        max_layers_above_base = std::max(max_layers_above_base, node.dist_mm_to_top);
                    }
 
                }
 
                //m_object->print()->set_status(65, (boost::format( _u8L("Support: generate polygons at layer %d")) % layer_nr).str());
 
                // join roof segments
                roof_areas     = diff_clipped(closing_ex(roof_areas, line_width_scaled), get_collision(false));
                roof_areas     = intersection_ex(roof_areas, m_machine_border);
                roof_base_areas = diff_clipped(closing_ex(roof_base_areas, line_width_scaled), get_collision(false));
                roof_base_areas = intersection_ex(roof_base_areas, m_machine_border);
                if (!roof_base_areas.empty() && !roof_areas.empty())
                    roof_base_areas = diff_ex(roof_base_areas,
                        ClipperUtils::clip_clipper_polygons_with_subject_bbox(roof_areas, get_extents(roof_base_areas)));
 
                first_base_roof_area = roof_areas.size();
                append(roof_areas, std::move(roof_base_areas));
                roof_1st_layer = diff_clipped(closing_ex(roof_1st_layer, line_width_scaled), get_collision(false));
 
                // roof_1st_layer and roof_areas may intersect, so need to subtract roof_areas from roof_1st_layer
                roof_1st_layer = diff_ex(roof_1st_layer, ClipperUtils::clip_clipper_polygons_with_subject_bbox(roof_areas,get_extents(roof_1st_layer)));
                roof_1st_layer = intersection_ex(roof_1st_layer, m_machine_border);
 
                ExPolygons roofs; append(roofs, roof_1st_layer); append(roofs, roof_areas);append(roofs, roof_gap_areas);
                base_areas = diff_ex(base_areas, ClipperUtils::clip_clipper_polygons_with_subject_bbox(roofs, get_extents(base_areas)));
                base_areas = intersection_ex(base_areas, m_machine_border);
 
                // Belt floor: clip tree support polygons by the belt surface plane.
                // Non-organic tree support layers inherit their print_z from the
                // (already globally-offset) object layers — see plan_layer_heights()
                // and add_tree_support_layer(); only ORGANIC layers get the global
                // Z offset applied later in _generate_support_material(). So here
                // ts_layer->print_z is in the GLOBAL frame and we must use init()
                // (global), not init_local(): mixing a local-frame clip plane with
                // a global print_z displaces the cutoff line by belt_global_z_offset
                // along the shear axis, leaving an un-clipped wedge of support below
                // the belt floor. In per-object (non-global) mode belt_global_z_offset
                // is 0 so init() and init_local() coincide — this is a no-op there.
                {
                    BeltFloorContext ctx;
                    if (ctx.init(m_slicing_params, *m_print_config)) {
                        Polygons belt_surface = ctx.surface_polygon(ts_layer->print_z);
                        base_areas     = diff_ex(base_areas,     belt_surface);
                        roof_areas     = diff_ex(roof_areas,     belt_surface);
                        roof_1st_layer = diff_ex(roof_1st_layer, belt_surface);
                        floor_areas    = diff_ex(floor_areas,    belt_surface);
                        roof_gap_areas = diff_ex(roof_gap_areas, belt_surface);
                    }
                }
 
                if (SQUARE_SUPPORT) {
                    // simplify support contours
                    ExPolygons base_areas_simplified;
                    for (auto &area : base_areas) { area.simplify(scale_(line_width / 2), &base_areas_simplified); }
                    base_areas = std::move(base_areas_simplified);
                }
                // ORCA:
                // Bottom interface / bottom gap must be anchored to the *true* support-to-model contact surface.
                // Do NOT window the contact search by gap or interface height.
                // First find the real contact below, then enforce:
                //   - an empty gap below (contact_z + gap)
                //   - exactly N interface layers above that
                if (!base_areas.empty() && !m_object_config->support_on_build_plate_only.value &&
                    (bottom_gap_height > EPSILON || bottom_interface_layers > 0))
                {
                    const coordf_t interface_height =
                        bottom_interface_layers > 0 ? coordf_t(bottom_interface_layers) * m_slicing_params.layer_height : 0.0;
 
                    const coordf_t layer_top_z = ts_layer->print_z;
                    const coordf_t layer_bottom_z = ts_layer->bottom_z();
                    ExPolygons new_base_areas;
                    ExPolygons new_floor_areas;
                    struct ContactBand {
                        coordf_t z = 0.0;
                        Polygons surfaces;
                    };
                    for (const ExPolygon& comp : base_areas) {
                        ExPolygons comp_poly { comp };
                        bool found_contact = false;
                        std::vector<ContactBand> bands;
 
                        // Search downward for object layers whose TOP/BOTTOM surfaces intersect this component.
                        for (size_t idx = obj_layer_nr + 1; idx-- > 0;) {
                            const Layer* below_layer = m_object->get_layer(idx);
                            Polygons top_surfaces = collect_region_slices_by_type(*below_layer, stTop);
                            Polygons bottom_surfaces = collect_region_slices_by_type(*below_layer, stBottom);
                            Polygons surf_union = top_surfaces;
                            polygons_append(surf_union, bottom_surfaces);
                            if (surf_union.empty())
                                continue;
 
                            ExPolygons inter = intersection_ex(comp_poly, surf_union);
                            if (!inter.empty()) {
                                bands.push_back(ContactBand{ below_layer->print_z, std::move(surf_union) });
                                found_contact = true;
                            }
                        }
 
                        if (found_contact) {
                            std::sort(bands.begin(), bands.end(), [](const ContactBand &a, const ContactBand &b) {
                                return a.z < b.z;
                            });
                        }
 
                        if (!found_contact) {
                            append(new_base_areas, comp_poly);
                            continue;
                        }
 
                        bool interface_id_set = false;
                        bool any_gap_cleared = false;
 
                        for (const ContactBand &band : bands) {
                            const coordf_t band_gap_top = band.z + bottom_gap_height;
                            const coordf_t band_iface_start = band_gap_top;
                            const bool band_applies = layer_top_z >= band.z - EPSILON;
                            if (!band_applies)
                                continue;
 
 
                            // Inside the gap: remove only the part overlapping the contact surface, keep the rest.
                            if (bottom_gap_height > EPSILON && layer_bottom_z < band_gap_top - EPSILON) {
                                any_gap_cleared = true;
                                comp_poly = diff_ex(comp_poly, band.surfaces);
                            }
 
                            // Overlaps interface band
                            if (bottom_interface_layers > 0 &&
                                layer_bottom_z >= band_iface_start - EPSILON &&
                                layer_bottom_z < band_iface_start + interface_height - EPSILON) {
                                if (!interface_id_set) {
                                    size_t first_interface_layer = layer_nr;
                                    while (first_interface_layer > 0) {
                                        if (m_ts_data->layer_heights[first_interface_layer - 1].print_z <= band_iface_start + EPSILON)
                                            break;
                                        --first_interface_layer;
                                    }
                                    // ORCA: Use support-layer index for base-interface selection (robust with independent heights).
                                    if (m_support_params.num_bottom_base_interface_layers > 0) {
                                        const int bottom_interface_idx =
                                            std::max(0, int(layer_nr) - int(first_interface_layer));
                                        const int bottom_base_start_idx =
                                            std::max(0, int(bottom_interface_layers) - int(m_support_params.num_bottom_base_interface_layers));
                                        floor_interface_as_base = bottom_interface_idx >= bottom_base_start_idx;
                                    }
                                    interface_id_set = true;
                                }
 
                                ExPolygons band_ex = union_ex(band.surfaces);
                                if (!band_ex.empty()) {
                                    const coordf_t margin = scale_(m_support_params.support_extrusion_width);
                                    ExPolygons comp_margin = offset_ex(comp_poly, margin);
                                    ExPolygons band_clipped = intersection_ex(band_ex, comp_margin);
                                    band_ex = std::move(band_clipped);
                                }
                                ExPolygons comp_interface = band_ex.empty() ? ExPolygons {} : intersection_ex(comp_poly, band_ex);
                                if (!comp_interface.empty()) {
                                    append(new_floor_areas, comp_interface);
                                    comp_poly = diff_ex(comp_poly, offset_ex(comp_interface, 10));
                                }
                            }
 
                        }
 
                        if (any_gap_cleared && comp_poly.empty()) {
                            continue;
                        }
 
                        if (!comp_poly.empty())
                            append(new_base_areas, comp_poly);
 
                    }
 
 
                    base_areas  = std::move(new_base_areas);
                    floor_areas = std::move(new_floor_areas);
                }
 
                // Orca: Hybrid tree first-layer expansion belongs only to the normal-support
                // part. area_poly is collected from ePolygon nodes above, which are the normal
                // support nodes in Hybrid mode. Apply the expansion before area_groups and
                // lslices are built so toolpaths and brim avoidance use the same footprint.
                if (layer_nr == 0 && m_raft_layers == 0 && !belt_floor_active && m_support_params.support_style == smsTreeHybrid &&
                    m_object_config->raft_first_layer_expansion.value > 0.f) {
                    ExPolygons expanded_base_areas;
                    const float inflate_factor_1st_layer = float(scale_(m_object_config->raft_first_layer_expansion.value));
                    Polygons trimming = offset(m_object->layers().front()->lslices, float(scale_(m_support_params.gap_xy_first_layer)),
                                               SUPPORT_SURFACES_OFFSET_PARAMETERS);
                    // Orca: Match normal support expansion: grow in steps and re-trim against the object each time.
                    const int nsteps = std::max(5, int(ceil(inflate_factor_1st_layer / m_support_params.first_layer_flow.scaled_width())));
                    const float step = inflate_factor_1st_layer / nsteps;
                    for (const ExPolygon &expoly : ts_layer->base_areas) {
                        if (overlaps({ expoly }, area_poly)) { // normal support in Hybrid mode
                            Polygons expanded = to_polygons(expoly);
                            for (int i = 0; i < nsteps; ++i)
                                expanded = diff(expand(expanded, step), trimming);
                            append(expanded_base_areas, union_ex(expanded));
                        } else
                            expanded_base_areas.emplace_back(expoly);
                    }
                    ts_layer->base_areas = std::move(expanded_base_areas);
                }
 
                // Orca: Final tree base polygons may be too close above model surfaces.
                // Enforce bottom Z clearance for non-contact support layers as well.
                if (!ts_layer->base_areas.empty()) {
                    const Polygons trimming = get_trim_support_regions(
                        *m_object, ts_layer, 0., m_slicing_params.gap_object_support, 0);
                    if (!trimming.empty())
                        ts_layer->base_areas = diff_ex(ts_layer->base_areas, trimming);
                }
 
                auto &area_groups = ts_layer->area_groups;
 
                for (auto& expoly : ts_layer->base_areas) {
                    //if (area(expoly) < SQ(scale_(1))) continue;
                    area_groups.emplace_back(&expoly, SupportLayer::BaseType, max_layers_above_base);
                    area_groups.back().need_infill = overlaps({ expoly }, area_poly);
                    area_groups.back().need_extra_wall = !area_groups.back().need_infill &&
                        !extra_wall_areas.empty() && overlaps({expoly}, extra_wall_areas);
                }
                for (size_t roof_idx = 0; roof_idx < ts_layer->roof_areas.size(); ++roof_idx) {
                    auto &expoly = ts_layer->roof_areas[roof_idx];
                    //if (area(expoly) < SQ(scale_(1))) continue;
                    area_groups.emplace_back(&expoly, SupportLayer::RoofType, max_layers_above_roof);
                    area_groups.back().interface_as_base = roof_idx >= first_base_roof_area;
                }
                for (auto &expoly : ts_layer->floor_areas) {
                    //if (area(expoly) < SQ(scale_(1))) continue;
                    area_groups.emplace_back(&expoly, SupportLayer::FloorType, 10000);
                    area_groups.back().interface_as_base = floor_interface_as_base;
                }
                for (auto &expoly : ts_layer->roof_1st_layer) {
                    //if (area(expoly) < SQ(scale_(1))) continue;
                    area_groups.emplace_back(&expoly, SupportLayer::Roof1stLayer, max_layers_above_roof1);
                    area_groups.back().interface_as_base = top_base_interface_layers > 0;
                }
 
                for (auto &area_group : area_groups) {
                    auto& expoly = area_group.area;
                    expoly->holes.erase(std::remove_if(expoly->holes.begin(), expoly->holes.end(),
                                                       [](auto &hole) {
                                                           auto bbox_size = get_extents(hole).size();
                                                           return bbox_size[0] < scale_(2) && bbox_size[1] < scale_(2);
                                                       }),
                                        expoly->holes.end());
 
                    if (layer_nr < brim_skirt_layers)
                        ts_layer->lslices.emplace_back(*expoly);
                }
 
                ts_layer->lslices = union_ex(ts_layer->lslices);
                //Must update bounding box which is used in avoid crossing perimeter
                ts_layer->lslices_bboxes.clear();
                ts_layer->lslices_bboxes.reserve(ts_layer->lslices.size());
 
                for (const ExPolygon& expoly : ts_layer->lslices)
                    ts_layer->lslices_bboxes.emplace_back(get_extents(expoly));
 
                ts_layer->backup_untyped_slices();
 
            }
        });
        // ORCA: normalize interface_id sequencing to follow printed interface layers only.
        const bool interlaced = m_object_config->support_interface_pattern == smipRectilinearInterlaced;
        int roof_interface_id = 0;
        int floor_interface_id = 0;
        bool has_roof_interface;
        bool has_floor_interface;
 
        for (size_t layer_nr = 0; layer_nr < m_ts_data->layer_heights.size(); ++layer_nr) {
            SupportLayer *ts_layer = m_object->get_support_layer(layer_nr + m_raft_layers);
            if (ts_layer == nullptr)
                continue;
 
            has_roof_interface = false;
            has_floor_interface = false;
 
            for (auto &area_group : ts_layer->area_groups) {
                if (area_group.type == SupportLayer::RoofType || area_group.type == SupportLayer::Roof1stLayer) {
                    if (interlaced)
                        area_group.interface_id = roof_interface_id;
                    has_roof_interface = true;
                } else if (area_group.type == SupportLayer::FloorType) {
                    if (interlaced)
                        area_group.interface_id = floor_interface_id;
                    has_floor_interface = true;
                }
            }
 
            if (has_roof_interface)
                ++roof_interface_id;
 
            if (has_floor_interface)
                ++floor_interface_id;
        }
 
        if (with_lightning_infill)
        {
            const bool global_lightning_infill = true;
 
            std::vector<Polygons> contours;
            std::vector<Polygons> overhangs;
            for (int layer_nr = 1; layer_nr < contact_nodes.size(); layer_nr++) {
                if (print->canceled()) break;
                const std::vector<SupportNode*>& curr_layer_nodes = contact_nodes[layer_nr];
                SupportLayer* ts_layer = m_object->get_support_layer(layer_nr + m_raft_layers);
                assert(ts_layer != nullptr);
 
                // skip if current layer has no points. This fixes potential crash in get_collision (see jira BBL001-355)
                if (curr_layer_nodes.empty()) continue;
                if (ts_layer->height < EPSILON) continue;
                if (ts_layer->area_groups.empty()) continue;
 
                ExPolygons& base_areas = ts_layer->base_areas;
 
                int layer_nr_lower = layer_nr - 1;
                for (; layer_nr_lower >= 0; layer_nr_lower--) {
                    if (!m_object->get_support_layer(layer_nr_lower + m_raft_layers)->area_groups.empty()) break;
                }
                if (layer_nr_lower <= 0) continue;
 
                SupportLayer* lower_layer = m_object->get_support_layer(layer_nr_lower + m_raft_layers);
                ExPolygons& base_areas_lower = lower_layer->base_areas;
 
                ExPolygons overhang;
                if (global_lightning_infill)
                {
                    //search overhangs globally
                    overhang = diff_ex(offset_ex(base_areas_lower, -2.0 * scale_(support_extrusion_width)), base_areas);
                }
                else
                {
                    //search overhangs only on floating islands
                    for (auto& base_area : base_areas)
                        for (auto& hole : base_area.holes)
                        {
                            Polygon rev_hole = hole;
                            rev_hole.make_counter_clockwise();
                            ExPolygons ex_hole;
                            ex_hole.emplace_back(ExPolygon(rev_hole));
                            for (auto& other_area : base_areas)
                                //if (&other_area != &base_area)
                                    ex_hole = diff_ex(ex_hole, other_area);
                            overhang = union_ex(overhang, ex_hole);
                        }
                    overhang = intersection_ex(overhang, offset_ex(base_areas_lower, -0.5 * scale_(support_extrusion_width)));
                }
 
                overhangs.emplace_back(to_polygons(overhang));
                contours.emplace_back(to_polygons(base_areas_lower));
                printZ_to_lightninglayer[lower_layer->print_z] = overhangs.size() - 1;
            }
 
 
            auto m_support_material_flow = support_material_flow(m_object, m_slicing_params.layer_height);
            coordf_t support_spacing = m_object_config->support_base_pattern_spacing.value + m_support_material_flow.spacing();
            coordf_t support_density = std::min(1., m_support_material_flow.spacing() / support_spacing * 2); // for lightning infill the density is defined differently, so need to double it
            generator = std::make_unique<FillLightning::Generator>(m_object, contours, overhangs, []() {}, support_density);
        }
 
        else if (!with_infill) {
            // move the holes to contour so they can be well supported
 
            // check if poly's contour intersects with expoly's contour
            auto intersects_contour = [](Polygon poly, ExPolygon expoly, Point& pt_on_poly, Point& pt_on_expoly, Point& pt_far_on_poly, float dist_thresh = 0.01) {
                Polylines pl_out = intersection_pl(to_polylines(expoly), ExPolygon(poly));
                if (pl_out.empty()) return false;
                float min_dist = std::numeric_limits<float>::max();
                float max_dist = 0;
                for (auto from : poly.points) {
                    for (int i = 0; i < expoly.num_contours(); i++) {
                        const Point* candidate = expoly.contour_or_hole(i).closest_point(from);
                        double       dist2 = vsize2_with_unscale(*candidate - from);
                        if (dist2 < min_dist) {
                            min_dist = dist2;
                            pt_on_poly = from;
                            pt_on_expoly = *candidate;
                            }
                        if (dist2 > max_dist) {
                            max_dist = dist2;
                            pt_far_on_poly = from;
                            }
                        if (dist2 < dist_thresh) { return true; }
                        }
                    }
                return false;
                };
 
            // polygon pointer: depth, direction, farPoint
            std::map<const Polygon*, std::tuple<int, Point, Point>> holePropagationInfos;
            for (int layer_nr = contact_nodes.size() - 1; layer_nr > 0; layer_nr--) {
                if (print->canceled()) break;
                //m_object->print()->set_status(66, (boost::format(_u8L("Support: fix holes at layer %d")) % layer_nr).str());
 
                const std::vector<SupportNode*>& curr_layer_nodes = contact_nodes[layer_nr];
                SupportLayer* ts_layer = m_object->get_support_layer(layer_nr + m_raft_layers);
                assert(ts_layer != nullptr);
 
                // skip if current layer has no points. This fixes potential crash in get_collision (see jira BBL001-355)
                if (curr_layer_nodes.empty()) continue;
                if (ts_layer->height < EPSILON) continue;
                if (ts_layer->area_groups.empty()) continue;
 
                int layer_nr_lower = layer_nr - 1;
                for (; layer_nr_lower >= 0; layer_nr_lower--) {
                    if (!m_object->get_support_layer(layer_nr_lower + m_raft_layers)->area_groups.empty()) break;
                }
                if (layer_nr_lower < 0) continue;
                auto& area_groups_lower = m_object->get_support_layer(layer_nr_lower + m_raft_layers)->area_groups;
 
                for (const auto& area_group : ts_layer->area_groups) {
                    if (area_group.type != SupportLayer::BaseType) continue;
                    const auto& area = area_group.area;
                    for (const auto& hole : area->holes) {
                        // auto hole_bbox = get_extents(hole).polygon();
                        for (auto& area_group_lower : area_groups_lower) {
                            if (area_group.type != SupportLayer::BaseType) continue;
                            auto& base_area_lower = *area_group_lower.area;
                            Point pt_on_poly, pt_on_expoly, pt_far_on_poly;
                            // if a hole doesn't intersect with lower layer's contours, add a hole to lower layer and move it slightly to the contour
                            if (base_area_lower.contour.contains(hole.points.front()) && !intersects_contour(hole, base_area_lower, pt_on_poly, pt_on_expoly, pt_far_on_poly)) {
                                Polygon hole_lower = hole;
                                Point   direction = normal(pt_on_expoly - pt_on_poly, line_width_scaled / 2);
                                hole_lower.translate(direction);
                                // note to expand a hole, we need to do negative offset
                                auto hole_expanded = offset(hole_lower, -line_width_scaled / 4, jtSquare);
                                if (!hole_expanded.empty()) {
                                    base_area_lower.holes.push_back(std::move(hole_expanded[0]));
                                    holePropagationInfos.insert({ &base_area_lower.holes.back(), {25, direction, pt_far_on_poly} });
                                    }
                                break;
                                }
                            else if (holePropagationInfos.find(&hole) != holePropagationInfos.end() && std::get<0>(holePropagationInfos[&hole]) > 0 &&
                                base_area_lower.contour.contains(std::get<2>(holePropagationInfos[&hole]))) {
                                Polygon hole_lower = hole;
                                auto&& direction = std::get<1>(holePropagationInfos[&hole]);
                                hole_lower.translate(direction);
                                // note to shrink a hole, we need to do positive offset
                                auto  hole_expanded = offset(hole_lower, line_width_scaled / 2, jtSquare);
                                Point farPoint = std::get<2>(holePropagationInfos[&hole]) + direction * 2;
                                if (!hole_expanded.empty()) {
                                    base_area_lower.holes.push_back(std::move(hole_expanded[0]));
                                    holePropagationInfos.insert({ &base_area_lower.holes.back(), {std::get<0>(holePropagationInfos[&hole]) - 1, direction, farPoint} });
                                    }
                                break;
                                }
                            }
                        {
                        // if roof1 interface is inside a hole, need to expand the interface
                        for (auto& roof1 : ts_layer->roof_1st_layer) {
                            //if (hole.contains(roof1.contour.points.front()) && hole.contains(roof1.contour.bounding_box().center()))
                            bool is_inside_hole = std::all_of(roof1.contour.points.begin(), roof1.contour.points.end(), [&hole](Point& pt) { return hole.contains(pt); });
                            if (is_inside_hole) {
                                Polygon hole_reoriented = hole;
                                if (roof1.contour.is_counter_clockwise())
                                    hole_reoriented.make_counter_clockwise();
                                else if (roof1.contour.is_clockwise())
                                    hole_reoriented.make_clockwise();
                                auto tmp = union_({ roof1.contour }, { hole_reoriented });
                                if (!tmp.empty()) roof1.contour = tmp[0];
 
                                // make sure 1) roof1 and object 2) roof1 and roof, won't intersect
                                // Note: We can't replace roof1 directly, as we have recorded its address.
                                //       So instead we need to replace its members one by one.
                                auto tmp1 = diff_ex(roof1, get_collision(0, m_ts_data->layer_heights[layer_nr].obj_layer_nr));
                                tmp1 = diff_ex(tmp1, ts_layer->roof_areas);
                                if (!tmp1.empty()) {
                                    roof1.contour = std::move(tmp1[0].contour);
                                    roof1.holes = std::move(tmp1[0].holes);
                                    }
                                break;
                                }
                            }
                        }
                        }
                    }
                }
            }
 
 
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
    for (int layer_nr = m_object->support_layer_count() - 1; layer_nr >= 0; layer_nr--) {
        SupportLayer* ts_layer = m_object->get_support_layer(layer_nr + m_raft_layers);
        ExPolygons& base_areas = ts_layer->base_areas;
        ExPolygons& roof_areas = ts_layer->roof_areas;
        ExPolygons& roof_1st_layer = ts_layer->roof_1st_layer;
        ExPolygons roofs = roof_areas; append(roofs, roof_1st_layer);
        if (base_areas.empty() && roof_areas.empty() && roof_1st_layer.empty()) continue;
        draw_contours_and_nodes_to_svg(debug_out_path("circles_%d_%.2f.svg", layer_nr, ts_layer->print_z), base_areas, roofs, ts_layer->lslices_extrudable, {}, {}, {"base", "roof", "lslices"}, {"blue","red","black"});
    }
#endif  // SUPPORT_TREE_DEBUG_TO_SVG
 
    SupportLayerPtrs& ts_layers = m_object->support_layers();
    // Orca: the vector owns its layers, so the dropped ones are deleted before they are erased.
    // std::stable_partition (unlike std::remove_if) leaves exactly the dropped layers in the tail.
    // Only heights below EPSILON are dropped; written as !(height < EPSILON), a NaN height is kept.
    auto iter = std::stable_partition(ts_layers.begin(), ts_layers.end(), [](SupportLayer* ts_layer) { return !(ts_layer->height < EPSILON); });
    for (auto it = iter; it != ts_layers.end(); ++it)
        delete *it;
    ts_layers.erase(iter, ts_layers.end());
    for (int layer_nr = 0; layer_nr < ts_layers.size(); layer_nr++) {
        ts_layers[layer_nr]->upper_layer = layer_nr != ts_layers.size() - 1 ? ts_layers[layer_nr + 1] : nullptr;
        ts_layers[layer_nr]->lower_layer = layer_nr > 0 ? ts_layers[layer_nr - 1] : nullptr;
    }
}

References Slic3r::angle(), Slic3r::MultiPoint::append(), avg_node_per_layer, Slic3r::Print::config(), draw_circles(), Slic3r::Print::has_brim(), Slic3r::Print::has_infinite_skirt(), Slic3r::BeltFloorContext::init(), Slic3r::ipLightning, Slic3r::layer_height(), m_object, m_object_config, m_print_config, m_raft_layers, m_slicing_params, m_support_params, m_ts_data, nodes_angle, Slic3r::nozzle_diameter(), Slic3r::number_of_support_interface_bottom_layers(), Slic3r::Print::objects(), Slic3r::PrintObjectConfig, Slic3r::range(), scale_, Slic3r::sqr(), and TAU.

Referenced by draw_circles(), and generate().

Here is the call graph for this function:

Here is the caller graph for this function:

drop_nodes()

void Slic3r::TreeSupport::drop_nodes ( )

private

Drops down the nodes of the tree support towards the build plate.

This is where the cleverness of tree support comes in: The nodes stay on their 2D layers but on the next layer they are slightly shifted. This causes them to move towards each other as they are copied to lower layers which ultimately results in a 3D tree.

Parameters

contact_nodes[in,out]

The nodes in the space that need to be dropped down. The nodes are dropped to lower layers inside the same vector of layers.

{
    const PrintObjectConfig &config = m_object->config();
    // Use Minimum Spanning Tree to connect the points on each layer and move them while dropping them down.
    const coordf_t support_extrusion_width = m_support_params.support_extrusion_width;
    const coordf_t layer_height = config.layer_height.value;
    const double angle = config.tree_support_branch_angle.value * M_PI / 180.;
    const int wall_count = std::max(1, config.tree_support_wall_count.value);
    double tan_angle = tan(angle); // when nodes are thick, they can move further. this is the max angle
    const coordf_t max_move_distance = (angle < M_PI / 2) ? (coordf_t)(tan_angle * layer_height)*wall_count : std::numeric_limits<coordf_t>::max();
    const double max_move_distance2 = max_move_distance * max_move_distance;
    const size_t tip_layers = base_radius / layer_height; //The number of layers to be shrinking the circle to create a tip. This produces a 45 degree angle.
    const coordf_t radius_sample_resolution = m_ts_data->m_radius_sample_resolution;
    const bool support_on_buildplate_only = config.support_on_build_plate_only.value;
    const bool has_belt_floor = std::abs(m_slicing_params.belt_floor_shear_factor) > EPSILON;
    const size_t bottom_interface_layers = number_of_support_interface_bottom_layers(config);
    SupportNode::diameter_angle_scale_factor = diameter_angle_scale_factor;
    float        DO_NOT_MOVER_UNDER_MM       = is_slim ? 0 : 5;                     // do not move contact points under 5mm
 
    auto get_max_move_dist = [this, tan_angle, support_extrusion_width](const SupportNode *node, int power = 1) {
        if (node->max_move_dist == 0) {
            node->radius        = get_radius(node);
            node->max_move_dist = std::min(tan_angle * node->height, support_extrusion_width);
        }
        double move_dist = node->max_move_dist;
        if (power == 2) move_dist = SQ(move_dist);
        return move_dist;
    };
 
    std::vector<LayerHeightData> &layer_heights = m_ts_data->layer_heights;
    if (layer_heights.empty()) return;
 
    // precalculate avoidance of all possible radii.
    // This will cause computing more (radius, layer_nr) pairs, but it's worth to do so since we are doning this in parallel.
    if (1) {
        typedef std::chrono::high_resolution_clock clock_;
        typedef std::chrono::duration<double, std::ratio<1> > second_;
        std::chrono::time_point<clock_> t0{ clock_::now() };
 
        // get all the possible radiis
        std::vector<std::set<coordf_t> > all_layer_radius(contact_nodes.size());
        std::vector<std::set<coordf_t>> all_layer_node_dist(contact_nodes.size());
        for (size_t layer_nr = contact_nodes.size() - 1; layer_nr > 0; layer_nr--) {
            auto& layer_radius = all_layer_radius[layer_nr];
            auto& layer_node_dist = all_layer_node_dist[layer_nr];
            for (auto* p_node : contact_nodes[layer_nr]) {
                layer_node_dist.emplace(p_node->dist_mm_to_top);
            }
            size_t layer_nr_next = layer_nr - 1;
            if (layer_nr_next <= contact_nodes.size() - 1 && layer_nr_next > 0) {
                for (auto node_dist : layer_node_dist)
                    all_layer_node_dist[layer_nr_next].emplace(node_dist + layer_heights[layer_nr].height);
            }
            for (auto node_dist : layer_node_dist) {
                layer_radius.emplace(calc_radius(node_dist));
            }
        }
 
        // parallel pre-compute avoidance
        tbb::parallel_for(tbb::blocked_range<size_t>(0, contact_nodes.size() - 1), [&](const tbb::blocked_range<size_t> &range) {
            for (size_t layer_nr = range.begin(); layer_nr < range.end(); layer_nr++) {
            for (auto node_radius : all_layer_radius[layer_nr]) {
                size_t obj_layer_nr= layer_heights[layer_nr].obj_layer_nr;
                m_ts_data->get_avoidance(node_radius, obj_layer_nr);
                get_collision(0, obj_layer_nr);
                get_collision(node_radius, obj_layer_nr);
            }
        }
        });
 
        double duration{ std::chrono::duration_cast<second_>(clock_::now() - t0).count() };
        BOOST_LOG_TRIVIAL(debug) << "finish pre calculate_avoidance. before m_avoidance_cache.size()=" << m_ts_data->m_avoidance_cache.size()
            << ", takes " << duration << " secs.";
    }
 
    m_spanning_trees.resize(contact_nodes.size());
    //m_mst_line_x_layer_contour_caches.resize(contact_nodes.size());
 
    for (size_t layer_nr = contact_nodes.size() - 1; layer_nr > 0; layer_nr--) // Skip layer 0, since we can't drop down the vertices there.
    {
        if (m_object->print()->canceled())
            break;
 
        auto& layer_contact_nodes = contact_nodes[layer_nr];
        if (layer_contact_nodes.empty())
            continue;
 
        int layer_nr_next = layer_nr - 1;
        coordf_t print_z = layer_heights[layer_nr].print_z;
        coordf_t print_z_next = layer_heights[layer_nr_next].print_z;
        coordf_t height_next   = layer_heights[layer_nr_next].height;
        size_t   obj_layer_nr  = layer_heights[layer_nr].obj_layer_nr;
        size_t   obj_layer_nr_next = layer_heights[layer_nr_next].obj_layer_nr;
 
        std::deque<std::pair<size_t, SupportNode*>> unsupported_branch_leaves; // All nodes that are leaves on this layer that would result in unsupported ('mid-air') branches.
 
        m_object->print()->set_status(60 + int(10 * (1 - float(layer_nr) / contact_nodes.size())), _u8L("Generating support"));// (boost::format(_u8L("Support: propagate branches at layer %d")) % layer_nr).str());
 
        Polygons layer_contours = m_ts_data->get_contours_with_holes(obj_layer_nr);
        //std::unordered_map<Line, bool, LineHash>& mst_line_x_layer_contour_cache = m_mst_line_x_layer_contour_caches[layer_nr];
        tbb::concurrent_unordered_map<Line, bool, LineHash> mst_line_x_layer_contour_cache;
        auto is_line_cut_by_contour = [&mst_line_x_layer_contour_cache,&layer_contours](Point a, Point b)
        {
            auto iter = mst_line_x_layer_contour_cache.find({ a, b });
            if (iter != mst_line_x_layer_contour_cache.end()) {
                if (iter->second)
                    return true;
            }
            else {
                profiler.tic();
                Line ln(b, a);
                Lines pls_intersect = intersection_ln(ln, layer_contours);
                mst_line_x_layer_contour_cache.insert({ {a, b}, !pls_intersect.empty() });
                mst_line_x_layer_contour_cache.insert({ ln, !pls_intersect.empty() });
                profiler.stage_add(STAGE_intersection_ln);
                if (!pls_intersect.empty())
                    return true;
            }
            return false;
        };
 
        //Group together all nodes for each part.
        const ExPolygons& parts = m_ts_data->m_layer_outlines_below[obj_layer_nr];
        std::vector<std::unordered_map<Point, SupportNode*, PointHash>> nodes_per_part(1 + parts.size()); //All nodes that aren't inside a part get grouped together in the 0th part.
        for (SupportNode* p_node : layer_contact_nodes)
        {
            const SupportNode& node = *p_node;
 
            if (support_on_buildplate_only && !node.to_buildplate) //Can't rest on model and unable to reach the build plate. Then we must drop the node and leave parts unsupported.
            {
                unsupported_branch_leaves.push_front({ layer_nr, p_node });
                continue;
            }
            if (node.to_buildplate || parts.empty()) //It's outside, so make it go towards the build plate.
            {
                nodes_per_part[0][node.position] = p_node;
                continue;
            }
 
            /* Find which part this node is located in and group the nodes in
             * the same part together. Since nodes have a radius and the
             * avoidance areas are offset by that radius, the set of parts may
             * be different per node. Here we consider a node to be inside the
             * part that is closest. The node may be inside a bigger part that
             * is actually two parts merged together due to an offset. In that
             * case we may incorrectly keep two nodes separate, but at least
             * every node falls into some group.
             */
            coordf_t closest_part_distance2 = std::numeric_limits<coordf_t>::max();
            size_t closest_part = -1;
            for (size_t part_index = 0; part_index < parts.size(); part_index++)
            {
                //constexpr bool border_result = true;
                if (is_inside_ex(parts[part_index], node.position)) //If it's inside, the distance is 0 and this part is considered the best.
                {
                    closest_part = part_index;
                    closest_part_distance2 = 0;
                    break;
                }
 
                Point closest_point = *parts[part_index].contour.closest_point(node.position);
                const coordf_t distance2 = vsize2_with_unscale(node.position - closest_point);
                if (distance2 < closest_part_distance2)
                {
                    closest_part_distance2 = distance2;
                    closest_part = part_index;
                }
            }
            //Put it in the best one.
            nodes_per_part[closest_part + 1][node.position] = p_node; //Index + 1 because the 0th index is the outside part.
        }
 
        //Create a MST for every part.
        profiler.tic();
        //std::vector<MinimumSpanningTree>& spanning_trees = m_spanning_trees[layer_nr];
        std::vector<MinimumSpanningTree> spanning_trees;
        for (const std::unordered_map<Point, SupportNode*, PointHash>& group : nodes_per_part)
        {
            std::vector<Point> points_to_buildplate;
            for (const std::pair<const Point, SupportNode*>& entry : group)
            {
                points_to_buildplate.emplace_back(entry.first); //Just the position of the node.
            }
            spanning_trees.emplace_back(points_to_buildplate);
        }
        profiler.stage_add(STAGE_MinimumSpanningTree);
 
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
        coordf_t branch_radius_temp = 0;
        coordf_t max_y = std::numeric_limits<coordf_t>::min();
        draw_layer_mst(debug_out_path("mtree_%.2f.svg", print_z), spanning_trees, m_object->get_layer(obj_layer_nr)->lslices_extrudable);
#endif
        for (size_t group_index = 0; group_index < nodes_per_part.size(); group_index++)
        {
            auto& nodes_this_part = nodes_per_part[group_index];
            const MinimumSpanningTree& mst = spanning_trees[group_index];
            //In the first pass, merge all nodes that are close together.
            std::vector<std::pair<const Point, SupportNode*>> nodes_vec(nodes_this_part.begin(), nodes_this_part.end());
            // Sequential: nodes merge into and invalidate each other in place, so parallel execution
            // makes the merge order (and thus the result) depend on thread scheduling.
            std::for_each(nodes_vec.begin(), nodes_vec.end(), [&](const std::pair<const Point, SupportNode*>& entry) {
                SupportNode* p_node = entry.second;
                SupportNode& node = *p_node;
                if (!p_node->valid)
                {
                    return; //Delete this node (don't create a new node for it on the next layer).
                }
                const std::vector<Point>& neighbours = mst.adjacent_nodes(node.position);
                if (node.type == ePolygon) {
                    // Remove all circle neighbours that are completely inside the polygon and merge them into this node.
                    for (const Point &neighbour : neighbours) {
                        SupportNode *    neighbour_node          = nodes_this_part[neighbour];
                        if (neighbour_node->valid == false) continue;
                        if (neighbour_node->type == ePolygon) continue;
                        coord_t    neighbour_radius = scale_(neighbour_node->radius);
                        Point     pt_north = neighbour + Point(0, neighbour_radius), pt_south = neighbour - Point(0, neighbour_radius),
                              pt_west = neighbour - Point(neighbour_radius, 0), pt_east = neighbour + Point(neighbour_radius, 0);
                        if (is_inside_ex(node.overhang, neighbour) && is_inside_ex(node.overhang, pt_north) && is_inside_ex(node.overhang, pt_south)
                            && is_inside_ex(node.overhang, pt_west) && is_inside_ex(node.overhang, pt_east)){
                            node.distance_to_top           = std::max(node.distance_to_top, neighbour_node->distance_to_top);
                            node.support_roof_layers_below = std::max(node.support_roof_layers_below, neighbour_node->support_roof_layers_below);
                            node.dist_mm_to_top            = std::max(node.dist_mm_to_top, neighbour_node->dist_mm_to_top);
                            node.merged_neighbours.push_front(neighbour_node);
                            node.merged_neighbours.insert(node.merged_neighbours.end(), neighbour_node->merged_neighbours.begin(), neighbour_node->merged_neighbours.end());
                            neighbour_node->valid = false;
                        }
                    }
                } else if (neighbours.size() == 1 && vsize2_with_unscale(neighbours[0] - node.position) < get_max_move_dist(p_node, 2) &&
                           mst.adjacent_nodes(neighbours[0]).size() == 1 &&
                           nodes_this_part[neighbours[0]]->type!=ePolygon) // We have just two nodes left, and they're very close, and the only neighbor is not ePolygon
                {
                    //Insert a completely new node and let both original nodes fade.
                    Point next_position = (node.position + neighbours[0]) / 2; //Average position of the two nodes.
                    coordf_t next_radius = calc_radius(node.dist_mm_to_top+height_next);
                    const ExPolygons& avoid_layer = get_avoidance(next_radius, obj_layer_nr_next);
                    if (group_index == 0)
                    {
                        //Avoid collisions.
                        const coordf_t max_move_between_samples = max_move_distance + radius_sample_resolution + EPSILON; //100 micron extra for rounding errors.
                        move_out_expolys(avoid_layer, next_position, radius_sample_resolution + EPSILON, max_move_between_samples);
                    }
 
                    SupportNode* neighbour = nodes_this_part[neighbours[0]];
                    SupportNode* node_parent;
                    if (p_node->parent && neighbour->parent)
                        node_parent = (node.dist_mm_to_top >= neighbour->dist_mm_to_top) ? p_node : neighbour;
                    else
                        node_parent = p_node->parent ? p_node : neighbour;
                    // Make sure the next pass doesn't drop down either of these (since that already happened).
                    node_parent->merged_neighbours.push_front(node_parent == p_node ? neighbour : p_node);
                    // Belt floor: a merged node ends once its whole circle is in the belt
                    // (its slices are clipped to the belt plane in draw_circles(), so it
                    // tapers to a tip on the belt).  Treat as object-surface termination
                    // (not buildplate) so the node gets floor/interface areas instead of
                    // base pads.
                    if (has_belt_floor && belt_node_landed(next_position, std::max(node.radius, neighbour->radius), print_z_next)) {
                        std::scoped_lock lock(m_ts_data->m_mutex);
                        node_parent->to_buildplate = false;
                        neighbour->valid = false;
                        p_node->valid = false;
                    } else {
                        const bool to_buildplate = !is_inside_ex(get_collision(0, obj_layer_nr_next), next_position);
                        SupportNode* next_node = m_ts_data->create_node(next_position, node_parent->distance_to_top + 1, obj_layer_nr_next,
                            node_parent->support_roof_layers_below - (node_parent->distance_to_top >= 0 ? 1 : 0),
                            to_buildplate, node_parent, print_z_next, height_next);
                        get_max_move_dist(next_node);
                        std::scoped_lock lock(m_ts_data->m_mutex);
                        contact_nodes[layer_nr_next].push_back(next_node);
                        neighbour->valid = false;
                        p_node->valid = false;
                    }
                }
                else if (neighbours.size() > 1) //Don't merge leaf nodes because we would then incur movement greater than the maximum move distance.
                {
                    //Remove all neighbours that are too close and merge them into this node.
                    for (const Point& neighbour : neighbours)
                    {
                        if (vsize2_with_unscale(neighbour - node.position) < get_max_move_dist(&node,2))
                        {
                            SupportNode* neighbour_node = nodes_this_part[neighbour];
                            if (neighbour_node->type == ePolygon) continue;
                            // only allow bigger node to merge smaller nodes. See STUDIO-6326
                            if(node.dist_mm_to_top < neighbour_node->dist_mm_to_top) continue;
 
                            m_ts_data->m_mutex.lock();
                            if (p_node->valid)
                            {  // since we are processing all nodes in parallel, p_node may have been deleted by another thread. In this case, we should not delete neighbour_node.
                                node.merged_neighbours.push_front(neighbour_node);
                                node.merged_neighbours.insert(node.merged_neighbours.end(), neighbour_node->merged_neighbours.begin(), neighbour_node->merged_neighbours.end());
                                neighbour_node->valid = false;
                            }
                            m_ts_data->m_mutex.unlock();
                        }
                    }
                }
            }
            );
 
            //In the second pass, move all middle nodes.
            // Still parallel: this pass only reads other nodes. Side effects (invalidation, new
            // nodes, contact_nodes/unsupported_branch_leaves updates) are recorded per node and
            // applied afterwards in node order. Node creation must be deferred too, since
            // SupportNode's constructor writes `parent->child = this` on other nodes.
            struct PendingNode {
                Point        position;
                int          distance_to_top           = 0;
                int          support_roof_layers_below = 0;
                bool         to_buildplate             = false;
                SupportNode *parent                    = nullptr;
                bool         zero_max_move             = false;
                bool         has_overhang              = false;
                ExPolygon    overhang;
                bool         clamp_radius              = false;
                coordf_t     parent_radius             = 0;
                double       dist_to_outer             = 0;
            };
            struct PassTwoResult {
                bool                     invalidate       = false;
                bool                     unsupported_leaf = false;
                std::vector<PendingNode> pending;
            };
            std::vector<PassTwoResult> pass2_results(nodes_vec.size());
            auto pass2_body = [&](size_t node_idx) {
                const std::pair<const Point, SupportNode*>& entry = nodes_vec[node_idx];
                PassTwoResult& pass2_out = pass2_results[node_idx];
 
                SupportNode* p_node = entry.second;
                const SupportNode& node = *p_node;
                if (!p_node->valid)
                {
                    return;
                }
                if (node.type == ePolygon) {
                    // polygon node do not merge or move
                    const bool to_buildplate = true;
                    // keep only the part that won't be removed by the next layer
                    ExPolygons overhangs_next = diff_clipped({ node.overhang }, get_collision(0, obj_layer_nr_next));
                    for(auto& overhang:overhangs_next) {
                        Point        next_pt     = overhang.contour.centroid();
                        // Belt floor: a polygon node ends once all of it is in the belt.
                        // Treat as object-surface termination (not buildplate).
                        if (has_belt_floor && belt_polygon_landed(overhang, print_z_next)) {
                            p_node->to_buildplate = false;
                            continue;
                        }
                        PendingNode pending;
                        pending.position                  = next_pt;
                        pending.distance_to_top           = p_node->distance_to_top + 1;
                        pending.support_roof_layers_below = p_node->support_roof_layers_below - (p_node->distance_to_top >= 0 ? 1 : 0);
                        pending.to_buildplate             = to_buildplate;
                        pending.parent                    = p_node;
                        pending.zero_max_move             = true;
                        pending.has_overhang              = true;
                        pending.overhang                  = std::move(overhang);
                        pass2_out.pending.emplace_back(std::move(pending));
 
                    }
                    return;
                }
 
                //If the branch falls completely inside a collision area (the entire branch would be removed by the X/Y offset), delete it.
                if (group_index > 0 && is_inside_ex(get_collision(0, obj_layer_nr), node.position))
                {
                    std::scoped_lock lock(m_ts_data->m_mutex);
                    const coordf_t branch_radius_node = get_radius(p_node);
                    Point to_outside = projection_onto(get_collision(0, obj_layer_nr), node.position);
                    double dist2_to_outside = vsize2_with_unscale(node.position - to_outside);
                    if (dist2_to_outside >= branch_radius_node * branch_radius_node) //Too far inside.
                    {
                        if (support_on_buildplate_only)
                        {
                            pass2_out.unsupported_leaf = true;
                        }
                        else {
                            pass2_out.invalidate = true;
                        }
                        return;
                    }
                    // if the link between parent and current is cut by contours, mark current as bottom contact node
                    if (p_node->parent && intersection_ln({p_node->position, p_node->parent->position}, layer_contours).empty()==false)
                    {
                        pass2_out.invalidate = true;
                        return;
                    }
                }
                Point next_layer_vertex = node.position;
                Point move_to_neighbor_center;
                std::vector<Point>       moves;
                std::vector<float>       weights;
                const std::vector<Point>& neighbours = mst.adjacent_nodes(node.position);
                // 1. do not merge neighbors under 5mm
                // 2. Only merge node with single neighbor in distance between [max_move_distance, 10mm/layer_height]
                float dist2_to_first_neighbor = neighbours.empty() ? 0 : vsize2_with_unscale(neighbours[0] - node.position);
                if (node.print_z > DO_NOT_MOVER_UNDER_MM &&
                    (neighbours.size() > 1 || (neighbours.size() == 1 && dist2_to_first_neighbor >= get_max_move_dist(p_node, 2)))) // Only nodes that aren't about to collapse.
                {
                    // Move towards the average position of all neighbours.
                    Point sum_direction(0, 0);
                    for (const Point &neighbour : neighbours) {
                        // do not move to the neighbor to be deleted
                        SupportNode *neighbour_node = nodes_this_part[neighbour];
                        if (!neighbour_node->valid) continue;
 
                        Point direction = neighbour - node.position;
                        // do not move to neighbor that's too far away (即使以最大速度移动，在接触热床之前都无法汇聚)
                        float dist2_to_neighbor = vsize2_with_unscale(direction);
 
                        coordf_t branch_bottom_radius = calc_radius(node.dist_mm_to_top + node.print_z);
                        coordf_t neighbour_bottom_radius = calc_radius(neighbour_node->dist_mm_to_top + neighbour_node->print_z);
                        double max_converge_distance = tan_angle * (p_node->print_z - DO_NOT_MOVER_UNDER_MM) + std::max(branch_bottom_radius, neighbour_bottom_radius);
                        if (dist2_to_neighbor > max_converge_distance * max_converge_distance) continue;
 
                        if (is_line_cut_by_contour(node.position, neighbour)) continue;
 
                        if (!is_strong)
                            sum_direction += direction * (1 / dist2_to_neighbor);
                        else
                            sum_direction += direction;
                    }
 
                    if (!is_strong)
                        move_to_neighbor_center = sum_direction;
                    else {
                        if (vsize2_with_unscale(sum_direction) <= get_max_move_dist(p_node, 2)) {
                            move_to_neighbor_center = sum_direction;
                        } else {
                            move_to_neighbor_center = normal(sum_direction, scale_(get_max_move_dist(p_node)));
                        }
                    }
                }
 
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
                if (node.position(1) > max_y) {
                    max_y              = node.position(1);
                    branch_radius_temp = get_radius(p_node);
                }
#endif
                coordf_t next_radius = calc_radius(node.dist_mm_to_top + height_next);
                const ExPolygons& avoidance_next = get_avoidance(next_radius, obj_layer_nr_next);
 
                Point  to_outside         = projection_onto(avoidance_next, node.position);
                Point  direction_to_outer = to_outside - node.position;
                double dist2_to_outer     = vsize2_with_unscale(direction_to_outer);
                // don't move if
                // 1) line of node and to_outside is cut by contour (means supports may intersect with object)
                // 2) it's impossible to move to build plate
                if (is_line_cut_by_contour(node.position, to_outside) || dist2_to_outer > max_move_distance2 * SQ(obj_layer_nr) ||
                    !is_inside_ex(avoidance_next, node.position)) {
                    // try move to outside of lower layer instead
                    Point candidate_vertex = node.position;
                    const coordf_t max_move_between_samples = max_move_distance + radius_sample_resolution + EPSILON; // 100 micron extra for rounding errors.
                    // use get_collision instead of get_avoidance here (See STUDIO-4252)
                    bool           is_outside               = move_out_expolys(get_collision(next_radius,obj_layer_nr_next), candidate_vertex, max_move_between_samples, max_move_between_samples);
                    if (is_outside) {
                        direction_to_outer = candidate_vertex - node.position;
                        dist2_to_outer    = vsize2_with_unscale(direction_to_outer);
                    } else {
                        direction_to_outer = Point(0, 0);
                        dist2_to_outer     = 0;
                    }
                }
                // move to the averaged direction of neighbor center and contour edge if they are roughly same direction
                Point movement;
                if (!is_strong)
                    movement = move_to_neighbor_center*2 + (dist2_to_outer > EPSILON ? direction_to_outer * (1 / dist2_to_outer) : Point(0, 0));
                else {
                    if (movement.dot(move_to_neighbor_center) >= 0.2 || move_to_neighbor_center == Point(0, 0))
                        movement = direction_to_outer + move_to_neighbor_center;
                    else
                        movement = move_to_neighbor_center; // otherwise move to neighbor center first
                }
 
                if (node.is_sharp_tail && node.dist_mm_to_top < 3) {
                    movement = normal(node.skin_direction, scale_(get_max_move_dist(&node)));
                }
                else if (dist2_to_outer > 0)
                    movement = normal(direction_to_outer, scale_(get_max_move_dist(&node)));
                else
                    movement = normal(move_to_neighbor_center, scale_(get_max_move_dist(&node)));
 
                next_layer_vertex += movement;
 
                if (group_index == 0 && 0) {
                    // Avoid collisions.
                    const coordf_t max_move_between_samples = get_max_move_dist(&node, 1) + radius_sample_resolution + EPSILON; // 100 micron extra for rounding errors.
                    bool           is_outside               = move_out_expolys(avoidance_next, next_layer_vertex, radius_sample_resolution + EPSILON, max_move_between_samples);
                    if (!is_outside) {
                        Point candidate_vertex = node.position;
                        is_outside             = move_out_expolys(avoidance_next, candidate_vertex, radius_sample_resolution + EPSILON, max_move_between_samples);
                        if (is_outside) { next_layer_vertex = candidate_vertex; }
                    }
                }
                // Belt floor: a node ends once its whole circle is in the belt; until
                // then it keeps dropping and draw_circles() clips each layer's circle
                // to the belt plane, so the branch tapers to a tip on the belt.
                // Treat as object-surface termination (not buildplate).
                if (has_belt_floor && belt_node_landed(next_layer_vertex, node.radius, print_z_next)) {
                    p_node->to_buildplate = false;
                    return; // from parallel_for_each lambda
                }
                const ExPolygons& next_collision = get_collision(0, obj_layer_nr_next);
                const bool   to_buildplate  = !is_inside_ex(m_ts_data->m_layer_outlines[obj_layer_nr_next], next_layer_vertex);
                // don't increase radius if next node will collide partially with the object (STUDIO-7883)
                to_outside             = projection_onto(next_collision, next_layer_vertex);
                direction_to_outer     = to_outside - node.position;
                double dist_to_outer   = unscale_(direction_to_outer.cast<double>().norm());
                PendingNode pending;
                pending.position                  = next_layer_vertex;
                pending.distance_to_top           = node.distance_to_top + 1;
                pending.support_roof_layers_below = node.support_roof_layers_below - (node.distance_to_top >= 0 ? 1 : 0);
                pending.to_buildplate             = to_buildplate;
                pending.parent                    = p_node;
                pending.clamp_radius              = true;
                pending.parent_radius             = node.radius;
                pending.dist_to_outer             = dist_to_outer;
                pass2_out.pending.emplace_back(std::move(pending));
            };
            tbb::parallel_for(tbb::blocked_range<size_t>(0, nodes_vec.size()),
                [&pass2_body](const tbb::blocked_range<size_t>& node_range) {
                    for (size_t node_idx = node_range.begin(); node_idx < node_range.end(); ++ node_idx)
                        pass2_body(node_idx);
                });
            // Apply the recorded side effects in node order.
            for (size_t node_idx = 0; node_idx < nodes_vec.size(); ++ node_idx) {
                PassTwoResult& pass2_out = pass2_results[node_idx];
                for (PendingNode& pending : pass2_out.pending) {
                    SupportNode* next_node = m_ts_data->create_node(pending.position, pending.distance_to_top, obj_layer_nr_next,
                        pending.support_roof_layers_below, pending.to_buildplate, pending.parent, print_z_next, height_next);
                    if (pending.zero_max_move)
                        next_node->max_move_dist = 0;
                    if (pending.has_overhang)
                        next_node->overhang = std::move(pending.overhang);
                    if (pending.clamp_radius) {
                        next_node->radius = std::max(pending.parent_radius, std::min(next_node->radius, pending.dist_to_outer));
                        get_max_move_dist(next_node);
                    }
                    contact_nodes[layer_nr_next].push_back(next_node);
                }
                if (pass2_out.unsupported_leaf)
                    unsupported_branch_leaves.push_front({ layer_nr, nodes_vec[node_idx].second });
                if (pass2_out.invalidate)
                    nodes_vec[node_idx].second->valid = false;
            }
        }
 
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
        if (contact_nodes[layer_nr].empty() == false) {
            draw_contours_and_nodes_to_svg(debug_out_path("contact_points_%.2f.svg", contact_nodes[layer_nr][0]->print_z), get_collision(0,obj_layer_nr_next),
                                           get_avoidance(branch_radius_temp, obj_layer_nr),
                                           m_ts_data->m_layer_outlines[obj_layer_nr],
            contact_nodes[layer_nr], contact_nodes[layer_nr_next], { "overhang","avoid","outline" }, { "blue","red","yellow" });
 
            BOOST_LOG_TRIVIAL(debug) << "drop_nodes layer->next " << layer_nr << "->" << layer_nr_next << ", print_z=" << print_z
                << ", num points: " << contact_nodes[layer_nr].size() << "->" << contact_nodes[layer_nr_next].size();
            for (size_t i = 0; i < std::min(size_t(5), contact_nodes[layer_nr].size()); i++) {
                auto &node = contact_nodes[layer_nr][i];
                BOOST_LOG_TRIVIAL(debug) << "\t node " << i << ", pos=" << node->position << ", move = " << node->movement;
            }
        }
#endif
 
        // Prune all branches that couldn't find support on either the model or the buildplate (resulting in 'mid-air' branches).
        for (;! unsupported_branch_leaves.empty(); unsupported_branch_leaves.pop_back())
        {
            const auto& entry = unsupported_branch_leaves.back();
            SupportNode* i_node = entry.second;
            for (; i_node != nullptr; i_node = i_node->parent)
            {
                size_t i_layer = i_node->obj_layer_nr;
                {
                    // update the parent-child chain
                    if (i_node->parent) {
                        i_node->parent->child = i_node->child;
                        for (SupportNode* parent : i_node->parents) {
                        if (parent->child==i_node)
                            parent->child = i_node->child;
                        }
                    }
                    if (i_node->child) {
                        i_node->child->parent = i_node->parent;
                        i_node->child->parents.erase(std::find(i_node->child->parents.begin(), i_node->child->parents.end(), i_node));
                        append(i_node->child->parents, i_node->parents);
                    }
                    i_node->is_processed = true;  // mark to be deleted later
 
                    for (SupportNode* neighbour : i_node->merged_neighbours)
                    {
                        if (neighbour && !neighbour->is_processed)
                            unsupported_branch_leaves.push_front({ i_layer, neighbour });
                    }
                }
            }
        }
        for (auto &layer_contact_nodes : contact_nodes) {
            if (!layer_contact_nodes.empty())
                layer_contact_nodes.erase(std::remove_if(layer_contact_nodes.begin(), layer_contact_nodes.end(), [](SupportNode *node) { return node->is_processed; }),
                                          layer_contact_nodes.end());
        }
    }
 
    BOOST_LOG_TRIVIAL(debug) << "after m_avoidance_cache.size()=" << m_ts_data->m_avoidance_cache.size();
}

References Slic3r::angle(), base_radius, calc_radius(), contact_nodes, Slic3r::SupportNode::diameter_angle_scale_factor, diameter_angle_scale_factor, drop_nodes(), EPSILON, get_radius(), is_slim, Slic3r::layer_height(), m_object, M_PI, m_slicing_params, m_support_params, m_ts_data, Slic3r::number_of_support_interface_bottom_layers(), Slic3r::PrintObjectConfig, Slic3r::range(), and SQ.

Referenced by drop_nodes(), and generate().

Here is the call graph for this function:

Here is the caller graph for this function:

generate()

void Slic3r::TreeSupport::generate

(

)

Create the areas that need support.

These areas are stored inside the given SliceDataStorage object.

Parameters

storage

The data storage where the mesh data is gotten from and where the resulting support areas are stored.

{
    if (!is_tree(m_object_config->support_type.value)) return;
 
    if (m_support_params.support_style == smsTreeOrganic) {
        generate_tree_support_3D(*m_object, this, this->throw_on_cancel);
        return;
    }
 
    profiler.stage_start(STAGE_total);
 
    // Generate overhang areas
    profiler.stage_start(STAGE_DETECT_OVERHANGS);
    m_object->print()->set_status(55, _u8L("Generating support"));
    detect_overhangs();
    profiler.stage_finish(STAGE_DETECT_OVERHANGS);
 
    create_tree_support_layers();
    m_ts_data = m_object->alloc_tree_support_preview_cache();
    m_ts_data->is_slim = is_slim;
    // // get the ring of outside plate
    // auto tmp= diff_ex(offset_ex(m_machine_border, scale_(100)), m_machine_border);
    // if (!tmp.empty()) m_ts_data->m_machine_border = tmp[0];
 
    std::vector<TreeSupport3D::SupportElements> move_bounds(m_highest_overhang_layer + 1);
    profiler.stage_start(STAGE_GENERATE_CONTACT_NODES);
    m_object->print()->set_status(56, _u8L("Support: generate contact points"));
    generate_contact_points();
    profiler.stage_finish(STAGE_GENERATE_CONTACT_NODES);
 
    m_ts_data->layer_heights = plan_layer_heights();
 
    //Drop nodes to lower layers.
    profiler.stage_start(STAGE_DROP_DOWN_NODES);
    m_object->print()->set_status(60, _u8L("Generating support"));
    drop_nodes();
    profiler.stage_finish(STAGE_DROP_DOWN_NODES);
 
    smooth_nodes();// , tree_support_3d_config);
 
    //Generate support areas.
    profiler.stage_start(STAGE_DRAW_CIRCLES);
    m_object->print()->set_status(65, _u8L("Generating support"));
    draw_circles();
    profiler.stage_finish(STAGE_DRAW_CIRCLES);
 
 
 
    profiler.stage_start(STAGE_GENERATE_TOOLPATHS);
    m_object->print()->set_status(70, _u8L("Generating support"));
    generate_toolpaths();
    profiler.stage_finish(STAGE_GENERATE_TOOLPATHS);
 
    profiler.stage_finish(STAGE_total);
    BOOST_LOG_TRIVIAL(info) << "tree support time " << profiler.report();
}

References _u8L, create_tree_support_layers(), detect_overhangs(), draw_circles(), drop_nodes(), generate(), generate_contact_points(), generate_toolpaths(), Slic3r::generate_tree_support_3D(), is_slim, Slic3r::is_tree(), m_highest_overhang_layer, m_object, m_object_config, m_support_params, m_ts_data, plan_layer_heights(), Slic3r::profiler, smooth_nodes(), Slic3r::smsTreeOrganic, Slic3r::STAGE_DETECT_OVERHANGS, Slic3r::STAGE_DRAW_CIRCLES, Slic3r::STAGE_DROP_DOWN_NODES, Slic3r::STAGE_GENERATE_CONTACT_NODES, Slic3r::STAGE_GENERATE_TOOLPATHS, Slic3r::STAGE_total, and throw_on_cancel.

Referenced by Slic3r::PrintObject::_generate_support_material(), and generate().

Here is the call graph for this function:

Here is the caller graph for this function:

generate_contact_points()

void Slic3r::TreeSupport::generate_contact_points ( )

private

Creates points where support contacts the model.

A set of points is created for each layer.

Parameters

mesh	The mesh to get the overhang areas to support of.
contact_nodes[out]	A vector of mappings from contact points to their tree nodes.
collision_areas	For every layer, the areas where a generated contact point would immediately collide with the model due to the X/Y distance.

Returns

For each layer, a list of points where the tree should connect with the model.

{
    const PrintObjectConfig &config = m_object->config();
    const coordf_t point_spread = scale_(config.tree_support_branch_distance.value);
    const coordf_t max_bridge_length = scale_(config.max_bridge_length.value);
    coord_t    radius_scaled         = scale_(base_radius);
    bool       on_buildplate_only    = m_object_config->support_on_build_plate_only.value;
    const bool has_belt_floor = std::abs(m_slicing_params.belt_floor_shear_factor) > EPSILON;
 
    //First generate grid points to cover the entire area of the print.
    BoundingBox bounding_box = m_object->bounding_box();
    const Point bounding_box_size = bounding_box.max - bounding_box.min;
    constexpr double rotate_angle = 22.0 / 180.0 * M_PI;
 
    const auto center = bounding_box_middle(bounding_box);
    const auto sin_angle = std::sin(rotate_angle);
    const auto cos_angle = std::cos(rotate_angle);
    const Point rotated_dims = Point(
        bounding_box_size(0) * cos_angle + bounding_box_size(1) * sin_angle,
        bounding_box_size(0) * sin_angle + bounding_box_size(1) * cos_angle) / 2;
 
    std::vector<Point> grid_points;
    coordf_t sample_step = std::max(point_spread, max_bridge_length / 2);
    for (auto x = -rotated_dims(0); x < rotated_dims(0); x += sample_step) {
        for (auto y = -rotated_dims(1); y < rotated_dims(1); y += sample_step) {
            Point pt(x, y);
            pt.rotate(cos_angle, sin_angle);
            pt += center;
            if (bounding_box.contains(pt)) {
                grid_points.push_back(pt);
            }
        }
    }
 
    const coordf_t layer_height = config.layer_height.value;
    coordf_t       z_distance_top = this->top_z_distance;
  //  if (!m_support_params.independent_layer_height) {
  //      z_distance_top = round(z_distance_top / layer_height) * layer_height;
  //  // BBS: add extra distance if thick bridge is enabled
  //  // Note: normal support uses print_z, but tree support uses integer layers, so we need to subtract layer_height
  //  if (!m_slicing_params.zero_gap_interface_top && m_object_config->thick_bridges) {
  //      z_distance_top += m_object->layers()[0]->regions()[0]->region().bridging_height_avg(m_object->print()->config()) - layer_height;
    //}
  //  }
    const int z_distance_top_layers = round_up_divide(scale_(z_distance_top), scale_(layer_height)) + 1; //Support must always be 1 layer below overhang.
    int gap_layers = z_distance_top == 0 ? 0 : 1;
 
    size_t support_roof_layers = config.support_interface_top_layers.value;
    coordf_t  thresh_angle = std::min(89.f, config.support_threshold_angle.value < EPSILON ? 30.f : config.support_threshold_angle.value);
    coordf_t  half_overhang_distance = scale_(tan(thresh_angle * M_PI / 180.0) * layer_height / 2);
 
    // fix bug of generating support for very thin objects
    if (m_object->layers().size() <= z_distance_top_layers + 1)
        return;
 
    contact_nodes.clear();
    contact_nodes.resize(m_object->layers().size());
 
    tbb::spin_mutex mtx;
 
    // add vertical enforcer points
    std::vector<float> zs = zs_from_layers(m_object->layers());
    std::vector<std::vector<std::pair<Point,Point>>> vertical_enforcer_points_by_layers(m_object->layer_count());
    for (auto& pt_and_normal : m_vertical_enforcer_points) {
        auto pt = pt_and_normal.first;
        auto normal = pt_and_normal.second;  // normal seems useless
        auto iter = std::lower_bound(zs.begin(), zs.end(), pt.z());
        if (iter != zs.end()) {
            size_t layer_nr = iter - zs.begin();
            if (layer_nr > 0 && layer_nr < contact_nodes.size()) {
                vertical_enforcer_points_by_layers[layer_nr].push_back({ to_2d(pt).cast<coord_t>(),scaled(to_2d(normal)) });
            }
        }
    }
 
    int      nonempty_layers = 0;
    tbb::concurrent_vector<Slic3r::Vec3f> all_nodes;
    tbb::parallel_for(tbb::blocked_range<size_t>(1, m_object->layers().size()), [&](const tbb::blocked_range<size_t>& range) {
        for (size_t layer_nr = range.begin(); layer_nr < range.end(); layer_nr++) {
            if (m_object->print()->canceled())
                break;
            Layer* layer = m_object->get_layer(layer_nr);
            auto& curr_nodes = contact_nodes[layer_nr-1];
 
            std::unordered_set<Point, PointHash> already_inserted;
            auto                                 bottom_z = m_object->get_layer(layer_nr)->bottom_z();
            bool                                 added = false; // Did we add a point this way?
            bool                                 is_sharp_tail = false;
 
            // take the least restrictive avoidance possible
            ExPolygons relevant_forbidden = offset_ex(m_ts_data->m_layer_outlines[layer_nr - 1], scale_(MIN_BRANCH_RADIUS));
            // prevent rounding errors down the line, points placed directly on the line of the forbidden area may not be added otherwise.
            relevant_forbidden = offset_ex(union_ex(relevant_forbidden), scaled<float>(0.005), jtMiter, 1.2);
 
 
            auto insert_point = [&](Point pt, const ExPolygon& overhang, double radius, bool force_add = false, bool add_interface=true) {
                // Belt floor: skip contact points whose bottom_z is at or below
                // the belt floor at this XY position (overhang rests on the belt).
                if (has_belt_floor && bottom_z <= belt_floor_print_z(pt))
                    return (SupportNode*) nullptr;
                Point        hash_pos = pt / ((radius_scaled + 1) / 1);
                SupportNode* contact_node = nullptr;
                if (force_add || !already_inserted.count(hash_pos)) {
                    already_inserted.emplace(hash_pos);
                    bool to_buildplate = true;
                    size_t roof_layers = add_interface ? support_roof_layers : 0;
                    // add a new node as a virtual node which acts as the invisible gap between support and object
                    // distance_to_top=-1: it's virtual
                    // print_z=object_layer->bottom_z: it directly contacts the bottom
                    // height=z_distance_top: it's height is exactly the gap distance
                    // dist_mm_to_top=0: it directly contacts the bottom
                    contact_node = m_ts_data->create_node(pt, -gap_layers, layer_nr-1, roof_layers, to_buildplate, SupportNode::NO_PARENT, bottom_z, z_distance_top, 0,
                                                          radius);
                    contact_node->overhang = overhang;
                    contact_node->is_sharp_tail = is_sharp_tail;
                    curr_nodes.emplace_back(contact_node);
                    added = true;
                };
                return contact_node;
                };
 
            for (const auto& overhang_part : layer->loverhangs)  {
                const auto& overhang_type = this->overhang_types[&overhang_part];
                is_sharp_tail = overhang_type == OverhangType::SharpTail;
                ExPolygons overhangs_regular;
                if (m_support_params.support_style == smsTreeHybrid && overhang_part.area() > m_support_params.thresh_big_overhang && !is_sharp_tail) {
                    overhangs_regular           = offset_ex(intersection_ex({overhang_part}, m_ts_data->m_layer_outlines_below[layer_nr - 1]), radius_scaled);
                    ExPolygons overhangs_normal = diff_ex({overhang_part}, overhangs_regular);
                    if (area(overhangs_normal) > m_support_params.thresh_big_overhang) {
                        // if the outside area is still big, we can need normal nodes
                        for (auto &overhang : overhangs_normal) {
                            BoundingBox  overhang_bounds = get_extents(overhang);
                            double       radius          = unscale_(overhang_bounds.radius());
                            Point        candidate       = overhang_bounds.center();
                            SupportNode *contact_node    = insert_point(candidate, overhang, radius, true, true);
                            if (contact_node) {
                                contact_node->type           = ePolygon;
                                curr_nodes.emplace_back(contact_node);
                            }
                        }
                    }else{
                        // otherwise, all nodes should be circle nodes
                        overhangs_regular = ExPolygons{overhang_part};
                    }
                } else {
                    overhangs_regular = ExPolygons{overhang_part};
                }
 
                for (auto &overhang : overhangs_regular) {
                    bool add_interface = area(overhang) > minimum_roof_area && !is_sharp_tail;
                    BoundingBox overhang_bounds = get_extents(overhang);
                    double      radius          = std::clamp(unscale_(overhang_bounds.radius()), MIN_BRANCH_RADIUS, base_radius);
                    // add supports at corners for both auto and manual overhangs, github #2008
                    auto &points = overhang.contour.points;
                    int   nSize = points.size();
                    for (int i = 0; i < nSize; i++) {
                        auto pt = points[i];
                        Vec2d v1 = (pt - points[(i - 1 + nSize) % nSize]).cast<double>().normalized();
                        Vec2d v2 = (pt - points[(i + 1) % nSize]).cast<double>().normalized();
                        if (v1.dot(v2) > -0.7) { // angle smaller than 135 degrees
                            SupportNode *contact_node = insert_point(pt, overhang, radius, false, add_interface);
                            if (contact_node) {
                                contact_node->is_corner = true;
                            }
                        }
                    }
 
                    // add supports along contours
                    ExPolygon closed_overhang = overhang; // make a copy to add closing point for edge cache
                    if (closed_overhang.contour.points.size() > 1)
                        closed_overhang.contour.points.emplace_back(closed_overhang.contour.points.front());
                    for (Polygon &hole : closed_overhang.holes)
                        if (hole.points.size() > 1)
                            hole.points.emplace_back(hole.points.front());
 
                    libnest2d::placers::EdgeCache<ExPolygon> edge_cache(closed_overhang);
                    for (size_t i = 0; i < edge_cache.holeCount() + 1; i++) {
                        double step     = point_spread / (i == 0 ? edge_cache.circumference() : edge_cache.circumference(i - 1));
                        double distance = 0;
                        while (distance < 1) {
                            auto         pt           = i == 0 ? edge_cache.coords(distance) : edge_cache.coords(i - 1, distance);
                            SupportNode *contact_node = insert_point(pt, overhang,radius, false, add_interface);
                            distance += step;
                        }
                    }
 
                    // don't add inner supports for sharp tails
                    if (is_sharp_tail) continue;
 
                    // add inner supports
                    overhang_bounds.inflated(-radius_scaled);
                    ExPolygons overhang_inner = offset_ex(overhang, -radius_scaled);
                    for (Point candidate : grid_points) {
                        if (overhang_bounds.contains(candidate)) {
                            // BBS: move_inside_expoly shouldn't be used if candidate is already inside, as it moves point to boundary and the inside is not well supported!
                            bool is_inside = is_inside_ex(overhang_inner, candidate);
                            if (is_inside) { SupportNode *contact_node = insert_point(candidate, overhang,radius, false, add_interface); }
                        }
                    }
                }
            }
            for (auto& pt_and_normal : vertical_enforcer_points_by_layers[layer_nr]) {
                is_sharp_tail = true;// fake it as sharp tail point so the contact distance will be 0
                auto vertical_enforcer_point= pt_and_normal.first;
                auto node=insert_point(vertical_enforcer_point, ExPolygon(), false);
                if (node)
                    node->skin_direction = pt_and_normal.second;
            }
            if (!curr_nodes.empty()) nonempty_layers++;
            for (auto node : curr_nodes) { all_nodes.emplace_back(node->position(0), node->position(1), scale_(node->print_z)); }
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
            if (!curr_nodes.empty())
            draw_contours_and_nodes_to_svg(debug_out_path("init_contact_points_%.2f.svg", bottom_z), layer->loverhangs,layer->lslices_extrudable, m_ts_data->m_layer_outlines_below[layer_nr],
                contact_nodes[layer_nr], contact_nodes[layer_nr - 1], { "overhang","lslices","outlines_below"});
#endif
        }}
    ); // end tbb::parallel_for
 
 
 
    int nNodes = all_nodes.size();
    avg_node_per_layer = nodes_angle = 0;
    if (nNodes > 0) {
        avg_node_per_layer = nNodes / nonempty_layers;
        // get orientation of nodes by line fitting
        // line: y=kx+b, where
        //       k=tan(nodes_angle)=(n\sum{xy}-\sum{x}\sum{y})/(n\sum{x^2}-\sum{x}^2)
        float mx = 0, my = 0, mxy = 0, mx2 = 0;
        for (auto &pt : all_nodes) {
            float x = unscale_(pt(0));
            float y = unscale_(pt(1));
            mx += x;
            my += y;
            mxy += x * y;
            mx2 += x * x;
        }
        nodes_angle = atan2(nNodes * mxy - mx * my, nNodes * mx2 - SQ(mx));
 
        BOOST_LOG_TRIVIAL(info) << "avg_node_per_layer=" << avg_node_per_layer << ", nodes_angle=" << nodes_angle;
    }
}

References base_radius, Slic3r::bounding_box(), Slic3r::bounding_box_middle(), Slic3r::center(), contact_nodes, EPSILON, generate_contact_points(), Slic3r::layer_height(), m_object, m_object_config, M_PI, m_slicing_params, m_vertical_enforcer_points, Slic3r::normal(), Slic3r::PrintObjectConfig, Slic3r::range(), Slic3r::Point::rotate(), Slic3r::round_up_divide(), scale_, Slic3r::scaled(), Slic3r::to_2d(), top_z_distance, and Slic3r::zs_from_layers().

Referenced by generate(), and generate_contact_points().

Here is the call graph for this function:

Here is the caller graph for this function:

generate_toolpaths()

void Slic3r::TreeSupport::generate_toolpaths ( )

private

{
    const PrintObjectConfig &object_config = m_object->config();
    coordf_t support_extrusion_width = m_support_params.support_extrusion_width;
    coordf_t nozzle_diameter = nozzle_diameter_for_filament(*m_print_config, object_config.support_filament, m_object->print()->is_BBL_printer());
    coordf_t layer_height = object_config.layer_height.value;
    const size_t wall_count = object_config.tree_support_wall_count.value;
 
    // Check if set to zero, use default if so.
    if (support_extrusion_width <= 0.0)
        support_extrusion_width = Flow::auto_extrusion_width(FlowRole::frSupportMaterial, (float)nozzle_diameter);
 
    // coconut: use same intensity settings as SupportMaterial.cpp
    auto m_support_material_interface_flow = support_material_interface_flow(m_object, float(m_slicing_params.layer_height));
    coordf_t interface_spacing = object_config.support_interface_spacing.value + m_support_material_interface_flow.spacing();
    coordf_t bottom_interface_spacing = object_config.support_bottom_interface_spacing.value + m_support_material_interface_flow.spacing();
    coordf_t interface_density = std::min(1., m_support_material_interface_flow.spacing() / interface_spacing);
    coordf_t bottom_interface_density = std::min(1., m_support_material_interface_flow.spacing() / bottom_interface_spacing);
 
    const coordf_t branch_radius = object_config.tree_support_branch_diameter.value / 2;
    const coordf_t branch_radius_scaled = scale_(branch_radius);
 
    if (m_object->support_layers().empty())
        return;
 
    // calculate fill areas for raft layers
    ExPolygons raft_areas;
    if (m_object->layer_count() > 0) {
        const Layer *layer = m_object->layers().front();
        for (const ExPolygon &expoly : layer->lslices) {
            raft_areas.push_back(expoly);
        }
    }
 
    if (m_object->support_layer_count() > m_raft_layers) {
        const SupportLayer *ts_layer = m_object->get_support_layer(m_raft_layers);
        for (const ExPolygon& expoly : ts_layer->floor_areas)
            raft_areas.push_back(expoly);
        for (const ExPolygon& expoly : ts_layer->roof_areas)
            raft_areas.push_back(expoly);
        for (const ExPolygon& expoly : ts_layer->base_areas)
            raft_areas.push_back(expoly);
    }
 
    raft_areas = offset_ex(raft_areas, scale_(object_config.raft_first_layer_expansion));
 
    size_t layer_nr = 0;
    for (; layer_nr < m_slicing_params.base_raft_layers; layer_nr++) {
        SupportLayer *ts_layer = m_object->get_support_layer(layer_nr);
        coordf_t expand_offset = (layer_nr == 0 ? m_object_config->raft_first_layer_expansion.value : 0.);
        auto raft_areas1 = offset_ex(raft_areas, scale_(expand_offset));
 
        Flow support_flow = Flow(support_extrusion_width, ts_layer->height, nozzle_diameter);
        Fill* filler_raft = Fill::new_from_type(ipRectilinear);
        filler_raft->angle = layer_nr == 0 ? PI/2 : 0;
        filler_raft->spacing = support_flow.spacing();
 
        FillParams fill_params;
        coordf_t raft_density = std::min(1., support_flow.spacing() / (object_config.support_base_pattern_spacing.value + support_flow.spacing()));
        fill_params.density = layer_nr == 0 ? object_config.raft_first_layer_density * 0.01 : raft_density;
        fill_params.dont_adjust = true;
 
        // wall of first layer raft
        if (layer_nr == 0) {
            Flow flow = Flow(support_extrusion_width, ts_layer->height, nozzle_diameter);
            extrusion_entities_append_loops(ts_layer->support_fills.entities, to_polygons(raft_areas1), erSupportMaterial,
                        float(flow.mm3_per_mm()), float(flow.width()), float(flow.height()));
            raft_areas1 = offset_ex(raft_areas1, -flow.scaled_spacing() / 2.);
        }
        fill_expolygons_generate_paths(ts_layer->support_fills.entities, raft_areas1,
            filler_raft, fill_params, erSupportMaterial, support_flow);
    }
 
    // subtract the non-raft support bases, otherwise we'll get support base on top of raft interfaces which is not stable
    ExPolygons first_non_raft_base;
    SupportLayer* first_non_raft_layer = m_object->get_support_layer(m_raft_layers);
    if (first_non_raft_layer) {
        for (auto& area_group : first_non_raft_layer->area_groups) {
            if (area_group.type == SupportLayer::BaseType)
                first_non_raft_base.emplace_back(*area_group.area);
        }
    }
    first_non_raft_base = offset_ex(first_non_raft_base, support_extrusion_width);
    ExPolygons raft_base_areas = intersection_ex(raft_areas, first_non_raft_base);
    ExPolygons raft_interface_areas = diff_ex(raft_areas, raft_base_areas);
 
 
    // raft interfaces
    for (layer_nr = m_slicing_params.base_raft_layers;
         layer_nr < m_slicing_params.base_raft_layers + m_slicing_params.interface_raft_layers;
         layer_nr++)
    {
        SupportLayer *ts_layer = m_object->get_support_layer(layer_nr);
 
        Flow support_flow(support_extrusion_width, ts_layer->height, nozzle_diameter);
        Fill* filler_interface = Fill::new_from_type(ipRectilinear);
        filler_interface->angle = M_PI_2;  // interface should be perpendicular to base
        filler_interface->spacing = support_flow.spacing();
 
        FillParams fill_params;
        fill_params.density = interface_density;
        fill_params.dont_adjust = true;
 
        fill_expolygons_generate_paths(ts_layer->support_fills.entities, raft_interface_areas,
            filler_interface, fill_params, erSupportMaterialInterface, support_flow);
 
        fill_params.density = object_config.raft_first_layer_density * 0.01;
        fill_expolygons_generate_paths(ts_layer->support_fills.entities, raft_base_areas,
            filler_interface, fill_params, erSupportMaterial, support_flow);
    }
 
    // layers between raft and object
    for (; layer_nr < m_raft_layers; layer_nr++) {
        SupportLayer *ts_layer = m_object->get_support_layer(layer_nr);
        Flow support_flow(support_extrusion_width, ts_layer->height, nozzle_diameter);
        Fill* filler_raft = Fill::new_from_type(ipRectilinear);
        filler_raft->angle = M_PI_2;
        filler_raft->spacing = support_flow.spacing();
        for (auto& poly : first_non_raft_base)
            make_perimeter_and_infill(ts_layer->support_fills.entities, poly, std::min(size_t(1), wall_count), support_flow, erSupportMaterial, filler_raft, interface_density, false);
    }
 
    if (m_object->support_layer_count() <= m_raft_layers)
        return;
 
    BoundingBox bbox_object(Point(-scale_(1.), -scale_(1.0)), Point(scale_(1.), scale_(1.)));
    // ORCA: base angle used for explicit interlaced interface orientation.
    const float base_support_angle = Geometry::deg2rad(object_config.support_angle.value);
 
    // Belt floor: the lowest support layer rests on the moving, tilted belt, not
    // on a flat bed — so it must NOT get the bed first-layer treatment (a brim on
    // interface areas, a first-layer-flow sheath at raft_first_layer_density on
    // base areas). That treatment draws a loop along the Z=0 belt-floor line that
    // reads as a stray brim/skirt. Gate those layer_id==0 special cases off when
    // the belt floor is active; false on non-belt printers so behavior is unchanged.
    BeltFloorContext belt_ctx;
    const bool belt_floor_active = belt_ctx.init(m_slicing_params, *m_print_config);
 
    // generate tree support tool paths
    tbb::parallel_for(
        tbb::blocked_range<size_t>(m_raft_layers, m_object->support_layer_count()),
        [&](const tbb::blocked_range<size_t>& range)
        {
            for (size_t layer_id = range.begin(); layer_id < range.end(); layer_id++) {
                if (m_object->print()->canceled())
                    break;
 
                //m_object->print()->set_status(70, (boost::format(_u8L("Support: generate toolpath at layer %d")) % layer_id).str());
 
                SupportLayer* ts_layer = m_object->get_support_layer(layer_id);
                Flow support_flow(support_extrusion_width, ts_layer->height, nozzle_diameter);
                Flow interface_flow = support_material_interface_flow(m_object, ts_layer->height); // update flow using real support layer height
                coordf_t support_spacing         = object_config.support_base_pattern_spacing.value + support_flow.spacing();
                coordf_t support_density         = std::min(1., support_flow.spacing() / support_spacing);
                ts_layer->support_fills.no_sort = false;
                // ORCA: per-layer Fill instances to avoid shared-state races during interlaced interfaces.
                std::shared_ptr<Fill> filler_interface = std::shared_ptr<Fill>(Fill::new_from_type(m_support_params.contact_fill_pattern));
                std::shared_ptr<Fill> filler_Roof1stLayer = std::shared_ptr<Fill>(Fill::new_from_type(ipRectilinear));
                filler_interface->set_bounding_box(bbox_object);
                filler_Roof1stLayer->set_bounding_box(bbox_object);
 
                for (auto& area_group : ts_layer->area_groups) {
                    ExPolygon& poly = *area_group.area;
                    ExPolygons polys;
                    FillParams fill_params;
                    // ORCA: reset interface Fill state per area group to keep angles deterministic.
                    filler_interface->fixed_angle = false;
                    filler_interface->layer_id = size_t(-1);
                    filler_Roof1stLayer->fixed_angle = false;
                    filler_Roof1stLayer->layer_id = size_t(-1);
                    filler_interface->angle = m_support_params.support_interface_angle(area_group.interface_id);
                    if (area_group.type != SupportLayer::BaseType) {
                        // interface
                        if (layer_id == 0 && !belt_floor_active) {
                            Flow flow = m_raft_layers == 0 ? m_object->print()->brim_flow() : support_flow;
                            ExtrusionRole brim_role = (area_group.type == SupportLayer::RoofType && !area_group.interface_as_base) ?
                                erSupportMaterialInterface : erSupportMaterial;
                            make_perimeter_and_inner_brim(ts_layer->support_fills.entities, poly, wall_count, flow,
                                                          brim_role);
                            polys = offset_ex(poly, -flow.scaled_spacing());
                        } else if (area_group.type == SupportLayer::Roof1stLayer) {
                            polys = offset_ex(poly, 0.5*support_flow.scaled_width());
                        }
                        else {
                            polys.push_back(poly);
                        }
                        fill_params.density = interface_density;
                        fill_params.dont_adjust = true;
                    }
                    if (area_group.type == SupportLayer::Roof1stLayer) {
                        // roof_1st_layer
                        // ORCA: Roof1stLayer may be printed with base material when it acts as a contact layer.
                        bool interface_as_base = area_group.interface_as_base;
                        fill_params.density = interface_density;
                        // Note: spacing means the separation between two lines as if they are tightly extruded
                        filler_Roof1stLayer->spacing = interface_flow.spacing();
                        filler_Roof1stLayer->angle = m_support_params.support_interface_angle(area_group.interface_id);
                        fill_params.dont_sort = true;
                        filler_Roof1stLayer->fixed_angle = (m_object_config->support_interface_pattern == smipRectilinearInterlaced ||
                                                            m_object_config->support_interface_pattern == smipRectilinear);
                        Flow interface_base_flow = interface_as_base ? support_flow : interface_flow;
                        ExtrusionRole interface_role = interface_as_base ? erSupportMaterial : erSupportMaterialInterface;
                        // generate a perimeter first to support interface better
                        ExtrusionEntityCollection* temp_support_fills = new ExtrusionEntityCollection();
                        make_perimeter_and_infill(temp_support_fills->entities, poly, 1, interface_base_flow, interface_role,
                            filler_Roof1stLayer.get(), interface_density, false);
                        temp_support_fills->no_sort = true; // make sure loops are first
                        if (!temp_support_fills->entities.empty())
                            ts_layer->support_fills.entities.push_back(temp_support_fills);
                        else
                            delete temp_support_fills;
                    } else if (area_group.type == SupportLayer::FloorType) {
                        // floor_areas
                        bool interface_as_base = area_group.interface_as_base;
                        fill_params.density = bottom_interface_density;
                        filler_interface->spacing = interface_flow.spacing();
 
                        fill_params.dont_sort = (m_object_config->support_interface_pattern == smipGrid ||
                                                m_object_config->support_interface_pattern == smipRectilinearInterlaced);   
 
                        filler_interface->fixed_angle = (m_object_config->support_interface_pattern == smipRectilinearInterlaced ||
                                                        m_object_config->support_interface_pattern == smipRectilinear);
 
                        Flow interface_base_flow = interface_as_base ? support_flow : interface_flow;
                        ExtrusionRole interface_role = interface_as_base ? erSupportMaterial : erSupportMaterialInterface;
                        fill_expolygons_generate_paths(ts_layer->support_fills.entities, polys,
                            filler_interface.get(), fill_params, interface_role, interface_base_flow);
                    } else if (area_group.type == SupportLayer::RoofType) {
                        // roof_areas
                        bool interface_as_base = area_group.interface_as_base;
                        fill_params.density       = interface_density;
                        filler_interface->spacing = interface_flow.spacing();
 
                        fill_params.dont_sort = (m_object_config->support_interface_pattern == smipGrid ||
                                                m_object_config->support_interface_pattern == smipRectilinearInterlaced);   
 
                        filler_interface->fixed_angle = (m_object_config->support_interface_pattern == smipRectilinearInterlaced ||
                                                        m_object_config->support_interface_pattern == smipRectilinear);
 
                        Flow interface_base_flow = interface_as_base ? support_flow : interface_flow;
                        ExtrusionRole interface_role = interface_as_base ? erSupportMaterial : erSupportMaterialInterface;
                        fill_expolygons_generate_paths(ts_layer->support_fills.entities, polys, filler_interface.get(), fill_params, interface_role,
                                                       interface_base_flow);
                    }
                    else {
                        // base_areas
                        bool support_base_on_bed = (layer_id == 0 && m_raft_layers == 0 && !belt_floor_active);
                        Flow flow = support_base_on_bed ? m_support_params.first_layer_flow : support_flow;
                        bool need_infill = with_infill;
                        if(m_object_config->support_base_pattern==smpDefault)
                            need_infill &= area_group.need_infill;
                        // Orca: Use rectilinear for support base on the bed
                        const InfillPattern base_fill_pattern = support_base_on_bed ? ipRectilinear : m_support_params.base_fill_pattern;
                        std::shared_ptr<Fill> filler_support = std::shared_ptr<Fill>(Fill::new_from_type(base_fill_pattern));
                        filler_support->set_bounding_box(bbox_object);
 
                        filler_support->spacing =
                            support_base_on_bed ?
                            flow.spacing() : // Orca: On the bed-contacting support base layer, use first-layer flow spacing directly.
                            support_spacing * support_density; // constant spacing to align support infill lines
                        filler_support->angle = Geometry::deg2rad(object_config.support_angle.value);
 
                        Polygons loops = to_polygons(poly);
                        //ORCA: Group base per area as no_sort to keep outline->fill together.
                        std::unique_ptr<ExtrusionEntityCollection> base_eec = std::make_unique<ExtrusionEntityCollection>();
                        base_eec->no_sort = true;
                        ExtrusionEntitiesPtr &base_dst = base_eec->entities;
                        if (layer_id == 0 && !belt_floor_active) {
                            float density = float(m_object_config->raft_first_layer_density.value * 0.01);
                            fill_expolygons_with_sheath_generate_paths(base_dst, loops, filler_support.get(), density, erSupportMaterial, flow,
                                                                       m_support_params, true, false);
                        }
                        else {
                            //ORCA: Force base walls before infill to keep outline->fill order.
                            if (need_infill && m_support_params.base_fill_pattern != ipLightning) {
                                // allow infill-only mode if support is thick enough (so min_wall_count is 0);
                                // otherwise must draw 1 wall
                                // Don't need extra walls if we have infill. Extra walls may overlap with the infills.
                                size_t min_wall_count = offset(poly, -scale_(support_spacing * 1.5)).empty() ? 1 : 0;
                                make_perimeter_and_infill(base_dst, poly, std::max(min_wall_count, wall_count), flow,
                                    erSupportMaterial, filler_support.get(), support_density, false);
                            }
                            else {
                                SupportParameters support_params = m_support_params;
                                if (area_group.need_extra_wall && object_config.tree_support_wall_count.value == 0)
                                    support_params.tree_branch_diameter_double_wall_area_scaled = 0.1;
                                tree_supports_generate_paths(base_dst, loops, flow, support_params);
                            }
                        }
 
                        //ORCA: Emit lightning infill per base area to avoid interleaving across islands.
                        if (m_support_params.base_fill_pattern == ipLightning) {
                            double print_z = ts_layer->print_z;
                            auto lightning_layer_mapping = printZ_to_lightninglayer.find(print_z);
                            if (lightning_layer_mapping != printZ_to_lightninglayer.end()) {
                                auto &lightning_layer = generator->getTreesForLayer(lightning_layer_mapping->second);
                                ExPolygons areas;
                                areas.emplace_back(poly);
                                areas = offset_ex(areas, -flow.scaled_spacing());
                                for (auto &area : areas) {
                                    Polylines polylines = lightning_layer.convertToLines(to_polygons(area), 0);
                                    for (auto itr = polylines.begin(); itr != polylines.end();) {
                                        if (itr->length() < scale_(1.0))
                                            itr = polylines.erase(itr);
                                        else
                                            itr++;
                                    }
                                    Polylines opt_polylines;
                                    append(opt_polylines, chain_polylines(std::move(polylines)));
                                    extrusion_entities_append_paths(base_dst, opt_polylines, erSupportMaterial,
                                        float(flow.mm3_per_mm()), float(flow.width()), float(flow.height()));
#ifdef SUPPORT_TREE_DEBUG_TO_SVG
                                    std::string name = debug_out_path("trees_polyline_%.2f.svg", ts_layer->print_z);
                                    BoundingBox bbox = get_extents(ts_layer->base_areas);
                                    SVG svg(name, bbox);
                                    if (svg.is_opened()) {
                                        svg.draw(ts_layer->base_areas, "blue");
                                        svg.draw(generator->Overhangs()[lightning_layer_mapping->second], "red");
                                        for (auto &line : opt_polylines) svg.draw(line, "yellow");
                                    }
#endif
                                }
                            }
                        }
 
                        //ORCA: Keep per-area base paths grouped for outline->fill preservation.
                        if (!base_eec->empty())
                            ts_layer->support_fills.entities.push_back(base_eec.release());
                    }
                }
 
                // sort extrusions to reduce travel, also make sure walls go before infills
                if (ts_layer->support_fills.no_sort == false) {
                    chain_and_reorder_extrusion_entities(ts_layer->support_fills.entities);
                }
            }
        }
    );
}

References Slic3r::Fill::angle, Slic3r::SupportLayer::area_groups, Slic3r::Flow::auto_extrusion_width(), Slic3r::SupportLayer::base_areas, Slic3r::SupportLayer::BaseType, Slic3r::Geometry::deg2rad(), Slic3r::FillParams::density, Slic3r::diff_ex(), Slic3r::FillParams::dont_adjust, Slic3r::ExtrusionEntityCollection::entities, Slic3r::erSupportMaterial, Slic3r::erSupportMaterialInterface, Slic3r::extrusion_entities_append_loops(), Slic3r::fill_expolygons_generate_paths(), Slic3r::SupportLayer::floor_areas, Slic3r::frSupportMaterial, generate_toolpaths(), Slic3r::Flow::height(), Slic3r::Layer::height, Slic3r::BeltFloorContext::init(), Slic3r::intersection_ex(), Slic3r::ipRectilinear, Slic3r::layer_height(), Slic3r::Layer::lslices, m_object, m_object_config, m_print_config, m_raft_layers, m_slicing_params, m_support_params, Slic3r::make_perimeter_and_infill(), Slic3r::Flow::mm3_per_mm(), Slic3r::Fill::new_from_type(), Slic3r::nozzle_diameter(), Slic3r::nozzle_diameter_for_filament(), Slic3r::offset_ex(), PI, Slic3r::PrintObjectConfig, Slic3r::range(), Slic3r::SupportLayer::roof_areas, scale_, Slic3r::Flow::scaled_spacing(), Slic3r::Fill::spacing, Slic3r::Flow::spacing(), Slic3r::SupportLayer::support_fills, Slic3r::support_material_interface_flow(), Slic3r::to_polygons(), and Slic3r::Flow::width().

Referenced by generate(), and generate_toolpaths().

Here is the call graph for this function:

Here is the caller graph for this function:

get_avoidance()

const ExPolygons & Slic3r::TreeSupport::get_avoidance ( coordf_t radius, size_t obj_layer_nr )

private

{
    return m_ts_data->get_avoidance(radius, obj_layer_nr);
}

References get_avoidance(), and m_ts_data.

Referenced by get_avoidance().

Here is the call graph for this function:

Here is the caller graph for this function:

get_collision()

const ExPolygons & Slic3r::TreeSupport::get_collision ( coordf_t radius, size_t layer_nr )

private

{
    return m_ts_data->get_collision(radius, layer_nr);
}

References get_collision(), and m_ts_data.

Referenced by get_collision().

Here is the call graph for this function:

Here is the caller graph for this function:

get_collision_polys()

Polygons Slic3r::TreeSupport::get_collision_polys ( coordf_t radius, size_t layer_nr )

private

{
#if USE_SUPPORT_3D
    if (m_model_volumes) {
        bool on_build_plate = m_object_config->support_on_build_plate_only.value;
        const Polygons& collision_polys = m_model_volumes->getCollision(radius, layer_nr, true);
        return collision_polys;
    }
#else
    ExPolygons expolys = m_ts_data->get_collision(radius, layer_nr);
    Polygons polys;
    for (auto& expoly : expolys)
        for (int i = 0; i < expoly.num_contours(); i++)
            polys.emplace_back(std::move(expoly.contour_or_hole(i)));
    return polys;
#endif
    return Polygons();
}

References get_collision_polys(), m_model_volumes, m_object_config, and m_ts_data.

Referenced by get_collision_polys().

Here is the call graph for this function:

Here is the caller graph for this function:

get_radius()

coordf_t Slic3r::TreeSupport::get_radius ( const SupportNode * node )

private

{
    if (node->radius == 0)
        node->radius = calc_radius(node->dist_mm_to_top);
    return node->radius;
}

References calc_radius(), Slic3r::SupportNode::dist_mm_to_top, get_radius(), and Slic3r::SupportNode::radius.

Referenced by drop_nodes(), and get_radius().

Here is the call graph for this function:

Here is the caller graph for this function:

get_trim_support_regions()

Polygons Slic3r::TreeSupport::get_trim_support_regions ( const PrintObject & object, SupportLayer * support_layer_ptr, const coordf_t gap_extra_above, const coordf_t gap_extra_below, const coordf_t gap_xy )

private

{
    static const double sharp_tail_xy_gap = 0.2f;
    static const double no_overlap_xy_gap = 0.2f;
    double gap_xy_scaled = scale_(gap_xy);
    SupportLayer& support_layer = *support_layer_ptr;
    const PrintConfig& print_config = object.print()->config();
 
    size_t idx_object_layer_overlapping = size_t(-1);
 
    auto is_layers_overlap = [](const SupportLayer& support_layer, const Layer& object_layer, coordf_t bridging_height = 0.f) -> bool {
        if (std::abs(support_layer.print_z - object_layer.print_z) < EPSILON)
            return true;
 
        coordf_t object_lh = bridging_height > EPSILON ? bridging_height : object_layer.height;
        if (support_layer.print_z < object_layer.print_z && support_layer.print_z > object_layer.print_z - object_lh)
            return true;
 
        if (support_layer.print_z > object_layer.print_z && support_layer.bottom_z() < object_layer.print_z - EPSILON)
            return true;
 
        return false;
        };
 
    // Find the overlapping object layers including the extra above / below gap.
    coordf_t z_threshold = support_layer.bottom_z() - gap_extra_below + EPSILON;
    idx_object_layer_overlapping = Layer::idx_higher_or_equal(
        object.layers().begin(), object.layers().end(), idx_object_layer_overlapping,
        [z_threshold](const Layer* layer) { return layer->print_z >= z_threshold; });
    // Collect all the object layers intersecting with this layer.
    Polygons polygons_trimming;
    size_t i = idx_object_layer_overlapping;
    for (; i < object.layers().size(); ++i) {
        const Layer& object_layer = *object.layers()[i];
        if (object_layer.bottom_z() > support_layer.print_z + gap_extra_above - EPSILON)
            break;
 
        bool is_overlap = is_layers_overlap(support_layer, object_layer);
        for (const ExPolygon& expoly : object_layer.lslices) {
            // BBS
            bool is_sharptail = !intersection_ex({ expoly }, object_layer.sharp_tails).empty();
            coordf_t trimming_offset = is_sharptail ? scale_(sharp_tail_xy_gap) :
                is_overlap ? gap_xy_scaled :
                scale_(no_overlap_xy_gap);
            polygons_append(polygons_trimming, offset({ expoly }, trimming_offset, SUPPORT_SURFACES_OFFSET_PARAMETERS));
            }
        }
    if (!m_slicing_params.zero_gap_interface_top && m_object_config->thick_bridges) {
        // Collect all bottom surfaces, which will be extruded with a bridging flow.
        for (; i < object.layers().size(); ++i) {
            const Layer& object_layer = *object.layers()[i];
            bool some_region_overlaps = false;
            for (LayerRegion* region : object_layer.regions()) {
                coordf_t bridging_height = region->region().bridging_height_avg(print_config);
                if (object_layer.print_z - bridging_height > support_layer.print_z + gap_extra_above - EPSILON)
                    break;
                some_region_overlaps = true;
 
                bool is_overlap = is_layers_overlap(support_layer, object_layer, bridging_height);
                coordf_t trimming_offset = is_overlap ? gap_xy_scaled : scale_(no_overlap_xy_gap);
                polygons_append(polygons_trimming,
                    offset(region->fill_surfaces.filter_by_type(stBottomBridge), trimming_offset, SUPPORT_SURFACES_OFFSET_PARAMETERS));
                }
            if (!some_region_overlaps)
                break;
            }
        }
 
    return polygons_trimming;
}

References Slic3r::Layer::bottom_z(), Slic3r::empty(), EPSILON, get_trim_support_regions(), Slic3r::Layer::idx_higher_or_equal(), Slic3r::intersection_ex(), Slic3r::Layer::lslices, m_object_config, m_slicing_params, Slic3r::no_overlap_xy_gap, Slic3r::offset(), Slic3r::polygons_append(), Slic3r::Layer::print_z, Slic3r::Layer::regions(), scale_, Slic3r::sharp_tail_xy_gap, Slic3r::Layer::sharp_tails, Slic3r::stBottomBridge, and SUPPORT_SURFACES_OFFSET_PARAMETERS.

Referenced by get_trim_support_regions().

Here is the call graph for this function:

Here is the caller graph for this function:

insert_dropped_node()

void Slic3r::TreeSupport::insert_dropped_node ( std::vector< SupportNode * > & nodes_layer, SupportNode * node )

private

Add a node to the next layer.

If a node is already at that position in the layer, the nodes are merged.

{
    std::vector<SupportNode*>::iterator conflicting_node_it = std::find(nodes_layer.begin(), nodes_layer.end(), p_node);
    if (conflicting_node_it == nodes_layer.end()) //No conflict.
    {
        nodes_layer.emplace_back(p_node);
        return;
    }
 
    SupportNode* conflicting_node = *conflicting_node_it;
    conflicting_node->distance_to_top = std::max(conflicting_node->distance_to_top, p_node->distance_to_top);
    conflicting_node->support_roof_layers_below = std::max(conflicting_node->support_roof_layers_below, p_node->support_roof_layers_below);
}

References Slic3r::SupportNode::distance_to_top, insert_dropped_node(), and Slic3r::SupportNode::support_roof_layers_below.

Referenced by insert_dropped_node().

Here is the call graph for this function:

Here is the caller graph for this function:

move_bounds_to_contact_nodes()

void Slic3r::TreeSupport::move_bounds_to_contact_nodes	(	std::vector< TreeSupport3D::SupportElements > &	move_bounds,
		PrintObject &	print_object,
		const TreeSupport3D::TreeSupportSettings &	config )

{
    m_ts_data = print_object.alloc_tree_support_preview_cache();
    // convert move_bounds back to Support Nodes for tree skeleton preview
    this->contact_nodes.resize(move_bounds.size());
    for (int layer_nr = move_bounds.size() - 1; layer_nr >= 0; layer_nr--) {
        TreeSupport3D::SupportElements &elements      = move_bounds[layer_nr];
        auto            &contact_nodes_layer = this->contact_nodes[layer_nr];
        for (size_t i = 0; i < elements.size(); i++) {
            auto &elem    = elements[i];
            auto &state   = elem.state;
            state.print_z = layer_z(print_object.slicing_parameters(), config, layer_nr);
            auto node = this->create_node(state.result_on_layer, state.distance_to_top, layer_nr, 0, state.to_buildplate, nullptr, state.print_z, config.layer_height);
            contact_nodes_layer.push_back(node);
            if (layer_nr < move_bounds.size() - 1 && !elem.parents.empty()) {
                node->parent = contact_nodes[layer_nr + 1][elem.parents.front()];
                for (int j : elem.parents) {
                    contact_nodes[layer_nr + 1][j]->child = node;
                    node->parents.push_back(contact_nodes[layer_nr + 1][j]);
                }
            }
 
            if (i == 0) { m_ts_data->layer_heights.emplace_back(state.print_z, config.layer_height, std::max(0, layer_nr - 1)); }
        }
    }
}

References Slic3r::PrintObject::alloc_tree_support_preview_cache(), contact_nodes, create_node(), Slic3r::TreeSupport3D::TreeSupportSettings::layer_height, m_ts_data, move_bounds_to_contact_nodes(), and Slic3r::PrintObject::slicing_parameters().

Referenced by move_bounds_to_contact_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

plan_layer_heights()

std::vector< LayerHeightData > Slic3r::TreeSupport::plan_layer_heights ( )

private

Optimize the generation of tree support by pre-planning the layer_heights.

BBS: MusangKing: maximum layer height

{
    std::vector<LayerHeightData> layer_heights;
    std::map<coordf_t, coordf_t> z_heights; // print_z:height
    if (!m_support_params.independent_layer_height) {
        layer_heights.resize(m_object->layer_count());
        for (int layer_nr = 0; layer_nr < m_object->layer_count(); layer_nr++) {
            z_heights[m_object->get_layer(layer_nr)->print_z] = m_object->get_layer(layer_nr)->height;
            layer_heights[layer_nr] = {m_object->get_layer(layer_nr)->print_z, m_object->get_layer(layer_nr)->height, size_t(layer_nr)};
        }
    } else {
        const coordf_t               max_layer_height = m_slicing_params.max_suport_layer_height;
        const coordf_t               min_layer_height = m_slicing_params.min_layer_height;
        std::map<coordf_t, coordf_t> bounds; // print_z: height
        // Keep first layer still
        bounds[m_object->get_layer(0)->print_z] = {m_object->get_layer(0)->height};
        std::vector<float> obj_layer_zs;
        obj_layer_zs.reserve(m_object->layer_count());
        for (const Layer *l : m_object->layers()) obj_layer_zs.emplace_back((float) l->print_z);
        z_heights[m_object->get_layer(0)->print_z] = m_object->get_layer(0)->height;
        const coordf_t min_print_z = m_object->get_layer(0)->print_z;
        // Collect top contact layers
        for (int layer_nr = 1; layer_nr < contact_nodes.size(); layer_nr++) {
            if (!contact_nodes[layer_nr].empty()) {
                coordf_t print_z = contact_nodes[layer_nr].front()->print_z;
                coordf_t height = contact_nodes[layer_nr].front()->height;
                // insertion will fail if there is already a key of print_z, so no need to check
                bounds.insert({print_z, height});
                bounds.insert({std::max(min_print_z, print_z - height), 0}); // the bottom_z of the layer
            }
        }
 
        auto it1 = bounds.begin();
        auto it2 = std::next(it1);
        for (; it2 != bounds.end(); it2++) {
            coordf_t z2   = it2->first;
            coordf_t h2   = it2->second;
            coordf_t z1   = it1->first;
            coordf_t h1   = it1->second;
            coordf_t dist = z2 - z1;
            if (dist < min_layer_height - EPSILON) continue;
 
            BOOST_LOG_TRIVIAL(trace) << format("plan_layer_heights0 (%.2f,%.2f)->(%.2f,%.2f): ", z1, h1, z2, h2);
 
            // Insert intermediate layers.
            size_t   n_layers_extra = size_t(ceil(dist / max_layer_height));
            coordf_t step = dist / coordf_t(n_layers_extra);
            coordf_t print_z        = z1 + step;
            for (int i = 0; i < n_layers_extra; i++, print_z += step) {
                z_heights[print_z] = step;
                BOOST_LOG_TRIVIAL(debug) << "plan_layer_heights add entry print_z, height: " << print_z << " " << step;
            }
            it1=it2;
        }
 
        // map z_heights to layer_heights
        int i                = 0;
        size_t obj_layer_nr     = 0;
        layer_heights.resize(z_heights.size());
        for (auto it = z_heights.begin(); it != z_heights.end(); it++, i++) {
            coordf_t print_z         = it->first;
            coordf_t height          = it->second;
            while (obj_layer_nr < obj_layer_zs.size() && obj_layer_zs[obj_layer_nr] < print_z - height / 2) obj_layer_nr++;
            layer_heights[i]       = {print_z, height, obj_layer_nr};
 
        }
    }
 
    // add support layers according to layer_heights
    int support_layer_nr = m_raft_layers;
    for (size_t i = 0; i < layer_heights.size(); i++, support_layer_nr++) {
        // SupportLayer *ts_layer = m_object->add_tree_support_layer(support_layer_nr, layer_heights[i].print_z, layer_heights[i].height, layer_heights[i].print_z);
 
        // ORCA: add_tree_support_layer() argument order is (id, height, print_z, slice_z).
        // Passing print_z as height breaks support layer geometry.
        SupportLayer *ts_layer = m_object->add_tree_support_layer(support_layer_nr, layer_heights[i].height, layer_heights[i].print_z, layer_heights[i].print_z);
 
        if (ts_layer->id() > m_raft_layers) {
            SupportLayer *lower_layer = m_object->get_support_layer(ts_layer->id() - 1);
            if (lower_layer) {
                lower_layer->upper_layer = ts_layer;
                ts_layer->lower_layer    = lower_layer;
            }
        }
    }
 
 
    // re-distribute contact_nodes to support layers
    decltype(contact_nodes) contact_nodes2(support_layer_nr);
    for (int layer_nr = 0; layer_nr < contact_nodes.size(); layer_nr++) {
        if (contact_nodes[layer_nr].empty()) continue;
        SupportNode *node1 = contact_nodes[layer_nr].front();
        auto         it    = std::min_element(layer_heights.begin(), layer_heights.end(), [node1](const LayerHeightData &l1, const LayerHeightData &l2) {
            return std::abs(l1.print_z - node1->print_z) < std::abs(l2.print_z - node1->print_z);
        });
        if (it == layer_heights.end()) it = std::prev(it);
        int layer_nr2 = std::distance(layer_heights.begin(), it);
        contact_nodes2[layer_nr2].insert(contact_nodes2[layer_nr2].end(), contact_nodes[layer_nr].begin(), contact_nodes[layer_nr].end());
    }
    contact_nodes = contact_nodes2;
 
    // adjust contact nodes' distance_to_top and support_roof_layers_below according to layer_heights
    // In case of very large top z distance, one gap layer is not enough, we need to split it into multiple layers
    for (int layer_nr = 0; layer_nr < contact_nodes.size(); layer_nr++) {
        if (contact_nodes[layer_nr].empty()) continue;
        SupportNode *node1 = contact_nodes[layer_nr].front();
        BOOST_LOG_TRIVIAL(debug) << format("plan_layer_heights node1->layer_nr,printz,height,distance_to_top: %d, %.2f,%.2f, %d", layer_nr, node1->print_z, node1->height, node1->distance_to_top)
                                 << ", object_layer_zs[" << layer_heights[layer_nr].obj_layer_nr << "]=" << m_object->get_layer(layer_heights[layer_nr].obj_layer_nr)->print_z;
        coordf_t new_height = layer_heights[layer_nr].height;
        if (std::abs(node1->height - new_height) < EPSILON) continue;
        if (top_z_distance < EPSILON && node1->height < EPSILON) continue; // top_z_distance==0, this is soluable interface
        coordf_t              accum_height = 0;
        int                   num_layers   = 0;
        for (int i=layer_nr;i>=0;i--){
            if (layer_heights[i].height > EPSILON) {
                accum_height += layer_heights[i].height;
                num_layers++;
                if (accum_height > node1->height - EPSILON) break;
            }
        }
        BOOST_LOG_TRIVIAL(debug) << format("plan_layer_heights adjust node's height print_z[%d]=%.2f: (%.3f,%d)->(%.3f,%.3f,%d)", layer_nr, node1->print_z,
            node1->height, node1->distance_to_top, new_height, accum_height, -num_layers);
        for (SupportNode *node : contact_nodes[layer_nr]) {
            node->height          = new_height;
            node->distance_to_top = -num_layers;
        }
    }
 
    // log layer_heights
    for (size_t i = 0; i < layer_heights.size(); i++) {
        //if (layer_heights[i].height > EPSILON)
            BOOST_LOG_TRIVIAL(trace) << format("plan_layer_heights[%d] print_z, height: %.2f, %.2f",i, layer_heights[i].print_z, layer_heights[i].height);
    }
    return layer_heights;
}

References Slic3r::bounds(), contact_nodes, Slic3r::Geometry::dist(), Slic3r::SupportNode::distance_to_top, Slic3r::empty(), EPSILON, Slic3r::format(), Slic3r::SupportNode::height, Slic3r::Layer::id(), Slic3r::l2(), Slic3r::Layer::lower_layer, m_object, m_raft_layers, m_slicing_params, m_support_params, plan_layer_heights(), Slic3r::SupportNode::print_z, Slic3r::trace(), and Slic3r::Layer::upper_layer.

Referenced by generate(), and plan_layer_heights().

Here is the call graph for this function:

Here is the caller graph for this function:

smooth_nodes()

void Slic3r::TreeSupport::smooth_nodes ( )

private

{
    for (int layer_nr = 0; layer_nr < contact_nodes.size(); layer_nr++) {
        std::vector<SupportNode *> &curr_layer_nodes = contact_nodes[layer_nr];
        if (curr_layer_nodes.empty()) continue;
        for (SupportNode *node : curr_layer_nodes) {
            node->is_processed = false;
        }
    }
    
    for (int layer_nr = 0; layer_nr< contact_nodes.size(); layer_nr++) {
        std::vector<SupportNode *> &curr_layer_nodes = contact_nodes[layer_nr];
        if (curr_layer_nodes.empty()) continue;
        for (SupportNode *node : curr_layer_nodes) {
            if (!node->is_processed) {
                std::vector<Point> pts;
                std::vector<double> radii;
                std::vector<SupportNode *>   branch;
                SupportNode *              p_node = node;
                // add a fixed head if it's not a polygon node, see STUDIO-4403
                // Polygon node can't be added because the move distance might be huge, making the nodes in between jump and dangling
                if (node->child && node->child->type!=ePolygon) {
                    pts.push_back(p_node->child->position);
                    radii.push_back(p_node->child->radius);
                    branch.push_back(p_node->child);
                }
                do {
                    pts.push_back(p_node->position);
                    radii.push_back(p_node->radius);
                    branch.push_back(p_node);
                    p_node = p_node->parent;
                } while (p_node && !p_node->is_processed);
                if (pts.size() < 3) continue;
 
                std::vector<Point> pts1 = pts;
                std::vector<double> radii1 = radii;
                // TODO here we assume layer height gap is constant. If not true, need to consider height jump
                const int iterations = 100;
                for (size_t k = 0; k < iterations; k++) {
                    for (size_t i = 1; i < pts.size() - 1; i++) {
                        Point pt = ( pts[i - 1] + pts[i] + pts[i + 1] ) / 3;
                        pts1[i] = pt;
                        radii1[i] = (radii[i - 1] + radii[i] + radii[i + 1] ) / 3;
                        if (k == iterations - 1) {
                            branch[i]->position = pt;
                            branch[i]->radius = radii1[i];
                            branch[i]->movement = (pts[i + 1] - pts[i - 1]) / 2;
                            branch[i]->is_processed = true;
                            BOOST_LOG_TRIVIAL(info) << "smooth_nodes: layer_nr=" << layer_nr << ", i=" << i << ", pt=" << pt << ", movement=" << branch[i]->movement << ", radius=" << branch[i]->radius;
                        }
                    }
                    if (k < iterations - 1) {
                        std::swap(pts, pts1);
                        std::swap(radii, radii1);
                    }
                }
            }
        }
    }
}

References Slic3r::SupportNode::child, contact_nodes, Slic3r::ePolygon, Slic3r::SupportNode::is_processed, Slic3r::SupportNode::parent, Slic3r::SupportNode::position, Slic3r::SupportNode::radius, and smooth_nodes().

Referenced by generate(), and smooth_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

avg_node_per_layer

int Slic3r::TreeSupport::avg_node_per_layer = 0

Referenced by draw_circles().

base_radius

coordf_t Slic3r::TreeSupport::base_radius = 0.0

private

Referenced by TreeSupport(), calc_branch_radius(), calc_branch_radius(), calc_radius(), drop_nodes(), and generate_contact_points().

contact_nodes

std::vector<std::vector<SupportNode*> > Slic3r::TreeSupport::contact_nodes

private

Generator for model collision, avoidance and internal guide volumes.

Lazily computes volumes as needed.

Warning

This class is NOT currently thread-safe and should not be accessed in OpenMP blocks

Referenced by drop_nodes(), generate_contact_points(), move_bounds_to_contact_nodes(), plan_layer_heights(), and smooth_nodes().

diameter_angle_scale_factor

double Slic3r::TreeSupport::diameter_angle_scale_factor = tan(5.0*M_PI/180.0)

private

Referenced by TreeSupport(), calc_branch_radius(), calc_branch_radius(), calc_radius(), and drop_nodes().

generator

std::unique_ptr<FillLightning::Generator> Slic3r::TreeSupport::generator

has_cantilever

bool Slic3r::TreeSupport::has_cantilever = false

Referenced by Slic3r::PrintObject::is_support_necessary().

has_sharp_tails

bool Slic3r::TreeSupport::has_sharp_tails = false

Referenced by Slic3r::PrintObject::is_support_necessary().

is_slim

bool Slic3r::TreeSupport::is_slim = false

private

Referenced by TreeSupport(), calc_branch_radius(), drop_nodes(), and generate().

is_strong

bool Slic3r::TreeSupport::is_strong = false

private

Referenced by TreeSupport().

m_highest_overhang_layer

size_t Slic3r::TreeSupport::m_highest_overhang_layer = 0

private

Referenced by detect_overhangs(), and generate().

m_machine_border

ExPolygon Slic3r::TreeSupport::m_machine_border

Polygons representing the limits of the printable area of the machine.

Referenced by TreeSupport(), and Slic3r::generate_tree_support_3D().

m_model_volumes

std::unique_ptr<TreeSupport3D::TreeModelVolumes> Slic3r::TreeSupport::m_model_volumes

private

Referenced by get_collision_polys().

m_mst_line_x_layer_contour_caches

std::vector< std::unordered_map<Line, bool, LineHash> > Slic3r::TreeSupport::m_mst_line_x_layer_contour_caches

private

m_object

PrintObject* Slic3r::TreeSupport::m_object

private

Referenced by TreeSupport(), create_tree_support_layers(), detect_overhangs(), draw_circles(), drop_nodes(), generate(), generate_contact_points(), generate_toolpaths(), and plan_layer_heights().

m_object_config

const PrintObjectConfig* Slic3r::TreeSupport::m_object_config

private

Referenced by TreeSupport(), calc_branch_radius(), detect_overhangs(), draw_circles(), generate(), generate_contact_points(), generate_toolpaths(), get_collision_polys(), and get_trim_support_regions().

m_print_config

const PrintConfig* Slic3r::TreeSupport::m_print_config

Referenced by TreeSupport(), belt_floor_print_z(), belt_node_landed(), belt_polygon_landed(), draw_circles(), generate_toolpaths(), and Slic3r::generate_tree_support_3D().

m_raft_layers

size_t Slic3r::TreeSupport::m_raft_layers = 0

private

Referenced by TreeSupport(), create_tree_support_layers(), draw_circles(), generate_toolpaths(), and plan_layer_heights().

m_slicing_params

SlicingParameters Slic3r::TreeSupport::m_slicing_params

private

Referenced by TreeSupport(), belt_floor_print_z(), belt_node_landed(), belt_polygon_landed(), create_tree_support_layers(), detect_overhangs(), draw_circles(), drop_nodes(), generate_contact_points(), generate_toolpaths(), get_trim_support_regions(), and plan_layer_heights().

m_spanning_trees

std::vector<std::vector<MinimumSpanningTree> > Slic3r::TreeSupport::m_spanning_trees

private

m_support_params

SupportParameters Slic3r::TreeSupport::m_support_params

private

Referenced by TreeSupport(), draw_circles(), drop_nodes(), generate(), generate_toolpaths(), and plan_layer_heights().

m_ts_data

std::shared_ptr<TreeSupportData> Slic3r::TreeSupport::m_ts_data

private

Referenced by create_node(), draw_circles(), drop_nodes(), generate(), get_avoidance(), get_collision(), get_collision_polys(), and move_bounds_to_contact_nodes().

m_vertical_enforcer_points

std::vector<std::pair<Vec3f, Vec3f> > Slic3r::TreeSupport::m_vertical_enforcer_points

Referenced by generate_contact_points(), and Slic3r::TreeSupport3D::generate_support_areas().

MAX_BRANCH_RADIUS

const coordf_t Slic3r::TreeSupport::MAX_BRANCH_RADIUS = 10.0

private

Referenced by calc_branch_radius(), and calc_branch_radius().

MAX_BRANCH_RADIUS_FIRST_LAYER

const coordf_t Slic3r::TreeSupport::MAX_BRANCH_RADIUS_FIRST_LAYER = 12.0

private

max_cantilever_dist

double Slic3r::TreeSupport::max_cantilever_dist = 0

Referenced by detect_overhangs(), and Slic3r::PrintObject::is_support_necessary().

MIN_BRANCH_RADIUS

const coordf_t Slic3r::TreeSupport::MIN_BRANCH_RADIUS = 0.4

private

Referenced by TreeSupport(), calc_branch_radius(), and calc_branch_radius().

MIN_BRANCH_RADIUS_FIRST_LAYER

const coordf_t Slic3r::TreeSupport::MIN_BRANCH_RADIUS_FIRST_LAYER = 2.0

private

minimum_roof_area

const double Slic3r::TreeSupport::minimum_roof_area {SQ(scaled<double>(1.))}

private

{SQ(scaled<double>(1.))};

nodes_angle

float Slic3r::TreeSupport::nodes_angle = 0

Referenced by draw_circles().

overhang_types

std::map<const ExPolygon*, OverhangType> Slic3r::TreeSupport::overhang_types

Referenced by Slic3r::TreeSupport3D::generate_support_areas().

printZ_to_lightninglayer

std::unordered_map<double, size_t> Slic3r::TreeSupport::printZ_to_lightninglayer

support_type

SupportType Slic3r::TreeSupport::support_type

Referenced by TreeSupport(), detect_overhangs(), and Slic3r::PrintObject::is_support_necessary().

throw_on_cancel

std::function<void()> Slic3r::TreeSupport::throw_on_cancel

Referenced by Slic3r::PrintObject::_generate_support_material(), and generate().

top_z_distance

float Slic3r::TreeSupport::top_z_distance = 0.0

private

Referenced by TreeSupport(), and generate_contact_points().

with_infill

bool Slic3r::TreeSupport::with_infill = false

private

Referenced by TreeSupport().

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Support/TreeSupport.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Support/TreeSupport.cpp