primase_core/shader/
shadow_atlas.rs

1//! A source's local-light shadow atlas, as a mechanism: the layout the source states ([`LocalShadowAtlas`]) and the
2//! placement of the lights a consumer chose to shadow in it ([`LocalShadowAtlas::place`]). Which lights get a shadow
3//! is chosen apart from the atlas, by the options the consumer states ([`super::LocalShadowChoice`]): the atlas places
4//! exactly the lights it is given, in the order given, and refuses, with the reason, what does not fit.
5use serde::Serialize;
6
7use super::{LocalShadow, LocalShadows};
8use crate::Entity;
9use crate::render_graph::{Region, TargetId};
10
11/// One face of a light's shadow: a view from the light's centre along `forward`, `right` and `up` its view's x and y,
12/// in the frame the source's shadowed programs compare positions in ([`LocalShadow::centre`]'s). Unit vectors, at
13/// right angles, with `right x up = forward`: a point `p` of the face's view lies at
14/// `(right . (p - c), up . (p - c), forward . (p - c))` in it.
15#[derive(Clone, Copy, Debug, PartialEq, Serialize)]
16pub struct ShadowFace {
17    pub forward: [f32; 3],
18    pub right: [f32; 3],
19    pub up: [f32; 3],
20}
21
22/// One depth projection term of a light's shadow record ([`LocalShadow::projection`]), of its faces' near plane `n` and
23/// far plane `f` (the light's range).
24#[derive(Clone, Copy, Debug, PartialEq, Serialize)]
25#[serde(rename_all = "snake_case")]
26pub enum ShadowDepthTerm {
27    /// `f / (f - n)`.
28    FarOverDepthRange,
29    /// `-n f / (f - n)`.
30    NegatedNearFarOverDepthRange,
31    /// A value the source's record holds whatever the light.
32    Constant(f32),
33}
34
35/// The device depth a face's projection writes over the depth `z` along its forward axis, between its near plane `n`
36/// and far plane `f`.
37#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
38#[serde(rename_all = "snake_case")]
39pub enum ShadowDepth {
40    /// 1 at the near plane, 0 at the far: `n (f - z) / (z (f - n))`. Casters keep the greater depth.
41    Reversed,
42    /// 0 at the near plane, 1 at the far: `f (z - n) / (z (f - n))`. Casters keep the lesser depth.
43    Standard,
44}
45
46/// The layout of a source's local-light shadow atlas, every value the source's: one depth target, square regions in
47/// the order the source fills them, the faces each shadowed light takes in its record's order, and how a face
48/// projects. A light takes `faces.len()` consecutive regions of `regions`, its first face the first of them.
49#[derive(Clone, Debug, PartialEq, Serialize)]
50pub struct LocalShadowAtlas {
51    /// The depth target the faces are drawn into ([`crate::render_graph::RenderGraph::targets`]).
52    pub target: TargetId,
53    /// The target's width and height in texels.
54    pub size: [u32; 2],
55    /// The side of a region in texels: a face's viewport.
56    pub region: u32,
57    /// How many texels across a region span the face's 90 degrees, centred: the rest is a guard band on each side
58    /// that the face's projection covers past 90 degrees and the shadowed programs never sample.
59    pub covered: u32,
60    /// Each region's top-left texel, in the order the source fills them.
61    pub regions: Vec<[u32; 2]>,
62    /// A light's faces, in the order its record lists them.
63    pub faces: Vec<ShadowFace>,
64    /// A face's near plane over the light's range (its far plane).
65    pub near_over_range: f32,
66    pub depth: ShadowDepth,
67    /// The terms of a light's record ([`LocalShadow::projection`]), in its order.
68    pub projection: Vec<ShadowDepthTerm>,
69    /// The fixed-function state the source draws the casters into the atlas with (its depth test, bias and culling),
70    /// what a consumer that draws them with programs of its own takes.
71    pub caster_state: iridia_interface::RenderState,
72    /// What the source's layout rests on: which of its values were read from the frames and which inferred.
73    pub why: String,
74}
75
76/// A light the consumer chose to shadow: its centre, in the frame the source's shadowed programs compare positions in,
77/// and its range.
78#[derive(Clone, Copy, Debug, PartialEq)]
79pub struct ShadowedLight {
80    pub light: Entity,
81    pub centre: [f32; 3],
82    pub range: f32,
83}
84
85/// One face of a placed light: its region of the atlas and its camera, the view a consumer draws the light's shadow
86/// casters from into that region.
87#[derive(Clone, Debug, PartialEq, Serialize)]
88pub struct ShadowFaceView {
89    pub light: Entity,
90    /// The face's index in [`LocalShadowAtlas::faces`].
91    pub face: u8,
92    pub region: Region,
93    /// World (the frame of [`ShadowedLight::centre`]) to the face's view, rows: `view * [p, 1]`.
94    pub view: [[f32; 4]; 4],
95    /// The face's view to clip, rows: `projection * [v, 1]`, its w the depth along the face's forward axis.
96    pub projection: [[f32; 4]; 4],
97    pub near: f32,
98    pub far: f32,
99}
100
101/// The lights a consumer chose, placed: each one's shadow as its record states it ([`LocalShadows`], for
102/// [`super::LightTable::pack`]), and every face's region and camera, light by light in the order given, each light's
103/// faces in the atlas's order.
104#[derive(Clone, Debug, Default, PartialEq)]
105pub struct ShadowPlacement {
106    pub shadows: LocalShadows,
107    pub faces: Vec<ShadowFaceView>,
108}
109
110fn dot(a: [f32; 3], b: [f32; 3]) -> f32 {
111    a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
112}
113
114fn cross(a: [f32; 3], b: [f32; 3]) -> [f32; 3] {
115    [
116        a[1] * b[2] - a[2] * b[1],
117        a[2] * b[0] - a[0] * b[2],
118        a[0] * b[1] - a[1] * b[0],
119    ]
120}
121
122impl LocalShadowAtlas {
123    /// How many lights the atlas holds: whole sets of faces in its regions.
124    pub fn capacity(&self) -> usize {
125        self.regions.len().checked_div(self.faces.len()).unwrap_or(0)
126    }
127
128    /// The layout is whole: at least one face and one region; every region inside the target and none overlapping
129    /// another; a guard band no wider than the region and as wide on both sides; each face a right-handed set of unit
130    /// vectors at right angles; a near plane inside the range; at least one finite projection term; and a reason.
131    pub fn verify(&self) -> Result<(), String> {
132        let [width, height] = self.size;
133        if width == 0 || height == 0 || self.region == 0 {
134            return Err("a local shadow atlas with an empty target or region".into());
135        }
136        if self.covered == 0 || self.covered > self.region || !(self.region - self.covered).is_multiple_of(2)
137        {
138            return Err(format!(
139                "a local shadow atlas covering {} of a region's {} texels: not a centred span inside it",
140                self.covered, self.region
141            ));
142        }
143        if self.faces.is_empty() || self.faces.len() > usize::from(u8::MAX) {
144            return Err(format!(
145                "a local shadow atlas of {} faces a light",
146                self.faces.len()
147            ));
148        }
149        if self.regions.is_empty() {
150            return Err("a local shadow atlas with no regions".into());
151        }
152        for (i, [x, y]) in self.regions.iter().enumerate() {
153            if x.checked_add(self.region).is_none_or(|r| r > width)
154                || y.checked_add(self.region).is_none_or(|b| b > height)
155            {
156                return Err(format!(
157                    "local shadow region {i} at ({x}, {y}) lies outside the {width} x {height} atlas"
158                ));
159            }
160            for (j, [u, v]) in self.regions[..i].iter().enumerate() {
161                if x.abs_diff(*u) < self.region && y.abs_diff(*v) < self.region {
162                    return Err(format!("local shadow regions {j} and {i} overlap"));
163                }
164            }
165        }
166        for (i, f) in self.faces.iter().enumerate() {
167            let unit = [f.forward, f.right, f.up]
168                .iter()
169                .all(|v| v.iter().all(|x| x.is_finite()) && (dot(*v, *v) - 1.0).abs() <= 1e-5);
170            let square = dot(f.forward, f.right).abs() <= 1e-5
171                && dot(f.forward, f.up).abs() <= 1e-5
172                && dot(f.right, f.up).abs() <= 1e-5;
173            let handed = cross(f.right, f.up)
174                .iter()
175                .zip(f.forward)
176                .all(|(a, b)| (a - b).abs() <= 1e-5);
177            if !(unit && square && handed) {
178                return Err(format!(
179                    "local shadow face {i} is not a right-handed set of unit vectors at right angles"
180                ));
181            }
182        }
183        if !(self.near_over_range > 0.0 && self.near_over_range < 1.0) {
184            return Err(format!(
185                "a local shadow near plane of {} times the range",
186                self.near_over_range
187            ));
188        }
189        if self.projection.is_empty()
190            || self
191                .projection
192                .iter()
193                .any(|t| matches!(t, ShadowDepthTerm::Constant(v) if !v.is_finite()))
194        {
195            return Err("a local shadow record with no projection terms, or one not finite".into());
196        }
197        self.caster_state
198            .verify()
199            .map_err(|e| format!("the local shadow casters' state: {e}"))?;
200        if self.why.trim().is_empty() {
201            return Err("a local shadow atlas layout with no reason".into());
202        }
203        Ok(())
204    }
205
206    /// Place `chosen`, in that order: light `i` takes regions `i * F ..` of [`LocalShadowAtlas::regions`] (`F` faces
207    /// each). Refused, with the reason, where they do not fit (more lights than [`LocalShadowAtlas::capacity`]), where a
208    /// light is given twice, or where its centre is not finite or its range not above 0. A face's view looks from the
209    /// centre along the face's axis; its projection maps the `covered` texels to 90 degrees (the region's
210    /// `region / covered` of the tangent to its edge) with the atlas's [`ShadowDepth`], near plane
211    /// `range * near_over_range` and far plane `range`.
212    pub fn place(&self, chosen: &[ShadowedLight]) -> Result<ShadowPlacement, String> {
213        self.verify()?;
214        if chosen.len() > self.capacity() {
215            return Err(format!(
216                "{} lights chosen for a local shadow atlas that holds {} ({} regions, {} faces a light)",
217                chosen.len(),
218                self.capacity(),
219                self.regions.len(),
220                self.faces.len()
221            ));
222        }
223        let [width, height] = self.size.map(|s| s as f32);
224        let half = self.covered as f32 / 2.0;
225        let scale = self.covered as f32 / self.region as f32;
226        let mut placed = ShadowPlacement::default();
227        for (i, l) in chosen.iter().enumerate() {
228            if chosen[..i].iter().any(|o| o.light == l.light) {
229                return Err(format!(
230                    "light {:?} chosen twice for the local shadow atlas",
231                    l.light
232                ));
233            }
234            if !l.centre.iter().all(|x| x.is_finite()) || !(l.range > 0.0 && l.range.is_finite()) {
235                return Err(format!(
236                    "light {:?}: a shadow centre {:?} and range {}",
237                    l.light, l.centre, l.range
238                ));
239            }
240            let far = l.range;
241            let near = far * self.near_over_range;
242            let depth = far - near;
243            let mut faces = Vec::with_capacity(self.faces.len());
244            for (k, f) in self.faces.iter().enumerate() {
245                let [x, y] = self.regions[i * self.faces.len() + k];
246                let row = |axis: [f32; 3]| [axis[0], axis[1], axis[2], -dot(axis, l.centre)];
247                let (a, b) = match self.depth {
248                    ShadowDepth::Reversed => (-near / depth, near * far / depth),
249                    ShadowDepth::Standard => (far / depth, -near * far / depth),
250                };
251                placed.faces.push(ShadowFaceView {
252                    light: l.light,
253                    face: k as u8,
254                    region: Region {
255                        x,
256                        y,
257                        width: self.region,
258                        height: self.region,
259                    },
260                    view: [row(f.right), row(f.up), row(f.forward), [0.0, 0.0, 0.0, 1.0]],
261                    projection: [
262                        [scale, 0.0, 0.0, 0.0],
263                        [0.0, scale, 0.0, 0.0],
264                        [0.0, 0.0, a, b],
265                        [0.0, 0.0, 1.0, 0.0],
266                    ],
267                    near,
268                    far,
269                });
270                // the face's 90 degrees in atlas coordinates: x right, y down from the region's centre
271                let centre = self.region as f32 / 2.0;
272                faces.push([
273                    half / width,
274                    -half / height,
275                    (x as f32 + centre) / width,
276                    (y as f32 + centre) / height,
277                ]);
278            }
279            let projection = self
280                .projection
281                .iter()
282                .map(|t| match t {
283                    ShadowDepthTerm::FarOverDepthRange => far / depth,
284                    ShadowDepthTerm::NegatedNearFarOverDepthRange => -(near * far) / depth,
285                    ShadowDepthTerm::Constant(v) => *v,
286                })
287                .collect();
288            placed.shadows.0.insert(
289                l.light,
290                LocalShadow {
291                    projection,
292                    centre: [l.centre[0], l.centre[1], l.centre[2], 1.0],
293                    faces,
294                },
295            );
296        }
297        Ok(placed)
298    }
299}
300
301#[cfg(test)]
302mod tests {
303    use super::*;
304
305    /// Six faces along the axes, each `right x up = forward`.
306    fn cube() -> Vec<ShadowFace> {
307        let face = |forward, right, up| ShadowFace { forward, right, up };
308        vec![
309            face([1., 0., 0.], [0., 0., -1.], [0., 1., 0.]),
310            face([-1., 0., 0.], [0., 0., 1.], [0., 1., 0.]),
311            face([0., 1., 0.], [1., 0., 0.], [0., 0., -1.]),
312            face([0., -1., 0.], [1., 0., 0.], [0., 0., 1.]),
313            face([0., 0., 1.], [1., 0., 0.], [0., 1., 0.]),
314            face([0., 0., -1.], [-1., 0., 0.], [0., 1., 0.]),
315        ]
316    }
317
318    fn atlas(regions: Vec<[u32; 2]>) -> LocalShadowAtlas {
319        LocalShadowAtlas {
320            target: 0,
321            size: [512, 512],
322            region: 64,
323            covered: 58,
324            regions,
325            faces: cube(),
326            near_over_range: 0.001,
327            depth: ShadowDepth::Reversed,
328            projection: vec![
329                ShadowDepthTerm::FarOverDepthRange,
330                ShadowDepthTerm::NegatedNearFarOverDepthRange,
331                ShadowDepthTerm::Constant(0.0),
332                ShadowDepthTerm::Constant(1.0),
333            ],
334            caster_state: iridia_interface::RenderState::default(),
335            why: "test".into(),
336        }
337    }
338
339    fn grid() -> Vec<[u32; 2]> {
340        (0..16).map(|i| [(i % 4) * 128, (i / 4) * 128]).collect()
341    }
342
343    fn mul(m: &[[f32; 4]; 4], v: [f32; 4]) -> [f32; 4] {
344        m.map(|r| r.iter().zip(v).map(|(a, b)| a * b).sum())
345    }
346
347    /// A point on each face's axis projects to its region's centre at the depth the record's terms give it, and a
348    /// point 45 degrees off the axis to the edge of the covered span: the record's place of a face and its camera
349    /// agree texel for texel.
350    #[test]
351    fn a_face_camera_and_the_record_place_a_point_alike() {
352        let a = atlas(grid());
353        let light = crate::World::new().spawn();
354        let c = [1.0, 2.0, -3.0];
355        let p = a
356            .place(&[ShadowedLight {
357                light,
358                centre: c,
359                range: 8.0,
360            }])
361            .unwrap();
362        let shadow = &p.shadows.0[&light];
363        assert_eq!(shadow.centre, [1.0, 2.0, -3.0, 1.0]);
364        assert_eq!(p.faces.len(), 6);
365        for (f, face) in p.faces.iter().zip(&a.faces) {
366            for (off, want) in [
367                ([0.0, 0.0], [0.0, 0.0]),
368                ([1.0, 0.0], [1.0, 0.0]),
369                ([0.0, 1.0], [0.0, 1.0]),
370            ] {
371                let z = 4.0;
372                let w: Vec<f32> = (0..3)
373                    .map(|k| c[k] + z * (face.forward[k] + off[0] * face.right[k] + off[1] * face.up[k]))
374                    .collect();
375                let clip = mul(&f.projection, mul(&f.view, [w[0], w[1], w[2], 1.0]));
376                let ndc = [clip[0] / clip[3], clip[1] / clip[3], clip[2] / clip[3]];
377                // the viewport: x right, y down
378                let px = f.region.x as f32 + (ndc[0] + 1.0) / 2.0 * 64.0;
379                let py = f.region.y as f32 + (1.0 - ndc[1]) / 2.0 * 64.0;
380                // what the shadowed program samples: the record's scale and offset of (u, v) / z
381                let [sx, sy, ox, oy] = shadow.faces[f.face as usize];
382                let ux = (ox + sx * want[0]) * 512.0;
383                let uy = (oy + sy * want[1]) * 512.0;
384                assert!(
385                    (px - ux).abs() < 1e-3 && (py - uy).abs() < 1e-3,
386                    "{f:?} {px} {py} {ux} {uy}"
387                );
388                // reversed depth from the record's terms: 1 - A - B / z
389                let record = 1.0 - shadow.projection[0] - shadow.projection[1] / z;
390                assert!((ndc[2] - record).abs() < 1e-6, "{} {record}", ndc[2]);
391            }
392        }
393        assert_eq!(shadow.projection[2..], [0.0, 1.0]);
394    }
395
396    /// Lights take whole sets of faces in the order given; more than fit, a light given twice and a range of 0 are
397    /// refused with the reason.
398    #[test]
399    fn the_atlas_places_what_it_is_given_and_refuses_what_does_not_fit() {
400        let a = atlas(grid());
401        assert_eq!(a.capacity(), 2);
402        let mut w = crate::World::new();
403        let e: Vec<Entity> = (0..4).map(|_| w.spawn()).collect();
404        let l = |i: usize, range| ShadowedLight {
405            light: e[i],
406            centre: [0.0; 3],
407            range,
408        };
409        let p = a.place(&[l(2, 4.0), l(1, 8.0)]).unwrap();
410        assert_eq!(p.faces[6].light, e[1]);
411        assert_eq!([p.faces[6].region.x, p.faces[6].region.y], [256, 128]);
412        assert_eq!(p.faces[0].near, 4.0 * 0.001);
413        let err = a.place(&[l(1, 8.0), l(2, 8.0), l(3, 8.0)]).unwrap_err();
414        assert!(err.contains("holds 2"), "{err}");
415        assert!(a.place(&[l(1, 8.0), l(1, 8.0)]).unwrap_err().contains("twice"));
416        assert!(a.place(&[l(1, 0.0)]).is_err());
417        assert!(a.place(&[]).unwrap().faces.is_empty());
418    }
419
420    /// Regions that overlap or leave the target, a guard band off centre and a face that is not right-handed are
421    /// refused.
422    #[test]
423    fn a_broken_layout_is_refused() {
424        assert!(
425            atlas(vec![[0, 0], [32, 0]])
426                .verify()
427                .unwrap_err()
428                .contains("overlap")
429        );
430        assert!(atlas(vec![[480, 0]]).verify().unwrap_err().contains("outside"));
431        let mut odd = atlas(grid());
432        odd.covered = 57;
433        assert!(odd.verify().is_err());
434        let mut left = atlas(grid());
435        left.faces[0].right = [0.0, 0.0, 1.0];
436        assert!(left.verify().unwrap_err().contains("right-handed"));
437    }
438}
primase_core/shader/shadow_atlas.rs

primase_core/shader/
shadow_atlas.rs
