1// Copyright 2020 the Resvg Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4#![allow(clippy::needless_range_loop)]
5
6use super::{f32_bound, ImageRefMut};
7use usvg::ApproxZeroUlps;
8
9const RAND_M: i32 = 2147483647; // 2**31 - 1
10const RAND_A: i32 = 16807; // 7**5; primitive root of m
11const RAND_Q: i32 = 127773; // m / a
12const RAND_R: i32 = 2836; // m % a
13const B_SIZE: usize = 0x100;
14const B_SIZE_32: i32 = 0x100;
15const B_LEN: usize = B_SIZE + B_SIZE + 2;
16const BM: i32 = 0xff;
17const PERLIN_N: i32 = 0x1000;
18
19#[derive(Clone, Copy)]
20struct StitchInfo {
21 width: i32, // How much to subtract to wrap for stitching.
22 height: i32,
23 wrap_x: i32, // Minimum value to wrap.
24 wrap_y: i32,
25}
26
27/// Applies a turbulence filter.
28///
29/// `dest` image pixels will have an **unpremultiplied alpha**.
30///
31/// - `offset_x` and `offset_y` indicate filter region offset.
32/// - `sx` and `sy` indicate canvas scale.
33pub fn apply(
34 offset_x: f64,
35 offset_y: f64,
36 sx: f64,
37 sy: f64,
38 base_frequency_x: f64,
39 base_frequency_y: f64,
40 num_octaves: u32,
41 seed: i32,
42 stitch_tiles: bool,
43 fractal_noise: bool,
44 dest: ImageRefMut,
45) {
46 let (lattice_selector, gradient) = init(seed);
47 let width = dest.width;
48 let height = dest.height;
49 let mut x = 0;
50 let mut y = 0;
51 for pixel in dest.data.iter_mut() {
52 let turb = |channel| {
53 let (tx, ty) = ((x as f64 + offset_x) / sx, (y as f64 + offset_y) / sy);
54 let n = turbulence(
55 channel,
56 tx,
57 ty,
58 x as f64,
59 y as f64,
60 width as f64,
61 height as f64,
62 base_frequency_x,
63 base_frequency_y,
64 num_octaves,
65 fractal_noise,
66 stitch_tiles,
67 &lattice_selector,
68 &gradient,
69 );
70
71 let n = if fractal_noise {
72 (n * 255.0 + 255.0) / 2.0
73 } else {
74 n * 255.0
75 };
76
77 (f32_bound(0.0, n as f32, 255.0) + 0.5) as u8
78 };
79
80 pixel.r = turb(0);
81 pixel.g = turb(1);
82 pixel.b = turb(2);
83 pixel.a = turb(3);
84
85 x += 1;
86 if x == dest.width {
87 x = 0;
88 y += 1;
89 }
90 }
91}
92
93fn init(mut seed: i32) -> (Vec<usize>, Vec<Vec<Vec<f64>>>) {
94 let mut lattice_selector = vec![0; B_LEN];
95 let mut gradient = vec![vec![vec![0.0; 2]; B_LEN]; 4];
96
97 if seed <= 0 {
98 seed = -seed % (RAND_M - 1) + 1;
99 }
100
101 if seed > RAND_M - 1 {
102 seed = RAND_M - 1;
103 }
104
105 for k in 0..4 {
106 for i in 0..B_SIZE {
107 lattice_selector[i] = i;
108 for j in 0..2 {
109 seed = random(seed);
110 gradient[k][i][j] =
111 ((seed % (B_SIZE_32 + B_SIZE_32)) - B_SIZE_32) as f64 / B_SIZE_32 as f64;
112 }
113
114 let s = (gradient[k][i][0] * gradient[k][i][0] + gradient[k][i][1] * gradient[k][i][1])
115 .sqrt();
116
117 gradient[k][i][0] /= s;
118 gradient[k][i][1] /= s;
119 }
120 }
121
122 for i in (1..B_SIZE).rev() {
123 let k = lattice_selector[i];
124 seed = random(seed);
125 let j = (seed % B_SIZE_32) as usize;
126 lattice_selector[i] = lattice_selector[j];
127 lattice_selector[j] = k;
128 }
129
130 for i in 0..B_SIZE + 2 {
131 lattice_selector[B_SIZE + i] = lattice_selector[i];
132 for g in gradient.iter_mut().take(4) {
133 for j in 0..2 {
134 g[B_SIZE + i][j] = g[i][j];
135 }
136 }
137 }
138
139 (lattice_selector, gradient)
140}
141
142fn turbulence(
143 color_channel: usize,
144 mut x: f64,
145 mut y: f64,
146 tile_x: f64,
147 tile_y: f64,
148 tile_width: f64,
149 tile_height: f64,
150 mut base_freq_x: f64,
151 mut base_freq_y: f64,
152 num_octaves: u32,
153 fractal_sum: bool,
154 do_stitching: bool,
155 lattice_selector: &[usize],
156 gradient: &[Vec<Vec<f64>>],
157) -> f64 {
158 // Adjust the base frequencies if necessary for stitching.
159 let mut stitch = if do_stitching {
160 // When stitching tiled turbulence, the frequencies must be adjusted
161 // so that the tile borders will be continuous.
162 if !base_freq_x.approx_zero_ulps(4) {
163 let lo_freq = (tile_width * base_freq_x).floor() / tile_width;
164 let hi_freq = (tile_width * base_freq_x).ceil() / tile_width;
165 if base_freq_x / lo_freq < hi_freq / base_freq_x {
166 base_freq_x = lo_freq;
167 } else {
168 base_freq_x = hi_freq;
169 }
170 }
171
172 if !base_freq_y.approx_zero_ulps(4) {
173 let lo_freq = (tile_height * base_freq_y).floor() / tile_height;
174 let hi_freq = (tile_height * base_freq_y).ceil() / tile_height;
175 if base_freq_y / lo_freq < hi_freq / base_freq_y {
176 base_freq_y = lo_freq;
177 } else {
178 base_freq_y = hi_freq;
179 }
180 }
181
182 // Set up initial stitch values.
183 let width = (tile_width * base_freq_x + 0.5) as i32;
184 let height = (tile_height * base_freq_y + 0.5) as i32;
185 let wrap_x = (tile_x * base_freq_x + PERLIN_N as f64 + width as f64) as i32;
186 let wrap_y = (tile_y * base_freq_y + PERLIN_N as f64 + height as f64) as i32;
187 Some(StitchInfo {
188 width,
189 height,
190 wrap_x,
191 wrap_y,
192 })
193 } else {
194 None
195 };
196
197 let mut sum = 0.0;
198 x *= base_freq_x;
199 y *= base_freq_y;
200 let mut ratio = 1.0;
201 for _ in 0..num_octaves {
202 if fractal_sum {
203 sum += noise2(color_channel, x, y, lattice_selector, gradient, stitch) / ratio;
204 } else {
205 sum += noise2(color_channel, x, y, lattice_selector, gradient, stitch).abs() / ratio;
206 }
207 x *= 2.0;
208 y *= 2.0;
209 ratio *= 2.0;
210
211 if let Some(ref mut stitch) = stitch {
212 // Update stitch values. Subtracting PerlinN before the multiplication and
213 // adding it afterward simplifies to subtracting it once.
214 stitch.width *= 2;
215 stitch.wrap_x = 2 * stitch.wrap_x - PERLIN_N;
216 stitch.height *= 2;
217 stitch.wrap_y = 2 * stitch.wrap_y - PERLIN_N;
218 }
219 }
220
221 sum
222}
223
224fn noise2(
225 color_channel: usize,
226 x: f64,
227 y: f64,
228 lattice_selector: &[usize],
229 gradient: &[Vec<Vec<f64>>],
230 stitch_info: Option<StitchInfo>,
231) -> f64 {
232 let t = x + PERLIN_N as f64;
233 let mut bx0 = t as i32;
234 let mut bx1 = bx0 + 1;
235 let rx0 = t - t as i64 as f64;
236 let rx1 = rx0 - 1.0;
237 let t = y + PERLIN_N as f64;
238 let mut by0 = t as i32;
239 let mut by1 = by0 + 1;
240 let ry0 = t - t as i64 as f64;
241 let ry1 = ry0 - 1.0;
242
243 // If stitching, adjust lattice points accordingly.
244 if let Some(info) = stitch_info {
245 if bx0 >= info.wrap_x {
246 bx0 -= info.width;
247 }
248
249 if bx1 >= info.wrap_x {
250 bx1 -= info.width;
251 }
252
253 if by0 >= info.wrap_y {
254 by0 -= info.height;
255 }
256
257 if by1 >= info.wrap_y {
258 by1 -= info.height;
259 }
260 }
261
262 bx0 &= BM;
263 bx1 &= BM;
264 by0 &= BM;
265 by1 &= BM;
266 let i = lattice_selector[bx0 as usize];
267 let j = lattice_selector[bx1 as usize];
268 let b00 = lattice_selector[i + by0 as usize];
269 let b10 = lattice_selector[j + by0 as usize];
270 let b01 = lattice_selector[i + by1 as usize];
271 let b11 = lattice_selector[j + by1 as usize];
272 let sx = s_curve(rx0);
273 let sy = s_curve(ry0);
274 let q = &gradient[color_channel][b00];
275 let u = rx0 * q[0] + ry0 * q[1];
276 let q = &gradient[color_channel][b10];
277 let v = rx1 * q[0] + ry0 * q[1];
278 let a = lerp(sx, u, v);
279 let q = &gradient[color_channel][b01];
280 let u = rx0 * q[0] + ry1 * q[1];
281 let q = &gradient[color_channel][b11];
282 let v = rx1 * q[0] + ry1 * q[1];
283 let b = lerp(sx, u, v);
284 lerp(sy, a, b)
285}
286
287fn random(seed: i32) -> i32 {
288 let mut result: i32 = RAND_A * (seed % RAND_Q) - RAND_R * (seed / RAND_Q);
289 if result <= 0 {
290 result += RAND_M;
291 }
292
293 result
294}
295
296#[inline]
297fn s_curve(t: f64) -> f64 {
298 t * t * (3.0 - 2.0 * t)
299}
300
301#[inline]
302fn lerp(t: f64, a: f64, b: f64) -> f64 {
303 a + t * (b - a)
304}
305