height_mesh/lib.rs
1//! A small crate to generate a 3D mesh from a 2D heightmap.
2//!
3//! ```
4//! use height_mesh::ndshape::{ConstShape, ConstShape2u32};
5//! use height_mesh::{height_mesh, HeightMeshBuffer};
6//!
7//! // A 64^2 chunk with 1-voxel boundary padding.
8//! type ChunkShape = ConstShape2u32<66, 66>;
9//!
10//! // This chunk will cover just a single quadrant of a parabola.
11//! let mut sdf = [1.0; ChunkShape::SIZE as usize];
12//! for i in 0u32..ChunkShape::SIZE {
13//! let [x, y] = ChunkShape::delinearize(i);
14//! sdf[i as usize] = ((x * x + y * y) as f32).sqrt();
15//! }
16//!
17//! let mut buffer = HeightMeshBuffer::default();
18//! height_mesh(&sdf, &ChunkShape {}, [0; 2], [65; 2], &mut buffer);
19//!
20//! // Some triangles were generated.
21//! assert!(!buffer.indices.is_empty());
22//! ```
23
24pub use ndshape;
25
26use ndshape::Shape;
27
28/// The output buffers used by [`height_mesh`]. These buffers can be reused to avoid reallocating memory.
29#[derive(Default)]
30pub struct HeightMeshBuffer {
31 /// The surface positions.
32 pub positions: Vec<[f32; 3]>,
33 /// The surface normals.
34 ///
35 /// The normals are **not** normalized, since that is done most efficiently on the GPU.
36 pub normals: Vec<[f32; 3]>,
37 /// Triangle indices, referring to offsets in the `positions` and `normals` vectors.
38 pub indices: Vec<u32>,
39 /// Used to map back from pixel stride to vertex index.
40 pub stride_to_index: Vec<u32>,
41}
42
43impl HeightMeshBuffer {
44 /// Clears all of the buffers, but keeps the memory allocated for reuse.
45 pub fn reset(&mut self, array_size: usize) {
46 self.positions.clear();
47 self.normals.clear();
48 self.indices.clear();
49
50 // Just make sure this buffer is long enough, whether or not we've used it before.
51 self.stride_to_index.resize(array_size, 0);
52 }
53}
54
55/// Generates a mesh with a vertex at each point on the interior of `[min, max]`.
56///
57/// The generated vertices are of the form `[x, height, z]` where `height` is taken directly from `height_map`.
58///
59/// Surface normals are estimated using central differencing, which requires each vertex to have a complete Von Neumann
60/// neighborhood. This means that points on the boundary are not eligible as mesh vertices, but they are still required.
61///
62/// This is illustrated in the ASCII art below, where "b" is a boundary point and "i" is an interior point. Line segments denote
63/// the edges of the mesh.
64///
65/// ```text
66/// b b b b
67///
68/// b i - i b
69/// | / |
70/// b i - i b
71///
72/// b b b b
73/// ```
74pub fn height_mesh<S: Shape<u32, 2>>(
75 height_map: &[f32],
76 map_shape: &S,
77 min: [u32; 2],
78 max: [u32; 2],
79 output: &mut HeightMeshBuffer,
80) {
81 // SAFETY
82 // Check the bounds on the array before we start using get_unchecked.
83 assert!((map_shape.linearize(min) as usize) < height_map.len());
84 assert!((map_shape.linearize(max) as usize) < height_map.len());
85
86 output.reset(height_map.len());
87
88 let [minx, miny] = min;
89 let [maxx, maxy] = max;
90
91 // Avoid accessing out of bounds with a 3x3x3 kernel.
92 let iminx = minx + 1;
93 let iminy = miny + 1;
94 let imaxx = maxx - 1;
95 let imaxy = maxy - 1;
96
97 let x_stride = map_shape.linearize([1, 0]);
98 let y_stride = map_shape.linearize([0, 1]);
99
100 // Note: Although we use (x, y) for the coordinates of the height map, these should be considered (x, z) in world
101 // coordinates, because +Y is the UP vector.
102 for z in iminy..=imaxy {
103 for x in iminx..=imaxx {
104 let stride = map_shape.linearize([x, z]);
105 let y = height_map[stride as usize];
106
107 output.stride_to_index[stride as usize] = output.positions.len() as u32;
108 output.positions.push([x as f32, y, z as f32]);
109
110 // Use central differencing to calculate the surface normal.
111 //
112 // From calculus, we know that gradients are always orthogonal to a level set. The surface approximated by the
113 // height map h(x, z) happens to be the 0 level set of the function:
114 //
115 // f(x, y, z) = y - h(x, z)
116 //
117 // And the gradient is:
118 //
119 // grad f = [-dh/dx, 1, -dh/dz]
120 let l_stride = stride - x_stride;
121 let r_stride = stride + x_stride;
122 let b_stride = stride - y_stride;
123 let t_stride = stride + y_stride;
124 let l_y = unsafe { height_map.get_unchecked(l_stride as usize) };
125 let r_y = unsafe { height_map.get_unchecked(r_stride as usize) };
126 let b_y = unsafe { height_map.get_unchecked(b_stride as usize) };
127 let t_y = unsafe { height_map.get_unchecked(t_stride as usize) };
128 let dy_dx = (r_y - l_y) / 2.0;
129 let dy_dz = (t_y - b_y) / 2.0;
130 // Not normalized, because that's done more efficiently on the GPU.
131 output.normals.push([-dy_dx, 1.0, -dy_dz]);
132 }
133 }
134
135 // Only add a quad when p is the bottom-left corner of a quad that fits in the interior.
136 let imaxx = imaxx - 1;
137 let imaxy = imaxy - 1;
138
139 for z in iminy..=imaxy {
140 for x in iminx..=imaxx {
141 let bl_stride = map_shape.linearize([x, z]);
142 let br_stride = bl_stride + x_stride;
143 let tl_stride = bl_stride + y_stride;
144 let tr_stride = bl_stride + x_stride + y_stride;
145
146 let bl_index = output.stride_to_index[bl_stride as usize];
147 let br_index = output.stride_to_index[br_stride as usize];
148 let tl_index = output.stride_to_index[tl_stride as usize];
149 let tr_index = output.stride_to_index[tr_stride as usize];
150
151 output
152 .indices
153 .extend_from_slice(&[bl_index, tl_index, tr_index, bl_index, tr_index, br_index]);
154 }
155 }
156}