18#ifndef _REGULAR_GRID_H
19#define _REGULAR_GRID_H
24#include <G3D/BoundsTrait.h>
25#include <G3D/PositionTrait.h>
26#include <unordered_map>
30 static Node *
makeNode(
int ,
int ) {
return new Node();}
36class BoundsFunc = BoundsTrait<T>,
37class PositionFunc = PositionTrait<T>
47 #define HGRID_MAP_SIZE (533.33333f * 64.f)
48 #define CELL_SIZE float(HGRID_MAP_SIZE/(float)CELL_NUMBER)
53 Node* nodes[CELL_NUMBER][CELL_NUMBER];
57 memset(nodes, 0,
sizeof(nodes));
62 for (
int x = 0; x < CELL_NUMBER; ++x)
63 for (
int y = 0; y < CELL_NUMBER; ++y)
70 BoundsFunc::getBounds(value, bounds);
71 Cell low = Cell::ComputeCell(bounds.low().x, bounds.low().y);
72 Cell high = Cell::ComputeCell(bounds.high().x, bounds.high().y);
73 for (
int x = low.
x; x <= high.
x; ++x)
75 for (
int y = low.
y; y <= high.
y; ++y)
77 Node& node = getGrid(x, y);
79 memberTable.emplace(&value, &node);
87 p.second->remove(value);
89 memberTable.erase(&value);
94 for (
int x = 0; x < CELL_NUMBER; ++x)
95 for (
int y = 0; y < CELL_NUMBER; ++y)
96 if (Node* n = nodes[x][y])
100 bool contains(
const T& value)
const {
return memberTable.count(&value) > 0; }
101 bool empty()
const {
return memberTable.empty(); }
108 return x == c2.
x && y == c2.
y;
113 Cell c = { int(fx * (1.f /
CELL_SIZE) + (CELL_NUMBER / 2)), int(fy * (1.f /
CELL_SIZE) + (CELL_NUMBER / 2)) };
117 bool isValid()
const {
return x >= 0 && x < CELL_NUMBER && y >= 0 && y < CELL_NUMBER; }
122 ASSERT(x < CELL_NUMBER && y < CELL_NUMBER);
124 nodes[x][y] = NodeCreatorFunc::makeNode(x, y);
128 template<
typename RayCallback>
129 void intersectRay(
const G3D::Ray& ray, RayCallback& intersectCallback,
float max_dist)
131 intersectRay(ray, intersectCallback, max_dist, ray.origin() + ray.direction() * max_dist);
134 template<
typename RayCallback>
135 void intersectRay(
const G3D::Ray& ray, RayCallback& intersectCallback,
float& max_dist,
const G3D::Vector3& end)
137 Cell cell = Cell::ComputeCell(ray.origin().x, ray.origin().y);
141 Cell last_cell = Cell::ComputeCell(end.x, end.y);
143 if (cell == last_cell)
145 if (Node* node = nodes[cell.
x][cell.
y])
146 node->intersectRay(ray, intersectCallback, max_dist);
151 float kx_inv = ray.invDirection().x, bx = ray.origin().x;
152 float ky_inv = ray.invDirection().y, by = ray.origin().y;
159 float x_border = (cell.
x+1) * voxel;
160 tMaxX = (x_border - bx) * kx_inv;
165 float x_border = (cell.
x-1) * voxel;
166 tMaxX = (x_border - bx) * kx_inv;
172 float y_border = (cell.
y+1) * voxel;
173 tMaxY = (y_border - by) * ky_inv;
178 float y_border = (cell.
y-1) * voxel;
179 tMaxY = (y_border - by) * ky_inv;
185 float tDeltaX = voxel * std::fabs(kx_inv);
186 float tDeltaY = voxel * std::fabs(ky_inv);
189 if (Node* node = nodes[cell.
x][cell.
y])
192 node->intersectRay(ray, intersectCallback, max_dist);
194 if (cell == last_cell)
210 template<
typename IsectCallback>
213 Cell cell = Cell::ComputeCell(point.x, point.y);
216 if (Node* node = nodes[cell.
x][cell.
y])
217 node->intersectPoint(point, intersectCallback);
221 template<
typename RayCallback>
224 Cell cell = Cell::ComputeCell(ray.origin().x, ray.origin().y);
227 if (Node* node = nodes[cell.
x][cell.
y])
228 node->intersectRay(ray, intersectCallback, max_dist);
Node & getGrid(int x, int y)
void intersectZAllignedRay(const G3D::Ray &ray, RayCallback &intersectCallback, float &max_dist)
void intersectRay(const G3D::Ray &ray, RayCallback &intersectCallback, float &max_dist, const G3D::Vector3 &end)
void insert(const T &value)
bool contains(const T &value) const
void intersectRay(const G3D::Ray &ray, RayCallback &intersectCallback, float max_dist)
void remove(const T &value)
std::unordered_multimap< const T *, Node * > MemberTable
void intersectPoint(const G3D::Vector3 &point, IsectCallback &intersectCallback)
auto MapEqualRange(M &map, typename M::key_type const &key)
static Node * makeNode(int, int)
bool operator==(Cell const &c2) const
static Cell ComputeCell(float fx, float fy)