Slic3r::Arachne Namespace Reference

Namespaces
namespace	LinearAlg2D

Classes
class	BeadingStrategy
class	BeadingStrategyFactory
class	DistributedBeadingStrategy
class	LimitedBeadingStrategy
class	OuterWallInsetBeadingStrategy
class	RedistributeBeadingStrategy
class	WideningBeadingStrategy
class	SkeletalTrapezoidation
class	SkeletalTrapezoidationEdge
class	STHalfEdge
class	STHalfEdgeNode
class	SkeletalTrapezoidationGraph
class	SkeletalTrapezoidationJoint
struct	ExtrusionJunction
struct	ExtrusionLine
class	HalfEdgeNode
class	HalfEdge
class	HalfEdgeGraph
class	PathsPointIndex
struct	PolygonsPointIndexSegmentLocator
struct	PathsPointIndexLocator
class	PolygonsSegmentIndex
class	PolylineStitcher
class	SparseGrid
	Sparse grid which can locate spatially nearby elements efficiently. More...
class	SparseLineGrid
	Sparse grid which can locate spatially nearby elements efficiently. More...
class	SparsePointGrid
	Sparse grid which can locate spatially nearby elements efficiently. More...
class	SquareGrid
class	WallToolPathsParams
class	WallToolPaths

Typedefs
using	BeadingStrategyPtr = std::unique_ptr<BeadingStrategy>
using	VD = Slic3r::Geometry::VoronoiDiagram
using	LineJunctions = std::vector<ExtrusionJunction>
using	ExtrusionJunctions = std::vector<ExtrusionJunction>
using	VariableWidthLines = std::vector<ExtrusionLine>
using	PolygonsPointIndex = PathsPointIndex<Polygons>
typedef SparseLineGrid< PolygonsPointIndex, PolygonsPointIndexSegmentLocator >	LocToLineGrid

Functions
template<typename T>
constexpr T	pi_div (const T div)
static Point	normal (const Point &p0, coord_t len)
Point	operator- (const ExtrusionJunction &a, const ExtrusionJunction &b)
const Point &	make_point (const ExtrusionJunction &ej)
coord_t	colinear_vertex_tolerance ()
template<class PathType>
static Slic3r::ThickPolyline	to_thick_polyline (const PathType &path)
static Polygon	to_polygon (const ExtrusionLine &line)
static Points	to_points (const ExtrusionLine &extrusion_line)
const Point &	make_point (const Point &p)
WallToolPathsParams	make_paths_params (const int layer_id, const PrintObjectConfig &print_object_config, const PrintConfig &print_config)
void	simplify (Polygon &thiss, const int64_t smallest_line_segment_squared, const int64_t allowed_error_distance_squared)
void	simplify (Polygons &thiss, const int64_t smallest_line_segment=scaled< coord_t >(0.01), const int64_t allowed_error_distance=scaled< coord_t >(0.005))
std::unique_ptr< LocToLineGrid >	createLocToLineGrid (const Polygons &polygons, int square_size)
void	fixSelfIntersections (const coord_t epsilon, Polygons &thiss)
void	removeDegenerateVerts (Polygons &thiss)
void	removeSmallAreas (Polygons &thiss, const double min_area_size, const bool remove_holes)
void	removeColinearEdges (Polygon &poly, const double max_deviation_angle)
void	removeColinearEdges (Polygons &thiss, const double max_deviation_angle=0.0005)
template<typename T>
bool	shorterThan (const T &shape, const coord_t check_length)
coord_t	meshfix_maximum_resolution ()
coord_t	meshfix_maximum_deviation ()
coord_t	meshfix_maximum_extrusion_area_deviation ()

Variables
constexpr bool	fill_outline_gaps = true

---

Class Documentation

Slic3r::Arachne::HalfEdgeGraph

class Slic3r::Arachne::HalfEdgeGraph

template<class node_data_t, class edge_data_t, class derived_node_t, class derived_edge_t>
class Slic3r::Arachne::HalfEdgeGraph< node_data_t, edge_data_t, derived_node_t, derived_edge_t >

Inheritance diagram for Slic3r::Arachne::HalfEdgeGraph< node_data_t, edge_data_t, derived_node_t, derived_edge_t >:

Collaboration diagram for Slic3r::Arachne::HalfEdgeGraph< node_data_t, edge_data_t, derived_node_t, derived_edge_t >:

Class Members
typedef derived_edge_t	edge_t derived_edge_t
typedef list< edge_t >	Edges std::list<edge_t>
typedef derived_node_t	node_t derived_node_t
typedef list< node_t >	Nodes std::list<node_t>

Class Members
Edges	edges
Nodes	nodes

Slic3r::Arachne::WallToolPathsParams

class Slic3r::Arachne::WallToolPathsParams

Class Members
bool	is_top_or_bottom_layer = false
float	min_bead_width = 0.f
float	min_feature_size = 0.f
float	min_length_factor = 0.5f
int	wall_distribution_count = 1
coord_t	wall_maximum_deviation = meshfix_maximum_deviation()
coord_t	wall_maximum_resolution = meshfix_maximum_resolution()
float	wall_transition_angle = 10.f
float	wall_transition_filter_deviation = 0.f
float	wall_transition_length = 0.f

Typedef Documentation

BeadingStrategyPtr

using Slic3r::Arachne::BeadingStrategyPtr = std::unique_ptr<BeadingStrategy>

ExtrusionJunctions

using Slic3r::Arachne::ExtrusionJunctions = std::vector<ExtrusionJunction>

LineJunctions

using Slic3r::Arachne::LineJunctions = std::vector<ExtrusionJunction>

LocToLineGrid

typedef SparseLineGrid<PolygonsPointIndex, PolygonsPointIndexSegmentLocator> Slic3r::Arachne::LocToLineGrid

PolygonsPointIndex

using Slic3r::Arachne::PolygonsPointIndex = PathsPointIndex<Polygons>

VariableWidthLines

using Slic3r::Arachne::VariableWidthLines = std::vector<ExtrusionLine>

VD

using Slic3r::Arachne::VD = Slic3r::Geometry::VoronoiDiagram

Function Documentation

colinear_vertex_tolerance()

coord_t Slic3r::Arachne::colinear_vertex_tolerance ( )

inline

{ return coord_t(SCALED_EPSILON); }

References SCALED_EPSILON.

Referenced by Slic3r::Arachne::ExtrusionLine::simplify(), and simplify().

Here is the caller graph for this function:

createLocToLineGrid()

std::unique_ptr< LocToLineGrid > Slic3r::Arachne::createLocToLineGrid	(	const Polygons &	polygons,
		int	square_size )

{
    unsigned int n_points = 0;
    for (const auto &poly : polygons)
        n_points += poly.size();
 
    auto ret = std::make_unique<LocToLineGrid>(square_size, n_points);
 
    for (unsigned int poly_idx = 0; poly_idx < polygons.size(); poly_idx++)
        for (unsigned int point_idx = 0; point_idx < polygons[poly_idx].size(); point_idx++)
            ret->insert(PolygonsPointIndex(&polygons, poly_idx, point_idx));
    return ret;
}

Referenced by fixSelfIntersections().

Here is the caller graph for this function:

fixSelfIntersections()

void Slic3r::Arachne::fixSelfIntersections	(	const coord_t	epsilon,
		Polygons &	thiss )

{
    if (epsilon < 1)
        return;
 
    const int64_t half_epsilon = (epsilon + 1) / 2;
 
    // Points too close to line segments should be moved a little away from those line segments, but less than epsilon,
    //   so at least half-epsilon distance between points can still be guaranteed.
    const coord_t grid_size  = scaled<coord_t>(2.);
    auto              query_grid = createLocToLineGrid(thiss, grid_size);
 
    const auto    move_dist         = std::max<int64_t>(2L, half_epsilon - 2);
    const int64_t half_epsilon_sqrd = half_epsilon * half_epsilon;
 
    const size_t n = thiss.size();
    for (size_t poly_idx = 0; poly_idx < n; poly_idx++) {
        const size_t pathlen = thiss[poly_idx].size();
        for (size_t point_idx = 0; point_idx < pathlen; ++point_idx) {
            Point &pt = thiss[poly_idx][point_idx];
            for (const auto &line : query_grid->getNearby(pt, epsilon)) {
                const size_t line_next_idx = (line.point_idx + 1) % thiss[line.poly_idx].size();
                if (poly_idx == line.poly_idx && (point_idx == line.point_idx || point_idx == line_next_idx))
                    continue;
 
                const Line segment(thiss[line.poly_idx][line.point_idx], thiss[line.poly_idx][line_next_idx]);
                Point      segment_closest_point;
                segment.distance_to_squared(pt, &segment_closest_point);
 
                if (half_epsilon_sqrd >= (pt - segment_closest_point).cast<int64_t>().squaredNorm()) {
                    const Point  &other = thiss[poly_idx][(point_idx + 1) % pathlen];
                    const Vec2i64 vec   = (LinearAlg2D::pointIsLeftOfLine(other, segment.a, segment.b) > 0 ? segment.b - segment.a : segment.a - segment.b).cast<int64_t>();
                    assert(Slic3r::sqr(double(vec.x())) < double(std::numeric_limits<int64_t>::max()));
                    assert(Slic3r::sqr(double(vec.y())) < double(std::numeric_limits<int64_t>::max()));
                    const int64_t len   = vec.norm();
                    pt.x() += (-vec.y() * move_dist) / len;
                    pt.y() += (vec.x() * move_dist) / len;
                }
            }
        }
    }
}

References Slic3r::cast(), createLocToLineGrid(), Slic3r::Arachne::LinearAlg2D::pointIsLeftOfLine(), Slic3r::scaled(), and Slic3r::sqr().

Referenced by Slic3r::Arachne::WallToolPaths::generate().

Here is the call graph for this function:

Here is the caller graph for this function:

make_paths_params()

WallToolPathsParams Slic3r::Arachne::make_paths_params	(	const int	layer_id,
		const PrintObjectConfig &	print_object_config,
		const PrintConfig &	print_config )

{
    WallToolPathsParams input_params;
    {
        const double min_nozzle_diameter = *std::min_element(print_config.nozzle_diameter.values.begin(), print_config.nozzle_diameter.values.end());
        if (const auto &min_feature_size_opt = print_object_config.min_feature_size)
            input_params.min_feature_size = min_feature_size_opt.value * 0.01 * min_nozzle_diameter;
 
        if (const auto &min_wall_length_factor_opt = print_object_config.min_length_factor)
            input_params.min_length_factor = min_wall_length_factor_opt.value;
        else
            input_params.min_length_factor = 0.5f;
 
        if (layer_id == 0) {
            if (const auto &initial_layer_min_bead_width_opt = print_object_config.initial_layer_min_bead_width)
                input_params.min_bead_width = initial_layer_min_bead_width_opt.value * 0.01 * min_nozzle_diameter;
        } else {
            if (const auto &min_bead_width_opt = print_object_config.min_bead_width)
                input_params.min_bead_width = min_bead_width_opt.value * 0.01 * min_nozzle_diameter;
        }
 
        if (const auto &wall_transition_filter_deviation_opt = print_object_config.wall_transition_filter_deviation)
            input_params.wall_transition_filter_deviation = wall_transition_filter_deviation_opt.value * 0.01 * min_nozzle_diameter;
 
        if (const auto &wall_transition_length_opt = print_object_config.wall_transition_length)
            input_params.wall_transition_length = wall_transition_length_opt.value * 0.01 * min_nozzle_diameter;
 
        input_params.wall_transition_angle   = print_object_config.wall_transition_angle.value;
        input_params.wall_distribution_count = print_object_config.wall_distribution_count.value;
 
        input_params.is_top_or_bottom_layer = false; // Set to default value
 
        if (const auto& wall_maximum_resolution_opt = print_object_config.wall_maximum_resolution)
            input_params.wall_maximum_resolution = scaled<coord_t>(wall_maximum_resolution_opt.value);
 
        if (const auto& wall_maximum_deviation_opt = print_object_config.wall_maximum_deviation)
            input_params.wall_maximum_deviation = scaled<coord_t>(wall_maximum_deviation_opt.value);
    }
 
    return input_params;
}

References Slic3r::Arachne::WallToolPathsParams::is_top_or_bottom_layer, Slic3r::Arachne::WallToolPathsParams::min_bead_width, Slic3r::Arachne::WallToolPathsParams::min_feature_size, Slic3r::Arachne::WallToolPathsParams::min_length_factor, Slic3r::PrintObjectConfig, Slic3r::scaled(), Slic3r::Arachne::WallToolPathsParams::wall_distribution_count, Slic3r::Arachne::WallToolPathsParams::wall_maximum_deviation, Slic3r::Arachne::WallToolPathsParams::wall_maximum_resolution, Slic3r::Arachne::WallToolPathsParams::wall_transition_angle, Slic3r::Arachne::WallToolPathsParams::wall_transition_filter_deviation, and Slic3r::Arachne::WallToolPathsParams::wall_transition_length.

Referenced by Slic3r::PerimeterGenerator::printable_slices().

Here is the call graph for this function:

Here is the caller graph for this function:

make_point() [1/2]

const Point & Slic3r::Arachne::make_point ( const ExtrusionJunction & ej )

inline

{
    return ej.p;
}

References Slic3r::Arachne::ExtrusionJunction::p.

Referenced by Slic3r::Arachne::PathsPointIndexLocator< Paths >::operator()(), Slic3r::Arachne::PathsPointIndex< Polygons >::p(), and Slic3r::Arachne::PolylineStitcher< Paths, Path, Junction >::stitch().

Here is the caller graph for this function:

make_point() [2/2]

const Point & Slic3r::Arachne::make_point ( const Point & p )

inline

{ return p; }

meshfix_maximum_deviation()

coord_t Slic3r::Arachne::meshfix_maximum_deviation ( )

inline

{ return scaled<coord_t>(0.025); }

References Slic3r::scaled().

Here is the call graph for this function:

meshfix_maximum_extrusion_area_deviation()

coord_t Slic3r::Arachne::meshfix_maximum_extrusion_area_deviation ( )

inline

{ return scaled<coord_t>(2.); }

References Slic3r::scaled().

Referenced by Slic3r::Arachne::WallToolPaths::simplifyToolPaths().

Here is the call graph for this function:

Here is the caller graph for this function:

meshfix_maximum_resolution()

coord_t Slic3r::Arachne::meshfix_maximum_resolution ( )

inline

{ return scaled<coord_t>(0.5); }

References Slic3r::scaled().

Here is the call graph for this function:

normal()

Point Slic3r::Arachne::normal ( const Point & p0, coord_t len )

inlinestatic

{
    int64_t _len = p0.cast<int64_t>().norm();
    if (_len < 1)
        return Point(len, 0);
    return (p0.cast<int64_t>() * int64_t(len) / _len).cast<coord_t>();
};

Referenced by Slic3r::Arachne::SkeletalTrapezoidation::applyTransitions(), and Slic3r::Arachne::SkeletalTrapezoidation::generateExtraRibs().

Here is the caller graph for this function:

operator-()

Point Slic3r::Arachne::operator- ( const ExtrusionJunction & a, const ExtrusionJunction & b )

inline

{
    return a.p - b.p;
}

References Slic3r::Arachne::ExtrusionJunction::p.

pi_div()

template<typename T>

T Slic3r::Arachne::pi_div ( const T div )

constexpr

{ return static_cast<T>(M_PI) / div; }

References M_PI.

removeColinearEdges() [1/2]

void Slic3r::Arachne::removeColinearEdges	(	Polygon &	poly,
		const double	max_deviation_angle )

{
    // TODO: Can be made more efficient (for example, use pointer-types for process-/skip-indices, so we can swap them without copy).
    size_t num_removed_in_iteration = 0;
    do {
        num_removed_in_iteration = 0;
        std::vector<bool> process_indices(poly.points.size(), true);
 
        bool go = true;
        while (go) {
            go = false;
 
            const auto  &rpath   = poly;
            const size_t pathlen = rpath.size();
            if (pathlen <= 3)
                return;
 
            std::vector<bool> skip_indices(poly.points.size(), false);
 
            Polygon new_path;
            for (size_t point_idx = 0; point_idx < pathlen; ++point_idx) {
                // Don't iterate directly over process-indices, but do it this way, because there are points _in_ process-indices that should nonetheless
                // be skipped:
                if (!process_indices[point_idx]) {
                    new_path.points.push_back(rpath[point_idx]);
                    continue;
                }
 
                // Should skip the last point for this iteration if the old first was removed (which can be seen from the fact that the new first was skipped):
                if (point_idx == (pathlen - 1) && skip_indices[0]) {
                    skip_indices[new_path.size()] = true;
                    go                            = true;
                    new_path.points.push_back(rpath[point_idx]);
                    break;
                }
 
                const Point &prev = rpath[(point_idx - 1 + pathlen) % pathlen];
                const Point &pt   = rpath[point_idx];
                const Point &next = rpath[(point_idx + 1) % pathlen];
 
                float angle = LinearAlg2D::getAngleLeft(prev, pt, next); // [0 : 2 * pi]
                if (angle >= float(M_PI)) { angle -= float(M_PI); }                    // map [pi : 2 * pi] to [0 : pi]
 
                // Check if the angle is within limits for the point to 'make sense', given the maximum deviation.
                // If the angle indicates near-parallel segments ignore the point 'pt'
                if (angle > max_deviation_angle && angle < M_PI - max_deviation_angle) {
                    new_path.points.push_back(pt);
                } else if (point_idx != (pathlen - 1)) {
                    // Skip the next point, since the current one was removed:
                    skip_indices[new_path.size()] = true;
                    go                            = true;
                    new_path.points.push_back(next);
                    ++point_idx;
                }
            }
            poly = new_path;
            num_removed_in_iteration += pathlen - poly.points.size();
 
            process_indices.clear();
            process_indices.insert(process_indices.end(), skip_indices.begin(), skip_indices.end());
        }
    } while (num_removed_in_iteration > 0);
}

References Slic3r::angle(), Slic3r::Arachne::LinearAlg2D::getAngleLeft(), M_PI, Slic3r::MultiPoint::points, and Slic3r::MultiPoint::size().

Referenced by Slic3r::Arachne::WallToolPaths::generate(), and removeColinearEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

removeColinearEdges() [2/2]

void Slic3r::Arachne::removeColinearEdges	(	Polygons &	thiss,
		const double	max_deviation_angle = 0.0005 )

{
    for (int p = 0; p < int(thiss.size()); p++) {
        removeColinearEdges(thiss[p], max_deviation_angle);
        if (thiss[p].size() < 3) {
            thiss.erase(thiss.begin() + p);
            p--;
        }
    }
}

References removeColinearEdges().

Here is the call graph for this function:

removeDegenerateVerts()

void Slic3r::Arachne::removeDegenerateVerts

(

Polygons &

thiss

)

Removes overlapping consecutive line segments which don't delimit a positive area.

{
    for (size_t poly_idx = 0; poly_idx < thiss.size(); poly_idx++) {
        Polygon &poly = thiss[poly_idx];
        Polygon  result;
 
        auto isDegenerate = [](const Point &last, const Point &now, const Point &next) {
            Vec2i64 last_line = (now - last).cast<int64_t>();
            Vec2i64 next_line = (next - now).cast<int64_t>();
            return last_line.dot(next_line) == -1 * last_line.norm() * next_line.norm();
        };
        bool isChanged = false;
        for (size_t idx = 0; idx < poly.size(); idx++) {
            const Point &last = (result.size() == 0) ? poly.back() : result.back();
            if (idx + 1 == poly.size() && result.size() == 0)
                break;
 
            const Point &next = (idx + 1 == poly.size()) ? result[0] : poly[idx + 1];
            if (isDegenerate(last, poly[idx], next)) { // lines are in the opposite direction
                // don't add vert to the result
                isChanged = true;
                while (result.size() > 1 && isDegenerate(result[result.size() - 2], result.back(), next))
                    result.points.pop_back();
            } else {
                result.points.emplace_back(poly[idx]);
            }
        }
 
        if (isChanged) {
            if (result.size() > 2) {
                poly = result;
            } else {
                thiss.erase(thiss.begin() + poly_idx);
                poly_idx--; // effectively the next iteration has the same poly_idx (referring to a new poly which is not yet processed)
            }
        }
    }
}

References Slic3r::MultiPoint::back(), Slic3r::cast(), Slic3r::MultiPoint::points, and Slic3r::MultiPoint::size().

Referenced by Slic3r::Arachne::WallToolPaths::generate().

Here is the call graph for this function:

Here is the caller graph for this function:

removeSmallAreas()

void Slic3r::Arachne::removeSmallAreas	(	Polygons &	thiss,
		const double	min_area_size,
		const bool	remove_holes )

{
    auto new_end = thiss.end();
    if (remove_holes) {
        for (auto it = thiss.begin(); it < new_end;) {
            // All polygons smaller than target are removed by replacing them with a polygon from the back of the vector.
            if (fabs(it->area()) < min_area_size) {
                --new_end;
                *it = std::move(*new_end);
                continue; // Don't increment the iterator such that the polygon just swapped in is checked next.
            }
            ++it;
        }
    } else {
        // For each polygon, computes the signed area, move small outlines at the end of the vector and keep pointer on small holes
        Polygons small_holes;
        for (auto it = thiss.begin(); it < new_end;) {
            if (double area = it->area(); fabs(area) < min_area_size) {
                if (area >= 0) {
                    --new_end;
                    if (it < new_end) {
                        std::swap(*new_end, *it);
                        continue;
                    } else { // Don't self-swap the last Path
                        break;
                    }
                } else {
                    small_holes.push_back(*it);
                }
            }
            ++it;
        }
 
        // Removes small holes that have their first point inside one of the removed outlines
        // Iterating in reverse ensures that unprocessed small holes won't be moved
        const auto removed_outlines_start = new_end;
        for (auto hole_it = small_holes.rbegin(); hole_it < small_holes.rend(); hole_it++)
            for (auto outline_it = removed_outlines_start; outline_it < thiss.end(); outline_it++)
                if (Polygon(*outline_it).contains(*hole_it->begin())) {
                    new_end--;
                    *hole_it = std::move(*new_end);
                    break;
                }
    }
    thiss.resize(new_end-thiss.begin());
}

References Slic3r::area(), and Slic3r::Polygon::contains().

Referenced by Slic3r::Arachne::WallToolPaths::generate().

Here is the call graph for this function:

Here is the caller graph for this function:

shorterThan()

template<typename T>

bool Slic3r::Arachne::shorterThan	(	const T &	shape,
		const coord_t	check_length )

{
    const auto *p0     = &shape.back();
    int64_t     length = 0;
    for (const auto &p1 : shape) {
        length += (*p0 - p1).template cast<int64_t>().norm();
        if (length >= check_length)
            return false;
        p0 = &p1;
    }
    return true;
}

References Slic3r::cast(), and Slic3r::length().

Referenced by Slic3r::Arachne::WallToolPaths::removeSmallLines().

Here is the call graph for this function:

Here is the caller graph for this function:

simplify() [1/2]

void Slic3r::Arachne::simplify	(	Polygon &	thiss,
		const int64_t	smallest_line_segment_squared,
		const int64_t	allowed_error_distance_squared )

{
    if (thiss.size() < 3) {
        thiss.points.clear();
        return;
    }
    if (thiss.size() == 3)
        return;
 
    Polygon new_path;
    Point previous = thiss.points.back();
    Point previous_previous = thiss.points.at(thiss.points.size() - 2);
    Point current = thiss.points.at(0);
 
    /* When removing a vertex, we check the height of the triangle of the area
     being removed from the original polygon by the simplification. However,
     when consecutively removing multiple vertices the height of the previously
     removed vertices w.r.t. the shortcut path changes.
     In order to not recompute the new height value of previously removed
     vertices we compute the height of a representative triangle, which covers
     the same amount of area as the area being cut off. We use the Shoelace
     formula to accumulate the area under the removed segments. This works by
     computing the area in a 'fan' where each of the blades of the fan go from
     the origin to one of the segments. While removing vertices the area in
     this fan accumulates. By subtracting the area of the blade connected to
     the short-cutting segment we obtain the total area of the cutoff region.
     From this area we compute the height of the representative triangle using
     the standard formula for a triangle area: A = .5*b*h
     */
    int64_t accumulated_area_removed = int64_t(previous.x()) * int64_t(current.y()) - int64_t(previous.y()) * int64_t(current.x()); // Twice the Shoelace formula for area of polygon per line segment.
 
    for (size_t point_idx = 0; point_idx < thiss.points.size(); point_idx++) {
        current = thiss.points.at(point_idx % thiss.points.size());
 
        //Check if the accumulated area doesn't exceed the maximum.
        Point next;
        if (point_idx + 1 < thiss.points.size()) {
            next = thiss.points.at(point_idx + 1);
        } else if (point_idx + 1 == thiss.points.size() && new_path.size() > 1) { // don't spill over if the [next] vertex will then be equal to [previous]
            next = new_path[0]; //Spill over to new polygon for checking removed area.
        } else {
            next = thiss.points.at((point_idx + 1) % thiss.points.size());
        }
        const int64_t removed_area_next = int64_t(current.x()) * int64_t(next.y()) - int64_t(current.y()) * int64_t(next.x()); // Twice the Shoelace formula for area of polygon per line segment.
        const int64_t negative_area_closing = int64_t(next.x()) * int64_t(previous.y()) - int64_t(next.y()) * int64_t(previous.x()); // area between the origin and the short-cutting segment
        accumulated_area_removed += removed_area_next;
 
        const int64_t length2 = (current - previous).cast<int64_t>().squaredNorm();
 
        // Orca:
        // Checking if the segment's length is smaller than 5 microns (0.005mm).
        // The value of `length2` is scaled and squared, so we need to compare it with the squared value of 5 microns
        if (length2 < Slic3r::sqr(scaled<coord_t>(0.005))) {
            // We're allowed to always delete segments of less than 5 micron.
            continue;
        }
 
        const int64_t area_removed_so_far = accumulated_area_removed + negative_area_closing; // close the shortcut area polygon
        const int64_t base_length_2 = (next - previous).cast<int64_t>().squaredNorm();
 
        if (base_length_2 == 0) //Two line segments form a line back and forth with no area.
            continue; //Remove the vertex.
        //We want to check if the height of the triangle formed by previous, current and next vertices is less than allowed_error_distance_squared.
        //1/2 L = A           [actual area is half of the computed shoelace value] // Shoelace formula is .5*(...) , but we simplify the computation and take out the .5
        //A = 1/2 * b * h     [triangle area formula]
        //L = b * h           [apply above two and take out the 1/2]
        //h = L / b           [divide by b]
        //h^2 = (L / b)^2     [square it]
        //h^2 = L^2 / b^2     [factor the divisor]
        const int64_t height_2 = double(area_removed_so_far) * double(area_removed_so_far) / double(base_length_2);
        // Orca: The value of `height_2` is squared, so we need to compare it with the squared value
        if ((height_2 <= Slic3r::sqr(colinear_vertex_tolerance()) //Almost exactly colinear (barring rounding errors).
             && Line::distance_to_infinite(current, previous, next) <= double(colinear_vertex_tolerance()))) // make sure that height_2 is not small because of cancellation of positive and negative areas
            continue;
 
        if (length2 < smallest_line_segment_squared
            && height_2 <= allowed_error_distance_squared) // removing the vertex doesn't introduce too much error.)
        {
            const int64_t next_length2 = (current - next).cast<int64_t>().squaredNorm();
            if (next_length2 > 4 * smallest_line_segment_squared) {
                // Special case; The next line is long. If we were to remove this, it could happen that we get quite noticeable artifacts.
                // We should instead move this point to a location where both edges are kept and then remove the previous point that we wanted to keep.
                // By taking the intersection of these two lines, we get a point that preserves the direction (so it makes the corner a bit more pointy).
                // We just need to be sure that the intersection point does not introduce an artifact itself.
                Point intersection_point;
                bool has_intersection = Line(previous_previous, previous).intersection_infinite(Line(current, next), &intersection_point);
                if (!has_intersection
                    || Line::distance_to_infinite_squared(intersection_point, previous, current) > double(allowed_error_distance_squared)
                    || (intersection_point - previous).cast<int64_t>().squaredNorm() > smallest_line_segment_squared  // The intersection point is way too far from the 'previous'
                    || (intersection_point - next).cast<int64_t>().squaredNorm() > smallest_line_segment_squared)     // and 'next' points, so it shouldn't replace 'current'
                {
                    // We can't find a better spot for it, but the size of the line is more than 5 micron.
                    // So the only thing we can do here is leave it in...
                }
                else {
                    // New point seems like a valid one.
                    current = intersection_point;
                    // If there was a previous point added, remove it.
                    if(!new_path.empty()) {
                        new_path.points.pop_back();
                        previous = previous_previous;
                    }
                }
            } else {
                continue; //Remove the vertex.
            }
        }
        //Don't remove the vertex.
        accumulated_area_removed = removed_area_next; // so that in the next iteration it's the area between the origin, [previous] and [current]
        previous_previous = previous;
        previous = current; //Note that "previous" is only updated if we don't remove the vertex.
        new_path.points.push_back(current);
    }
 
    thiss = new_path;
}

References Slic3r::cast(), colinear_vertex_tolerance(), Slic3r::Line::distance_to_infinite(), Slic3r::Line::distance_to_infinite_squared(), Slic3r::MultiPoint::empty(), Slic3r::Line::intersection_infinite(), Slic3r::MultiPoint::points, Slic3r::scaled(), Slic3r::MultiPoint::size(), and Slic3r::sqr().

Referenced by Slic3r::Arachne::WallToolPaths::generate(), and simplify().

Here is the call graph for this function:

Here is the caller graph for this function:

simplify() [2/2]

void Slic3r::Arachne::simplify	(	Polygons &	thiss,
		const int64_t	smallest_line_segment = scaled<coord_t>(0.01),
		const int64_t	allowed_error_distance = scaled<coord_t>(0.005) )

Removes vertices of the polygons to make sure that they are not too high resolution.

This removes points which are connected to line segments that are shorter than the smallest_line_segment, unless that would introduce a deviation in the contour of more than allowed_error_distance.

Criteria:

1. Never remove a vertex if either of the connceted segments is larger than smallest_line_segment
2. Never remove a vertex if the distance between that vertex and the final resulting polygon would be higher than allowed_error_distance
3. The direction of segments longer than smallest_line_segment always remains unaltered (but their end points may change if it is connected to a small segment)

Simplify uses a heuristic and doesn't neccesarily remove all removable vertices under the above criteria, but simplify may never violate these criteria. Unless the segments or the distance is smaller than the rounding error of 5 micron.

Vertices which introduce an error of less than 5 microns are removed anyway, even if the segments are longer than the smallest line segment. This makes sure that (practically) colinear line segments are joined into a single line segment.

Parameters

smallest_line_segment	Maximal length of removed line segments.
allowed_error_distance	If removing a vertex introduces a deviation from the original path that is more than this distance, the vertex may not be removed.

{
    const int64_t allowed_error_distance_squared = int64_t(allowed_error_distance) * int64_t(allowed_error_distance);
    const int64_t smallest_line_segment_squared = int64_t(smallest_line_segment) * int64_t(smallest_line_segment);
    for (size_t p = 0; p < thiss.size(); p++)
    {
        simplify(thiss[p], smallest_line_segment_squared, allowed_error_distance_squared);
        if (thiss[p].size() < 3)
        {
            thiss.erase(thiss.begin() + p);
            p--;
        }
    }
}

References Slic3r::scaled(), and simplify().

Here is the call graph for this function:

to_points()

Points Slic3r::Arachne::to_points ( const ExtrusionLine & extrusion_line )

static

{
    Points points;
    points.reserve(extrusion_line.junctions.size());
    for (const ExtrusionJunction &junction : extrusion_line.junctions)
        points.emplace_back(junction.p);
    return points;
}

References Slic3r::Arachne::ExtrusionLine::junctions, and Slic3r::Arachne::ExtrusionJunction::p.

Referenced by Slic3r::Arachne::SkeletalTrapezoidation::constructFromPolygons().

Here is the caller graph for this function:

to_polygon()

Polygon Slic3r::Arachne::to_polygon ( const ExtrusionLine & line )

inlinestatic

{
    Polygon out;
    assert(line.junctions.size() >= 3);
    assert(line.junctions.front().p == line.junctions.back().p);
    out.points.reserve(line.junctions.size() - 1);
    for (auto it = line.junctions.begin(); it != line.junctions.end() - 1; ++it)
        out.points.emplace_back(it->p);
    return out;
}

References Slic3r::Arachne::ExtrusionLine::junctions, and Slic3r::MultiPoint::points.

to_thick_polyline()

template<class PathType>

Slic3r::ThickPolyline Slic3r::Arachne::to_thick_polyline ( const PathType & path )

inlinestatic

{
    assert(path.size() >= 2);
    Slic3r::ThickPolyline out;
    out.points.emplace_back(path.front().x(), path.front().y());
    out.width.emplace_back(path.front().z());
    out.points.emplace_back(path[1].x(), path[1].y());
    out.width.emplace_back(path[1].z());
 
    auto it_prev = path.begin() + 1;
    for (auto it = path.begin() + 2; it != path.end(); ++it) {
        out.points.emplace_back(it->x(), it->y());
        out.width.emplace_back(it_prev->z());
        out.width.emplace_back(it->z());
        it_prev = it;
    }
 
    return out;
}

References Slic3r::MultiPoint::points, and Slic3r::ThickPolyline::width.

Referenced by Slic3r::FillConcentric::_fill_surface_single(), Slic3r::FillSpiralInset::_fill_surface_single(), Slic3r::extrusion_paths_append(), Slic3r::extrusion_paths_append(), Slic3r::FillConcentricInternal::fill_surface_extrusion(), Slic3r::open_loop(), and Slic3r::traverse_loops().

Here is the caller graph for this function:

Variable Documentation

fill_outline_gaps

bool Slic3r::Arachne::fill_outline_gaps = true

constexpr

Referenced by Slic3r::Arachne::WallToolPaths::WallToolPaths().