fuzzyworld

tower / files / src / views / forest-view.ts

forest-view.ts

18.9 KB · history · blame

1/**
2 * The trees near the eye. See world-generation.md §4.6.
3 *
4 * Greatwood holds about three billion trees, so what exists at any moment is only the ones
5 * you could actually see as trees: a few thousand as **meshes** within a couple of hundred
6 * metres, tens of thousands as **cards** — one billboarded quad each — out to about half a
7 * kilometre, and beyond that nothing, because the tile's canopy skin has taken over
8 * (interior-model.ts CANOPY_VERT). The three ranges meet where the change is under a pixel.
9 *
10 * Which trees they are comes from forest.ts, whose placement is a pure function of the
11 * world's seed and the ground: walking a kilometre and back puts every tree back exactly
12 * where it was, and two people standing in the same clearing see the same trees.
13 *
14 * The ground is sampled on a grid and the trees interpolate between its nodes — one full
15 * elevation sample per tree would be tens of thousands of them per rebuild.
16 */
17import {
18 BufferAttribute, BufferGeometry, ConeGeometry, CylinderGeometry, Group, IcosahedronGeometry,
19 InstancedBufferAttribute, InstancedMesh, Matrix4, type ShaderMaterial, Vector3,
20} from 'three'
21import { RADIUS_M } from '../canon/constants.js'
22import {
23 type CForest, type Clump, type Spot, type Tree, cellSizeM, forEachClump, forEachTree,
24} from '../terrain/forest.js'
25import { nearestA } from '../terrain/shapes.js'
26import { type GroundAt, type TerrainService } from '../terrain/service.js'
27
28/** How many trees are drawn as meshes, as cards, and as clumps. */
29const MAX_MESH = 6000
30const MAX_CARD = 45_000
31const MAX_CLUMP = 30_000
32/**
33 * Past the cards a stand of trees is drawn as clumps: one card for everything in a cell
34 * this wide. A card each would be a quarter of a million of them at a kilometre and a
35 * million at two; a clump every twenty-six metres reaches nearly three kilometres for
36 * thirty thousand, and at that distance a clump is about the width of a thumbnail held out
37 * at arm's length — which is what a group of crowns looks like from there anyway.
38 */
39const CLUMP_CELL_M = 30
40const CLUMP_REACH_M = 2800
41/** How far apart the clump layer samples the ground. */
42const CLUMP_GROUND_M = 90
43/** Rebuilt once the eye has moved this far, metres — and the clump layer, this far. */
44const MOVED_M = 30
45const MOVED_FAR_M = 170
46/**
47 * Moving faster than this between rebuilds — flying rather than walking — the wood is
48 * rebuilt at a fraction of the budget. A full rebuild is about 19 ms, which is nothing
49 * every twenty seconds of walking and a stutter every sixth of a second in flight; at
50 * 100 m/s the near trees are a blur going past, and the canopy behind them is not.
51 */
52const FLYING_M = 260
53const FLYING_SHARE = 0.28
54/** The ground is sampled this far apart for the mesh trees, and for the cards. */
55const FINE_M = 12
56const COARSE_M = 45
57
58export interface Fleet {
59 conifer: InstancedMesh
60 broadleaf: InstancedMesh
61 giant: InstancedMesh
62 cards: InstancedMesh
63 clumps: InstancedMesh
64}
65
66export class ForestView {
67 readonly group = new Group()
68 readonly meshes: Fleet
69 /** Trees standing as meshes, cards and clumps in the last rebuild. */
70 counts = { mesh: 0, card: 0, clump: 0 }
71
72 private eye = new Vector3(Infinity, 0, 0)
73 private farEye = new Vector3(Infinity, 0, 0)
74 private generation = -1
75 /** The last rebuild ran at the flying budget, so the wood is thinner than it should be. */
76 private thinned = false
77 private cards: InstancedBufferAttribute
78 private clumps: InstancedBufferAttribute
79
80 constructor(
81 private service: TerrainService,
82 treeMaterial: ShaderMaterial,
83 cardMaterial: ShaderMaterial,
84 ) {
85 this.group.name = 'forest'
86 const mesh = (geometry: BufferGeometry, max: number, material: ShaderMaterial, name: string): InstancedMesh => {
87 const m = new InstancedMesh(geometry, material, max)
88 m.name = name
89 m.count = 0
90 // The instances are placed around the eye every rebuild; the mesh's own bounds mean
91 // nothing, and its matrix is the eye's.
92 m.frustumCulled = false
93 return m
94 }
95 this.meshes = {
96 conifer: mesh(coniferGeometry(), MAX_MESH, treeMaterial, 'conifers'),
97 broadleaf: mesh(broadleafGeometry(), MAX_MESH, treeMaterial, 'broadleaves'),
98 giant: mesh(giantGeometry(), MAX_MESH, treeMaterial, 'giants'),
99 cards: mesh(cardGeometry(), MAX_CARD, cardMaterial, 'tree cards'),
100 clumps: mesh(cardGeometry(), MAX_CLUMP, cardMaterial, 'tree clumps'),
101 }
102 // What each card is: 0 broadleaf, 1 conifer, 2 giant, 3 a clump; and its own number.
103 this.cards = new InstancedBufferAttribute(new Float32Array(MAX_CARD * 2), 2)
104 this.meshes.cards.geometry.setAttribute('aCard', this.cards)
105 this.clumps = new InstancedBufferAttribute(new Float32Array(MAX_CLUMP * 2), 2)
106 this.meshes.clumps.geometry.setAttribute('aCard', this.clumps)
107 this.group.add(
108 this.meshes.conifer, this.meshes.broadleaf, this.meshes.giant,
109 this.meshes.cards, this.meshes.clumps)
110 }
111
112 /** Put the trees around the eye. Cheap to call every frame: it only rebuilds when it must. */
113 update(eye: Vector3): void {
114 const compiled = this.service.compiled
115 if (!compiled || !compiled.forests?.length) {
116 for (const m of Object.values(this.meshes)) m.count = 0
117 return
118 }
119 const moved = this.eye.distanceTo(eye) * 1000
120 const gen = this.service.generation
121 /**
122 * A thinned wood is rebuilt in full as soon as the eye settles — otherwise arriving
123 * somewhere by flight or by selecting a place left the trees at a quarter strength
124 * until you walked thirty metres, which looked like a thin wood rather than a fast one.
125 */
126 if (moved < MOVED_M && !this.thinned && this.generation === gen) return
127 this.eye.copy(eye)
128 const share = moved > FLYING_M ? FLYING_SHARE : 1
129 this.thinned = share < 1
130 /**
131 * The clumps are two kilometres out and cost more than everything else together, and at
132 * that distance a hundred metres of walking moves them by nothing anyone can see. So
133 * they are left where they are until the eye has gone a good way — which is why they
134 * keep their own origin rather than sharing the near layers'.
135 */
136 const far = this.farEye.distanceTo(eye) * 1000 > MOVED_FAR_M || this.generation !== gen
137 if (far) this.farEye.copy(eye)
138 this.rebuild(
139 compiled.forests, eye, Math.round(MAX_MESH * share), Math.round(MAX_CARD * share), far)
140 }
141
142 private rebuild(
143 forests: CForest[], eye: Vector3, maxMesh: number, maxCard: number, rebuildFar: boolean,
144 ): void {
145 /**
146 * Every instance is placed relative to the eye, so a rebuild starts from nothing.
147 * Left to grow, the counts kept last rebuild's trees as well — at the old eye, and
148 * turned for the ground they used to stand on, which drew them lying over as logs.
149 */
150 for (const [name, m] of Object.entries(this.meshes)) {
151 if (name === 'clumps' && !rebuildFar) continue
152 m.position.copy(eye)
153 m.count = 0
154 }
155 this.generation = this.service.generation
156 const theta = Math.atan2(eye.y, eye.x)
157 const centre = { z: eye.z * 1000, a: theta * RADIUS_M }
158
159 let mesh = 0, card = 0, clump = 0
160 const matrix = new Matrix4()
161 /**
162 * Only the woods the eye is anywhere near share the budget. Dividing it between every
163 * forest in the world halved the reach of the one you were standing in because the tall
164 * wood exists twenty kilometres away.
165 */
166 const nearby = forests.filter((f) => near(f.box, centre, CLUMP_REACH_M))
167 for (const f of nearby) {
168 /**
169 * How far out the trees reach: whatever fits the budget at this forest's density,
170 * capped so a sparse wood does not reach past where the canopy skin takes over.
171 */
172 const perM2 = f.densityPerHa / 10_000
173 const meshR = Math.min(320, Math.sqrt(maxMesh / nearby.length / perM2 / Math.PI))
174 const cardR = Math.min(760, Math.sqrt(maxCard / nearby.length / perM2 / Math.PI))
175 if (cardR < cellSizeM(f)) continue
176
177 const fine = new Field(this.service, centre, meshR, FINE_M)
178 const coarse = new Field(this.service, centre, cardR, COARSE_M)
179 const box = (r: number) => ({ z0: centre.z - r, z1: centre.z + r, a0: centre.a - r, a1: centre.a + r })
180
181 const within = (r: number) => (z: number, a: number): boolean =>
182 (z - centre.z) * (z - centre.z) + (a - centre.a) * (a - centre.a) <= r * r
183 forEachTree(f, box(cardR), (z, a) => coarse.at(z, a), (tree) => {
184 const d = Math.hypot(tree.z - centre.z, tree.a - centre.a)
185 if (d > cardR) return
186 // Near the eye a tree is a mesh, and its ground is resampled finely so its foot
187 // sits on the ground rather than on the interpolation between two samples.
188 if (d <= meshR) {
189 if (mesh >= maxMesh) return
190 place(matrix, tree, fine.at(tree.z, tree.a).h, tree.heightM / 1000, eye)
191 const target = tree.giant ? this.meshes.giant : tree.conifer ? this.meshes.conifer : this.meshes.broadleaf
192 target.setMatrixAt(target.count++, matrix)
193 mesh++
194 return
195 }
196 if (card >= maxCard) return
197 cardMatrix(matrix, tree, coarse.at(tree.z, tree.a).h, eye)
198 this.cards.setXY(card, tree.giant ? 2 : tree.conifer ? 1 : 0, tree.rand)
199 this.meshes.cards.setMatrixAt(card++, matrix)
200 }, within(cardR))
201
202 /**
203 * And the wood beyond the cards, as clumps, out to where the tile's canopy skin
204 * takes over. Its ground is sampled coarsely: at two kilometres nobody can tell
205 * whether a stand of trees is standing ten metres higher than it is.
206 */
207 if (!rebuildFar) continue
208 const clumpR = Math.min(
209 CLUMP_REACH_M,
210 Math.sqrt((MAX_CLUMP / nearby.length) * CLUMP_CELL_M * CLUMP_CELL_M / Math.PI))
211 const far = new Field(this.service, centre, clumpR, CLUMP_GROUND_M)
212 forEachClump(f, box(clumpR), CLUMP_CELL_M, (z, a) => far.at(z, a), (c) => {
213 if (clump >= MAX_CLUMP) return
214 const d = Math.hypot(c.z - centre.z, c.a - centre.a)
215 if (d < cardR || d > clumpR) return
216 clumpMatrix(matrix, c, far.at(c.z, c.a).h, eye)
217 this.clumps.setXY(clump, 3, c.rand)
218 this.meshes.clumps.setMatrixAt(clump++, matrix)
219 }, within(clumpR))
220 }
221
222 this.meshes.cards.count = card
223 this.cards.needsUpdate = true
224 for (const m of Object.values(this.meshes)) {
225 if (m === this.meshes.clumps && !rebuildFar) continue
226 m.instanceMatrix.needsUpdate = true
227 }
228 if (rebuildFar) {
229 this.meshes.clumps.count = clump
230 this.clumps.needsUpdate = true
231 this.counts = { mesh, card, clump }
232 } else {
233 this.counts = { mesh, card, clump: this.counts.clump }
234 }
235 }
236
237 dispose(): void {
238 for (const m of Object.values(this.meshes)) {
239 m.geometry.dispose()
240 m.dispose()
241 }
242 }
243}
244
245/** Whether a forest's box comes within `reach` of a point, allowing for theta's wrap. */
246function near(box: { z0: number; z1: number; a0: number; a1: number }, at: { z: number; a: number }, reach: number): boolean {
247 if (at.z < box.z0 - reach || at.z > box.z1 + reach) return false
248 if (!Number.isFinite(box.a0) || !Number.isFinite(box.a1)) return true
249 const a = nearestA(at.a, (box.a0 + box.a1) / 2)
250 return a >= box.a0 - reach && a <= box.a1 + reach
251}
252
253/**
254 * A grid of what the ground is, sampled once and read between its nodes — including **how
255 * thick the wood is**, which is what the placement reads rather than working the density
256 * out from the noise at every candidate cell. The meadows' edges are then as fine as this
257 * grid, which at twelve metres near the eye is finer than the trees are apart.
258 */
259class Field {
260 private readonly n: number
261 private readonly z0: number
262 private readonly a0: number
263 private readonly h: Float32Array
264 private readonly stems: Float32Array
265 private readonly water: Uint8Array
266
267 constructor(service: TerrainService, centre: { z: number; a: number }, reach: number, private cell: number) {
268 this.n = Math.ceil((2 * reach) / cell) + 2
269 this.z0 = centre.z - reach - cell
270 this.a0 = centre.a - reach - cell
271 const n = this.n
272 this.h = new Float32Array(n * n)
273 this.stems = new Float32Array(n * n)
274 this.water = new Uint8Array(n * n)
275 const blank: GroundAt = { h: 0, water: false, stems: 0, canopyM: 0, desert: 0, rock: 0, glacier: false }
276 for (let i = 0; i < n; i++) {
277 for (let j = 0; j < n; j++) {
278 const z = this.z0 + i * cell, a = this.a0 + j * cell
279 const g = service.groundAt(a / RADIUS_M, z, cell) ?? blank
280 const k = i * n + j
281 this.h[k] = g.h
282 this.stems[k] = g.stems
283 this.water[k] = g.water ? 1 : 0
284 }
285 }
286 }
287
288 /** Shared, as Runtime.sample's is: read it before asking again. */
289 private readonly out: Spot = { stems: 0, h: 0 }
290
291 at(z: number, a: number): Spot {
292 const fi = Math.min(this.n - 2, Math.max(0, (z - this.z0) / this.cell))
293 const fj = Math.min(this.n - 2, Math.max(0, (a - this.a0) / this.cell))
294 const i = Math.floor(fi), j = Math.floor(fj)
295 const ti = fi - i, tj = fj - j
296 const k = i * this.n + j
297 const lerp = (arr: Float32Array): number => {
298 const top = arr[k]! * (1 - tj) + arr[k + 1]! * tj
299 const bot = arr[k + this.n]! * (1 - tj) + arr[k + this.n + 1]! * tj
300 return top * (1 - ti) + bot * ti
301 }
302 const out = this.out
303 out.h = lerp(this.h)
304 // Any wet corner takes the trees out: a tree half in a river is worse than none.
305 out.stems = this.water[k]! || this.water[k + 1]! || this.water[k + this.n]! || this.water[k + this.n + 1]!
306 ? 0
307 : lerp(this.stems)
308 return out
309 }
310
311}
312
313/**
314 * A tree's instance matrix. The tree stands on the floor, so its up is toward the axis and
315 * it is turned about that by its own number — every tree the same way round would read as
316 * a pattern from the air.
317 */
318const scratch = {
319 up: new Vector3(), x: new Vector3(), zAxis: new Vector3(), scale: new Vector3(),
320}
321
322function place(out: Matrix4, tree: Tree, groundM: number, scaleKm: number, eye: Vector3): Matrix4 {
323 const theta = tree.a / RADIUS_M
324 const cos = Math.cos(theta), sin = Math.sin(theta)
325 const r = (RADIUS_M - groundM) / 1000
326 const turn = tree.rand * Math.PI * 2
327 const { up, x, zAxis, scale } = scratch
328 up.set(-cos, -sin, 0)
329 // Deepward turned by the tree's own number: x = cos·deepward + sin·spinward.
330 x.set(-sin * Math.sin(turn), cos * Math.sin(turn), Math.cos(turn))
331 zAxis.crossVectors(x, up)
332 out.makeBasis(x, up, zAxis)
333 out.scale(scale.setScalar(scaleKm))
334 out.setPosition(r * cos - eye.x, r * sin - eye.y, tree.z / 1000 - eye.z)
335 return out
336}
337
338/** A clump's matrix: the same as a card's, at the size of the whole stand. */
339function clumpMatrix(out: Matrix4, c: Clump, groundM: number, eye: Vector3): Matrix4 {
340 const theta = c.a / RADIUS_M
341 const cos = Math.cos(theta), sin = Math.sin(theta)
342 const r = (RADIUS_M - groundM) / 1000
343 out.identity()
344 out.elements[0] = c.widthM / 1000
345 out.elements[5] = c.heightM / 1000
346 out.setPosition(r * cos - eye.x, r * sin - eye.y, c.z / 1000 - eye.z)
347 return out
348}
349
350/**
351 * A card's matrix: where the tree stands, how wide it is and how tall. The quad itself is
352 * turned to face the eye in the shader, about the tree's own upright, so a card never
353 * leans and never shows its edge.
354 */
355function cardMatrix(out: Matrix4, tree: Tree, groundM: number, eye: Vector3): Matrix4 {
356 const theta = tree.a / RADIUS_M
357 const cos = Math.cos(theta), sin = Math.sin(theta)
358 const r = (RADIUS_M - groundM) / 1000
359 out.identity()
360 out.elements[0] = (tree.crownM * 2.1) / 1000
361 out.elements[5] = tree.heightM / 1000
362 out.setPosition(r * cos - eye.x, r * sin - eye.y, tree.z / 1000 - eye.z)
363 return out
364}
365
366// ------------------------------------------------------------------ geometries
367
368/**
369 * What a vertex belongs to, for the shader: bark, or the foliage of one kind of tree.
370 * Every tree mesh shares one material, so the part is carried by the geometry.
371 */
372export const PART = { bark: 0, conifer: 1, broadleaf: 2, giant: 3 } as const
373
374/** Merge a few geometries into one non-indexed buffer, tagging each vertex's part. */
375function merge(parts: { geometry: BufferGeometry; part: number; y: number; scale?: number }[]): BufferGeometry {
376 const positions: number[] = [], normals: number[] = [], kinds: number[] = []
377 for (const part of parts) {
378 const g = part.geometry.toNonIndexed()
379 const pos = g.getAttribute('position'), nor = g.getAttribute('normal')
380 const s = part.scale ?? 1
381 for (let i = 0; i < pos.count; i++) {
382 positions.push(pos.getX(i) * s, pos.getY(i) * s + part.y, pos.getZ(i) * s)
383 normals.push(nor.getX(i), nor.getY(i), nor.getZ(i))
384 kinds.push(part.part)
385 }
386 g.dispose()
387 part.geometry.dispose()
388 }
389 const out = new BufferGeometry()
390 out.setAttribute('position', new BufferAttribute(new Float32Array(positions), 3))
391 out.setAttribute('normal', new BufferAttribute(new Float32Array(normals), 3))
392 out.setAttribute('aPart', new BufferAttribute(new Float32Array(kinds), 1))
393 return out
394}
395
396/**
397 * A conifer, one unit tall: a tapered trunk and three stacked cones, narrow — §4.6 puts a
398 * conifer's crown at 0.28 of its height. Sixty-odd triangles.
399 */
400function coniferGeometry(): BufferGeometry {
401 const crown = 0.14
402 return merge([
403 { geometry: new CylinderGeometry(0.006, 0.014, 1, 6, 1), part: PART.bark, y: 0.5 },
404 { geometry: new ConeGeometry(crown, 0.44, 8, 1), part: PART.conifer, y: 0.36 },
405 { geometry: new ConeGeometry(crown * 0.78, 0.38, 8, 1), part: PART.conifer, y: 0.6 },
406 { geometry: new ConeGeometry(crown * 0.5, 0.3, 8, 1), part: PART.conifer, y: 0.83 },
407 ])
408}
409
410/** A broadleaf: a short trunk under a crown of three lumps, wide and round (§4.6). */
411function broadleafGeometry(): BufferGeometry {
412 const crown = 0.31
413 return merge([
414 { geometry: new CylinderGeometry(0.008, 0.018, 0.55, 6, 1), part: PART.bark, y: 0.27 },
415 { geometry: new IcosahedronGeometry(crown, 0), part: PART.broadleaf, y: 0.68 },
416 { geometry: new IcosahedronGeometry(crown * 0.72, 0), part: PART.broadleaf, y: 0.52 },
417 { geometry: new IcosahedronGeometry(crown * 0.62, 0), part: PART.broadleaf, y: 0.85 },
418 ])
419}
420
421/**
422 * A giant: a column of a trunk — 1/22 of its height, so a 110 m tree is 5 m through — bare
423 * for half its height, with the crown above that (§4.6).
424 */
425function giantGeometry(): BufferGeometry {
426 const crown = 0.09
427 return merge([
428 { geometry: new CylinderGeometry(0.028, 0.048, 1, 10, 1), part: PART.bark, y: 0.5 },
429 { geometry: new ConeGeometry(crown, 0.4, 10, 1), part: PART.giant, y: 0.62 },
430 { geometry: new ConeGeometry(crown * 0.72, 0.34, 10, 1), part: PART.giant, y: 0.82 },
431 { geometry: new ConeGeometry(crown * 0.44, 0.22, 8, 1), part: PART.giant, y: 0.95 },
432 ])
433}
434
435/** A card: a unit quad standing on the ground, billboarded by the shader. */
436function cardGeometry(): BufferGeometry {
437 const g = new BufferGeometry()
438 g.setAttribute('position', new BufferAttribute(new Float32Array([
439 -0.5, 0, 0, 0.5, 0, 0, 0.5, 1, 0, -0.5, 0, 0, 0.5, 1, 0, -0.5, 1, 0,
440 ]), 3))
441 g.setAttribute('uv', new BufferAttribute(new Float32Array([0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1]), 2))
442 return g
443}