procedurals
Procedural generation building blocks
Loading...
Searching...
No Matches
PoissonDiskSampling.hpp
Go to the documentation of this file.
1
10#pragma once
11
12#include "Type.hpp" // Vector2f
13#include <algorithm>
14#include <cmath>
15#include <cstdint>
16#include <random>
17#include <vector>
18
20public:
29 static std::vector<Vector2f> generate(float width, float height, float r,
30 int k = 30, uint64_t seed = 42) {
31 const float cellSize = r / std::sqrt(2.0f);
32 const int gridW = int(width / cellSize) + 1;
33 const int gridH = int(height / cellSize) + 1;
34
35 std::vector<int> grid(gridW * gridH, -1);
36 std::vector<Vector2f> points;
37 std::vector<int> active;
38
39 std::mt19937 rng(seed);
40 std::uniform_real_distribution<float> dx(0, width);
41 std::uniform_real_distribution<float> dy(0, height);
42 std::uniform_real_distribution<float> angle(0, 2 * M_PI);
43 std::uniform_real_distribution<float> radius(r, 2 * r);
44
45 auto insert = [&](const Vector2f& p) {
46 points.push_back(p);
47 int gx = int(p.x / cellSize), gy = int(p.y / cellSize);
48 grid[gy * gridW + gx] = int(points.size()) - 1;
49 active.push_back(int(points.size()) - 1);
50 };
51
52 insert({dx(rng), dy(rng)});
53
54 while (!active.empty()) {
55 int idx = active[rng() % active.size()];
56 bool found = false;
57 for (int i = 0; i < k; ++i) {
58 float a = angle(rng), rad = radius(rng);
59 Vector2f cand{ points[idx].x + rad * std::cos(a),
60 points[idx].y + rad * std::sin(a) };
61 if (cand.x < 0 || cand.y < 0 || cand.x >= width || cand.y >= height) continue;
62 if (isValid(cand, r, grid, cellSize, gridW, gridH, points)) {
63 insert(cand);
64 found = true;
65 break;
66 }
67 }
68 if (!found)
69 active.erase(std::remove(active.begin(), active.end(), idx), active.end());
70 }
71 return points;
72 }
73
74private:
75 static bool isValid(const Vector2f& pt, float r,
76 const std::vector<int>& grid, float cellSize,
77 int gridW, int gridH,
78 const std::vector<Vector2f>& points) {
79 int gx = std::min(int(pt.x / cellSize), gridW - 1);
80 int gy = std::min(int(pt.y / cellSize), gridH - 1);
81
82 for (int dy = -2; dy <= 2; ++dy) {
83 for (int dx = -2; dx <= 2; ++dx) {
84 int nx = gx + dx, ny = gy + dy;
85 if (nx < 0 || ny < 0 || nx >= gridW || ny >= gridH) continue;
86 int idx = grid[ny * gridW + nx];
87 if (idx >= 0) {
88 float d = std::hypot(pt.x - points[idx].x, pt.y - points[idx].y);
89 if (d < r) return false;
90 }
91 }
92 }
93 return true;
94 }
95};
Definition PoissonDiskSampling.hpp:19
static std::vector< Vector2f > generate(float width, float height, float r, int k=30, uint64_t seed=42)
Generate points evenly spaced by at least r, inside a width x height area.
Definition PoissonDiskSampling.hpp:29