Slic3r::BridgeDetector Class Reference

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

Collaboration diagram for Slic3r::BridgeDetector:

Classes
struct	BridgeDirection

Public Member Functions
	BridgeDetector (ExPolygon _expolygon, const ExPolygons &_lower_slices, coord_t _extrusion_width)
	BridgeDetector (const ExPolygons &_expolygons, const ExPolygons &_lower_slices, coord_t _extrusion_width)
bool	detect_angle (double bridge_direction_override=0.)
Polygons	coverage (double angle=-1, bool precise=true) const
void	unsupported_edges (double angle, Polylines *unsupported) const
Polylines	unsupported_edges (double angle=-1) const

Public Attributes
const ExPolygons &	expolygons
ExPolygons	expolygons_owned
const ExPolygons &	lower_slices
coord_t	spacing
double	resolution
double	angle

Private Member Functions
BridgeDetector &	operator= (const BridgeDetector &)
void	initialize ()
std::vector< double >	bridge_direction_candidates () const

Private Attributes
Polylines	_edges
ExPolygons	_anchor_regions

Detailed Description

Constructor & Destructor Documentation

BridgeDetector() [1/2]

Slic3r::BridgeDetector::BridgeDetector	(	ExPolygon	_expolygon,
		const ExPolygons &	_lower_slices,
		coord_t	_extrusion_width )

                                :
    // The original infill polygon, not inflated.
    expolygons(expolygons_owned),
    // All surfaces of the object supporting this region.
    lower_slices(_lower_slices),
    spacing(_spacing)
{
    this->expolygons_owned.push_back(std::move(_expolygon));
    initialize();
}

References expolygons, expolygons_owned, initialize(), lower_slices, and spacing.

Referenced by operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

BridgeDetector() [2/2]

Slic3r::BridgeDetector::BridgeDetector	(	const ExPolygons &	_expolygons,
		const ExPolygons &	_lower_slices,
		coord_t	_extrusion_width )

                                 : 
    // The original infill polygon, not inflated.
    expolygons(_expolygons),
    // All surfaces of the object supporting this region.
    lower_slices(_lower_slices),
    spacing(_spacing)
{
    initialize();
}

References expolygons, initialize(), lower_slices, and spacing.

Here is the call graph for this function:

Member Function Documentation

bridge_direction_candidates()

std::vector< double > Slic3r::BridgeDetector::bridge_direction_candidates ( ) const

private

{
    // we test angles according to configured resolution
    std::vector<double> angles;
    for (int i = 0; i <= PI/this->resolution; ++i)
        angles.push_back(i * this->resolution);
    
    // we also test angles of each bridge contour
    {
        Lines lines = to_lines(this->expolygons);
        for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line)
            angles.push_back(line->direction());
    }
    
    /*  we also test angles of each open supporting edge
        (this finds the optimal angle for C-shaped supports) */
    for (const Polyline &edge : this->_edges)
        if (edge.first_point() != edge.last_point())
            angles.push_back(Line(edge.first_point(), edge.last_point()).direction());
    
    // remove duplicates
    double min_resolution = PI/180.0;  // 1 degree
    std::sort(angles.begin(), angles.end());
    for (size_t i = 1; i < angles.size(); ++i) {
        if (Slic3r::Geometry::directions_parallel(angles[i], angles[i-1], min_resolution)) {
            angles.erase(angles.begin() + i);
            --i;
        }
    }
    /*  compare first value with last one and remove the greatest one (PI) 
        in case they are parallel (PI, 0) */
    if (Slic3r::Geometry::directions_parallel(angles.front(), angles.back(), min_resolution))
        angles.pop_back();
 
    return angles;
}

References _edges, Slic3r::Line::direction(), Slic3r::Geometry::directions_parallel(), expolygons, PI, resolution, and Slic3r::to_lines().

Referenced by detect_angle().

Here is the call graph for this function:

Here is the caller graph for this function:

coverage()

Polygons Slic3r::BridgeDetector::coverage	(	double	angle = -1,
		bool	precise = true ) const

{
    if (angle == -1)
        angle = this->angle;
 
    Polygons covered;
 
    if (angle != -1) {
        // Get anchors, convert them to Polygons and rotate them.
        Polygons anchors = to_polygons(this->_anchor_regions);
        polygons_rotate(anchors, PI / 2.0 - angle);
        //same for region which do not need bridging
        //Polygons supported_area = diff(this->lower_slices.expolygons, this->_anchor_regions, true);
        //polygons_rotate(anchors, PI / 2.0 - angle);
 
        for (ExPolygon expolygon : this->expolygons) {
            // Clone our expolygon and rotate it so that we work with vertical lines.
            expolygon.rotate(PI / 2.0 - angle);
            // Outset the bridge expolygon by half the amount we used for detecting anchors;
            // we'll use this one to generate our trapezoids and be sure that their vertices
            // are inside the anchors and not on their contours leading to false negatives.
            for (ExPolygon &expoly : offset_ex(expolygon, 0.5f * float(this->spacing))) {
                // Compute trapezoids according to a vertical orientation
                Polygons trapezoids;
                if (!precise) get_trapezoids2(expoly, &trapezoids, PI / 2);
                else get_trapezoids3_half(expoly, &trapezoids, float(this->spacing));
                for (Polygon &trapezoid : trapezoids) {
                    size_t n_supported = 0;
                    if (!precise) {
                        // not nice, we need a more robust non-numeric check
                        // imporvment 1: take into account when we go in the supported area.
                        for (const Line &supported_line : intersection_ln(trapezoid.lines(), anchors))
                            if (supported_line.length() >= this->spacing)
                                ++n_supported;
                    } else {
                        Polygons intersects = intersection(Polygons{trapezoid}, anchors);
                        n_supported = intersects.size();
 
                        if (n_supported >= 2) {
                            // trim it to not allow to go outside of the intersections
                            BoundingBox center_bound = intersects[0].bounding_box();
                            coord_t min_y = center_bound.center()(1), max_y = center_bound.center()(1);
                            for (Polygon &poly_bound : intersects) {
                                center_bound = poly_bound.bounding_box();
                                if (min_y > center_bound.center()(1)) min_y = center_bound.center()(1);
                                if (max_y < center_bound.center()(1)) max_y = center_bound.center()(1);
                            }
                            coord_t min_x = trapezoid[0](0), max_x = trapezoid[0](0);
                            for (Point &p : trapezoid.points) {
                                if (min_x > p(0)) min_x = p(0);
                                if (max_x < p(0)) max_x = p(0);
                            }
                            //add what get_trapezoids3 has removed (+EPSILON)
                            min_x -= (this->spacing / 4 + 1);
                            max_x += (this->spacing / 4 + 1);
                            coord_t mid_x = (min_x + max_x) / 2;
                            for (Point &p : trapezoid.points) {
                                if (p(1) < min_y) p(1) = min_y;
                                if (p(1) > max_y) p(1) = max_y;
                                if (p(0) > min_x && p(0) < mid_x) p(0) = min_x;
                                if (p(0) < max_x && p(0) > mid_x) p(0) = max_x;
                            }
                        }
                    }
 
                    if (n_supported >= 2) {
                        //add it
                        covered.push_back(std::move(trapezoid));
                    }
                }
            }
        }
 
        // Unite the trapezoids before rotation, as the rotation creates tiny gaps and intersections between the trapezoids
        // instead of exact overlaps.
        covered = union_(covered);
        // Intersect trapezoids with actual bridge area to remove extra margins and append it to result.
        polygons_rotate(covered, -(PI/2.0 - angle));
        //covered = intersection(this->expolygons, covered);
#if 0
        {
            my @lines = map @{$_->lines}, @$trapezoids;
            $_->rotate(-(PI/2 - $angle), [0,0]) for @lines;
            
            require "Slic3r/SVG.pm";
            Slic3r::SVG::output(
                "coverage_" . rad2deg($angle) . ".svg",
                expolygons          => [$self->expolygon],
                green_expolygons    => $self->_anchor_regions,
                red_expolygons      => $coverage,
                lines               => \@lines,
            );
        }
#endif
    }
    return covered;
}

References _anchor_regions, angle, Slic3r::BoundingBoxBase< PointType, APointsType >::center(), expolygons, Slic3r::get_trapezoids2(), Slic3r::get_trapezoids3_half(), Slic3r::intersection(), Slic3r::intersection_ln(), Slic3r::offset_ex(), PI, Slic3r::polygons_rotate(), Slic3r::Geometry::rad2deg(), spacing, Slic3r::to_polygons(), and Slic3r::union_().

Referenced by detect_angle(), and Slic3r::PerimeterGenerator::process_no_bridge().

Here is the call graph for this function:

Here is the caller graph for this function:

detect_angle()

bool Slic3r::BridgeDetector::detect_angle

(

double

bridge_direction_override = 0.

)

{
    if (this->_edges.empty() || this->_anchor_regions.empty()) 
        // The bridging region is completely in the air, there are no anchors available at the layer below.
        return false;
 
    std::vector<BridgeDirection> candidates;
    if (bridge_direction_override == 0.) {
        std::vector<double> angles = bridge_direction_candidates();
        candidates.reserve(angles.size());
        for (size_t i = 0; i < angles.size(); ++ i)
            candidates.emplace_back(BridgeDirection(angles[i]));
    } else
        candidates.emplace_back(BridgeDirection(bridge_direction_override));
    
    /*  Outset the bridge expolygon by half the amount we used for detecting anchors;
        we'll use this one to clip our test lines and be sure that their endpoints
        are inside the anchors and not on their contours leading to false negatives. */
    Polygons clip_area = offset(this->expolygons, 0.5f * float(this->spacing));
    
    /*  we'll now try several directions using a rudimentary visibility check:
        bridge in several directions and then sum the length of lines having both
        endpoints within anchors */
        
    bool have_coverage = false;
    for (size_t i_angle = 0; i_angle < candidates.size(); ++ i_angle)
    {
        const double angle = candidates[i_angle].angle;
 
        Lines lines;
        {
            // Get an oriented bounding box around _anchor_regions.
            BoundingBox bbox = get_extents_rotated(this->_anchor_regions, - angle);
            // Cover the region with line segments.
            lines.reserve((bbox.max(1) - bbox.min(1) + this->spacing) / this->spacing);
            double s = sin(angle);
            double c = cos(angle);
            //FIXME Vojtech: The lines shall be spaced half the line width from the edge, but then 
            // some of the test cases fail. Need to adjust the test cases then?
//            for (coord_t y = bbox.min(1) + this->spacing / 2; y <= bbox.max(1); y += this->spacing)
            for (coord_t y = bbox.min(1); y <= bbox.max(1); y += this->spacing)
                lines.push_back(Line(
                    Point((coord_t)round(c * bbox.min(0) - s * y), (coord_t)round(c * y + s * bbox.min(0))),
                    Point((coord_t)round(c * bbox.max(0) - s * y), (coord_t)round(c * y + s * bbox.max(0)))));
        }
 
        double total_length = 0;
        double max_length = 0;
        {
            Lines clipped_lines = intersection_ln(lines, clip_area);
            size_t archored_line_num = 0;
            for (size_t i = 0; i < clipped_lines.size(); ++i) {
                const Line &line = clipped_lines[i];
                if (expolygons_contain(this->_anchor_regions, line.a) && expolygons_contain(this->_anchor_regions, line.b)) {
                    // This line could be anchored.
                    double len = line.length();
                    total_length += len;
                    max_length = std::max(max_length, len);
                    archored_line_num++;
                }
            }
            if (clipped_lines.size() > 0 && archored_line_num > 0) {
                candidates[i_angle].archored_percent = (double)archored_line_num / (double)clipped_lines.size();
            }
        }
        if (total_length == 0.)
            continue;
 
        have_coverage = true;
        // Sum length of bridged lines.
        candidates[i_angle].coverage = total_length;
        /*  The following produces more correct results in some cases and more broken in others.
            TODO: investigate, as it looks more reliable than line clipping. */
        // $directions_coverage{$angle} = sum(map $_->area, @{$self->coverage($angle)}) // 0;
        // max length of bridged lines
        candidates[i_angle].max_length = max_length;
    }
 
    // if no direction produced coverage, then there's no bridge direction
    if (! have_coverage)
        return false;
    
    // sort directions by coverage - most coverage first
    std::sort(candidates.begin(), candidates.end());
    
    // if any other direction is within extrusion width of coverage, prefer it if shorter
    // TODO: There are two options here - within width of the angle with most coverage, or within width of the currently perferred?
    size_t i_best = 0;
//    for (size_t i = 1; i < candidates.size() && abs(candidates[i_best].archored_percent - candidates[i].archored_percent) < EPSILON; ++ i)
    for (size_t i = 1; i < candidates.size() && candidates[i_best].coverage - candidates[i].coverage < this->spacing; ++ i)
        if (candidates[i].max_length < candidates[i_best].max_length)
            i_best = i;
 
    this->angle = candidates[i_best].angle;
    if (this->angle >= PI)
        this->angle -= PI;
    
    #ifdef SLIC3R_DEBUG
    printf("  Optimal infill angle is %d degrees\n", (int)Slic3r::Geometry::rad2deg(this->angle));
    #endif
    
    return true;
}

References _anchor_regions, _edges, Slic3r::Line::a, angle, Slic3r::Line::b, bridge_direction_candidates(), coverage(), expolygons, Slic3r::expolygons_contain(), Slic3r::get_extents_rotated(), Slic3r::intersection_ln(), Slic3r::Line::length(), Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::min, Slic3r::offset(), PI, Slic3r::Geometry::rad2deg(), spacing, and Slic3r::total_length().

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

Here is the call graph for this function:

Here is the caller graph for this function:

initialize()

void Slic3r::BridgeDetector::initialize ( )

private

{
    // 5 degrees stepping
    this->resolution = PI/36.0; 
    // output angle not known
    this->angle = -1.;
 
    // Outset our bridge by an arbitrary amout; we'll use this outer margin for detecting anchors.
    Polygons grown = offset(this->expolygons, float(this->spacing));
    
    // Detect possible anchoring edges of this bridging region.
    // Detect what edges lie on lower slices by turning bridge contour and holes
    // into polylines and then clipping them with each lower slice's contour.
    // Currently _edges are only used to set a candidate direction of the bridge (see bridge_direction_candidates()).
  Polygons contours;
  contours.reserve(this->lower_slices.size());
  for (const ExPolygon &expoly : this->lower_slices)
    contours.push_back(expoly.contour);
    this->_edges = intersection_pl(to_polylines(grown), contours);
    
    #ifdef SLIC3R_DEBUG
    printf("  bridge has %zu support(s)\n", this->_edges.size());
    #endif
    
    // detect anchors as intersection between our bridge expolygon and the lower slices
    // safety offset required to avoid Clipper from detecting empty intersection while Boost actually found some edges
    this->_anchor_regions = intersection_ex(grown, union_safety_offset(this->lower_slices));
    
    /*
    if (0) {
        require "Slic3r/SVG.pm";
        Slic3r::SVG::output("bridge.svg",
            expolygons      => [ $self->expolygon ],
            red_expolygons  => $self->lower_slices,
            polylines       => $self->_edges,
        );
    }
    */
}

References _anchor_regions, _edges, angle, expolygons, Slic3r::intersection_ex(), Slic3r::intersection_pl(), lower_slices, Slic3r::offset(), PI, resolution, spacing, Slic3r::to_polylines(), and Slic3r::union_safety_offset().

Referenced by BridgeDetector(), and BridgeDetector().

Here is the call graph for this function:

Here is the caller graph for this function:

operator=()

BridgeDetector & Slic3r::BridgeDetector::operator= ( const BridgeDetector & )

private

References BridgeDetector().

Here is the call graph for this function:

unsupported_edges() [1/2]

void Slic3r::BridgeDetector::unsupported_edges	(	double	angle,
		Polylines *	unsupported ) const

{
    if (angle == -1) angle = this->angle;
    if (angle == -1) return;
 
    Polygons grown_lower = offset(this->lower_slices, float(this->spacing));
 
    for (ExPolygons::const_iterator it_expoly = this->expolygons.begin(); it_expoly != this->expolygons.end(); ++ it_expoly) {    
        // get unsupported bridge edges (both contour and holes)
        Lines unsupported_lines = to_lines(diff_pl(to_polylines(*it_expoly), grown_lower));
        /*  Split into individual segments and filter out edges parallel to the bridging angle
            TODO: angle tolerance should probably be based on segment length and flow width,
            so that we build supports whenever there's a chance that at least one or two bridge
            extrusions would be anchored within such length (i.e. a slightly non-parallel bridging
            direction might still benefit from anchors if long enough)
            double angle_tolerance = PI / 180.0 * 5.0; */
        for (const Line &line : unsupported_lines)
            if (! Slic3r::Geometry::directions_parallel(line.direction(), angle)) {
                unsupported->emplace_back(Polyline());
                unsupported->back().points.emplace_back(line.a);
                unsupported->back().points.emplace_back(line.b);
            }
    }
    
    /*
    if (0) {
        require "Slic3r/SVG.pm";
        Slic3r::SVG::output(
            "unsupported_" . rad2deg($angle) . ".svg",
            expolygons          => [$self->expolygon],
            green_expolygons    => $self->_anchor_regions,
            red_expolygons      => union_ex($grown_lower),
            no_arrows           => 1,
            polylines           => \@bridge_edges,
            red_polylines       => $unsupported,
        );
    }
    */
}

References angle, Slic3r::diff_pl(), Slic3r::Geometry::directions_parallel(), expolygons, lower_slices, Slic3r::offset(), spacing, Slic3r::to_lines(), and Slic3r::to_polylines().

Referenced by unsupported_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

unsupported_edges() [2/2]

Polylines Slic3r::BridgeDetector::unsupported_edges

(

double

angle = -1

)

const

{
    Polylines pp;
    this->unsupported_edges(angle, &pp);
    return pp;
}

References angle, and unsupported_edges().

Here is the call graph for this function:

Member Data Documentation

_anchor_regions

ExPolygons Slic3r::BridgeDetector::_anchor_regions

private

Referenced by coverage(), detect_angle(), and initialize().

_edges

Polylines Slic3r::BridgeDetector::_edges

private

Referenced by bridge_direction_candidates(), detect_angle(), and initialize().

angle

double Slic3r::BridgeDetector::angle

Referenced by coverage(), detect_angle(), initialize(), unsupported_edges(), and unsupported_edges().

expolygons

const ExPolygons& Slic3r::BridgeDetector::expolygons

Referenced by BridgeDetector(), BridgeDetector(), bridge_direction_candidates(), coverage(), detect_angle(), initialize(), and unsupported_edges().

expolygons_owned

ExPolygons Slic3r::BridgeDetector::expolygons_owned

Referenced by BridgeDetector().

lower_slices

const ExPolygons& Slic3r::BridgeDetector::lower_slices

Referenced by BridgeDetector(), BridgeDetector(), initialize(), and unsupported_edges().

resolution

double Slic3r::BridgeDetector::resolution

Referenced by bridge_direction_candidates(), and initialize().

spacing

coord_t Slic3r::BridgeDetector::spacing

Referenced by BridgeDetector(), BridgeDetector(), coverage(), detect_angle(), initialize(), and unsupported_edges().

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/BridgeDetector.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/BridgeDetector.cpp