summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorStanislaw Halik <sthalik@misaki.pl>2023-03-24 00:54:01 +0100
committerStanislaw Halik <sthalik@misaki.pl>2023-03-24 00:55:34 +0100
commitb0c238ec74f8c2296d2f82a76147f3a9f417e6bf (patch)
treea09325d734dcfeee067ab94a71346a5dfe27e2bd
parenta3762299ba5416ae2f85df2fb27b262d088a1e06 (diff)
src: split RTree::Search definition into own file
-rw-r--r--editor/draw.cpp2
-rw-r--r--src/RTree-search.hpp72
-rw-r--r--src/RTree.cpp11
-rw-r--r--src/RTree.h27
-rw-r--r--src/RTree.hpp87
-rw-r--r--src/character.cpp3
-rw-r--r--src/chunk-collision.cpp2
-rw-r--r--src/chunk.hpp2
-rw-r--r--src/entity.cpp2
9 files changed, 105 insertions, 103 deletions
diff --git a/editor/draw.cpp b/editor/draw.cpp
index 39f1b9fe..ab9cb7ee 100644
--- a/editor/draw.cpp
+++ b/editor/draw.cpp
@@ -12,7 +12,7 @@
#include <Magnum/Math/Color.h>
#include <Magnum/Math/Vector3.h>
#include <Magnum/GL/Renderer.h>
-#include "src/RTree.hpp"
+#include "src/RTree-search.hpp"
namespace floormat {
diff --git a/src/RTree-search.hpp b/src/RTree-search.hpp
new file mode 100644
index 00000000..4b824cd6
--- /dev/null
+++ b/src/RTree-search.hpp
@@ -0,0 +1,72 @@
+#pragma once
+#include "compat/assert.hpp"
+#include "RTree.h"
+
+RTREE_TEMPLATE
+template<typename F>
+int RTREE_QUAL::Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], F&& callback) const
+{
+#ifndef FM_NO_DEBUG
+ for(int index=0; index<NUMDIMS; ++index)
+ {
+ fm_assert(a_min[index] <= a_max[index]);
+ }
+#endif
+
+ Rect rect;
+
+ for(int axis=0; axis<NUMDIMS; ++axis)
+ {
+ rect.m_min[axis] = a_min[axis];
+ rect.m_max[axis] = a_max[axis];
+ }
+
+ // NOTE: May want to return search result another way, perhaps returning the number of found elements here.
+
+ int foundCount = 0;
+ Search(m_root, &rect, foundCount, callback);
+
+ return foundCount;
+}
+
+// Search in an index tree or subtree for all data retangles that overlap the argument rectangle.
+RTREE_TEMPLATE
+template<typename F>
+bool RTREE_QUAL::Search(Node* a_node, Rect* a_rect, int& a_foundCount, F&& callback) const
+{
+ fm_assert(a_node);
+ fm_assert(a_node->m_level >= 0);
+ fm_assert(a_rect);
+
+ if(a_node->IsInternalNode())
+ {
+ // This is an internal node in the tree
+ for(int index=0; index < a_node->m_count; ++index)
+ {
+ if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
+ {
+ if(!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, callback))
+ {
+ // The callback indicated to stop searching
+ return false;
+ }
+ }
+ }
+ }
+ else
+ {
+ // This is a leaf node
+ for(int index=0; index < a_node->m_count; ++index)
+ {
+ if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
+ {
+ ++a_foundCount;
+ const Rect& r = a_node->m_branch[index].m_rect;
+ if(!callback(a_node->m_branch[index].m_data, r))
+ return false; // Don't continue searching
+ }
+ }
+ }
+
+ return true; // Continue searching
+}
diff --git a/src/RTree.cpp b/src/RTree.cpp
index 40343e31..f77d0697 100644
--- a/src/RTree.cpp
+++ b/src/RTree.cpp
@@ -1,4 +1,4 @@
-#define RTREE_NO_EXTERN_TEMPLATE_POOL
+#define RTREE_NO_EXTERN_TEMPLATE
#include "RTree.hpp"
//#define RTREE_POOL_DEBUG
@@ -70,10 +70,11 @@ template<typename T> void rtree_pool<T>::free(T* ptr)
free_list = n;
}
-using my_rtree = RTree<uint64_t, float, 2, float>;
-template struct rtree_pool<my_rtree::Node>;
-template struct rtree_pool<my_rtree::ListNode>;
-
} // namespace floormat::detail
+using my_rtree = RTree<floormat::uint64_t, float, 2, float>;
+template struct floormat::detail::rtree_pool<my_rtree::Node>;
+template struct floormat::detail::rtree_pool<my_rtree::ListNode>;
+template<> floormat::detail::rtree_pool<my_rtree::Node> my_rtree::node_pool = {}; // NOLINT
+template<> floormat::detail::rtree_pool<my_rtree::ListNode> my_rtree::list_node_pool = {}; // NOLINT
template class RTree<floormat::uint64_t, float, 2, float>;
diff --git a/src/RTree.h b/src/RTree.h
index 3ceb64ac..95784409 100644
--- a/src/RTree.h
+++ b/src/RTree.h
@@ -20,9 +20,17 @@
//#define RTREE_DONT_USE_MEMPOOLS // This version does not contain a fixed memory allocator, fill in lines with EXAMPLE to implement one.
#define RTREE_USE_SPHERICAL_VOLUME // Better split classification, may be slower on some systems
-namespace floormat::detail { template<typename T> struct rtree_pool; }
+#ifdef RTREE_STDIO
+// Fwd decl
+class RTFileStream; // File I/O helper class, look below for implementation and notes.
+#endif
-template<typename T> struct floormat::detail::rtree_pool final
+#define RTREE_TEMPLATE template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
+#define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES>
+
+namespace floormat::detail {
+
+template<typename T> struct rtree_pool final
{
rtree_pool() noexcept;
rtree_pool(const rtree_pool&) = delete;
@@ -44,10 +52,7 @@ private:
node_u* free_list = nullptr;
};
-#ifdef RTREE_STDIO
-// Fwd decl
-class RTFileStream; // File I/O helper class, look below for implementation and notes.
-#endif
+} // namespace floormat::detail
/// \class RTree
/// Implementation of RTree, a multidimensional bounding rectangle tree.
@@ -234,8 +239,8 @@ public:
Node* m_node; ///< Node
};
- floormat::detail::rtree_pool<Node> node_pool;
- floormat::detail::rtree_pool<ListNode> list_node_pool;
+ static floormat::detail::rtree_pool<Node> node_pool;
+ static floormat::detail::rtree_pool<ListNode> list_node_pool;
protected:
/// Variables for finding a split partition
@@ -302,10 +307,12 @@ public:
void ListTree(std::vector<Rect>& vec, std::vector<Node*>& temp) const;
};
-extern template class RTree<floormat::uint64_t, float, 2, float>;
+
+#ifndef RTREE_NO_EXTERN_TEMPLATE
extern template struct floormat::detail::rtree_pool<RTree<floormat::uint64_t, float, 2, float>::Node>;
extern template struct floormat::detail::rtree_pool<RTree<floormat::uint64_t, float, 2, float>::ListNode>;
-
+extern template class RTree<floormat::uint64_t, float, 2, float>;
+#endif
//#undef RTREE_TEMPLATE
//#undef RTREE_QUAL
diff --git a/src/RTree.hpp b/src/RTree.hpp
index 046c5e1d..de175fbd 100644
--- a/src/RTree.hpp
+++ b/src/RTree.hpp
@@ -1,6 +1,7 @@
#pragma once
#include "RTree.h"
+#include "RTree-search.hpp"
#include <math.h>
#include <stdlib.h>
@@ -13,8 +14,6 @@
#pragma GCC diagnostic ignored "-Wzero-as-null-pointer-constant"
#endif
-#define RTREE_TEMPLATE template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
-#define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES>
#undef _DEBUG
#ifndef FM_NO_DEBUG
#define _DEBUG
@@ -31,14 +30,10 @@
#define Max std::max
#endif //Max
-namespace floormat::detail {
-
-
-#ifndef RTREE_NO_EXTERN_TEMPLATE_POOL
-extern template struct rtree_pool<RTree<std::uint64_t, float, 2, float>::Node>;
-extern template struct rtree_pool<RTree<std::uint64_t, float, 2, float>::ListNode>;
+#ifndef RTREE_NO_EXTERN_TEMPLATE
+extern template struct floormat::detail::rtree_pool<RTree<floormat::uint64_t, float, 2, float>::Node>;
+extern template struct floormat::detail::rtree_pool<RTree<floormat::uint64_t, float, 2, float>::ListNode>;
#endif
-} // namespace floormat::detail
#ifdef RTREE_STDIO
// Because there is not stream support, this is a quick and dirty file I/O helper.
@@ -215,34 +210,6 @@ void RTREE_QUAL::Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMD
RTREE_TEMPLATE
-template<typename F>
-int RTREE_QUAL::Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], F&& callback) const
-{
-#ifdef _DEBUG
- for(int index=0; index<NUMDIMS; ++index)
- {
- ASSERT(a_min[index] <= a_max[index]);
- }
-#endif //_DEBUG
-
- Rect rect;
-
- for(int axis=0; axis<NUMDIMS; ++axis)
- {
- rect.m_min[axis] = a_min[axis];
- rect.m_max[axis] = a_max[axis];
- }
-
- // NOTE: May want to return search result another way, perhaps returning the number of found elements here.
-
- int foundCount = 0;
- Search(m_root, &rect, foundCount, callback);
-
- return foundCount;
-}
-
-
-RTREE_TEMPLATE
int RTREE_QUAL::Count() const
{
int count = 0;
@@ -1288,49 +1255,6 @@ void RTREE_QUAL::ReInsert(Node* a_node, ListNode** a_listNode)
}
-// Search in an index tree or subtree for all data retangles that overlap the argument rectangle.
-RTREE_TEMPLATE
-template<typename F>
-bool RTREE_QUAL::Search(Node* a_node, Rect* a_rect, int& a_foundCount, F&& callback) const
-{
- ASSERT(a_node);
- ASSERT(a_node->m_level >= 0);
- ASSERT(a_rect);
-
- if(a_node->IsInternalNode())
- {
- // This is an internal node in the tree
- for(int index=0; index < a_node->m_count; ++index)
- {
- if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
- {
- if(!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, callback))
- {
- // The callback indicated to stop searching
- return false;
- }
- }
- }
- }
- else
- {
- // This is a leaf node
- for(int index=0; index < a_node->m_count; ++index)
- {
- if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
- {
- ++a_foundCount;
- const Rect& r = a_node->m_branch[index].m_rect;
- if(!callback(a_node->m_branch[index].m_data, r))
- return false; // Don't continue searching
- }
- }
- }
-
- return true; // Continue searching
-}
-
-
RTREE_TEMPLATE
void RTREE_QUAL::ListTree(std::vector<Rect>& treeList, std::vector<Node*>& toVisit) const
{
@@ -1486,9 +1410,6 @@ bool RTREE_QUAL::Iterator::FindNextData()
#undef _DEBUG
#undef ASSERT
-#undef RTREE_QUAL
-#undef RTREE_TEMPLATE
-
#ifdef __GNUG__
#pragma GCC diagnostic pop
#endif
diff --git a/src/character.cpp b/src/character.cpp
index e2888b85..5a021681 100644
--- a/src/character.cpp
+++ b/src/character.cpp
@@ -3,9 +3,10 @@
#include "loader/loader.hpp"
#include "src/world.hpp"
#include "src/entity.hpp"
-#include "src/RTree.hpp"
+#include "src/RTree-search.hpp"
#include <cmath>
#include <utility>
+#include <algorithm>
namespace floormat {
diff --git a/src/chunk-collision.cpp b/src/chunk-collision.cpp
index 5e0c7a94..438b6a61 100644
--- a/src/chunk-collision.cpp
+++ b/src/chunk-collision.cpp
@@ -1,7 +1,7 @@
#include "chunk.hpp"
-#include "RTree.hpp"
#include "tile-atlas.hpp"
#include "entity.hpp"
+#include "src/RTree-search.hpp"
#include <bit>
#include <Corrade/Containers/PairStl.h>
diff --git a/src/chunk.hpp b/src/chunk.hpp
index c7183d2c..2fecb6fe 100644
--- a/src/chunk.hpp
+++ b/src/chunk.hpp
@@ -2,12 +2,12 @@
#include "object-id.hpp"
#include "tile.hpp"
#include "tile-iterator.hpp"
+#include "src/RTree.h"
#include <Corrade/Containers/Array.h>
#include <type_traits>
#include <array>
#include <memory>
#include <Magnum/GL/Mesh.h>
-#include "RTree.h"
namespace floormat {
diff --git a/src/entity.cpp b/src/entity.cpp
index 10dd0ca6..42ae5c4b 100644
--- a/src/entity.cpp
+++ b/src/entity.cpp
@@ -2,7 +2,7 @@
#include "world.hpp"
#include "rotation.inl"
#include "anim-atlas.hpp"
-#include "RTree.hpp"
+#include "src/RTree-search.hpp"
#include "compat/exception.hpp"
#include <cmath>
#include <algorithm>