kill lqt

14 files changed, 3 insertions, 2602 deletions

diff --git a/compat/LooseQuadtree-impl.h b/compat/LooseQuadtree-impl.h
deleted file mode 100644
index 26bddac1..00000000
--- a/compat/LooseQuadtree-impl.h
+++ /dev/null
@@ -1,1286 +0,0 @@
-#pragma once
-
-#include "LooseQuadtree.h"
-#include "compat/assert.hpp"
-#undef assert
-#define assert(...) fm_debug_assert(__VA_ARGS__)
-
-#include <array>
-#include <cstddef>
-#include <deque>
-#include <forward_list>
-#include <limits>
-#include <map>
-#include <memory>
-#include <unordered_map>
-#include <type_traits>
-#include <vector>
-
-#ifdef __GNUG__
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wfloat-equal"
-#endif
-
-namespace loose_quadtree::detail {
-
-
-
-#define LQT_USE_OWN_ALLOCATOR
-
-
-class BlocksAllocator {
-public:
-    static constexpr std::size_t kBlockAlign = alignof(long double);
-    static constexpr std::size_t kBlockSize = 16384;
-    static constexpr std::size_t kMaxAllowedAlloc = sizeof(void*) * 8;
-
-    BlocksAllocator();
-    ~BlocksAllocator();
-    BlocksAllocator(const BlocksAllocator&) = delete;
-    BlocksAllocator& operator=(const BlocksAllocator&) = delete;
-
-    void* Allocate(std::size_t object_size);
-    void Deallocate(void* p, std::size_t object_size);
-    void ReleaseFreeBlocks();
-    template <typename T, typename... Args>
-    T* New(Args&&... args);
-    template <typename T>
-    void Delete(T* p);
-
-private:
-    struct Block {
-        alignas(kBlockAlign) unsigned char data[kBlockSize];
-    };
-
-    //template <std::size_t kSizeT>
-    //union Slot {
-    //  Slot* next_empty_slot;
-    //  std::array<char, kSizeT> data;
-    //};
-
-    using BlocksAndEmptySlots = std::map<Block*, std::size_t>;
-
-    struct BlocksHead {
-        BlocksAndEmptySlots address_to_empty_slot_number;
-        void* first_empty_slot;
-        std::size_t slots_in_a_block_;
-
-        BlocksHead(std::size_t object_size) :
-            first_empty_slot(nullptr),
-            slots_in_a_block_(kBlockSize / object_size)
-        {
-        }
-    };
-
-    std::map<std::size_t, BlocksHead> size_to_blocks_;
-};
-
-
-template <typename T>
-struct BlocksAllocatorAdaptor {
-    using value_type = T;
-    using pointer = T*;
-    using const_pointer = const T*;
-    using reference = T&;
-    using const_reference = const T&;
-    using size_type = std::size_t;
-    using difference_type = std::ptrdiff_t;
-    template<typename U>
-    struct rebind {using other = BlocksAllocatorAdaptor<U>;};
-
-    BlocksAllocatorAdaptor(BlocksAllocator& allocator);
-    template <typename U>
-    BlocksAllocatorAdaptor(const BlocksAllocatorAdaptor<U>& other);
-    template <typename U>
-    BlocksAllocatorAdaptor& operator=(const BlocksAllocatorAdaptor<U>& other);
-
-    pointer address(reference r) const {return &r;}
-    const_pointer address(const_reference r) const {return &r;}
-    size_type max_size() const {return std::numeric_limits<size_type>::max();}
-    template <typename U, typename... Args>
-    void construct(U* p, Args&&... args) {
-        new((void*)p) U(std::forward<Args>(args)...);
-    }
-    template <typename U>
-    void destroy(U* p) {
-        p->~U();
-    }
-
-    T* allocate(std::size_t n);
-    void deallocate(T* p, std::size_t n);
-
-    BlocksAllocator* allocator_;
-};
-
-
-
-template <typename T, typename... Args>
-T* BlocksAllocator::New(Args&&... args) {
-    return new(Allocate(sizeof(T))) T(std::forward<Args>(args)...);
-}
-
-
-template <typename T>
-void BlocksAllocator::Delete(T* p) {
-    p->~T();
-    Deallocate(p, sizeof(T));
-}
-
-
-template <typename T>
-BlocksAllocatorAdaptor<T>::BlocksAllocatorAdaptor(BlocksAllocator& allocator)
-    : allocator_(&allocator) {
-}
-
-template <typename T>
-template <typename U>
-BlocksAllocatorAdaptor<T>::BlocksAllocatorAdaptor(const BlocksAllocatorAdaptor<U>& other)
-    : allocator_(other.allocator_) {
-}
-
-template <typename T>
-template <typename U>
-BlocksAllocatorAdaptor<T>&
-BlocksAllocatorAdaptor<T>::operator=(const BlocksAllocatorAdaptor<U>& other) {
-    allocator_ = other.allocator_;
-}
-
-template <typename T>
-T* BlocksAllocatorAdaptor<T>::allocate(std::size_t n) {
-    if (sizeof(T) <= BlocksAllocator::kMaxAllowedAlloc && n == 1) {
-        return reinterpret_cast<T*>(allocator_->Allocate(sizeof(T)));
-    }
-    else {
-        return reinterpret_cast<T*>(new char[sizeof(T) * n]);
-    }
-}
-
-template <typename T>
-void BlocksAllocatorAdaptor<T>::deallocate(T* p, std::size_t n) {
-    if (sizeof(T) <= BlocksAllocator::kMaxAllowedAlloc && n == 1) {
-        allocator_->Deallocate(p, sizeof(T));
-    }
-    else {
-        delete[] reinterpret_cast<char*>(p);
-    }
-}
-
-
-
-
-
-
-template <typename NumberT>
-struct MakeDistance { using Type = typename std::make_unsigned<NumberT>::type;};
-
-template <>
-struct MakeDistance<float> { using Type = float;};
-
-template <>
-struct MakeDistance<double> { using Type = double;};
-
-template <>
-struct MakeDistance<long double> { using Type = long double;};
-
-
-
-enum class ChildPosition {
-    kNone,
-    kTopLeft,
-    kTopRight,
-    kBottomRight,
-    kBottomLeft,
-};
-
-
-
-template <typename ObjectT>
-struct TreeNode {
-    using Object = ObjectT;
-    using ObjectContainer =
-        std::forward_list<Object*, BlocksAllocatorAdaptor<Object*>>;
-
-    TreeNode(BlocksAllocator& allocator) :
-        top_left(nullptr), top_right(nullptr), bottom_right(nullptr),
-        bottom_left(nullptr), objects(BlocksAllocatorAdaptor<Object*>(allocator))
-    {}
-
-    TreeNode<Object>* top_left;
-    TreeNode<Object>* top_right;
-    TreeNode<Object>* bottom_right;
-    TreeNode<Object>* bottom_left;
-    ObjectContainer objects;
-};
-
-
-
-template <typename NumberT, typename ObjectT>
-class ForwardTreeTraversal {
-public:
-    using Number = NumberT;
-    using Object = ObjectT;
-
-    struct TreePosition {
-        TreePosition(const BoundingBox<Number>& _bbox, TreeNode<Object>* _node) :
-            bounding_box(_bbox), node(_node),
-            current_child(ChildPosition::kNone)
-        {
-        }
-
-        BoundingBox<Number> bounding_box;
-        TreeNode<Object>* node;
-        ChildPosition current_child;
-    };
-
-    ForwardTreeTraversal();
-    void StartAt(TreeNode<Object>* root, const BoundingBox<Number>& root_bounds);
-    int GetDepth() const; ///< starting from 0
-    TreeNode<Object>* GetNode() const;
-    const BoundingBox<Number>& GetNodeBoundingBox() const;
-    void GoTopLeft();
-    void GoTopRight();
-    void GoBottomRight();
-    void GoBottomLeft();
-
-protected:
-    TreePosition position_;
-    int depth_;
-};
-
-
-
-template <typename NumberT, typename ObjectT>
-class FullTreeTraversal : public ForwardTreeTraversal<NumberT, ObjectT> {
-public:
-    using Number = NumberT;
-    using Object = ObjectT;
-    using typename ForwardTreeTraversal<Number, Object>::TreePosition;
-
-    void StartAt(TreeNode<Object>* root, const BoundingBox<Number>& root_bounds);
-    ChildPosition GetNodeCurrentChild() const;
-    void SetNodeCurrentChild(ChildPosition child_position);
-    void GoUp();
-    void GoTopLeft();
-    void GoTopRight();
-    void GoBottomRight();
-    void GoBottomLeft();
-
-private:
-    using ForwardTreeTraversal<Number, Object>::position_;
-    using ForwardTreeTraversal<Number, Object>::depth_;
-
-    std::vector<TreePosition> position_stack_;
-};
-
-
-
-} // namespace loose_quadtree::detail
-
-namespace loose_quadtree {
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-class LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl {
-public:
-    enum class QueryType {kIntersects, kInside, kContains, kEndOfQuery};
-
-    Impl();
-    void Acquire(typename LooseQuadtree<Number, Object, BoundingBoxExtractor>::Impl* quadtree,
-        const BoundingBox<Number>* query_region, QueryType query_type);
-    void Release();
-    bool IsAvailable() const;
-    bool EndOfQuery() const;
-    Object* GetCurrent() const;
-    void Next();
-
-private:
-    enum class FitType {kNoFit = 0, kPartialFit, kFreeRide};
-
-    bool CurrentObjectFits() const;
-    FitType CurrentNodeFits() const;
-
-    typename LooseQuadtree<Number, Object, BoundingBoxExtractor>::Impl* quadtree_;
-    detail::FullTreeTraversal<Number, Object> traversal_;
-    typename detail::TreeNode<Object>::ObjectContainer::iterator object_iterator_;
-    typename detail::TreeNode<Object>::ObjectContainer::iterator object_iterator_before_;
-    BoundingBox<Number> query_region_;
-    QueryType query_type_;
-    int free_ride_from_level_;
-};
-
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-class LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl {
-public:
-    constexpr static int kInternalMinDepth = 4;
-    constexpr static int kInternalMaxDepth = (sizeof(long long) * 8 - 1) / 2;
-    constexpr static Number kMinimalObjectExtent =
-        std::is_integral<Number>::value ? 1 :
-            std::numeric_limits<Number>::min() * 16;
-
-    Impl();
-    ~Impl();
-    Impl(const Impl&) = delete;
-    Impl& operator=(const Impl&) = delete;
-
-    bool Insert(Object* object);
-    bool Update(Object* object);
-    bool Remove(Object* object);
-    bool Contains(Object* object) const;
-    Query QueryIntersectsRegion(const BoundingBox<Number>& region);
-    Query QueryInsideRegion(const BoundingBox<Number>& region);
-    Query QueryContainsRegion(const BoundingBox<Number>& region);
-    const BoundingBox<Number>& GetBoundingBox() const; ///< loose sense bounds
-    int GetSize() const;
-    void Clear();
-    void ForceCleanup();
-
-private:
-    friend class Query::Impl;
-    using ObjectPointerContainer =
-        std::unordered_map<Object*, Object**,
-        std::hash<Object*>, std::equal_to<Object*>,
-        detail::BlocksAllocatorAdaptor<std::pair<Object *const, Object**>>>;
-    using QueryPoolContainer =
-        std::deque<typename LooseQuadtree<Number, Object, BoundingBoxExtractor>::Query::Impl>;
-
-    void RecalculateMaximalDepth();
-    void DeleteTree();
-    Object** InsertIntoTree(Object* object);
-    typename Query::Impl* GetAvailableQueryFromPool();
-
-    detail::BlocksAllocator allocator_;
-    detail::TreeNode<Object>* root_;
-    BoundingBox<Number> bounding_box_;
-    ObjectPointerContainer object_pointers_;
-    int number_of_objects_;
-    int maximal_depth_;
-    detail::FullTreeTraversal<Number, Object> internal_traversal_;
-    QueryPoolContainer query_pool_;
-    int running_queries_; ///< queries which are opened and not at their end
-};
-
-
-
-template <typename NumberT>
-bool BoundingBox<NumberT>::Intersects(const BoundingBox<Number>& other) const {
-    return !(
-        left + width <= other.left || other.left + other.width <= left ||
-        top + height <= other.top || other.top + other.height <= top
-        );
-}
-
-template <typename NumberT>
-bool BoundingBox<NumberT>::Contains(const BoundingBox<Number>& other)  const {
-    return left <= other.left && left + width >= other.left + other.width &&
-        top <= other.top && top + height >= other.top + other.height;
-}
-
-template <typename NumberT>
-bool BoundingBox<NumberT>::Contains(Number x, Number y) const {
-    return left <= x && x < left + width &&
-        top <= y && y < top + height;
-}
-
-
-
-template <typename NumberT, typename ObjectT>
-detail::ForwardTreeTraversal<NumberT, ObjectT>::ForwardTreeTraversal() :
-    position_(BoundingBox<Number>(0, 0, 0, 0), nullptr), depth_(0) {
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::ForwardTreeTraversal<NumberT, ObjectT>::StartAt(TreeNode<Object>* root, const BoundingBox<Number>& root_bounds) {
-    position_.bounding_box = root_bounds;
-    position_.node = root;
-    depth_ = 0;
-}
-
-template <typename NumberT, typename ObjectT>
-int detail::ForwardTreeTraversal<NumberT, ObjectT>::GetDepth() const {
-    return depth_;
-}
-
-template <typename NumberT, typename ObjectT>
-detail::TreeNode<ObjectT>* detail::ForwardTreeTraversal<NumberT, ObjectT>::GetNode() const {
-    return position_.node;
-}
-
-template <typename NumberT, typename ObjectT>
-const BoundingBox<NumberT>& detail::ForwardTreeTraversal<NumberT, ObjectT>::GetNodeBoundingBox() const {
-    return position_.bounding_box;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::ForwardTreeTraversal<NumberT, ObjectT>::GoTopLeft() {
-    BoundingBox<Number>& bbox = position_.bounding_box;
-    bbox.width = (Number)((typename MakeDistance<Number>::Type)bbox.width / 2);
-    bbox.height = (Number)((typename MakeDistance<Number>::Type)bbox.height / 2);
-    position_.node = position_.node->top_left;
-    assert(position_.node != nullptr);
-    depth_++;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::ForwardTreeTraversal<NumberT, ObjectT>::GoTopRight() {
-    BoundingBox<Number>& bbox = position_.bounding_box;
-    Number right = (Number)(bbox.left + bbox.width);
-    bbox.left = (Number)(bbox.left +
-            (Number)((typename MakeDistance<Number>::Type)bbox.width / 2));
-    bbox.width = (Number)(right - bbox.left);
-    bbox.height = (Number)((typename MakeDistance<Number>::Type)bbox.height / 2);
-    position_.node = position_.node->top_right;
-    assert(position_.node != nullptr);
-    depth_++;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::ForwardTreeTraversal<NumberT, ObjectT>::GoBottomRight() {
-    BoundingBox<Number>& bbox = position_.bounding_box;
-    Number right = (Number)(bbox.left + bbox.width);
-    bbox.left = (Number)(bbox.left +
-            (Number)((typename MakeDistance<Number>::Type)bbox.width / 2));
-    bbox.width = (Number)(right - bbox.left);
-    Number bottom = (Number)(bbox.top + bbox.height);
-    bbox.top = (Number)(bbox.top +
-            (Number)((typename MakeDistance<Number>::Type)bbox.height / 2));
-    bbox.height = (Number)(bottom - bbox.top);
-    position_.node = position_.node->bottom_right;
-    assert(position_.node != nullptr);
-    depth_++;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::ForwardTreeTraversal<NumberT, ObjectT>::GoBottomLeft() {
-    BoundingBox<Number>& bbox = position_.bounding_box;
-    bbox.width = (Number)((typename MakeDistance<Number>::Type)bbox.width / 2);
-    Number bottom = (Number)(bbox.top + bbox.height);
-    bbox.top = (Number)(bbox.top +
-            (Number)((typename MakeDistance<Number>::Type)bbox.height / 2));
-    bbox.height = (Number)(bottom - bbox.top);
-    position_.node = position_.node->bottom_left;
-    assert(position_.node != nullptr);
-    depth_++;
-}
-
-
-
-template <typename NumberT, typename ObjectT>
-void detail::FullTreeTraversal<NumberT, ObjectT>::StartAt(TreeNode<Object>* root, const BoundingBox<Number>& root_bounds) {
-    ForwardTreeTraversal<Number, Object>::StartAt(root, root_bounds);
-    position_.current_child = ChildPosition::kNone;
-    position_stack_.clear();
-}
-
-template <typename NumberT, typename ObjectT>
-detail::ChildPosition detail::FullTreeTraversal<NumberT, ObjectT>::GetNodeCurrentChild() const {
-    return position_.current_child;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::FullTreeTraversal<NumberT, ObjectT>::SetNodeCurrentChild(ChildPosition child_position) {
-    position_.current_child = child_position;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::FullTreeTraversal<NumberT, ObjectT>::GoTopLeft() {
-    assert((size_t)depth_ == position_stack_.size());
-    position_.current_child = ChildPosition::kTopLeft;
-    position_stack_.emplace_back(position_);
-    ForwardTreeTraversal<Number, Object>::GoTopLeft();
-    position_.current_child = ChildPosition::kNone;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::FullTreeTraversal<NumberT, ObjectT>::GoTopRight() {
-    assert((size_t)depth_ == position_stack_.size());
-    position_.current_child = ChildPosition::kTopRight;
-    position_stack_.emplace_back(position_);
-    ForwardTreeTraversal<Number, Object>::GoTopRight();
-    position_.current_child = ChildPosition::kNone;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::FullTreeTraversal<NumberT, ObjectT>::GoBottomRight() {
-    assert((size_t)depth_ == position_stack_.size());
-    position_.current_child = ChildPosition::kBottomRight;
-    position_stack_.emplace_back(position_);
-    ForwardTreeTraversal<Number, Object>::GoBottomRight();
-    position_.current_child = ChildPosition::kNone;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::FullTreeTraversal<NumberT, ObjectT>::GoBottomLeft() {
-    assert((size_t)depth_ == position_stack_.size());
-    position_.current_child = ChildPosition::kBottomLeft;
-    position_stack_.emplace_back(position_);
-    ForwardTreeTraversal<Number, Object>::GoBottomLeft();
-    position_.current_child = ChildPosition::kNone;
-}
-
-template <typename NumberT, typename ObjectT>
-void detail::FullTreeTraversal<NumberT, ObjectT>::GoUp() {
-    assert((size_t)depth_ == position_stack_.size() && depth_ > 0);
-    position_ = position_stack_.back();
-    depth_--;
-    position_stack_.pop_back();
-}
-
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::Impl() : quadtree_(nullptr), query_region_(0,0,0,0),
-    query_type_(QueryType::kEndOfQuery),
-    free_ride_from_level_(LooseQuadtree<Number, Object, BoundingBoxExtractor>::Impl::kInternalMaxDepth) {
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::Acquire(typename LooseQuadtree<Number, Object, BoundingBoxExtractor>::Impl* quadtree,
-        const BoundingBox<Number>* query_region, QueryType query_type) {
-    assert(IsAvailable());
-    assert(query_type != QueryType::kEndOfQuery);
-    quadtree_ = quadtree;
-    query_region_ = *query_region;
-    query_type_ = query_type;
-    free_ride_from_level_ =
-        LooseQuadtree<Number, Object, BoundingBoxExtractor>::Impl::kInternalMaxDepth;
-    if (quadtree->root_ == nullptr) {
-        query_type_ = QueryType::kEndOfQuery;
-    }
-    else {
-        quadtree_->running_queries_++;
-        traversal_.StartAt(quadtree->root_, quadtree->bounding_box_);
-        object_iterator_ = traversal_.GetNode()->objects.before_begin();
-        Next();
-    }
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::Release() {
-    assert(!IsAvailable());
-    quadtree_ = nullptr;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::IsAvailable() const {
-    return quadtree_ == nullptr;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::EndOfQuery() const {
-    assert(!IsAvailable());
-    return query_type_ == QueryType::kEndOfQuery;
-}
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-ObjectT* LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::GetCurrent() const {
-    assert(!IsAvailable());
-    assert(!EndOfQuery());
-    return *object_iterator_;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::Next() {
-    assert(!IsAvailable());
-    assert(!EndOfQuery());
-    do {
-        object_iterator_before_ = object_iterator_;
-        object_iterator_++;
-        if (object_iterator_ == traversal_.GetNode()->objects.end()) {
-            do {
-                switch (traversal_.GetNodeCurrentChild()) {
-                case detail::ChildPosition::kNone:
-                    if (traversal_.GetNode()->top_left == nullptr) {
-                        traversal_.SetNodeCurrentChild(detail::ChildPosition::kTopLeft);
-                        continue;
-                    }
-                    else {
-                        traversal_.GoTopLeft();
-                    }
-                    break;
-                case detail::ChildPosition::kTopLeft:
-                    if (traversal_.GetNode()->top_right == nullptr) {
-                        traversal_.SetNodeCurrentChild(detail::ChildPosition::kTopRight);
-                        continue;
-                    }
-                    else {
-                        traversal_.GoTopRight();
-                    }
-                    break;
-                case detail::ChildPosition::kTopRight:
-                    if (traversal_.GetNode()->bottom_right == nullptr) {
-                        traversal_.SetNodeCurrentChild(detail::ChildPosition::kBottomRight);
-                        continue;
-                    }
-                    else {
-                        traversal_.GoBottomRight();
-                    }
-                    break;
-                case detail::ChildPosition::kBottomRight:
-                    if (traversal_.GetNode()->bottom_left == nullptr) {
-                        traversal_.SetNodeCurrentChild(detail::ChildPosition::kBottomLeft);
-                        continue;
-                    }
-                    else {
-                        traversal_.GoBottomLeft();
-                    }
-                    break;
-                case detail::ChildPosition::kBottomLeft:
-
-#ifndef NDEBUG
-                    int running_queries = 0;
-                    for (auto& query : quadtree_->query_pool_) {
-                        if (!query.IsAvailable() && !query.EndOfQuery()) running_queries++;
-                    }
-                    assert(running_queries == quadtree_->running_queries_);
-#endif
-
-                    //only run this if no parallel queries are running
-                    if (traversal_.GetDepth() > quadtree_->maximal_depth_ &&
-                            quadtree_->running_queries_ == 1) {
-                        typename detail::TreeNode<Object>::ObjectContainer& objects =
-                                traversal_.GetNode()->objects;
-                        auto iterator = objects.begin();
-                        while (iterator != objects.end()) {
-                            if (*iterator != nullptr) {
-                                quadtree_->Update(*iterator);
-                                assert(*iterator == nullptr);
-                            }
-                            iterator++;
-                        }
-                        objects.clear();
-                    }
-
-                    if (traversal_.GetDepth() > 0) {
-                        bool remove_node = (traversal_.GetNode()->objects.empty() &&
-                                traversal_.GetNode()->top_left == nullptr &&
-                                traversal_.GetNode()->top_right == nullptr &&
-                                traversal_.GetNode()->bottom_right == nullptr &&
-                                traversal_.GetNode()->bottom_left == nullptr);
-                        detail::TreeNode<Object>* node = traversal_.GetNode();
-                        traversal_.GoUp();
-
-                        // if the node is empty no other queries can be invalidated by deleting
-                        if (remove_node) {
-                            switch (traversal_.GetNodeCurrentChild()) {
-                            case detail::ChildPosition::kTopLeft:
-                                traversal_.GetNode()->top_left = nullptr;
-                                break;
-                            case detail::ChildPosition::kTopRight:
-                                traversal_.GetNode()->top_right = nullptr;
-                                break;
-                            case detail::ChildPosition::kBottomRight:
-                                traversal_.GetNode()->bottom_right = nullptr;
-                                break;
-                            case detail::ChildPosition::kBottomLeft:
-                                traversal_.GetNode()->bottom_left = nullptr;
-                                break;
-                            case detail::ChildPosition::kNone:
-                                assert(false);
-                            }
-                            quadtree_->allocator_.Delete(node);
-                        }
-
-                        if (free_ride_from_level_ == traversal_.GetDepth() + 1) {
-                            free_ride_from_level_ =
-                                LooseQuadtree<Number, Object,
-                                    BoundingBoxExtractor>::Impl::kInternalMaxDepth;
-                        }
-                        continue;
-                    }
-                    else {
-                        // if the root is empty no other queries can be invalidated by deleting
-                        if (traversal_.GetNode()->objects.empty() &&
-                                traversal_.GetNode()->top_left == nullptr &&
-                                traversal_.GetNode()->top_right == nullptr &&
-                                traversal_.GetNode()->bottom_right == nullptr &&
-                                traversal_.GetNode()->bottom_left == nullptr) {
-                            assert(traversal_.GetNode() == quadtree_->root_);
-                            assert(quadtree_->GetSize() == 0);
-                            assert(quadtree_->object_pointers_.size() == 0);
-                            quadtree_->allocator_.Delete(quadtree_->root_);
-                            quadtree_->root_ = nullptr;
-                            quadtree_->bounding_box_ = BoundingBox<Number>(0,0,0,0);
-                        }
-
-                        quadtree_->running_queries_--;
-                        query_type_ = QueryType::kEndOfQuery;
-                        return;
-                    }
-                    break;
-                }
-                assert(traversal_.GetNodeCurrentChild() == detail::ChildPosition::kNone);
-                {
-                    FitType fit = FitType::kPartialFit;
-                    if (traversal_.GetDepth() >= free_ride_from_level_ ||
-                            (fit = CurrentNodeFits()) != FitType::kNoFit) {
-                        if (fit == FitType::kFreeRide) {
-                            free_ride_from_level_ = traversal_.GetDepth();
-                        }
-                    }
-                    else {
-                        traversal_.SetNodeCurrentChild(detail::ChildPosition::kBottomLeft);
-                        continue;
-                    }
-                }
-                object_iterator_ = traversal_.GetNode()->objects.before_begin();
-                break;
-            } while (true);
-        }
-        else if (*object_iterator_ == nullptr) {
-            // other queries also cannot stop on an empty object,
-            // so we are not invalidating any iterators/queries with this
-            traversal_.GetNode()->objects.erase_after(object_iterator_before_);
-            object_iterator_ = object_iterator_before_;
-        }
-        else {
-            if (traversal_.GetDepth() >= free_ride_from_level_ ||
-                    CurrentObjectFits()) {
-                break;
-            }
-        }
-    } while (true);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::CurrentObjectFits() const {
-    BoundingBox<Number> object_bounds(0,0,0,0);
-    BoundingBoxExtractor::ExtractBoundingBox(GetCurrent(), &object_bounds);
-    switch (query_type_) {
-    case QueryType::kIntersects:
-        return query_region_.Intersects(object_bounds);
-    case QueryType::kInside:
-        return query_region_.Contains(object_bounds);
-    case QueryType::kContains:
-        return object_bounds.Contains(query_region_);
-    case QueryType::kEndOfQuery:
-        assert(false);
-    }
-    return false;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Impl::CurrentNodeFits() const -> FitType {
-    const BoundingBox<Number>& node_bounds = traversal_.GetNodeBoundingBox();
-    BoundingBox<Number> extended_bounds = node_bounds;
-    Number half_width =
-        (Number)((typename detail::MakeDistance<Number>::Type)node_bounds.width / 2);
-    Number half_height =
-        (Number)((typename detail::MakeDistance<Number>::Type)node_bounds.height / 2);
-    extended_bounds.width = (Number)(extended_bounds.width * 2);
-    extended_bounds.height = (Number)(extended_bounds.height * 2);
-    extended_bounds.left = (Number)(extended_bounds.left - half_width);
-    extended_bounds.top = (Number)(extended_bounds.top - half_height);
-    switch (query_type_) {
-    case QueryType::kIntersects:
-        if (!query_region_.Intersects(extended_bounds)) {
-            return FitType::kNoFit;
-        }
-        else if (query_region_.Contains(node_bounds)) {
-            return FitType::kFreeRide;
-        }
-        return FitType::kPartialFit;
-    case QueryType::kInside:
-        if (!query_region_.Intersects(node_bounds)) {
-            return FitType::kNoFit;
-        }
-        else if (query_region_.Contains(extended_bounds)) {
-            return FitType::kFreeRide;
-        }
-        return FitType::kPartialFit;
-    case QueryType::kContains:
-        if (!extended_bounds.Contains(query_region_)) {
-            return FitType::kNoFit;
-        }
-        return FitType::kPartialFit;
-    case QueryType::kEndOfQuery:
-        assert(false);
-    }
-    return FitType::kNoFit;
-}
-
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::Impl() :
-    root_(nullptr), bounding_box_(0, 0, 0, 0),
-    object_pointers_(64, std::hash<Object*>(), std::equal_to<Object*>(),
-        detail::BlocksAllocatorAdaptor<std::pair<const Object*, Object**>>(allocator_)),
-    number_of_objects_(0), maximal_depth_(kInternalMinDepth),
-    running_queries_(0) {
-    assert(maximal_depth_ < kInternalMaxDepth);
-    //object_pointers_.reserve(64);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::~Impl() {
-    DeleteTree();
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::Insert(Object* object) {
-    bool was_removed = Remove(object);
-    Object** place = InsertIntoTree(object);
-    object_pointers_.emplace(object, place);
-    number_of_objects_++;
-    RecalculateMaximalDepth();
-    return !was_removed;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::Update(Object* object) {
-    return !Insert(object);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::Remove(Object* object) {
-    auto it = object_pointers_.find(object);
-    if (it != object_pointers_.end()) {
-        assert(*(it->second) == it->first);
-        *(it->second) = nullptr;
-        object_pointers_.erase(it);
-        number_of_objects_--;
-        RecalculateMaximalDepth();
-        return true;
-    }
-    return false;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::Contains(Object* object) const {
-    return object_pointers_.find(object) != object_pointers_.end();
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::QueryIntersectsRegion(const BoundingBox<Number>& region) -> Query {
-    typename Query::Impl* query_impl = GetAvailableQueryFromPool();
-    query_impl->Acquire(this, &region, Query::Impl::QueryType::kIntersects);
-    return Query(query_impl);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::QueryInsideRegion(const BoundingBox<Number>& region) -> Query {
-    typename Query::Impl* query_impl = GetAvailableQueryFromPool();
-    query_impl->Acquire(this, &region, Query::Impl::QueryType::kInside);
-    return Query(query_impl);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::QueryContainsRegion(const BoundingBox<Number>& region) -> Query {
-    typename Query::Impl* query_impl = GetAvailableQueryFromPool();
-    query_impl->Acquire(this, &region, Query::Impl::QueryType::kContains);
-    return Query(query_impl);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-const BoundingBox<NumberT>& LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::GetBoundingBox() const {
-    return bounding_box_;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::ForceCleanup() {
-    Query query = QueryIntersectsRegion(bounding_box_);
-    while (!query.EndOfQuery()) {
-        query.Next();
-    }
-    allocator_.ReleaseFreeBlocks();
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-int LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::GetSize() const {
-    return number_of_objects_;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::Clear() {
-    DeleteTree();
-}
-
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::RecalculateMaximalDepth() {
-    do {
-        if (maximal_depth_ < kInternalMaxDepth &&
-                number_of_objects_ > 1ll << (maximal_depth_ << 1)) {
-            maximal_depth_++;
-        }
-        else if (maximal_depth_ > kInternalMinDepth &&
-                number_of_objects_ <= 1ll << ((maximal_depth_ - 1) << 1)) {
-            maximal_depth_--;
-        }
-        else {
-            break;
-        }
-    } while (true);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::DeleteTree() {
-    object_pointers_.clear();
-    detail::FullTreeTraversal<Number, Object>& trav = internal_traversal_;
-    trav.StartAt(root_, bounding_box_);
-    while (root_ != nullptr) {
-        assert(trav.GetDepth() >= 0 && trav.GetDepth() <= kInternalMaxDepth);
-        detail::TreeNode<Object>* node = trav.GetNode();
-        if (node->top_left != nullptr) {
-            trav.GoTopLeft();
-        }
-        else if (node->top_right != nullptr) {
-            trav.GoTopRight();
-        }
-        else if (node->bottom_right != nullptr) {
-            trav.GoBottomRight();
-        }
-        else if (node->bottom_left != nullptr) {
-            trav.GoBottomLeft();
-        }
-        else {
-            if (trav.GetDepth() > 0) {
-                trav.GoUp();
-                switch (trav.GetNodeCurrentChild()) {
-                case detail::ChildPosition::kNone:
-                    assert(false);
-                    break;
-                case detail::ChildPosition::kTopLeft:
-                    assert(node == trav.GetNode()->top_left);
-                    trav.GetNode()->top_left = nullptr;
-                    break;
-                case detail::ChildPosition::kTopRight:
-                    assert(node == trav.GetNode()->top_right);
-                    trav.GetNode()->top_right = nullptr;
-                    break;
-                case detail::ChildPosition::kBottomRight:
-                    assert(node == trav.GetNode()->bottom_right);
-                    trav.GetNode()->bottom_right = nullptr;
-                    break;
-                case detail::ChildPosition::kBottomLeft:
-                    assert(node == trav.GetNode()->bottom_left);
-                    trav.GetNode()->bottom_left = nullptr;
-                    break;
-                }
-                allocator_.Delete(node);
-            }
-            else {
-                assert(node == root_);
-                allocator_.Delete(root_);
-                root_ = nullptr;
-            }
-        }
-    }
-
-    bounding_box_ = BoundingBox<Number>(0, 0, 0, 0);
-    number_of_objects_ = 0;
-    maximal_depth_ = kInternalMinDepth;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-ObjectT** LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::InsertIntoTree(Object* object) {
-    BoundingBox<Number> object_bounds(0,0,0,0);
-    BoundingBoxExtractor::ExtractBoundingBox(object, &object_bounds);
-    assert(object_bounds.width >= 0);
-    assert(object_bounds.height >= 0);
-    assert(object_bounds.left <= object_bounds.left + object_bounds.width);
-    assert(object_bounds.top <= object_bounds.top + object_bounds.height);
-    Number maximal_object_extent = object_bounds.width >= object_bounds.height ?
-        object_bounds.width : object_bounds.height;
-    if (maximal_object_extent < kMinimalObjectExtent) {
-        maximal_object_extent = kMinimalObjectExtent;
-    }
-    Number object_center_x = (Number)(object_bounds.left +
-        (Number)((typename detail::MakeDistance<Number>::Type)object_bounds.width / 2));
-    Number object_center_y = (Number)(object_bounds.top +
-        (Number)((typename detail::MakeDistance<Number>::Type)object_bounds.height / 2));
-
-    if (root_ != nullptr) {
-        assert(number_of_objects_ >= 0);
-        assert(bounding_box_.width > 0);
-        assert(bounding_box_.width == bounding_box_.height);
-
-        int depth_increase = 0;
-        while (!bounding_box_.Contains(object_center_x, object_center_y) ||
-                maximal_object_extent > bounding_box_.width) {
-            Number previous_size = bounding_box_.width;
-            bounding_box_.width = (Number)(bounding_box_.width * 2);
-            bounding_box_.height = bounding_box_.width;
-            Number previous_half =
-                (Number)((typename detail::MakeDistance<Number>::Type)previous_size / 2);
-            Number bb_center_x = (Number)(bounding_box_.left + previous_half);
-            Number bb_center_y = (Number)(bounding_box_.top + previous_half);
-            detail::TreeNode<Object>* old_root = root_;
-            root_ = allocator_.New<detail::TreeNode<Object>>(allocator_);
-            if (object_center_x <= bb_center_x) {
-                bounding_box_.left = (Number)(bounding_box_.left - previous_size);
-                if (object_center_y <= bb_center_y) {
-                    bounding_box_.top = (Number)(bounding_box_.top - previous_size);
-                    root_->bottom_right = old_root;
-                }
-                else {
-                    root_->top_right = old_root;
-                }
-            }
-            else {
-                if (object_center_y <= bb_center_y) {
-                    bounding_box_.top = (Number)(bounding_box_.top - previous_size);
-                    root_->bottom_left = old_root;
-                }
-                else {
-                    root_->top_left = old_root;
-                }
-            }
-            depth_increase++;
-            assert(depth_increase < kInternalMaxDepth);
-            (void)depth_increase;
-            assert(bounding_box_.left < bounding_box_.left + bounding_box_.width);
-            assert(bounding_box_.top < bounding_box_.top + bounding_box_.height);
-            // If this happens with integral types you are close to get out of bounds
-            // The bounding box of things should be at least 1/8 of the total interval spanned
-            assert(!std::is_integral<Number>::value ||
-                bounding_box_.width < std::numeric_limits<Number>::max() / 8 * 7);
-            assert(!std::is_integral<Number>::value ||
-                bounding_box_.height < std::numeric_limits<Number>::max() / 8 * 7);
-        }
-
-        detail::ForwardTreeTraversal<Number, Object> trav;
-        trav.StartAt(root_, bounding_box_);
-        do {
-            const BoundingBox<Number>& node_bounds = trav.GetNodeBoundingBox();
-            assert(node_bounds.Contains(object_center_x, object_center_y));
-            Number maximal_bb_extent =
-                    node_bounds.width >= node_bounds.height ?
-                        node_bounds.width : node_bounds.height;
-            Number half_bb_extent =
-                (Number)((typename detail::MakeDistance<Number>::Type)maximal_bb_extent / 2);
-            assert(maximal_object_extent <= maximal_bb_extent);
-
-            if (maximal_object_extent > half_bb_extent ||
-                    trav.GetDepth() >= maximal_depth_) {
-                break;
-            }
-
-            Number node_center_x = (Number)(node_bounds.left +
-                (Number)((typename detail::MakeDistance<Number>::Type)node_bounds.width / 2));
-            Number node_center_y = (Number)(node_bounds.top +
-                (Number)((typename detail::MakeDistance<Number>::Type)node_bounds.height / 2));
-
-            detail::TreeNode<Object>** direction;
-            if (object_center_x < node_center_x) {
-                if (object_center_y < node_center_y) {
-                    direction = &trav.GetNode()->top_left;
-                }
-                else {
-                    direction = &trav.GetNode()->bottom_left;
-                }
-            }
-            else {
-                if (object_center_y < node_center_y) {
-                    direction = &trav.GetNode()->top_right;
-                }
-                else {
-                    direction = &trav.GetNode()->bottom_right;
-                }
-            }
-
-            if (*direction == nullptr) {
-                *direction = allocator_.New<detail::TreeNode<Object>>(allocator_);
-            }
-
-            if (*direction == trav.GetNode()->top_left) {
-                trav.GoTopLeft();
-            }
-            else if (*direction == trav.GetNode()->top_right) {
-                trav.GoTopRight();
-            }
-            else if (*direction == trav.GetNode()->bottom_right) {
-                trav.GoBottomRight();
-            }
-            else {
-                assert(*direction == trav.GetNode()->bottom_left);
-                trav.GoBottomLeft();
-            }
-        } while (true);
-
-#ifndef NDEBUG
-        BoundingBox<Number> effective_bounds = trav.GetNodeBoundingBox();
-        Number half_width =
-            (Number)((typename detail::MakeDistance<Number>::Type)effective_bounds.width / 2);
-        Number half_height =
-            (Number)((typename detail::MakeDistance<Number>::Type)effective_bounds.height / 2);
-        effective_bounds.width = (Number)(effective_bounds.width * 2);
-        effective_bounds.height = (Number)(effective_bounds.height * 2);
-        effective_bounds.left = (Number)(effective_bounds.left - half_width);
-        effective_bounds.top = (Number)(effective_bounds.top - half_height);
-        assert(effective_bounds.Contains(object_bounds));
-#endif
-
-        typename detail::TreeNode<Object>::ObjectContainer& objects =
-                trav.GetNode()->objects;
-        if (!objects.empty() && objects.front() == nullptr) {
-            objects.front() = object;
-        }
-        else {
-            objects.emplace_front(object);
-        }
-        return &objects.front();
-    }
-    else {
-        assert(number_of_objects_ == 0);
-        {
-            bounding_box_.width =
-                (Number)((typename detail::MakeDistance<Number>::Type)maximal_object_extent * 2 * 7 / 8);
-            bounding_box_.height = bounding_box_.width;
-            Number extent_half =
-                (Number)((typename detail::MakeDistance<Number>::Type)bounding_box_.width / 2);
-            bounding_box_.left = (Number)(object_center_x - extent_half);
-            bounding_box_.top = (Number)(object_center_y - extent_half);
-            assert(bounding_box_.left < bounding_box_.left + bounding_box_.width);
-            assert(bounding_box_.top < bounding_box_.top + bounding_box_.height);
-        }
-        root_ = allocator_.New<detail::TreeNode<Object>>(allocator_);
-        root_->objects.emplace_front(object);
-        return &root_->objects.front();
-    }
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Impl::GetAvailableQueryFromPool() -> typename Query::Impl* {
-    for (auto it = query_pool_.begin(); it != query_pool_.end(); it++) {
-        if (it->IsAvailable()) {
-            return &*it;
-        }
-    }
-    query_pool_.emplace_back();
-    assert(query_pool_.back().IsAvailable());
-    return &query_pool_.back();
-}
-
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Insert(Object* object) {
-    return impl_.Insert(object);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Update(Object* object) {
-    return impl_.Update(object);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Remove(Object* object) {
-    return impl_.Remove(object);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Contains(Object* object) const {
-    return impl_.Contains(object);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::QueryIntersectsRegion(const BoundingBox<Number>& region) -> Query {
-    return impl_.QueryIntersectsRegion(region);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::QueryInsideRegion(const BoundingBox<Number>& region) -> Query {
-    return impl_.QueryInsideRegion(region);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::QueryContainsRegion(const BoundingBox<Number>& region) -> Query {
-    return impl_.QueryContainsRegion(region);
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-const BoundingBox<NumberT>&
-    LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::GetLooseBoundingBox() const {
-    return impl_.GetBoundingBox();
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::ForceCleanup() {
-    impl_.ForceCleanup();
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-int LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::GetSize() const {
-    return impl_.GetSize();
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::IsEmpty() const {
-    return impl_.GetSize() == 0;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Clear() {
-    impl_.Clear();
-}
-
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Query(Impl* pimpl) : pimpl_(pimpl) {
-    assert(pimpl_ != nullptr);
-    assert(!pimpl_->IsAvailable());
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::~Query() {
-    if (pimpl_ != nullptr) {
-        pimpl_->Release();
-        assert(pimpl_->IsAvailable());
-        pimpl_ = nullptr;
-    }
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Query(Query&& other) noexcept : pimpl_(other.pimpl_) {
-    other.pimpl_ = nullptr;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-auto LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::operator=(Query&& other) noexcept -> Query& {
-    this->~Query();
-    pimpl_ = other.pimpl_;
-    other.pimpl_ = nullptr;
-    return *this;
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-bool LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::EndOfQuery() const {
-    return pimpl_->EndOfQuery();
-}
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-ObjectT* LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::GetCurrent() const {
-    return pimpl_->GetCurrent();
-}
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-void LooseQuadtree<NumberT, ObjectT, BoundingBoxExtractorT>::Query::Next() {
-    pimpl_->Next();
-}
-
-
-template <typename Src>
-struct TrivialBBExtractor {
-    template<typename Dst = Src>
-    static void ExtractBoundingBox(const BoundingBox<Src> *object, BoundingBox<Dst> *bbox)
-    {
-        bbox->left = object->left;
-        bbox->top = object->top;
-        bbox->width = object->width;
-        bbox->height = object->height;
-    }
-};
-
-} // namespace loose_quadtree
-
-#ifdef __GNUG__
-#pragma GCC diagnostic pop
-#endif
-
-#undef assert
diff --git a/compat/LooseQuadtree.LICENSE b/compat/LooseQuadtree.LICENSE
deleted file mode 100644
index 4edbdc84..00000000
--- a/compat/LooseQuadtree.LICENSE
+++ /dev/null
@@ -1,22 +0,0 @@
-The MIT License (MIT)
-
-Copyright (c) 2015 Zoltán Gera
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all
-copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-SOFTWARE.
-
diff --git a/compat/LooseQuadtree.cpp b/compat/LooseQuadtree.cpp
deleted file mode 100644
index 7017b0ac..00000000
--- a/compat/LooseQuadtree.cpp
+++ /dev/null
@@ -1,140 +0,0 @@
-#include "LooseQuadtree-impl.h"
-#include "compat/assert.hpp"
-#undef assert
-#define assert fm_assert
-
-namespace loose_quadtree::detail {
-
-BlocksAllocator::BlocksAllocator() {}
-
-
-BlocksAllocator::~BlocksAllocator() {
-    for (auto& size_block_pair : size_to_blocks_) {
-        BlocksHead& blocks_head = size_block_pair.second;
-        for (auto& address_empty_pair : blocks_head.address_to_empty_slot_number) {
-            assert(address_empty_pair.second == blocks_head.slots_in_a_block_);
-            Block* block = address_empty_pair.first;
-            delete block;
-        }
-    }
-}
-
-
-void* BlocksAllocator::Allocate(std::size_t object_size) {
-#ifdef LQT_USE_OWN_ALLOCATOR
-    if (object_size < sizeof(void*)) object_size = sizeof(void*);
-    assert(object_size <= kMaxAllowedAlloc);
-    auto size_blocks_it = size_to_blocks_.find(object_size);
-    if (size_blocks_it == size_to_blocks_.end()) {
-        size_blocks_it = size_to_blocks_.emplace(object_size, object_size).first;
-    }
-    BlocksHead& blocks_head = size_blocks_it->second;
-    assert(blocks_head.slots_in_a_block_ == kBlockSize / object_size);
-    if (blocks_head.first_empty_slot == nullptr) {
-        Block* new_block = new Block();
-        std::size_t empties = blocks_head.slots_in_a_block_;
-        blocks_head.address_to_empty_slot_number.emplace(new_block, empties);
-        blocks_head.first_empty_slot = reinterpret_cast<void*>(new_block);
-        void* current_slot = reinterpret_cast<void*>(new_block);
-        empties--;
-        while (empties > 0) {
-            void* next_slot =
-                reinterpret_cast<void*>(reinterpret_cast<char*>(current_slot)
-                        + object_size);
-            *reinterpret_cast<void**>(current_slot) = next_slot;
-            current_slot = next_slot;
-            empties--;
-        }
-        *reinterpret_cast<void**>(current_slot) = nullptr;
-    }
-    assert(blocks_head.first_empty_slot != nullptr);
-    void* slot = blocks_head.first_empty_slot;
-    blocks_head.first_empty_slot = *reinterpret_cast<void**>(slot);
-    auto address_empties_it =
-        blocks_head.address_to_empty_slot_number.upper_bound(reinterpret_cast<Block*>(slot));
-    assert(address_empties_it != blocks_head.address_to_empty_slot_number.begin());
-    address_empties_it--;
-    assert(address_empties_it->first <= reinterpret_cast<Block*>(slot) &&
-        (std::size_t)(reinterpret_cast<char*>(slot) -
-            reinterpret_cast<char*>(address_empties_it->first)) < kBlockSize);
-    assert((std::size_t)(reinterpret_cast<char*>(slot) -
-        reinterpret_cast<char*>(address_empties_it->first)) % object_size == 0);
-    assert(address_empties_it->second > 0 &&
-            address_empties_it->second <= blocks_head.slots_in_a_block_);
-    address_empties_it->second--;
-    return slot;
-#else
-    return reinterpret_cast<void*>(new char[object_size]);
-#endif
-}
-
-
-void BlocksAllocator::Deallocate(void* p, std::size_t object_size) {
-#ifdef LQT_USE_OWN_ALLOCATOR
-    if (object_size < sizeof(void*)) object_size = sizeof(void*);
-    assert(object_size <= kMaxAllowedAlloc);
-    auto size_blocks_it = size_to_blocks_.find(object_size);
-    assert(size_blocks_it != size_to_blocks_.end());
-    BlocksHead& blocks_head = size_blocks_it->second;
-    assert(blocks_head.slots_in_a_block_ == kBlockSize / object_size);
-    auto address_empties_it =
-        blocks_head.address_to_empty_slot_number.upper_bound(reinterpret_cast<Block*>(p));
-    assert(address_empties_it != blocks_head.address_to_empty_slot_number.begin());
-    address_empties_it--;
-    assert(address_empties_it->first <= reinterpret_cast<Block*>(p) &&
-        (std::size_t)(reinterpret_cast<char*>(p) -
-            reinterpret_cast<char*>(address_empties_it->first)) < kBlockSize);
-    assert((std::size_t)(reinterpret_cast<char*>(p) -
-        reinterpret_cast<char*>(address_empties_it->first)) % object_size == 0);
-    assert(address_empties_it->second < blocks_head.slots_in_a_block_);
-    void* slot = p;
-    *reinterpret_cast<void**>(slot) = blocks_head.first_empty_slot;
-    blocks_head.first_empty_slot = slot;
-    address_empties_it->second++;
-    assert(address_empties_it->second > 0 &&
-            address_empties_it->second <= blocks_head.slots_in_a_block_);
-#else
-    (void)object_size;
-    delete[] reinterpret_cast<char*>(p);
-#endif
-}
-
-
-void BlocksAllocator::ReleaseFreeBlocks() {
-    for (auto& size_block_pair : size_to_blocks_) {
-        BlocksHead& blocks_head = size_block_pair.second;
-        void** current = &blocks_head.first_empty_slot;
-        while (*current != nullptr) {
-            auto address_empties_it =
-                blocks_head.address_to_empty_slot_number.upper_bound(reinterpret_cast<Block*>(*current));
-            assert(address_empties_it != blocks_head.address_to_empty_slot_number.begin());
-            address_empties_it--;
-            assert(address_empties_it->first <= reinterpret_cast<Block*>(*current) &&
-                (std::size_t)(reinterpret_cast<char*>(*current) -
-                    reinterpret_cast<char*>(address_empties_it->first)) < kBlockSize);
-            assert((std::size_t)(reinterpret_cast<char*>(*current) -
-                reinterpret_cast<char*>(address_empties_it->first)) % size_block_pair.first == 0);
-            assert(address_empties_it->second > 0 &&
-                    address_empties_it->second <= blocks_head.slots_in_a_block_);
-            if (address_empties_it->second >= blocks_head.slots_in_a_block_) {
-                *current = **(void***)current;
-            }
-            else {
-                current = *(void***)current;
-            }
-        }
-        auto address_empties_it = blocks_head.address_to_empty_slot_number.begin();
-        while (address_empties_it != blocks_head.address_to_empty_slot_number.end()) {
-            if (address_empties_it->second >= blocks_head.slots_in_a_block_) {
-                auto prev_address_empties_it = address_empties_it;
-                address_empties_it++;
-                blocks_head.address_to_empty_slot_number.erase(prev_address_empties_it);
-            }
-            else {
-                address_empties_it++;
-            }
-        }
-    }
-}
-
-} // namespace loose_quadtree::detail
diff --git a/compat/LooseQuadtree.h b/compat/LooseQuadtree.h
deleted file mode 100644
index 507a92fa..00000000
--- a/compat/LooseQuadtree.h
+++ /dev/null
@@ -1,112 +0,0 @@
-#pragma once
-/**
- * LooseQuadtree written by Zozo
- * use freely under MIT license
- *
- * Loose quadtree (unlike normal quadtrees which are for points only) is
- * a region tree designed to store bounding boxes effectively
- * See boost::geometry::index::rtree for a more advanced, general solution!
- *
- * This implementation features:
- * - Fully adaptive behavior, adjusts its bounds, height and memory on demand
- * - Every object will be stored on the level to which its size corresponds to
- * - Gives theoretically optimal search results (see previous)
- * - Uses tree structure instead of hashed (smaller memory footprint, cache friendly)
- * - Uses as much data in-place as it can (by using its own allocator)
- * - Allocates memory in big chunks
- * - Uses axis-aligned bounding boxes for calculations
- * - Uses left-top-width-height bounds for better precision (no right-bottom)
- * - Uses left-top closed right-bottom open interval logic (for integral types)
- * - Uses X-towards-right Y-towards-bottom screen-like coordinate system
- * - It is suitable for both floating- and fixed-point logic
- * - This library is not thread-safe but multiple queries can be run at once
- *
- * Generic parameters are:
- * - Src generic number type allows its floating- and fixed-point usage
- * - ObjectT* only pointer is stored, no object copying is done, not an inclusive container
- * - BoundingBoxExtractorT allows using your own bounding box type/source, needs
- *     BoundingBoxExtractor::ExtractBoundingBox(ObjectT* in, BoundingBox<Number>* out) implemented
- */
-
-
-
-namespace loose_quadtree {
-
-
-
-template <typename NumberT>
-struct BoundingBox {
-    using Number = NumberT;
-
-    constexpr BoundingBox(Number _left, Number _top, Number _width, Number _height) :
-        left(_left), top(_top), width(_width), height(_height) {}
-    bool Intersects(const BoundingBox<Number>& other) const ;
-    bool Contains(const BoundingBox<Number>& other) const;
-    bool Contains(Number x, Number y) const;
-    BoundingBox& operator=(const BoundingBox&) noexcept = default;
-    BoundingBox(const BoundingBox&) noexcept = default;
-
-    Number left;
-    Number top;
-    Number width;
-    Number height;
-};
-
-
-
-template <typename NumberT, typename ObjectT, typename BoundingBoxExtractorT>
-class LooseQuadtree {
-public:
-    using Number = NumberT;
-    using Object = ObjectT;
-    using BoundingBoxExtractor = BoundingBoxExtractorT;
-
-private:
-    class Impl;
-
-public:
-    class Query {
-    public:
-        ~Query();
-        Query() = delete;
-        Query(const Query&) = delete;
-        Query& operator=(const Query&) = delete;
-        Query(Query&&) noexcept;
-        Query& operator=(Query&&) noexcept;
-
-        bool EndOfQuery() const;
-        Object* GetCurrent() const;
-        void Next();
-
-    private:
-        friend class LooseQuadtree<Number, Object, BoundingBoxExtractor>::Impl;
-        class Impl;
-        Query(Impl* pimpl);
-        Impl* pimpl_;
-    };
-
-    LooseQuadtree() = default;
-    ~LooseQuadtree() = default;
-    LooseQuadtree(const LooseQuadtree&) = delete;
-    LooseQuadtree& operator=(const LooseQuadtree&) = delete;
-
-    bool Insert(Object* object); ///< true if it was inserted (else updated)
-    bool Update(Object* object); ///< true if it was updated (else inserted)
-    bool Remove(Object* object); ///< true if it was removed
-    bool Contains(Object* object) const; ///< true if object is in tree
-    Query QueryIntersectsRegion(const BoundingBox<Number>& region);
-    Query QueryInsideRegion(const BoundingBox<Number>& region);
-    Query QueryContainsRegion(const BoundingBox<Number>& region);
-    const BoundingBox<Number>& GetLooseBoundingBox() const;
-    ///< double its size to get a bounding box including everything contained for sure
-    int GetSize() const;
-    bool IsEmpty() const;
-    void Clear();
-    void ForceCleanup(); ///< does a full data structure and memory cleanup
-    ///< cleanup is semi-automatic during queries so you needn't call this normally
-
-private:
-    Impl impl_;
-};
-
-} //loose_quadtree
diff --git a/editor/draw.cpp b/editor/draw.cpp
index baf7f135..4e175ab4 100644
--- a/editor/draw.cpp
+++ b/editor/draw.cpp
@@ -7,7 +7,6 @@
 #include "draw/anim.hpp"
 #include "src/camera-offset.hpp"
 #include "src/world.hpp"
-#include "src/collision.hpp"
 #include <Magnum/Math/Color.h>
 #include <Magnum/Math/Vector3.h>
 
@@ -61,6 +60,7 @@ void app::draw_cursor()
 
 void app::draw_collision_boxes()
 {
+#if 0
     const auto [minx, maxx, miny, maxy] = M->get_draw_bounds();
     const auto sz = M->window_size();
     auto& world = M->world();
@@ -97,6 +97,7 @@ void app::draw_collision_boxes()
             }
         }
     shader.set_tint({1, 1, 1, 1});
+#endif
 }
 
 void app::draw()
diff --git a/src/chunk-bbox.cpp b/src/chunk-bbox.cpp
deleted file mode 100644
index 52be8635..00000000
--- a/src/chunk-bbox.cpp
+++ /dev/null
@@ -1,171 +0,0 @@
-#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 {
-
-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();
-
-    std::vector<collision_bbox> bboxes;
-    _bboxes.clear();
-    bboxes.reserve(TILE_COUNT*4);
-
-    constexpr auto scenery_tile = [](std::size_t k, pass_mode p, const scenery& sc) constexpr -> collision_bbox {
-      constexpr auto half = sTILE_SIZE2/2;
-      auto center = tile_start(k) + Vector2s(sc.bbox_offset) + half;
-      auto size = Vector2us(sc.bbox_size)*2;
-      auto start = center - Vector2s(sc.bbox_size);
-      return { start[0], start[1], size[0], size[1], p };
-    };
-
-    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(); s && s.frame.passability != pass_mode::pass)
-            if (auto bb = scenery_tile(i, s.frame.passability, s.frame); bb.width && bb.height)
-                bboxes.push_back(bb);
-        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));
-    }
-
-    _bboxes.reserve(bboxes.size());
-
-    for (const collision_bbox& bbox : bboxes)
-    {
-        _bboxes.push_back(bbox);
-        auto* ptr = &_bboxes.back();
-
-        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<float> 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<float> 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<float> 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.get();
-    case collision::shoot:
-        return _lqt_shoot.get();
-    case collision::view:
-        return _lqt_view.get();
-    }
-    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 94506f1a..033e1831 100644
--- a/src/chunk.cpp
+++ b/src/chunk.cpp
@@ -1,6 +1,5 @@
 #include "chunk.hpp"
 #include "src/tile-atlas.hpp"
-#include "compat/LooseQuadtree-impl.h"
 
 namespace floormat {
 
@@ -42,11 +41,7 @@ void chunk::mark_modified() noexcept
 }
 
 chunk::chunk() noexcept = default;
-
-chunk::~chunk() noexcept
-{
-    cleanup_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 2f257c38..9dd0f117 100644
--- a/src/chunk.hpp
+++ b/src/chunk.hpp
@@ -8,21 +8,10 @@
 #include <memory>
 #include <Magnum/GL/Mesh.h>
 
-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;
 
-template<typename Num, typename BB, typename BBE> struct collision_iterator;
-template<typename Num, typename BB, typename BBE> struct collision_query;
-struct collision_bbox;
-
 enum class collision : std::uint8_t {
     view, shoot, move,
 };
@@ -88,17 +77,6 @@ struct chunk final
 
     void ensure_passability() noexcept;
 
-    using BB = loose_quadtree::BoundingBox<std::int16_t>;
-    using BBE = loose_quadtree::TrivialBBExtractor<std::int16_t>;
-    using lqt = loose_quadtree::LooseQuadtree<float, BB, BBE>;
-    using Query = collision_query<float, BB, BBE>;
-
-    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;
-
-    lqt* lqt_from_collision_type(collision type) const noexcept;
-
 private:
     std::array<std::shared_ptr<tile_atlas>, TILE_COUNT> _ground_atlases;
     std::array<std::uint8_t, TILE_COUNT> ground_indexes = {};
@@ -110,17 +88,12 @@ private:
     std::array<std::uint8_t, TILE_COUNT> scenery_indexes = {};
     std::array<scenery, TILE_COUNT> _scenery_variants = {};
 
-    std::unique_ptr<lqt> _lqt_move, _lqt_shoot, _lqt_view;
-    std::vector<loose_quadtree::BoundingBox<std::int16_t>> _bboxes;
-
     GL::Mesh ground_mesh{NoCreate}, wall_mesh{NoCreate}, scenery_mesh{NoCreate};
     mutable bool _maybe_empty      : 1 = true,
                  _ground_modified  : 1 = true,
                  _walls_modified   : 1 = true,
                  _scenery_modified : 1 = true,
                  _pass_modified    : 1 = true;
-    static std::unique_ptr<lqt> make_lqt();
-    void cleanup_lqt();
 };
 
 } // namespace floormat
diff --git a/src/collision.cpp b/src/collision.cpp
deleted file mode 100644
index e2e4974d..00000000
--- a/src/collision.cpp
+++ /dev/null
@@ -1,6 +0,0 @@
-#include "collision.hpp"
-#include <bit>
-
-namespace floormat {
-
-} // namespace floormat
diff --git a/src/collision.hpp b/src/collision.hpp
deleted file mode 100644
index 0568cc39..00000000
--- a/src/collision.hpp
+++ /dev/null
@@ -1,73 +0,0 @@
-#pragma once
-#include "compat/LooseQuadtree-impl.h"
-#include "src/pass-mode.hpp"
-
-namespace floormat {
-
-template<typename Num, typename BB, typename BBE>
-struct collision_iterator final
-{
-    using Query = typename loose_quadtree::LooseQuadtree<Num, BB, BBE>::Query;
-
-    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<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;
-};
-
-} // namespace floormat
diff --git a/test/app.hpp b/test/app.hpp
index 46ea3fc0..b3787826 100644
--- a/test/app.hpp
+++ b/test/app.hpp
@@ -28,8 +28,6 @@ struct test_app final : private FM_APPLICATION
     static void test_const_math();
     static void test_serializer();
     static void test_entity();
-    static void test_quadtree();
     static void test_loader();
-    static void test_bbox();
 };
 } // namespace floormat
diff --git a/test/bbox.cpp b/test/bbox.cpp
deleted file mode 100644
index 9ffd6122..00000000
--- a/test/bbox.cpp
+++ /dev/null
@@ -1,25 +0,0 @@
-#include "app.hpp"
-#include "src/chunk.hpp"
-#include "src/collision.hpp"
-#include <Magnum/Math/Vector2.h>
-#include <Magnum/Math/Vector4.h>
-
-namespace floormat {
-
-void test_app::test_bbox()
-{
-    auto c = make_test_chunk();
-
-    constexpr auto pos1 = sTILE_SIZE2 * (TILE_MAX_DIM/2) - Vector2s(0, sTILE_SIZE2[1]/2);
-    constexpr auto b1 = Vector4s{pos1[0], pos1[1], sTILE_SIZE2[0], sTILE_SIZE2[1]};
-    constexpr auto pos2 = Vector2s(iTILE_SIZE2 * (Vector2i(TILE_MAX_DIM/2) - Vector2i(-1, -1)) - Vector2i(0, iTILE_SIZE[1]/2));
-    constexpr auto b2 = Vector4s{pos2[0], pos2[1], usTILE_SIZE2[0], usTILE_SIZE2[1]};
-    {
-        auto q1 = c.query_collisions(b1, collision::move);
-        fm_assert(q1);
-        auto q2 = c.query_collisions(b2, collision::move);
-        fm_assert(!q2);
-    }
-}
-
-} // namespace floormat
diff --git a/test/main.cpp b/test/main.cpp
index 305c4926..c01f09f0 100644
--- a/test/main.cpp
+++ b/test/main.cpp
@@ -25,8 +25,6 @@ int test_app::exec()
     test_serializer();
     test_entity();
     test_loader();
-    test_bbox();
-    test_quadtree();
     return 0;
 }
 
diff --git a/test/quadtree.cpp b/test/quadtree.cpp
deleted file mode 100644
index f1a3ab6f..00000000
--- a/test/quadtree.cpp
+++ /dev/null
@@ -1,729 +0,0 @@
-#if defined __GNUG__ || defined __CLION_IDE__
-#pragma GCC diagnostic ignored "-Wfloat-equal"
-#endif
-#ifdef _MSC_VER
-#pragma warning(disable : 4244)
-#endif
-#define ASSERT fm_assert
-
-#include "compat/LooseQuadtree.h"
-#include "compat/LooseQuadtree-impl.h"
-#include "compat/assert.hpp"
-#include "src/collision.hpp"
-#include "test/app.hpp"
-
-#include <chrono>
-#include <cstdint>
-#include <cstdio>
-#include <random>
-#include <vector>
-
-using namespace loose_quadtree;
-
-namespace {
-
-template <typename NumberT>
-void TestBoundingBox() {
-    BoundingBox<NumberT> big(100, 100, 200, 50);
-    BoundingBox<NumberT> small_inside(200, 125, 5, 5);
-    BoundingBox<NumberT> edge_inside(110, 110, 190, 40);
-    BoundingBox<NumberT> edge_outside(300, 150, 20, 5);
-    BoundingBox<NumberT> intersecting1(290, 90, 29, 25);
-    BoundingBox<NumberT> intersecting2(290, 110, 29, 25);
-    BoundingBox<NumberT> outside(290, 210, 29, 25);
-
-    ASSERT(big.Contains(100, 100));
-    ASSERT(!big.Contains(300, 150));
-
-    ASSERT(big.Contains(big));
-    ASSERT(big.Contains(small_inside));
-    ASSERT(!small_inside.Contains(big));
-    ASSERT(big.Contains(edge_inside));
-    ASSERT(!edge_inside.Contains(big));
-    ASSERT(!big.Contains(edge_outside));
-    ASSERT(!edge_outside.Contains(big));
-    ASSERT(!big.Contains(intersecting1));
-    ASSERT(!intersecting1.Contains(big));
-    ASSERT(!big.Contains(intersecting2));
-    ASSERT(!intersecting1.Contains(big));
-    ASSERT(!intersecting1.Contains(intersecting2));
-    ASSERT(!big.Contains(outside));
-    ASSERT(!outside.Contains(big));
-
-    ASSERT(big.Intersects(big));
-    ASSERT(big.Intersects(small_inside));
-    ASSERT(small_inside.Intersects(big));
-    ASSERT(big.Intersects(edge_inside));
-    ASSERT(edge_inside.Intersects(big));
-    ASSERT(!big.Intersects(edge_outside));
-    ASSERT(!edge_outside.Intersects(big));
-    ASSERT(big.Intersects(intersecting1));
-    ASSERT(intersecting1.Intersects(big));
-    ASSERT(big.Intersects(intersecting2));
-    ASSERT(intersecting2.Intersects(big));
-    ASSERT(intersecting1.Intersects(intersecting2));
-    ASSERT(!big.Intersects(outside));
-    ASSERT(!outside.Intersects(big));
-}
-
-
-
-template <typename NumberT>
-void TestForwardTreeTraversal() {
-    detail::BlocksAllocator allocator;
-    detail::ForwardTreeTraversal<NumberT, BoundingBox<NumberT>> fortt;
-    detail::TreeNode<BoundingBox<NumberT>> root(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> tl(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> tr(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> br(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> bl(allocator);
-    root.top_left = &tl;
-    tl.top_right = &tr;
-    tr.bottom_right = &br;
-    root.bottom_left = &bl;
-    fortt.StartAt(&root, BoundingBox<NumberT>(0, 0, 64, 64));
-    ASSERT(fortt.GetDepth() == 0);
-    ASSERT(fortt.GetNode() == &root);
-    ASSERT(fortt.GetNodeBoundingBox().left == 0);
-    ASSERT(fortt.GetNodeBoundingBox().top == 0);
-    ASSERT(fortt.GetNodeBoundingBox().width == 64);
-    ASSERT(fortt.GetNodeBoundingBox().height == 64);
-    fortt.GoTopLeft();
-    ASSERT(fortt.GetDepth() == 1);
-    ASSERT(fortt.GetNode() == &tl);
-    ASSERT(fortt.GetNodeBoundingBox().left == 0);
-    ASSERT(fortt.GetNodeBoundingBox().top == 0);
-    ASSERT(fortt.GetNodeBoundingBox().width == 32);
-    ASSERT(fortt.GetNodeBoundingBox().height == 32);
-    fortt.GoTopRight();
-    ASSERT(fortt.GetDepth() == 2);
-    ASSERT(fortt.GetNode() == &tr);
-    ASSERT(fortt.GetNodeBoundingBox().left == 16);
-    ASSERT(fortt.GetNodeBoundingBox().top == 0);
-    ASSERT(fortt.GetNodeBoundingBox().width == 16);
-    ASSERT(fortt.GetNodeBoundingBox().height == 16);
-    fortt.GoBottomRight();
-    ASSERT(fortt.GetDepth() == 3);
-    ASSERT(fortt.GetNode() == &br);
-    ASSERT(fortt.GetNodeBoundingBox().left == 24);
-    ASSERT(fortt.GetNodeBoundingBox().top == 8);
-    ASSERT(fortt.GetNodeBoundingBox().width == 8);
-    ASSERT(fortt.GetNodeBoundingBox().height == 8);
-    fortt.StartAt(&root, BoundingBox<NumberT>(0, 0, 64, 64));
-    ASSERT(fortt.GetDepth() == 0);
-    ASSERT(fortt.GetNode() == &root);
-    ASSERT(fortt.GetNodeBoundingBox().left == 0);
-    ASSERT(fortt.GetNodeBoundingBox().top == 0);
-    ASSERT(fortt.GetNodeBoundingBox().width == 64);
-    ASSERT(fortt.GetNodeBoundingBox().height == 64);
-    fortt.GoBottomLeft();
-    ASSERT(fortt.GetDepth() == 1);
-    ASSERT(fortt.GetNode() == &bl);
-    ASSERT(fortt.GetNodeBoundingBox().left == 0);
-    ASSERT(fortt.GetNodeBoundingBox().top == 32);
-    ASSERT(fortt.GetNodeBoundingBox().width == 32);
-    ASSERT(fortt.GetNodeBoundingBox().height == 32);
-}
-
-template <typename NumberT>
-void TestFullTreeTraversal() {
-    detail::BlocksAllocator allocator;
-    detail::FullTreeTraversal<NumberT, BoundingBox<NumberT>> fultt;
-    detail::TreeNode<BoundingBox<NumberT>> root(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> tl(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> tr(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> br(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> bl(allocator);
-    root.top_left = &tl;
-    tl.top_right = &tr;
-    tr.bottom_right = &br;
-    br.bottom_left = &bl;
-    fultt.StartAt(&root, BoundingBox<NumberT>(0, 0, 64, 64));
-    ASSERT(fultt.GetDepth() == 0);
-    ASSERT(fultt.GetNode() == &root);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone);
-    fultt.GoTopLeft();
-    ASSERT(fultt.GetDepth() == 1);
-    ASSERT(fultt.GetNode() == &tl);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone);
-    fultt.GoTopRight();
-    ASSERT(fultt.GetDepth() == 2);
-    ASSERT(fultt.GetNode() == &tr);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone);
-    fultt.GoBottomRight();
-    ASSERT(fultt.GetDepth() == 3);
-    ASSERT(fultt.GetNode() == &br);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone);
-    fultt.GoBottomLeft();
-    ASSERT(fultt.GetDepth() == 4);
-    ASSERT(fultt.GetNode() == &bl);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kNone);
-    fultt.GoUp();
-    ASSERT(fultt.GetDepth() == 3);
-    ASSERT(fultt.GetNode() == &br);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kBottomLeft);
-    fultt.GoUp();
-    ASSERT(fultt.GetDepth() == 2);
-    ASSERT(fultt.GetNode() == &tr);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kBottomRight);
-    fultt.GoUp();
-    ASSERT(fultt.GetDepth() == 1);
-    ASSERT(fultt.GetNode() == &tl);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kTopRight);
-    fultt.GoUp();
-    ASSERT(fultt.GetDepth() == 0);
-    ASSERT(fultt.GetNode() == &root);
-    ASSERT(fultt.GetNodeCurrentChild() == detail::ChildPosition::kTopLeft);
-}
-
-template <typename NumberT>
-void TestBoundingBoxDiscrepancy() {
-    detail::BlocksAllocator allocator;
-    detail::FullTreeTraversal<NumberT, BoundingBox<NumberT>> ftt;
-    detail::TreeNode<BoundingBox<NumberT>> root(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> tl(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> tr(allocator);
-    detail::TreeNode<BoundingBox<NumberT>> br(allocator);
-    root.top_left = &tl;
-    root.top_right = &tr;
-    root.bottom_right = &br;
-    ftt.StartAt(&root, BoundingBox<NumberT>(10, 10, 17, 19));
-    NumberT orig_width = ftt.GetNodeBoundingBox().width;
-    NumberT orig_height = ftt.GetNodeBoundingBox().height;
-    ftt.GoTopLeft();
-    NumberT tl_width = ftt.GetNodeBoundingBox().width;
-    NumberT tl_height = ftt.GetNodeBoundingBox().height;
-    ftt.GoUp();
-    ftt.GoTopRight();
-    NumberT tr_width = ftt.GetNodeBoundingBox().width;
-    NumberT tr_height = ftt.GetNodeBoundingBox().height;
-    ftt.GoUp();
-    ftt.GoBottomRight();
-    NumberT br_width = ftt.GetNodeBoundingBox().width;
-    NumberT br_height = ftt.GetNodeBoundingBox().height;
-    ftt.GoUp();
-    ASSERT(orig_width == tl_width + tr_width);
-    ASSERT(orig_height == tl_height + br_height);
-    ASSERT(tr_width == br_width);
-    ASSERT(tl_height == tr_height);
-}
-
-template <typename NumberT>
-void TestTraversals() {
-    TestForwardTreeTraversal<NumberT>();
-    TestFullTreeTraversal<NumberT>();
-    TestBoundingBoxDiscrepancy<NumberT>();
-}
-
-
-template <typename NumberT>
-void TestInsertRemove(bool reclaim_losses) {
-    std::vector<BoundingBox<NumberT>> objects;
-    objects.emplace_back(1000, 1300, 50, 30);
-    objects.emplace_back(1060, 1300, 50, 30);
-    objects.emplace_back(1060, 1300, 5, 3);
-    LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>> lqt;
-    if (reclaim_losses) lqt.ForceCleanup();
-    ASSERT(lqt.GetSize() == 0);
-    ASSERT(lqt.IsEmpty());
-    ASSERT(!lqt.Contains(&objects[0]));
-    ASSERT(lqt.GetSize() == 0);
-    lqt.Insert(&objects[0]);
-    ASSERT(lqt.GetSize() == 1);
-    ASSERT(!lqt.IsEmpty());
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(!lqt.Contains(&objects[1]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0]));
-    ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox()));
-    lqt.Remove(&objects[0]);
-    ASSERT(!lqt.Contains(&objects[0]));
-    ASSERT(lqt.GetSize() == 0);
-    ASSERT(lqt.IsEmpty());
-    if (reclaim_losses) lqt.ForceCleanup();
-
-    lqt.Insert(&objects[1]);
-    ASSERT(lqt.GetSize() == 1);
-    ASSERT(!lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    lqt.Insert(&objects[0]);
-    lqt.Insert(&objects[0]);
-    lqt.Insert(&objects[0]);
-    ASSERT(lqt.GetSize() == 2);
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    ASSERT(!lqt.Contains(&objects[2]));
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Insert(&objects[2]);
-    ASSERT(lqt.GetSize() == 3);
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    ASSERT(lqt.Contains(&objects[2]));
-    if (reclaim_losses) lqt.ForceCleanup();
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0]));
-    ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1]));
-    ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2]));
-    ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox()));
-    lqt.Remove(&objects[1]);
-    lqt.Remove(&objects[1]);
-    lqt.Remove(&objects[1]);
-    ASSERT(lqt.GetSize() == 2);
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(!lqt.Contains(&objects[1]));
-    ASSERT(lqt.Contains(&objects[2]));
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Remove(&objects[0]);
-    ASSERT(lqt.GetSize() == 1);
-    ASSERT(!lqt.Contains(&objects[0]));
-    ASSERT(!lqt.Contains(&objects[1]));
-    ASSERT(lqt.Contains(&objects[2]));
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Remove(&objects[0]);
-    ASSERT(lqt.GetSize() == 1);
-    ASSERT(!lqt.Contains(&objects[0]));
-    ASSERT(!lqt.Contains(&objects[1]));
-    ASSERT(lqt.Contains(&objects[2]));
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Remove(&objects[2]);
-    ASSERT(lqt.GetSize() == 0);
-    ASSERT(!lqt.Contains(&objects[0]));
-    ASSERT(!lqt.Contains(&objects[1]));
-    ASSERT(!lqt.Contains(&objects[2]));
-    if (reclaim_losses) lqt.ForceCleanup();
-}
-
-template <typename NumberT>
-void TestUpdate(bool reclaim_losses) {
-    std::vector<BoundingBox<NumberT>> objects;
-    objects.emplace_back(1000, 1000, 50, 30);
-    objects.emplace_back(1060, 1000, 50, 30);
-    objects.emplace_back(1060, 1000, 5, 3);
-    LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>> lqt;
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Insert(&objects[0]);
-    lqt.Insert(&objects[1]);
-    lqt.Insert(&objects[2]);
-    if (reclaim_losses) lqt.ForceCleanup();
-    ASSERT(lqt.GetSize() == 3);
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    ASSERT(lqt.Contains(&objects[2]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2]));
-    ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox()));
-    objects[2].width = 50;
-    objects[2].height = 30;
-    lqt.Update(&objects[2]);
-    objects[0].left = 1060;
-    lqt.Update(&objects[0]);
-    ASSERT(lqt.GetSize() == 3);
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    ASSERT(lqt.Contains(&objects[2]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2]));
-    ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox()));
-    if (reclaim_losses) lqt.ForceCleanup();
-    ASSERT(lqt.GetSize() == 3);
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    ASSERT(lqt.Contains(&objects[2]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2]));
-    ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox()));
-    lqt.Remove(&objects[0]);
-    ASSERT(lqt.GetSize() == 2);
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Remove(&objects[1]);
-    ASSERT(lqt.GetSize() == 1);
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Remove(&objects[2]);
-    ASSERT(lqt.GetSize() == 0);
-    if (reclaim_losses) lqt.ForceCleanup();
-}
-
-template <typename NumberT>
-void TestMoreTrees(bool reclaim_losses) {
-    std::vector<BoundingBox<NumberT>> objects;
-    objects.emplace_back(1000, 1000, 50, 30);
-    objects.emplace_back(1060, 1000, 50, 30);
-    objects.emplace_back(1060, 1000, 5, 3);
-    LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>> lqt;
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Insert(&objects[0]);
-    lqt.Insert(&objects[1]);
-    ASSERT(lqt.GetSize() == 2);
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1]));
-    ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox()));
-    if (reclaim_losses) lqt.ForceCleanup();
-    {
-        LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>> lqt2;
-        if (reclaim_losses) lqt2.ForceCleanup();
-        ASSERT(lqt2.GetSize() == 0);
-        lqt2.Insert(&objects[1]);
-        lqt2.Insert(&objects[2]);
-        lqt.Insert(&objects[2]);
-        if (reclaim_losses) lqt.ForceCleanup();
-        ASSERT(lqt2.GetSize() == 2);
-        ASSERT(!lqt2.Contains(&objects[0]));
-        ASSERT(lqt2.Contains(&objects[1]));
-        ASSERT(lqt2.Contains(&objects[2]));
-        if (reclaim_losses) lqt2.ForceCleanup();
-        lqt2.Remove(&objects[1]);
-        lqt2.Remove(&objects[2]);
-        ASSERT(lqt2.GetSize() == 0);
-        if (reclaim_losses) lqt2.ForceCleanup();
-    }
-    {
-        LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>> lqt2;
-        lqt2.Insert(&objects[1]);
-        if (reclaim_losses) lqt2.ForceCleanup();
-    }
-    {
-        LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>> lqt2;
-        lqt2.Insert(&objects[1]);
-        lqt2.Insert(&objects[2]);
-        lqt2.Insert(&objects[0]);
-        ASSERT(lqt2.Contains(&objects[1]));
-        lqt2.Clear();
-        ASSERT(lqt2.GetSize() == 0);
-        ASSERT(!lqt2.Contains(&objects[1]));
-        if (reclaim_losses) lqt2.ForceCleanup();
-        ASSERT(lqt2.GetSize() == 0);
-        ASSERT(!lqt2.Contains(&objects[1]));
-        lqt2.Insert(&objects[1]);
-        ASSERT(lqt2.GetSize() == 1);
-        ASSERT(lqt2.Contains(&objects[1]));
-    }
-    ASSERT(lqt.GetSize() == 3);
-    ASSERT(lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    ASSERT(lqt.Contains(&objects[2]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[0]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[1]));
-    ASSERT(lqt.GetLooseBoundingBox().Intersects(objects[2]));
-    ASSERT(!objects[0].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[1].Contains(lqt.GetLooseBoundingBox()));
-    ASSERT(!objects[2].Contains(lqt.GetLooseBoundingBox()));
-    lqt.Remove(&objects[0]);
-    lqt.Remove(&objects[2]);
-    ASSERT(!lqt.Contains(&objects[0]));
-    ASSERT(lqt.Contains(&objects[1]));
-    ASSERT(lqt.GetSize() == 1);
-    if (reclaim_losses) lqt.ForceCleanup();
-    lqt.Remove(&objects[1]);
-    ASSERT(lqt.GetSize() == 0);
-    if (reclaim_losses) lqt.ForceCleanup();
-}
-
-template <typename NumberT>
-void TestContainer() {
-    TestInsertRemove<NumberT>(false);
-    TestInsertRemove<NumberT>(true);
-    TestUpdate<NumberT>(false);
-    TestUpdate<NumberT>(true);
-    TestMoreTrees<NumberT>(false);
-    TestMoreTrees<NumberT>(true);
-}
-
-
-
-template <typename NumberT>
-void TestQueryIntersects(const std::vector<BoundingBox<NumberT>>& objects,
-        LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>>& lqt) {
-    auto query = lqt.QueryIntersectsRegion(BoundingBox<NumberT>(33,33,1,1));
-    ASSERT(query.EndOfQuery());
-
-    query = lqt.QueryIntersectsRegion(BoundingBox<NumberT>(9000,9000,9000,9000));
-    int count = 0;
-    while (!query.EndOfQuery()) {
-        BoundingBox<NumberT>* obj = query.GetCurrent();
-        (void)obj;
-        count++;
-        query.Next();
-    }
-    ASSERT(count == 7);
-
-    query = lqt.QueryIntersectsRegion(BoundingBox<NumberT>(10003,10003,3,7));
-    count = 0;
-    while (!query.EndOfQuery()) {
-        BoundingBox<NumberT>* obj = query.GetCurrent();
-        if (obj != &objects[0] && obj != &objects[1] && obj != &objects[2]) {
-            ASSERT(false);
-        }
-        count++;
-        query.Next();
-    }
-    ASSERT(count == 3);
-
-    query = lqt.QueryIntersectsRegion(BoundingBox<NumberT>(14900,14900,200,200));
-    count = 0;
-    while (!query.EndOfQuery()) {
-        BoundingBox<NumberT>* obj = query.GetCurrent();
-        if (obj != &objects[0] && obj != &objects[1] && obj != &objects[3] && obj != &objects[5]) {
-            ASSERT(false);
-        }
-        count++;
-        query.Next();
-    }
-    ASSERT(count == 4);
-}
-
-template <typename NumberT>
-void TestQueryInside(const std::vector<BoundingBox<NumberT>>& objects,
-        LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>>& lqt) {
-    auto query = lqt.QueryInsideRegion(BoundingBox<NumberT>(33,33,1,1));
-    ASSERT(query.EndOfQuery());
-
-    query = lqt.QueryInsideRegion(BoundingBox<NumberT>(9000,9000,9000,9000));
-    int count = 0;
-    while (!query.EndOfQuery()) {
-        BoundingBox<NumberT>* obj = query.GetCurrent();
-        (void)obj;
-        count++;
-        query.Next();
-    }
-    ASSERT(count == 7);
-
-    query = lqt.QueryInsideRegion(BoundingBox<NumberT>(10003,10003,3,7));
-    ASSERT(query.EndOfQuery());
-
-    query = lqt.QueryInsideRegion(BoundingBox<NumberT>(14900,14900,300,300));
-    count = 0;
-    while (!query.EndOfQuery()) {
-        BoundingBox<NumberT>* obj = query.GetCurrent();
-        if (obj != &objects[5] && obj != &objects[6]) {
-            ASSERT(false);
-        }
-        count++;
-        query.Next();
-    }
-    ASSERT(count == 2);
-}
-
-template <typename NumberT>
-void TestQueryContains(const std::vector<BoundingBox<NumberT>>& objects,
-        LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>>& lqt) {
-    auto query = lqt.QueryContainsRegion(BoundingBox<NumberT>(33,33,1,1));
-    ASSERT(query.EndOfQuery());
-
-    query = lqt.QueryContainsRegion(BoundingBox<NumberT>(9000,9000,9000,9000));
-    ASSERT(query.EndOfQuery());
-
-    query = lqt.QueryContainsRegion(BoundingBox<NumberT>(10003,10003,3,7));
-    int count = 0;
-    while (!query.EndOfQuery()) {
-        BoundingBox<NumberT>* obj = query.GetCurrent();
-        if (obj != &objects[0] && obj != &objects[1]) {
-            ASSERT(false);
-        }
-        count++;
-        query.Next();
-    }
-    ASSERT(count == 2);
-
-    query = lqt.QueryContainsRegion(BoundingBox<NumberT>(14900,14900,200,200));
-    count = 0;
-    while (!query.EndOfQuery()) {
-        BoundingBox<NumberT>* obj = query.GetCurrent();
-        if (obj != &objects[0] && obj != &objects[1]) {
-            ASSERT(false);
-        }
-        count++;
-        query.Next();
-    }
-    ASSERT(count == 2);
-
-    query = lqt.QueryContainsRegion(BoundingBox<NumberT>(15000,15000,2,2));
-    count = 0;
-    while (!query.EndOfQuery()) {
-        BoundingBox<NumberT>* obj = query.GetCurrent();
-        if (obj != &objects[0] && obj != &objects[1] && obj != &objects[3] && obj != &objects[5]) {
-            ASSERT(false);
-        }
-        count++;
-        query.Next();
-    }
-    ASSERT(count == 4);
-}
-
-template <typename NumberT>
-void TestQueries() {
-    std::vector<BoundingBox<NumberT>> objects;
-    objects.emplace_back(10000, 10000, 8000, 8000);//0
-    objects.emplace_back(10000, 10000, 7000, 6000);//1
-    objects.emplace_back(10000, 10000, 7, 6);//2
-    objects.emplace_back(15000, 15000, 500, 600);//3
-    objects.emplace_back(15100, 15100, 200, 200);//4
-    objects.emplace_back(15000, 15000, 200, 200);//5
-    objects.emplace_back(15100, 15100, 2, 2);//6
-    LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>> lqt;
-    for (auto& obj : objects) {
-        lqt.Insert(&obj);
-    }
-    TestQueryIntersects<NumberT>(objects, lqt);
-    TestQueryInside<NumberT>(objects, lqt);
-    TestQueryContains<NumberT>(objects, lqt);
-}
-
-template <typename NumberT>
-[[maybe_unused]] void StressTest() {
-#if 0
-    const int objects_generated = 100;
-    const int object_fluctuation = 10;
-#else
-    const int objects_generated = 200000;
-    const int object_fluctuation = 20000;
-#endif
-    const int full_rounds = 24;
-    const int query_rounds = 4;
-    std::minstd_rand rand;
-    std::uniform_int_distribution<std::size_t> index(0, objects_generated - 1);
-    std::uniform_real_distribution<float>
-        coordinate(std::is_integral<NumberT>::value ?
-                    (float)(std::is_signed<NumberT>::value ?
-                    -std::numeric_limits<NumberT>::max() / 8 :
-                    std::numeric_limits<NumberT>::max() / 16 * 7) :
-                    -1.0f,
-                std::is_integral<NumberT>::value ?
-                    (float)(std::is_signed<NumberT>::value ?
-                    std::numeric_limits<NumberT>::max() / 8 :
-                    std::numeric_limits<NumberT>::max() / 16 * 9) :
-                    1.0f);
-    std::uniform_real_distribution<float>
-        distance(0.0f, std::is_integral<NumberT>::value ?
-                    (float)(std::is_signed<NumberT>::value ?
-                    std::numeric_limits<NumberT>::max() / 8 :
-                    std::numeric_limits<NumberT>::max() / 16) :
-                    0.5f);
-
-    std::vector<BoundingBox<NumberT>> objects;
-    objects.reserve(objects_generated);
-    std::vector<bool> flags(objects_generated, false);
-    LooseQuadtree<NumberT, BoundingBox<NumberT>, TrivialBBExtractor<NumberT>> lqt;
-    for (std::size_t i = 0; i < objects_generated; i++) {
-        objects.emplace_back((NumberT)coordinate(rand), (NumberT)coordinate(rand),
-                (NumberT)distance(rand), (NumberT)distance(rand));
-        lqt.Insert(&objects[i]);
-    }
-    ASSERT(objects.size() == objects_generated);
-    ASSERT(flags.size() == objects_generated);
-
-    for (int round = 0; round < full_rounds; round++) {
-        for (int fluctobj = 0; fluctobj < object_fluctuation; fluctobj++) {
-            std::size_t id = index(rand);
-            objects[id] = BoundingBox<NumberT>((NumberT)coordinate(rand), (NumberT)coordinate(rand),
-                    (NumberT)distance(rand), (NumberT)distance(rand));
-            lqt.Update(&objects[id]);
-        }
-        for (int query_round = 0; query_round < query_rounds; query_round++) {
-            BoundingBox<NumberT> query_region((NumberT)coordinate(rand), (NumberT)coordinate(rand),
-                    (NumberT)distance(rand), (NumberT)distance(rand));
-            for (std::size_t i = 0; i < objects_generated; i++) {
-                flags[i] = false;
-            }
-
-            auto query = lqt.QueryIntersectsRegion(query_region);
-            while (!query.EndOfQuery()) {
-                BoundingBox<NumberT>* obj = query.GetCurrent();
-                ASSERT(query_region.Intersects(*obj));
-                std::size_t id = (std::size_t)(obj - &objects[0]);
-                ASSERT(id < objects_generated);
-                flags[id] = true;
-                query.Next();
-            }
-            for (std::size_t i = 0; i < objects_generated; i++) {
-                ASSERT(flags[i] == query_region.Intersects(objects[i]));
-                flags[i] = false;
-            }
-
-            query = lqt.QueryInsideRegion(query_region);
-            while (!query.EndOfQuery()) {
-                BoundingBox<NumberT>* obj = query.GetCurrent();
-                ASSERT(query_region.Contains(*obj));
-                std::size_t id = (std::size_t)(obj - &objects[0]);
-                ASSERT(id < objects_generated);
-                flags[id] = true;
-                query.Next();
-            }
-            for (std::size_t i = 0; i < objects_generated; i++) {
-                ASSERT(flags[i] == query_region.Contains(objects[i]));
-                flags[i] = false;
-            }
-
-            query = lqt.QueryContainsRegion(query_region);
-            while (!query.EndOfQuery()) {
-                BoundingBox<NumberT>* obj = query.GetCurrent();
-                ASSERT(obj->Contains(query_region));
-                std::size_t id = (std::size_t)(obj - &objects[0]);
-                ASSERT(id < objects_generated);
-                flags[id] = true;
-                query.Next();
-            }
-            for (std::size_t i = 0; i < objects_generated; i++) {
-                ASSERT(flags[i] == objects[i].Contains(query_region));
-                //flags[i] = false;
-            }
-        }
-    }
-    lqt.ForceCleanup();
-}
-
-#define FM_NO_QUADTREE_BENCHMARK
-
-template <typename NumberT>
-void RunTests(const char* type_str)
-{
-    (void)type_str;
-#ifndef FM_NO_QUADTREE_BENCHMARK
-    printf("quadtree test %13s", type_str);
-    fflush(stdout);
-    auto start = std::chrono::high_resolution_clock::now();
-#endif
-    TestBoundingBox<NumberT>();
-    TestTraversals<NumberT>();
-    TestContainer<NumberT>();
-    TestQueries<NumberT>();
-#ifndef FM_NO_QUADTREE_BENCHMARK
-    StressTest<Src>();
-    auto end = std::chrono::high_resolution_clock::now();
-    std::chrono::duration<double, std::milli> time = end - start;
-    printf(": %.1f ms\n", time.count());
-    fflush(stdout);
-#endif
-}
-
-} // namespace
-
-namespace floormat {
-
-#define RUN_TEST(x) RunTests<x>(#x)
-
-void test_app::test_quadtree()
-{
-    RUN_TEST(float);
-    RUN_TEST(double);
-    RUN_TEST(long double);
-    RUN_TEST(std::int16_t);
-    RUN_TEST(std::int32_t);
-    RUN_TEST(std::int64_t);
-    RUN_TEST(std::uint16_t);
-    RUN_TEST(std::uint32_t);
-    RUN_TEST(std::uint64_t);
-}
-
-} // namespace floormat