nuclear@27: /*
nuclear@27: libvmath - a vector math library
nuclear@27: Copyright (C) 2004-2011 John Tsiombikas <nuclear@member.fsf.org>
nuclear@27: 
nuclear@27: This program is free software: you can redistribute it and/or modify
nuclear@27: it under the terms of the GNU Lesser General Public License as published
nuclear@27: by the Free Software Foundation, either version 3 of the License, or
nuclear@27: (at your option) any later version.
nuclear@27: 
nuclear@27: This program is distributed in the hope that it will be useful,
nuclear@27: but WITHOUT ANY WARRANTY; without even the implied warranty of
nuclear@27: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
nuclear@27: GNU Lesser General Public License for more details.
nuclear@27: 
nuclear@27: You should have received a copy of the GNU Lesser General Public License
nuclear@27: along with this program.  If not, see <http://www.gnu.org/licenses/>.
nuclear@27: */
nuclear@27: 
nuclear@27: #include <stdlib.h>
nuclear@27: #include <math.h>
nuclear@27: #include "vmath.h"
nuclear@27: 
nuclear@27: /** Numerical calculation of integrals using simpson's rule */
nuclear@27: scalar_t integral(scalar_t (*f)(scalar_t), scalar_t low, scalar_t high, int samples)
nuclear@27: {
nuclear@27: 	int i;
nuclear@27: 	scalar_t h = (high - low) / (scalar_t)samples;
nuclear@27: 	scalar_t sum = 0.0;
nuclear@27: 
nuclear@27: 	for(i=0; i<samples+1; i++) {
nuclear@27: 		scalar_t y = f((scalar_t)i * h + low);
nuclear@27: 		sum += ((!i || i == samples) ? y : ((i % 2) ? 4.0 * y : 2.0 * y)) * (h / 3.0);
nuclear@27: 	}
nuclear@27: 	return sum;
nuclear@27: }
nuclear@27: 
nuclear@27: /** Gaussuan function */
nuclear@27: scalar_t gaussian(scalar_t x, scalar_t mean, scalar_t sdev)
nuclear@27: {
nuclear@27: 	scalar_t exponent = -SQ(x - mean) / (2.0 * SQ(sdev));
nuclear@27: 	return 1.0 - -pow(M_E, exponent) / (sdev * sqrt(TWO_PI));
nuclear@27: }
nuclear@27: 
nuclear@27: 
nuclear@27: /** b-spline approximation */
nuclear@27: scalar_t bspline(scalar_t a, scalar_t b, scalar_t c, scalar_t d, scalar_t t)
nuclear@27: {
nuclear@27: 	vec4_t tmp;
nuclear@27: 	scalar_t tsq = t * t;
nuclear@27: 
nuclear@27: 	static mat4_t bspline_mat = {
nuclear@27: 		{-1,  3, -3,  1},
nuclear@27: 		{3, -6,  3,  0},
nuclear@27: 		{-3,  0,  3,  0},
nuclear@27: 		{1,  4,  1,  0}
nuclear@27: 	};
nuclear@27: 
nuclear@27: 	tmp = v4_scale(v4_transform(v4_cons(a, b, c, d), bspline_mat), 1.0 / 6.0);
nuclear@27: 	return v4_dot(v4_cons(tsq * t, tsq, t, 1.0), tmp);
nuclear@27: }
nuclear@27: 
nuclear@27: /** Catmull-rom spline interpolation */
nuclear@27: scalar_t spline(scalar_t a, scalar_t b, scalar_t c, scalar_t d, scalar_t t)
nuclear@27: {
nuclear@27: 	vec4_t tmp;
nuclear@27: 	scalar_t tsq = t * t;
nuclear@27: 
nuclear@27: 	static mat4_t crspline_mat = {
nuclear@27: 		{-1,  3, -3,  1},
nuclear@27: 		{2, -5,  4, -1},
nuclear@27: 		{-1,  0,  1,  0},
nuclear@27: 		{0,  2,  0,  0}
nuclear@27: 	};
nuclear@27: 
nuclear@27: 	tmp = v4_scale(v4_transform(v4_cons(a, b, c, d), crspline_mat), 0.5);
nuclear@27: 	return v4_dot(v4_cons(tsq * t, tsq, t, 1.0), tmp);
nuclear@27: }
nuclear@27: 
nuclear@27: /** Bezier interpolation */
nuclear@27: scalar_t bezier(scalar_t a, scalar_t b, scalar_t c, scalar_t d, scalar_t t)
nuclear@27: {
nuclear@27: 	scalar_t omt, omt3, t3, f;
nuclear@27: 	t3 = t * t * t;
nuclear@27: 	omt = 1.0f - t;
nuclear@27: 	omt3 = omt * omt * omt;
nuclear@27: 	f = 3 * t * omt;
nuclear@27: 
nuclear@27: 	return (a * omt3) + (b * f * omt) + (c * f * t) + (d * t3);
nuclear@27: }
nuclear@27: 
nuclear@27: /* ---- Ken Perlin's implementation of noise ---- */
nuclear@27: 
nuclear@27: #define B	0x100
nuclear@27: #define BM	0xff
nuclear@27: #define N	0x1000
nuclear@27: #define NP	12   /* 2^N */
nuclear@27: #define NM	0xfff
nuclear@27: 
nuclear@27: #define s_curve(t) (t * t * (3.0f - 2.0f * t))
nuclear@27: 
nuclear@27: #define setup(elem, b0, b1, r0, r1) \
nuclear@27: 	do {							\
nuclear@27: 		scalar_t t = elem + N;		\
nuclear@27: 		b0 = ((int)t) & BM;			\
nuclear@27: 		b1 = (b0 + 1) & BM;			\
nuclear@27: 		r0 = t - (int)t;			\
nuclear@27: 		r1 = r0 - 1.0f;				\
nuclear@27: 	} while(0)
nuclear@27: 
nuclear@27: 
nuclear@27: static int perm[B + B + 2];			/* permuted index from g_n onto themselves */
nuclear@27: static vec3_t grad3[B + B + 2];		/* 3D random gradients */
nuclear@27: static vec2_t grad2[B + B + 2];		/* 2D random gradients */
nuclear@27: static scalar_t grad1[B + B + 2];	/* 1D random ... slopes */
nuclear@27: static int tables_valid;
nuclear@27: 
nuclear@27: static void init_noise()
nuclear@27: {
nuclear@27: 	int i;
nuclear@27: 
nuclear@27: 	/* calculate random gradients */
nuclear@27: 	for(i=0; i<B; i++) {
nuclear@27: 		perm[i] = i;	/* .. and initialize permutation mapping to identity */
nuclear@27: 
nuclear@27: 		grad1[i] = (scalar_t)((rand() % (B + B)) - B) / B;
nuclear@27: 
nuclear@27: 		grad2[i].x = (scalar_t)((rand() % (B + B)) - B) / B;
nuclear@27: 		grad2[i].y = (scalar_t)((rand() % (B + B)) - B) / B;
nuclear@27: 		grad2[i] = v2_normalize(grad2[i]);
nuclear@27: 
nuclear@27: 		grad3[i].x = (scalar_t)((rand() % (B + B)) - B) / B;
nuclear@27: 		grad3[i].y = (scalar_t)((rand() % (B + B)) - B) / B;
nuclear@27: 		grad3[i].z = (scalar_t)((rand() % (B + B)) - B) / B;
nuclear@27: 		grad3[i] = v3_normalize(grad3[i]);
nuclear@27: 	}
nuclear@27: 
nuclear@27: 	/* permute indices by swapping them randomly */
nuclear@27: 	for(i=0; i<B; i++) {
nuclear@27: 		int rand_idx = rand() % B;
nuclear@27: 
nuclear@27: 		int tmp = perm[i];
nuclear@27: 		perm[i] = perm[rand_idx];
nuclear@27: 		perm[rand_idx] = tmp;
nuclear@27: 	}
nuclear@27: 
nuclear@27: 	/* fill up the rest of the arrays by duplicating the existing gradients */
nuclear@27: 	/* and permutations */
nuclear@27: 	for(i=0; i<B+2; i++) {
nuclear@27: 		perm[B + i] = perm[i];
nuclear@27: 		grad1[B + i] = grad1[i];
nuclear@27: 		grad2[B + i] = grad2[i];
nuclear@27: 		grad3[B + i] = grad3[i];
nuclear@27: 	}
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t noise1(scalar_t x)
nuclear@27: {
nuclear@27: 	int bx0, bx1;
nuclear@27: 	scalar_t rx0, rx1, sx, u, v;
nuclear@27: 
nuclear@27: 	if(!tables_valid) {
nuclear@27: 		init_noise();
nuclear@27: 		tables_valid = 1;
nuclear@27: 	}
nuclear@27: 
nuclear@27: 	setup(x, bx0, bx1, rx0, rx1);
nuclear@27: 	sx = s_curve(rx0);
nuclear@27: 	u = rx0 * grad1[perm[bx0]];
nuclear@27: 	v = rx1 * grad1[perm[bx1]];
nuclear@27: 
nuclear@27: 	return lerp(u, v, sx);
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t noise2(scalar_t x, scalar_t y)
nuclear@27: {
nuclear@27: 	int i, j, b00, b10, b01, b11;
nuclear@27: 	int bx0, bx1, by0, by1;
nuclear@27: 	scalar_t rx0, rx1, ry0, ry1;
nuclear@27: 	scalar_t sx, sy, u, v, a, b;
nuclear@27: 
nuclear@27: 	if(!tables_valid) {
nuclear@27: 		init_noise();
nuclear@27: 		tables_valid = 1;
nuclear@27: 	}
nuclear@27: 
nuclear@27: 	setup(x, bx0, bx1, rx0, rx1);
nuclear@27: 	setup(y, by0, by1, ry0, ry1);
nuclear@27: 
nuclear@27: 	i = perm[bx0];
nuclear@27: 	j = perm[bx1];
nuclear@27: 
nuclear@27: 	b00 = perm[i + by0];
nuclear@27: 	b10 = perm[j + by0];
nuclear@27: 	b01 = perm[i + by1];
nuclear@27: 	b11 = perm[j + by1];
nuclear@27: 
nuclear@27: 	/* calculate hermite inteprolating factors */
nuclear@27: 	sx = s_curve(rx0);
nuclear@27: 	sy = s_curve(ry0);
nuclear@27: 
nuclear@27: 	/* interpolate along the left edge */
nuclear@27: 	u = v2_dot(grad2[b00], v2_cons(rx0, ry0));
nuclear@27: 	v = v2_dot(grad2[b10], v2_cons(rx1, ry0));
nuclear@27: 	a = lerp(u, v, sx);
nuclear@27: 
nuclear@27: 	/* interpolate along the right edge */
nuclear@27: 	u = v2_dot(grad2[b01], v2_cons(rx0, ry1));
nuclear@27: 	v = v2_dot(grad2[b11], v2_cons(rx1, ry1));
nuclear@27: 	b = lerp(u, v, sx);
nuclear@27: 
nuclear@27: 	/* interpolate between them */
nuclear@27: 	return lerp(a, b, sy);
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t noise3(scalar_t x, scalar_t y, scalar_t z)
nuclear@27: {
nuclear@27: 	int i, j;
nuclear@27: 	int bx0, bx1, by0, by1, bz0, bz1;
nuclear@27: 	int b00, b10, b01, b11;
nuclear@27: 	scalar_t rx0, rx1, ry0, ry1, rz0, rz1;
nuclear@27: 	scalar_t sx, sy, sz;
nuclear@27: 	scalar_t u, v, a, b, c, d;
nuclear@27: 
nuclear@27: 	if(!tables_valid) {
nuclear@27: 		init_noise();
nuclear@27: 		tables_valid = 1;
nuclear@27: 	}
nuclear@27: 
nuclear@27: 	setup(x, bx0, bx1, rx0, rx1);
nuclear@27: 	setup(y, by0, by1, ry0, ry1);
nuclear@27: 	setup(z, bz0, bz1, rz0, rz1);
nuclear@27: 
nuclear@27: 	i = perm[bx0];
nuclear@27: 	j = perm[bx1];
nuclear@27: 
nuclear@27: 	b00 = perm[i + by0];
nuclear@27: 	b10 = perm[j + by0];
nuclear@27: 	b01 = perm[i + by1];
nuclear@27: 	b11 = perm[j + by1];
nuclear@27: 
nuclear@27: 	/* calculate hermite interpolating factors */
nuclear@27: 	sx = s_curve(rx0);
nuclear@27: 	sy = s_curve(ry0);
nuclear@27: 	sz = s_curve(rz0);
nuclear@27: 
nuclear@27: 	/* interpolate along the top slice of the cell */
nuclear@27: 	u = v3_dot(grad3[b00 + bz0], v3_cons(rx0, ry0, rz0));
nuclear@27: 	v = v3_dot(grad3[b10 + bz0], v3_cons(rx1, ry0, rz0));
nuclear@27: 	a = lerp(u, v, sx);
nuclear@27: 
nuclear@27: 	u = v3_dot(grad3[b01 + bz0], v3_cons(rx0, ry1, rz0));
nuclear@27: 	v = v3_dot(grad3[b11 + bz0], v3_cons(rx1, ry1, rz0));
nuclear@27: 	b = lerp(u, v, sx);
nuclear@27: 
nuclear@27: 	c = lerp(a, b, sy);
nuclear@27: 
nuclear@27: 	/* interpolate along the bottom slice of the cell */
nuclear@27: 	u = v3_dot(grad3[b00 + bz0], v3_cons(rx0, ry0, rz1));
nuclear@27: 	v = v3_dot(grad3[b10 + bz0], v3_cons(rx1, ry0, rz1));
nuclear@27: 	a = lerp(u, v, sx);
nuclear@27: 
nuclear@27: 	u = v3_dot(grad3[b01 + bz0], v3_cons(rx0, ry1, rz1));
nuclear@27: 	v = v3_dot(grad3[b11 + bz0], v3_cons(rx1, ry1, rz1));
nuclear@27: 	b = lerp(u, v, sx);
nuclear@27: 
nuclear@27: 	d = lerp(a, b, sy);
nuclear@27: 
nuclear@27: 	/* interpolate between slices */
nuclear@27: 	return lerp(c, d, sz);
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t fbm1(scalar_t x, int octaves)
nuclear@27: {
nuclear@27: 	int i;
nuclear@27: 	scalar_t res = 0.0f, freq = 1.0f;
nuclear@27: 	for(i=0; i<octaves; i++) {
nuclear@27: 		res += noise1(x * freq) / freq;
nuclear@27: 		freq *= 2.0f;
nuclear@27: 	}
nuclear@27: 	return res;
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t fbm2(scalar_t x, scalar_t y, int octaves)
nuclear@27: {
nuclear@27: 	int i;
nuclear@27: 	scalar_t res = 0.0f, freq = 1.0f;
nuclear@27: 	for(i=0; i<octaves; i++) {
nuclear@27: 		res += noise2(x * freq, y * freq) / freq;
nuclear@27: 		freq *= 2.0f;
nuclear@27: 	}
nuclear@27: 	return res;
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t fbm3(scalar_t x, scalar_t y, scalar_t z, int octaves)
nuclear@27: {
nuclear@27: 	int i;
nuclear@27: 	scalar_t res = 0.0f, freq = 1.0f;
nuclear@27: 	for(i=0; i<octaves; i++) {
nuclear@27: 		res += noise3(x * freq, y * freq, z * freq) / freq;
nuclear@27: 		freq *= 2.0f;
nuclear@27: 	}
nuclear@27: 	return res;
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t turbulence1(scalar_t x, int octaves)
nuclear@27: {
nuclear@27: 	int i;
nuclear@27: 	scalar_t res = 0.0f, freq = 1.0f;
nuclear@27: 	for(i=0; i<octaves; i++) {
nuclear@27: 		res += fabs(noise1(x * freq) / freq);
nuclear@27: 		freq *= 2.0f;
nuclear@27: 	}
nuclear@27: 	return res;
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t turbulence2(scalar_t x, scalar_t y, int octaves)
nuclear@27: {
nuclear@27: 	int i;
nuclear@27: 	scalar_t res = 0.0f, freq = 1.0f;
nuclear@27: 	for(i=0; i<octaves; i++) {
nuclear@27: 		res += fabs(noise2(x * freq, y * freq) / freq);
nuclear@27: 		freq *= 2.0f;
nuclear@27: 	}
nuclear@27: 	return res;
nuclear@27: }
nuclear@27: 
nuclear@27: scalar_t turbulence3(scalar_t x, scalar_t y, scalar_t z, int octaves)
nuclear@27: {
nuclear@27: 	int i;
nuclear@27: 	scalar_t res = 0.0f, freq = 1.0f;
nuclear@27: 	for(i=0; i<octaves; i++) {
nuclear@27: 		res += fabs(noise3(x * freq, y * freq, z * freq) / freq);
nuclear@27: 		freq *= 2.0f;
nuclear@27: 	}
nuclear@27: 	return res;
nuclear@27: }