block_mesh/greedy/
merge_strategy.rs

1use crate::greedy::face_needs_mesh;
2use crate::Voxel;
3
4use super::MergeVoxel;
5
6// TODO: implement a MergeStrategy for voxels with an ambient occlusion value at each vertex
7
8/// A strategy for merging cube faces into quads.
9pub trait MergeStrategy {
10    type Voxel;
11
12    /// Return the width and height of the quad that should be constructed.
13    ///
14    /// `min_index`: The linear index for the minimum voxel in this quad.
15    ///
16    /// `max_width`: The maximum possible width for the quad to be constructed.
17    ///
18    /// `max_height`: The maximum possible height for the quad to be constructed.
19    ///
20    /// `face_strides`: Strides to help with indexing in the necessary directions for this cube face.
21    ///
22    /// `voxels`: The entire array of voxel data.
23    ///
24    /// `visited`: The bitmask of which voxels have already been meshed. A quad's extent will be marked as visited (`true`)
25    ///            after `find_quad` returns.
26    ///
27    /// # Safety
28    ///
29    /// Some implementations may use unchecked indexing of `voxels` for performance. If this trait is not invoked with correct
30    /// arguments, access out of bounds may cause undefined behavior.
31    unsafe fn find_quad(
32        min_index: u32,
33        max_width: u32,
34        max_height: u32,
35        face_strides: &FaceStrides,
36        voxels: &[Self::Voxel],
37        visited: &[bool],
38    ) -> (u32, u32)
39    where
40        Self::Voxel: Voxel;
41}
42
43pub struct FaceStrides {
44    pub n_stride: u32,
45    pub u_stride: u32,
46    pub v_stride: u32,
47    pub visibility_offset: u32,
48}
49
50pub struct VoxelMerger<T> {
51    marker: std::marker::PhantomData<T>,
52}
53
54impl<T> MergeStrategy for VoxelMerger<T>
55where
56    T: MergeVoxel,
57{
58    type Voxel = T;
59
60    unsafe fn find_quad(
61        min_index: u32,
62        max_width: u32,
63        max_height: u32,
64        face_strides: &FaceStrides,
65        voxels: &[T],
66        visited: &[bool],
67    ) -> (u32, u32) {
68        // Greedily search for the biggest visible quad where all merge values are the same.
69        let quad_value = voxels.get_unchecked(min_index as usize).merge_value();
70
71        // Start by finding the widest quad in the U direction.
72        let mut row_start_stride = min_index;
73        let quad_width = Self::get_row_width(
74            voxels,
75            visited,
76            &quad_value,
77            face_strides.visibility_offset,
78            row_start_stride,
79            face_strides.u_stride,
80            max_width,
81        );
82
83        // Now see how tall we can make the quad in the V direction without changing the width.
84        row_start_stride += face_strides.v_stride;
85        let mut quad_height = 1;
86        while quad_height < max_height {
87            let row_width = Self::get_row_width(
88                voxels,
89                visited,
90                &quad_value,
91                face_strides.visibility_offset,
92                row_start_stride,
93                face_strides.u_stride,
94                quad_width,
95            );
96            if row_width < quad_width {
97                break;
98            }
99            quad_height += 1;
100            row_start_stride = row_start_stride.wrapping_add(face_strides.v_stride);
101        }
102
103        (quad_width, quad_height)
104    }
105}
106
107impl<T> VoxelMerger<T> {
108    unsafe fn get_row_width(
109        voxels: &[T],
110        visited: &[bool],
111        quad_merge_voxel_value: &T::MergeValue,
112        visibility_offset: u32,
113        start_stride: u32,
114        delta_stride: u32,
115        max_width: u32,
116    ) -> u32
117    where
118        T: MergeVoxel,
119    {
120        let mut quad_width = 0;
121        let mut row_stride = start_stride;
122        while quad_width < max_width {
123            let voxel = voxels.get_unchecked(row_stride as usize);
124
125            if !face_needs_mesh(voxel, row_stride, visibility_offset, voxels, visited) {
126                break;
127            }
128
129            if !voxel.merge_value().eq(quad_merge_voxel_value) {
130                // Voxel needs to be non-empty and match the quad merge value.
131                break;
132            }
133
134            quad_width += 1;
135            row_stride += delta_stride;
136        }
137
138        quad_width
139    }
140}
block_mesh/greedy/merge_strategy.rs

block_mesh/greedy/
merge_strategy.rs
