w

5 files changed, 80 insertions, 67 deletions

diff --git a/editor/tests/hole-test.cpp b/editor/tests/hole-test.cpp
index 07c0b093..389f3ec9 100644
--- a/editor/tests/hole-test.cpp
+++ b/editor/tests/hole-test.cpp
@@ -58,8 +58,8 @@ constexpr auto colors = std::array{
 
 void hole_test::draw_ui(app& a, float)
 {
-    using crr = cut_rectangle_result<Int>;
-    using bbox = typename crr::bbox;
+    using Cr = CutResult<Int>;
+    using bbox = Cr::bbox;
     const auto& m = a.main();
     const auto width = Math::min(ImGui::GetWindowSize().x, 400.f);
     const auto window_size = ImVec2{width, width};
@@ -76,7 +76,7 @@ void hole_test::draw_ui(app& a, float)
     ImGui::NewLine();
 
     bbox rect{{}, Vector2ub{tile_size_xy}};
-    const auto res = crr::cut(rect, {st.pos, st.size});
+    const auto res = Cr::cut(rect, {st.pos, st.size});
 
     ImGui::SetNextWindowSize({width, width});
     if (auto b1 = imgui::begin_child("Test area"_s, window_size, igcf, igwf))
@@ -110,8 +110,6 @@ void hole_test::draw_ui(app& a, float)
                      to_imvec2(center + (Vector2(st.pos) + Vector2(st.size)*.5f)* mult), red, 0, 0, 1); // hole
     }
 
-    constexpr auto rmin = Int{-tile_size_xy/2}, rmax = Int{(tile_size_xy+1)/2};
-    const bool found = res.size != 1 || res.array[0].min != Vector2i{rmin} || res.array[0].max != Vector2i{rmax};
     const auto label_width = ImGui::CalcTextSize("MMMMMM").x;
 
     ImGui::NewLine();
@@ -135,7 +133,7 @@ void hole_test::draw_ui(app& a, float)
     }
     {
         label_left("found", buf, label_width);
-        ImGui::Text("%s", found ? "true" : "false");
+        ImGui::Text("%s", res.found ? "true" : "false");
     }
 
     ImGui::Unindent(style.FramePadding.x);
diff --git a/src/chunk-collision.cpp b/src/chunk-collision.cpp
index 1f6e0d27..33b0453b 100644
--- a/src/chunk-collision.cpp
+++ b/src/chunk-collision.cpp
@@ -1,8 +1,10 @@
 #include "chunk.hpp"
 #include "ground-atlas.hpp"
 #include "object.hpp"
+#include "world.hpp"
 #include "src/RTree-search.hpp"
 #include "rect-intersects.hpp"
+#include "hole.hpp"
 #include "src/chunk-scenery.hpp"
 #include "src/tile-bbox.hpp"
 #include "src/hole.hpp"
@@ -10,7 +12,6 @@
 #include <bit>
 #include <Corrade/Containers/StructuredBindings.h>
 #include <Corrade/Containers/Pair.h>
-//#include <cr/GrowableArray.h>
 
 namespace floormat {
 
@@ -32,13 +33,6 @@ constexpr object_id make_id(collision_type type, pass_mode p, object_id id)
     return std::bit_cast<object_id>(make_id_(type, p, id));
 }
 
-struct Data
-{
-    object_id id;
-    Vector2 min, max;
-};
-
-#if 0
 template<bool IsNeighbor>
 void add_holes_from(chunk::RTree& rtree, chunk& c, Vector2b chunk_offset)
 {
@@ -65,35 +59,55 @@ void add_holes_from(chunk::RTree& rtree, chunk& c, Vector2b chunk_offset)
     }
 }
 
-void filter_through_holes(chunk::RTree& rtree, Data bbox, unsigned stack)
+#if 0
+void filter_through_holes(chunk::RTree& rtree, object_id id, Vector2 min, Vector2 max, unsigned stack = 0)
 {
-    using Rect = typename chunk::RTree::Rect;
-    Vector2 hmin, hmax;
+start:
+    CutResult<float>::rect hole;
     bool ret = true;
-    rtree.Search(bbox.min.data(), bbox.max.data(), [&](uint64_t data, const Rect& r) {
+    rtree.Search(min.data(), max.data(), [&](uint64_t data, const chunk::RTree::Rect& r) {
         [[maybe_unused]] auto x = std::bit_cast<collision_data>(data);
         if (x.pass == (uint64_t)pass_mode::pass && x.tag == (uint64_t)collision_type::none)
         {
-            hmin = Vector2(r.m_min[0], r.m_min[1]);
-            hmax = Vector2(r.m_max[0], r.m_max[1]);
-            return ret = false;
+            CutResult<float>::rect holeʹ {
+                .min = { r.m_min[0], r.m_min[1] },
+                .max = { r.m_max[0], r.m_max[1] },
+            };
+            if (rect_intersects(holeʹ.min, holeʹ.max, min, max))
+            {
+                hole = holeʹ;
+                return ret = false;
+            }
         }
         return true;
     });
 
     if (ret) [[likely]]
-        rtree.Insert(bbox.min.data(), bbox.max.data(), bbox.id);
+        rtree.Insert(min.data(), max.data(), id);
     else
     {
-        //auto res = cut_rectangle_result<float>::cut();
-        //for (auto i = 0uz; i < )
-        fm_assert(++stack <= 4096);
-    }
+        auto res = CutResult<float>::cut(min, max, hole.min, hole.max);
+        if (!res.found)
+        {
+            rtree.Insert(min.data(), max.data(), id);
+        }
+        else if (res.size == 1)
+        {
+            min = res.array[0].min;
+            max = res.array[0].max;
+            goto start;
+        }
+        else
+        {
+            fm_assert(stack <= 1024);
+            for (auto i = 0uz; i < res.size; i++)
+                filter_through_holes(rtree, id, res.array[i].min, res.array[i].max, stack+1);
+        }}
 }
 #else
-void filter_through_holes(chunk::RTree& rtree, Data bbox, unsigned)
+void filter_through_holes(chunk::RTree& rtree, object_id id, Vector2 min, Vector2 max, unsigned = 0)
 {
-    rtree.Insert(bbox.min.data(), bbox.max.data(), bbox.id);
+    rtree.Insert(min.data(), max.data(), id);
 }
 #endif
 
@@ -109,13 +123,21 @@ void chunk::ensure_passability() noexcept
 
     _rtree->RemoveAll();
 
+    {
+        add_holes_from<false>(*_rtree, *this, {});
+        const auto nbs = _world->neighbors(_coord);
+        for (auto i = 0u; i < 8; i++)
+            if (nbs[i])
+                add_holes_from<true>(*_rtree, *nbs[i], world::neighbor_offsets[i]);
+    }
+
     for (auto i = 0uz; i < TILE_COUNT; i++)
     {
         if (const auto* atlas = ground_atlas_at(i))
         {
             auto [min, max] = whole_tile(i);
             auto id = make_id(collision_type::geometry, atlas->pass_mode(), i+1);
-            filter_through_holes(*_rtree, {id, min, max}, 0);
+            filter_through_holes(*_rtree, id, min, max);
         }
     }
     for (auto i = 0uz; i < TILE_COUNT; i++)
@@ -125,35 +147,31 @@ void chunk::ensure_passability() noexcept
         {
             auto [min, max] = wall_north(i, (float)atlas->info().depth);
             auto id = make_id(collision_type::geometry, atlas->info().passability, TILE_COUNT+i+1);
-            filter_through_holes(*_rtree, {id, min, max}, 0);
+            filter_through_holes(*_rtree, id, min, max);
 
             if (tile.wall_west_atlas())
             {
                 auto [min, max] = wall_pillar(i, (float)atlas->info().depth);
-                filter_through_holes(*_rtree, {id, min, max}, 0);
+                filter_through_holes(*_rtree, id, min, max);
             }
         }
         if (const auto* atlas = tile.wall_west_atlas().get())
         {
             auto [min, max] = wall_west(i, (float)atlas->info().depth);
             auto id = make_id(collision_type::geometry, atlas->info().passability, TILE_COUNT*2+i+1);
-            filter_through_holes(*_rtree, {id, min, max}, 0);
+            filter_through_holes(*_rtree, id, min, max);
         }
     }
-    for (const std::shared_ptr<object>& s : objects())
-        if (!s->is_dynamic())
-            if (bbox box; _bbox_for_scenery(*s, box))
-                filter_through_holes(*_rtree, {std::bit_cast<object_id>(box.data), Vector2(box.start), Vector2(box.end)}, 0);
-
-    //for (auto [id, min, max] : vec) _rtree->Insert(min.data(), max.data(), id);
-    //arrayResize(vec, 0); arrayResize(vec2, 0); // done with holes
-
-    for (const std::shared_ptr<object>& s : objects())
+    for (const std::shared_ptr<object>& sʹ : objects())
     {
         bbox box;
-        if (s->is_dynamic())
-            if (_bbox_for_scenery(*s, box))
+        if (sʹ->type() != object_type::hole && _bbox_for_scenery(*sʹ, box))
+        {
+            if (sʹ->is_dynamic())
                 _add_bbox(box);
+            else
+                filter_through_holes(*_rtree, std::bit_cast<object_id>(box.data), Vector2(box.start), Vector2(box.end));
+        }
     }
 }
 
diff --git a/src/hole-cut.cpp b/src/hole-cut.cpp
index 51d1a8af..bb27c10b 100644
--- a/src/hole-cut.cpp
+++ b/src/hole-cut.cpp
@@ -15,9 +15,9 @@
 namespace floormat {
 namespace {
 
-template<typename T> using crr = cut_rectangle_result<T>;
-template<typename T> using bbox = typename cut_rectangle_result<T>::bbox;
-template<typename T> using rect = typename cut_rectangle_result<T>::rect;
+template<typename T> using Cr = CutResult<T>;
+template<typename T> using bbox = typename Cr<T>::bbox;
+template<typename T> using rect = typename Cr<T>::rect;
 
 enum shift : uint8_t { __ = 0, x0 = 1 << 0, x1 = 1 << 1, y0 = 1 << 2, y1 = 1 << 3, };
 enum class location : uint8_t { R0, R1, H0, H1, };
@@ -151,12 +151,13 @@ constexpr bool check_empty(Vec2ʹ<T> r0, Vec2ʹ<T> r1, Vec2ʹ<T> h0, Vec2ʹ<T> h
 }
 
 template<typename T>
-constexpr cut_rectangle_result<T> cut_rectangle(Vec2ʹ<T> r0, Vec2ʹ<T> r1, Vec2ʹ<T> h0, Vec2ʹ<T> h1)
+constexpr Cr<T> cut_rectangle(Vec2ʹ<T> r0, Vec2ʹ<T> r1, Vec2ʹ<T> h0, Vec2ʹ<T> h1)
 {
     if (check_empty<T>(r0, r1, h0, h1))
         return {
-            .size = 1,
             .array = {{ { r0, r1 }, }},
+            .size = 1,
+            .found = false,
         };
 
     const bool sx = h0.x() <= r0.x();
@@ -168,9 +169,10 @@ constexpr cut_rectangle_result<T> cut_rectangle(Vec2ʹ<T> r0, Vec2ʹ<T> r1, Vec2
     CORRADE_ASSUME(val < 16);
     const auto elt = elements[val];
     const auto sz = elt.size;
-    cut_rectangle_result<T> res = {
-        .size = sz,
+    Cr<T> res = {
         .array = {},
+        .size = sz,
+        .found = true,
     };
 
     for (auto i = 0u; i < 8; i++)
@@ -180,7 +182,7 @@ constexpr cut_rectangle_result<T> cut_rectangle(Vec2ʹ<T> r0, Vec2ʹ<T> r1, Vec2
 }
 
 template<typename T>
-constexpr cut_rectangle_result<T> cut_rectangle(bbox<T> input, bbox<T> hole)
+constexpr Cr<T> cut_rectangle(bbox<T> input, bbox<T> hole)
 {
     using Vec2 = Vec2ʹ<T>;
 
@@ -197,16 +199,10 @@ constexpr cut_rectangle_result<T> cut_rectangle(bbox<T> input, bbox<T> hole)
 
 } // namespace
 
-template struct cut_rectangle_result<Int>;
-template struct cut_rectangle_result<float>;
-
-template<typename T> crr<T> cut_rectangle_result<T>::cut(bbox input, bbox hole) { return cut_rectangle<T>(input, hole); }
-template<typename T> crr<T> cut_rectangle_result<T>::cut(Vec2 r0, Vec2 r1, Vec2 h0, Vec2 h1) { return cut_rectangle<T>(r0, r1, h0, h1); }
-
-template cut_rectangle_result<Int> cut_rectangle_result<Int>::cut(bbox input, bbox hole);
-template cut_rectangle_result<float> cut_rectangle_result<float>::cut(bbox input, bbox hole);
+template<typename T> Cr<T> CutResult<T>::cut(bbox input, bbox hole) { return cut_rectangle<T>(input, hole); }
+template<typename T> Cr<T> CutResult<T>::cut(Vec2 r0, Vec2 r1, Vec2 h0, Vec2 h1) { return cut_rectangle<T>(r0, r1, h0, h1); }
 
-template cut_rectangle_result<Int> cut_rectangle_result<Int>::cut(Vector2i r0, Vector2i r1, Vector2i h0, Vector2i h1);
-template cut_rectangle_result<float> cut_rectangle_result<float>::cut(Vector2 r0, Vector2 r1, Vector2 h0, Vector2 h1);
+template struct CutResult<Int>;
+template struct CutResult<float>;
 
 } // namespace floormat
diff --git a/src/hole.hpp b/src/hole.hpp
index 384a5044..5e993072 100644
--- a/src/hole.hpp
+++ b/src/hole.hpp
@@ -56,17 +56,18 @@ private:
 };
 
 template<typename T>
-struct cut_rectangle_result // todo rename
+struct CutResult
 {
     using Vec2 = VectorTypeFor<2, T>;
     struct bbox { Vec2 position; Vector2ub bbox_size; };
     struct rect { Vec2 min, max; };
 
-    static cut_rectangle_result cut(bbox input, bbox hole);
-    static cut_rectangle_result cut(Vec2 r0, Vec2 r1, Vec2 h0, Vec2 h1);
+    static CutResult cut(bbox input, bbox hole);
+    static CutResult cut(Vec2 r0, Vec2 r1, Vec2 h0, Vec2 h1);
 
-    uint8_t size = 0;
     std::array<rect, 8> array;
+    uint8_t size = 0;
+    bool found = false;
 };
 
 } // namespace floormat
diff --git a/test/hole.cpp b/test/hole.cpp
index 8bfb8c8a..7ccc86c3 100644
--- a/test/hole.cpp
+++ b/test/hole.cpp
@@ -4,13 +4,13 @@
 namespace floormat {
 namespace {
 
-using bbox = cut_rectangle_result<Int>::bbox;
+using bbox = CutResult<Int>::bbox;
 
 auto cut(bbox rect, bbox hole, Vector2i offset)
 {
     auto rectʹ = bbox { rect.position + offset, rect.bbox_size };
     auto holeʹ = bbox { hole.position + offset, hole.bbox_size };
-    return cut_rectangle_result<Int>::cut(rectʹ, holeʹ).size;
+    return CutResult<Int>::cut(rectʹ, holeʹ).size;
 }
 
 void test1(Vector2i offset)