Slic3r::FillLightning::Layer Class Reference

#include <src/libslic3r/Fill/Lightning/Layer.hpp>

Collaboration diagram for Slic3r::FillLightning::Layer:

Public Member Functions
void	generateNewTrees (const Polygons &current_overhang, const Polygons &current_outlines, const BoundingBox &current_outlines_bbox, const EdgeGrid::Grid &outline_locator, coord_t supporting_radius, coord_t wall_supporting_radius, const std::function< void()> &throw_on_cancel_callback)
GroundingLocation	getBestGroundingLocation (const Point &unsupported_location, const Polygons &current_outlines, const BoundingBox &current_outlines_bbox, const EdgeGrid::Grid &outline_locator, coord_t supporting_radius, coord_t wall_supporting_radius, const SparseNodeGrid &tree_node_locator, const NodeSPtr &exclude_tree=nullptr)
bool	attach (const Point &unsupported_location, const GroundingLocation &ground, NodeSPtr &new_child, NodeSPtr &new_root)
void	reconnectRoots (std::vector< NodeSPtr > &to_be_reconnected_tree_roots, const Polygons &current_outlines, const BoundingBox &current_outlines_bbox, const EdgeGrid::Grid &outline_locator, coord_t supporting_radius, coord_t wall_supporting_radius)
Polylines	convertToLines (const Polygons &limit_to_outline, coord_t line_overlap) const
coord_t	getWeightedDistance (const Point &boundary_loc, const Point &unsupported_location)
void	fillLocator (SparseNodeGrid &tree_node_locator, const BoundingBox &current_outlines_bbox)

Public Attributes
std::vector< NodeSPtr >	tree_roots

Detailed Description

A layer of the lightning fill.

Contains the trees to be printed and propagated to the next layer below.

Member Function Documentation

attach()

bool Slic3r::FillLightning::Layer::attach	(	const Point &	unsupported_location,
		const GroundingLocation &	ground,
		NodeSPtr &	new_child,
		NodeSPtr &	new_root
	)

Parameters

[out]	new_child	The new child node introduced
[out]	new_root	The new root node if one had been made

Returns

Whether a new root was added

{
    // Update trees & distance fields.
    if (grounding_loc.boundary_location) {
        new_root = Node::create(grounding_loc.p(), std::make_optional(grounding_loc.p()));
        new_child = new_root->addChild(unsupported_location);
        tree_roots.push_back(new_root);
        return true;
    } else {
        new_child = grounding_loc.tree_node->addChild(unsupported_location);
        return false;
    }
}

References Slic3r::FillLightning::GroundingLocation::boundary_location, Slic3r::FillLightning::GroundingLocation::p(), and Slic3r::FillLightning::GroundingLocation::tree_node.

Referenced by generateNewTrees().

Here is the call graph for this function:

Here is the caller graph for this function:

convertToLines()

Polylines Slic3r::FillLightning::Layer::convertToLines	(	const Polygons &	limit_to_outline,
		coord_t	line_overlap
	)		const

{
    if (tree_roots.empty())
        return {};
 
    Polylines result_lines;
    for (const auto &tree : tree_roots)
        tree->convertToPolylines(result_lines, line_overlap);
 
    return intersection_pl(result_lines, limit_to_outline);
}

References Slic3r::intersection_pl().

Referenced by Slic3r::FillLightning::Filler::_fill_surface_single().

Here is the call graph for this function:

Here is the caller graph for this function:

fillLocator()

void Slic3r::FillLightning::Layer::fillLocator	(	SparseNodeGrid &	tree_node_locator,
		const BoundingBox &	current_outlines_bbox
	)

{
    std::function<void(NodeSPtr)> add_node_to_locator_func = [&tree_node_locator, &current_outlines_bbox](const NodeSPtr &node) {
        tree_node_locator.insert(std::make_pair(to_grid_point(node->getLocation(), current_outlines_bbox), node));
    };
    for (auto& tree : tree_roots)
        tree->visitNodes(add_node_to_locator_func);
}

References Slic3r::FillLightning::to_grid_point(), tree_roots, and void().

Referenced by generateNewTrees().

Here is the call graph for this function:

Here is the caller graph for this function:

generateNewTrees()

void Slic3r::FillLightning::Layer::generateNewTrees	(	const Polygons &	current_overhang,
		const Polygons &	current_outlines,
		const BoundingBox &	current_outlines_bbox,
		const EdgeGrid::Grid &	outline_locator,
		coord_t	supporting_radius,
		coord_t	wall_supporting_radius,
		const std::function< void()> &	throw_on_cancel_callback
	)

{
    DistanceField distance_field(supporting_radius, current_outlines, current_outlines_bbox, current_overhang);
    throw_on_cancel_callback();
 
    SparseNodeGrid tree_node_locator;
    fillLocator(tree_node_locator, current_outlines_bbox);
 
    // Until no more points need to be added to support all:
    // Determine next point from tree/outline areas via distance-field
    size_t unsupported_cell_idx = 0;
    Point  unsupported_location;
    while (distance_field.tryGetNextPoint(&unsupported_location, &unsupported_cell_idx, unsupported_cell_idx)) {
        throw_on_cancel_callback();
        GroundingLocation grounding_loc = getBestGroundingLocation(
            unsupported_location, current_outlines, current_outlines_bbox, outlines_locator, supporting_radius, wall_supporting_radius, tree_node_locator);
 
        NodeSPtr new_parent;
        NodeSPtr new_child;
        this->attach(unsupported_location, grounding_loc, new_child, new_parent);
        tree_node_locator.insert(std::make_pair(to_grid_point(new_child->getLocation(), current_outlines_bbox), new_child));
        if (new_parent)
            tree_node_locator.insert(std::make_pair(to_grid_point(new_parent->getLocation(), current_outlines_bbox), new_parent));
        // update distance field
        distance_field.update(grounding_loc.p(), unsupported_location);
    }
 
#ifdef LIGHTNING_TREE_NODE_DEBUG_OUTPUT
    {
        static int iRun = 0;
        export_to_svg(debug_out_path("FillLightning-TreeNodes-%d.svg", iRun++), current_outlines, this->tree_roots);
    }
#endif /* LIGHTNING_TREE_NODE_DEBUG_OUTPUT */
}

References attach(), Slic3r::debug_out_path(), Slic3r::export_to_svg(), fillLocator(), getBestGroundingLocation(), Slic3r::FillLightning::GroundingLocation::p(), Slic3r::FillLightning::to_grid_point(), tree_roots, Slic3r::FillLightning::DistanceField::tryGetNextPoint(), and Slic3r::FillLightning::DistanceField::update().

Referenced by Slic3r::FillLightning::Generator::generateTrees().

Here is the call graph for this function:

Here is the caller graph for this function:

getBestGroundingLocation()

GroundingLocation Slic3r::FillLightning::Layer::getBestGroundingLocation	(	const Point &	unsupported_location,
		const Polygons &	current_outlines,
		const BoundingBox &	current_outlines_bbox,
		const EdgeGrid::Grid &	outline_locator,
		coord_t	supporting_radius,
		coord_t	wall_supporting_radius,
		const SparseNodeGrid &	tree_node_locator,
		const NodeSPtr &	exclude_tree = nullptr
	)

Determine & connect to connection point in tree/outline.

Parameters

min_dist_from_boundary_for_tree

If the unsupported point is closer to the boundary than this then don't consider connecting it to a tree

{
    // Closest point on current_outlines to unsupported_location:
    Point node_location;
    {
        double d2 = std::numeric_limits<double>::max();
        for (const Polygon &contour : current_outlines)
            if (contour.size() > 2) {
                Point prev = contour.points.back();
                for (const Point &p2 : contour.points) {
                    Point closest_point;
                    if (double d = line_alg::distance_to_squared(Line{prev, p2}, unsupported_location, &closest_point); d < d2) {
                        d2 = d;
                        node_location = closest_point;
                    }
                    prev = p2;
                }
            }
    }
 
    const auto within_dist = coord_t((node_location - unsupported_location).cast<double>().norm());
 
    NodeSPtr sub_tree{nullptr};
    coord_t  current_dist = getWeightedDistance(node_location, unsupported_location);
    if (current_dist >= wall_supporting_radius) { // Only reconnect tree roots to other trees if they are not already close to the outlines.
        const coord_t search_radius = std::min(current_dist, within_dist);
        BoundingBox region(unsupported_location - Point(search_radius, search_radius), unsupported_location + Point(search_radius + locator_cell_size, search_radius + locator_cell_size));
        region.min = to_grid_point(region.min, current_outlines_bbox);
        region.max = to_grid_point(region.max, current_outlines_bbox);
 
        Point      current_dist_grid_addr{std::numeric_limits<coord_t>::lowest(), std::numeric_limits<coord_t>::lowest()};
        std::mutex current_dist_mutex;
        tbb::parallel_for(tbb::blocked_range2d<coord_t>(region.min.y(), region.max.y(), region.min.x(), region.max.x()), [&current_dist, current_dist_copy = current_dist, &current_dist_mutex, &sub_tree, &current_dist_grid_addr, &exclude_tree = std::as_const(exclude_tree), &outline_locator = std::as_const(outline_locator), &supporting_radius = std::as_const(supporting_radius), &tree_node_locator = std::as_const(tree_node_locator), &unsupported_location = std::as_const(unsupported_location)](const tbb::blocked_range2d<coord_t> &range) -> void {
            for (coord_t grid_addr_y = range.rows().begin(); grid_addr_y < range.rows().end(); ++grid_addr_y)
                for (coord_t grid_addr_x = range.cols().begin(); grid_addr_x < range.cols().end(); ++grid_addr_x) {
                    const Point local_grid_addr{grid_addr_x, grid_addr_y};
                    NodeSPtr    local_sub_tree{nullptr};
                    coord_t     local_current_dist = current_dist_copy;
                    const auto  it_range           = tree_node_locator.equal_range(local_grid_addr);
                    for (auto it = it_range.first; it != it_range.second; ++it) {
                        const NodeSPtr candidate_sub_tree = it->second.lock();
                        if ((candidate_sub_tree && candidate_sub_tree != exclude_tree) &&
                            !(exclude_tree && exclude_tree->hasOffspring(candidate_sub_tree)) &&
                            !polygonCollidesWithLineSegment(unsupported_location, candidate_sub_tree->getLocation(), outline_locator)) {
                            if (const coord_t candidate_dist = candidate_sub_tree->getWeightedDistance(unsupported_location, supporting_radius); candidate_dist < local_current_dist) {
                                local_current_dist = candidate_dist;
                                local_sub_tree     = candidate_sub_tree;
                            }
                        }
                    }
                    // To always get the same result in a parallel version as in a non-parallel version,
                    // we need to preserve that for the same current_dist, we select the same sub_tree
                    // as in the non-parallel version. For this purpose, inside the variable
                    // current_dist_grid_addr is stored from with 2D grid position assigned sub_tree comes.
                    // And when there are two sub_tree with the same current_dist, one which will be found
                    // the first in the non-parallel version is selected.
                    {
                        std::lock_guard<std::mutex> lock(current_dist_mutex);
                        if (local_current_dist < current_dist ||
                            (local_current_dist == current_dist && (grid_addr_y < current_dist_grid_addr.y() ||
                              (grid_addr_y == current_dist_grid_addr.y() && grid_addr_x < current_dist_grid_addr.x())))) {
                            current_dist           = local_current_dist;
                            sub_tree               = local_sub_tree;
                            current_dist_grid_addr = local_grid_addr;
                        }
                    }
                }
        }); // end of parallel_for
    }
 
    return ! sub_tree ?
        GroundingLocation{ nullptr, node_location } :
        GroundingLocation{ sub_tree, std::optional<Point>() };
}

References Slic3r::contour(), Slic3r::line_alg::distance_to_squared(), getWeightedDistance(), Slic3r::FillLightning::locator_cell_size, Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::min, Slic3r::MultiPoint::points, Slic3r::range(), Slic3r::MultiPoint::size(), and Slic3r::FillLightning::to_grid_point().

Referenced by generateNewTrees().

Here is the call graph for this function:

Here is the caller graph for this function:

getWeightedDistance()

coord_t Slic3r::FillLightning::Layer::getWeightedDistance	(	const Point &	boundary_loc,
		const Point &	unsupported_location
	)

{
    return coord_t((boundary_loc - unsupported_location).cast<double>().norm());
}

Referenced by getBestGroundingLocation().

Here is the caller graph for this function:

reconnectRoots()

void Slic3r::FillLightning::Layer::reconnectRoots	(	std::vector< NodeSPtr > &	to_be_reconnected_tree_roots,
		const Polygons &	current_outlines,
		const BoundingBox &	current_outlines_bbox,
		const EdgeGrid::Grid &	outline_locator,
		coord_t	supporting_radius,
		coord_t	wall_supporting_radius
	)

{
    constexpr coord_t tree_connecting_ignore_offset = 100;
 
    SparseNodeGrid tree_node_locator;
    fillLocator(tree_node_locator, current_outlines_bbox);
 
    const coord_t within_max_dist = outline_locator.resolution() * 2;
    for (const auto &root_ptr : to_be_reconnected_tree_roots)
    {
        auto old_root_it = std::find(tree_roots.begin(), tree_roots.end(), root_ptr);
 
        if (root_ptr->getLastGroundingLocation())
        {
            const Point& ground_loc = *root_ptr->getLastGroundingLocation();
            if (ground_loc != root_ptr->getLocation())
            {
                Point new_root_pt;
                // Find an intersection of the line segment from root_ptr->getLocation() to ground_loc, at within_max_dist from ground_loc.
                if (lineSegmentPolygonsIntersection(root_ptr->getLocation(), ground_loc, outline_locator, new_root_pt, within_max_dist)) {
                    auto new_root = Node::create(new_root_pt, new_root_pt);
                    root_ptr->addChild(new_root);
                    new_root->reroot();
 
                    tree_node_locator.insert(std::make_pair(to_grid_point(new_root->getLocation(), current_outlines_bbox), new_root));
 
                    *old_root_it = std::move(new_root); // replace old root with new root
                    continue;
                }
            }
        }
 
        const coord_t tree_connecting_ignore_width = wall_supporting_radius - tree_connecting_ignore_offset; // Ideally, the boundary size in which the valence rule is ignored would be configurable.
        GroundingLocation ground =
            getBestGroundingLocation
            (
                root_ptr->getLocation(),
                current_outlines,
                current_outlines_bbox,
                outline_locator,
                supporting_radius,
                tree_connecting_ignore_width,
                tree_node_locator,
                root_ptr
            );
        if (ground.boundary_location)
        {
            if (*ground.boundary_location == root_ptr->getLocation())
                continue; // Already on the boundary.
 
            auto new_root = Node::create(ground.p(), ground.p());
            auto attach_ptr = root_ptr->closestNode(new_root->getLocation());
            attach_ptr->reroot();
 
            new_root->addChild(attach_ptr);
            tree_node_locator.insert(std::make_pair(to_grid_point(new_root->getLocation(), current_outlines_bbox), new_root));
 
            *old_root_it = std::move(new_root); // replace old root with new root
        }
        else
        {
            assert(ground.tree_node);
            assert(ground.tree_node != root_ptr);
            assert(!root_ptr->hasOffspring(ground.tree_node));
            assert(!ground.tree_node->hasOffspring(root_ptr));
 
            auto attach_ptr = root_ptr->closestNode(ground.tree_node->getLocation());
            attach_ptr->reroot();
 
            ground.tree_node->addChild(attach_ptr);
 
            // remove old root
            *old_root_it = std::move(tree_roots.back());
            tree_roots.pop_back();
        }
    }
}

References Slic3r::FillLightning::GroundingLocation::boundary_location, Slic3r::FillLightning::lineSegmentPolygonsIntersection(), Slic3r::FillLightning::GroundingLocation::p(), Slic3r::EdgeGrid::Grid::resolution(), Slic3r::FillLightning::to_grid_point(), and Slic3r::FillLightning::GroundingLocation::tree_node.

Referenced by Slic3r::FillLightning::Generator::generateTrees().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

tree_roots

std::vector<NodeSPtr> Slic3r::FillLightning::Layer::tree_roots

Referenced by fillLocator(), generateNewTrees(), and Slic3r::FillLightning::Generator::generateTrees().

---

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

• src/libslic3r/Fill/Lightning/Layer.hpp
• src/libslic3r/Fill/Lightning/Layer.cpp