Slic3r::Geometry::VoronoiDiagram Class Reference

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

Classes
struct	Segment

Public Types
enum class	IssueType {   NO_ISSUE_DETECTED , FINITE_EDGE_WITH_NON_FINITE_VERTEX , MISSING_VORONOI_VERTEX , NON_PLANAR_VORONOI_DIAGRAM ,   VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT , PARABOLIC_VORONOI_EDGE_WITHOUT_FOCUS_POINT , UNKNOWN }
enum class	State { REPAIR_NOT_NEEDED , REPAIR_SUCCESSFUL , REPAIR_UNSUCCESSFUL , UNKNOWN }
using	coord_type = double
using	voronoi_diagram_type = boost::polygon::voronoi_diagram<coord_type>
using	point_type = boost::polygon::point_data<voronoi_diagram_type::coordinate_type>
using	segment_type = boost::polygon::segment_data<voronoi_diagram_type::coordinate_type>
using	rect_type = boost::polygon::rectangle_data<voronoi_diagram_type::coordinate_type>
using	coordinate_type = voronoi_diagram_type::coordinate_type
using	vertex_type = voronoi_diagram_type::vertex_type
using	edge_type = voronoi_diagram_type::edge_type
using	cell_type = voronoi_diagram_type::cell_type
using	const_vertex_iterator = voronoi_diagram_type::const_vertex_iterator
using	const_edge_iterator = voronoi_diagram_type::const_edge_iterator
using	const_cell_iterator = voronoi_diagram_type::const_cell_iterator
using	vertex_container_type = voronoi_diagram_type::vertex_container_type
using	edge_container_type = voronoi_diagram_type::edge_container_type
using	cell_container_type = voronoi_diagram_type::cell_container_type
using	SegmentIt = std::vector<Slic3r::Geometry::VoronoiDiagram::Segment>::iterator

Public Member Functions
	VoronoiDiagram ()=default
virtual	~VoronoiDiagram ()=default
IssueType	get_issue_type () const
State	get_state () const
bool	is_valid () const
void	clear ()
const vertex_container_type &	vertices () const
const edge_container_type &	edges () const
const cell_container_type &	cells () const
std::size_t	num_vertices () const
std::size_t	num_edges () const
std::size_t	num_cells () const
template<typename SegmentIterator>
boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, void >::type	construct_voronoi (SegmentIterator segment_begin, SegmentIterator segment_end, bool try_to_repair_if_needed=true)
template<typename PointIterator>
boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_point_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< PointIterator >::value_type >::type >::type >::type, void >::type	construct_voronoi (const PointIterator first, const PointIterator last)
template<typename PointIterator, typename SegmentIterator>
boost::polygon::enable_if< typenameboost::polygon::gtl_and< typenameboost::polygon::gtl_if< typenameboost::polygon::is_point_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< PointIterator >::value_type >::type >::type >::type, typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type >::type, void >::type	construct_voronoi (const PointIterator p_first, const PointIterator p_last, const SegmentIterator s_first, const SegmentIterator s_last)
template<typename SegmentIterator>
boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, VoronoiDiagram::IssueType >::type	try_to_repair_degenerated_voronoi_diagram_by_rotation (SegmentIterator segment_begin, SegmentIterator segment_end, double fix_angle)
template<typename SegmentIterator>
boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, VoronoiDiagram::IssueType >::type	try_to_repair_degenerated_voronoi_diagram (SegmentIterator segment_begin, SegmentIterator segment_end)

Static Public Member Functions
template<typename SegmentIterator>
static boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, IssueType >::type	detect_known_issues (const VoronoiDiagram &voronoi_diagram, SegmentIterator segment_begin, SegmentIterator segment_end)

Private Member Functions
void	copy_to_local (voronoi_diagram_type &voronoi_diagram)

Static Private Member Functions
template<typename SegmentIterator>
static boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, IssueType >::type	detect_known_voronoi_cell_issues (const VoronoiDiagram &voronoi_diagram, SegmentIterator segment_begin, SegmentIterator segment_end)
static IssueType	detect_known_voronoi_edge_issues (const VoronoiDiagram &voronoi_diagram)

Private Attributes
voronoi_diagram_type	m_voronoi_diagram
vertex_container_type	m_vertices
edge_container_type	m_edges
cell_container_type	m_cells
bool	m_is_modified = false
State	m_state = State::UNKNOWN
IssueType	m_issue_type = IssueType::UNKNOWN

Friends
struct	boost::polygon::segment_traits< Slic3r::Geometry::VoronoiDiagram::Segment >

Detailed Description

Member Typedef Documentation

cell_container_type

using Slic3r::Geometry::VoronoiDiagram::cell_container_type = voronoi_diagram_type::cell_container_type

cell_type

using Slic3r::Geometry::VoronoiDiagram::cell_type = voronoi_diagram_type::cell_type

const_cell_iterator

using Slic3r::Geometry::VoronoiDiagram::const_cell_iterator = voronoi_diagram_type::const_cell_iterator

const_edge_iterator

using Slic3r::Geometry::VoronoiDiagram::const_edge_iterator = voronoi_diagram_type::const_edge_iterator

const_vertex_iterator

using Slic3r::Geometry::VoronoiDiagram::const_vertex_iterator = voronoi_diagram_type::const_vertex_iterator

coord_type

using Slic3r::Geometry::VoronoiDiagram::coord_type = double

coordinate_type

using Slic3r::Geometry::VoronoiDiagram::coordinate_type = voronoi_diagram_type::coordinate_type

edge_container_type

using Slic3r::Geometry::VoronoiDiagram::edge_container_type = voronoi_diagram_type::edge_container_type

edge_type

using Slic3r::Geometry::VoronoiDiagram::edge_type = voronoi_diagram_type::edge_type

point_type

using Slic3r::Geometry::VoronoiDiagram::point_type = boost::polygon::point_data<voronoi_diagram_type::coordinate_type>

rect_type

using Slic3r::Geometry::VoronoiDiagram::rect_type = boost::polygon::rectangle_data<voronoi_diagram_type::coordinate_type>

segment_type

using Slic3r::Geometry::VoronoiDiagram::segment_type = boost::polygon::segment_data<voronoi_diagram_type::coordinate_type>

SegmentIt

using Slic3r::Geometry::VoronoiDiagram::SegmentIt = std::vector<Slic3r::Geometry::VoronoiDiagram::Segment>::iterator

vertex_container_type

using Slic3r::Geometry::VoronoiDiagram::vertex_container_type = voronoi_diagram_type::vertex_container_type

vertex_type

using Slic3r::Geometry::VoronoiDiagram::vertex_type = voronoi_diagram_type::vertex_type

voronoi_diagram_type

using Slic3r::Geometry::VoronoiDiagram::voronoi_diagram_type = boost::polygon::voronoi_diagram<coord_type>

Member Enumeration Documentation

IssueType

enum class Slic3r::Geometry::VoronoiDiagram::IssueType

strong

Enumerator
NO_ISSUE_DETECTED
FINITE_EDGE_WITH_NON_FINITE_VERTEX
MISSING_VORONOI_VERTEX
NON_PLANAR_VORONOI_DIAGRAM
VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT
PARABOLIC_VORONOI_EDGE_WITHOUT_FOCUS_POINT
UNKNOWN

                         {
        NO_ISSUE_DETECTED,
        FINITE_EDGE_WITH_NON_FINITE_VERTEX,
        MISSING_VORONOI_VERTEX,
        NON_PLANAR_VORONOI_DIAGRAM,
        VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT,
        PARABOLIC_VORONOI_EDGE_WITHOUT_FOCUS_POINT,
        UNKNOWN                                     // Repairs are disabled in the constructor.
    };

State

enum class Slic3r::Geometry::VoronoiDiagram::State

strong

Enumerator
REPAIR_NOT_NEEDED
REPAIR_SUCCESSFUL
REPAIR_UNSUCCESSFUL
UNKNOWN

                     {
        REPAIR_NOT_NEEDED,   // The original Voronoi diagram doesn't have any issue.
        REPAIR_SUCCESSFUL,   // The original Voronoi diagram has some issues, but it was repaired.
        REPAIR_UNSUCCESSFUL, // The original Voronoi diagram has some issues, but it wasn't repaired.
        UNKNOWN              // Repairs are disabled in the constructor.
    };

Constructor & Destructor Documentation

VoronoiDiagram()

Slic3r::Geometry::VoronoiDiagram::VoronoiDiagram ( )

default

Referenced by detect_known_issues(), detect_known_voronoi_cell_issues(), and detect_known_voronoi_edge_issues().

Here is the caller graph for this function:

~VoronoiDiagram()

virtual Slic3r::Geometry::VoronoiDiagram::~VoronoiDiagram ( )

virtualdefault

Member Function Documentation

cells()

const cell_container_type & Slic3r::Geometry::VoronoiDiagram::cells ( ) const

inline

{ return m_is_modified ? m_cells : m_voronoi_diagram.cells(); }

References m_cells, m_is_modified, and m_voronoi_diagram.

Referenced by Slic3r::Arachne::SkeletalTrapezoidation::constructFromPolygons(), detect_known_voronoi_cell_issues(), Slic3r::Voronoi::reset_inside_outside_annotations(), and Slic3r::Voronoi::debug::verify_inside_outside_annotations().

Here is the caller graph for this function:

clear()

void Slic3r::Geometry::VoronoiDiagram::clear

(

)

{
    if (m_is_modified) {
        m_vertices.clear();
        m_edges.clear();
        m_cells.clear();
        m_is_modified = false;
    } else {
        m_voronoi_diagram.clear();
    }
 
    m_state      = State::UNKNOWN;
    m_issue_type = IssueType::UNKNOWN;
}

References m_cells, m_edges, m_is_modified, m_issue_type, m_state, m_vertices, m_voronoi_diagram, and UNKNOWN.

construct_voronoi() [1/3]

template<typename PointIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_point_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< PointIterator >::value_type >::type >::type >::type, void >::type Slic3r::Geometry::VoronoiDiagram::construct_voronoi ( const PointIterator first, const PointIterator last )

inline

    {
        boost::polygon::construct_voronoi(first, last, &m_voronoi_diagram);
        m_state      = State::UNKNOWN;
        m_issue_type = IssueType::UNKNOWN;
    }

References m_issue_type, m_state, m_voronoi_diagram, and UNKNOWN.

construct_voronoi() [2/3]

template<typename PointIterator, typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_and< typenameboost::polygon::gtl_if< typenameboost::polygon::is_point_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< PointIterator >::value_type >::type >::type >::type, typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type >::type, void >::type Slic3r::Geometry::VoronoiDiagram::construct_voronoi ( const PointIterator p_first, const PointIterator p_last, const SegmentIterator s_first, const SegmentIterator s_last )

inline

    {
        boost::polygon::construct_voronoi(p_first, p_last, s_first, s_last, &m_voronoi_diagram);
        m_state      = State::UNKNOWN;
        m_issue_type = IssueType::UNKNOWN;
    }

References m_issue_type, m_state, m_voronoi_diagram, and UNKNOWN.

construct_voronoi() [3/3]

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, void >::type Slic3r::Geometry::VoronoiDiagram::construct_voronoi	(	SegmentIterator	segment_begin,
		SegmentIterator	segment_end,
		bool	try_to_repair_if_needed = true )

                                                                                                                                            {
    boost::polygon::construct_voronoi(segment_begin, segment_end, &m_voronoi_diagram);
    if (try_to_repair_if_needed) {
        if (m_issue_type = detect_known_issues(*this, segment_begin, segment_end); m_issue_type != IssueType::NO_ISSUE_DETECTED) {
            if (m_issue_type == IssueType::MISSING_VORONOI_VERTEX) {
                BOOST_LOG_TRIVIAL(warning) << "Detected missing Voronoi vertex, input polygons will be rotated back and forth.";
            } else if (m_issue_type == IssueType::NON_PLANAR_VORONOI_DIAGRAM) {
                BOOST_LOG_TRIVIAL(warning) << "Detected non-planar Voronoi diagram, input polygons will be rotated back and forth.";
            } else if (m_issue_type == IssueType::VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT) {
                BOOST_LOG_TRIVIAL(warning) << "Detected Voronoi edge intersecting input segment, input polygons will be rotated back and forth.";
            } else if (m_issue_type == IssueType::FINITE_EDGE_WITH_NON_FINITE_VERTEX) {
                BOOST_LOG_TRIVIAL(warning) << "Detected finite Voronoi vertex with non finite vertex, input polygons will be rotated back and forth.";
            } else if (m_issue_type == IssueType::PARABOLIC_VORONOI_EDGE_WITHOUT_FOCUS_POINT) {
                BOOST_LOG_TRIVIAL(warning) << "Detected parabolic Voronoi edges without focus point, input polygons will be rotated back and forth.";
            } else {
                BOOST_LOG_TRIVIAL(error) << "Detected unknown Voronoi diagram issue, input polygons will be rotated back and forth.";
            }
 
            if (m_issue_type = try_to_repair_degenerated_voronoi_diagram(segment_begin, segment_end); m_issue_type != IssueType::NO_ISSUE_DETECTED) {
                if (m_issue_type == IssueType::MISSING_VORONOI_VERTEX) {
                    BOOST_LOG_TRIVIAL(error) << "Detected missing Voronoi vertex even after the rotation of input.";
                } else if (m_issue_type == IssueType::NON_PLANAR_VORONOI_DIAGRAM) {
                    BOOST_LOG_TRIVIAL(error) << "Detected non-planar Voronoi diagram even after the rotation of input.";
                } else if (m_issue_type == IssueType::VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT) {
                    BOOST_LOG_TRIVIAL(error) << "Detected Voronoi edge intersecting input segment even after the rotation of input.";
                } else if (m_issue_type == IssueType::FINITE_EDGE_WITH_NON_FINITE_VERTEX) {
                    BOOST_LOG_TRIVIAL(error) << "Detected finite Voronoi vertex with non finite vertex even after the rotation of input.";
                } else if (m_issue_type == IssueType::PARABOLIC_VORONOI_EDGE_WITHOUT_FOCUS_POINT) {
                    BOOST_LOG_TRIVIAL(error) << "Detected parabolic Voronoi edges without focus point even after the rotation of input.";
                } else {
                    BOOST_LOG_TRIVIAL(error) << "Detected unknown Voronoi diagram issue even after the rotation of input.";
                }
 
                m_state = State::REPAIR_UNSUCCESSFUL;
            } else {
                m_state = State::REPAIR_SUCCESSFUL;
            }
        } else {
            m_state      = State::REPAIR_NOT_NEEDED;
            m_issue_type = IssueType::NO_ISSUE_DETECTED;
        }
    } else {
        m_state      = State::UNKNOWN;
        m_issue_type = IssueType::UNKNOWN;
    }
}

References detect_known_issues(), FINITE_EDGE_WITH_NON_FINITE_VERTEX, m_issue_type, m_state, m_voronoi_diagram, MISSING_VORONOI_VERTEX, NO_ISSUE_DETECTED, NON_PLANAR_VORONOI_DIAGRAM, PARABOLIC_VORONOI_EDGE_WITHOUT_FOCUS_POINT, REPAIR_NOT_NEEDED, REPAIR_SUCCESSFUL, REPAIR_UNSUCCESSFUL, try_to_repair_degenerated_voronoi_diagram(), UNKNOWN, and VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT.

Referenced by Slic3r::build_graph(), and Slic3r::Arachne::SkeletalTrapezoidation::constructFromPolygons().

Here is the call graph for this function:

Here is the caller graph for this function:

copy_to_local()

void Slic3r::Geometry::VoronoiDiagram::copy_to_local ( voronoi_diagram_type & voronoi_diagram )

private

                                                                        {
    m_edges.clear();
    m_cells.clear();
    m_vertices.clear();
 
    // Copy Voronoi edges.
    m_edges.reserve(voronoi_diagram.num_edges());
    for (const edge_type &edge : voronoi_diagram.edges()) {
        m_edges.emplace_back(edge.is_linear(), edge.is_primary());
        m_edges.back().color(edge.color());
    }
 
    // Copy Voronoi cells.
    m_cells.reserve(voronoi_diagram.num_cells());
    for (const cell_type &cell : voronoi_diagram.cells()) {
        m_cells.emplace_back(cell.source_index(), cell.source_category());
        m_cells.back().color(cell.color());
 
        if (cell.incident_edge()) {
            size_t incident_edge_idx = cell.incident_edge() - voronoi_diagram.edges().data();
            m_cells.back().incident_edge(&m_edges[incident_edge_idx]);
        }
    }
 
    // Copy Voronoi vertices.
    m_vertices.reserve(voronoi_diagram.num_vertices());
    for (const vertex_type &vertex : voronoi_diagram.vertices()) {
        m_vertices.emplace_back(vertex.x(), vertex.y());
        m_vertices.back().color(vertex.color());
 
        if (vertex.incident_edge()) {
            size_t incident_edge_idx = vertex.incident_edge() - voronoi_diagram.edges().data();
            m_vertices.back().incident_edge(&m_edges[incident_edge_idx]);
        }
    }
 
    // Assign all pointers for each Voronoi edge.
    for (const edge_type &old_edge : voronoi_diagram.edges()) {
        size_t     edge_idx = &old_edge - voronoi_diagram.edges().data();
        edge_type &new_edge = m_edges[edge_idx];
 
        if (old_edge.cell()) {
            size_t cell_idx = old_edge.cell() - voronoi_diagram.cells().data();
            new_edge.cell(&m_cells[cell_idx]);
        }
 
        if (old_edge.vertex0()) {
            size_t vertex0_idx = old_edge.vertex0() - voronoi_diagram.vertices().data();
            new_edge.vertex0(&m_vertices[vertex0_idx]);
        }
 
        if (old_edge.twin()) {
            size_t twin_edge_idx = old_edge.twin() - voronoi_diagram.edges().data();
            new_edge.twin(&m_edges[twin_edge_idx]);
        }
 
        if (old_edge.next()) {
            size_t next_edge_idx = old_edge.next() - voronoi_diagram.edges().data();
            new_edge.next(&m_edges[next_edge_idx]);
        }
 
        if (old_edge.prev()) {
            size_t prev_edge_idx = old_edge.prev() - voronoi_diagram.edges().data();
            new_edge.prev(&m_edges[prev_edge_idx]);
        }
    }
 
    m_voronoi_diagram.clear();
    m_is_modified = true;
}

References m_cells, m_edges, m_is_modified, m_vertices, and m_voronoi_diagram.

Referenced by try_to_repair_degenerated_voronoi_diagram_by_rotation().

Here is the caller graph for this function:

detect_known_issues()

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, VoronoiDiagram::IssueType >::type Slic3r::Geometry::VoronoiDiagram::detect_known_issues ( const VoronoiDiagram & voronoi_diagram, SegmentIterator segment_begin, SegmentIterator segment_end )

static

{
    if (const IssueType edge_issue_type = detect_known_voronoi_edge_issues(voronoi_diagram); edge_issue_type != IssueType::NO_ISSUE_DETECTED) {
        return edge_issue_type;
    } else if (const IssueType cell_issue_type = detect_known_voronoi_cell_issues(voronoi_diagram, segment_begin, segment_end); cell_issue_type != IssueType::NO_ISSUE_DETECTED) {
        return cell_issue_type;
    } else if (!VoronoiUtilsCgal::is_voronoi_diagram_planar_angle(voronoi_diagram, segment_begin, segment_end)) {
        // Detection of non-planar Voronoi diagram detects at least GH issues #8474, #8514 and #8446.
        return IssueType::NON_PLANAR_VORONOI_DIAGRAM;
    }
 
    return IssueType::NO_ISSUE_DETECTED;
}

References VoronoiDiagram(), detect_known_voronoi_cell_issues(), detect_known_voronoi_edge_issues(), Slic3r::Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_angle(), NO_ISSUE_DETECTED, and NON_PLANAR_VORONOI_DIAGRAM.

Referenced by construct_voronoi(), and try_to_repair_degenerated_voronoi_diagram_by_rotation().

Here is the call graph for this function:

Here is the caller graph for this function:

detect_known_voronoi_cell_issues()

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, VoronoiDiagram::IssueType >::type Slic3r::Geometry::VoronoiDiagram::detect_known_voronoi_cell_issues ( const VoronoiDiagram & voronoi_diagram, SegmentIterator segment_begin, SegmentIterator segment_end )

staticprivate

{
    using Segment          = typename std::iterator_traits<SegmentIterator>::value_type;
    using Point            = typename boost::polygon::segment_point_type<Segment>::type;
    using SegmentCellRange = SegmentCellRange<Point>;
 
    for (VD::cell_type cell : voronoi_diagram.cells()) {
        if (cell.is_degenerate() || !cell.contains_segment())
            continue; // Skip degenerated cell that has no spoon. Also, skip a cell that doesn't contain a segment.
 
        if (const SegmentCellRange cell_range = VoronoiUtils::compute_segment_cell_range(cell, segment_begin, segment_end); cell_range.is_valid()) {
            // Detection if Voronoi edge is intersecting input segment.
            // It detects this type of issue at least in GH issues #8446, #8474 and #8514.
 
            const Segment &source_segment      = Geometry::VoronoiUtils::get_source_segment(cell, segment_begin, segment_end);
            const Vec2d    source_segment_from = boost::polygon::segment_traits<Segment>::get(source_segment, boost::polygon::LOW).template cast<double>();
            const Vec2d    source_segment_to   = boost::polygon::segment_traits<Segment>::get(source_segment, boost::polygon::HIGH).template cast<double>();
            const Vec2d    source_segment_vec  = source_segment_to - source_segment_from;
 
            // All Voronoi vertices must be on the left side of the source segment, otherwise the Voronoi diagram is invalid.
            for (const VD::edge_type *edge = cell_range.edge_begin; edge != cell_range.edge_end; edge = edge->next()) {
                if (edge->is_infinite()) {
                    // When there is a missing Voronoi vertex, we may encounter an infinite Voronoi edge.
                    // This happens, for example, in GH issue #8846.
                    return IssueType::MISSING_VORONOI_VERTEX;
                } else if (const Vec2d edge_v1(edge->vertex1()->x(), edge->vertex1()->y()); Slic3r::cross2(source_segment_vec, edge_v1 - source_segment_from) < 0) {
                    return IssueType::VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT;
                }
            }
        } else {
            // When there is a missing Voronoi vertex (especially at one of the endpoints of the input segment),
            // the returned cell_range is marked as invalid.
            // It detects this type of issue at least in GH issue #8846.
            return IssueType::MISSING_VORONOI_VERTEX;
        }
    }
 
    return IssueType::NO_ISSUE_DETECTED;
}

References VoronoiDiagram(), Slic3r::cast(), cells(), Slic3r::Geometry::VoronoiUtils::compute_segment_cell_range(), Slic3r::cross2(), Slic3r::Geometry::VoronoiUtils::get_source_segment(), MISSING_VORONOI_VERTEX, NO_ISSUE_DETECTED, and VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT.

Referenced by detect_known_issues().

Here is the call graph for this function:

Here is the caller graph for this function:

detect_known_voronoi_edge_issues()

VoronoiDiagram::IssueType Slic3r::Geometry::VoronoiDiagram::detect_known_voronoi_edge_issues ( const VoronoiDiagram & voronoi_diagram )

staticprivate

{
    for (const voronoi_diagram_type::edge_type &edge : voronoi_diagram.edges()) {
        if (edge.is_finite()) {
            assert(edge.vertex0() != nullptr && edge.vertex1() != nullptr);
            if (edge.vertex0() == nullptr || edge.vertex1() == nullptr || !VoronoiUtils::is_finite(*edge.vertex0()) || !VoronoiUtils::is_finite(*edge.vertex1()))
                return IssueType::FINITE_EDGE_WITH_NON_FINITE_VERTEX;
 
            if (edge.is_curved() && !edge.cell()->contains_point() && !edge.twin()->cell()->contains_point())
                return IssueType::PARABOLIC_VORONOI_EDGE_WITHOUT_FOCUS_POINT;
        }
    }
 
    return IssueType::NO_ISSUE_DETECTED;
}

References VoronoiDiagram(), edges(), FINITE_EDGE_WITH_NON_FINITE_VERTEX, Slic3r::Geometry::VoronoiUtils::is_finite(), NO_ISSUE_DETECTED, and PARABOLIC_VORONOI_EDGE_WITHOUT_FOCUS_POINT.

Referenced by detect_known_issues().

Here is the call graph for this function:

Here is the caller graph for this function:

edges()

const edge_container_type & Slic3r::Geometry::VoronoiDiagram::edges ( ) const

inline

{ return m_is_modified ? m_edges : m_voronoi_diagram.edges(); }

References m_edges, m_is_modified, and m_voronoi_diagram.

Referenced by Slic3r::Voronoi::annotate_inside_outside(), Slic3r::build_graph(), detect_known_voronoi_edge_issues(), Slic3r::dump_voronoi_to_svg(), Slic3r::Voronoi::edge_offset_contour_intersections(), Slic3r::Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_intersection(), Slic3r::Voronoi::offset(), Slic3r::Voronoi::reset_inside_outside_annotations(), Slic3r::Voronoi::skeleton_edges_rough(), Slic3r::Voronoi::debug::verify_inside_outside_annotations(), Slic3r::Voronoi::debug::verify_offset_intersection_points(), Slic3r::Voronoi::debug::verify_signed_distances(), Slic3r::Voronoi::debug::verify_twin_halfedges_successive(), and Slic3r::Voronoi::debug::verify_vertices_on_contour().

Here is the caller graph for this function:

get_issue_type()

IssueType Slic3r::Geometry::VoronoiDiagram::get_issue_type ( ) const

inline

{ return m_issue_type; }

References m_issue_type.

get_state()

State Slic3r::Geometry::VoronoiDiagram::get_state ( ) const

inline

{ return m_state; }

References m_state.

is_valid()

bool Slic3r::Geometry::VoronoiDiagram::is_valid ( ) const

inline

{ return m_state != State::REPAIR_UNSUCCESSFUL; }

References m_state, and REPAIR_UNSUCCESSFUL.

num_cells()

std::size_t Slic3r::Geometry::VoronoiDiagram::num_cells ( ) const

inline

{ return m_is_modified ? m_cells.size() : m_voronoi_diagram.num_cells(); }

References m_cells, m_is_modified, and m_voronoi_diagram.

num_edges()

std::size_t Slic3r::Geometry::VoronoiDiagram::num_edges ( ) const

inline

{ return m_is_modified ? m_edges.size() : m_voronoi_diagram.num_edges(); }

References m_edges, m_is_modified, and m_voronoi_diagram.

Referenced by Slic3r::Voronoi::edge_offset_contour_intersections(), Slic3r::Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_intersection(), Slic3r::Voronoi::offset(), Slic3r::Voronoi::skeleton_edges_rough(), and Slic3r::Voronoi::debug::verify_twin_halfedges_successive().

Here is the caller graph for this function:

num_vertices()

std::size_t Slic3r::Geometry::VoronoiDiagram::num_vertices ( ) const

inline

{ return m_is_modified ? m_vertices.size() : m_voronoi_diagram.num_vertices(); }

References m_is_modified, m_vertices, and m_voronoi_diagram.

try_to_repair_degenerated_voronoi_diagram()

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, VoronoiDiagram::IssueType >::type Slic3r::Geometry::VoronoiDiagram::try_to_repair_degenerated_voronoi_diagram	(	SegmentIterator	segment_begin,
		SegmentIterator	segment_end )

{
    IssueType issue_type = m_issue_type;
 
    const std::vector<double> fix_angles = {PI / 6, PI / 5, PI / 7, PI / 11};
    for (const double fix_angle : fix_angles) {
        issue_type = try_to_repair_degenerated_voronoi_diagram_by_rotation(segment_begin, segment_end, fix_angle);
        if (issue_type == IssueType::NO_ISSUE_DETECTED) {
            return issue_type;
        }
    }
 
    return issue_type;
}

References m_issue_type, NO_ISSUE_DETECTED, PI, and try_to_repair_degenerated_voronoi_diagram_by_rotation().

Referenced by construct_voronoi().

Here is the call graph for this function:

Here is the caller graph for this function:

try_to_repair_degenerated_voronoi_diagram_by_rotation()

template<typename SegmentIterator>

boost::polygon::enable_if< typenameboost::polygon::gtl_if< typenameboost::polygon::is_segment_concept< typenameboost::polygon::geometry_concept< typenamestd::iterator_traits< SegmentIterator >::value_type >::type >::type >::type, VoronoiDiagram::IssueType >::type Slic3r::Geometry::VoronoiDiagram::try_to_repair_degenerated_voronoi_diagram_by_rotation	(	SegmentIterator	segment_begin,
		SegmentIterator	segment_end,
		double	fix_angle )

{
    using SegmentType = typename std::iterator_traits<SegmentIterator>::value_type;
    using PointType   = typename boost::polygon::segment_traits<SegmentType>::point_type;
 
    // Copy all segments and rotate their vertices.
    std::vector<VoronoiDiagram::Segment> segments_rotated;
    segments_rotated.reserve(std::distance(segment_begin, segment_end));
    for (auto segment_it = segment_begin; segment_it != segment_end; ++segment_it) {
        PointType from = boost::polygon::segment_traits<SegmentType>::get(*segment_it, boost::polygon::LOW);
        PointType to   = boost::polygon::segment_traits<SegmentType>::get(*segment_it, boost::polygon::HIGH);
        segments_rotated.emplace_back(from.rotated(fix_angle), to.rotated(fix_angle));
    }
 
    VoronoiDiagram::voronoi_diagram_type voronoi_diagram_rotated;
    boost::polygon::construct_voronoi(segments_rotated.begin(), segments_rotated.end(), &voronoi_diagram_rotated);
 
    this->copy_to_local(voronoi_diagram_rotated);
    const IssueType issue_type = detect_known_issues(*this, segments_rotated.begin(), segments_rotated.end());
 
    // We want to remap all Voronoi vertices at the endpoints of input segments
    // to ensure that Voronoi vertices at endpoints will be preserved after rotation.
    // So we assign every Voronoi vertices color to map this Vertex into input segments.
    for (cell_type cell : m_cells) {
        if (cell.is_degenerate())
            continue;
 
        if (cell.contains_segment()) {
            if (const SegmentCellRange cell_range = VoronoiUtils::compute_segment_cell_range(cell, segments_rotated.begin(), segments_rotated.end()); cell_range.is_valid()) {
                if (cell_range.edge_end->vertex1()->color() == 0) {
                    // Vertex 1 of edge_end points to the starting endpoint of the input segment (from() or line.a).
                    VD::vertex_type::color_type color = encode_input_segment_endpoint(cell.source_index(), boost::polygon::LOW);
                    cell_range.edge_end->vertex1()->color(color);
                }
 
                if (cell_range.edge_begin->vertex0()->color() == 0) {
                    // Vertex 0 of edge_end points to the ending endpoint of the input segment (to() or line.b).
                    VD::vertex_type::color_type color = encode_input_segment_endpoint(cell.source_index(), boost::polygon::HIGH);
                    cell_range.edge_begin->vertex0()->color(color);
                }
            } else {
                // This could happen when there is a missing Voronoi vertex even after rotation.
                assert(cell_range.is_valid());
            }
        }
 
        // FIXME @hejllukas: Implement mapping also for source points and not just for source segments.
    }
 
    // Rotate all Voronoi vertices back.
    // When a Voronoi vertex can be mapped to the input segment endpoint, then we don't need to do rotation back.
    for (vertex_type &vertex : m_vertices) {
        if (vertex.color() == 0) {
            // This vertex isn't mapped to any vertex, so we rotate it back.
            vertex = VoronoiUtils::make_rotated_vertex(vertex, -fix_angle);
        } else {
            // This vertex can be mapped to the input segment endpoint.
            PointType   endpoint = decode_input_segment_endpoint(vertex.color(), segment_begin, segment_end);
            vertex_type endpoint_vertex{double(endpoint.x()), double(endpoint.y())};
            endpoint_vertex.incident_edge(vertex.incident_edge());
            endpoint_vertex.color(vertex.color());
            vertex = endpoint_vertex;
        }
    }
 
    // We have to clear all marked vertices because some algorithms expect that all vertices have a color equal to 0.
    for (vertex_type &vertex : m_vertices)
        vertex.color(0);
 
    return issue_type;
}

References Slic3r::Geometry::VoronoiUtils::compute_segment_cell_range(), copy_to_local(), Slic3r::Geometry::decode_input_segment_endpoint(), detect_known_issues(), Slic3r::Geometry::encode_input_segment_endpoint(), m_cells, m_vertices, and Slic3r::Geometry::VoronoiUtils::make_rotated_vertex().

Referenced by try_to_repair_degenerated_voronoi_diagram().

Here is the call graph for this function:

Here is the caller graph for this function:

vertices()

const vertex_container_type & Slic3r::Geometry::VoronoiDiagram::vertices ( ) const

inline

{ return m_is_modified ? m_vertices : m_voronoi_diagram.vertices(); }

References m_is_modified, m_vertices, and m_voronoi_diagram.

Referenced by Slic3r::MMU_Graph::append_voronoi_vertices(), Slic3r::build_graph(), Slic3r::dump_voronoi_to_svg(), Slic3r::Voronoi::edge_offset_contour_intersections(), Slic3r::Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_angle(), Slic3r::Voronoi::reset_inside_outside_annotations(), Slic3r::Voronoi::signed_vertex_distances(), Slic3r::Voronoi::debug::verify_inside_outside_annotations(), and Slic3r::Voronoi::debug::verify_signed_distances().

Here is the caller graph for this function:

Friends And Related Symbol Documentation

boost::polygon::segment_traits< Slic3r::Geometry::VoronoiDiagram::Segment >

friend struct boost::polygon::segment_traits< Slic3r::Geometry::VoronoiDiagram::Segment >

friend

References m_issue_type, and UNKNOWN.

Member Data Documentation

m_cells

cell_container_type Slic3r::Geometry::VoronoiDiagram::m_cells

private

Referenced by cells(), clear(), copy_to_local(), num_cells(), and try_to_repair_degenerated_voronoi_diagram_by_rotation().

m_edges

edge_container_type Slic3r::Geometry::VoronoiDiagram::m_edges

private

Referenced by clear(), copy_to_local(), edges(), and num_edges().

m_is_modified

bool Slic3r::Geometry::VoronoiDiagram::m_is_modified = false

private

Referenced by cells(), clear(), copy_to_local(), edges(), num_cells(), num_edges(), num_vertices(), and vertices().

m_issue_type

IssueType Slic3r::Geometry::VoronoiDiagram::m_issue_type = IssueType::UNKNOWN

private

Referenced by boost::polygon::segment_traits< Slic3r::Geometry::VoronoiDiagram::Segment >, clear(), construct_voronoi(), construct_voronoi(), construct_voronoi(), get_issue_type(), and try_to_repair_degenerated_voronoi_diagram().

m_state

State Slic3r::Geometry::VoronoiDiagram::m_state = State::UNKNOWN

private

Referenced by clear(), construct_voronoi(), construct_voronoi(), construct_voronoi(), get_state(), and is_valid().

m_vertices

vertex_container_type Slic3r::Geometry::VoronoiDiagram::m_vertices

private

Referenced by clear(), copy_to_local(), num_vertices(), try_to_repair_degenerated_voronoi_diagram_by_rotation(), and vertices().

m_voronoi_diagram

voronoi_diagram_type Slic3r::Geometry::VoronoiDiagram::m_voronoi_diagram

private

Referenced by cells(), clear(), construct_voronoi(), construct_voronoi(), construct_voronoi(), copy_to_local(), edges(), num_cells(), num_edges(), num_vertices(), and vertices().

---

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

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