diff options
author | supermerill <merill@free.fr> | 2021-12-02 19:10:47 +0300 |
---|---|---|
committer | supermerill <merill@free.fr> | 2021-12-02 19:11:32 +0300 |
commit | 201dfdb5c854644392077d7f328995eca32fc35b (patch) | |
tree | 5c0922a4cc72fc1beddef7a2a3866398f4fa1d91 | |
parent | e76b3c6d31aa008db10b081ccb6a9f1123d26105 (diff) |
Optimize the new bridge detector.
-rw-r--r-- | src/libslic3r/BridgeDetector.cpp | 77 |
1 files changed, 69 insertions, 8 deletions
diff --git a/src/libslic3r/BridgeDetector.cpp b/src/libslic3r/BridgeDetector.cpp index 1df8af4f6..dd9c5e5f3 100644 --- a/src/libslic3r/BridgeDetector.cpp +++ b/src/libslic3r/BridgeDetector.cpp @@ -114,22 +114,84 @@ bool BridgeDetector::detect_angle(double bridge_direction_override) 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()); + } + //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]; bool good_line = false; - if (expolygons_contain(this->_anchor_regions, line.a) && expolygons_contain(this->_anchor_regions, line.b)) { - //check that it isn't always inside - Lines lines = intersection_ln(line, to_polygons(this->_anchor_regions)); - good_line = lines.size() > 1; + 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. - coordf_t len = line.length(); + // 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); @@ -137,7 +199,6 @@ bool BridgeDetector::detect_angle(double bridge_direction_override) 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++; @@ -193,7 +254,7 @@ bool BridgeDetector::detect_angle(double bridge_direction_override) 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 + // This line has one anchor (or is totally anchored) coordf_t len = line.length(); //store stats c.total_length_anchored += len; |