Cube-World

The shape of hesitation. A slow dissolution of a perfect idea.

Log in to post a comment.

"use strict";

//////////////////////////////////////////////////
// PRNG
//
const PRNG = () => {
	let seed = 0;

	function random () {
		const s = seed;
		seed = (Math.imul(s, 747796405) + 2891336453) | 0;
		const word = Math.imul((s >>> ((s >>> 28) + 4)) ^ s, 277803737);
		return (((word >>> 22) ^ word) >>> 0) / 4294967296;
	}

	function randomize (s) {
		seed = s | 0;
		return api;
	}

	function randArray (a) {
		return a[Math.floor(random() * a.length)];
	}

	function Noise3D() {
	    const F3 = 1 / 3;
		const G3 = 1 / 6;
		const perm = new Uint32Array(512);
		const gradIndex = new Uint8Array(256);
		const grad = new Int32Array([
			 1,  1,  0,
			-1,  1,  0,
			 1, -1,  0,
			-1, -1,  0,
			 1,  0,  1,
			-1,  0,  1,
			 1,  0, -1,
			-1,  0, -1,
			 0,  1,  1,
			 0, -1,  1,
			 0,  1, -1,
			 0, -1, -1,
		]);

		{
			const s = seed;
			const p = new Uint32Array(256);
			for (let i = 0; i < 256; i++) p[i] = i;
			for (let i = 255; i > 0; i--) {
				const n = Math.floor((i + 1) * random());
				const q = p[i];
				p[i] = p[n];
				p[n] = q;
			}
			for (let i = 0; i < 512; i++) perm[i] = p[i & 255];
			for (let i = 0; i < 256; i++) {
				gradIndex[i] = 3 * (i % 12);
			}
			seed = s;
		}

		function contrib(x, y, z, gi) {
			let t = 0.6 - x * x - y * y - z * z;
			if (t <= 0) return 0;
			t *= t;
			return t * t * (
				x * grad[gi] +
				y * grad[gi + 1] +
				z * grad[gi + 2]
			);
		}

		function noise(xin, yin, zin) {
			const s = (xin + yin + zin) * F3,
				i = (xin + s) | 0,
				j = (yin + s) | 0,
				k = (zin + s) | 0,
				t = (i + j + k) * G3,
				X0 = i - t,
				Y0 = j - t,
				Z0 = k - t,
				x0 = xin - X0,
				y0 = yin - Y0,
				z0 = zin - Z0;

			let i1, j1, k1, i2, j2, k2;

			if (x0 >= y0) {
				if (y0 >= z0) {
					i1 = 1;
					j1 = 0;
					k1 = 0;
					i2 = 1;
					j2 = 1;
					k2 = 0;
				} else if (x0 >= z0) {
					i1 = 1;
					j1 = 0;
					k1 = 0;
					i2 = 1;
					j2 = 0;
					k2 = 1;
				} else {
					i1 = 0;
					j1 = 0;
					k1 = 1;
					i2 = 1;
					j2 = 0;
					k2 = 1;
				}
			} else {
				if (y0 < z0) {
					i1 = 0;
					j1 = 0;
					k1 = 1;
					i2 = 0;
					j2 = 1;
					k2 = 1;
				} else if (x0 < z0) {
					i1 = 0;
					j1 = 1;
					k1 = 0;
					i2 = 0;
					j2 = 1;
					k2 = 1;
				} else {
					i1 = 0;
					j1 = 1;
					k1 = 0;
					i2 = 1;
					j2 = 1;
					k2 = 0;
				}
			}

			const x1 = x0 - i1 + G3,
				y1 = y0 - j1 + G3,
				z1 = z0 - k1 + G3,
				x2 = x0 - i2 + F3,
				y2 = y0 - j2 + F3,
				z2 = z0 - k2 + F3,
				x3 = x0 - 0.5,
				y3 = y0 - 0.5,
				z3 = z0 - 0.5,
				ii = i & 255,
				jj = j & 255,
				kk = k & 255,
				gi0 = gradIndex[perm[ii + perm[jj + perm[kk]]]],
				gi1 = gradIndex[perm[ii + i1 + perm[jj + j1 + perm[kk + k1]]]],
				gi2 = gradIndex[perm[ii + i2 + perm[jj + j2 + perm[kk + k2]]]],
				gi3 = gradIndex[perm[ii + 1 + perm[jj + 1 + perm[kk + 1]]]];

				return 20 * (
					contrib(x0, y0, z0, gi0) +
					contrib(x1, y1, z1, gi1) +
					contrib(x2, y2, z2, gi2) +
					contrib(x3, y3, z3, gi3)
				) + 1;
		}
		return noise;
	}

	const api = {
		randomize,
		randArray,
		random,
		Noise3D,
	};

	return api;
};

//////////////////////////////////////////////////
// Voxel engine
//
const Voxel = (noise, config) => {
	const {
		size,
		frequency,
		threshold,
		aoRays,
		aoReach,
	} = config;

	const normals = [
		[-1,  0,  0],
		[ 1,  0,  0],
		[ 0, -1,  0],
		[ 0,  1,  0],
		[ 0,  0, -1],
		[ 0,  0,  1],
	];

	const quads = [
		[
			[0, 0, 0],
			[0, 0, 1],
			[0, 1, 1],
			[0, 1, 0],
		], // -X
		[
			[1, 0, 0],
			[1, 1, 0],
			[1, 1, 1],
			[1, 0, 1],
		], // +X
		[
			[0, 0, 0],
			[1, 0, 0],
			[1, 0, 1],
			[0, 0, 1],
		], // -Y
		[
			[0, 1, 0],
			[0, 1, 1],
			[1, 1, 1],
			[1, 1, 0],
		], // +Y
		[
			[0, 0, 0],
			[0, 1, 0],
			[1, 1, 0],
			[1, 0, 0],
		], // -Z
		[
			[0, 0, 1],
			[1, 0, 1],
			[1, 1, 1],
			[0, 1, 1],
		], // +Z
	];

	const dot = (a, b) => a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
	const vertices = ([x, y, z, side]) => {
		const q = quads[side];
		const result = [];
		for (let i = 0; i < 4; i++) result.push([x + q[i][0], y + q[i][1], z + q[i][2]]);
		return result;
	};

	function volume () {
		const volume = new Uint8Array(size * size * size);
		for (let x = 1; x < size - 1; x++) {
			const xf = x / size;
			for (let y = 1; y < size - 1; y++) {
				const yf = y / size;
				for (let z = 1; z < size - 1; z++) {
					const zf = z / size;
					const density = noise(
						(xf + 1) * frequency,
						(yf + 1) * frequency,
						(zf + 1) * frequency,
					);
					if (density > threshold) {
						volume[x + y * size + z * size * size] = 1;
					}
				}
			}
		}
		return volume;
	}

	function faces (volume) {
		const faces = [];
		const slice = size * size;
		for (let z = 1; z < size - 1; z++) {
			for (let y = 1; y < size - 1; y++) {
				for (let x = 1; x < size - 1; x++) {
					const i = x + y * size + z * slice;
					if (!volume[i]) continue;
					if (!volume[i - 1]) faces.push([ x, y, z, 0 ]);
					if (!volume[i + 1]) faces.push([ x, y, z, 1 ]);
					if (!volume[i - size]) faces.push([ x, y, z, 2 ]);
					if (!volume[i + size]) faces.push([ x, y, z, 3 ]);
					if (!volume[i - slice]) faces.push([ x, y, z, 4 ]);
					if (!volume[i + slice]) faces.push([ x, y, z, 5 ]);
				}
			}
		}
		return faces;
	}

	function makeRays () {
		const rays = [];
		const golden = Math.PI * (3 - Math.sqrt(5));

		for (let i = 0; i < aoRays; i++) {
			const y = 1 - (2 * (i + 0.5)) / aoRays;
			const rho = Math.sqrt(Math.max(0, 1 - y * y));
			const angle = golden * i;
			const dir = [rho * Math.cos(angle), y, rho * Math.sin(angle)];
			const step = dir.map((v) => Math.sign(v));
			const dt = dir.map((v) =>
				Math.abs(v) > 1e-12 ? 1 / Math.abs(v) : Infinity,
			);
			const t = dt.map((v) => v * 0.5);
			const p = [0, 0, 0];
			const offsets = [];

			while (true) {
				const next = Math.min(t[0], t[1], t[2]);
				if (next > aoReach) break;
				for (let axis = 0; axis < 3; axis++) {
					if (t[axis] <= next + 1e-9) {
						p[axis] += step[axis];
						t[axis] += dt[axis];
					}
				}
				offsets.push([p[0], p[1], p[2]]);
			}
			rays.push({ dir, offsets });
		}
		return rays;
	}

	// Ambient Occlusion
	// Ref Florian Boesch - @pyalot - Minecraft Like Rendering Experiments in OpenGL 4
	// https://web.archive.org/web/20200503045748/http://codeflow.org/entries/2010/dec/09/minecraft-like-rendering-experiments-in-opengl-4/
	//
	function computeAO (rays) {
		const normalWeights = normals.map((normal) => {
			const weights = new Float32Array(rays.length);
			let total = 0;
			for (let i = 0; i < rays.length; i++) {
				const w = Math.max(0, dot(normal, rays[i].dir));
				weights[i] = w;
				total += w;
			}
			return { weights, total };
		});

		const sample = (volume, face) => {
			const slice = size * size;
			const { weights, total } = normalWeights[face[3]];
			const n = normals[face[3]];
			const ax = face[0] + n[0];
			const ay = face[1] + n[1];
			const az = face[2] + n[2];
			let light = 0;

			for (let i = 0; i < rays.length; i++) {
				const w = weights[i];
				if (w <= 0) continue;
				let blocked = false;
				for (const offset of rays[i].offsets) {
					const X = ax + offset[0];
					const Y = ay + offset[1];
					const Z = az + offset[2];
					if (X < 0 || Y < 0 || Z < 0 || X >= size || Y >= size || Z >= size)
						break;
					if (volume[X + Y * size + Z * slice]) {
						blocked = true;
						break;
					}
				}
				if (!blocked) light += w;
			}
			return total > 0 ? light / total : 1;
		};
		return { sample };
	}

	function projection(faces, camera) {
		const eye = camera.eye();
		const result = [];

		for (const face of faces) {
			const n = normals[face[3]];
			const cx = face[0] + 0.5 + n[0] * 0.5;
			const cy = face[1] + 0.5 + n[1] * 0.5;
			const cz = face[2] + 0.5 + n[2] * 0.5;

			if (
				n[0] * (eye[0] - cx) + n[1] * (eye[1] - cy) + n[2] * (eye[2] - cz) <= 0
			) continue;

			const quad = vertices(face);

			const p0 = camera.project(quad[0]);
			const p1 = camera.project(quad[1]);
			const p2 = camera.project(quad[2]);
			const p3 = camera.project(quad[3]);

			if (!p0 || !p1 || !p2 || !p3) continue;

			const xmin = Math.min(p0[0], p1[0], p2[0], p3[0]);
			const xmax = Math.max(p0[0], p1[0], p2[0], p3[0]);
			const ymin = Math.min(p0[1], p1[1], p2[1], p3[1]);
			const ymax = Math.max(p0[1], p1[1], p2[1], p3[1]);

			if (xmax < -100 || xmin > 100 || ymax < -100 || ymin > 100) continue;

			result.push({
				face,
				points: [
					p0[0], p0[1],
					p1[0], p1[1],
					p2[0], p2[1],
					p3[0], p3[1]
				],
				depth: Math.min(p0[2], p1[2], p2[2], p3[2]),
			});
		}
		result.sort((a, b) => a.depth - b.depth);
		return result;
	}

	return {
		volume,
		faces,
		makeRays,
		computeAO,
		projection,
		size
	};
};

//////////////////////////////////////////////////
// Perspective camera
//
const Camera3D = () => {
	const DEG = Math.PI / 180;
	let ex, ey, ez;
	let fx, fy, fz;
	let rx, ry, rz;
	let ux, uy, uz;
	let scale, tanHalfFov;

	const setup = ({
		target = [0, 0, 0],
		yaw = 0,
		pitch = 25,
		roll = 0,
		radius = 50,
		fov = 90,
		screenScale = 200,
	} = {}) => {
		const a = yaw * DEG;
		const b = pitch * DEG;
		const c = roll * DEG;

		const sa = Math.sin(a), ca = Math.cos(a);
		const sb = Math.sin(b), cb = Math.cos(b);
		const sc = Math.sin(c), cc = Math.cos(c);

		ex = target[0] + radius * sa * cb;
		ey = target[1] + radius * sb;
		ez = target[2] - radius * ca * cb;
		fx = -sa * cb;
		fy = -sb;
		fz = ca * cb;

		const r0x = -ca;
		const r0z = -sa;
		const u0x = -sa * sb;
		const u0y = cb;
		const u0z = ca * sb;

		rx = r0x * cc + u0x * sc;
		ry = u0y * sc;
		rz = r0z * cc + u0z * sc;
		ux = u0x * cc - r0x * sc;
		uy = u0y * cc;
		uz = u0z * cc - r0z * sc;

		scale = screenScale;
		tanHalfFov = Math.tan(fov * DEG * 0.5);

		return api;
	};

	const project = (p) => {
		const dx = p[0] - ex;
		const dy = p[1] - ey;
		const dz = p[2] - ez;
		const x = dx * rx + dy * ry + dz * rz;
		const y = dx * ux + dy * uy + dz * uz;
		const z = dx * fx + dy * fy + dz * fz;
		if (z <= 1e-2) return null;
		const k = scale / (z * tanHalfFov);
		return [
		    x * k,
		    -y * k,
		    dx * dx + dy * dy + dz * dz
		];
	};
	const api = {
		setup,
		project,
		eye: () => [ ex, ey, ez ],
	};
	return api;
};

//////////////////////////////////////////////////
// 2D polygons clipper
//
function PolyClip(
	turtle,
	bounds = [-100, -100, 100, 100],
	stroke = (x0, y0, x1, y1) => {
		turtle.jump([x0, y0]);
		turtle.goto([x1, y1]);
	},
) {
	const epsilon = 1e-9;
	const crossings = [];
	const spans = [];
	const layers = [];
	const grid = 32;
	const cells = Array.from({ length: grid * grid }, () => []);
	const marks = [];
	const [xmin, ymin, xmax, ymax] = bounds;
	const cellX = (x) =>
		Math.max(0, Math.min(grid - 1, Math.floor(((x - xmin) / (xmax - xmin)) * grid)));
	const cellY = (y) =>
		Math.max(0, Math.min(grid - 1, Math.floor(((y - ymin) / (ymax - ymin)) * grid)));
	const seen = new Set();
	const a = new Float64Array(2);
	const b = new Float64Array(2);
	const p0 = new Float64Array(2);
	const p1 = new Float64Array(2);
	const pieces = [];
	const masks = [];
	const occluders = [];
	const intersections = [];
	let hx, hy, nx, ny;
	let stamp = 0;

	function uniqueEdge(x0, y0, x1, y1, repeat = 1) {
		const a = `${x0.toFixed(2)},${y0.toFixed(2)}`;
		const b = `${x1.toFixed(2)},${y1.toFixed(2)}`;
		const key = a < b ? `${a}|${b}` : `${b}|${a}`;
		if (seen.has(key)) return;
		seen.add(key);
		visible(x0, y0, x1, y1, repeat);
	}

	function prepare(points) {
		const flat = typeof points?.[0] === "number";
		const count = flat ? points.length / 2 : points?.length;
		const xy = new Float64Array(count * 2);
		let minx = Infinity;
		let miny = Infinity;
		let maxx = -Infinity;
		let maxy = -Infinity;
		for (let i = 0; i < count; i++) {
			const x = flat ? points[2 * i] : points[i][0];
			const y = flat ? points[2 * i + 1] : points[i][1];
			xy[i * 2] = x;
			xy[i * 2 + 1] = y;
			if (x < minx) minx = x;
			if (x > maxx) maxx = x;
			if (y < miny) miny = y;
			if (y > maxy) maxy = y;
		}
		return { xy, minx, miny, maxx, maxy };
	}

	function query(poly) {
		occluders.length = 0;
		const current = ++stamp;
		const x0 = cellX(poly.minx);
		const y0 = cellY(poly.miny);
		const x1 = cellX(poly.maxx);
		const y1 = cellY(poly.maxy);

		for (let iy = y0; iy <= y1; iy++) {
			for (let ix = x0; ix <= x1; ix++) {
				const cell = cells[iy * grid + ix];

				for (let k = 0; k < cell.length; k++) {
					const id = cell[k];
					if (marks[id] === current) continue;
					marks[id] = current;
					const q = layers[id];
					if (
						q.maxx < poly.minx ||
						q.minx > poly.maxx ||
						q.maxy < poly.miny ||
						q.miny > poly.maxy
					)
						continue;
					occluders.push(q);
				}
			}
		}
	}

	function insert(poly) {
		const id = layers.length;
		layers.push(poly);
		marks.push(0);
		if (
			poly.maxx < xmin ||
			poly.minx > xmax ||
			poly.maxy < ymin ||
			poly.miny > ymax
		)
			return;

		const x0 = cellX(poly.minx);
		const y0 = cellY(poly.miny);
		const x1 = cellX(poly.maxx);
		const y1 = cellY(poly.maxy);

		for (let iy = y0; iy <= y1; iy++) {
			for (let ix = x0; ix <= x1; ix++) {
				cells[iy * grid + ix].push(id);
			}
		}
	}

	function subtractRanges(a, b, ranges, repeat = 1) {
		const ax = a[0];
		const ay = a[1];
		const bx = b[0];
		const by = b[1];
		const dx = bx - ax;
		const dy = by - ay;
		const length = Math.hypot(dx, dy);
		const output = (lo, hi) => {
			if (hi - lo > tEps)
				emitBounded(
					ax + dx * lo,
					ay + dy * lo,
					ax + dx * hi,
					ay + dy * hi,
					repeat,
				);
		};
		if (length <= epsilon) return;
		const tEps = epsilon / length;
		spans.length = 0;
		for (let i = 0; i < ranges.length; i += 2) {
			const lo = Math.max(0, Math.min(ranges[i], ranges[i + 1]));
			const hi = Math.min(1, Math.max(ranges[i], ranges[i + 1]));
			if (hi - lo > tEps) spans.push(lo, hi);
		}
		union(spans, tEps);
		let at = 0;
		for (let i = 0; i < spans.length; i += 2) {
			output(at, spans[i]);
			at = Math.max(at, spans[i + 1]);
		}
		output(at, 1);
	}

	function emitBounded(x0, y0, x1, y1, repeat = 1) {
		const dx = x1 - x0;
		const dy = y1 - y0;
		let lo = 0;
		let hi = 1;

		function trim(p, q) {
			if (Math.abs(p) < 1e-12) return q >= 0;
			const t = q / p;
			if (p < 0) lo = Math.max(lo, t);
			else hi = Math.min(hi, t);
			return lo <= hi;
		}

		if (
			!trim(-dx, x0 - xmin) ||
			!trim(dx, xmax - x0) ||
			!trim(-dy, y0 - ymin) ||
			!trim(dy, ymax - y0)
		) return;

		if (hi - lo <= epsilon / Math.max(1, Math.hypot(dx, dy))) return;

		for (let i = 0; i < repeat; i++) {
			stroke(x0 + dx * lo, y0 + dy * lo, x0 + dx * hi, y0 + dy * hi);
		}
	}

	function visible(x0, y0, x1, y1, repeat = 1) {
		p0[0] = x0;
		p0[1] = y0;
		p1[0] = x1;
		p1[1] = y1;
		if (!occluders.length) {
			emitBounded(x0, y0, x1, y1, repeat);
			return;
		}
		const dx = x1 - x0;
		const dy = y1 - y0;
		const len2 = dx * dx + dy * dy;
		if (len2 <= epsilon * epsilon) return;
		const minx = Math.min(x0, x1);
		const maxx = Math.max(x0, x1);
		const miny = Math.min(y0, y1);
		const maxy = Math.max(y0, y1);
		masks.length = 0;
		for (let j = 0; j < occluders.length; j++) {
			const q = occluders[j];
			if (!(q.maxx < minx || q.minx > maxx || q.maxy < miny || q.miny > maxy)) {
				intersections.length = 0;
				intersect(p0, p1, q, intersections);
				for (let k = 0; k < intersections.length; k += 4) {
					masks.push(
						((intersections[k] - x0) * dx + (intersections[k + 1] - y0) * dy) / len2,
						((intersections[k + 2] - x0) * dx + (intersections[k + 3] - y0) * dy) / len2,
					);
				}
			}
		}
		subtractRanges(p0, p1, masks, repeat);
	}

	function viewportLine(s) {
		let lo = -Infinity;
		let hi = Infinity;
		const cx = s * nx;
		const cy = s * ny;
		if (Math.abs(hx) < 1e-12) {
			if (cx < xmin || cx > xmax) return false;
		} else {
			const t0 = (xmin - cx) / hx;
			const t1 = (xmax - cx) / hx;
			lo = Math.max(lo, Math.min(t0, t1));
			hi = Math.min(hi, Math.max(t0, t1));
		}
		if (Math.abs(hy) < 1e-12) {
			if (cy < ymin || cy > ymax) return false;
		} else {
			const t0 = (ymin - cy) / hy;
			const t1 = (ymax - cy) / hy;
			lo = Math.max(lo, Math.min(t0, t1));
			hi = Math.min(hi, Math.max(t0, t1));
		}
		if (!(hi - lo > epsilon)) return false;
		a[0] = cx + lo * hx;
		a[1] = cy + lo * hy;
		b[0] = cx + hi * hx;
		b[1] = cy + hi * hy;
		return true;
	}

	function gather(ax, ay, bx, by, poly, length, out) {
		if (
			poly.maxx < Math.min(ax, bx) - epsilon ||
			poly.minx > Math.max(ax, bx) + epsilon ||
			poly.maxy < Math.min(ay, by) - epsilon ||
			poly.miny > Math.max(ay, by) + epsilon
		) return;
		const dx = bx - ax;
		const dy = by - ay;
		const invLength2 = 1 / (length * length);
		const sideEps = epsilon * length;
		const tEps = epsilon / length;
		const xy = poly.xy;
		crossings.length = 0;
		let x0 = xy[xy.length - 2];
		let y0 = xy[xy.length - 1];
		let s0 = dx * (y0 - ay) - dy * (x0 - ax);
		if (Math.abs(s0) <= sideEps) s0 = 0;
		let t0 = ((x0 - ax) * dx + (y0 - ay) * dy) * invLength2;
		for (let i = 0; i < xy.length; i += 2) {
			const x1 = xy[i];
			const y1 = xy[i + 1];
			let s1 = dx * (y1 - ay) - dy * (x1 - ax);
			if (Math.abs(s1) <= sideEps) s1 = 0;
			const t1 = ((x1 - ax) * dx + (y1 - ay) * dy) * invLength2;
			if (s0 === 0 && s1 === 0) {
				const lo = Math.max(0, Math.min(t0, t1));
				const hi = Math.min(1, Math.max(t0, t1));
				if (hi - lo > tEps) out.push(lo, hi);
			} else if (s0 > 0 !== s1 > 0)
				crossings.push(t0 + ((t1 - t0) * s0) / (s0 - s1));
			x0 = x1;
			y0 = y1;
			s0 = s1;
			t0 = t1;
		}
		crossings.sort((a, b) => a - b);
		for (let i = 0; i + 1 < crossings.length; i += 2) {
			const lo = Math.max(0, crossings[i]);
			const hi = Math.min(1, crossings[i + 1]);
			if (hi - lo > tEps) out.push(lo, hi);
		}
	}

	function sortPairs(a, left, right) {
		while (left < right) {
			let i = left;
			let j = right;
			const pivot = a[2 * ((left + right) >> 1)];
			while (i <= j) {
				while (a[2 * i] < pivot) i++;
				while (a[2 * j] > pivot) j--;
				if (i <= j) {
					const lo = a[2 * i];
					const hi = a[2 * i + 1];
					a[2 * i] = a[2 * j];
					a[2 * i + 1] = a[2 * j + 1];
					a[2 * j] = lo;
					a[2 * j + 1] = hi;
					i++;
					j--;
				}
			}
			if (j - left < right - i) {
				if (left < j) sortPairs(a, left, j);
				left = i;
			} else {
				if (i < right) sortPairs(a, i, right);
				right = j;
			}
		}
	}

	function union(a, tEps) {
		if (!a.length) return;
		if (a.length > 2) sortPairs(a, 0, a.length / 2 - 1);
		let lo = a[0];
		let hi = a[1];
		let w = 0;
		for (let i = 2; i < a.length; i += 2) {
			if (a[i] <= hi + tEps) hi = Math.max(hi, a[i + 1]);
			else {
				a[w++] = lo;
				a[w++] = hi;
				lo = a[i];
				hi = a[i + 1];
			}
		}
		a[w++] = lo;
		a[w++] = hi;
		a.length = w;
	}

	function intersect(a, b, poly, out) {
		const ax = a[0];
		const ay = a[1];
		const bx = b[0];
		const by = b[1];
		const dx = bx - ax;
		const dy = by - ay;
		const length = Math.hypot(dx, dy);
		if (length <= epsilon) return;
		spans.length = 0;
		gather(ax, ay, bx, by, poly, length, spans);
		const tEps = epsilon / length;
		union(spans, tEps);
		for (let i = 0; i < spans.length; i += 2) {
			const lo = spans[i];
			const hi = spans[i + 1];
			if (hi - lo > tEps) {
				out.push(
					ax + dx * lo, ay + dy * lo,
					ax + dx * hi, ay + dy * hi
				);
			}
		}
	}
	return {
		drawPolygon(
			points,
			{
				outline = false,
				hatch = null,
				segments = null,
				occlude = true,
				edges = null,
			} = {},
		) {
			const poly = points && points.xy instanceof Float64Array ? points : prepare(points);
			const minx = Math.max(xmin, poly.minx);
			const maxx = Math.min(xmax, poly.maxx);
			const miny = Math.max(ymin, poly.miny);
			const maxy = Math.min(ymax, poly.maxy);
			const pitch = hatch ? (hatch.pitch ?? hatch.step ?? 0) : 0;
			const angle = hatch ? (hatch.angle ?? 0) : 0;
			if (minx < maxx && miny < maxy && (outline || pitch || segments)) {
				query(poly);
				if (outline) {
					const xy = poly.xy;
					for (let q = 0; q < xy.length; q += 2) {
						const repeat = edges?.[q / 2] ? 4 : 1;
						const n = (q + 2) % xy.length;
						uniqueEdge(xy[q], xy[q + 1], xy[n], xy[n + 1], repeat);
					}
				}
				if (segments) {
					if (typeof segments[0] === "number") {
						for (let q = 0; q < segments.length; q += 4)
							uniqueEdge(
								segments[q],
								segments[q + 1],
								segments[q + 2],
								segments[q + 3],
							);
					} else {
						for (const [p, q] of segments) uniqueEdge(p[0], p[1], q[0], q[1]);
					}
				}
				if (pitch > 0) {
					hx = Math.cos(angle);
					hy = Math.sin(angle);
					nx = -hy;
					ny = hx;
					const sMin = (nx > 0 ? nx * minx : nx * maxx) + (ny > 0 ? ny * miny : ny * maxy);
					const sMax = (nx > 0 ? nx * maxx : nx * minx) + (ny > 0 ? ny * maxy : ny * miny);
					for (
						let k = Math.ceil((sMin - 1e-10) / pitch);
						k <= Math.floor((sMax + 1e-10) / pitch);
						k++
					) {
						if (!viewportLine(k * pitch)) continue;
						pieces.length = 0;
						intersect(a, b, poly, pieces);
						for (let q = 0; q < pieces.length; q += 4)
							visible(pieces[q], pieces[q + 1], pieces[q + 2], pieces[q + 3]);
					}
				}
			}
			if (occlude) insert(poly);
		},
	};
}

//////////////////////////////////////////////////
// Boot
//

// init turtle
const turtle = new Turtle();
turtle.pendown();
Canvas.setpenopacity(0.75);

// seed, PRNG and noise
const seed = (Math.random() * 1e9) | 0; // random seed
console.log("Seed:", seed);

const prng = PRNG().randomize(seed);
const noise = prng.Noise3D();

// compute voxel
const voxel = Voxel(noise, {
	size: 64,
	frequency: 3,
	threshold: 1.1,
	aoRays: 512,
	aoReach: 32
});

const volume = voxel.volume();
const faces = voxel.faces(volume);
const rays = voxel.makeRays();
const ao = voxel.computeAO(rays);

// perspective camera
const camera = Camera3D().setup({
	target: [ voxel.size / 2, voxel.size / 2 - 5, voxel.size / 2 ],
	yaw: prng.randArray([35, 45, -35]),
	pitch: 25,
	radius: voxel.size * 2.3,
	fov: 40,
	screenScale: 100,
});

const projected = voxel.projection(faces, camera);

// clipping polygons
const clipper = PolyClip(turtle);

// Turtletoy walk function
let cursor = 0;

function walk() {
	if (cursor >= projected.length) return false;
	const { face, points } = projected[cursor++];
	const segments = [];
	for (let i = 0; i < 4; i++) {
		const j = (i + 1) & 3;
		segments.push(
			points[2 * i],
			points[2 * i + 1],
			points[2 * j],
			points[2 * j + 1],
		);
	}
	const visibility = ao.sample(volume, face);
	const darkness = 1 - visibility;
	const level = Math.round(darkness * 8);
	const hatch = level > 0 ? {
		pitch: 1 / (level + 1),
		angle: -Math.PI / 4,
	} : null;

	clipper.drawPolygon(points, {
		segments,
		hatch,
		occlude: true
	});
	return cursor < projected.length;
}