15 template <
typename PositionFn>
16 void build(PositionFn positions,
size_t num_photons,
float radius) {
17 radius_sqr = radius * radius;
18 inv_size = 0.5f / radius;
22 #pragma omp parallel for reduction(bbox_extend: bbox) 23 for (
size_t i = 0; i < num_photons; ++i)
24 bbox = extend(bbox, positions(i));
27 auto extents = bbox.max - bbox.min;
28 bbox.max += extents * 0.001f;
29 bbox.min -= extents * 0.001f;
31 photons.resize(num_photons);
32 cell_counts.resize(1 << (closest_log2(num_photons) + 1));
33 std::fill(cell_counts.begin(), cell_counts.end(), 0);
36 #pragma omp parallel for 37 for (
size_t i = 0; i < num_photons; i++) {
38 auto h = hash_photon(positions(i));
44 std::partial_sum(cell_counts.begin(), cell_counts.end(), cell_counts.begin());
45 assert(cell_counts.back() == photons.size());
48 #pragma omp parallel for 49 for (
size_t i = 0; i < num_photons; i++) {
50 auto h = hash_photon(positions(i));
52 #pragma omp atomic capture 53 old_count = --cell_counts[h];
54 photons[old_count] = uint32_t(i);
58 template <
typename PositionFn,
typename InsertFn>
59 void query(
const float3& pos, PositionFn positions, InsertFn insert)
const {
60 if (!is_inside(bbox, pos))
return;
62 auto p = (pos - bbox.min) * inv_size;
66 int px2 = px1 + (p.x - px1 > 0.5f ? 1 : -1);
67 int py2 = py1 + (p.y - py1 > 0.5f ? 1 : -1);
68 int pz2 = pz1 + (p.z - pz1 > 0.5f ? 1 : -1);
70 for (
int i = 0; i < 8; i++) {
71 auto range = cell_range(i & 1 ? px2 : px1,
75 for (
auto j = range.first; j < range.second; j++) {
76 int photon_id = photons[j];
77 auto photon_pos = positions(photon_id);
78 auto d = lensqr(pos - photon_pos);
86 std::pair<size_t, size_t> cell_range(uint32_t x, uint32_t y, uint32_t z)
const {
87 auto h = hash_cell(x, y, z);
88 return std::make_pair(cell_counts[h], h == cell_counts.size() - 1 ? photons.size() : cell_counts[h + 1]);
91 uint32_t hash_cell(uint32_t x, uint32_t y, uint32_t z)
const {
92 uint32_t h = bernstein_hash(bernstein_init(), x);
93 h = bernstein_hash(h, y);
94 h = bernstein_hash(h, z);
95 return h & (cell_counts.size() - 1);
98 uint32_t hash_photon(
const float3& pos)
const {
99 auto p = (pos - bbox.min) * inv_size;
100 return hash_cell(p.x, p.y, p.z);
103 std::vector<uint32_t> photons;
104 std::vector<uint32_t> cell_counts;
110 #endif // HASH_GRID_H Bounding box represented by its two extreme points.
Definition: bbox.h:9
Definition: hash_grid.h:11