diff options
Diffstat (limited to 'src/libslic3r/BridgeDetector.cpp')
| -rw-r--r-- | src/libslic3r/BridgeDetector.cpp | 454 |
1 files changed, 382 insertions, 72 deletions
diff --git a/src/libslic3r/BridgeDetector.cpp b/src/libslic3r/BridgeDetector.cpp index 03d671db4..407a8d7ce 100644 --- a/src/libslic3r/BridgeDetector.cpp +++ b/src/libslic3r/BridgeDetector.cpp @@ -34,8 +34,8 @@ BridgeDetector::BridgeDetector( void BridgeDetector::initialize() { - // 5 degrees stepping - this->resolution = PI/36.0; + // 2 degrees stepping + this->resolution = PI/(90); // output angle not known this->angle = -1.; @@ -46,10 +46,10 @@ void BridgeDetector::initialize() // 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); + 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 @@ -80,10 +80,7 @@ bool BridgeDetector::detect_angle(double bridge_direction_override) 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])); + candidates = bridge_direction_candidates(); } else candidates.emplace_back(BridgeDirection(bridge_direction_override)); @@ -100,63 +97,239 @@ bool BridgeDetector::detect_angle(double bridge_direction_override) 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); + lines.reserve((bbox.max.y() - bbox.min.y() + this->spacing - SCALED_EPSILON) / 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) + // As The lines be spaced half the line width from the edge + // FIXME: some of the test cases may fail. Need to adjust the test cases + for (coord_t y = bbox.min.y() + this->spacing / 2; y <= bbox.max.y(); y += this->spacing) + //for (coord_t y = bbox.min.y(); y <= bbox.max.y(); y += this->spacing) //this is the old version 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))))); + Point((coord_t)round(c * bbox.min.x() - s * y), (coord_t)round(c * y + s * bbox.min.x())), + Point((coord_t)round(c * bbox.max.x() - s * y), (coord_t)round(c * y + s * bbox.max.x())))); + } + + //create boundingbox for anchor regions + std::vector<BoundingBox> anchor_bb; + for (ExPolygon& poly : this->_anchor_regions) { + anchor_bb.emplace_back(poly.contour.bounding_box()); } - double total_length = 0; - double max_length = 0; + //compute stat on line with anchors, and their lengths. + BridgeDirection& c = candidates[i_angle]; + std::vector<coordf_t> dist_anchored; { Lines clipped_lines = intersection_ln(lines, clip_area); for (size_t i = 0; i < clipped_lines.size(); ++i) { + // this can be called 100 000 time per detect_angle, please optimise 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); + bool good_line = false; + coordf_t len = line.length(); + //is anchored? + size_t line_a_anchor_idx = -1; + size_t line_b_anchor_idx = -1; + for (int i = 0; i < _anchor_regions.size(); ++i) { + ExPolygon& poly = this->_anchor_regions[i]; + BoundingBox& polybb = anchor_bb[i]; + if (polybb.contains(line.a) && poly.contains(line.a)) { // using short-circuit evaluation to test boundingbox and only then the other + line_a_anchor_idx = i; + } + if (polybb.contains(line.b) && poly.contains(line.b)) { // using short-circuit evaluation to test boundingbox and only then the other + line_b_anchor_idx = i; + } + if (line_a_anchor_idx < clipped_lines.size() && line_b_anchor_idx < clipped_lines.size()) + break; + } + //check if the anchor search has been successful + if ( (line_a_anchor_idx < clipped_lines.size()) & (line_b_anchor_idx < clipped_lines.size())) { // this 'if' isn't very effective (culls ~ 10% on a benchy) but it's almost free to compute + good_line = true; + //test if it's not a fake bridge + if (line_a_anchor_idx == line_b_anchor_idx) { + good_line = false; + //check that the line go out of the anchor into the briding area + // don't call intersection_ln here, as even if we succeed to limit the number of candidates to ~100, here we can have hundreds of lines, so that means dozen of thousands of calls (or more)! + // add some points (at least the middle) to test, it's quick + Point middle_point = line.midpoint(); + for (int i = 0; i < _anchor_regions.size(); ++i) { + ExPolygon& poly = this->_anchor_regions[i]; + BoundingBox& polybb = anchor_bb[i]; + if (!polybb.contains(middle_point) || !poly.contains(middle_point)) { // using short-circuit evaluation to test boundingbox and only then the other + good_line = true; + break; + } + } + // if still bad, the line is long enough to warrant two more test point? (1/2000 on a benchy) + if (!good_line && len > this->spacing * 10) { + //now test with to more points + Line middle_line; + middle_line.a = (line.a + middle_point) / 2; + middle_line.b = (line.b + middle_point) / 2; + for (int i = 0; i < _anchor_regions.size(); ++i) { + ExPolygon& poly = this->_anchor_regions[i]; + BoundingBox& polybb = anchor_bb[i]; + if (!polybb.contains(middle_line.a) || !poly.contains(middle_line.a)) { // using short-circuit evaluation to test boundingbox and only then the other + good_line = true; + break; + } + if (!polybb.contains(middle_line.b) || !poly.contains(middle_line.b)) { // using short-circuit evaluation to test boundingbox and only then the other + good_line = true; + break; + } + } + } + // If the line is still bad and is a long one, use the more costly intersection_ln. This case is rare enough to swallow the cost. (1/10000 on a benchy) + if (!good_line && len > this->spacing * 40) { + //now test with intersection_ln + Lines lines = intersection_ln(line, to_polygons(this->_anchor_regions)); + good_line = lines.size() > 1; + } + } + } + if(good_line) { + // This line could be anchored at both side and goes over the void to bridge it in its middle. + //store stats + c.total_length_anchored += len; + c.max_length_anchored = std::max(c.max_length_anchored, len); + c.nb_lines_anchored++; + dist_anchored.push_back(len); + } else { + // this line could NOT be anchored. + c.total_length_free += len; + c.max_length_free = std::max(c.max_length_free, len); + c.nb_lines_free++; } } } - if (total_length == 0.) + if (c.total_length_anchored == 0. || c.nb_lines_anchored == 0) { continue; + } else { + have_coverage = true; + // compute median + if (!dist_anchored.empty()) { + std::sort(dist_anchored.begin(), dist_anchored.end()); + c.median_length_anchor = dist_anchored[dist_anchored.size() / 2]; + } + - 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; + // size is 20% + } + } + + // if no direction produced coverage, then there's no bridge direction ? + if (!have_coverage) { + //try again to choose the least worse + // use only poly contour angles + if (bridge_direction_override == 0.) { + candidates = bridge_direction_candidates(true); + } else + candidates.emplace_back(BridgeDirection(bridge_direction_override)); + for (size_t i_angle = 0; i_angle < candidates.size(); ++i_angle) + { + const double angle = candidates[i_angle].angle; + //use the whole polygon + Lines lines; + { + // Get an oriented bounding box around _anchor_regions. + BoundingBox bbox = get_extents_rotated(clip_area, -angle); + // Cover the region with line segments. + lines.reserve((bbox.max.y() - bbox.min.y() + this->spacing - SCALED_EPSILON) / this->spacing); + double s = sin(angle); + double c = cos(angle); + // The lines be spaced half the line width from the edge + for (coord_t y = bbox.min.y() + this->spacing / 2; y <= bbox.max.y(); y += this->spacing) + lines.push_back(Line( + Point((coord_t)round(c * bbox.min.x() - s * y), (coord_t)round(c * y + s * bbox.min.x())), + Point((coord_t)round(c * bbox.max.x() - s * y), (coord_t)round(c * y + s * bbox.max.x())))); + } + //compute stat on line with anchors, and their lengths. + BridgeDirection& c = candidates[i_angle]; + std::vector<coordf_t> dist_anchored; + { + Lines clipped_lines = intersection_ln(lines, clip_area); + 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 has one anchor (or is totally anchored) + coordf_t len = line.length(); + //store stats + c.total_length_anchored += len; + c.max_length_anchored = std::max(c.max_length_anchored, len); + c.nb_lines_anchored++; + dist_anchored.push_back(len); + } else { + // this line could NOT be anchored. + coordf_t len = line.length(); + c.total_length_free += len; + c.max_length_free = std::max(c.max_length_free, len); + c.nb_lines_free++; + } + } + } + if (c.total_length_anchored == 0. || c.nb_lines_anchored == 0) { + continue; + } else { + have_coverage = true; + // compute median + if (!dist_anchored.empty()) { + std::sort(dist_anchored.begin(), dist_anchored.end()); + c.median_length_anchor = dist_anchored[dist_anchored.size() / 2]; + } + + + // size is 20% + } + } } // if no direction produced coverage, then there's no bridge direction - if (! have_coverage) + if (!have_coverage) return false; - - // sort directions by coverage - most coverage first - std::sort(candidates.begin(), candidates.end()); + + //compute global stat (max & min median & max length) + std::vector<coordf_t> all_median_length; + std::vector<coordf_t> all_max_length; + for (BridgeDirection &c : candidates) { + all_median_length.push_back(c.median_length_anchor); + all_max_length.push_back(c.max_length_anchored); + } + std::sort(all_median_length.begin(), all_median_length.end()); + std::sort(all_max_length.begin(), all_max_length.end()); + coordf_t median_max_length = all_max_length[all_max_length.size() / 2]; + coordf_t min_max_length = all_max_length.front(); + coordf_t max_max_length = all_max_length.back(); + coordf_t median_median_length = all_median_length[all_median_length.size() / 2]; + coordf_t min_median_length = all_median_length.front(); + coordf_t max_median_length = all_median_length.back(); + + //compute individual score + for (BridgeDirection& c : candidates) { + c.coverage = 0; + //ratio_anchored is 70% of the score + double ratio_anchored = c.total_length_anchored / (c.total_length_anchored + c.total_length_free); + c.coverage = 70 * ratio_anchored; + //median is 15% (and need to invert it) + double ratio_median = 1 - double(c.median_length_anchor - min_median_length) / (double)std::max(1., max_median_length - min_median_length); + c.coverage += 15 * ratio_median; + //max is 15 % (and need to invert it) + double ratio_max = 1 - double(c.max_length_anchored - min_max_length) / (double)std::max(1., max_max_length - min_max_length); + c.coverage += 15 * ratio_max; + //bonus for perimeter dir + if (c.along_perimeter_length > 0) + c.coverage += 5; + + } // if any other direction is within extrusion width of coverage, prefer it if shorter + // shorter = shorter max length, or if in espilon (10) range, the shorter mean length. // 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() && candidates[i_best].coverage - candidates[i].coverage < this->spacing; ++ i) - if (candidates[i].max_length < candidates[i_best].max_length) + for (size_t i = 1; i < candidates.size(); ++ i) + if (candidates[i].coverage > candidates[i_best].coverage) i_best = i; this->angle = candidates[i_best].angle; @@ -166,42 +339,95 @@ bool BridgeDetector::detect_angle(double bridge_direction_override) #ifdef SLIC3R_DEBUG printf(" Optimal infill angle is %d degrees\n", (int)Slic3r::Geometry::rad2deg(this->angle)); #endif - + return true; } -std::vector<double> BridgeDetector::bridge_direction_candidates() const +std::vector<BridgeDetector::BridgeDirection> BridgeDetector::bridge_direction_candidates(bool only_from_polygon) const { + std::vector<BridgeDirection> angles; // 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); + if (!only_from_polygon) + for (int i = 0; i <= PI/this->resolution; ++i) + angles.emplace_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()); + //if many lines, only takes the bigger ones. + float mean_sqr_size = 0; + if (lines.size() > 200) { + for (int i = 0; i < 200; i++) { + mean_sqr_size += (float)lines[i].a.distance_to_square(lines[i].b); + } + mean_sqr_size /= 200; + for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line) { + float dist_sqr = line->a.distance_to_square(line->b); + if (dist_sqr > mean_sqr_size) + angles.emplace_back(line->direction(), dist_sqr); + } + }else + for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line) + angles.emplace_back(line->direction(), line->a.distance_to_square(line->b)); } /* 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()); + angles.emplace_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()); + std::sort(angles.begin(), angles.end(), [](const BridgeDirection& bt1, const BridgeDirection& bt2) { return bt1.angle < bt2.angle; }); + + //first delete angles too close to an angle from a perimeter + for (size_t i = 1; i < angles.size(); ++i) { + if (angles[i - 1].along_perimeter_length > 0 && angles[i].along_perimeter_length == 0) + if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i - 1].angle, this->resolution)) { + angles.erase(angles.begin() + i); + --i; + continue; + } + if (angles[i].along_perimeter_length > 0 && angles[i - 1].along_perimeter_length == 0) + if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i - 1].angle, this->resolution)) { + angles.erase(angles.begin() + (i-1)); + --i; + continue; + } + } + //then delete angle to close to each other (high resolution) + double min_resolution = this->resolution / 8; 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; + if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i - 1].angle, min_resolution)) { + // keep the longest of the two. + if (angles[i].along_perimeter_length < angles[i - 1].along_perimeter_length) { + angles.erase(angles.begin() + i); + --i; + } else { + angles.erase(angles.begin() + (i-1)); + --i; + } + } + } + //then, if too much angles, delete more + while (angles.size() > 200) { + min_resolution *= 2; + for (size_t i = 1; i < angles.size(); ++i) { + if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i - 1].angle, min_resolution)) { + // keep the longest of the two. + if (angles[i].along_perimeter_length < angles[i - 1].along_perimeter_length) { + angles.erase(angles.begin() + i); + --i; + } else { + angles.erase(angles.begin() + (i - 1)); + --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)) + if (Slic3r::Geometry::directions_parallel(angles.front().angle, angles.back().angle, min_resolution)) angles.pop_back(); return angles; @@ -266,8 +492,56 @@ static void get_trapezoids2(const ExPolygon &expoly, Polygons* polygons, double polygon.rotate(-(PI/2 - angle), Point(0,0)); } -// Coverage is currently only used by the unit tests. It is extremely slow and unreliable! -Polygons BridgeDetector::coverage(double angle) const + + +void get_trapezoids3_half(const ExPolygon& expoly, Polygons* polygons, float spacing) +{ + + // get all points of this ExPolygon + Points pp = expoly; + + if (pp.empty()) return; + + // build our bounding box + BoundingBox bb(pp); + + // get all x coordinates + coord_t min_x = pp[0].x(), max_x = pp[0].x(); + std::vector<coord_t> xx; + for (Points::const_iterator p = pp.begin(); p != pp.end(); ++p) { + if (min_x > p->x()) min_x = p->x(); + if (max_x < p->x()) max_x = p->x(); + } + for (coord_t x = min_x; x < max_x - (coord_t)(spacing / 2); x += (coord_t)spacing) { + xx.push_back(x); + } + xx.push_back(max_x); + //std::sort(xx.begin(), xx.end()); + + // find trapezoids by looping from first to next-to-last coordinate + for (std::vector<coord_t>::const_iterator x = xx.begin(); x != xx.end() - 1; ++x) { + coord_t next_x = *(x + 1); + if (*x == next_x) continue; + + // build rectangle + Polygon poly; + poly.points.resize(4); + poly[0].x() = *x + (coord_t)spacing / 4; + poly[0].y() = bb.min(1); + poly[1].x() = next_x - (coord_t)spacing / 4; + poly[1].y() = bb.min(1); + poly[2].x() = next_x - (coord_t)spacing / 4; + poly[2].y() = bb.max(1); + poly[3].x() = *x + (coord_t)spacing / 4; + poly[3].y() = bb.max(1); + + // intersect with this expolygon + // append results to return value + polygons_append(*polygons, intersection(Polygons{ poly }, to_polygons(expoly))); + } +} + +Polygons BridgeDetector::coverage(double angle, bool precise) const { if (angle == -1) angle = this->angle; @@ -277,26 +551,65 @@ Polygons BridgeDetector::coverage(double angle) const 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); - + 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); + 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; - get_trapezoids2(expoly, &trapezoids, PI/2.0); - for (const Polygon &trapezoid : trapezoids) { - // not nice, we need a more robust non-numeric check + 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; - for (const Line &supported_line : intersection_ln(trapezoid.lines(), anchors)) - if (supported_line.length() >= this->spacing) - ++ n_supported; - if (n_supported >= 2) + 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)); + } } } } @@ -306,7 +619,7 @@ Polygons BridgeDetector::coverage(double angle) const 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); + //covered = intersection(this->expolygons, covered); #if 0 { my @lines = map @{$_->lines}, @$trapezoids; @@ -329,8 +642,7 @@ Polygons BridgeDetector::coverage(double angle) const /* This method returns the bridge edges (as polylines) that are not supported but would allow the entire bridge area to be bridged with detected angle if supported too */ -void -BridgeDetector::unsupported_edges(double angle, Polylines* unsupported) const +void BridgeDetector::unsupported_edges(double angle, Polylines* unsupported) const { if (angle == -1) angle = this->angle; if (angle == -1) return; @@ -370,9 +682,7 @@ BridgeDetector::unsupported_edges(double angle, Polylines* unsupported) const */ } -Polylines -BridgeDetector::unsupported_edges(double angle) const -{ +Polylines BridgeDetector::unsupported_edges(double angle) const { Polylines pp; this->unsupported_edges(angle, &pp); return pp; |