SOURCE / PINNED RELEASE
Made of little things.
Drift City
- Release
- 098731aa0f0f…
- Author-recorded commit
- 2822ea0a4f5b…
- License
- LICENSE
- Author’s source reference
- nostr://npub12lm3rxsva8kfempyjkxupt09e02n3fezurkyadyqfejdc5e0r2kscqty6r/wss%3A%2F%2Fgit.napplet.soy%2F/n-a4c0039c855
Archive hash verified: b3323e408235502b…. The source-to-build association is the author’s claim; it has not been independently rebuilt.
import * as THREE from 'three';
import { Clipper, FillRule, Path64, Paths64, PointInPolygonResult, type Point64 } from 'clipper2-js';
/**
* Road surfaces as shapes rather than strips: every road's outline merged into one shape
* (Clipper2) and triangulated (earcut, via three's ShapeUtils) into one surface. Where roads
* cross or join at any angle there's a single clean piece of asphalt: no overlaps, no
* slivers, no gaps showing the ground.
*
* The outlines are sorted into square tiles first and each tile merged and triangulated on
* its own: small simple shapes, which earcut always gets right (one shape for the whole
* city's streets, with hundreds of holes, it doesn't), and quick. Each tile's triangles are
* checked against its area; if they don't add up, the tile falls back on its outlines
* drawn as they are.
*/
/** Clipper works in whole numbers: centimetres (decimetres left hairline cracks between neighbouring pieces). */
const S = 100;
const TILE = 100;
export type Ring = { x: number; z: number }[];
type Emit = (a: [number, number], b: [number, number], c: [number, number]) => void;
/** The outline of a road hw either side of a centre line. */
export function ribbon(pts: { x: number; z: number }[], hw: number): Ring {
const n = pts.length;
const left: Ring = [];
const right: Ring = [];
for (let i = 0; i < n; i++) {
const a = pts[Math.max(0, i - 1)]!;
const b = pts[Math.min(n - 1, i + 1)]!;
const l = Math.hypot(b.x - a.x, b.z - a.z) || 1;
const nx = -(b.z - a.z) / l;
const nz = (b.x - a.x) / l;
left.push({ x: pts[i]!.x + nx * hw, z: pts[i]!.z + nz * hw });
right.push({ x: pts[i]!.x - nx * hw, z: pts[i]!.z - nz * hw });
}
return [...left, ...right.reverse()];
}
/** A circle of radius r round (x, z). */
export function disc(x: number, z: number, r: number, n = 20): Ring {
return Array.from({ length: n }, (_, k) => ({ x: x + Math.cos((k / n) * Math.PI * 2) * r, z: z + Math.sin((k / n) * Math.PI * 2) * r }));
}
/** A rectangle. */
export function rect(x0: number, z0: number, x1: number, z1: number): Ring {
return [
{ x: x0, z: z0 },
{ x: x1, z: z0 },
{ x: x1, z: z1 },
{ x: x0, z: z1 },
];
}
function toPath(r: Ring): Path64 {
const p = new Path64();
for (const q of r) p.push({ x: Math.round(q.x * S), y: Math.round(q.z * S) });
return p;
}
function paths(rings: Ring[]): Paths64 {
const out = new Paths64();
for (const r of rings) {
if (r.length < 3) continue;
// All the same way round: where two outlines overlap, one going each way would cancel
// out (a hole in the road) rather than add up.
const p = toPath(r);
out.push(Clipper.area(p) < 0 ? Clipper.reversePath(p) : p);
}
return out;
}
/** Each ring into the tiles its bounds overlap. */
function bucket(rings: Ring[]): Map<string, Ring[]> {
const out = new Map<string, Ring[]>();
for (const r of rings) {
let x0 = Infinity;
let x1 = -Infinity;
let z0 = Infinity;
let z1 = -Infinity;
for (const q of r) {
x0 = Math.min(x0, q.x);
x1 = Math.max(x1, q.x);
z0 = Math.min(z0, q.z);
z1 = Math.max(z1, q.z);
}
for (let tx = Math.floor(x0 / TILE); tx <= Math.floor(x1 / TILE); tx++)
for (let tz = Math.floor(z0 / TILE); tz <= Math.floor(z1 / TILE); tz++) {
const k = `${tx},${tz}`;
let list = out.get(k);
if (!list) out.set(k, (list = []));
list.push(r);
}
}
return out;
}
/** A shape's pieces as triangles; false if they don't cover exactly its area (earcut got it wrong). */
function fill(shape: Paths64, emit: Emit): boolean {
const outers: Path64[] = [];
const holes: Path64[] = [];
for (const p of shape) if (p.length >= 3) (Clipper.area(p) > 0 ? outers : holes).push(p);
const areas = outers.map((p) => Clipper.area(p));
const kids: Path64[][] = outers.map(() => []);
for (const h of holes) {
let best = -1;
outers.forEach((o, i) => {
if (Clipper.pointInPolygon(h[0] as Point64, o) === PointInPolygonResult.IsOutside) return;
if (best < 0 || areas[i]! < areas[best]!) best = i;
});
if (best >= 0) kids[best]!.push(h);
}
const v = (p: Path64) => p.map((q) => new THREE.Vector2(q.x / S, q.y / S));
const out: [number, number][][] = [];
let ok = true;
outers.forEach((o, i) => {
const contour = v(o);
const hs = kids[i]!.map(v);
const all = [...contour, ...hs.flat()];
let got = 0;
for (const [a, b, c] of THREE.ShapeUtils.triangulateShape(contour, hs)) {
const p = all[a!]!;
const q = all[b!]!;
const r = all[c!]!;
got += Math.abs((q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)) / 2;
out.push([
[p.x, p.y],
[q.x, q.y],
[r.x, r.y],
]);
}
const want = (areas[i]! + kids[i]!.reduce((s, h) => s + Clipper.area(h), 0)) / (S * S);
if (Math.abs(got - want) > 0.5 + want * 0.001) ok = false;
});
if (ok) for (const t of out) emit(t[0]!, t[1]!, t[2]!);
return ok;
}
/**
* The rings merged (less any of `minus`, and within `within` if given) and triangulated,
* a tile at a time. Returns how many tiles had to fall back on their raw outlines.
*/
export function surface(rings: Ring[], emit: Emit, opts: { minus?: Ring[]; within?: Ring } = {}): number {
const tiles = bucket(rings);
const cut = opts.minus ? bucket(opts.minus) : null;
let fallbacks = 0;
const w = new Paths64();
if (opts.within) w.push(toPath(opts.within));
// A square: merged and triangulated; if earcut gets it wrong, in quarters, down to 12.5 m.
const square = (x0: number, z0: number, size: number, list: Ring[], minus: Ring[] | undefined): void => {
const box = new Paths64();
box.push(toPath(rect(x0, z0, x0 + size, z0 + size)));
let shape = Clipper.Intersect(Clipper.Union(paths(list), undefined, FillRule.NonZero), box, FillRule.NonZero);
if (minus) shape = Clipper.Difference(shape, paths(minus), FillRule.NonZero);
if (opts.within) shape = Clipper.Intersect(shape, w, FillRule.NonZero);
if (!shape.length || fill(shape, emit)) return;
if (size > TILE / 8) {
const h = size / 2;
for (const [dx, dz] of [[0, 0], [h, 0], [0, h], [h, h]] as const) square(x0 + dx, z0 + dz, h, list, minus);
return;
}
fallbacks++;
// Drawn as they are instead (overlapping, but never wrong).
for (const r of list) fill(Clipper.Intersect(paths([r]), box, FillRule.NonZero), emit);
};
for (const [k, list] of tiles) {
const [tx, tz] = k.split(',').map(Number) as [number, number];
square(tx * TILE, tz * TILE, TILE, list, cut?.get(k));
}
return fallbacks;
}
/**
* A ring less some others, cut exactly (along their edges, at whatever angle), and
* triangulated; returns the outlines of what's left (for kerbs along them).
*/
export function cutOut(base: Ring, minus: Ring[], emit: Emit): Ring[] {
const sub = minus.length ? paths(minus) : null;
const cut = (ring: Paths64) => (sub ? Clipper.Difference(ring, sub, FillRule.NonZero) : ring);
const shape = cut(paths([base]));
// Earcut slips up now and then: then the piece is filled a quarter at a time (down to
// squares of a metre or so), each cut the same way.
const square = (x0: number, z0: number, x1: number, z1: number, piece: Paths64, depth: number): void => {
if (!piece.length || fill(piece, emit) || depth > 5) return;
const xm = (x0 + x1) / 2;
const zm = (z0 + z1) / 2;
for (const [a, b, c, d] of [
[x0, z0, xm, zm],
[xm, z0, x1, zm],
[x0, zm, xm, z1],
[xm, zm, x1, z1],
] as const) {
const q = new Paths64();
q.push(toPath(rect(a, b, c, d)));
square(a, b, c, d, Clipper.Intersect(shape, q, FillRule.NonZero), depth + 1);
}
};
const xs = base.map((p) => p.x);
const zs = base.map((p) => p.z);
square(Math.min(...xs), Math.min(...zs), Math.max(...xs), Math.max(...zs), shape, 0);
return shape.map((p) => p.map((q) => ({ x: q.x / S, z: q.y / S })));
}
