751{
752 assert(perimeter_and_gapfill_ranges.size() == fill_expolygons_ranges.size());
753 assert(! layer_region_ids.empty());
754
755 LayerRegion &this_layer_region = *
m_regions[region_id];
756
757
759 fill_expolygons_bboxes.reserve(fill_expolygons.size());
760 for (const ExPolygon &expolygon : fill_expolygons)
761 fill_expolygons_bboxes.emplace_back(
get_extents(expolygon));
762
763
764
765 std::vector<std::pair<uint32_t, Point>> perimeter_slices_queue;
766 perimeter_slices_queue.reserve(slices.size());
768 const std::pair<ExtrusionRange, ExtrusionRange> &extrusions = perimeter_and_gapfill_ranges[islice];
770 bool sample_set = false;
771
772 for (
uint32_t iexpoly : fill_expolygons_ranges[islice])
773 if (
const ExPolygon &expoly = fill_expolygons[iexpoly]; ! expoly.empty()) {
774 sample = expoly.contour.points[expoly.contour.points.size() / 2];
775 sample_set = true;
776 break;
777 }
778 if (! sample_set) {
779
780 for (
uint32_t iperimeter : extrusions.first) {
781 const ExtrusionEntity &ee = *this_layer_region.perimeters().entities[iperimeter];
782 if (ee.is_collection()) {
783 for (
const ExtrusionEntity *ee2 : dynamic_cast<
const ExtrusionEntityCollection&>(ee).entities)
784 if (! ee2->role().is_external()) {
785 sample = ee2->middle_point();
786 sample_set = true;
787 goto loop_end;
788 }
789 } else if (! ee.role().is_external()) {
790 sample = ee.middle_point();
791 sample_set = true;
792 break;
793 }
794 }
795 loop_end:
796 if (! sample_set) {
797 if (! extrusions.second.empty()) {
798
799 sample = this_layer_region.thin_fills().entities[*extrusions.second.begin()]->middle_point();
800 sample_set = true;
801 }
802 if (! sample_set && ! extrusions.first.empty()) {
803
804 sample = this_layer_region.perimeters().entities[*extrusions.first.begin()]->middle_point();
805 sample_set = true;
806 }
807 }
808 }
809
810
811 if (sample_set)
812 perimeter_slices_queue.emplace_back(islice, sample);
813 }
814
815
816
817 struct RegionWithFillIndex {
818 int region_id{ -1 };
819 int fill_in_region_id{ -1 };
820 };
821 std::vector<RegionWithFillIndex> map_expolygon_to_region_and_fill;
822 const bool has_multiple_regions = layer_region_ids.size() > 1;
823 assert(has_multiple_regions || layer_region_ids.size() == 1);
824
825 if (! fill_expolygons.empty()) {
826 if (has_multiple_regions) {
827
828 std::vector<uint32_t> fill_expolygons_bboxes_sorted(fill_expolygons_bboxes.size());
829 std::iota(fill_expolygons_bboxes_sorted.begin(), fill_expolygons_bboxes_sorted.end(), 0);
830 std::sort(fill_expolygons_bboxes_sorted.begin(), fill_expolygons_bboxes_sorted.end(), [&fill_expolygons_bboxes](
uint32_t lhs,
uint32_t rhs){
831 const BoundingBox &bbl = fill_expolygons_bboxes[lhs];
832 const BoundingBox &bbr = fill_expolygons_bboxes[rhs];
833 return bbl.min < bbr.min || (bbl.min == bbr.min && bbl.max < bbr.max);
834 });
835 map_expolygon_to_region_and_fill.assign(fill_expolygons.size(), {});
836 for (
uint32_t region_idx : layer_region_ids) {
838 l.m_fill_expolygons =
intersection_ex(l.slices().surfaces, fill_expolygons);
839 l.m_fill_expolygons_bboxes.reserve(l.fill_expolygons().size());
840 for (const ExPolygon &expolygon : l.fill_expolygons()) {
842 l.m_fill_expolygons_bboxes.emplace_back(bbox);
843 auto it_bbox = std::lower_bound(fill_expolygons_bboxes_sorted.begin(), fill_expolygons_bboxes_sorted.end(), bbox, [&fill_expolygons_bboxes](
uint32_t lhs,
const BoundingBox &bbr){
844 const BoundingBox &bbl = fill_expolygons_bboxes[lhs];
845 return bbl.min < bbr.min || (bbl.min == bbr.min && bbl.max < bbr.max);
846 });
847 if (it_bbox != fill_expolygons_bboxes_sorted.end())
848 if (
uint32_t fill_id = *it_bbox; fill_expolygons_bboxes[fill_id] == bbox) {
849
851 RegionWithFillIndex &ref = map_expolygon_to_region_and_fill[fill_id];
852
853 assert(ref.region_id == -1 && ref.fill_in_region_id == -1);
854 ref.region_id = region_idx;
855 ref.fill_in_region_id = int(&expolygon - l.fill_expolygons().data());
856 }
857 }
858 }
859 }
860
861
862
863 int sort_region_id = -1;
864
866
867 std::vector<int> new_positions;
868 do {
869 sort_region_id = -1;
870 for (size_t source_slice_idx = 0; source_slice_idx < fill_expolygons_ranges.size(); ++ source_slice_idx)
871 if (
ExPolygonRange fill_range = fill_expolygons_ranges[source_slice_idx]; fill_range.
size() > 1) {
872
873 uint32_t fill_idx = *fill_range.begin();
874 if (const int fill_regon_id = map_expolygon_to_region_and_fill[fill_idx].region_id; fill_regon_id != -1) {
875 int fill_in_region_id = map_expolygon_to_region_and_fill[fill_idx].fill_in_region_id;
876 bool needs_sorting = false;
877 for (++ fill_idx; fill_idx != *fill_range.end(); ++ fill_idx) {
878 if (const RegionWithFillIndex &ref = map_expolygon_to_region_and_fill[fill_idx]; ref.region_id != fill_regon_id) {
879
880 needs_sorting = false;
881 break;
882 } else if (ref.fill_in_region_id != ++ fill_in_region_id) {
883
884 needs_sorting = true;
885 }
886 }
887 if (needs_sorting) {
888 sort_region_id = fill_regon_id;
889 break;
890 }
891 }
892 }
893 if (sort_region_id != -1) {
894
895 LayerRegion &layerm = *
m_regions[sort_region_id];
896 new_positions.assign(layerm.fill_expolygons().size(), -1);
897 int last = 0;
898 for (RegionWithFillIndex &ref : map_expolygon_to_region_and_fill)
899 if (ref.region_id == sort_region_id) {
900 new_positions[ref.fill_in_region_id] = last;
901 ref.fill_in_region_id = last ++;
902 }
903 for (auto &new_pos : new_positions)
905
906 new_pos = last ++;
907
908 auto &fills = layerm.m_fill_expolygons;
909 assert(last == int(fills.size()));
910 fills_temp.reserve(fills.size());
911 fills_temp.insert(fills_temp.end(), std::make_move_iterator(fills.begin()), std::make_move_iterator(fills.end()));
912 for (ExPolygon &ex : fills)
913 ex.clear();
914
915 for (size_t old_pos = 0; old_pos < new_positions.size(); ++ old_pos)
916 fills[new_positions[old_pos]] = std::move(fills_temp[old_pos]);
917 }
918 } while (sort_region_id != -1);
919 } else {
920 this_layer_region.m_fill_expolygons = std::move(fill_expolygons);
921 this_layer_region.m_fill_expolygons_bboxes = std::move(fill_expolygons_bboxes);
922 }
923 }
924
925 auto insert_into_island = [
926
927 region_id,
928
929 has_multiple_regions,
930
931 &perimeter_and_gapfill_ranges,
932
933 &fill_expolygons, &fill_expolygons_bboxes, &fill_expolygons_ranges,
934
935 &map_expolygon_to_region_and_fill,
936
938 (int lslice_idx, int source_slice_idx) {
940 LayerIsland &island =
lslices_ex[lslice_idx].islands.back();
941 island.perimeters = LayerExtrusionRange(region_id, perimeter_and_gapfill_ranges[source_slice_idx].first);
942 island.thin_fills = perimeter_and_gapfill_ranges[source_slice_idx].second;
943 if (
ExPolygonRange fill_range = fill_expolygons_ranges[source_slice_idx]; ! fill_range.
empty()) {
944 if (has_multiple_regions) {
945
947 for (
uint32_t fill_idx : fill_range) {
948 if (const int fill_regon_id = map_expolygon_to_region_and_fill[fill_idx].region_id;
951 break;
952 } else
953 island.fill_region_id = fill_regon_id;
954 }
955 if (island.fill_expolygons_composite()) {
956
957 LayerRegion &this_layer_region = *
regions[region_id];
958 auto begin =
uint32_t(this_layer_region.fill_expolygons_composite().size());
959 this_layer_region.m_fill_expolygons_composite.reserve(this_layer_region.fill_expolygons_composite().size() + fill_range.size());
960 std::move(fill_expolygons.begin() + *fill_range.begin(), fill_expolygons.begin() + *fill_range.end(), std::back_inserter(this_layer_region.m_fill_expolygons_composite));
961 this_layer_region.m_fill_expolygons_composite_bboxes.insert(this_layer_region.m_fill_expolygons_composite_bboxes.end(),
962 fill_expolygons_bboxes.begin() + *fill_range.begin(), fill_expolygons_bboxes.begin() + *fill_range.end());
963 island.fill_expolygons =
ExPolygonRange(begin,
uint32_t(this_layer_region.fill_expolygons_composite().size()));
964 } else {
965
967 map_expolygon_to_region_and_fill[*fill_range.begin()].fill_in_region_id,
968 map_expolygon_to_region_and_fill[*fill_range.end() - 1].fill_in_region_id + 1);
969 }
970 } else {
971
972 island.fill_expolygons = fill_range;
973 island.fill_region_id = region_id;
974 }
975 }
976 };
977
978
979
980
982 const BoundingBox &bbox =
lslices_ex[lslice_idx].bbox;
983 return point.x() >= bbox.min.x() && point.x() < bbox.max.x() &&
984 point.y() >= bbox.min.y() && point.y() < bbox.max.y() &&
985
986
987
988
989 lslices[lslice_idx].contains(point);
990 };
991 for (
int lslice_idx =
int(
lslices_ex.size()) - 1; lslice_idx >= 0 && ! perimeter_slices_queue.empty(); -- lslice_idx)
992 for (auto it_source_slice = perimeter_slices_queue.begin(); it_source_slice != perimeter_slices_queue.end(); ++ it_source_slice)
993 if (point_inside_surface(lslice_idx, it_source_slice->second)) {
994 insert_into_island(lslice_idx, it_source_slice->first);
995 if (std::next(it_source_slice) != perimeter_slices_queue.end())
996
997 *it_source_slice = perimeter_slices_queue.back();
998 perimeter_slices_queue.pop_back();
999 break;
1000 }
1001 if (! perimeter_slices_queue.empty()) {
1002
1003
1004
1005
1008 const auto bbox_eps = scaled<coord_t>(
1009 EPSILON + print_config.gcode_resolution.value +
1010 (region_config.fuzzy_skin.value ==
FuzzySkinType::None ? 0. : region_config.fuzzy_skin_thickness.value
1011
1013 auto point_inside_surface_dist2 =
1015 (
const size_t lslice_idx,
const Point &point) {
1016 const BoundingBox &bbox =
lslices_ex[lslice_idx].bbox;
1017 return
1018 point.x() < bbox.min.x() - bbox_eps || point.x() > bbox.max.x() + bbox_eps ||
1019 point.y() < bbox.min.y() - bbox_eps || point.y() > bbox.max.y() + bbox_eps ?
1020 std::numeric_limits<double>::max() :
1021 (
lslices[lslice_idx].point_projection(point) - point).
cast<double>().squaredNorm();
1022 };
1023 for (auto it_source_slice = perimeter_slices_queue.begin(); it_source_slice != perimeter_slices_queue.end(); ++ it_source_slice) {
1024 double d2min = std::numeric_limits<double>::max();
1025 int lslice_idx_min = -1;
1026 for (
int lslice_idx =
int(
lslices_ex.size()) - 1; lslice_idx >= 0; -- lslice_idx)
1027 if (double d2 = point_inside_surface_dist2(lslice_idx, it_source_slice->second); d2 < d2min) {
1028 d2min = d2;
1029 lslice_idx_min = lslice_idx;
1030 }
1031 if (lslice_idx_min == -1) {
1032
1033
1034 for (
int lslice_idx =
int(
lslices_ex.size()) - 1; lslice_idx >= 0; -- lslice_idx)
1035 if (
double d2 = (
lslices[lslice_idx].point_projection(it_source_slice->second) - it_source_slice->second).cast<
double>().squaredNorm(); d2 < d2min) {
1036 d2min = d2;
1037 lslice_idx_min = lslice_idx;
1038 }
1039 }
1040 assert(lslice_idx_min != -1);
1041 insert_into_island(lslice_idx_min, it_source_slice->first);
1042 }
1043 }
1044}
EIGEN_DEVICE_FUNC CastXpr< NewType >::Type cast() const
Definition CommonCwiseUnaryOps.h:62
bool empty() const
Definition Layer.hpp:55
T size() const
Definition Layer.hpp:56
bool expolygons_match(const ExPolygon &l, const ExPolygon &r)
Definition ExPolygon.cpp:342
IndexRange< uint32_t > ExPolygonRange
Definition Layer.hpp:66
std::vector< BoundingBox > BoundingBoxes
Definition BoundingBox.hpp:202
static constexpr const uint32_t fill_region_composite_id
Definition Layer.hpp:240
Inheritance diagram for Slic3r::SupportLayer:
1.9.8