196 lines
8.9 KiB
C++
196 lines
8.9 KiB
C++
|
#ifndef slic3r_Geometry_Voronoi_hpp_
|
||
|
|
#define slic3r_Geometry_Voronoi_hpp_
|
||
|
|
|
||
|
|
#include "../Line.hpp"
|
||
|
|
#include "../Polyline.hpp"
|
||
|
|
|
||
|
|
#ifdef _MSC_VER
|
||
|
|
// Suppress warning C4146 in OpenVDB: unary minus operator applied to unsigned type, result still unsigned
|
||
|
|
#pragma warning(push)
|
||
|
|
#pragma warning(disable : 4146)
|
||
|
|
#endif // _MSC_VER
|
||
|
|
#include "boost/polygon/voronoi.hpp"
|
||
|
|
#ifdef _MSC_VER
|
||
|
|
#pragma warning(pop)
|
||
|
|
#endif // _MSC_VER
|
||
|
|
|
||
|
|
namespace Slic3r::Geometry {
|
||
|
|
|
||
|
|
class VoronoiDiagram
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
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;
|
||
|
|
|
||
|
|
enum class IssueType {
|
||
|
|
NO_ISSUE_DETECTED,
|
||
|
|
FINITE_EDGE_WITH_NON_FINITE_VERTEX,
|
||
|
|
MISSING_VORONOI_VERTEX,
|
||
|
|
NON_PLANAR_VORONOI_DIAGRAM,
|
||
|
|
VORONOI_EDGE_INTERSECTING_INPUT_SEGMENT,
|
||
|
|
UNKNOWN // Repairs are disabled in the constructor.
|
||
|
|
};
|
||
|
|
|
||
|
|
enum class State {
|
||
|
|
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.
|
||
|
|
};
|
||
|
|
|
||
|
|
VoronoiDiagram() = default;
|
||
|
|
|
||
|
|
virtual ~VoronoiDiagram() = default;
|
||
|
|
|
||
|
|
IssueType get_issue_type() const { return m_issue_type; }
|
||
|
|
|
||
|
|
State get_state() const { return m_state; }
|
||
|
|
|
||
|
|
bool is_valid() const { return m_state != State::REPAIR_UNSUCCESSFUL; }
|
||
|
|
|
||
|
|
void clear();
|
||
|
|
|
||
|
|
const vertex_container_type &vertices() const { return m_is_modified ? m_vertices : m_voronoi_diagram.vertices(); }
|
||
|
|
|
||
|
|
const edge_container_type &edges() const { return m_is_modified ? m_edges : m_voronoi_diagram.edges(); }
|
||
|
|
|
||
|
|
const cell_container_type &cells() const { return m_is_modified ? m_cells : m_voronoi_diagram.cells(); }
|
||
|
|
|
||
|
|
std::size_t num_vertices() const { return m_is_modified ? m_vertices.size() : m_voronoi_diagram.num_vertices(); }
|
||
|
|
|
||
|
|
std::size_t num_edges() const { return m_is_modified ? m_edges.size() : m_voronoi_diagram.num_edges(); }
|
||
|
|
|
||
|
|
std::size_t num_cells() const { return m_is_modified ? m_cells.size() : m_voronoi_diagram.num_cells(); }
|
||
|
|
|
||
|
|
template<typename SegmentIterator>
|
||
|
|
typename boost::polygon::enable_if<
|
||
|
|
typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<
|
||
|
|
typename boost::polygon::geometry_concept<typename std::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>
|
||
|
|
typename boost::polygon::enable_if<
|
||
|
|
typename boost::polygon::gtl_if<typename boost::polygon::is_point_concept<
|
||
|
|
typename boost::polygon::geometry_concept<typename std::iterator_traits<PointIterator>::value_type>::type>::type>::type,
|
||
|
|
void>::type
|
||
|
|
construct_voronoi(const PointIterator first, const PointIterator last)
|
||
|
|
{
|
||
|
|
boost::polygon::construct_voronoi(first, last, &m_voronoi_diagram);
|
||
|
|
m_state = State::UNKNOWN;
|
||
|
|
m_issue_type = IssueType::UNKNOWN;
|
||
|
|
}
|
||
|
|
|
||
|
|
template<typename PointIterator, typename SegmentIterator>
|
||
|
|
typename boost::polygon::enable_if<
|
||
|
|
typename boost::polygon::gtl_and<
|
||
|
|
typename boost::polygon::gtl_if<typename boost::polygon::is_point_concept<
|
||
|
|
typename boost::polygon::geometry_concept<typename std::iterator_traits<PointIterator>::value_type>::type>::type>::type,
|
||
|
|
typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<typename boost::polygon::geometry_concept<
|
||
|
|
typename std::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)
|
||
|
|
{
|
||
|
|
boost::polygon::construct_voronoi(p_first, p_last, s_first, s_last, &m_voronoi_diagram);
|
||
|
|
m_state = State::UNKNOWN;
|
||
|
|
m_issue_type = IssueType::UNKNOWN;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Try to detect cases when some Voronoi vertex is missing, when the Voronoi diagram
|
||
|
|
// is not planar or some Voronoi edge is intersecting input segment.
|
||
|
|
template<typename SegmentIterator>
|
||
|
|
static typename boost::polygon::enable_if<
|
||
|
|
typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<
|
||
|
|
typename boost::polygon::geometry_concept<typename std::iterator_traits<SegmentIterator>::value_type>::type>::type>::type,
|
||
|
|
IssueType>::type
|
||
|
|
detect_known_issues(const VoronoiDiagram &voronoi_diagram, SegmentIterator segment_begin, SegmentIterator segment_end);
|
||
|
|
|
||
|
|
template<typename SegmentIterator>
|
||
|
|
typename boost::polygon::enable_if<
|
||
|
|
typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<
|
||
|
|
typename boost::polygon::geometry_concept<typename std::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>
|
||
|
|
typename boost::polygon::enable_if<
|
||
|
|
typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<
|
||
|
|
typename boost::polygon::geometry_concept<typename std::iterator_traits<SegmentIterator>::value_type>::type>::type>::type,
|
||
|
|
VoronoiDiagram::IssueType>::type
|
||
|
|
try_to_repair_degenerated_voronoi_diagram(SegmentIterator segment_begin, SegmentIterator segment_end);
|
||
|
|
|
||
|
|
private:
|
||
|
|
struct Segment
|
||
|
|
{
|
||
|
|
Point from;
|
||
|
|
Point to;
|
||
|
|
|
||
|
|
Segment() = delete;
|
||
|
|
explicit Segment(const Point &from, const Point &to) : from(from), to(to) {}
|
||
|
|
};
|
||
|
|
|
||
|
|
void copy_to_local(voronoi_diagram_type &voronoi_diagram);
|
||
|
|
|
||
|
|
// Detect issues related to Voronoi cells, or that can be detected by iterating over Voronoi cells.
|
||
|
|
// The first type of issue that can be detected is a missing Voronoi vertex, especially when it is
|
||
|
|
// missing at one of the endpoints of the input segment.
|
||
|
|
// The second type of issue that can be detected is a Voronoi edge that intersects the input segment.
|
||
|
|
template<typename SegmentIterator>
|
||
|
|
static typename boost::polygon::enable_if<
|
||
|
|
typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<
|
||
|
|
typename boost::polygon::geometry_concept<typename std::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 bool has_finite_edge_with_non_finite_vertex(const VoronoiDiagram &voronoi_diagram);
|
||
|
|
|
||
|
|
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;
|
||
|
|
|
||
|
|
public:
|
||
|
|
using SegmentIt = std::vector<Slic3r::Geometry::VoronoiDiagram::Segment>::iterator;
|
||
|
|
|
||
|
|
friend struct boost::polygon::segment_traits<Slic3r::Geometry::VoronoiDiagram::Segment>;
|
||
|
|
};
|
||
|
|
|
||
|
|
} // namespace Slic3r::Geometry
|
||
|
|
|
||
|
|
namespace boost::polygon {
|
||
|
|
template<> struct geometry_concept<Slic3r::Geometry::VoronoiDiagram::Segment>
|
||
|
|
{
|
||
|
|
typedef segment_concept type;
|
||
|
|
};
|
||
|
|
|
||
|
|
template<> struct segment_traits<Slic3r::Geometry::VoronoiDiagram::Segment>
|
||
|
|
{
|
||
|
|
using coordinate_type = coord_t;
|
||
|
|
using point_type = Slic3r::Point;
|
||
|
|
using segment_type = Slic3r::Geometry::VoronoiDiagram::Segment;
|
||
|
|
|
||
|
|
static inline point_type get(const segment_type &segment, direction_1d dir) { return dir.to_int() ? segment.to : segment.from; }
|
||
|
|
};
|
||
|
|
} // namespace boost::polygon
|
||
|
|
|
||
|
|
#endif // slic3r_Geometry_Voronoi_hpp_
|