Simulant  21.12-194
A portable game engine for Windows, OSX, Linux, Dreamcast, and PSP
spatial_hash.h
1 #pragma once
2 
3 #include <cstring>
4 #include <map>
5 #include <unordered_set>
6 #include <ostream>
7 #include <unordered_set>
8 #include "../../interfaces.h"
9 
10 /*
11  * Hierarchical Grid Spatial Hash implementation
12  *
13  * Objects are inserted into (preferably) one bucket
14  */
15 
16 namespace smlt {
17 
18 
19 const uint32_t MAX_GRID_LEVELS = 16;
20 struct Hash {
21  Hash() = default;
22  Hash(int16_t x, int16_t y, int16_t z):
23  x(x), y(y), z(z) {}
24 
25  int16_t x = 0;
26  int16_t y = 0;
27  int16_t z = 0;
28 };
29 
30 /*
31  * Heirarchical hash key. Each level in the key is a hash of cell_size, x, y, z
32  * if a child key is visible then all parent and child keys are visible. Using a multimap
33  * we can rapidly gather child key objects (by iterating until the key no longer starts with this one)
34  * and we can gather parent ones by checking all levels of the hash_path
35  */
36 struct Key {
37  Hash hash_path[MAX_GRID_LEVELS];
38  std::size_t ancestors = 0;
39  std::size_t hash_code = 0;
40 
41  bool operator<(const Key& other) const {
42  auto len = std::min(other.ancestors, ancestors) + 1;
43  auto ret = memcmp(hash_path, other.hash_path, sizeof(Hash) * len);
44  return ret < 0 || (ret == 0 && ancestors < other.ancestors);
45  }
46 
47  bool operator==(const Key& other) const {
48  return (
49  ancestors == other.ancestors &&
50  memcmp(hash_path, other.hash_path, sizeof(Hash) * (ancestors + 1)) == 0
51  );
52  }
53 
54  bool is_root() const { return ancestors == 0; }
55  Key parent_key() const;
56 
57  bool is_ancestor_of(const Key& other) const;
58 
59  friend std::ostream& operator<<(std::ostream& os, const Key& key);
60 };
61 
62 }
63 
64 namespace std {
65 
66  template<>
67  struct hash<smlt::Key> {
68  typedef smlt::Key argument_type;
69  typedef std::size_t result_type;
70 
71  result_type operator()(argument_type const& s) const
72  {
73  return s.hash_code;
74  }
75  };
76 
77 }
78 
79 namespace smlt {
80 
81 std::ostream& operator<<(std::ostream& os, const Key& key);
82 
83 Key make_key(int32_t cell_size, float x, float y, float z);
84 Hash make_hash(int32_t cell_size, float x, float y, float z);
85 
86 typedef std::unordered_set<Key> KeyList;
87 
89 public:
90  virtual ~SpatialHashEntry() {}
91 
92  void set_hash_aabb(const AABB& aabb) {
93  hash_aabb_ = aabb;
94  }
95 
96  void push_key(const Key& key) {
97  keys_.insert(key);
98  }
99 
100  void remove_key(const Key& key) {
101  keys_.erase(key);
102  }
103 
104  void set_keys(const KeyList& keys) {
105  keys_ = std::move(keys);
106  }
107 
108  const KeyList& keys() const {
109  return keys_;
110  }
111 
112  const AABB& hash_aabb() const { return hash_aabb_; }
113 private:
114  KeyList keys_;
115  AABB hash_aabb_;
116 };
117 
118 typedef std::unordered_set<SpatialHashEntry*> HGSHEntryList;
119 
120 class SpatialHash {
121 public:
122  SpatialHash();
123 
124  void insert_object_for_box(const AABB& box, SpatialHashEntry* object);
125  void remove_object(SpatialHashEntry* object);
126 
127  void update_object_for_box(const AABB& new_box, SpatialHashEntry* object);
128 
129  HGSHEntryList find_objects_within_box(const AABB& box);
130  HGSHEntryList find_objects_within_frustum(const Frustum& frustum);
131 
132  friend std::ostream &operator<<(std::ostream &os, const SpatialHash &hash);
133 
134 private:
135  void erase_object_from_key(Key key, SpatialHashEntry* object);
136 
137  int32_t find_cell_size_for_box(const AABB& box) const;
138  void insert_object_for_key(Key key, SpatialHashEntry* entry);
139 
140  typedef std::map<Key, std::unordered_set<SpatialHashEntry*>> Index;
141  Index index_;
142 };
143 
144 std::ostream &operator<<(std::ostream &os, const SpatialHash &hash);
145 
146 void generate_boxes_for_frustum(const Frustum& frustum, std::vector<AABB>& results);
147 
148 }
149 
150 
151 
smlt::Frustum
Definition: frustum.h:43
smlt::SpatialHashEntry
Definition: spatial_hash.h:88
smlt
Definition: animation.cpp:25
smlt::Hash
Definition: spatial_hash.h:20
smlt::Key
Definition: spatial_hash.h:36
smlt::SpatialHash
Definition: spatial_hash.h:120
smlt::AABB
Definition: aabb.h:22
std
Extensions to the C++ standard library.
Definition: unique_id.h:200