Slic3r::Arachne Namespace Reference

Namespaces
namespace	LinearAlg2D

Classes
class	BeadingStrategy
class	BeadingStrategyFactory
class	DistributedBeadingStrategy
struct	ExtrusionJunction
struct	ExtrusionLine
class	HalfEdge
class	HalfEdgeGraph
class	HalfEdgeNode
class	LimitedBeadingStrategy
class	OuterWallInsetBeadingStrategy
class	PathsPointIndex
struct	PathsPointIndexLocator
class	PointMatrix
struct	PolygonsPointIndexSegmentLocator
class	PolygonsSegmentIndex
class	PolylineStitcher
class	RedistributeBeadingStrategy
class	SkeletalTrapezoidation
class	SkeletalTrapezoidationEdge
class	SkeletalTrapezoidationGraph
class	SkeletalTrapezoidationJoint
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	STHalfEdge
class	STHalfEdgeNode
class	VoronoiUtils
class	WallToolPaths
class	WideningBeadingStrategy

Typedefs
using	BeadingStrategyPtr = std::unique_ptr< BeadingStrategy >
using	PointMap = SkeletalTrapezoidation::PointMap
using	NodeSet = SkeletalTrapezoidation::NodeSet
using	LineJunctions = std::vector< ExtrusionJunction >
using	VariableWidthLines = std::vector< ExtrusionLine >
using	PolygonsPointIndex = PathsPointIndex< Polygons >
using	PolygonsPointIndexLocator = PathsPointIndexLocator< Polygons >
typedef SparseLineGrid< PolygonsPointIndex, PolygonsPointIndexSegmentLocator >	LocToLineGrid

Enumerations
enum class	VoronoiDiagramStatus {   NO_ISSUE_DETECTED , MISSING_VORONOI_VERTEX , NON_PLANAR_VORONOI_DIAGRAM , VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT ,   OTHER_TYPE_OF_VORONOI_DIAGRAM_DEGENERATION }

Functions
template<typename T >
constexpr T	pi_div (const T div)
static bool	has_finite_edge_with_non_finite_vertex (const Geometry::VoronoiDiagram &voronoi_diagram)
static bool	detect_missing_voronoi_vertex (const Geometry::VoronoiDiagram &voronoi_diagram, const std::vector< SkeletalTrapezoidation::Segment > &segments)
static bool	has_missing_twin_edge (const SkeletalTrapezoidationGraph &graph)
static void	rotate_back_skeletal_trapezoidation_graph_after_fix (SkeletalTrapezoidationGraph &graph, const double fix_angle, const PointMap &vertex_mapping)
bool	detect_voronoi_edge_intersecting_input_segment (const Geometry::VoronoiDiagram &voronoi_diagram, const std::vector< VoronoiUtils::Segment > &segments)
VoronoiDiagramStatus	detect_voronoi_diagram_known_issues (const Geometry::VoronoiDiagram &voronoi_diagram, const std::vector< SkeletalTrapezoidation::Segment > &segments)
static std::pair< PointMap, double >	try_to_fix_degenerated_voronoi_diagram_by_rotation (Geometry::VoronoiDiagram &voronoi_diagram, const Polygons &polys, Polygons &polys_rotated, std::vector< SkeletalTrapezoidation::Segment > &segments, const std::vector< double > &fix_angles)
static Point	normal (const Point &p0, coord_t len)
Point	operator- (const ExtrusionJunction &a, const ExtrusionJunction &b)
const Point &	make_point (const ExtrusionJunction &ej)
static Slic3r::ThickPolyline	to_thick_polyline (const Arachne::ExtrusionLine &line_junctions)
static Slic3r::ThickPolyline	to_thick_polyline (const ClipperLib_Z::Path &path)
static Polygon	to_polygon (const ExtrusionLine &line)
const Point &	make_point (const Point &p)
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)

Variables
constexpr bool	fill_outline_gaps = true
constexpr coord_t	meshfix_maximum_resolution = scaled<coord_t>(0.5)
constexpr coord_t	meshfix_maximum_deviation = scaled<coord_t>(0.025)
constexpr coord_t	meshfix_maximum_extrusion_area_deviation = scaled<coord_t>(2.)

---

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
typedef list< edge_t >	Edges
typedef derived_node_t	node_t
typedef list< node_t >	Nodes

Class Members
Edges	edges
Nodes	nodes

Typedef Documentation

BeadingStrategyPtr

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

LineJunctions

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

LocToLineGrid

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

NodeSet

using Slic3r::Arachne::NodeSet = typedef SkeletalTrapezoidation::NodeSet

PointMap

using Slic3r::Arachne::PointMap = typedef SkeletalTrapezoidation::PointMap

PolygonsPointIndex

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

PolygonsPointIndexLocator

using Slic3r::Arachne::PolygonsPointIndexLocator = typedef PathsPointIndexLocator<Polygons>

VariableWidthLines

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

Enumeration Type Documentation

VoronoiDiagramStatus

enum class Slic3r::Arachne::VoronoiDiagramStatus

strong

Enumerator
NO_ISSUE_DETECTED
MISSING_VORONOI_VERTEX
NON_PLANAR_VORONOI_DIAGRAM
VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT
OTHER_TYPE_OF_VORONOI_DIAGRAM_DEGENERATION

                                {
    NO_ISSUE_DETECTED,
    MISSING_VORONOI_VERTEX,
    NON_PLANAR_VORONOI_DIAGRAM,
    VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT,
    OTHER_TYPE_OF_VORONOI_DIAGRAM_DEGENERATION
};

Function Documentation

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:

detect_missing_voronoi_vertex()

static bool Slic3r::Arachne::detect_missing_voronoi_vertex ( const Geometry::VoronoiDiagram &  voronoi_diagram, const std::vector< SkeletalTrapezoidation::Segment > &  segments  )

static

                                                                                                                                                   {
    if (has_finite_edge_with_non_finite_vertex(voronoi_diagram))
        return true;
 
    for (VoronoiUtils::vd_t::cell_type cell : voronoi_diagram.cells()) {
        if (!cell.incident_edge())
            continue; // There is no spoon
 
        if (cell.contains_segment()) {
            const SkeletalTrapezoidation::Segment &source_segment = VoronoiUtils::getSourceSegment(cell, segments);
            const Point                            from           = source_segment.from();
            const Point                            to             = source_segment.to();
 
            // Find starting edge
            // Find end edge
            bool                           seen_possible_start             = false;
            bool                           after_start                     = false;
            bool                           ending_edge_is_set_before_start = false;
            VoronoiUtils::vd_t::edge_type *starting_vd_edge                = nullptr;
            VoronoiUtils::vd_t::edge_type *ending_vd_edge                  = nullptr;
            VoronoiUtils::vd_t::edge_type *edge                            = cell.incident_edge();
            do {
                if (edge->is_infinite() || edge->vertex0() == nullptr || edge->vertex1() == nullptr || !VoronoiUtils::is_finite(*edge->vertex0()) || !VoronoiUtils::is_finite(*edge->vertex1()))
                    continue;
 
                Vec2i64 v0 = VoronoiUtils::p(edge->vertex0());
                Vec2i64 v1 = VoronoiUtils::p(edge->vertex1());
 
                assert(!(v0 == to.cast<int64_t>() && v1 == from.cast<int64_t>()));
                if (v0 == to.cast<int64_t>() && !after_start) { // Use the last edge which starts in source_segment.to
                    starting_vd_edge    = edge;
                    seen_possible_start = true;
                } else if (seen_possible_start) {
                    after_start = true;
                }
 
                if (v1 == from.cast<int64_t>() && (!ending_vd_edge || ending_edge_is_set_before_start)) {
                    ending_edge_is_set_before_start = !after_start;
                    ending_vd_edge                  = edge;
                }
            } while (edge = edge->next(), edge != cell.incident_edge());
 
            if (!starting_vd_edge || !ending_vd_edge || starting_vd_edge == ending_vd_edge)
                return true;
        }
    }
 
    return false;
}

References Slic3r::Arachne::PolygonsSegmentIndex::from(), Slic3r::Arachne::VoronoiUtils::getSourceSegment(), has_finite_edge_with_non_finite_vertex(), Slic3r::Arachne::VoronoiUtils::is_finite(), Slic3r::Arachne::VoronoiUtils::p(), and Slic3r::Arachne::PolygonsSegmentIndex::to().

Referenced by Slic3r::Arachne::SkeletalTrapezoidation::constructFromPolygons(), and detect_voronoi_diagram_known_issues().

Here is the call graph for this function:

Here is the caller graph for this function:

detect_voronoi_diagram_known_issues()

VoronoiDiagramStatus Slic3r::Arachne::detect_voronoi_diagram_known_issues	(	const Geometry::VoronoiDiagram &	voronoi_diagram,
		const std::vector< SkeletalTrapezoidation::Segment > &	segments
	)

{
    if (const bool has_missing_voronoi_vertex = detect_missing_voronoi_vertex(voronoi_diagram, segments); has_missing_voronoi_vertex) {
        return VoronoiDiagramStatus::MISSING_VORONOI_VERTEX;
    } else if (const bool has_voronoi_edge_intersecting_input_segment = detect_voronoi_edge_intersecting_input_segment(voronoi_diagram, segments); has_voronoi_edge_intersecting_input_segment) {
        // Detection if Voronoi edge is intersecting input segment detects at least one model in GH issue #8446.
        return VoronoiDiagramStatus::VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT;
    } else if (const bool is_voronoi_diagram_planar = Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_angle(voronoi_diagram, segments); !is_voronoi_diagram_planar) {
        // Detection of non-planar Voronoi diagram detects at least GH issues #8474, #8514 and #8446.
        return VoronoiDiagramStatus::NON_PLANAR_VORONOI_DIAGRAM;
    }
    return VoronoiDiagramStatus::NO_ISSUE_DETECTED;
}

References detect_missing_voronoi_vertex(), detect_voronoi_edge_intersecting_input_segment(), Slic3r::Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_angle(), MISSING_VORONOI_VERTEX, NO_ISSUE_DETECTED, NON_PLANAR_VORONOI_DIAGRAM, and VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT.

Referenced by Slic3r::Arachne::SkeletalTrapezoidation::constructFromPolygons(), and try_to_fix_degenerated_voronoi_diagram_by_rotation().

Here is the call graph for this function:

Here is the caller graph for this function:

detect_voronoi_edge_intersecting_input_segment()

bool Slic3r::Arachne::detect_voronoi_edge_intersecting_input_segment	(	const Geometry::VoronoiDiagram &	voronoi_diagram,
		const std::vector< VoronoiUtils::Segment > &	segments
	)

{
    for (VoronoiUtils::vd_t::cell_type cell : voronoi_diagram.cells()) {
        if (!cell.incident_edge())
            continue; // Degenerated cell, there is no spoon
 
        if (!cell.contains_segment())
            continue; // Skip cells that don't contain segments.
 
        const VoronoiUtils::Segment &source_segment      = VoronoiUtils::getSourceSegment(cell, segments);
        const Vec2d                  source_segment_from = source_segment.from().cast<double>();
        const Vec2d                  source_segment_vec  = source_segment.to().cast<double>() - source_segment_from;
 
        Point                          start_source_point, end_source_point;
        VoronoiUtils::vd_t::edge_type *begin_voronoi_edge = nullptr, *end_voronoi_edge = nullptr;
        SkeletalTrapezoidation::computeSegmentCellRange(cell, start_source_point, end_source_point, begin_voronoi_edge, end_voronoi_edge, segments);
        // All Voronoi vertices must be on left side of the source segment, otherwise Voronoi diagram is invalid.
        // FIXME Lukas H.: Be aware that begin_voronoi_edge and end_voronoi_edge could be nullptr in some specific cases.
        //                 It mostly happens when there is some missing Voronoi, for example, in GH issue #8846 (IssuesWithMysteriousPerimeters.3mf).
        if (begin_voronoi_edge != nullptr && end_voronoi_edge != nullptr)
            for (VoronoiUtils::vd_t::edge_type *edge = begin_voronoi_edge; edge != end_voronoi_edge; edge = edge->next())
                if (const Vec2d edge_v1(edge->vertex1()->x(), edge->vertex1()->y()); Slic3r::cross2(source_segment_vec, edge_v1 - source_segment_from) < 0)
                    return true;
    }
 
    return false;
}

Referenced by detect_voronoi_diagram_known_issues().

Here is the caller graph for this function:

fixSelfIntersections()

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

{
    if (epsilon < 1) {
        ClipperLib::SimplifyPolygons(ClipperUtils::PolygonsProvider(thiss), ClipperLib::pftEvenOdd);
        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.
    constexpr 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;
                }
            }
        }
    }
 
    ClipperLib::SimplifyPolygons(ClipperUtils::PolygonsProvider(thiss), ClipperLib::pftEvenOdd);
}

References createLocToLineGrid(), ClipperLib::pftEvenOdd, Slic3r::Arachne::LinearAlg2D::pointIsLeftOfLine(), segment(), ClipperLib::SimplifyPolygons(), 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:

has_finite_edge_with_non_finite_vertex()

static bool Slic3r::Arachne::has_finite_edge_with_non_finite_vertex ( const Geometry::VoronoiDiagram &  voronoi_diagram )

static

{
    for (const VoronoiUtils::vd_t::edge_type &edge : voronoi_diagram.edges()) {
        if (edge.is_finite()) {
            assert(edge.vertex0() != nullptr && edge.vertex1() != nullptr);
            if (edge.vertex0() == nullptr || edge.vertex1() == nullptr || !VoronoiUtils::is_finite(*edge.vertex0()) ||
                !VoronoiUtils::is_finite(*edge.vertex1()))
                return true;
        }
    }
    return false;
}

References Slic3r::Arachne::VoronoiUtils::is_finite().

Referenced by detect_missing_voronoi_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

has_missing_twin_edge()

static bool Slic3r::Arachne::has_missing_twin_edge ( const SkeletalTrapezoidationGraph &  graph )

static

{
    for (const auto &edge : graph.edges)
        if (edge.twin == nullptr)
            return true;
    return false;
}

References Slic3r::Arachne::HalfEdgeGraph< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::edges.

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

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< Paths >::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; }

normal()

static 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(), Slic3r::Arachne::SkeletalTrapezoidation::generateExtraRibs(), and Slic3r::Arachne::LinearAlg2D::isInsideCorner().

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;
}

pi_div()

template<typename T >

constexpr 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::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 to_path = [](const Polygon &poly) -> ClipperLib::Path {
        ClipperLib::Path out;
        for (const Point &pt : poly.points)
            out.emplace_back(ClipperLib::cInt(pt.x()), ClipperLib::cInt(pt.y()));
        return out;
    };
 
    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(ClipperLib::Area(to_path(*it))) < 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 = ClipperLib::Area(to_path(*it)); 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(), ClipperLib::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:

rotate_back_skeletal_trapezoidation_graph_after_fix()

static void Slic3r::Arachne::rotate_back_skeletal_trapezoidation_graph_after_fix ( SkeletalTrapezoidationGraph &  graph, const double  fix_angle, const PointMap &  vertex_mapping  )

inlinestatic

{
    for (STHalfEdgeNode &node : graph.nodes) {
        // If a mapping exists between a rotated point and an original point, use this mapping. Otherwise, rotate a point in the opposite direction.
        if (auto node_it = vertex_mapping.find(node.p); node_it != vertex_mapping.end())
            node.p = node_it->second;
        else
            node.p.rotate(-fix_angle);
    }
}

References Slic3r::Arachne::HalfEdgeGraph< node_data_t, edge_data_t, derived_node_t, derived_edge_t >::nodes.

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

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::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();
        if (length2 < scaled<int64_t>(25.)) {
            // 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);
        if ((height_2 <= Slic3r::sqr(scaled<coord_t>(0.005)) //Almost exactly colinear (barring rounding errors).
             && Line::distance_to_infinite(current, previous, next) <= scaled<double>(0.005))) // 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::Line::distance_to_infinite(), Slic3r::Line::distance_to_infinite_squared(), Slic3r::MultiPoint::empty(), Slic3r::Line::intersection_infinite(), Slic3r::MultiPoint::points, 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 simplify().

Here is the call graph for this function:

to_polygon()

static 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() [1/2]

static Slic3r::ThickPolyline Slic3r::Arachne::to_thick_polyline ( const Arachne::ExtrusionLine &  line_junctions )

inlinestatic

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

References Slic3r::Arachne::ExtrusionLine::begin(), Slic3r::Arachne::ExtrusionLine::end(), Slic3r::Arachne::ExtrusionLine::front(), Slic3r::ThickPolyline::points, Slic3r::Arachne::ExtrusionLine::size(), and Slic3r::ThickPolyline::width.

Referenced by Slic3r::FillConcentric::_fill_surface_single(), Slic3r::extrusion_paths_append(), and Slic3r::extrusion_paths_append().

Here is the call graph for this function:

Here is the caller graph for this function:

to_thick_polyline() [2/2]

static Slic3r::ThickPolyline Slic3r::Arachne::to_thick_polyline ( const ClipperLib_Z::Path &  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::ThickPolyline::points, and Slic3r::ThickPolyline::width.

try_to_fix_degenerated_voronoi_diagram_by_rotation()

static std::pair< PointMap, double > Slic3r::Arachne::try_to_fix_degenerated_voronoi_diagram_by_rotation ( Geometry::VoronoiDiagram &  voronoi_diagram, const Polygons &  polys, Polygons &  polys_rotated, std::vector< SkeletalTrapezoidation::Segment > &  segments, const std::vector< double > &  fix_angles  )

inlinestatic

{
    const Polygons                              polys_rotated_original = polys_rotated;
    double                                      fixed_by_angle         = fix_angles.front();
    PointMap                                    vertex_mapping;
 
    for (const double &fix_angle : fix_angles) {
        vertex_mapping.clear();
        polys_rotated  = polys_rotated_original;
        fixed_by_angle = fix_angle;
 
        for (Polygon &poly : polys_rotated)
            poly.rotate(fix_angle);
 
        assert(polys_rotated.size() == polys.size());
        for (size_t poly_idx = 0; poly_idx < polys.size(); ++poly_idx) {
            assert(polys_rotated[poly_idx].size() == polys[poly_idx].size());
            for (size_t point_idx = 0; point_idx < polys[poly_idx].size(); ++point_idx)
                vertex_mapping.insert({polys_rotated[poly_idx][point_idx], polys[poly_idx][point_idx]});
        }
 
        segments.clear();
        for (size_t poly_idx = 0; poly_idx < polys_rotated.size(); poly_idx++)
            for (size_t point_idx = 0; point_idx < polys_rotated[poly_idx].size(); point_idx++)
                segments.emplace_back(&polys_rotated, poly_idx, point_idx);
 
        voronoi_diagram.clear();
        construct_voronoi(segments.begin(), segments.end(), &voronoi_diagram);
 
#ifdef ARACHNE_DEBUG_VORONOI
        {
            static int iRun = 0;
            dump_voronoi_to_svg(debug_out_path("arachne_voronoi-diagram-rotated-%d.svg", iRun++).c_str(), voronoi_diagram, to_points(polys), to_lines(polys));
        }
#endif
 
        if (detect_voronoi_diagram_known_issues(voronoi_diagram, segments) == VoronoiDiagramStatus::NO_ISSUE_DETECTED)
            break;
    }
 
    assert(Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_intersection(voronoi_diagram));
 
    return {vertex_mapping, fixed_by_angle};
}

References Slic3r::debug_out_path(), detect_voronoi_diagram_known_issues(), Slic3r::dump_voronoi_to_svg(), Slic3r::Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_intersection(), NO_ISSUE_DETECTED, Slic3r::to_lines(), and Slic3r::to_points().

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

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

fill_outline_gaps

constexpr bool Slic3r::Arachne::fill_outline_gaps = true

constexpr

meshfix_maximum_deviation

constexpr coord_t Slic3r::Arachne::meshfix_maximum_deviation = scaled<coord_t>(0.025)

constexpr

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

meshfix_maximum_extrusion_area_deviation

constexpr coord_t Slic3r::Arachne::meshfix_maximum_extrusion_area_deviation = scaled<coord_t>(2.)

constexpr

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

meshfix_maximum_resolution

constexpr coord_t Slic3r::Arachne::meshfix_maximum_resolution = scaled<coord_t>(0.5)

constexpr

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