Arrange cache in ModeInstance and logical bed remembered.

9 files changed, 486 insertions, 410 deletions

diff --git a/src/libnest2d/include/libnest2d/libnest2d.hpp b/src/libnest2d/include/libnest2d/libnest2d.hpp
index a83a16ecf..11c032fae 100644
--- a/src/libnest2d/include/libnest2d/libnest2d.hpp
+++ b/src/libnest2d/include/libnest2d/libnest2d.hpp
@@ -127,25 +127,6 @@ public:
     inline _Item(TContour<RawShape>&& contour,
                  THolesContainer<RawShape>&& holes):
         sh_(sl::create<RawShape>(std::move(contour), std::move(holes))) {}
-
-//    template<class... Args>
-//    _Item(std::function<void(const _Item&, unsigned)> applyfn, Args &&... args):
-//        _Item(std::forward<Args>(args)...)
-//    {
-//        applyfn_ = std::move(applyfn);
-//    }
-
-    // Call the apply callback set in constructor. Within the callback, the
-    // original caller can apply the stored transformation to the original
-    // objects inteded for nesting. It might not be the shape handed over
-    // to _Item (e.g. arranging 3D shapes based on 2D silhouette or the
-    // client uses a simplified or processed polygon for nesting)
-    // This callback, if present, will be called for each item after the nesting
-    // is finished.
-//    inline void callApplyFunction(unsigned binidx) const
-//    {
-//        if (applyfn_) applyfn_(*this, binidx);
-//    }
     
     inline bool isFixed() const noexcept { return fixed_; }
     inline void markAsFixed(bool fixed = true) { fixed_ = fixed; }
@@ -881,34 +862,6 @@ public:
     {
         return selector_.getResult();
     }
-
-private:
-
-      
-    // This function will be used only if the iterators are pointing to
-    // a type compatible with the libnets2d::_Item template.
-    // This way we can use references to input elements as they will
-    // have to exist for the lifetime of this call.
-//    template<class It, class Key>
-//    inline ConvertibleOnly<It, void> _execute(It from, It to)
-//    {
-//        __execute(from, to);
-//    }
-    
-//    template<class It> inline void _execute(It from, It to)
-//    {
-//        auto infl = static_cast<Coord>(std::ceil(min_obj_distance_/2.0));
-//        if(infl > 0) std::for_each(from, to, [this](Item& item) {
-//            item.inflate(infl);
-//        });
-
-//        selector_.template packItems<PlacementStrategy>(
-//                    from, to, bin_, pconfig_);
-        
-//        if(min_obj_distance_ > 0) std::for_each(from, to, [](Item& item) {
-//            item.inflate(-infl);
-//        });
-//    }
 };
 
 }
diff --git a/src/libnest2d/include/libnest2d/selections/firstfit.hpp b/src/libnest2d/include/libnest2d/selections/firstfit.hpp
index 6a3e2e61b..74207f8cf 100644
--- a/src/libnest2d/include/libnest2d/selections/firstfit.hpp
+++ b/src/libnest2d/include/libnest2d/selections/firstfit.hpp
@@ -42,8 +42,13 @@ public:
         
         std::for_each(first, last, [this](Item& itm) {
             if(itm.isFixed()) {
-                if(packed_bins_.empty()) packed_bins_.emplace_back();
-                packed_bins_.front().emplace_back(itm);
+                if (itm.binId() < 0) itm.binId(0);
+                auto binidx = size_t(itm.binId());
+                
+                while(packed_bins_.size() <= binidx)
+                    packed_bins_.emplace_back();
+                
+                packed_bins_[binidx].emplace_back(itm);
             } else {
                 store_.emplace_back(itm);
             }
diff --git a/src/libslic3r/Arrange.cpp b/src/libslic3r/Arrange.cpp
index c49c9fb97..fd3573699 100644
--- a/src/libslic3r/Arrange.cpp
+++ b/src/libslic3r/Arrange.cpp
@@ -434,9 +434,7 @@ inline Circle to_lnCircle(const CircleBed& circ) {
 }
 
 // Get the type of bed geometry from a simple vector of points.
-BedShapeHint bedShape(const Polyline &bed) {
-    BedShapeHint ret;
-
+BedShapeHint::BedShapeHint(const Polyline &bed) {
     auto x = [](const Point& p) { return p(X); };
     auto y = [](const Point& p) { return p(Y); };
 
@@ -497,19 +495,16 @@ BedShapeHint bedShape(const Polyline &bed) {
     auto parea = poly_area(bed);
 
     if( (1.0 - parea/area(bb)) < 1e-3 ) {
-        ret.type = BedShapeType::BOX;
-        ret.shape.box = bb;
+        m_type = BedShapes::bsBox;
+        m_bed.box = bb;
     }
     else if(auto c = isCircle(bed)) {
-        ret.type = BedShapeType::CIRCLE;
-        ret.shape.circ = c;
+        m_type = BedShapes::bsCircle;
+        m_bed.circ = c;
     } else {
-        ret.type = BedShapeType::IRREGULAR;
-        ret.shape.polygon = bed;
+        m_type = BedShapes::bsIrregular;
+        m_bed.polygon = bed;
     }
-
-    // Determine the bed shape by hand
-    return ret;
 }
 
 template<class BinT> // Arrange for arbitrary bin type
@@ -588,6 +583,7 @@ void arrange(ArrangePolygons &             arrangables,
         outp.emplace_back(std::move(clpath));
         outp.back().rotation(rotation);
         outp.back().translation({offs.x(), offs.y()});
+        outp.back().binId(arrpoly.bed_idx);
     };
 
     for (ArrangePolygon &arrangeable : arrangables)
@@ -596,6 +592,8 @@ void arrange(ArrangePolygons &             arrangables,
     for (const ArrangePolygon &fixed: excludes)
         process_arrangeable(fixed, fixeditems);
     
+    for (Item &itm : fixeditems) itm.inflate(-2 * SCALED_EPSILON);
+    
     // Integer ceiling the min distance from the bed perimeters
     coord_t md = min_obj_dist - SCALED_EPSILON;
     md = (md % 2) ? md / 2 + 1 : md / 2;
@@ -603,39 +601,38 @@ void arrange(ArrangePolygons &             arrangables,
     auto &cfn = stopcondition;
     auto &pri = progressind;
     
-    switch (bedhint.type) {
-    case BedShapeType::BOX: {
+    switch (bedhint.get_type()) {
+    case bsBox: {
         // Create the arranger for the box shaped bed
-        BoundingBox bbb = bedhint.shape.box;
+        BoundingBox bbb = bedhint.get_box();
         bbb.min -= Point{md, md}, bbb.max += Point{md, md};
         Box binbb{{bbb.min(X), bbb.min(Y)}, {bbb.max(X), bbb.max(Y)}};
         
         _arrange(items, fixeditems, binbb, min_obj_dist, pri, cfn);
         break;
     }
-    case BedShapeType::CIRCLE: {
-        auto c  = bedhint.shape.circ;
-        auto cc = to_lnCircle(c);
+    case bsCircle: {
+        auto cc = to_lnCircle(bedhint.get_circle());
         
         _arrange(items, fixeditems, cc, min_obj_dist, pri, cfn);
         break;
     }
-    case BedShapeType::IRREGULAR: {
-        auto ctour = Slic3rMultiPoint_to_ClipperPath(bedhint.shape.polygon);
+    case bsIrregular: {
+        auto ctour = Slic3rMultiPoint_to_ClipperPath(bedhint.get_irregular());
         auto irrbed = sl::create<clppr::Polygon>(std::move(ctour));
-        BoundingBox polybb(bedhint.shape.polygon);
+        BoundingBox polybb(bedhint.get_irregular());
         
         _arrange(items, fixeditems, irrbed, min_obj_dist, pri, cfn);
         break;
     }
-    case BedShapeType::INFINITE: {
-        const InfiniteBed& nobin = bedhint.shape.infinite;
+    case bsInfinite: {
+        const InfiniteBed& nobin = bedhint.get_infinite();
         auto infbb = Box::infinite({nobin.center.x(), nobin.center.y()});
         
         _arrange(items, fixeditems, infbb, min_obj_dist, pri, cfn);
         break;
     }
-    case BedShapeType::UNKNOWN: {
+    case bsUnknown: {
         // We know nothing about the bed, let it be infinite and zero centered
         _arrange(items, fixeditems, Box::infinite(), min_obj_dist, pri, cfn);
         break;
diff --git a/src/libslic3r/Arrange.hpp b/src/libslic3r/Arrange.hpp
index bc23108cd..c705b612b 100644
--- a/src/libslic3r/Arrange.hpp
+++ b/src/libslic3r/Arrange.hpp
@@ -22,97 +22,152 @@ public:
     inline operator bool() { return !std::isnan(radius_); }
 };
 
-/// Representing an unbounded bin
+/// Representing an unbounded bed.
 struct InfiniteBed { Point center; };
 
 /// Types of print bed shapes.
-enum class BedShapeType {
-    BOX,
-    CIRCLE,
-    IRREGULAR,
-    INFINITE,
-    UNKNOWN
+enum BedShapes {
+    bsBox,
+    bsCircle,
+    bsIrregular,
+    bsInfinite,
+    bsUnknown
 };
 
-/// Info about the print bed for the arrange() function.
-struct BedShapeHint {
-    BedShapeType type = BedShapeType::INFINITE;
-    union BedShape_u {  // I know but who cares... TODO: use variant from cpp17?
+/// Info about the print bed for the arrange() function. This is a variant 
+/// holding one of the four shapes a bed can be.
+class BedShapeHint {
+    BedShapes m_type = BedShapes::bsInfinite;
+    
+    union BedShape_u {  // TODO: use variant from cpp17?
         CircleBed   circ;
         BoundingBox box;
         Polyline    polygon;
-        InfiniteBed infinite{};
+        InfiniteBed infbed{};
         ~BedShape_u() {}
         BedShape_u() {};
-    } shape;
+    } m_bed;
     
-    BedShapeHint() {};
+public:
+
+    BedShapeHint(){};
     
-    ~BedShapeHint() {
-        if (type == BedShapeType::IRREGULAR)
-            shape.polygon.Slic3r::Polyline::~Polyline();
-    };
+    /// Get a bed shape hint for arrange() from a naked Polyline.
+    explicit BedShapeHint(const Polyline &polyl);
+    explicit BedShapeHint(const BoundingBox &bb)
+    {
+        m_type = bsBox; m_bed.box = bb;
+    }
     
-    BedShapeHint(const BedShapeHint &cpy) {
-        *this = cpy;
+    explicit BedShapeHint(const CircleBed &c)
+    {
+        m_type = bsCircle; m_bed.circ = c;
     }
     
-    BedShapeHint& operator=(const BedShapeHint &cpy) {
-        type = cpy.type;
-        switch(type) {
-        case BedShapeType::BOX: shape.box = cpy.shape.box; break;
-        case BedShapeType::CIRCLE: shape.circ = cpy.shape.circ; break;
-        case BedShapeType::IRREGULAR: shape.polygon = cpy.shape.polygon; break;
-        case BedShapeType::INFINITE: shape.infinite = cpy.shape.infinite; break;
-        case BedShapeType::UNKNOWN: break;
+    explicit BedShapeHint(const InfiniteBed &ibed)
+    {
+        m_type = bsInfinite; m_bed.infbed = ibed;
+    }
+
+    ~BedShapeHint()
+    {
+        if (m_type == BedShapes::bsIrregular)
+            m_bed.polygon.Slic3r::Polyline::~Polyline();
+    };
+
+    BedShapeHint(const BedShapeHint &cpy) { *this = cpy; }
+    BedShapeHint(BedShapeHint &&cpy) { *this = std::move(cpy); }
+
+    BedShapeHint &operator=(const BedShapeHint &cpy)
+    {
+        m_type = cpy.m_type;
+        switch(m_type) {
+        case bsBox: m_bed.box = cpy.m_bed.box; break;
+        case bsCircle: m_bed.circ = cpy.m_bed.circ; break;
+        case bsIrregular: m_bed.polygon = cpy.m_bed.polygon; break;
+        case bsInfinite: m_bed.infbed = cpy.m_bed.infbed; break;
+        case bsUnknown: break;
         }
         
         return *this;
     }
-};
 
-/// Get a bed shape hint for arrange() from a naked Polyline.
-BedShapeHint bedShape(const Polyline& bed);
+    BedShapeHint& operator=(BedShapeHint &&cpy)
+    {
+        m_type = cpy.m_type;
+        switch(m_type) {
+        case bsBox: m_bed.box = std::move(cpy.m_bed.box); break;
+        case bsCircle: m_bed.circ = std::move(cpy.m_bed.circ); break;
+        case bsIrregular: m_bed.polygon = std::move(cpy.m_bed.polygon); break;
+        case bsInfinite: m_bed.infbed = std::move(cpy.m_bed.infbed); break;
+        case bsUnknown: break;
+        }
+        
+        return *this;
+    }
+    
+    BedShapes get_type() const { return m_type; }
 
-static const constexpr long UNARRANGED = -1;
+    const BoundingBox &get_box() const
+    {
+        assert(m_type == bsBox); return m_bed.box;
+    }
+    const CircleBed &get_circle() const
+    {
+        assert(m_type == bsCircle); return m_bed.circ;
+    }
+    const Polyline &get_irregular() const
+    {
+        assert(m_type == bsIrregular); return m_bed.polygon;
+    }
+    const InfiniteBed &get_infinite() const
+    {
+        assert(m_type == bsInfinite); return m_bed.infbed;
+    }
+};
 
+/// A logical bed representing an object not being arranged. Either the arrange
+/// has not yet succesfully run on this ArrangePolygon or it could not fit the
+/// object due to overly large size or invalid geometry.
+static const constexpr int UNARRANGED = -1;
+
+/// Input/Output structure for the arrange() function. The poly field will not
+/// be modified during arrangement. Instead, the translation and rotation fields
+/// will mark the needed transformation for the polygon to be in the arranged
+/// position. These can also be set to an initial offset and rotation.
+/// 
+/// The bed_idx field will indicate the logical bed into which the
+/// polygon belongs: UNARRANGED means no place for the polygon
+/// (also the initial state before arrange), 0..N means the index of the bed.
+/// Zero is the physical bed, larger than zero means a virtual bed.
 struct ArrangePolygon {
-    const ExPolygon poly;
-    Vec2crd   translation{0, 0};
-    double    rotation{0.0};
-    long      bed_idx{UNARRANGED};
+    const ExPolygon poly;           /// The 2D silhouette to be arranged
+    Vec2crd   translation{0, 0};    /// The translation of the poly
+    double    rotation{0.0};        /// The rotation of the poly in radians
+    int       bed_idx{UNARRANGED};  /// To which logical bed does poly belong...
     
-    ArrangePolygon(const ExPolygon &p, const Vec2crd &tr = {}, double rot = 0.0)
-        : poly{p}, translation{tr}, rotation{rot}
+    ArrangePolygon(ExPolygon p, const Vec2crd &tr = {}, double rot = 0.0)
+        : poly{std::move(p)}, translation{tr}, rotation{rot}
     {}
 };
 
 using ArrangePolygons = std::vector<ArrangePolygon>;
 
 /**
- * \brief Arranges the model objects on the screen.
+ * \brief Arranges the input polygons.
  *
- * The arrangement considers multiple bins (aka. print beds) for placing
- * all the items provided in the model argument. If the items don't fit on
- * one print bed, the remaining will be placed onto newly created print
- * beds. The first_bin_only parameter, if set to true, disables this
- * behavior and makes sure that only one print bed is filled and the
- * remaining items will be untouched. When set to false, the items which
- * could not fit onto the print bed will be placed next to the print bed so
- * the user should see a pile of items on the print bed and some other
- * piles outside the print area that can be dragged later onto the print
- * bed as a group.
+ * WARNING: Currently, only convex polygons are supported by the libnest2d 
+ * library which is used to do the arrangement. This might change in the future
+ * this is why the interface contains a general polygon capable to have holes.
  *
- * \param items Input which are object pointers implementing the
- * Arrangeable interface.
+ * \param items Input vector of ArrangePolygons. The transformation, rotation 
+ * and bin_idx fields will be changed after the call finished and can be used
+ * to apply the result on the input polygon.
  *
  * \param min_obj_distance The minimum distance which is allowed for any
  * pair of items on the print bed in any direction.
  *
- * \param bedhint Info about the shape and type of the
- * bed. remaining items which do not fit onto the print area next to the
- * print bed or leave them untouched (let the user arrange them by hand or
- * remove them).
+ * \param bedhint Info about the shape and type of the bed.
  *
  * \param progressind Progress indicator callback called when
  * an object gets packed. The unsigned argument is the number of items
@@ -127,7 +182,7 @@ void arrange(ArrangePolygons &             items,
              std::function<bool(void)>     stopcondition = nullptr);
 
 /// Same as the previous, only that it takes unmovable items as an
-/// additional argument.
+/// additional argument. Those will be considered as already arranged objects.
 void arrange(ArrangePolygons &             items,
              const ArrangePolygons &       excludes,
              coord_t                       min_obj_distance,
diff --git a/src/libslic3r/Model.cpp b/src/libslic3r/Model.cpp
index 966be4c88..5f296cc5f 100644
--- a/src/libslic3r/Model.cpp
+++ b/src/libslic3r/Model.cpp
@@ -372,35 +372,7 @@ static bool _arrange(const Pointfs &sizes, coordf_t dist, const BoundingBoxf* bb
 /*  arrange objects preserving their instance count
     but altering their instance positions */
 bool Model::arrange_objects(coordf_t dist, const BoundingBoxf* bb)
-{
-    // get the (transformed) size of each instance so that we take
-    // into account their different transformations when packing
-//    Pointfs instance_sizes;
-//    Pointfs instance_centers;
-//    for (const ModelObject *o : this->objects)
-//        for (size_t i = 0; i < o->instances.size(); ++ i) {
-//            // an accurate snug bounding box around the transformed mesh.
-//            BoundingBoxf3 bbox(o->instance_bounding_box(i, true));
-//            instance_sizes.emplace_back(to_2d(bbox.size()));
-//            instance_centers.emplace_back(to_2d(bbox.center()));
-//        }
-
-//    Pointfs positions;
-//    if (! _arrange(instance_sizes, dist, bb, positions))
-//        return false;
-
-//    size_t idx = 0;
-//    for (ModelObject *o : this->objects) {
-//        for (ModelInstance *i : o->instances) {
-//            Vec2d offset_xy = positions[idx] - instance_centers[idx];
-//            i->set_offset(Vec3d(offset_xy(0), offset_xy(1), i->get_offset(Z)));
-//            ++idx;
-//        }
-//        o->invalidate_bounding_box();
-//    }
-    
-//    return true;
-    
+{    
     size_t count = 0;
     for (auto obj : objects) count += obj->instances.size();
     
@@ -414,29 +386,23 @@ bool Model::arrange_objects(coordf_t dist, const BoundingBoxf* bb)
             instances.emplace_back(minst);
         }
     
-    
     arrangement::BedShapeHint bedhint;
-    
-    if (bb) {
-        bedhint.type = arrangement::BedShapeType::BOX;
-        bedhint.shape.box = BoundingBox(scaled(bb->min), scaled(bb->max));
-    }
-    
+
+    if (bb)
+        bedhint = arrangement::BedShapeHint(
+            BoundingBox(scaled(bb->min), scaled(bb->max)));
+
     arrangement::arrange(input, scaled(dist), bedhint);
     
     bool ret = true;
     
     for(size_t i = 0; i < input.size(); ++i) {
-        auto inst = instances[i];
-        inst->set_rotation(Z, input[i].rotation);
-        auto tr = unscaled<double>(input[i].translation);
-        inst->set_offset(X, tr.x());
-        inst->set_offset(Y, tr.y());
-        
-        if (input[i].bed_idx != 0) ret = false; // no logical beds are allowed
+        if (input[i].bed_idx == 0) { // no logical beds are allowed
+            instances[i]->apply_arrange_result(input[i].translation,
+                                               input[i].rotation);
+        } else ret = false;
     }
     
-    
     return ret;
 }
 
@@ -1842,28 +1808,37 @@ void ModelInstance::transform_polygon(Polygon* polygon) const
 arrangement::ArrangePolygon ModelInstance::get_arrange_polygon() const
 {
     static const double SIMPLIFY_TOLERANCE_MM = 0.1;
+    
+    if (!m_arrange_cache.valid) {
+        Vec3d rotation = get_rotation();
+        rotation.z()   = 0.;
+        Transform3d trafo_instance =
+            Geometry::assemble_transform(Vec3d::Zero(), rotation,
+                                         get_scaling_factor(), get_mirror());
+    
+        Polygon p = get_object()->convex_hull_2d(trafo_instance);
+    
+        assert(!p.points.empty());
+    
+        // this may happen for malformed models, see:
+        // https://github.com/prusa3d/PrusaSlicer/issues/2209
+        if (p.points.empty()) return {{}};
+    
+        Polygons pp{p};
+        pp = p.simplify(scaled<double>(SIMPLIFY_TOLERANCE_MM));
+        if (!pp.empty()) p = pp.front();
+        m_arrange_cache.poly.contour = std::move(p);
+        m_arrange_cache.valid = true;
+    }
 
-    Vec3d rotation = get_rotation();
-    rotation.z()   = 0.;
-    Transform3d trafo_instance =
-        Geometry::assemble_transform(Vec3d::Zero(), rotation,
-                                     get_scaling_factor(), get_mirror());
-
-    Polygon p = get_object()->convex_hull_2d(trafo_instance);
-
-    assert(!p.points.empty());
-
-    // this may happen for malformed models, see:
-    // https://github.com/prusa3d/PrusaSlicer/issues/2209
-    if (p.points.empty()) return {{}};
-
-    Polygons pp{p};
-    pp = p.simplify(scaled<double>(SIMPLIFY_TOLERANCE_MM));
-    if (!pp.empty()) p = pp.front();
+    arrangement::ArrangePolygon ret{m_arrange_cache.poly,
+                                    Vec2crd{scaled(get_offset(X)),
+                                            scaled(get_offset(Y))},
+                                    get_rotation(Z)};
     
-    ExPolygon ep; ep.contour = std::move(p);
+    ret.bed_idx = m_arrange_cache.bed_idx;
     
-    return {ep, Vec2crd{scaled(get_offset(X)), scaled(get_offset(Y))}, get_rotation(Z)};
+    return ret;
 }
 
 // Test whether the two models contain the same number of ModelObjects with the same set of IDs
diff --git a/src/libslic3r/Model.hpp b/src/libslic3r/Model.hpp
index 2fd696d14..7ce790c7c 100644
--- a/src/libslic3r/Model.hpp
+++ b/src/libslic3r/Model.hpp
@@ -512,7 +512,7 @@ public:
     ModelObject* get_object() const { return this->object; }
 
     const Geometry::Transformation& get_transformation() const { return m_transformation; }
-    void set_transformation(const Geometry::Transformation& transformation) { m_transformation = transformation; }
+    void set_transformation(const Geometry::Transformation& transformation) { m_transformation = transformation; m_arrange_cache.valid = false; }
 
     const Vec3d& get_offset() const { return m_transformation.get_offset(); }
     double get_offset(Axis axis) const { return m_transformation.get_offset(axis); }
@@ -523,21 +523,21 @@ public:
     const Vec3d& get_rotation() const { return m_transformation.get_rotation(); }
     double get_rotation(Axis axis) const { return m_transformation.get_rotation(axis); }
 
-    void set_rotation(const Vec3d& rotation) { m_transformation.set_rotation(rotation); }
-    void set_rotation(Axis axis, double rotation) { m_transformation.set_rotation(axis, rotation); }
+    void set_rotation(const Vec3d& rotation) { m_transformation.set_rotation(rotation); m_arrange_cache.valid = false; }
+    void set_rotation(Axis axis, double rotation) { m_transformation.set_rotation(axis, rotation); if (axis != Z) m_arrange_cache.valid = false; }
 
     const Vec3d& get_scaling_factor() const { return m_transformation.get_scaling_factor(); }
     double get_scaling_factor(Axis axis) const { return m_transformation.get_scaling_factor(axis); }
 
-    void set_scaling_factor(const Vec3d& scaling_factor) { m_transformation.set_scaling_factor(scaling_factor); }
-    void set_scaling_factor(Axis axis, double scaling_factor) { m_transformation.set_scaling_factor(axis, scaling_factor); }
+    void set_scaling_factor(const Vec3d& scaling_factor) { m_transformation.set_scaling_factor(scaling_factor); m_arrange_cache.valid = false; }
+    void set_scaling_factor(Axis axis, double scaling_factor) { m_transformation.set_scaling_factor(axis, scaling_factor); m_arrange_cache.valid = false; }
 
     const Vec3d& get_mirror() const { return m_transformation.get_mirror(); }
     double get_mirror(Axis axis) const { return m_transformation.get_mirror(axis); }
 	bool is_left_handed() const { return m_transformation.is_left_handed(); }
-
-    void set_mirror(const Vec3d& mirror) { m_transformation.set_mirror(mirror); }
-    void set_mirror(Axis axis, double mirror) { m_transformation.set_mirror(axis, mirror); }
+    
+    void set_mirror(const Vec3d& mirror) { m_transformation.set_mirror(mirror); m_arrange_cache.valid = false; }
+    void set_mirror(Axis axis, double mirror) { m_transformation.set_mirror(axis, mirror); m_arrange_cache.valid = false; }
 
     // To be called on an external mesh
     void transform_mesh(TriangleMesh* mesh, bool dont_translate = false) const;
@@ -554,20 +554,17 @@ public:
 
     bool is_printable() const { return print_volume_state == PVS_Inside; }
     
-    // /////////////////////////////////////////////////////////////////////////
-    // Implement arrangement::Arrangeable interface
-    // /////////////////////////////////////////////////////////////////////////
-    
     // Getting the input polygon for arrange
     arrangement::ArrangePolygon get_arrange_polygon() const;
     
     // Apply the arrange result on the ModelInstance
-    void apply_arrange_result(Vec2crd offs, double rot_rads)
+    void apply_arrange_result(Vec2crd offs, double rot_rads, int bed_idx = 0)
     {
         // write the transformation data into the model instance
         set_rotation(Z, rot_rads);
         set_offset(X, unscale<double>(offs(X)));
         set_offset(Y, unscale<double>(offs(Y)));
+        m_arrange_cache.bed_idx = bed_idx;
     }
 
 protected:
@@ -583,15 +580,28 @@ private:
     ModelObject* object;
 
     // Constructor, which assigns a new unique ID.
-    explicit ModelInstance(ModelObject *object) : object(object), print_volume_state(PVS_Inside) {}
+    explicit ModelInstance(ModelObject *object) : object(object), print_volume_state(PVS_Inside)
+    {
+        get_arrange_polygon(); // initialize the arrange cache
+    }
     // Constructor, which assigns a new unique ID.
     explicit ModelInstance(ModelObject *object, const ModelInstance &other) :
-        m_transformation(other.m_transformation), object(object), print_volume_state(PVS_Inside) {}
+        m_transformation(other.m_transformation), object(object), print_volume_state(PVS_Inside)
+    {
+        get_arrange_polygon(); // initialize the arrange cache
+    }
 
     ModelInstance() = delete;
     explicit ModelInstance(ModelInstance &&rhs) = delete;
     ModelInstance& operator=(const ModelInstance &rhs) = delete;
     ModelInstance& operator=(ModelInstance &&rhs) = delete;
+    
+    // Warning! This object is not guarded against concurrency.
+    mutable struct ArrangeCache {
+        bool valid = false;
+        int bed_idx { arrangement::UNARRANGED };
+        ExPolygon poly;
+    } m_arrange_cache;
 };
 
 // The print bed content.
diff --git a/src/slic3r/GUI/GLCanvas3D.cpp b/src/slic3r/GUI/GLCanvas3D.cpp
index 4e3093489..771d092a7 100644
--- a/src/slic3r/GUI/GLCanvas3D.cpp
+++ b/src/slic3r/GUI/GLCanvas3D.cpp
@@ -5739,10 +5739,11 @@ const SLAPrint* GLCanvas3D::sla_print() const
     return (m_process == nullptr) ? nullptr : m_process->sla_print();
 }
 
-void GLCanvas3D::WipeTowerInfo::apply_arrange_result(Vec2d offset, double rotation_rads)
+void GLCanvas3D::WipeTowerInfo::apply_arrange_result(Vec2crd off, double rotation_rads)
 {
-    m_pos      = offset;
-    m_rotation = rotation_rads;
+    Vec2d offset = unscaled(off);
+    m_pos        = offset;
+    m_rotation   = rotation_rads;
     DynamicPrintConfig cfg;
     cfg.opt<ConfigOptionFloat>("wipe_tower_x", true)->value = m_pos(X);
     cfg.opt<ConfigOptionFloat>("wipe_tower_y", true)->value = m_pos(Y);
diff --git a/src/slic3r/GUI/GLCanvas3D.hpp b/src/slic3r/GUI/GLCanvas3D.hpp
index 2316637d8..a28791ed0 100644
--- a/src/slic3r/GUI/GLCanvas3D.hpp
+++ b/src/slic3r/GUI/GLCanvas3D.hpp
@@ -624,7 +624,7 @@ public:
             return !std::isnan(m_pos.x()) && !std::isnan(m_pos.y());
         }
 
-        void apply_arrange_result(Vec2d offset, double rotation_rads);
+        void apply_arrange_result(Vec2crd offset, double rotation_rads);
         
         arrangement::ArrangePolygon get_arrange_polygon() const
         {
diff --git a/src/slic3r/GUI/Plater.cpp b/src/slic3r/GUI/Plater.cpp
index 3adfc0f05..f615c66d1 100644
--- a/src/slic3r/GUI/Plater.cpp
+++ b/src/slic3r/GUI/Plater.cpp
@@ -1272,147 +1272,290 @@ struct Plater::priv
     // objects would be frozen for the user. In case of arrange, an animation
     // could be shown, or with the optimize orientations, partial results
     // could be displayed.
-    class Job: public wxEvtHandler {
-        int m_range = 100;
+    class Job : public wxEvtHandler
+    {
+        int               m_range = 100;
         std::future<void> m_ftr;
-        priv *m_plater = nullptr;
-        std::atomic<bool> m_running {false}, m_canceled {false};
-        bool m_finalized = false;
-        
-        void run() { 
-            m_running.store(true); process(); m_running.store(false); 
-            
+        priv *            m_plater = nullptr;
+        std::atomic<bool> m_running{false}, m_canceled{false};
+        bool              m_finalized = false;
+
+        void run()
+        {
+            m_running.store(true);
+            process();
+            m_running.store(false);
+
             // ensure to call the last status to finalize the job
             update_status(status_range(), "");
         }
-        
+
     protected:
-        
         // status range for a particular job
         virtual int status_range() const { return 100; }
-        
+
         // status update, to be used from the work thread (process() method)
-        void update_status(int st, const wxString& msg = "") { 
-            auto evt = new wxThreadEvent(); evt->SetInt(st); evt->SetString(msg);
-            wxQueueEvent(this, evt); 
+        void update_status(int st, const wxString &msg = "")
+        {
+            auto evt = new wxThreadEvent();
+            evt->SetInt(st);
+            evt->SetString(msg);
+            wxQueueEvent(this, evt);
         }
-        
-        priv& plater() { return *m_plater; }
-        bool was_canceled() const { return m_canceled.load(); }
-        
+
+        priv &plater() { return *m_plater; }
+        bool  was_canceled() const { return m_canceled.load(); }
+
         // Launched just before start(), a job can use it to prepare internals
         virtual void prepare() {}
-        
-        // Launched when the job is finished. It refreshes the 3dscene by def.
-        virtual void finalize() {
+
+        // Launched when the job is finished. It refreshes the 3Dscene by def.
+        virtual void finalize()
+        {
             // Do a full refresh of scene tree, including regenerating
             // all the GLVolumes. FIXME The update function shall just
             // reload the modified matrices.
-            if(! was_canceled())
-                plater().update(true);
+            if (!was_canceled()) plater().update(true);
         }
-        
+
     public:
-        
-        Job(priv *_plater): m_plater(_plater)
+        Job(priv *_plater) : m_plater(_plater)
         {
-            Bind(wxEVT_THREAD, [this](const wxThreadEvent& evt){
+            Bind(wxEVT_THREAD, [this](const wxThreadEvent &evt) {
                 auto msg = evt.GetString();
-                if(! msg.empty()) plater().statusbar()->set_status_text(msg);
-                
-                if(m_finalized) return;
-                
+                if (!msg.empty())
+                    plater().statusbar()->set_status_text(msg);
+
+                if (m_finalized) return;
+
                 plater().statusbar()->set_progress(evt.GetInt());
-                if(evt.GetInt() == status_range()) {
-                    
+                if (evt.GetInt() == status_range()) {
                     // set back the original range and cancel callback
                     plater().statusbar()->set_range(m_range);
                     plater().statusbar()->set_cancel_callback();
                     wxEndBusyCursor();
-                    
+
                     finalize();
-                    
+
                     // dont do finalization again for the same process
                     m_finalized = true;
                 }
             });
         }
-        
-        // TODO: use this when we all migrated to VS2019
-        // Job(const Job&) = delete;
-        // Job(Job&&) = default;
-        // Job& operator=(const Job&) = delete;
-        // Job& operator=(Job&&) = default;
-        Job(const Job&) = delete;
-        Job& operator=(const Job&) = delete;
-        Job(Job &&o) :
-            m_range(o.m_range),
-            m_ftr(std::move(o.m_ftr)),
-            m_plater(o.m_plater),
-            m_finalized(o.m_finalized)
-        {
-            m_running.store(o.m_running.load());
-            m_canceled.store(o.m_canceled.load());
-        }
-        
+
+        Job(const Job &) = delete;
+        Job(Job &&)      = default;
+        Job &operator=(const Job &) = delete;
+        Job &operator=(Job &&) = default;
+
         virtual void process() = 0;
-        
-        void start() { // Start the job. No effect if the job is already running
-            if(! m_running.load()) {
-                
-                prepare();                
-                
+
+        void start()
+        { // Start the job. No effect if the job is already running
+            if (!m_running.load()) {
+                prepare();
+
                 // Save the current status indicatior range and push the new one
                 m_range = plater().statusbar()->get_range();
                 plater().statusbar()->set_range(status_range());
-                
+
                 // init cancellation flag and set the cancel callback
                 m_canceled.store(false);
-                plater().statusbar()->set_cancel_callback( [this](){ 
-                    m_canceled.store(true);
-                });
-                
+                plater().statusbar()->set_cancel_callback(
+                    [this]() { m_canceled.store(true); });
+
                 m_finalized = false;
-                
+
                 // Changing cursor to busy
                 wxBeginBusyCursor();
-                
-                try {   // Execute the job
+
+                try { // Execute the job
                     m_ftr = std::async(std::launch::async, &Job::run, this);
-                } catch(std::exception& ) { 
-                    update_status(status_range(), 
-                    _(L("ERROR: not enough resources to execute a new job.")));
+                } catch (std::exception &) {
+                    update_status(status_range(),
+                                  _(L("ERROR: not enough resources to "
+                                      "execute a new job.")));
                 }
-                
+
                 // The state changes will be undone when the process hits the
                 // last status value, in the status update handler (see ctor)
             }
         }
-        
-        // To wait for the running job and join the threads. False is returned
-        // if the timeout has been reached and the job is still running. Call
-        // cancel() before this fn if you want to explicitly end the job.
-        bool join(int timeout_ms = 0) const { 
-            if(!m_ftr.valid()) return true;
-            
-            if(timeout_ms <= 0) 
+
+        // To wait for the running job and join the threads. False is
+        // returned if the timeout has been reached and the job is still
+        // running. Call cancel() before this fn if you want to explicitly
+        // end the job.
+        bool join(int timeout_ms = 0) const
+        {
+            if (!m_ftr.valid()) return true;
+
+            if (timeout_ms <= 0)
                 m_ftr.wait();
-            else if(m_ftr.wait_for(std::chrono::milliseconds(timeout_ms)) == 
-                    std::future_status::timeout) 
+            else if (m_ftr.wait_for(std::chrono::milliseconds(
+                         timeout_ms)) == std::future_status::timeout)
                 return false;
-            
+
             return true;
         }
-        
+
         bool is_running() const { return m_running.load(); }
         void cancel() { m_canceled.store(true); }
     };
-    
+
     enum class Jobs : size_t {
         Arrange,
         Rotoptimize
     };
     
+    class ArrangeJob : public Job
+    {
+        // The gap between logical beds in the x axis expressed in ratio of
+        // the current bed width.
+        static const constexpr double LOGICAL_BED_GAP = 1. / 5.;
+        
+        // Cache the wti info
+        GLCanvas3D::WipeTowerInfo m_wti;
+        
+        // Cache the selected instances needed to write back the arrange
+        // result. The order of instances is the same as the arrange polys
+        struct IndexedArrangePolys {
+            ModelInstancePtrs insts;
+            arrangement::ArrangePolygons polys;
+            
+            void reserve(size_t cap) { insts.reserve(cap); polys.reserve(cap); }
+            void clear() { insts.clear(); polys.clear(); }
+        
+            void emplace_back(ModelInstance *inst) {
+                insts.emplace_back(inst);
+                polys.emplace_back(inst->get_arrange_polygon());
+            }
+            
+            void swap(IndexedArrangePolys &pp) {
+                insts.swap(pp.insts); polys.swap(pp.polys);
+            }
+        };
+        
+        IndexedArrangePolys m_selected, m_unselected;
+        
+    protected:
+        
+        void prepare() override
+        {
+            m_wti = plater().view3D->get_canvas3d()->get_wipe_tower_info();
+            
+            // Get the selection map
+            Selection& sel = plater().get_selection();
+            const Selection::ObjectIdxsToInstanceIdxsMap &selmap =
+                sel.get_content();
+            
+            Model &model = plater().model;
+            
+            size_t count = 0; // To know how much space to reserve
+            for (auto obj : model.objects) count += obj->instances.size();
+            
+            m_selected.clear(), m_unselected.clear();
+            m_selected.reserve(count + 1 /* for optional wti */);
+            m_unselected.reserve(count + 1 /* for optional wti */);
+            
+            // Go through the objects and check if inside the selection
+            for (size_t oidx = 0; oidx < model.objects.size(); ++oidx) {
+                auto oit = selmap.find(int(oidx));
+                
+                if (oit != selmap.end()) { // Object is selected
+                    auto &iids = oit->second;
+                    
+                    // Go through instances and check if inside selection
+                    size_t instcnt = model.objects[oidx]->instances.size();
+                    for (size_t iidx = 0; iidx < instcnt; ++iidx) {
+                        auto           instit = iids.find(iidx);
+                        ModelInstance *oi     = model.objects[oidx]
+                                                ->instances[iidx];
+                        
+                        // Instance is selected
+                        instit != iids.end() ?
+                            m_selected.emplace_back(oi) :
+                            m_unselected.emplace_back(oi);
+                    }
+                } else // object not selected, all instances are unselected
+                    for (ModelInstance *oi : model.objects[oidx]->instances)
+                        m_unselected.emplace_back(oi);
+            }
+            
+            // If the selection is completely empty, consider all items as the
+            // selection
+            if (m_selected.insts.empty() && m_selected.polys.empty())
+                m_selected.swap(m_unselected);
+                        
+            if (m_wti)
+                sel.is_wipe_tower() ?
+                    m_selected.polys.emplace_back(m_wti.get_arrange_polygon()) :
+                    m_unselected.polys.emplace_back(m_wti.get_arrange_polygon());
+            
+            // Stride between logical beds
+            double bedwidth = plater().bed_shape_bb().size().x();
+            coord_t stride = scaled((1. + LOGICAL_BED_GAP) * bedwidth);
+            
+            for (arrangement::ArrangePolygon &ap : m_selected.polys)
+                if (ap.bed_idx > 0) ap.translation.x() -= ap.bed_idx * stride;
+            
+            for (arrangement::ArrangePolygon &ap : m_unselected.polys)
+                if (ap.bed_idx > 0) ap.translation.x() -= ap.bed_idx * stride;
+        }
+        
+    public:
+        using Job::Job;
+        
+        
+        int status_range() const override
+        {
+            return int(m_selected.polys.size());
+        }
+        
+        void process() override;
+        
+        void finalize() override {
+            
+            if (was_canceled()) { // Ignore the arrange result if aborted.
+                Job::finalize();
+                return;
+            }
+            
+            // Stride between logical beds
+            double bedwidth = plater().bed_shape_bb().size().x();
+            coord_t stride = scaled((1. + LOGICAL_BED_GAP) * bedwidth);
+            
+            for(size_t i = 0; i < m_selected.insts.size(); ++i) {
+                if (m_selected.polys[i].bed_idx != arrangement::UNARRANGED) {
+                    Vec2crd offs = m_selected.polys[i].translation;
+                    double rot   = m_selected.polys[i].rotation;
+                    int bdidx    = m_selected.polys[i].bed_idx;
+                    offs.x()    += bdidx * stride;
+                    m_selected.insts[i]->apply_arrange_result(offs, rot, bdidx);
+                }
+            }
+            
+            // Handle the wipe tower
+            const arrangement::ArrangePolygon &wtipoly = m_selected.polys.back();
+            if (m_wti && wtipoly.bed_idx != arrangement::UNARRANGED) {
+                Vec2crd o = wtipoly.translation;
+                double  r = wtipoly.rotation;
+                o.x() += wtipoly.bed_idx * stride;
+                m_wti.apply_arrange_result(o, r);
+            }
+            
+            // Call original finalize (will update the scene)
+            Job::finalize();
+        }
+    };
+    
+    class RotoptimizeJob : public Job
+    {
+    public:
+        using Job::Job;
+        void process() override;
+    };
+    
     // Jobs defined inside the group class will be managed so that only one can
     // run at a time. Also, the background process will be stopped if a job is
     // started.
@@ -1422,84 +1565,8 @@ struct Plater::priv
         
         priv * m_plater;
 
-        class ArrangeJob : public Job
-        {   
-            GLCanvas3D::WipeTowerInfo m_wti;
-            arrangement::ArrangePolygons m_selected, m_unselected;
-            
-            static std::array<arrangement::ArrangePolygons, 2> collect(
-                Model &model, const Selection &sel)
-            {
-                const Selection::ObjectIdxsToInstanceIdxsMap &selmap =
-                    sel.get_content();
-                
-                size_t count = 0;
-                for (auto obj : model.objects) count += obj->instances.size();
-                
-                arrangement::ArrangePolygons selected, unselected;
-                selected.reserve(count + 1 /* for optional wti */);
-                unselected.reserve(count + 1 /* for optional wti */);
-                
-                for (size_t oidx = 0; oidx < model.objects.size(); ++oidx) {
-                    auto oit = selmap.find(int(oidx));
-
-                    if (oit != selmap.end()) {
-                        auto &iids = oit->second;
-
-                        for (size_t iidx = 0;
-                             iidx < model.objects[oidx]->instances.size();
-                             ++iidx)
-                        {
-                            auto           instit = iids.find(iidx);
-                            ModelInstance *inst   = model.objects[oidx]
-                                                      ->instances[iidx];
-                            instit == iids.end() ?
-                                unselected.emplace_back(inst->get_arrange_polygon()) :
-                                selected.emplace_back(inst->get_arrange_polygon());
-                        }
-                    } else // object not selected, all instances are unselected
-                        for (auto inst : model.objects[oidx]->instances)
-                            unselected.emplace_back(inst->get_arrange_polygon());
-                }
-                
-                if (selected.empty()) selected.swap(unselected);
-                
-                return {selected, unselected};
-            }
-
-        protected:
-
-            void prepare() override
-            {
-                m_wti = plater().view3D->get_canvas3d()->get_wipe_tower_info();
-                
-                const Selection& sel = plater().get_selection();
-                BoundingBoxf bedbb(plater().bed.get_shape());
-                auto arrinput = collect(plater().model, sel);
-                m_selected.swap(arrinput[0]);
-                m_unselected.swap(arrinput[1]);
-
-                if (m_wti)
-                    sel.is_wipe_tower() ?
-                        m_selected.emplace_back(m_wti.get_arrange_polygon()) :
-                        m_unselected.emplace_back(m_wti.get_arrange_polygon());
-            }
-
-        public:
-            using Job::Job;
-            int status_range() const override
-            {
-                return int(m_selected.size());
-            }
-            void process() override;
-        } arrange_job{m_plater};
-
-        class RotoptimizeJob : public Job
-        {
-        public:
-            using Job::Job;
-            void process() override;
-        } rotoptimize_job{m_plater};
+        ArrangeJob arrange_job{m_plater};
+        RotoptimizeJob rotoptimize_job{m_plater};
 
         // To create a new job, just define a new subclass of Job, implement
         // the process and the optional prepare() and finalize() methods
@@ -2447,50 +2514,47 @@ void Plater::priv::sla_optimize_rotation() {
 }
 
 arrangement::BedShapeHint Plater::priv::get_bed_shape_hint() const {
-    arrangement::BedShapeHint bedshape;
     
     const auto *bed_shape_opt = config->opt<ConfigOptionPoints>("bed_shape");
     assert(bed_shape_opt);
     
-    if (bed_shape_opt) {
-        auto &bedpoints = bed_shape_opt->values;
-        Polyline bedpoly; bedpoly.points.reserve(bedpoints.size());
-        for (auto &v : bedpoints) bedpoly.append(scaled(v));
-        bedshape = arrangement::bedShape(bedpoly);
-    }
+    if (!bed_shape_opt) return {};
     
-    return bedshape;
+    auto &bedpoints = bed_shape_opt->values;
+    Polyline bedpoly; bedpoly.points.reserve(bedpoints.size());
+    for (auto &v : bedpoints) bedpoly.append(scaled(v));
+    
+    return arrangement::BedShapeHint(bedpoly);
 }
 
-void Plater::priv::ExclusiveJobGroup::ArrangeJob::process() {
-    auto count = unsigned(m_selected.size());
-    plater().model.arrange_objects(6.f, nullptr);
-//    static const auto arrangestr = _(L("Arranging"));
+void Plater::priv::ArrangeJob::process() {
+    static const auto arrangestr = _(L("Arranging"));
     
-//    // FIXME: I don't know how to obtain the minimum distance, it depends
-//    // on printer technology. I guess the following should work but it crashes.
-//    double dist = 6; // PrintConfig::min_object_distance(config);
-//    if (plater().printer_technology == ptFFF) {
-//        dist = PrintConfig::min_object_distance(plater().config);
-//    }
+    // FIXME: I don't know how to obtain the minimum distance, it depends
+    // on printer technology. I guess the following should work but it crashes.
+    double dist = 6; // PrintConfig::min_object_distance(config);
+    if (plater().printer_technology == ptFFF) {
+        dist = PrintConfig::min_object_distance(plater().config);
+    }
     
-//    coord_t min_obj_distance = scaled(dist);
-//    auto count = unsigned(m_selected.size());
-//    arrangement::BedShapeHint bedshape = plater().get_bed_shape_hint();
+    coord_t min_obj_distance = scaled(dist);
+    auto count = unsigned(m_selected.polys.size());
+    arrangement::BedShapeHint bedshape = plater().get_bed_shape_hint();
     
-//    try {
-//        arrangement::arrange(m_selected, m_unselected, min_obj_distance,
-//                             bedshape,
-//                             [this, count](unsigned st) {
-//                                 if (st > 0) // will not finalize after last one
-//                                     update_status(count - st, arrangestr);
-//                             },
-//                             [this]() { return was_canceled(); });
-//    } catch (std::exception & /*e*/) {
-//        GUI::show_error(plater().q,
-//                        _(L("Could not arrange model objects! "
-//                            "Some geometries may be invalid.")));
-//    }
+    try {
+        arrangement::arrange(m_selected.polys, m_unselected.polys,
+                             min_obj_distance,
+                             bedshape,
+                             [this, count](unsigned st) {
+                                 if (st > 0) // will not finalize after last one
+                                     update_status(count - st, arrangestr);
+                             },
+                             [this]() { return was_canceled(); });
+    } catch (std::exception & /*e*/) {
+        GUI::show_error(plater().q,
+                        _(L("Could not arrange model objects! "
+                            "Some geometries may be invalid.")));
+    }
     
     // finalize just here.
     update_status(int(count),
@@ -2503,11 +2567,27 @@ void find_new_position(const Model &            model,
                        coord_t                  min_d,
                        const arrangement::BedShapeHint &bedhint)
 {
+    arrangement::ArrangePolygons movable, fixed;
     
-    // TODO
+    for (const ModelObject *mo : model.objects)
+        for (const ModelInstance *inst : mo->instances) {
+            auto it = std::find(instances.begin(), instances.end(), inst);
+            if (it != instances.end())
+                fixed.emplace_back(inst->get_arrange_polygon());
+        }
+    
+    for (ModelInstance *inst : instances)
+        movable.emplace_back(inst->get_arrange_polygon());
+    
+    arrangement::arrange(movable, fixed, min_d, bedhint);
+    
+    for (size_t i = 0; i < instances.size(); ++i)
+        if (movable[i].bed_idx == 0)
+            instances[i]->apply_arrange_result(movable[i].translation,
+                                               movable[i].rotation);
 }
 
-void Plater::priv::ExclusiveJobGroup::RotoptimizeJob::process()
+void Plater::priv::RotoptimizeJob::process()
 {
     int obj_idx = plater().get_selected_object_idx();
     if (obj_idx < 0) { return; }