refactor: move everything into src/ subdirectory

7 files changed, 709 insertions, 0 deletions

diff --git a/src/modules/Geometry.js b/src/modules/Geometry.js
new file mode 100644
index 0000000..628512b
--- /dev/null
+++ b/src/modules/Geometry.js
@@ -0,0 +1,229 @@
+'use strict';
+
+/* AABB - axis-aligned bounding box */
+class AABB {
+	/* create a new AABB */
+	constructor(x, y, width, height) {
+		this.x = x; this.y = y;
+		this.width = width; this.height = height;
+	}
+
+	/* check if a point is inside the box
+	 *
+	 * a "point" is any object with an x- and y-coordinate.
+	 * any other data in the object is ignored.
+	 *
+	 * returns true if the point is inside, and false otherwise.
+	 */
+	contains(point) {
+		if (point.x >= this.x && point.y >= this.y
+		    && point.x < this.x + this.width
+			&& point.y < this.y + this.height)
+			return true;
+		return false;
+	}
+
+	/* check if two AABBs overlap */
+	intersects(aabb) {
+		const overlap = (ax, arange, bx, brange) => {
+			const range = ax < bx ? arange : brange;
+			if (Math.abs(bx - ax) < range)
+				return true;
+			return false;
+		};
+
+		if (overlap(this.x, this.width, aabb.x, aabb.width) &&
+		    overlap(this.y, this.height, aabb.y, aabb.height))
+			return true;
+		return false;
+	}
+}
+
+
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ *
+ * QUADTREE
+ *
+ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ */
+
+/* lil enum class for QTNode types */
+class QTNodeType {
+	constructor(name) { this.name = name; }
+	toString() { return `QTNode.${this.name}`; }
+}
+
+
+/* nodes in a quadtree
+ *
+ * they can be either "Empty" (no point),
+ * "Leaf" (they contain a point and no sub-nodes),
+ * or "Branch" (they contain no point and have sub-nodes).
+ * There are no QTNodes with children and point data.
+ */
+class QTNode {
+	static Empty = new QTNodeType('Empty');
+	static Leaf = new QTNodeType('Leaf');
+	static Branch = new QTNodeType('Branch');
+
+	constructor(x, y, width, height) {
+		this.aabb = new AABB(x, y, width, height);
+		/* all QTNodes start empty */
+		this.type = QTNode.Empty;
+	}
+
+	/* insert a point into the tree, starting with this node
+	 *
+	 * as above, points are just objects with 'x' and 'y' values.
+	 * other data in the point is not examined and is incorporated into the
+	 * tree.
+	 *
+	 * this function returns false if the point was not contained in the bounding box,
+	 * and true otherwise. inserting a point may cause the node's type to change
+	 * (e.g. a Leaf node would become a Branch node and its point data would be
+	 * moved lower in the tree).
+	 */
+	insert(point) {
+		if (this.aabb.contains(point)) {
+			if (this.type == QTNode.Empty) {
+				/* empty nodes are easy -- just switch to Leaf and add the point */
+				this.type = QTNode.Leaf;
+				this.point = point;
+				return true;
+			}
+			else if (this.type == QTNode.Leaf) {
+				/* Leaf must become a Branch */
+				this.type = QTNode.Branch;
+				this.subdivide();
+
+				/* move current point into a child */
+				let result = this.insert(this.point);
+				if (!result) return false;
+				this.point = undefined;
+
+				/* add new point */
+				return this.insert(point);
+			}
+			else {
+				/* This is a Branch, and we should insert into a child node */
+				/* just try them all until we find one where the point can go */
+				if (this.subnode[0].insert(point)) return true;
+				if (this.subnode[1].insert(point)) return true;
+				if (this.subnode[2].insert(point)) return true;
+				if (this.subnode[3].insert(point)) return true;
+				return false; // something strange has happened!!
+			}
+		}
+		/* point not in this node, return false */
+		return false;
+	}
+
+	/* subdivide the node into four child nodes
+	 *
+	 * under normal circumstances, the user should not call this function --
+	 * it's just meant to be used during insertion.
+	 */
+	subdivide() {
+		/* some useful constants */
+		const x = this.aabb.x; const y = this.aabb.y;
+		const w = this.aabb.width/2; const h = this.aabb.height/2;
+
+		/* generate sub-nodes */
+		this.subnode = [
+			new QTNode(x, y, w, h),
+			new QTNode(x+w, y, w, h),
+			new QTNode(x, y+h, w, h),
+			new QTNode(x+w, y+h, w, h),
+		];
+	}
+
+	/* query the tree for all points contained within a region recursively
+	 *
+	 * returns an array containing any points in the tree beneath this node
+	 * that are inside the supplied AABB.
+	 */
+	getPointsInRegion(aabb) {
+		if (this.type == QTNode.Empty) return [];
+		if (!this.aabb.intersects(aabb)) return [];
+		if (this.type == QTNode.Leaf) return [this.point];
+		
+		/* Branch - recusively query children */
+		return [
+			...this.subnode[0].getPointsInRegion(aabb),
+			...this.subnode[1].getPointsInRegion(aabb),
+			...this.subnode[2].getPointsInRegion(aabb),
+			...this.subnode[3].getPointsInRegion(aabb),
+		];
+	}
+}
+
+
+/* full-blown quadtree! */
+class QuadTree {
+	/* create a new quadtree */
+	constructor(width, height) {
+		this.root = new QTNode(0, 0, width, height);
+	}
+
+	/* insert a point into the tree */
+	insert(point) {
+		return this.root.insert(point);
+	}
+
+	/* get the closest tree point to the given point */
+	closest(point) {
+		/* the algorithm goes like this:
+		 *   1. find the smallest node containing the point
+		 *   2. the closest point is within a box at most 4x the
+		 *      size of that lowest node, so query all points within
+		 *      such a region.
+		 *   3. brute-force within the list of points.
+		 */
+
+		/* recursively find the node containing a point */
+		const getLeaf = (point, node) => {
+			/* is point in bounding box? */
+			if (!node.aabb.contains(point)) return null;
+			/* is this a Leaf or Empty node? */
+			if (node.type == QTNode.Empty ||
+			    node.type == QTNode.Leaf) return node;
+			
+			/* this is a branch node, so recurse */
+			for (let subnode of node.subnode) {
+				const leaf = getLeaf(point, subnode);
+				if (leaf !== null) return leaf;
+			}
+
+			/* should never get here */
+			return null;
+		}
+
+		/* find the node, starting at the tree root */
+		const leaf = getLeaf(point, this.root);
+		if (leaf === null) return leaf;
+
+		/* construct the 4x AABB, centered on the query point */
+		const dim = 2*Math.max(leaf.aabb.width, leaf.aabb.height);
+		const region = new AABB(point.x - dim, point.y - dim, 2*dim, 2*dim);
+
+		/* get all points */
+		const points = this.root.getPointsInRegion(region);
+
+		/* brute force search within the small list */
+		let closest = null;
+		let min_dist = 100 * this.root.aabb.width * this.root.aabb.height;
+		const dist = (a, b) => (a.x - b.x)**2 + (a.y - b.y)**2;
+		for (let pt of points) {
+			const d = dist(point, pt);
+			if (d < min_dist) {
+				closest = pt;
+				min_dist = d;
+			}
+		}
+
+		/* done! */
+		return closest;
+	}
+}
+
+export { AABB, QTNode, QuadTree };
diff --git a/src/modules/Geometry.test.js b/src/modules/Geometry.test.js
new file mode 100644
index 0000000..925a53d
--- /dev/null
+++ b/src/modules/Geometry.test.js
@@ -0,0 +1,259 @@
+import { test, assert } from './test-assert.js';
+import { AABB, QTNode, QuadTree } from './Geometry.js';
+
+const RUN_BENCHMARKS = false;
+
+
+test('AABB correctly contains/excludes points', () => {
+	const box = new AABB(0, 0, 1, 1);
+
+	// interior
+	assert.ok(box.contains({ x: 0.5, y: 0.5 }));
+
+	// upper left
+	assert.ok(!box.contains({ x: -1, y: -1 }));
+
+	// above
+	assert.ok(!box.contains({ x: 0.5, y: -1}));
+
+	// upper right
+	assert.ok(!box.contains({ x: 2, y: -1 }));
+
+	// left
+	assert.ok(!box.contains({ x: -1, y: 0.5 }));
+
+	// right
+	assert.ok(!box.contains({ x: 2, y: 0.5}));
+
+	// lower left
+	assert.ok(!box.contains({ x: -1, y: 2 }));
+
+	// below 
+	assert.ok(!box.contains({ x: 0.5, y: 2}));
+
+	// lower right
+	assert.ok(!box.contains({ x: 2, y: 2 }));
+});
+
+
+test('AABB correctly intersects other AABBs', () => {
+	const box = new AABB(1, 1, 4, 4);
+
+	// interior
+	assert.ok(box.intersects(new AABB(2, 2, 2, 2,)));
+
+	// upper left
+	assert.ok(box.intersects(new AABB(0, 0, 4, 4)));
+	assert.ok(!box.intersects(new AABB(0, 0, 0.5, 0.5)));
+
+	// above
+	assert.ok(box.intersects(new AABB(2, 0, 2, 2)));
+	assert.ok(!box.intersects(new AABB(2, 0, 2, 0.5)));
+
+	// upper right
+	assert.ok(box.intersects(new AABB(2, 0, 4, 2)));
+	assert.ok(!box.intersects(new AABB(6, 0, 4, 2)));
+
+	// left
+	assert.ok(box.intersects(new AABB(0, 2, 2, 2)));
+	assert.ok(!box.intersects(new AABB(0, 2, 0.5, 2)));
+
+	// right
+	assert.ok(box.intersects(new AABB(4, 2, 2, 2)));
+	assert.ok(!box.intersects(new AABB(6, 2, 2, 2)));
+
+	// lower left
+	assert.ok(box.intersects(new AABB(0, 4, 4, 4)));
+	assert.ok(!box.intersects(new AABB(0, 6, 0.5, 0.5)));
+
+	// below
+	assert.ok(box.intersects(new AABB(2, 4, 2, 2)));
+	assert.ok(!box.intersects(new AABB(2, 6, 2, 0.5)));
+
+	// lower right
+	assert.ok(box.intersects(new AABB(2, 4, 4, 2)));
+	assert.ok(!box.intersects(new AABB(6, 6, 4, 2)));
+});
+
+
+test('AABB correctly handles points at the edges', () => {
+	const box = new AABB(0, 0, 1, 1);
+
+	assert.ok(box.contains({ x: 0, y: 0 }));
+	assert.ok(box.contains({ x: 0.5, y: 0 }));
+	assert.ok(box.contains({ x: 0, y: 0.5 }));
+
+	// bad corners
+	assert.ok(!box.contains({ x: 1, y: 0 }));
+	assert.ok(!box.contains({ x: 0, y: 1 }));
+	assert.ok(!box.contains({ x: 1, y: 1 }));
+
+	// bad edges
+	assert.ok(!box.contains({ x: 1, y: 0.5 }));
+	assert.ok(!box.contains({ x: 0.5, y: 1 }));
+});
+
+
+test('QTNode correctly inserts points', () => {
+	const node = new QTNode(0, 0, 1, 1);
+	assert.equal(node.type.toString(), 'QTNode.Empty');
+
+	let result = node.insert({ x: -1, y: -1 }); // out of range, should not insert
+	assert.ok(!result);
+	assert.equal(node.type.toString(), 'QTNode.Empty');
+
+	result = node.insert({ x: 0.5, y: 0.5 }); // in range
+	assert.ok(result);
+	assert.equal(node.type.toString(), 'QTNode.Leaf');
+	assert.deepEqual(node.point, { x: 0.5, y: 0.5 });
+});
+
+
+test('QTNode correctly subdivides', () => {
+	const node = new QTNode(0, 0, 2, 2);
+	assert.ok(!node.subnode);
+	node.subdivide();
+	assert.equal(node.subnode.length, 4);
+
+	assert.deepEqual(node.subnode[0], new QTNode(0, 0, 1, 1));
+	assert.deepEqual(node.subnode[1], new QTNode(1, 0, 1, 1));
+	assert.deepEqual(node.subnode[2], new QTNode(0, 1, 1, 1));
+	assert.deepEqual(node.subnode[3], new QTNode(1, 1, 1, 1));
+});
+
+
+test('QTNode correctly inserts multiple points', () => {
+	const node = new QTNode(0, 0, 2, 2);
+	
+	const p0 = { x: 1, y: 1 };
+	const p1 = { x: 0.5, y: 0.5 };
+	const oob = { x: 10, y: 15 };
+
+	assert.ok(node.insert(p0));
+	assert.ok(node.insert(p1));
+	assert.ok(!node.insert(oob));
+
+	assert.equal(node.type.toString(), 'QTNode.Branch');
+	
+	assert.equal(node.subnode[0].type.toString(), 'QTNode.Leaf');
+	assert.deepEqual(node.subnode[0].point, p1);
+
+	assert.equal(node.subnode[1].type.toString(), 'QTNode.Empty');
+	assert.equal(node.subnode[2].type.toString(), 'QTNode.Empty');
+
+	assert.equal(node.subnode[3].type.toString(), 'QTNode.Leaf');
+assert.deepEqual(node.subnode[3].point, p0);
+});
+
+
+const randomPoint = () => ({ x: Math.random(), y: Math.random() });
+
+
+test('QTNode correctly returns points in region', () => {
+	const node = new QTNode(0, 0, 1, 1);
+	let points = [];
+	for (let i=0; i<100; i++) {
+		const pt = randomPoint();
+		node.insert(pt);
+		points.push(pt);
+	}
+
+	const pointsInRegion = aabb => {
+		let pts = [];
+		for (let pt of points) {
+			if (aabb.contains(pt)) pts.push(pt);
+		}
+		return pts;
+	};
+
+	const region = new AABB(0.25, 0.25, 0.5, 0.5);
+	let bf_points = pointsInRegion(region);
+	let qt_points = node.getPointsInRegion(region);
+	const compare = (a, b) => {
+		if (a.x == b.x)
+			return b.y - a.y;
+		return b.x - a.x;
+	};
+	bf_points.sort(compare);
+	qt_points.sort(compare);
+	assert.deepEqual(bf_points, qt_points);});
+
+
+test('QuadTree correctly finds closest point for 10,000 random points', () => {
+	const tree = new QuadTree(1, 1);
+
+	let points = [];
+	for (let i=0; i<10000; i++) {
+		const pt = randomPoint();
+		tree.insert(pt);
+		points.push(pt);
+	}
+	
+	const distance = (a, b) => Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2);
+	const bf_closest = a => {
+		let closest = null;
+		let min_dist = 1000;
+		for (let b of points) {
+			let d = distance(a, b);
+			if (d < min_dist) {
+				min_dist = d;
+				closest = b;
+			}
+		}
+		return closest;
+	}
+
+	for (let i=0; i<10000; i++) {
+		const pt = randomPoint();
+		assert.deepEqual(bf_closest(pt), tree.closest(pt));
+	}
+});
+
+
+function benchmark(desc, f, iterations) {
+	process.stdout.write(`${desc}: `);
+	const start = process.uptime();
+	for (let i=0; i<iterations; i++) f();
+	const elapsed = process.uptime() - start;
+	console.log(`${elapsed} seconds`);
+}
+
+const closest_benchmark = () => {
+	const n_points = 1e5;
+	const iterations = 1e4;
+	console.log(`> benchmark get closest of ${n_points} random points ${iterations} times`);
+
+	const tree = new QuadTree(1, 1);
+	let points = [];
+	for (let i=0; i<n_points; i++) {
+		const pt = randomPoint();
+		tree.insert(pt);
+		points.push(pt);
+	}
+
+	const distance = (a, b) => Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2);
+	const bf_closest = a => {
+		let closest = null;
+		let min_dist = 1000;
+		for (let b of points) {
+			let d = distance(a, b);
+			if (d < min_dist) {
+				min_dist = d;
+				closest = b;
+			}
+		}
+		return closest;
+	}
+
+	benchmark('\tbrute force', () => {
+		const pt = randomPoint();
+		bf_closest(pt);
+	}, iterations);
+
+	benchmark('\tquadtree', () => {
+		const pt = randomPoint();
+		tree.closest(pt);
+	}, iterations);
+}
+if (RUN_BENCHMARKS)
+	closest_benchmark();
diff --git a/src/modules/Mouse.js b/src/modules/Mouse.js
new file mode 100644
index 0000000..0b8f922
--- /dev/null
+++ b/src/modules/Mouse.js
@@ -0,0 +1,53 @@
+class Mouse {
+	constructor(ct) {
+		this.ct = ct;
+		this.x = 0;
+		this.y = 0;
+		this.radius = 0.005;
+		this.show = false;
+		this.pressed = false;
+		this.onMove = null;
+
+		window.addEventListener('mousemove', e => {
+			/* get current transform matrix */
+			const matrix = this.ct.getTransform();
+			matrix.invertSelf();
+
+			const x = e.offsetX; const y = e.offsetY;
+			this.x = matrix.a*x + matrix.b*y;
+			this.y = matrix.c*x + matrix.d*y;
+			
+			if (this.onMove) this.onMove();
+		});
+
+		const root = document.getElementById('root');
+
+		root.addEventListener('mouseover', e => {
+			e = e ? e : window.event;
+			this.show = true;
+		});
+
+		root.addEventListener('mouseout', e => {
+			e = e ? e: window.event;
+			this.show = false;
+		});
+	}
+
+	render(ct) {
+		if (!this.show) return;
+		console.log(this.radius);
+		ct.save();
+
+		ct.strokeStyle = '#fff';
+		
+		ct.beginPath();
+		ct.arc(this.x, this.y, this.radius, 0, 2*Math.PI);
+		ct.closePath();
+		ct.stroke();
+
+		ct.restore();
+	}
+}
+
+
+export default Mouse;
diff --git a/src/modules/Terrain.js b/src/modules/Terrain.js
new file mode 100644
index 0000000..21908ac
--- /dev/null
+++ b/src/modules/Terrain.js
@@ -0,0 +1,111 @@
+'use strict';
+
+import Voronoi from './3rdparty/rhill-voronoi-core.js';
+
+import { useAverage } from './Util.js';
+import { AABB, QuadTree } from './Geometry.js';
+
+
+/* from here on up, we always assume that points live in the range [(0,0), (1,1)) */
+
+function lloydRelax(point_set, density) {
+	/* setup quadtree and averages */
+	let tree = new QuadTree(1,1);
+	let averages = {};
+	for (let i=0; i<point_set.length; i++) {
+		const point = point_set[i];
+		point.index = i;
+		tree.insert(point);
+
+		let [avg, append] = useAverage();
+		const cent_x = { avg, append };
+		[avg, append] = useAverage();
+		const cent_y = { avg, append };
+		averages[i] = { cent_x, cent_y };
+	}
+
+	/* compute average centroids */
+	for (let x=0; x<1; x += 1/density) {
+		for (let y=0; y<1; y += 1/density) {
+			const point = { x, y };
+			const closest = tree.closest(point);
+			const { cent_x, cent_y } = averages[closest.index];
+			cent_x.append(point.x);
+			cent_y.append(point.y);
+		}
+	}
+
+	/* return centroid points */
+	const result = [];
+	for (let i=0; i<point_set.length; i++) {
+		const point = { x: averages[i].cent_x.avg(), y: averages[i].cent_y.avg() };
+		result.push(point);
+	}
+	return result;
+}
+
+
+class Terrain {
+	constructor() {
+		const N_SEED_POINTS = 2**12;
+		const N_RELAX_ITERATIONS = 1;
+		const RELAX_DENSITY = 400;
+		const randomPoint = () => ({x: Math.random(), y: Math.random()});
+
+		this.min_height = 0;
+		this.max_height = 0;
+
+		let seed_points = [];
+		for (let i=0; i<N_SEED_POINTS; i++) seed_points.push(randomPoint());
+
+		for (let i=0; i<N_RELAX_ITERATIONS; i++)
+			lloydRelax(seed_points, RELAX_DENSITY);
+
+		const v = new Voronoi();
+		this.graph = v.compute(seed_points, {xl: 0, xr: 1, yt: 0, yb: 1});
+
+		this.tree = new QuadTree(1,1);
+		for (let v of this.graph.vertices) {
+			v.height = 0;
+			this.tree.insert(v);
+		}
+	}
+
+
+	applyBrush(x, y, f, strength, radius) {
+		const region = new AABB(x-radius, y-radius, 2*radius, 2*radius);
+		const points = this.tree.root.getPointsInRegion(region);
+		
+		const dist2 = (a, b) => (a.x - b.x)**2 + (a.y - b.y)**2;
+
+		const sigma = radius/3;
+		const beta = 1/(2*sigma*sigma);
+		const center = { x, y };
+		const power = pt => Math.exp(-beta * dist2(pt, center));
+		
+		for (let pt of points) f(pt, strength * power(pt));
+	}
+
+
+	renderGrid(ct) {
+		ct.save();
+		ct.lineWidth = 0.001;
+		for (let edge of this.graph.edges) {
+			ct.fillStyle = `hsl(${edge.va.height}, 100%, 50%)`;
+			ct.beginPath();
+			ct.arc(edge.va.x, edge.va.y, 0.005, 0, 2*Math.PI);
+			ct.closePath();
+			ct.fill();
+
+			ct.beginPath();
+			ct.moveTo(edge.va.x, edge.va.y);
+			ct.lineTo(edge.vb.x, edge.vb.y);
+			ct.closePath();
+			ct.stroke();
+		}
+		ct.restore();
+	}
+}
+
+export { lloydRelax };
+export default Terrain;
diff --git a/src/modules/Util.js b/src/modules/Util.js
new file mode 100644
index 0000000..cbe466d
--- /dev/null
+++ b/src/modules/Util.js
@@ -0,0 +1,13 @@
+function useAverage() {
+	var avg = 0;
+	let weight = 0;
+	const append = value => {
+		avg = (weight * avg) + value;
+		weight += 1;
+		avg = avg/weight;
+	}
+
+	return [() => avg, append];
+}
+
+export { useAverage };
diff --git a/src/modules/Util.test.js b/src/modules/Util.test.js
new file mode 100644
index 0000000..000d54e
--- /dev/null
+++ b/src/modules/Util.test.js
@@ -0,0 +1,23 @@
+import { test, assert} from './test-assert.js';
+import { useAverage } from './Util.js';
+
+
+test('Average correctly accumulates an average', () => {
+	let [avg, avg_append] = useAverage();
+	let data = [];
+	for (let i=0; i<5000; i++) {
+		let d = Math.random();
+		data.push(d);
+		avg_append(d);
+	}
+
+	let manual_average = 0;
+	for (let d of data) manual_average += d;
+	manual_average /= data.length;
+
+	const precision = (decimalPlaces, num) => {
+		const theta = 10**decimalPlaces;
+		return Math.floor(num * theta) / theta;
+	};
+	assert.equal(precision(5, avg()), precision(5, manual_average));
+});
diff --git a/src/modules/test-assert.js b/src/modules/test-assert.js
new file mode 100644
index 0000000..7be2989
--- /dev/null
+++ b/src/modules/test-assert.js
@@ -0,0 +1,21 @@
+import { strict as assert } from 'node:assert';
+
+function test(description, func)
+{
+	process.stdout.write(description);
+	let error = null;
+	try {
+		func();
+	}
+	catch(err) {
+		error = err;
+	}
+
+	if (error) {
+		console.log(' - FAIL'); 
+		console.log(error);
+	}
+	else console.log(' - OK');
+}
+
+export { test, assert };