1630{
1631 BOOST_LOG_TRIVIAL(info) <<
"Bridge over infill - Start" <<
log_memory_info();
1632
1633 struct CandidateSurface
1634 {
1635 CandidateSurface(const Surface *original_surface,
1636 int layer_index,
1637 Polygons new_polys,
1638 const LayerRegion *region,
1639 double bridge_angle)
1640 : original_surface(original_surface)
1641 , layer_index(layer_index)
1642 , new_polys(new_polys)
1643 , region(region)
1645 {}
1646 const Surface *original_surface;
1647 int layer_index;
1649 const LayerRegion *region;
1651 };
1652
1653 std::map<size_t, std::vector<CandidateSurface>> surfaces_by_layer;
1654
1655
1656 {
1657 tbb::concurrent_vector<CandidateSurface> candidate_surfaces;
1658 tbb::parallel_for(tbb::blocked_range<size_t>(0, this->
layers().
size()), [po =
static_cast<const PrintObject *
>(
this),
1659 &candidate_surfaces](tbb::blocked_range<size_t> r) {
1661 for (size_t lidx = r.begin(); lidx < r.end(); lidx++) {
1662 const Layer *layer = po->get_layer(lidx);
1663 if (layer->lower_layer == nullptr) {
1664 continue;
1665 }
1666 double spacing = layer->regions().front()->flow(
frSolidInfill).scaled_spacing();
1667
1670 for (const LayerRegion *region : layer->lower_layer->regions()) {
1672
1673 unsupported_area.insert(unsupported_area.end(), fill_polys.begin(), fill_polys.end());
1674 for (const Surface &surface : region->fill_surfaces()) {
1675 if (surface.surface_type !=
stInternal || region->region().config().fill_density.value == 100) {
1677 lower_layer_solids.insert(lower_layer_solids.end(), p.begin(), p.end());
1678 }
1679 }
1680 }
1682
1683
1684 lower_layer_solids =
shrink(lower_layer_solids, 1 * spacing);
1685 lower_layer_solids =
expand(lower_layer_solids, (1 + 3) * spacing);
1686
1687 unsupported_area =
shrink(unsupported_area, 3 * spacing);
1688 unsupported_area =
diff(unsupported_area, lower_layer_solids);
1689
1690 for (const LayerRegion *region : layer->regions()) {
1692 for (const Surface *s : region_internal_solids) {
1694
1695
1697 if (!unsupported.empty() && (!partially_supported ||
area(unsupported) > 3 * 3 * spacing * spacing)) {
1699
1701 double area = p.area();
1703 worth_bridging.push_back(p);
1704 }
1705 }
1707 candidate_surfaces.push_back(CandidateSurface(s, lidx, worth_bridging, region, 0));
1708
1709#ifdef DEBUG_BRIDGE_OVER_INFILL
1710 debug_draw(std::to_string(lidx) +
"_candidate_surface_" + std::to_string(
area(s->expolygon)),
1713#endif
1714#ifdef DEBUG_BRIDGE_OVER_INFILL
1715 debug_draw(std::to_string(lidx) +
"_candidate_processing_" + std::to_string(
area(unsupported)),
1719#endif
1720 }
1721 }
1722 }
1723 }
1724 });
1725
1726 for (const CandidateSurface &c : candidate_surfaces) {
1727 surfaces_by_layer[
c.layer_index].push_back(c);
1728 }
1729 }
1730
1731
1732
1733
1734 bool has_lightning_infill = false;
1737 has_lightning_infill = true;
1738 break;
1739 }
1740 }
1741 if (has_lightning_infill) {
1742
1743
1744
1745 std::map<size_t, std::map<const LayerRegion *, SurfaceCollection>> backup_surfaces;
1746 for (
size_t lidx = 0; lidx < this->
layer_count(); lidx++) {
1747 backup_surfaces[lidx] = {};
1748 }
1749
1750 tbb::parallel_for(tbb::blocked_range<size_t>(0, this->
layers().
size()), [po =
this, &backup_surfaces,
1751 &surfaces_by_layer](tbb::blocked_range<size_t> r) {
1753 for (size_t lidx = r.begin(); lidx < r.end(); lidx++) {
1754 if (surfaces_by_layer.find(lidx) == surfaces_by_layer.end())
1755 continue;
1756
1757 Layer *layer = po->get_layer(lidx);
1758 const Layer *lower_layer = layer->lower_layer;
1759 if (lower_layer == nullptr)
1760 continue;
1761
1763 for (const LayerRegion *region : lower_layer->regions()) {
1764 if (region->region().config().fill_pattern ==
ipLightning) {
1766 lightning_fill.insert(lightning_fill.end(), lf.begin(), lf.end());
1767 }
1768 }
1769
1770 if (lightning_fill.empty())
1771 continue;
1772
1773 for (LayerRegion *region : layer->regions()) {
1774 backup_surfaces[lidx][region] = std::move(
1775 region->m_fill_surfaces);
1776
1777 region->m_fill_surfaces = backup_surfaces[lidx][region];
1778 }
1779
1780 for (LayerRegion *region : layer->regions()) {
1783
1784 if (sparse_infill.empty()) {
1785 break;
1786 }
1787 for (const auto &surface : surfaces_by_layer[lidx]) {
1788 if (surface.region != region)
1789 continue;
1791 solid_infill.insert(solid_infill.end(), expansion.begin(), expansion.end());
1792 }
1793
1795 sparse_infill =
diff_ex(sparse_infill, solid_infill);
1796
1798 for (const ExPolygon &ep : solid_infill) {
1800 }
1801 for (const ExPolygon &ep : sparse_infill) {
1802 region->m_fill_surfaces.surfaces.emplace_back(
stInternal, ep);
1803 }
1804 }
1805 }
1806 });
1807
1808
1810
1811
1812
1813 for (
size_t lidx = 0; lidx < this->
layer_count(); lidx++) {
1815 for (LayerRegion *region : layer->regions()) {
1816 if (backup_surfaces[lidx].
find(region) != backup_surfaces[lidx].
end()) {
1817 region->m_fill_surfaces = std::move(backup_surfaces[lidx][region]);
1818 }
1819 }
1820 }
1821 }
1822
1823 std::map<size_t, Polylines> infill_lines;
1824
1825 {
1826 std::vector<std::pair<const Surface *, float>> surfaces_w_bottom_z;
1827 for (const auto &pair : surfaces_by_layer) {
1828 for (const CandidateSurface &c : pair.second) {
1829 surfaces_w_bottom_z.emplace_back(
c.original_surface,
c.region->m_layer->bottom_z());
1830 }
1831 }
1832
1834
1835 std::vector<size_t> layers_to_generate_infill;
1836 for (const auto &pair : surfaces_by_layer) {
1837 assert(pair.first > 0);
1838 infill_lines[pair.first - 1] = {};
1839 layers_to_generate_infill.push_back(pair.first - 1);
1840 }
1841
1842 tbb::parallel_for(tbb::blocked_range<size_t>(0, layers_to_generate_infill.size()), [po =
static_cast<const PrintObject *
>(
this),
1843 &layers_to_generate_infill,
1844 &infill_lines](tbb::blocked_range<size_t> r) {
1845 PRINT_OBJECT_TIME_LIMIT_MILLIS(PRINT_OBJECT_TIME_LIMIT_DEFAULT);
1846 for (size_t job_idx = r.begin(); job_idx < r.end(); job_idx++) {
1847 size_t lidx = layers_to_generate_infill[job_idx];
1848 infill_lines.at(
1849 lidx) = po->get_layer(lidx)->generate_sparse_infill_polylines_for_anchoring(po->m_adaptive_fill_octrees.first.get(),
1850 po->m_adaptive_fill_octrees.second.get(),
1851 po->m_lightning_generator.get());
1852 }
1853 });
1854#ifdef DEBUG_BRIDGE_OVER_INFILL
1855 for (const auto &il : infill_lines) {
1857 }
1858#endif
1859 }
1860
1861
1862 std::vector<std::vector<size_t>> clustered_layers_for_threads;
1863 float target_flow_height_factor = 0.9f;
1864 {
1865 std::vector<size_t> layers_with_candidates;
1866 std::map<size_t, Polygons> layer_area_covered_by_candidates;
1867 for (const auto& pair : surfaces_by_layer) {
1868 layers_with_candidates.push_back(pair.first);
1869 layer_area_covered_by_candidates[pair.first] = {};
1870 }
1871
1872
1873
1874 tbb::parallel_for(tbb::blocked_range<size_t>(0, layers_with_candidates.size()), [&layers_with_candidates, &surfaces_by_layer,
1875 &layer_area_covered_by_candidates](
1876 tbb::blocked_range<size_t> r) {
1877 PRINT_OBJECT_TIME_LIMIT_MILLIS(PRINT_OBJECT_TIME_LIMIT_DEFAULT);
1878 for (size_t job_idx = r.begin(); job_idx < r.end(); job_idx++) {
1879 size_t lidx = layers_with_candidates[job_idx];
1880 for (const auto &candidate : surfaces_by_layer.at(lidx)) {
1881 Polygon candiate_inflated_aabb = get_extents(candidate.new_polys).inflated(scale_(7)).polygon();
1882 layer_area_covered_by_candidates.at(lidx) = union_(layer_area_covered_by_candidates.at(lidx),
1883 Polygons{candiate_inflated_aabb});
1884 }
1885 }
1886 });
1887
1888
1889 for (auto pair : surfaces_by_layer) {
1890 if (clustered_layers_for_threads.empty() ||
1891 this->get_layer(clustered_layers_for_threads.back().back())->print_z <
1892 this->get_layer(pair.first)->print_z -
1893 this->get_layer(pair.first)->regions()[0]->bridging_flow(
frSolidInfill,
true).height() * target_flow_height_factor -
1895 intersection(layer_area_covered_by_candidates[clustered_layers_for_threads.back().back()],
1896 layer_area_covered_by_candidates[pair.first])
1897 .empty()) {
1898 clustered_layers_for_threads.push_back({pair.first});
1899 } else {
1900 clustered_layers_for_threads.back().push_back(pair.first);
1901 }
1902 }
1903
1904#ifdef DEBUG_BRIDGE_OVER_INFILL
1905 std::cout << "BRIDGE OVER INFILL CLUSTERED LAYERS FOR SINGLE THREAD" << std::endl;
1906 for (auto cluster : clustered_layers_for_threads) {
1907 std::cout << "CLUSTER: ";
1909 std::cout << l << " ";
1910 }
1911 std::cout << std::endl;
1912 }
1913#endif
1914 }
1915
1916
1917 auto gather_areas_w_depth = [target_flow_height_factor](
const PrintObject *po,
int lidx,
float target_flow_height) {
1918
1921 double bottom_z = po->get_layer(lidx)->print_z - target_flow_height * target_flow_height_factor -
EPSILON;
1922 for (int i = int(lidx) - 1; i >= 0; --i) {
1923
1924 const Layer *layer = po->get_layer(i);
1925 if (layer->print_z < bottom_z && i < int(lidx) - 1)
1926 break;
1927
1928 for (const LayerRegion *region : layer->regions()) {
1929 bool has_low_density = region->region().config().fill_density.value < 100;
1930 for (const Surface &surface : region->fill_surfaces()) {
1932 layers_sparse_infill.push_back(surface.expolygon);
1933 } else {
1934 not_sparse_infill.push_back(surface.expolygon);
1935 }
1936 }
1937 }
1938 }
1939 layers_sparse_infill =
union_ex(layers_sparse_infill);
1941 not_sparse_infill =
union_ex(not_sparse_infill);
1943 return diff(layers_sparse_infill, not_sparse_infill);
1944 };
1945
1946
1948 AABBTreeLines::LinesDistancer<Line> lines_tree(anchors);
1949
1950 std::map<double, int> counted_directions;
1951 for (const Polygon &p : bridged_area) {
1952 double acc_distance = 0;
1953 for (int point_idx = 0; point_idx < int(p.points.size()) - 1; ++point_idx) {
1954 Vec2d start = p.points[point_idx].cast<
double>();
1955 Vec2d next = p.points[point_idx + 1].cast<
double>();
1956 Vec2d v = next - start;
1957 double dist_to_next = v.norm();
1958 acc_distance += dist_to_next;
1959 if (acc_distance >
scaled(2.0)) {
1960 acc_distance = 0.0;
1961 v.normalize();
1962 int lines_count = int(std::ceil(dist_to_next /
scaled(2.0)));
1963 float step_size = dist_to_next / lines_count;
1964 for (int i = 0; i < lines_count; ++i) {
1966 auto [
distance, index, p] = lines_tree.distance_from_lines_extra<
false>(
a);
1967 double angle = lines_tree.get_line(index).orientation();
1970 }
1972 counted_directions[
angle]++;
1973 }
1974 }
1975 }
1976 }
1977
1978 std::pair<double, int> best_dir{0, 0};
1979
1980 for (const auto &dir : counted_directions) {
1981 int score_acc = 0;
1982 double dir_acc = 0;
1983 double window_start_angle = dir.first -
PI * 0.1;
1984 double window_end_angle = dir.first +
PI * 0.1;
1985 for (auto dirs_window = counted_directions.lower_bound(window_start_angle);
1986 dirs_window != counted_directions.upper_bound(window_end_angle); dirs_window++) {
1987 dir_acc += dirs_window->first * dirs_window->second;
1988 score_acc += dirs_window->second;
1989 }
1990
1991
1992 if (window_start_angle < 0.5 *
PI) {
1993 for (
auto dirs_window = counted_directions.lower_bound(1.5 *
PI - (0.5 *
PI - window_start_angle));
1994 dirs_window != counted_directions.end(); dirs_window++) {
1995 dir_acc += dirs_window->first * dirs_window->second;
1996 score_acc += dirs_window->second;
1997 }
1998 }
1999 if (window_start_angle > 1.5 *
PI) {
2000 for (auto dirs_window = counted_directions.begin();
2001 dirs_window != counted_directions.upper_bound(window_start_angle - 1.5 *
PI); dirs_window++) {
2002 dir_acc += dirs_window->first * dirs_window->second;
2003 score_acc += dirs_window->second;
2004 }
2005 }
2006
2007 if (score_acc > best_dir.second) {
2008 best_dir = {dir_acc / score_acc, score_acc};
2009 }
2010 }
2011 double bridging_angle = best_dir.first;
2012 if (bridging_angle == 0) {
2013 bridging_angle = 0.001;
2014 }
2015 switch (dominant_pattern) {
2018 default: break;
2019 }
2020
2021 return bridging_angle;
2022 };
2023
2024
2025
2026 auto construct_anchored_polygon = [](
Polygons bridged_area,
Lines anchors,
const Flow &bridging_flow,
double bridging_angle) {
2027 auto lines_rotate = [](
Lines &lines,
double cos_angle,
double sin_angle) {
2028 for (Line &l : lines) {
2029 double ax = double(l.a.x());
2030 double ay = double(l.a.y());
2031 l.a.x() =
coord_t(
round(cos_angle * ax - sin_angle * ay));
2032 l.a.y() =
coord_t(
round(cos_angle * ay + sin_angle * ax));
2033 double bx = double(l.b.x());
2034 double by = double(l.b.y());
2035 l.b.x() =
coord_t(
round(cos_angle * bx - sin_angle * by));
2036 l.b.y() =
coord_t(
round(cos_angle * by + sin_angle * bx));
2037 }
2038 };
2039
2041 return (alow >= blow && alow <= bhigh) || (ahigh >= blow && ahigh <= bhigh) || (blow >= alow && blow <= ahigh) ||
2042 (bhigh >= alow && bhigh <= ahigh);
2043 };
2044
2046 double aligning_angle = -bridging_angle +
PI * 0.5;
2047 {
2049 lines_rotate(anchors,
cos(aligning_angle),
sin(aligning_angle));
2052
2053 const size_t n_vlines = (bb_x.max.x() - bb_x.min.x() + bridging_flow.scaled_spacing() - 1) / bridging_flow.scaled_spacing();
2054 std::vector<Line> vertical_lines(n_vlines);
2055 for (size_t i = 0; i < n_vlines; i++) {
2056 coord_t x = bb_x.min.x() + i * bridging_flow.scaled_spacing();
2057 coord_t y_min = bb_y.min.y() - bridging_flow.scaled_spacing();
2058 coord_t y_max = bb_y.max.y() + bridging_flow.scaled_spacing();
2059 vertical_lines[i].a =
Point{
x, y_min};
2060 vertical_lines[i].b =
Point{
x, y_max};
2061 }
2062
2063 auto anchors_and_walls_tree = AABBTreeLines::LinesDistancer<Line>{std::move(anchors)};
2064 auto bridged_area_tree = AABBTreeLines::LinesDistancer<Line>{
to_lines(bridged_area)};
2065
2066 std::vector<std::vector<Line>> polygon_sections(n_vlines);
2067 for (size_t i = 0; i < n_vlines; i++) {
2068 auto area_intersections = bridged_area_tree.intersections_with_line<true>(vertical_lines[i]);
2069 for (int intersection_idx = 0; intersection_idx < int(area_intersections.size()) - 1; intersection_idx++) {
2070 if (bridged_area_tree.outside(
2071 (area_intersections[intersection_idx].first + area_intersections[intersection_idx + 1].first) / 2) < 0) {
2072 polygon_sections[i].emplace_back(area_intersections[intersection_idx].first,
2073 area_intersections[intersection_idx + 1].first);
2074 }
2075 }
2076 auto anchors_intersections = anchors_and_walls_tree.intersections_with_line<true>(vertical_lines[i]);
2077
2078 for (Line §ion : polygon_sections[i]) {
2079 auto maybe_below_anchor = std::upper_bound(anchors_intersections.rbegin(), anchors_intersections.rend(), section.a,
2080 [](
const Point &a,
const std::pair<Point, size_t> &b) {
2081 return a.y() > b.first.y();
2082 });
2083 if (maybe_below_anchor != anchors_intersections.rend()) {
2084 section.a = maybe_below_anchor->first;
2085 section.a.y() -= bridging_flow.scaled_width() * (0.5 + 0.5);
2086 }
2087
2088 auto maybe_upper_anchor = std::upper_bound(anchors_intersections.begin(), anchors_intersections.end(), section.b,
2089 [](
const Point &a,
const std::pair<Point, size_t> &b) {
2090 return a.y() < b.first.y();
2091 });
2092 if (maybe_upper_anchor != anchors_intersections.end()) {
2093 section.b = maybe_upper_anchor->first;
2094 section.b.y() += bridging_flow.scaled_width() * (0.5 + 0.5);
2095 }
2096 }
2097
2098 for (
int section_idx = 0; section_idx < int(polygon_sections[i].
size()) - 1; section_idx++) {
2099 Line §ion_a = polygon_sections[i][section_idx];
2100 Line §ion_b = polygon_sections[i][section_idx + 1];
2101 if (segments_overlap(section_a.a.y(), section_a.b.y(), section_b.a.y(), section_b.b.y())) {
2102 section_b.a = section_a.a.y() < section_b.a.y() ? section_a.a : section_b.a;
2103 section_b.b = section_a.b.y() < section_b.b.y() ? section_b.b : section_a.b;
2104 section_a.a = section_a.b;
2105 }
2106 }
2107
2108 polygon_sections[i].erase(std::remove_if(polygon_sections[i].
begin(), polygon_sections[i].
end(),
2109 [](const Line &s) { return s.a == s.b; }),
2110 polygon_sections[i].
end());
2111 std::sort(polygon_sections[i].
begin(), polygon_sections[i].
end(),
2112 [](
const Line &a,
const Line &b) {
return a.a.y() <
b.b.y(); });
2113 }
2114
2115
2116 struct TracedPoly
2117 {
2120 };
2121
2122 std::vector<TracedPoly> current_traced_polys;
2123 for (const auto &polygon_slice : polygon_sections) {
2124 std::unordered_set<const Line *> used_segments;
2125 for (TracedPoly &traced_poly : current_traced_polys) {
2126 auto candidates_begin = std::upper_bound(polygon_slice.begin(), polygon_slice.end(), traced_poly.lows.back(),
2127 [](
const Point &low,
const Line &seg) { return seg.b.y() > low.y(); });
2128 auto candidates_end = std::upper_bound(polygon_slice.begin(), polygon_slice.end(), traced_poly.highs.back(),
2129 [](
const Point &high,
const Line &seg) { return seg.a.y() > high.y(); });
2130
2131 bool segment_added = false;
2132 for (auto candidate = candidates_begin; candidate != candidates_end && !segment_added; candidate++) {
2133 if (used_segments.find(&(*candidate)) != used_segments.end()) {
2134 continue;
2135 }
2136
2137 if ((traced_poly.lows.back() - candidate->a).cast<double>().squaredNorm() <
2138 36.0 * double(bridging_flow.scaled_spacing()) * bridging_flow.scaled_spacing()) {
2139 traced_poly.lows.push_back(candidate->a);
2140 } else {
2141 traced_poly.lows.push_back(traced_poly.lows.back() +
Point{bridging_flow.scaled_spacing() / 2, 0});
2142 traced_poly.lows.push_back(candidate->a -
Point{bridging_flow.scaled_spacing() / 2, 0});
2143 traced_poly.lows.push_back(candidate->a);
2144 }
2145
2146 if ((traced_poly.highs.back() - candidate->b).cast<double>().squaredNorm() <
2147 36.0 * double(bridging_flow.scaled_spacing()) * bridging_flow.scaled_spacing()) {
2148 traced_poly.highs.push_back(candidate->b);
2149 } else {
2150 traced_poly.highs.push_back(traced_poly.highs.back() +
Point{bridging_flow.scaled_spacing() / 2, 0});
2151 traced_poly.highs.push_back(candidate->b -
Point{bridging_flow.scaled_spacing() / 2, 0});
2152 traced_poly.highs.push_back(candidate->b);
2153 }
2154 segment_added = true;
2155 used_segments.insert(&(*candidate));
2156 }
2157
2158 if (!segment_added) {
2159
2160 traced_poly.lows.push_back(traced_poly.lows.back() +
Point{bridging_flow.scaled_spacing() / 2, 0});
2161 traced_poly.highs.push_back(traced_poly.highs.back() +
Point{bridging_flow.scaled_spacing() / 2, 0});
2162 Polygon &new_poly = expanded_bridged_area.emplace_back(std::move(traced_poly.lows));
2163 new_poly.
points.insert(new_poly.points.end(), traced_poly.highs.rbegin(), traced_poly.highs.rend());
2164 traced_poly.lows.clear();
2165 traced_poly.highs.clear();
2166 }
2167 }
2168
2169 current_traced_polys.erase(std::remove_if(current_traced_polys.begin(), current_traced_polys.end(),
2170 [](const TracedPoly &tp) { return tp.lows.empty(); }),
2171 current_traced_polys.end());
2172
2173 for (
const auto &
segment : polygon_slice) {
2174 if (used_segments.find(&
segment) == used_segments.end()) {
2175 TracedPoly &new_tp = current_traced_polys.emplace_back();
2176 new_tp.lows.push_back(
segment.a -
Point{bridging_flow.scaled_spacing() / 2, 0});
2177 new_tp.lows.push_back(
segment.a);
2178 new_tp.highs.push_back(
segment.b -
Point{bridging_flow.scaled_spacing() / 2, 0});
2179 new_tp.highs.push_back(
segment.b);
2180 }
2181 }
2182 }
2183
2184
2185 for (TracedPoly &traced_poly : current_traced_polys) {
2186 Polygon &new_poly = expanded_bridged_area.emplace_back(std::move(traced_poly.lows));
2187 new_poly.
points.insert(new_poly.points.end(), traced_poly.highs.rbegin(), traced_poly.highs.rend());
2188 }
2190 }
2191
2193 return expanded_bridged_area;
2194 };
2195
2196 tbb::parallel_for(tbb::blocked_range<size_t>(0, clustered_layers_for_threads.size()), [po =
static_cast<const PrintObject *
>(
this),
2197 target_flow_height_factor, &surfaces_by_layer,
2198 &clustered_layers_for_threads,
2199 gather_areas_w_depth, &infill_lines,
2200 determine_bridging_angle,
2201 construct_anchored_polygon](
2202 tbb::blocked_range<size_t> r) {
2203 PRINT_OBJECT_TIME_LIMIT_MILLIS(PRINT_OBJECT_TIME_LIMIT_DEFAULT);
2204 for (size_t cluster_idx = r.begin(); cluster_idx < r.end(); cluster_idx++) {
2205 for (size_t job_idx = 0; job_idx < clustered_layers_for_threads[cluster_idx].size(); job_idx++) {
2206 size_t lidx = clustered_layers_for_threads[cluster_idx][job_idx];
2207 const Layer *layer = po->get_layer(lidx);
2208
2209
2210
2211
2212
2213 std::sort(surfaces_by_layer[lidx].begin(), surfaces_by_layer[lidx].end(),
2214 [](const CandidateSurface &left, const CandidateSurface &right) {
2215 auto a = get_extents(left.new_polys);
2216 auto b = get_extents(right.new_polys);
2217
2218 if (a.min.x() == b.min.x()) {
2219 return a.min.y() < b.min.y();
2220 };
2221 return a.min.x() < b.min.x();
2222 });
2223 if (surfaces_by_layer[lidx].size() > 2) {
2224 Vec2d origin = get_extents(surfaces_by_layer[lidx].front().new_polys).max.cast<double>();
2225 std::stable_sort(surfaces_by_layer[lidx].begin() + 1, surfaces_by_layer[lidx].end(),
2226 [origin](const CandidateSurface &left, const CandidateSurface &right) {
2227 auto a = get_extents(left.new_polys);
2228 auto b = get_extents(right.new_polys);
2229
2230 return (origin - a.min.cast<double>()).squaredNorm() <
2231 (origin - b.min.cast<double>()).squaredNorm();
2232 });
2233 }
2234
2235
2236 coordf_t spacing = surfaces_by_layer[lidx].front().region->bridging_flow(frSolidInfill, true).scaled_spacing();
2237 coordf_t target_flow_height = surfaces_by_layer[lidx].front().region->bridging_flow(frSolidInfill, true).height() *
2238 target_flow_height_factor;
2239 Polygons deep_infill_area = gather_areas_w_depth(po, lidx, target_flow_height);
2240
2241 {
2242
2243
2244 Polygons filled_polyons_on_lower_layers;
2245 double bottom_z = layer->print_z - target_flow_height - EPSILON;
2246 if (job_idx > 0) {
2247 for (int lower_job_idx = job_idx - 1; lower_job_idx >= 0; lower_job_idx--) {
2248 size_t lower_layer_idx = clustered_layers_for_threads[cluster_idx][lower_job_idx];
2249 const Layer *lower_layer = po->get_layer(lower_layer_idx);
2250 if (lower_layer->print_z >= bottom_z) {
2251 for (const auto &c : surfaces_by_layer[lower_layer_idx]) {
2252 filled_polyons_on_lower_layers.insert(filled_polyons_on_lower_layers.end(), c.new_polys.begin(),
2253 c.new_polys.end());
2254 }
2255 } else {
2256 break;
2257 }
2258 }
2259 }
2260 deep_infill_area = diff(deep_infill_area, filled_polyons_on_lower_layers);
2261 }
2262
2263 deep_infill_area = expand(deep_infill_area, spacing * 1.5);
2264
2265
2266 Polygons lightning_area;
2267 Polygons expansion_area;
2268 Polygons total_fill_area;
2269 for (const LayerRegion *region : layer->regions()) {
2270 Polygons internal_polys = to_polygons(region->fill_surfaces().filter_by_types({stInternal, stInternalSolid}));
2271 expansion_area.insert(expansion_area.end(), internal_polys.begin(), internal_polys.end());
2272 Polygons fill_polys = to_polygons(region->fill_expolygons());
2273 total_fill_area.insert(total_fill_area.end(), fill_polys.begin(), fill_polys.end());
2274 if (region->region().config().fill_pattern == ipLightning) {
2275 Polygons l = to_polygons(region->fill_surfaces().filter_by_type(stInternal));
2276 lightning_area.insert(lightning_area.end(), l.begin(), l.end());
2277 }
2278 }
2279 total_fill_area = closing(total_fill_area, float(SCALED_EPSILON));
2280 expansion_area = closing(expansion_area, float(SCALED_EPSILON));
2281 expansion_area = intersection(expansion_area, deep_infill_area);
2282 Polylines anchors = intersection_pl(infill_lines[lidx - 1], shrink(expansion_area, spacing));
2283 Polygons internal_unsupported_area = shrink(deep_infill_area, spacing * 4.5);
2284
2285#ifdef DEBUG_BRIDGE_OVER_INFILL
2286 debug_draw(std::to_string(lidx) + "_" + std::to_string(cluster_idx) + "_" + std::to_string(job_idx) + "_" + "_total_area",
2287 to_lines(total_fill_area), to_lines(expansion_area), to_lines(deep_infill_area), to_lines(anchors));
2288#endif
2289
2290 std::vector<CandidateSurface> expanded_surfaces;
2291 expanded_surfaces.reserve(surfaces_by_layer[lidx].size());
2292 for (const CandidateSurface &candidate : surfaces_by_layer[lidx]) {
2293 const Flow &flow = candidate.region->bridging_flow(frSolidInfill, true);
2294 Polygons area_to_be_bridge = expand(candidate.new_polys, flow.scaled_spacing());
2295 area_to_be_bridge = intersection(area_to_be_bridge, deep_infill_area);
2296
2297 area_to_be_bridge.erase(std::remove_if(area_to_be_bridge.begin(), area_to_be_bridge.end(),
2298 [internal_unsupported_area](const Polygon &p) {
2299 return intersection({p}, internal_unsupported_area).empty();
2300 }),
2301 area_to_be_bridge.end());
2302
2303 Polygons limiting_area = union_(area_to_be_bridge, expansion_area);
2304
2305 if (area_to_be_bridge.empty())
2306 continue;
2307
2308 Polylines boundary_plines = to_polylines(expand(total_fill_area, 1.3 * flow.scaled_spacing()));
2309 {
2310 Polylines limiting_plines = to_polylines(expand(limiting_area, 0.3*flow.spacing()));
2311 boundary_plines.insert(boundary_plines.end(), limiting_plines.begin(), limiting_plines.end());
2312 }
2313
2314#ifdef DEBUG_BRIDGE_OVER_INFILL
2315 int r = rand();
2316 debug_draw(std::to_string(lidx) + "_" + std::to_string(cluster_idx) + "_" + std::to_string(job_idx) + "_" +
2317 "_anchors_" + std::to_string(r),
2318 to_lines(area_to_be_bridge), to_lines(boundary_plines), to_lines(anchors), to_lines(expansion_area));
2319#endif
2320
2321 double bridging_angle = 0;
2322 if (!anchors.empty()) {
2323 bridging_angle = determine_bridging_angle(area_to_be_bridge, to_lines(anchors),
2324 candidate.region->region().config().fill_pattern.value);
2325 } else {
2326
2327
2328 bridging_angle = determine_bridging_angle(area_to_be_bridge, to_lines(boundary_plines), InfillPattern::ipLine);
2329 }
2330
2331 boundary_plines.insert(boundary_plines.end(), anchors.begin(), anchors.end());
2332 if (!lightning_area.empty() && !intersection(area_to_be_bridge, lightning_area).empty()) {
2333 boundary_plines = intersection_pl(boundary_plines, expand(area_to_be_bridge, scale_(10)));
2334 }
2335 Polygons bridging_area = construct_anchored_polygon(area_to_be_bridge, to_lines(boundary_plines), flow, bridging_angle);
2336
2337
2338 {
2339 bool reconstruct = false;
2340 Polygons tmp_expanded_area = expand(bridging_area, 3.0 * flow.scaled_spacing());
2341 for (const CandidateSurface &s : expanded_surfaces) {
2342 if (!intersection(s.new_polys, tmp_expanded_area).empty()) {
2343 bridging_angle = s.bridge_angle;
2344 reconstruct = true;
2345 break;
2346 }
2347 }
2348 if (reconstruct) {
2349 bridging_area = construct_anchored_polygon(area_to_be_bridge, to_lines(boundary_plines), flow, bridging_angle);
2350 }
2351 }
2352
2353 bridging_area = opening(bridging_area, flow.scaled_spacing());
2354 bridging_area = closing(bridging_area, flow.scaled_spacing());
2355 bridging_area = intersection(bridging_area, limiting_area);
2356 bridging_area = intersection(bridging_area, total_fill_area);
2357 expansion_area = diff(expansion_area, bridging_area);
2358
2359#ifdef DEBUG_BRIDGE_OVER_INFILL
2360 debug_draw(std::to_string(lidx) + "_" + std::to_string(cluster_idx) + "_" + std::to_string(job_idx) + "_" + "_expanded_bridging" + std::to_string(r),
2361 to_lines(layer->lslices), to_lines(boundary_plines), to_lines(candidate.new_polys), to_lines(bridging_area));
2362#endif
2363
2364 expanded_surfaces.push_back(CandidateSurface(candidate.original_surface, candidate.layer_index, bridging_area,
2365 candidate.region, bridging_angle));
2366 }
2367 surfaces_by_layer[lidx].swap(expanded_surfaces);
2368 expanded_surfaces.clear();
2369 }
2370 }
2371 });
2372
2373 BOOST_LOG_TRIVIAL(info) <<
"Bridge over infill - Directions and expanded surfaces computed" <<
log_memory_info();
2374
2375 tbb::parallel_for(tbb::blocked_range<size_t>(0, this->
layers().
size()), [po =
this, &surfaces_by_layer](tbb::blocked_range<size_t> r) {
2377 for (size_t lidx = r.begin(); lidx < r.end(); lidx++) {
2378 if (surfaces_by_layer.find(lidx) == surfaces_by_layer.end() && surfaces_by_layer.find(lidx + 1) == surfaces_by_layer.end())
2379 continue;
2380 Layer *layer = po->get_layer(lidx);
2381
2383 if (surfaces_by_layer.find(lidx) != surfaces_by_layer.end()) {
2384 for (const auto &surface : surfaces_by_layer.at(lidx)) {
2385 cut_from_infill.insert(cut_from_infill.end(), surface.new_polys.begin(), surface.new_polys.end());
2386 }
2387 }
2388
2389 Polygons additional_ensuring_areas{};
2390 if (surfaces_by_layer.find(lidx + 1) != surfaces_by_layer.end()) {
2391 for (const auto &surface : surfaces_by_layer.at(lidx + 1)) {
2392 auto additional_area =
diff(surface.new_polys,
2394 additional_ensuring_areas.insert(additional_ensuring_areas.end(), additional_area.begin(), additional_area.end());
2395 }
2396 }
2397
2398 for (LayerRegion *region : layer->regions()) {
2400
2402 near_perimeters =
diff(near_perimeters,
shrink(near_perimeters, region->flow(
frSolidInfill).scaled_spacing()));
2404
2407 new_internal_infills =
diff_ex(new_internal_infills, additional_ensuring);
2408 for (const ExPolygon &ep : new_internal_infills) {
2410 }
2411
2413 if (surfaces_by_layer.find(lidx) != surfaces_by_layer.end()) {
2414 for (const CandidateSurface &cs : surfaces_by_layer.at(lidx)) {
2415 for (const Surface *surface : internal_solids) {
2416 if (cs.original_surface == surface) {
2417 Surface tmp{*surface, {}};
2419 tmp.bridge_angle = cs.bridge_angle;
2420 for (
const ExPolygon &ep :
union_ex(cs.new_polys)) {
2421 new_surfaces.emplace_back(tmp, ep);
2422 }
2423 break;
2424 }
2425 }
2426 }
2427 }
2429 new_internal_solids.insert(new_internal_solids.end(), additional_ensuring.begin(), additional_ensuring.end());
2430 new_internal_solids =
diff_ex(new_internal_solids, cut_from_infill);
2432 for (const ExPolygon &ep : new_internal_solids) {
2434 }
2435
2436#ifdef DEBUG_BRIDGE_OVER_INFILL
2437 debug_draw(
"Aensuring_" + std::to_string(
reinterpret_cast<uint64_t>(®ion)),
to_polylines(additional_ensuring),
2440 debug_draw(
"Aensuring_" + std::to_string(
reinterpret_cast<uint64_t>(®ion)) +
"_new",
to_polylines(additional_ensuring),
2443#endif
2444
2446 region->m_fill_surfaces.append(new_surfaces);
2447 }
2448 }
2449 });
2450
2451 BOOST_LOG_TRIVIAL(info) <<
"Bridge over infill - End" <<
log_memory_info();
2452
2453}
EIGEN_DEVICE_FUNC const CosReturnType cos() const
Definition ArrayCwiseUnaryOps.h:202
EIGEN_DEVICE_FUNC const SinReturnType sin() const
Definition ArrayCwiseUnaryOps.h:220
EIGEN_DEVICE_FUNC const RoundReturnType round() const
Definition ArrayCwiseUnaryOps.h:374
EIGEN_DEVICE_FUNC SegmentReturnType segment(Index start, Index n)
This is the const version of segment(Index,Index).
Definition BlockMethods.h:888
#define PRINT_OBJECT_TIME_LIMIT_MILLIS(limit)
Definition PrintObject.cpp:73
ExPolygons lslices
Definition Layer.hpp:339
Points points
Definition MultiPoint.hpp:18
size_t num_printing_regions() const
Definition Print.hpp:312
auto layers() const
Definition Print.hpp:247
PrintObject(Print *print, ModelObject *model_object, const Transform3d &trafo, PrintInstances &&instances)
Definition PrintObject.cpp:97
const PrintRegion & printing_region(size_t idx) const
Definition Print.hpp:313
FillLightning::GeneratorPtr m_lightning_generator
Definition Print.hpp:418
std::pair< FillAdaptive::OctreePtr, FillAdaptive::OctreePtr > m_adaptive_fill_octrees
Definition Print.hpp:417
const Vec3crd & size() const
Definition Print.hpp:245
size_t layer_count() const
Definition Print.hpp:278
const Layer * get_layer(int idx) const
Definition Print.hpp:280
FillLightning::GeneratorPtr prepare_lightning_infill_data()
Definition PrintObject.cpp:574
std::pair< FillAdaptive::OctreePtr, FillAdaptive::OctreePtr > prepare_adaptive_infill_data(const std::vector< std::pair< const Surface *, float > > &surfaces_w_bottom_z) const
Definition PrintObject.cpp:536
const PrintRegionConfig & config() const
Definition Print.hpp:87
static constexpr double PI
Definition libslic3r.h:58
#define SCALED_EPSILON
Definition libslic3r.h:71
#define scale_(val)
Definition libslic3r.h:69
ClusteredPoints cluster(Index3D &sindex, unsigned max_points, std::function< std::vector< PointIndexEl >(const Index3D &, const PointIndexEl &)> qfn)
Definition Clustering.cpp:19
std::vector< Polygon, PointsAllocator< Polygon > > Polygons
Definition Polygon.hpp:15
InfillPattern
Definition PrintConfig.hpp:60
@ ipHilbertCurve
Definition PrintConfig.hpp:62
@ ipOctagramSpiral
Definition PrintConfig.hpp:62
@ ipLightning
Definition PrintConfig.hpp:63
std::vector< Line > Lines
Definition Line.hpp:17
BoundingBox scaled(const BoundingBoxf &bb)
Definition BoundingBox.hpp:240
std::vector< const Surface * > SurfacesPtr
Definition Surface.hpp:98
Polylines to_polylines(const ExPolygon &src)
Definition ExPolygon.hpp:209
bridge_angle((ConfigOptionInt, bottom_solid_layers))((ConfigOptionFloat
Slic3r::ExPolygons diff_ex(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset)
Definition ClipperUtils.cpp:726
Slic3r::Polygons expand(const Slic3r::Polygon &polygon, const float delta, ClipperLib::JoinType joinType=DefaultJoinType, double miterLimit=DefaultMiterLimit)
Definition ClipperUtils.hpp:363
Slic3r::ExPolygons union_ex(const Slic3r::Polygons &subject, ClipperLib::PolyFillType fill_type)
Definition ClipperUtils.cpp:774
Eigen::Matrix< double, 2, 1, Eigen::DontAlign > Vec2d
Definition Point.hpp:51
@ frSolidInfill
Definition Flow.hpp:20
std::vector< ExPolygon > ExPolygons
Definition ExPolygon.hpp:13
Slic3r::Polygons shrink(const Slic3r::Polygons &polygons, const float delta, ClipperLib::JoinType joinType=DefaultJoinType, double miterLimit=DefaultMiterLimit)
Definition ClipperUtils.hpp:372
Slic3r::Polygons intersection(const Slic3r::Polygon &subject, const Slic3r::Polygon &clip, ApplySafetyOffset do_safety_offset)
Definition ClipperUtils.cpp:686
double area(const ExPolygon &poly)
Definition ExPolygon.hpp:467
Lines to_lines(const ExPolygon &src)
Definition ExPolygon.hpp:117
ExPolygons to_expolygons(const Polygons &polys)
Definition ExPolygon.hpp:347
Slic3r::ExPolygons closing_ex(const Slic3r::Polygons &polygons, const float delta1, const float delta2, ClipperLib::JoinType joinType, double miterLimit)
Definition ClipperUtils.cpp:593
BoundingBox get_extents(const ExPolygon &expolygon)
Definition ExPolygon.cpp:352
double angle(const Eigen::MatrixBase< Derived > &v1, const Eigen::MatrixBase< Derived2 > &v2)
Definition Point.hpp:112
std::string log_memory_info(bool ignore_loglevel)
Definition utils.cpp:1073
Slic3r::Polygons closing(const Slic3r::Polygons &polygons, const float delta1, const float delta2, ClipperLib::JoinType joinType, double miterLimit)
Definition ClipperUtils.cpp:587
Polygons to_polygons(const ExPolygon &src)
Definition ExPolygon.hpp:281
std::vector< Surface > Surfaces
Definition Surface.hpp:97
Slic3r::ExPolygons intersection_ex(const Slic3r::Polygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset)
Definition ClipperUtils.cpp:755
Slic3r::ExPolygons union_safety_offset_ex(const Slic3r::Polygons &polygons)
Definition ClipperUtils.hpp:354
Slic3r::Polygons union_safety_offset(const Slic3r::Polygons &polygons)
Definition ClipperUtils.hpp:352
@ stInternalSolid
Definition Surface.hpp:19
@ stInternal
Definition Surface.hpp:17
@ stInternalBridge
Definition Surface.hpp:21
@ stInternalVoid
Definition Surface.hpp:24
void polygons_rotate(Polygons &polys, double angle)
Definition Polygon.hpp:155
Slic3r::Polygons diff(const Slic3r::Polygon &subject, const Slic3r::Polygon &clip, ApplySafetyOffset do_safety_offset)
Definition ClipperUtils.cpp:672
std::vector< Point, PointsAllocator< Point > > Points
Definition Point.hpp:58
IGL_INLINE void find(const Eigen::SparseMatrix< T > &X, Eigen::DenseBase< DerivedI > &I, Eigen::DenseBase< DerivedJ > &J, Eigen::DenseBase< DerivedV > &V)
Definition find.cpp:18
TCoord< P > x(const P &p)
Definition geometry_traits.hpp:297
double distance(const P &p1, const P &p2)
Definition geometry_traits.hpp:329
S::iterator begin(S &sh, const PathTag &)
Definition geometry_traits.hpp:614
S::iterator end(S &sh, const PathTag &)
Definition geometry_traits.hpp:620
Slic3r::Polygon Polygon
Definition Emboss.cpp:34
unsigned __int64 uint64_t
Definition unistd.h:80
Inheritance diagram for Slic3r::PrintObject:
1.9.8