Parallelize TriangleMeshSlicer::slice(), cherry picked from @alexrj 83ad123d951c6ee663d2f3b02e095c203ca794e7

1 files changed, 100 insertions, 33 deletions

diff --git a/xs/src/libslic3r/TriangleMesh.cpp b/xs/src/libslic3r/TriangleMesh.cpp
index 5737747a2..9ed0dfcd4 100644
--- a/xs/src/libslic3r/TriangleMesh.cpp
+++ b/xs/src/libslic3r/TriangleMesh.cpp
@@ -2,7 +2,6 @@
 #include "ClipperUtils.hpp"
 #include "Geometry.hpp"
 #include <cmath>
-#include <queue>
 #include <deque>
 #include <set>
 #include <vector>
@@ -403,7 +402,7 @@ TriangleMesh::require_shared_vertices()
 }
 
 void
-TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<Polygons>* layers)
+TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<Polygons>* layers) const
 {
     /*
        This method gets called with a list of unscaled Z coordinates and outputs
@@ -427,7 +426,6 @@ TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<Polygons>* la
         
         At the end, we free the tables generated by analyze() as we don't 
         need them anymore.
-        FUTURE: parallelize slice_facet() and make_loops()
         
         NOTE: this method accepts a vector of floats because the mesh coordinate
         type is float.
@@ -435,18 +433,66 @@ TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<Polygons>* la
     
     std::vector<IntersectionLines> lines(z.size());
     
-    for (int facet_idx = 0; facet_idx < this->mesh->stl.stats.number_of_facets; facet_idx++) {
-        stl_facet* facet = &this->mesh->stl.facet_start[facet_idx];
+    {
+        // queue all the facet indices
+        std::queue<size_t> queue;
+        boost::mutex queue_mutex, lines_mutex;
+        for (size_t i = 0; i < this->mesh->stl.stats.number_of_facets; ++i) queue.push(i);
+        
+        boost::thread_group workers;
+        for (int i = 0; i < boost::thread::hardware_concurrency(); i++)
+            workers.add_thread(new boost::thread(&TriangleMeshSlicer::_slice_do, this,
+                &queue, &queue_mutex, &lines, &lines_mutex, z));
+        workers.join_all();
+    }
+    
+    // v_scaled_shared could be freed here
+    
+    // build loops
+    layers->resize(z.size());
+    {
+        // queue all the layer numbers
+        std::queue<size_t> queue;
+        boost::mutex queue_mutex;
+        for (size_t i = 0; i < lines.size(); ++i) queue.push(i);
+        
+        // We don't use a mutex for lines because workers are only writing the skip property
+        // and no workers work on the same layer (i.e. item of 'lines').
+        boost::thread_group workers;
+        for (int i = 0; i < boost::thread::hardware_concurrency(); i++)
+            workers.add_thread(new boost::thread(&TriangleMeshSlicer::_make_loops_do, this,
+                &queue, &queue_mutex, &lines, layers));
+        workers.join_all();
+    }
+}
+
+void
+TriangleMeshSlicer::_slice_do(std::queue<size_t>* queue, boost::mutex* queue_mutex,
+    std::vector<IntersectionLines>* lines, boost::mutex* lines_mutex, const std::vector<float> &z) const
+{
+    //std::cout << "THREAD STARTED: " << boost::this_thread::get_id() << std::endl;
+    
+    while (true) {
+        int facet_idx;
+        {
+            boost::lock_guard<boost::mutex> l(*queue_mutex);
+            if (queue->empty()) return;
+            facet_idx = queue->front();
+            queue->pop();
+        }
+        //std::cout << "  Facet " << facet_idx << " (" << boost::this_thread::get_id() << ")" << std::endl;
+        
+        const stl_facet &facet = this->mesh->stl.facet_start[facet_idx];
         
         // find facet extents
-        float min_z = fminf(facet->vertex[0].z, fminf(facet->vertex[1].z, facet->vertex[2].z));
-        float max_z = fmaxf(facet->vertex[0].z, fmaxf(facet->vertex[1].z, facet->vertex[2].z));
+        const float min_z = fminf(facet.vertex[0].z, fminf(facet.vertex[1].z, facet.vertex[2].z));
+        const float max_z = fmaxf(facet.vertex[0].z, fmaxf(facet.vertex[1].z, facet.vertex[2].z));
         
         #ifdef SLIC3R_TRIANGLEMESH_DEBUG
         printf("\n==> FACET %d (%f,%f,%f - %f,%f,%f - %f,%f,%f):\n", facet_idx,
-            facet->vertex[0].x, facet->vertex[0].y, facet->vertex[0].z,
-            facet->vertex[1].x, facet->vertex[1].y, facet->vertex[1].z,
-            facet->vertex[2].x, facet->vertex[2].y, facet->vertex[2].z);
+            facet.vertex[0].x, facet.vertex[0].y, facet.vertex[0].z,
+            facet.vertex[1].x, facet.vertex[1].y, facet.vertex[1].z,
+            facet.vertex[2].x, facet.vertex[2].y, facet.vertex[2].z);
         printf("z: min = %.2f, max = %.2f\n", min_z, max_z);
         #endif
         
@@ -460,25 +506,14 @@ TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<Polygons>* la
         
         for (std::vector<float>::const_iterator it = min_layer; it != max_layer + 1; ++it) {
             std::vector<float>::size_type layer_idx = it - z.begin();
-            this->slice_facet(*it / SCALING_FACTOR, *facet, facet_idx, min_z, max_z, &lines[layer_idx]);
+            this->slice_facet(*it / SCALING_FACTOR, facet, facet_idx, min_z, max_z, &(*lines)[layer_idx], lines_mutex);
         }
-    }
-    
-    // v_scaled_shared could be freed here
-    
-    // build loops
-    layers->resize(z.size());
-    for (std::vector<IntersectionLines>::iterator it = lines.begin(); it != lines.end(); ++it) {
-        size_t layer_idx = it - lines.begin();
-        #ifdef SLIC3R_TRIANGLEMESH_DEBUG
-        printf("Layer " PRINTF_ZU ":\n", layer_idx);
-        #endif
-        this->make_loops(*it, &(*layers)[layer_idx]);
+        boost::this_thread::interruption_point();
     }
 }
 
 void
-TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<ExPolygons>* layers)
+TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<ExPolygons>* layers) const
 {
     std::vector<Polygons> layers_p;
     this->slice(z, &layers_p);
@@ -495,7 +530,9 @@ TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<ExPolygons>*
 }
 
 void
-TriangleMeshSlicer::slice_facet(float slice_z, const stl_facet &facet, const int &facet_idx, const float &min_z, const float &max_z, std::vector<IntersectionLine>* lines) const
+TriangleMeshSlicer::slice_facet(float slice_z, const stl_facet &facet, const int &facet_idx,
+    const float &min_z, const float &max_z, std::vector<IntersectionLine>* lines,
+    boost::mutex* lines_mutex) const
 {
     std::vector<IntersectionPoint> points;
     std::vector< std::vector<IntersectionPoint>::size_type > points_on_layer;
@@ -547,7 +584,12 @@ TriangleMeshSlicer::slice_facet(float slice_z, const stl_facet &facet, const int
             line.b.y    = b->y;
             line.a_id   = a_id;
             line.b_id   = b_id;
-            lines->push_back(line);
+            if (lines_mutex != NULL) {
+                boost::lock_guard<boost::mutex> l(*lines_mutex);
+                lines->push_back(line);
+            } else {
+                lines->push_back(line);
+            }
             
             found_horizontal_edge = true;
             
@@ -600,13 +642,38 @@ TriangleMeshSlicer::slice_facet(float slice_z, const stl_facet &facet, const int
         line.b_id       = points[0].point_id;
         line.edge_a_id  = points[1].edge_id;
         line.edge_b_id  = points[0].edge_id;
-        lines->push_back(line);
+        if (lines_mutex != NULL) {
+            boost::lock_guard<boost::mutex> l(*lines_mutex);
+            lines->push_back(line);
+        } else {
+            lines->push_back(line);
+        }
         return;
     }
 }
 
 void
-TriangleMeshSlicer::make_loops(std::vector<IntersectionLine> &lines, Polygons* loops)
+TriangleMeshSlicer::_make_loops_do(std::queue<size_t>* queue, boost::mutex* queue_mutex,
+    std::vector<IntersectionLines>* lines, std::vector<Polygons>* layers) const
+{
+    //std::cout << "THREAD STARTED: " << boost::this_thread::get_id() << std::endl;
+    
+    while (true) {
+        size_t layer_id;
+        {
+            boost::lock_guard<boost::mutex> l(*queue_mutex);
+            if (queue->empty()) return;
+            layer_id = queue->front();
+            queue->pop();
+        }
+        //std::cout << "  Layer " << layer_id << " (" << boost::this_thread::get_id() << ")" << std::endl;
+        this->make_loops((*lines)[layer_id], &(*layers)[layer_id]);
+        boost::this_thread::interruption_point();
+    }
+}
+
+void
+TriangleMeshSlicer::make_loops(std::vector<IntersectionLine> &lines, Polygons* loops) const
 {
     /*
     SVG svg("lines.svg");
@@ -707,6 +774,7 @@ TriangleMeshSlicer::make_loops(std::vector<IntersectionLine> &lines, Polygons* l
                     for (IntersectionLinePtrs::const_iterator lineptr = loop.begin(); lineptr != loop.end(); ++lineptr) {
                         p.points.push_back((*lineptr)->a);
                     }
+                    
                     loops->push_back(p);
                     
                     #ifdef SLIC3R_TRIANGLEMESH_DEBUG
@@ -746,7 +814,7 @@ class _area_comp {
 };
 
 void
-TriangleMeshSlicer::make_expolygons_simple(std::vector<IntersectionLine> &lines, ExPolygons* slices)
+TriangleMeshSlicer::make_expolygons_simple(std::vector<IntersectionLine> &lines, ExPolygons* slices) const
 {
     Polygons loops;
     this->make_loops(lines, &loops);
@@ -780,7 +848,7 @@ TriangleMeshSlicer::make_expolygons_simple(std::vector<IntersectionLine> &lines,
 }
 
 void
-TriangleMeshSlicer::make_expolygons(const Polygons &loops, ExPolygons* slices)
+TriangleMeshSlicer::make_expolygons(const Polygons &loops, ExPolygons* slices) const
 {
     /*
         Input loops are not suitable for evenodd nor nonzero fill types, as we might get
@@ -844,7 +912,7 @@ TriangleMeshSlicer::make_expolygons(const Polygons &loops, ExPolygons* slices)
 }
 
 void
-TriangleMeshSlicer::make_expolygons(std::vector<IntersectionLine> &lines, ExPolygons* slices)
+TriangleMeshSlicer::make_expolygons(std::vector<IntersectionLine> &lines, ExPolygons* slices) const
 {
     Polygons pp;
     this->make_loops(lines, &pp);
@@ -852,7 +920,7 @@ TriangleMeshSlicer::make_expolygons(std::vector<IntersectionLine> &lines, ExPoly
 }
 
 void
-TriangleMeshSlicer::cut(float z, TriangleMesh* upper, TriangleMesh* lower)
+TriangleMeshSlicer::cut(float z, TriangleMesh* upper, TriangleMesh* lower) const
 {
     IntersectionLines upper_lines, lower_lines;
     
@@ -1004,7 +1072,6 @@ TriangleMeshSlicer::cut(float z, TriangleMesh* upper, TriangleMesh* lower)
     
     stl_get_size(&(upper->stl));
     stl_get_size(&(lower->stl));
-    
 }
 
 TriangleMeshSlicer::TriangleMeshSlicer(TriangleMesh* _mesh) : mesh(_mesh), v_scaled_shared(NULL)