fuzzyworld

tower / files / src / views / terrain-lod.ts

terrain-lod.ts

Blame: the commit that last changed each line · file · history

376f2ce6 2026-09-16 Pavel Safronov1/**
2 * The ground, as a quadtree of generated tiles. See world-generation.md §6.1.
3 *
4 * Replaces the single displaced cylinder of D-034. Every frame the view hands in
5 * where the eye is; this decides which tiles should be drawn at which level of
6 * detail, asks the terrain service for any it does not have, and shows the best
7 * ones it does. Detail arrives in the background and pops *in*: a tile is split only
8 * once all four of its children are ready, so the ground is never missing, only
9 * coarser than it is about to be.
10 *
11 * Both 3D views use it. From outside, looking in through a window 100 km away, the
12 * split rule keeps it to the coarsest tiles by itself.
13 */
14import {
15 BufferAttribute, BufferGeometry, Group, InterleavedBuffer, InterleavedBufferAttribute, Mesh,
16 type ShaderMaterial, Vector3,
17} from 'three'
18import type { TerrainService } from '../terrain/service.js'
19import {
00ceeedb 2026-09-27 Pavel Safronov20 CANOPY_ATTRS, MATERIALS, MAX_LEVEL, ROOTS_ALONG, ROOTS_AROUND, type TileData, type TileGrid,
21 type TileKey, WATER_ATTRS,
376f2ce6 2026-09-16 Pavel Safronov22 tileCentreKm, tileIndices, tileKey, tileSize,
23} from '../terrain/tile.js'
24
25interface Node {
26 t: TileKey
27 key: string
28 mesh: Mesh | null
29 requested: boolean
30 /** Frame this node was last drawn or wanted, for eviction. */
31 used: number
32 /** Where the tile's mesh is placed: its centre on the datum cylinder, km. */
33 centre: Vector3
34 /**
35 * A sphere around the tile's actual surface, for deciding how near it is. Until the
36 * tile is built its relief is unknown, and the datum centre and flat extent stand in.
37 */
38 boundCentre: Vector3
39 radius: number
40 /** The tile's larger side, km. */
41 size: number
42}
43
44export interface TerrainLODOptions {
45 grid: TileGrid
46 maxLevel: number
47 /** Split a tile once the eye is closer than this many tile-widths. */
48 split: number
49 /** Most tiles kept in memory at once. */
50 budget: number
51}
52
53/**
54 * Measured, not guessed. At a split of 1.8 a level holds about 64 tiles around the eye,
55 * and a 65-vertex tile at that distance puts a vertex every half degree or so — about
56 * a dozen pixels on a laptop screen — which the smooth normals hide. At 2.4 it was
57 * 96 a level and three million triangles for no visible gain.
58 */
59export const DESKTOP_LOD: TerrainLODOptions = { grid: 65, maxLevel: MAX_LEVEL, split: 1.8, budget: 1400 }
60export const PHONE_LOD: TerrainLODOptions = { grid: 33, maxLevel: MAX_LEVEL, split: 1.6, budget: 900 }
61
62/** Most tile requests outstanding at once, per worker. More only queues. */
63const REQUESTS_PER_WORKER = 2
64
65export class TerrainLOD {
66 readonly group = new Group()
67 private nodes = new Map<string, Node>()
68 /** The previous generation's tiles, drawn until the new one has its roots. */
69 private old: Map<string, Node> | null = null
70 private generation = -1
71 private frame = 0
72 private outstanding = 0
73 private eye = new Vector3()
74
75 constructor(
76 private service: TerrainService,
77 private material: ShaderMaterial,
80bcc97a 2026-09-17 Pavel Safronov78 private waterMaterial: ShaderMaterial,
00ceeedb 2026-09-27 Pavel Safronov79 private canopyMaterial: ShaderMaterial,
376f2ce6 2026-09-16 Pavel Safronov80 private opts: TerrainLODOptions,
81 ) {
82 this.group.name = 'ground'
83 }
84
85 /** True when every tile the current view wants is on the ground. */
86 get settled(): boolean {
87 return this.generation >= 0 && this.generation === this.service.generation && !this.old
88 && this.outstanding === 0 && this.wantedMissing === 0
89 }
90 private wantedMissing = 0
91
92 /** Choose and request tiles for an eye at `eye` (km, tower frame). Call every frame. */
93 update(eye: Vector3): void {
94 this.frame++
95 this.eye.copy(eye)
96 if (this.service.generation !== this.generation && this.service.compiled) {
97 this.startGeneration()
98 }
99 for (const n of this.nodes.values()) if (n.mesh) n.mesh.visible = false
100 if (this.old) for (const n of this.old.values()) if (n.mesh) n.mesh.visible = false
101 if (this.generation < 0) return
102
103 const wanted: Node[] = []
104 const roots: Node[] = []
105 for (let i = 0; i < ROOTS_ALONG; i++) {
106 for (let j = 0; j < ROOTS_AROUND; j++) roots.push(this.node(this.nodes, { level: 0, i, j }))
107 }
108
109 if (this.old && roots.every((r) => r.mesh)) {
110 for (const n of this.old.values()) this.dispose(n)
111 this.old = null
112 }
113 if (this.old) {
114 // Keep showing the last world while the new one's roots arrive.
115 for (const r of roots) if (!r.mesh) wanted.push(r)
116 for (let i = 0; i < ROOTS_ALONG; i++) {
117 for (let j = 0; j < ROOTS_AROUND; j++) {
118 this.select(this.old, this.node(this.old, { level: 0, i, j }), null)
119 }
120 }
121 } else {
122 for (const r of roots) this.select(this.nodes, r, wanted)
123 }
124
125 this.wantedMissing = wanted.length
126 this.request(wanted)
127 this.evict()
128 }
129
130 private startGeneration(): void {
131 if (this.old) for (const n of this.old.values()) this.dispose(n)
132 this.old = this.nodes.size ? this.nodes : null
133 this.nodes = new Map()
134 this.generation = this.service.generation
135 }
136
137 private node(map: Map<string, Node>, t: TileKey): Node {
138 const key = tileKey(t)
139 let n = map.get(key)
140 if (!n) {
141 const size = tileSize(t.level)
142 const along = size.along / 1000, around = size.around / 1000
143 n = {
144 t, key, mesh: null, requested: false, used: 0,
145 centre: new Vector3(...tileCentreKm(t)),
146 boundCentre: new Vector3(...tileCentreKm(t)),
147 radius: Math.hypot(along, around) / 2,
148 size: Math.max(along, around),
149 }
150 map.set(key, n)
151 }
152 return n
153 }
154
155 private distance(n: Node): number {
156 return Math.max(0, this.eye.distanceTo(n.boundCentre) - n.radius)
157 }
158
159 /**
160 * Draw `n`, or its children if they are wanted and all ready. `wanted` collects the
161 * tiles that should exist and do not; null while drawing an old generation, which
162 * never asks for anything.
163 */
164 private select(map: Map<string, Node>, n: Node, wanted: Node[] | null): void {
165 n.used = this.frame
166 if (!n.mesh) {
167 if (wanted && !n.requested) wanted.push(n)
168 return
169 }
170 const split = n.t.level < this.opts.maxLevel && this.distance(n) < this.opts.split * n.size
171 if (split) {
172 const { level, i, j } = n.t
173 const around = ROOTS_AROUND * 2 ** (level + 1)
174 const kids = [
175 this.child(map, level + 1, 2 * i, 2 * j, around, wanted !== null),
176 this.child(map, level + 1, 2 * i + 1, 2 * j, around, wanted !== null),
177 this.child(map, level + 1, 2 * i, 2 * j + 1, around, wanted !== null),
178 this.child(map, level + 1, 2 * i + 1, 2 * j + 1, around, wanted !== null),
179 ].filter((k): k is Node => k !== null)
180 if (kids.length === 4 && kids.every((k) => k.mesh)) {
181 for (const k of kids) this.select(map, k, wanted)
182 return
183 }
184 if (wanted) for (const k of kids) if (!k.mesh && !k.requested) wanted.push(k)
185 }
186 n.mesh.visible = true
187 }
188
189 private child(map: Map<string, Node>, level: number, i: number, j: number, around: number, create: boolean): Node | null {
190 const t = { level, i, j: ((j % around) + around) % around }
191 if (create) {
192 const n = this.node(map, t)
193 n.used = this.frame
194 return n
195 }
196 return map.get(tileKey(t)) ?? null
197 }
198
199 /** Ask for the wanted tiles, coarsest and nearest first, as the pool has room. */
200 private request(wanted: Node[]): void {
201 const room = this.service.workers * REQUESTS_PER_WORKER - this.outstanding
202 if (room <= 0 || !wanted.length) return
203 wanted.sort((a, b) => a.t.level - b.t.level || this.distance(a) / a.size - this.distance(b) / b.size)
204 const gen = this.generation
205 for (const n of wanted.slice(0, room)) {
206 n.requested = true
207 this.outstanding++
208 void this.service.tile(n.t, this.opts.grid).then((data) => {
209 this.outstanding--
210 if (gen !== this.generation || this.nodes.get(n.key) !== n) return
211 if (!data) {
212 n.requested = false
213 return
214 }
215 /**
216 * Measure the tile now that its relief is known. A fixed allowance for the
217 * tallest mountain made every small tile within 5 km of the eye look near
218 * enough to split, all the way to the finest level, which is tens of
219 * thousands of tiles; the real extent of a 33 m tile is a few metres.
220 */
221 const midKm = (data.minM + data.maxM) / 2000
222 const r = Math.hypot(n.centre.x, n.centre.y)
223 n.boundCentre.set(n.centre.x * (1 - midKm / r), n.centre.y * (1 - midKm / r), n.centre.z)
224 n.radius = Math.hypot(n.radius, (data.maxM - data.minM) / 2000)
225 n.mesh = this.build(n, data)
226 this.group.add(n.mesh)
227 }, () => {
228 this.outstanding--
229 n.requested = false
230 })
231 }
232 }
233
234 private build(n: Node, data: TileData): Mesh {
235 const g = new BufferGeometry()
236 g.setAttribute('position', new BufferAttribute(data.positions, 3))
237 g.setAttribute('normal', new BufferAttribute(data.normals, 3, true))
238 const mats = new InterleavedBuffer(data.materials, MATERIALS.length)
239 g.setAttribute('aMatA', new InterleavedBufferAttribute(mats, 4, 0, true))
240 g.setAttribute('aMatB', new InterleavedBufferAttribute(mats, 4, 4, true))
abc0aad0 2026-10-01 Pavel Safronov241 // Salt, sandstone and farmland sit past the two vec4s (tile.ts MATERIALS).
242 g.setAttribute('aExtra', new InterleavedBufferAttribute(mats, 3, 8, true))
376f2ce6 2026-09-16 Pavel Safronov243 /**
244 * The index array is shared, but each tile gets its own attribute around it.
245 * Sharing the attribute too would share one GL buffer, and disposing any tile
246 * deletes that buffer out from under every other tile still drawing with it.
247 */
248 g.setIndex(new BufferAttribute(tileIndices(this.opts.grid), 1))
249 g.computeBoundingSphere()
250 /**
251 * Once on the GPU the CPU copies are dead weight — a thousand tiles of them is a
252 * couple of hundred megabytes — and nothing reads them again: the bounding sphere
253 * is already computed, and standing on the ground asks the elevation function,
254 * not the mesh. So they are dropped on upload.
255 */
256 const release = function (this: { array: unknown }): void { this.array = null }
257 for (const a of [g.attributes['position'], g.attributes['normal'], g.index]) {
258 (a as BufferAttribute).onUpload(release)
259 }
260 mats.onUpload(release)
261 const mesh = new Mesh(g, this.material)
262 mesh.name = `tile ${n.key}`
263 mesh.position.copy(n.centre)
264 mesh.matrixAutoUpdate = false
265 mesh.updateMatrix()
266 mesh.visible = false
80bcc97a 2026-09-17 Pavel Safronov267 if (data.water) mesh.add(this.buildWater(data.water))
00ceeedb 2026-09-27 Pavel Safronov268 if (data.canopy) mesh.add(this.buildCanopy(data.canopy))
269 return mesh
270 }
271
272 /** The tile's forest canopy, a child of its ground like the water. */
273 private buildCanopy(c: NonNullable<TileData['canopy']>): Mesh {
274 const g = new BufferGeometry()
275 g.setAttribute('position', new BufferAttribute(c.positions, 3))
276 g.setAttribute('aCanopy', new BufferAttribute(c.attrs, CANOPY_ATTRS))
277 g.setIndex(new BufferAttribute(c.indices, 1))
278 g.computeBoundingSphere()
279 const release = function (this: { array: unknown }): void { this.array = null }
280 for (const a of [g.attributes['position'], g.attributes['aCanopy'], g.index]) {
281 (a as BufferAttribute).onUpload(release)
282 }
283 const mesh = new Mesh(g, this.canopyMaterial)
284 mesh.name = 'canopy'
285 mesh.matrixAutoUpdate = false
80bcc97a 2026-09-17 Pavel Safronov286 return mesh
287 }
288
289 /** The tile's water, a child of its ground so it shows and hides and disposes with it. */
290 private buildWater(w: NonNullable<TileData['water']>): Mesh {
291 const g = new BufferGeometry()
292 g.setAttribute('position', new BufferAttribute(w.positions, 3))
293 const attrs = new InterleavedBuffer(w.attrs, WATER_ATTRS)
294 g.setAttribute('aWater', new InterleavedBufferAttribute(attrs, 4, 0))
295 g.setAttribute('aFlow', new InterleavedBufferAttribute(attrs, 4, 4))
296 g.setIndex(new BufferAttribute(w.indices, 1))
297 g.computeBoundingSphere()
298 const release = function (this: { array: unknown }): void { this.array = null }
299 ;(g.attributes['position'] as BufferAttribute).onUpload(release)
300 ;(g.index as BufferAttribute).onUpload(release)
301 attrs.onUpload(release)
302 const mesh = new Mesh(g, this.waterMaterial)
303 mesh.name = 'water'
304 // After the ground, so it blends over the bed.
305 mesh.renderOrder = 1
306 mesh.matrixAutoUpdate = false
376f2ce6 2026-09-16 Pavel Safronov307 return mesh
308 }
309
310 /** Drop the least recently used tiles past the budget. Roots stay: they are the floor. */
311 private evict(): void {
312 let loaded = 0
313 for (const n of this.nodes.values()) if (n.mesh) loaded++
314 if (loaded <= this.opts.budget) return
315 const victims = [...this.nodes.values()]
316 .filter((n) => n.mesh && n.t.level > 0 && n.used < this.frame)
317 .sort((a, b) => a.used - b.used)
318 for (const n of victims.slice(0, loaded - this.opts.budget)) {
319 this.dispose(n)
320 this.nodes.delete(n.key)
321 }
322 }
323
324 private dispose(n: Node): void {
325 if (!n.mesh) return
326 this.group.remove(n.mesh)
80bcc97a 2026-09-17 Pavel Safronov327 for (const child of n.mesh.children) (child as Mesh).geometry.dispose()
376f2ce6 2026-09-16 Pavel Safronov328 n.mesh.geometry.dispose()
329 n.mesh = null
330 }
331
332 /** Tiles currently drawn, for the flight recorder. */
333 get drawn(): number {
334 let k = 0
335 for (const n of this.nodes.values()) if (n.mesh?.visible) k++
336 return k
337 }
338}