binary_greedy_meshing/
lib.rs

1#![no_std]
2
3#[macro_use]
4extern crate alloc;
5
6mod face;
7mod quad;
8
9use alloc::{boxed::Box, collections::btree_set::BTreeSet, vec::Vec};
10
11pub use face::*;
12pub use quad::*;
13
14#[derive(Debug)]
15pub struct Mesher<const CS: usize> {
16    // Output
17    pub quads: [Vec<Quad>; 6],
18    // Internal buffers
19    /// CS_2 * 6
20    face_masks: Box<[u64]>,
21    /// CS_2
22    forward_merged: Box<[u8]>,
23    /// CS
24    right_merged: Box<[u8]>,
25}
26
27impl<const CS: usize> Mesher<CS> {
28    pub const CS_2: usize = CS * CS;
29    pub const CS_P: usize = CS + 2;
30    pub const CS_P2: usize = Self::CS_P * Self::CS_P;
31    pub const CS_P3: usize = Self::CS_P * Self::CS_P * Self::CS_P;
32    pub const P_MASK: u64 = !(1 << (Self::CS_P - 1) | 1);
33
34    /// Creates a mesher object, allocates necessary buffers
35    pub fn new() -> Self {
36        Self {
37            face_masks: vec![0; Self::CS_2 * 6].into_boxed_slice(),
38            forward_merged: vec![0; Self::CS_2].into_boxed_slice(),
39            right_merged: vec![0; CS].into_boxed_slice(),
40            quads: core::array::from_fn(|_| Vec::new()),
41        }
42    }
43
44    /// Call this between each meshing call to reset the buffers without reallocating them
45    pub fn clear(&mut self) {
46        self.face_masks.fill(0);
47        self.forward_merged.fill(0);
48        self.right_merged.fill(0);
49        for i in 0..self.quads.len() {
50            self.quads[i].clear();
51        }
52    }
53
54    fn face_culling(&mut self, voxels: &[u16], transparents: &BTreeSet<u16>) {
55        // Hidden face culling
56        for a in 1..(Self::CS_P - 1) {
57            let a_cs_p = a * Self::CS_P;
58
59            for b in 1..(Self::CS_P - 1) {
60                let ab = (a_cs_p + b) * Self::CS_P;
61                let ba_index = (b - 1) + (a - 1) * CS;
62                let ab_index = (a - 1) + (b - 1) * CS;
63
64                for c in 1..(Self::CS_P - 1) {
65                    let abc = ab + c;
66                    let v1 = voxels[abc];
67                    if v1 == 0 {
68                        continue;
69                    }
70                    self.face_masks[ba_index + 0 * Self::CS_2] |=
71                        face_value(v1, voxels[abc + Self::CS_P2], &transparents) << (c - 1);
72                    self.face_masks[ba_index + 1 * Self::CS_2] |=
73                        face_value(v1, voxels[abc - Self::CS_P2], &transparents) << (c - 1);
74
75                    self.face_masks[ab_index + 2 * Self::CS_2] |=
76                        face_value(v1, voxels[abc + Self::CS_P], &transparents) << (c - 1);
77                    self.face_masks[ab_index + 3 * Self::CS_2] |=
78                        face_value(v1, voxels[abc - Self::CS_P], &transparents) << (c - 1);
79
80                    self.face_masks[ba_index + 4 * Self::CS_2] |=
81                        face_value(v1, voxels[abc + 1], &transparents) << c;
82                    self.face_masks[ba_index + 5 * Self::CS_2] |=
83                        face_value(v1, voxels[abc - 1], &transparents) << c;
84                }
85            }
86        }
87    }
88
89    fn fast_face_culling(&mut self, voxels: &[u16], opaque_mask: &[u64], trans_mask: &[u64]) {
90        // Hidden face culling
91        for a in 1..(Self::CS_P - 1) {
92            let a_ = a * Self::CS_P;
93
94            for b in 1..(Self::CS_P - 1) {
95                // Column-wise opaque step
96                let ab = a_ + b;
97                let opaque_col = opaque_mask[ab] & Self::P_MASK;
98                let unpadded_opaque_col = opaque_col >> 1;
99                let ba_index = (b - 1) + (a - 1) * CS;
100                let ab_index = (a - 1) + (b - 1) * CS;
101                let up_faces = ba_index + 0 * Self::CS_2;
102                let down_faces = ba_index + 1 * Self::CS_2;
103                let right_faces = ab_index + 2 * Self::CS_2;
104                let left_faces = ab_index + 3 * Self::CS_2;
105                let front_faces = ba_index + 4 * Self::CS_2;
106                let back_faces = ba_index + 5 * Self::CS_2;
107                let not_front_col = !opaque_mask[ab + Self::CS_P] >> 1;
108                let not_back_col = !opaque_mask[ab - Self::CS_P] >> 1;
109                let not_right_col = !opaque_mask[ab + 1] >> 1;
110                let not_left_col = !opaque_mask[ab - 1] >> 1;
111                let not_col_up = !(opaque_mask[ab] >> 1);
112                let not_col_down = !(opaque_mask[ab] << 1);
113                self.face_masks[up_faces] = unpadded_opaque_col & not_front_col;
114                self.face_masks[down_faces] = unpadded_opaque_col & not_back_col;
115
116                self.face_masks[right_faces] = unpadded_opaque_col & not_right_col;
117                self.face_masks[left_faces] = unpadded_opaque_col & not_left_col;
118
119                self.face_masks[front_faces] = opaque_col & not_col_up;
120                self.face_masks[back_faces] = opaque_col & not_col_down;
121
122                // check if there's transparent blocks in this column
123                let mut bits_here = trans_mask[ab] & Self::P_MASK;
124                if bits_here == 0 {
125                    continue;
126                }
127                // Block-wise transparent step
128                // The transparent step is slower than the opaque step
129                // because we need to check if neighboring transparent blocks are differents (we don't care about that for opaque blocks)
130                let ab_ = ab * Self::CS_P;
131                while bits_here != 0 {
132                    let c = bits_here.trailing_zeros() as usize;
133                    let c_mask = 1 << c;
134                    let unpadded_c_mask = c_mask >> 1;
135                    bits_here &= !(c_mask);
136                    let abc = ab_ + c;
137                    let v1 = voxels[abc];
138                    self.face_masks[up_faces] |= not_front_col
139                        & unpadded_c_mask
140                        & ((v1 != voxels[abc + Self::CS_P2]) as u64) << (c - 1);
141                    self.face_masks[down_faces] |= not_back_col
142                        & unpadded_c_mask
143                        & ((v1 != voxels[abc - Self::CS_P2]) as u64) << (c - 1);
144
145                    self.face_masks[right_faces] |= not_right_col
146                        & unpadded_c_mask
147                        & ((v1 != voxels[abc + Self::CS_P]) as u64) << (c - 1);
148                    self.face_masks[left_faces] |= not_left_col
149                        & unpadded_c_mask
150                        & ((v1 != voxels[abc - Self::CS_P]) as u64) << (c - 1);
151
152                    self.face_masks[front_faces] |=
153                        not_col_up & c_mask & ((v1 != voxels[abc + 1]) as u64) << c;
154                    self.face_masks[back_faces] |=
155                        not_col_down & c_mask & ((v1 != voxels[abc - 1]) as u64) << c;
156                }
157            }
158        }
159    }
160
161    fn face_merging(&mut self, voxels: &[u16]) {
162        // Greedy meshing faces 0-3
163        for face in 0..=3 {
164            let axis = face / 2;
165
166            for layer in 0..CS {
167                let bits_location = layer * CS + face * Self::CS_2;
168
169                for forward in 0..CS {
170                    let mut bits_here = self.face_masks[forward + bits_location];
171                    if bits_here == 0 {
172                        continue;
173                    }
174
175                    let bits_next = if forward + 1 < CS {
176                        self.face_masks[(forward + 1) + bits_location]
177                    } else {
178                        0
179                    };
180
181                    let mut right_merged = 1;
182                    while bits_here != 0 {
183                        let bit_pos = bits_here.trailing_zeros() as usize;
184
185                        let v_type =
186                            voxels[get_axis_index::<CS>(axis, forward + 1, bit_pos + 1, layer + 1)];
187
188                        if (bits_next >> bit_pos & 1) != 0
189                            && v_type
190                                == voxels[get_axis_index::<CS>(
191                                    axis,
192                                    forward + 2,
193                                    bit_pos + 1,
194                                    layer + 1,
195                                )]
196                        {
197                            self.forward_merged[bit_pos] += 1;
198                            bits_here &= !(1 << bit_pos);
199                            continue;
200                        }
201
202                        for right in (bit_pos + 1)..CS {
203                            if (bits_here >> right & 1) == 0
204                                || self.forward_merged[bit_pos] != self.forward_merged[right]
205                                || v_type
206                                    != voxels[get_axis_index::<CS>(
207                                        axis,
208                                        forward + 1,
209                                        right + 1,
210                                        layer + 1,
211                                    )]
212                            {
213                                break;
214                            }
215                            self.forward_merged[right] = 0;
216                            right_merged += 1;
217                        }
218                        bits_here &= !((1 << (bit_pos + right_merged)) - 1);
219
220                        let mesh_front = forward - self.forward_merged[bit_pos] as usize;
221                        let mesh_left = bit_pos;
222                        let mesh_up = layer + (!face & 1);
223
224                        let mesh_width = right_merged;
225                        let mesh_length = (self.forward_merged[bit_pos] + 1) as usize;
226
227                        self.forward_merged[bit_pos] = 0;
228                        right_merged = 1;
229
230                        let v_type = v_type as usize;
231
232                        let quad = match face {
233                            0 => Quad::pack(
234                                mesh_front,
235                                mesh_up,
236                                mesh_left,
237                                mesh_length,
238                                mesh_width,
239                                v_type,
240                            ),
241                            1 => Quad::pack(
242                                mesh_front + mesh_length as usize,
243                                mesh_up,
244                                mesh_left,
245                                mesh_length,
246                                mesh_width,
247                                v_type,
248                            ),
249                            2 => Quad::pack(
250                                mesh_up,
251                                mesh_front + mesh_length as usize,
252                                mesh_left,
253                                mesh_length,
254                                mesh_width,
255                                v_type,
256                            ),
257                            3 => Quad::pack(
258                                mesh_up,
259                                mesh_front,
260                                mesh_left,
261                                mesh_length,
262                                mesh_width,
263                                v_type,
264                            ),
265                            _ => unreachable!(),
266                        };
267                        self.quads[face].push(quad);
268                    }
269                }
270            }
271        }
272
273        // Greedy meshing faces 4-5
274        for face in 4..6 {
275            let axis = face / 2;
276
277            for forward in 0..CS {
278                let bits_location = forward * CS + face * Self::CS_2;
279                let bits_forward_location = (forward + 1) * CS + face * Self::CS_2;
280
281                for right in 0..CS {
282                    let mut bits_here = self.face_masks[right + bits_location];
283                    if bits_here == 0 {
284                        continue;
285                    }
286
287                    let bits_forward = if forward < CS - 1 {
288                        self.face_masks[right + bits_forward_location]
289                    } else {
290                        0
291                    };
292                    let bits_right = if right < CS - 1 {
293                        self.face_masks[right + 1 + bits_location]
294                    } else {
295                        0
296                    };
297                    let right_cs = right * CS;
298
299                    while bits_here != 0 {
300                        let bit_pos = bits_here.trailing_zeros() as usize;
301
302                        bits_here &= !(1 << bit_pos);
303
304                        let v_type =
305                            voxels[get_axis_index::<CS>(axis, right + 1, forward + 1, bit_pos)];
306                        let forward_merge_i = right_cs + (bit_pos - 1);
307                        let right_merged_ref = &mut self.right_merged[bit_pos - 1];
308
309                        if *right_merged_ref == 0
310                            && (bits_forward >> bit_pos & 1) != 0
311                            && v_type
312                                == voxels
313                                    [get_axis_index::<CS>(axis, right + 1, forward + 2, bit_pos)]
314                        {
315                            self.forward_merged[forward_merge_i] += 1;
316                            continue;
317                        }
318
319                        if (bits_right >> bit_pos & 1) != 0
320                            && self.forward_merged[forward_merge_i]
321                                == self.forward_merged[(right_cs + CS) + (bit_pos - 1)]
322                            && v_type
323                                == voxels
324                                    [get_axis_index::<CS>(axis, right + 2, forward + 1, bit_pos)]
325                        {
326                            self.forward_merged[forward_merge_i] = 0;
327                            *right_merged_ref += 1;
328                            continue;
329                        }
330
331                        let mesh_left = right - *right_merged_ref as usize;
332                        let mesh_front = forward - self.forward_merged[forward_merge_i] as usize;
333                        let mesh_up = bit_pos - 1 + (!face & 1);
334
335                        let mesh_width = 1 + *right_merged_ref;
336                        let mesh_length = 1 + self.forward_merged[forward_merge_i];
337
338                        self.forward_merged[forward_merge_i] = 0;
339                        *right_merged_ref = 0;
340
341                        let quad = Quad::pack(
342                            mesh_left + (if face == 4 { mesh_width } else { 0 }) as usize,
343                            mesh_front,
344                            mesh_up,
345                            mesh_width as usize,
346                            mesh_length as usize,
347                            v_type as usize,
348                        );
349                        self.quads[face].push(quad);
350                    }
351                }
352            }
353        }
354    }
355
356    /// Meshes a voxel buffer representing a chunk, using an opaque and transparent mask with 1 u64 per column with 1 bit per voxel in the column,
357    /// signaling if the voxel is opaque or transparent.
358    /// This is ~4x faster than the regular mesh method but requires maintaining 2 masks for each chunk.
359    /// See https://github.com/Inspirateur/binary-greedy-meshing?tab=readme-ov-file#what-to-do-with-mesh_dataquads for using the output
360    pub fn fast_mesh(&mut self, voxels: &[u16], opaque_mask: &[u64], trans_mask: &[u64]) {
361        self.fast_face_culling(voxels, opaque_mask, trans_mask);
362        self.face_merging(voxels);
363    }
364
365    /// Meshes a voxel buffer representing a chunk, using a BTreeSet signaling which voxel values are transparent.
366    /// This is ~4x slower than the fast_mesh method but does not require maintaining 2 masks for each chunk.
367    /// See https://github.com/Inspirateur/binary-greedy-meshing?tab=readme-ov-file#what-to-do-with-mesh_dataquads for using the output
368    pub fn mesh(&mut self, voxels: &[u16], transparents: &BTreeSet<u16>) {
369        self.face_culling(voxels, transparents);
370        self.face_merging(voxels);
371    }
372}
373
374#[inline]
375/// v1 is not AIR
376fn face_value(v1: u16, v2: u16, transparents: &BTreeSet<u16>) -> u64 {
377    (v2 == 0 || (v1 != v2 && transparents.contains(&v2))) as u64
378}
379
380#[inline]
381fn get_axis_index<const CS: usize>(axis: usize, a: usize, b: usize, c: usize) -> usize {
382    // TODO: figure out how to shuffle this around to make it work with YZX
383    match axis {
384        0 => b + (a * Mesher::<CS>::CS_P) + (c * Mesher::<CS>::CS_P2),
385        1 => b + (c * Mesher::<CS>::CS_P) + (a * Mesher::<CS>::CS_P2),
386        _ => c + (a * Mesher::<CS>::CS_P) + (b * Mesher::<CS>::CS_P2),
387    }
388}
389
390/// Compute Mesh indices for a given amount of quads
391pub fn indices(num_quads: usize) -> Vec<u32> {
392    // Each quads is made of 2 triangles which require 6 indices
393    // The indices are the same regardless of the face
394    let mut res = Vec::with_capacity(num_quads * 6);
395    for i in 0..num_quads as u32 {
396        res.push((i << 2) | 2);
397        res.push((i << 2) | 0);
398        res.push((i << 2) | 1);
399        res.push((i << 2) | 1);
400        res.push((i << 2) | 3);
401        res.push((i << 2) | 2);
402    }
403    res
404}
405
406pub fn pad_linearize<const CS: usize>(x: usize, y: usize, z: usize) -> usize {
407    z + 1 + (x + 1) * Mesher::<CS>::CS_P + (y + 1) * Mesher::<CS>::CS_P2
408}
409
410/// Compute an opacity mask from a voxel buffer and a BTreeSet specifying which voxel values are transparent
411pub fn compute_opaque_mask<const CS: usize>(
412    voxels: &[u16],
413    transparents: &BTreeSet<u16>,
414) -> Box<[u64]> {
415    let mut opaque_mask = vec![0; Mesher::<CS>::CS_P2].into_boxed_slice();
416    // Fill the opacity mask
417    for (i, voxel) in voxels.iter().enumerate() {
418        // If the voxel is transparent we skip it
419        if *voxel == 0 || transparents.contains(voxel) {
420            continue;
421        }
422        let (r, q) = (i / Mesher::<CS>::CS_P, i % Mesher::<CS>::CS_P);
423        opaque_mask[r] |= 1 << q;
424    }
425    opaque_mask
426}
427
428/// Compute a transparent mask from a voxel buffer and a BTreeSet specifying which voxel values are transparent
429pub fn compute_transparent_mask<const CS: usize>(
430    voxels: &[u16],
431    transparents: &BTreeSet<u16>,
432) -> Box<[u64]> {
433    let mut trans_mask = vec![0; Mesher::<CS>::CS_P2].into_boxed_slice();
434    // Fill the opacity mask
435    for (i, voxel) in voxels.iter().enumerate() {
436        // If the voxel is opaque we skip it
437        if *voxel == 0 || !transparents.contains(voxel) {
438            continue;
439        }
440        let (r, q) = (i / Mesher::<CS>::CS_P, i % Mesher::<CS>::CS_P);
441        trans_mask[r] |= 1 << q;
442    }
443    trans_mask
444}
445
446#[cfg(test)]
447mod tests {
448    use crate::{self as bgm};
449    use alloc::{boxed::Box, collections::btree_set::BTreeSet};
450
451    pub const CS: usize = 62;
452
453    /// Show quad output on a simple 2 voxels case
454    #[test]
455    fn test_output() {
456        extern crate std;
457        let mut voxels = [0; bgm::Mesher::<CS>::CS_P3];
458        voxels[bgm::pad_linearize::<CS>(0, 0, 0)] = 1;
459        voxels[bgm::pad_linearize::<CS>(0, 1, 0)] = 1;
460
461        let mut mesher = bgm::Mesher::<CS>::new();
462        let opaque_mask = bgm::compute_opaque_mask::<CS>(&voxels, &BTreeSet::new());
463        let trans_mask = vec![0; bgm::Mesher::<CS>::CS_P2].into_boxed_slice();
464        mesher.fast_mesh(&voxels, &opaque_mask, &trans_mask);
465        // self.quads is the output
466        for (i, quads) in mesher.quads.iter().enumerate() {
467            std::println!("--- Face {i} ---");
468            for &quad in quads {
469                std::println!("{:?}", quad);
470            }
471        }
472    }
473
474    /// Ensures that mesh and fast_mesh return the same results
475    #[test]
476    fn same_results() {
477        let voxels = test_buffer();
478        let transparent_blocks = BTreeSet::from([2]);
479        let opaque_mask = bgm::compute_opaque_mask::<CS>(voxels.as_slice(), &BTreeSet::new());
480        let trans_mask =
481            bgm::compute_transparent_mask::<CS>(voxels.as_slice(), &transparent_blocks);
482        let mut mesher1 = bgm::Mesher::<CS>::new();
483        mesher1.mesh(voxels.as_slice(), &transparent_blocks);
484        let mut mesher2 = bgm::Mesher::<CS>::new();
485        mesher2.fast_mesh(voxels.as_slice(), &opaque_mask, &trans_mask);
486        assert_eq!(mesher1.quads, mesher2.quads);
487    }
488
489    fn test_buffer() -> Box<[u16; bgm::Mesher::<CS>::CS_P3]> {
490        let mut voxels = Box::new([0; bgm::Mesher::<CS>::CS_P3]);
491        for x in 0..CS {
492            for y in 0..CS {
493                for z in 0..CS {
494                    voxels[bgm::pad_linearize::<CS>(x, y, z)] = transparent_sphere(x, y, z);
495                }
496            }
497        }
498        voxels
499    }
500
501    fn transparent_sphere(x: usize, y: usize, z: usize) -> u16 {
502        if x == 8 {
503            2
504        } else if (x as i32 - 31).pow(2) + (y as i32 - 31).pow(2) + (z as i32 - 31).pow(2)
505            < 16 as i32
506        {
507            1
508        } else {
509            0
510        }
511    }
512}
binary_greedy_meshing/lib.rs

binary_greedy_meshing/
lib.rs
