1 #include "ClipperUtils.hpp"
2 #include "ExtrusionEntityCollection.hpp"
3 #include "Layer.hpp"
4 #include "Print.hpp"
5 #include "SupportMaterial.hpp"
6 #include "Fill/FillBase.hpp"
7 #include "EdgeGrid.hpp"
8 #include "Geometry.hpp"
9
10 #include <cmath>
11 #include <memory>
12 #include <boost/log/trivial.hpp>
13
14 #include <tbb/parallel_for.h>
15 #include <tbb/spin_mutex.h>
16 #include <tbb/task_group.h>
17
18 // #define SLIC3R_DEBUG
19
20 // Make assert active if SLIC3R_DEBUG
21 #ifdef SLIC3R_DEBUG
22 #define DEBUG
23 #define _DEBUG
24 #undef NDEBUG
25 #include "SVG.hpp"
26 #endif
27
28 // #undef NDEBUG
29 #include <cassert>
30
31 namespace Slic3r {
32
33 // Increment used to reach MARGIN in steps to avoid trespassing thin objects
34 #define NUM_MARGIN_STEPS 3
35
36 // Dimensions of a tree-like structure to save material
37 #define PILLAR_SIZE (2.5)
38 #define PILLAR_SPACING 10
39
40 //#define SUPPORT_SURFACES_OFFSET_PARAMETERS ClipperLib::jtMiter, 3.
41 //#define SUPPORT_SURFACES_OFFSET_PARAMETERS ClipperLib::jtMiter, 1.5
42 #define SUPPORT_SURFACES_OFFSET_PARAMETERS ClipperLib::jtSquare, 0.
43
44 #ifdef SLIC3R_DEBUG
support_surface_type_to_color_name(const PrintObjectSupportMaterial::SupporLayerType surface_type)45 const char* support_surface_type_to_color_name(const PrintObjectSupportMaterial::SupporLayerType surface_type)
46 {
47 switch (surface_type) {
48 case PrintObjectSupportMaterial::sltTopContact: return "rgb(255,0,0)"; // "red";
49 case PrintObjectSupportMaterial::sltTopInterface: return "rgb(0,255,0)"; // "green";
50 case PrintObjectSupportMaterial::sltBase: return "rgb(0,0,255)"; // "blue";
51 case PrintObjectSupportMaterial::sltBottomInterface:return "rgb(255,255,128)"; // yellow
52 case PrintObjectSupportMaterial::sltBottomContact: return "rgb(255,0,255)"; // magenta
53 case PrintObjectSupportMaterial::sltRaftInterface: return "rgb(0,255,255)";
54 case PrintObjectSupportMaterial::sltRaftBase: return "rgb(128,128,128)";
55 case PrintObjectSupportMaterial::sltUnknown: return "rgb(128,0,0)"; // maroon
56 default: return "rgb(64,64,64)";
57 };
58 }
59
export_support_surface_type_legend_to_svg_box_size()60 Point export_support_surface_type_legend_to_svg_box_size()
61 {
62 return Point(scale_(1.+10.*8.), scale_(3.));
63 }
64
export_support_surface_type_legend_to_svg(SVG & svg,const Point & pos)65 void export_support_surface_type_legend_to_svg(SVG &svg, const Point &pos)
66 {
67 // 1st row
68 coord_t pos_x0 = pos(0) + scale_(1.);
69 coord_t pos_x = pos_x0;
70 coord_t pos_y = pos(1) + scale_(1.5);
71 coord_t step_x = scale_(10.);
72 svg.draw_legend(Point(pos_x, pos_y), "top contact" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltTopContact));
73 pos_x += step_x;
74 svg.draw_legend(Point(pos_x, pos_y), "top iface" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltTopInterface));
75 pos_x += step_x;
76 svg.draw_legend(Point(pos_x, pos_y), "base" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltBase));
77 pos_x += step_x;
78 svg.draw_legend(Point(pos_x, pos_y), "bottom iface" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltBottomInterface));
79 pos_x += step_x;
80 svg.draw_legend(Point(pos_x, pos_y), "bottom contact" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltBottomContact));
81 // 2nd row
82 pos_x = pos_x0;
83 pos_y = pos(1)+scale_(2.8);
84 svg.draw_legend(Point(pos_x, pos_y), "raft interface" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltRaftInterface));
85 pos_x += step_x;
86 svg.draw_legend(Point(pos_x, pos_y), "raft base" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltRaftBase));
87 pos_x += step_x;
88 svg.draw_legend(Point(pos_x, pos_y), "unknown" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltUnknown));
89 pos_x += step_x;
90 svg.draw_legend(Point(pos_x, pos_y), "intermediate" , support_surface_type_to_color_name(PrintObjectSupportMaterial::sltIntermediate));
91 }
92
export_print_z_polygons_to_svg(const char * path,PrintObjectSupportMaterial::MyLayer ** const layers,size_t n_layers)93 void export_print_z_polygons_to_svg(const char *path, PrintObjectSupportMaterial::MyLayer ** const layers, size_t n_layers)
94 {
95 BoundingBox bbox;
96 for (int i = 0; i < n_layers; ++ i)
97 bbox.merge(get_extents(layers[i]->polygons));
98 Point legend_size = export_support_surface_type_legend_to_svg_box_size();
99 Point legend_pos(bbox.min(0), bbox.max(1));
100 bbox.merge(Point(std::max(bbox.min(0) + legend_size(0), bbox.max(0)), bbox.max(1) + legend_size(1)));
101 SVG svg(path, bbox);
102 const float transparency = 0.5f;
103 for (int i = 0; i < n_layers; ++ i)
104 svg.draw(union_ex(layers[i]->polygons), support_surface_type_to_color_name(layers[i]->layer_type), transparency);
105 for (int i = 0; i < n_layers; ++ i)
106 svg.draw(to_polylines(layers[i]->polygons), support_surface_type_to_color_name(layers[i]->layer_type));
107 export_support_surface_type_legend_to_svg(svg, legend_pos);
108 svg.Close();
109 }
110
export_print_z_polygons_and_extrusions_to_svg(const char * path,PrintObjectSupportMaterial::MyLayer ** const layers,size_t n_layers,SupportLayer & support_layer)111 void export_print_z_polygons_and_extrusions_to_svg(
112 const char *path,
113 PrintObjectSupportMaterial::MyLayer ** const layers,
114 size_t n_layers,
115 SupportLayer &support_layer)
116 {
117 BoundingBox bbox;
118 for (int i = 0; i < n_layers; ++ i)
119 bbox.merge(get_extents(layers[i]->polygons));
120 Point legend_size = export_support_surface_type_legend_to_svg_box_size();
121 Point legend_pos(bbox.min(0), bbox.max(1));
122 bbox.merge(Point(std::max(bbox.min(0) + legend_size(0), bbox.max(0)), bbox.max(1) + legend_size(1)));
123 SVG svg(path, bbox);
124 const float transparency = 0.5f;
125 for (int i = 0; i < n_layers; ++ i)
126 svg.draw(union_ex(layers[i]->polygons), support_surface_type_to_color_name(layers[i]->layer_type), transparency);
127 for (int i = 0; i < n_layers; ++ i)
128 svg.draw(to_polylines(layers[i]->polygons), support_surface_type_to_color_name(layers[i]->layer_type));
129
130 Polygons polygons_support, polygons_interface;
131 support_layer.support_fills.polygons_covered_by_width(polygons_support, SCALED_EPSILON);
132 // support_layer.support_interface_fills.polygons_covered_by_width(polygons_interface, SCALED_EPSILON);
133 svg.draw(union_ex(polygons_support), "brown");
134 svg.draw(union_ex(polygons_interface), "black");
135
136 export_support_surface_type_legend_to_svg(svg, legend_pos);
137 svg.Close();
138 }
139 #endif /* SLIC3R_DEBUG */
140
PrintObjectSupportMaterial(const PrintObject * object,const SlicingParameters & slicing_params)141 PrintObjectSupportMaterial::PrintObjectSupportMaterial(const PrintObject *object, const SlicingParameters &slicing_params) :
142 m_object (object),
143 m_print_config (&object->print()->config()),
144 m_object_config (&object->config()),
145 m_slicing_params (slicing_params),
146 m_first_layer_flow (support_material_1st_layer_flow(object, float(slicing_params.first_print_layer_height))),
147 m_support_material_flow (support_material_flow(object, float(slicing_params.layer_height))),
148 m_support_material_interface_flow(support_material_interface_flow(object, float(slicing_params.layer_height))),
149 m_support_layer_height_min(0.01)
150 {
151 // Calculate a minimum support layer height as a minimum over all extruders, but not smaller than 10um.
152 m_support_layer_height_min = 1000000.;
153 for (auto lh : m_print_config->min_layer_height.values)
154 m_support_layer_height_min = std::min(m_support_layer_height_min, std::max(0.01, lh));
155
156 if (m_object_config->support_material_interface_layers.value == 0) {
157 // No interface layers allowed, print everything with the base support pattern.
158 m_support_material_interface_flow = m_support_material_flow;
159 }
160
161 // Evaluate the XY gap between the object outer perimeters and the support structures.
162 // Evaluate the XY gap between the object outer perimeters and the support structures.
163 coordf_t external_perimeter_width = 0.;
164 for (size_t region_id = 0; region_id < object->region_volumes.size(); ++ region_id)
165 if (! object->region_volumes[region_id].empty())
166 external_perimeter_width = std::max(external_perimeter_width,
167 (coordf_t)object->print()->get_region(region_id)->flow(frExternalPerimeter, slicing_params.layer_height, false, false, -1, *object).width);
168 m_gap_xy = m_object_config->support_material_xy_spacing.get_abs_value(external_perimeter_width);
169
170 m_can_merge_support_regions = m_object_config->support_material_extruder.value == m_object_config->support_material_interface_extruder.value;
171 if (! m_can_merge_support_regions && (m_object_config->support_material_extruder.value == 0 || m_object_config->support_material_interface_extruder.value == 0)) {
172 // One of the support extruders is of "don't care" type.
173 auto object_extruders = m_object->print()->object_extruders();
174 if (object_extruders.size() == 1 &&
175 *object_extruders.begin() == std::max<unsigned int>(m_object_config->support_material_extruder.value, m_object_config->support_material_interface_extruder.value))
176 // Object is printed with the same extruder as the support.
177 m_can_merge_support_regions = true;
178 }
179 }
180
181 // Using the std::deque as an allocator.
layer_allocate(std::deque<PrintObjectSupportMaterial::MyLayer> & layer_storage,PrintObjectSupportMaterial::SupporLayerType layer_type)182 inline PrintObjectSupportMaterial::MyLayer& layer_allocate(
183 std::deque<PrintObjectSupportMaterial::MyLayer> &layer_storage,
184 PrintObjectSupportMaterial::SupporLayerType layer_type)
185 {
186 layer_storage.push_back(PrintObjectSupportMaterial::MyLayer());
187 layer_storage.back().layer_type = layer_type;
188 return layer_storage.back();
189 }
190
layer_allocate(std::deque<PrintObjectSupportMaterial::MyLayer> & layer_storage,tbb::spin_mutex & layer_storage_mutex,PrintObjectSupportMaterial::SupporLayerType layer_type)191 inline PrintObjectSupportMaterial::MyLayer& layer_allocate(
192 std::deque<PrintObjectSupportMaterial::MyLayer> &layer_storage,
193 tbb::spin_mutex &layer_storage_mutex,
194 PrintObjectSupportMaterial::SupporLayerType layer_type)
195 {
196 layer_storage_mutex.lock();
197 layer_storage.push_back(PrintObjectSupportMaterial::MyLayer());
198 PrintObjectSupportMaterial::MyLayer *layer_new = &layer_storage.back();
199 layer_storage_mutex.unlock();
200 layer_new->layer_type = layer_type;
201 return *layer_new;
202 }
203
layers_append(PrintObjectSupportMaterial::MyLayersPtr & dst,const PrintObjectSupportMaterial::MyLayersPtr & src)204 inline void layers_append(PrintObjectSupportMaterial::MyLayersPtr &dst, const PrintObjectSupportMaterial::MyLayersPtr &src)
205 {
206 dst.insert(dst.end(), src.begin(), src.end());
207 }
208
209 // Compare layers lexicographically.
210 struct MyLayersPtrCompare
211 {
operator ()Slic3r::MyLayersPtrCompare212 bool operator()(const PrintObjectSupportMaterial::MyLayer* layer1, const PrintObjectSupportMaterial::MyLayer* layer2) const {
213 return *layer1 < *layer2;
214 }
215 };
216
generate(PrintObject & object)217 void PrintObjectSupportMaterial::generate(PrintObject &object)
218 {
219 BOOST_LOG_TRIVIAL(info) << "Support generator - Start";
220
221 coordf_t max_object_layer_height = 0.;
222 for (size_t i = 0; i < object.layer_count(); ++ i)
223 max_object_layer_height = std::max(max_object_layer_height, object.layers()[i]->height);
224
225 // Layer instances will be allocated by std::deque and they will be kept until the end of this function call.
226 // The layers will be referenced by various LayersPtr (of type std::vector<Layer*>)
227 MyLayerStorage layer_storage;
228
229 BOOST_LOG_TRIVIAL(info) << "Support generator - Creating top contacts";
230
231 // Determine the top contact surfaces of the support, defined as:
232 // contact = overhangs - clearance + margin
233 // This method is responsible for identifying what contact surfaces
234 // should the support material expose to the object in order to guarantee
235 // that it will be effective, regardless of how it's built below.
236 // If raft is to be generated, the 1st top_contact layer will contain the 1st object layer silhouette without holes.
237 MyLayersPtr top_contacts = this->top_contact_layers(object, layer_storage);
238 if (top_contacts.empty())
239 // Nothing is supported, no supports are generated.
240 return;
241
242 #ifdef SLIC3R_DEBUG
243 static int iRun = 0;
244 iRun ++;
245 for (const MyLayer *layer : top_contacts)
246 Slic3r::SVG::export_expolygons(
247 debug_out_path("support-top-contacts-%d-%lf.svg", iRun, layer->print_z),
248 union_ex(layer->polygons, false));
249 #endif /* SLIC3R_DEBUG */
250
251 BOOST_LOG_TRIVIAL(info) << "Support generator - Creating bottom contacts";
252
253 // Determine the bottom contact surfaces of the supports over the top surfaces of the object.
254 // Depending on whether the support is soluble or not, the contact layer thickness is decided.
255 // layer_support_areas contains the per object layer support areas. These per object layer support areas
256 // may get merged and trimmed by this->generate_base_layers() if the support layers are not synchronized with object layers.
257 std::vector<Polygons> layer_support_areas;
258 MyLayersPtr bottom_contacts = this->bottom_contact_layers_and_layer_support_areas(
259 object, top_contacts, layer_storage,
260 layer_support_areas);
261
262 #ifdef SLIC3R_DEBUG
263 for (size_t layer_id = 0; layer_id < object.layers().size(); ++ layer_id)
264 Slic3r::SVG::export_expolygons(
265 debug_out_path("support-areas-%d-%lf.svg", iRun, object.layers()[layer_id]->print_z),
266 union_ex(layer_support_areas[layer_id], false));
267 #endif /* SLIC3R_DEBUG */
268
269 BOOST_LOG_TRIVIAL(info) << "Support generator - Creating intermediate layers - indices";
270
271 // Allocate empty layers between the top / bottom support contact layers
272 // as placeholders for the base and intermediate support layers.
273 // The layers may or may not be synchronized with the object layers, depending on the configuration.
274 // For example, a single nozzle multi material printing will need to generate a waste tower, which in turn
275 // wastes less material, if there are as little tool changes as possible.
276 MyLayersPtr intermediate_layers = this->raft_and_intermediate_support_layers(
277 object, bottom_contacts, top_contacts, layer_storage);
278
279 // this->trim_support_layers_by_object(object, top_contacts, m_slicing_params.soluble_interface ? 0. : m_support_layer_height_min, 0., m_gap_xy);
280 this->trim_support_layers_by_object(object, top_contacts,
281 m_slicing_params.soluble_interface ? 0. : m_object_config->support_material_contact_distance.value,
282 m_slicing_params.soluble_interface ? 0. : m_object_config->support_material_contact_distance.value, m_gap_xy);
283
284 #ifdef SLIC3R_DEBUG
285 for (const MyLayer *layer : top_contacts)
286 Slic3r::SVG::export_expolygons(
287 debug_out_path("support-top-contacts-trimmed-by-object-%d-%lf.svg", iRun, layer->print_z),
288 union_ex(layer->polygons, false));
289 #endif
290
291 BOOST_LOG_TRIVIAL(info) << "Support generator - Creating base layers";
292
293 // Fill in intermediate layers between the top / bottom support contact layers, trimm them by the object.
294 this->generate_base_layers(object, bottom_contacts, top_contacts, intermediate_layers, layer_support_areas);
295
296 #ifdef SLIC3R_DEBUG
297 for (MyLayersPtr::const_iterator it = intermediate_layers.begin(); it != intermediate_layers.end(); ++ it)
298 Slic3r::SVG::export_expolygons(
299 debug_out_path("support-base-layers-%d-%lf.svg", iRun, (*it)->print_z),
300 union_ex((*it)->polygons, false));
301 #endif /* SLIC3R_DEBUG */
302
303 BOOST_LOG_TRIVIAL(info) << "Support generator - Trimming top contacts by bottom contacts";
304
305 // Because the top and bottom contacts are thick slabs, they may overlap causing over extrusion
306 // and unwanted strong bonds to the object.
307 // Rather trim the top contacts by their overlapping bottom contacts to leave a gap instead of over extruding
308 // top contacts over the bottom contacts.
309 this->trim_top_contacts_by_bottom_contacts(object, bottom_contacts, top_contacts);
310
311
312 BOOST_LOG_TRIVIAL(info) << "Support generator - Creating interfaces";
313
314 // Propagate top / bottom contact layers to generate interface layers.
315 MyLayersPtr interface_layers = this->generate_interface_layers(
316 bottom_contacts, top_contacts, intermediate_layers, layer_storage);
317
318 BOOST_LOG_TRIVIAL(info) << "Support generator - Creating raft";
319
320 // If raft is to be generated, the 1st top_contact layer will contain the 1st object layer silhouette with holes filled.
321 // There is also a 1st intermediate layer containing bases of support columns.
322 // Inflate the bases of the support columns and create the raft base under the object.
323 MyLayersPtr raft_layers = this->generate_raft_base(top_contacts, interface_layers, intermediate_layers, layer_storage);
324
325 #ifdef SLIC3R_DEBUG
326 for (MyLayersPtr::const_iterator it = interface_layers.begin(); it != interface_layers.end(); ++ it)
327 Slic3r::SVG::export_expolygons(
328 debug_out_path("support-interface-layers-%d-%lf.svg", iRun, (*it)->print_z),
329 union_ex((*it)->polygons, false));
330 #endif /* SLIC3R_DEBUG */
331
332 /*
333 // Clip with the pillars.
334 if (! shape.empty()) {
335 this->clip_with_shape(interface, shape);
336 this->clip_with_shape(base, shape);
337 }
338 */
339
340 BOOST_LOG_TRIVIAL(info) << "Support generator - Creating layers";
341
342 // For debugging purposes, one may want to show only some of the support extrusions.
343 // raft_layers.clear();
344 // bottom_contacts.clear();
345 // top_contacts.clear();
346 // intermediate_layers.clear();
347 // interface_layers.clear();
348
349 // Install support layers into the object.
350 // A support layer installed on a PrintObject has a unique print_z.
351 MyLayersPtr layers_sorted;
352 layers_sorted.reserve(raft_layers.size() + bottom_contacts.size() + top_contacts.size() + intermediate_layers.size() + interface_layers.size());
353 layers_append(layers_sorted, raft_layers);
354 layers_append(layers_sorted, bottom_contacts);
355 layers_append(layers_sorted, top_contacts);
356 layers_append(layers_sorted, intermediate_layers);
357 layers_append(layers_sorted, interface_layers);
358 // Sort the layers lexicographically by a raising print_z and a decreasing height.
359 std::sort(layers_sorted.begin(), layers_sorted.end(), MyLayersPtrCompare());
360 int layer_id = 0;
361 assert(object.support_layers().empty());
362 for (size_t i = 0; i < layers_sorted.size();) {
363 // Find the last layer with roughly the same print_z, find the minimum layer height of all.
364 // Due to the floating point inaccuracies, the print_z may not be the same even if in theory they should.
365 size_t j = i + 1;
366 coordf_t zmax = layers_sorted[i]->print_z + EPSILON;
367 for (; j < layers_sorted.size() && layers_sorted[j]->print_z <= zmax; ++j) ;
368 // Assign an average print_z to the set of layers with nearly equal print_z.
369 coordf_t zavg = 0.5 * (layers_sorted[i]->print_z + layers_sorted[j - 1]->print_z);
370 coordf_t height_min = layers_sorted[i]->height;
371 bool empty = true;
372 for (size_t u = i; u < j; ++u) {
373 MyLayer &layer = *layers_sorted[u];
374 if (! layer.polygons.empty())
375 empty = false;
376 layer.print_z = zavg;
377 height_min = std::min(height_min, layer.height);
378 }
379 if (! empty) {
380 // Here the upper_layer and lower_layer pointers are left to null at the support layers,
381 // as they are never used. These pointers are candidates for removal.
382 object.add_support_layer(layer_id ++, height_min, zavg);
383 }
384 i = j;
385 }
386
387 BOOST_LOG_TRIVIAL(info) << "Support generator - Generating tool paths";
388
389 // Generate the actual toolpaths and save them into each layer.
390 this->generate_toolpaths(object, raft_layers, bottom_contacts, top_contacts, intermediate_layers, interface_layers);
391
392 #ifdef SLIC3R_DEBUG
393 {
394 size_t layer_id = 0;
395 for (int i = 0; i < int(layers_sorted.size());) {
396 // Find the last layer with roughly the same print_z, find the minimum layer height of all.
397 // Due to the floating point inaccuracies, the print_z may not be the same even if in theory they should.
398 int j = i + 1;
399 coordf_t zmax = layers_sorted[i]->print_z + EPSILON;
400 bool empty = true;
401 for (; j < layers_sorted.size() && layers_sorted[j]->print_z <= zmax; ++j)
402 if (! layers_sorted[j]->polygons.empty())
403 empty = false;
404 if (! empty) {
405 export_print_z_polygons_to_svg(
406 debug_out_path("support-%d-%lf.svg", iRun, layers_sorted[i]->print_z).c_str(),
407 layers_sorted.data() + i, j - i);
408 export_print_z_polygons_and_extrusions_to_svg(
409 debug_out_path("support-w-fills-%d-%lf.svg", iRun, layers_sorted[i]->print_z).c_str(),
410 layers_sorted.data() + i, j - i,
411 *object.support_layers()[layer_id]);
412 ++layer_id;
413 }
414 i = j;
415 }
416 }
417 #endif /* SLIC3R_DEBUG */
418
419 BOOST_LOG_TRIVIAL(info) << "Support generator - End";
420 }
421
422 // Collect all polygons of all regions in a layer with a given surface type.
collect_region_slices_by_type(const Layer & layer,SurfaceType surface_type)423 Polygons collect_region_slices_by_type(const Layer &layer, SurfaceType surface_type)
424 {
425 // 1) Count the new polygons first.
426 size_t n_polygons_new = 0;
427 for (const LayerRegion *region : layer.regions())
428 for (const Surface &surface : region->slices.surfaces)
429 if (surface.surface_type == surface_type)
430 n_polygons_new += surface.expolygon.holes.size() + 1;
431 // 2) Collect the new polygons.
432 Polygons out;
433 out.reserve(n_polygons_new);
434 for (const LayerRegion *region : layer.regions())
435 for (const Surface &surface : region->slices.surfaces)
436 if (surface.surface_type == surface_type)
437 polygons_append(out, surface.expolygon);
438 return out;
439 }
440
441 // Collect outer contours of all slices of this layer.
442 // This is useful for calculating the support base with holes filled.
collect_slices_outer(const Layer & layer)443 Polygons collect_slices_outer(const Layer &layer)
444 {
445 Polygons out;
446 out.reserve(out.size() + layer.lslices.size());
447 for (const ExPolygon &expoly : layer.lslices)
448 out.emplace_back(expoly.contour);
449 return out;
450 }
451
452 class SupportGridPattern
453 {
454 public:
455 // Achtung! The support_polygons need to be trimmed by trimming_polygons, otherwise
456 // the selection by island_samples (see the island_samples() method) will not work!
SupportGridPattern(const Polygons & support_polygons,const Polygons & trimming_polygons,coordf_t support_spacing,coordf_t support_angle)457 SupportGridPattern(
458 // Support islands, to be stretched into a grid. Already trimmed with min(lower_layer_offset, m_gap_xy)
459 const Polygons &support_polygons,
460 // Trimming polygons, to trim the stretched support islands. support_polygons were already trimmed with trimming_polygons.
461 const Polygons &trimming_polygons,
462 // Grid spacing, given by "support_material_spacing" + m_support_material_flow.spacing()
463 coordf_t support_spacing,
464 coordf_t support_angle) :
465 m_support_polygons(&support_polygons), m_trimming_polygons(&trimming_polygons),
466 m_support_spacing(support_spacing), m_support_angle(support_angle)
467 {
468 if (m_support_angle != 0.) {
469 // Create a copy of the rotated contours.
470 m_support_polygons_rotated = support_polygons;
471 m_trimming_polygons_rotated = trimming_polygons;
472 m_support_polygons = &m_support_polygons_rotated;
473 m_trimming_polygons = &m_trimming_polygons_rotated;
474 polygons_rotate(m_support_polygons_rotated, - support_angle);
475 polygons_rotate(m_trimming_polygons_rotated, - support_angle);
476 }
477 // Create an EdgeGrid, initialize it with projection, initialize signed distance field.
478 coord_t grid_resolution = coord_t(scale_(m_support_spacing));
479 BoundingBox bbox = get_extents(*m_support_polygons);
480 bbox.offset(20);
481 bbox.align_to_grid(grid_resolution);
482 m_grid.set_bbox(bbox);
483 m_grid.create(*m_support_polygons, grid_resolution);
484 #if 0
485 if (m_grid.has_intersecting_edges()) {
486 // EdgeGrid fails to produce valid signed distance function for self-intersecting polygons.
487 m_support_polygons_rotated = simplify_polygons(*m_support_polygons);
488 m_support_polygons = &m_support_polygons_rotated;
489 m_grid.set_bbox(bbox);
490 m_grid.create(*m_support_polygons, grid_resolution);
491 // assert(! m_grid.has_intersecting_edges());
492 printf("SupportGridPattern: fixing polygons with intersection %s\n",
493 m_grid.has_intersecting_edges() ? "FAILED" : "SUCCEEDED");
494 }
495 #endif
496 m_grid.calculate_sdf();
497 // Sample a single point per input support polygon, keep it as a reference to maintain corresponding
498 // polygons if ever these polygons get split into parts by the trimming polygons.
499 m_island_samples = island_samples(*m_support_polygons);
500 }
501
502 // Extract polygons from the grid, offsetted by offset_in_grid,
503 // and trim the extracted polygons by trimming_polygons.
504 // Trimming by the trimming_polygons may split the extracted polygons into pieces.
505 // Remove all the pieces, which do not contain any of the island_samples.
extract_support(const coord_t offset_in_grid,bool fill_holes)506 Polygons extract_support(const coord_t offset_in_grid, bool fill_holes)
507 {
508 // Generate islands, so each island may be tested for overlap with m_island_samples.
509 assert(std::abs(2 * offset_in_grid) < m_grid.resolution());
510 #ifdef SLIC3R_DEBUG
511 Polygons support_polygons_simplified = m_grid.contours_simplified(offset_in_grid, fill_holes);
512 ExPolygons islands = diff_ex(support_polygons_simplified, *m_trimming_polygons, false);
513 #else
514 ExPolygons islands = diff_ex(m_grid.contours_simplified(offset_in_grid, fill_holes), *m_trimming_polygons, false);
515 #endif
516
517 // Extract polygons, which contain some of the m_island_samples.
518 Polygons out;
519 for (ExPolygon &island : islands) {
520 BoundingBox bbox = get_extents(island.contour);
521 // Samples are sorted lexicographically.
522 auto it_lower = std::lower_bound(m_island_samples.begin(), m_island_samples.end(), Point(bbox.min - Point(1, 1)));
523 auto it_upper = std::upper_bound(m_island_samples.begin(), m_island_samples.end(), Point(bbox.max + Point(1, 1)));
524 std::vector<std::pair<Point,bool>> samples_inside;
525 for (auto it = it_lower; it != it_upper; ++ it)
526 if (bbox.contains(*it))
527 samples_inside.push_back(std::make_pair(*it, false));
528 if (! samples_inside.empty()) {
529 // For all samples_inside count the boundary crossing.
530 for (size_t i_contour = 0; i_contour <= island.holes.size(); ++ i_contour) {
531 Polygon &contour = (i_contour == 0) ? island.contour : island.holes[i_contour - 1];
532 Points::const_iterator i = contour.points.begin();
533 Points::const_iterator j = contour.points.end() - 1;
534 for (; i != contour.points.end(); j = i ++) {
535 //FIXME this test is not numerically robust. Particularly, it does not handle horizontal segments at y == point(1) well.
536 // Does the ray with y == point(1) intersect this line segment?
537 for (auto &sample_inside : samples_inside) {
538 if (((*i)(1) > sample_inside.first(1)) != ((*j)(1) > sample_inside.first(1))) {
539 double x1 = (double)sample_inside.first(0);
540 double x2 = (double)(*i)(0) + (double)((*j)(0) - (*i)(0)) * (double)(sample_inside.first(1) - (*i)(1)) / (double)((*j)(1) - (*i)(1));
541 if (x1 < x2)
542 sample_inside.second = !sample_inside.second;
543 }
544 }
545 }
546 }
547 // If any of the sample is inside this island, add this island to the output.
548 for (auto &sample_inside : samples_inside)
549 if (sample_inside.second) {
550 polygons_append(out, std::move(island));
551 island.clear();
552 break;
553 }
554 }
555 }
556
557 #ifdef SLIC3R_DEBUG
558 static int iRun = 0;
559 ++iRun;
560 BoundingBox bbox = get_extents(*m_trimming_polygons);
561 if (! islands.empty())
562 bbox.merge(get_extents(islands));
563 if (!out.empty())
564 bbox.merge(get_extents(out));
565 if (!support_polygons_simplified.empty())
566 bbox.merge(get_extents(support_polygons_simplified));
567 SVG svg(debug_out_path("extract_support_from_grid_trimmed-%d.svg", iRun).c_str(), bbox);
568 svg.draw(union_ex(support_polygons_simplified), "gray", 0.25f);
569 svg.draw(islands, "red", 0.5f);
570 svg.draw(union_ex(out), "green", 0.5f);
571 svg.draw(union_ex(*m_support_polygons), "blue", 0.5f);
572 svg.draw_outline(islands, "red", "red", scale_(0.05));
573 svg.draw_outline(union_ex(out), "green", "green", scale_(0.05));
574 svg.draw_outline(union_ex(*m_support_polygons), "blue", "blue", scale_(0.05));
575 for (const Point &pt : m_island_samples)
576 svg.draw(pt, "black", coord_t(scale_(0.15)));
577 svg.Close();
578 #endif /* SLIC3R_DEBUG */
579
580 if (m_support_angle != 0.)
581 polygons_rotate(out, m_support_angle);
582 return out;
583 }
584
585 #ifdef SLIC3R_DEBUG
serialize(const std::string & path)586 void serialize(const std::string &path)
587 {
588 FILE *file = ::fopen(path.c_str(), "wb");
589 ::fwrite(&m_support_spacing, 8, 1, file);
590 ::fwrite(&m_support_angle, 8, 1, file);
591 uint32_t n_polygons = m_support_polygons->size();
592 ::fwrite(&n_polygons, 4, 1, file);
593 for (uint32_t i = 0; i < n_polygons; ++ i) {
594 const Polygon &poly = (*m_support_polygons)[i];
595 uint32_t n_points = poly.size();
596 ::fwrite(&n_points, 4, 1, file);
597 for (uint32_t j = 0; j < n_points; ++ j) {
598 const Point &pt = poly.points[j];
599 ::fwrite(&pt.x(), sizeof(coord_t), 1, file);
600 ::fwrite(&pt.y(), sizeof(coord_t), 1, file);
601 }
602 }
603 n_polygons = m_trimming_polygons->size();
604 ::fwrite(&n_polygons, 4, 1, file);
605 for (uint32_t i = 0; i < n_polygons; ++ i) {
606 const Polygon &poly = (*m_trimming_polygons)[i];
607 uint32_t n_points = poly.size();
608 ::fwrite(&n_points, 4, 1, file);
609 for (uint32_t j = 0; j < n_points; ++ j) {
610 const Point &pt = poly.points[j];
611 ::fwrite(&pt.x(), sizeof(coord_t), 1, file);
612 ::fwrite(&pt.y(), sizeof(coord_t), 1, file);
613 }
614 }
615 ::fclose(file);
616 }
617
deserialize(const std::string & path,int which=-1)618 static SupportGridPattern deserialize(const std::string &path, int which = -1)
619 {
620 SupportGridPattern out;
621 out.deserialize_(path, which);
622 return out;
623 }
624
625 // Deserialization constructor
deserialize_(const std::string & path,int which=-1)626 bool deserialize_(const std::string &path, int which = -1)
627 {
628 FILE *file = ::fopen(path.c_str(), "rb");
629 if (file == nullptr)
630 return false;
631
632 m_support_polygons = &m_support_polygons_deserialized;
633 m_trimming_polygons = &m_trimming_polygons_deserialized;
634
635 ::fread(&m_support_spacing, 8, 1, file);
636 ::fread(&m_support_angle, 8, 1, file);
637 //FIXME
638 //m_support_spacing *= 0.01 / 2;
639 uint32_t n_polygons;
640 ::fread(&n_polygons, 4, 1, file);
641 m_support_polygons_deserialized.reserve(n_polygons);
642 int32_t scale = 1;
643 for (uint32_t i = 0; i < n_polygons; ++ i) {
644 Polygon poly;
645 uint32_t n_points;
646 ::fread(&n_points, 4, 1, file);
647 poly.points.reserve(n_points);
648 for (uint32_t j = 0; j < n_points; ++ j) {
649 coord_t x, y;
650 ::fread(&x, sizeof(coord_t), 1, file);
651 ::fread(&y, sizeof(coord_t), 1, file);
652 poly.points.emplace_back(Point(x * scale, y * scale));
653 }
654 if (which == -1 || which == i)
655 m_support_polygons_deserialized.emplace_back(std::move(poly));
656 printf("Polygon %d, area: %lf\n", i, area(poly.points));
657 }
658 ::fread(&n_polygons, 4, 1, file);
659 m_trimming_polygons_deserialized.reserve(n_polygons);
660 for (uint32_t i = 0; i < n_polygons; ++ i) {
661 Polygon poly;
662 uint32_t n_points;
663 ::fread(&n_points, 4, 1, file);
664 poly.points.reserve(n_points);
665 for (uint32_t j = 0; j < n_points; ++ j) {
666 coord_t x, y;
667 ::fread(&x, sizeof(coord_t), 1, file);
668 ::fread(&y, sizeof(coord_t), 1, file);
669 poly.points.emplace_back(Point(x * scale, y * scale));
670 }
671 m_trimming_polygons_deserialized.emplace_back(std::move(poly));
672 }
673 ::fclose(file);
674
675 m_support_polygons_deserialized = simplify_polygons(m_support_polygons_deserialized, false);
676 //m_support_polygons_deserialized = to_polygons(union_ex(m_support_polygons_deserialized, false));
677
678 // Create an EdgeGrid, initialize it with projection, initialize signed distance field.
679 coord_t grid_resolution = coord_t(scale_(m_support_spacing));
680 BoundingBox bbox = get_extents(*m_support_polygons);
681 bbox.offset(20);
682 bbox.align_to_grid(grid_resolution);
683 m_grid.set_bbox(bbox);
684 m_grid.create(*m_support_polygons, grid_resolution);
685 m_grid.calculate_sdf();
686 // Sample a single point per input support polygon, keep it as a reference to maintain corresponding
687 // polygons if ever these polygons get split into parts by the trimming polygons.
688 m_island_samples = island_samples(*m_support_polygons);
689 return true;
690 }
691
support_polygons() const692 const Polygons& support_polygons() const { return *m_support_polygons; }
trimming_polygons() const693 const Polygons& trimming_polygons() const { return *m_trimming_polygons; }
grid() const694 const EdgeGrid::Grid& grid() const { return m_grid; }
695
696 #endif /* SLIC3R_DEBUG */
697
698 private:
SupportGridPattern()699 SupportGridPattern() {}
700 SupportGridPattern& operator=(const SupportGridPattern &rhs);
701
702 #if 0
703 // Get some internal point of an expolygon, to be used as a representative
704 // sample to test, whether this island is inside another island.
705 //FIXME this was quick, but not sufficiently robust.
706 static Point island_sample(const ExPolygon &expoly)
707 {
708 // Find the lowest point lexicographically.
709 const Point *pt_min = &expoly.contour.points.front();
710 for (size_t i = 1; i < expoly.contour.points.size(); ++ i)
711 if (expoly.contour.points[i] < *pt_min)
712 pt_min = &expoly.contour.points[i];
713
714 // Lowest corner will always be convex, in worst case denegenerate with zero angle.
715 const Point &p1 = (pt_min == &expoly.contour.points.front()) ? expoly.contour.points.back() : *(pt_min - 1);
716 const Point &p2 = *pt_min;
717 const Point &p3 = (pt_min == &expoly.contour.points.back()) ? expoly.contour.points.front() : *(pt_min + 1);
718
719 Vector v = (p3 - p2) + (p1 - p2);
720 double l2 = double(v(0))*double(v(0))+double(v(1))*double(v(1));
721 if (l2 == 0.)
722 return p2;
723 double coef = 20. / sqrt(l2);
724 return Point(p2(0) + coef * v(0), p2(1) + coef * v(1));
725 }
726 #endif
727
728 // Sample one internal point per expolygon.
729 // FIXME this is quite an overkill to calculate a complete offset just to get a single point, but at least it is robust.
island_samples(const ExPolygons & expolygons)730 static Points island_samples(const ExPolygons &expolygons)
731 {
732 Points pts;
733 pts.reserve(expolygons.size());
734 for (const ExPolygon &expoly : expolygons)
735 if (expoly.contour.points.size() > 2) {
736 #if 0
737 pts.push_back(island_sample(expoly));
738 #else
739 Polygons polygons = offset(expoly, - 20.f);
740 for (const Polygon &poly : polygons)
741 if (! poly.points.empty()) {
742 pts.push_back(poly.points.front());
743 break;
744 }
745 #endif
746 }
747 // Sort the points lexicographically, so a binary search could be used to locate points inside a bounding box.
748 std::sort(pts.begin(), pts.end());
749 return pts;
750 }
751
island_samples(const Polygons & polygons)752 static Points island_samples(const Polygons &polygons)
753 {
754 return island_samples(union_ex(polygons));
755 }
756
757 const Polygons *m_support_polygons;
758 const Polygons *m_trimming_polygons;
759 Polygons m_support_polygons_rotated;
760 Polygons m_trimming_polygons_rotated;
761 // Angle in radians, by which the whole support is rotated.
762 coordf_t m_support_angle;
763 // X spacing of the support lines parallel with the Y axis.
764 coordf_t m_support_spacing;
765
766 Slic3r::EdgeGrid::Grid m_grid;
767 // Internal sample points of supporting expolygons. These internal points are used to pick regions corresponding
768 // to the initial supporting regions, after these regions werre grown and possibly split to many by the trimming polygons.
769 Points m_island_samples;
770
771 #ifdef SLIC3R_DEBUG
772 // support for deserialization of m_support_polygons, m_trimming_polygons
773 Polygons m_support_polygons_deserialized;
774 Polygons m_trimming_polygons_deserialized;
775 #endif /* SLIC3R_DEBUG */
776 };
777
778 namespace SupportMaterialInternal {
has_bridging_perimeters(const ExtrusionLoop & loop)779 static inline bool has_bridging_perimeters(const ExtrusionLoop &loop)
780 {
781 for (const ExtrusionPath &ep : loop.paths)
782 if (ep.role() == erOverhangPerimeter && ! ep.polyline.empty())
783 return ep.size() >= (ep.is_closed() ? 3 : 2);
784 return false;
785 }
has_bridging_perimeters(const ExtrusionEntityCollection & perimeters)786 static bool has_bridging_perimeters(const ExtrusionEntityCollection &perimeters)
787 {
788 for (const ExtrusionEntity *ee : perimeters.entities) {
789 if (ee->is_collection()) {
790 for (const ExtrusionEntity *ee2 : static_cast<const ExtrusionEntityCollection*>(ee)->entities) {
791 assert(! ee2->is_collection());
792 if (ee2->is_loop())
793 if (has_bridging_perimeters(*static_cast<const ExtrusionLoop*>(ee2)))
794 return true;
795 }
796 } else if (ee->is_loop() && has_bridging_perimeters(*static_cast<const ExtrusionLoop*>(ee)))
797 return true;
798 }
799 return false;
800 }
has_bridging_fills(const ExtrusionEntityCollection & fills)801 static bool has_bridging_fills(const ExtrusionEntityCollection &fills)
802 {
803 for (const ExtrusionEntity *ee : fills.entities) {
804 assert(ee->is_collection());
805 for (const ExtrusionEntity *ee2 : static_cast<const ExtrusionEntityCollection*>(ee)->entities) {
806 assert(! ee2->is_collection());
807 assert(! ee2->is_loop());
808 if (ee2->role() == erBridgeInfill)
809 return true;
810 }
811 }
812 return false;
813 }
has_bridging_extrusions(const Layer & layer)814 static bool has_bridging_extrusions(const Layer &layer)
815 {
816 for (const LayerRegion *region : layer.regions()) {
817 if (SupportMaterialInternal::has_bridging_perimeters(region->perimeters))
818 return true;
819 if (region->fill_surfaces.has(stBottomBridge) && has_bridging_fills(region->fills))
820 return true;
821 }
822 return false;
823 }
824
collect_bridging_perimeter_areas(const ExtrusionLoop & loop,const float expansion_scaled,Polygons & out)825 static inline void collect_bridging_perimeter_areas(const ExtrusionLoop &loop, const float expansion_scaled, Polygons &out)
826 {
827 assert(expansion_scaled >= 0.f);
828 for (const ExtrusionPath &ep : loop.paths)
829 if (ep.role() == erOverhangPerimeter && ! ep.polyline.empty()) {
830 float exp = 0.5f * (float)scale_(ep.width) + expansion_scaled;
831 if (ep.is_closed()) {
832 if (ep.size() >= 3) {
833 // This is a complete loop.
834 // Add the outer contour first.
835 Polygon poly;
836 poly.points = ep.polyline.points;
837 poly.points.pop_back();
838 if (poly.area() < 0)
839 poly.reverse();
840 polygons_append(out, offset(poly, exp, SUPPORT_SURFACES_OFFSET_PARAMETERS));
841 Polygons holes = offset(poly, - exp, SUPPORT_SURFACES_OFFSET_PARAMETERS);
842 polygons_reverse(holes);
843 polygons_append(out, holes);
844 }
845 } else if (ep.size() >= 2) {
846 // Offset the polyline.
847 polygons_append(out, offset(ep.polyline, exp, SUPPORT_SURFACES_OFFSET_PARAMETERS));
848 }
849 }
850 }
collect_bridging_perimeter_areas(const ExtrusionEntityCollection & perimeters,const float expansion_scaled,Polygons & out)851 static void collect_bridging_perimeter_areas(const ExtrusionEntityCollection &perimeters, const float expansion_scaled, Polygons &out)
852 {
853 for (const ExtrusionEntity *ee : perimeters.entities) {
854 if (ee->is_collection()) {
855 for (const ExtrusionEntity *ee2 : static_cast<const ExtrusionEntityCollection*>(ee)->entities) {
856 assert(! ee2->is_collection());
857 if (ee2->is_loop())
858 collect_bridging_perimeter_areas(*static_cast<const ExtrusionLoop*>(ee2), expansion_scaled, out);
859 }
860 } else if (ee->is_loop())
861 collect_bridging_perimeter_areas(*static_cast<const ExtrusionLoop*>(ee), expansion_scaled, out);
862 }
863 }
864
remove_bridges_from_contacts(const PrintConfig & print_config,const Layer & lower_layer,const Polygons & lower_layer_polygons,LayerRegion * layerm,float fw,Polygons & contact_polygons)865 static void remove_bridges_from_contacts(
866 const PrintConfig &print_config,
867 const Layer &lower_layer,
868 const Polygons &lower_layer_polygons,
869 LayerRegion *layerm,
870 float fw,
871 Polygons &contact_polygons)
872 {
873 // compute the area of bridging perimeters
874 Polygons bridges;
875 {
876 // Surface supporting this layer, expanded by 0.5 * nozzle_diameter, as we consider this kind of overhang to be sufficiently supported.
877 Polygons lower_grown_slices = offset(lower_layer_polygons,
878 //FIXME to mimic the decision in the perimeter generator, we should use half the external perimeter width.
879 0.5f * float(scale_(print_config.nozzle_diameter.get_at(layerm->region()->config().perimeter_extruder-1))),
880 SUPPORT_SURFACES_OFFSET_PARAMETERS);
881 // Collect perimeters of this layer.
882 //FIXME split_at_first_point() could split a bridge mid-way
883 #if 0
884 Polylines overhang_perimeters = layerm->perimeters.as_polylines();
885 // workaround for Clipper bug, see Slic3r::Polygon::clip_as_polyline()
886 for (Polyline &polyline : overhang_perimeters)
887 polyline.points[0].x += 1;
888 // Trim the perimeters of this layer by the lower layer to get the unsupported pieces of perimeters.
889 overhang_perimeters = diff_pl(overhang_perimeters, lower_grown_slices);
890 #else
891 Polylines overhang_perimeters = diff_pl(layerm->perimeters.as_polylines(), lower_grown_slices);
892 #endif
893
894 // only consider straight overhangs
895 // only consider overhangs having endpoints inside layer's slices
896 // convert bridging polylines into polygons by inflating them with their thickness
897 // since we're dealing with bridges, we can't assume width is larger than spacing,
898 // so we take the largest value and also apply safety offset to be ensure no gaps
899 // are left in between
900 Flow bridge_flow = layerm->flow(frPerimeter, true);
901 float w = float(std::max(bridge_flow.scaled_width(), bridge_flow.scaled_spacing()));
902 for (Polyline &polyline : overhang_perimeters)
903 if (polyline.is_straight()) {
904 // This is a bridge
905 polyline.extend_start(fw);
906 polyline.extend_end(fw);
907 // Is the straight perimeter segment supported at both sides?
908 Point pts[2] = { polyline.first_point(), polyline.last_point() };
909 bool supported[2] = { false, false };
910 for (size_t i = 0; i < lower_layer.lslices.size() && ! (supported[0] && supported[1]); ++ i)
911 for (int j = 0; j < 2; ++ j)
912 if (! supported[j] && lower_layer.lslices_bboxes[i].contains(pts[j]) && lower_layer.lslices[i].contains(pts[j]))
913 supported[j] = true;
914 if (supported[0] && supported[1])
915 // Offset a polyline into a thick line.
916 polygons_append(bridges, offset(polyline, 0.5f * w + 10.f));
917 }
918 bridges = union_(bridges);
919 }
920 // remove the entire bridges and only support the unsupported edges
921 //FIXME the brided regions are already collected as layerm->bridged. Use it?
922 for (const Surface &surface : layerm->fill_surfaces.surfaces)
923 if (surface.surface_type == stBottomBridge && surface.bridge_angle != -1)
924 polygons_append(bridges, surface.expolygon);
925 //FIXME add the gap filled areas. Extrude the gaps with a bridge flow?
926 // Remove the unsupported ends of the bridges from the bridged areas.
927 //FIXME add supports at regular intervals to support long bridges!
928 bridges = diff(bridges,
929 // Offset unsupported edges into polygons.
930 offset(layerm->unsupported_bridge_edges, scale_(SUPPORT_MATERIAL_MARGIN), SUPPORT_SURFACES_OFFSET_PARAMETERS));
931 // Remove bridged areas from the supported areas.
932 contact_polygons = diff(contact_polygons, bridges, true);
933 }
934 }
935
936 #if 0
937 static int Test()
938 {
939 // for (int i = 0; i < 30; ++ i)
940 {
941 int i = -1;
942 // SupportGridPattern grid("d:\\temp\\support-top-contacts-final-run1-layer460-z70.300000-prev.bin", i);
943 // SupportGridPattern grid("d:\\temp\\support-top-contacts-final-run1-layer460-z70.300000.bin", i);
944 auto grid = SupportGridPattern::deserialize("d:\\temp\\support-top-contacts-final-run1-layer27-z5.650000.bin", i);
945 std::vector<std::pair<EdgeGrid::Grid::ContourEdge, EdgeGrid::Grid::ContourEdge>> intersections = grid.grid().intersecting_edges();
946 if (! intersections.empty())
947 printf("Intersections between contours!\n");
948 Slic3r::export_intersections_to_svg("d:\\temp\\support_polygon_intersections.svg", grid.support_polygons());
949 Slic3r::SVG::export_expolygons("d:\\temp\\support_polygons.svg", union_ex(grid.support_polygons(), false));
950 Slic3r::SVG::export_expolygons("d:\\temp\\trimming_polygons.svg", union_ex(grid.trimming_polygons(), false));
951 Polygons extracted = grid.extract_support(scale_(0.21 / 2), true);
952 Slic3r::SVG::export_expolygons("d:\\temp\\extracted.svg", union_ex(extracted, false));
953 printf("hu!");
954 }
955 return 0;
956 }
957 static int run_support_test = Test();
958 #endif /* SLIC3R_DEBUG */
959
960 // Generate top contact layers supporting overhangs.
961 // For a soluble interface material synchronize the layer heights with the object, otherwise leave the layer height undefined.
962 // If supports over bed surface only are requested, don't generate contact layers over an object.
top_contact_layers(const PrintObject & object,MyLayerStorage & layer_storage) const963 PrintObjectSupportMaterial::MyLayersPtr PrintObjectSupportMaterial::top_contact_layers(
964 const PrintObject &object, MyLayerStorage &layer_storage) const
965 {
966 #ifdef SLIC3R_DEBUG
967 static int iRun = 0;
968 ++ iRun;
969 #endif /* SLIC3R_DEBUG */
970
971 // Slice support enforcers / support blockers.
972 std::vector<ExPolygons> enforcers = object.slice_support_enforcers();
973 std::vector<ExPolygons> blockers = object.slice_support_blockers();
974
975 // Append custom supports.
976 object.project_and_append_custom_facets(false, EnforcerBlockerType::ENFORCER, enforcers);
977 object.project_and_append_custom_facets(false, EnforcerBlockerType::BLOCKER, blockers);
978
979 // Output layers, sorted by top Z.
980 MyLayersPtr contact_out;
981
982 const bool support_auto = m_object_config->support_material_auto.value;
983 // If user specified a custom angle threshold, convert it to radians.
984 // Zero means automatic overhang detection.
985 const double threshold_rad = (m_object_config->support_material_threshold.value > 0) ?
986 M_PI * double(m_object_config->support_material_threshold.value + 1) / 180. : // +1 makes the threshold inclusive
987 0.;
988
989 // Build support on a build plate only? If so, then collect and union all the surfaces below the current layer.
990 // Unfortunately this is an inherently serial process.
991 const bool buildplate_only = this->build_plate_only();
992 std::vector<Polygons> buildplate_covered;
993 if (buildplate_only) {
994 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::top_contact_layers() - collecting regions covering the print bed.";
995 buildplate_covered.assign(object.layers().size(), Polygons());
996 for (size_t layer_id = 1; layer_id < object.layers().size(); ++ layer_id) {
997 const Layer &lower_layer = *object.layers()[layer_id-1];
998 // Merge the new slices with the preceding slices.
999 // Apply the safety offset to the newly added polygons, so they will connect
1000 // with the polygons collected before,
1001 // but don't apply the safety offset during the union operation as it would
1002 // inflate the polygons over and over.
1003 Polygons &covered = buildplate_covered[layer_id];
1004 covered = buildplate_covered[layer_id - 1];
1005 polygons_append(covered, offset(lower_layer.lslices, scale_(0.01)));
1006 covered = union_(covered, false); // don't apply the safety offset.
1007 }
1008 }
1009
1010 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::top_contact_layers() in parallel - start";
1011 // Determine top contact areas.
1012 // If generating raft only (no support), only calculate top contact areas for the 0th layer.
1013 // If having a raft, start with 0th layer, otherwise with 1st layer.
1014 // Note that layer_id < layer->id when raft_layers > 0 as the layer->id incorporates the raft layers.
1015 // So layer_id == 0 means first object layer and layer->id == 0 means first print layer if there are no explicit raft layers.
1016 size_t num_layers = this->has_support() ? object.layer_count() : 1;
1017 // For each overhang layer, two supporting layers may be generated: One for the overhangs extruded with a bridging flow,
1018 // and the other for the overhangs extruded with a normal flow.
1019 contact_out.assign(num_layers * 2, nullptr);
1020 tbb::spin_mutex layer_storage_mutex;
1021 tbb::parallel_for(tbb::blocked_range<size_t>(this->has_raft() ? 0 : 1, num_layers),
1022 [this, &object, &buildplate_covered, &enforcers, &blockers, support_auto, threshold_rad, &layer_storage, &layer_storage_mutex, &contact_out]
1023 (const tbb::blocked_range<size_t>& range) {
1024 for (size_t layer_id = range.begin(); layer_id < range.end(); ++ layer_id)
1025 {
1026 const Layer &layer = *object.layers()[layer_id];
1027
1028 // Detect overhangs and contact areas needed to support them.
1029 // Collect overhangs and contacts of all regions of this layer supported by the layer immediately below.
1030 Polygons overhang_polygons;
1031 Polygons contact_polygons;
1032 Polygons slices_margin_cached;
1033 float slices_margin_cached_offset = -1.;
1034 Polygons lower_layer_polygons = (layer_id == 0) ? Polygons() : to_polygons(object.layers()[layer_id-1]->lslices);
1035 // Offset of the lower layer, to trim the support polygons with to calculate dense supports.
1036 float no_interface_offset = 0.f;
1037 if (layer_id == 0) {
1038 // This is the first object layer, so the object is being printed on a raft and
1039 // we're here just to get the object footprint for the raft.
1040 // We only consider contours and discard holes to get a more continuous raft.
1041 overhang_polygons = collect_slices_outer(layer);
1042 // Extend by SUPPORT_MATERIAL_MARGIN, which is 1.5mm
1043 contact_polygons = offset(overhang_polygons, scale_(SUPPORT_MATERIAL_MARGIN));
1044 } else {
1045 // Generate overhang / contact_polygons for non-raft layers.
1046 const Layer &lower_layer = *object.layers()[layer_id-1];
1047 for (LayerRegion *layerm : layer.regions()) {
1048 // Extrusion width accounts for the roundings of the extrudates.
1049 // It is the maximum widh of the extrudate.
1050 float fw = float(layerm->flow(frExternalPerimeter).scaled_width());
1051 no_interface_offset = (no_interface_offset == 0.f) ? fw : std::min(no_interface_offset, fw);
1052 float lower_layer_offset =
1053 (layer_id < (size_t)m_object_config->support_material_enforce_layers.value) ?
1054 // Enforce a full possible support, ignore the overhang angle.
1055 0.f :
1056 (threshold_rad > 0. ?
1057 // Overhang defined by an angle.
1058 float(scale_(lower_layer.height / tan(threshold_rad))) :
1059 // Overhang defined by half the extrusion width.
1060 0.5f * fw);
1061 // Overhang polygons for this layer and region.
1062 Polygons diff_polygons;
1063 Polygons layerm_polygons = to_polygons(layerm->slices);
1064 if (lower_layer_offset == 0.f) {
1065 // Support everything.
1066 diff_polygons = diff(layerm_polygons, lower_layer_polygons);
1067 if (! buildplate_covered.empty()) {
1068 // Don't support overhangs above the top surfaces.
1069 // This step is done before the contact surface is calculated by growing the overhang region.
1070 diff_polygons = diff(diff_polygons, buildplate_covered[layer_id]);
1071 }
1072 } else {
1073 if (support_auto) {
1074 // Get the regions needing a suport, collapse very tiny spots.
1075 //FIXME cache the lower layer offset if this layer has multiple regions.
1076 #if 1
1077 diff_polygons = offset2(
1078 diff(layerm_polygons,
1079 offset2(lower_layer_polygons, - 0.5f * fw, lower_layer_offset + 0.5f * fw, SUPPORT_SURFACES_OFFSET_PARAMETERS)),
1080 //FIXME This offset2 is targeted to reduce very thin regions to support, but it may lead to
1081 // no support at all for not so steep overhangs.
1082 - 0.1f * fw, 0.1f * fw);
1083 #else
1084 diff_polygons =
1085 diff(layerm_polygons,
1086 offset(lower_layer_polygons, lower_layer_offset, SUPPORT_SURFACES_OFFSET_PARAMETERS));
1087 #endif
1088 if (! buildplate_covered.empty()) {
1089 // Don't support overhangs above the top surfaces.
1090 // This step is done before the contact surface is calculated by growing the overhang region.
1091 diff_polygons = diff(diff_polygons, buildplate_covered[layer_id]);
1092 }
1093 if (! diff_polygons.empty()) {
1094 // Offset the support regions back to a full overhang, restrict them to the full overhang.
1095 // This is done to increase size of the supporting columns below, as they are calculated by
1096 // propagating these contact surfaces downwards.
1097 diff_polygons = diff(
1098 intersection(offset(diff_polygons, lower_layer_offset, SUPPORT_SURFACES_OFFSET_PARAMETERS), layerm_polygons),
1099 lower_layer_polygons);
1100 }
1101 }
1102 if (! enforcers.empty()) {
1103 // Apply the "support enforcers".
1104 //FIXME add the "enforcers" to the sparse support regions only.
1105 const ExPolygons &enforcer = enforcers[layer_id];
1106 if (! enforcer.empty()) {
1107 // Enforce supports (as if with 90 degrees of slope) for the regions covered by the enforcer meshes.
1108 Polygons new_contacts = diff(intersection(layerm_polygons, to_polygons(std::move(enforcer))),
1109 offset(lower_layer_polygons, 0.05f * fw, SUPPORT_SURFACES_OFFSET_PARAMETERS));
1110 if (! new_contacts.empty()) {
1111 if (diff_polygons.empty())
1112 diff_polygons = std::move(new_contacts);
1113 else
1114 diff_polygons = union_(diff_polygons, new_contacts);
1115 }
1116 }
1117 }
1118 }
1119
1120 if (diff_polygons.empty())
1121 continue;
1122
1123 // Apply the "support blockers".
1124 if (! blockers.empty() && ! blockers[layer_id].empty()) {
1125 // Expand the blocker a bit. Custom blockers produce strips
1126 // spanning just the projection between the two slices.
1127 // Subtracting them as they are may leave unwanted narrow
1128 // residues of diff_polygons that would then be supported.
1129 diff_polygons = diff(diff_polygons,
1130 offset(union_(to_polygons(std::move(blockers[layer_id]))),
1131 1000.*SCALED_EPSILON));
1132 }
1133
1134 #ifdef SLIC3R_DEBUG
1135 {
1136 ::Slic3r::SVG svg(debug_out_path("support-top-contacts-raw-run%d-layer%d-region%d.svg",
1137 iRun, layer_id,
1138 std::find_if(layer.regions().begin(), layer.regions().end(), [layerm](const LayerRegion* other){return other == layerm;}) - layer.regions().begin()),
1139 get_extents(diff_polygons));
1140 Slic3r::ExPolygons expolys = union_ex(diff_polygons, false);
1141 svg.draw(expolys);
1142 }
1143 #endif /* SLIC3R_DEBUG */
1144
1145 if (this->m_object_config->dont_support_bridges)
1146 SupportMaterialInternal::remove_bridges_from_contacts(
1147 *m_print_config, lower_layer, lower_layer_polygons, layerm, fw, diff_polygons);
1148
1149 if (diff_polygons.empty())
1150 continue;
1151
1152 #ifdef SLIC3R_DEBUG
1153 Slic3r::SVG::export_expolygons(
1154 debug_out_path("support-top-contacts-filtered-run%d-layer%d-region%d-z%f.svg",
1155 iRun, layer_id,
1156 std::find_if(layer.regions().begin(), layer.regions().end(), [layerm](const LayerRegion* other){return other == layerm;}) - layer.regions().begin(),
1157 layer.print_z),
1158 union_ex(diff_polygons, false));
1159 #endif /* SLIC3R_DEBUG */
1160
1161 //FIXME the overhang_polygons are used to construct the support towers as well.
1162 //if (this->has_contact_loops())
1163 // Store the exact contour of the overhang for the contact loops.
1164 polygons_append(overhang_polygons, diff_polygons);
1165
1166 // Let's define the required contact area by using a max gap of half the upper
1167 // extrusion width and extending the area according to the configured margin.
1168 // We increment the area in steps because we don't want our support to overflow
1169 // on the other side of the object (if it's very thin).
1170 {
1171 //FIMXE 1) Make the offset configurable, 2) Make the Z span configurable.
1172 //FIXME one should trim with the layer span colliding with the support layer, this layer
1173 // may be lower than lower_layer, so the support area needed may need to be actually bigger!
1174 // For the same reason, the non-bridging support area may be smaller than the bridging support area!
1175 float slices_margin_offset = std::min(lower_layer_offset, float(scale_(m_gap_xy)));
1176 if (slices_margin_cached_offset != slices_margin_offset) {
1177 slices_margin_cached_offset = slices_margin_offset;
1178 slices_margin_cached = (slices_margin_offset == 0.f) ?
1179 lower_layer_polygons :
1180 offset2(to_polygons(lower_layer.lslices), - no_interface_offset * 0.5f, slices_margin_offset + no_interface_offset * 0.5f, SUPPORT_SURFACES_OFFSET_PARAMETERS);
1181 if (! buildplate_covered.empty()) {
1182 // Trim the inflated contact surfaces by the top surfaces as well.
1183 polygons_append(slices_margin_cached, buildplate_covered[layer_id]);
1184 slices_margin_cached = union_(slices_margin_cached);
1185 }
1186 }
1187 // Offset the contact polygons outside.
1188 for (size_t i = 0; i < NUM_MARGIN_STEPS; ++ i) {
1189 diff_polygons = diff(
1190 offset(
1191 diff_polygons,
1192 SUPPORT_MATERIAL_MARGIN / NUM_MARGIN_STEPS,
1193 ClipperLib::jtRound,
1194 // round mitter limit
1195 scale_(0.05)),
1196 slices_margin_cached);
1197 }
1198 }
1199 polygons_append(contact_polygons, diff_polygons);
1200 } // for each layer.region
1201 } // end of Generate overhang/contact_polygons for non-raft layers.
1202
1203 // Now apply the contact areas to the layer where they need to be made.
1204 if (! contact_polygons.empty()) {
1205 MyLayer &new_layer = layer_allocate(layer_storage, layer_storage_mutex, sltTopContact);
1206 new_layer.idx_object_layer_above = layer_id;
1207 MyLayer *bridging_layer = nullptr;
1208 if (layer_id == 0) {
1209 // This is a raft contact layer sitting directly on the print bed.
1210 assert(this->has_raft());
1211 new_layer.print_z = m_slicing_params.raft_contact_top_z;
1212 new_layer.bottom_z = m_slicing_params.raft_interface_top_z;
1213 new_layer.height = m_slicing_params.contact_raft_layer_height;
1214 } else if (m_slicing_params.soluble_interface) {
1215 // Align the contact surface height with a layer immediately below the supported layer.
1216 // Interface layer will be synchronized with the object.
1217 new_layer.print_z = layer.print_z - layer.height;
1218 new_layer.height = object.layers()[layer_id - 1]->height;
1219 new_layer.bottom_z = (layer_id == 1) ? m_slicing_params.object_print_z_min : object.layers()[layer_id - 2]->print_z;
1220 } else {
1221 new_layer.print_z = layer.print_z - layer.height - m_object_config->support_material_contact_distance;
1222 new_layer.bottom_z = new_layer.print_z;
1223 new_layer.height = 0.;
1224 // Ignore this contact area if it's too low.
1225 // Don't want to print a layer below the first layer height as it may not stick well.
1226 //FIXME there may be a need for a single layer support, then one may decide to print it either as a bottom contact or a top contact
1227 // and it may actually make sense to do it with a thinner layer than the first layer height.
1228 if (new_layer.print_z < m_slicing_params.first_print_layer_height - EPSILON) {
1229 // This contact layer is below the first layer height, therefore not printable. Don't support this surface.
1230 continue;
1231 } else if (new_layer.print_z < m_slicing_params.first_print_layer_height + EPSILON) {
1232 // Align the layer with the 1st layer height.
1233 new_layer.print_z = m_slicing_params.first_print_layer_height;
1234 new_layer.bottom_z = 0;
1235 new_layer.height = m_slicing_params.first_print_layer_height;
1236 } else {
1237 // Don't know the height of the top contact layer yet. The top contact layer is printed with a normal flow and
1238 // its height will be set adaptively later on.
1239 }
1240
1241 // Contact layer will be printed with a normal flow, but
1242 // it will support layers printed with a bridging flow.
1243 if (SupportMaterialInternal::has_bridging_extrusions(layer)) {
1244 coordf_t bridging_height = 0.;
1245 for (const LayerRegion *region : layer.regions())
1246 bridging_height += region->region()->bridging_height_avg(*m_print_config);
1247 bridging_height /= coordf_t(layer.regions().size());
1248 coordf_t bridging_print_z = layer.print_z - bridging_height - m_object_config->support_material_contact_distance;
1249 if (bridging_print_z >= m_slicing_params.first_print_layer_height - EPSILON) {
1250 // Not below the first layer height means this layer is printable.
1251 if (new_layer.print_z < m_slicing_params.first_print_layer_height + EPSILON) {
1252 // Align the layer with the 1st layer height.
1253 bridging_print_z = m_slicing_params.first_print_layer_height;
1254 }
1255 if (bridging_print_z < new_layer.print_z - EPSILON) {
1256 // Allocate the new layer.
1257 bridging_layer = &layer_allocate(layer_storage, layer_storage_mutex, sltTopContact);
1258 bridging_layer->idx_object_layer_above = layer_id;
1259 bridging_layer->print_z = bridging_print_z;
1260 if (bridging_print_z == m_slicing_params.first_print_layer_height) {
1261 bridging_layer->bottom_z = 0;
1262 bridging_layer->height = m_slicing_params.first_print_layer_height;
1263 } else {
1264 // Don't know the height yet.
1265 bridging_layer->bottom_z = bridging_print_z;
1266 bridging_layer->height = 0;
1267 }
1268 }
1269 }
1270 }
1271 }
1272
1273 // Achtung! The contact_polygons need to be trimmed by slices_margin_cached, otherwise
1274 // the selection by island_samples (see the SupportGridPattern::island_samples() method) will not work!
1275 SupportGridPattern support_grid_pattern(
1276 // Support islands, to be stretched into a grid.
1277 contact_polygons,
1278 // Trimming polygons, to trim the stretched support islands.
1279 slices_margin_cached,
1280 // Grid resolution.
1281 m_object_config->support_material_spacing.value + m_support_material_flow.spacing(),
1282 Geometry::deg2rad(m_object_config->support_material_angle.value));
1283 // 1) Contact polygons will be projected down. To keep the interface and base layers from growing, return a contour a tiny bit smaller than the grid cells.
1284 new_layer.contact_polygons = new Polygons(support_grid_pattern.extract_support(-3, true));
1285 // 2) infill polygons, expand them by half the extrusion width + a tiny bit of extra.
1286 if (layer_id == 0 || m_slicing_params.soluble_interface) {
1287 // if (no_interface_offset == 0.f) {
1288 new_layer.polygons = support_grid_pattern.extract_support(m_support_material_flow.scaled_spacing()/2 + 5, true);
1289 } else {
1290 // Reduce the amount of dense interfaces: Do not generate dense interfaces below overhangs with 60% overhang of the extrusions.
1291 Polygons dense_interface_polygons = diff(overhang_polygons,
1292 offset2(lower_layer_polygons, - no_interface_offset * 0.5f, no_interface_offset * (0.6f + 0.5f), SUPPORT_SURFACES_OFFSET_PARAMETERS));
1293 if (! dense_interface_polygons.empty()) {
1294 dense_interface_polygons =
1295 // Achtung! The dense_interface_polygons need to be trimmed by slices_margin_cached, otherwise
1296 // the selection by island_samples (see the SupportGridPattern::island_samples() method) will not work!
1297 diff(
1298 // Regularize the contour.
1299 offset(dense_interface_polygons, no_interface_offset * 0.1f),
1300 slices_margin_cached);
1301 SupportGridPattern support_grid_pattern(
1302 // Support islands, to be stretched into a grid.
1303 dense_interface_polygons,
1304 // Trimming polygons, to trim the stretched support islands.
1305 slices_margin_cached,
1306 // Grid resolution.
1307 m_object_config->support_material_spacing.value + m_support_material_flow.spacing(),
1308 Geometry::deg2rad(m_object_config->support_material_angle.value));
1309 new_layer.polygons = support_grid_pattern.extract_support(m_support_material_flow.scaled_spacing()/2 + 5, false);
1310 #ifdef SLIC3R_DEBUG
1311 {
1312 support_grid_pattern.serialize(debug_out_path("support-top-contacts-final-run%d-layer%d-z%f.bin", iRun, layer_id, layer.print_z));
1313
1314 BoundingBox bbox = get_extents(contact_polygons);
1315 bbox.merge(get_extents(new_layer.polygons));
1316 ::Slic3r::SVG svg(debug_out_path("support-top-contacts-final0-run%d-layer%d-z%f.svg", iRun, layer_id, layer.print_z));
1317 svg.draw(union_ex(*new_layer.contact_polygons, false), "gray", 0.5f);
1318 svg.draw(union_ex(contact_polygons, false), "blue", 0.5f);
1319 svg.draw(union_ex(dense_interface_polygons, false), "green", 0.5f);
1320 svg.draw(union_ex(new_layer.polygons, true), "red", 0.5f);
1321 svg.draw_outline(union_ex(new_layer.polygons, true), "black", "black", scale_(0.1f));
1322 }
1323 #endif /* SLIC3R_DEBUG */
1324 }
1325 }
1326 #ifdef SLIC3R_DEBUG
1327 {
1328 BoundingBox bbox = get_extents(contact_polygons);
1329 bbox.merge(get_extents(new_layer.polygons));
1330 ::Slic3r::SVG svg(debug_out_path("support-top-contacts-final-run%d-layer%d-z%f.svg", iRun, layer_id, layer.print_z));
1331 svg.draw(union_ex(*new_layer.contact_polygons, false), "gray", 0.5f);
1332 svg.draw(union_ex(contact_polygons, false), "blue", 0.5f);
1333 svg.draw(union_ex(overhang_polygons, false), "green", 0.5f);
1334 svg.draw(union_ex(new_layer.polygons, true), "red", 0.5f);
1335 svg.draw_outline(union_ex(new_layer.polygons, true), "black", "black", scale_(0.1f));
1336 }
1337 #endif /* SLIC3R_DEBUG */
1338
1339 // Even after the contact layer was expanded into a grid, some of the contact islands may be too tiny to be extruded.
1340 // Remove those tiny islands from new_layer.polygons and new_layer.contact_polygons.
1341
1342 // Store the overhang polygons.
1343 // The overhang polygons are used in the path generator for planning of the contact loops.
1344 // if (this->has_contact_loops()). Compared to "polygons", "overhang_polygons" are snug.
1345 new_layer.overhang_polygons = new Polygons(std::move(overhang_polygons));
1346 contact_out[layer_id * 2] = &new_layer;
1347 if (bridging_layer != nullptr) {
1348 bridging_layer->polygons = new_layer.polygons;
1349 bridging_layer->contact_polygons = new Polygons(*new_layer.contact_polygons);
1350 bridging_layer->overhang_polygons = new Polygons(*new_layer.overhang_polygons);
1351 contact_out[layer_id * 2 + 1] = bridging_layer;
1352 }
1353 }
1354 }
1355 });
1356
1357 // Compress contact_out, remove the nullptr items.
1358 remove_nulls(contact_out);
1359 // Sort the layers, as one layer may produce bridging and non-bridging contact layers with different print_z.
1360 std::sort(contact_out.begin(), contact_out.end(), [](const MyLayer *l1, const MyLayer *l2) { return l1->print_z < l2->print_z; });
1361
1362 // Merge close contact layers conservatively: If two layers are closer than the minimum allowed print layer height (the min_layer_height parameter),
1363 // the top contact layer is merged into the bottom contact layer.
1364 {
1365 int i = 0;
1366 int k = 0;
1367 {
1368 // Find the span of layers, which are to be printed at the first layer height.
1369 int j = 0;
1370 for (; j < (int)contact_out.size() && contact_out[j]->print_z < m_slicing_params.first_print_layer_height + this->m_support_layer_height_min - EPSILON; ++ j);
1371 if (j > 0) {
1372 // Merge the contact_out layers (0) to (j - 1) into the contact_out[0].
1373 MyLayer &dst = *contact_out.front();
1374 for (int u = 1; u < j; ++ u) {
1375 MyLayer &src = *contact_out[u];
1376 // The union_() does not support move semantic yet, but maybe one day it will.
1377 dst.polygons = union_(dst.polygons, std::move(src.polygons));
1378 *dst.contact_polygons = union_(*dst.contact_polygons, std::move(*src.contact_polygons));
1379 *dst.overhang_polygons = union_(*dst.overhang_polygons, std::move(*src.overhang_polygons));
1380 // Source polygon is no more needed, it will not be refrenced. Release its data.
1381 src.reset();
1382 }
1383 // Snap the first layer to the 1st layer height.
1384 dst.print_z = m_slicing_params.first_print_layer_height;
1385 dst.height = m_slicing_params.first_print_layer_height;
1386 dst.bottom_z = 0;
1387 ++ k;
1388 }
1389 i = j;
1390 }
1391 for (; i < int(contact_out.size()); ++ k) {
1392 // Find the span of layers closer than m_support_layer_height_min.
1393 int j = i + 1;
1394 coordf_t zmax = contact_out[i]->print_z + m_support_layer_height_min + EPSILON;
1395 for (; j < (int)contact_out.size() && contact_out[j]->print_z < zmax; ++ j) ;
1396 if (i + 1 < j) {
1397 // Merge the contact_out layers (i + 1) to (j - 1) into the contact_out[i].
1398 MyLayer &dst = *contact_out[i];
1399 for (int u = i + 1; u < j; ++ u) {
1400 MyLayer &src = *contact_out[u];
1401 // The union_() does not support move semantic yet, but maybe one day it will.
1402 dst.polygons = union_(dst.polygons, std::move(src.polygons));
1403 *dst.contact_polygons = union_(*dst.contact_polygons, std::move(*src.contact_polygons));
1404 *dst.overhang_polygons = union_(*dst.overhang_polygons, std::move(*src.overhang_polygons));
1405 // Source polygon is no more needed, it will not be refrenced. Release its data.
1406 src.reset();
1407 }
1408 }
1409 if (k < i)
1410 contact_out[k] = contact_out[i];
1411 i = j;
1412 }
1413 if (k < (int)contact_out.size())
1414 contact_out.erase(contact_out.begin() + k, contact_out.end());
1415 }
1416
1417 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::top_contact_layers() in parallel - end";
1418
1419 return contact_out;
1420 }
1421
1422 // Generate bottom contact layers supporting the top contact layers.
1423 // For a soluble interface material synchronize the layer heights with the object,
1424 // otherwise set the layer height to a bridging flow of a support interface nozzle.
bottom_contact_layers_and_layer_support_areas(const PrintObject & object,const MyLayersPtr & top_contacts,MyLayerStorage & layer_storage,std::vector<Polygons> & layer_support_areas) const1425 PrintObjectSupportMaterial::MyLayersPtr PrintObjectSupportMaterial::bottom_contact_layers_and_layer_support_areas(
1426 const PrintObject &object, const MyLayersPtr &top_contacts, MyLayerStorage &layer_storage,
1427 std::vector<Polygons> &layer_support_areas) const
1428 {
1429 #ifdef SLIC3R_DEBUG
1430 static int iRun = 0;
1431 ++ iRun;
1432 #endif /* SLIC3R_DEBUG */
1433
1434 // Allocate empty surface areas, one per object layer.
1435 layer_support_areas.assign(object.total_layer_count(), Polygons());
1436
1437 // find object top surfaces
1438 // we'll use them to clip our support and detect where does it stick
1439 MyLayersPtr bottom_contacts;
1440
1441 if (! top_contacts.empty())
1442 {
1443 // There is some support to be built, if there are non-empty top surfaces detected.
1444 // Sum of unsupported contact areas above the current layer.print_z.
1445 Polygons projection;
1446 // Last top contact layer visited when collecting the projection of contact areas.
1447 int contact_idx = int(top_contacts.size()) - 1;
1448 for (int layer_id = int(object.total_layer_count()) - 2; layer_id >= 0; -- layer_id) {
1449 BOOST_LOG_TRIVIAL(trace) << "Support generator - bottom_contact_layers - layer " << layer_id;
1450 const Layer &layer = *object.get_layer(layer_id);
1451 // Collect projections of all contact areas above or at the same level as this top surface.
1452 for (; contact_idx >= 0 && top_contacts[contact_idx]->print_z > layer.print_z - EPSILON; -- contact_idx) {
1453 Polygons polygons_new;
1454 // Contact surfaces are expanded away from the object, trimmed by the object.
1455 // Use a slight positive offset to overlap the touching regions.
1456 #if 0
1457 // Merge and collect the contact polygons. The contact polygons are inflated, but not extended into a grid form.
1458 polygons_append(polygons_new, offset(*top_contacts[contact_idx]->contact_polygons, SCALED_EPSILON));
1459 #else
1460 // Consume the contact_polygons. The contact polygons are already expanded into a grid form, and they are a tiny bit smaller
1461 // than the grid cells.
1462 polygons_append(polygons_new, std::move(*top_contacts[contact_idx]->contact_polygons));
1463 #endif
1464 // These are the overhang surfaces. They are touching the object and they are not expanded away from the object.
1465 // Use a slight positive offset to overlap the touching regions.
1466 polygons_append(polygons_new, offset(*top_contacts[contact_idx]->overhang_polygons, float(SCALED_EPSILON)));
1467 polygons_append(projection, union_(polygons_new));
1468 }
1469 if (projection.empty())
1470 continue;
1471 Polygons projection_raw = union_(projection);
1472
1473 tbb::task_group task_group;
1474 if (! m_object_config->support_material_buildplate_only)
1475 // Find the bottom contact layers above the top surfaces of this layer.
1476 task_group.run([this, &object, &top_contacts, contact_idx, &layer, layer_id, &layer_storage, &layer_support_areas, &bottom_contacts, &projection_raw] {
1477 Polygons top = collect_region_slices_by_type(layer, stTop);
1478 #ifdef SLIC3R_DEBUG
1479 {
1480 BoundingBox bbox = get_extents(projection_raw);
1481 bbox.merge(get_extents(top));
1482 ::Slic3r::SVG svg(debug_out_path("support-bottom-layers-raw-%d-%lf.svg", iRun, layer.print_z), bbox);
1483 svg.draw(union_ex(top, false), "blue", 0.5f);
1484 svg.draw(union_ex(projection_raw, true), "red", 0.5f);
1485 svg.draw_outline(union_ex(projection_raw, true), "red", "blue", scale_(0.1f));
1486 svg.draw(layer.lslices, "green", 0.5f);
1487 }
1488 #endif /* SLIC3R_DEBUG */
1489
1490 // Now find whether any projection of the contact surfaces above layer.print_z not yet supported by any
1491 // top surfaces above layer.print_z falls onto this top surface.
1492 // Touching are the contact surfaces supported exclusively by this top surfaces.
1493 // Don't use a safety offset as it has been applied during insertion of polygons.
1494 if (! top.empty()) {
1495 Polygons touching = intersection(top, projection_raw, false);
1496 if (! touching.empty()) {
1497 // Allocate a new bottom contact layer.
1498 MyLayer &layer_new = layer_allocate(layer_storage, sltBottomContact);
1499 bottom_contacts.push_back(&layer_new);
1500 // Grow top surfaces so that interface and support generation are generated
1501 // with some spacing from object - it looks we don't need the actual
1502 // top shapes so this can be done here
1503 //FIXME calculate layer height based on the actual thickness of the layer:
1504 // If the layer is extruded with no bridging flow, support just the normal extrusions.
1505 layer_new.height = m_slicing_params.soluble_interface ?
1506 // Align the interface layer with the object's layer height.
1507 object.layers()[layer_id + 1]->height :
1508 // Place a bridge flow interface layer over the top surface.
1509 //FIXME Check whether the bottom bridging surfaces are extruded correctly (no bridging flow correction applied?)
1510 // According to Jindrich the bottom surfaces work well.
1511 //FIXME test the bridging flow instead?
1512 m_support_material_interface_flow.nozzle_diameter;
1513 layer_new.print_z = m_slicing_params.soluble_interface ? object.layers()[layer_id + 1]->print_z :
1514 layer.print_z + layer_new.height + m_object_config->support_material_contact_distance.value;
1515 layer_new.bottom_z = layer.print_z;
1516 layer_new.idx_object_layer_below = layer_id;
1517 layer_new.bridging = ! m_slicing_params.soluble_interface;
1518 //FIXME how much to inflate the bottom surface, as it is being extruded with a bridging flow? The following line uses a normal flow.
1519 //FIXME why is the offset positive? It will be trimmed by the object later on anyway, but then it just wastes CPU clocks.
1520 layer_new.polygons = offset(touching, float(m_support_material_flow.scaled_width()), SUPPORT_SURFACES_OFFSET_PARAMETERS);
1521 if (! m_slicing_params.soluble_interface) {
1522 // Walk the top surfaces, snap the top of the new bottom surface to the closest top of the top surface,
1523 // so there will be no support surfaces generated with thickness lower than m_support_layer_height_min.
1524 for (size_t top_idx = size_t(std::max<int>(0, contact_idx));
1525 top_idx < top_contacts.size() && top_contacts[top_idx]->print_z < layer_new.print_z + this->m_support_layer_height_min + EPSILON;
1526 ++ top_idx) {
1527 if (top_contacts[top_idx]->print_z > layer_new.print_z - this->m_support_layer_height_min - EPSILON) {
1528 // A top layer has been found, which is close to the new bottom layer.
1529 coordf_t diff = layer_new.print_z - top_contacts[top_idx]->print_z;
1530 assert(std::abs(diff) <= this->m_support_layer_height_min + EPSILON);
1531 if (diff > 0.) {
1532 // The top contact layer is below this layer. Make the bridging layer thinner to align with the existing top layer.
1533 assert(diff < layer_new.height + EPSILON);
1534 assert(layer_new.height - diff >= m_support_layer_height_min - EPSILON);
1535 layer_new.print_z = top_contacts[top_idx]->print_z;
1536 layer_new.height -= diff;
1537 } else {
1538 // The top contact layer is above this layer. One may either make this layer thicker or thinner.
1539 // By making the layer thicker, one will decrease the number of discrete layers with the price of extruding a bit too thick bridges.
1540 // By making the layer thinner, one adds one more discrete layer.
1541 layer_new.print_z = top_contacts[top_idx]->print_z;
1542 layer_new.height -= diff;
1543 }
1544 break;
1545 }
1546 }
1547 }
1548 #ifdef SLIC3R_DEBUG
1549 Slic3r::SVG::export_expolygons(
1550 debug_out_path("support-bottom-contacts-%d-%lf.svg", iRun, layer_new.print_z),
1551 union_ex(layer_new.polygons, false));
1552 #endif /* SLIC3R_DEBUG */
1553 // Trim the already created base layers above the current layer intersecting with the new bottom contacts layer.
1554 //FIXME Maybe this is no more needed, as the overlapping base layers are trimmed by the bottom layers at the final stage?
1555 touching = offset(touching, float(SCALED_EPSILON));
1556 for (int layer_id_above = layer_id + 1; layer_id_above < int(object.total_layer_count()); ++ layer_id_above) {
1557 const Layer &layer_above = *object.layers()[layer_id_above];
1558 if (layer_above.print_z > layer_new.print_z - EPSILON)
1559 break;
1560 if (! layer_support_areas[layer_id_above].empty()) {
1561 #ifdef SLIC3R_DEBUG
1562 {
1563 BoundingBox bbox = get_extents(touching);
1564 bbox.merge(get_extents(layer_support_areas[layer_id_above]));
1565 ::Slic3r::SVG svg(debug_out_path("support-support-areas-raw-before-trimming-%d-with-%f-%lf.svg", iRun, layer.print_z, layer_above.print_z), bbox);
1566 svg.draw(union_ex(touching, false), "blue", 0.5f);
1567 svg.draw(union_ex(layer_support_areas[layer_id_above], true), "red", 0.5f);
1568 svg.draw_outline(union_ex(layer_support_areas[layer_id_above], true), "red", "blue", scale_(0.1f));
1569 }
1570 #endif /* SLIC3R_DEBUG */
1571 layer_support_areas[layer_id_above] = diff(layer_support_areas[layer_id_above], touching);
1572 #ifdef SLIC3R_DEBUG
1573 Slic3r::SVG::export_expolygons(
1574 debug_out_path("support-support-areas-raw-after-trimming-%d-with-%f-%lf.svg", iRun, layer.print_z, layer_above.print_z),
1575 union_ex(layer_support_areas[layer_id_above], false));
1576 #endif /* SLIC3R_DEBUG */
1577 }
1578 }
1579 }
1580 } // ! top.empty()
1581 });
1582
1583 Polygons &layer_support_area = layer_support_areas[layer_id];
1584 task_group.run([this, &projection, &projection_raw, &layer, &layer_support_area, layer_id] {
1585 // Remove the areas that touched from the projection that will continue on next, lower, top surfaces.
1586 // Polygons trimming = union_(to_polygons(layer.slices), touching, true);
1587 Polygons trimming = offset(layer.lslices, float(SCALED_EPSILON));
1588 projection = diff(projection_raw, trimming, false);
1589 #ifdef SLIC3R_DEBUG
1590 {
1591 BoundingBox bbox = get_extents(projection_raw);
1592 bbox.merge(get_extents(trimming));
1593 ::Slic3r::SVG svg(debug_out_path("support-support-areas-raw-%d-%lf.svg", iRun, layer.print_z), bbox);
1594 svg.draw(union_ex(trimming, false), "blue", 0.5f);
1595 svg.draw(union_ex(projection, true), "red", 0.5f);
1596 svg.draw_outline(union_ex(projection, true), "red", "blue", scale_(0.1f));
1597 }
1598 #endif /* SLIC3R_DEBUG */
1599 remove_sticks(projection);
1600 remove_degenerate(projection);
1601 #ifdef SLIC3R_DEBUG
1602 Slic3r::SVG::export_expolygons(
1603 debug_out_path("support-support-areas-raw-cleaned-%d-%lf.svg", iRun, layer.print_z),
1604 union_ex(projection, false));
1605 #endif /* SLIC3R_DEBUG */
1606 SupportGridPattern support_grid_pattern(
1607 // Support islands, to be stretched into a grid.
1608 projection,
1609 // Trimming polygons, to trim the stretched support islands.
1610 trimming,
1611 // Grid spacing.
1612 m_object_config->support_material_spacing.value + m_support_material_flow.spacing(),
1613 Geometry::deg2rad(m_object_config->support_material_angle.value));
1614 tbb::task_group task_group_inner;
1615 // 1) Cache the slice of a support volume. The support volume is expanded by 1/2 of support material flow spacing
1616 // to allow a placement of suppot zig-zag snake along the grid lines.
1617 task_group_inner.run([this, &support_grid_pattern, &layer_support_area
1618 #ifdef SLIC3R_DEBUG
1619 , &layer
1620 #endif /* SLIC3R_DEBUG */
1621 ] {
1622 layer_support_area = support_grid_pattern.extract_support(m_support_material_flow.scaled_spacing()/2 + 25, true);
1623 #ifdef SLIC3R_DEBUG
1624 Slic3r::SVG::export_expolygons(
1625 debug_out_path("support-layer_support_area-gridded-%d-%lf.svg", iRun, layer.print_z),
1626 union_ex(layer_support_area, false));
1627 #endif /* SLIC3R_DEBUG */
1628 });
1629 // 2) Support polygons will be projected down. To keep the interface and base layers from growing, return a contour a tiny bit smaller than the grid cells.
1630 Polygons projection_new;
1631 task_group_inner.run([&projection_new, &support_grid_pattern
1632 #ifdef SLIC3R_DEBUG
1633 , &layer
1634 #endif /* SLIC3R_DEBUG */
1635 ] {
1636 projection_new = support_grid_pattern.extract_support(-5, true);
1637 #ifdef SLIC3R_DEBUG
1638 Slic3r::SVG::export_expolygons(
1639 debug_out_path("support-projection_new-gridded-%d-%lf.svg", iRun, layer.print_z),
1640 union_ex(projection_new, false));
1641 #endif /* SLIC3R_DEBUG */
1642 });
1643 task_group_inner.wait();
1644 projection = std::move(projection_new);
1645 });
1646 task_group.wait();
1647 }
1648 std::reverse(bottom_contacts.begin(), bottom_contacts.end());
1649 // trim_support_layers_by_object(object, bottom_contacts, 0., 0., m_gap_xy);
1650 trim_support_layers_by_object(object, bottom_contacts,
1651 m_slicing_params.soluble_interface ? 0. : m_object_config->support_material_contact_distance.value,
1652 m_slicing_params.soluble_interface ? 0. : m_object_config->support_material_contact_distance.value, m_gap_xy);
1653
1654 } // ! top_contacts.empty()
1655
1656 return bottom_contacts;
1657 }
1658
1659 // FN_HIGHER_EQUAL: the provided object pointer has a Z value >= of an internal threshold.
1660 // Find the first item with Z value >= of an internal threshold of fn_higher_equal.
1661 // If no vec item with Z value >= of an internal threshold of fn_higher_equal is found, return vec.size()
1662 // If the initial idx is size_t(-1), then use binary search.
1663 // Otherwise search linearly upwards.
1664 template<typename T, typename FN_HIGHER_EQUAL>
idx_higher_or_equal(const std::vector<T * > & vec,size_t idx,FN_HIGHER_EQUAL fn_higher_equal)1665 size_t idx_higher_or_equal(const std::vector<T*> &vec, size_t idx, FN_HIGHER_EQUAL fn_higher_equal)
1666 {
1667 if (vec.empty()) {
1668 idx = 0;
1669 } else if (idx == size_t(-1)) {
1670 // First of the batch of layers per thread pool invocation. Use binary search.
1671 int idx_low = 0;
1672 int idx_high = std::max(0, int(vec.size()) - 1);
1673 while (idx_low + 1 < idx_high) {
1674 int idx_mid = (idx_low + idx_high) / 2;
1675 if (fn_higher_equal(vec[idx_mid]))
1676 idx_high = idx_mid;
1677 else
1678 idx_low = idx_mid;
1679 }
1680 idx = fn_higher_equal(vec[idx_low]) ? idx_low :
1681 (fn_higher_equal(vec[idx_high]) ? idx_high : vec.size());
1682 } else {
1683 // For the other layers of this batch of layers, search incrementally, which is cheaper than the binary search.
1684 while (idx < vec.size() && ! fn_higher_equal(vec[idx]))
1685 ++ idx;
1686 }
1687 return idx;
1688 }
1689
1690 // FN_LOWER_EQUAL: the provided object pointer has a Z value <= of an internal threshold.
1691 // Find the first item with Z value <= of an internal threshold of fn_lower_equal.
1692 // If no vec item with Z value <= of an internal threshold of fn_lower_equal is found, return -1.
1693 // If the initial idx is < -1, then use binary search.
1694 // Otherwise search linearly downwards.
1695 template<typename T, typename FN_LOWER_EQUAL>
idx_lower_or_equal(const std::vector<T * > & vec,int idx,FN_LOWER_EQUAL fn_lower_equal)1696 int idx_lower_or_equal(const std::vector<T*> &vec, int idx, FN_LOWER_EQUAL fn_lower_equal)
1697 {
1698 if (vec.empty()) {
1699 idx = -1;
1700 } else if (idx < -1) {
1701 // First of the batch of layers per thread pool invocation. Use binary search.
1702 int idx_low = 0;
1703 int idx_high = std::max(0, int(vec.size()) - 1);
1704 while (idx_low + 1 < idx_high) {
1705 int idx_mid = (idx_low + idx_high) / 2;
1706 if (fn_lower_equal(vec[idx_mid]))
1707 idx_low = idx_mid;
1708 else
1709 idx_high = idx_mid;
1710 }
1711 idx = fn_lower_equal(vec[idx_high]) ? idx_high :
1712 (fn_lower_equal(vec[idx_low ]) ? idx_low : -1);
1713 } else {
1714 // For the other layers of this batch of layers, search incrementally, which is cheaper than the binary search.
1715 while (idx >= 0 && ! fn_lower_equal(vec[idx]))
1716 -- idx;
1717 }
1718 return idx;
1719 }
1720
1721 // Trim the top_contacts layers with the bottom_contacts layers if they overlap, so there would not be enough vertical space for both of them.
trim_top_contacts_by_bottom_contacts(const PrintObject & object,const MyLayersPtr & bottom_contacts,MyLayersPtr & top_contacts) const1722 void PrintObjectSupportMaterial::trim_top_contacts_by_bottom_contacts(
1723 const PrintObject &object, const MyLayersPtr &bottom_contacts, MyLayersPtr &top_contacts) const
1724 {
1725 tbb::parallel_for(tbb::blocked_range<int>(0, int(top_contacts.size())),
1726 [this, &object, &bottom_contacts, &top_contacts](const tbb::blocked_range<int>& range) {
1727 int idx_bottom_overlapping_first = -2;
1728 // For all top contact layers, counting downwards due to the way idx_higher_or_equal caches the last index to avoid repeated binary search.
1729 for (int idx_top = range.end() - 1; idx_top >= range.begin(); -- idx_top) {
1730 MyLayer &layer_top = *top_contacts[idx_top];
1731 // Find the first bottom layer overlapping with layer_top.
1732 idx_bottom_overlapping_first = idx_lower_or_equal(bottom_contacts, idx_bottom_overlapping_first, [&layer_top](const MyLayer *layer_bottom){ return layer_bottom->bottom_print_z() - EPSILON <= layer_top.bottom_z; });
1733 // For all top contact layers overlapping with the thick bottom contact layer:
1734 for (int idx_bottom_overlapping = idx_bottom_overlapping_first; idx_bottom_overlapping >= 0; -- idx_bottom_overlapping) {
1735 const MyLayer &layer_bottom = *bottom_contacts[idx_bottom_overlapping];
1736 assert(layer_bottom.bottom_print_z() - EPSILON <= layer_top.bottom_z);
1737 if (layer_top.print_z < layer_bottom.print_z + EPSILON) {
1738 // Layers overlap. Trim layer_top with layer_bottom.
1739 layer_top.polygons = diff(layer_top.polygons, layer_bottom.polygons);
1740 } else
1741 break;
1742 }
1743 }
1744 });
1745 }
1746
raft_and_intermediate_support_layers(const PrintObject & object,const MyLayersPtr & bottom_contacts,const MyLayersPtr & top_contacts,MyLayerStorage & layer_storage) const1747 PrintObjectSupportMaterial::MyLayersPtr PrintObjectSupportMaterial::raft_and_intermediate_support_layers(
1748 const PrintObject &object,
1749 const MyLayersPtr &bottom_contacts,
1750 const MyLayersPtr &top_contacts,
1751 MyLayerStorage &layer_storage) const
1752 {
1753 MyLayersPtr intermediate_layers;
1754
1755 // Collect and sort the extremes (bottoms of the top contacts and tops of the bottom contacts).
1756 MyLayersPtr extremes;
1757 extremes.reserve(top_contacts.size() + bottom_contacts.size());
1758 for (size_t i = 0; i < top_contacts.size(); ++ i)
1759 // Bottoms of the top contact layers. In case of non-soluble supports,
1760 // the top contact layer thickness is not known yet.
1761 extremes.push_back(top_contacts[i]);
1762 for (size_t i = 0; i < bottom_contacts.size(); ++ i)
1763 // Tops of the bottom contact layers.
1764 extremes.push_back(bottom_contacts[i]);
1765 if (extremes.empty())
1766 return intermediate_layers;
1767
1768 auto layer_extreme_lower = [](const MyLayer *l1, const MyLayer *l2) {
1769 coordf_t z1 = l1->extreme_z();
1770 coordf_t z2 = l2->extreme_z();
1771 // If the layers are aligned, return the top contact surface first.
1772 return z1 < z2 || (z1 == z2 && l1->layer_type == PrintObjectSupportMaterial::sltTopContact && l2->layer_type == PrintObjectSupportMaterial::sltBottomContact);
1773 };
1774 std::sort(extremes.begin(), extremes.end(), layer_extreme_lower);
1775
1776 assert(extremes.empty() ||
1777 (extremes.front()->extreme_z() > m_slicing_params.raft_interface_top_z - EPSILON &&
1778 (m_slicing_params.raft_layers() == 1 || // only raft contact layer
1779 extremes.front()->layer_type == sltTopContact || // first extreme is a top contact layer
1780 extremes.front()->extreme_z() > m_slicing_params.first_print_layer_height - EPSILON)));
1781
1782 bool synchronize = this->synchronize_layers();
1783
1784 #ifdef _DEBUG
1785 // Verify that the extremes are separated by m_support_layer_height_min.
1786 for (size_t i = 1; i < extremes.size(); ++ i) {
1787 assert(extremes[i]->extreme_z() - extremes[i-1]->extreme_z() == 0. ||
1788 extremes[i]->extreme_z() - extremes[i-1]->extreme_z() > m_support_layer_height_min - EPSILON);
1789 assert(extremes[i]->extreme_z() - extremes[i-1]->extreme_z() > 0. ||
1790 extremes[i]->layer_type == extremes[i-1]->layer_type ||
1791 (extremes[i]->layer_type == sltBottomContact && extremes[i - 1]->layer_type == sltTopContact));
1792 }
1793 #endif
1794
1795 // Generate intermediate layers.
1796 // The first intermediate layer is the same as the 1st layer if there is no raft,
1797 // or the bottom of the first intermediate layer is aligned with the bottom of the raft contact layer.
1798 // Intermediate layers are always printed with a normal etrusion flow (non-bridging).
1799 size_t idx_layer_object = 0;
1800 for (size_t idx_extreme = 0; idx_extreme < extremes.size(); ++ idx_extreme) {
1801 MyLayer *extr2 = extremes[idx_extreme];
1802 coordf_t extr2z = extr2->extreme_z();
1803 if (std::abs(extr2z - m_slicing_params.raft_interface_top_z) < EPSILON) {
1804 // This is a raft contact layer, its height has been decided in this->top_contact_layers().
1805 assert(extr2->layer_type == sltTopContact);
1806 continue;
1807 }
1808 if (std::abs(extr2z - m_slicing_params.first_print_layer_height) < EPSILON) {
1809 // This is a bottom of a synchronized (or soluble) top contact layer, its height has been decided in this->top_contact_layers().
1810 assert(extr2->layer_type == sltTopContact);
1811 assert(extr2->bottom_z == m_slicing_params.first_print_layer_height);
1812 assert(extr2->print_z >= m_slicing_params.first_print_layer_height + m_support_layer_height_min - EPSILON);
1813 if (intermediate_layers.empty() || intermediate_layers.back()->print_z < m_slicing_params.first_print_layer_height) {
1814 MyLayer &layer_new = layer_allocate(layer_storage, sltIntermediate);
1815 layer_new.bottom_z = 0.;
1816 layer_new.print_z = m_slicing_params.first_print_layer_height;
1817 layer_new.height = m_slicing_params.first_print_layer_height;
1818 intermediate_layers.push_back(&layer_new);
1819 }
1820 continue;
1821 }
1822 assert(extr2z >= m_slicing_params.raft_interface_top_z + EPSILON);
1823 assert(extr2z >= m_slicing_params.first_print_layer_height + EPSILON);
1824 MyLayer *extr1 = (idx_extreme == 0) ? nullptr : extremes[idx_extreme - 1];
1825 // Fuse a support layer firmly to the raft top interface (not to the raft contacts).
1826 coordf_t extr1z = (extr1 == nullptr) ? m_slicing_params.raft_interface_top_z : extr1->extreme_z();
1827 assert(extr2z >= extr1z);
1828 assert(extr2z > extr1z || (extr1 != nullptr && extr2->layer_type == sltBottomContact));
1829 if (std::abs(extr1z) < EPSILON) {
1830 // This layer interval starts with the 1st layer. Print the 1st layer using the prescribed 1st layer thickness.
1831 assert(! m_slicing_params.has_raft());
1832 assert(intermediate_layers.empty() || intermediate_layers.back()->print_z <= m_slicing_params.first_print_layer_height);
1833 // At this point only layers above first_print_layer_heigth + EPSILON are expected as the other cases were captured earlier.
1834 assert(extr2z >= m_slicing_params.first_print_layer_height + EPSILON);
1835 // Generate a new intermediate layer.
1836 MyLayer &layer_new = layer_allocate(layer_storage, sltIntermediate);
1837 layer_new.bottom_z = 0.;
1838 layer_new.print_z = extr1z = m_slicing_params.first_print_layer_height;
1839 layer_new.height = extr1z;
1840 intermediate_layers.push_back(&layer_new);
1841 // Continue printing the other layers up to extr2z.
1842 }
1843 coordf_t dist = extr2z - extr1z;
1844 assert(dist >= 0.);
1845 if (dist == 0.)
1846 continue;
1847 // The new layers shall be at least m_support_layer_height_min thick.
1848 assert(dist >= m_support_layer_height_min - EPSILON);
1849 if (synchronize) {
1850 // Emit support layers synchronized with the object layers.
1851 // Find the first object layer, which has its print_z in this support Z range.
1852 while (idx_layer_object < object.layers().size() && object.layers()[idx_layer_object]->print_z < extr1z + EPSILON)
1853 ++ idx_layer_object;
1854 if (idx_layer_object == 0 && extr1z == m_slicing_params.raft_interface_top_z) {
1855 // Insert one base support layer below the object.
1856 MyLayer &layer_new = layer_allocate(layer_storage, sltIntermediate);
1857 layer_new.print_z = m_slicing_params.object_print_z_min;
1858 layer_new.bottom_z = m_slicing_params.raft_interface_top_z;
1859 layer_new.height = layer_new.print_z - layer_new.bottom_z;
1860 intermediate_layers.push_back(&layer_new);
1861 }
1862 // Emit all intermediate support layers synchronized with object layers up to extr2z.
1863 for (; idx_layer_object < object.layers().size() && object.layers()[idx_layer_object]->print_z < extr2z + EPSILON; ++ idx_layer_object) {
1864 MyLayer &layer_new = layer_allocate(layer_storage, sltIntermediate);
1865 layer_new.print_z = object.layers()[idx_layer_object]->print_z;
1866 layer_new.height = object.layers()[idx_layer_object]->height;
1867 layer_new.bottom_z = (idx_layer_object > 0) ? object.layers()[idx_layer_object - 1]->print_z : (layer_new.print_z - layer_new.height);
1868 assert(intermediate_layers.empty() || intermediate_layers.back()->print_z < layer_new.print_z + EPSILON);
1869 intermediate_layers.push_back(&layer_new);
1870 }
1871 } else {
1872 // Insert intermediate layers.
1873 size_t n_layers_extra = size_t(ceil(dist / m_slicing_params.max_suport_layer_height));
1874 assert(n_layers_extra > 0);
1875 coordf_t step = dist / coordf_t(n_layers_extra);
1876 if (extr1 != nullptr && extr1->layer_type == sltTopContact &&
1877 extr1->print_z + m_support_layer_height_min > extr1->bottom_z + step) {
1878 // The bottom extreme is a bottom of a top surface. Ensure that the gap
1879 // between the 1st intermediate layer print_z and extr1->print_z is not too small.
1880 assert(extr1->bottom_z + m_support_layer_height_min < extr1->print_z + EPSILON);
1881 // Generate the first intermediate layer.
1882 MyLayer &layer_new = layer_allocate(layer_storage, sltIntermediate);
1883 layer_new.bottom_z = extr1->bottom_z;
1884 layer_new.print_z = extr1z = extr1->print_z;
1885 layer_new.height = extr1->height;
1886 intermediate_layers.push_back(&layer_new);
1887 dist = extr2z - extr1z;
1888 n_layers_extra = size_t(ceil(dist / m_slicing_params.max_suport_layer_height));
1889 if (n_layers_extra == 0)
1890 continue;
1891 // Continue printing the other layers up to extr2z.
1892 step = dist / coordf_t(n_layers_extra);
1893 }
1894 if (! m_slicing_params.soluble_interface && extr2->layer_type == sltTopContact) {
1895 // This is a top interface layer, which does not have a height assigned yet. Do it now.
1896 assert(extr2->height == 0.);
1897 assert(extr1z > m_slicing_params.first_print_layer_height - EPSILON);
1898 extr2->height = step;
1899 extr2->bottom_z = extr2z = extr2->print_z - step;
1900 if (-- n_layers_extra == 0)
1901 continue;
1902 }
1903 coordf_t extr2z_large_steps = extr2z;
1904 // Take the largest allowed step in the Z axis until extr2z_large_steps is reached.
1905 for (size_t i = 0; i < n_layers_extra; ++ i) {
1906 MyLayer &layer_new = layer_allocate(layer_storage, sltIntermediate);
1907 if (i + 1 == n_layers_extra) {
1908 // Last intermediate layer added. Align the last entered layer with extr2z_large_steps exactly.
1909 layer_new.bottom_z = (i == 0) ? extr1z : intermediate_layers.back()->print_z;
1910 layer_new.print_z = extr2z_large_steps;
1911 layer_new.height = layer_new.print_z - layer_new.bottom_z;
1912 }
1913 else {
1914 // Intermediate layer, not the last added.
1915 layer_new.height = step;
1916 layer_new.bottom_z = extr1z + i * step;
1917 layer_new.print_z = layer_new.bottom_z + step;
1918 }
1919 assert(intermediate_layers.empty() || intermediate_layers.back()->print_z <= layer_new.print_z);
1920 intermediate_layers.push_back(&layer_new);
1921 }
1922 }
1923 }
1924
1925 #ifdef _DEBUG
1926 for (size_t i = 0; i < top_contacts.size(); ++i)
1927 assert(top_contacts[i]->height > 0.);
1928 #endif /* _DEBUG */
1929
1930 return intermediate_layers;
1931 }
1932
1933 // At this stage there shall be intermediate_layers allocated between bottom_contacts and top_contacts, but they have no polygons assigned.
1934 // Also the bottom/top_contacts shall have a layer thickness assigned already.
generate_base_layers(const PrintObject & object,const MyLayersPtr & bottom_contacts,const MyLayersPtr & top_contacts,MyLayersPtr & intermediate_layers,const std::vector<Polygons> & layer_support_areas) const1935 void PrintObjectSupportMaterial::generate_base_layers(
1936 const PrintObject &object,
1937 const MyLayersPtr &bottom_contacts,
1938 const MyLayersPtr &top_contacts,
1939 MyLayersPtr &intermediate_layers,
1940 const std::vector<Polygons> &layer_support_areas) const
1941 {
1942 #ifdef SLIC3R_DEBUG
1943 static int iRun = 0;
1944 #endif /* SLIC3R_DEBUG */
1945
1946 if (top_contacts.empty())
1947 // No top contacts -> no intermediate layers will be produced.
1948 return;
1949
1950 // coordf_t fillet_radius_scaled = scale_(m_object_config->support_material_spacing);
1951
1952 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::generate_base_layers() in parallel - start";
1953 tbb::parallel_for(
1954 tbb::blocked_range<size_t>(0, intermediate_layers.size()),
1955 [this, &object, &bottom_contacts, &top_contacts, &intermediate_layers, &layer_support_areas](const tbb::blocked_range<size_t>& range) {
1956 // index -2 means not initialized yet, -1 means intialized and decremented to 0 and then -1.
1957 int idx_top_contact_above = -2;
1958 int idx_bottom_contact_overlapping = -2;
1959 int idx_object_layer_above = -2;
1960 // Counting down due to the way idx_lower_or_equal caches indices to avoid repeated binary search over the complete sequence.
1961 for (int idx_intermediate = int(range.end()) - 1; idx_intermediate >= int(range.begin()); -- idx_intermediate)
1962 {
1963 BOOST_LOG_TRIVIAL(trace) << "Support generator - generate_base_layers - creating layer " <<
1964 idx_intermediate << " of " << intermediate_layers.size();
1965 MyLayer &layer_intermediate = *intermediate_layers[idx_intermediate];
1966 // Layers must be sorted by print_z.
1967 assert(idx_intermediate == 0 || layer_intermediate.print_z >= intermediate_layers[idx_intermediate - 1]->print_z);
1968
1969 // Find a top_contact layer touching the layer_intermediate from above, if any, and collect its polygons into polygons_new.
1970 // New polygons for layer_intermediate.
1971 Polygons polygons_new;
1972
1973 // Use the precomputed layer_support_areas.
1974 idx_object_layer_above = std::max(0, idx_lower_or_equal(object.layers(), idx_object_layer_above,
1975 [&layer_intermediate](const Layer *layer){ return layer->print_z <= layer_intermediate.print_z + EPSILON; }));
1976 polygons_new = layer_support_areas[idx_object_layer_above];
1977
1978 // Polygons to trim polygons_new.
1979 Polygons polygons_trimming;
1980
1981 // Trimming the base layer with any overlapping top layer.
1982 // Following cases are recognized:
1983 // 1) top.bottom_z >= base.top_z -> No overlap, no trimming needed.
1984 // 2) base.bottom_z >= top.print_z -> No overlap, no trimming needed.
1985 // 3) base.print_z > top.print_z && base.bottom_z >= top.bottom_z -> Overlap, which will be solved inside generate_toolpaths() by reducing the base layer height where it overlaps the top layer. No trimming needed here.
1986 // 4) base.print_z > top.bottom_z && base.bottom_z < top.bottom_z -> Base overlaps with top.bottom_z. This must not happen.
1987 // 5) base.print_z <= top.print_z && base.bottom_z >= top.bottom_z -> Base is fully inside top. Trim base by top.
1988 idx_top_contact_above = idx_lower_or_equal(top_contacts, idx_top_contact_above,
1989 [&layer_intermediate](const MyLayer *layer){ return layer->bottom_z <= layer_intermediate.print_z - EPSILON; });
1990 // Collect all the top_contact layer intersecting with this layer.
1991 for ( int idx_top_contact_overlapping = idx_top_contact_above; idx_top_contact_overlapping >= 0; -- idx_top_contact_overlapping) {
1992 MyLayer &layer_top_overlapping = *top_contacts[idx_top_contact_overlapping];
1993 if (layer_top_overlapping.print_z < layer_intermediate.bottom_z + EPSILON)
1994 break;
1995 // Base must not overlap with top.bottom_z.
1996 assert(! (layer_intermediate.print_z > layer_top_overlapping.bottom_z + EPSILON && layer_intermediate.bottom_z < layer_top_overlapping.bottom_z - EPSILON));
1997 if (layer_intermediate.print_z <= layer_top_overlapping.print_z + EPSILON && layer_intermediate.bottom_z >= layer_top_overlapping.bottom_z - EPSILON)
1998 // Base is fully inside top. Trim base by top.
1999 polygons_append(polygons_trimming, layer_top_overlapping.polygons);
2000 }
2001
2002 // Trimming the base layer with any overlapping bottom layer.
2003 // Following cases are recognized:
2004 // 1) bottom.bottom_z >= base.top_z -> No overlap, no trimming needed.
2005 // 2) base.bottom_z >= bottom.print_z -> No overlap, no trimming needed.
2006 // 3) base.print_z > bottom.bottom_z && base.bottom_z < bottom.bottom_z -> Overlap, which will be solved inside generate_toolpaths() by reducing the bottom layer height where it overlaps the base layer. No trimming needed here.
2007 // 4) base.print_z > bottom.print_z && base.bottom_z >= bottom.print_z -> Base overlaps with bottom.print_z. This must not happen.
2008 // 5) base.print_z <= bottom.print_z && base.bottom_z >= bottom.bottom_z -> Base is fully inside top. Trim base by top.
2009 idx_bottom_contact_overlapping = idx_lower_or_equal(bottom_contacts, idx_bottom_contact_overlapping,
2010 [&layer_intermediate](const MyLayer *layer){ return layer->bottom_print_z() <= layer_intermediate.print_z - EPSILON; });
2011 // Collect all the bottom_contacts layer intersecting with this layer.
2012 for (int i = idx_bottom_contact_overlapping; i >= 0; -- i) {
2013 MyLayer &layer_bottom_overlapping = *bottom_contacts[i];
2014 if (layer_bottom_overlapping.print_z < layer_intermediate.bottom_print_z() + EPSILON)
2015 break;
2016 // Base must not overlap with bottom.top_z.
2017 assert(! (layer_intermediate.print_z > layer_bottom_overlapping.print_z + EPSILON && layer_intermediate.bottom_z < layer_bottom_overlapping.print_z - EPSILON));
2018 if (layer_intermediate.print_z <= layer_bottom_overlapping.print_z + EPSILON && layer_intermediate.bottom_z >= layer_bottom_overlapping.bottom_print_z() - EPSILON)
2019 // Base is fully inside bottom. Trim base by bottom.
2020 polygons_append(polygons_trimming, layer_bottom_overlapping.polygons);
2021 }
2022
2023 #ifdef SLIC3R_DEBUG
2024 {
2025 BoundingBox bbox = get_extents(polygons_new);
2026 bbox.merge(get_extents(polygons_trimming));
2027 ::Slic3r::SVG svg(debug_out_path("support-intermediate-layers-raw-%d-%lf.svg", iRun, layer_intermediate.print_z), bbox);
2028 svg.draw(union_ex(polygons_new, false), "blue", 0.5f);
2029 svg.draw(to_polylines(polygons_new), "blue");
2030 svg.draw(union_ex(polygons_trimming, true), "red", 0.5f);
2031 svg.draw(to_polylines(polygons_trimming), "red");
2032 }
2033 #endif /* SLIC3R_DEBUG */
2034
2035 // Trim the polygons, store them.
2036 if (polygons_trimming.empty())
2037 layer_intermediate.polygons = std::move(polygons_new);
2038 else
2039 layer_intermediate.polygons = diff(
2040 polygons_new,
2041 polygons_trimming,
2042 true); // safety offset to merge the touching source polygons
2043 layer_intermediate.layer_type = sltBase;
2044
2045 #if 0
2046 // Fillet the base polygons and trim them again with the top, interface and contact layers.
2047 $base->{$i} = diff(
2048 offset2(
2049 $base->{$i},
2050 $fillet_radius_scaled,
2051 -$fillet_radius_scaled,
2052 # Use a geometric offsetting for filleting.
2053 JT_ROUND,
2054 0.2*$fillet_radius_scaled),
2055 $trim_polygons,
2056 false); // don't apply the safety offset.
2057 }
2058 #endif
2059 }
2060 });
2061 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::generate_base_layers() in parallel - end";
2062
2063 #ifdef SLIC3R_DEBUG
2064 for (MyLayersPtr::const_iterator it = intermediate_layers.begin(); it != intermediate_layers.end(); ++it)
2065 ::Slic3r::SVG::export_expolygons(
2066 debug_out_path("support-intermediate-layers-untrimmed-%d-%lf.svg", iRun, (*it)->print_z),
2067 union_ex((*it)->polygons, false));
2068 ++ iRun;
2069 #endif /* SLIC3R_DEBUG */
2070
2071 // trim_support_layers_by_object(object, intermediate_layers, 0., 0., m_gap_xy);
2072 this->trim_support_layers_by_object(object, intermediate_layers,
2073 m_slicing_params.soluble_interface ? 0. : m_object_config->support_material_contact_distance.value,
2074 m_slicing_params.soluble_interface ? 0. : m_object_config->support_material_contact_distance.value, m_gap_xy);
2075 }
2076
trim_support_layers_by_object(const PrintObject & object,MyLayersPtr & support_layers,const coordf_t gap_extra_above,const coordf_t gap_extra_below,const coordf_t gap_xy) const2077 void PrintObjectSupportMaterial::trim_support_layers_by_object(
2078 const PrintObject &object,
2079 MyLayersPtr &support_layers,
2080 const coordf_t gap_extra_above,
2081 const coordf_t gap_extra_below,
2082 const coordf_t gap_xy) const
2083 {
2084 const float gap_xy_scaled = float(scale_(gap_xy));
2085
2086 // Collect non-empty layers to be processed in parallel.
2087 // This is a good idea as pulling a thread from a thread pool for an empty task is expensive.
2088 MyLayersPtr nonempty_layers;
2089 nonempty_layers.reserve(support_layers.size());
2090 for (size_t idx_layer = 0; idx_layer < support_layers.size(); ++ idx_layer) {
2091 MyLayer *support_layer = support_layers[idx_layer];
2092 if (! support_layer->polygons.empty() && support_layer->print_z >= m_slicing_params.raft_contact_top_z + EPSILON)
2093 // Non-empty support layer and not a raft layer.
2094 nonempty_layers.push_back(support_layer);
2095 }
2096
2097 // For all intermediate support layers:
2098 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::trim_support_layers_by_object() in parallel - start";
2099 tbb::parallel_for(
2100 tbb::blocked_range<size_t>(0, nonempty_layers.size()),
2101 [this, &object, &nonempty_layers, gap_extra_above, gap_extra_below, gap_xy_scaled](const tbb::blocked_range<size_t>& range) {
2102 size_t idx_object_layer_overlapping = size_t(-1);
2103 for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++ idx_layer) {
2104 MyLayer &support_layer = *nonempty_layers[idx_layer];
2105 // BOOST_LOG_TRIVIAL(trace) << "Support generator - trim_support_layers_by_object - trimmming non-empty layer " << idx_layer << " of " << nonempty_layers.size();
2106 assert(! support_layer.polygons.empty() && support_layer.print_z >= m_slicing_params.raft_contact_top_z + EPSILON);
2107 // Find the overlapping object layers including the extra above / below gap.
2108 coordf_t z_threshold = support_layer.print_z - support_layer.height - gap_extra_below + EPSILON;
2109 idx_object_layer_overlapping = idx_higher_or_equal(
2110 object.layers(), idx_object_layer_overlapping,
2111 [z_threshold](const Layer *layer){ return layer->print_z >= z_threshold; });
2112 // Collect all the object layers intersecting with this layer.
2113 Polygons polygons_trimming;
2114 size_t i = idx_object_layer_overlapping;
2115 for (; i < object.layers().size(); ++ i) {
2116 const Layer &object_layer = *object.layers()[i];
2117 if (object_layer.print_z - object_layer.height > support_layer.print_z + gap_extra_above - EPSILON)
2118 break;
2119 polygons_append(polygons_trimming, offset(object_layer.lslices, gap_xy_scaled, SUPPORT_SURFACES_OFFSET_PARAMETERS));
2120 }
2121 if (! m_slicing_params.soluble_interface) {
2122 // Collect all bottom surfaces, which will be extruded with a bridging flow.
2123 for (; i < object.layers().size(); ++ i) {
2124 const Layer &object_layer = *object.layers()[i];
2125 bool some_region_overlaps = false;
2126 for (LayerRegion *region : object_layer.regions()) {
2127 coordf_t bridging_height = region->region()->bridging_height_avg(*this->m_print_config);
2128 if (object_layer.print_z - bridging_height > support_layer.print_z + gap_extra_above - EPSILON)
2129 break;
2130 some_region_overlaps = true;
2131 polygons_append(polygons_trimming,
2132 offset(to_expolygons(region->fill_surfaces.filter_by_type(stBottomBridge)),
2133 gap_xy_scaled, SUPPORT_SURFACES_OFFSET_PARAMETERS));
2134 if (region->region()->config().overhangs.value)
2135 SupportMaterialInternal::collect_bridging_perimeter_areas(region->perimeters, gap_xy_scaled, polygons_trimming);
2136 }
2137 if (! some_region_overlaps)
2138 break;
2139 }
2140 }
2141 // $layer->slices contains the full shape of layer, thus including
2142 // perimeter's width. $support contains the full shape of support
2143 // material, thus including the width of its foremost extrusion.
2144 // We leave a gap equal to a full extrusion width.
2145 support_layer.polygons = diff(support_layer.polygons, polygons_trimming);
2146 }
2147 });
2148 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::trim_support_layers_by_object() in parallel - end";
2149 }
2150
generate_raft_base(const MyLayersPtr & top_contacts,const MyLayersPtr & interface_layers,const MyLayersPtr & base_layers,MyLayerStorage & layer_storage) const2151 PrintObjectSupportMaterial::MyLayersPtr PrintObjectSupportMaterial::generate_raft_base(
2152 const MyLayersPtr &top_contacts,
2153 const MyLayersPtr &interface_layers,
2154 const MyLayersPtr &base_layers,
2155 MyLayerStorage &layer_storage) const
2156 {
2157 // How much to inflate the support columns to be stable. This also applies to the 1st layer, if no raft layers are to be printed.
2158 const float inflate_factor_fine = float(scale_((m_slicing_params.raft_layers() > 1) ? 0.5 : EPSILON));
2159 const float inflate_factor_1st_layer = float(scale_(3.)) - inflate_factor_fine;
2160 MyLayer *contacts = top_contacts .empty() ? nullptr : top_contacts .front();
2161 MyLayer *interfaces = interface_layers.empty() ? nullptr : interface_layers.front();
2162 MyLayer *columns_base = base_layers .empty() ? nullptr : base_layers .front();
2163 if (contacts != nullptr && contacts->print_z > std::max(m_slicing_params.first_print_layer_height, m_slicing_params.raft_contact_top_z) + EPSILON)
2164 // This is not the raft contact layer.
2165 contacts = nullptr;
2166 if (interfaces != nullptr && interfaces->bottom_print_z() > m_slicing_params.raft_interface_top_z + EPSILON)
2167 // This is not the raft column base layer.
2168 interfaces = nullptr;
2169 if (columns_base != nullptr && columns_base->bottom_print_z() > m_slicing_params.raft_interface_top_z + EPSILON)
2170 // This is not the raft interface layer.
2171 columns_base = nullptr;
2172
2173 Polygons interface_polygons;
2174 if (contacts != nullptr && ! contacts->polygons.empty())
2175 polygons_append(interface_polygons, offset(contacts->polygons, inflate_factor_fine, SUPPORT_SURFACES_OFFSET_PARAMETERS));
2176 if (interfaces != nullptr && ! interfaces->polygons.empty())
2177 polygons_append(interface_polygons, offset(interfaces->polygons, inflate_factor_fine, SUPPORT_SURFACES_OFFSET_PARAMETERS));
2178
2179 // Output vector.
2180 MyLayersPtr raft_layers;
2181
2182 if (m_slicing_params.raft_layers() > 1) {
2183 Polygons base;
2184 Polygons columns;
2185 if (columns_base != nullptr) {
2186 base = columns_base->polygons;
2187 columns = base;
2188 if (! interface_polygons.empty())
2189 // Trim the 1st layer columns with the inflated interface polygons.
2190 columns = diff(columns, interface_polygons);
2191 }
2192 if (! interface_polygons.empty()) {
2193 // Merge the untrimmed columns base with the expanded raft interface, to be used for the support base and interface.
2194 base = union_(base, interface_polygons);
2195 }
2196 // Do not add the raft contact layer, only add the raft layers below the contact layer.
2197 // Insert the 1st layer.
2198 {
2199 MyLayer &new_layer = layer_allocate(layer_storage, (m_slicing_params.base_raft_layers > 0) ? sltRaftBase : sltRaftInterface);
2200 raft_layers.push_back(&new_layer);
2201 new_layer.print_z = m_slicing_params.first_print_layer_height;
2202 new_layer.height = m_slicing_params.first_print_layer_height;
2203 new_layer.bottom_z = 0.;
2204 new_layer.polygons = offset(base, inflate_factor_1st_layer);
2205 }
2206 // Insert the base layers.
2207 for (size_t i = 1; i < m_slicing_params.base_raft_layers; ++ i) {
2208 coordf_t print_z = raft_layers.back()->print_z;
2209 MyLayer &new_layer = layer_allocate(layer_storage, sltRaftBase);
2210 raft_layers.push_back(&new_layer);
2211 new_layer.print_z = print_z + m_slicing_params.base_raft_layer_height;
2212 new_layer.height = m_slicing_params.base_raft_layer_height;
2213 new_layer.bottom_z = print_z;
2214 new_layer.polygons = base;
2215 }
2216 // Insert the interface layers.
2217 for (size_t i = 1; i < m_slicing_params.interface_raft_layers; ++ i) {
2218 coordf_t print_z = raft_layers.back()->print_z;
2219 MyLayer &new_layer = layer_allocate(layer_storage, sltRaftInterface);
2220 raft_layers.push_back(&new_layer);
2221 new_layer.print_z = print_z + m_slicing_params.interface_raft_layer_height;
2222 new_layer.height = m_slicing_params.interface_raft_layer_height;
2223 new_layer.bottom_z = print_z;
2224 new_layer.polygons = interface_polygons;
2225 //FIXME misusing contact_polygons for support columns.
2226 new_layer.contact_polygons = new Polygons(columns);
2227 }
2228 } else if (columns_base != nullptr) {
2229 // Expand the bases of the support columns in the 1st layer.
2230 columns_base->polygons = diff(
2231 offset(columns_base->polygons, inflate_factor_1st_layer),
2232 offset(m_object->layers().front()->lslices, (float)scale_(m_gap_xy), SUPPORT_SURFACES_OFFSET_PARAMETERS));
2233 if (contacts != nullptr)
2234 columns_base->polygons = diff(columns_base->polygons, interface_polygons);
2235 }
2236
2237 return raft_layers;
2238 }
2239
2240 // Convert some of the intermediate layers into top/bottom interface layers.
generate_interface_layers(const MyLayersPtr & bottom_contacts,const MyLayersPtr & top_contacts,MyLayersPtr & intermediate_layers,MyLayerStorage & layer_storage) const2241 PrintObjectSupportMaterial::MyLayersPtr PrintObjectSupportMaterial::generate_interface_layers(
2242 const MyLayersPtr &bottom_contacts,
2243 const MyLayersPtr &top_contacts,
2244 MyLayersPtr &intermediate_layers,
2245 MyLayerStorage &layer_storage) const
2246 {
2247 // my $area_threshold = $self->interface_flow->scaled_spacing ** 2;
2248
2249 MyLayersPtr interface_layers;
2250 // Contact layer is considered an interface layer, therefore run the following block only if support_material_interface_layers > 1.
2251 if (! intermediate_layers.empty() && m_object_config->support_material_interface_layers.value > 1) {
2252 // For all intermediate layers, collect top contact surfaces, which are not further than support_material_interface_layers.
2253 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::generate_interface_layers() in parallel - start";
2254 interface_layers.assign(intermediate_layers.size(), nullptr);
2255 tbb::spin_mutex layer_storage_mutex;
2256 tbb::parallel_for(tbb::blocked_range<size_t>(0, intermediate_layers.size()),
2257 [this, &bottom_contacts, &top_contacts, &intermediate_layers, &layer_storage, &layer_storage_mutex, &interface_layers](const tbb::blocked_range<size_t>& range) {
2258 // Index of the first top contact layer intersecting the current intermediate layer.
2259 size_t idx_top_contact_first = size_t(-1);
2260 // Index of the first bottom contact layer intersecting the current intermediate layer.
2261 size_t idx_bottom_contact_first = size_t(-1);
2262 for (size_t idx_intermediate_layer = range.begin(); idx_intermediate_layer < range.end(); ++ idx_intermediate_layer) {
2263 MyLayer &intermediate_layer = *intermediate_layers[idx_intermediate_layer];
2264 // Top / bottom Z coordinate of a slab, over which we are collecting the top / bottom contact surfaces.
2265 coordf_t top_z = intermediate_layers[std::min<int>(intermediate_layers.size()-1, idx_intermediate_layer + m_object_config->support_material_interface_layers - 1)]->print_z;
2266 coordf_t bottom_z = intermediate_layers[std::max<int>(0, int(idx_intermediate_layer) - int(m_object_config->support_material_interface_layers) + 1)]->bottom_z;
2267 // Move idx_top_contact_first up until above the current print_z.
2268 idx_top_contact_first = idx_higher_or_equal(top_contacts, idx_top_contact_first, [&intermediate_layer](const MyLayer *layer){ return layer->print_z >= intermediate_layer.print_z; }); // - EPSILON
2269 // Collect the top contact areas above this intermediate layer, below top_z.
2270 Polygons polygons_top_contact_projected;
2271 for (size_t idx_top_contact = idx_top_contact_first; idx_top_contact < top_contacts.size(); ++ idx_top_contact) {
2272 const MyLayer &top_contact_layer = *top_contacts[idx_top_contact];
2273 //FIXME maybe this adds one interface layer in excess?
2274 if (top_contact_layer.bottom_z - EPSILON > top_z)
2275 break;
2276 polygons_append(polygons_top_contact_projected, top_contact_layer.polygons);
2277 }
2278 // Move idx_bottom_contact_first up until touching bottom_z.
2279 idx_bottom_contact_first = idx_higher_or_equal(bottom_contacts, idx_bottom_contact_first, [bottom_z](const MyLayer *layer){ return layer->print_z >= bottom_z - EPSILON; });
2280 // Collect the top contact areas above this intermediate layer, below top_z.
2281 Polygons polygons_bottom_contact_projected;
2282 for (size_t idx_bottom_contact = idx_bottom_contact_first; idx_bottom_contact < bottom_contacts.size(); ++ idx_bottom_contact) {
2283 const MyLayer &bottom_contact_layer = *bottom_contacts[idx_bottom_contact];
2284 if (bottom_contact_layer.print_z - EPSILON > intermediate_layer.bottom_z)
2285 break;
2286 polygons_append(polygons_bottom_contact_projected, bottom_contact_layer.polygons);
2287 }
2288
2289 if (polygons_top_contact_projected.empty() && polygons_bottom_contact_projected.empty())
2290 continue;
2291
2292 // Insert a new layer into top_interface_layers.
2293 MyLayer &layer_new = layer_allocate(layer_storage, layer_storage_mutex,
2294 polygons_top_contact_projected.empty() ? sltBottomInterface : sltTopInterface);
2295 layer_new.print_z = intermediate_layer.print_z;
2296 layer_new.bottom_z = intermediate_layer.bottom_z;
2297 layer_new.height = intermediate_layer.height;
2298 layer_new.bridging = intermediate_layer.bridging;
2299 interface_layers[idx_intermediate_layer] = &layer_new;
2300
2301 polygons_append(polygons_top_contact_projected, polygons_bottom_contact_projected);
2302 polygons_top_contact_projected = union_(polygons_top_contact_projected, true);
2303 layer_new.polygons = intersection(intermediate_layer.polygons, polygons_top_contact_projected);
2304 //FIXME filter layer_new.polygons islands by a minimum area?
2305 // $interface_area = [ grep abs($_->area) >= $area_threshold, @$interface_area ];
2306 intermediate_layer.polygons = diff(intermediate_layer.polygons, polygons_top_contact_projected, false);
2307 }
2308 });
2309
2310 // Compress contact_out, remove the nullptr items.
2311 remove_nulls(interface_layers);
2312 BOOST_LOG_TRIVIAL(debug) << "PrintObjectSupportMaterial::generate_interface_layers() in parallel - start";
2313 }
2314
2315 return interface_layers;
2316 }
2317
fill_expolygons_generate_paths(ExtrusionEntitiesPtr & dst,const ExPolygons & expolygons,Fill * filler,float density,ExtrusionRole role,const Flow & flow)2318 static inline void fill_expolygons_generate_paths(
2319 ExtrusionEntitiesPtr &dst,
2320 const ExPolygons &expolygons,
2321 Fill *filler,
2322 float density,
2323 ExtrusionRole role,
2324 const Flow &flow)
2325 {
2326 FillParams fill_params;
2327 fill_params.density = density;
2328 fill_params.dont_adjust = true;
2329 for (const ExPolygon &expoly : expolygons) {
2330 Surface surface(stInternal, expoly);
2331 Polylines polylines;
2332 try {
2333 polylines = filler->fill_surface(&surface, fill_params);
2334 } catch (InfillFailedException &) {
2335 }
2336 extrusion_entities_append_paths(
2337 dst,
2338 std::move(polylines),
2339 role,
2340 flow.mm3_per_mm(), flow.width, flow.height);
2341 }
2342 }
2343
fill_expolygons_generate_paths(ExtrusionEntitiesPtr & dst,ExPolygons && expolygons,Fill * filler,float density,ExtrusionRole role,const Flow & flow)2344 static inline void fill_expolygons_generate_paths(
2345 ExtrusionEntitiesPtr &dst,
2346 ExPolygons &&expolygons,
2347 Fill *filler,
2348 float density,
2349 ExtrusionRole role,
2350 const Flow &flow)
2351 {
2352 FillParams fill_params;
2353 fill_params.density = density;
2354 fill_params.dont_adjust = true;
2355 for (ExPolygon &expoly : expolygons) {
2356 Surface surface(stInternal, std::move(expoly));
2357 Polylines polylines;
2358 try {
2359 polylines = filler->fill_surface(&surface, fill_params);
2360 } catch (InfillFailedException &) {
2361 }
2362 extrusion_entities_append_paths(
2363 dst,
2364 std::move(polylines),
2365 role,
2366 flow.mm3_per_mm(), flow.width, flow.height);
2367 }
2368 }
2369
2370 // Support layers, partially processed.
2371 struct MyLayerExtruded
2372 {
MyLayerExtrudedSlic3r::MyLayerExtruded2373 MyLayerExtruded() : layer(nullptr), m_polygons_to_extrude(nullptr) {}
~MyLayerExtrudedSlic3r::MyLayerExtruded2374 ~MyLayerExtruded() { delete m_polygons_to_extrude; m_polygons_to_extrude = nullptr; }
2375
emptySlic3r::MyLayerExtruded2376 bool empty() const {
2377 return layer == nullptr || layer->polygons.empty();
2378 }
2379
set_polygons_to_extrudeSlic3r::MyLayerExtruded2380 void set_polygons_to_extrude(Polygons &&polygons) {
2381 if (m_polygons_to_extrude == nullptr)
2382 m_polygons_to_extrude = new Polygons(std::move(polygons));
2383 else
2384 *m_polygons_to_extrude = std::move(polygons);
2385 }
polygons_to_extrudeSlic3r::MyLayerExtruded2386 Polygons& polygons_to_extrude() { return (m_polygons_to_extrude == nullptr) ? layer->polygons : *m_polygons_to_extrude; }
polygons_to_extrudeSlic3r::MyLayerExtruded2387 const Polygons& polygons_to_extrude() const { return (m_polygons_to_extrude == nullptr) ? layer->polygons : *m_polygons_to_extrude; }
2388
could_mergeSlic3r::MyLayerExtruded2389 bool could_merge(const MyLayerExtruded &other) const {
2390 return ! this->empty() && ! other.empty() &&
2391 std::abs(this->layer->height - other.layer->height) < EPSILON &&
2392 this->layer->bridging == other.layer->bridging;
2393 }
2394
2395 // Merge regions, perform boolean union over the merged polygons.
mergeSlic3r::MyLayerExtruded2396 void merge(MyLayerExtruded &&other) {
2397 assert(this->could_merge(other));
2398 // 1) Merge the rest polygons to extrude, if there are any.
2399 if (other.m_polygons_to_extrude != nullptr) {
2400 if (m_polygons_to_extrude == nullptr) {
2401 // This layer has no extrusions generated yet, if it has no m_polygons_to_extrude (its area to extrude was not reduced yet).
2402 assert(this->extrusions.empty());
2403 m_polygons_to_extrude = new Polygons(this->layer->polygons);
2404 }
2405 Slic3r::polygons_append(*m_polygons_to_extrude, std::move(*other.m_polygons_to_extrude));
2406 *m_polygons_to_extrude = union_(*m_polygons_to_extrude, true);
2407 delete other.m_polygons_to_extrude;
2408 other.m_polygons_to_extrude = nullptr;
2409 } else if (m_polygons_to_extrude != nullptr) {
2410 assert(other.m_polygons_to_extrude == nullptr);
2411 // The other layer has no extrusions generated yet, if it has no m_polygons_to_extrude (its area to extrude was not reduced yet).
2412 assert(other.extrusions.empty());
2413 Slic3r::polygons_append(*m_polygons_to_extrude, other.layer->polygons);
2414 *m_polygons_to_extrude = union_(*m_polygons_to_extrude, true);
2415 }
2416 // 2) Merge the extrusions.
2417 this->extrusions.insert(this->extrusions.end(), other.extrusions.begin(), other.extrusions.end());
2418 other.extrusions.clear();
2419 // 3) Merge the infill polygons.
2420 Slic3r::polygons_append(this->layer->polygons, std::move(other.layer->polygons));
2421 this->layer->polygons = union_(this->layer->polygons, true);
2422 other.layer->polygons.clear();
2423 }
2424
polygons_appendSlic3r::MyLayerExtruded2425 void polygons_append(Polygons &dst) const {
2426 if (layer != NULL && ! layer->polygons.empty())
2427 Slic3r::polygons_append(dst, layer->polygons);
2428 }
2429
2430 // The source layer. It carries the height and extrusion type (bridging / non bridging, extrusion height).
2431 PrintObjectSupportMaterial::MyLayer *layer;
2432 // Collect extrusions. They will be exported sorted by the bottom height.
2433 ExtrusionEntitiesPtr extrusions;
2434 // In case the extrusions are non-empty, m_polygons_to_extrude may contain the rest areas yet to be filled by additional support.
2435 // This is useful mainly for the loop interfaces, which are generated before the zig-zag infills.
2436 Polygons *m_polygons_to_extrude;
2437 };
2438
2439 typedef std::vector<MyLayerExtruded*> MyLayerExtrudedPtrs;
2440
2441 struct LoopInterfaceProcessor
2442 {
LoopInterfaceProcessorSlic3r::LoopInterfaceProcessor2443 LoopInterfaceProcessor(coordf_t circle_r) :
2444 n_contact_loops(0),
2445 circle_radius(circle_r),
2446 circle_distance(circle_r * 3.)
2447 {
2448 // Shape of the top contact area.
2449 circle.points.reserve(6);
2450 for (size_t i = 0; i < 6; ++ i) {
2451 double angle = double(i) * M_PI / 3.;
2452 circle.points.push_back(Point(circle_radius * cos(angle), circle_radius * sin(angle)));
2453 }
2454 }
2455
2456 // Generate loop contacts at the top_contact_layer,
2457 // trim the top_contact_layer->polygons with the areas covered by the loops.
2458 void generate(MyLayerExtruded &top_contact_layer, const Flow &interface_flow_src) const;
2459
2460 int n_contact_loops;
2461 coordf_t circle_radius;
2462 coordf_t circle_distance;
2463 Polygon circle;
2464 };
2465
generate(MyLayerExtruded & top_contact_layer,const Flow & interface_flow_src) const2466 void LoopInterfaceProcessor::generate(MyLayerExtruded &top_contact_layer, const Flow &interface_flow_src) const
2467 {
2468 if (n_contact_loops == 0 || top_contact_layer.empty())
2469 return;
2470
2471 Flow flow = interface_flow_src;
2472 flow.height = float(top_contact_layer.layer->height);
2473
2474 Polygons overhang_polygons;
2475 if (top_contact_layer.layer->overhang_polygons != nullptr)
2476 overhang_polygons = std::move(*top_contact_layer.layer->overhang_polygons);
2477
2478 // Generate the outermost loop.
2479 // Find centerline of the external loop (or any other kind of extrusions should the loop be skipped)
2480 ExPolygons top_contact_expolygons = offset_ex(union_ex(top_contact_layer.layer->polygons), - 0.5f * flow.scaled_width());
2481
2482 // Grid size and bit shifts for quick and exact to/from grid coordinates manipulation.
2483 coord_t circle_grid_resolution = 1;
2484 coord_t circle_grid_powerof2 = 0;
2485 {
2486 // epsilon to account for rounding errors
2487 coord_t circle_grid_resolution_non_powerof2 = coord_t(2. * circle_distance + 3.);
2488 while (circle_grid_resolution < circle_grid_resolution_non_powerof2) {
2489 circle_grid_resolution <<= 1;
2490 ++ circle_grid_powerof2;
2491 }
2492 }
2493
2494 struct PointAccessor {
2495 const Point* operator()(const Point &pt) const { return &pt; }
2496 };
2497 typedef ClosestPointInRadiusLookup<Point, PointAccessor> ClosestPointLookupType;
2498
2499 Polygons loops0;
2500 {
2501 // find centerline of the external loop of the contours
2502 // Only consider the loops facing the overhang.
2503 Polygons external_loops;
2504 // Holes in the external loops.
2505 Polygons circles;
2506 Polygons overhang_with_margin = offset(union_ex(overhang_polygons), 0.5f * flow.scaled_width());
2507 for (ExPolygons::iterator it_contact_expoly = top_contact_expolygons.begin(); it_contact_expoly != top_contact_expolygons.end(); ++ it_contact_expoly) {
2508 // Store the circle centers placed for an expolygon into a regular grid, hashed by the circle centers.
2509 ClosestPointLookupType circle_centers_lookup(coord_t(circle_distance - SCALED_EPSILON));
2510 Points circle_centers;
2511 Point center_last;
2512 // For each contour of the expolygon, start with the outer contour, continue with the holes.
2513 for (size_t i_contour = 0; i_contour <= it_contact_expoly->holes.size(); ++ i_contour) {
2514 Polygon &contour = (i_contour == 0) ? it_contact_expoly->contour : it_contact_expoly->holes[i_contour - 1];
2515 const Point *seg_current_pt = nullptr;
2516 coordf_t seg_current_t = 0.;
2517 if (! intersection_pl((Polylines)contour.split_at_first_point(), overhang_with_margin).empty()) {
2518 // The contour is below the overhang at least to some extent.
2519 //FIXME ideally one would place the circles below the overhang only.
2520 // Walk around the contour and place circles so their centers are not closer than circle_distance from each other.
2521 if (circle_centers.empty()) {
2522 // Place the first circle.
2523 seg_current_pt = &contour.points.front();
2524 seg_current_t = 0.;
2525 center_last = *seg_current_pt;
2526 circle_centers_lookup.insert(center_last);
2527 circle_centers.push_back(center_last);
2528 }
2529 for (Points::const_iterator it = contour.points.begin() + 1; it != contour.points.end(); ++it) {
2530 // Is it possible to place a circle on this segment? Is it not too close to any of the circles already placed on this contour?
2531 const Point &p1 = *(it-1);
2532 const Point &p2 = *it;
2533 // Intersection of a ray (p1, p2) with a circle placed at center_last, with radius of circle_distance.
2534 const Vec2d v_seg(coordf_t(p2(0)) - coordf_t(p1(0)), coordf_t(p2(1)) - coordf_t(p1(1)));
2535 const Vec2d v_cntr(coordf_t(p1(0) - center_last(0)), coordf_t(p1(1) - center_last(1)));
2536 coordf_t a = v_seg.squaredNorm();
2537 coordf_t b = 2. * v_seg.dot(v_cntr);
2538 coordf_t c = v_cntr.squaredNorm() - circle_distance * circle_distance;
2539 coordf_t disc = b * b - 4. * a * c;
2540 if (disc > 0.) {
2541 // The circle intersects a ray. Avoid the parts of the segment inside the circle.
2542 coordf_t t1 = (-b - sqrt(disc)) / (2. * a);
2543 coordf_t t2 = (-b + sqrt(disc)) / (2. * a);
2544 coordf_t t0 = (seg_current_pt == &p1) ? seg_current_t : 0.;
2545 // Take the lowest t in <t0, 1.>, excluding <t1, t2>.
2546 coordf_t t;
2547 if (t0 <= t1)
2548 t = t0;
2549 else if (t2 <= 1.)
2550 t = t2;
2551 else {
2552 // Try the following segment.
2553 seg_current_pt = nullptr;
2554 continue;
2555 }
2556 seg_current_pt = &p1;
2557 seg_current_t = t;
2558 center_last = Point(p1(0) + coord_t(v_seg(0) * t), p1(1) + coord_t(v_seg(1) * t));
2559 // It has been verified that the new point is far enough from center_last.
2560 // Ensure, that it is far enough from all the centers.
2561 std::pair<const Point*, coordf_t> circle_closest = circle_centers_lookup.find(center_last);
2562 if (circle_closest.first != nullptr) {
2563 -- it;
2564 continue;
2565 }
2566 } else {
2567 // All of the segment is outside the circle. Take the first point.
2568 seg_current_pt = &p1;
2569 seg_current_t = 0.;
2570 center_last = p1;
2571 }
2572 // Place the first circle.
2573 circle_centers_lookup.insert(center_last);
2574 circle_centers.push_back(center_last);
2575 }
2576 external_loops.push_back(std::move(contour));
2577 for (const Point ¢er : circle_centers) {
2578 circles.push_back(circle);
2579 circles.back().translate(center);
2580 }
2581 }
2582 }
2583 }
2584 // Apply a pattern to the external loops.
2585 loops0 = diff(external_loops, circles);
2586 }
2587
2588 Polylines loop_lines;
2589 {
2590 // make more loops
2591 Polygons loop_polygons = loops0;
2592 for (int i = 1; i < n_contact_loops; ++ i)
2593 polygons_append(loop_polygons,
2594 offset2(
2595 loops0,
2596 - i * flow.scaled_spacing() - 0.5f * flow.scaled_spacing(),
2597 0.5f * flow.scaled_spacing()));
2598 // Clip such loops to the side oriented towards the object.
2599 // Collect split points, so they will be recognized after the clipping.
2600 // At the split points the clipped pieces will be stitched back together.
2601 loop_lines.reserve(loop_polygons.size());
2602 std::unordered_map<Point, int, PointHash> map_split_points;
2603 for (Polygons::const_iterator it = loop_polygons.begin(); it != loop_polygons.end(); ++ it) {
2604 assert(map_split_points.find(it->first_point()) == map_split_points.end());
2605 map_split_points[it->first_point()] = -1;
2606 loop_lines.push_back(it->split_at_first_point());
2607 }
2608 loop_lines = intersection_pl(loop_lines, offset(overhang_polygons, scale_(SUPPORT_MATERIAL_MARGIN)));
2609 // Because a closed loop has been split to a line, loop_lines may contain continuous segments split to 2 pieces.
2610 // Try to connect them.
2611 for (int i_line = 0; i_line < int(loop_lines.size()); ++ i_line) {
2612 Polyline &polyline = loop_lines[i_line];
2613 auto it = map_split_points.find(polyline.first_point());
2614 if (it != map_split_points.end()) {
2615 // This is a stitching point.
2616 // If this assert triggers, multiple source polygons likely intersected at this point.
2617 assert(it->second != -2);
2618 if (it->second < 0) {
2619 // First occurence.
2620 it->second = i_line;
2621 } else {
2622 // Second occurence. Join the lines.
2623 Polyline &polyline_1st = loop_lines[it->second];
2624 assert(polyline_1st.first_point() == it->first || polyline_1st.last_point() == it->first);
2625 if (polyline_1st.first_point() == it->first)
2626 polyline_1st.reverse();
2627 polyline_1st.append(std::move(polyline));
2628 it->second = -2;
2629 }
2630 continue;
2631 }
2632 it = map_split_points.find(polyline.last_point());
2633 if (it != map_split_points.end()) {
2634 // This is a stitching point.
2635 // If this assert triggers, multiple source polygons likely intersected at this point.
2636 assert(it->second != -2);
2637 if (it->second < 0) {
2638 // First occurence.
2639 it->second = i_line;
2640 } else {
2641 // Second occurence. Join the lines.
2642 Polyline &polyline_1st = loop_lines[it->second];
2643 assert(polyline_1st.first_point() == it->first || polyline_1st.last_point() == it->first);
2644 if (polyline_1st.first_point() == it->first)
2645 polyline_1st.reverse();
2646 polyline.reverse();
2647 polyline_1st.append(std::move(polyline));
2648 it->second = -2;
2649 }
2650 }
2651 }
2652 // Remove empty lines.
2653 remove_degenerate(loop_lines);
2654 }
2655
2656 // add the contact infill area to the interface area
2657 // note that growing loops by $circle_radius ensures no tiny
2658 // extrusions are left inside the circles; however it creates
2659 // a very large gap between loops and contact_infill_polygons, so maybe another
2660 // solution should be found to achieve both goals
2661 // Store the trimmed polygons into a separate polygon set, so the original infill area remains intact for
2662 // "modulate by layer thickness".
2663 top_contact_layer.set_polygons_to_extrude(diff(top_contact_layer.layer->polygons, offset(loop_lines, float(circle_radius * 1.1))));
2664
2665 // Transform loops into ExtrusionPath objects.
2666 extrusion_entities_append_paths(
2667 top_contact_layer.extrusions,
2668 std::move(loop_lines),
2669 erSupportMaterialInterface, flow.mm3_per_mm(), flow.width, flow.height);
2670 }
2671
2672 #ifdef SLIC3R_DEBUG
dbg_index_to_color(int idx)2673 static std::string dbg_index_to_color(int idx)
2674 {
2675 if (idx < 0)
2676 return "yellow";
2677 idx = idx % 3;
2678 switch (idx) {
2679 case 0: return "red";
2680 case 1: return "green";
2681 default: return "blue";
2682 }
2683 }
2684 #endif /* SLIC3R_DEBUG */
2685
2686 // When extruding a bottom interface layer over an object, the bottom interface layer is extruded in a thin air, therefore
2687 // it is being extruded with a bridging flow to not shrink excessively (the die swell effect).
2688 // Tiny extrusions are better avoided and it is always better to anchor the thread to an existing support structure if possible.
2689 // Therefore the bottom interface spots are expanded a bit. The expanded regions may overlap with another bottom interface layers,
2690 // leading to over extrusion, where they overlap. The over extrusion is better avoided as it often makes the interface layers
2691 // to stick too firmly to the object.
modulate_extrusion_by_overlapping_layers(ExtrusionEntitiesPtr & extrusions_in_out,const PrintObjectSupportMaterial::MyLayer & this_layer,const PrintObjectSupportMaterial::MyLayersPtr & overlapping_layers)2692 void modulate_extrusion_by_overlapping_layers(
2693 // Extrusions generated for this_layer.
2694 ExtrusionEntitiesPtr &extrusions_in_out,
2695 const PrintObjectSupportMaterial::MyLayer &this_layer,
2696 // Multiple layers overlapping with this_layer, sorted bottom up.
2697 const PrintObjectSupportMaterial::MyLayersPtr &overlapping_layers)
2698 {
2699 size_t n_overlapping_layers = overlapping_layers.size();
2700 if (n_overlapping_layers == 0 || extrusions_in_out.empty())
2701 // The extrusions do not overlap with any other extrusion.
2702 return;
2703
2704 // Get the initial extrusion parameters.
2705 ExtrusionPath *extrusion_path_template = dynamic_cast<ExtrusionPath*>(extrusions_in_out.front());
2706 assert(extrusion_path_template != nullptr);
2707 ExtrusionRole extrusion_role = extrusion_path_template->role();
2708 float extrusion_width = extrusion_path_template->width;
2709
2710 struct ExtrusionPathFragment
2711 {
2712 ExtrusionPathFragment() : mm3_per_mm(-1), width(-1), height(-1) {};
2713 ExtrusionPathFragment(double mm3_per_mm, float width, float height) : mm3_per_mm(mm3_per_mm), width(width), height(height) {};
2714
2715 Polylines polylines;
2716 double mm3_per_mm;
2717 float width;
2718 float height;
2719 };
2720
2721 // Split the extrusions by the overlapping layers, reduce their extrusion rate.
2722 // The last path_fragment is from this_layer.
2723 std::vector<ExtrusionPathFragment> path_fragments(
2724 n_overlapping_layers + 1,
2725 ExtrusionPathFragment(extrusion_path_template->mm3_per_mm, extrusion_path_template->width, extrusion_path_template->height));
2726 // Don't use it, it will be released.
2727 extrusion_path_template = nullptr;
2728
2729 #ifdef SLIC3R_DEBUG
2730 static int iRun = 0;
2731 ++ iRun;
2732 BoundingBox bbox;
2733 for (size_t i_overlapping_layer = 0; i_overlapping_layer < n_overlapping_layers; ++ i_overlapping_layer) {
2734 const PrintObjectSupportMaterial::MyLayer &overlapping_layer = *overlapping_layers[i_overlapping_layer];
2735 bbox.merge(get_extents(overlapping_layer.polygons));
2736 }
2737 for (ExtrusionEntitiesPtr::const_iterator it = extrusions_in_out.begin(); it != extrusions_in_out.end(); ++ it) {
2738 ExtrusionPath *path = dynamic_cast<ExtrusionPath*>(*it);
2739 assert(path != nullptr);
2740 bbox.merge(get_extents(path->polyline));
2741 }
2742 SVG svg(debug_out_path("support-fragments-%d-%lf.svg", iRun, this_layer.print_z).c_str(), bbox);
2743 const float transparency = 0.5f;
2744 // Filled polygons for the overlapping regions.
2745 svg.draw(union_ex(this_layer.polygons), dbg_index_to_color(-1), transparency);
2746 for (size_t i_overlapping_layer = 0; i_overlapping_layer < n_overlapping_layers; ++ i_overlapping_layer) {
2747 const PrintObjectSupportMaterial::MyLayer &overlapping_layer = *overlapping_layers[i_overlapping_layer];
2748 svg.draw(union_ex(overlapping_layer.polygons), dbg_index_to_color(int(i_overlapping_layer)), transparency);
2749 }
2750 // Contours of the overlapping regions.
2751 svg.draw(to_polylines(this_layer.polygons), dbg_index_to_color(-1), scale_(0.2));
2752 for (size_t i_overlapping_layer = 0; i_overlapping_layer < n_overlapping_layers; ++ i_overlapping_layer) {
2753 const PrintObjectSupportMaterial::MyLayer &overlapping_layer = *overlapping_layers[i_overlapping_layer];
2754 svg.draw(to_polylines(overlapping_layer.polygons), dbg_index_to_color(int(i_overlapping_layer)), scale_(0.1));
2755 }
2756 // Fill extrusion, the source.
2757 for (ExtrusionEntitiesPtr::const_iterator it = extrusions_in_out.begin(); it != extrusions_in_out.end(); ++ it) {
2758 ExtrusionPath *path = dynamic_cast<ExtrusionPath*>(*it);
2759 std::string color_name;
2760 switch ((it - extrusions_in_out.begin()) % 9) {
2761 case 0: color_name = "magenta"; break;
2762 case 1: color_name = "deepskyblue"; break;
2763 case 2: color_name = "coral"; break;
2764 case 3: color_name = "goldenrod"; break;
2765 case 4: color_name = "orange"; break;
2766 case 5: color_name = "olivedrab"; break;
2767 case 6: color_name = "blueviolet"; break;
2768 case 7: color_name = "brown"; break;
2769 default: color_name = "orchid"; break;
2770 }
2771 svg.draw(path->polyline, color_name, scale_(0.2));
2772 }
2773 #endif /* SLIC3R_DEBUG */
2774
2775 // End points of the original paths.
2776 std::vector<std::pair<Point, Point>> path_ends;
2777 // Collect the paths of this_layer.
2778 {
2779 Polylines &polylines = path_fragments.back().polylines;
2780 for (ExtrusionEntitiesPtr::const_iterator it = extrusions_in_out.begin(); it != extrusions_in_out.end(); ++ it) {
2781 ExtrusionPath *path = dynamic_cast<ExtrusionPath*>(*it);
2782 assert(path != nullptr);
2783 polylines.emplace_back(Polyline(std::move(path->polyline)));
2784 path_ends.emplace_back(std::pair<Point, Point>(polylines.back().points.front(), polylines.back().points.back()));
2785 }
2786 }
2787 // Destroy the original extrusion paths, their polylines were moved to path_fragments already.
2788 // This will be the destination for the new paths.
2789 extrusions_in_out.clear();
2790
2791 // Fragment the path segments by overlapping layers. The overlapping layers are sorted by an increasing print_z.
2792 // Trim by the highest overlapping layer first.
2793 for (int i_overlapping_layer = int(n_overlapping_layers) - 1; i_overlapping_layer >= 0; -- i_overlapping_layer) {
2794 const PrintObjectSupportMaterial::MyLayer &overlapping_layer = *overlapping_layers[i_overlapping_layer];
2795 ExtrusionPathFragment &frag = path_fragments[i_overlapping_layer];
2796 Polygons polygons_trimming = offset(union_ex(overlapping_layer.polygons), float(scale_(0.5*extrusion_width)));
2797 frag.polylines = intersection_pl(path_fragments.back().polylines, polygons_trimming, false);
2798 path_fragments.back().polylines = diff_pl(path_fragments.back().polylines, polygons_trimming, false);
2799 // Adjust the extrusion parameters for a reduced layer height and a non-bridging flow (nozzle_dmr = -1, does not matter).
2800 assert(this_layer.print_z > overlapping_layer.print_z);
2801 frag.height = float(this_layer.print_z - overlapping_layer.print_z);
2802 frag.mm3_per_mm = Flow(frag.width, frag.height, -1.f, false).mm3_per_mm();
2803 #ifdef SLIC3R_DEBUG
2804 svg.draw(frag.polylines, dbg_index_to_color(i_overlapping_layer), scale_(0.1));
2805 #endif /* SLIC3R_DEBUG */
2806 }
2807
2808 #ifdef SLIC3R_DEBUG
2809 svg.draw(path_fragments.back().polylines, dbg_index_to_color(-1), scale_(0.1));
2810 svg.Close();
2811 #endif /* SLIC3R_DEBUG */
2812
2813 // Now chain the split segments using hashing and a nearly exact match, maintaining the order of segments.
2814 // Create a single ExtrusionPath or ExtrusionEntityCollection per source ExtrusionPath.
2815 // Map of fragment start/end points to a pair of <i_overlapping_layer, i_polyline_in_layer>
2816 // Because a non-exact matching is used for the end points, a multi-map is used.
2817 // As the clipper library may reverse the order of some clipped paths, store both ends into the map.
2818 struct ExtrusionPathFragmentEnd
2819 {
2820 ExtrusionPathFragmentEnd(size_t alayer_idx, size_t apolyline_idx, bool ais_start) :
2821 layer_idx(alayer_idx), polyline_idx(apolyline_idx), is_start(ais_start) {}
2822 size_t layer_idx;
2823 size_t polyline_idx;
2824 bool is_start;
2825 };
2826 class ExtrusionPathFragmentEndPointAccessor {
2827 public:
2828 ExtrusionPathFragmentEndPointAccessor(const std::vector<ExtrusionPathFragment> &path_fragments) : m_path_fragments(path_fragments) {}
2829 // Return an end point of a fragment, or nullptr if the fragment has been consumed already.
2830 const Point* operator()(const ExtrusionPathFragmentEnd &fragment_end) const {
2831 const Polyline &polyline = m_path_fragments[fragment_end.layer_idx].polylines[fragment_end.polyline_idx];
2832 return polyline.points.empty() ? nullptr :
2833 (fragment_end.is_start ? &polyline.points.front() : &polyline.points.back());
2834 }
2835 private:
2836 ExtrusionPathFragmentEndPointAccessor& operator=(const ExtrusionPathFragmentEndPointAccessor&) {
2837 return *this;
2838 }
2839
2840 const std::vector<ExtrusionPathFragment> &m_path_fragments;
2841 };
2842 const coord_t search_radius = 7;
2843 ClosestPointInRadiusLookup<ExtrusionPathFragmentEnd, ExtrusionPathFragmentEndPointAccessor> map_fragment_starts(
2844 search_radius, ExtrusionPathFragmentEndPointAccessor(path_fragments));
2845 for (size_t i_overlapping_layer = 0; i_overlapping_layer <= n_overlapping_layers; ++ i_overlapping_layer) {
2846 const Polylines &polylines = path_fragments[i_overlapping_layer].polylines;
2847 for (size_t i_polyline = 0; i_polyline < polylines.size(); ++ i_polyline) {
2848 // Map a starting point of a polyline to a pair of <layer, polyline>
2849 if (polylines[i_polyline].points.size() >= 2) {
2850 map_fragment_starts.insert(ExtrusionPathFragmentEnd(i_overlapping_layer, i_polyline, true));
2851 map_fragment_starts.insert(ExtrusionPathFragmentEnd(i_overlapping_layer, i_polyline, false));
2852 }
2853 }
2854 }
2855
2856 // For each source path:
2857 for (size_t i_path = 0; i_path < path_ends.size(); ++ i_path) {
2858 const Point &pt_start = path_ends[i_path].first;
2859 const Point &pt_end = path_ends[i_path].second;
2860 Point pt_current = pt_start;
2861 // Find a chain of fragments with the original / reduced print height.
2862 ExtrusionMultiPath multipath;
2863 for (;;) {
2864 // Find a closest end point to pt_current.
2865 std::pair<const ExtrusionPathFragmentEnd*, coordf_t> end_and_dist2 = map_fragment_starts.find(pt_current);
2866 // There may be a bug in Clipper flipping the order of two last points in a fragment?
2867 // assert(end_and_dist2.first != nullptr);
2868 assert(end_and_dist2.first == nullptr || end_and_dist2.second < search_radius * search_radius);
2869 if (end_and_dist2.first == nullptr) {
2870 // New fragment connecting to pt_current was not found.
2871 // Verify that the last point found is close to the original end point of the unfragmented path.
2872 //const double d2 = (pt_end - pt_current).cast<double>.squaredNorm();
2873 //assert(d2 < coordf_t(search_radius * search_radius));
2874 // End of the path.
2875 break;
2876 }
2877 const ExtrusionPathFragmentEnd &fragment_end_min = *end_and_dist2.first;
2878 // Fragment to consume.
2879 ExtrusionPathFragment &frag = path_fragments[fragment_end_min.layer_idx];
2880 Polyline &frag_polyline = frag.polylines[fragment_end_min.polyline_idx];
2881 // Path to append the fragment to.
2882 ExtrusionPath *path = multipath.paths.empty() ? nullptr : &multipath.paths.back();
2883 if (path != nullptr) {
2884 // Verify whether the path is compatible with the current fragment.
2885 assert(this_layer.layer_type == PrintObjectSupportMaterial::sltBottomContact || path->height != frag.height || path->mm3_per_mm != frag.mm3_per_mm);
2886 if (path->height != frag.height || path->mm3_per_mm != frag.mm3_per_mm) {
2887 path = nullptr;
2888 }
2889 // Merging with the previous path. This can only happen if the current layer was reduced by a base layer, which was split into a base and interface layer.
2890 }
2891 if (path == nullptr) {
2892 // Allocate a new path.
2893 multipath.paths.push_back(ExtrusionPath(extrusion_role, frag.mm3_per_mm, frag.width, frag.height));
2894 path = &multipath.paths.back();
2895 }
2896 // The Clipper library may flip the order of the clipped polylines arbitrarily.
2897 // Reverse the source polyline, if connecting to the end.
2898 if (! fragment_end_min.is_start)
2899 frag_polyline.reverse();
2900 // Enforce exact overlap of the end points of successive fragments.
2901 assert(frag_polyline.points.front() == pt_current);
2902 frag_polyline.points.front() = pt_current;
2903 // Don't repeat the first point.
2904 if (! path->polyline.points.empty())
2905 path->polyline.points.pop_back();
2906 // Consume the fragment's polyline, remove it from the input fragments, so it will be ignored the next time.
2907 path->polyline.append(std::move(frag_polyline));
2908 frag_polyline.points.clear();
2909 pt_current = path->polyline.points.back();
2910 if (pt_current == pt_end) {
2911 // End of the path.
2912 break;
2913 }
2914 }
2915 if (!multipath.paths.empty()) {
2916 if (multipath.paths.size() == 1) {
2917 // This path was not fragmented.
2918 extrusions_in_out.push_back(new ExtrusionPath(std::move(multipath.paths.front())));
2919 } else {
2920 // This path was fragmented. Copy the collection as a whole object, so the order inside the collection will not be changed
2921 // during the chaining of extrusions_in_out.
2922 extrusions_in_out.push_back(new ExtrusionMultiPath(std::move(multipath)));
2923 }
2924 }
2925 }
2926 // If there are any non-consumed fragments, add them separately.
2927 //FIXME this shall not happen, if the Clipper works as expected and all paths split to fragments could be re-connected.
2928 for (auto it_fragment = path_fragments.begin(); it_fragment != path_fragments.end(); ++ it_fragment)
2929 extrusion_entities_append_paths(extrusions_in_out, std::move(it_fragment->polylines), extrusion_role, it_fragment->mm3_per_mm, it_fragment->width, it_fragment->height);
2930 }
2931
generate_toolpaths(const PrintObject & object,const MyLayersPtr & raft_layers,const MyLayersPtr & bottom_contacts,const MyLayersPtr & top_contacts,const MyLayersPtr & intermediate_layers,const MyLayersPtr & interface_layers) const2932 void PrintObjectSupportMaterial::generate_toolpaths(
2933 const PrintObject &object,
2934 const MyLayersPtr &raft_layers,
2935 const MyLayersPtr &bottom_contacts,
2936 const MyLayersPtr &top_contacts,
2937 const MyLayersPtr &intermediate_layers,
2938 const MyLayersPtr &interface_layers) const
2939 {
2940 // Slic3r::debugf "Generating patterns\n";
2941 // loop_interface_processor with a given circle radius.
2942 LoopInterfaceProcessor loop_interface_processor(1.5 * m_support_material_interface_flow.scaled_width());
2943 loop_interface_processor.n_contact_loops = this->has_contact_loops() ? 1 : 0;
2944
2945 float base_angle = Geometry::deg2rad(float(m_object_config->support_material_angle.value));
2946 float interface_angle = Geometry::deg2rad(float(m_object_config->support_material_angle.value + 90.));
2947 coordf_t interface_spacing = m_object_config->support_material_interface_spacing.value + m_support_material_interface_flow.spacing();
2948 coordf_t interface_density = std::min(1., m_support_material_interface_flow.spacing() / interface_spacing);
2949 coordf_t support_spacing = m_object_config->support_material_spacing.value + m_support_material_flow.spacing();
2950 coordf_t support_density = std::min(1., m_support_material_flow.spacing() / support_spacing);
2951 if (m_object_config->support_material_interface_layers.value == 0) {
2952 // No interface layers allowed, print everything with the base support pattern.
2953 interface_spacing = support_spacing;
2954 interface_density = support_density;
2955 }
2956
2957 // Prepare fillers.
2958 SupportMaterialPattern support_pattern = m_object_config->support_material_pattern;
2959 bool with_sheath = m_object_config->support_material_with_sheath;
2960 InfillPattern infill_pattern = (support_pattern == smpHoneycomb ? ipHoneycomb : ipRectilinear);
2961 std::vector<float> angles;
2962 angles.push_back(base_angle);
2963
2964 if (support_pattern == smpRectilinearGrid)
2965 angles.push_back(interface_angle);
2966
2967 BoundingBox bbox_object(Point(-scale_(1.), -scale_(1.0)), Point(scale_(1.), scale_(1.)));
2968
2969 // const coordf_t link_max_length_factor = 3.;
2970 const coordf_t link_max_length_factor = 0.;
2971
2972 float raft_angle_1st_layer = 0.f;
2973 float raft_angle_base = 0.f;
2974 float raft_angle_interface = 0.f;
2975 if (m_slicing_params.base_raft_layers > 1) {
2976 // There are all raft layer types (1st layer, base, interface & contact layers) available.
2977 raft_angle_1st_layer = interface_angle;
2978 raft_angle_base = base_angle;
2979 raft_angle_interface = interface_angle;
2980 } else if (m_slicing_params.base_raft_layers == 1 || m_slicing_params.interface_raft_layers > 1) {
2981 // 1st layer, interface & contact layers available.
2982 raft_angle_1st_layer = base_angle;
2983 if (this->has_support())
2984 // Print 1st layer at 45 degrees from both the interface and base angles as both can land on the 1st layer.
2985 raft_angle_1st_layer += 0.7854f;
2986 raft_angle_interface = interface_angle;
2987 } else if (m_slicing_params.interface_raft_layers == 1) {
2988 // Only the contact raft layer is non-empty, which will be printed as the 1st layer.
2989 assert(m_slicing_params.base_raft_layers == 0);
2990 assert(m_slicing_params.interface_raft_layers == 1);
2991 assert(m_slicing_params.raft_layers() == 1 && raft_layers.size() == 0);
2992 } else {
2993 // No raft.
2994 assert(m_slicing_params.base_raft_layers == 0);
2995 assert(m_slicing_params.interface_raft_layers == 0);
2996 assert(m_slicing_params.raft_layers() == 0 && raft_layers.size() == 0);
2997 }
2998
2999 // Insert the raft base layers.
3000 size_t n_raft_layers = size_t(std::max(0, int(m_slicing_params.raft_layers()) - 1));
3001 tbb::parallel_for(tbb::blocked_range<size_t>(0, n_raft_layers),
3002 [this, &object, &raft_layers,
3003 infill_pattern, &bbox_object, support_density, interface_density, raft_angle_1st_layer, raft_angle_base, raft_angle_interface, link_max_length_factor, with_sheath]
3004 (const tbb::blocked_range<size_t>& range) {
3005 for (size_t support_layer_id = range.begin(); support_layer_id < range.end(); ++ support_layer_id)
3006 {
3007 assert(support_layer_id < raft_layers.size());
3008 SupportLayer &support_layer = *object.support_layers()[support_layer_id];
3009 assert(support_layer.support_fills.entities.empty());
3010 MyLayer &raft_layer = *raft_layers[support_layer_id];
3011
3012 std::unique_ptr<Fill> filler_interface = std::unique_ptr<Fill>(Fill::new_from_type(ipRectilinear));
3013 std::unique_ptr<Fill> filler_support = std::unique_ptr<Fill>(Fill::new_from_type(infill_pattern));
3014 filler_interface->set_bounding_box(bbox_object);
3015 filler_support->set_bounding_box(bbox_object);
3016
3017 // Print the support base below the support columns, or the support base for the support columns plus the contacts.
3018 if (support_layer_id > 0) {
3019 Polygons to_infill_polygons = (support_layer_id < m_slicing_params.base_raft_layers) ?
3020 raft_layer.polygons :
3021 //FIXME misusing contact_polygons for support columns.
3022 ((raft_layer.contact_polygons == nullptr) ? Polygons() : *raft_layer.contact_polygons);
3023 if (! to_infill_polygons.empty()) {
3024 Flow flow(float(m_support_material_flow.width), float(raft_layer.height), m_support_material_flow.nozzle_diameter, raft_layer.bridging);
3025 // find centerline of the external loop/extrusions
3026 ExPolygons to_infill = (support_layer_id == 0 || ! with_sheath) ?
3027 // union_ex(base_polygons, true) :
3028 offset2_ex(to_infill_polygons, float(SCALED_EPSILON), float(- SCALED_EPSILON)) :
3029 offset2_ex(to_infill_polygons, float(SCALED_EPSILON), float(- SCALED_EPSILON - 0.5*flow.scaled_width()));
3030 if (! to_infill.empty() && with_sheath) {
3031 // Draw a perimeter all around the support infill. This makes the support stable, but difficult to remove.
3032 // TODO: use brim ordering algorithm
3033 to_infill_polygons = to_polygons(to_infill);
3034 // TODO: use offset2_ex()
3035 to_infill = offset_ex(to_infill, float(- 0.4 * flow.scaled_spacing()));
3036 extrusion_entities_append_paths(
3037 support_layer.support_fills.entities,
3038 to_polylines(std::move(to_infill_polygons)),
3039 erSupportMaterial, flow.mm3_per_mm(), flow.width, flow.height);
3040 }
3041 if (! to_infill.empty()) {
3042 // We don't use $base_flow->spacing because we need a constant spacing
3043 // value that guarantees that all layers are correctly aligned.
3044 Fill *filler = filler_support.get();
3045 filler->angle = raft_angle_base;
3046 filler->spacing = m_support_material_flow.spacing();
3047 filler->link_max_length = coord_t(scale_(filler->spacing * link_max_length_factor / support_density));
3048 fill_expolygons_generate_paths(
3049 // Destination
3050 support_layer.support_fills.entities,
3051 // Regions to fill
3052 std::move(to_infill),
3053 // Filler and its parameters
3054 filler, float(support_density),
3055 // Extrusion parameters
3056 erSupportMaterial, flow);
3057 }
3058 }
3059 }
3060
3061 Fill *filler = filler_interface.get();
3062 Flow flow = m_first_layer_flow;
3063 float density = 0.f;
3064 if (support_layer_id == 0) {
3065 // Base flange.
3066 filler->angle = raft_angle_1st_layer;
3067 filler->spacing = m_first_layer_flow.spacing();
3068 // 70% of density on the 1st layer.
3069 density = 0.7f;
3070 } else if (support_layer_id >= m_slicing_params.base_raft_layers) {
3071 filler->angle = raft_angle_interface;
3072 // We don't use $base_flow->spacing because we need a constant spacing
3073 // value that guarantees that all layers are correctly aligned.
3074 filler->spacing = m_support_material_flow.spacing();
3075 flow = Flow(float(m_support_material_interface_flow.width), float(raft_layer.height), m_support_material_flow.nozzle_diameter, raft_layer.bridging);
3076 density = float(interface_density);
3077 } else
3078 continue;
3079 filler->link_max_length = coord_t(scale_(filler->spacing * link_max_length_factor / density));
3080 fill_expolygons_generate_paths(
3081 // Destination
3082 support_layer.support_fills.entities,
3083 // Regions to fill
3084 offset2_ex(raft_layer.polygons, float(SCALED_EPSILON), float(- SCALED_EPSILON)),
3085 // Filler and its parameters
3086 filler, density,
3087 // Extrusion parameters
3088 (support_layer_id < m_slicing_params.base_raft_layers) ? erSupportMaterial : erSupportMaterialInterface, flow);
3089 }
3090 });
3091
3092 struct LayerCacheItem {
3093 LayerCacheItem(MyLayerExtruded *layer_extruded = nullptr) : layer_extruded(layer_extruded) {}
3094 MyLayerExtruded *layer_extruded;
3095 std::vector<MyLayer*> overlapping;
3096 };
3097 struct LayerCache {
3098 MyLayerExtruded bottom_contact_layer;
3099 MyLayerExtruded top_contact_layer;
3100 MyLayerExtruded base_layer;
3101 MyLayerExtruded interface_layer;
3102 std::vector<LayerCacheItem> overlaps;
3103 };
3104 std::vector<LayerCache> layer_caches(object.support_layers().size(), LayerCache());
3105
3106 tbb::parallel_for(tbb::blocked_range<size_t>(n_raft_layers, object.support_layers().size()),
3107 [this, &object, &bottom_contacts, &top_contacts, &intermediate_layers, &interface_layers, &layer_caches, &loop_interface_processor,
3108 infill_pattern, &bbox_object, support_density, interface_density, interface_angle, &angles, link_max_length_factor, with_sheath]
3109 (const tbb::blocked_range<size_t>& range) {
3110 // Indices of the 1st layer in their respective container at the support layer height.
3111 size_t idx_layer_bottom_contact = size_t(-1);
3112 size_t idx_layer_top_contact = size_t(-1);
3113 size_t idx_layer_intermediate = size_t(-1);
3114 size_t idx_layer_inteface = size_t(-1);
3115 std::unique_ptr<Fill> filler_interface = std::unique_ptr<Fill>(Fill::new_from_type(m_slicing_params.soluble_interface ? ipConcentric : ipRectilinear));
3116 std::unique_ptr<Fill> filler_support = std::unique_ptr<Fill>(Fill::new_from_type(infill_pattern));
3117 filler_interface->set_bounding_box(bbox_object);
3118 filler_support->set_bounding_box(bbox_object);
3119 for (size_t support_layer_id = range.begin(); support_layer_id < range.end(); ++ support_layer_id)
3120 {
3121 SupportLayer &support_layer = *object.support_layers()[support_layer_id];
3122 LayerCache &layer_cache = layer_caches[support_layer_id];
3123
3124 // Find polygons with the same print_z.
3125 MyLayerExtruded &bottom_contact_layer = layer_cache.bottom_contact_layer;
3126 MyLayerExtruded &top_contact_layer = layer_cache.top_contact_layer;
3127 MyLayerExtruded &base_layer = layer_cache.base_layer;
3128 MyLayerExtruded &interface_layer = layer_cache.interface_layer;
3129 // Increment the layer indices to find a layer at support_layer.print_z.
3130 {
3131 auto fun = [&support_layer](const MyLayer *l){ return l->print_z >= support_layer.print_z - EPSILON; };
3132 idx_layer_bottom_contact = idx_higher_or_equal(bottom_contacts, idx_layer_bottom_contact, fun);
3133 idx_layer_top_contact = idx_higher_or_equal(top_contacts, idx_layer_top_contact, fun);
3134 idx_layer_intermediate = idx_higher_or_equal(intermediate_layers, idx_layer_intermediate, fun);
3135 idx_layer_inteface = idx_higher_or_equal(interface_layers, idx_layer_inteface, fun);
3136 }
3137 // Copy polygons from the layers.
3138 if (idx_layer_bottom_contact < bottom_contacts.size() && bottom_contacts[idx_layer_bottom_contact]->print_z < support_layer.print_z + EPSILON)
3139 bottom_contact_layer.layer = bottom_contacts[idx_layer_bottom_contact];
3140 if (idx_layer_top_contact < top_contacts.size() && top_contacts[idx_layer_top_contact]->print_z < support_layer.print_z + EPSILON)
3141 top_contact_layer.layer = top_contacts[idx_layer_top_contact];
3142 if (idx_layer_inteface < interface_layers.size() && interface_layers[idx_layer_inteface]->print_z < support_layer.print_z + EPSILON)
3143 interface_layer.layer = interface_layers[idx_layer_inteface];
3144 if (idx_layer_intermediate < intermediate_layers.size() && intermediate_layers[idx_layer_intermediate]->print_z < support_layer.print_z + EPSILON)
3145 base_layer.layer = intermediate_layers[idx_layer_intermediate];
3146
3147 if (m_object_config->support_material_interface_layers == 0) {
3148 // If no interface layers were requested, we treat the contact layer exactly as a generic base layer.
3149 if (m_can_merge_support_regions) {
3150 if (base_layer.could_merge(top_contact_layer))
3151 base_layer.merge(std::move(top_contact_layer));
3152 else if (base_layer.empty() && !top_contact_layer.empty() && !top_contact_layer.layer->bridging)
3153 std::swap(base_layer, top_contact_layer);
3154 if (base_layer.could_merge(bottom_contact_layer))
3155 base_layer.merge(std::move(bottom_contact_layer));
3156 else if (base_layer.empty() && !bottom_contact_layer.empty() && !bottom_contact_layer.layer->bridging)
3157 std::swap(base_layer, bottom_contact_layer);
3158 }
3159 } else {
3160 loop_interface_processor.generate(top_contact_layer, m_support_material_interface_flow);
3161 // If no loops are allowed, we treat the contact layer exactly as a generic interface layer.
3162 // Merge interface_layer into top_contact_layer, as the top_contact_layer is not synchronized and therefore it will be used
3163 // to trim other layers.
3164 if (top_contact_layer.could_merge(interface_layer))
3165 top_contact_layer.merge(std::move(interface_layer));
3166 }
3167
3168 if (! interface_layer.empty() && ! base_layer.empty()) {
3169 // turn base support into interface when it's contained in our holes
3170 // (this way we get wider interface anchoring)
3171 //FIXME one wants to fill in the inner most holes of the interfaces, not all the holes.
3172 Polygons islands = top_level_islands(interface_layer.layer->polygons);
3173 polygons_append(interface_layer.layer->polygons, intersection(base_layer.layer->polygons, islands));
3174 base_layer.layer->polygons = diff(base_layer.layer->polygons, islands);
3175 }
3176
3177 // Top and bottom contacts, interface layers.
3178 for (size_t i = 0; i < 3; ++ i) {
3179 MyLayerExtruded &layer_ex = (i == 0) ? top_contact_layer : (i == 1 ? bottom_contact_layer : interface_layer);
3180 if (layer_ex.empty() || layer_ex.polygons_to_extrude().empty())
3181 continue;
3182 //FIXME When paralellizing, each thread shall have its own copy of the fillers.
3183 bool interface_as_base = (&layer_ex == &interface_layer) && m_object_config->support_material_interface_layers.value == 0;
3184 //FIXME Bottom interfaces are extruded with the briding flow. Some bridging layers have its height slightly reduced, therefore
3185 // the bridging flow does not quite apply. Reduce the flow to area of an ellipse? (A = pi * a * b)
3186 Flow interface_flow(
3187 float(layer_ex.layer->bridging ? layer_ex.layer->height : (interface_as_base ? m_support_material_flow.width : m_support_material_interface_flow.width)),
3188 float(layer_ex.layer->height),
3189 m_support_material_interface_flow.nozzle_diameter,
3190 layer_ex.layer->bridging);
3191 filler_interface->angle = interface_as_base ?
3192 // If zero interface layers are configured, use the same angle as for the base layers.
3193 angles[support_layer_id % angles.size()] :
3194 // Use interface angle for the interface layers.
3195 interface_angle;
3196 filler_interface->spacing = m_support_material_interface_flow.spacing();
3197 filler_interface->link_max_length = coord_t(scale_(filler_interface->spacing * link_max_length_factor / interface_density));
3198 fill_expolygons_generate_paths(
3199 // Destination
3200 layer_ex.extrusions,
3201 // Regions to fill
3202 union_ex(layer_ex.polygons_to_extrude(), true),
3203 // Filler and its parameters
3204 filler_interface.get(), float(interface_density),
3205 // Extrusion parameters
3206 erSupportMaterialInterface, interface_flow);
3207 }
3208
3209 // Base support or flange.
3210 if (! base_layer.empty() && ! base_layer.polygons_to_extrude().empty()) {
3211 //FIXME When paralellizing, each thread shall have its own copy of the fillers.
3212 Fill *filler = filler_support.get();
3213 filler->angle = angles[support_layer_id % angles.size()];
3214 // We don't use $base_flow->spacing because we need a constant spacing
3215 // value that guarantees that all layers are correctly aligned.
3216 Flow flow(
3217 float(base_layer.layer->bridging ? base_layer.layer->height : m_support_material_flow.width),
3218 float(base_layer.layer->height),
3219 m_support_material_flow.nozzle_diameter,
3220 base_layer.layer->bridging);
3221 filler->spacing = m_support_material_flow.spacing();
3222 filler->link_max_length = coord_t(scale_(filler->spacing * link_max_length_factor / support_density));
3223 float density = float(support_density);
3224 // find centerline of the external loop/extrusions
3225 ExPolygons to_infill = (support_layer_id == 0 || ! with_sheath) ?
3226 // union_ex(base_polygons, true) :
3227 offset2_ex(base_layer.polygons_to_extrude(), float(SCALED_EPSILON), float(- SCALED_EPSILON)) :
3228 offset2_ex(base_layer.polygons_to_extrude(), float(SCALED_EPSILON), float(- SCALED_EPSILON - 0.5*flow.scaled_width()));
3229 if (base_layer.layer->bottom_z < EPSILON) {
3230 // Base flange (the 1st layer).
3231 filler = filler_interface.get();
3232 filler->angle = Geometry::deg2rad(float(m_object_config->support_material_angle.value + 90.));
3233 density = 0.5f;
3234 flow = m_first_layer_flow;
3235 // use the proper spacing for first layer as we don't need to align
3236 // its pattern to the other layers
3237 //FIXME When paralellizing, each thread shall have its own copy of the fillers.
3238 filler->spacing = flow.spacing();
3239 filler->link_max_length = coord_t(scale_(filler->spacing * link_max_length_factor / density));
3240 } else if (with_sheath) {
3241 // Draw a perimeter all around the support infill. This makes the support stable, but difficult to remove.
3242 // TODO: use brim ordering algorithm
3243 Polygons to_infill_polygons = to_polygons(to_infill);
3244 // TODO: use offset2_ex()
3245 to_infill = offset_ex(to_infill, - 0.4f * float(flow.scaled_spacing()));
3246 extrusion_entities_append_paths(
3247 base_layer.extrusions,
3248 to_polylines(std::move(to_infill_polygons)),
3249 erSupportMaterial, flow.mm3_per_mm(), flow.width, flow.height);
3250 }
3251 fill_expolygons_generate_paths(
3252 // Destination
3253 base_layer.extrusions,
3254 // Regions to fill
3255 std::move(to_infill),
3256 // Filler and its parameters
3257 filler, density,
3258 // Extrusion parameters
3259 erSupportMaterial, flow);
3260 }
3261
3262 layer_cache.overlaps.reserve(4);
3263 if (! bottom_contact_layer.empty())
3264 layer_cache.overlaps.push_back(&bottom_contact_layer);
3265 if (! top_contact_layer.empty())
3266 layer_cache.overlaps.push_back(&top_contact_layer);
3267 if (! interface_layer.empty())
3268 layer_cache.overlaps.push_back(&interface_layer);
3269 if (! base_layer.empty())
3270 layer_cache.overlaps.push_back(&base_layer);
3271 // Sort the layers with the same print_z coordinate by their heights, thickest first.
3272 std::sort(layer_cache.overlaps.begin(), layer_cache.overlaps.end(), [](const LayerCacheItem &lc1, const LayerCacheItem &lc2) { return lc1.layer_extruded->layer->height > lc2.layer_extruded->layer->height; });
3273 // Collect the support areas with this print_z into islands, as there is no need
3274 // for retraction over these islands.
3275 Polygons polys;
3276 // Collect the extrusions, sorted by the bottom extrusion height.
3277 for (LayerCacheItem &layer_cache_item : layer_cache.overlaps) {
3278 // Collect islands to polys.
3279 layer_cache_item.layer_extruded->polygons_append(polys);
3280 // The print_z of the top contact surfaces and bottom_z of the bottom contact surfaces are "free"
3281 // in a sense that they are not synchronized with other support layers. As the top and bottom contact surfaces
3282 // are inflated to achieve a better anchoring, it may happen, that these surfaces will at least partially
3283 // overlap in Z with another support layers, leading to over-extrusion.
3284 // Mitigate the over-extrusion by modulating the extrusion rate over these regions.
3285 // The print head will follow the same print_z, but the layer thickness will be reduced
3286 // where it overlaps with another support layer.
3287 //FIXME When printing a briging path, what is an equivalent height of the squished extrudate of the same width?
3288 // Collect overlapping top/bottom surfaces.
3289 layer_cache_item.overlapping.reserve(16);
3290 coordf_t bottom_z = layer_cache_item.layer_extruded->layer->bottom_print_z() + EPSILON;
3291 for (int i = int(idx_layer_bottom_contact) - 1; i >= 0 && bottom_contacts[i]->print_z > bottom_z; -- i)
3292 layer_cache_item.overlapping.push_back(bottom_contacts[i]);
3293 for (int i = int(idx_layer_top_contact) - 1; i >= 0 && top_contacts[i]->print_z > bottom_z; -- i)
3294 layer_cache_item.overlapping.push_back(top_contacts[i]);
3295 if (layer_cache_item.layer_extruded->layer->layer_type == sltBottomContact) {
3296 // Bottom contact layer may overlap with a base layer, which may be changed to interface layer.
3297 for (int i = int(idx_layer_intermediate) - 1; i >= 0 && intermediate_layers[i]->print_z > bottom_z; -- i)
3298 layer_cache_item.overlapping.push_back(intermediate_layers[i]);
3299 for (int i = int(idx_layer_inteface) - 1; i >= 0 && interface_layers[i]->print_z > bottom_z; -- i)
3300 layer_cache_item.overlapping.push_back(interface_layers[i]);
3301 }
3302 std::sort(layer_cache_item.overlapping.begin(), layer_cache_item.overlapping.end(), MyLayersPtrCompare());
3303 }
3304 if (! polys.empty())
3305 expolygons_append(support_layer.support_islands.expolygons, union_ex(polys));
3306 /* {
3307 require "Slic3r/SVG.pm";
3308 Slic3r::SVG::output("islands_" . $z . ".svg",
3309 red_expolygons => union_ex($contact),
3310 green_expolygons => union_ex($interface),
3311 green_polylines => [ map $_->unpack->polyline, @{$layer->support_contact_fills} ],
3312 polylines => [ map $_->unpack->polyline, @{$layer->support_fills} ],
3313 );
3314 } */
3315 } // for each support_layer_id
3316 });
3317
3318 // Now modulate the support layer height in parallel.
3319 tbb::parallel_for(tbb::blocked_range<size_t>(n_raft_layers, object.support_layers().size()),
3320 [this, &object, &layer_caches]
3321 (const tbb::blocked_range<size_t>& range) {
3322 for (size_t support_layer_id = range.begin(); support_layer_id < range.end(); ++ support_layer_id) {
3323 SupportLayer &support_layer = *object.support_layers()[support_layer_id];
3324 LayerCache &layer_cache = layer_caches[support_layer_id];
3325 for (LayerCacheItem &layer_cache_item : layer_cache.overlaps) {
3326 modulate_extrusion_by_overlapping_layers(layer_cache_item.layer_extruded->extrusions, *layer_cache_item.layer_extruded->layer, layer_cache_item.overlapping);
3327 support_layer.support_fills.append(std::move(layer_cache_item.layer_extruded->extrusions));
3328 }
3329 }
3330 });
3331 }
3332
3333 /*
3334 void PrintObjectSupportMaterial::clip_by_pillars(
3335 const PrintObject &object,
3336 LayersPtr &bottom_contacts,
3337 LayersPtr &top_contacts,
3338 LayersPtr &intermediate_contacts);
3339
3340 {
3341 // this prevents supplying an empty point set to BoundingBox constructor
3342 if (top_contacts.empty())
3343 return;
3344
3345 coord_t pillar_size = scale_(PILLAR_SIZE);
3346 coord_t pillar_spacing = scale_(PILLAR_SPACING);
3347
3348 // A regular grid of pillars, filling the 2D bounding box.
3349 Polygons grid;
3350 {
3351 // Rectangle with a side of 2.5x2.5mm.
3352 Polygon pillar;
3353 pillar.points.push_back(Point(0, 0));
3354 pillar.points.push_back(Point(pillar_size, 0));
3355 pillar.points.push_back(Point(pillar_size, pillar_size));
3356 pillar.points.push_back(Point(0, pillar_size));
3357
3358 // 2D bounding box of the projection of all contact polygons.
3359 BoundingBox bbox;
3360 for (LayersPtr::const_iterator it = top_contacts.begin(); it != top_contacts.end(); ++ it)
3361 bbox.merge(get_extents((*it)->polygons));
3362 grid.reserve(size_t(ceil(bb.size()(0) / pillar_spacing)) * size_t(ceil(bb.size()(1) / pillar_spacing)));
3363 for (coord_t x = bb.min(0); x <= bb.max(0) - pillar_size; x += pillar_spacing) {
3364 for (coord_t y = bb.min(1); y <= bb.max(1) - pillar_size; y += pillar_spacing) {
3365 grid.push_back(pillar);
3366 for (size_t i = 0; i < pillar.points.size(); ++ i)
3367 grid.back().points[i].translate(Point(x, y));
3368 }
3369 }
3370 }
3371
3372 // add pillars to every layer
3373 for my $i (0..n_support_z) {
3374 $shape->[$i] = [ @$grid ];
3375 }
3376
3377 // build capitals
3378 for my $i (0..n_support_z) {
3379 my $z = $support_z->[$i];
3380
3381 my $capitals = intersection(
3382 $grid,
3383 $contact->{$z} // [],
3384 );
3385
3386 // work on one pillar at time (if any) to prevent the capitals from being merged
3387 // but store the contact area supported by the capital because we need to make
3388 // sure nothing is left
3389 my $contact_supported_by_capitals = [];
3390 foreach my $capital (@$capitals) {
3391 // enlarge capital tops
3392 $capital = offset([$capital], +($pillar_spacing - $pillar_size)/2);
3393 push @$contact_supported_by_capitals, @$capital;
3394
3395 for (my $j = $i-1; $j >= 0; $j--) {
3396 my $jz = $support_z->[$j];
3397 $capital = offset($capital, -$self->interface_flow->scaled_width/2);
3398 last if !@$capitals;
3399 push @{ $shape->[$j] }, @$capital;
3400 }
3401 }
3402
3403 // Capitals will not generally cover the whole contact area because there will be
3404 // remainders. For now we handle this situation by projecting such unsupported
3405 // areas to the ground, just like we would do with a normal support.
3406 my $contact_not_supported_by_capitals = diff(
3407 $contact->{$z} // [],
3408 $contact_supported_by_capitals,
3409 );
3410 if (@$contact_not_supported_by_capitals) {
3411 for (my $j = $i-1; $j >= 0; $j--) {
3412 push @{ $shape->[$j] }, @$contact_not_supported_by_capitals;
3413 }
3414 }
3415 }
3416 }
3417
3418 sub clip_with_shape {
3419 my ($self, $support, $shape) = @_;
3420
3421 foreach my $i (keys %$support) {
3422 // don't clip bottom layer with shape so that we
3423 // can generate a continuous base flange
3424 // also don't clip raft layers
3425 next if $i == 0;
3426 next if $i < $self->object_config->raft_layers;
3427 $support->{$i} = intersection(
3428 $support->{$i},
3429 $shape->[$i],
3430 );
3431 }
3432 }
3433 */
3434
3435 } // namespace Slic3r
3436