Collaboration diagram for Slic3r::SupportGridPattern:

Public Member Functions
	SupportGridPattern (const Polygons support_polygons, const Polygons trimming_polygons, const SupportGridParams &params)

Polygons	extract_support (const coord_t offset_in_grid, bool fill_holes)

Private Member Functions
	SupportGridPattern ()

SupportGridPattern &	operator= (const SupportGridPattern &rhs)

Static Private Member Functions
static std::vector< unsigned char >	dilate_trimming_region (const std::vector< unsigned char > &trimming, const Vec2i &grid_size)

static void	seed_fill_block (std::vector< unsigned char > &grid, Vec2i grid_size, const std::vector< unsigned char > &trimming, const Vec2i &grid_blocks, int oversampling)

static Points	island_samples (const ExPolygons &expolygons)

Private Attributes
SupportMaterialStyle	m_style

const Polygons *	m_support_polygons

const Polygons *	m_trimming_polygons

Polygons	m_support_polygons_rotated

Polygons	m_trimming_polygons_rotated

coordf_t	m_support_angle

coordf_t	m_support_spacing

coordf_t	m_extrusion_width

coordf_t	m_support_material_closing_radius

Vec2i	m_grid_size

double	m_pixel_size

BoundingBox	m_bbox

std::vector< unsigned char >	m_grid2

Detailed Description

Constructor & Destructor Documentation

◆ SupportGridPattern() [1/2]

Slic3r::SupportGridPattern::SupportGridPattern	(	const Polygons *	support_polygons,
		const Polygons *	trimming_polygons,
		const SupportGridParams &	params
	)

inline

                                         :
        m_style(params.style),
        m_support_polygons(support_polygons), m_trimming_polygons(trimming_polygons),
        m_support_spacing(params.grid_resolution), m_support_angle(params.support_angle),
        m_extrusion_width(params.extrusion_width),
        m_support_material_closing_radius(params.support_material_closing_radius)
    {
        switch (m_style) {
        case smsGrid:
        {
            // Prepare the grid data, it will be reused when extracting support structures.
            if (m_support_angle != 0.) {
                // Create a copy of the rotated contours.
                m_support_polygons_rotated  = *support_polygons;
                m_trimming_polygons_rotated = *trimming_polygons;
                m_support_polygons  = &m_support_polygons_rotated;
                m_trimming_polygons = &m_trimming_polygons_rotated;
                polygons_rotate(m_support_polygons_rotated, - params.support_angle);
                polygons_rotate(m_trimming_polygons_rotated, - params.support_angle);
            }
 
            // Resolution of the sparse support grid.
            coord_t grid_resolution = coord_t(scale_(m_support_spacing));
            BoundingBox bbox = get_extents(*m_support_polygons);
            bbox.offset(20);
            // Align the bounding box with the sparse support grid.
            bbox.align_to_grid(grid_resolution);
 
    #ifdef SUPPORT_USE_AGG_RASTERIZER
            m_bbox       = bbox;
            // Oversample the grid to avoid leaking of supports through or around the object walls.
            int extrusion_width_scaled = scale_(params.extrusion_width);
            int oversampling = std::clamp(int(scale_(m_support_spacing) / (extrusion_width_scaled + 100)), 1, 8);
            m_pixel_size = std::max<double>(extrusion_width_scaled + 21, scale_(m_support_spacing / oversampling));
            // Add one empty column / row boundaries.
            m_bbox.offset(m_pixel_size);
            // Grid size fitting the support polygons plus one pixel boundary around the polygons.
            Vec2i grid_size_raw(int(ceil((m_bbox.max.x() - m_bbox.min.x()) / m_pixel_size)),
                                int(ceil((m_bbox.max.y() - m_bbox.min.y()) / m_pixel_size)));
            // Overlay macro blocks of (oversampling x oversampling) over the grid.
            Vec2i grid_blocks((grid_size_raw.x() + oversampling - 1 - 2) / oversampling, 
                              (grid_size_raw.y() + oversampling - 1 - 2) / oversampling);
            // and resize the grid to fit the macro blocks + one pixel boundary.
            m_grid_size = grid_blocks * oversampling + Vec2i(2, 2);
            assert(m_grid_size.x() >= grid_size_raw.x());
            assert(m_grid_size.y() >= grid_size_raw.y());
            m_grid2 = rasterize_polygons(m_grid_size, m_pixel_size, m_bbox.min, *m_support_polygons);
 
            seed_fill_block(m_grid2, m_grid_size,
                dilate_trimming_region(rasterize_polygons(m_grid_size, m_pixel_size, m_bbox.min, *m_trimming_polygons), m_grid_size),
                grid_blocks, oversampling);
 
    #ifdef SLIC3R_DEBUG
            {
                static int irun;
                Slic3r::png::write_gray_to_file_scaled(debug_out_path("support-rasterizer-%d.png", irun++), m_grid_size.x(), m_grid_size.y(), m_grid2.data(), 4);
            }
    #endif // SLIC3R_DEBUG
 
    #else // SUPPORT_USE_AGG_RASTERIZER
            // Create an EdgeGrid, initialize it with projection, initialize signed distance field.
            m_grid.set_bbox(bbox);
            m_grid.create(*m_support_polygons, grid_resolution);
    #if 0
            if (m_grid.has_intersecting_edges()) {
                // EdgeGrid fails to produce valid signed distance function for self-intersecting polygons.
                m_support_polygons_rotated = simplify_polygons(*m_support_polygons);
                m_support_polygons = &m_support_polygons_rotated;
                m_grid.set_bbox(bbox);
                m_grid.create(*m_support_polygons, grid_resolution);
    //            assert(! m_grid.has_intersecting_edges());
                printf("SupportGridPattern: fixing polygons with intersection %s\n",
                    m_grid.has_intersecting_edges() ? "FAILED" : "SUCCEEDED");
            }
    #endif
            m_grid.calculate_sdf();
    #endif // SUPPORT_USE_AGG_RASTERIZER
            break;
        }
 
        case smsSnug:
        default:
            // nothing to prepare
            break;
        }
    }

References Slic3r::BoundingBox::align_to_grid(), ceil(), Slic3r::debug_out_path(), dilate_trimming_region(), Slic3r::SupportGridParams::extrusion_width, Slic3r::get_extents(), m_bbox, m_grid2, m_grid_size, m_pixel_size, m_style, m_support_angle, m_support_polygons, m_support_polygons_rotated, m_support_spacing, m_trimming_polygons, m_trimming_polygons_rotated, Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::min, Slic3r::BoundingBoxBase< PointType, APointsType >::offset(), Slic3r::polygons_rotate(), Slic3r::rasterize_polygons(), scale_, seed_fill_block(), Slic3r::simplify_polygons(), Slic3r::smsGrid, Slic3r::smsSnug, Slic3r::SupportGridParams::support_angle, and Slic3r::png::write_gray_to_file_scaled().

Here is the call graph for this function:

◆ SupportGridPattern() [2/2]

Slic3r::SupportGridPattern::SupportGridPattern ( )

inlineprivate

823{}

Member Function Documentation

◆ dilate_trimming_region()

static std::vector< unsigned char > Slic3r::SupportGridPattern::dilate_trimming_region	(	const std::vector< unsigned char > &	trimming,
		const Vec2i &	grid_size
	)

inlinestaticprivate

    {
        std::vector<unsigned char> dilated(trimming.size(), 0);
        for (int r = 1; r + 1 < grid_size.y(); ++ r)
            for (int c = 1; c + 1 < grid_size.x(); ++ c) {
                //int addr = c + r * m_grid_size.x();
                // 4-neighborhood is not sufficient.
                // dilated[addr] = trimming[addr] != 0 && trimming[addr - 1] != 0 && trimming[addr + 1] != 0 && trimming[addr - m_grid_size.x()] != 0 && trimming[addr + m_grid_size.x()] != 0;
                // 8-neighborhood
                int addr = c + (r - 1) * grid_size.x();
                bool b = trimming[addr - 1] != 0 && trimming[addr] != 0 && trimming[addr + 1] != 0;
                addr += grid_size.x();
                b = b && trimming[addr - 1] != 0 && trimming[addr] != 0 && trimming[addr + 1] != 0;
                addr += grid_size.x();
                b = b && trimming[addr - 1] != 0 && trimming[addr] != 0 && trimming[addr + 1] != 0;
                dilated[addr - grid_size.x()] = b;
            }
        return dilated;
    }

Referenced by SupportGridPattern().

Here is the caller graph for this function:

◆ extract_support()

Polygons Slic3r::SupportGridPattern::extract_support	(	const coord_t	offset_in_grid,
		bool	fill_holes
	)

inline

    {
        switch (m_style) {
        case smsGrid:
        {
    #ifdef SUPPORT_USE_AGG_RASTERIZER
            Polygons support_polygons_simplified = contours_simplified(m_grid_size, m_pixel_size, m_bbox.min, m_grid2, offset_in_grid, fill_holes);
    #else // SUPPORT_USE_AGG_RASTERIZER
            // Generate islands, so each island may be tested for overlap with island_samples.
            assert(std::abs(2 * offset_in_grid) < m_grid.resolution());
            Polygons support_polygons_simplified = m_grid.contours_simplified(offset_in_grid, fill_holes);
    #endif // SUPPORT_USE_AGG_RASTERIZER
 
            ExPolygons islands = diff_ex(support_polygons_simplified, *m_trimming_polygons);
 
            // Extract polygons, which contain some of the island_samples.
            Polygons out;
 
            // Sample a single point per input support polygon, keep it as a reference to maintain corresponding
            // polygons if ever these polygons get split into parts by the trimming polygons.
            // As offset_in_grid may be negative, m_support_polygons may stick slightly outside of islands.
            // Trim ti with islands.
            Points samples = island_samples(
                offset_in_grid > 0 ? 
                    // Expanding, thus m_support_polygons are all inside islands.
                    union_ex(*m_support_polygons) :
                    // Shrinking, thus m_support_polygons may be trimmed a tiny bit by islands.
                    intersection_ex(*m_support_polygons, islands));
 
            std::vector<std::pair<Point,bool>> samples_inside;
            for (ExPolygon &island : islands) {
                BoundingBox bbox = get_extents(island.contour);
                // Samples are sorted lexicographically.
                auto it_lower = std::lower_bound(samples.begin(), samples.end(), Point(bbox.min - Point(1, 1)));
                auto it_upper = std::upper_bound(samples.begin(), samples.end(), Point(bbox.max + Point(1, 1)));
                samples_inside.clear();
                for (auto it = it_lower; it != it_upper; ++ it)
                    if (bbox.contains(*it))
                        samples_inside.push_back(std::make_pair(*it, false));
                if (! samples_inside.empty()) {
                    // For all samples_inside count the boundary crossing.
                    for (size_t i_contour = 0; i_contour <= island.holes.size(); ++ i_contour) {
                        Polygon &contour = (i_contour == 0) ? island.contour : island.holes[i_contour - 1];
                        Points::const_iterator i = contour.points.begin();
                        Points::const_iterator j = contour.points.end() - 1;
                        for (; i != contour.points.end(); j = i ++) {
                            //FIXME this test is not numerically robust. Particularly, it does not handle horizontal segments at y == point(1) well.
                            // Does the ray with y == point(1) intersect this line segment?
                            for (auto &sample_inside : samples_inside) {
                                if (((*i)(1) > sample_inside.first(1)) != ((*j)(1) > sample_inside.first(1))) {
                                    double x1 = (double)sample_inside.first(0);
                                    double x2 = (double)(*i)(0) + (double)((*j)(0) - (*i)(0)) * (double)(sample_inside.first(1) - (*i)(1)) / (double)((*j)(1) - (*i)(1));
                                    if (x1 < x2)
                                        sample_inside.second = !sample_inside.second;
                                }
                            }
                        }
                    }
                    // If any of the sample is inside this island, add this island to the output.
                    for (auto &sample_inside : samples_inside)
                        if (sample_inside.second) {
                            polygons_append(out, std::move(island));
                            island.clear();
                            break;
                        }
                }
            }
 
    #ifdef SLIC3R_DEBUG
            BoundingBox bbox = get_extents(*m_trimming_polygons);
            if (! islands.empty())
                bbox.merge(get_extents(islands));
            if (!out.empty())
                bbox.merge(get_extents(out));
            if (!support_polygons_simplified.empty())
                bbox.merge(get_extents(support_polygons_simplified));
            SVG svg(debug_out_path("extract_support_from_grid_trimmed-%s-%d-%d-%lf.svg", step_name, iRun, layer_id, print_z).c_str(), bbox);
            svg.draw(union_ex(support_polygons_simplified), "gray", 0.25f);
            svg.draw(islands, "red", 0.5f);
            svg.draw(union_ex(out), "green", 0.5f);
            svg.draw(union_ex(*m_support_polygons), "blue", 0.5f);
            svg.draw_outline(islands, "red", "red", scale_(0.05));
            svg.draw_outline(union_ex(out), "green", "green", scale_(0.05));
            svg.draw_outline(union_ex(*m_support_polygons), "blue", "blue", scale_(0.05));
            for (const Point &pt : samples)
                svg.draw(pt, "black", coord_t(scale_(0.15)));
            svg.Close();
    #endif /* SLIC3R_DEBUG */
 
            if (m_support_angle != 0.)
                polygons_rotate(out, m_support_angle);
            return out;
        }
        case smsTree:
        case smsOrganic:
//            assert(false);
            [[fallthrough]];
        case smsSnug:
            // Merge the support polygons by applying morphological closing and inwards smoothing.
            auto closing_distance   = scaled<float>(m_support_material_closing_radius);
            auto smoothing_distance = scaled<float>(m_extrusion_width);
#ifdef SLIC3R_DEBUG
            SVG::export_expolygons(debug_out_path("extract_support_from_grid_trimmed-%s-%d-%d-%lf.svg", step_name, iRun, layer_id, print_z),
                { { { diff_ex(expand(*m_support_polygons, closing_distance), closing(*m_support_polygons, closing_distance, SUPPORT_SURFACES_OFFSET_PARAMETERS)) }, { "closed", "blue",   0.5f } },
                  { { union_ex(smooth_outward(closing(*m_support_polygons, closing_distance, SUPPORT_SURFACES_OFFSET_PARAMETERS), smoothing_distance)) },           { "regularized", "red", "black", "", scaled<coord_t>(0.1f), 0.5f } },
                  { { union_ex(*m_support_polygons) },                                                                                                              { "src",   "green",  0.5f } },
                });
#endif /* SLIC3R_DEBUG */
            //FIXME do we want to trim with the object here? On one side the columns will be thinner, on the other side support interfaces may disappear for snug supports.
            // return diff(smooth_outward(closing(*m_support_polygons, closing_distance, SUPPORT_SURFACES_OFFSET_PARAMETERS), smoothing_distance), *m_trimming_polygons);
            return smooth_outward(closing(*m_support_polygons, closing_distance, SUPPORT_SURFACES_OFFSET_PARAMETERS), smoothing_distance);
        }
        assert(false);
        return Polygons();
    }

References Slic3r::SVG::Close(), Slic3r::closing(), Slic3r::BoundingBoxBase< PointType, APointsType >::contains(), Slic3r::contour(), Slic3r::contours_simplified(), Slic3r::debug_out_path(), Slic3r::diff_ex(), Slic3r::SVG::draw(), Slic3r::SVG::draw_outline(), Slic3r::expand(), Slic3r::SVG::export_expolygons(), Slic3r::get_extents(), Slic3r::intersection_ex(), island_samples(), m_bbox, m_extrusion_width, m_grid2, m_grid_size, m_pixel_size, m_style, m_support_angle, m_support_material_closing_radius, m_support_polygons, m_trimming_polygons, Slic3r::BoundingBoxBase< PointType, APointsType >::max, Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::BoundingBoxBase< PointType, APointsType >::min, Slic3r::MultiPoint::points, Slic3r::polygons_append(), Slic3r::polygons_rotate(), scale_, Slic3r::smooth_outward(), Slic3r::smsGrid, Slic3r::smsOrganic, Slic3r::smsSnug, Slic3r::smsTree, SUPPORT_SURFACES_OFFSET_PARAMETERS, and Slic3r::union_ex().

Referenced by Slic3r::fill_contact_layer().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ island_samples()

static Points Slic3r::SupportGridPattern::island_samples ( const ExPolygons & expolygons )

inlinestaticprivate

    {
        Points pts;
        pts.reserve(expolygons.size());
        for (const ExPolygon &expoly : expolygons)
            if (expoly.contour.points.size() > 2) {
                #if 0
                    pts.push_back(island_sample(expoly));
                #else 
                    Polygons polygons = offset(expoly, - 20.f);
                    for (const Polygon &poly : polygons)
                        if (! poly.points.empty()) {
                            // Take a small fixed number of samples of this polygon for robustness.
                            int num_points  = int(poly.points.size());
                            int num_samples = std::min(num_points, 4);
                            int stride = num_points / num_samples;
                            for (int i = 0; i < num_points; i += stride)
                                pts.push_back(poly.points[i]);
                            break;
                        }
                #endif
            }
        // Sort the points lexicographically, so a binary search could be used to locate points inside a bounding box.
        std::sort(pts.begin(), pts.end());
        return pts;
    } 

References Slic3r::ExPolygon::contour, Slic3r::offset(), and Slic3r::MultiPoint::points.

Referenced by extract_support().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator=()

SupportGridPattern & Slic3r::SupportGridPattern::operator= ( const SupportGridPattern & rhs )

private

◆ seed_fill_block()

static void Slic3r::SupportGridPattern::seed_fill_block	(	std::vector< unsigned char > &	grid,
		Vec2i	grid_size,
		const std::vector< unsigned char > &	trimming,
		const Vec2i &	grid_blocks,
		int	oversampling
	)

inlinestaticprivate

    {
        int size      = oversampling;
        int stride    = grid_size.x();
        for (int block_r = 0; block_r < grid_blocks.y(); ++ block_r)
            for (int block_c = 0; block_c < grid_blocks.x(); ++ block_c) {
                // Propagate the support pixels over the macro cell up to the trimming mask.
                int                  addr      = block_c * size + 1 + (block_r * size + 1) * stride;
                unsigned char       *grid_data = grid.data() + addr;
                const unsigned char *mask_data = trimming.data() + addr;
                // Top to bottom propagation.
                #define PROPAGATION_STEP(offset) \
                    do { \
                        int addr = r * stride + c; \
                        int addr2 = addr + offset; \
                        if (grid_data[addr2] && ! mask_data[addr] && ! mask_data[addr2]) \
                            grid_data[addr] = 1; \
                    } while (0);
                for (int r = 0; r < size; ++ r) {
                    if (r > 0)
                        for (int c = 0; c < size; ++ c)
                            PROPAGATION_STEP(- stride);
                    for (int c = 1; c < size; ++ c)
                        PROPAGATION_STEP(- 1);
                    for (int c = size - 2; c >= 0; -- c)
                        PROPAGATION_STEP(+ 1);
                }
                // Bottom to top propagation.
                for (int r = size - 2; r >= 0; -- r) {
                    for (int c = 0; c < size; ++ c)
                        PROPAGATION_STEP(+ stride);
                    for (int c = 1; c < size; ++ c)
                        PROPAGATION_STEP(- 1);
                    for (int c = size - 2; c >= 0; -- c)
                        PROPAGATION_STEP(+ 1);
                }
                #undef PROPAGATION_STEP
            }
    }