Improved memory allocation efficiency of the 3D path preview generator.

3 files changed, 59 insertions, 41 deletions

diff --git a/xs/src/libslic3r/Utils.hpp b/xs/src/libslic3r/Utils.hpp
index 5e55ccd2b..5bbf1b624 100644
--- a/xs/src/libslic3r/Utils.hpp
+++ b/xs/src/libslic3r/Utils.hpp
@@ -6,6 +6,33 @@ namespace Slic3r {
 extern void set_logging_level(unsigned int level);
 extern void trace(unsigned int level, const char *message);
 
+// Compute the next highest power of 2 of 32-bit v
+// http://graphics.stanford.edu/~seander/bithacks.html
+inline uint32_t next_highest_power_of_2(uint32_t v)
+{
+	if (v != 0)
+	    -- v;
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    return ++ v;
+}
+
+inline uint64_t next_highest_power_of_2(uint64_t v)
+{
+	if (v != 0)
+	    -- v;
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    v |= v >> 32;
+    return ++ v;
+}
+
 } // namespace Slic3r
 
 #endif // slic3r_Utils_hpp_
diff --git a/xs/src/slic3r/GUI/3DScene.cpp b/xs/src/slic3r/GUI/3DScene.cpp
index ab12f7d07..9929655f5 100644
--- a/xs/src/slic3r/GUI/3DScene.cpp
+++ b/xs/src/slic3r/GUI/3DScene.cpp
@@ -512,20 +512,12 @@ static void thick_lines_to_indexed_vertex_array(
                 idx_a[RIGHT] = idx_prev[RIGHT];
             } else if (cross(v_prev, v) > 0.) {
                 // Right turn. Fill in the right turn wedge.
-                volume.triangle_indices.push_back(idx_prev[RIGHT]);
-                volume.triangle_indices.push_back(idx_a   [RIGHT]);
-                volume.triangle_indices.push_back(idx_prev[TOP]);
-                volume.triangle_indices.push_back(idx_prev[RIGHT]);
-                volume.triangle_indices.push_back(idx_prev[BOTTOM]);
-                volume.triangle_indices.push_back(idx_a   [RIGHT]);
+                volume.push_triangle(idx_prev[RIGHT], idx_a   [RIGHT],  idx_prev[TOP]   );
+                volume.push_triangle(idx_prev[RIGHT], idx_prev[BOTTOM], idx_a   [RIGHT] );
             } else {
                 // Left turn. Fill in the left turn wedge.
-                volume.triangle_indices.push_back(idx_prev[LEFT]);
-                volume.triangle_indices.push_back(idx_prev[TOP]);
-                volume.triangle_indices.push_back(idx_a   [LEFT]);
-                volume.triangle_indices.push_back(idx_prev[LEFT]);
-                volume.triangle_indices.push_back(idx_a   [LEFT]);
-                volume.triangle_indices.push_back(idx_prev[BOTTOM]);
+                volume.push_triangle(idx_prev[LEFT],  idx_prev[TOP],    idx_a   [LEFT]  );
+                volume.push_triangle(idx_prev[LEFT],  idx_a   [LEFT],   idx_prev[BOTTOM]);
             }
             if (ii == lines.size()) {
                 if (! sharp) {
@@ -575,42 +567,22 @@ static void thick_lines_to_indexed_vertex_array(
 
         if (! closed) {
             // Terminate open paths with caps.
-            if (i == 0) {
-                volume.quad_indices.push_back(idx_a[BOTTOM]);
-                volume.quad_indices.push_back(idx_a[RIGHT]);
-                volume.quad_indices.push_back(idx_a[TOP]);
-                volume.quad_indices.push_back(idx_a[LEFT]);
-            }
+            if (i == 0)
+                volume.push_quad(idx_a[BOTTOM], idx_a[RIGHT], idx_a[TOP], idx_a[LEFT]);
             // We don't use 'else' because both cases are true if we have only one line.
-            if (i + 1 == lines.size()) {
-                volume.quad_indices.push_back(idx_b[BOTTOM]);
-                volume.quad_indices.push_back(idx_b[LEFT]);
-                volume.quad_indices.push_back(idx_b[TOP]);
-                volume.quad_indices.push_back(idx_b[RIGHT]);
-            }
+            if (i + 1 == lines.size())
+                volume.push_quad(idx_b[BOTTOM], idx_b[LEFT], idx_b[TOP], idx_b[RIGHT]);
         }
         
         // Add quads for a straight hollow tube-like segment.
         // bottom-right face
-        volume.quad_indices.push_back(idx_a[BOTTOM]);
-        volume.quad_indices.push_back(idx_b[BOTTOM]);
-        volume.quad_indices.push_back(idx_b[RIGHT]);
-        volume.quad_indices.push_back(idx_a[RIGHT]);
+        volume.push_quad(idx_a[BOTTOM], idx_b[BOTTOM], idx_b[RIGHT], idx_a[RIGHT]);
         // top-right face
-        volume.quad_indices.push_back(idx_a[RIGHT]);
-        volume.quad_indices.push_back(idx_b[RIGHT]);
-        volume.quad_indices.push_back(idx_b[TOP]);
-        volume.quad_indices.push_back(idx_a[TOP]);
+        volume.push_quad(idx_a[RIGHT], idx_b[RIGHT], idx_b[TOP], idx_a[TOP]);
         // top-left face
-        volume.quad_indices.push_back(idx_a[TOP]);
-        volume.quad_indices.push_back(idx_b[TOP]);
-        volume.quad_indices.push_back(idx_b[LEFT]);
-        volume.quad_indices.push_back(idx_a[LEFT]);
+        volume.push_quad(idx_a[TOP], idx_b[TOP], idx_b[LEFT], idx_a[LEFT]);
         // bottom-left face
-        volume.quad_indices.push_back(idx_a[LEFT]);
-        volume.quad_indices.push_back(idx_b[LEFT]);
-        volume.quad_indices.push_back(idx_b[BOTTOM]);
-        volume.quad_indices.push_back(idx_a[BOTTOM]);
+        volume.push_quad(idx_a[LEFT], idx_b[LEFT], idx_b[BOTTOM], idx_a[BOTTOM]);
     }
 
 #undef LEFT
diff --git a/xs/src/slic3r/GUI/3DScene.hpp b/xs/src/slic3r/GUI/3DScene.hpp
index 4653d5466..1e5b968ba 100644
--- a/xs/src/slic3r/GUI/3DScene.hpp
+++ b/xs/src/slic3r/GUI/3DScene.hpp
@@ -5,6 +5,7 @@
 #include "../../libslic3r/Point.hpp"
 #include "../../libslic3r/Line.hpp"
 #include "../../libslic3r/TriangleMesh.hpp"
+#include "../../libslic3r/Utils.hpp"
 
 namespace Slic3r {
 
@@ -91,7 +92,8 @@ public:
     }
 
     inline void push_geometry(float x, float y, float z, float nx, float ny, float nz) {
-        this->vertices_and_normals_interleaved.reserve(this->vertices_and_normals_interleaved.size() + 6);
+        if (this->vertices_and_normals_interleaved.size() + 6 > this->vertices_and_normals_interleaved.capacity())
+            this->vertices_and_normals_interleaved.reserve(next_highest_power_of_2(this->vertices_and_normals_interleaved.size() + 6));
         this->vertices_and_normals_interleaved.push_back(nx);
         this->vertices_and_normals_interleaved.push_back(ny);
         this->vertices_and_normals_interleaved.push_back(nz);
@@ -104,6 +106,23 @@ public:
         push_geometry(float(x), float(y), float(z), float(nx), float(ny), float(nz));
     }
 
+    inline void push_triangle(int idx1, int idx2, int idx3) {
+        if (this->triangle_indices.size() + 3 > this->vertices_and_normals_interleaved.capacity())
+            this->triangle_indices.reserve(next_highest_power_of_2(this->triangle_indices.size() + 3));
+        this->triangle_indices.push_back(idx1);
+        this->triangle_indices.push_back(idx2);
+        this->triangle_indices.push_back(idx3);
+    };
+
+    inline void push_quad(int idx1, int idx2, int idx3, int idx4) {
+        if (this->quad_indices.size() + 4 > this->vertices_and_normals_interleaved.capacity())
+            this->quad_indices.reserve(next_highest_power_of_2(this->quad_indices.size() + 4));
+        this->quad_indices.push_back(idx1);
+        this->quad_indices.push_back(idx2);
+        this->quad_indices.push_back(idx3);
+        this->quad_indices.push_back(idx4);
+    };
+
     // Finalize the initialization of the geometry & indices,
     // upload the geometry and indices to OpenGL VBO objects
     // and shrink the allocated data, possibly relasing it if it has been loaded into the VBOs.