Slic3r::Geometry::MedialAxis Class Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Geometry/MedialAxis.hpp>

Collaboration diagram for Slic3r::Geometry::MedialAxis:

Classes
struct	EdgeData

Public Member Functions
	MedialAxis (double min_width, double max_width, const ExPolygon &expolygon)
void	build (ThickPolylines *polylines)
void	build (Polylines *polylines)

Private Types
using	VD = VoronoiDiagram

Private Member Functions
std::pair< EdgeData &, bool >	edge_data (const VD::edge_type &edge)
void	process_edge_neighbors (const VD::edge_type *edge, ThickPolyline *polyline)
bool	validate_edge (const VD::edge_type *edge)

Private Attributes
const ExPolygon &	m_expolygon
Lines	m_lines
double	m_min_width
double	m_max_width
VD	m_vd
std::vector< EdgeData >	m_edge_data

Detailed Description

---

Class Documentation

Slic3r::Geometry::MedialAxis::EdgeData

struct Slic3r::Geometry::MedialAxis::EdgeData

Class Members
bool	active { false }
double	width_end { 0 }
double	width_start { 0 }

Member Typedef Documentation

VD

using Slic3r::Geometry::MedialAxis::VD = VoronoiDiagram

private

Constructor & Destructor Documentation

MedialAxis()

Slic3r::Geometry::MedialAxis::MedialAxis	(	double	min_width,
		double	max_width,
		const ExPolygon &	expolygon )

                                                                                     :
    m_expolygon(expolygon), m_lines(expolygon.lines()), m_min_width(min_width), m_max_width(max_width)
{}

References m_expolygon, m_lines, m_max_width, and m_min_width.

Member Function Documentation

build() [1/2]

void Slic3r::Geometry::MedialAxis::build

(

Polylines *

polylines

)

{
    ThickPolylines tp;
    this->build(&tp);
    polylines->reserve(polylines->size() + tp.size());
    for (auto &pl : tp)
        polylines->emplace_back(pl.points);
}

References build().

Here is the call graph for this function:

build() [2/2]

void Slic3r::Geometry::MedialAxis::build

(

ThickPolylines *

polylines

)

{
    m_vd.construct_voronoi(m_lines.begin(), m_lines.end());
 
    // For several ExPolygons in SPE-1729, an invalid Voronoi diagram was produced that wasn't fixable by rotating input data.
    // Those ExPolygons contain very thin lines and holes formed by very close (1-5nm) vertices that are on the edge of our resolution.
    // Those thin lines and holes are both unprintable and cause the Voronoi diagram to be invalid.
    // So we filter out such thin lines and holes and try to compute the Voronoi diagram again.
    if (!m_vd.is_valid()) {
        m_lines = to_lines(closing_ex({m_expolygon}, float(2. * SCALED_EPSILON)));
        m_vd.construct_voronoi(m_lines.begin(), m_lines.end());
 
        if (!m_vd.is_valid())
            BOOST_LOG_TRIVIAL(error) << "MedialAxis - Invalid Voronoi diagram even after morphological closing.";
    }
 
    Slic3r::Voronoi::annotate_inside_outside(m_vd, m_lines);
//    static constexpr double threshold_alpha = M_PI / 12.; // 30 degrees
//    std::vector<Vec2d> skeleton_edges = Slic3r::Voronoi::skeleton_edges_rough(vd, lines, threshold_alpha);
    
    /*
    // DEBUG: dump all Voronoi edges
    {
        for (VD::const_edge_iterator edge = m_vd.edges().begin(); edge != m_vd.edges().end(); ++edge) {
            if (edge->is_infinite()) continue;
            
            ThickPolyline polyline;
            polyline.points.push_back(Point( edge->vertex0()->x(), edge->vertex0()->y() ));
            polyline.points.push_back(Point( edge->vertex1()->x(), edge->vertex1()->y() ));
            polylines->push_back(polyline);
        }
        return;
    }
    */
    
    // collect valid edges (i.e. prune those not belonging to MAT)
    // note: this keeps twins, so it inserts twice the number of the valid edges
    m_edge_data.assign(m_vd.edges().size() / 2, EdgeData{});
    for (VD::const_edge_iterator edge = m_vd.edges().begin(); edge != m_vd.edges().end(); edge += 2)
        if (edge->is_primary() && edge->is_finite() &&
            (Voronoi::vertex_category(edge->vertex0()) == Voronoi::VertexCategory::Inside ||
             Voronoi::vertex_category(edge->vertex1()) == Voronoi::VertexCategory::Inside) &&
            this->validate_edge(&*edge)) {
            // Valid skeleton edge.
            this->edge_data(*edge).first.active = true;
        }
    
    // iterate through the valid edges to build polylines
    ThickPolyline reverse_polyline;
    for (VD::const_edge_iterator seed_edge = m_vd.edges().begin(); seed_edge != m_vd.edges().end(); seed_edge += 2)
        if (EdgeData &seed_edge_data = this->edge_data(*seed_edge).first; seed_edge_data.active) {
            // Mark this edge as visited.
            seed_edge_data.active = false;
 
            // Start a polyline.
            ThickPolyline polyline;
            polyline.points.emplace_back(seed_edge->vertex0()->x(), seed_edge->vertex0()->y());
            polyline.points.emplace_back(seed_edge->vertex1()->x(), seed_edge->vertex1()->y());
            polyline.width.emplace_back(seed_edge_data.width_start);
            polyline.width.emplace_back(seed_edge_data.width_end);        
            // Grow the polyline in a forward direction.
            this->process_edge_neighbors(&*seed_edge, &polyline);
            assert(polyline.width.size() == polyline.points.size() * 2 - 2);
        
            // Grow the polyline in a backward direction.
            reverse_polyline.clear();
            this->process_edge_neighbors(seed_edge->twin(), &reverse_polyline);
            polyline.points.insert(polyline.points.begin(), reverse_polyline.points.rbegin(), reverse_polyline.points.rend());
            polyline.width.insert(polyline.width.begin(), reverse_polyline.width.rbegin(), reverse_polyline.width.rend());
            polyline.endpoints.first = reverse_polyline.endpoints.second;
            assert(polyline.width.size() == polyline.points.size() * 2 - 2);
        
            // Prevent loop endpoints from being extended.
            if (polyline.first_point() == polyline.last_point()) {
                polyline.endpoints.first = false;
                polyline.endpoints.second = false;
            }
 
            // Append polyline to result.
            polylines->emplace_back(std::move(polyline));
        }
 
    #ifdef SLIC3R_DEBUG
    {
        static int iRun = 0;
        dump_voronoi_to_svg(m_lines, m_vd, polylines, debug_out_path("MedialAxis-%d.svg", iRun ++).c_str());
        printf("Thick lines: ");
        for (ThickPolylines::const_iterator it = polylines->begin(); it != polylines->end(); ++ it) {
            ThickLines lines = it->thicklines();
            for (ThickLines::const_iterator it2 = lines.begin(); it2 != lines.end(); ++ it2) {
                printf("%f,%f ", it2->a_width, it2->b_width);
            }
        }
        printf("\n");
    }
    #endif /* SLIC3R_DEBUG */
}

References Slic3r::Geometry::MedialAxis::EdgeData::active, Slic3r::Voronoi::annotate_inside_outside(), Slic3r::ThickPolyline::clear(), Slic3r::closing_ex(), Slic3r::debug_out_path(), Slic3r::dump_voronoi_to_svg(), edge_data(), Slic3r::ThickPolyline::endpoints, Slic3r::MultiPoint::first_point(), Slic3r::Voronoi::Inside, Slic3r::Polyline::last_point(), m_edge_data, m_expolygon, m_lines, m_vd, Slic3r::MultiPoint::points, process_edge_neighbors(), SCALED_EPSILON, Slic3r::to_lines(), Slic3r::Voronoi::vertex_category(), and Slic3r::ThickPolyline::width.

Referenced by build(), and Slic3r::ExPolygon::medial_axis().

Here is the call graph for this function:

Here is the caller graph for this function:

edge_data()

std::pair< EdgeData &, bool > Slic3r::Geometry::MedialAxis::edge_data ( const VD::edge_type & edge )

inlineprivate

                                                                {
        size_t edge_id = &edge - &m_vd.edges().front();
        return { m_edge_data[edge_id / 2], (edge_id & 1) != 0 };
    }

References m_edge_data, and m_vd.

Referenced by build(), process_edge_neighbors(), and validate_edge().

Here is the caller graph for this function:

process_edge_neighbors()

void Slic3r::Geometry::MedialAxis::process_edge_neighbors ( const VD::edge_type * edge, ThickPolyline * polyline )

private

{
    for (;;) {
        // Since rot_next() works on the edge starting point but we want
        // to find neighbors on the ending point, we just swap edge with
        // its twin.
        const VD::edge_type *twin = edge->twin();
    
        // count neighbors for this edge
        size_t               num_neighbors  = 0;
        const VD::edge_type *first_neighbor = nullptr;
        for (const VD::edge_type *neighbor = twin->rot_next(); neighbor != twin; neighbor = neighbor->rot_next())
            if (this->edge_data(*neighbor).first.active) {
                if (num_neighbors == 0)
                    first_neighbor = neighbor;
                ++ num_neighbors;
            }
    
        // if we have a single neighbor then we can continue recursively
        if (num_neighbors == 1) {
            if (std::pair<EdgeData&, bool> neighbor_data = this->edge_data(*first_neighbor);
                neighbor_data.first.active) {
                neighbor_data.first.active = false;
                polyline->points.emplace_back(first_neighbor->vertex1()->x(), first_neighbor->vertex1()->y());
                if (neighbor_data.second) {
                    polyline->width.push_back(neighbor_data.first.width_end);
                    polyline->width.push_back(neighbor_data.first.width_start);
                } else {
                    polyline->width.push_back(neighbor_data.first.width_start);
                    polyline->width.push_back(neighbor_data.first.width_end);
                }
                edge = first_neighbor;
                // Continue chaining.
                continue;
            }
        } else if (num_neighbors == 0) {
            polyline->endpoints.second = true;
        } else {
            // T-shaped or star-shaped joint    
        }
        // Stop chaining.
        break;
    }
}

References edge_data(), Slic3r::ThickPolyline::endpoints, Slic3r::MultiPoint::points, and Slic3r::ThickPolyline::width.

Referenced by build().

Here is the call graph for this function:

Here is the caller graph for this function:

validate_edge()

bool Slic3r::Geometry::MedialAxis::validate_edge ( const VD::edge_type * edge )

private

{
    auto retrieve_segment = [this](const VD::cell_type* cell) -> const Line& { return m_lines[cell->source_index()]; };
    auto retrieve_endpoint = [retrieve_segment](const VD::cell_type* cell) -> const Point& {
        const Line &line = retrieve_segment(cell);
        return cell->source_category() == boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT ? line.a : line.b;
    };
 
    // prevent overflows and detect almost-infinite edges
// #ifndef CLIPPERLIB_INT32
//     if (std::abs(edge->vertex0()->x()) > double(CLIPPER_MAX_COORD_UNSCALED) || 
//         std::abs(edge->vertex0()->y()) > double(CLIPPER_MAX_COORD_UNSCALED) || 
//         std::abs(edge->vertex1()->x()) > double(CLIPPER_MAX_COORD_UNSCALED) ||
//         std::abs(edge->vertex1()->y()) > double(CLIPPER_MAX_COORD_UNSCALED))
//         return false;
// #endif // CLIPPERLIB_INT32
 
    // construct the line representing this edge of the Voronoi diagram
    const Line line({ edge->vertex0()->x(), edge->vertex0()->y() },
                    { edge->vertex1()->x(), edge->vertex1()->y() });
    
    // retrieve the original line segments which generated the edge we're checking
    const VD::cell_type* cell_l = edge->cell();
    const VD::cell_type* cell_r = edge->twin()->cell();
    const Line &segment_l = retrieve_segment(cell_l);
    const Line &segment_r = retrieve_segment(cell_r);
    
    /*
    SVG svg("edge.svg");
    svg.draw(m_expolygon);
    svg.draw(line);
    svg.draw(segment_l, "red");
    svg.draw(segment_r, "blue");
    svg.Close();
    */
    
    /*  Calculate thickness of the cross-section at both the endpoints of this edge.
        Our Voronoi edge is part of a CCW sequence going around its Voronoi cell 
        located on the left side. (segment_l).
        This edge's twin goes around segment_r. Thus, segment_r is 
        oriented in the same direction as our main edge, and segment_l is oriented
        in the same direction as our twin edge.
        We used to only consider the (half-)distances to segment_r, and that works
        whenever segment_l and segment_r are almost specular and facing. However, 
        at curves they are staggered and they only face for a very little length
        (our very short edge represents such visibility).
        Both w0 and w1 can be calculated either towards cell_l or cell_r with equal
        results by Voronoi definition.
        When cell_l or cell_r don't refer to the segment but only to an endpoint, we
        calculate the distance to that endpoint instead.  */
    
    coordf_t w0 = cell_r->contains_segment()
        ? segment_r.distance_to(line.a)*2
        : (retrieve_endpoint(cell_r) - line.a).cast<double>().norm()*2;
    
    coordf_t w1 = cell_l->contains_segment()
        ? segment_l.distance_to(line.b)*2
        : (retrieve_endpoint(cell_l) - line.b).cast<double>().norm()*2;
    
    if (cell_l->contains_segment() && cell_r->contains_segment()) {
        // calculate the relative angle between the two boundary segments
        double angle = fabs(segment_r.orientation() - segment_l.orientation());
        if (angle > PI)
            angle = 2. * PI - angle;
        assert(angle >= 0 && angle <= PI);
 
        // fabs(angle) ranges from 0 (collinear, same direction) to PI (collinear, opposite direction)
        // we're interested only in segments close to the second case (facing segments)
        // so we allow some tolerance.
        // this filter ensures that we're dealing with a narrow/oriented area (longer than thick)
        // we don't run it on edges not generated by two segments (thus generated by one segment
        // and the endpoint of another segment), since their orientation would not be meaningful
        if (PI - angle > PI / 8.) {
            // angle is not narrow enough
            // only apply this filter to segments that are not too short otherwise their 
            // angle could possibly be not meaningful
            if (w0 < SCALED_EPSILON || w1 < SCALED_EPSILON || line.length() >= m_min_width)
                return false;
        }
    } else {
        if (w0 < SCALED_EPSILON || w1 < SCALED_EPSILON)
            return false;
    }
    
    if ((w0 >= m_min_width || w1 >= m_min_width) &&
        (w0 <= m_max_width || w1 <= m_max_width)) {
        std::pair<EdgeData&, bool> ed = this->edge_data(*edge);
        if (ed.second)
            std::swap(w0, w1);
        ed.first.width_start = w0;
        ed.first.width_end   = w1;
        return true;
    }
 
    return false;
}

References Slic3r::Line::a, Slic3r::angle(), Slic3r::Line::b, Slic3r::cast(), Slic3r::Line::distance_to(), edge_data(), m_lines, m_max_width, m_min_width, Slic3r::Line::orientation(), PI, and SCALED_EPSILON.

Here is the call graph for this function:

Member Data Documentation

m_edge_data

std::vector<EdgeData> Slic3r::Geometry::MedialAxis::m_edge_data

private

Referenced by build(), and edge_data().

m_expolygon

const ExPolygon& Slic3r::Geometry::MedialAxis::m_expolygon

private

Referenced by MedialAxis(), and build().

m_lines

Lines Slic3r::Geometry::MedialAxis::m_lines

private

Referenced by MedialAxis(), build(), and validate_edge().

m_max_width

double Slic3r::Geometry::MedialAxis::m_max_width

private

Referenced by MedialAxis(), and validate_edge().

m_min_width

double Slic3r::Geometry::MedialAxis::m_min_width

private

Referenced by MedialAxis(), and validate_edge().

m_vd

VD Slic3r::Geometry::MedialAxis::m_vd

private

Referenced by build(), and edge_data().

---

The documentation for this class was generated from the following files:

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Geometry/MedialAxis.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/Geometry/MedialAxis.cpp