Merge remote-tracking branch 'remotes/prusa/master' 2.4 into dev 2.3.58

still need much tests (& bugfixes) and finish some merging things.

1 files changed, 273 insertions, 0 deletions

diff --git a/sandboxes/its_neighbor_index/main.cpp b/sandboxes/its_neighbor_index/main.cpp
new file mode 100644
index 000000000..2c89da3ac
--- /dev/null
+++ b/sandboxes/its_neighbor_index/main.cpp
@@ -0,0 +1,273 @@
+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <tuple>
+#include <random>
+
+#include "ItsNeighborIndex.hpp"
+
+#include "libnest2d/tools/benchmark.h"
+#include "libnest2d/utils/metaloop.hpp"
+
+namespace Slic3r {
+
+enum { IndexCreation, Split };
+struct MeasureResult
+{
+    static constexpr const char * Names[] = {
+        "Index creation [s]",
+        "Split [s]"
+    };
+
+    double measurements[std::size(Names)] = {0.};
+};
+
+template<class IndexCreatorFn>
+static MeasureResult measure_index(const indexed_triangle_set &its, IndexCreatorFn fn)
+{
+    Benchmark b;
+
+    MeasureResult r;
+    for (int i = 0; i < 10; ++i) {
+        b.start();
+        ItsNeighborsWrapper itsn{its, fn(its)};
+        b.stop();
+
+        r.measurements[IndexCreation] += b.getElapsedSec();
+
+        b.start();
+        auto res = its_split(itsn);
+        b.stop();
+
+//        if (res.size() != 2 || res[0].indices.size() != res[1].indices.size() )
+//            std::cerr << "Something is wrong, split result invalid" << std::endl;
+
+        r.measurements[Split] += b.getElapsedSec();
+    }
+
+    r.measurements[IndexCreation] /= 10;
+    r.measurements[Split] /= 10;
+
+    return r;
+}
+
+const auto Seed = 0;// std::random_device{}();
+
+static indexed_triangle_set make_sphere_rnd(double radius, double detail)
+{
+    using namespace Slic3r;
+
+    auto sphere = its_make_sphere(radius, detail);
+
+    auto vfidx = create_vertex_faces_index(sphere);
+
+    const size_t vertexnum = sphere.vertices.size();
+    const size_t facenum   = sphere.indices.size();
+
+    std::mt19937 rng{Seed};
+    std::uniform_int_distribution<size_t> distv(sphere.vertices.size() / 2, sphere.vertices.size() - 1);
+    std::uniform_int_distribution<size_t> distf(sphere.indices.size() / 2, sphere.indices.size() - 1) ;
+
+    std::vector<bool> was(vertexnum / 2, false);
+
+    for (size_t i = 0; i < vertexnum / 2; ++i) {
+        size_t image = distv(rng);
+        if (was[image - vertexnum / 2]) continue;
+        was[image - vertexnum / 2] = true;
+
+        std::swap(sphere.vertices[i], sphere.vertices[image]);
+        for (size_t face_id : vfidx[i]) {
+            for (int &vi : sphere.indices[face_id])
+                if (vi == int(i)) vi = image;
+        }
+
+        for (size_t face_id : vfidx[image]) {
+            for (int &vi : sphere.indices[face_id])
+                if (vi == int(image)) vi = i;
+        }
+
+        std::swap(vfidx[i], vfidx[image]);
+    }
+
+    for (size_t i = 0; i < facenum / 2; ++i) {
+        size_t image = distf(rng);
+        std::swap(sphere.indices[i], sphere.indices[image]);
+    }
+
+    return sphere;
+}
+
+static indexed_triangle_set two_spheres(double detail)
+{
+    auto sphere1 = make_sphere_rnd(10., 2 * PI / detail), sphere2 = sphere1;
+
+    its_transform(sphere1, identity3f().translate(Vec3f{-5.f, 0.f, 0.f}));
+    its_transform(sphere2, identity3f().translate(Vec3f{5.f, 0.f, 0.f}));
+
+    its_merge(sphere1, sphere2);
+
+    return sphere1;
+}
+
+static indexed_triangle_set make_spheres(unsigned N, double detail)
+{
+    indexed_triangle_set ret, sphere = make_sphere_rnd(10., 2. * PI / detail);
+
+    for (unsigned i = 0u ; i < N; ++i)
+        its_merge(ret, sphere);
+
+    return ret;
+}
+
+constexpr double sq2 = std::sqrt(2.);
+
+static const std::pair<const std::string, indexed_triangle_set> ToMeasure[] = {
+//    {"two_spheres_1x", two_spheres(60.)},
+//    {"two_spheres_2x", two_spheres(120.)},
+//    {"two_spheres_4x", two_spheres(240.)},
+//    {"two_spheres_8x", two_spheres(480.)},
+//    {"two_spheres_16x", two_spheres(2 * 480.)},
+//    {"two_spheres_32x", two_spheres(2 * 2 * 480.)},
+
+    {"two_spheres_1x", two_spheres(60.)},
+    {"two_spheres_2x", two_spheres(sq2 * 60.)},
+    {"two_spheres_4x", two_spheres(2 * 60.)},
+    {"two_spheres_8x", two_spheres(sq2 * 2. * 60.)},
+    {"two_spheres_16x", two_spheres(4. * 60.)},
+    {"two_spheres_32x", two_spheres(sq2 * 4. * 60.)},
+    {"two_spheres_64x", two_spheres(8. * 60.)},
+    {"two_spheres_128x", two_spheres(sq2 * 8. * 60.)},
+    {"two_spheres_256x", two_spheres(16. * 60.)},
+    {"two_spheres_512x", two_spheres(sq2 * 16. * 60.)},
+
+    {"2_spheres", make_spheres(2, 60.)},
+    {"4_spheres", make_spheres(4, 60.)},
+    {"8_spheres", make_spheres(8, 60.)},
+    {"16_spheres", make_spheres(16,  60.)},
+    {"32_spheres", make_spheres(32, 60.)},
+    {"64_spheres", make_spheres(64, 60.)},
+    {"128_spheres", make_spheres(128, 60.)},
+    {"256_spheres", make_spheres(256, 60.)},
+    {"512_spheres", make_spheres(512, 60.)},
+    {"1024_spheres", make_spheres(1024, 60.)}
+};
+
+static const auto IndexFunctions = std::make_tuple(
+    std::make_pair("tamas's unordered_map based", [](const auto &its) { return measure_index(its, its_create_neighbors_index_1); }),
+    std::make_pair("vojta std::sort based", [](const auto &its) { return measure_index(its, its_create_neighbors_index_2); }),
+    std::make_pair("vojta tbb::parallel_sort based", [](const auto &its) { return measure_index(its, its_create_neighbors_index_3); }),
+    std::make_pair("filip's vertex->face based", [](const auto &its) { return measure_index(its, its_create_neighbors_index_5); }),
+    std::make_pair("vojta's vertex->face", [](const auto &its) { return measure_index(its, its_create_neighbors_index_9); }),
+    std::make_pair("vojta's vertex->face parallel", [](const auto &its) { return measure_index(its, its_create_neighbors_index_10); }),
+    std::make_pair("tamas's std::sort based", [](const auto &its) { return measure_index(its, its_create_neighbors_index_6); }),
+    std::make_pair("tamas's tbb::parallel_sort based", [](const auto &its) { return measure_index(its, its_create_neighbors_index_7); }),
+    std::make_pair("tamas's map based", [](const auto &its) { return measure_index(its, its_create_neighbors_index_8); }),
+    std::make_pair("TriangleMesh split", [](const auto &its) {
+
+        MeasureResult r;
+        for (int i = 0; i < 10; ++i) {
+            TriangleMesh m{its};
+            Benchmark b;
+
+            b.start();
+            m.repair(); // FIXME: this does more than just create neighborhood map
+            b.stop();
+            r.measurements[IndexCreation] += b.getElapsedSec();
+
+            b.start();
+            auto res = m.split();
+            b.stop();
+            r.measurements[Split] += b.getElapsedSec();
+
+//            if (res.size() != 2 || res[0]->size() != res[1]->size())
+//                std::cerr << "Something is wrong, split result invalid" << std::endl;
+        }
+        r.measurements[IndexCreation] /= 10;
+        r.measurements[Split] /= 10;
+
+        return r;
+    })
+
+//    std::make_pair("Vojta's vertex->face index", [](const auto &its){
+//        Benchmark b;
+//        b.start();
+//        auto index = create_vertex_faces_index(its);
+//        b.stop();
+
+//        if (index.size() != its.vertices.size())
+//            std::cerr << "Something went wrong!";
+
+//        return  MeasureResult{b.getElapsedSec(), 0., 0.};
+//    }),
+//    std::make_pair("Tamas's vertex->face index", [](const auto &its){
+//        Benchmark b;
+//        b.start();
+//        VertexFaceIndex index{its};
+//        b.stop();
+
+//        if (index.size() < its.vertices.size())
+//            std::cerr << "Something went wrong!";
+
+//        return  MeasureResult{b.getElapsedSec(), 0., 0.};
+//    })
+);
+
+static constexpr size_t IndexFuncNum = std::tuple_size_v<decltype (IndexFunctions)>;
+
+} // namespace Slic3r
+
+int main(const int argc, const char * argv[])
+{
+    using namespace Slic3r;
+
+    std::array<MeasureResult, IndexFuncNum> results[std::size(ToMeasure)];
+    std::array<std::string, IndexFuncNum> funcnames;
+
+    for (size_t i = 0; i < std::size(ToMeasure); ++i) {
+        auto &m = ToMeasure[i];
+        auto &name = m.first;
+        auto &mesh = m.second;
+
+//        its_write_obj(mesh, (std::string(name) + ".obj").c_str());
+
+        std::cout << "Mesh " << name << " has " << mesh.indices.size() << " faces and " << mesh.vertices.size() << " vertices." << std::endl;
+        libnest2d::opt::metaloop::apply([&mesh, i, &results, &funcnames](int N, auto &e) {
+            MeasureResult r = e.second(mesh);
+            funcnames[N] = e.first;
+            results[i][N] = r;
+        }, IndexFunctions);
+    }
+
+    std::string outfilename = "out.csv";
+    std::fstream outfile;
+    if (argc > 1) {
+        outfilename = argv[1];
+        outfile.open(outfilename, std::fstream::out);
+        std::cout << outfilename << " will be used" << std::endl;
+    }
+
+    std::ostream &out = outfile.is_open() ? outfile : std::cout;
+
+    for (size_t m = 0; m < std::size(MeasureResult::Names); ++m) {
+        out << MeasureResult::Names[m] << "\n";
+        out << std::endl;
+        out << "model;" ;
+        for (const std::string &funcname : funcnames) {
+            out << funcname << ";";
+        }
+
+        out << std::endl;
+
+        for (size_t i = 0; i < std::size(ToMeasure); ++i) {
+            const auto &result_row = results[i];
+            const std::string &name = ToMeasure[i].first;
+            out << name << ";";
+            for (auto &r : result_row)
+                out << r.measurements[m] << ";";
+
+            out << std::endl;
+        }
+    }
+
+    return 0;
+}