tower / files / src / views / terrain-lod.ts
terrain-lod.ts
| 1 | /** |
| 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 | */ |
| 14 | import { |
| 15 | BufferAttribute, BufferGeometry, Group, InterleavedBuffer, InterleavedBufferAttribute, Mesh, |
| 16 | type ShaderMaterial, Vector3, |
| 17 | } from 'three' |
| 18 | import type { TerrainService } from '../terrain/service.js' |
| 19 | import { |
| 20 | CANOPY_ATTRS, MATERIALS, MAX_LEVEL, ROOTS_ALONG, ROOTS_AROUND, type TileData, type TileGrid, |
| 21 | type TileKey, WATER_ATTRS, |
| 22 | tileCentreKm, tileIndices, tileKey, tileSize, |
| 23 | } from '../terrain/tile.js' |
| 24 | |
| 25 | interface 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 | |
| 44 | export 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 | */ |
| 59 | export const DESKTOP_LOD: TerrainLODOptions = { grid: 65, maxLevel: MAX_LEVEL, split: 1.8, budget: 1400 } |
| 60 | export 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. */ |
| 63 | const REQUESTS_PER_WORKER = 2 |
| 64 | |
| 65 | export 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, |
| 78 | private waterMaterial: ShaderMaterial, |
| 79 | private canopyMaterial: ShaderMaterial, |
| 80 | 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)) |
| 241 | // Salt, sandstone and farmland sit past the two vec4s (tile.ts MATERIALS). |
| 242 | g.setAttribute('aExtra', new InterleavedBufferAttribute(mats, 3, 8, true)) |
| 243 | /** |
| 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 |
| 267 | if (data.water) mesh.add(this.buildWater(data.water)) |
| 268 | 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 |
| 286 | 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 |
| 307 | 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) |
| 327 | for (const child of n.mesh.children) (child as Mesh).geometry.dispose() |
| 328 | 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 | } |