5 files changed, 278 insertions, 216 deletions

diff --git a/src/chunk-bbox.cpp b/src/chunk-bbox.cpp
new file mode 100644
index 00000000..78c10a4f
--- /dev/null
+++ b/src/chunk-bbox.cpp
@@ -0,0 +1,187 @@
+#include "chunk.hpp"
+#include "compat/LooseQuadtree-impl.h"
+#include "src/tile-atlas.hpp"
+#include "src/collision.hpp"
+#include <bit>
+#include <Magnum/Math/Vector4.h>
+
+namespace floormat {
+
+template<>
+struct chunk::insert_into_lqt<false>
+{
+    using BB = loose_quadtree::BoundingBox<std::int16_t>;
+    using TBBE = loose_quadtree::TrivialBBExtractor<std::int16_t>;
+    static BB* insert(const BB& bbox, std::vector<BB>& vec)
+    {
+        vec.push_back(bbox);
+        return &vec.back();
+    }
+};
+
+template<>
+struct chunk::insert_into_lqt<true>
+{
+    using BB = loose_quadtree::BoundingBox<std::int16_t>;
+    static compact_bb* insert(const BB& bbox, std::vector<void**>&)
+    {
+        if constexpr(sizeof(void*) >= sizeof(BB))
+            return std::bit_cast<compact_bb*>(bbox);
+        else
+            return {};
+    }
+};
+
+struct collision_bbox final
+{
+    using BB = loose_quadtree::BoundingBox<std::int16_t>;
+    operator BB() const noexcept;
+
+    std::int16_t left = 0, top = 0;
+    std::uint16_t width = 0, height = 0;
+    enum pass_mode pass_mode = pass_mode::pass;
+};
+
+collision_bbox::operator BB() const noexcept
+{
+    return { left, top, (std::int16_t)width, (std::int16_t)height };
+}
+
+static constexpr Vector2s tile_start(std::size_t k)
+{
+    const auto i = std::uint8_t(k);
+    const local_coords coord{i};
+    return sTILE_SIZE2 * Vector2s(coord.x, coord.y) - sTILE_SIZE2/2;
+}
+
+void chunk::ensure_passability() noexcept
+{
+    if (!_pass_modified)
+        return;
+    _pass_modified = false;
+
+    if (!_lqt_move)
+        _lqt_move = make_lqt();
+    if (!_lqt_shoot)
+        _lqt_shoot = make_lqt();
+    if (!_lqt_view)
+        _lqt_view = make_lqt();
+
+    _lqt_move->Clear();
+    _lqt_shoot->Clear();
+    _lqt_view->Clear();
+    _bboxes.clear();
+
+    std::vector<collision_bbox> bboxes; bboxes.reserve(TILE_COUNT*4);
+
+    constexpr auto whole_tile = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
+        auto start = tile_start(k);
+        return { start[0], start[1], usTILE_SIZE2[0], usTILE_SIZE2[1], p };
+    };
+
+    constexpr auto wall_north = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
+        auto start = tile_start(k) - Vector2s(0, 1);
+        return { start[0], start[1], usTILE_SIZE2[0], 2, p };
+    };
+
+    constexpr auto wall_west = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
+        auto start = tile_start(k) - Vector2s(1, 0);
+        return { start[0], start[1], 2, usTILE_SIZE2[1], p };
+    };
+
+    for (std::size_t i = 0; i < TILE_COUNT; i++)
+    {
+        const auto tile = const_cast<chunk&>(*this)[i];
+        if (auto s = tile.scenery())
+            if (auto p = s.frame.passability; p != pass_mode::pass)
+                bboxes.push_back(whole_tile(i, p));
+        if (auto atlas = tile.ground_atlas())
+            if (auto p = atlas->pass_mode(pass_mode::pass); p != pass_mode::pass)
+                bboxes.push_back(whole_tile(i, p));
+        if (auto atlas = tile.wall_north_atlas())
+            if (auto p = atlas->pass_mode(pass_mode::blocked); p != pass_mode::pass)
+                bboxes.push_back(wall_north(i, p));
+        if (auto atlas = tile.wall_west_atlas())
+            if (auto p = atlas->pass_mode(pass_mode::blocked); p != pass_mode::pass)
+                bboxes.push_back(wall_west(i, p));
+    }
+
+    if constexpr (!lqt_compact_bb)
+        _bboxes.reserve(bboxes.size());
+
+    for (const collision_bbox& bbox : bboxes)
+    {
+        auto* ptr = insert_into_lqt<lqt_compact_bb>::insert(bbox, _bboxes);
+
+        switch (bbox.pass_mode)
+        {
+        case pass_mode::blocked:
+            _lqt_view->Insert(ptr);
+            [[fallthrough]];
+        case pass_mode::see_through:
+            _lqt_shoot->Insert(ptr);
+            [[fallthrough]];
+        case pass_mode::shoot_through:
+            _lqt_move->Insert(ptr);
+            break;
+        case pass_mode::pass:
+            break;
+        }
+    }
+}
+
+auto chunk::query_collisions(Vector4s vec, collision type) const -> Query
+{
+    const_cast<chunk&>(*this).ensure_passability();
+    loose_quadtree::BoundingBox<std::int16_t> bbox { vec[0], vec[1], vec[2], vec[3] };
+    return { lqt_from_collision_type(type).QueryIntersectsRegion(bbox) };
+}
+
+auto chunk::query_collisions(Vector2s position, Vector2us size, collision type) const -> Query
+{
+    const_cast<chunk&>(*this).ensure_passability();
+    constexpr auto half = sTILE_SIZE2/2;
+    const auto start = position - half;
+    loose_quadtree::BoundingBox<std::int16_t> bbox {start[0], start[1], (Short)size[0], (Short)size[1] };
+    return { lqt_from_collision_type(type).QueryIntersectsRegion(bbox) };
+}
+
+auto chunk::query_collisions(local_coords p, Vector2us size, Vector2s offset, collision type) const -> Query
+{
+    const_cast<chunk&>(*this).ensure_passability();
+    const auto pos = Vector2s(p.x, p.y) * sTILE_SIZE2 + offset;
+    const auto start = pos - Vector2s(size/2);
+    loose_quadtree::BoundingBox<std::int16_t> bbox { start[0], start[1], (Short)size[0], (Short)size[1] };
+    return { lqt_from_collision_type(type).QueryIntersectsRegion(bbox) };
+}
+
+auto chunk::lqt_from_collision_type(collision type) const noexcept -> lqt&
+{
+    switch (type)
+    {
+    case collision::move:
+        return *_lqt_move;
+    case collision::shoot:
+        return *_lqt_shoot;
+    case collision::view:
+        return *_lqt_view;
+    }
+    fm_abort("wrong collision type '%hhu'", std::uint8_t(type));
+}
+
+auto chunk::make_lqt() -> std::unique_ptr<lqt>
+{
+    return std::make_unique<lqt>();
+}
+
+void chunk::cleanup_lqt()
+{
+    if (_lqt_move)
+        _lqt_move->ForceCleanup();
+    if (_lqt_shoot)
+        _lqt_shoot->ForceCleanup();
+    if (_lqt_view)
+        _lqt_view->ForceCleanup();
+}
+
+} // namespace floormat
diff --git a/src/chunk.cpp b/src/chunk.cpp
index f40480ee..cb9760e1 100644
--- a/src/chunk.cpp
+++ b/src/chunk.cpp
@@ -1,8 +1,6 @@
 #include "chunk.hpp"
-#include "compat/LooseQuadtree-impl.h"
-#include "src/collision.hpp"
 #include "src/tile-atlas.hpp"
-#include <Magnum/Math/Vector4.h>
+#include "compat/LooseQuadtree-impl.h"
 
 namespace floormat {
 
@@ -42,94 +40,13 @@ void chunk::mark_modified() noexcept
     mark_scenery_modified();
 }
 
-static constexpr auto tile_size2us = Vector2us(iTILE_SIZE2);
-
-static constexpr Vector2s tile_start(std::size_t k)
-{
-    const auto i = std::uint8_t(k);
-    const local_coords coord{i};
-    constexpr auto tile_size2s = Vector2s(tile_size2us), half = tile_size2s/2;
-    return tile_size2s * Vector2s(coord.x, coord.y) - half;
-}
-
-auto chunk::ensure_passability() noexcept -> lqt&
-{
-    auto& qt = *_static_lqt;
-
-    if (!_pass_modified)
-        return qt;
-    _pass_modified = false;
-
-    qt.Clear();
-    _lqt_bboxes.clear();
-    _lqt_bboxes.reserve(32);
-
-    constexpr auto whole_tile = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
-        auto start = tile_start(k);
-        return { start[0], start[1], tile_size2us[0], tile_size2us[1], p };
-    };
-
-    constexpr auto wall_north = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
-        auto start = tile_start(k) - Vector2s(0, 1);
-        return { start[0], start[1], tile_size2us[0], 2, p };
-    };
-
-    constexpr auto wall_west = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
-        auto start = tile_start(k) - Vector2s(1, 0);
-        return { start[0], start[1], 2, tile_size2us[1], p };
-    };
-
-    for (std::size_t i = 0; i < TILE_COUNT; i++)
-    {
-        const auto tile = const_cast<chunk&>(*this)[i];
-        if (auto s = tile.scenery())
-            if (auto p = s.frame.passability; p != pass_mode::pass)
-                _lqt_bboxes.push_back(whole_tile(i, p));
-        if (auto atlas = tile.ground_atlas())
-            if (auto p = atlas->pass_mode(pass_mode::pass); p != pass_mode::pass)
-                _lqt_bboxes.push_back(whole_tile(i, p));
-        if (auto atlas = tile.wall_north_atlas())
-            if (auto p = atlas->pass_mode(pass_mode::blocked); p != pass_mode::pass)
-                _lqt_bboxes.push_back(wall_north(i, p));
-        if (auto atlas = tile.wall_west_atlas())
-            if (auto p = atlas->pass_mode(pass_mode::blocked); p != pass_mode::pass)
-                _lqt_bboxes.push_back(wall_west(i, p));
-    }
-
-    for (auto& bbox : _lqt_bboxes)
-        qt.Insert(&bbox);
-
-    return qt;
-}
-
-using namespace loose_quadtree;
-
-collision_query chunk::query_collisions(Vector4s vec) const
-{
-    const_cast<chunk&>(*this).ensure_passability();
-    BoundingBox<std::int16_t> bbox { vec[0], vec[1], vec[2], vec[3] };
-    return { _static_lqt->QueryIntersectsRegion(bbox) };
-}
-
-collision_query chunk::query_collisions(Vector2s position, Vector2us size) const
-{
-    const_cast<chunk&>(*this).ensure_passability();
-    constexpr auto half = sTILE_SIZE2/2;
-    const auto start = position - half;
-    return query_collisions(Vector4s{start[0], start[1], (Short)size[0], (Short)size[1] });
-}
+chunk::chunk() noexcept = default;
 
-collision_query chunk::query_collisions(local_coords p, Vector2us size, Vector2s offset) const
+chunk::~chunk() noexcept
 {
-    const_cast<chunk&>(*this).ensure_passability();
-    const auto pos = Vector2s(p.x, p.y) * sTILE_SIZE2 + offset;
-    const auto start = pos - Vector2s(size/2);
-    BoundingBox<std::int16_t> bbox { start[0], start[1], (Short)size[0], (Short)size[1] };
-    return { _static_lqt->QueryIntersectsRegion(bbox) };
+    cleanup_lqt();
 }
 
-chunk::chunk() noexcept : _static_lqt { std::make_unique<lqt>() } {}
-chunk::~chunk() noexcept = default;
 chunk::chunk(chunk&&) noexcept = default;
 chunk& chunk::operator=(chunk&&) noexcept = default;
 
diff --git a/src/chunk.hpp b/src/chunk.hpp
index a560fa21..2d2a5c75 100644
--- a/src/chunk.hpp
+++ b/src/chunk.hpp
@@ -11,15 +11,22 @@
 namespace loose_quadtree {
 template<typename Number, typename Object, typename BBExtractor> class LooseQuadtree;
 template<typename Number, typename Object, typename BBExtractor> struct Query;
+template<typename Number> struct BoundingBox;
+template<typename Number> struct TrivialBBExtractor;
 } // namespace loose_quadtree
 
 namespace floormat {
 
 struct anim_atlas;
-struct collision_iterator;
+template<typename Num, typename BB, typename BBE> struct collision_iterator;
+template<typename Num, typename BB, typename BBE> struct collision_query;
 struct collision_bbox;
-struct collision_bb_extractor;
-struct collision_query;
+struct compact_bb;
+struct compact_bb_extractor;
+
+enum class collision : std::uint8_t {
+    view, shoot, move,
+};
 
 struct chunk final
 {
@@ -69,12 +76,18 @@ struct chunk final
     wall_mesh_tuple ensure_wall_mesh() noexcept;
     tile_atlas* wall_atlas_at(std::size_t i) const noexcept;
 
-    using lqt = loose_quadtree::LooseQuadtree<std::int16_t, collision_bbox, collision_bb_extractor>;
-    lqt& ensure_passability() noexcept;
+    void ensure_passability() noexcept;
+
+    static constexpr inline bool lqt_compact_bb = sizeof(void*) >= 8;
+    //static constexpr inline bool lqt_compact_bb = false;
+    using BB  = std::conditional_t<lqt_compact_bb, compact_bb, loose_quadtree::BoundingBox<std::int16_t>>;
+    using BBE = std::conditional_t<lqt_compact_bb, compact_bb_extractor, loose_quadtree::TrivialBBExtractor<std::int16_t>>;
+    using lqt = loose_quadtree::LooseQuadtree<std::int16_t, BB, BBE>;
+    using Query = collision_query<std::int16_t, BB, BBE>;
 
-    collision_query query_collisions(Vector2s position, Vector2us size) const;
-    collision_query query_collisions(local_coords p, Vector2us size, Vector2s offset = {}) const;
-    collision_query query_collisions(Vector4s vec) const;
+    Query query_collisions(Vector2s position, Vector2us size, collision type) const;
+    Query query_collisions(local_coords p, Vector2us size, Vector2s offset, collision type) const;
+    Query query_collisions(Vector4s vec, collision type) const;
 
 private:
     std::array<std::shared_ptr<tile_atlas>, TILE_COUNT> _ground_atlases;
@@ -86,8 +99,10 @@ private:
     std::array<std::shared_ptr<anim_atlas>, TILE_COUNT> _scenery_atlases;
     std::array<scenery, TILE_COUNT> _scenery_variants = {};
 
-    std::unique_ptr<lqt> _static_lqt;
-    std::vector<collision_bbox> _lqt_bboxes;
+    template<bool> struct insert_into_lqt;
+
+    std::unique_ptr<lqt> _lqt_move, _lqt_shoot, _lqt_view;
+    std::vector<std::conditional_t<lqt_compact_bb, void**, loose_quadtree::BoundingBox<std::int16_t>>> _bboxes;
 
     GL::Mesh ground_mesh{NoCreate}, wall_mesh{NoCreate};
     mutable bool _maybe_empty      : 1 = true,
@@ -95,6 +110,10 @@ private:
                  _walls_modified   : 1 = true,
                  _scenery_modified : 1 = true,
                  _pass_modified    : 1 = true;
+
+    lqt& lqt_from_collision_type(collision type) const noexcept;
+    static std::unique_ptr<lqt> make_lqt();
+    void cleanup_lqt();
 };
 
 } // namespace floormat
diff --git a/src/collision.cpp b/src/collision.cpp
index 1a9c0b3f..64f33c95 100644
--- a/src/collision.cpp
+++ b/src/collision.cpp
@@ -1,89 +1,12 @@
 #include "collision.hpp"
-#include "compat/assert.hpp"
-#include "src/chunk.hpp"
-#include "compat/LooseQuadtree-impl.h"
-#include <utility>
+#include <bit>
 
 namespace floormat {
 
-void collision_bb_extractor::ExtractBoundingBox(const collision_bbox* x, BB* bbox)
+void compact_bb_extractor::ExtractBoundingBox(compact_bb* object, BB* bbox)
 {
-    *bbox = { x->left, x->top, std::int16_t(x->width), std::int16_t(x->height) };
-}
-
-collision_iterator::collision_iterator() noexcept : q{nullptr} {}
-collision_iterator::collision_iterator(Query* q) noexcept : q{q} {}
-
-collision_iterator::~collision_iterator() noexcept
-{
-    if (q)
-        while (!q->EndOfQuery())
-            q->Next();
-}
-
-collision_iterator& collision_iterator::operator++() noexcept
-{
-    fm_debug_assert(q != nullptr && !q->EndOfQuery());
-    q->Next();
-    return *this;
-}
-
-auto collision_iterator::operator++(int) noexcept -> const collision_bbox*
-{
-    fm_debug_assert(q != nullptr && !q->EndOfQuery());
-    auto* bbox = q->GetCurrent();
-    fm_debug_assert(bbox != nullptr);
-    operator++();
-    return bbox;
-}
-
-auto collision_iterator::operator*() const noexcept -> const collision_bbox&
-{
-    return *operator->();
-}
-
-auto collision_iterator::operator->() const noexcept -> const collision_bbox*
-{
-    fm_debug_assert(q != nullptr && !q->EndOfQuery());
-    auto* ptr = q->GetCurrent();
-    fm_debug_assert(ptr != nullptr);
-    return ptr;
-}
-
-bool collision_iterator::operator==(const collision_iterator& other) const noexcept
-{
-    if (q && !other.q) [[likely]]
-        return q->EndOfQuery();
-    else if (!q && !other.q)
-        return true;
-    else if (!q)
-        return other.q->EndOfQuery();
-    else
-        return q == other.q;
-}
-
-collision_iterator::operator bool() const noexcept
-{
-    return q && !q->EndOfQuery();
-}
-
-collision_query::collision_query(collision_query::Query&& q) noexcept : q{std::move(q)} {}
-collision_iterator collision_query::begin() noexcept { return collision_iterator{&q}; }
-collision_iterator collision_query::end() noexcept { return collision_iterator{nullptr}; }
-
-collision_bbox::operator BB() const noexcept
-{
-    return BB{left, top, (Short)width, (Short)height};
-}
-
-bool collision_bbox::intersects(BB bb) const noexcept
-{
-    return BB(*this).Intersects(bb);
-}
-
-bool collision_bbox::intersects(collision_bbox bb) const noexcept
-{
-    return BB(*this).Intersects(bb);
+    if constexpr(sizeof(void*) >= 8)
+        *bbox = std::bit_cast<loose_quadtree::BoundingBox<std::int16_t>>((void*)object);
 }
 
 } // namespace floormat
diff --git a/src/collision.hpp b/src/collision.hpp
index adfec6b0..31be7c1f 100644
--- a/src/collision.hpp
+++ b/src/collision.hpp
@@ -5,59 +5,75 @@
 
 namespace floormat {
 
-struct collision_bbox final
-{
-    using BB = loose_quadtree::BoundingBox<std::int16_t>;
-
-    std::int16_t left, top;
-    std::uint16_t width, height;
-    enum pass_mode pass_mode;
-
-    constexpr collision_bbox();
-    constexpr collision_bbox(std::int16_t left, std::int16_t top, std::uint16_t width, std::uint16_t height, enum pass_mode p) noexcept;
-    operator BB() const noexcept;
-    bool intersects(BB bb) const noexcept;
-    bool intersects(collision_bbox bb) const noexcept;
-};
-
-constexpr collision_bbox::collision_bbox() :
-    left{0}, top{0}, width{0}, height{0}, pass_mode{pass_mode::pass}
-{}
-
-constexpr collision_bbox::collision_bbox(std::int16_t left, std::int16_t top, std::uint16_t width, std::uint16_t height, enum pass_mode p) noexcept :
-    left{left}, top{top}, width{width}, height{height}, pass_mode{p}
-{}
+struct compact_bb;
 
-struct collision_bb_extractor final
+struct compact_bb_extractor final
 {
     using BB = loose_quadtree::BoundingBox<std::int16_t>;
-    static void ExtractBoundingBox(const collision_bbox* object, BB* bbox);
+    [[maybe_unused]] static void ExtractBoundingBox(compact_bb* object, BB* bbox);
 };
 
+template<typename Num, typename BB, typename BBE>
 struct collision_iterator final
 {
-    using Query = typename loose_quadtree::LooseQuadtree<std::int16_t, collision_bbox, collision_bb_extractor>::Query;
+    using Query = typename loose_quadtree::LooseQuadtree<std::int16_t, BB, BBE>::Query;
 
-    explicit collision_iterator() noexcept;
-    explicit collision_iterator(Query* q) noexcept;
-    ~collision_iterator() noexcept;
-    collision_iterator& operator++() noexcept;
-    const collision_bbox* operator++(int) noexcept;
-    const collision_bbox& operator*() const noexcept;
-    const collision_bbox* operator->() const noexcept;
-    bool operator==(const collision_iterator& other) const noexcept;
-    operator bool() const noexcept;
+    explicit collision_iterator() noexcept : q{nullptr} {}
+    explicit collision_iterator(Query* q) noexcept : q{q} {}
+    ~collision_iterator() noexcept
+    {
+        if (q)
+            while (!q->EndOfQuery())
+                q->Next();
+    }
+    collision_iterator& operator++() noexcept
+    {
+        fm_debug_assert(q != nullptr && !q->EndOfQuery());
+        q->Next();
+        return *this;
+    }
+    const BB* operator++(int) noexcept
+    {
+        fm_debug_assert(q != nullptr && !q->EndOfQuery());
+        auto* bbox = q->GetCurrent();
+        fm_debug_assert(bbox != nullptr);
+        operator++();
+        return bbox;
+    }
+    const BB& operator*() const noexcept { return *operator->(); }
+    const BB* operator->() const noexcept
+    {
+        fm_debug_assert(q != nullptr && !q->EndOfQuery());
+        auto* ptr = q->GetCurrent();
+        fm_debug_assert(ptr != nullptr);
+        return ptr;
+    }
+    bool operator==(const collision_iterator& other) const noexcept
+    {
+        if (q && !other.q) [[likely]]
+            return q->EndOfQuery();
+        else if (!q && !other.q)
+            return true;
+        else if (!q)
+            return other.q->EndOfQuery();
+        else
+            return q == other.q;
+    }
+    operator bool() const noexcept { return q && !q->EndOfQuery(); }
 
 private:
     Query* q;
 };
 
+template<typename Num, typename BB, typename BBE>
 struct collision_query
 {
-    using Query = typename loose_quadtree::LooseQuadtree<std::int16_t, collision_bbox, collision_bb_extractor>::Query;
-    collision_query(Query&& q) noexcept;
-    collision_iterator begin() noexcept;
-    static collision_iterator end() noexcept;
+    using Query = typename loose_quadtree::LooseQuadtree<Num, BB, BBE>::Query;
+    collision_query(Query&& q) noexcept : q{std::move(q)} {}
+    ~collision_query() noexcept { while (!q.EndOfQuery()) q.Next(); }
+    collision_iterator<Num, BB, BBE> begin() noexcept { return collision_iterator<Num, BB, BBE>{&q}; }
+    static collision_iterator<Num, BB, BBE> end() noexcept { return collision_iterator<Num, BB, BBE>{nullptr}; }
+    operator bool() const noexcept { return !q.EndOfQuery(); }
 
 private:
     Query q;