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}