sgl-3d 0.4.2

Caller-driven 3D rendering for SGL games, native and in the browser (WebGPU)
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
//! The world grid over a specular probe collection's influence boxes, which
//! probe captures and ray hits walk instead of every probe
//! (probe_grid.wgsl). The pattern is Wicked Engine's surfel grid (revision
//! 4323a33): a ray hit in surfel_raytraceCS.hlsl reads its cell's
//! `SurfelGridCell` count and offset (ShaderInterop_Renderer.h) into a list of
//! the surfels that overlap the cell, which surfel_binningCS.hlsl fills.
//! Probes are static, so SGL3D builds the grid once, on the CPU, when they are
//! installed: one level over the collection's bounds, not around the camera.
use crate::baked_specular_probe::SpecularProbeBox;
use glam::{Mat4, UVec3, Vec3};

/// Cells at most: 256 KiB of cell records.
const MAX_CELLS: u32 = 1 << 15;

/// The farthest world coordinate the grid covers: a quarter of f32's range,
/// so the extent of bounds clamped to it, with its margin, and the grid's
/// origin and scale stay finite. A box reaching past it, or one whose world
/// bounds overflow f32 (a rotated box nearly as wide as f32 allows), covers
/// the grid only to here. Proxies are clamped to it in their own frame
/// (probes.rs), which keeps box projection's distances finite.
pub(super) const REACH: f32 = f32::MAX / 4.;

/// One cell's record in `ProbeGrid::words`: its list's first index into
/// `words` and its probe count. probe_grid.wgsl reads it as
/// PROBE_GRID_CELL_WORDS words, the fields at PROBE_GRID_CELL_FIRST and
/// PROBE_GRID_CELL_COUNT.
#[repr(C)]
#[derive(Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
struct GridCell {
    first: u32,
    count: u32,
}

/// `GridCell`'s size in words.
const CELL_WORDS: usize = std::mem::size_of::<GridCell>() / 4;

pub(super) struct ProbeGrid {
    /// The minimum corner of cell (0, 0, 0).
    pub origin: Vec3,
    /// Cells per metre.
    pub scale: f32,
    /// Cells on each axis; zero without probes.
    pub size: UVec3,
    /// Each cell's `GridCell`, x fastest, then y, then z, followed by the
    /// cells' probe indices, each list ascending.
    pub words: Vec<u32>,
}

impl ProbeGrid {
    /// No cells; one word, so the collection's grid is never empty.
    pub fn empty() -> Self {
        Self {
            origin: Vec3::ZERO,
            scale: 0.,
            size: UVec3::ZERO,
            words: vec![0],
        }
    }

    /// The grid over probes whose influence boxes are `influences`, each a
    /// world-to-local transform and the box in that frame.
    pub fn new(influences: &[(Mat4, SpecularProbeBox)]) -> Self {
        if influences.is_empty() {
            return Self::empty();
        }
        let reach = Vec3::splat(REACH);
        let bounds: Vec<[Vec3; 2]> = influences
            .iter()
            .map(|influence| world_bounds(influence).map(|b| b.clamp(-reach, reach)))
            .collect();
        let (min, max) = bounds.iter().fold(
            (Vec3::INFINITY, Vec3::NEG_INFINITY),
            |(min, max), [lo, hi]| (min.min(*lo), max.max(*hi)),
        );
        // Cubic cells, as fine as the budget allows.
        let extent = max - min;
        let magnitude = min.abs().max(max.abs()).max_element();
        // No finer than the longest axis allows, which also keeps a thin
        // collection's cell positive, nor than f32's spacing at the bounds,
        // which keeps it positive when a tiny box far from the origin has
        // no extent in f32, nor below the smallest normal f32, where a
        // sub-picometre box at the origin underflows both. Each axis's cube
        // root is taken first, so the volume cannot overflow.
        let mut cell = (extent.x.cbrt() * extent.y.cbrt() * extent.z.cbrt()
            / (MAX_CELLS as f32).cbrt())
        .max(extent.max_element() / MAX_CELLS as f32)
        .max(magnitude * f32::EPSILON)
        .max(f32::MIN_POSITIVE);
        // A cell lists every probe whose bounds, widened by `margin`, overlap
        // it, so rounding in the GPU's local transform and cell arithmetic
        // cannot move a point a probe reaches into a cell that omits it.
        let (margin, size) = loop {
            let margin = cell / 64. + magnitude * f32::EPSILON * 512.;
            // Counted in f32: a tiny box far from the origin has a margin of
            // so many cells that their product overflows any integer, and
            // f32 is exact to the budget and rounds monotonically past it.
            let counts = ((extent + Vec3::splat(2. * margin)) / cell)
                .ceil()
                .max(Vec3::ONE);
            if counts.element_product() <= MAX_CELLS as f32 {
                break (margin, counts.as_uvec3());
            }
            cell *= 1.125;
        };
        let mut grid = Self {
            origin: min - Vec3::splat(margin),
            scale: 1. / cell,
            size,
            words: Vec::new(),
        };
        let last_cell = (size - UVec3::ONE).as_vec3();
        let mut cells = vec![Vec::new(); size.element_product() as usize];
        for (index, [lo, hi]) in bounds.iter().enumerate() {
            let first = grid
                .coordinates(*lo - Vec3::splat(margin))
                .clamp(Vec3::ZERO, last_cell)
                .as_uvec3();
            let last = grid
                .coordinates(*hi + Vec3::splat(margin))
                .clamp(Vec3::ZERO, last_cell)
                .as_uvec3();
            for z in first.z..=last.z {
                for y in first.y..=last.y {
                    for x in first.x..=last.x {
                        cells[grid.flatten(UVec3::new(x, y, z))].push(index as u32);
                    }
                }
            }
        }
        let mut first = (CELL_WORDS * cells.len()) as u32;
        let records: Vec<GridCell> = cells
            .iter()
            .map(|list| {
                let cell = GridCell {
                    first,
                    count: list.len() as u32,
                };
                first += cell.count;
                cell
            })
            .collect();
        grid.words.extend_from_slice(bytemuck::cast_slice(&records));
        grid.words.extend(cells.into_iter().flatten());
        grid
    }

    /// The cell coordinates of `point`, as probe_grid.wgsl computes them.
    fn coordinates(&self, point: Vec3) -> Vec3 {
        ((point - self.origin) * self.scale).floor()
    }

    fn flatten(&self, cell: UVec3) -> usize {
        (cell.x + self.size.x * (cell.y + self.size.y * cell.z)) as usize
    }
}

/// probe_grid.wgsl's twins of `GridCell`'s layout, in words.
#[cfg(test)]
pub(crate) fn constants() -> [crate::shading::layout_tests::Constant; 3] {
    use crate::shading::layout_tests::Constant;
    use std::mem::offset_of;
    let words = |bytes: usize| naga::Literal::U32((bytes / 4) as u32);
    [
        Constant::new("geometry", "PROBE_GRID_CELL_WORDS", words(CELL_WORDS * 4)),
        Constant::new(
            "geometry",
            "PROBE_GRID_CELL_FIRST",
            words(offset_of!(GridCell, first)),
        ),
        Constant::new(
            "geometry",
            "PROBE_GRID_CELL_COUNT",
            words(offset_of!(GridCell, count)),
        ),
    ]
}

/// The world-space bounds of a probe's influence box.
fn world_bounds((world_to_local, influence): &(Mat4, SpecularProbeBox)) -> [Vec3; 2] {
    let to_world = world_to_local.inverse();
    let [lo, hi] = [influence.min, influence.max];
    (0..8)
        .map(|corner| {
            let pick = glam::BVec3::new(corner & 1 != 0, corner & 2 != 0, corner & 4 != 0);
            to_world.transform_point3(Vec3::select(pick, hi, lo))
        })
        .fold([Vec3::INFINITY, Vec3::NEG_INFINITY], |[min, max], p| {
            [min.min(p), max.max(p)]
        })
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::baked_specular_probe::{
        BakedSpecularProbe, SpecularProbeRadiance, SpecularProbeTexels,
    };
    use glam::Quat;
    use wasm_bindgen_test::wasm_bindgen_test;

    /// SplitMix64 from a fixed seed, as uniform values in [0, 1).
    struct Random(u64);
    impl Random {
        fn next(&mut self) -> f32 {
            self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15);
            let mut z = self.0;
            z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
            z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
            ((z ^ (z >> 31)) >> 40) as f32 / (1u64 << 24) as f32
        }
        fn range(&mut self, lo: f32, hi: f32) -> f32 {
            lo + (hi - lo) * self.next()
        }
        fn vec(&mut self, lo: f32, hi: f32) -> Vec3 {
            Vec3::new(self.range(lo, hi), self.range(lo, hi), self.range(lo, hi))
        }
    }

    /// A rigidly rotated and translated influence box far from the origin.
    fn probe(random: &mut Random) -> BakedSpecularProbe {
        let rotation = Quat::from_axis_angle(
            random.vec(-1., 1.).try_normalize().unwrap_or(Vec3::Y),
            random.range(0., std::f32::consts::TAU),
        );
        let center = random.vec(-400., 400.) + Vec3::new(1500., 0., -900.);
        let half = random.vec(0.5, 30.);
        BakedSpecularProbe {
            center,
            world_to_local: Mat4::from_rotation_translation(rotation, center).inverse(),
            influence: SpecularProbeBox {
                min: -half,
                max: half,
            },
            blend: Vec3::ZERO,
            proxy: None,
            radiance: SpecularProbeRadiance {
                face_size: 64,
                texels: SpecularProbeTexels::Rgba16Float(Vec::new()),
            },
        }
    }

    // Defect: a cell omits a probe whose influence box reaches a point in it
    // (a rotated box's bounds, an off-by-one cell range), so walking the cell
    // differs from walking every probe. Independent signal:
    // brute-force containment in each probe's local box, at points inside, on
    // and around the boxes.
    #[wasm_bindgen_test(unsupported = test)]
    fn each_cell_lists_every_probe_that_reaches_it_in_ascending_order() {
        let mut random = Random(0x5eed);
        for collection in 0..8 {
            let probes: Vec<_> = (0..1 + collection * 24)
                .map(|_| probe(&mut random))
                .collect();
            let influences: Vec<_> = probes
                .iter()
                .map(|probe| (probe.world_to_local, probe.influence))
                .collect();
            let grid = ProbeGrid::new(&influences);
            for _ in 0..4000 {
                let owner = &probes[(random.next() * probes.len() as f32) as usize];
                let [lo, hi] = [owner.influence.min, owner.influence.max];
                let mut local = Vec3::new(
                    random.range(lo.x, hi.x),
                    random.range(lo.y, hi.y),
                    random.range(lo.z, hi.z),
                ) * random.range(0.9, 1.1);
                if random.next() < 0.25 {
                    local.x = if random.next() < 0.5 { lo.x } else { hi.x };
                }
                let point = owner.world_to_local.inverse().transform_point3(local);
                let cell = grid.coordinates(point);
                let records: &[GridCell] = bytemuck::cast_slice(
                    &grid.words[..CELL_WORDS * grid.size.element_product() as usize],
                );
                let listed =
                    if cell.cmpge(Vec3::ZERO).all() && cell.cmplt(grid.size.as_vec3()).all() {
                        let GridCell { first, count } = records[grid.flatten(cell.as_uvec3())];
                        &grid.words[first as usize..(first + count) as usize]
                    } else {
                        &[][..]
                    };
                assert!(
                    listed.windows(2).all(|pair| pair[0] < pair[1]),
                    "cell list out of order: {listed:?}"
                );
                for (index, probe) in probes.iter().enumerate() {
                    let p = probe.world_to_local.transform_point3(point);
                    let reaches =
                        p.cmpge(probe.influence.min).all() && p.cmple(probe.influence.max).all();
                    assert!(
                        !reaches || listed.contains(&(index as u32)),
                        "probe {index} reaches {point} but its cell lists {listed:?}"
                    );
                }
            }
        }
    }

    // Defect: the cell count overflows its integer (a panic with overflow
    // checks, else a wrongly sized grid or an endless loop) when a tiny box
    // far from the origin has a margin of thousands of cells, or has an axis
    // (or every axis) with no extent in f32. Independent signal: the grid
    // builds and the box's centre cell lists it.
    #[wasm_bindgen_test(unsupported = test)]
    fn a_tiny_box_far_from_the_origin_builds_a_grid() {
        for (center, half) in [
            // A margin of about 1984 cells per axis.
            (Vec3::new(50_000., 0., 0.), 0.05),
            // No extent on x.
            (Vec3::new(50_000., 0., 0.), 0.0005),
            // No extent on any axis.
            (Vec3::splat(50_000.), 0.0005),
            // Every cell floor underflows to zero.
            (Vec3::ZERO, 1e-42),
        ] {
            let world_to_local = Mat4::from_translation(-center);
            let influence = SpecularProbeBox {
                min: Vec3::splat(-half),
                max: Vec3::splat(half),
            };
            let grid = ProbeGrid::new(&[(world_to_local, influence)]);
            let records: &[GridCell] = bytemuck::cast_slice(
                &grid.words[..CELL_WORDS * grid.size.element_product() as usize],
            );
            let GridCell { first, count } =
                records[grid.flatten(grid.coordinates(center).as_uvec3())];
            assert_eq!(
                &grid.words[first as usize..(first + count) as usize],
                &[0],
                "{center} {half}"
            );
        }
    }

    // Defect: the collection's cell volume overflows f32 once it spans more
    // than about 7e12 on each axis, or its extent and margin overflow when a
    // box is nearly as wide as f32 allows, or a rotated box's world bounds
    // overflow, so the origin or scale is not finite and probe_grid.wgsl's
    // lookup (NaN cells) finds no probe. Independent signal: points inside
    // the box (its centre among the symmetric ones), found as
    // probe_grid.wgsl finds them, land in a cell of the grid that lists it.
    #[wasm_bindgen_test(unsupported = test)]
    fn a_huge_box_is_listed_where_it_reaches() {
        let around_centre = [0.375, 0.5, 0.625];
        for (rotation, center, min, max, fractions) in [
            (Quat::IDENTITY, Vec3::ZERO, -1e13, 1e13, around_centre),
            (
                Quat::IDENTITY,
                Vec3::new(3e12, -1e12, 0.),
                -1e13,
                1e13,
                around_centre,
            ),
            (
                Quat::IDENTITY,
                Vec3::ZERO,
                -f32::MAX / 2.,
                f32::MAX / 2.,
                around_centre,
            ),
            // Its far corner's world x, about 3.5e38, overflows f32.
            (
                Quat::from_rotation_y(std::f32::consts::FRAC_PI_4),
                Vec3::ZERO,
                0.,
                2.5e38,
                [0.0625, 0.125, 0.1875],
            ),
        ] {
            let world_to_local = Mat4::from_rotation_translation(rotation, center).inverse();
            let influence = SpecularProbeBox {
                min: Vec3::splat(min),
                max: Vec3::splat(max),
            };
            let grid = ProbeGrid::new(&[(world_to_local, influence)]);
            assert!(
                grid.origin.is_finite() && grid.scale.is_finite() && grid.scale > 0.,
                "{max}: origin {} scale {}",
                grid.origin,
                grid.scale
            );
            let records: &[GridCell] = bytemuck::cast_slice(
                &grid.words[..CELL_WORDS * grid.size.element_product() as usize],
            );
            for x in fractions {
                for y in fractions {
                    for z in fractions {
                        let local = min + (max - min) * Vec3::new(x, y, z);
                        let point = world_to_local.inverse().transform_point3(local);
                        let cell = grid.coordinates(point);
                        assert!(
                            cell.cmpge(Vec3::ZERO).all() && cell.cmplt(grid.size.as_vec3()).all(),
                            "{max}: {point} is in cell {cell} outside {}",
                            grid.size
                        );
                        let GridCell { first, count } = records[grid.flatten(cell.as_uvec3())];
                        assert_eq!(
                            &grid.words[first as usize..(first + count) as usize],
                            &[0],
                            "{max}: {point}"
                        );
                    }
                }
            }
        }
    }
}