diff options
Diffstat (limited to 'src/modules')
| -rw-r--r-- | src/modules/Geometry.js | 229 | ||||
| -rw-r--r-- | src/modules/Geometry.test.js | 259 | ||||
| -rw-r--r-- | src/modules/Mouse.js | 53 | ||||
| -rw-r--r-- | src/modules/Terrain.js | 111 | ||||
| -rw-r--r-- | src/modules/Util.js | 13 | ||||
| -rw-r--r-- | src/modules/Util.test.js | 23 | ||||
| -rw-r--r-- | src/modules/test-assert.js | 21 |
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 }; |