Cathedrals of Static (v2)
The signal remembers its ruins.
Log in to post a comment.
/*
Cathedrals of Static (v2)
A simpler, more brutalist take on "Cathedrals of Static".
No sophisticated 3D visibility engine here. Just a procedural world of cubes and frames,
tessellated faces, a rough depth sort, and a generic 2D polygon clipper.
Generate. Tessellate. Sort by Z. Clip. Plot.
*/
Canvas.setpenopacity(0.9);
const turtle = new Turtle();
turtle.pendown();
//////////////////////////////////////////////////////
// PRNG
//
const PRNG = () => {
let seed = (Math.random() * 1e7) | 0;
return {
randomize(s) {
seed = s | 0;
},
random() {
const s = seed;
seed = (Math.imul(s, 747796405) + 2891336453) | 0;
let word = Math.imul((s >>> ((s >>> 28) + 4)) ^ s, 277803737);
return (((word >>> 22) ^ word) >>> 0) / 4294967296;
},
};
};
//////////////////////////////////////////////////////
// Procedural scene generation
//
const CFDG = (prng) => {
const { randomize, random } = prng;
let rule = {};
let setup = {};
let rules = {};
let matrices = [];
const shapes = [];
const stack = [];
const DEG = Math.PI / 180;
const snap = (x) =>
Math.abs(x) < 1e-12
? 0
: Math.abs(x - 1) < 1e-12
? 1
: Math.abs(x + 1) < 1e-12
? -1
: x;
// Local affine transformations used by the grammar
const transforms = {
x(m, v) {
m[12] += m[0] * v;
m[13] += m[1] * v;
m[14] += m[2] * v;
},
y(m, v) {
m[12] += m[4] * v;
m[13] += m[5] * v;
m[14] += m[6] * v;
},
z(m, v) {
m[12] += m[8] * v;
m[13] += m[9] * v;
m[14] += m[10] * v;
},
s(m, v) {
const a = Array.isArray(v);
const x = a ? v[0] : v;
const y = a ? v[1] : x;
const z = a ? v[2] : x;
m[0] *= x;
m[1] *= x;
m[2] *= x;
m[4] *= y;
m[5] *= y;
m[6] *= y;
m[8] *= z;
m[9] *= z;
m[10] *= z;
},
rx(m, v) {
const s = snap(Math.sin(v * DEG));
const c = snap(Math.cos(v * DEG));
const a10 = m[4];
const a11 = m[5];
const a12 = m[6];
const a20 = m[8];
const a21 = m[9];
const a22 = m[10];
m[4] = a10 * c + a20 * s;
m[5] = a11 * c + a21 * s;
m[6] = a12 * c + a22 * s;
m[8] = a10 * -s + a20 * c;
m[9] = a11 * -s + a21 * c;
m[10] = a12 * -s + a22 * c;
},
ry(m, v) {
const s = snap(Math.sin(v * DEG));
const c = snap(Math.cos(v * DEG));
const a00 = m[0];
const a01 = m[1];
const a02 = m[2];
const a20 = m[8];
const a21 = m[9];
const a22 = m[10];
m[0] = a00 * c + a20 * -s;
m[1] = a01 * c + a21 * -s;
m[2] = a02 * c + a22 * -s;
m[8] = a00 * s + a20 * c;
m[9] = a01 * s + a21 * c;
m[10] = a02 * s + a22 * c;
},
rz(m, v) {
const s = snap(Math.sin(v * DEG));
const c = snap(Math.cos(v * DEG));
const a00 = m[0];
const a01 = m[1];
const a02 = m[2];
const a10 = m[4];
const a11 = m[5];
const a12 = m[6];
m[0] = a00 * c + a10 * s;
m[1] = a01 * c + a11 * s;
m[2] = a02 * c + a12 * s;
m[4] = a00 * -s + a10 * c;
m[5] = a01 * -s + a11 * c;
m[6] = a02 * -s + a12 * c;
}
};
const SHAPE = (m, t, p) => {
const s = m.slice(0);
for (const c in t) transforms[c](s, t[c]);
s[19] = p;
matrices.push(s);
};
const transform = (s, p) => {
const m = s.slice(0);
m[17]++;
for (const c in p) transforms[c](m, p[c]);
return m;
};
// Rule dispatch and recursive growth
const singlerule = (i) => {
return (s, t) => {
s = transform(s, t);
if (!s) return;
s[18] = i;
stack.push(s);
};
};
const randomrule = (totalWeight, weight, index, len) => {
return (s, t) => {
s = transform(s, t);
if (!s) return;
let w = 0;
const r = random() * totalWeight;
for (let i = 0; i < len; i++) {
w += weight[i];
if (r <= w) {
s[18] = index[i];
stack.push(s);
return;
}
}
};
};
return {
init(cfg, rules) {
setup = cfg;
if (setup.seed) randomize(setup.seed);
shapes.length = 0;
for (const namerule in rules) {
const r = rules[namerule];
if (Array.isArray(r)) {
let totalWeight = 0;
const weight = [];
const index = [];
for (let i = 0; i < r.length; i += 2) {
totalWeight += r[i];
shapes.push(r[i + 1]);
weight.push(r[i]);
index.push(shapes.length - 1);
}
rule[namerule] = randomrule(totalWeight, weight, index, index.length);
} else {
shapes.push(r);
rule[namerule] = singlerule(shapes.length - 1);
}
}
},
run() {
const t0 = performance.now();
console.clear();
const maxDepth = setup.maxDepth ?? 100;
let minComplexity = setup.minComplexity ?? 0;
let complexity;
do {
complexity = 0;
matrices.length = 0;
stack.length = 0;
// identity
rule[setup.start](
[
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
0, 0, 0, 1,
1, // 16 brightness
0, // 17 depth
0, // 18 fn index
0, // 19 primitive (0 = CUBE)
],
setup.transform ?? {},
);
// run rules
let head = 0;
while (head < stack.length) {
const s = stack[head++];
if (s !== undefined && s[17] <= maxDepth + 1) {
shapes[s[18]](s);
complexity++;
}
}
} while (complexity < minComplexity--);
stack.length = 0;
const scene = matrices;
matrices = [];
console.log("CFDG runtime:", performance.now() - t0, "ms");
return scene;
},
// Reject primitives outside the camera view before building geometry
cull(scene, camera) {
const planes = camera.frustum();
const visible = [];
for (let i = 0; i < scene.length; i++) {
const m = scene[i];
let rejected = false;
for (let j = 0; j < planes.length; j++) {
const p = planes[j];
const d = p[0] * m[12] + p[1] * m[13] + p[2] * m[14] + p[3];
const r = 0.5 * (
Math.abs(p[0] * m[0] + p[1] * m[1] + p[2] * m[2]) +
Math.abs(p[0] * m[4] + p[1] * m[5] + p[2] * m[6]) +
Math.abs(p[0] * m[8] + p[1] * m[9] + p[2] * m[10])
);
if (j === 0 ? d - r <= 0 : d + r < 0) {
rejected = true;
break;
}
}
if (!rejected) visible.push(m);
}
return visible;
},
rule,
CUBE: (m, t) => SHAPE(m, t, 0),
FRAME(m, t) {
SHAPE(m, { x: -0.45, z: -0.45, s: [0.1, 0.8, 0.1] }, 1);
SHAPE(m, { x: 0.45, z: -0.45, s: [0.1, 0.8, 0.1] }, 1);
SHAPE(m, { x: -0.45, z: 0.45, s: [0.1, 0.8, 0.1] }, 1);
SHAPE(m, { x: 0.45, z: 0.45, s: [0.1, 0.8, 0.1] }, 1);
SHAPE(m, { y: -0.45, z: -0.45, s: [1, 0.1, 0.1] }, 1);
SHAPE(m, { y: 0.45, z: -0.45, s: [1, 0.1, 0.1] }, 1);
SHAPE(m, { y: -0.45, z: 0.45, s: [1, 0.1, 0.1] }, 1);
SHAPE(m, { y: 0.45, z: 0.45, s: [1, 0.1, 0.1] }, 1);
SHAPE(m, { y: -0.45, x: -0.45, s: [0.1, 0.1, 0.8] }, 1);
SHAPE(m, { y: 0.45, x: -0.45, s: [0.1, 0.1, 0.8] }, 1);
SHAPE(m, { y: -0.45, x: 0.45, s: [0.1, 0.1, 0.8] }, 1);
SHAPE(m, { y: 0.45, x: 0.45, s: [0.1, 0.1, 0.8] }, 1);
},
};
};
//////////////////////////////////////////////////////
// Perspective projection
//
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;
let frustum = [];
const setup = ({
target = { x: 0, y: 0, z: 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.x + radius * sa * cb;
ey = target.y + radius * sb;
ez = target.z - radius * ca * cb;
fx = -sa * cb;
fy = -sb;
fz = ca * cb;
const r0x = -ca, r0z = -sa;
const u0x = -sa * sb, u0y = cb, 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);
const k = (100 * tanHalfFov) / scale;
const plane = (nx, ny, nz, near = 0) => [
nx,
ny,
nz,
-(nx * ex + ny * ey + nz * ez) - near,
];
frustum = [
plane(fx, fy, fz, 1e-2), // Near
plane(fx * k + rx, fy * k + ry, fz * k + rz), // Left
plane(fx * k - rx, fy * k - ry, fz * k - rz), // Right
plane(fx * k + ux, fy * k + uy, fz * k + uz), // Bottom
plane(fx * k - ux, fy * k - uy, fz * k - uz), // Top
];
};
const project = (p) => {
const dx = p.x - ex;
const dy = p.y - ey;
const dz = p.z - 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: x * k,
y: -y * k,
z,
};
};
return {
setup,
project,
frustum: () => frustum,
};
};
//////////////////////////////////////////////////////
// Project cubes
//
const Projection3D = () => {
const vertices = [
[-0.5, -0.5, -0.5],
[0.5, -0.5, -0.5],
[0.5, 0.5, -0.5],
[-0.5, 0.5, -0.5],
[-0.5, -0.5, 0.5],
[0.5, -0.5, 0.5],
[0.5, 0.5, 0.5],
[-0.5, 0.5, 0.5],
];
const faces = [
[0, 3, 2, 1], // -Z
[4, 5, 6, 7], // +Z
[0, 1, 5, 4], // -Y
[3, 7, 6, 2], // +Y
[0, 4, 7, 3], // -X
[1, 2, 6, 5], // +X
];
const edges = [
[0, 1],
[1, 2],
[2, 3],
[3, 0],
[4, 5],
[5, 6],
[6, 7],
[7, 4],
[0, 4],
[1, 5],
[2, 6],
[3, 7],
];
const area2 = (a, b, c) =>
(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
const determinant = (m) =>
m[0] * (m[5] * m[10] - m[6] * m[9]) +
m[1] * (m[6] * m[8] - m[4] * m[10]) +
m[2] * (m[4] * m[9] - m[5] * m[8]);
const transform = (v, m) => {
const x = v[0];
const y = v[1];
const z = v[2];
return [
m[0] * x + m[4] * y + m[8] * z + m[12],
m[1] * x + m[5] * y + m[9] * z + m[13],
m[2] * x + m[6] * y + m[10] * z + m[14],
];
};
return {
build(scene, camera) {
const cubes = [];
const faceList = [];
for (let cubeId = 0; cubeId < scene.length; cubeId++) {
const m = scene[cubeId];
const world = vertices.map((v) => transform(v, m));
const screen = world.map((p) =>
camera.project({
x: p[0],
y: p[1],
z: p[2],
}),
);
if (screen.some((p) => p === null)) continue;
const sign = Math.sign(determinant(m)) || 1;
const visibleFaces = [];
for (let faceId = 0; faceId < faces.length; faceId++) {
const f = faces[faceId];
const p0 = screen[f[0]];
const p1 = screen[f[1]];
const p2 = screen[f[2]];
if (area2(p0, p1, p2) * sign < 0) {
visibleFaces.push(faceId);
const poly = [];
let zsum = 0;
let xmin = Infinity;
let ymin = Infinity;
let xmax = -Infinity;
let ymax = -Infinity;
for (let i = 0; i < 4; i++) {
const sp = screen[f[i]];
poly.push(sp.x, sp.y);
zsum += sp.z;
if (sp.x < xmin) xmin = sp.x;
if (sp.y < ymin) ymin = sp.y;
if (sp.x > xmax) xmax = sp.x;
if (sp.y > ymax) ymax = sp.y;
}
faceList.push({
cubeId,
faceId,
indices: f,
points: poly,
zAvg: zsum / 4,
bounds: [xmin, ymin, xmax, ymax],
});
}
}
cubes.push({
cubeId,
world,
screen,
visibleFaces,
});
}
return { cubes, faces: faceList };
},
};
};
//////////////////////////////////////////////////////
// Tesselation
//
const Texels = () => {
const build = (projected, camera, {
size = 0.5,
maxDiv = 16,
minStep = 0.5
} = {}) => {
const tiles = [];
const cubes = new Map(projected.cubes.map((c) => [c.cubeId, c]));
for (const face of projected.faces) {
const cube = cubes.get(face.cubeId);
const [i0, i1, i2, i3] = face.indices;
const a = cube.world[i0];
const b = cube.world[i1];
const d = cube.world[i3];
const u = [b[0] - a[0], b[1] - a[1], b[2] - a[2]];
const v = [d[0] - a[0], d[1] - a[1], d[2] - a[2]];
const lenU = Math.hypot(...u);
const lenV = Math.hypot(...v);
const screen = cube.screen;
const dist = (a, b) => Math.hypot(
screen[a].x - screen[b].x,
screen[a].y - screen[b].y
);
const projectedU = Math.max(dist(i0, i1), dist(i3, i2));
const projectedV = Math.max(dist(i0, i3), dist(i1, i2));
const nu = Math.max(1, Math.min(
maxDiv,
Math.ceil(lenU / size),
Math.floor(projectedU / minStep)
));
const nv = Math.max(1, Math.min(
maxDiv,
Math.ceil(lenV / size),
Math.floor(projectedV / minStep)
));
const point = (x, y) =>
camera.project({
x: a[0] + u[0] * x + v[0] * y,
y: a[1] + u[1] * x + v[1] * y,
z: a[2] + u[2] * x + v[2] * y,
});
for (let j = 0; j < nv; j++) {
for (let i = 0; i < nu; i++) {
const x0 = i / nu;
const x1 = (i + 1) / nu;
const y0 = j / nv;
const y1 = (j + 1) / nv;
const p0 = point(x0, y0);
const p1 = point(x1, y0);
const p2 = point(x1, y1);
const p3 = point(x0, y1);
if (!p0 || !p1 || !p2 || !p3) continue;
tiles.push({
points: [p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y],
zAvg: (p0.z + p1.z + p2.z + p3.z) * 0.25,
});
}
}
}
tiles.sort((a, b) => a.zAvg - b.zAvg);
return tiles;
};
return { build };
};
//////////////////////////////////////////////////////
// Generative grammar
//
const Cathedral = (cfdg, prng) => {
const { rule, CUBE, FRAME } = cfdg;
const { random } = prng;
const rules = {
start(s) {
rule.R1(s);
},
R1: [
1,
(s) => {
CUBE(s);
rule.R1(s, { x: 1.1 });
},
1,
(s) => {
if (random() > 0.5) FRAME(s);
else CUBE(s);
rule.R1(s, { x: 1.1 });
},
0.06,
(s) => {
CUBE(s);
rule.R1(s, { x: 1.1, ry: 90 });
rule.R1(s, { x: 1.1, rz: -90, s: 0.5 });
},
0.1,
(s) => {
CUBE(s);
rule.R1(s, { x: 1.1, rx: 90 });
rule.R1(s, { x: 1.1, rz: -90, s: 2 });
},
],
};
return {
run(setup) {
cfdg.init(setup, rules);
const scene = cfdg.run();
console.log("Nbr Boxes:", scene.length);
return scene;
},
};
};
//////////////////////////////////////////////////////
// PolyClip — analytic segment / polygon clipping
// Inspired by Reinder Nijhoff's Polygon Clipping Utility (2019, MIT)
// ge1doot — November 2026
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) {
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);
}
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 };
}
// Find previous occluders overlapping a polygon.
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);
}
}
}
}
// Register an occluding polygon for future drawings.
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) {
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);
};
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) {
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;
stroke(x0 + dx * lo, y0 + dy * lo, x0 + dx * hi, y0 + dy * hi);
}
function visible(x0, y0, x1, y1) {
p0[0] = x0;
p0[1] = y0;
p1[0] = x1;
p1[1] = y1;
if (!occluders.length) {
emitBounded(x0, y0, x1, y1);
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);
}
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 } = {},
) {
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 n = (q + 2) % xy.length;
uniqueEdge(xy[q], xy[q + 1], xy[n], xy[n + 1]);
}
}
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);
},
walk(draw, intervalMs = 0) {
let next = 0;
return function () {
const now = performance.now();
if (now < next) return true;
const more = draw();
next = now + intervalMs;
return more;
};
},
};
}
//////////////////////////////////////////////////////
// Boot
const prng = PRNG();
const cfdg = CFDG(prng);
const cathedral = Cathedral(cfdg, prng);
const scene = cathedral.run({
start: "start",
seed: 0, // 0 = random
transform: { s: 0.2 },
maxDepth: 40,
minComplexity: 1400,
});
const camera = Camera3D();
camera.setup({
yaw: -30 + prng.random() * 60,
pitch: -30 + prng.random() * 60,
roll: 0,
radius: 20,
fov: 120
});
const renderer = Projection3D();
const texels = Texels();
const visible = cfdg.cull(scene, camera);
const projected = renderer.build(visible, camera);
const tiles = texels.build(projected, camera, {
size: 0.2,
maxDiv: 64,
minStep: 0.5
});
const clipper = PolyClip(turtle);
let cursor = 0;
function walk() {
const batch = 100;
for (let n = 0; n < batch && cursor < tiles.length; n++) {
clipper.drawPolygon(tiles[cursor++].points, {
outline: true,
});
}
return cursor < tiles.length;
}