summaryrefslogtreecommitdiff
path: root/src/vector/geom.zig
blob: b80c55aa9c7c27f532e2ef3a44d59601c3e2ebe6 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
//! Points, affine transforms and cubic Béziers: the only geometry there is.
//! 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 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 };
    }
    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()));
    }
    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 angle = start;
    var from = p0;
    for (0..pieces) |i| {
        const next = angle + step;
        const a: Vec = .{ @cos(angle), @sin(angle) };
        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;
        angle = next;
    }
}

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);
}