From a06b6716eaab6784fa09a839ac1a384f536cc33c Mon Sep 17 00:00:00 2001 From: Lukas Matena Date: Thu, 9 Aug 2018 16:35:28 +0200 Subject: First naive implementation of TriangleMesh convex hull calculation --- xs/src/libslic3r/TriangleMesh.cpp | 48 +++++++++++++++++++++++++++++++++++++++ xs/src/libslic3r/TriangleMesh.hpp | 1 + 2 files changed, 49 insertions(+) (limited to 'xs/src/libslic3r') diff --git a/xs/src/libslic3r/TriangleMesh.cpp b/xs/src/libslic3r/TriangleMesh.cpp index 45e4b6f5d..197b4d488 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 #include #include @@ -10,6 +13,7 @@ #include #include #include +#include #include @@ -597,6 +601,50 @@ TriangleMesh::bounding_box() const return bb; } + +TriangleMesh TriangleMesh::convex_hull3d() const +{ + // qhull's realT is assumed to be a typedef for float - let's better check it first: + static_assert(std::is_same::value, "Internal type realT in the qhull library must be float!"); + + // Helper struct for qhull: + struct PointForQHull{ + PointForQHull(float x_p, float y_p, float z_p) : x(x_p), y(y_p), z(z_p) {} + float x,y,z; + }; + std::vector input_verts; + + // 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 j=0;j<3;++j) + input_verts.emplace_back(PointForQHull(facet_ptr->vertex[j].x, facet_ptr->vertex[j].y, facet_ptr->vertex[j].z)); + facet_ptr+=1; + } + + // The qhull call: + orgQhull::Qhull qhull; + qhull.disableOutputStream(); // we want qhull to be quiet + qhull.runQhull("", 3, input_verts.size(), (const realT*)(input_verts.data()), "Qt" ); + + // Let's collect results: + Pointf3s vertices; + std::vector facets; + auto facet_list = qhull.facetList().toStdVector(); + for (const orgQhull::QhullFacet& facet : facet_list) { // iterate through facets + for (unsigned char i=0; i<3; ++i) { // iterate through facet's vertices + orgQhull::QhullPoint p = (facet.vertices())[i].point(); + const float* coords = p.coordinates(); + Pointf3 vert((float)coords[0], (float)coords[1], (float)coords[2]); + vertices.emplace_back(vert); + } + facets.emplace_back(Point3(vertices.size()-3, vertices.size()-2, vertices.size()-1)); + } + TriangleMesh output_mesh(vertices, facets); + output_mesh.repair(); + return output_mesh; +} + void TriangleMesh::require_shared_vertices() { diff --git a/xs/src/libslic3r/TriangleMesh.hpp b/xs/src/libslic3r/TriangleMesh.hpp index c700784a5..14fdba6c3 100644 --- a/xs/src/libslic3r/TriangleMesh.hpp +++ b/xs/src/libslic3r/TriangleMesh.hpp @@ -55,6 +55,7 @@ public: ExPolygons horizontal_projection() const; Polygon convex_hull(); BoundingBoxf3 bounding_box() const; + TriangleMesh convex_hull3d() const; void reset_repair_stats(); bool needed_repair() const; size_t facets_count() const; -- cgit v1.2.3 From 6742735596eb342d8166ce00aa370cf0fba15c1f Mon Sep 17 00:00:00 2001 From: Enrico Turri Date: Mon, 13 Aug 2018 16:16:37 +0200 Subject: Better fix for minimum z of object to lay on the bed after rotations --- xs/src/libslic3r/Model.cpp | 11 +---------- 1 file changed, 1 insertion(+), 10 deletions(-) (limited to 'xs/src/libslic3r') diff --git a/xs/src/libslic3r/Model.cpp b/xs/src/libslic3r/Model.cpp index bceeea258..f9936537f 100644 --- a/xs/src/libslic3r/Model.cpp +++ b/xs/src/libslic3r/Model.cpp @@ -771,21 +771,12 @@ void ModelObject::scale(const Pointf3 &versor) void ModelObject::rotate(float angle, const Axis &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); } - 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(); -- cgit v1.2.3 From 4d98d321996de6e6d036403c319b6ef044144dcd Mon Sep 17 00:00:00 2001 From: Enrico Turri Date: Wed, 15 Aug 2018 12:50:06 +0200 Subject: Use of bounding box of rotated 3D convex hull for out of print volume detection --- xs/src/libslic3r/Format/3mf.cpp | 1 + xs/src/libslic3r/Format/AMF.cpp | 1 + xs/src/libslic3r/Model.cpp | 129 +++++++++++------------------------- xs/src/libslic3r/Model.hpp | 36 +++++++---- xs/src/libslic3r/TriangleMesh.cpp | 133 ++++++++++++++++++++++++++++++++++++++ xs/src/libslic3r/TriangleMesh.hpp | 6 +- 6 files changed, 202 insertions(+), 104 deletions(-) (limited to 'xs/src/libslic3r') 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/Model.cpp b/xs/src/libslic3r/Model.cpp index f9936537f..23d447748 100644 --- a/xs/src/libslic3r/Model.cpp +++ b/xs/src/libslic3r/Model.cpp @@ -17,6 +17,11 @@ #include "SVG.hpp" #include +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,15 +704,22 @@ 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(); @@ -774,6 +730,7 @@ void ModelObject::rotate(float angle, const Axis &axis) for (ModelVolume *v : this->volumes) { v->mesh.rotate(angle, axis); + v->m_convex_hull.rotate(angle, axis); } center_around_origin(); @@ -790,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); @@ -799,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(); } @@ -904,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); - - for (int f = 0; f < vol->mesh.stl.stats.number_of_facets; ++f) - { - const stl_facet& facet = vol->mesh.stl.facet_start[f]; + std::vector world_mat(UNIT_MATRIX, std::end(UNIT_MATRIX)); + Eigen::Transform m = Eigen::Transform::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 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; @@ -1025,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..23af9fb1c 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; @@ -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/TriangleMesh.cpp b/xs/src/libslic3r/TriangleMesh.cpp index 45e4b6f5d..fc72a45aa 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 #include #include @@ -15,6 +18,8 @@ #include +#include + #if 0 #define DEBUG #define _DEBUG @@ -597,6 +602,134 @@ TriangleMesh::bounding_box() const return bb; } +BoundingBoxf3 TriangleMesh::transformed_bounding_box(const std::vector& 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 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 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 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(); + return output_mesh; +} + void TriangleMesh::require_shared_vertices() { diff --git a/xs/src/libslic3r/TriangleMesh.hpp b/xs/src/libslic3r/TriangleMesh.hpp index c700784a5..6ab52efe2 100644 --- a/xs/src/libslic3r/TriangleMesh.hpp +++ b/xs/src/libslic3r/TriangleMesh.hpp @@ -55,6 +55,10 @@ public: ExPolygons horizontal_projection() 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& 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 +70,7 @@ public: // Count disconnected triangle patches. size_t number_of_patches() const; - stl_file stl; + mutable stl_file stl; bool repaired; private: -- cgit v1.2.3 From 48b9793d3d2f5a9b4163f4927563ffd4266e4f12 Mon Sep 17 00:00:00 2001 From: Lukas Matena Date: Fri, 17 Aug 2018 15:20:35 +0200 Subject: Templated convex_hull function in Geometry.cpp --- xs/src/libslic3r/Geometry.cpp | 53 +++++++++++++++++++++++++++---------------- xs/src/libslic3r/Geometry.hpp | 2 ++ xs/src/libslic3r/Point.cpp | 6 +++++ xs/src/libslic3r/Point.hpp | 1 + 4 files changed, 43 insertions(+), 19 deletions(-) (limited to 'xs/src/libslic3r') 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 + 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 +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 &retval, Point start_near); void chained_path(const Points &points, std::vector &retval); template void chained_path_items(Points &points, T &items, T &retval); 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); -- cgit v1.2.3 From f9efcc36b64d631bfece0a207fbb74388c3bb514 Mon Sep 17 00:00:00 2001 From: Lukas Matena Date: Fri, 17 Aug 2018 15:40:47 +0200 Subject: Lay flat gizmo improvements - merge adjacent faces, compute and cache convex hull for entire ModelObject, refresh when moved, etc. --- xs/src/libslic3r/TriangleMesh.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'xs/src/libslic3r') diff --git a/xs/src/libslic3r/TriangleMesh.cpp b/xs/src/libslic3r/TriangleMesh.cpp index 957515db3..19dcc6a07 100644 --- a/xs/src/libslic3r/TriangleMesh.cpp +++ b/xs/src/libslic3r/TriangleMesh.cpp @@ -728,6 +728,7 @@ TriangleMesh TriangleMesh::convex_hull_3d() const TriangleMesh output_mesh(det_vertices, facets); output_mesh.repair(); + output_mesh.require_shared_vertices(); return output_mesh; } -- cgit v1.2.3 From b0dd328fdec094cd072ece2cbfff87dcf07d51c2 Mon Sep 17 00:00:00 2001 From: Lukas Matena Date: Mon, 20 Aug 2018 11:27:25 +0200 Subject: Lay flat - icons and invalidation improvement --- xs/src/libslic3r/TriangleMesh.cpp | 5 +++++ xs/src/libslic3r/TriangleMesh.hpp | 1 + 2 files changed, 6 insertions(+) (limited to 'xs/src/libslic3r') diff --git a/xs/src/libslic3r/TriangleMesh.cpp b/xs/src/libslic3r/TriangleMesh.cpp index 19dcc6a07..008679e6c 100644 --- a/xs/src/libslic3r/TriangleMesh.cpp +++ b/xs/src/libslic3r/TriangleMesh.cpp @@ -732,6 +732,11 @@ TriangleMesh TriangleMesh::convex_hull_3d() const 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 6ab52efe2..be151f062 100644 --- a/xs/src/libslic3r/TriangleMesh.hpp +++ b/xs/src/libslic3r/TriangleMesh.hpp @@ -53,6 +53,7 @@ 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 -- cgit v1.2.3 From 86b67bbd4282016fbbbbc94306e37eada582daf1 Mon Sep 17 00:00:00 2001 From: Lukas Matena Date: Tue, 21 Aug 2018 15:40:11 +0200 Subject: Lay flat - rotation is now done in one go directly about the necessary axis --- xs/src/libslic3r/Model.cpp | 2 +- xs/src/libslic3r/Model.hpp | 2 +- xs/src/libslic3r/TriangleMesh.cpp | 11 +++++++++++ xs/src/libslic3r/TriangleMesh.hpp | 1 + 4 files changed, 14 insertions(+), 2 deletions(-) (limited to 'xs/src/libslic3r') diff --git a/xs/src/libslic3r/Model.cpp b/xs/src/libslic3r/Model.cpp index 23d447748..09b515c2f 100644 --- a/xs/src/libslic3r/Model.cpp +++ b/xs/src/libslic3r/Model.cpp @@ -725,7 +725,7 @@ void ModelObject::scale(const Pointf3 &versor) this->invalidate_bounding_box(); } -void ModelObject::rotate(float angle, const Axis &axis) +void ModelObject::rotate(float angle, const Pointf3& axis) { for (ModelVolume *v : this->volumes) { diff --git a/xs/src/libslic3r/Model.hpp b/xs/src/libslic3r/Model.hpp index 23af9fb1c..dadd515de 100644 --- a/xs/src/libslic3r/Model.hpp +++ b/xs/src/libslic3r/Model.hpp @@ -120,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; diff --git a/xs/src/libslic3r/TriangleMesh.cpp b/xs/src/libslic3r/TriangleMesh.cpp index 008679e6c..4c45680b6 100644 --- a/xs/src/libslic3r/TriangleMesh.cpp +++ b/xs/src/libslic3r/TriangleMesh.cpp @@ -324,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 m = Eigen::Transform::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) diff --git a/xs/src/libslic3r/TriangleMesh.hpp b/xs/src/libslic3r/TriangleMesh.hpp index be151f062..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); -- cgit v1.2.3