From 3a81e6bee420196698e3f1409a8a7318dd35965b Mon Sep 17 00:00:00 2001 From: bubnikv Date: Fri, 30 Sep 2016 15:23:18 +0200 Subject: Bugfix of bottom bridges. If close regions shall be closed by bridges, these regions are grown to anchor the bridge lines to the bottom surface. The grown regions may overlap. In that case the regions are now merged before the bridging direction is calculated for the merged region. --- xs/src/libslic3r/BoundingBox.cpp | 17 ++++ xs/src/libslic3r/BoundingBox.hpp | 2 + xs/src/libslic3r/ExPolygon.cpp | 41 +++++++++ xs/src/libslic3r/ExPolygon.hpp | 11 +++ xs/src/libslic3r/LayerRegion.cpp | 148 +++++++++++++++++++++++++++++++-- xs/src/libslic3r/Polyline.cpp | 17 ++++ xs/src/libslic3r/Polyline.hpp | 3 + xs/src/libslic3r/SVG.cpp | 2 +- xs/src/libslic3r/SurfaceCollection.cpp | 27 ++++++ xs/src/libslic3r/SurfaceCollection.hpp | 3 + xs/src/libslic3r/libslic3r.h | 2 +- xs/xsp/BoundingBox.xsp | 2 + 12 files changed, 265 insertions(+), 10 deletions(-) diff --git a/xs/src/libslic3r/BoundingBox.cpp b/xs/src/libslic3r/BoundingBox.cpp index c16d92f4e..2b3f00df1 100644 --- a/xs/src/libslic3r/BoundingBox.cpp +++ b/xs/src/libslic3r/BoundingBox.cpp @@ -259,4 +259,21 @@ BoundingBox3Base::center() const } template Pointf3 BoundingBox3Base::center() const; +template bool +BoundingBoxBase::contains(const PointClass &point) const +{ + return point.x >= this->min.x && point.x <= this->max.x + && point.y >= this->min.y && point.y <= this->max.y; +} +template bool BoundingBoxBase::contains(const Point &point) const; +template bool BoundingBoxBase::contains(const Pointf &point) const; + +template bool +BoundingBoxBase::overlap(const BoundingBoxBase &other) const +{ + return this->contains(other.min) || other.contains(this->min); +} +template bool BoundingBoxBase::overlap(const BoundingBoxBase &point) const; +template bool BoundingBoxBase::overlap(const BoundingBoxBase &point) const; + } diff --git a/xs/src/libslic3r/BoundingBox.hpp b/xs/src/libslic3r/BoundingBox.hpp index b4f101976..7746515cb 100644 --- a/xs/src/libslic3r/BoundingBox.hpp +++ b/xs/src/libslic3r/BoundingBox.hpp @@ -32,6 +32,8 @@ class BoundingBoxBase void translate(coordf_t x, coordf_t y); void offset(coordf_t delta); PointClass center() const; + bool contains(const PointClass &point) const; + bool overlap(const BoundingBoxBase &other) const; }; template diff --git a/xs/src/libslic3r/ExPolygon.cpp b/xs/src/libslic3r/ExPolygon.cpp index 2220772b8..76a48b46a 100644 --- a/xs/src/libslic3r/ExPolygon.cpp +++ b/xs/src/libslic3r/ExPolygon.cpp @@ -4,6 +4,7 @@ #include "Polygon.hpp" #include "Line.hpp" #include "ClipperUtils.hpp" +#include "SVG.hpp" #include "polypartition.h" #include "poly2tri/poly2tri.h" #include @@ -34,6 +35,17 @@ ExPolygon::operator Polygons() const return polygons; } +ExPolygon::operator Polylines() const +{ + Polylines polylines; + polylines.reserve(this->holes.size() + 1); + polylines.push_back((Polyline)this->contour); + for (Polygons::const_iterator it = this->holes.begin(); it != this->holes.end(); ++it) { + polylines.push_back((Polyline)*it); + } + return polylines; +} + void ExPolygon::scale(double factor) { @@ -104,6 +116,25 @@ ExPolygon::contains(const Polyline &polyline) const return pl_out.empty(); } +bool +ExPolygon::contains(const Polylines &polylines) const +{ + #if 0 + BoundingBox bbox = get_extents(polylines); + bbox.merge(get_extents(*this)); + SVG svg("out\\ExPolygon_contains.svg", bbox); + svg.draw(*this); + svg.draw_outline(*this); + svg.draw(polylines, "blue"); + #endif + Polylines pl_out; + diff(polylines, *this, &pl_out); + #if 0 + svg.draw(pl_out, "red"); + #endif + return pl_out.empty(); +} + bool ExPolygon::contains(const Point &point) const { @@ -131,6 +162,16 @@ ExPolygon::has_boundary_point(const Point &point) const return false; } +bool +ExPolygon::overlaps(const ExPolygon &other) const +{ + Polylines pl_out; + intersection((Polylines)other, *this, &pl_out); + if (! pl_out.empty()) + return true; + return ! other.contour.points.empty() && this->contains_b(other.contour.points.front()); +} + void ExPolygon::simplify_p(double tolerance, Polygons* polygons) const { diff --git a/xs/src/libslic3r/ExPolygon.hpp b/xs/src/libslic3r/ExPolygon.hpp index ada37cecc..f283822da 100644 --- a/xs/src/libslic3r/ExPolygon.hpp +++ b/xs/src/libslic3r/ExPolygon.hpp @@ -18,17 +18,28 @@ class ExPolygon Polygons holes; operator Points() const; operator Polygons() const; + operator Polylines() const; + void clear() { contour.points.clear(); holes.clear(); } void scale(double factor); void translate(double x, double y); void rotate(double angle); void rotate(double angle, const Point ¢er); double area() const; bool is_valid() const; + + // Contains the line / polyline / polylines etc COMPLETELY. bool contains(const Line &line) const; bool contains(const Polyline &polyline) const; + bool contains(const Polylines &polylines) const; bool contains(const Point &point) const; bool contains_b(const Point &point) const; bool has_boundary_point(const Point &point) const; + + // Does this expolygon overlap another expolygon? + // Either the ExPolygons intersect, or one is fully inside the other, + // and it is not inside a hole of the other expolygon. + bool overlap(const ExPolygon &other) const; + void simplify_p(double tolerance, Polygons* polygons) const; Polygons simplify_p(double tolerance) const; ExPolygons simplify(double tolerance) const; diff --git a/xs/src/libslic3r/LayerRegion.cpp b/xs/src/libslic3r/LayerRegion.cpp index fe35fd04b..64482145e 100644 --- a/xs/src/libslic3r/LayerRegion.cpp +++ b/xs/src/libslic3r/LayerRegion.cpp @@ -4,6 +4,7 @@ #include "PerimeterGenerator.hpp" #include "Print.hpp" #include "Surface.hpp" +#include "BoundingBox.hpp" #include "SVG.hpp" #include @@ -103,11 +104,12 @@ LayerRegion::process_external_surfaces(const Layer* lower_layer) export_region_fill_surfaces_to_svg_debug("3_process_external_surfaces-initial"); #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */ +#if 0 SurfaceCollection bottom; // For all stBottom && stBottomBridge surfaces: for (Surfaces::const_iterator surface = surfaces.begin(); surface != surfaces.end(); ++surface) { if (!surface->is_bottom()) continue; - // Grown by 3mm. + ExPolygons grown = offset_ex(surface->expolygon, +margin); /* detect bridge direction before merging grown surfaces otherwise adjacent bridges @@ -119,22 +121,19 @@ LayerRegion::process_external_surfaces(const Layer* lower_layer) BridgeDetector bd( surface->expolygon, lower_layer->slices, - // Using extrusion width of an infill. this->flow(frInfill, this->layer()->height, true).scaled_width() ); #ifdef SLIC3R_DEBUG - printf("Processing bridge at layer %zu:\n", this->layer()->id()); + printf("Processing bridge at layer %zu:\n", this->layer()->id(); #endif if (bd.detect_angle()) { angle = bd.angle; - // Are supports enabled? + if (this->layer()->object()->config.support_material) { Polygons coverage = bd.coverage(); - // Bridged polygons do not require supports. this->bridged.insert(this->bridged.end(), coverage.begin(), coverage.end()); - // Unsupported edges of the infill. this->unsupported_bridge_edges.append(bd.unsupported_edges()); } } @@ -147,7 +146,140 @@ LayerRegion::process_external_surfaces(const Layer* lower_layer) bottom.surfaces.push_back(s); } } - +#else + // 1) Collect bottom and bridge surfaces, each of them grown by a fixed 3mm offset + // for better anchoring. + SurfaceCollection bottom; + SurfaceCollection bridges; + std::vector bridge_bboxes; + // For all stBottom && stBottomBridge surfaces: + for (Surfaces::const_iterator surface = surfaces.begin(); surface != surfaces.end(); ++surface) { + if (!surface->is_bottom()) continue; + // Grown by 3mm. + ExPolygons grown = offset_ex(surface->expolygon, +margin); + for (ExPolygons::const_iterator it = grown.begin(); it != grown.end(); ++it) { + Surface s = *surface; + s.expolygon = *it; + if (surface->surface_type == stBottomBridge) { + bridges.surfaces.push_back(s); + bridge_bboxes.push_back(get_extents(s)); + } else + bottom.surfaces.push_back(s); + } + } + +#if 0 + { + char path[2048]; + static int iRun = 0; + sprintf(path, "out\\bridges-before-grouping-%d.svg", iRun ++); + bridges.export_to_svg(path, true); + } +#endif + + // 2) Group the bridge surfaces by overlaps. + std::vector bridge_group(bridges.surfaces.size(), (size_t)-1); + size_t n_groups = 0; + for (size_t i = 0; i < bridges.surfaces.size(); ++ i) { + // A grup id for this bridge. + size_t group_id = (bridge_group[i] == -1) ? (n_groups ++) : bridge_group[i]; + bridge_group[i] = group_id; + // For all possibly overlaping bridges: + for (size_t j = i + 1; j < bridges.surfaces.size(); ++ j) { + if (! bridge_bboxes[i].overlap(bridge_bboxes[j])) + continue; + if (! bridges.surfaces[i].expolygon.overlaps(bridges.surfaces[j].expolygon)) + continue; + // The two bridge regions intersect. Give them the same group id. + if (bridge_group[j] != -1) { + // The j'th bridge has been merged with some other bridge before. + size_t group_id_new = bridge_group[j]; + for (size_t k = 0; k < j; ++ k) + if (bridge_group[k] == group_id) + bridge_group[k] = group_id_new; + group_id = group_id_new; + } + bridge_group[j] = group_id; + } + } + + // 3) Merge the groups with the same group id. + { + SurfaceCollection bridges_merged; + bridges_merged.surfaces.reserve(n_groups); + for (size_t group_id = 0; group_id < n_groups; ++ group_id) { + size_t n_bridges_merged = 0; + size_t idx_last = (size_t)-1; + for (size_t i = 0; i < bridges.surfaces.size(); ++ i) { + if (bridge_group[i] == group_id) { + ++ n_bridges_merged; + idx_last = i; + } + } + if (n_bridges_merged == 1) + bridges_merged.surfaces.push_back(bridges.surfaces[idx_last]); + else if (n_bridges_merged > 1) { + Slic3r::Polygons polygons; + for (size_t i = 0; i < bridges.surfaces.size(); ++ i) { + if (bridge_group[i] != group_id) + continue; + const Surface &surface = bridges.surfaces[i]; + polygons.push_back(surface.expolygon.contour); + for (size_t j = 0; j < surface.expolygon.holes.size(); ++ j) + polygons.push_back(surface.expolygon.holes[j]); + } + ExPolygons expp; + // without safety offset, artifacts are generated (GH #2494) + union_(polygons, &expp, true); + Surface &surface0 = bridges.surfaces[idx_last]; + surface0.expolygon.clear(); + for (size_t i = 0; i < expp.size(); ++ i) { + surface0.expolygon = expp[i]; + bridges_merged.surfaces.push_back(surface0); + } + } + } + std::swap(bridges_merged, bridges); + } + +#if 0 + { + char path[2048]; + static int iRun = 0; + sprintf(path, "out\\bridges-after-grouping-%d.svg", iRun ++); + bridges.export_to_svg(path, true); + } +#endif + + // 4) Detect bridge directions. + if (lower_layer != NULL) { + for (size_t i = 0; i < bridges.surfaces.size(); ++ i) { + Surface &surface = bridges.surfaces[i]; + /* detect bridge direction before merging grown surfaces otherwise adjacent bridges + would get merged into a single one while they need different directions + also, supply the original expolygon instead of the grown one, because in case + of very thin (but still working) anchors, the grown expolygon would go beyond them */ + BridgeDetector bd( + surface.expolygon, + lower_layer->slices, + this->flow(frInfill, this->layer()->height, true).scaled_width() + ); + #ifdef SLIC3R_DEBUG + printf("Processing bridge at layer %zu:\n", this->layer()->id(); + #endif + if (bd.detect_angle()) { + surface.bridge_angle = bd.angle; + if (this->layer()->object()->config.support_material) { + Polygons coverage = bd.coverage(); + this->bridged.insert(this->bridged.end(), coverage.begin(), coverage.end()); + this->unsupported_bridge_edges.append(bd.unsupported_edges()); + } + } + } + } + bottom.surfaces.insert(bottom.surfaces.end(), bridges.surfaces.begin(), bridges.surfaces.end()); +#endif + SurfaceCollection top; for (Surfaces::const_iterator surface = surfaces.begin(); surface != surfaces.end(); ++surface) { if (surface->surface_type != stTop) continue; @@ -204,7 +336,7 @@ LayerRegion::process_external_surfaces(const Layer* lower_layer) Surface s = *g->front(); s.expolygon = *ex; new_surfaces.surfaces.push_back(s); - } + } } } diff --git a/xs/src/libslic3r/Polyline.cpp b/xs/src/libslic3r/Polyline.cpp index baa2bbf5d..08717b57c 100644 --- a/xs/src/libslic3r/Polyline.cpp +++ b/xs/src/libslic3r/Polyline.cpp @@ -1,3 +1,4 @@ +#include "BoundingBox.hpp" #include "Polyline.hpp" #include "ExPolygon.hpp" #include "ExPolygonCollection.hpp" @@ -220,6 +221,22 @@ Polyline::wkt() const return wkt.str(); } +BoundingBox get_extents(const Polyline &polyline) +{ + return polyline.bounding_box(); +} + +BoundingBox get_extents(const Polylines &polylines) +{ + BoundingBox bb; + if (! polylines.empty()) { + bb = polylines.front().bounding_box(); + for (size_t i = 1; i < polylines.size(); ++ i) + bb.merge(polylines[i]); + } + return bb; +} + ThickLines ThickPolyline::thicklines() const { diff --git a/xs/src/libslic3r/Polyline.hpp b/xs/src/libslic3r/Polyline.hpp index 4d6673f2c..dd2818199 100644 --- a/xs/src/libslic3r/Polyline.hpp +++ b/xs/src/libslic3r/Polyline.hpp @@ -33,6 +33,9 @@ class Polyline : public MultiPoint { std::string wkt() const; }; +extern BoundingBox get_extents(const Polyline &polyline); +extern BoundingBox get_extents(const Polylines &polylines); + class ThickPolyline : public Polyline { public: std::vector width; diff --git a/xs/src/libslic3r/SVG.cpp b/xs/src/libslic3r/SVG.cpp index d89602046..8b6d86622 100644 --- a/xs/src/libslic3r/SVG.cpp +++ b/xs/src/libslic3r/SVG.cpp @@ -182,7 +182,7 @@ void SVG::draw(const Polylines &polylines, std::string stroke, coordf_t stroke_width) { for (Polylines::const_iterator it = polylines.begin(); it != polylines.end(); ++it) - this->draw(*it, fill, stroke_width); + this->draw(*it, stroke, stroke_width); } void SVG::draw(const ThickLines &thicklines, const std::string &fill, const std::string &stroke, coordf_t stroke_width) diff --git a/xs/src/libslic3r/SurfaceCollection.cpp b/xs/src/libslic3r/SurfaceCollection.cpp index 5fbb913b1..c30998df4 100644 --- a/xs/src/libslic3r/SurfaceCollection.cpp +++ b/xs/src/libslic3r/SurfaceCollection.cpp @@ -1,4 +1,7 @@ #include "SurfaceCollection.hpp" +#include "BoundingBox.hpp" +#include "SVG.hpp" + #include namespace Slic3r { @@ -213,4 +216,28 @@ SurfaceCollection::append(const SurfaceType surfaceType, const Slic3r::ExPolygon this->surfaces.push_back(Slic3r::Surface(surfaceType, *it)); } +void SurfaceCollection::export_to_svg(const char *path, bool show_labels) +{ + BoundingBox bbox; + for (Surfaces::const_iterator surface = this->surfaces.begin(); surface != this->surfaces.end(); ++surface) + bbox.merge(get_extents(surface->expolygon)); + Point legend_size = export_surface_type_legend_to_svg_box_size(); + Point legend_pos(bbox.min.x, bbox.max.y); + bbox.merge(Point(std::max(bbox.min.x + legend_size.x, bbox.max.x), bbox.max.y + legend_size.y)); + + SVG svg(path, bbox); + const float transparency = 0.5f; + for (Surfaces::const_iterator surface = this->surfaces.begin(); surface != this->surfaces.end(); ++surface) { + svg.draw(surface->expolygon, surface_type_to_color_name(surface->surface_type), transparency); + if (show_labels) { + int idx = int(surface - this->surfaces.cbegin()); + char label[64]; + sprintf(label, "%d", idx); + svg.draw_text(surface->expolygon.contour.points.front(), label, "black"); + } + } + export_surface_type_legend_to_svg(svg, legend_pos); + svg.Close(); +} + } diff --git a/xs/src/libslic3r/SurfaceCollection.hpp b/xs/src/libslic3r/SurfaceCollection.hpp index 07d0b0029..43835841d 100644 --- a/xs/src/libslic3r/SurfaceCollection.hpp +++ b/xs/src/libslic3r/SurfaceCollection.hpp @@ -30,6 +30,9 @@ class SurfaceCollection void filter_by_type(SurfaceType type, Polygons* polygons); void append(const SurfaceCollection &coll); void append(const SurfaceType surfaceType, const Slic3r::ExPolygons &expoly); + + // For debugging purposes: + void export_to_svg(const char *path, bool show_labels); }; } diff --git a/xs/src/libslic3r/libslic3r.h b/xs/src/libslic3r/libslic3r.h index 431b6fb45..e92124536 100644 --- a/xs/src/libslic3r/libslic3r.h +++ b/xs/src/libslic3r/libslic3r.h @@ -63,6 +63,6 @@ void confess_at(const char *file, int line, const char *func, const char *pat, . #endif // Write slices as SVG images into out directory during the 2D processing of the slices. -#define SLIC3R_DEBUG_SLICE_PROCESSING +// #define SLIC3R_DEBUG_SLICE_PROCESSING #endif diff --git a/xs/xsp/BoundingBox.xsp b/xs/xsp/BoundingBox.xsp index 948042eaf..efb5dea3b 100644 --- a/xs/xsp/BoundingBox.xsp +++ b/xs/xsp/BoundingBox.xsp @@ -16,6 +16,8 @@ void scale(double factor); void translate(double x, double y); void offset(double delta); + bool contains_point(Point* point) %code{% RETVAL = THIS->contains(*point); %}; + bool overlap(BoundingBox* bbox) %code{% RETVAL = THIS->overlap(*bbox); %}; Clone polygon(); Clone size(); Clone center(); -- cgit v1.2.3