diff options
| author | Gabriel Schneider <[email protected]> | 2026-10-30 21:34:41 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-11-12 13:22:02 -0300 |
| commit | 2348776791e9dd17afeb12a06ba42a4a71917bcf (patch) | |
| tree | 780c4b12b76c8b97a28408dd40944d65f159fdc7 /src/math | |
| parent | 590ba7b9b579b97e34b51ab7e3460ebc85713343 (diff) | |
| download | sketchbook-2348776791e9dd17afeb12a06ba42a4a71917bcf.tar.gz sketchbook-2348776791e9dd17afeb12a06ba42a4a71917bcf.zip | |
sketchbook: a drawing layer on top, host fixes for replay and migration
Diffstat (limited to 'src/math')
| -rw-r--r-- | src/math/noise.zig | 157 | ||||
| -rw-r--r-- | src/math/root.zig | 327 |
2 files changed, 484 insertions, 0 deletions
diff --git a/src/math/noise.zig b/src/math/noise.zig new file mode 100644 index 0000000..07764cf --- /dev/null +++ b/src/math/noise.zig @@ -0,0 +1,157 @@ +//! Noise, without a table: see `noise`. +const std = @import("std"); + +/// Smooth noise in 0..1, like Processing's and p5's `noise()`: four octaves +/// of gradient noise, each at twice the frequency and half the weight of the +/// one before, around 0.5. Neighbouring inputs give neighbouring values; one +/// unit is roughly one bump. Pass 0 for unused axes (`noise(seed, t, 0, 0)` +/// is 1D noise). +/// +/// Its spread is Processing's: standard deviation about 0.11 (0.12 in 1D), +/// almost all of it within 0.1..0.9, so `noise → angle` turns all the way +/// round as in the book. Each octave is shifted by an irrational offset, +/// so integer inputs are not special (plain Perlin noise is 0 at every +/// lattice point). The mean is 0.5 (Processing's is about 0.47). +/// +/// No table and no state: the lattice gradients come from hashing the +/// integer coordinates with `seed`, so the seed can be a State field and +/// changing it is free. Only f32 arithmetic and integer hashing, no +/// library calls, so the bits are the same on every target (native and +/// wasm32, Debug and release; tested). Coordinates are clamped to ±1e9. +pub fn noise(seed: u32, x: f32, y: f32, z: f32) f32 { + var sum: f32 = 0; + var weight: f32 = 0.5; + var frequency: f32 = 1; + for (octave_offsets, 0..) |o, octave| { + const s = seed +% @as(u32, @intCast(octave)) *% 0x9e3779b9; + sum += weight * gradient(s, x * frequency + o[0], y * frequency + o[1], z * frequency + o[2]); + weight *= 0.5; + frequency *= 2; + } + // One octave of 3D gradient noise has a deviation of about 0.2; the + // octaves together about 0.16, scaled here to Processing's 0.11. + return std.math.clamp(0.5 + 0.7 * sum, 0, 1); +} + +/// Fractions of multiples of the golden ratio (and of the plastic number, +/// for z): far from every lattice point and from each other. +const octave_offsets = [4][3]f32{ + .{ 0.6180340, 0.3819660, 0.7548777 }, + .{ 0.2360680, 0.7639320, 0.5097553 }, + .{ 0.8541020, 0.1458980, 0.2646330 }, + .{ 0.4721360, 0.5278640, 0.0195106 }, +}; + +/// Ken Perlin's improved noise at one octave, about -1..1, with the +/// permutation table replaced by a hash. +fn gradient(seed: u32, x: f32, y: f32, z: f32) f32 { + const fx = @floor(std.math.clamp(x, -1e9, 1e9)); + const fy = @floor(std.math.clamp(y, -1e9, 1e9)); + const fz = @floor(std.math.clamp(z, -1e9, 1e9)); + const ix: u32 = @bitCast(@as(i32, @intFromFloat(fx))); + const iy: u32 = @bitCast(@as(i32, @intFromFloat(fy))); + const iz: u32 = @bitCast(@as(i32, @intFromFloat(fz))); + const dx = clampUnit(x - fx); + const dy = clampUnit(y - fy); + const dz = clampUnit(z - fz); + const u = fade(dx); + const v = fade(dy); + const w = fade(dz); + const x0 = lerp(grad(lattice(seed, ix, iy, iz), dx, dy, dz), grad(lattice(seed, ix +% 1, iy, iz), dx - 1, dy, dz), u); + const x1 = lerp(grad(lattice(seed, ix, iy +% 1, iz), dx, dy - 1, dz), grad(lattice(seed, ix +% 1, iy +% 1, iz), dx - 1, dy - 1, dz), u); + const x2 = lerp(grad(lattice(seed, ix, iy, iz +% 1), dx, dy, dz - 1), grad(lattice(seed, ix +% 1, iy, iz +% 1), dx - 1, dy, dz - 1), u); + const x3 = lerp(grad(lattice(seed, ix, iy +% 1, iz +% 1), dx, dy - 1, dz - 1), grad(lattice(seed, ix +% 1, iy +% 1, iz +% 1), dx - 1, dy - 1, dz - 1), u); + return lerp(lerp(x0, x1, v), lerp(x2, x3, v), w); +} + +/// Past ±2^24 a float has no fraction left, and rounding may give 1. +fn clampUnit(t: f32) f32 { + return @min(@max(t, 0), 1); +} + +fn fade(t: f32) f32 { + return t * t * t * (t * (t * 6 - 15) + 10); +} + +fn lerp(a: f32, b: f32, t: f32) f32 { + return a + t * (b - a); +} + +/// A well-mixed 32-bit hash of a lattice point (lowbias32's finalizer). +fn lattice(seed: u32, x: u32, y: u32, z: u32) u32 { + var h = seed ^ (x *% 0x8da6b343) ^ (y *% 0xd8163841) ^ (z *% 0xcb1ab31f); + h ^= h >> 16; + h *%= 0x7feb352d; + h ^= h >> 15; + h *%= 0x846ca68b; + h ^= h >> 16; + return h; +} + +/// One of Perlin's 12 edge gradients (4 of them twice), dotted with the +/// offset. +fn grad(hash: u32, x: f32, y: f32, z: f32) f32 { + const h = hash >> 28; + const u = if (h < 8) x else y; + const v = if (h < 4) y else if (h == 12 or h == 14) x else z; + return (if (h & 1 == 0) u else -u) + (if (h & 2 == 0) v else -v); +} + +/// Golden values, as bits: the test runs on native targets and, through +/// `zig build test`, on wasm32-wasi too, so a change in either shows. +const noise_goldens = [_]struct { seed: u32, p: [3]f32, bits: u32 }{ + .{ .seed = 0, .p = .{ 0, 0, 0 }, .bits = 0x3f14f2bf }, + .{ .seed = 0, .p = .{ 0.5, 0, 0 }, .bits = 0x3ef55b7e }, + .{ .seed = 1, .p = .{ 0.3, 0.7, 0 }, .bits = 0x3f01da7c }, + .{ .seed = 7, .p = .{ 12.25, -3.5, 0.125 }, .bits = 0x3efb37d9 }, + .{ .seed = 42, .p = .{ 1000.1, 2000.2, 3.3 }, .bits = 0x3f142994 }, + .{ .seed = 0xdeadbeef, .p = .{ -0.01, 5.5, 99.9 }, .bits = 0x3edcff5c }, +}; + +test "noise is smooth, in 0..1, and the same bits everywhere" { + var lo: f32 = 1; + var hi: f32 = 0; + var previous = noise(3, 0, 0, 1.5); + for (1..4000) |i| { + const t = @as(f32, @floatFromInt(i)) * 0.01; + const n = noise(3, t, t * 0.5, 1.5); + try std.testing.expect(n >= 0 and n <= 1); + try std.testing.expect(@abs(n - previous) < 0.1); + lo = @min(lo, n); + hi = @max(hi, n); + previous = n; + } + try std.testing.expect(hi - lo > 0.5); + try std.testing.expect(noise(1, 0.3, 0.7, 0) != noise(2, 0.3, 0.7, 0)); + for (noise_goldens) |g| { + const n = noise(g.seed, g.p[0], g.p[1], g.p[2]); + std.testing.expectEqual(g.bits, @as(u32, @bitCast(n))) catch |err| { + std.debug.print("noise({d}, {d}, {d}, {d}) = {d} (0x{x})\n", .{ g.seed, g.p[0], g.p[1], g.p[2], n, @as(u32, @bitCast(n)) }); + return err; + }; + } +} + +test "noise has Processing's spread, and lattice points are not special" { + // Processing's noise() on this grid (flow_field's, 0.1 apart, z = 0): + // deviation 0.111, range 0.08..0.81, over 50 seeds. + var sum: f64 = 0; + var squares: f64 = 0; + var count: f64 = 0; + for (0..50) |seed| for (0..32) |i| for (0..18) |j| { + const v: f64 = noise(@intCast(seed), @as(f32, @floatFromInt(i)) * 0.1, @as(f32, @floatFromInt(j)) * 0.1, 0); + sum += v; + squares += v * v; + count += 1; + }; + const mean = sum / count; + const deviation = @sqrt(squares / count - mean * mean); + try std.testing.expect(@abs(mean - 0.5) < 0.02); + try std.testing.expect(deviation > 0.095 and deviation < 0.13); + var at_half: u32 = 0; + for (0..100) |i| { + const v = noise(9, @floatFromInt(i), @floatFromInt(i * 7 % 13), 0); + if (v == 0.5) at_half += 1; + } + try std.testing.expectEqual(@as(u32, 0), at_half); +} diff --git a/src/math/root.zig b/src/math/root.zig new file mode 100644 index 0000000..f9f2ffe --- /dev/null +++ b/src/math/root.zig @@ -0,0 +1,327 @@ +//! Points, vectors, affine transforms, cubic Béziers and noise: the one +//! geometry module, `sk.math` in sketches and `vector.geom` in the vector +//! library. Pure functions over `@Vector(2, f32)`, so `+`, `-`, `*` and +//! `+=` work on points directly, as on a shader's `vec2`. +//! +//! In the vector library every path is a list of cubics, lines included, as +//! in manim: one shape of data makes morphing and partial drawing plain +//! arithmetic. +const std = @import("std"); + +pub const Vec = @Vector(2, f32); + +pub fn vec(x: f32, y: f32) Vec { + return .{ x, y }; +} +pub fn dot(a: Vec, b: Vec) f32 { + return @reduce(.Add, a * b); +} +pub fn cross(a: Vec, b: Vec) f32 { + return a[0] * b[1] - a[1] * b[0]; +} +pub fn length(a: Vec) f32 { + return @sqrt(dot(a, a)); +} +pub fn splat(s: f32) Vec { + return @splat(s); +} +pub fn mix(a: Vec, b: Vec, t: f32) Vec { + return a + (b - a) * splat(t); +} +/// Perpendicular, rotated a quarter turn counterclockwise in y-down space. +pub fn perp(a: Vec) Vec { + return .{ a[1], -a[0] }; +} +pub fn normalize(a: Vec) Vec { + const l = length(a); + return if (l > 0) a / splat(l) else a; +} +/// `a` times `k`: Zig does not broadcast a scalar over a vector. +pub fn scale(a: Vec, k: f32) Vec { + return a * splat(k); +} +pub fn distance(a: Vec, b: Vec) f32 { + return length(b - a); +} +/// `a` in the same direction, `len` long; zero stays zero. PVector's `setMag`. +pub fn withLength(a: Vec, len: f32) Vec { + return scale(normalize(a), len); +} +/// `a`, shortened to `max` if longer. PVector's `limit`. +pub fn clampLength(a: Vec, max: f32) Vec { + const l2 = dot(a, a); + return if (l2 > max * max) scale(a, max / @sqrt(l2)) else a; +} +/// The direction of `a` in radians, from +x toward +y (clockwise on a +/// y-down screen). PVector's `heading`. Not for shader code: `atan2` is +/// table-driven, which SPIR-V's logical addressing forbids. +pub fn angle(a: Vec) f32 { + return std.math.atan2(a[1], a[0]); +} +/// The unit vector at `radians`. PVector's `fromAngle`. +pub fn unit(radians: f32) Vec { + return .{ @cos(radians), @sin(radians) }; +} + +/// `[a c e; b d f]`, SVG's `matrix(a b c d e f)`. +pub const Affine = struct { + a: f32 = 1, + b: f32 = 0, + c: f32 = 0, + d: f32 = 1, + e: f32 = 0, + f: f32 = 0, + + pub const identity: Affine = .{}; + + pub fn translate(x: f32, y: f32) Affine { + return .{ .e = x, .f = y }; + } + pub fn scale(sx: f32, sy: f32) Affine { + return .{ .a = sx, .d = sy }; + } + pub fn rotate(radians: f32) Affine { + const c = @cos(radians); + const s = @sin(radians); + return .{ .a = c, .b = s, .c = -s, .d = c }; + } + /// Moves the origin to `at`, turned by `radians`: Processing's + /// `translate(at); rotate(radians)`. + pub fn place(at: Vec, radians: f32) Affine { + var m = rotate(radians); + m.e = at[0]; + m.f = at[1]; + return m; + } + pub fn skew(x: f32, y: f32) Affine { + return .{ .b = @tan(y), .c = @tan(x) }; + } + /// `self` after `inner`: apply `inner` first. + pub fn mul(self: Affine, inner: Affine) Affine { + return .{ + .a = self.a * inner.a + self.c * inner.b, + .b = self.b * inner.a + self.d * inner.b, + .c = self.a * inner.c + self.c * inner.d, + .d = self.b * inner.c + self.d * inner.d, + .e = self.a * inner.e + self.c * inner.f + self.e, + .f = self.b * inner.e + self.d * inner.f + self.f, + }; + } + pub fn apply(m: Affine, p: Vec) Vec { + return .{ m.a * p[0] + m.c * p[1] + m.e, m.b * p[0] + m.d * p[1] + m.f }; + } + pub fn applyVector(m: Affine, p: Vec) Vec { + return .{ m.a * p[0] + m.c * p[1], m.b * p[0] + m.d * p[1] }; + } + pub fn determinant(m: Affine) f32 { + return m.a * m.d - m.b * m.c; + } + /// How much the transform scales lengths, on average. + pub fn scaleFactor(m: Affine) f32 { + return @sqrt(@abs(m.determinant())); + } + /// How much the transform stretches lengths at most, nearly: the + /// longer of its two axes. + pub fn maxScale(m: Affine) f32 { + return @max(@sqrt(m.a * m.a + m.b * m.b), @sqrt(m.c * m.c + m.d * m.d)); + } + pub fn invert(m: Affine) Affine { + const det = m.determinant(); + if (det == 0) return .{}; + const i = 1 / det; + return .{ + .a = m.d * i, + .b = -m.b * i, + .c = -m.c * i, + .d = m.a * i, + .e = (m.c * m.f - m.d * m.e) * i, + .f = (m.b * m.e - m.a * m.f) * i, + }; + } +}; + +pub const Rect = struct { + x: f32 = 0, + y: f32 = 0, + w: f32 = 0, + h: f32 = 0, + + pub fn center(r: Rect) Vec { + return .{ r.x + r.w / 2, r.y + r.h / 2 }; + } +}; + +/// Growing bounds over points. +pub const Bounds = struct { + min: Vec = splat(std.math.inf(f32)), + max: Vec = splat(-std.math.inf(f32)), + + pub fn add(b: *Bounds, p: Vec) void { + b.min = @min(b.min, p); + b.max = @max(b.max, p); + } + pub fn empty(b: Bounds) bool { + return b.min[0] > b.max[0]; + } + pub fn rect(b: Bounds) Rect { + if (b.empty()) return .{}; + return .{ .x = b.min[0], .y = b.min[1], .w = b.max[0] - b.min[0], .h = b.max[1] - b.min[1] }; + } +}; + +/// A cubic's four control points. +pub const Cubic = [4]Vec; + +pub fn line(a: Vec, b: Vec) Cubic { + return .{ a, mix(a, b, 1.0 / 3.0), mix(a, b, 2.0 / 3.0), b }; +} + +pub fn quad(a: Vec, c: Vec, b: Vec) Cubic { + return .{ a, mix(a, c, 2.0 / 3.0), mix(b, c, 2.0 / 3.0), b }; +} + +pub fn eval(c: Cubic, t: f32) Vec { + const u = 1 - t; + return c[0] * splat(u * u * u) + c[1] * splat(3 * u * u * t) + c[2] * splat(3 * u * t * t) + c[3] * splat(t * t * t); +} + +/// de Casteljau: the two halves of `c` at `t`. +pub fn split(c: Cubic, t: f32) [2]Cubic { + const ab = mix(c[0], c[1], t); + const bc = mix(c[1], c[2], t); + const cd = mix(c[2], c[3], t); + const abc = mix(ab, bc, t); + const bcd = mix(bc, cd, t); + const p = mix(abc, bcd, t); + return .{ .{ c[0], ab, abc, p }, .{ p, bcd, cd, c[3] } }; +} + +/// Line segments needed to stay within `tolerance` of the curve. +pub fn flattenCount(c: Cubic, tolerance: f32) u32 { + const d1 = c[0] - splat(2) * c[1] + c[2]; + const d2 = c[1] - splat(2) * c[2] + c[3]; + const dd = @max(length(d1), length(d2)); + const n = @ceil(@sqrt(0.75 * dd / tolerance)); + return @intFromFloat(std.math.clamp(n, 1, 256)); +} + +/// A cheap length estimate: between chord and control polygon. +pub fn roughLength(c: Cubic) f32 { + const chord = length(c[3] - c[0]); + const polygon = length(c[1] - c[0]) + length(c[2] - c[1]) + length(c[3] - c[2]); + return (chord + polygon) / 2; +} + +/// Cubics for an SVG elliptical arc from `p0` to `p1` (endpoint form). +pub fn arc(out: *std.ArrayList(Cubic), gpa: std.mem.Allocator, p0: Vec, radii: Vec, x_rotation_degrees: f32, large: bool, sweep: bool, p1: Vec) !void { + var rx = @abs(radii[0]); + var ry = @abs(radii[1]); + if (rx == 0 or ry == 0 or @reduce(.And, p0 == p1)) { + if (!@reduce(.And, p0 == p1)) try out.append(gpa, line(p0, p1)); + return; + } + const phi = x_rotation_degrees * std.math.pi / 180; + const cos_phi = @cos(phi); + const sin_phi = @sin(phi); + const half = (p0 - p1) / splat(2); + const x1 = cos_phi * half[0] + sin_phi * half[1]; + const y1 = -sin_phi * half[0] + cos_phi * half[1]; + // Radii too small to reach are scaled up, as the SVG spec says. + const lambda = (x1 * x1) / (rx * rx) + (y1 * y1) / (ry * ry); + if (lambda > 1) { + rx *= @sqrt(lambda); + ry *= @sqrt(lambda); + } + const num = rx * rx * ry * ry - rx * rx * y1 * y1 - ry * ry * x1 * x1; + const den = rx * rx * y1 * y1 + ry * ry * x1 * x1; + var coef = @sqrt(@max(0, num / den)); + if (large == sweep) coef = -coef; + const cx1 = coef * rx * y1 / ry; + const cy1 = -coef * ry * x1 / rx; + const mid = (p0 + p1) / splat(2); + const center: Vec = .{ cos_phi * cx1 - sin_phi * cy1 + mid[0], sin_phi * cx1 + cos_phi * cy1 + mid[1] }; + const start = std.math.atan2((y1 - cy1) / ry, (x1 - cx1) / rx); + var delta = std.math.atan2((-y1 - cy1) / ry, (-x1 - cx1) / rx) - start; + if (sweep and delta < 0) delta += 2 * std.math.pi; + if (!sweep and delta > 0) delta -= 2 * std.math.pi; + const pieces: u32 = @intFromFloat(@max(1, @ceil(@abs(delta) / (std.math.pi / 2.0) - 1e-4))); + const step = delta / @as(f32, @floatFromInt(pieces)); + const k = 4.0 / 3.0 * @tan(step / 4); + const m: Affine = (Affine{ .a = cos_phi, .b = sin_phi, .c = -sin_phi, .d = cos_phi, .e = center[0], .f = center[1] }).mul(.scale(rx, ry)); + var theta = start; + var from = p0; + for (0..pieces) |i| { + const next = theta + step; + const a: Vec = .{ @cos(theta), @sin(theta) }; + const b: Vec = .{ @cos(next), @sin(next) }; + const to = if (i + 1 == pieces) p1 else m.apply(b); + try out.append(gpa, .{ from, m.apply(a + perp(a) * splat(-k)), m.apply(b - perp(b) * splat(-k)), to }); + from = to; + theta = next; + } +} + +pub const noise = @import("noise.zig").noise; + +/// A float in `lo..hi`: Processing's `random(lo, hi)`. `r` is any +/// `std.Random` (keep a concrete `std.Random.Xoshiro256` in State and pass +/// `s.rng.random()`); this only saves spelling out the lerp. +pub fn uniform(r: std.Random, lo: f32, hi: f32) f32 { + return std.math.lerp(lo, hi, r.float(f32)); +} + +/// A unit vector in a uniformly random direction: `PVector.random2D()`. +pub fn randomUnit(r: std.Random) Vec { + return unit(uniform(r, 0, std.math.tau)); +} + +test "affine composition and inversion round trip" { + const m = Affine.translate(10, 5).mul(.rotate(0.7)).mul(.scale(2, 3)); + const p = vec(3, -4); + const q = m.invert().apply(m.apply(p)); + try std.testing.expectApproxEqAbs(p[0], q[0], 1e-4); + try std.testing.expectApproxEqAbs(p[1], q[1], 1e-4); +} + +test "a half-circle arc stays on the circle" { + var cubics: std.ArrayList(Cubic) = .empty; + defer cubics.deinit(std.testing.allocator); + try arc(&cubics, std.testing.allocator, vec(-10, 0), vec(10, 10), 0, false, true, vec(10, 0)); + try std.testing.expectEqual(@as(usize, 2), cubics.items.len); + for (cubics.items) |c| for (0..9) |i| { + const r = length(eval(c, @as(f32, @floatFromInt(i)) / 8)); + try std.testing.expectApproxEqAbs(@as(f32, 10), r, 0.03); + }; + // Sweep flag 1 in y-down space goes through negative y. + try std.testing.expect(eval(cubics.items[0], 1)[1] < -9.9); +} + +test "vector helpers" { + const v = vec(3, 4); + try std.testing.expectEqual(@as(f32, 5), length(v)); + try std.testing.expectEqual(vec(6, 8), scale(v, 2)); + try std.testing.expectEqual(@as(f32, 5), distance(.{ 0, 0 }, v)); + try std.testing.expectApproxEqAbs(@as(f32, 10), length(withLength(v, 10)), 1e-5); + try std.testing.expectEqual(vec(0, 0), withLength(.{ 0, 0 }, 3)); + try std.testing.expectApproxEqAbs(@as(f32, 2.5), length(clampLength(v, 2.5)), 1e-5); + try std.testing.expectEqual(v, clampLength(v, 7)); + try std.testing.expectApproxEqAbs(@as(f32, std.math.pi / 2.0), angle(.{ 0, 1 }), 1e-6); + const u = unit(angle(v)); + try std.testing.expectApproxEqAbs(@as(f32, 0.6), u[0], 1e-6); + const p = Affine.place(.{ 10, 20 }, std.math.pi / 2.0).apply(.{ 1, 0 }); + try std.testing.expectApproxEqAbs(@as(f32, 10), p[0], 1e-5); + try std.testing.expectApproxEqAbs(@as(f32, 21), p[1], 1e-5); +} + +test "uniform stays in range and randomUnit is unit length" { + var prng: std.Random.Xoshiro256 = .init(3); + for (0..1000) |_| { + const x = uniform(prng.random(), -2, 5); + try std.testing.expect(x >= -2 and x < 5); + try std.testing.expectApproxEqAbs(@as(f32, 1), length(randomUnit(prng.random())), 1e-5); + } +} + +test { + _ = @import("noise.zig"); +} |
