Slic3r::FillLightning::DistanceField Class Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Fill/Lightning/DistanceField.hpp>

Collaboration diagram for Slic3r::FillLightning::DistanceField:

Classes
struct	UnsupportedCell
class	UnsupportedPointsGrid

Public Member Functions
	DistanceField (const coord_t &radius, const Polygons &current_outline, const BoundingBox &current_outlines_bbox, const Polygons &current_overhang)
bool	tryGetNextPoint (Point *out_unsupported_location, size_t *out_unsupported_cell_idx, const size_t start_idx=0) const
void	update (const Point &to_node, const Point &added_leaf)

Protected Member Functions
Point	to_grid_point (const Point &point) const
Point	from_grid_point (const Point &point) const

Protected Attributes
coord_t	m_cell_size
coord_t	m_supporting_radius
int64_t	m_supporting_radius2
std::vector< UnsupportedCell >	m_unsupported_points
std::vector< bool >	m_unsupported_points_erased
const BoundingBox	m_unsupported_points_bbox
UnsupportedPointsGrid	m_unsupported_points_grid

Detailed Description

2D field that maintains locations which need to be supported for Lightning Infill.

This field contains a set of "cells", spaced out in a grid. Each cell maintains how far it is removed from the edge, which is used to determine how it gets supported by Lightning Infill.

---

Class Documentation

Slic3r::FillLightning::DistanceField::UnsupportedCell

struct Slic3r::FillLightning::DistanceField::UnsupportedCell

Represents a small discrete area of infill that needs to be supported.

Collaboration diagram for Slic3r::FillLightning::DistanceField::UnsupportedCell:

Class Members
coord_t	dist_to_boundary
Point	loc

Constructor & Destructor Documentation

DistanceField()

Slic3r::FillLightning::DistanceField::DistanceField	(	const coord_t &	radius,
		const Polygons &	current_outline,
		const BoundingBox &	current_outlines_bbox,
		const Polygons &	current_overhang )

Construct a new field to calculate Lightning Infill with.

Parameters

radius	The radius of influence that an infill line is expected to support in the layer above.
current_outline	The total infill area on this layer.
current_overhang	The overhang that needs to be supported on this layer.

                                                                                                                                                               :
    m_cell_size(radius / radius_per_cell_size),
    m_supporting_radius(radius),
    m_unsupported_points_bbox(current_outlines_bbox)
{
    m_supporting_radius2 = Slic3r::sqr(int64_t(radius));
    // Sample source polygons with a regular grid sampling pattern.
    const BoundingBox overhang_bbox = get_extents(current_overhang);
    ExPolygons expolys = offset2_ex(union_ex(current_overhang), -m_cell_size / 2, m_cell_size / 2); // remove dangling lines which causes sample_grid_pattern crash (fails the OUTER_LOW assertions)
    for (const ExPolygon &expoly : expolys) {
        const Points sampled_points               = sample_grid_pattern(expoly, m_cell_size, overhang_bbox);
        const size_t unsupported_points_prev_size = m_unsupported_points.size();
        m_unsupported_points.resize(unsupported_points_prev_size + sampled_points.size());
 
        tbb::parallel_for(tbb::blocked_range<size_t>(0, sampled_points.size()), [&self = *this, &expoly = std::as_const(expoly), &sampled_points = std::as_const(sampled_points), &unsupported_points_prev_size = std::as_const(unsupported_points_prev_size)](const tbb::blocked_range<size_t> &range) -> void {
            for (size_t sp_idx = range.begin(); sp_idx < range.end(); ++sp_idx) {
                const Point &sp = sampled_points[sp_idx];
                // Find a squared distance to the source expolygon boundary.
                double d2 = std::numeric_limits<double>::max();
                for (size_t icontour = 0; icontour <= expoly.holes.size(); ++icontour) {
                    const Polygon &contour = icontour == 0 ? expoly.contour : expoly.holes[icontour - 1];
                    if (contour.size() > 2) {
                        Point prev = contour.points.back();
                        for (const Point &p2 : contour.points) {
                            d2   = std::min(d2, Line::distance_to_squared(sp, prev, p2));
                            prev = p2;
                        }
                    }
                }
                self.m_unsupported_points[unsupported_points_prev_size + sp_idx] = {sp, coord_t(std::sqrt(d2))};
                assert(self.m_unsupported_points_bbox.contains(sp));
            }
        }); // end of parallel_for
    }
    std::stable_sort(m_unsupported_points.begin(), m_unsupported_points.end(), [&radius](const UnsupportedCell &a, const UnsupportedCell &b) {
        constexpr coord_t prime_for_hash = 191;
        return std::abs(b.dist_to_boundary - a.dist_to_boundary) > radius ?
               a.dist_to_boundary < b.dist_to_boundary :
               (PointHash{}(a.loc) % prime_for_hash) < (PointHash{}(b.loc) % prime_for_hash);
        });
 
    m_unsupported_points_erased.resize(m_unsupported_points.size());
    std::fill(m_unsupported_points_erased.begin(), m_unsupported_points_erased.end(), false);
 
    m_unsupported_points_grid.initialize(m_unsupported_points, [&self = std::as_const(*this)](const Point &p) -> Point { return self.to_grid_point(p); });
 
    // Because the distance between two points is at least one axis equal to m_cell_size, every cell
    // in m_unsupported_points_grid contains exactly one point.
    assert(m_unsupported_points.size() == m_unsupported_points_grid.size());
 
#ifdef LIGHTNING_DISTANCE_FIELD_DEBUG_OUTPUT
    {
        static int iRun = 0;
        export_distance_field_to_svg(debug_out_path("FillLightning-DistanceField-%d.svg", iRun++), current_outline, current_overhang, m_unsupported_points);
    }
#endif
}

References Slic3r::FillLightning::get_extents(), m_cell_size, m_supporting_radius, m_supporting_radius2, m_unsupported_points, m_unsupported_points_bbox, Slic3r::offset2_ex(), Slic3r::FillLightning::radius_per_cell_size, Slic3r::range(), Slic3r::sample_grid_pattern(), Slic3r::sqr(), and Slic3r::union_ex().

Here is the call graph for this function:

Member Function Documentation

from_grid_point()

Point Slic3r::FillLightning::DistanceField::from_grid_point ( const Point & point ) const

inlineprotected

Maps the point to the grid coordinates.

                                                    {
        return point * m_cell_size + m_unsupported_points_bbox.min;
    }

References m_cell_size, and m_unsupported_points_bbox.

Referenced by update().

Here is the caller graph for this function:

to_grid_point()

Point Slic3r::FillLightning::DistanceField::to_grid_point ( const Point & point ) const

inlineprotected

Maps the point to the grid coordinates.

                                                  {
        return (point - m_unsupported_points_bbox.min) / m_cell_size;
    }

References m_cell_size, and m_unsupported_points_bbox.

Referenced by update().

Here is the caller graph for this function:

tryGetNextPoint()

bool Slic3r::FillLightning::DistanceField::tryGetNextPoint ( Point * out_unsupported_location, size_t * out_unsupported_cell_idx, const size_t start_idx = 0 ) const

inline

Gets the next unsupported location to be supported by a new branch.

Parameters

p	Output variable for the next point to support.

Returns

true if successful, or false if there are no more points to consider.

    {
        for (size_t point_idx = start_idx; point_idx < m_unsupported_points.size(); ++point_idx) {
            if (!m_unsupported_points_erased[point_idx]) {
                *out_unsupported_cell_idx = point_idx;
                *out_unsupported_location = m_unsupported_points[point_idx].loc;
                return true;
            }
        }
 
        return false;
    }

References m_unsupported_points, and m_unsupported_points_erased.

Referenced by Slic3r::FillLightning::Layer::generateNewTrees().

Here is the caller graph for this function:

update()

void Slic3r::FillLightning::DistanceField::update	(	const Point &	to_node,
		const Point &	added_leaf )

Update the distance field with a newly added branch.

The branch is a line extending from to_node to added_leaf . This function updates the grid cells so that the distance field knows how far off it is from being supported by the current pattern. Grid points are updated with sampling points spaced out by the supporting radius along the line.

Parameters

to_node	The node endpoint of the newly added branch.
added_leaf	The location of the leaf of the newly added branch, drawing a straight line to the node.

{
    Vec2d       v  = (added_leaf - to_node).cast<double>();
    auto        l2 = v.squaredNorm();
    Vec2d       extent = Vec2d(-v.y(), v.x()) * m_supporting_radius / sqrt(l2);
 
    BoundingBox grid;
    {
        Point diagonal(m_supporting_radius, m_supporting_radius);
        Point iextent(extent.cast<coord_t>());
        grid = BoundingBox(added_leaf - diagonal, added_leaf + diagonal);
        grid.merge(to_node - iextent);
        grid.merge(to_node + iextent);
        grid.merge(added_leaf - iextent);
        grid.merge(added_leaf + iextent);
 
        // Clip grid by m_unsupported_points_bbox. Mainly to ensure that grid.min is a non-negative value.
        grid.min.x() = std::max(grid.min.x(), m_unsupported_points_bbox.min.x());
        grid.min.y() = std::max(grid.min.y(), m_unsupported_points_bbox.min.y());
        grid.max.x() = std::min(grid.max.x(), m_unsupported_points_bbox.max.x());
        grid.max.y() = std::min(grid.max.y(), m_unsupported_points_bbox.max.y());
 
        grid.min = this->to_grid_point(grid.min);
        grid.max = this->to_grid_point(grid.max);
    }
 
    Point grid_addr;
    Point grid_loc;
    for (grid_addr.y() = grid.min.y(); grid_addr.y() <= grid.max.y(); ++grid_addr.y()) {
        for (grid_addr.x() = grid.min.x(); grid_addr.x() <= grid.max.x(); ++grid_addr.x()) {
            grid_loc = this->from_grid_point(grid_addr);
            // Test inside a circle at the new leaf.
            if ((grid_loc - added_leaf).cast<int64_t>().squaredNorm() > m_supporting_radius2) {
                // Not inside a circle at the end of the new leaf.
                // Test inside a rotated rectangle.
                Vec2d  vx = (grid_loc - to_node).cast<double>();
                double d  = v.dot(vx);
                if (d >= 0 && d <= l2) {
                    d = extent.dot(vx);
                    if (d < -1. || d > 1.)
                        // Not inside a rotated rectangle.
                        continue;
                }
            }
            // Inside a circle at the end of the new leaf, or inside a rotated rectangle.
            // Remove unsupported leafs at this grid location.
            if (const size_t cell_idx = m_unsupported_points_grid.find_cell_idx(grid_addr); cell_idx != std::numeric_limits<size_t>::max()) {
                const UnsupportedCell &cell = m_unsupported_points[cell_idx];
                if ((cell.loc - added_leaf).cast<int64_t>().squaredNorm() <= m_supporting_radius2) {
                    m_unsupported_points_erased[cell_idx] = true;
                    m_unsupported_points_grid.mark_erased(grid_addr);
                }
            }
        }
    }
}

References Slic3r::cast(), from_grid_point(), Slic3r::grid(), Slic3r::l2(), Slic3r::FillLightning::DistanceField::UnsupportedCell::loc, m_supporting_radius, m_supporting_radius2, m_unsupported_points, m_unsupported_points_bbox, m_unsupported_points_erased, m_unsupported_points_grid, to_grid_point(), and update().

Referenced by Slic3r::FillLightning::Layer::generateNewTrees(), and update().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

m_cell_size

coord_t Slic3r::FillLightning::DistanceField::m_cell_size

protected

Spacing between grid points to consider supporting.

Referenced by DistanceField(), from_grid_point(), and to_grid_point().

m_supporting_radius

coord_t Slic3r::FillLightning::DistanceField::m_supporting_radius

protected

The radius of the area of the layer above supported by a point on a branch of a tree.

Referenced by DistanceField(), and update().

m_supporting_radius2

int64_t Slic3r::FillLightning::DistanceField::m_supporting_radius2

protected

Referenced by DistanceField(), and update().

m_unsupported_points

std::vector<UnsupportedCell> Slic3r::FillLightning::DistanceField::m_unsupported_points

protected

Cells which still need to be supported at some point.

Referenced by DistanceField(), tryGetNextPoint(), and update().

m_unsupported_points_bbox

const BoundingBox Slic3r::FillLightning::DistanceField::m_unsupported_points_bbox

protected

BoundingBox of all points in m_unsupported_points. Used for mapping of sign integer numbers to positive integer numbers.

Referenced by DistanceField(), from_grid_point(), to_grid_point(), and update().

m_unsupported_points_erased

std::vector<bool> Slic3r::FillLightning::DistanceField::m_unsupported_points_erased

protected

Referenced by tryGetNextPoint(), and update().

m_unsupported_points_grid

UnsupportedPointsGrid Slic3r::FillLightning::DistanceField::m_unsupported_points_grid

protected

Referenced by update().

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Fill/Lightning/DistanceField.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Fill/Lightning/DistanceField.cpp