Slic3r::MMU_Graph Struct Reference

Collaboration diagram for Slic3r::MMU_Graph:

Classes
struct	Arc
struct	Node

Public Types
enum class	ARC_TYPE { BORDER , NON_BORDER }

Public Member Functions
void	remove_edge (const size_t from_idx, const size_t to_idx)
size_t	get_global_index (const size_t poly_idx, const size_t point_idx) const
void	append_edge (const size_t &from_idx, const size_t &to_idx, int color=-1, ARC_TYPE type=ARC_TYPE::NON_BORDER)
MMU_Graph::Arc	get_border_arc (size_t idx) const
size_t	nodes_count () const
void	remove_nodes_with_one_arc ()
void	add_contours (const std::vector< std::vector< ColoredLine > > &color_poly)
bool	is_vertex_on_contour (const Voronoi::VD::vertex_type *vertex) const
bool	is_edge_attach_to_contour (const voronoi_diagram< double >::const_edge_iterator &edge_iterator) const
bool	is_edge_connecting_two_contour_vertices (const voronoi_diagram< double >::const_edge_iterator &edge_iterator) const
void	append_voronoi_vertices (const Geometry::VoronoiDiagram &vd, const Polygons &color_poly_tmp, BoundingBox bbox)
void	garbage_collect ()

Public Attributes
std::vector< MMU_Graph::Node >	nodes
std::vector< MMU_Graph::Arc >	arcs
size_t	all_border_points {}
std::vector< size_t >	polygon_idx_offset
std::vector< size_t >	polygon_sizes

Detailed Description

Member Enumeration Documentation

ARC_TYPE

enum class Slic3r::MMU_Graph::ARC_TYPE

strong

Enumerator
BORDER
NON_BORDER

{ BORDER, NON_BORDER };

Member Function Documentation

add_contours()

void Slic3r::MMU_Graph::add_contours ( const std::vector< std::vector< ColoredLine > > & color_poly )

inline

    {
        this->all_border_points = nodes.size();
        this->polygon_sizes     = std::vector<size_t>(color_poly.size());
        for (size_t polygon_idx = 0; polygon_idx < color_poly.size(); ++polygon_idx) this->polygon_sizes[polygon_idx] = color_poly[polygon_idx].size();
        this->polygon_idx_offset    = std::vector<size_t>(color_poly.size());
        this->polygon_idx_offset[0] = 0;
        for (size_t polygon_idx = 1; polygon_idx < color_poly.size(); ++polygon_idx) {
            this->polygon_idx_offset[polygon_idx] = this->polygon_idx_offset[polygon_idx - 1] + color_poly[polygon_idx - 1].size();
        }
 
        size_t poly_idx = 0;
        for (const std::vector<ColoredLine> &color_lines : color_poly) {
            size_t line_idx = 0;
            for (const ColoredLine &color_line : color_lines) {
                size_t from_idx = this->get_global_index(poly_idx, line_idx);
                size_t to_idx   = this->get_global_index(poly_idx, (line_idx + 1) % color_lines.size());
                this->append_edge(from_idx, to_idx, color_line.color, ARC_TYPE::BORDER);
                ++line_idx;
            }
            ++poly_idx;
        }
    }

References append_edge(), BORDER, get_global_index(), and nodes.

Referenced by Slic3r::build_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

append_edge()

void Slic3r::MMU_Graph::append_edge ( const size_t & from_idx, const size_t & to_idx, int color = -1, ARC_TYPE type = ARC_TYPE::NON_BORDER )

inline

    {
        // Don't append duplicate edges between the same nodes.
        for (const size_t &arc_idx : this->nodes[from_idx].arc_idxs)
            if (arcs[arc_idx].to_idx == to_idx) return;
        for (const size_t &arc_idx : this->nodes[to_idx].arc_idxs)
            if (arcs[arc_idx].to_idx == from_idx) return;
 
        this->nodes[from_idx].arc_idxs.push_back(this->arcs.size());
        this->arcs.push_back({from_idx, to_idx, color, type});
 
        // Always insert only one directed arc for the input polygons.
        // Two directed arcs in both directions are inserted if arcs aren't between points of the input polygons.
        if (type == ARC_TYPE::NON_BORDER) {
            this->nodes[to_idx].arc_idxs.push_back(this->arcs.size());
            this->arcs.push_back({to_idx, from_idx, color, type});
        }
    }

References arcs, and NON_BORDER.

Referenced by add_contours(), and Slic3r::build_graph().

Here is the caller graph for this function:

append_voronoi_vertices()

void Slic3r::MMU_Graph::append_voronoi_vertices ( const Geometry::VoronoiDiagram & vd, const Polygons & color_poly_tmp, BoundingBox bbox )

inline

    {
        bbox.offset(SCALED_EPSILON);
 
        struct CPoint
        {
            CPoint() = delete;
            CPoint(const Vec2d &point, size_t contour_idx, size_t point_idx) : m_point_double(point), m_point(mk_point(point)), m_point_idx(point_idx), m_contour_idx(contour_idx)
            {}
            CPoint(const Vec2d &point, size_t point_idx) : m_point_double(point), m_point(mk_point(point)), m_point_idx(point_idx), m_contour_idx(0) {}
            const Vec2d m_point_double;
            const Point m_point;
            size_t      m_point_idx;
            size_t      m_contour_idx;
 
            [[nodiscard]] const Vec2d &point_double() const { return m_point_double; }
            [[nodiscard]] const Point &point() const { return m_point; }
            bool                       operator==(const CPoint &rhs) const
            {
                return this->m_point_double == rhs.m_point_double && this->m_contour_idx == rhs.m_contour_idx && this->m_point_idx == rhs.m_point_idx;
            }
        };
        struct CPointAccessor
        {
            const Point *operator()(const CPoint &pt) const { return &pt.point(); }
        };
        typedef ClosestPointInRadiusLookup<CPoint, CPointAccessor> CPointLookupType;
 
        CPointLookupType closest_voronoi_point(coord_t(SCALED_EPSILON));
        CPointLookupType closest_contour_point(3 * coord_t(SCALED_EPSILON));
        for (const Polygon &polygon : color_poly_tmp)
            for (const Point &pt : polygon.points) closest_contour_point.insert(CPoint(Vec2d(pt.x(), pt.y()), &polygon - &color_poly_tmp.front(), &pt - &polygon.points.front()));
 
        for (const voronoi_diagram<double>::vertex_type &vertex : vd.vertices()) {
            vertex.color(-1);
            Vec2d vertex_point_double = Vec2d(vertex.x(), vertex.y());
            Point vertex_point        = mk_point(vertex);
 
            const Vec2d &first_point_double  = this->nodes[this->get_border_arc(vertex.incident_edge()->cell()->source_index()).from_idx].point;
            const Vec2d &second_point_double = this->nodes[this->get_border_arc(vertex.incident_edge()->twin()->cell()->source_index()).from_idx].point;
 
            if (vertex_equal_to_point(&vertex, first_point_double)) {
                assert(vertex.color() != vertex.incident_edge()->cell()->source_index());
                assert(vertex.color() != vertex.incident_edge()->twin()->cell()->source_index());
                vertex.color(this->get_border_arc(vertex.incident_edge()->cell()->source_index()).from_idx);
            } else if (vertex_equal_to_point(&vertex, second_point_double)) {
                assert(vertex.color() != vertex.incident_edge()->cell()->source_index());
                assert(vertex.color() != vertex.incident_edge()->twin()->cell()->source_index());
                vertex.color(this->get_border_arc(vertex.incident_edge()->twin()->cell()->source_index()).from_idx);
            } else if (bbox.contains(vertex_point)) {
                if (auto [contour_pt, c_dist_sqr] = closest_contour_point.find(vertex_point); contour_pt != nullptr && c_dist_sqr < Slic3r::sqr(3 * SCALED_EPSILON)) {
                    vertex.color(this->get_global_index(contour_pt->m_contour_idx, contour_pt->m_point_idx));
                } else if (auto [voronoi_pt, v_dist_sqr] = closest_voronoi_point.find(vertex_point); voronoi_pt == nullptr || v_dist_sqr >= Slic3r::sqr(SCALED_EPSILON / 10.0)) {
                    closest_voronoi_point.insert(CPoint(vertex_point_double, this->nodes_count()));
                    vertex.color(this->nodes_count());
                    this->nodes.push_back({vertex_point_double});
                } else {
                    // Boost Voronoi diagram generator sometimes creates two very closed points instead of one point.
                    // For the example points (146872.99999999997, -146872.99999999997) and (146873, -146873), this example also included in Voronoi generator test cases.
                    std::vector<std::pair<const CPoint *, double>> all_closes_c_points = closest_voronoi_point.find_all(vertex_point);
                    int                                            merge_to_point      = -1;
                    for (const std::pair<const CPoint *, double> &c_point : all_closes_c_points)
                        if ((vertex_point_double - c_point.first->point_double()).squaredNorm() <= Slic3r::sqr(EPSILON)) {
                            merge_to_point = int(c_point.first->m_point_idx);
                            break;
                        }
 
                    if (merge_to_point != -1) {
                        vertex.color(merge_to_point);
                    } else {
                        closest_voronoi_point.insert(CPoint(vertex_point_double, this->nodes_count()));
                        vertex.color(this->nodes_count());
                        this->nodes.push_back({vertex_point_double});
                    }
                }
            }
        }
    }

References Slic3r::BoundingBoxBase< PointType, APointsType >::contains(), EPSILON, Slic3r::MMU_Graph::Arc::from_idx, get_border_arc(), get_global_index(), Slic3r::mk_point(), nodes_count(), Slic3r::BoundingBoxBase< PointType, APointsType >::offset(), Slic3r::operator==(), SCALED_EPSILON, Slic3r::sqr(), Slic3r::vertex_equal_to_point(), and Slic3r::Geometry::VoronoiDiagram::vertices().

Referenced by Slic3r::build_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

garbage_collect()

void Slic3r::MMU_Graph::garbage_collect ( )

inline

    {
        std::vector<int> nodes_map(this->nodes.size(), -1);
        int              nodes_count = 0;
        size_t           arcs_count  = 0;
        for (const MMU_Graph::Node &node : this->nodes)
            if (size_t node_idx = &node - &this->nodes.front(); !node.arc_idxs.empty()) {
                nodes_map[node_idx] = nodes_count++;
                arcs_count += node.arc_idxs.size();
            }
 
        std::vector<MMU_Graph::Node> new_nodes;
        std::vector<MMU_Graph::Arc>  new_arcs;
        new_nodes.reserve(nodes_count);
        new_arcs.reserve(arcs_count);
        for (const MMU_Graph::Node &node : this->nodes)
            if (size_t node_idx = &node - &this->nodes.front(); nodes_map[node_idx] >= 0) {
                new_nodes.push_back({node.point});
                for (const size_t &arc_idx : node.arc_idxs) {
                    const Arc &arc = this->arcs[arc_idx];
                    new_nodes.back().arc_idxs.emplace_back(new_arcs.size());
                    new_arcs.push_back({size_t(nodes_map[arc.from_idx]), size_t(nodes_map[arc.to_idx]), arc.color, arc.type});
                }
            }
 
        this->nodes = std::move(new_nodes);
        this->arcs  = std::move(new_arcs);
    }

References nodes_count().

Here is the call graph for this function:

get_border_arc()

MMU_Graph::Arc Slic3r::MMU_Graph::get_border_arc ( size_t idx ) const

inlinenodiscard

    {
        assert(idx < this->all_border_points);
        return this->arcs[idx];
    }

References all_border_points.

Referenced by append_voronoi_vertices(), and Slic3r::build_graph().

Here is the caller graph for this function:

get_global_index()

size_t Slic3r::MMU_Graph::get_global_index ( const size_t poly_idx, const size_t point_idx ) const

inlinenodiscard

{ return polygon_idx_offset[poly_idx] + point_idx; }

References polygon_idx_offset.

Referenced by add_contours(), append_voronoi_vertices(), Slic3r::build_graph(), Slic3r::init_polygon_indices(), and Slic3r::remove_multiple_edges_in_vertices().

Here is the caller graph for this function:

is_edge_attach_to_contour()

bool Slic3r::MMU_Graph::is_edge_attach_to_contour ( const voronoi_diagram< double >::const_edge_iterator & edge_iterator ) const

inlinenodiscard

    {
        return this->is_vertex_on_contour(edge_iterator->vertex0()) || this->is_vertex_on_contour(edge_iterator->vertex1());
    }

References is_vertex_on_contour().

Referenced by Slic3r::build_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

is_edge_connecting_two_contour_vertices()

bool Slic3r::MMU_Graph::is_edge_connecting_two_contour_vertices ( const voronoi_diagram< double >::const_edge_iterator & edge_iterator ) const

inlinenodiscard

    {
        return this->is_vertex_on_contour(edge_iterator->vertex0()) && this->is_vertex_on_contour(edge_iterator->vertex1());
    }

References is_vertex_on_contour().

Referenced by Slic3r::build_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

is_vertex_on_contour()

bool Slic3r::MMU_Graph::is_vertex_on_contour ( const Voronoi::VD::vertex_type * vertex ) const

inline

    {
        assert(vertex != nullptr);
        return vertex->color() < this->all_border_points;
    }

Referenced by Slic3r::build_graph(), is_edge_attach_to_contour(), and is_edge_connecting_two_contour_vertices().

Here is the caller graph for this function:

nodes_count()

size_t Slic3r::MMU_Graph::nodes_count ( ) const

inlinenodiscard

{ return this->nodes.size(); }

Referenced by append_voronoi_vertices(), Slic3r::build_graph(), and garbage_collect().

Here is the caller graph for this function:

remove_edge()

void Slic3r::MMU_Graph::remove_edge ( const size_t from_idx, const size_t to_idx )

inline

    {
        nodes[from_idx].remove_edge(to_idx, *this);
        nodes[to_idx].remove_edge(from_idx, *this);
    }

References nodes.

Referenced by Slic3r::remove_multiple_edges_in_vertices(), and remove_nodes_with_one_arc().

Here is the caller graph for this function:

remove_nodes_with_one_arc()

void Slic3r::MMU_Graph::remove_nodes_with_one_arc ( )

inline

    {
        std::queue<size_t> update_queue;
        for (const MMU_Graph::Node &node : this->nodes) {
            size_t node_idx = &node - &this->nodes.front();
            // Skip nodes that represent points of input polygons.
            if (node.arc_idxs.size() == 1 && node_idx >= this->all_border_points) update_queue.emplace(&node - &this->nodes.front());
        }
 
        while (!update_queue.empty()) {
            size_t           node_from_idx = update_queue.front();
            MMU_Graph::Node &node_from     = this->nodes[update_queue.front()];
            update_queue.pop();
            if (node_from.arc_idxs.empty()) continue;
 
            assert(node_from.arc_idxs.size() == 1);
            size_t           node_to_idx = arcs[node_from.arc_idxs.front()].to_idx;
            MMU_Graph::Node &node_to     = this->nodes[node_to_idx];
            this->remove_edge(node_from_idx, node_to_idx);
            if (node_to.arc_idxs.size() == 1 && node_to_idx >= this->all_border_points) update_queue.emplace(node_to_idx);
        }
    }

References Slic3r::MMU_Graph::Node::arc_idxs, arcs, and remove_edge().

Referenced by Slic3r::build_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

all_border_points

size_t Slic3r::MMU_Graph::all_border_points {}

{};

Referenced by Slic3r::extract_colored_segments(), and get_border_arc().

arcs

std::vector<MMU_Graph::Arc> Slic3r::MMU_Graph::arcs

Referenced by append_edge(), Slic3r::compute_edge_length(), Slic3r::extract_colored_segments(), Slic3r::get_all_next_arcs(), Slic3r::get_next_arc(), Slic3r::MMU_Graph::Node::remove_edge(), Slic3r::remove_multiple_edges_in_vertices(), and remove_nodes_with_one_arc().

nodes

std::vector<MMU_Graph::Node> Slic3r::MMU_Graph::nodes

Referenced by add_contours(), Slic3r::build_graph(), Slic3r::compute_edge_length(), Slic3r::extract_colored_segments(), Slic3r::get_all_next_arcs(), Slic3r::get_next_arc(), remove_edge(), and Slic3r::remove_multiple_edges_in_vertices().

polygon_idx_offset

std::vector<size_t> Slic3r::MMU_Graph::polygon_idx_offset

Referenced by get_global_index().

polygon_sizes

std::vector<size_t> Slic3r::MMU_Graph::polygon_sizes

Referenced by Slic3r::remove_multiple_edges_in_vertices().

---

The documentation for this struct was generated from the following file:

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MultiMaterialSegmentation.cpp