veloren_voxygen/mesh/
terrain.rs

1#![expect(clippy::clone_on_copy)] // TODO: fix after wgpu branch
2
3use crate::{
4    mesh::{
5        MeshGen,
6        greedy::{self, GreedyConfig, GreedyMesh},
7    },
8    render::{AltIndices, FluidVertex, Mesh, TerrainAtlasData, TerrainVertex, Vertex},
9    scene::terrain::{BlocksOfInterest, DEEP_ALT, SHALLOW_ALT},
10};
11use common::{
12    terrain::{Block, TerrainChunk},
13    util::either_with,
14    vol::{ReadVol, RectRasterableVol},
15    volumes::vol_grid_2d::{CachedVolGrid2d, VolGrid2d},
16};
17use common_base::span;
18use std::{collections::VecDeque, fmt::Debug, sync::Arc};
19use tracing::error;
20use vek::*;
21
22#[derive(Clone, Copy, PartialEq)]
23pub enum FaceKind {
24    /// Opaque face that is facing something non-opaque; either
25    /// water (Opaque(true)) or something else (Opaque(false)).
26    Opaque(bool),
27    /// Fluid face that is facing something non-opaque, non-tangible,
28    /// and non-fluid (most likely air).
29    Fluid,
30}
31
32pub const SUNLIGHT: u8 = 24;
33pub const SUNLIGHT_INV: f32 = 1.0 / SUNLIGHT as f32;
34pub const MAX_LIGHT_DIST: i32 = SUNLIGHT as i32;
35
36fn calc_light<
37    V: RectRasterableVol<Vox = Block> + ReadVol + Debug,
38    L: Iterator<Item = (Vec3<i32>, u8)>,
39>(
40    is_sunlight: bool,
41    // When above bounds
42    default_light: u8,
43    bounds: Aabb<i32>,
44    vol: &VolGrid2d<V>,
45    lit_blocks: L,
46) -> impl Fn(Vec3<i32>) -> f32 + 'static + Send + Sync + use<V, L> {
47    span!(_guard, "calc_light");
48    const UNKNOWN: u8 = 255;
49    const OPAQUE: u8 = 254;
50
51    let outer = Aabb {
52        min: bounds.min - Vec3::new(SUNLIGHT as i32, SUNLIGHT as i32, 1),
53        max: bounds.max + Vec3::new(SUNLIGHT as i32, SUNLIGHT as i32, 1),
54    };
55
56    let mut vol_cached = vol.cached();
57
58    let mut light_map = vec![UNKNOWN; outer.size().product() as usize];
59    let lm_idx = {
60        let (w, h, _) = outer.clone().size().into_tuple();
61        move |x, y, z| (w * h * z + h * x + y) as usize
62    };
63    // Light propagation queue
64    let mut prop_que = lit_blocks
65        .map(|(pos, light)| {
66            let rpos = pos - outer.min;
67            light_map[lm_idx(rpos.x, rpos.y, rpos.z)] = light.min(SUNLIGHT); // Brightest light
68            (rpos.x as u8, rpos.y as u8, rpos.z as u16)
69        })
70        .collect::<VecDeque<_>>();
71    // Start sun rays
72    if is_sunlight {
73        for x in 0..outer.size().w {
74            for y in 0..outer.size().h {
75                let mut light = SUNLIGHT as f32;
76                for z in (0..outer.size().d).rev() {
77                    let (min_light, attenuation) = vol_cached
78                        .get(outer.min + Vec3::new(x, y, z))
79                        .map_or((0, 0.0), |b| b.get_max_sunlight());
80
81                    if light > min_light as f32 {
82                        light = (light - attenuation).max(min_light as f32);
83                    }
84
85                    light_map[lm_idx(x, y, z)] = light.floor() as u8;
86
87                    if light <= 0.0 {
88                        break;
89                    } else {
90                        prop_que.push_back((x as u8, y as u8, z as u16));
91                    }
92                }
93            }
94        }
95    }
96
97    // Determines light propagation
98    let propagate = |src: u8,
99                     dest: &mut u8,
100                     pos: Vec3<i32>,
101                     prop_que: &mut VecDeque<_>,
102                     vol: &mut CachedVolGrid2d<V>| {
103        if *dest != OPAQUE {
104            if *dest == UNKNOWN {
105                if vol.get(outer.min + pos).ok().is_some_and(|b| b.is_fluid()) {
106                    *dest = src.saturating_sub(1);
107                    // Can't propagate further
108                    if *dest > 1 {
109                        prop_que.push_back((pos.x as u8, pos.y as u8, pos.z as u16));
110                    }
111                } else {
112                    *dest = OPAQUE;
113                }
114            } else if *dest < src.saturating_sub(1) {
115                *dest = src - 1;
116                // Can't propagate further
117                if *dest > 1 {
118                    prop_que.push_back((pos.x as u8, pos.y as u8, pos.z as u16));
119                }
120            }
121        }
122    };
123
124    // Propagate light
125    while let Some(pos) = prop_que.pop_front() {
126        let pos = Vec3::new(pos.0 as i32, pos.1 as i32, pos.2 as i32);
127        let light = light_map[lm_idx(pos.x, pos.y, pos.z)];
128
129        // Up
130        // Bounds checking
131        if pos.z + 1 < outer.size().d {
132            propagate(
133                light,
134                light_map.get_mut(lm_idx(pos.x, pos.y, pos.z + 1)).unwrap(),
135                Vec3::new(pos.x, pos.y, pos.z + 1),
136                &mut prop_que,
137                &mut vol_cached,
138            )
139        }
140        // Down
141        if pos.z > 0 {
142            propagate(
143                light,
144                light_map.get_mut(lm_idx(pos.x, pos.y, pos.z - 1)).unwrap(),
145                Vec3::new(pos.x, pos.y, pos.z - 1),
146                &mut prop_que,
147                &mut vol_cached,
148            )
149        }
150        // The XY directions
151        if pos.y + 1 < outer.size().h {
152            propagate(
153                light,
154                light_map.get_mut(lm_idx(pos.x, pos.y + 1, pos.z)).unwrap(),
155                Vec3::new(pos.x, pos.y + 1, pos.z),
156                &mut prop_que,
157                &mut vol_cached,
158            )
159        }
160        if pos.y > 0 {
161            propagate(
162                light,
163                light_map.get_mut(lm_idx(pos.x, pos.y - 1, pos.z)).unwrap(),
164                Vec3::new(pos.x, pos.y - 1, pos.z),
165                &mut prop_que,
166                &mut vol_cached,
167            )
168        }
169        if pos.x + 1 < outer.size().w {
170            propagate(
171                light,
172                light_map.get_mut(lm_idx(pos.x + 1, pos.y, pos.z)).unwrap(),
173                Vec3::new(pos.x + 1, pos.y, pos.z),
174                &mut prop_que,
175                &mut vol_cached,
176            )
177        }
178        if pos.x > 0 {
179            propagate(
180                light,
181                light_map.get_mut(lm_idx(pos.x - 1, pos.y, pos.z)).unwrap(),
182                Vec3::new(pos.x - 1, pos.y, pos.z),
183                &mut prop_que,
184                &mut vol_cached,
185            )
186        }
187    }
188
189    let min_bounds = Aabb {
190        min: bounds.min - 1,
191        max: bounds.max + 1,
192    };
193
194    // Minimise light map to reduce duplication. We can now discard light info
195    // for blocks outside of the chunk borders.
196    let mut light_map2 = vec![UNKNOWN; min_bounds.size().product() as usize];
197    let lm_idx2 = {
198        let (w, h, _) = min_bounds.clone().size().into_tuple();
199        move |x, y, z| (w * h * z + h * x + y) as usize
200    };
201    for x in 0..min_bounds.size().w {
202        for y in 0..min_bounds.size().h {
203            for z in 0..min_bounds.size().d {
204                let off = min_bounds.min - outer.min;
205                light_map2[lm_idx2(x, y, z)] = light_map[lm_idx(x + off.x, y + off.y, z + off.z)];
206            }
207        }
208    }
209
210    drop(light_map);
211
212    move |wpos| {
213        let pos = wpos - min_bounds.min;
214        let l = light_map2
215            .get(lm_idx2(pos.x, pos.y, pos.z))
216            .copied()
217            .unwrap_or(default_light);
218
219        if l != OPAQUE && l != UNKNOWN {
220            l as f32 * SUNLIGHT_INV
221        } else {
222            0.0
223        }
224    }
225}
226
227#[expect(clippy::type_complexity)]
228pub fn generate_mesh<'a>(
229    vol: &'a VolGrid2d<TerrainChunk>,
230    (range, max_texture_size, _boi): (Aabb<i32>, Vec2<u16>, &'a BlocksOfInterest),
231) -> MeshGen<
232    TerrainVertex,
233    FluidVertex,
234    TerrainVertex,
235    (
236        Aabb<f32>,
237        TerrainAtlasData,
238        Vec2<u16>,
239        Arc<dyn Fn(Vec3<i32>) -> f32 + Send + Sync>,
240        Arc<dyn Fn(Vec3<i32>) -> f32 + Send + Sync>,
241        AltIndices,
242        (f32, f32),
243    ),
244> {
245    span!(
246        _guard,
247        "generate_mesh",
248        "<&VolGrid2d as Meshable<_, _>>::generate_mesh"
249    );
250
251    // Find blocks that should glow
252    // TODO: Search neighbouring chunks too!
253    // let glow_blocks = boi.lights
254    //     .iter()
255    //     .map(|(pos, glow)| (*pos + range.min.xy(), *glow));
256    /*  DefaultVolIterator::new(vol, range.min - MAX_LIGHT_DIST, range.max + MAX_LIGHT_DIST)
257    .filter_map(|(pos, block)| block.get_glow().map(|glow| (pos, glow))); */
258
259    let mut glow_blocks = Vec::new();
260
261    // TODO: This expensive, use BlocksOfInterest instead
262    let mut volume = vol.cached();
263    for x in -MAX_LIGHT_DIST..range.size().w + MAX_LIGHT_DIST {
264        for y in -MAX_LIGHT_DIST..range.size().h + MAX_LIGHT_DIST {
265            for z in -1..range.size().d + 1 {
266                let wpos = range.min + Vec3::new(x, y, z);
267                volume
268                    .get(wpos)
269                    .ok()
270                    .and_then(|b| b.get_glow())
271                    .map(|glow| glow_blocks.push((wpos, glow)));
272            }
273        }
274    }
275
276    // Calculate chunk lighting (sunlight defaults to 1.0, glow to 0.0)
277    let light = calc_light(true, SUNLIGHT, range, vol, core::iter::empty());
278    let glow = calc_light(false, 0, range, vol, glow_blocks.into_iter());
279
280    let (underground_alt, deep_alt) = vol
281        .get_key(vol.pos_key((range.min + range.max) / 2))
282        .map_or((0.0, 0.0), |c| {
283            (c.meta().alt() - SHALLOW_ALT, c.meta().alt() - DEEP_ALT)
284        });
285
286    let mut opaque_limits = None::<Limits>;
287    let mut fluid_limits = None::<Limits>;
288    let mut air_limits = None::<Limits>;
289    let flat_get = {
290        span!(_guard, "copy to flat array");
291        let (w, h, d) = range.size().into_tuple();
292        // z can range from -1..range.size().d + 1
293        let d = d + 2;
294        let flat = {
295            let mut volume = vol.cached();
296            const AIR: Block = Block::empty();
297            // TODO: Once we can manage it sensibly, consider using something like
298            // Option<Block> instead of just assuming air.
299            let mut flat = vec![AIR; (w * h * d) as usize];
300            let mut i = 0;
301            for x in 0..range.size().w {
302                for y in 0..range.size().h {
303                    for z in -1..range.size().d + 1 {
304                        let wpos = range.min + Vec3::new(x, y, z);
305                        let block = volume
306                            .get(wpos)
307                            .copied()
308                            // TODO: Replace with None or some other more reasonable value,
309                            // since it's not clear this will work properly with liquid.
310                            .unwrap_or(AIR);
311                        if block.is_opaque() {
312                            opaque_limits = opaque_limits
313                                .map(|l| l.including(z))
314                                .or_else(|| Some(Limits::from_value(z)));
315                        } else if block.is_liquid() {
316                            fluid_limits = fluid_limits
317                                .map(|l| l.including(z))
318                                .or_else(|| Some(Limits::from_value(z)));
319                        } else {
320                            // Assume air
321                            air_limits = air_limits
322                                .map(|l| l.including(z))
323                                .or_else(|| Some(Limits::from_value(z)));
324                        };
325                        flat[i] = block;
326                        i += 1;
327                    }
328                }
329            }
330            flat
331        };
332
333        move |Vec3 { x, y, z }| {
334            // z can range from -1..range.size().d + 1
335            let z = z + 1;
336            match flat.get((x * h * d + y * d + z) as usize).copied() {
337                Some(b) => b,
338                None => panic!("x {} y {} z {} d {} h {}", x, y, z, d, h),
339            }
340        }
341    };
342
343    // Constrain iterated area
344    let (z_start, z_end) = match (air_limits, fluid_limits, opaque_limits) {
345        (Some(air), Some(fluid), Some(opaque)) => air.three_way_intersection(fluid, opaque),
346        (Some(air), Some(fluid), None) => air.intersection(fluid),
347        (Some(air), None, Some(opaque)) => air.intersection(opaque),
348        (None, Some(fluid), Some(opaque)) => fluid.intersection(opaque),
349        // No interfaces (Note: if there are multiple fluid types this could change)
350        (Some(_), None, None) | (None, Some(_), None) | (None, None, Some(_)) => None,
351        (None, None, None) => {
352            error!("Impossible unless given an input AABB that has a height of zero");
353            None
354        },
355    }
356    .map_or((0, 0), |limits| {
357        let (start, end) = limits.into_tuple();
358        let start = start.max(0);
359        let end = end.clamp(start, range.size().d - 1);
360        (start, end)
361    });
362
363    let max_size = max_texture_size;
364    assert!(z_end >= z_start);
365    let greedy_size = Vec3::new(range.size().w - 2, range.size().h - 2, z_end - z_start + 1);
366    // NOTE: Terrain sizes are limited to 32 x 32 x 16384 (to fit in 24 bits: 5 + 5
367    // + 14). FIXME: Make this function fallible, since the terrain
368    // information might be dynamically generated which would make this hard
369    // to enforce.
370    assert!(greedy_size.x <= 32 && greedy_size.y <= 32 && greedy_size.z <= 16384);
371    // NOTE: Cast is safe by prior assertion on greedy_size; it fits into a u16,
372    // which always fits into a f32.
373    let max_bounds: Vec3<f32> = greedy_size.as_::<f32>();
374    // NOTE: Cast is safe by prior assertion on greedy_size; it fits into a u16,
375    // which always fits into a usize.
376    let greedy_size = greedy_size.as_::<usize>();
377    let greedy_size_cross = Vec3::new(greedy_size.x - 1, greedy_size.y - 1, greedy_size.z);
378    let draw_delta = Vec3::new(1, 1, z_start);
379
380    let get_light = |_: &mut (), pos: Vec3<i32>| {
381        if flat_get(pos).is_opaque() {
382            0.0
383        } else {
384            light(pos + range.min)
385        }
386    };
387    let get_ao = |_: &mut (), pos: Vec3<i32>| {
388        if flat_get(pos).is_opaque() { 0.0 } else { 1.0 }
389    };
390    let get_glow = |_: &mut (), pos: Vec3<i32>| glow(pos + range.min);
391    let get_color =
392        |_: &mut (), pos: Vec3<i32>| flat_get(pos).get_color().unwrap_or_else(Rgb::zero);
393    let get_kind = |_: &mut (), pos: Vec3<i32>| flat_get(pos).kind() as u8;
394    let get_opacity = |_: &mut (), pos: Vec3<i32>| !flat_get(pos).is_opaque();
395    let should_draw = |_: &mut (), pos: Vec3<i32>, delta: Vec3<i32>, _uv| {
396        should_draw_greedy(pos, delta, &flat_get)
397    };
398    // NOTE: Conversion to f32 is fine since this i32 is actually in bounds for u16.
399    let mesh_delta = Vec3::new(0.0, 0.0, (z_start + range.min.z) as f32);
400    let create_opaque =
401        |atlas_pos, pos, norm, meta| TerrainVertex::new(atlas_pos, pos + mesh_delta, norm, meta);
402    let create_transparent = |_atlas_pos, pos: Vec3<f32>, norm| {
403        // TODO: It *should* be possible to pull most of this code out of this function
404        // and compute it per-chunk. For some reason, this doesn't work! If you,
405        // dear reader, feel like giving it a go then feel free. For now
406        // it's been kept as-is because I'm lazy and water vertices aren't nearly common
407        // enough for this to matter much. If you want to test whether your
408        // change works, look carefully at how waves interact between water
409        // polygons in different chunks. If the join is smooth, you've solved the
410        // problem!
411        let key = vol.pos_key(range.min + pos.as_());
412        let v00 = vol
413            .get_key(key + Vec2::new(0, 0))
414            .map_or(Vec3::zero(), |c| c.meta().river_velocity());
415        let v10 = vol
416            .get_key(key + Vec2::new(1, 0))
417            .map_or(Vec3::zero(), |c| c.meta().river_velocity());
418        let v01 = vol
419            .get_key(key + Vec2::new(0, 1))
420            .map_or(Vec3::zero(), |c| c.meta().river_velocity());
421        let v11 = vol
422            .get_key(key + Vec2::new(1, 1))
423            .map_or(Vec3::zero(), |c| c.meta().river_velocity());
424        let factor =
425            (range.min + pos.as_()).map(|e| e as f32) / TerrainChunk::RECT_SIZE.map(|e| e as f32);
426        let vel = Lerp::lerp(
427            Lerp::lerp(v00, v10, factor.x.rem_euclid(1.0)),
428            Lerp::lerp(v01, v11, factor.x.rem_euclid(1.0)),
429            factor.y.rem_euclid(1.0),
430        );
431        FluidVertex::new(pos + mesh_delta, norm, vel.xy())
432    };
433
434    let mut greedy = GreedyMesh::<TerrainAtlasData, guillotiere::SimpleAtlasAllocator>::new(
435        max_size,
436        greedy::general_config(),
437    );
438    let mut opaque_deep = Vec::new();
439    let mut opaque_shallow = Vec::new();
440    let mut opaque_surface = Vec::new();
441    let mut fluid_mesh = Mesh::new();
442    greedy.push(GreedyConfig {
443        data: (),
444        draw_delta,
445        greedy_size,
446        greedy_size_cross,
447        get_ao,
448        get_light,
449        get_glow,
450        get_opacity,
451        should_draw,
452        push_quad: |atlas_origin, dim, origin, draw_dim, norm, meta: &FaceKind| match meta {
453            FaceKind::Opaque(meta) => {
454                let mut max_z = None;
455                let mut min_z = None;
456                let quad = greedy::create_quad(
457                    atlas_origin,
458                    dim,
459                    origin,
460                    draw_dim,
461                    norm,
462                    meta,
463                    |atlas_pos, pos, norm, &meta| {
464                        max_z = Some(max_z.map_or(pos.z, |z: f32| z.max(pos.z)));
465                        min_z = Some(min_z.map_or(pos.z, |z: f32| z.min(pos.z)));
466                        create_opaque(atlas_pos, pos, norm, meta)
467                    },
468                );
469                let max_alt = mesh_delta.z + max_z.expect("quad had no vertices?");
470                let min_alt = mesh_delta.z + min_z.expect("quad had no vertices?");
471
472                if max_alt < deep_alt {
473                    opaque_deep.push(quad);
474                } else if min_alt > underground_alt {
475                    opaque_surface.push(quad);
476                } else {
477                    opaque_shallow.push(quad);
478                }
479            },
480            FaceKind::Fluid => {
481                fluid_mesh.push_quad(greedy::create_quad(
482                    atlas_origin,
483                    dim,
484                    origin,
485                    draw_dim,
486                    norm,
487                    &(),
488                    |atlas_pos, pos, norm, &_meta| create_transparent(atlas_pos, pos, norm),
489                ));
490            },
491        },
492        make_face_texel: |(col_light, kind): (&mut [u8; 4], &mut u8),
493                          data: &mut (),
494                          pos,
495                          light,
496                          glow,
497                          ao| {
498            *col_light = TerrainVertex::make_col_light(light, glow, get_color(data, pos), ao);
499            *kind = get_kind(data, pos);
500        },
501    });
502
503    let min_bounds = mesh_delta;
504    let bounds = Aabb {
505        min: min_bounds,
506        max: max_bounds + min_bounds,
507    };
508    let (atlas_data, atlas_size) = greedy.finalize();
509
510    let deep_end = opaque_deep.len()
511        * if TerrainVertex::QUADS_INDEX.is_some() {
512            4
513        } else {
514            6
515        };
516    let alt_indices = AltIndices {
517        deep_end,
518        underground_end: deep_end
519            + opaque_shallow.len()
520                * if TerrainVertex::QUADS_INDEX.is_some() {
521                    4
522                } else {
523                    6
524                },
525    };
526    let sun_occluder_z_bounds = (underground_alt.max(bounds.min.z), bounds.max.z);
527
528    (
529        opaque_deep
530            .into_iter()
531            .chain(opaque_shallow)
532            .chain(opaque_surface)
533            .collect(),
534        fluid_mesh,
535        Mesh::new(),
536        (
537            bounds,
538            atlas_data,
539            atlas_size,
540            Arc::new(light),
541            Arc::new(glow),
542            alt_indices,
543            sun_occluder_z_bounds,
544        ),
545    )
546}
547
548/// NOTE: Make sure to reflect any changes to how meshing is performanced in
549/// [scene::terrain::Terrain::skip_remesh].
550pub fn should_draw_greedy(
551    pos: Vec3<i32>,
552    delta: Vec3<i32>,
553    flat_get: impl Fn(Vec3<i32>) -> Block,
554) -> Option<(bool, FaceKind)> {
555    let from = flat_get(pos - delta);
556    let to = flat_get(pos);
557    // Don't use `is_opaque`, because it actually refers to light transmission
558    let from_filled = from.is_filled();
559    if from_filled == to.is_filled() {
560        // Check the interface of liquid and non-tangible non-liquid (e.g. air).
561        let from_liquid = from.is_liquid();
562        if from_liquid == to.is_liquid() || from.is_filled() || to.is_filled() {
563            None
564        } else {
565            // While liquid is not culled, we still try to keep a consistent orientation as
566            // we do for land; if going from liquid to non-liquid,
567            // forwards-facing; otherwise, backwards-facing.
568            Some((from_liquid, FaceKind::Fluid))
569        }
570    } else {
571        // If going from unfilled to filled, backward facing; otherwise, forward
572        // facing.  Also, if either from or to is fluid, set the meta accordingly.
573        Some((
574            from_filled,
575            FaceKind::Opaque(if from_filled {
576                to.is_liquid()
577            } else {
578                from.is_liquid()
579            }),
580        ))
581    }
582}
583
584/// 1D Aabr
585#[derive(Copy, Clone, Debug)]
586struct Limits {
587    min: i32,
588    max: i32,
589}
590
591impl Limits {
592    fn from_value(v: i32) -> Self { Self { min: v, max: v } }
593
594    fn including(mut self, v: i32) -> Self {
595        if v < self.min {
596            self.min = v
597        } else if v > self.max {
598            self.max = v
599        }
600        self
601    }
602
603    fn union(self, other: Self) -> Self {
604        Self {
605            min: self.min.min(other.min),
606            max: self.max.max(other.max),
607        }
608    }
609
610    // Find limits that include the overlap of the two
611    fn intersection(self, other: Self) -> Option<Self> {
612        // Expands intersection by 1 since that fits our use-case
613        // (we need to get blocks on either side of the interface)
614        let min = self.min.max(other.min) - 1;
615        let max = self.max.min(other.max) + 1;
616
617        (min < max).then_some(Self { min, max })
618    }
619
620    // Find limits that include any areas of overlap between two of the three
621    fn three_way_intersection(self, two: Self, three: Self) -> Option<Self> {
622        let intersection = self.intersection(two);
623        let intersection = either_with(self.intersection(three), intersection, Limits::union);
624        either_with(two.intersection(three), intersection, Limits::union)
625    }
626
627    fn into_tuple(self) -> (i32, i32) { (self.min, self.max) }
628}