From 5efc7885e1c3959aa165be640858ffb3f8a5860b Mon Sep 17 00:00:00 2001 From: sanine Date: Tue, 31 May 2022 20:52:15 -0500 Subject: refactor: remove modules/ folder --- src/BrushSelector.js | 72 ------------ src/Geometry/Geometry.js | 233 +++++++++++++++++++++++++++++++++++++ src/Geometry/Geometry.test.js | 259 ++++++++++++++++++++++++++++++++++++++++++ src/Terrain.js | 206 --------------------------------- src/Util/Util.js | 20 ++++ src/Util/Util.test.js | 41 +++++++ src/main.js | 39 ------- src/modules/Geometry.js | 233 ------------------------------------- src/modules/Geometry.test.js | 259 ------------------------------------------ src/modules/Mouse.js | 53 --------- src/modules/Util.js | 20 ---- src/modules/Util.test.js | 23 ---- src/modules/test-assert.js | 21 ---- src/test-assert.js | 21 ++++ 14 files changed, 574 insertions(+), 926 deletions(-) delete mode 100644 src/BrushSelector.js create mode 100644 src/Geometry/Geometry.js create mode 100644 src/Geometry/Geometry.test.js delete mode 100644 src/Terrain.js create mode 100644 src/Util/Util.js create mode 100644 src/Util/Util.test.js delete mode 100644 src/main.js delete mode 100644 src/modules/Geometry.js delete mode 100644 src/modules/Geometry.test.js delete mode 100644 src/modules/Mouse.js delete mode 100644 src/modules/Util.js delete mode 100644 src/modules/Util.test.js delete mode 100644 src/modules/test-assert.js create mode 100644 src/test-assert.js (limited to 'src') diff --git a/src/BrushSelector.js b/src/BrushSelector.js deleted file mode 100644 index ea72990..0000000 --- a/src/BrushSelector.js +++ /dev/null @@ -1,72 +0,0 @@ -import { lerp } from './modules/Util.js'; - -class BrushSelector { - constructor(rootId, canvas, terrain) { - console.log('hi'); - this.canvas = canvas; - this.terrain = terrain; - this.div = document.createElement('div'); - this.div.setAttribute('style', 'position: absolute; padding: 10px; display: block; right: 10px; bottom: 10px;'); - - this.radiusSlider = this.addSlider('Brush Size', 0, 500); - this.strengthSlider = this.addSlider('Brush Strength', 0, 100); - - this.addBrush('Raise', (pt, str) => pt.height += 5 * str); - this.addBrush('Lower', (pt, str) => pt.height -= 5 * str); - this.addBrush('Round', (pt, str) => { - const neighbors = this.terrain.getNeighbors(pt); - let avg = 0; - for (let n of neighbors) avg += n.height; - avg /= neighbors.length; - pt.height = lerp(pt.height, avg, str); - }); - - const root = document.getElementById(rootId); - root.appendChild(this.div); - } - - addSlider(label, min, max) { - const l = document.createElement('label'); - const text = document.createTextNode(label); - l.appendChild(text); - this.div.appendChild(l); - - const s = document.createElement('input'); - s.type = 'range'; - s.min = min; - s.max = max; - s.value = 0.5 * (max + min); - this.div.appendChild(s); - return s; - } - - addBrush(name, f) { - const button = document.createElement('button'); - const text = document.createTextNode(name); - button.appendChild(text); - - button.onclick = () => { - if (this.button === button) return // already selected - if (this.button) this.button.classList.remove('selected'); - button.classList.add('selected'); - this.button = button; - this.f = f; - }; - - if (!this.button) button.onclick(); - - this.div.appendChild(button); - } - - apply() { - const radius = this.radiusSlider.value; - const str = this.strengthSlider.value/this.strengthSlider.max; - this.terrain.applyBrush( - this.canvas.mouse.drawingPos.x, - this.canvas.mouse.drawingPos.y, - this.f, str, this.canvas.pixelsToUnits(radius) - ); - } -} - -export default BrushSelector; diff --git a/src/Geometry/Geometry.js b/src/Geometry/Geometry.js new file mode 100644 index 0000000..43f277f --- /dev/null +++ b/src/Geometry/Geometry.js @@ -0,0 +1,233 @@ +'use strict'; + +function dist(a, b) { + return Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2); +} + +/* 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 { dist, AABB, QTNode, QuadTree }; diff --git a/src/Geometry/Geometry.test.js b/src/Geometry/Geometry.test.js new file mode 100644 index 0000000..0b81438 --- /dev/null +++ b/src/Geometry/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 { + 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 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/Terrain.js b/src/Terrain.js deleted file mode 100644 index 291a4fc..0000000 --- a/src/Terrain.js +++ /dev/null @@ -1,206 +0,0 @@ -'use strict'; - -import Voronoi from './3rdparty/rhill-voronoi-core.js'; - -import { lerp, clamp, useAverage } from './modules/Util.js'; -import { dist, AABB, QuadTree } from './modules/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 ({x: Math.random(), y: Math.random()}); - - this.min_height = 0; - this.max_height = 0; - - let seed_points = []; - for (let i=0; i (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)); - } - - - getNeighbors(point) { - const indices = Array.from(this.graph[point.index]); - return indices.map( index => this.voronoi.vertices[index] ); - } - - - renderGrid(ct) { - ct.save(); - ct.lineWidth = 0.001; - for (let edge of this.voronoi.edges) { - ct.fillStyle = `hsl(${edge.va.height}, 100%, 50%)`; - ct.beginPath(); - ct.arc(edge.va.x, edge.va.y, 0.0005, 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(); - } - - render(ct) { - function rgb(r, g, b) { - this.r = r; this.g = g; this.b = b; - } - const renderRgb = rgb => `rgb(${rgb.r}, ${rgb.g}, ${rgb.b})`; - const lerpColors = (a, b, alpha) => new rgb( - lerp(a.r, b.r, alpha), - lerp(a.g, b.g, alpha), - lerp(a.b, b.b, alpha) - ); - const getBucket = (value, min, max, numBuckets) => { - const delta = max - min; - const step = delta/numBuckets; - return clamp(Math.floor((value-min)/step), 0, numBuckets-1); - } - const getColor = (value, min, max, colors) => { - if (value < min) return colors[0]; - if (value >= max) return colors[colors.length-1]; - - const step = (max - min)/(colors.length - 1); - - const index = getBucket(value, min, max, colors.length-1); - const alpha = (value - (index*step) - min)/step; - const color = lerpColors( - colors[index], colors[index+1], - alpha - ); - if (color.r <= 0) - console.log(value, index, alpha, color); - return color; - } - - const colors = [ - /* ocean */ - new rgb(31, 59, 68), - new rgb(68, 130, 149), - - /* land */ - new rgb(229, 199, 169), - new rgb(198, 133, 67), - new rgb(117, 89, 61), - - /* mountain */ - new rgb(82, 74, 64), - new rgb(82, 74, 64), - new rgb(255, 255, 255), - ]; - ct.save(); - - for (let cell of this.voronoi.cells) { - ct.beginPath(); - - let height = 0; - let count = 1; - for (let edge of cell.halfedges) { - const p0 = edge.getStartpoint(); - const p1 = edge.getEndpoint(); - height += p0.height; - count += 1; - ct.lineTo(p0.x, p0.y); - ct.lineTo(p1.x, p1.y); - } - ct.closePath(); - height /= count; - height = 10 * Math.floor(height/10); - const color = getColor(height, 0, 100, colors); - if (color.r <=0) console.log(color); - ct.fillStyle = renderRgb(color); - ct.strokeStyle = renderRgb(color); - ct.stroke(); - ct.fill(); - } - - ct.restore(); - } -} - -export { lloydRelax }; -export default Terrain; diff --git a/src/Util/Util.js b/src/Util/Util.js new file mode 100644 index 0000000..165d1d0 --- /dev/null +++ b/src/Util/Util.js @@ -0,0 +1,20 @@ +function useAverage() { + var avg = 0; + let weight = 0; + const append = value => { + avg = (weight * avg) + value; + weight += 1; + avg = avg/weight; + } + + return [() => avg, append]; +} + +function clamp(value, min, max) { + return Math.min(Math.max(value, min), max); +} + +function lerp(a, b, alpha) { + return ((1-alpha)*a) + (alpha*b); +} +export { useAverage, clamp, lerp }; diff --git a/src/Util/Util.test.js b/src/Util/Util.test.js new file mode 100644 index 0000000..9c6adbf --- /dev/null +++ b/src/Util/Util.test.js @@ -0,0 +1,41 @@ +import { test, assert} from '../test-assert.js'; +import { useAverage, clamp, lerp } 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)); +}); + + +test('Clamp correctly constrains values', () => { + assert.equal(clamp(5, 0, 10), 5); + assert.equal(clamp(-1, 0, 10), 0); + assert.equal(clamp(15, 0, 10), 10); +}); + + +test ('Lerp correctly interpolates values', () => { + const a = 15; + const b = 10; + assert.equal(lerp(a, b, 0), a); + assert.equal(lerp(a, b, 1), b); + assert.equal(lerp(a, b, 0.5), (a+b)/2); + assert.equal(lerp(a, b, 0.25), (3*a + b)/4); + assert.equal(lerp(a, b, 0.75), (a + (3*b))/4); +}); diff --git a/src/main.js b/src/main.js deleted file mode 100644 index f73a17b..0000000 --- a/src/main.js +++ /dev/null @@ -1,39 +0,0 @@ -import Terrain from './Terrain.js'; -import Canvas from './Canvas.js'; -import Brush from './Brush.js'; -import BrushSelector from './BrushSelector.js'; - -const $ = id => document.getElementById(id) - -window.onload = () => { - const canvas = new Canvas('root'); - const terrain = new Terrain(); - const selector = new BrushSelector('root', canvas, terrain); - - let brushing = false; - - canvas.onMouseDown = e => { - if (e.button == 0) brushing = true; - }; - canvas.onMouseUp = e => { - if (e.button == 0) brushing = false; - }; - - const pos = canvas.mouse.drawingPos; - canvas.onMouseMove = () => { - if (brushing) selector.apply(); - canvas.draw(); - }; - - canvas.onDraw = ct => { - terrain.render(ct); - - ct.strokeStyle = '#fff'; - ct.lineWidth = canvas.pixelsToUnits(1); - ct.beginPath(); - ct.arc(pos.x, pos.y, canvas.pixelsToUnits(selector.radiusSlider.value), 0, 2*Math.PI); - ct.closePath(); - ct.stroke(); - }; - canvas.draw(); -} diff --git a/src/modules/Geometry.js b/src/modules/Geometry.js deleted file mode 100644 index 43f277f..0000000 --- a/src/modules/Geometry.js +++ /dev/null @@ -1,233 +0,0 @@ -'use strict'; - -function dist(a, b) { - return Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2); -} - -/* 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 { dist, AABB, QTNode, QuadTree }; diff --git a/src/modules/Geometry.test.js b/src/modules/Geometry.test.js deleted file mode 100644 index 925a53d..0000000 --- a/src/modules/Geometry.test.js +++ /dev/null @@ -1,259 +0,0 @@ -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 { - 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 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 deleted file mode 100644 index 0b8f922..0000000 --- a/src/modules/Mouse.js +++ /dev/null @@ -1,53 +0,0 @@ -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/Util.js b/src/modules/Util.js deleted file mode 100644 index 165d1d0..0000000 --- a/src/modules/Util.js +++ /dev/null @@ -1,20 +0,0 @@ -function useAverage() { - var avg = 0; - let weight = 0; - const append = value => { - avg = (weight * avg) + value; - weight += 1; - avg = avg/weight; - } - - return [() => avg, append]; -} - -function clamp(value, min, max) { - return Math.min(Math.max(value, min), max); -} - -function lerp(a, b, alpha) { - return ((1-alpha)*a) + (alpha*b); -} -export { useAverage, clamp, lerp }; diff --git a/src/modules/Util.test.js b/src/modules/Util.test.js deleted file mode 100644 index 000d54e..0000000 --- a/src/modules/Util.test.js +++ /dev/null @@ -1,23 +0,0 @@ -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 deleted file mode 100644 index 7be2989..0000000 --- a/src/modules/test-assert.js +++ /dev/null @@ -1,21 +0,0 @@ -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 }; diff --git a/src/test-assert.js b/src/test-assert.js new file mode 100644 index 0000000..7be2989 --- /dev/null +++ b/src/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 }; -- cgit v1.2.1