libs/din: add a perlin noise implementation

This is a 3D noise field addressed as a unit cube.

The caller supplies the resolution of the noise field in three
dimensions.

I've just pulled in my v3f.h here, but it probably makes sense to
later on move vector headers into libs/ and share them.  Later.

It's called din as in noise, because it's shorter than perlin and
noise.

5 files changed, 321 insertions, 1 deletions

diff --git a/src/libs/Makefile.am b/src/libs/Makefile.am
index e0895ce..9f3499d 100644
--- a/src/libs/Makefile.am
+++ b/src/libs/Makefile.am
@@ -1 +1 @@
-SUBDIRS = ascii grid ray txt
+SUBDIRS = ascii grid din ray txt
diff --git a/src/libs/din/Makefile.am b/src/libs/din/Makefile.am
new file mode 100644
index 0000000..b918de6
--- /dev/null
+++ b/src/libs/din/Makefile.am
@@ -0,0 +1,3 @@
+noinst_LIBRARIES = libdin.a
+libdin_a_SOURCES = din.c din.h v3f.h
+libdin_a_CPPFLAGS = -I@top_srcdir@/src
diff --git a/src/libs/din/din.c b/src/libs/din/din.c
new file mode 100644
index 0000000..2293c30
--- /dev/null
+++ b/src/libs/din/din.c
@@ -0,0 +1,147 @@
+/* implements a classical perlin noise function */
+/* https://en.wikipedia.org/wiki/Perlin_noise */
+
+#include <stdlib.h>
+
+#include "din.h"
+#include "v3f.h"
+
+typedef struct din_t {
+	int	width, height, depth;
+	v3f_t	grid[];
+} din_t;
+
+
+/* return random number between -1 and +1 */
+static inline float randf(void)
+{
+	return 2.f / RAND_MAX * rand() - 1.f;
+}
+
+
+void din_randomize(din_t *din)
+{
+	int	x, y, z;
+
+	for (z = 0; z < din->depth; z++) {
+		for (y = 0; y < din->height; y++) {
+			for (x = 0; x < din->width; x++) {
+				v3f_t	r;
+
+				r.x = randf();
+				r.y = randf();
+				r.z = randf();
+
+				din->grid[z * din->width * din->height + y * din->width + x] = v3f_normalize(&r);
+			}
+		}
+	}
+}
+
+
+din_t * din_new(int width, int height, int depth)
+{
+	din_t	*din;
+
+	din = calloc(1, sizeof(din_t) + (sizeof(v3f_t) * (width * height * depth)));
+	if (!din)
+		return NULL;
+
+	din->width = width;
+	din->height = height;
+	din->depth = depth;
+
+	din_randomize(din);
+
+	return din;
+}
+
+
+void din_free(din_t *din)
+{
+	free(din);
+}
+
+
+static inline float dotgradient(const din_t *din, int x, int y, int z, const v3f_t coordinate)
+{
+	v3f_t	distance = v3f_sub(&coordinate, &(v3f_t){.x = x, .y = y, .z = z});
+
+	return v3f_dot(&din->grid[z * din->width * din->height + y * din->width + x], &distance);
+}
+
+
+static inline float lerp(float a, float b, float t)
+{
+	return (1.0f - t) * a + t * b;
+}
+
+
+static inline float clamp(float x, float lowerlimit, float upperlimit) {
+	if (x < lowerlimit)
+		x = lowerlimit;
+
+	if (x > upperlimit)
+		x = upperlimit;
+
+	return x;
+}
+
+
+static inline float smootherstep(float edge0, float edge1, float x) {
+	x = clamp((x - edge0) / (edge1 - edge0), 0.f, 1.f);
+
+	return x * x * x * (x * (x * 6.f - 15.f) + 10.f);
+}
+
+
+/* coordinate is in a unit cube of -1...+1 */
+float din(din_t *din, v3f_t coordinate)
+{
+	int	x0, y0, z0, x1, y1, z1;
+	float	i1, i2, ii1, ii2;
+	float	tx, ty, tz;
+	float	n0, n1;
+
+	coordinate.x = 1.f + (coordinate.x * .5f + .5f) * (float)(din->width - 2);
+	coordinate.y = 1.f + (coordinate.y * .5f + .5f) * (float)(din->height - 2);
+	coordinate.z = 1.f + (coordinate.z * .5f + .5f) * (float)(din->depth - 2);
+
+	x0 = floorf(coordinate.x);
+	y0 = floorf(coordinate.y);
+	z0 = floorf(coordinate.z);
+
+	x1 = x0 + 1.f;
+	y1 = y0 + 1.f;
+	z1 = z0 + 1.f;
+
+	tx = coordinate.x - (float)x0;
+	ty = coordinate.y - (float)y0;
+	tz = coordinate.z - (float)z0;
+
+	n0 = dotgradient(din, x0, y0, z0, coordinate);
+	n1 = dotgradient(din, x1, y0, z0, coordinate);
+	tx = smootherstep(0.f, 1.f, tx);
+	i1 = lerp(n0, n1, tx);
+
+	n0 = dotgradient(din, x0, y1, z0, coordinate);
+	n1 = dotgradient(din, x1, y1, z0, coordinate);
+	i2 = lerp(n0, n1, tx);
+
+	ty = smootherstep(0.f, 1.f, ty);
+	ii1 = lerp(i1, i2, ty);
+
+	n0 = dotgradient(din, x0, y0, z1, coordinate);
+	n1 = dotgradient(din, x1, y0, z1, coordinate);
+	i1 = lerp(n0, n1, tx);
+
+	n0 = dotgradient(din, x0, y1, z1, coordinate);
+	n1 = dotgradient(din, x1, y1, z1, coordinate);
+	i2 = lerp(n0, n1, tx);
+
+	ii2 = lerp(i1, i2, ty);
+
+	tz = smootherstep(0.f, 1.f, tz);
+
+	return lerp(ii1, ii2, tz);
+}
diff --git a/src/libs/din/din.h b/src/libs/din/din.h
new file mode 100644
index 0000000..2e06072
--- /dev/null
+++ b/src/libs/din/din.h
@@ -0,0 +1,13 @@
+#ifndef _DIN_H
+#define _DIN_H
+
+#include "v3f.h"
+
+typedef struct din_t din_t;
+
+din_t * din_new(int width, int height, int depth);
+void din_free(din_t *din);
+void din_randomize(din_t *din);
+float din(din_t *din, v3f_t coordinate);
+
+#endif
diff --git a/src/libs/din/v3f.h b/src/libs/din/v3f.h
new file mode 100644
index 0000000..81750ab
--- /dev/null
+++ b/src/libs/din/v3f.h
@@ -0,0 +1,157 @@
+#ifndef _V3F_H
+#define _V3F_H
+
+#include <math.h>
+
+typedef struct v3f_t {
+	float	x, y, z;
+} v3f_t;
+
+#define v3f_set(_v3f, _x, _y, _z)	\
+	(_v3f)->x = _x;			\
+	(_v3f)->y = _y;			\
+	(_v3f)->z = _z;
+
+#define v3f_init(_x, _y, _z)		\
+	{				\
+		.x = _x,		\
+		.y = _y,		\
+		.z = _z,		\
+	}
+
+/* return if a and b are equal */
+static inline int v3f_equal(const v3f_t *a, const v3f_t *b)
+{
+	return (a->x == b->x && a->y == b->y && a->z == b->z);
+}
+
+
+/* return the result of (a + b) */
+static inline v3f_t v3f_add(const v3f_t *a, const v3f_t *b)
+{
+	v3f_t	res = v3f_init(a->x + b->x, a->y + b->y, a->z + b->z);
+
+	return res;
+}
+
+
+/* return the result of (a - b) */
+static inline v3f_t v3f_sub(const v3f_t *a, const v3f_t *b)
+{
+	v3f_t	res = v3f_init(a->x - b->x, a->y - b->y, a->z - b->z);
+
+	return res;
+}
+
+
+/* return the result of (-v) */
+static inline v3f_t v3f_negate(const v3f_t *v)
+{
+	v3f_t	res = v3f_init(-v->x, -v->y, -v->z);
+
+	return res;
+}
+
+
+/* return the result of (a * b) */
+static inline v3f_t v3f_mult(const v3f_t *a, const v3f_t *b)
+{
+	v3f_t	res = v3f_init(a->x * b->x, a->y * b->y, a->z * b->z);
+
+	return res;
+}
+
+
+/* return the result of (v * scalar) */
+static inline v3f_t v3f_mult_scalar(const v3f_t *v, float scalar)
+{
+	v3f_t	res = v3f_init( v->x * scalar, v->y * scalar, v->z * scalar);
+
+	return res;
+}
+
+
+/* return the result of (uv / scalar) */
+static inline v3f_t v3f_div_scalar(const v3f_t *v, float scalar)
+{
+	v3f_t	res = v3f_init(v->x / scalar, v->y / scalar, v->z / scalar);
+
+	return res;
+}
+
+
+/* return the result of (a . b) */
+static inline float v3f_dot(const v3f_t *a, const v3f_t *b)
+{
+	return a->x * b->x + a->y * b->y + a->z * b->z;
+}
+
+
+/* return the length of the supplied vector */
+static inline float v3f_length(const v3f_t *v)
+{
+	return sqrtf(v3f_dot(v, v));
+}
+
+
+/* return the normalized form of the supplied vector */
+static inline v3f_t v3f_normalize(const v3f_t *v)
+{
+	v3f_t	nv;
+	float	f;
+
+	f = 1.0f / v3f_length(v);
+
+	v3f_set(&nv, f * v->x, f * v->y, f * v->z);
+
+	return nv;
+}
+
+
+/* return the distance squared between two arbitrary points */
+static inline float v3f_distance_sq(const v3f_t *a, const v3f_t *b)
+{
+	return powf(a->x - b->x, 2) + powf(a->y - b->y, 2) + powf(a->z - b->z, 2);
+}
+
+
+/* return the distance between two arbitrary points */
+/* (consider using v3f_distance_sq() instead if possible, sqrtf() is slow) */
+static inline float v3f_distance(const v3f_t *a, const v3f_t *b)
+{
+	return sqrtf(v3f_distance_sq(a, b));
+}
+
+
+/* return the cross product of two unit vectors */
+static inline v3f_t v3f_cross(const v3f_t *a, const v3f_t *b)
+{
+	v3f_t	product = v3f_init(a->y * b->z - a->z * b->y, a->z * b->x - a->x * b->z, a->x * b->y - a->y * b->x);
+
+	return product;
+}
+
+
+/* return the linearly interpolated vector between the two vectors at point alpha (0-1.0) */
+static inline v3f_t v3f_lerp(const v3f_t *a, const v3f_t *b, float alpha)
+{
+	v3f_t	lerp_a, lerp_b;
+
+	lerp_a = v3f_mult_scalar(a, 1.0f - alpha);
+	lerp_b = v3f_mult_scalar(b, alpha);
+
+	return v3f_add(&lerp_a, &lerp_b);
+}
+
+
+/* return the normalized linearly interpolated vector between the two vectors at point alpha (0-1.0) */
+static inline v3f_t v3f_nlerp(const v3f_t *a, const v3f_t *b, float alpha)
+{
+	v3f_t	lerp;
+
+	lerp = v3f_lerp(a, b, alpha);
+
+	return v3f_normalize(&lerp);
+}
+
+#endif