Skip to main content

quick_noise/noise/generators/cellular/
grid_2d.rs

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
17/// Candidate offsets for the 12 candidates (4 base + 8 ring). The ring is
18/// grouped by bounding edge and stay aligned with the near/far gate
19///        (0,-1) (1,-1)
20/// (-1,0) (0,0) (1,0) (2,0)
21/// (-1,1) (0,1) (1,1) (2,1)
22///        (0,2) (1,2)
23const 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/// Hashes `LANES` consecutive lattice columns from a pre-built `cx_v` vector
143/// at fixed y in one shot
144#[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/// Split a hash into the per-axis jitter offsets. The lower 23 bits
171/// become the x-mantissa and the next 23 bits become the y-mantissa, giving
172/// unform values in the range `[1, 2)`
173#[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
200/// Jitter offsets for the 12 candidates (4 base + 8 ring).
201/// Stored as a flat array of 24 floats: [x0,y0, x1,y1, ..., x11,y11].
202struct 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>(&params, &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        // Pre-fill the 4 rows: top (y-1), sec (y=0), thi (y=1), bot (y=2)
268        let cx_offset = grid_data.grid_start[0] - 1;
269        RowWindow::fill_row::<A>(
270            &params,
271            &grid_data,
272            window.top_mut(),
273            grid_data.grid_start[1] - 1,
274            cx_offset,
275        );
276        RowWindow::fill_row::<A>(
277            &params,
278            &grid_data,
279            window.sec_mut(),
280            grid_data.grid_start[1],
281            cx_offset,
282        );
283        RowWindow::fill_row::<A>(
284            &params,
285            &grid_data,
286            window.thi_mut(),
287            grid_data.grid_start[1] + 1,
288            cx_offset,
289        );
290        RowWindow::fill_row::<A>(
291            &params,
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            // Swap rows: sec->top, thi->sec, bot->thi, old top->bot
332            window.swap();
333
334            // Fill the new bot row
335            RowWindow::fill_row::<A>(
336                &params,
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        // (sy - jy)^2` is identical for every block in this cell segment,
370        // so they are computed once per row instead of once per block.
371        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