Merge pull request #1653 from Ultimaker/5.0

5.0

7 files changed, 106 insertions, 107 deletions

diff --git a/src/FffGcodeWriter.cpp b/src/FffGcodeWriter.cpp
index d620fdbd9..4b2532743 100644
--- a/src/FffGcodeWriter.cpp
+++ b/src/FffGcodeWriter.cpp
@@ -2796,7 +2796,7 @@ bool FffGcodeWriter::processSupportInfill(const SliceDataStorage& storage, Layer
                 const ZSeamConfig z_seam_config(EZSeamType::SHORTEST, gcode_layer.getLastPlannedPositionOrStartingPosition(), EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_NONE, simplify_curvature);
                 InsetOrderOptimizer wall_orderer(*this, storage, gcode_layer, infill_extruder.settings, extruder_nr,
                                                 config, config, config, config,
-                                                retract_before_outer_wall, wipe_dist, wipe_dist, extruder_nr, extruder_nr, z_seam_config, wall_toolpaths);
+                                                retract_before_outer_wall, wipe_dist, wipe_dist, extruder_nr, extruder_nr, z_seam_config, wall_toolpaths_here);
                 added_something |= wall_orderer.addToLayer();
             }
         }
diff --git a/src/InsetOrderOptimizer.cpp b/src/InsetOrderOptimizer.cpp
index f606c13bb..01479bc8a 100644
--- a/src/InsetOrderOptimizer.cpp
+++ b/src/InsetOrderOptimizer.cpp
@@ -8,6 +8,8 @@
 #include "utils/logoutput.h"
 #include "WallToolPaths.h"
 
+#include <iterator>
+
 namespace cura
 {
 
@@ -52,81 +54,54 @@ InsetOrderOptimizer::InsetOrderOptimizer(const FffGcodeWriter& gcode_writer,
 bool InsetOrderOptimizer::addToLayer()
 {
     // Settings & configs:
-    const bool pack_by_inset = ! settings.get<bool>("optimize_wall_printing_order");
-    const InsetDirection inset_direction = settings.get<InsetDirection>("inset_direction");
-    const bool alternate_walls = settings.get<bool>("material_alternate_walls");
+    const auto pack_by_inset = ! settings.get<bool>("optimize_wall_printing_order");
+    const auto inset_direction = settings.get<InsetDirection>("inset_direction");
+    const auto alternate_walls = settings.get<bool>("material_alternate_walls");
 
     const bool outer_to_inner = inset_direction == InsetDirection::OUTSIDE_IN;
-    
-    size_t start_inset;
-    size_t end_inset;
-    int direction;
-    //If the entire wall is printed with the current extruder, print all of it.
-    if (wall_0_extruder_nr == wall_x_extruder_nr && wall_x_extruder_nr == extruder_nr)
-    {
-        //If printing the outer inset first, start with the lowest inset.
-        //Otherwise start with the highest inset and iterate backwards.
-        if(inset_direction == InsetDirection::OUTSIDE_IN)
-        {
-            start_inset = 0;
-            end_inset = paths.size();
-            direction = 1;
-        }
-        else //INSIDE_OUT or CENTER_LAST.
+    const bool use_one_extruder = wall_0_extruder_nr == wall_x_extruder_nr;
+    const bool current_extruder_is_wall_x = wall_x_extruder_nr == extruder_nr;
+
+    const auto should_reverse = [&](){
+        if (use_one_extruder && current_extruder_is_wall_x)
         {
-            start_inset = paths.size() - 1;
-            end_inset = -1;
-            direction = -1;
+            // The entire wall is printed with the current extruder.
+            // Reversing the insets now depends on the inverse of the inset direction.
+            // If we want to print the outer insets first we start with the lowest and move forward
+            // otherwise we start with the highest and iterate back.
+            return ! outer_to_inner;
         }
-    }
-    //If the wall is partially printed with the current extruder, print the correct part.
-    else if (wall_0_extruder_nr != wall_x_extruder_nr)
+        // If the wall is partially printed with the current extruder we need to move forward
+        // for the outer wall extruder and iterate back for the inner wall extruder
+        return current_extruder_is_wall_x;
+    };  // Helper lambda to ensure that the reverse bool can be a const type
+    const bool reverse = should_reverse();
+
+    // Switches the begin()...end() forward iterator for a rbegin()...rend() reverse iterator
+    // I can't wait till we use the C++20 standard and have access to ranges and views
+    const auto get_walls_to_be_added = [&](const bool reverse, const std::vector<VariableWidthLines>& paths)
     {
-        //If the wall_0 and wall_x extruders are different, then only include the insets that should be printed by the
-        //current extruder_nr.
-        if(extruder_nr == wall_0_extruder_nr)
+        if (paths.empty())
         {
-            start_inset = 0;
-            end_inset = 1; // Ignore inner walls
-            direction = 1;
+            return std::vector<const ExtrusionLine*>{};
         }
-        else if(extruder_nr == wall_x_extruder_nr)
+        if (reverse)
         {
-            start_inset = paths.size() - 1;
-            end_inset = 0; // Ignore outer wall
-            direction = -1;
+            if (use_one_extruder)
+            {
+                return wallsToBeAdded(paths.rbegin(), paths.rend()); // Complete wall with one extruder
+            }
+            return wallsToBeAdded(paths.rbegin(), std::prev(paths.rend())); // Ignore inner wall
         }
-        else
+        if (use_one_extruder)
         {
-            return added_something;
+            return wallsToBeAdded(paths.begin(), paths.end()); // Complete wall with one extruder
         }
-    }
-    else //The wall is not printed with this extruder, not even in part. Don't print anything then.
-    {
-        return added_something;
-    }
+        return wallsToBeAdded(paths.begin(), std::next(paths.begin())); // Ignore outer wall
+    };
+    const auto walls_to_be_added = get_walls_to_be_added(reverse, paths);
 
-    
-    std::vector<const ExtrusionLine*> walls_to_be_added;
-    //Add all of the insets one by one.
-    for (size_t inset_idx = start_inset; inset_idx != end_inset; inset_idx += direction)
-    {
-        if (paths[inset_idx].empty())
-        {
-            continue; //Don't switch extruders either, etc.
-        }
-        const VariableWidthLines& inset = paths[inset_idx];
-        for (const ExtrusionLine& wall : inset)
-        {
-            walls_to_be_added.emplace_back(&wall);
-        }
-    }
-    
-    
-    std::unordered_set<std::pair<const ExtrusionLine*, const ExtrusionLine*>> order = 
-        pack_by_inset?
-        getInsetOrder(walls_to_be_added, outer_to_inner)
-        : getRegionOrder(walls_to_be_added, outer_to_inner);
+    const auto order = pack_by_inset ? getInsetOrder(walls_to_be_added, outer_to_inner) : getRegionOrder(walls_to_be_added, outer_to_inner);
     
     constexpr Ratio flow = 1.0_r;
     
diff --git a/src/InsetOrderOptimizer.h b/src/InsetOrderOptimizer.h
index d8aa87d48..ce2af0a03 100644
--- a/src/InsetOrderOptimizer.h
+++ b/src/InsetOrderOptimizer.h
@@ -118,6 +118,31 @@ private:
      * closing that polyline into a polygon.
      */
     constexpr static coord_t coincident_point_distance = 10;
+
+    /*!
+     * Helper function to either iterate forward or backward over the path and output a vector of ExtrusionLines
+     *
+     * @tparam It an iterator type, forward or revers
+     * @param begin either the begin() or rbegin() of the path
+     * @param end either the end() or rend() of the path
+     * @return a vector of const ExtrusionLine pointers (whom ever came up with that container???)
+     */
+    template<typename It>
+    std::vector<const ExtrusionLine*> wallsToBeAdded(It begin, It end)
+    {
+        std::vector<const ExtrusionLine*> walls_to_be_added;
+        for (It it = begin; it != end; ++it)
+        {
+            if (! it->empty())
+            {
+                for (const auto& wall : *it)
+                {
+                    walls_to_be_added.emplace_back(&wall);
+                }
+            }
+        }
+        return walls_to_be_added;
+    }
 };
 
 
diff --git a/src/TreeModelVolumes.cpp b/src/TreeModelVolumes.cpp
index 1c6889ee8..7479d5a82 100644
--- a/src/TreeModelVolumes.cpp
+++ b/src/TreeModelVolumes.cpp
@@ -104,8 +104,6 @@ const Polygons& TreeModelVolumes::calculateCollision(const RadiusLayerPair& key)
             collision_areas = collision_areas.unionPolygons(collision_model.offset(radius));
         }
     }
-
-    const std::lock_guard<std::mutex> lock(object_mutex_);
     const auto ret = collision_cache_.insert({key, std::move(collision_areas)});
     assert(ret.second);
     return ret.first->second;
@@ -137,8 +135,6 @@ const Polygons& TreeModelVolumes::calculateAvoidance(const RadiusLayerPair& key)
     }
     auto avoidance_areas = getAvoidance(radius, layer_idx - 1).offset(-max_move_).smooth(5);
     avoidance_areas = avoidance_areas.unionPolygons(getCollision(radius, layer_idx));
-
-    const std::lock_guard<std::mutex> lock(object_mutex_);
     const auto ret = avoidance_cache_.insert({key, std::move(avoidance_areas)});
     assert(ret.second);
     return ret.first->second;
@@ -148,9 +144,8 @@ const Polygons& TreeModelVolumes::calculateInternalModel(const RadiusLayerPair&
 {
     const auto& radius = key.first;
     const auto& layer_idx = key.second;
-    const auto& internal_areas = getAvoidance(radius, layer_idx).difference(getCollision(radius, layer_idx));
 
-    const std::lock_guard<std::mutex> lock(object_mutex_);
+    const auto& internal_areas = getAvoidance(radius, layer_idx).difference(getCollision(radius, layer_idx));
     const auto ret = internal_model_cache_.insert({key, internal_areas});
     assert(ret.second);
     return ret.first->second;
diff --git a/src/TreeModelVolumes.h b/src/TreeModelVolumes.h
index 29d23b0d6..74f2b4cc3 100644
--- a/src/TreeModelVolumes.h
+++ b/src/TreeModelVolumes.h
@@ -4,7 +4,6 @@
 #ifndef TREEMODELVOLUMES_H
 #define TREEMODELVOLUMES_H
 
-#include <mutex>
 #include <unordered_map>
 
 #include "settings/EnumSettings.h" //To store whether X/Y or Z distance gets priority.
@@ -21,7 +20,7 @@ class Settings;
 /*!
  * \brief Lazily generates tree guidance volumes.
  *
- * \warning This class blocks on thread access. Use calls to this in threaded blocks sparingly.
+ * \warning This class is not currently thread-safe and should not be accessed in OpenMP blocks
  */
 class TreeModelVolumes
 {
@@ -196,11 +195,6 @@ private:
     mutable std::unordered_map<RadiusLayerPair, Polygons> collision_cache_;
     mutable std::unordered_map<RadiusLayerPair, Polygons> avoidance_cache_;
     mutable std::unordered_map<RadiusLayerPair, Polygons> internal_model_cache_;
-
-    /*!
-     * \brief Used to make the class thread-safe.
-     */
-    mutable std::mutex object_mutex_;
 };
 
 }
diff --git a/src/TreeSupport.cpp b/src/TreeSupport.cpp
index 278cd3e16..49fac17f9 100644
--- a/src/TreeSupport.cpp
+++ b/src/TreeSupport.cpp
@@ -31,9 +31,10 @@
 namespace cura
 {
 
-TreeSupport::TreeSupport(const SliceDataStorage& storage) :
-    volumes_(storage, Application::getInstance().current_slice->scene.current_mesh_group->settings)
+TreeSupport::TreeSupport(const SliceDataStorage& storage)
 {
+    const Settings& mesh_group_settings = Application::getInstance().current_slice->scene.current_mesh_group->settings;
+    volumes_ = TreeModelVolumes(storage, mesh_group_settings);
 }
 
 void TreeSupport::generateSupportAreas(SliceDataStorage& storage)
@@ -98,8 +99,9 @@ void TreeSupport::drawCircles(SliceDataStorage& storage, const std::vector<std::
     const size_t tip_layers = (branch_radius - minimum_tip_radius) / layer_height; //The number of layers to be shrinking the circle to create a tip. This produces a 45 degree angle.
     const coord_t resolution = mesh_group_settings.get<coord_t>("support_tree_collision_resolution");
 
-    std::atomic<size_t> completed = 0; //To track progress in a multi-threaded environment.
-    std::mutex critical_sections;
+    size_t completed = 0; //To track progress, should be locked when altered.
+    std::mutex critical_section_volumes;
+    std::mutex critical_section_progress;
     cura::parallel_for<size_t>(0, contact_nodes.size(), 1, [&](const size_t layer_nr)
     {
         Polygons support_layer;
@@ -141,8 +143,12 @@ void TreeSupport::drawCircles(SliceDataStorage& storage, const std::vector<std::
         support_layer = support_layer.unionPolygons();
         roof_layer = roof_layer.unionPolygons();
         const size_t z_collision_layer = static_cast<size_t>(std::max(0, static_cast<int>(layer_nr) - static_cast<int>(z_distance_bottom_layers) + 1)); //Layer to test against to create a Z-distance.
-        support_layer = support_layer.difference(volumes_.getCollision(0, z_collision_layer)); //Subtract the model itself (sample 0 is with 0 diameter but proper X/Y offset).
-        roof_layer = roof_layer.difference(volumes_.getCollision(0, z_collision_layer));
+        {
+            const std::lock_guard<std::mutex> lock(critical_section_volumes);
+
+            support_layer = support_layer.difference(volumes_.getCollision(0, z_collision_layer)); //Subtract the model itself (sample 0 is with 0 diameter but proper X/Y offset).
+            roof_layer = roof_layer.difference(volumes_.getCollision(0, z_collision_layer));
+        }
         support_layer = support_layer.difference(roof_layer);
         //We smooth this support as much as possible without altering single circles. So we remove any line less than the side length of those circles.
         const double diameter_angle_scale_factor_this_layer = static_cast<double>(storage.support.supportLayers.size() - layer_nr - tip_layers) * diameter_angle_scale_factor; //Maximum scale factor.
@@ -180,19 +186,14 @@ void TreeSupport::drawCircles(SliceDataStorage& storage, const std::vector<std::
         }
 
         {
-            std::lock_guard<std::mutex> critical_section_support_max_layer_nr(critical_sections);
+            const std::lock_guard<std::mutex> lock(critical_section_progress);
 
             if (!storage.support.supportLayers[layer_nr].support_infill_parts.empty() || !storage.support.supportLayers[layer_nr].support_roof.empty())
             {
                 storage.support.layer_nr_max_filled_layer = std::max(storage.support.layer_nr_max_filled_layer, static_cast<int>(layer_nr));
             }
-        }
-
-        ++completed;
-
-        {
-            std::lock_guard<std::mutex> critical_section_progress(critical_sections);
 
+            ++completed;
             const double progress_contact_nodes = contact_nodes.size() * PROGRESS_WEIGHT_DROPDOWN;
             const double progress_current = completed * PROGRESS_WEIGHT_AREAS;
             const double progress_total = completed * PROGRESS_WEIGHT_AREAS;
@@ -318,12 +319,12 @@ void TreeSupport::dropNodes(std::vector<std::vector<Node*>>& contact_nodes)
                              return branch_radius * (node.distance_to_top + 1) / tip_layers;
                         }
                     }();
-                    if (group_index == 0)
-                    {
-                        //Avoid collisions.
-                        const coord_t maximum_move_between_samples = maximum_move_distance + radius_sample_resolution + 100; //100 micron extra for rounding errors.
-                        PolygonUtils::moveOutside(volumes_.getAvoidance(branch_radius_node, layer_nr - 1), next_position, radius_sample_resolution + 100, maximum_move_between_samples * maximum_move_between_samples); //Some extra offset to prevent rounding errors with the sample resolution.
-                    }
+
+                    //Avoid collisions.
+                    constexpr size_t rounding_compensation = 100;
+                    const coord_t maximum_move_between_samples = maximum_move_distance + radius_sample_resolution + rounding_compensation;
+                    const Polygons avoidance = group_index == 0 ? volumes_.getAvoidance(branch_radius_node, layer_nr - 1) : volumes_.getCollision(branch_radius_node, layer_nr - 1);
+                    PolygonUtils::moveOutside(avoidance, next_position, radius_sample_resolution + rounding_compensation, maximum_move_between_samples * maximum_move_between_samples);
 
                     Node* neighbour = nodes_per_part[group_index][neighbours[0]];
                     size_t new_distance_to_top = std::max(node.distance_to_top, neighbour->distance_to_top) + 1;
@@ -365,7 +366,9 @@ void TreeSupport::dropNodes(std::vector<std::vector<Node*>>& contact_nodes)
                     continue;
                 }
                 //If the branch falls completely inside a collision area (the entire branch would be removed by the X/Y offset), delete it.
-                if (group_index > 0 && volumes_.getCollision(0, layer_nr).inside(node.position))
+
+                const Polygons collision = volumes_.getCollision(0, layer_nr);
+                if (group_index > 0 && collision.inside(node.position))
                 {
                     const coord_t branch_radius_node = [&]() -> coord_t
                     {
@@ -378,8 +381,15 @@ void TreeSupport::dropNodes(std::vector<std::vector<Node*>>& contact_nodes)
                             return branch_radius * node.distance_to_top / tip_layers;
                         }
                     }();
-                    const ClosestPolygonPoint to_outside = PolygonUtils::findClosest(node.position, volumes_.getCollision(0, layer_nr));
-                    if (vSize2(node.position - to_outside.location) >= branch_radius_node * branch_radius_node) //Too far inside.
+
+                    const ClosestPolygonPoint to_outside = PolygonUtils::findClosest(node.position, collision);
+                    const bool node_is_tip = node.distance_to_top <= tip_layers;
+                    coord_t max_inside_dist = branch_radius_node;
+                    if (node_is_tip) {
+                        // if the node is part of the tip allow the branch to travel through the support xy distance
+                        max_inside_dist += (tip_layers - node.distance_to_top) * maximum_move_distance;
+                    }
+                    if (vSize2(node.position - to_outside.location) >= max_inside_dist * max_inside_dist) // Too far inside.
                     {
                         if (! support_rests_on_model)
                         {
@@ -419,12 +429,12 @@ void TreeSupport::dropNodes(std::vector<std::vector<Node*>>& contact_nodes)
                         return branch_radius * (node.distance_to_top + 1) / tip_layers;
                     }
                 }();
-                if (group_index == 0)
-                {
-                    //Avoid collisions.
-                    const coord_t maximum_move_between_samples = maximum_move_distance + radius_sample_resolution + 100; //100 micron extra for rounding errors.
-                    PolygonUtils::moveOutside(volumes_.getAvoidance(branch_radius_node, layer_nr - 1), next_layer_vertex, radius_sample_resolution + 100, maximum_move_between_samples * maximum_move_between_samples); //Some extra offset to prevent rounding errors with the sample resolution.
-                }
+
+                //Avoid collisions.
+                constexpr size_t rounding_compensation = 100;
+                const coord_t maximum_move_between_samples = maximum_move_distance + radius_sample_resolution + rounding_compensation;
+                const Polygons avoidance = group_index == 0 ? volumes_.getAvoidance(branch_radius_node, layer_nr - 1) : volumes_.getCollision(branch_radius_node, layer_nr - 1);
+                PolygonUtils::moveOutside(avoidance, next_layer_vertex, radius_sample_resolution + rounding_compensation, maximum_move_between_samples * maximum_move_between_samples);
 
                 const bool to_buildplate = !volumes_.getAvoidance(branch_radius_node, layer_nr - 1).inside(next_layer_vertex);
                 Node* next_node = new Node(next_layer_vertex, node.distance_to_top + 1, node.skin_direction, node.support_roof_layers_below - 1, to_buildplate, p_node);
diff --git a/src/support.cpp b/src/support.cpp
index 23e611ffb..0034ad19a 100644
--- a/src/support.cpp
+++ b/src/support.cpp
@@ -865,7 +865,7 @@ void AreaSupport::generateSupportAreasForMesh(SliceDataStorage& storage, const S
             if (use_xy_distance_overhang) //Z overrides XY distance.
             {
                 // we also want to use the min XY distance when the support is resting on a sloped surface so we calculate the area of the
-                // layer below that protudes beyond the current layer's area and combine it with the current layer's overhang disallowed area
+                // layer below that protrudes beyond the current layer's area and combine it with the current layer's overhang disallowed area
 
                 Polygons larger_area_below; // the areas in the layer below that protrude beyond the area of the current layer
                 if (layer_idx > 1)
@@ -875,7 +875,7 @@ void AreaSupport::generateSupportAreasForMesh(SliceDataStorage& storage, const S
 
                     if (larger_area_below.size())
                     {
-                        // if the layer below protudes sufficiently such that a normal support at xy_distance could be placed there,
+                        // if the layer below protrudes sufficiently such that a normal support at xy_distance could be placed there,
                         // we don't want to use the min XY distance in that area and so we remove the wide area from larger_area_below
 
                         // assume that a minimal support structure would be one line spaced at xy_distance from the model (verified by experiment)