1 //Copyright (c) 2018 Ultimaker B.V.
2 //CuraEngine is released under the terms of the AGPLv3 or higher.
3
4 #ifndef INFILL_ZIGZAG_CONNECTOR_PROCESSOR_H
5 #define INFILL_ZIGZAG_CONNECTOR_PROCESSOR_H
6
7 #include "../utils/polygon.h" //TODO: We have implementation in this header file!
8
9 namespace cura
10 {
11
12 /*!
13 * Processor class for processing the connections between lines which makes the infill a zigzag pattern.
14 *
15 * During the creation of the infill lines, calls are made to a ZigzagConnectorProcessor so that the zigzag connector segments are created
16 * at the same time as the lines are created.
17 *
18 * generate lines within the area of [in_outline], at regular intervals of [line_distance]
19 * idea:
20 * intersect a regular grid of 'scanlines' with the area inside [in_outline] (see generateLineInfill)
21 * zigzag:
22 * include pieces of boundary, connecting the lines, forming an accordion like zigzag instead of separate lines |_|^|_|
23 *
24 * we call the areas between two consecutive scanlines a 'scansegment'
25 *
26 * algorithm:
27 * 1. for each line segment of each polygon:
28 * store the intersections of that line segment with all scanlines in a mapping (vector of vectors) from scanline to intersections
29 * (zigzag): add boundary segments to result
30 * 2. for each scanline:
31 * sort the associated intersections
32 * and connect them using the even-odd rule
33 *
34 * zigzag algorithm:
35 * while walking around (each) polygon (1.)
36 * if polygon intersects with even scanline
37 * start boundary segment (add each following segment to the [result])
38 * when polygon intersects with a scanline again
39 * stop boundary segment (stop adding segments to the [result])
40 * if polygon intersects with even scanline again (instead of odd)
41 * dont add the last line segment to the boundary (unless [connected_zigzags])
42 *
43 * Note that ZigZag consists of 3 types:
44 * - without endpieces
45 * - with disconnected endpieces
46 * - with connected endpieces
47 * <<extra>> there is also a NoZigzagConnector which creates no zags. It is used for the Line infill pattern
48 *
49 * v v zigzag connectors
50 * <--
51 * :___: : < scanlines
52 * | | |
53 * | | | < infill lines along scanlines
54 * | |___|
55 * : : :
56 * --> winding order of polygon
57 *
58 * ^ = even scanline
59 * ^ ^ no endpieces
60 *
61 * start boundary from even scanline! :D
62 * include only a boundary segment if it starts in an even scanline and ends in an odd scanline
63 *
64 * ________
65 * | | | \ .
66 * | | | |
67 * |_____| |__/ .
68 *
69 * ^ ^ ^ scanlines
70 * ^ connected end piece
71 * include a boundary segment also if it starts in an odd scanline and ends odd,
72 * or starts in an even scanline and ends in an even scanline,
73 * but not when it starts in an odd and ends in an even scanline (see top left or bottom middle).
74 *
75 * _____
76 * | | | \ .
77 * | | | |
78 * |_____| |__/
79 *
80 * ^ ^ ^ scanlines
81 * ^ disconnected end piece
82 * Leave out the last line segment of the boundary polygon: from a vertex to the linesegment-scanline intersection.
83 *
84 *
85 * Note that:
86 * (1) Micromovements:
87 * In the current ZigZag implementation, there can be some micro movements for the zag connectors.
88 * The points on a zag connector are first collected and then added to the result polygon when this
89 * zag connector has for sure reached its end (i.e., all the points on this zag connector is known).
90 * Based on the model, a zag connector can contain a lot of tiny lines which can cause micro movements
91 * if we added them all.
92 *
93 * To resolve this issue, we define a "minimum line length" for lines in a zag connector. If a line is
94 * shorter than the threshold, a second point (the "to" point) on this line will simply be ignored and
95 * the first point (the "from" point) will be kept as the starting point until there is a line that is
96 * long enough, and then that line will be added.
97 */
98 class ZigzagConnectorProcessor
99 {
100 public:
101 /*!
102 * Constructor.
103 *
104 * \param rotation_matrix The rotation matrix used to enforce the infill angle
105 * \param result The resulting line segments (Each line segment is a Polygon with 2 points)
106 * \param use_endpieces Whether to include end pieces or not
107 * \param connected_endpieces Whether the end pieces should be connected with the rest part of the infill
108 * \param skip_some_zags Whether to skip some zags
109 * \param zag_skip_count Skip 1 zag in every N zags
110 */
ZigzagConnectorProcessor(const PointMatrix & rotation_matrix,Polygons & result,bool use_endpieces,bool connected_endpieces,bool skip_some_zags,int zag_skip_count)111 ZigzagConnectorProcessor(const PointMatrix& rotation_matrix, Polygons& result,
112 bool use_endpieces, bool connected_endpieces,
113 bool skip_some_zags, int zag_skip_count)
114 : rotation_matrix(rotation_matrix)
115 , result(result)
116 , use_endpieces(use_endpieces)
117 , connected_endpieces(connected_endpieces)
118 , skip_some_zags(skip_some_zags)
119 , zag_skip_count(zag_skip_count)
120 , is_first_connector(true)
121 , first_connector_end_scanline_index(0)
122 , last_connector_index(0)
123 {}
124
~ZigzagConnectorProcessor()125 virtual ~ZigzagConnectorProcessor()
126 {}
127
128 /*!
129 * Handle the next vertex on the outer boundary.
130 * \param vertex The vertex
131 */
132 virtual void registerVertex(const Point& vertex);
133
134 /*!
135 * Handle the next intersection between a scanline and the outer boundary.
136 *
137 * \param intersection The intersection
138 * \param scanline_index Index of the current scanline
139 */
140 virtual void registerScanlineSegmentIntersection(const Point& intersection, int scanline_index);
141
142 /*!
143 * Handle the end of a polygon and prepare for the next.
144 * This function should reset all member variables.
145 */
146 virtual void registerPolyFinished();
147
148 protected:
149 /*!
150 * Reset the state so it can be used for processing another polygon.
151 */
152 void reset();
153
154 /*!
155 * Add a line to the result but not applying the rotation matrix.
156 *
157 * \param from The one end of the line segment
158 * \param to The other end of the line segment
159 */
160 void addLine(Point from, Point to);
161
162 /*!
163 * Checks whether the current connector should be added or not.
164 *
165 * \param start_scanline_idx the start scanline index of this scanline segment
166 * \param end_scanline_idx The the end scanline index of this scanline segment
167 */
168 bool shouldAddCurrentConnector(int start_scanline_idx, int end_scanline_idx) const;
169
170 /*!
171 * Checks whether two points are separated at least by "threshold" microns.
172 * If they are far away from each other enough, the line represented by the two points
173 * will be added; In case they are close, the second point will be set to be the same
174 * as the first and this line won't be added.
175 *
176 * \param first_point The first of the points
177 * \param second_point The second of the points
178 */
179 void checkAndAddZagConnectorLine(Point* first_point, Point* second_point);
180
181 /*!
182 * Adds a Zag connector represented by the given points. The last line of the connector will not be
183 * added if the given connector is an end piece and "connected_endpieces" is not enabled.
184 *
185 * \param points All the points on this connector
186 * \param is_endpiece Whether this connector is an end piece
187 */
188 void addZagConnector(std::vector<Point>& points, bool is_endpiece);
189
190 protected:
191 const PointMatrix& rotation_matrix; //!< The rotation matrix used to enforce the infill angle
192 Polygons& result; //!< The result of the computation
193
194 bool use_endpieces; //!< Whether to include end pieces or not
195 bool connected_endpieces; //!< Whether the end pieces should be connected with the rest part of the infill
196 int skip_some_zags; //!< Whether to skip some zags
197 int zag_skip_count; //!< Skip 1 zag in every N zags
198
199 bool is_first_connector; //!< indicating whether we are still looking for the first connector or not
200 int first_connector_end_scanline_index; //!< scanline segment index of the first connector
201 int last_connector_index; //!< scanline segment index of the last connector
202
203 /*!
204 * The line segments belonging the zigzag connector to which the very first vertex belongs.
205 * This will be combined with the last handled zigzag_connector, which combine to a whole zigzag connector.
206 *
207 * Because the boundary polygon may start in in the middle of a zigzag connector,
208 */
209 std::vector<Point> first_connector;
210 /*!
211 * The currently built up zigzag connector (not the first/last) or end piece or discarded boundary segment
212 */
213 std::vector<Point> current_connector;
214 };
215
216 //
217 // Inline functions
218 //
219
reset()220 inline void ZigzagConnectorProcessor::reset()
221 {
222 is_first_connector = true;
223 first_connector_end_scanline_index = 0;
224 last_connector_index = 0;
225 first_connector.clear();
226 current_connector.clear();
227 }
228
addLine(Point from,Point to)229 inline void ZigzagConnectorProcessor::addLine(Point from, Point to)
230 {
231 result.addLine(rotation_matrix.unapply(from), rotation_matrix.unapply(to));
232 }
233
234
235 } // namespace cura
236
237
238 #endif // INFILL_ZIGZAG_CONNECTOR_PROCESSOR_H
239