summaryrefslogtreecommitdiff
path: root/src/math/root.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/math/root.zig')
-rw-r--r--src/math/root.zig327
1 files changed, 327 insertions, 0 deletions
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");
+}