Use Perlin noise

@@ -1,8 +1,18 @@
1- use std::ops::{Add, Div};
2  
3  #[derive(Debug, Copy, Clone)]
4  pub(crate) struct Vec2(pub(crate) f32, pub(crate) f32);
5  
 
 
 
 
 
 
 
 
 
 
6  impl Div<f32> for Vec2 {
7      type Output = Vec2;
8  
@@ -11,6 +21,14 @@
11      }
12  }
13  
 
 
 
 
 
 
 
 
14  #[derive(Debug, Copy, Clone)]
15  pub(crate) struct Vec3(pub(crate) f32, pub(crate) f32, pub(crate) f32);
16  
@@ -130,6 +148,53 @@
130              a, b
131          );
132      }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
133  }
134  
135  pub(crate) fn interpolate(value_a: f32, value_b: f32, t: f32) -> f32 {

@@ -1,8 +1,18 @@
1+ use std::ops::{Add, Div, Sub};
2  
3  #[derive(Debug, Copy, Clone)]
4  pub(crate) struct Vec2(pub(crate) f32, pub(crate) f32);
5  
6+ impl Vec2 {
7+     pub(crate) fn from_angle(angle: f32) -> Self {
8+         Self(angle.cos(), angle.sin())
9+     }
10+ 
11+     pub(crate) fn dot(&self, rhs: &Vec2) -> f32 {
12+         self.0 * rhs.0 + self.1 * rhs.1
13+     }
14+ }
15+ 
16  impl Div<f32> for Vec2 {
17      type Output = Vec2;
18  
@@ -11,6 +21,14 @@
21      }
22  }
23  
24+ impl Sub<Vec2> for Vec2 {
25+     type Output = Vec2;
26+ 
27+     fn sub(self, rhs: Vec2) -> Self::Output {
28+         Vec2(self.0 - rhs.0, self.1 - rhs.1)
29+     }
30+ }
31+ 
32  #[derive(Debug, Copy, Clone)]
33  pub(crate) struct Vec3(pub(crate) f32, pub(crate) f32, pub(crate) f32);
34  
@@ -130,6 +148,53 @@
148              a, b
149          );
150      }
151+ 
152+     #[test]
153+     fn check_distribution_of_random_f32s() {
154+         const NUM_EXAMPLES: u32 = 10_000;
155+         const NUM_BUCKETS: u32 = 10;
156+         const EXPECTED_BUCKET_COUNT: u32 = NUM_EXAMPLES / NUM_BUCKETS;
157+         const MAX_ALLOWED_DEVIATION: u32 = 100;
158+ 
159+         let mut buckets = [0; NUM_BUCKETS as usize];
160+         let mut rng = RandomNumberGenerator::with_seed(314159);
161+ 
162+         for _ in 0..NUM_EXAMPLES {
163+             let value = rng.gen_f32();
164+             let i = (value / 0.1) as usize;
165+             buckets[i] += 1;
166+         }
167+ 
168+         for count in buckets.iter() {
169+             assert!((*count - EXPECTED_BUCKET_COUNT as i32).unsigned_abs() < MAX_ALLOWED_DEVIATION);
170+         }
171+     }
172+ 
173+     #[test]
174+     fn create_vec2_from_angle() {
175+         let examples = [
176+             (0.0, Vec2(1.0, 0.0)),
177+             (PI, Vec2(-1.0, 0.0)),
178+             (2.0 * PI, Vec2(1.0, 0.0)),
179+             (FRAC_PI_2, Vec2(0.0, 1.0)),
180+             (FRAC_PI_3, Vec2(0.5, 0.866025)),
181+         ];
182+ 
183+         for (angle, expected) in examples.into_iter() {
184+             let actual = Vec2::from_angle(angle);
185+             assert_vec2s_equal(&actual, &expected);
186+         }
187+     }
188+ 
189+     fn assert_vec2s_equal(a: &Vec2, b: &Vec2) {
190+         const TOLERANCE: f32 = 0.00001;
191+         let vecs_equal = (a.0 - b.0).abs() < TOLERANCE && (a.1 - b.1).abs() < TOLERANCE;
192+         assert!(
193+             vecs_equal,
194+             "vecs are not equal:\n  left: {:?}\n right: {:?}\n",
195+             a, b
196+         );
197+     }
198  }
199  
200  pub(crate) fn interpolate(value_a: f32, value_b: f32, t: f32) -> f32 {

@@ -119,14 +119,18 @@
119  
120              const TEXTURE_WIDTH: usize = 8;
121              const TEXTURE_HEIGHT: usize = 8;
 
122              const VALUES_PER_PIXEL: usize = 3;
123-             const TEXTURE_SIZE: usize = TEXTURE_WIDTH * TEXTURE_HEIGHT * VALUES_PER_PIXEL;
124  
125              let mut rng = RandomNumberGenerator::with_seed(42);
126-             let mut data: Vec<u8> = Vec::with_capacity(TEXTURE_SIZE);
127  
128-             for _ in 0..TEXTURE_SIZE {
129-                 data.push(rng.gen_range(120, 180) as u8);
 
 
 
130              }
131  
132              gl::TexImage2D(
@@ -138,7 +142,7 @@
138                  0,
139                  gl::RGB,
140                  gl::UNSIGNED_BYTE,
141-                 data.as_ptr() as *const c_void,
142              );
143              gl::TexParameteri(gl::TEXTURE_2D, gl::TEXTURE_MAG_FILTER, gl::NEAREST as GLint);
144              gl::TexParameteri(
@@ -337,7 +341,6 @@
337          program.set_uniform_f32("camera_pitch", &camera.pitch());
338  
339          let mut program = self.activate_skybox_program();
340-         program.set_uniform_vec3("camera_position", camera.position());
341          program.set_uniform_f32("camera_heading", &camera.heading());
342          program.set_uniform_f32("camera_pitch", &camera.pitch());
343      }

@@ -119,14 +119,18 @@
119  
120              const TEXTURE_WIDTH: usize = 8;
121              const TEXTURE_HEIGHT: usize = 8;
122+             const NUM_PIXELS: usize = TEXTURE_WIDTH * TEXTURE_HEIGHT;
123              const VALUES_PER_PIXEL: usize = 3;
124+             const TEXTURE_SIZE: usize = NUM_PIXELS * VALUES_PER_PIXEL;
125  
126              let mut rng = RandomNumberGenerator::with_seed(42);
127+             let mut texture: Vec<u8> = Vec::with_capacity(TEXTURE_SIZE);
128  
129+             for _ in 0..NUM_PIXELS {
130+                 let value = rng.gen_range(50, 200) as u8;
131+                 texture.push(value);
132+                 texture.push(value);
133+                 texture.push(value);
134              }
135  
136              gl::TexImage2D(
@@ -138,7 +142,7 @@
142                  0,
143                  gl::RGB,
144                  gl::UNSIGNED_BYTE,
145+                 texture.as_ptr() as *const c_void,
146              );
147              gl::TexParameteri(gl::TEXTURE_2D, gl::TEXTURE_MAG_FILTER, gl::NEAREST as GLint);
148              gl::TexParameteri(
@@ -337,7 +341,6 @@
341          program.set_uniform_f32("camera_pitch", &camera.pitch());
342  
343          let mut program = self.activate_skybox_program();
 
344          program.set_uniform_f32("camera_heading", &camera.heading());
345          program.set_uniform_f32("camera_pitch", &camera.pitch());
346      }

@@ -148,29 +148,64 @@
148  }
149  
150  /// Describes how elevation varies across the x-z plane.
 
 
 
 
151  struct Heightmap {
152      cell_size: f32,
153      num_x_cells: u32,
154      num_z_cells: u32,
155-     heights: Vec<f32>,
156  }
157  
158  impl Heightmap {
 
159      fn new(cell_size: f32, num_x_cells: u32, num_z_cells: u32) -> Self {
160          let mut rng = RandomNumberGenerator::with_seed(32131);
161  
162          let num_values = ((num_z_cells + 1) * (num_x_cells + 1)) as usize;
163-         let mut heights = Vec::with_capacity(num_values);
164  
165          for _ in 0..num_values {
166-             heights.push(rng.gen_f32());
 
167          }
168  
169          Self {
170              cell_size,
171              num_x_cells,
172              num_z_cells,
173-             heights,
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
174          }
175      }
176  
@@ -192,7 +227,8 @@
192          let x0_height = math::interpolate(x0z0_height, x0z1_height, z_frac);
193          let x1_height = math::interpolate(x1z0_height, x1z1_height, z_frac);
194  
195-         math::interpolate(x0_height, x1_height, x_frac)
 
196      }
197  
198      fn is_out_of_range(&self, xz_position: &Vec2) -> bool {
@@ -223,27 +259,59 @@
223  
224      fn height_at_x0z0(&self, normalized_position: &Vec2) -> f32 {
225          let Vec2(x, z) = *normalized_position;
226-         self.height_at_index(x as usize, z as usize)
 
 
 
 
 
 
 
 
227      }
228  
229      fn height_at_x1z0(&self, normalized_position: &Vec2) -> f32 {
230          let Vec2(x, z) = *normalized_position;
231-         self.height_at_index((x as usize) + 1, z as usize)
 
 
 
 
 
 
 
 
232      }
233  
234      fn height_at_x0z1(&self, normalized_position: &Vec2) -> f32 {
235          let Vec2(x, z) = *normalized_position;
236-         self.height_at_index(x as usize, (z as usize) + 1)
 
 
 
 
 
 
 
 
237      }
238  
239      fn height_at_x1z1(&self, normalized_position: &Vec2) -> f32 {
240          let Vec2(x, z) = *normalized_position;
241-         self.height_at_index(x as usize + 1, z as usize + 1)
 
 
 
 
 
 
 
 
242      }
243  
244-     fn height_at_index(&self, xi: usize, zi: usize) -> f32 {
245          let i = zi * self.num_x_cells as usize + xi;
246-         self.heights[i]
247      }
248  }
249  
@@ -255,3 +323,88 @@
255          Vec3(x as f32 + 0.5, y as f32 + 0.5, z as f32 + 0.5)
256      }
257  }

@@ -148,29 +148,64 @@
148  }
149  
150  /// Describes how elevation varies across the x-z plane.
151+ ///
152+ /// For now, the heightmap works on local coordinates from 0..CHUNK_SIDE_LENGTH on the X and Z
153+ /// axis. The returned height must be within 0..CHUNK_SIDE_LENGTH.
154+ #[derive(Debug)]
155  struct Heightmap {
156      cell_size: f32,
157      num_x_cells: u32,
158      num_z_cells: u32,
159+     gradients: Vec<Vec2>,
160  }
161  
162  impl Heightmap {
163+     /// Constructs a Perlin noise grid with random gradients.
164      fn new(cell_size: f32, num_x_cells: u32, num_z_cells: u32) -> Self {
165          let mut rng = RandomNumberGenerator::with_seed(32131);
166  
167          let num_values = ((num_z_cells + 1) * (num_x_cells + 1)) as usize;
168+         let mut gradients = Vec::with_capacity(num_values);
169  
170          for _ in 0..num_values {
171+             let angle = rng.gen_f32() * std::f32::consts::PI * 2.0;
172+             gradients.push(Vec2::from_angle(angle));
173          }
174  
175          Self {
176              cell_size,
177              num_x_cells,
178              num_z_cells,
179+             gradients,
180+         }
181+     }
182+ 
183+     /// Constructs a Perlin noise grid with the given gradients.
184+     ///
185+     /// The number of gradients must match the number of corners in the Perlin grid. The first
186+     /// gradient is used for x_min / z_min in the grid. The next gradient moves along the x-axis
187+     /// first until it reaches x_max, then it moves onto the next row in the z axis. This function
188+     /// asserts that enough gradients are given to fit all of the grid corners.
189+     #[cfg(test)]
190+     fn with_gradients(
191+         gradients: Vec<Vec2>,
192+         cell_size: f32,
193+         num_x_cells: u32,
194+         num_z_cells: u32,
195+     ) -> Self {
196+         let expected_num_gradients = (num_x_cells + 1) * (num_z_cells + 1);
197+ 
198+         assert_eq!(
199+             gradients.len(),
200+             expected_num_gradients as usize,
201+             "wrong number of gradients for heightmap"
202+         );
203+ 
204+         Self {
205+             cell_size,
206+             num_x_cells,
207+             num_z_cells,
208+             gradients,
209          }
210      }
211  
@@ -192,7 +227,8 @@
227          let x0_height = math::interpolate(x0z0_height, x0z1_height, z_frac);
228          let x1_height = math::interpolate(x1z0_height, x1z1_height, z_frac);
229  
230+         let height = math::interpolate(x0_height, x1_height, x_frac);
231+         (height + 1.0) * 0.5
232      }
233  
234      fn is_out_of_range(&self, xz_position: &Vec2) -> bool {
@@ -223,27 +259,59 @@
259  
260      fn height_at_x0z0(&self, normalized_position: &Vec2) -> f32 {
261          let Vec2(x, z) = *normalized_position;
262+ 
263+         let xi = x as usize;
264+         let zi = z as usize;
265+ 
266+         let corner_position = Vec2(xi as f32, zi as f32);
267+         let gradient = self.gradient_at_index(xi, zi);
268+ 
269+         let offset = *normalized_position - corner_position;
270+         gradient.dot(&offset)
271      }
272  
273      fn height_at_x1z0(&self, normalized_position: &Vec2) -> f32 {
274          let Vec2(x, z) = *normalized_position;
275+ 
276+         let xi = x as usize + 1;
277+         let zi = z as usize;
278+ 
279+         let corner_position = Vec2(xi as f32, zi as f32);
280+         let gradient = self.gradient_at_index(xi, zi);
281+ 
282+         let offset = *normalized_position - corner_position;
283+         gradient.dot(&offset)
284      }
285  
286      fn height_at_x0z1(&self, normalized_position: &Vec2) -> f32 {
287          let Vec2(x, z) = *normalized_position;
288+ 
289+         let xi = x as usize;
290+         let zi = z as usize + 1;
291+ 
292+         let corner_position = Vec2(xi as f32, zi as f32);
293+         let gradient = self.gradient_at_index(xi, zi);
294+ 
295+         let offset = *normalized_position - corner_position;
296+         gradient.dot(&offset)
297      }
298  
299      fn height_at_x1z1(&self, normalized_position: &Vec2) -> f32 {
300          let Vec2(x, z) = *normalized_position;
301+ 
302+         let xi = x as usize + 1;
303+         let zi = z as usize + 1;
304+ 
305+         let corner_position = Vec2(xi as f32, zi as f32);
306+         let gradient = self.gradient_at_index(xi, zi);
307+ 
308+         let offset = *normalized_position - corner_position;
309+         gradient.dot(&offset)
310      }
311  
312+     fn gradient_at_index(&self, xi: usize, zi: usize) -> Vec2 {
313          let i = zi * self.num_x_cells as usize + xi;
314+         self.gradients[i]
315      }
316  }
317  
@@ -255,3 +323,88 @@
323          Vec3(x as f32 + 0.5, y as f32 + 0.5, z as f32 + 0.5)
324      }
325  }
326+ 
327+ #[cfg(test)]
328+ mod tests {
329+     use std::f32::consts::*;
330+ 
331+     use super::*;
332+ 
333+     #[test]
334+     fn perlin_noise_single_grid_cell() {
335+         // Create a 2D Perlin noise grid with one cell and four gradients (one for each corner). In
336+         // this example, all gradients are unit vectors that point along either the X or Z axis.
337+         let gradients = vec![
338+             Vec2::from_angle(0.0),
339+             Vec2::from_angle(-PI),
340+             Vec2::from_angle(FRAC_PI_2),
341+             Vec2::from_angle(-FRAC_PI_2),
342+         ];
343+ 
344+         let heightmap = Heightmap::with_gradients(gradients, 1.0, 1, 1);
345+ 
346+         let examples = [
347+             // Always zero at the grid corner
348+             (Vec2(0.0, 0.0), 0.0),
349+             // Halfway between two corners on X axis, both with gradients facing inward (max strength)
350+             (Vec2(0.5, 0.0), 0.5),
351+             // Strength drops as approaching either corner. Should drop equally on both sides.
352+             (Vec2(0.25, 0.0), 0.375),
353+             (Vec2(0.75, 0.0), 0.375),
354+             // Along the Z axis, gradient faces away so should be negative
355+             (Vec2(0.0, 0.5), -0.25),
356+             (Vec2(0.0, 0.25), -0.1875),
357+             (Vec2(0.0, 0.75), -0.1875),
358+             // In the middle. The two gradients along Z=0 contribute 0.5, and the two gradients at
359+             // Z=1 are facing opposite directions and cancel each other out (so 0.0), which results
360+             // in an interpolated value of 0.25.
361+             (Vec2(0.5, 0.5), 0.25),
362+         ];
363+ 
364+         for (position, expected) in examples.into_iter() {
365+             let actual = heightmap.height_at(&position);
366+ 
367+             assert!((actual - expected).abs() < 0.00001);
368+         }
369+     }
370+ 
371+     #[test]
372+     fn perlin_noise_varying_cell_size() {
373+         let small_cell_heightmap = Heightmap::new(1.0, 2, 2);
374+         let big_cell_heightmap = Heightmap::new(16.0, 2, 2);
375+ 
376+         // Positions for the small cell and big cell heightmaps. The left and right values should
377+         // return the same height value since they're in the same spot relative to the size of the
378+         // grid.
379+         let examples = [
380+             (Vec2(0.0, 0.0), Vec2(0.0, 0.0)),
381+             (Vec2(1.5, 0.5), Vec2(24.0, 8.0)),
382+             (Vec2(1.0, 1.0), Vec2(16.0, 16.0)),
383+         ];
384+ 
385+         for (small_position, big_position) in examples.into_iter() {
386+             let small_cell_height = small_cell_heightmap.height_at(&small_position);
387+             let big_cell_height = big_cell_heightmap.height_at(&big_position);
388+ 
389+             assert_eq!(small_cell_height, big_cell_height);
390+         }
391+     }
392+ 
393+     #[test]
394+     fn perlin_noise_outside_of_cell_range() {
395+         let heightmap = Heightmap::new(16.0, 2, 2);
396+ 
397+         // Positions outside of the grid range should return 0.0 height.
398+         let examples = [
399+             Vec2(-0.0001, 0.0),
400+             Vec2(32.0, 32.0),
401+             Vec2(32.0, 0.0),
402+             Vec2(16.0, 32.0),
403+             Vec2(-0.0001, 10.0),
404+         ];
405+ 
406+         for position in examples.into_iter() {
407+             assert_eq!(heightmap.height_at(&position), 0.0);
408+         }
409+     }
410+ }