commit 0daf3a4f126da9e86e77561323265981ea9efc1a
parent 24e568107e8b8e79abbda6c044a695f4b76aee1f
Author: William Casarin <jb55@jb55.com>
Date: Fri, 27 Apr 2018 21:45:42 -0700
POISSON DISK SAMPLING BOIS
Diffstat:
6 files changed, 284 insertions(+), 2 deletions(-)
diff --git a/Makefile b/Makefile
@@ -18,6 +18,7 @@ OBJS += $(SRC)/debug.o
OBJS += $(SRC)/event.o
OBJS += $(SRC)/file.o
OBJS += $(SRC)/perlin.o
+OBJS += $(SRC)/poisson.o
OBJS += $(SRC)/game.o
OBJS += $(SRC)/mat4/mat4.o
OBJS += $(SRC)/vec3/vec3.o
diff --git a/src/main.c b/src/main.c
@@ -13,10 +13,22 @@
#include "terrain.h"
#include <assert.h>
#include <time.h>
+#include "poisson.h"
int main(void)
{
+ int nsamples;
+ struct point *samples;
+ const double size = 500;
+ const double point_dist = 20;
+
+ srand(time(NULL));
+
+ samples = poisson_disk_samples(point_dist, size, 30, &nsamples);
+ draw_samples(samples, point_dist, nsamples, size);
+ exit(0);
+
struct game game;
struct slab slab;
struct geometry slab_geom;
@@ -32,8 +44,6 @@ int main(void)
"SDL2/OpenGL Demo", 0, 0, width, height,
SDL_WINDOW_OPENGL|SDL_WINDOW_RESIZABLE);
- srand(time(NULL));
-
SDL_GL_CreateContext(window);
init_gl(&game.test_resources, width, height);
game_init(&game);
diff --git a/src/poisson.c b/src/poisson.c
@@ -0,0 +1,232 @@
+
+#include <stdlib.h>
+#include <math.h>
+#include "util.h"
+#include "poisson.h"
+
+
+struct grid_info {
+ double size;
+ int *grid;
+ int *active;
+ int cellw;
+ int cells;
+ float cell_size;
+ struct point *samples;
+ int n_samples;
+ int n_active;
+};
+
+void
+draw_samples(struct point *samples, double point_dist, const int nsamples, const int size) {
+ const int dimx = size, dimy = size;
+ int x, y;
+ int close = 0;
+ FILE *fp = fopen("poisson.ppm", "wb"); /* b - binary mode */
+ fprintf(fp, "P6\n%d %d\n255\n", dimx, dimy);
+ for (y = 0; y < dimy; ++y)
+ for (x = 0; x < dimx; ++x) {
+ static unsigned char color[3];
+ double dx, dy, dist;
+ for (int i = 0; i < nsamples; ++i) {
+ dx = samples[i].x - (double)x;
+ dy = samples[i].y - (double)y;
+ dist = dx * dx + dy * dy;
+ if (dist <= 2) {
+ close = 1;
+ break;
+ }
+ }
+ /* if (fmod(x, point_dist/sqrt(2)) <= 1 || */
+ /* fmod(y, point_dist/sqrt(2)) <= 1) { */
+ /* color[0] = 180; */
+ /* color[1] = 180; */
+ /* color[2] = 180; */
+ /* } */
+ if (close) {
+ int c = 255-(int)(dist/(point_dist/sqrt(2)) * 255.0);
+ color[0] = c;
+ color[1] = c;
+ color[2] = c;
+ }
+ else {
+ color[0] = 0;
+ color[1] = 0;
+ color[2] = 0;
+ }
+ fwrite(color, 1, 3, fp);
+ close = 0;
+ }
+ fclose(fp);
+}
+
+int
+grid_lookup(struct grid_info *info, int x, int y) {
+ if (x > info->cellw || y > info->cellw || x < 0 || y < 0)
+ return -2;
+
+ int grid_ix = x * info->cellw + y;
+ assert(grid_ix < info->cells && "blah");
+ int ix = info->grid[grid_ix];
+
+ return ix;
+}
+
+static int
+add_sample(struct grid_info *info, struct point *candidate) {
+ int grid_x = floor(candidate->x / info->cell_size);
+ int grid_y = floor(candidate->y / info->cell_size);
+
+ int i = info->n_samples++;
+ int grid_ix = grid_ix = grid_x * info->cellw + grid_y;
+ int ai = info->n_active++;
+
+ assert(info->n_samples < info->cells);
+ assert(grid_ix < info->cells);
+ assert(ai < info->cells);
+
+ info->active[ai] = i;
+ info->samples[i].x = candidate->x;
+ info->samples[i].y = candidate->y;
+ assert(info->grid[grid_ix] == -1);
+ info->grid[grid_ix] = i;
+ return i;
+}
+
+static void
+remove_active(struct grid_info *info, int i) {
+ if (info->n_active == 0)
+ return;
+
+ if (info->n_active == 1 && i == 0) {
+ info->n_active = 0;
+ return;
+ }
+
+ if (info->n_active == 1 && i != 0)
+ assert(!"trying to remove and index that doesn't exist");
+
+ for (int j = i; j < info->n_active-1; ++j) {
+ assert(j >= 0);
+ assert(j+1 < info->cells);
+ info->active[j] = info->active[j+1];
+ }
+
+ info->n_active--;
+}
+
+struct point *
+poisson_disk_samples(const double point_dist, double size,
+ const int reject_limit, int *n_samples) {
+ struct point candidate;
+ struct grid_info info;
+
+ double cell_size = point_dist / sqrt(2);
+
+ int cellw = ceil(size/cell_size)+1;
+ int cells = cellw * cellw;
+
+ int *grid = malloc(cells * sizeof(*grid));
+ int *active = malloc(cells * sizeof(*active));
+ struct point *samples = malloc(cells * sizeof(*samples));
+
+ info.n_samples = 0;
+ info.grid = grid;
+ info.samples = samples;
+ info.active = active;
+ info.n_active = 0;
+ info.cellw = cellw;
+ info.cells = cells;
+ info.size = size;
+ info.cell_size = cell_size;
+
+ for (int i = 0; i < cells; ++i)
+ grid[i] = -1;
+
+ candidate.x = rand_0to1() * size;
+ candidate.y = rand_0to1() * size;
+
+ add_sample(&info, &candidate);
+
+ assert(info.n_active == 1);
+ assert(info.n_samples == 1);
+
+ int nexti = -1;
+ while (info.n_active > 0) {
+ int rand_i = nexti != -1 ? nexti : rand() % info.n_active;
+ struct point *xi = &samples[rand_i];
+
+ int all_rejected = 1;
+
+ for (int i = 0; i < reject_limit; ++i) {
+ int sx = rand() % 2 ? 1 : -1;
+ int sy = rand() % 2 ? 1 : -1;
+
+ double rx = ((rand_0to1() * point_dist) + point_dist) * sx;
+ double ry = ((rand_0to1() * point_dist) + point_dist) * sy;
+
+ /* printf("xi %f xy %f rx %f ry %f\n", xi->x, xi->y, rx, ry); */
+
+ candidate.x = xi->x + rx;
+ candidate.y = xi->y + ry;
+
+ int cx = floor(candidate.x / info.cell_size);
+ int cy = floor(candidate.y / info.cell_size);
+
+ if (candidate.x > size || candidate.x < 0 || candidate.y > size || candidate.y < 0)
+ continue;
+
+ int nearby[] = {
+ grid_lookup(&info, cx - 1, cy - 1),
+ grid_lookup(&info, cx + 0, cy - 1),
+ grid_lookup(&info, cx + 1, cy - 1),
+
+ grid_lookup(&info, cx - 1, cy + 0),
+ grid_lookup(&info, cx + 0, cy + 0),
+ grid_lookup(&info, cx + 1, cy + 0),
+
+ grid_lookup(&info, cx - 1, cy + 1),
+ grid_lookup(&info, cx + 0, cy + 1),
+ grid_lookup(&info, cx + 1, cy + 1),
+ };
+
+
+ int found = 1;
+
+ if (grid_lookup(&info, cx + 0, cy + 0) != -1) {
+ found = 0;
+ }
+ else {
+ for (size_t j = 0; j < ARRAY_SIZE(nearby); ++j) {
+ int neari = nearby[j];
+
+ assert(neari < cells);
+ struct point *near = &samples[neari];
+ double dx = near->x - candidate.x;
+ double dy = near->y - candidate.y;
+ double dist = sqrt(dx * dx + dy * dy);
+ if (dist < point_dist) {
+ found = 0;
+ break;
+ }
+ }
+ }
+
+ if (found) {
+ all_rejected = 0;
+ nexti = add_sample(&info, &candidate);
+ }
+ } // gen up to reject_limit samples
+
+ if (all_rejected) {
+ nexti = -1;
+ remove_active(&info, rand_i);
+ }
+ }
+
+ *n_samples = info.n_samples;
+
+ free(grid);
+ free(active);
+ return samples;
+}
diff --git a/src/poisson.h b/src/poisson.h
@@ -0,0 +1,17 @@
+
+#ifndef POLYADVENT_POISSON_H
+#define POLYADVENT_POISSON_H
+
+struct point {
+ double x, y;
+};
+
+void draw_samples(struct point *samples, double point_dist,
+ const int nsamples, const int size);
+
+struct point *
+poisson_disk_samples(const double point_dist, double size,
+ const int reject_limit, int *n_samples);
+
+
+#endif /* POLYADVENT_POISSON_H */
diff --git a/src/util.c b/src/util.c
@@ -2,6 +2,26 @@
#include "util.h"
#include <stdlib.h>
+int clampi(int a, int mina, int maxa) {
+ if (a > maxa)
+ return maxa;
+
+ if (a < mina)
+ return mina;
+
+ return a;
+}
+
+double clamp(double a, double mina, double maxa) {
+ if (a > maxa)
+ return maxa;
+
+ if (a < mina)
+ return mina;
+
+ return a;
+}
+
void check_gl() {
unsigned int e = glGetError();
if (e != GL_NO_ERROR) {
diff --git a/src/util.h b/src/util.h
@@ -8,6 +8,8 @@
#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
void check_gl(void);
+int clampi(int a, int mina, int maxa);
+double clamp(double a, double mina, double maxa);
double rand_0to1();
