Merge remote-tracking branch 'remotes/prusa/master' 2.4 into dev 2.3.58

still need much tests (& bugfixes) and finish some merging things.

1 files changed, 110 insertions, 21 deletions

diff --git a/src/libslic3r/EdgeGrid.hpp b/src/libslic3r/EdgeGrid.hpp
index 3141b440f..44de5a919 100644
--- a/src/libslic3r/EdgeGrid.hpp
+++ b/src/libslic3r/EdgeGrid.hpp
@@ -12,22 +12,109 @@
 namespace Slic3r {
 namespace EdgeGrid {
 
+
+class Contour {
+public:
+	Contour() = default;
+	Contour(const Slic3r::Point *begin, const Slic3r::Point *end, bool open) : m_begin(begin), m_end(end), m_open(open) {}
+	Contour(const Slic3r::Point *data, size_t size, bool open) : Contour(data, data + size, open) {}
+	Contour(const std::vector<Slic3r::Point> &pts, bool open) : Contour(pts.data(), pts.size(), open) {}
+
+    const Slic3r::Point *begin()  const { return m_begin; }
+    const Slic3r::Point *end()    const { return m_end; }
+    bool                 open()   const { return m_open; }
+    bool                 closed() const { return !m_open; }
+
+    const Slic3r::Point &front()  const { return *m_begin; }
+    const Slic3r::Point &back()   const { return *(m_end - 1); }
+
+	// Start point of a segment idx.
+	const Slic3r::Point& segment_start(size_t idx) const {
+		assert(idx < this->num_segments());
+		return m_begin[idx];
+	}
+
+	// End point of a segment idx.
+	const Slic3r::Point& segment_end(size_t idx) const {
+		assert(idx < this->num_segments());
+		const Slic3r::Point *ptr = m_begin + idx + 1;
+		return ptr == m_end ? *m_begin : *ptr;
+	}
+
+	// Start point of a segment preceding idx.
+	const Slic3r::Point& segment_prev(size_t idx) const {
+		assert(idx < this->num_segments());
+		assert(idx > 0 || ! m_open);
+		return idx == 0 ? m_end[-1] : m_begin[idx - 1];
+	}
+
+	// Index of a segment preceding idx.
+	const size_t 		 segment_idx_prev(size_t idx) const {
+		assert(idx < this->num_segments());
+		assert(idx > 0 || ! m_open);
+		return (idx == 0 ? this->size() : idx) - 1;
+	}
+
+	// Index of a segment preceding idx.
+	const size_t 		 segment_idx_next(size_t idx) const {
+		assert(idx < this->num_segments());
+		++ idx;
+		return m_begin + idx == m_end ? 0 : idx;
+	}
+
+	size_t               num_segments() const { return this->size() - (m_open ? 1 : 0); }
+
+    Line                 get_segment(size_t idx) const
+    {
+        assert(idx < this->num_segments());
+        return Line(this->segment_start(idx), this->segment_end(idx));
+    }
+
+    Lines                get_segments() const
+    {
+        Lines lines;
+        lines.reserve(this->num_segments());
+        if (this->num_segments() > 2) {
+            for (auto it = this->begin(); it != this->end() - 1; ++it) lines.push_back(Line(*it, *(it + 1)));
+            if (!m_open) lines.push_back(Line(this->back(), this->front()));
+        }
+        return lines;
+    }
+
+private:
+	size_t  			 size() const { return m_end - m_begin; }
+
+	const Slic3r::Point *m_begin { nullptr };
+	const Slic3r::Point *m_end   { nullptr };
+	bool                 m_open  { false };
+};
+
 class Grid
 {
 public:
-	Grid();
-	~Grid();
+	Grid() = default;
+	Grid(const BoundingBox &bbox) : m_bbox(bbox) {}
 
 	void set_bbox(const BoundingBox &bbox) { m_bbox = bbox; }
 
+	// Fill in the grid with open polylines or closed contours.
+	// If open flag is indicated, then polylines_or_polygons are considered to be open by default.
+	// Only if the first point of a polyline is equal to the last point of a polyline, 
+	// then the polyline is considered to be closed and the last repeated point is removed when
+	// inserted into the EdgeGrid.
+	// Most of the Grid functions expect all the contours to be closed, you have been warned!
+	void create(const std::vector<Points> &polylines_or_polygons, coord_t resolution, bool open);
+	void create(const Polygons &polygons, const Polylines &polylines, coord_t resolution);
+
+	// Fill in the grid with closed contours.
 	void create(const Polygons &polygons, coord_t resolution);
 	void create(const std::vector<const Polygon*> &polygons, coord_t resolution);
-	void create(const std::vector<Points> &polygons, coord_t resolution);
+	void create(const std::vector<Points> &polygons, coord_t resolution) { this->create(polygons, resolution, false); }
 	void create(const ExPolygon &expoly, coord_t resolution);
 	void create(const ExPolygons &expolygons, coord_t resolution);
 	void create(const ExPolygonCollection &expolygons, coord_t resolution);
 
-	const std::vector<const Slic3r::Points*>& contours() const { return m_contours; }
+	const std::vector<Contour>& contours() const { return m_contours; }
 
 #if 0
 	// Test, whether the edges inside the grid intersect with the polygons provided.
@@ -44,12 +131,14 @@ public:
 
 	// Fill in a rough m_signed_distance_field from the edge grid.
 	// The rough SDF is used by signed_distance() for distances outside of the search_radius.
+	// Only call this function for closed contours!
 	void calculate_sdf();
 
 	// Return an estimate of the signed distance based on m_signed_distance_field grid.
 	float signed_distance_bilinear(const Point &pt) const;
 
 	// Calculate a signed distance to the contours in search_radius from the point.
+	// Only call this function for closed contours!
 	struct ClosestPointResult {
 		size_t contour_idx  	= size_t(-1);
 		size_t start_point_idx  = size_t(-1);
@@ -60,12 +149,14 @@ public:
 
 		bool valid() const { return contour_idx != size_t(-1); }
 	};
-	ClosestPointResult closest_point(const Point &pt, coord_t search_radius) const;
+	ClosestPointResult closest_point_signed_distance(const Point &pt, coord_t search_radius) const;
 
+	// Only call this function for closed contours!
 	bool signed_distance_edges(const Point &pt, coord_t search_radius, coordf_t &result_min_dist, bool *pon_segment = nullptr) const;
 
 	// Calculate a signed distance to the contours in search_radius from the point. If no edge is found in search_radius,
 	// return an interpolated value from m_signed_distance_field, if it exists.
+	// Only call this function for closed contours!
 	bool signed_distance(const Point &pt, coord_t search_radius, coordf_t &result_min_dist) const;
 
 	const BoundingBox& 	bbox() const { return m_bbox; }
@@ -76,8 +167,8 @@ public:
 	// For supports: Contours enclosing the rasterized edges.
 	Polygons 			contours_simplified(coord_t offset, bool fill_holes) const;
 
-	typedef std::pair<const Slic3r::Points*, size_t> ContourPoint;
-	typedef std::pair<const Slic3r::Points*, size_t> ContourEdge;
+	typedef std::pair<const Contour*, size_t> ContourPoint;
+	typedef std::pair<const Contour*, size_t> ContourEdge;
 	std::vector<std::pair<ContourEdge, ContourEdge>> intersecting_edges() const;
 	bool 											 has_intersecting_edges() const;
 
@@ -245,28 +336,26 @@ public:
 					return;
 	}
 
-	std::pair<std::vector<std::pair<size_t, size_t>>::const_iterator, std::vector<std::pair<size_t, size_t>>::const_iterator> cell_data_range(coord_t row, coord_t col) const
+    std::pair<std::vector<std::pair<size_t, size_t>>::const_iterator, std::vector<std::pair<size_t, size_t>>::const_iterator> cell_data_range(coord_t row, coord_t col) const
 	{
-		assert(row >= 0);
-		assert(row < (coord_t)m_rows);
-		assert(col >= 0);
-		assert(col < (coord_t)m_cols);
+        assert(row >= 0 && size_t(row) < m_rows);
+        assert(col >= 0 && size_t(col) < m_cols);
 		const EdgeGrid::Grid::Cell &cell = m_cells[row * m_cols + col];
 		return std::make_pair(m_cell_data.begin() + cell.begin, m_cell_data.begin() + cell.end);
 	}
 
 	std::pair<const Slic3r::Point&, const Slic3r::Point&> segment(const std::pair<size_t, size_t> &contour_and_segment_idx) const
 	{
-		const Slic3r::Points &ipts = *m_contours[contour_and_segment_idx.first];
-		size_t ipt = contour_and_segment_idx.second;
-		return std::pair<const Slic3r::Point&, const Slic3r::Point&>(ipts[ipt], ipts[ipt + 1 == ipts.size() ? 0 : ipt + 1]);
+		const Contour &contour = m_contours[contour_and_segment_idx.first];
+		size_t iseg = contour_and_segment_idx.second;
+		return std::pair<const Slic3r::Point&, const Slic3r::Point&>(contour.segment_start(iseg), contour.segment_end(iseg));
 	}
 
 	Line line(const std::pair<size_t, size_t> &contour_and_segment_idx) const
 	{
-		const Slic3r::Points &ipts = *m_contours[contour_and_segment_idx.first];
-		size_t ipt = contour_and_segment_idx.second;
-		return Line(ipts[ipt], ipts[ipt + 1 == ipts.size() ? 0 : ipt + 1]);
+		const Contour &contour = m_contours[contour_and_segment_idx.first];
+		size_t iseg = contour_and_segment_idx.second;
+		return Line(contour.segment_start(iseg), contour.segment_end(iseg));
 	}
 
 protected:
@@ -297,13 +386,13 @@ protected:
 	BoundingBox 								m_bbox;
 	// Grid dimensions.
 	coord_t										m_resolution;
-	size_t										m_rows;
-	size_t										m_cols;
+	size_t										m_rows = 0;
+	size_t										m_cols = 0;
 
 	// Referencing the source contours.
 	// This format allows one to work with any Slic3r fixed point contour format
 	// (Polygon, ExPolygon, ExPolygonCollection etc).
-	std::vector<const Slic3r::Points*>			m_contours;
+	std::vector<Contour>						m_contours;
 
 	// Referencing a contour and a line segment of m_contours.
 	std::vector<std::pair<size_t, size_t> >		m_cell_data;