veloren_voxygen/mesh/
greedy.rs

1use crate::render::{Vertex, mesh::Quad, pipelines::AtlasData};
2use common_base::{prof_span, span};
3use vek::*;
4
5type TodoRect = (
6    Vec3<i32>,
7    Vec2<Vec3<u16>>,
8    guillotiere::Rectangle,
9    Vec3<i32>,
10);
11
12pub struct GreedyConfig<D, FA, FL, FG, FO, FS, FP, FT> {
13    pub data: D,
14    /// The minimum position to mesh, in the coordinate system used
15    /// for queries against the volume.
16    pub draw_delta: Vec3<i32>,
17    /// For each dimension i, for faces drawn in planes *parallel* to i,
18    /// represents the number of voxels considered along dimension i in those
19    /// planes, starting from `draw_delta`.
20    pub greedy_size: Vec3<usize>,
21    /// For each dimension i, represents the number of planes considered
22    /// *orthogonal* to dimension i, starting from `draw_delta`.  This should
23    /// usually be the same as greedy_size.
24    ///
25    /// An important exception is during chunk rendering (where vertical faces
26    /// at chunk boundaries would otherwise be rendered twice, and also
27    /// force us to use more than 5 bits to represent x and y
28    /// positions--though there may be a clever way around the latter).
29    /// Thus, for chunk rendering we set the number of *vertical* planes to
30    /// one less than the chunk size along the x and y dimensions, but keep
31    /// the number of *horizontal* planes large enough to cover the whole
32    /// chunk.
33    pub greedy_size_cross: Vec3<usize>,
34    /// Given a position, return the AO information for the voxel at that
35    /// position (0.0 - 1.0).
36    pub get_ao: FA,
37    /// Given a position, return the lighting information for the voxel at that
38    /// position.
39    pub get_light: FL,
40    /// Given a position, return the glow information for the voxel at that
41    /// position (i.e: additional non-sun light).
42    pub get_glow: FG,
43    /// Given a position, return the opacity information for the voxel at that
44    /// position. Currently, we don't support real translucent lighting, so the
45    /// value should either be `false` (for opaque blocks) or `true`
46    /// (otherwise).
47    pub get_opacity: FO,
48    /// Given a position and a normal, should we draw the face between the
49    /// position and position - normal (i.e. the voxel "below" this vertex)?
50    /// If so, provide its orientation, together with any other meta
51    /// information required for the mesh that needs to split up faces.  For
52    /// example, terrain faces currently record a bit indicating whether
53    /// they are exposed to water or not, so we should not merge faces where
54    /// one is submerged in water and the other is not, even if they
55    /// otherwise have the same orientation, dimensions, and are
56    /// next to each other.
57    pub should_draw: FS,
58    /// Create an opaque quad (used for only display rendering) from its
59    /// top-left atlas position, the rectangle's dimensions in (2D) atlas
60    /// space, a world position, the u and v axes of the rectangle in (3D)
61    /// world space, the normal facing out frmo the rectangle in world
62    /// space, and meta information common to every voxel in this rectangle.
63    pub push_quad: FP,
64    /// Given a position and the lighting information for a face at that
65    /// position, return the texel for the face at that position.
66    pub make_face_texel: FT,
67}
68
69/// A suspended greedy mesh, with enough information to recover color data.
70///
71/// The reason this exists is that greedy meshing is split into two parts.
72/// First, the meshing itself needs to be performed; secondly, we generate a
73/// texture atlas.  We do things in this order to avoid having to copy all the
74/// old vertices to the correct location.  However, when trying to use the same
75/// texture atlas for more than one model, this approach runs into the
76/// problem that enough model information needs to be remembered to be able to
77/// generate the colors after the function returns, so we box up the actual
78/// coloring part as a continuation.  When called with a final tile size and
79/// vector, the continuation will consume the color data and write it to the
80/// vector.
81pub type SuspendedMesh<'a, A> = dyn for<'r> FnOnce(&'r mut A, Vec2<u16>) + 'a;
82
83/// Abstraction over different atlas allocators. Useful to swap out the
84/// allocator implementation for specific cases (e.g. sprites).
85pub trait AtlasAllocator {
86    type Config;
87
88    /// Creates a new instance of this atlas allocator taking into account the
89    /// provided max size;
90    fn with_max_size(max_size: Vec2<u16>, config: Self::Config) -> Self;
91
92    /// Allocates a rectangle of the given size.
93    // TODO: don't use guillotiere type here
94    fn allocate(&mut self, size: Vec2<u16>) -> Option<guillotiere::Rectangle>;
95
96    /// Retrieves the current size of the atlas being allocated from.
97    fn size(&self) -> Vec2<u16>;
98
99    /// Grows the size of the atlas to the provided size.
100    fn grow(&mut self, new_size: Vec2<u16>);
101}
102
103fn guillotiere_size<T: Into<i32>>(size: Vec2<T>) -> guillotiere::Size {
104    guillotiere::Size::new(size.x.into(), size.y.into())
105}
106
107/// Currently used by terrain/particles/figures
108pub fn general_config() -> guillotiere::AllocatorOptions {
109    // TODO: Collect information to see if we can choose a good value here. These
110    // current values were optimized for sprites, but we are using a
111    // different allocator for them so different values might be better
112    // here.
113    let large_size_threshold = 8; //256.min(min_max_dim / 2 + 1);
114    let small_size_threshold = 3; //33.min(large_size_threshold / 2 + 1);
115
116    guillotiere::AllocatorOptions {
117        alignment: guillotiere::Size::new(1, 1),
118        small_size_threshold,
119        large_size_threshold,
120    }
121}
122
123pub fn sprite_config() -> guillotiere::AllocatorOptions {
124    // TODO: Collect information to see if we can choose a better value here (these
125    // values were picked before switching to this tiled implementation). I
126    // suspect these are still near optimal though.
127    let large_size_threshold = 8;
128    let small_size_threshold = 3;
129
130    guillotiere::AllocatorOptions {
131        alignment: guillotiere::Size::new(1, 1),
132        small_size_threshold,
133        large_size_threshold,
134    }
135}
136
137impl AtlasAllocator for guillotiere::SimpleAtlasAllocator {
138    type Config = guillotiere::AllocatorOptions;
139
140    fn with_max_size(max_size: Vec2<u16>, config: Self::Config) -> Self {
141        let size = guillotiere_size(Vec2::new(32, 32)).min(guillotiere_size(max_size));
142        guillotiere::SimpleAtlasAllocator::with_options(size, &config)
143    }
144
145    /// Allocates a rectangle of the given size.
146    fn allocate(&mut self, size: Vec2<u16>) -> Option<guillotiere::Rectangle> {
147        self.allocate(guillotiere_size(size))
148    }
149
150    /// Retrieves the current size of the atlas being allocated from.
151    fn size(&self) -> Vec2<u16> {
152        // NOTE: with_max_size / grow take a u16 so the size will never be larger than
153        // u16::MAX
154        Vec2::<i32>::from(self.size().to_array()).map(|e| e as u16)
155    }
156
157    /// Grows the size of the atlas to the provided size.
158    fn grow(&mut self, new_size: Vec2<u16>) { self.grow(guillotiere_size(new_size)) }
159}
160
161pub struct GuillotiereTiled {
162    options: guillotiere::AllocatorOptions,
163    // Each tile is Self::TILE_SIZE (unless max size is not aligned to this, in which case the
164    // tiles that reach the max size are truncated below this value).
165    allocator: guillotiere::SimpleAtlasAllocator,
166    // offset in tiles
167    free_tiles: Vec<Vec2<usize>>,
168    // Total width and height in tiles (in case this isn't a square).
169    // Not zero
170    size: Vec2<usize>,
171    // Offset (in tiles) of current tile being allocated from (others returned `None` on last
172    // allocation attempt)
173    current: Option<Vec2<usize>>,
174    // Efficiency history for filled tiles (total area, used area)
175    //
176    // This is useful to examine packing efficiency.
177    history: Vec<(u32, u32)>,
178    used_in_current_tile: u32,
179}
180
181impl GuillotiereTiled {
182    // We can potentially further optimize packing by deferring the allocations
183    // until all rectangles are available for packing. We could also cache this
184    // for sprites if we get to the point of having the rest of start up times
185    // fast enough for this to be helpful (e.g. for iterative work).
186    //
187    // Tested with sprites:
188    // 64 1.63s 1.109 packing
189    // 128 1.65s 1.083 packing
190    // 256 1.77s 1.070 packing
191    // 512 2.27s 1.055 packing
192    // 1024 5.32s 1.045 packing
193    // 2048 10.49s n/a packing (didn't fill up)
194    const TILE_SIZE: u16 = 512;
195
196    fn next_tile(&mut self) {
197        if self.current.is_some() {
198            prof_span!("stats");
199            let size = self.allocator.size();
200            // NOTE: TILE_SIZE is small enough that this won't overflow.
201            let area = size.width as u32 * size.height as u32;
202            let used = self.used_in_current_tile;
203            self.history.push((area, used));
204        }
205
206        self.current = if let Some(offset) = self.free_tiles.pop() {
207            self.allocator.reset(
208                guillotiere_size(Vec2::broadcast(Self::TILE_SIZE)),
209                &self.options,
210            );
211            self.used_in_current_tile = 0;
212            Some(offset)
213        } else {
214            None
215        };
216    }
217}
218
219impl AtlasAllocator for GuillotiereTiled {
220    type Config = guillotiere::AllocatorOptions;
221
222    fn with_max_size(max_size: Vec2<u16>, config: Self::Config) -> Self {
223        let size =
224            guillotiere_size(Vec2::broadcast(Self::TILE_SIZE)).min(guillotiere_size(max_size));
225
226        let allocator = guillotiere::SimpleAtlasAllocator::with_options(size, &config);
227
228        Self {
229            options: config,
230            allocator,
231            free_tiles: Vec::new(),
232            size: Vec2::new(1, 1),
233            current: Some(Vec2::new(0, 0)),
234            history: Vec::new(),
235            used_in_current_tile: 0,
236        }
237    }
238
239    /// Allocates a rectangle of the given size.
240    fn allocate(&mut self, size: Vec2<u16>) -> Option<guillotiere::Rectangle> {
241        let size = guillotiere_size(size);
242
243        while let Some(current) = self.current {
244            match self.allocator.allocate(size) {
245                Some(r) => {
246                    // NOTE: The offset will always be smaller or equal to the `u16`s passed into
247                    // `with_max_size`/`grow` so this won't overflow.
248                    let offset = guillotiere_size(current.map(|e| e as u16 * Self::TILE_SIZE));
249
250                    let offset_rect = guillotiere::Rectangle {
251                        min: r.min.add_size(&offset),
252                        max: r.max.add_size(&offset),
253                    };
254                    // NOTE: `i32` -> `u32` conversion is fine since these will always be positive.
255                    self.used_in_current_tile += size.width as u32 * size.height as u32;
256
257                    return Some(offset_rect);
258                },
259                None => self.next_tile(),
260            }
261        }
262
263        None
264    }
265
266    /// Retrieves the current size of the atlas being allocated from.
267    fn size(&self) -> Vec2<u16> {
268        // NOTE: The size will always be smaller or equal to the `u16`s passed into
269        // `with_max_size`/`grow` so this won't overflow.
270        self.size.map(|e| e as u16 * Self::TILE_SIZE)
271    }
272
273    /// Grows the size of the atlas to the provided size.
274    fn grow(&mut self, new_size: Vec2<u16>) {
275        if tracing::enabled!(tracing::Level::TRACE) {
276            tracing::trace!(
277                "Tile count: {}",
278                self.history.len() + self.free_tiles.len() + self.current.is_some() as usize
279            );
280            let mut total_area = 0;
281            let mut total_used = 0;
282            for (area, used) in self.history.iter() {
283                total_area += area;
284                total_used += used;
285            }
286            tracing::trace!("Packing ratio: {}", total_area as f32 / total_used as f32);
287        }
288
289        let diff = new_size.map2(self.size(), |n, s| n.saturating_sub(s));
290        // NOTE: Growing only occurs in increments of TILE_SIZE so any remaining size is
291        // ignored. Max size is not known here so this must truncate instead of rounding
292        // up.
293        let diff_tiles = diff.map(|e| usize::from(e) / usize::from(Self::TILE_SIZE));
294        let old_size = self.size;
295        self.size += diff_tiles;
296
297        // Add new tiles to free tile list
298        for x in old_size.x..self.size.x {
299            for y in 0..old_size.y {
300                self.free_tiles.push(Vec2::new(x, y));
301            }
302        }
303        for y in old_size.y..self.size.y {
304            for x in 0..self.size.x {
305                self.free_tiles.push(Vec2::new(x, y));
306            }
307        }
308        if self.current.is_none() {
309            self.next_tile();
310        }
311    }
312}
313
314pub type SpriteAtlasAllocator = GuillotiereTiled;
315
316/// Shared state for a greedy mesh, potentially passed along to multiple models.
317///
318/// For an explanation of why we want this, see `SuspendedMesh`.
319pub struct GreedyMesh<
320    'a,
321    A: AtlasData,
322    Allocator: AtlasAllocator = guillotiere::SimpleAtlasAllocator,
323> {
324    //atlas: guillotiere::SimpleAtlasAllocator,
325    atlas: Allocator,
326    tex_size: Vec2<u16>,
327    max_size: Vec2<u16>,
328    suspended: Vec<Box<SuspendedMesh<'a, A>>>,
329}
330
331impl<'a, A: AtlasData, Allocator: AtlasAllocator> GreedyMesh<'a, A, Allocator> {
332    /// Construct a new greedy mesher.
333    ///
334    /// Takes as input the maximum allowable size of the texture atlas used to
335    /// store the light/color data for this mesh.
336    ///
337    /// NOTE: It is an error to pass any size > u16::MAX (this is now enforced
338    /// by the type being `u16`).
339    ///
340    /// Even aside from the above limitation, this will not necessarily always
341    /// be the same as the maximum atlas size supported by the hardware.
342    /// For instance, since we want to reserve 4 bits for a bone index for
343    /// figures in their shadow vertex, the atlas parameter for figures has
344    /// to have at least 2 bits of the normal; thus, it can only take up at
345    /// most 30 bits total, meaning we are restricted to "only" at most 2^15
346    /// × 2^15 atlases even if the hardware supports larger ones.
347    pub fn new(max_size: Vec2<u16>, config: Allocator::Config) -> Self {
348        span!(_guard, "new", "GreedyMesh::new");
349        let min_max_dim = max_size.reduce_min();
350        assert!(
351            min_max_dim >= 4,
352            "min_max_dim={:?} >= 4 ({:?}",
353            min_max_dim,
354            max_size
355        );
356        let atlas = Allocator::with_max_size(max_size, config);
357        let tex_size = Vec2::new(1, 1);
358        Self {
359            atlas,
360            tex_size,
361            max_size,
362            suspended: Vec::new(),
363        }
364    }
365
366    /// Perform greedy meshing on a model, separately producing "pure" model
367    /// data (the opaque mesh, together with atlas positions connecting
368    /// each rectangle with texture information), and raw light and color
369    /// data ready to be used as a texture (accessible with `finalize`).
370    /// Texture data built up within the same greedy mesh will be inserted
371    /// into the same atlas, which can be used to group texture data for
372    /// things like figures that are the result of meshing multiple models.
373    ///
374    /// Returns an estimate of the bounds of the current meshed model.
375    ///
376    /// For more information on the config parameter, see [GreedyConfig].
377    pub fn push<M: PartialEq, D: 'a, FA, FL, FG, FO, FS, FP, FT>(
378        &mut self,
379        config: GreedyConfig<D, FA, FL, FG, FO, FS, FP, FT>,
380    ) where
381        FA: for<'r> FnMut(&'r mut D, Vec3<i32>) -> f32 + 'a,
382        FL: for<'r> FnMut(&'r mut D, Vec3<i32>) -> f32 + 'a,
383        FG: for<'r> FnMut(&'r mut D, Vec3<i32>) -> f32 + 'a,
384        FO: for<'r> FnMut(&'r mut D, Vec3<i32>) -> bool + 'a,
385        FS: for<'r> FnMut(&'r mut D, Vec3<i32>, Vec3<i32>, Vec2<Vec3<i32>>) -> Option<(bool, M)>,
386        FP: FnMut(Vec2<u16>, Vec2<Vec2<u16>>, Vec3<f32>, Vec2<Vec3<f32>>, Vec3<f32>, &M),
387        FT: for<'r> FnMut(<A::SliceMut<'_> as Iterator>::Item, &'r mut D, Vec3<i32>, u8, u8, bool)
388            + 'a,
389    {
390        span!(_guard, "push", "GreedyMesh::push");
391        let cont = greedy_mesh(&mut self.atlas, &mut self.tex_size, self.max_size, config);
392        self.suspended.push(cont);
393    }
394
395    /// Finalize the mesh, producing texture color data for the whole model.
396    ///
397    /// By delaying finalization until the contents of the whole texture atlas
398    /// are known, we can perform just a single allocation to construct a
399    /// precisely fitting atlas.  This will also let us (in the future)
400    /// suspend meshing partway through in order to meet frame budget, and
401    /// potentially use a single staged upload to the GPU.
402    ///
403    /// Returns the ColLightsInfo corresponding to the constructed atlas.
404    pub fn finalize(self) -> (A, Vec2<u16>) {
405        span!(_guard, "finalize", "GreedyMesh::finalize");
406        let mut atlas_texture_data = A::blank_with_size(self.tex_size);
407        self.suspended.into_iter().for_each(|cont| {
408            cont(&mut atlas_texture_data, self.tex_size);
409        });
410        (atlas_texture_data, self.tex_size)
411    }
412
413    pub fn max_size(&self) -> Vec2<u16> { self.max_size }
414}
415
416fn greedy_mesh<
417    'a,
418    M: PartialEq,
419    D: 'a,
420    FA,
421    FL,
422    FG,
423    FO,
424    FS,
425    FP,
426    FT,
427    A: AtlasData,
428    Allocator: AtlasAllocator,
429>(
430    atlas: &mut Allocator,
431    atlas_size: &mut Vec2<u16>,
432    max_size: Vec2<u16>,
433    GreedyConfig {
434        mut data,
435        draw_delta,
436        greedy_size,
437        greedy_size_cross,
438        get_ao,
439        get_light,
440        get_glow,
441        get_opacity,
442        mut should_draw,
443        mut push_quad,
444        make_face_texel,
445    }: GreedyConfig<D, FA, FL, FG, FO, FS, FP, FT>,
446) -> Box<SuspendedMesh<'a, A>>
447where
448    FA: for<'r> FnMut(&'r mut D, Vec3<i32>) -> f32 + 'a,
449    FL: for<'r> FnMut(&'r mut D, Vec3<i32>) -> f32 + 'a,
450    FG: for<'r> FnMut(&'r mut D, Vec3<i32>) -> f32 + 'a,
451    FO: for<'r> FnMut(&'r mut D, Vec3<i32>) -> bool + 'a,
452    FS: for<'r> FnMut(&'r mut D, Vec3<i32>, Vec3<i32>, Vec2<Vec3<i32>>) -> Option<(bool, M)>,
453    FP: FnMut(Vec2<u16>, Vec2<Vec2<u16>>, Vec3<f32>, Vec2<Vec3<f32>>, Vec3<f32>, &M),
454    FT: for<'r> FnMut(<A::SliceMut<'_> as Iterator>::Item, &'r mut D, Vec3<i32>, u8, u8, bool) + 'a,
455{
456    span!(_guard, "greedy_mesh");
457    // TODO: Collect information to see if we can choose a good value here.
458    let mut todo_rects = Vec::with_capacity(1024);
459
460    // x (u = y, v = z)
461    greedy_mesh_cross_section(
462        Vec3::new(greedy_size.y, greedy_size.z, greedy_size_cross.x),
463        |pos| {
464            should_draw(
465                &mut data,
466                draw_delta + Vec3::new(pos.z, pos.x, pos.y),
467                Vec3::unit_x(),
468                Vec2::new(Vec3::unit_y(), Vec3::unit_z()),
469            )
470        },
471        |pos, dim, &(faces_forward, ref meta)| {
472            let pos = Vec3::new(pos.z, pos.x, pos.y);
473            let uv = Vec2::new(Vec3::unit_y(), Vec3::unit_z());
474            let norm = Vec3::unit_x();
475            let atlas_pos = add_to_atlas(
476                atlas,
477                &mut todo_rects,
478                pos,
479                uv,
480                dim,
481                norm,
482                faces_forward,
483                max_size,
484                atlas_size,
485            );
486            create_quad_greedy(
487                pos,
488                dim,
489                uv,
490                norm,
491                faces_forward,
492                meta,
493                atlas_pos,
494                |atlas_pos, dim, pos, draw_dim, norm, meta| {
495                    push_quad(atlas_pos, dim, pos, draw_dim, norm, meta)
496                },
497            );
498        },
499    );
500
501    // y (u = z, v = x)
502    greedy_mesh_cross_section(
503        Vec3::new(greedy_size.z, greedy_size.x, greedy_size_cross.y),
504        |pos| {
505            should_draw(
506                &mut data,
507                draw_delta + Vec3::new(pos.y, pos.z, pos.x),
508                Vec3::unit_y(),
509                Vec2::new(Vec3::unit_z(), Vec3::unit_x()),
510            )
511        },
512        |pos, dim, &(faces_forward, ref meta)| {
513            let pos = Vec3::new(pos.y, pos.z, pos.x);
514            let uv = Vec2::new(Vec3::unit_z(), Vec3::unit_x());
515            let norm = Vec3::unit_y();
516            let atlas_pos = add_to_atlas(
517                atlas,
518                &mut todo_rects,
519                pos,
520                uv,
521                dim,
522                norm,
523                faces_forward,
524                max_size,
525                atlas_size,
526            );
527            create_quad_greedy(
528                pos,
529                dim,
530                uv,
531                norm,
532                faces_forward,
533                meta,
534                atlas_pos,
535                |atlas_pos, dim, pos, draw_dim, norm, meta| {
536                    push_quad(atlas_pos, dim, pos, draw_dim, norm, meta)
537                },
538            );
539        },
540    );
541
542    // z (u = x, v = y)
543    greedy_mesh_cross_section(
544        Vec3::new(greedy_size.x, greedy_size.y, greedy_size_cross.z),
545        |pos| {
546            should_draw(
547                &mut data,
548                draw_delta + Vec3::new(pos.x, pos.y, pos.z),
549                Vec3::unit_z(),
550                Vec2::new(Vec3::unit_x(), Vec3::unit_y()),
551            )
552        },
553        |pos, dim, &(faces_forward, ref meta)| {
554            let pos = Vec3::new(pos.x, pos.y, pos.z);
555            let uv = Vec2::new(Vec3::unit_x(), Vec3::unit_y());
556            let norm = Vec3::unit_z();
557            let atlas_pos = add_to_atlas(
558                atlas,
559                &mut todo_rects,
560                pos,
561                uv,
562                dim,
563                norm,
564                faces_forward,
565                max_size,
566                atlas_size,
567            );
568            create_quad_greedy(
569                pos,
570                dim,
571                uv,
572                norm,
573                faces_forward,
574                meta,
575                atlas_pos,
576                |atlas_pos, dim, pos, draw_dim, norm, meta| {
577                    push_quad(atlas_pos, dim, pos, draw_dim, norm, meta)
578                },
579            );
580        },
581    );
582
583    Box::new(move |atlas_texture_data, cur_size| {
584        let mut data = data;
585        draw_texels::<_, A>(
586            atlas_texture_data,
587            cur_size,
588            &mut data,
589            todo_rects,
590            draw_delta,
591            get_ao,
592            get_light,
593            get_glow,
594            get_opacity,
595            make_face_texel,
596        );
597    })
598}
599
600/// Greedy meshing a single cross-section.
601// TODO: See if we can speed a lot of this up using SIMD.
602fn greedy_mesh_cross_section<M: PartialEq>(
603    dims: Vec3<usize>,
604    // Should we draw a face here (below this vertex)?  If so, provide its meta information.
605    mut draw_face: impl FnMut(Vec3<i32>) -> Option<M>,
606    // Vertex, width and height, and meta information about the block.
607    mut push_quads: impl FnMut(Vec3<usize>, Vec2<usize>, &M),
608) {
609    span!(_guard, "greedy_mesh_cross_section");
610    // mask represents which faces are either set while the other is unset, or unset
611    // while the other is set.
612    let mut mask = (0..dims.y * dims.x).map(|_| None).collect::<Vec<_>>();
613    (0..dims.z + 1).for_each(|d| {
614        // Compute mask
615        mask.iter_mut().enumerate().for_each(|(posi, mask)| {
616            let i = posi % dims.x;
617            let j = posi / dims.x;
618            // NOTE: Safe because dims.z actually fits in a u16.
619            *mask = draw_face(Vec3::new(i as i32, j as i32, d as i32));
620        });
621
622        (0..dims.y).for_each(|j| {
623            let mut i = 0;
624            while i < dims.x {
625                // Compute width (number of set x bits for this row and layer, starting at the
626                // current minimum column).
627                if let Some(ori) = &mask[j * dims.x + i] {
628                    let width = 1 + mask[j * dims.x + i + 1..j * dims.x + dims.x]
629                        .iter()
630                        .take_while(move |&mask| mask.as_ref() == Some(ori))
631                        .count();
632                    let max_x = i + width;
633                    // Compute height (number of rows having w set x bits for this layer, starting
634                    // at the current minimum column and row).
635                    let height = 1
636                        + (j + 1..dims.y)
637                            .take_while(|h| {
638                                mask[h * dims.x + i..h * dims.x + max_x]
639                                    .iter()
640                                    .all(|mask| mask.as_ref() == Some(ori))
641                            })
642                            .count();
643                    let max_y = j + height;
644                    // Add quad.
645                    push_quads(Vec3::new(i, j, d), Vec2::new(width, height), ori);
646                    // Unset mask bits in drawn region, so we don't try to re-draw them.
647                    (j..max_y).for_each(|l| {
648                        mask[l * dims.x + i..l * dims.x + max_x]
649                            .iter_mut()
650                            .for_each(|mask| {
651                                *mask = None;
652                            });
653                    });
654                    // Update x value.
655                    i = max_x;
656                } else {
657                    i += 1;
658                }
659            }
660        });
661    });
662}
663
664fn add_to_atlas<Allocator: AtlasAllocator>(
665    atlas: &mut Allocator,
666    todo_rects: &mut Vec<TodoRect>,
667    pos: Vec3<usize>,
668    uv: Vec2<Vec3<u16>>,
669    dim: Vec2<usize>,
670    norm: Vec3<i16>,
671    faces_forward: bool,
672    max_size: Vec2<u16>,
673    cur_size: &mut Vec2<u16>,
674) -> guillotiere::Rectangle {
675    // TODO: Check this conversion.
676    let atlas_rect = loop {
677        // NOTE: Conversion to u16 is safe because he x, y, and z dimensions for any
678        // chunk index must fit in at least an i16 (lower for x and y, probably
679        // lower for z) and at least x and y are not negative.
680        let res = atlas.allocate(Vec2::new(dim.x as u16 + 1, dim.y as u16 + 1));
681        if let Some(atlas_rect) = res {
682            break atlas_rect;
683        }
684        // Allocation failure.
685        let current_size = atlas.size();
686        if current_size == max_size {
687            // NOTE: Currently, if we fail to allocate a terrain chunk in the atlas and we
688            // have already reached the maximum texture size, we choose to just skip the
689            // geometry and log a warning, rather than panicking or trying to use a fallback
690            // technique (e.g. a texture array).
691            //
692            // FIXME: Either make more robust, or explicitly document that limits on texture
693            // size need to be respected for terrain data (the OpenGL minimum requirement is
694            // 1024 × 1024, but in practice almost all computers support 4096 × 4096 or
695            // higher; see
696            // https://feedback.wildfiregames.com/report/opengl/feature/GL_MAX_TEXTURE_SIZE).
697            panic!(
698                "Could not add texture to atlas using simple allocator (pos={:?}, dim={:?});we \
699                 could not fit the whole model into a single texture on this machine
700                        (max texture size={:?}, so we are discarding this rectangle.",
701                pos, dim, max_size
702            );
703        }
704        // Otherwise, we haven't reached max size yet, so double the size (or reach the
705        // max texture size) and try again.
706        let new_size = max_size.map2(current_size, |max, current| {
707            max.min(current.saturating_mul(2))
708        });
709        atlas.grow(new_size);
710    };
711    // NOTE: Conversion is correct because our initial max size for the atlas was a
712    // u16 and we never grew the atlas past the max size, meaning all valid
713    // coordinates within the atlas also fit into a u16.
714    *cur_size = Vec2::new(
715        cur_size.x.max(atlas_rect.max.x as u16),
716        cur_size.y.max(atlas_rect.max.y as u16),
717    );
718
719    // NOTE: pos can be converted safely from usize to i32 because all legal block
720    // coordinates in this chunk must fit in an i32 (actually we have the much
721    // stronger property that this holds across the whole map).
722    let norm = norm.map(i32::from);
723    todo_rects.push((
724        pos.map(|e| e as i32) + if faces_forward { -norm } else { Vec3::zero() },
725        uv,
726        atlas_rect,
727        if faces_forward { norm } else { -norm },
728    ));
729    atlas_rect
730}
731
732/// We deferred actually recording the colors within the rectangles in order to
733/// generate a texture of minimal size; we now proceed to create and populate
734/// it.
735// TODO: Consider using the heavier interface (not the simple one) which seems
736// to provide builtin support for what we're doing here.
737//
738// TODO: See if we can speed this up using SIMD.
739fn draw_texels<D, A: AtlasData>(
740    atlas_texture_data: &mut A,
741    cur_size: Vec2<u16>,
742    data: &mut D,
743    todo_rects: Vec<TodoRect>,
744    draw_delta: Vec3<i32>,
745    mut get_ao: impl FnMut(&mut D, Vec3<i32>) -> f32,
746    mut get_light: impl FnMut(&mut D, Vec3<i32>) -> f32,
747    mut get_glow: impl FnMut(&mut D, Vec3<i32>) -> f32,
748    mut get_opacity: impl FnMut(&mut D, Vec3<i32>) -> bool,
749    mut make_face_texel: impl FnMut(
750        <A::SliceMut<'_> as Iterator>::Item,
751        &mut D,
752        Vec3<i32>,
753        u8,
754        u8,
755        bool,
756    ),
757) {
758    todo_rects.into_iter().for_each(|(pos, uv, rect, delta)| {
759        // NOTE: Conversions are safe because width, height, and offset must be
760        // non-negative, and because every allocated coordinate in the atlas must be in
761        // bounds for the original size, max_texture_size, which fit into a u16.
762        let width = (rect.max.x - rect.min.x) as u16;
763        let height = (rect.max.y - rect.min.y) as u16;
764        let left = rect.min.x as u16;
765        let top = rect.min.y as u16;
766        let uv = uv.map(|e| e.map(i32::from));
767        let pos = pos + draw_delta;
768        (0..height).for_each(|v| {
769            let start = cur_size.x as usize * usize::from(top + v) + usize::from(left);
770            (0..width)
771                .zip(atlas_texture_data.slice_mut(start..start + usize::from(width)))
772                .for_each(|(u, texel)| {
773                    let pos = pos + uv.x * i32::from(u) + uv.y * i32::from(v);
774                    // TODO: Consider optimizing to take advantage of the fact that this whole
775                    // face should be facing nothing but air (this is not currently true, but
776                    // could be if we used the right AO strategy).
777                    // Each indirect light needs to come in through the direct light.
778                    // Thus, we assign each light a score based on opacity (currently just 0 or
779                    // 1, but it could support translucent lights in the future).
780                    // Thus, indirect_u_opacity and indirect_v_opacity are multiplied by
781                    // direct_opacity, and indirect_uv_opacity is multiplied by
782                    // the maximum of both of u and v's indirect opacities (since there are
783                    // two choices for how to get to the direct surface).
784                    let pos = pos
785                        + if u + 1 == width { -uv.x } else { Vec3::zero() }
786                        + if v + 1 == height { -uv.y } else { Vec3::zero() };
787                    let uv = Vec2::new(
788                        if u + 1 == width { -uv.x } else { uv.x },
789                        if v + 1 == height { -uv.y } else { uv.y },
790                    );
791
792                    let light_pos = pos + delta;
793
794                    // Currently, we assume that direct_opacity is 1 (if it's 0, you can't see
795                    // the face anyway, since it's blocked by the block directly in front of it).
796                    // TODO: If we add non-0/1 opacities, fix this.
797                    // bottom-left block
798                    let direct_u_opacity = get_opacity(data, light_pos - uv.x);
799                    // top-right block
800                    let direct_v_opacity = get_opacity(data, light_pos - uv.y);
801
802                    // NOTE: Since we only support 0/1 opacities currently, we assume
803                    // direct_opacity is  1, and the light value will be zero anyway for objects
804                    // with opacity 0, we only "multiply" by indirect_uv_opacity for now (since
805                    // it's the only one that could be 0 even if its light value is not).
806                    // However, "spiritually" these light values are all being multiplied by
807                    // their opacities.
808                    let darkness = (
809                        // Light from the bottom-right-front block to this vertex always
810                        // appears on this face, since it's the block this face is facing (so
811                        // it can't be blocked by anything).
812                        get_light(data, light_pos)
813                            + get_light(data, light_pos - uv.x)
814                            + get_light(data, light_pos - uv.y)
815                            + if direct_u_opacity || direct_v_opacity {
816                                get_light(data, light_pos - uv.x - uv.y)
817                            } else {
818                                0.0
819                            }
820                    ) / 4.0;
821                    let ao = (get_ao(data, light_pos)
822                        + get_ao(data, light_pos - uv.x)
823                        + get_ao(data, light_pos - uv.y)
824                        + if direct_u_opacity || direct_v_opacity {
825                            get_ao(data, light_pos - uv.x - uv.y)
826                        } else {
827                            0.0
828                        })
829                        / 4.0;
830                    let glowiness = (get_glow(data, light_pos)
831                        + get_glow(data, light_pos - uv.x)
832                        + get_glow(data, light_pos - uv.y)
833                        + if direct_u_opacity || direct_v_opacity {
834                            get_glow(data, light_pos - uv.x - uv.y)
835                        } else {
836                            0.0
837                        })
838                        / 4.0;
839                    let light = (darkness * 31.5) as u8;
840                    let glow = (glowiness * 31.5) as u8;
841                    let ao = ao > 0.7;
842                    make_face_texel(texel, data, pos, light, glow, ao);
843                });
844        });
845    });
846}
847
848/// Precondition: when this function is called, atlas_pos should reflect an
849/// actual valid position in a texture atlas (meaning it should fit into a u16).
850// TODO: See if we can speed a lot of this up using SIMD.
851fn create_quad_greedy<M>(
852    origin: Vec3<usize>,
853    dim: Vec2<usize>,
854    uv: Vec2<Vec3<u16>>,
855    norm: Vec3<i16>,
856    faces_forward: bool,
857    meta: &M,
858    atlas_pos: guillotiere::Rectangle,
859    mut push_quad: impl FnMut(Vec2<u16>, Vec2<Vec2<u16>>, Vec3<f32>, Vec2<Vec3<f32>>, Vec3<f32>, &M),
860) {
861    let origin = origin.map(|e| e as f32);
862    // NOTE: Conversion to f32 safe by function precondition (u16 can losslessly
863    // cast to f32, and dim fits in a u16).
864    let draw_dim = uv.map2(dim.map(|e| e as f32), |e, f| e.map(f32::from) * f);
865    let dim = Vec2::new(Vec2::new(dim.x as u16, 0), Vec2::new(0, dim.y as u16));
866    let (draw_dim, dim, /* uv, */ norm) = if faces_forward {
867        (draw_dim, dim, norm)
868    } else {
869        (
870            Vec2::new(draw_dim.y, draw_dim.x),
871            Vec2::new(dim.y, dim.x),
872            -norm,
873        )
874    };
875    let norm = norm.map(f32::from);
876    // NOTE: Conversion to u16 safe by function precondition.
877    let atlas_pos = Vec2::new(atlas_pos.min.x as u16, atlas_pos.min.y as u16);
878    push_quad(atlas_pos, dim, origin, draw_dim, norm, meta);
879}
880
881pub fn create_quad<O: Vertex, M>(
882    atlas_pos: Vec2<u16>,
883    dim: Vec2<Vec2<u16>>,
884    origin: Vec3<f32>,
885    draw_dim: Vec2<Vec3<f32>>,
886    norm: Vec3<f32>,
887    meta: &M,
888    mut create_vertex: impl FnMut(Vec2<u16>, Vec3<f32>, Vec3<f32>, &M) -> O,
889) -> Quad<O> {
890    Quad::new(
891        create_vertex(atlas_pos, origin, norm, meta),
892        create_vertex(atlas_pos + dim.x, origin + draw_dim.x, norm, meta),
893        create_vertex(
894            atlas_pos + dim.x + dim.y,
895            origin + draw_dim.x + draw_dim.y,
896            norm,
897            meta,
898        ),
899        create_vertex(atlas_pos + dim.y, origin + draw_dim.y, norm, meta),
900    )
901}