Merge remote-tracking branch 'remotes/origin/lm_lay_flat_round_merged_facets'

10 files changed, 268 insertions, 135 deletions

diff --git a/xs/src/libslic3r/Format/3mf.cpp b/xs/src/libslic3r/Format/3mf.cpp
index dd3500eba..5de1d26c5 100644
--- a/xs/src/libslic3r/Format/3mf.cpp
+++ b/xs/src/libslic3r/Format/3mf.cpp
@@ -1491,6 +1491,7 @@ namespace Slic3r {
 
             stl_get_size(&stl);
             volume->mesh.repair();
+            volume->calculate_convex_hull();
 
             // apply volume's name and config data
             for (const Metadata& metadata : volume_data.metadata)
diff --git a/xs/src/libslic3r/Format/AMF.cpp b/xs/src/libslic3r/Format/AMF.cpp
index 600aa6cd9..886bbae97 100644
--- a/xs/src/libslic3r/Format/AMF.cpp
+++ b/xs/src/libslic3r/Format/AMF.cpp
@@ -406,6 +406,7 @@ void AMFParserContext::endElement(const char * /* name */)
         }
         stl_get_size(&stl);
         m_volume->mesh.repair();
+        m_volume->calculate_convex_hull();
         m_volume_facets.clear();
         m_volume = nullptr;
         break;
diff --git a/xs/src/libslic3r/Geometry.cpp b/xs/src/libslic3r/Geometry.cpp
index 39b626ee3..aaf0352c9 100644
--- a/xs/src/libslic3r/Geometry.cpp
+++ b/xs/src/libslic3r/Geometry.cpp
@@ -195,47 +195,62 @@ using namespace boost::polygon;  // provides also high() and low()
 
 namespace Slic3r { namespace Geometry {
 
-static bool
-sort_points (Point a, Point b)
-{
-    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
-}
+struct SortPoints {
+    template <class T>
+    bool operator()(const T& a, const T& b) const {
+        return (b.x > a.x) || (a.x == b.x && b.y > a.y);
+    }
+};
 
-/* This implementation is based on Andrew's monotone chain 2D convex hull algorithm */
-Polygon
-convex_hull(Points points)
+// This implementation is based on Andrew's monotone chain 2D convex hull algorithm
+template<class T>
+static T raw_convex_hull(T& points)
 {
     assert(points.size() >= 3);
     // sort input points
-    std::sort(points.begin(), points.end(), sort_points);
+    std::sort(points.begin(), points.end(), SortPoints());
     
     int n = points.size(), k = 0;
-    Polygon hull;
+    T hull;
 
     if (n >= 3) {
-        hull.points.resize(2*n);
+        hull.resize(2*n);
 
         // Build lower hull
         for (int i = 0; i < n; i++) {
-            while (k >= 2 && points[i].ccw(hull.points[k-2], hull.points[k-1]) <= 0) k--;
-            hull.points[k++] = points[i];
+            while (k >= 2 && points[i].ccw(hull[k-2], hull[k-1]) <= 0) k--;
+            hull[k++] = points[i];
         }
 
         // Build upper hull
         for (int i = n-2, t = k+1; i >= 0; i--) {
-            while (k >= t && points[i].ccw(hull.points[k-2], hull.points[k-1]) <= 0) k--;
-            hull.points[k++] = points[i];
+            while (k >= t && points[i].ccw(hull[k-2], hull[k-1]) <= 0) k--;
+            hull[k++] = points[i];
         }
 
-        hull.points.resize(k);
+        hull.resize(k);
         
-        assert( hull.points.front().coincides_with(hull.points.back()) );
-        hull.points.pop_back();
+        assert( hull.front().coincides_with(hull.back()) );
+        hull.pop_back();
     }
     
     return hull;
 }
 
+Pointf3s
+convex_hull(Pointf3s points)
+{
+    return raw_convex_hull(points);
+}
+
+Polygon
+convex_hull(Points points)
+{
+    Polygon hull;
+    hull.points = raw_convex_hull(points);
+    return hull;
+}
+
 Polygon
 convex_hull(const Polygons &polygons)
 {
@@ -243,7 +258,7 @@ convex_hull(const Polygons &polygons)
     for (Polygons::const_iterator p = polygons.begin(); p != polygons.end(); ++p) {
         pp.insert(pp.end(), p->points.begin(), p->points.end());
     }
-    return convex_hull(pp);
+    return convex_hull(std::move(pp));
 }
 
 /* accepts an arrayref of points and returns a list of indices
diff --git a/xs/src/libslic3r/Geometry.hpp b/xs/src/libslic3r/Geometry.hpp
index c2c3dc8b7..956ef82aa 100644
--- a/xs/src/libslic3r/Geometry.hpp
+++ b/xs/src/libslic3r/Geometry.hpp
@@ -108,8 +108,10 @@ inline bool segment_segment_intersection(const Pointf &p1, const Vectorf &v1, co
     return true;
 }
 
+Pointf3s convex_hull(Pointf3s points);
 Polygon convex_hull(Points points);
 Polygon convex_hull(const Polygons &polygons);
+
 void chained_path(const Points &points, std::vector<Points::size_type> &retval, Point start_near);
 void chained_path(const Points &points, std::vector<Points::size_type> &retval);
 template<class T> void chained_path_items(Points &points, T &items, T &retval);
diff --git a/xs/src/libslic3r/Model.cpp b/xs/src/libslic3r/Model.cpp
index bceeea258..09b515c2f 100644
--- a/xs/src/libslic3r/Model.cpp
+++ b/xs/src/libslic3r/Model.cpp
@@ -17,6 +17,11 @@
 #include "SVG.hpp"
 #include <Eigen/Dense>
 
+static const float UNIT_MATRIX[] = { 1.0f, 0.0f, 0.0f, 0.0f,
+                                     0.0f, 1.0f, 0.0f, 0.0f,
+                                     0.0f, 0.0f, 1.0f, 0.0f,
+                                     0.0f, 0.0f, 0.0f, 1.0f };
+
 namespace Slic3r {
 
     unsigned int Model::s_auto_extruder_id = 1;
@@ -235,14 +240,6 @@ BoundingBoxf3 Model::bounding_box() const
     return bb;
 }
 
-BoundingBoxf3 Model::transformed_bounding_box() const
-{
-    BoundingBoxf3 bb;
-    for (const ModelObject* obj : this->objects)
-        bb.merge(obj->tight_bounding_box(false));
-    return bb;
-}
-
 void Model::center_instances_around_point(const Pointf &point)
 {
 //    BoundingBoxf3 bb = this->bounding_box();
@@ -623,54 +620,6 @@ const BoundingBoxf3& ModelObject::bounding_box() const
     return m_bounding_box;
 }
 
-BoundingBoxf3 ModelObject::tight_bounding_box(bool include_modifiers) const
-{
-    BoundingBoxf3 bb;
-
-    for (const ModelVolume* vol : this->volumes)
-    {
-        if (include_modifiers || !vol->modifier)
-        {
-            for (const ModelInstance* inst : this->instances)
-            {
-                double c = cos(inst->rotation);
-                double s = sin(inst->rotation);
-
-                for (int f = 0; f < vol->mesh.stl.stats.number_of_facets; ++f)
-                {
-                    const stl_facet& facet = vol->mesh.stl.facet_start[f];
-
-                    for (int i = 0; i < 3; ++i)
-                    {
-                        // original point
-                        const stl_vertex& v = facet.vertex[i];
-                        Pointf3 p((double)v.x, (double)v.y, (double)v.z);
-
-                        // scale
-                        p.x *= inst->scaling_factor;
-                        p.y *= inst->scaling_factor;
-                        p.z *= inst->scaling_factor;
-
-                        // rotate Z
-                        double x = p.x;
-                        double y = p.y;
-                        p.x = c * x - s * y;
-                        p.y = s * x + c * y;
-
-                        // translate
-                        p.x += inst->offset.x;
-                        p.y += inst->offset.y;
-
-                        bb.merge(p);
-                    }
-                }
-            }
-        }
-    }
-
-    return bb;
-}
-
 // A mesh containing all transformed instances of this object.
 TriangleMesh ModelObject::mesh() const
 {
@@ -755,37 +704,36 @@ void ModelObject::center_around_origin()
 void ModelObject::translate(coordf_t x, coordf_t y, coordf_t z)
 {
     for (ModelVolume *v : this->volumes)
+    {
         v->mesh.translate(float(x), float(y), float(z));
-    if (m_bounding_box_valid) 
+        v->m_convex_hull.translate(float(x), float(y), float(z));
+    }
+
+    if (m_bounding_box_valid)
         m_bounding_box.translate(x, y, z);
 }
 
 void ModelObject::scale(const Pointf3 &versor)
 {
     for (ModelVolume *v : this->volumes)
+    {
         v->mesh.scale(versor);
+        v->m_convex_hull.scale(versor);
+    }
     // reset origin translation since it doesn't make sense anymore
     this->origin_translation = Pointf3(0,0,0);
     this->invalidate_bounding_box();
 }
 
-void ModelObject::rotate(float angle, const Axis &axis)
+void ModelObject::rotate(float angle, const Pointf3& axis)
 {
-    float min_z = FLT_MAX;
     for (ModelVolume *v : this->volumes)
     {
         v->mesh.rotate(angle, axis);
-        min_z = std::min(min_z, v->mesh.stl.stats.min.z);
+        v->m_convex_hull.rotate(angle, axis);
     }
 
-    if (min_z != 0.0f)
-    {
-        // translate the object so that its minimum z lays on the bed
-        for (ModelVolume *v : this->volumes)
-        {
-            v->mesh.translate(0.0f, 0.0f, -min_z);
-        }
-    }
+    center_around_origin();
 
     this->origin_translation = Pointf3(0, 0, 0);
     this->invalidate_bounding_box();
@@ -799,6 +747,7 @@ void ModelObject::transform(const float* matrix3x4)
     for (ModelVolume* v : volumes)
     {
         v->mesh.transform(matrix3x4);
+        v->m_convex_hull.transform(matrix3x4);
     }
 
     origin_translation = Pointf3(0.0, 0.0, 0.0);
@@ -808,8 +757,12 @@ void ModelObject::transform(const float* matrix3x4)
 void ModelObject::mirror(const Axis &axis)
 {
     for (ModelVolume *v : this->volumes)
+    {
         v->mesh.mirror(axis);
-    this->origin_translation = Pointf3(0,0,0);
+        v->m_convex_hull.mirror(axis);
+    }
+
+    this->origin_translation = Pointf3(0, 0, 0);
     this->invalidate_bounding_box();
 }
 
@@ -913,45 +866,20 @@ void ModelObject::split(ModelObjectPtrs* new_objects)
 
 void ModelObject::check_instances_print_volume_state(const BoundingBoxf3& print_volume)
 {
-    for (ModelVolume* vol : this->volumes)
+    for (const ModelVolume* vol : this->volumes)
     {
         if (!vol->modifier)
         {
             for (ModelInstance* inst : this->instances)
             {
-                BoundingBoxf3 bb;
-
-                double c = cos(inst->rotation);
-                double s = sin(inst->rotation);
+                std::vector<float> world_mat(UNIT_MATRIX, std::end(UNIT_MATRIX));
+                Eigen::Transform<float, 3, Eigen::Affine> m = Eigen::Transform<float, 3, Eigen::Affine>::Identity();
+                m.translate(Eigen::Vector3f((float)inst->offset.x, (float)inst->offset.y, 0.0f));
+                m.rotate(Eigen::AngleAxisf(inst->rotation, Eigen::Vector3f::UnitZ()));
+                m.scale(inst->scaling_factor);
+                ::memcpy((void*)world_mat.data(), (const void*)m.data(), 16 * sizeof(float));
 
-                for (int f = 0; f < vol->mesh.stl.stats.number_of_facets; ++f)
-                {
-                    const stl_facet& facet = vol->mesh.stl.facet_start[f];
-
-                    for (int i = 0; i < 3; ++i)
-                    {
-                        // original point
-                        const stl_vertex& v = facet.vertex[i];
-                        Pointf3 p((double)v.x, (double)v.y, (double)v.z);
-
-                        // scale
-                        p.x *= inst->scaling_factor;
-                        p.y *= inst->scaling_factor;
-                        p.z *= inst->scaling_factor;
-
-                        // rotate Z
-                        double x = p.x;
-                        double y = p.y;
-                        p.x = c * x - s * y;
-                        p.y = s * x + c * y;
-
-                        // translate
-                        p.x += inst->offset.x;
-                        p.y += inst->offset.y;
-
-                        bb.merge(p);
-                    }
-                }
+                BoundingBoxf3 bb = vol->get_convex_hull().transformed_bounding_box(world_mat);
 
                 if (print_volume.contains(bb))
                     inst->print_volume_state = ModelInstance::PVS_Inside;
@@ -1034,6 +962,16 @@ ModelMaterial* ModelVolume::assign_unique_material()
     return model->add_material(this->_material_id);
 }
 
+void ModelVolume::calculate_convex_hull()
+{
+    m_convex_hull = mesh.convex_hull_3d();
+}
+
+const TriangleMesh& ModelVolume::get_convex_hull() const
+{
+    return m_convex_hull;
+}
+
 // Split this volume, append the result to the object owning this volume.
 // Return the number of volumes created from this one.
 // This is useful to assign different materials to different volumes of an object.
diff --git a/xs/src/libslic3r/Model.hpp b/xs/src/libslic3r/Model.hpp
index 4c650f0de..dadd515de 100644
--- a/xs/src/libslic3r/Model.hpp
+++ b/xs/src/libslic3r/Model.hpp
@@ -105,9 +105,6 @@ public:
     // This bounding box is being cached.
     const BoundingBoxf3& bounding_box() const;
     void invalidate_bounding_box() { m_bounding_box_valid = false; }
-    // Returns a snug bounding box of the transformed instances.
-    // This bounding box is not being cached.
-    BoundingBoxf3 tight_bounding_box(bool include_modifiers) const;
 
     // A mesh containing all transformed instances of this object.
     TriangleMesh mesh() const;
@@ -123,7 +120,7 @@ public:
     void translate(const Vectorf3 &vector) { this->translate(vector.x, vector.y, vector.z); }
     void translate(coordf_t x, coordf_t y, coordf_t z);
     void scale(const Pointf3 &versor);
-    void rotate(float angle, const Axis &axis);
+    void rotate(float angle, const Pointf3& axis);
     void transform(const float* matrix3x4);
     void mirror(const Axis &axis);
     size_t materials_count() const;
@@ -157,6 +154,10 @@ private:
 class ModelVolume
 {
     friend class ModelObject;
+
+    // The convex hull of this model's mesh.
+    TriangleMesh m_convex_hull;
+
 public:
     std::string name;
     // The triangular model.
@@ -180,19 +181,32 @@ public:
 
     ModelMaterial* assign_unique_material();
     
+    void calculate_convex_hull();
+    const TriangleMesh& get_convex_hull() const;
+
 private:
     // Parent object owning this ModelVolume.
     ModelObject* object;
     t_model_material_id _material_id;
     
-    ModelVolume(ModelObject *object, const TriangleMesh &mesh) : mesh(mesh), modifier(false), object(object) {}
-    ModelVolume(ModelObject *object, TriangleMesh &&mesh) : mesh(std::move(mesh)), modifier(false), object(object) {}
-    ModelVolume(ModelObject *object, const ModelVolume &other) : 
-        name(other.name), mesh(other.mesh), config(other.config), modifier(other.modifier), object(object)
-        { this->material_id(other.material_id()); }
-    ModelVolume(ModelObject *object, const ModelVolume &other, const TriangleMesh &&mesh) : 
+    ModelVolume(ModelObject *object, const TriangleMesh &mesh) : mesh(mesh), modifier(false), object(object)
+    {
+        if (mesh.stl.stats.number_of_facets > 1)
+            calculate_convex_hull();
+    }
+    ModelVolume(ModelObject *object, TriangleMesh &&mesh, TriangleMesh &&convex_hull) : mesh(std::move(mesh)), m_convex_hull(std::move(convex_hull)), modifier(false), object(object) {}
+    ModelVolume(ModelObject *object, const ModelVolume &other) :
+        name(other.name), mesh(other.mesh), m_convex_hull(other.m_convex_hull), config(other.config), modifier(other.modifier), object(object)
+    {
+        this->material_id(other.material_id());
+    }
+    ModelVolume(ModelObject *object, const ModelVolume &other, const TriangleMesh &&mesh) :
         name(other.name), mesh(std::move(mesh)), config(other.config), modifier(other.modifier), object(object)
-        { this->material_id(other.material_id()); }
+    {
+        this->material_id(other.material_id());
+        if (mesh.stl.stats.number_of_facets > 1)
+            calculate_convex_hull();
+    }
 };
 
 // A single instance of a ModelObject.
@@ -285,8 +299,6 @@ public:
     bool add_default_instances();
     // Returns approximate axis aligned bounding box of this model
     BoundingBoxf3 bounding_box() const;
-    // Returns tight axis aligned bounding box of this model
-    BoundingBoxf3 transformed_bounding_box() const;
     void center_instances_around_point(const Pointf &point);
     void translate(coordf_t x, coordf_t y, coordf_t z) { for (ModelObject *o : this->objects) o->translate(x, y, z); }
     TriangleMesh mesh() const;
diff --git a/xs/src/libslic3r/Point.cpp b/xs/src/libslic3r/Point.cpp
index 2abcd26af..349b00bb6 100644
--- a/xs/src/libslic3r/Point.cpp
+++ b/xs/src/libslic3r/Point.cpp
@@ -263,6 +263,12 @@ operator<<(std::ostream &stm, const Pointf &pointf)
     return stm << pointf.x << "," << pointf.y;
 }
 
+double
+Pointf::ccw(const Pointf &p1, const Pointf &p2) const
+{
+    return (double)(p2.x - p1.x)*(double)(this->y - p1.y) - (double)(p2.y - p1.y)*(double)(this->x - p1.x);
+}
+
 std::string
 Pointf::wkt() const
 {
diff --git a/xs/src/libslic3r/Point.hpp b/xs/src/libslic3r/Point.hpp
index 87104674f..347966c03 100644
--- a/xs/src/libslic3r/Point.hpp
+++ b/xs/src/libslic3r/Point.hpp
@@ -221,6 +221,7 @@ public:
     static Pointf new_unscale(const Point &p) {
         return Pointf(unscale(p.x), unscale(p.y));
     };
+    double ccw(const Pointf &p1, const Pointf &p2) const;
     std::string wkt() const;
     std::string dump_perl() const;
     void scale(double factor);
diff --git a/xs/src/libslic3r/TriangleMesh.cpp b/xs/src/libslic3r/TriangleMesh.cpp
index 45e4b6f5d..4c45680b6 100644
--- a/xs/src/libslic3r/TriangleMesh.cpp
+++ b/xs/src/libslic3r/TriangleMesh.cpp
@@ -1,6 +1,9 @@
 #include "TriangleMesh.hpp"
 #include "ClipperUtils.hpp"
 #include "Geometry.hpp"
+#include "qhull/src/libqhullcpp/Qhull.h"
+#include "qhull/src/libqhullcpp/QhullFacetList.h"
+#include "qhull/src/libqhullcpp/QhullVertexSet.h"
 #include <cmath>
 #include <deque>
 #include <queue>
@@ -10,11 +13,14 @@
 #include <utility>
 #include <algorithm>
 #include <math.h>
+#include <type_traits>
 
 #include <boost/log/trivial.hpp>
 
 #include <tbb/parallel_for.h>
 
+#include <Eigen/Dense>
+
 #if 0
     #define DEBUG
     #define _DEBUG
@@ -318,6 +324,17 @@ void TriangleMesh::translate(float x, float y, float z)
     stl_invalidate_shared_vertices(&this->stl);
 }
 
+void TriangleMesh::rotate(float angle, Pointf3 axis)
+{
+    if (angle == 0.f)
+        return;
+
+    axis = normalize(axis);
+    Eigen::Transform<float, 3, Eigen::Affine> m = Eigen::Transform<float, 3, Eigen::Affine>::Identity();
+    m.rotate(Eigen::AngleAxisf(angle, Eigen::Vector3f(axis.x, axis.y, axis.z)));
+    stl_transform(&stl, (float*)m.data());
+}
+
 void TriangleMesh::rotate(float angle, const Axis &axis)
 {
     if (angle == 0.f)
@@ -597,6 +614,140 @@ TriangleMesh::bounding_box() const
     return bb;
 }
 
+BoundingBoxf3 TriangleMesh::transformed_bounding_box(const std::vector<float>& matrix) const
+{
+    bool has_shared = (stl.v_shared != nullptr);
+    if (!has_shared)
+        stl_generate_shared_vertices(&stl);
+
+    unsigned int vertices_count = (stl.stats.shared_vertices > 0) ? (unsigned int)stl.stats.shared_vertices : 3 * (unsigned int)stl.stats.number_of_facets;
+
+    if (vertices_count == 0)
+        return BoundingBoxf3();
+
+    Eigen::MatrixXf src_vertices(3, vertices_count);
+
+    if (stl.stats.shared_vertices > 0)
+    {
+        stl_vertex* vertex_ptr = stl.v_shared;
+        for (int i = 0; i < stl.stats.shared_vertices; ++i)
+        {
+            src_vertices(0, i) = vertex_ptr->x;
+            src_vertices(1, i) = vertex_ptr->y;
+            src_vertices(2, i) = vertex_ptr->z;
+            vertex_ptr += 1;
+        }
+    }
+    else
+    {
+        stl_facet* facet_ptr = stl.facet_start;
+        unsigned int v_id = 0;
+        while (facet_ptr < stl.facet_start + stl.stats.number_of_facets)
+        {
+            for (int i = 0; i < 3; ++i)
+            {
+                src_vertices(0, v_id) = facet_ptr->vertex[i].x;
+                src_vertices(1, v_id) = facet_ptr->vertex[i].y;
+                src_vertices(2, v_id) = facet_ptr->vertex[i].z;
+            }
+            facet_ptr += 1;
+            ++v_id;
+        }
+    }
+
+    if (!has_shared && (stl.stats.shared_vertices > 0))
+        stl_invalidate_shared_vertices(&stl);
+
+    Eigen::Transform<float, 3, Eigen::Affine> m;
+    ::memcpy((void*)m.data(), (const void*)matrix.data(), 16 * sizeof(float));
+
+    Eigen::MatrixXf dst_vertices(3, vertices_count);
+    dst_vertices = m * src_vertices.colwise().homogeneous();
+
+    float min_x = dst_vertices(0, 0);
+    float max_x = dst_vertices(0, 0);
+    float min_y = dst_vertices(1, 0);
+    float max_y = dst_vertices(1, 0);
+    float min_z = dst_vertices(2, 0);
+    float max_z = dst_vertices(2, 0);
+
+    for (int i = 1; i < vertices_count; ++i)
+    {
+        min_x = std::min(min_x, dst_vertices(0, i));
+        max_x = std::max(max_x, dst_vertices(0, i));
+        min_y = std::min(min_y, dst_vertices(1, i));
+        max_y = std::max(max_y, dst_vertices(1, i));
+        min_z = std::min(min_z, dst_vertices(2, i));
+        max_z = std::max(max_z, dst_vertices(2, i));
+    }
+
+    return BoundingBoxf3(Pointf3((coordf_t)min_x, (coordf_t)min_y, (coordf_t)min_z), Pointf3((coordf_t)max_x, (coordf_t)max_y, (coordf_t)max_z));
+}
+
+TriangleMesh TriangleMesh::convex_hull_3d() const
+{
+    // Helper struct for qhull:
+    struct PointForQHull{
+        PointForQHull(float x_p, float y_p, float z_p) : x((realT)x_p), y((realT)y_p), z((realT)z_p) {}
+        realT x, y, z;
+    };
+    std::vector<PointForQHull> src_vertices;
+
+    // We will now fill the vector with input points for computation:
+    stl_facet* facet_ptr = stl.facet_start;
+    while (facet_ptr < stl.facet_start + stl.stats.number_of_facets)
+    {
+        for (int i = 0; i < 3; ++i)
+        {
+            const stl_vertex& v = facet_ptr->vertex[i];
+            src_vertices.emplace_back(v.x, v.y, v.z);
+        }
+
+        facet_ptr += 1;
+    }
+
+    // The qhull call:
+    orgQhull::Qhull qhull;
+    qhull.disableOutputStream(); // we want qhull to be quiet
+    try
+    {
+        qhull.runQhull("", 3, (int)src_vertices.size(), (const realT*)(src_vertices.data()), "Qt");
+    }
+    catch (...)
+    {
+        std::cout << "Unable to create convex hull" << std::endl;
+        return TriangleMesh();
+    }
+
+    // Let's collect results:
+    Pointf3s det_vertices;
+    std::vector<Point3> facets;
+    auto facet_list = qhull.facetList().toStdVector();
+    for (const orgQhull::QhullFacet& facet : facet_list)
+    {   // iterate through facets
+        orgQhull::QhullVertexSet vertices = facet.vertices();
+        for (int i = 0; i < 3; ++i)
+        {   // iterate through facet's vertices
+
+            orgQhull::QhullPoint p = vertices[i].point();
+            const float* coords = p.coordinates();
+            det_vertices.emplace_back(coords[0], coords[1], coords[2]);
+        }
+        unsigned int size = (unsigned int)det_vertices.size();
+        facets.emplace_back(size - 3, size - 2, size - 1);
+    }
+
+    TriangleMesh output_mesh(det_vertices, facets);
+    output_mesh.repair();
+    output_mesh.require_shared_vertices();
+    return output_mesh;
+}
+
+const float* TriangleMesh::first_vertex() const
+{
+    return stl.facet_start ? &stl.facet_start->vertex[0].x : nullptr;
+}
+
 void
 TriangleMesh::require_shared_vertices()
 {
diff --git a/xs/src/libslic3r/TriangleMesh.hpp b/xs/src/libslic3r/TriangleMesh.hpp
index c700784a5..72e541afc 100644
--- a/xs/src/libslic3r/TriangleMesh.hpp
+++ b/xs/src/libslic3r/TriangleMesh.hpp
@@ -40,6 +40,7 @@ public:
     void scale(const Pointf3 &versor);
     void translate(float x, float y, float z);
     void rotate(float angle, const Axis &axis);
+    void rotate(float angle, Pointf3 axis);
     void rotate_x(float angle);
     void rotate_y(float angle);
     void rotate_z(float angle);
@@ -53,8 +54,13 @@ public:
     TriangleMeshPtrs split() const;
     void merge(const TriangleMesh &mesh);
     ExPolygons horizontal_projection() const;
+    const float* first_vertex() const;
     Polygon convex_hull();
     BoundingBoxf3 bounding_box() const;
+    // Returns the bbox of this TriangleMesh transformed by the given matrix
+    BoundingBoxf3 transformed_bounding_box(const std::vector<float>& matrix) const;
+    // Returns the convex hull of this TriangleMesh
+    TriangleMesh convex_hull_3d() const;
     void reset_repair_stats();
     bool needed_repair() const;
     size_t facets_count() const;
@@ -66,7 +72,7 @@ public:
     // Count disconnected triangle patches.
     size_t number_of_patches() const;
 
-    stl_file stl;
+    mutable stl_file stl;
     bool repaired;
     
 private: