1use std::mem::MaybeUninit;
2
3use simply_simd::{Arch, Simd, enable_targets};
4
5use crate::api::grid::interface::GridNoiseParams;
6use crate::noise::combiners::{Combiner, CombinerState};
7use crate::noise::util::constants::{BYTE_SHUFFLE, CELLULAR_EXP_MASK, HASH_MASK, HASH_PRIME};
8use crate::noise::util::grid_data::{GridData, Lerp};
9use crate::noise::util::grid_helpers::{
10 Arena, ArenaBuffer, MaybeUninitSliceSimdExt, maybe_tail_load, maybe_tail_store, pad_grid_size,
11 validate_grid_size, validate_state_size,
12};
13use crate::{Cellular, GridGenerator};
14
15const LERP: u8 = Lerp::Quintic as u8;
16
17const NEIGHBORS_12: [(i32, i32); 12] = [
24 (0, 0),
25 (1, 0),
26 (0, 1),
27 (1, 1),
28 (-1, 0),
29 (-1, 1),
30 (0, -1),
31 (1, -1),
32 (2, 0),
33 (2, 1),
34 (0, 2),
35 (1, 2),
36];
37
38struct RowWindow {
39 top: *mut f32,
40 sec: *mut f32,
41 thi: *mut f32,
42 bot: *mut f32,
43 width: usize,
44}
45
46impl RowWindow {
47 fn new(arena: &mut Arena, width: usize) -> Self {
48 Self {
49 top: arena.allocate::<f32>(width * 2).as_mut_ptr().cast(),
50 sec: arena.allocate::<f32>(width * 2).as_mut_ptr().cast(),
51 thi: arena.allocate::<f32>(width * 2).as_mut_ptr().cast(),
52 bot: arena.allocate::<f32>(width * 2).as_mut_ptr().cast(),
53 width,
54 }
55 }
56
57 #[inline(always)]
58 fn fill_row<A: Arch>(
59 params: &GridNoiseParams<2>,
60 grid_data: &GridData<2>,
61 buff: &mut [(f32, f32)],
62 cy: i32,
63 cx_start: i32,
64 ) {
65 let cy = grid_data.octave_tiling[1].map_or(cy, |t| cy.rem_euclid(t as i32));
66 let y_shuf = hash_cell_y::<A>(cy as u32, params.seed);
67 let y_shuf_v = Simd::<u32, A>::splat(y_shuf);
68 let lanes = Simd::<f32, A>::LANES;
69
70 let mut x_it = 0;
71 while x_it + lanes <= buff.len() {
72 let cx_base = cx_start.wrapping_add(x_it as i32);
73 let cx_v = Simd::<i32, A>::splat(cx_base) + Simd::<i32, A>::iota(0);
74 let cx_v = if let Some(t) = grid_data.octave_tiling[0] {
75 simd_rem_euclid_i32::<A>(cx_v, t as i32)
76 } else {
77 cx_v
78 };
79 let hashes = hash_cells_row::<A>(cx_v.raw_cast(), y_shuf_v, params.seed);
80 let (tx, ty) = split_hash_batch::<A>(hashes);
81 let tx_arr = tx.to_array();
82 let ty_arr = ty.to_array();
83 for i in 0..lanes {
84 buff[x_it + i] = (tx_arr[i], ty_arr[i]);
85 }
86 x_it += lanes;
87 }
88 for i in x_it..buff.len() {
89 let cx = cx_start.wrapping_add(i as i32);
90 let cx = grid_data.octave_tiling[0].map_or(cx, |t| cx.rem_euclid(t as i32));
91 buff[i] = split_hash(hash_cell_with_y::<A>(cx as u32, y_shuf, params.seed));
92 }
93 }
94
95 fn top(&self) -> &[(f32, f32)] {
96 unsafe { std::slice::from_raw_parts(self.top.cast::<(f32, f32)>(), self.width) }
97 }
98
99 fn sec(&self) -> &[(f32, f32)] {
100 unsafe { std::slice::from_raw_parts(self.sec.cast::<(f32, f32)>(), self.width) }
101 }
102
103 fn thi(&self) -> &[(f32, f32)] {
104 unsafe { std::slice::from_raw_parts(self.thi.cast::<(f32, f32)>(), self.width) }
105 }
106
107 fn bot(&self) -> &[(f32, f32)] {
108 unsafe { std::slice::from_raw_parts(self.bot.cast::<(f32, f32)>(), self.width) }
109 }
110
111 fn top_mut(&mut self) -> &mut [(f32, f32)] {
112 unsafe { std::slice::from_raw_parts_mut(self.top.cast::<(f32, f32)>(), self.width) }
113 }
114
115 fn sec_mut(&mut self) -> &mut [(f32, f32)] {
116 unsafe { std::slice::from_raw_parts_mut(self.sec.cast::<(f32, f32)>(), self.width) }
117 }
118
119 fn thi_mut(&mut self) -> &mut [(f32, f32)] {
120 unsafe { std::slice::from_raw_parts_mut(self.thi.cast::<(f32, f32)>(), self.width) }
121 }
122
123 fn bot_mut(&mut self) -> &mut [(f32, f32)] {
124 unsafe { std::slice::from_raw_parts_mut(self.bot.cast::<(f32, f32)>(), self.width) }
125 }
126
127 #[inline(always)]
128 fn swap(&mut self) {
129 let tmp = self.top;
130 self.top = self.sec;
131 self.sec = self.thi;
132 self.thi = self.bot;
133 self.bot = tmp;
134 }
135}
136
137#[inline(always)]
138pub(super) fn hash_cell<A: Arch>(x: u32, y: u32, seed: u32) -> u32 {
139 hash_cell_with_y::<A>(x, hash_cell_y::<A>(y, seed), seed)
140}
141
142#[inline(always)]
145fn hash_cells_row<A: Arch>(cx_v: Simd<u32, A>, y_shuf: Simd<u32, A>, seed: u32) -> Simd<u32, A> {
146 let shuffle_indices = unsafe { Simd::<u8, A>::from_slice_unchecked(&BYTE_SHUFFLE[..]) };
147 let prime = Simd::<u32, A>::splat(HASH_PRIME);
148 let seed_v = Simd::<u32, A>::splat(seed);
149
150 let x_shuf = (cx_v * seed_v).permute_8(shuffle_indices) ^ prime;
151 (x_shuf * y_shuf) ^ x_shuf
152}
153
154#[inline(always)]
155fn hash_cell_y<A: Arch>(y: u32, seed: u32) -> u32 {
156 let shuffle_indices = unsafe { Simd::<u8, A>::from_slice_unchecked(&BYTE_SHUFFLE[..]) };
157 let prime = Simd::<u32, A>::splat(HASH_PRIME);
158 (Simd::<u32, A>::splat(y.wrapping_mul(seed)).permute_8(shuffle_indices) ^ prime).to_array()[0]
159}
160
161#[inline(always)]
162fn hash_cell_with_y<A: Arch>(x: u32, y_shuf: u32, seed: u32) -> u32 {
163 let shuffle_indices = unsafe { Simd::<u8, A>::from_slice_unchecked(&BYTE_SHUFFLE[..]) };
164 let prime = Simd::<u32, A>::splat(HASH_PRIME);
165 let x_shuf = (Simd::<u32, A>::splat(x.wrapping_mul(seed)).permute_8(shuffle_indices) ^ prime)
166 .to_array()[0];
167 x_shuf.wrapping_mul(y_shuf) ^ x_shuf
168}
169
170#[inline(always)]
174pub(super) fn split_hash(hash: u32) -> (f32, f32) {
175 let exp_bits = CELLULAR_EXP_MASK;
176 let hash_mask = HASH_MASK;
177 let tx = 1.5 - f32::from_bits((hash & hash_mask) | exp_bits);
178 let ty = 1.5 - f32::from_bits((hash >> 9) | exp_bits);
179 (tx, ty)
180}
181
182#[inline(always)]
183fn split_hash_batch<A: Arch>(hash: Simd<u32, A>) -> (Simd<f32, A>, Simd<f32, A>) {
184 let exp_bits = Simd::<u32, A>::splat(0x3f800000);
185 let hash_mask = Simd::<u32, A>::splat(0x007fffff);
186 let one_halves = Simd::<f32, A>::splat(1.5);
187
188 let tx = one_halves - ((hash & hash_mask) | exp_bits).raw_cast::<f32>();
189 let ty = one_halves - ((hash >> Simd::<u32, A>::splat(9)) | exp_bits).raw_cast::<f32>();
190 (tx, ty)
191}
192
193#[inline(always)]
194fn simd_rem_euclid_i32<A: Arch>(x: Simd<i32, A>, t: i32) -> Simd<i32, A> {
195 let t_f = Simd::<f32, A>::splat(t as f32);
196 let x_f = x.cast_float();
197 (x_f - (x_f / t_f).floor() * t_f).cast_int_trunc()
198}
199
200struct CellJitters {
203 parts: *mut MaybeUninit<f32>,
204}
205
206impl CellJitters {
207 fn new(arena: &mut Arena) -> Self {
208 Self {
209 parts: arena.allocate(24).as_mut_ptr(),
210 }
211 }
212
213 #[inline(always)]
214 fn write<A: Arch>(
215 &mut self,
216 top: &[(f32, f32)],
217 sec: &[(f32, f32)],
218 thi: &[(f32, f32)],
219 bot: &[(f32, f32)],
220 x_it: usize,
221 ) {
222 for (i, &(ox, oy)) in NEIGHBORS_12.iter().enumerate() {
223 let row: &[(f32, f32)] = match oy {
224 -1 => top,
225 0 => sec,
226 1 => thi,
227 2 => bot,
228 _ => unreachable!(),
229 };
230 let (jx, jy) = row[x_it + ((ox + 1) as usize)];
231 unsafe {
232 self.parts
233 .add(i * 2)
234 .write(MaybeUninit::new(jx + (ox as f32)));
235 self.parts
236 .add(i * 2 + 1)
237 .write(MaybeUninit::new(jy + (oy as f32)));
238 }
239 }
240 }
241}
242
243#[enable_targets(A)]
244impl GridGenerator<2> for Cellular {
245 fn sample_grid<A: Arch, C: Combiner, const INIT: bool, const FINAL: bool>(
246 params: GridNoiseParams<2>,
247 combiner: C::Config,
248 state: &mut [f32],
249 dst: &mut [f32],
250 ) {
251 validate_grid_size(params.grid_size, dst.len());
252 validate_state_size::<C, A, _>(params.grid_size, state.len());
253 let padded_size = pad_grid_size::<A, _>(params.grid_size);
254
255 let required_cache =
256 padded_size[1] * 3 + padded_size[0] * 3 + (padded_size[0] + 1) * 8 + 24;
257 let mut cache = ArenaBuffer::<A>::with_capacity(required_cache);
258 let mut arena = Arena::with_cache(&mut cache);
259 let mut sub_arena = arena.allocate_arena(padded_size[0] * 3 + padded_size[1] * 3);
260
261 let grid_data = GridData::new::<A, LERP>(¶ms, &mut sub_arena, &padded_size);
262
263 let row_len = grid_data.num_loops[0] + 3;
264 let mut window = RowWindow::new(&mut arena, row_len);
265 let mut cell_jitters = CellJitters::new(&mut arena);
266
267 let cx_offset = grid_data.grid_start[0] - 1;
269 RowWindow::fill_row::<A>(
270 ¶ms,
271 &grid_data,
272 window.top_mut(),
273 grid_data.grid_start[1] - 1,
274 cx_offset,
275 );
276 RowWindow::fill_row::<A>(
277 ¶ms,
278 &grid_data,
279 window.sec_mut(),
280 grid_data.grid_start[1],
281 cx_offset,
282 );
283 RowWindow::fill_row::<A>(
284 ¶ms,
285 &grid_data,
286 window.thi_mut(),
287 grid_data.grid_start[1] + 1,
288 cx_offset,
289 );
290 RowWindow::fill_row::<A>(
291 ¶ms,
292 &grid_data,
293 window.bot_mut(),
294 grid_data.grid_start[1] + 2,
295 cx_offset,
296 );
297
298 let mut y_idx = 0;
299 for y_it in 0..grid_data.num_loops[1] {
300 let y_next_idx =
301 unsafe { grid_data.grid_indices[1].get_unchecked(y_it).assume_init() as usize };
302
303 let mut x_idx = 0;
304 for x_it in 0..grid_data.num_loops[0] {
305 let x_next_idx =
306 unsafe { grid_data.grid_indices[0].get_unchecked(x_it).assume_init() as usize };
307
308 cell_jitters.write::<A>(
309 window.top(),
310 window.sec(),
311 window.thi(),
312 window.bot(),
313 x_it,
314 );
315
316 grid_cellular_fill::<A, C, INIT, FINAL>(
317 &grid_data,
318 &cell_jitters,
319 x_idx,
320 x_next_idx,
321 y_idx,
322 y_next_idx,
323 dst,
324 state,
325 &combiner,
326 );
327
328 x_idx = x_next_idx;
329 }
330
331 window.swap();
333
334 RowWindow::fill_row::<A>(
336 ¶ms,
337 &grid_data,
338 window.bot_mut(),
339 grid_data.grid_start[1] + (y_it as i32) + 3,
340 cx_offset,
341 );
342
343 y_idx = y_next_idx;
344 }
345 }
346}
347
348#[inline(always)]
349fn grid_cellular_fill<A: Arch, C: Combiner, const INIT: bool, const FINAL: bool>(
350 grid_data: &GridData<2>,
351 jit: &CellJitters,
352 x_idx: usize,
353 x_next: usize,
354 y_idx: usize,
355 y_next: usize,
356 dst: &mut [f32],
357 state: &mut [f32],
358 combiner_config: &C::Config,
359) {
360 let lanes = Simd::<f32, A>::LANES;
361 let row_width = grid_data.grid_size[0];
362
363 let weight_vec = Simd::<f32, A>::splat(grid_data.weight);
364
365 for y in y_idx..y_next {
366 let sy = unsafe { grid_data.distances[1].get_unchecked(y).assume_init() };
367 let row_start = y * row_width;
368
369 let mut dysq: [MaybeUninit<Simd<f32, A>>; 12] =
372 std::array::from_fn(|_| MaybeUninit::uninit());
373 for c in 0..12 {
374 let jy = unsafe { (*jit.parts.add(c * 2 + 1)).assume_init() };
375 let dy_sq = (Simd::<f32, A>::splat(sy) - Simd::<f32, A>::splat(jy))
376 * (Simd::<f32, A>::splat(sy) - Simd::<f32, A>::splat(jy));
377 dysq[c].write(dy_sq);
378 }
379 let dysq = &dysq;
380
381 let mut index = x_idx;
382 while index + lanes <= x_next {
383 grid_cellular_fill_block::<A, C, INIT, FINAL, false>(
384 grid_data,
385 jit,
386 &dysq,
387 weight_vec,
388 sy,
389 row_start,
390 x_next,
391 index,
392 dst,
393 state,
394 combiner_config,
395 );
396 index += lanes;
397 }
398 if index < x_next {
399 grid_cellular_fill_block::<A, C, INIT, FINAL, true>(
400 grid_data,
401 jit,
402 &dysq,
403 weight_vec,
404 sy,
405 row_start,
406 x_next,
407 index,
408 dst,
409 state,
410 combiner_config,
411 );
412 }
413 }
414}
415
416#[inline(always)]
417fn grid_cellular_fill_block<
418 A: Arch,
419 C: Combiner,
420 const INIT: bool,
421 const FINAL: bool,
422 const IS_TAIL: bool,
423>(
424 grid_data: &GridData<2>,
425 jit: &CellJitters,
426 dysq: &[MaybeUninit<Simd<f32, A>>; 12],
427 weight_vec: Simd<f32, A>,
428 sy: f32,
429 row_start: usize,
430 x_next: usize,
431 index: usize,
432 dst: &mut [f32],
433 state: &mut [f32],
434 combiner_config: &C::Config,
435) {
436 let lanes = if IS_TAIL {
437 x_next - index
438 } else {
439 Simd::<f32, A>::LANES
440 };
441 let sample_start = row_start + index;
442 let sample_end = sample_start + lanes;
443
444 let sx: Simd<f32, A> = unsafe { grid_data.distances[0].load_simd(index) };
445
446 let mut min_sq = Simd::<f32, A>::splat(f32::MAX);
447 for c in 0..4 {
448 let jx = Simd::<f32, A>::splat(unsafe { (*jit.parts.add(c * 2)).assume_init() });
449 let dy_sq = unsafe { *dysq[c].assume_init_ref() };
450 let dx = sx - jx;
451 min_sq = min_sq.min(dx.mul_add(dx, dy_sq));
452 }
453
454 let x_edge_lo = sx + Simd::<f32, A>::splat(0.5);
455 let x_edge_hi = Simd::<f32, A>::splat(1.5) - sx;
456 let y_edge_lo = Simd::<f32, A>::splat(sy + 0.5);
457 let y_edge_hi = Simd::<f32, A>::splat(1.5 - sy);
458
459 let near_sq = {
460 let edge = x_edge_lo.min(y_edge_lo);
461 edge * edge
462 };
463 let far_sq = {
464 let edge = x_edge_hi.min(y_edge_hi);
465 edge * edge
466 };
467 let any_near = min_sq.simd_gt(near_sq).to_bits() != 0;
468 let any_far = min_sq.simd_gt(far_sq).to_bits() != 0;
469
470 if any_near {
471 for c in 4..8 {
472 let jx = Simd::<f32, A>::splat(unsafe { (*jit.parts.add(c * 2)).assume_init() });
473 let dy_sq = unsafe { *dysq[c].assume_init_ref() };
474 let dx = sx - jx;
475 min_sq = min_sq.min(dx.mul_add(dx, dy_sq));
476 }
477 }
478
479 if any_far {
480 for c in 8..12 {
481 let jx = Simd::<f32, A>::splat(unsafe { (*jit.parts.add(c * 2)).assume_init() });
482 let dy_sq = unsafe { *dysq[c].assume_init_ref() };
483 let dx = sx - jx;
484 min_sq = min_sq.min(dx.mul_add(dx, dy_sq));
485 }
486 }
487
488 let raw_val = min_sq.sqrt() * weight_vec;
489
490 let (cur_state, mut result) = if INIT {
491 C::initialize_sample(combiner_config, raw_val)
492 } else {
493 let mut cur_state = C::State::<A>::default();
494 for i in 0..C::State::<A>::STATE_SIZE {
495 let offset = i * grid_data.total_size;
496 cur_state[i] = unsafe {
497 maybe_tail_load::<A, IS_TAIL>(sample_start + offset..sample_end + offset, state)
498 };
499 }
500 let cur_result = unsafe { maybe_tail_load::<A, IS_TAIL>(sample_start..sample_end, dst) };
501 C::apply_sample(combiner_config, cur_state, cur_result, raw_val)
502 };
503
504 if !FINAL {
505 for i in 0..C::State::<A>::STATE_SIZE {
506 let offset = i * grid_data.total_size;
507 unsafe {
508 maybe_tail_store::<A, IS_TAIL>(
509 sample_start + offset..sample_end + offset,
510 cur_state[i],
511 state,
512 );
513 }
514 }
515 }
516
517 if FINAL {
518 result = C::finalize_sample(combiner_config, cur_state, result);
519 }
520
521 unsafe {
522 maybe_tail_store::<A, IS_TAIL>(sample_start..sample_end, result, dst);
523 }
524}
525
526#[cfg(test)]
527mod tests {
528 use super::*;
529 use crate::api::seed::gen_octave_seed;
530 use crate::math::random::Random;
531 use crate::simd::StaticArch;
532 use crate::{Cellular, Fbm, Grid};
533
534 #[test]
535 fn cellular_grid_2d_sanity() {
536 let grid = Grid::<2>::new(32, 32);
537 let mut result = [0.0; 1024];
538 grid.builder::<Fbm, Cellular>().fill(result.as_mut_slice());
539 verify_slice(result.as_slice());
540 }
541
542 fn verify_slice(slice: &[f32]) {
543 let mut min = f32::MAX;
544 let mut max = f32::NEG_INFINITY;
545 let mut dif_total = 0.0;
546 let mut prev = slice[0];
547
548 for val in slice.iter() {
549 min = val.min(min);
550 max = val.max(max);
551
552 let dif = (*val - prev).abs();
553 dif_total += dif;
554 prev = *val;
555 }
556
557 assert!(min >= 0.0, "Cellular distance of {min} was negative!");
558 assert!(max < 10.0, "Maximum value of {max} was above 10!");
559 assert!(dif_total > 0.0, "Output is constant of {}!", slice[0]);
560 }
561
562 #[test]
563 fn cellular_grid_2d_reference() {
564 let seed = 123456789i64;
565
566 for freq in [
567 1.0 / 32.0,
568 1.0 / 8.0,
569 1.0 / 6.0,
570 1.0 / 4.0,
571 1.0 / 3.0,
572 1.0 / 2.0,
573 ] {
574 check_reference(64, 64, seed, -5.0, 3.0, freq);
575 }
576
577 check_reference(32, 96, seed, -5.0, 3.0, 1.0 / 6.0);
578 }
579
580 fn check_reference(w: usize, h: usize, seed: i64, offset_x: f32, offset_y: f32, freq: f32) {
581 let grid = Grid::<2>::new(w, h)
582 .seed(seed)
583 .sample_position(offset_x as f64, offset_y as f64);
584 let grid_seed = Random::mix_u64(seed as u64);
585 let base_seed = Random::mix_u64_pair(grid_seed, 0xd5e7b3c94f8a1e6b);
586 let octave_seed = gen_octave_seed([freq, freq], base_seed);
587
588 let mut result = vec![0.0; w * h];
589 grid.builder::<Fbm, Cellular>()
590 .frequency(freq)
591 .fill(result.as_mut_slice());
592
593 let mut max_diff = 0.0f32;
594 for y in 0..h {
595 for x in 0..w {
596 let px = (offset_x + x as f32) * freq;
597 let py = (offset_y + y as f32) * freq;
598 let reference = reference_cellular(octave_seed, px, py);
599 let actual = result[y * w + x];
600 max_diff = max_diff.max((actual - reference).abs());
601 }
602 }
603 assert!(
604 max_diff < 1e-4,
605 "Grid cellular at freq {freq} diverges from the brute-force Cellular by {max_diff}"
606 );
607 }
608
609 fn reference_cellular(seed: u32, px: f32, py: f32) -> f32 {
610 let cell_x = px.floor() as i32;
611 let cell_y = py.floor() as i32;
612 let sx = px - px.floor();
613 let sy = py - py.floor();
614
615 let mut min_dist = f32::MAX;
616 for ox in -3..=3 {
617 for oy in -3..=3 {
618 let (jx, jy) = split_hash(hash_cell::<StaticArch>(
619 (cell_x + ox) as u32,
620 (cell_y + oy) as u32,
621 seed,
622 ));
623 let dx = sx - ((ox as f32) + jx);
624 let dy = sy - ((oy as f32) + jy);
625 min_dist = min_dist.min(dx.mul_add(dx, dy * dy));
626 }
627 }
628 min_dist.sqrt()
629 }
630}
631